¿Cómo funcionan malloc () y free ()?

Quiero saber cómo mallocy freetrabajar.

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

Estaría realmente agradecido si la respuesta es profunda a nivel de memoria, si es posible.

OK, ya se publicaron algunas respuestas sobre malloc.

La parte más interesante es cómo funciona gratis (y en esta dirección, malloc también se puede entender mejor).

En muchas implementaciones malloc / free, free normalmente no devuelve la memoria al sistema operativo (o al menos solo en casos excepcionales). La razón es que obtendrá huecos en su montón y, por lo tanto, puede suceder, que simplemente termine sus 2 o 4 GB de memoria virtual con huecos. Esto debe evitarse, ya que tan pronto como termine la memoria virtual, se encontrará en un gran problema. La otra razón es que el sistema operativo solo puede manejar fragmentos de memoria de un tamaño y alineación específicos. Para ser específicos: normalmente el sistema operativo solo puede manejar bloques que el administrador de memoria virtual puede manejar (con frecuencia múltiplos de 512 bytes, por ejemplo, 4KB).

Por lo tanto, devolver 40 Bytes al sistema operativo simplemente no funcionará. Entonces, ¿qué hace gratis?

Free pondrá el bloque de memoria en su propia lista de bloqueos gratuitos. Normalmente también intenta fusionar bloques adyacentes en el espacio de direcciones. La lista de bloqueo libre es solo una lista circular de fragmentos de memoria que tienen algunos datos administrativos al principio. Esta es también la razón por la cual administrar elementos de memoria muy pequeños con el estándar malloc / free no es eficiente. Cada fragmento de memoria necesita datos adicionales y con tamaños más pequeños se produce una mayor fragmentación.

La lista libre también es el primer lugar que malloc mira cuando se necesita una nueva porción de memoria. Se escanea antes de solicitar nueva memoria del sistema operativo. Cuando se encuentra un fragmento que es más grande que la memoria necesaria, se divide en dos partes. Uno se devuelve a la persona que llama, el otro se vuelve a colocar en la lista gratuita.

Hay muchas optimizaciones diferentes para este comportamiento estándar (por ejemplo, para pequeños fragmentos de memoria). Pero dado que malloc y free deben ser tan universales, el comportamiento estándar siempre es la alternativa cuando las alternativas no son utilizables. También hay optimizaciones en el manejo de la lista libre, por ejemplo, almacenar los fragmentos en listas ordenadas por tamaños. Pero todas las optimizaciones también tienen sus propias limitaciones.

¿Por qué se bloquea tu código?

La razón es que al escribir 9 caracteres (no olvide el byte nulo final) en un área de 4 caracteres, probablemente sobrescribirá los datos administrativos almacenados para otro fragmento de memoria que reside "detrás" de su fragmento de datos ( ya que estos datos se almacenan con mayor frecuencia "en frente" de los fragmentos de memoria). Cuando está libre, entonces intenta poner su parte en la lista libre, puede tocar estos datos administrativos y, por lo tanto, tropezar con un puntero sobrescrito. Esto bloqueará el sistema.

Este es un comportamiento bastante elegante. También he visto situaciones en las que un puntero desbocado en algún lugar ha sobrescrito datos en la lista libre de memoria y el sistema no se bloqueó de inmediato, sino algunas subrutinas más tarde. ¡Incluso en un sistema de complejidad media, tales problemas pueden ser muy, muy difíciles de depurar! En el único caso en el que estuve involucrado, nos tomó (un grupo más grande de desarrolladores) varios días encontrar la razón del bloqueo, ya que estaba en una ubicación totalmente diferente a la indicada por el volcado de memoria. Es como una bomba de tiempo. Ya sabes, tu próximo "gratis" o "malloc" se bloqueará, ¡pero no sabes por qué!

Esos son algunos de los peores problemas de C / C ++, y una de las razones por las cuales los punteros pueden ser tan problemáticos.

Como dice aluser en este hilo del foro :

Su proceso tiene una región de memoria, desde la dirección x hasta la dirección y, llamada montón. Todos sus datos mallocados viven en esta área. malloc () mantiene cierta estructura de datos, digamos una lista, de todos los fragmentos de espacio libre en el montón. Cuando llama a malloc, busca en la lista un fragmento que sea lo suficientemente grande para usted, le devuelve un puntero y registra el hecho de que ya no es gratis, así como su tamaño. Cuando llama a free () con el mismo puntero, free () busca qué tan grande es ese fragmento y lo agrega nuevamente a la lista de fragmentos libres (). Si llama a malloc () y no puede encontrar ningún fragmento lo suficientemente grande en el montón, utiliza la llamada al sistema brk () para hacer crecer el montón, es decir, aumentar la dirección y y hacer que todas las direcciones entre la antigua y y la nueva y Ser memoria válida. brk () debe ser una llamada al sistema;

