malloc sizeof

¿Cómo se implementa malloc() internamente?

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo funcionan malloc () y free ()? 14 respuestas

¿Alguien puede explicar cómo funciona malloc() internamente?

A veces he hecho un strace program y veo muchas llamadas al sistema sbrk , haciendo que el man sbrk hable de que se usa en malloc() pero no mucho más.

Answer 1

La sbrk sistema sbrk mueve el "borde" del segmento de datos. Esto significa que mueve un borde de un área en la que un programa puede leer / escribir datos (permitiéndole crecer o reducirse, aunque AFAIK no malloc realmente le da segmentos de memoria al kernel con ese método). Aparte de eso, también hay mmap que se utiliza para asignar archivos a la memoria, pero también se utiliza para asignar memoria (si necesita asignar memoria compartida, mmap es cómo lo hace).

Entonces tiene dos métodos para obtener más memoria del kernel: sbrk y mmap . Hay varias estrategias sobre cómo organizar la memoria que tiene del kernel.

Una forma ingenua es dividirla en zonas, a menudo llamadas "cubos", que están dedicados a ciertos tamaños de estructura. Por ejemplo, una implementación malloc podría crear divisiones para estructuras de 16, 64, 256 y 1024 bytes. Si le pides a malloc que te dé memoria de un tamaño dado, redondea ese número al siguiente tamaño de cubo y luego te da un elemento de ese cubo. Si necesita un área más grande, malloc podría usar mmap para asignar directamente con el kernel. Si el cubo de cierto tamaño está vacío, malloc podría usar sbrk para obtener más espacio para un nuevo cubo.

Hay varios diseños de malloc y no existe una manera verdadera y verdadera de implementar malloc ya que se necesita hacer un compromiso entre velocidad, sobrecarga y evitar la fragmentación / efectividad del espacio. Por ejemplo, si una cubeta se queda sin elementos, una implementación podría obtener un elemento de una cubeta más grande, dividirlo y agregarlo a la cubeta que se quedó sin elementos. Esto sería bastante eficiente desde el punto de vista del espacio, pero no sería posible con cada diseño. Si acaba de obtener otro cubo a través de sbrk / mmap que podría ser más rápido y más fácil, pero no tan eficiente en el uso del espacio. Además, el diseño debe tener en cuenta, por supuesto, que "libre" necesita volver a dejar espacio disponible para malloc alguna manera. No solo entregas la memoria sin reutilizarla.

Si está interesado, el proxy SIP OpenSER / Kamailio tiene dos implementaciones malloc (que necesitan las suyas porque hacen un uso intensivo de la memoria compartida y el sistema malloc no es compatible con la memoria compartida). Ver: https://github.com/OpenSIPS/opensips/tree/master/mem

Entonces también podría echarle un vistazo a la implementación GNU libc malloc , pero esa es muy complicada, IIRC.

Answer 2

Simplísticamente malloc y libre funcionan así:

malloc proporciona acceso al montón de un proceso. El montón es una construcción en la biblioteca de núcleo C (comúnmente libc) que permite a los objetos obtener acceso exclusivo a algún espacio en el montón del proceso.

Cada asignación en el montón se llama pila de montón. Esto generalmente consiste en un encabezado que contiene información sobre el tamaño de la celda, así como un puntero a la siguiente celda de pila. Esto hace que un montón sea efectivamente una lista vinculada.

Cuando uno comienza un proceso, el montón contiene una sola celda que contiene todo el espacio de montón asignado al inicio. Esta celda existe en la lista gratuita del montón.

Cuando uno llama a malloc, la memoria se toma de la celda de pila grande, que es devuelta por malloc. El resto se forma en una nueva pila de montón que consiste en todo el resto de la memoria.

Cuando uno libera memoria, la celda de pila se agrega al final de la lista libre del montón. Los mallocs subsiguientes recorren la lista gratuita buscando una célula de tamaño adecuado.

Como se puede esperar, el montón puede fragmentarse y el administrador del montón puede ocasionalmente intentar fusionar celdas de montón adyacentes.

Cuando no queda memoria en la lista libre para una asignación deseada, malloc llama a brk o sbrk, que son las llamadas al sistema que solicitan más páginas de memoria desde el sistema operativo.

Ahora hay algunas modificaciones para optimizar las operaciones de montón.

• Para asignaciones de memoria grandes (normalmente> 512 bytes, el administrador de montón puede ir directamente al sistema operativo y asignar una página de memoria completa.
• El montón puede especificar un tamaño mínimo de asignación para evitar grandes cantidades de fragmentación.
• El montón también puede dividirse en contenedores uno para asignaciones pequeñas y uno para asignaciones más grandes para hacer asignaciones más grandes más rápido.
• También hay mecanismos inteligentes para optimizar la asignación de heap de subprocesos múltiples.

Answer 3

También es importante darse cuenta de que simplemente mover el puntero de interrupción del programa con brk y sbrk realidad no asigna la memoria, simplemente configura el espacio de direcciones. En Linux, por ejemplo, la memoria estará "respaldada" por páginas físicas reales cuando se acceda a ese rango de direcciones, lo que dará como resultado un error de página, y eventualmente llevará al kernel a llamar al asignador de páginas para obtener una página de respaldo.