heap_allocator
1.0.0
Это простой распределитель кучи, который я написал для своей любительской ОС, над которой работал. Я написал этот распределитель, проведя очень мало исследований, и он сделан максимально простым для понимания. Я думаю, что этот репозиторий может быть полезен тем, кто новичок в разработке ОС (например, я) или хочет увидеть упрощенную версию функций, таких как malloc и free.
Существует два файла заголовков, которые определяют кучу и связанный список. для компиляции этого репозитория:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
это запустит демонстрационную версию распределителя и распечатает некоторую информацию.
Чтобы инициализировать эту кучу, необходимо предоставить раздел памяти. В этом репозитории эта память предоставляется malloc (да, выделение кучи через кучу). В настройках ОС некоторые страницы необходимо будет сопоставить и передать в кучу (один сценарий). Обратите внимание, что для ячеек в структуре heap_t также требуется выделение памяти.
При вызове функции init_heap должен быть указан адрес пустой структуры кучи (с выделенными указателями ячеек). Затем функция init_heap создаст один большой фрагмент с заголовком (структура node_t ) и нижним колонтитулом (структура footer_t ). Чтобы определить размер этого фрагмента, функция использует константу HEAP_INIT_SIZE . Он добавит это к аргументу start , чтобы определить, где заканчивается куча.
Каждый фрагмент памяти имеет структуру узла в начале и структуру нижнего колонтитула в конце. Узел хранит размер независимо от того, свободен ли фрагмент или нет, а также два указателя, используемые в двусвязном списке (следующий и предыдущий). Структура нижнего колонтитула просто содержит указатель на заголовок (используется при освобождении соседних фрагментов). Кусок в конце кучи называется «диким куском». Это самый большой фрагмент, его минимальный и максимальный размеры определяются в heap.h. сжимать и расширять кучу так же просто, как изменять размер этого пустого куска. Свободные фрагменты памяти хранятся в «корзинах», каждый бункер на самом деле представляет собой просто двусвязный список узлов одинакового размера. Структура кучи содержит определенное количество ячеек ( BIN_COUNT в heap.h). Чтобы определить, в какой контейнер поместить фрагмент, размер фрагмента сопоставляется с индексом бункера с помощью функции get_bin_index . Эта последовательная функция объединения гарантирует, что к фрагментам можно получить доступ и сохранить их определенным образом. Фрагменты сортируются по мере их помещения в бункеры, поэтому вставка фрагментов не является O(1), но это значительно упрощает поиск фрагментов, которые лучше всего подходят. Обратите внимание, что функция группирования может быть определена по усмотрению пользователя этой кучи. может быть полезно определить более сложную функцию группирования, чтобы облегчить быстрый поиск фрагментов.
Функция heap_alloc принимает адрес структуры кучи, из которой необходимо выделить, и ее размер. Функция просто использует get_bin_index чтобы определить, где ДОЛЖЕН находиться фрагмент такого размера, конечно, фрагмента такого размера может не быть. Если в соответствующем контейнере не обнаружено кусков, будет проверен следующий контейнер. Это будет продолжаться до тех пор, пока не будет найден фрагмент или не будет достигнут последний интервал, и в этом случае часть памяти будет просто взята из пустого фрагмента. Если найденный фрагмент достаточно велик, он будет разделен. Чтобы определить, следует ли разделить фрагмент, объем метаданных (накладных расходов) вычитается из того, что наше текущее распределение не использует. Если то, что осталось, больше или равно MIN_ALLOC_SZ , это означает, что мы должны разделить этот кусок и поместить остатки в правильный контейнер. Как только мы будем готовы вернуть найденный фрагмент, мы берем адрес next поля и возвращаем его. Это сделано потому, что поля next и prev не используются, пока выделен фрагмент, поэтому пользователь фрагмента может записывать данные в эти поля, не влияя на внутреннюю работу кучи.
Функция heap_free принимает указатель, возвращаемый heap_alloc . Он вычитает правильное смещение, чтобы получить адрес структуры узла. Вместо того, чтобы просто помещать фрагмент в правильный контейнер, проверяются фрагменты, окружающие предоставленный фрагмент. Если какой-либо из этих фрагментов свободен, мы можем объединить эти фрагменты, чтобы создать более крупный фрагмент. Для объединения фрагментов нижний колонтитул используется для получения структуры узла предыдущего фрагмента и структуры узла следующего фрагмента. Например, предположим, что у нас есть чанк под названием to_free . Чтобы получить фрагмент перед этим фрагментом, мы вычитаем sizeof(footer_t) чтобы получить нижний колонтитул предыдущего фрагмента. Нижний колонтитул содержит указатель на заголовок предыдущего фрагмента. Чтобы получить следующий фрагмент, мы просто получаем нижний колонтитул to_free , а затем добавляем sizeof(footer_t) чтобы получить следующий фрагмент. Как только все это будет сделано и размеры будут пересчитаны, кусок будет помещен обратно в корзину.
ПРИМЕЧАНИЕ. Этот код изначально был скомпилирован для 32-битной машины. Это означает, что при использовании этого кода было приемлемо привести int к указателю, поскольку они оба имеют одинаковый размер. В 64-битной системе компилятор предупредит вас о разнице в размерах. Чтобы заглушить эти предупреждения, я использовал uintptr_t при приведении беззнакового целого числа к указателю. Это немного ухудшает читаемость, а некоторые приведения и арифметика указателей являются многословными, поэтому имейте это в виду при чтении кода.