malloc () depende del sistema / compilador, por lo que es difícil dar una respuesta específica. Básicamente, sin embargo, realiza un seguimiento de qué memoria está asignada y dependiendo de cómo lo haga, por lo que sus llamadas gratuitas podrían fallar o tener éxito.

malloc() and free() don't work the same way on every O/S.

Una implementación de malloc / free hace lo siguiente:

1. Obtenga un bloque de memoria del sistema operativo a través de sbrk () (llamada Unix).
2. Cree un encabezado y un pie de página alrededor de ese bloque de memoria con cierta información, como el tamaño, los permisos y dónde están el bloque siguiente y el anterior.
3. Cuando entra una llamada a malloc, se hace referencia a una lista que apunta a bloques del tamaño apropiado.
4. Este bloque se devuelve y los encabezados y pies de página se actualizan en consecuencia.

La protección de memoria tiene granularidad de página y requeriría la interacción del núcleo

Su código de ejemplo esencialmente pregunta por qué el programa de ejemplo no atrapa, y la respuesta es que la protección de la memoria es una característica del núcleo y se aplica solo a páginas enteras, mientras que el asignador de memoria es una característica de la biblioteca y administra ... sin aplicación ... arbitraria bloques de tamaño que a menudo son mucho más pequeños que las páginas.

La memoria solo se puede eliminar de su programa en unidades de páginas, e incluso es poco probable que se observe.

calloc (3) y malloc (3) interactúan con el núcleo para obtener memoria, si es necesario. Pero la mayoría de las implementaciones de free (3) no devuelven la memoria al kernel ¹ , solo la agregan a una lista gratuita que calloc () y malloc () consultarán más adelante para reutilizar los bloques liberados.

Incluso si un free () quisiera devolver la memoria al sistema, necesitaría al menos una página de memoria contigua para que el núcleo realmente proteja la región, por lo que liberar un pequeño bloque solo conduciría a un cambio de protección si fuera El último bloque pequeño en una página.

Entonces su bloque está ahí, sentado en la lista libre. Casi siempre puede acceder a él y a la memoria cercana como si todavía estuviera asignado. C compila directamente al código de máquina y sin arreglos especiales de depuración no hay controles de sanidad en cargas y tiendas. Ahora, si intenta acceder a un bloque libre, el comportamiento no está definido por el estándar para no hacer demandas irrazonables a los implementadores de la biblioteca. Si intenta acceder a la memoria o memoria liberada fuera de un bloque asignado, hay varias cosas que pueden salir mal:

• A veces los asignadores mantienen bloques de memoria separados, a veces usan un encabezado que asignan justo antes o después (un "pie de página", supongo) de su bloque, pero es posible que solo quieran usar la memoria dentro del bloque con el fin de mantener la lista libre Unidos entre sí. Si es así, su lectura del bloque está bien, pero su contenido puede cambiar, y escribir en el bloque podría causar que el asignador se porte mal o se bloquee.
• Naturalmente, su bloque puede asignarse en el futuro y es probable que su código o una rutina de biblioteca lo sobrescriba, o calloc () con ceros.
• Si el bloque se reasigna, también se puede cambiar su tamaño, en cuyo caso se escribirán aún más enlaces o inicializaciones en varios lugares.
• Obviamente, puede hacer referencia tan lejos del rango que cruce un límite de uno de los segmentos conocidos del núcleo de su programa, y ​​en este caso quedará atrapado.

teoría de operación

Entonces, trabajando hacia atrás desde su ejemplo hasta la teoría general, malloc (3) obtiene memoria del núcleo cuando lo necesita, y generalmente en unidades de páginas. Estas páginas están divididas o consolidadas según lo requiera el programa. Malloc y free cooperan para mantener un directorio. Fusionan bloques libres adyacentes cuando es posible para poder proporcionar bloques grandes. El directorio puede o no implicar el uso de la memoria en bloques liberados para formar una lista vinculada. (La alternativa es un poco más amigable con la memoria compartida y la paginación, e implica asignar memoria específicamente para el directorio). Malloc y free tienen poca o ninguna capacidad para forzar el acceso a bloques individuales incluso cuando se compila código de depuración especial y opcional. el programa.

