¿Qué es un buen asignador de memoria C para sistemas integrados?

Question

Tengo una sola aplicación integrada con subprocesos que asigna y desasigna muchos y pequeños bloques (32-64b). El escenario perfecto para un asignador basado en caché. Y aunque podría INTENTAR escribir uno, probablemente sea una pérdida de tiempo, y no tan probado y sintonizado como una solución que ya ha estado en primera línea.

Entonces, ¿cuál sería el mejor asignador que podría usar para este escenario?

Nota: Estoy usando una máquina virtual Lua en el sistema (que es el culpable de más del 80% de las asignaciones), así que no puedo refactorizar trivialmente mi código para usar asignaciones de pila para aumentar el rendimiento de la asignación.

Answer 1

Hice algunas investigaciones sobre este tema recientemente, ya que tuvimos un problema con la fragmentación de la memoria. Al final, decidimos quedarnos con la implementación de libc de GNU y agregar algunas agrupaciones de memoria a nivel de aplicación donde sea necesario. Hubo otros asignadores que tenían un mejor comportamiento de fragmentación, pero no fuimos lo suficientemente cómodos con ellos para reemplazar malloc a nivel mundial. GNU tiene el beneficio de una larga historia detrás de esto.

En su caso, parece justificado; suponiendo que no puede arreglar la VM, esas pequeñas asignaciones son muy derrochadoras. No sé cuál es su entorno completo, pero podría considerar envolver las llamadas a malloc/realloc/free solo en la máquina virtual para que pueda pasarlo a un controlador diseñado para pequeñas agrupaciones.

Answer 2

En un proyecto anterior en C en el que trabajé, emprendimos el camino de implementar nuestras propias rutinas de administración de memoria para una biblioteca que se ejecutaba en una amplia gama de plataformas, incluidos los sistemas integrados. La biblioteca también asignó y liberó una gran cantidad de pequeños buffers. Funcionó relativamente bien y no requirió una gran cantidad de código para implementar. Puedo darte un poco de información sobre esa implementación en caso de que quieras desarrollar algo tú mismo.

La implementación básica incluía un conjunto de rutinas que gestionaba búferes de un tamaño determinado. Las rutinas se usaron como envoltorios alrededor de malloc() y free(). Utilizamos estas rutinas para administrar la asignación de las estructuras que utilizamos con frecuencia y también para administrar los almacenamientos intermedios genéricos de los tamaños establecidos. Se utilizó una estructura para describir cada tipo de memoria intermedia que se gestiona. Cuando se asignaba un búfer de un tipo específico, malloc() la memoria en bloques (si una lista de búferes libres estaba vacía). IE, si estuviéramos gestionando buffers de 10 bytes, podríamos crear un solo malloc() que contuviera espacio para 100 de estos buffers para reducir la fragmentación y el número de mallocs subyacentes necesarios.

En la parte frontal de cada memoria tampón se usaría un puntero para encadenar los almacenamientos intermedios en una lista libre. Cuando se asignaron los 100 búferes, cada búfer se encadenaría en la lista libre. Cuando el búfer estaba en uso, el puntero se establecería en nulo. También mantuvimos una lista de los "bloques" de almacenamientos intermedios, de modo que pudiéramos hacer una limpieza simple llamando a free() en cada uno de los buffers malloc'd reales.

Para gestionar los tamaños de búfer dinámicos, también agregamos una variable size_t al principio de cada búfer que indica el tamaño del búfer. Esto se usó para identificar qué bloque de almacenamiento intermedio volver a poner en el búfer cuando se liberó. Teníamos rutinas de reemplazo para malloc() y free() que hacía aritmética de puntero para obtener el tamaño del búfer y luego poner el búfer en la lista libre. También teníamos un límite sobre la cantidad de búferes que manejamos. Los búferes más grandes que este límite simplemente se malloc'd y se pasaron al usuario. Para las estructuras que administramos, creamos rutinas contenedoras para la asignación y liberación de las estructuras específicas.

Eventualmente también desarrollamos el sistema para incluir la recolección de basura cuando el usuario lo solicita para limpiar la memoria no utilizada. Como teníamos el control de todo el sistema, hubo varias optimizaciones que pudimos realizar a lo largo del tiempo para aumentar el rendimiento del sistema. Como mencioné, funcionó bastante bien.

Answer 3

Aunque ha pasado un tiempo desde que pregunté esto, mi solución final fue utilizar SmallObjectAllocator de LoKi. Funcionó muy bien. Deshizo todas las llamadas del sistema operativo y mejoró el rendimiento de mi motor Lua para dispositivos integrados. ¡Muy agradable y simple, y solo 5 minutos de trabajo!

Answer 4

