Мотивация

Меня всегда удивляло, как можно использовать простые структуры данных для создания мощных инструментов. Недавно мне стало любопытно, как «маллок» работает за кулисами. Было интересно узнать, что большинство реализаций используют двусвязные списки в фоновом режиме. Следовательно, в итоге написал собственный распределитель динамической памяти (DMA). Цель этой заметки состоит в том, чтобы зафиксировать и поделиться пониманием и реализацией.

Начнем

Как правило, для кучи резервируется огромный объем памяти. Приложения могут запрашивать память с помощью вызова «malloc». После его использования приложение может освободить память с помощью «свободного» вызова. Чтобы избежать двусмысленности, мы будем называть память, зарезервированную для DMA, кучей, а подмножество кучи, выделенное или освобожденное приложением, — блоком в остальной части статьи.

Вот несколько параметров дизайна, которые мы намерены оптимизировать с помощью этого дизайна прямого доступа к памяти:

  1. Время выделения: время, необходимое для выполнения «malloc».
  2. Фрагментация: это относится к ситуации, когда свободная память в куче распределена по нескольким несмежным блокам. Минимальная фрагментация лучше.
  3. Накладные расходы на учет: любой алгоритм прямого доступа к памяти должен поддерживать метаданные, чтобы отслеживать выделенные и нераспределенные блоки памяти. Минимальный размер метаданных лучше.

Структуры данных

  1. avail_dll: Один двусвязный список (DLL) для отслеживания доступных блоков. Каждый узел в DLL представляет собой блок памяти и называется дескриптором блока (BD).
  2. alloc_dll: еще одна DLL для отслеживания выделенных блоков. DLL поддерживает BD в отсортированном порядке. Сортировка основана на адресах блоков, на которые указывает BD. то есть первый BD в DLL будет указывать на свободный блок с наименьшим адресом.
  3. BD помещаются в кучу. Каждый BD размещается в куче таким образом, что он непосредственно предшествует блоку, на который указывает.

Алгоритм

  1. malloc: Алгоритм следует первому подходящему подходу. malloc ищет первый подходящий свободный блок. Идентифицированный свободный блок может иметь больше памяти, чем запрошено. Следовательно, блок разделен на два, один блок выделен вызывающей программе malloc, а другой невыделенный блок. BD, указывающий на выделенный блок, добавляется в alloc_dll. Новый BD, указывающий на нераспределенный блок, создается и добавляется в avail_dll. Временная сложность растет линейно в зависимости от количества блоков.
  2. free: Удаляет BD, указывающий на освобождаемый блок, из alloc_dll. Удаленный BD добавляется в файл avail_dll таким образом, что файл avail_dll остается отсортированным. Затем выполняется проверка, указывает ли непосредственно предшествующий BD в файле avail_dll на непосредственно предшествующий блок в куче. Если да, оба блока объединены, объедините блоки, объединив BD. Аналогичным образом выполняется проверка, соответствует ли непосредственно следующий за ним блок BD непосредственно следующему за ним блоку в куче. Если да, блоки объединяются путем объединения BD. Временная сложность растет линейно в зависимости от количества свободных блоков.

Видео 1 иллюстрирует работу алгоритма на примере. На шаге 1 куча инициализируется путем создания BD 1 в начале кучи. BD 1 добавляется к avail_dll и представляет полную кучу. На шаге 2 выполняется вызов malloc(sizeof(int)). Алгоритм выполняет поиск в avail_dll, чтобы найти BD, представляющий блок, размер которого больше или равен запрошенному размеру. В этом вызове поиск остановится на BD 1, так как он представляет собой блок большего размера, чем запрошенный размер. Блок, представленный BD 1, разделен на два, так как он содержит больше памяти, чем запрошено. BD 1 обновляется, чтобы ссылаться на выделенный блок (т. е. запрошенный вызывающей программой malloc). Новый BD, BD 2, создается для ссылки на свободный блок. BD 2 добавлен в файл avail_dll.

На шаге 3, аналогично шагу 2, выполняется вызов malloc(sizeof(int)). Поиск свободного блока сужается до BD 2. Блок, на который указывает BD 2, разбивается на два. BD 2 обновляется, чтобы ссылаться на выделенный блок (т. е. блок, запрошенный вызывающей программой malloc). BD 3 создан для обозначения свободного блока. На шаге 4 выполняется вызов free(p1) (т.е. p1 указывает на память, выделенную на шаге 2). BD 1, указывающая на освобождаемый блок, удаляется из alloc_dll и добавляется в avail_dll. На шаге 5 выполняется вызов free(p2) (т.е. p2 указывает на память, выделенную на шаге 3). BD 2, указывающая на освобождаемый блок, удаляется из alloc_dll и добавляется в avail_dll. Поскольку BD 1, BD 2 и BD 3 указывают на последовательные свободные блоки, блоки могут быть объединены. BD 1 обновляется, чтобы указать на объединенный блок. BD 2 и BD 3 удалены.

Реализация

DMA предоставляет три API:

API спроектированы таким образом, чтобы обеспечить возможность использования нескольких куч в системе. HEAP_INFO_t определяет кучу. Каждому API необходимо предоставить экземпляр HEAP_INFO_t в качестве первого аргумента. Ниже представлена ​​реализация API:

Полную реализацию вместе с тестами можно найти здесь.



GitHub — dheeptuck/custom_malloc: пользовательская реализация malloc.
Вы не можете выполнить это действие в данный момент. Вы вошли в другую вкладку или окно. Вы вышли на другой вкладке или…github.com



Заключение

Выбор реализации malloc осуществляется на основе компромиссов между различными факторами. Freertos имеет несколько реализаций кучи, каждая из которых обменивает один параметр дизайна на другой (см. здесь). Эффективность памяти алгоритма может быть увеличена за счет упаковки структуры (т.е. __attribute__(packed)). Излишне говорить, что реализация не является потокобезопасной, и большинство используемых реализаций должны быть потокобезопасными. Я уверен, что это не исчерпывающая статья, может быть много методов для реализации эффективных malloc, пожалуйста, поделитесь ими. Кроме того, поделитесь любыми другими мыслями, которые у вас есть.