^{1. El hecho de que muy pocas implementaciones de free () intenten devolver memoria al sistema no se debe necesariamente a que los implementadores se aflojen. Interactuar con el núcleo es mucho más lento que simplemente ejecutar código de biblioteca, y el beneficio sería pequeño. La mayoría de los programas tienen una huella de memoria constante o en aumento, por lo que el tiempo dedicado a analizar el montón en busca de memoria retornable se desperdiciaría por completo. Otras razones incluyen el hecho de que la fragmentación interna hace que sea improbable que existan bloques alineados con la página, y es probable que devolver un bloque fragmente los bloques a ambos lados. Finalmente, es probable que los pocos programas que devuelven grandes cantidades de memoria omitan malloc () y simplemente asignen y liberen páginas de todos modos.}

En teoría, malloc obtiene memoria del sistema operativo para esta aplicación. Sin embargo, dado que es posible que solo desee 4 bytes, y el sistema operativo necesita trabajar en páginas (a menudo 4k), malloc hace un poco más que eso. Toma una página y pone su propia información allí para que pueda realizar un seguimiento de lo que ha asignado y liberado de esa página.

Cuando asigna 4 bytes, por ejemplo, malloc le da un puntero a 4 bytes. Lo que quizás no se dé cuenta es que malloc está utilizando la memoria de 8-12 bytes antes de sus 4 bytes para crear una cadena de toda la memoria que ha asignado. Cuando llama gratis, toma su puntero, retrocede hasta donde están sus datos y opera con eso.

Cuando libera memoria, malloc quita ese bloque de memoria de la cadena ... y puede o no devolver esa memoria al sistema operativo. Si lo hace, el acceso a esa memoria probablemente fallará, ya que el sistema operativo le quitará sus permisos para acceder a esa ubicación. Si malloc mantiene la memoria (porque tiene otras cosas asignadas en esa página, o para alguna optimización), entonces el acceso funcionará. Todavía está mal, pero podría funcionar.

DESCARGO DE RESPONSABILIDAD: Lo que describí es una implementación común de malloc, pero de ninguna manera es la única posible.

Su línea strcpy intenta almacenar 9 bytes, no 8, debido al terminador NUL. Invoca un comportamiento indefinido.

La llamada a liberar puede bloquearse o no. La memoria "después" de los 4 bytes de su asignación podría ser utilizada para otra cosa por su implementación de C o C ++. Si se usa para otra cosa, entonces garabatear por todas partes hará que "otra cosa" salga mal, pero si no se usa para otra cosa, entonces podría salirse con la suya. "Salirse con la suya" puede sonar bien, pero en realidad es malo, ya que significa que su código parecerá funcionar bien, pero en una ejecución futura es posible que no se salga con la suya.

Con un asignador de memoria de estilo de depuración, puede encontrar que se ha escrito un valor de protección especial allí, y que comprueba libremente ese valor y entra en pánico si no lo encuentra.

De lo contrario, puede encontrar que los siguientes 5 bytes incluyen parte de un nodo de enlace que pertenece a algún otro bloque de memoria que aún no se ha asignado. Liberar su bloque podría implicar agregarlo a una lista de bloques disponibles, y debido a que ha garabateado en el nodo de la lista, esa operación podría desreferenciar un puntero con un valor no válido, causando un bloqueo.

Todo depende del asignador de memoria: diferentes implementaciones utilizan diferentes mecanismos.

El funcionamiento de malloc () y free () depende de la biblioteca de tiempo de ejecución utilizada. Generalmente, malloc () asigna un montón (un bloque de memoria) del sistema operativo. Cada solicitud a malloc () luego asigna una pequeña porción de esta memoria devolviendo un puntero a la persona que llama. Las rutinas de asignación de memoria deberán almacenar información adicional sobre el bloque de memoria asignado para poder realizar un seguimiento de la memoria usada y libre en el montón. Esta información a menudo se almacena en unos pocos bytes justo antes de que malloc () devuelva el puntero y puede ser una lista vinculada de bloques de memoria.

Al escribir más allá del bloque de memoria asignado por malloc (), lo más probable es que destruya parte de la información de contabilidad del siguiente bloque, que puede ser el bloque de memoria restante no utilizado.

Un lugar donde su programa también puede fallar es cuando copia demasiados caracteres en el búfer. Si los caracteres adicionales se encuentran fuera del montón, es posible que obtenga una infracción de acceso al intentar escribir en la memoria no existente.

