OSDEV: Разработка аллокатора на С++ часть 3. Финальный аллокатор со списками свободных блоков

Вот важная новость с фронта ИИ: GNU_Dimarik 5 минут назад OSDEV: Разработка аллокатора на С++ часть 3. Финальный аллокатор со списками свободных блоков Средний 15 мин 5 C++ * Алгоритмы * ОглавлениеЧасть 1Часть 2В третьей статье пойдет речь уже о готовом аллокаторе который вполне пригоден для распределения памяти. Он полностью переписан, но идея та же самая, неявный список свободных блоков с граничными тегами сверху и снизу, но с массивом списков свободных блоков.

Бины реализованы как массив размером 256 указателей на двусвязные списки. Блоки хранятся в бине индекс которого равен размеру блока если блок <= 255 байт, остальные блоки лежат в бине с индексом 255 и отсортированы по размеру. В бинах с меньшими индексами свободный блок просто добавляется в начало списка со сложностью O(1).

Технические детали

Так же поиск бина получается быстрым так как доступ по индексу в массиве так же имеет сложность O(1), это оптимизирует работу с блоками небольшого размера. Для поиска больших блоков придется довольствоваться поиском в отсортированном по размеру списке. Вот общая схема:Индекс бина вычисляется следующим образом:static size_t bin_index_from_size(size_t size) { if (size >= kHugeBlockMinSize) { return kHugeBinIndex; } return size; } Связи хранятся в так называемом payload, т.

в пространстве которое будет использовано если блок занят, но если блок свободен, то мы можем использовать его как захотим. Следует отметить что это обязывает нас сделать минимальный размер блока 16 байт, или sizeof(void*) * 2Это обеспечивается простым набором функций в стиле С. Все функции высокого уровня работают только с указателями на payload блока.

Функции высокого уровня это функции которые работают с блоками, а не с сырой памятью. Ниже функции работающие с сырой памятью. Именно они делают из нее блоки.

/** * Memory block related stuff */ // Возвращает указатель типа size_t* на память на которую укзывает __p // нужно для чтения и записи служебной информации хранящейся в граничных тегах static size_t *mem_block_size_t_ptr(void *_p) { return reinterpret_cast(_p); } // Возвращает размер блока. Предполагается что __p указывает на хедер // или футер блока static size_t mem_block_get_size(void *_p) { return *mem_block_size_t_ptr(_p) & ~0x01; } // Возвращает указатель типа char* на память на которую укзывает __p // нужно для арифметических операций с указателями, что бы шаг был размером в байт static char *mem_block_char_ptr(void *_p) { return reinterpret_cast(_p); } // Возвращает указатель на payload из указателя на заголовок блока // Все функции высокого уровня работают с указателями на payload static char *mem_block_user_ptr(void *_p) { return mem_block_char_ptr(_p) + kHeaderSize; } // Упаковывает вместе размер блока и бит состояния.

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.