Desde version 5.1, Lua ha permitido que custom allocator se establezca cuando creating new states.

Answer 5

También me gustaría añadir algo a esto a pesar de que es un hilo viejo. En una aplicación integrada si puede analizar el uso de la memoria para su aplicación y obtener una cantidad máxima de asignación de memoria de los distintos tamaños, generalmente el tipo más rápido de asignador es uno que usa agrupaciones de memoria. En nuestras aplicaciones integradas podemos determinar todos los tamaños de asignación que alguna vez se necesitarán durante el tiempo de ejecución. Si puede hacer esto, puede eliminar por completo la fragmentación del montón y tener asignaciones muy rápidas. La mayoría de estas implementaciones tienen un grupo de desbordamiento que hará un malloc regular para los casos especiales que, con suerte, serán lejanos y pocos si hiciste tu análisis correctamente.

Answer 6

He usado el sistema 'binary buddy' con buen efecto en vxworks. Básicamente, repartes tu montón cortando bloques a la mitad para obtener la potencia más pequeña de dos bloques de tamaño para mantener tu pedido, y cuando los bloques se liberan, puedes hacer un pase por el árbol para fusionar los bloques nuevamente para mitigar la fragmentación. Una búsqueda en Google debería mostrar toda la información que necesita.

Answer 7

estoy un poco tarde a la fiesta, pero sólo quiero compartir asignador de memoria muy eficiente para sistemas embebidos recientemente he encontrado y probado: https://github.com/dimonomid/umm_malloc

Esta es una biblioteca de gestión de memoria diseñada específicamente para trabajar con el ARM7, personalmente lo uso en un dispositivo PIC32, pero debería funcionar en cualquier dispositivo de 16 y 8 bits (tengo planes para probar el PIC24 de 16 bits, pero aún no lo he probado)

La fragmentación con el asignador predeterminado me golpeó seriamente: mi proyecto a menudo asigna bloques de varios tamaños, desde varios bytes hasta varios cientos de bytes, y algunas veces tuve que enfrentar el error de "falta de memoria". Mi dispositivo PIC32 tiene un total de 32K de RAM y 8192 bytes para el montón. En el momento particular, hay más de 5K de memoria libre, pero el asignador predeterminado tiene un bloque de memoria no fragmentado máximo de apenas 700 bytes, debido a la fragmentación. Esto es muy malo, así que decidí buscar una solución más eficiente.

Ya conocía algunas asignaciones, pero todas tienen algunas limitaciones (como el tamaño de bloque debería ser una potencia o 2, y comenzando no desde 2 sino desde, digamos, 128 bytes), o simplemente tenía errores. Cada vez antes, tuve que volver al asignador predeterminado.

Pero esta vez, tengo suerte: he encontrado este uno: Bloque http://hempeldesigngroup.com/embedded/stories/memorymanager/

Cuando probé este asignador de memoria, exactamente en la misma situación con 5K de memoria libre, que tiene más de 3800 bytes ! Fue tan increíble para mí (comparando con 700 bytes), y realicé una prueba dura: el dispositivo funcionó mucho más de 30 horas. No hay pérdidas de memoria, todo funciona como debería funcionar. También encontré este asignador en el repositorio FreeRTOS: http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg=1041#, y este hecho es una evidencia adicional de la estabilidad de umm_malloc. Así que cambié completamente a umm_malloc, y estoy bastante contento con él.

Solo tuve que cambiarlo un poco: la configuración estaba un poco falsa cuando la macro UMM_TEST_MAIN no está definida, así que creé el repositorio github (el enlace está en la parte superior de esta publicación). Ahora, la configuración dependiente del usuario se almacena en un archivo separado umm_malloc_cfg.h

Todavía no he profundizado en los algoritmos aplicados en este asignador, pero tiene una explicación muy detallada de los algoritmos, por lo que cualquier persona que esté interesada puede ver la parte superior del archivo umm_malloc.c. Al menos, el enfoque "binning" debería dar un gran beneficio en menos fragmentación: http://g.oswego.edu/dl/html/malloc.html

Creo que cualquiera que necesite un asignador eficiente de memoria para microcontroladores, al menos debería intentarlo.

Answer 8

Estoy escribiendo un asignador de memoria C llamado tinymem que está destinado a ser capaz de desfragmentar el montón, y reutilizar la memoria. Compruébelo usted mismo:

https://github.com/vitiral/tinymem

Nota: este proyecto ha sido descontinuado para trabajar en la implementación de óxido:

https://github.com/vitiral/defrag-rs

Además, no había oído hablar de umm_malloc antes. Desafortunadamente, no parece ser capaz de lidiar con la fragmentación, pero definitivamente parece útil. Voy a tener que comprobarlo.