Esto no tiene nada que ver específicamente con malloc y gratis. Su programa exhibe un comportamiento indefinido después de copiar la cadena; podría bloquearse en ese punto o en cualquier otro punto posterior. Esto sería cierto incluso si nunca usó malloc y free, y asignó el conjunto de caracteres en la pila o estáticamente.

malloc y free dependen de la implementación. Una implementación típica implica dividir la memoria disponible en una "lista libre", una lista vinculada de bloques de memoria disponibles. Muchas implementaciones lo dividen artificialmente en objetos pequeños y grandes. Los bloques gratuitos comienzan con información sobre el tamaño del bloque de memoria y dónde está el siguiente, etc.

Cuando malloc, se extrae un bloque de la lista libre. Cuando libera, el bloque se vuelve a colocar en la lista libre. Lo más probable es que, cuando sobrescribe el final de su puntero, está escribiendo en el encabezado de un bloque en la lista libre. Cuando libera su memoria, free () intenta mirar el siguiente bloque y probablemente termina golpeando un puntero que causa un error de bus.

Bueno, depende de la implementación del asignador de memoria y del sistema operativo.

En Windows, por ejemplo, un proceso puede solicitar una página o más de RAM. El sistema operativo luego asigna esas páginas al proceso. Sin embargo, esto no es memoria asignada a su aplicación. El asignador de memoria CRT marcará la memoria como un bloque contiguo "disponible". El asignador de memoria CRT se ejecutará a través de la lista de bloques libres y encontrará el bloque más pequeño posible que pueda usar. Luego tomará la mayor cantidad de ese bloque que necesite y lo agregará a una lista "asignada". Adjunto al encabezado de la asignación de memoria real habrá un encabezado. Este encabezado contendrá varios bits de información (podría, por ejemplo, contener los bloques asignados siguiente y anterior para formar una lista vinculada. Probablemente contendrá el tamaño de la asignación).

Free eliminará el encabezado y lo agregará nuevamente a la lista de memoria libre. Si forma un bloque más grande con los bloques libres circundantes, estos se sumarán para obtener un bloque más grande. Si una página completa ahora está libre, el asignador probablemente devolverá la página al sistema operativo.

No es un problema simple. La parte del asignador del sistema operativo está completamente fuera de su control. Le recomiendo que lea algo como Malloc de Doug Lea (DLMalloc) para comprender cómo funcionará un asignador bastante rápido.

Editar: su bloqueo se debe al hecho de que al escribir más grande que la asignación, ha sobrescrito el siguiente encabezado de memoria. De esta manera, cuando se libera, se confunde mucho sobre qué es exactamente lo que está liberando y cómo fusionarse en el siguiente bloque. Esto no siempre puede causar un bloqueo inmediato en la versión gratuita. Puede causar un bloqueo más adelante. En general, evite sobrescribir la memoria!

Su programa se bloquea porque utiliza memoria que no le pertenece. Puede ser utilizado por otra persona o no; si tiene suerte, se bloquea, de lo contrario, el problema puede permanecer oculto durante mucho tiempo y volver y morderlo más tarde.

En cuanto a la implementación de malloc / free, se dedican libros completos al tema. Básicamente, el asignador obtendría grandes cantidades de memoria del sistema operativo y las administraría por usted. Algunos de los problemas que un asignador debe abordar son:

• Cómo obtener nueva memoria
• Cómo almacenarlo: (lista u otra estructura, listas múltiples para fragmentos de memoria de diferentes tamaños, etc.)
• Qué hacer si el usuario solicita más memoria de la que está disponible actualmente (solicite más memoria del sistema operativo, únase a algunos de los bloques existentes, cómo unirlos exactamente, ...)
• Qué hacer cuando el usuario libera memoria
• Los asignadores de depuración pueden darle una porción más grande que solicitó y llenarlo con un patrón de bytes, cuando libera la memoria, el asignador puede verificar si se escribió fuera del bloque (lo que probablemente esté sucediendo en su caso) ...

Es difícil de decir porque el comportamiento real es diferente entre diferentes compiladores / tiempos de ejecución. Incluso las versiones de depuración / liberación tienen un comportamiento diferente. Las compilaciones de depuración de VS2005 insertarán marcadores entre asignaciones para detectar daños en la memoria, por lo que en lugar de un bloqueo, se afirmará en free ().

También es importante darse cuenta de que simplemente moviendo el puntero de interrupción del programa brky sbrkno asigna la memoria, solo 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 núcleo a llamar al asignador de página para obtener una página de respaldo.