Как использовать двусвязный список в Buddy аллокаторе?

Question

[Имя]

Предположим имеется такая схема памяти с точки зрения аллокатора:

|    1     |
| 2  || 3  |
|4||5||6||7|

В основном, для учёта блоков используется битовая карта.
Для быстрого нахождения свободного блока используется двусвязный список.
И я предполагаю, что у нас есть три двусвязных списка, содержащие индексы свободных блоков каждого размера.
В этом случае, при выделении блока 2, следует удалить блоки 4 и 5 из двусвязного списка, но проблема в том, что порядок элементов в списке может быть произвольным, 4 и 5 не обязательно будут идти в начале. (Да и даже если бы они шли в правильном порядке, то пришлось бы каждый раз перебирать элементы списка, прежде чем были бы найдены элементы ответственные за 4 и 5).
Так как же организовать работу с двусвязным списком что-бы избежать проблемы при удалении дочерних блоков из списка при выделении их отца?

Comments

[Василий Дёмин]

Не разбирался в работе buddy аллокатора, но всегда можно посмотреть в каком-нибудь популярном репозитории, например в этом

[mayton2019]

Сложно комментировать пересказанный алгоритм словами.
Нужен исходник.

[spaskalev]

Василий Дёмин Спасибо за ссылку на мой проект! Это работает немного по-другому — есть двоичное дерево с весами, отображаемое в памяти.

Answer 1

[Wataru]

И пофигу на порядок. Пусть он в списках будет произвольный. При выделении блока просто берете первый из списка, удаляете оттуда и выдаете. При освобождении блока пихаете его в список куда угодно.

Только надо поддерживать еще указатели на buddy. Т.е. тут что-то вроде трех-связного списка будет. При освобождении бока, если видите, что его buddy свободен, то удаляете его их обоих из списка и "освобождаете" удвоенный кусок.

Можно это в массиве делать и хранить указатели вперед-назад в двух элементах под двух buddy. У вас в списке же только один из парочки всегда может быть.

Comments

[Имя]

Так проблема как раз в том, что выдавая блок основываясь на двусвязном списке, нельзя оперативно удалить его "детей" и "родителя" из списков других порядков.
Для примера выше:
3 списка
free_lists[0]: 1
free_lists[1]: 2<->3
free_lists[2]: 4<->5<->6<->7
Выдавая блок 2, нам нужно удалить из списков выше и ниже блоки 1, 4, 5, но это сделать сложно, т.к. они могут находиться там в произвольном порядке, не перебирать же все списки.
Вот как с этой проблемой совладать?

[Wataru]

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

[Имя]

Wataru, почему их не существует? Блок 2 является свободным, а значит и блоки 4 и 5 тоже. Блок 2 хранится в одном списке, 4 и 5 в другом. Разве не так?

[Wataru]

Герман, В алгоритме у вас есть сначала один большой кусок. Один-одиношинек, никаких половин, четвертинок и дальше еще не существует. Вот при выделении, вы берете любой самый маленький достаточно большой кусок и, пока он в 2 раза больше запроса, делите его пополам.

Вам не надо следить за мелким куском, если он является частью большого свободного.

[Имя]

Wataru, в этом случае, при поиске маленького блока, нам придётся перебирать частично занятые большие блоки(в них же может влезть маленький), а это долго.

[Wataru]

Герман, Перечитайте википедию. Аллокатор всегда выдает блок целиком. Хотя бы вот пример:

Program C requests memory 35 K, order 0. An order 0 block is available, so it is allocated to C.

Запросили 35k а получили блок 64k целиком. И там еще схемка есть: клетки - целые блоки всегда.

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

[Имя]

Wataru, так

|    1     |       128B
| 2  || 3  |      64B
|4||5||6||7|    32B

По умолчанию у нас есть лишь блок 128B. Запрос на выделение 50 байт, мы делим блок 1 пополам, выдаём блок 2, что делаем с блоком 3? Сохраняем ли его куда-нибудь?

[Wataru]

Герман, нет, нужен список свободных блоков для каждого размера. В вашм примере изначально только в списке 0 храниться один блок. Вы его пилите, одну половину выдаете, а вторую сохраняете в список 1. Если бы щапрос был на 10b, то вы бы уполовинили блок 2 раза и созранили бы пустой блок в чписки 1 и 2 соответственно.