Как правильно управлять памятью через mmap?

Question

Я пытаюсь написать свой malloc а также free реализация ради обучения, просто mmap а также munmap (поскольку brk а также sbrk являются устаревшими). Я прочитал довольно много документации по этому вопросу, но каждый пример, который я вижу, использует sbrk или не очень хорошо объясняет, как обрабатывать большие зоны отображаемой памяти.

Идея того, что я пытаюсь написать, заключается в следующем: я сначала сопоставляю большую зону (т.е. 512 страниц); эта зона будет содержать все распределения от 1 до 992 байтов с шагом 16 байтов. Я сделаю то же самое позже с зоной 4096 страниц для больших выделений (или mmap напрямую, если запрошенный размер больше, чем страница). Поэтому мне нужен способ хранения информации о каждом фрагменте, который я выделяю или освобождаю.

У меня вопрос, как мне правильно обращаться с этой информацией?

Мои проблемы: если я создаю связанный список, как мне выделить больше места для каждого узла? Или мне нужно скопировать его в сопоставленную зону? Если так, как я могу манипулировать между пространством данных и зарезервированным пространством? Или лучше использовать массив статического размера? Проблема в том, что размер моей зоны зависит от размера страницы.

Answer 1

Существует несколько возможных реализаций для malloc на основе mmap:

Последовательный (первое соответствие, лучшее соответствие).

Идея: использовать связанный список с размером последнего чанка до оставшегося размера вашей страницы.

struct chunk
{
   size_t size;
   struct chunk *next;
   int is_free;
}

1. Выделить
   1. Итерируйте свой список для подходящего свободного чанка (оптимизируемого)
   2. Если ничего не найдено, измените размер последнего чанка до необходимого размера и создайте свободный чанк до оставшегося размера.
   3. Если вы дойдете до конца страницы, (size слишком маленький, и next NULL), просто отобразить новую страницу (оптимизируемо: создать пользовательскую страницу, если ее размер ненормальный...)
2. Чтобы освободить, еще проще: просто установить is_free к 1. опционально, вы можете проверить, свободен ли следующий блок и объединить оба в больший блок (не пропустите границы страницы).

Плюсы: Легко реализовать, тривиально понять, легко настроить.

Минусы: не очень эффективны (итерируйте весь список, чтобы найти блок?), Требуется много оптимизации, беспокойная организация памяти

Двоичные приятели (я люблю двоичную арифметику и рекурсию)

Идея: использовать степени 2 как единицы размера:

struct chunk
{
   size_t size;
   int is_free;
}

структура здесь не нужна next как вы увидите.

Принцип заключается в следующем:

• У вас есть страница размером 4096 байт. то есть (-16 для метаданных) 4080 используемых байтов
• Чтобы выделить небольшой блок, просто разделите страницу на два фрагмента по 2048 байт и снова разделите первую половину на фрагменты по 1028 байт..., пока не получите подходящее полезное пространство (минимум 32 байта (16 используемых)),
• Каждый блок, если это не полная страница, имеет приятеля.
• Вы получите древовидную структуру, подобную этой:
• чтобы получить доступ к своему собеседнику, используйте двоичный XOR между указателем и размером блока.

Реализация:

1. Выделение блока размера Size
   1. Получить необходимый Block_size = 2^k > size + sizeof(chunk)
   2. найти наименьшее свободное место в дереве, которое подходит block_size
   3. Если он может уменьшиться, разделите его рекурсивно.
2. Освобождение блока
   1. настройка is_free до 1
   2. проверка, свободен ли ваш друг (размер XOR, не забудьте проверить, что он того же размера, что и вы)
   3. если он есть, удвойте его размер. Recurse.

Плюсы: чрезвычайно быстрый и эффективный для памяти, чистый.

Минусы: Сложно, несколько хитрых дел (границы страниц и размеры собеседников). Необходимо вести список ваших страниц.

Ведра (у меня много времени, чтобы потерять)

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

struct bucket
{
  size_t buck_num;  //number of data segment
  size_t buck_size; //size of a data segment
  void *page;
  void *freeinfo;
}

• С самого начала у вас есть несколько маленьких страниц, каждая из которых разбита на блоки постоянного размера (одна 8-байтовая страница, одна 16-байтовая, одна 32-байтовая и т. Д.)
• "Информация о свободе" этих блоков данных хранится в наборах битов (структурах, представляющих большой набор целых чисел) либо в начале каждой страницы, либо в отдельной зоне памяти.

например, для блока объемом 512 байт на страницах размером 4096 байт набор битов, представляющий его, будет набором битов в 8 битов, предполагая *freeinfo = 01001000это будет означать, что второе и пятое ведра свободны.

Плюсы: безусловно, самые быстрые и чистые в долгосрочной перспективе, наиболее эффективные при небольших распределениях

Минусы: очень громоздкий для реализации, достаточно тяжелый для небольшой программы, требующий отдельного пространства памяти для битовых наборов.

Вероятно, существуют другие алгоритмы и реализации, но эти три являются наиболее используемыми, поэтому я надеюсь, что вы сможете получить представление о том, что вы хотите сделать из этого.