heap_allocator
1.0.0
Este es un asignador de montón simple que escribí para un sistema operativo aficionado en el que he estado trabajando. Escribí este asignador con muy poca investigación y está hecho para que sea lo más fácil de entender posible. Creo que este repositorio puede ser útil para quienes son nuevos en el desarrollo de sistemas operativos (como yo) o están interesados en ver una versión simplificada de funciones como malloc y free.
Hay dos archivos de encabezado que definen el montón y la lista vinculada. para compilar este repositorio:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
esto ejecutará una demostración del asignador e imprimirá cierta información.
Para inicializar este montón, se debe proporcionar una sección de memoria. En este repositorio, esa memoria la proporciona malloc (sí, asignando un montón mediante montón). En una configuración de sistema operativo, algunas páginas deberían asignarse y suministrarse al montón (un escenario). Tenga en cuenta que los contenedores en la estructura heap_t también necesitan que se les asigne memoria.
Cuando se llama a la función init_heap, se debe proporcionar la dirección de la estructura del montón vacía (con punteros bin asignados). La función init_heap creará un fragmento grande con un encabezado ( node_t struct) y un pie de página ( footer_t struct). Para determinar el tamaño de este fragmento, la función utiliza la constante HEAP_INIT_SIZE . Agregará esto al argumento start para determinar dónde termina el montón.
Cada fragmento de memoria tiene una estructura de nodo al principio y una estructura de pie de página al final. El nodo contiene el tamaño, ya sea que el fragmento esté libre o no, y dos punteros utilizados en la lista doblemente enlazada (siguiente y anterior). La estructura del pie de página simplemente contiene un puntero al encabezado (que se usa para liberar fragmentos adyacentes). El fragmento al final del montón se llama fragmento "desierto". Es el fragmento más grande y sus tamaños mínimo y máximo están definidos en heap.h. Contraer y expandir el montón es tan fácil como cambiar el tamaño de este trozo salvaje. Los trozos de memoria libres se almacenan en "contenedores". Cada contenedor es en realidad solo una lista doblemente enlazada de nodos con tamaños similares. La estructura del montón contiene un número definido de contenedores ( BIN_COUNT en heap.h). Para determinar en qué contenedor colocar un fragmento, la función get_bin_index asigna el tamaño del fragmento a un índice de contenedor. Esta función de agrupación consistente garantizará que se pueda acceder a los fragmentos y almacenarlos de manera definida. Los fragmentos se clasifican a medida que se insertan en los contenedores, por lo que la inserción de fragmentos no es O(1), pero esto hace que sea mucho más fácil encontrar los fragmentos que mejor se ajusten. Tenga en cuenta que la función de agrupación se puede definir como el usuario de este montón lo considere adecuado. Puede resultar beneficioso determinar una función de agrupación más sofisticada para ayudar a la recuperación rápida de fragmentos.
La función heap_alloc toma la dirección de la estructura del montón para asignar y un tamaño. La función simplemente usa get_bin_index para determinar dónde DEBE estar un fragmento de este tamaño; por supuesto, puede que no haya un fragmento de ese tamaño. Si no se encuentran fragmentos en el contenedor correspondiente, se verificará el siguiente contenedor. Esto continuará hasta que se encuentre un fragmento o se llegue al último contenedor, en cuyo caso se tomará un fragmento de memoria del fragmento silvestre. Si el trozo encontrado es lo suficientemente grande, se dividirá. Para determinar si un fragmento debe dividirse, la cantidad de metadatos (gastos generales) se resta de lo que nuestra asignación actual no utiliza. Si lo que queda es mayor o igual a MIN_ALLOC_SZ , entonces significa que debemos dividir este trozo y colocar las sobras en el contenedor correcto. Una vez que estemos listos para devolver el fragmento que encontramos, tomamos la dirección del next campo y lo devolvemos. Esto se hace porque los campos next y prev no se utilizan mientras se asigna un fragmento, por lo que el usuario del fragmento puede escribir datos en estos campos sin afectar el funcionamiento interno del montón.
La función heap_free toma un puntero devuelto por heap_alloc . Resta el desplazamiento correcto para obtener la dirección de la estructura del nodo. En lugar de simplemente colocar el trozo en el contenedor correcto, se verifican los trozos que rodean al trozo proporcionado. Si alguno de estos fragmentos está libre, podemos fusionarlos para crear un fragmento más grande. Para unir los fragmentos, se utiliza el pie de página para obtener la estructura de nodo del fragmento anterior y la estructura de nodo del siguiente fragmento. Por ejemplo, digamos que tenemos un fragmento llamado to_free . Para obtener el fragmento anterior a este fragmento, restamos sizeof(footer_t) para obtener el pie de página del fragmento anterior. El pie de página contiene un puntero al encabezado del fragmento anterior. Para obtener el siguiente fragmento, simplemente obtenemos el pie de página de to_free y luego agregamos sizeof(footer_t) para obtener el siguiente fragmento. Una vez hecho todo esto y recalculados los tamaños, el trozo se vuelve a colocar en un contenedor.
NOTA: Este código se compiló originalmente para una máquina de 32 bits, esto significa que cuando se usaba este código era aceptable convertir un int a un puntero debido a que ambos tienen el mismo tamaño. En un sistema de 64 bits, el compilador le advertirá de la diferencia de tamaño. Para silenciar estas advertencias, he utilizado uintptr_t al transmitir desde un int sin firmar a un puntero. Esto enturbia un poco la legibilidad y algunas de las conversiones y la aritmética de punteros son detalladas, así que téngalo en cuenta al leer el código.
