Идея аллокатора.

Обсудите такую идею аллокатора. Юзкейс - выделять объекты размером не более, допустим, 4КБ и иметь минимум оверхеда на служебные структуры. Применять в in-memory nosql хранилке ключей key=value.

Выделяем объекты любого размера (до 4kb) последовательно в странице (как арена аллокатор) (макс размер объекта = не более страницы), при заполнении страницы берём у ОС новую и продолжаем. При освобождении объекта, помечаем его в странице как свободный, но выделение в этой точке невозможно - выделялка максимально тупая и берёт всегда только с конца "текущей".

В процессе освобождения очередного элемента проверяем страницу Q (в которой он только что был освобождён) на суммарное количество свободных фрагментов sum_free. Если sum_free достигает некого критического уровня (скажем, 0.4 от общего размера страницы) - делаем compaction - вытряхиваем все несвободные фрагменты из страницы Q в новую чистую страницу (линейное время), подменяем новой страницей страницу Q, убиваем страницу Q. Помещаем нашу новую страницу в множество страниц где снова можно выделять память с конца (при этом её конец будет уже не в начале, т.к. какое-то кол-во памяти там уже сожрано).

Чтобы работала подмена страниц, юзеры такого аллокатора ссылаются на свои данные не просто указателем, а парой (page_idx, offset), где page_idx - индекс страницы в таблице страниц. То есть, подмена страниц будет делаться заменой указателя в нужном индексе этой таблицы. page_idx и offset могут быть размера 32 bit и 16 bit (если страница на неск. КБ), что суммарно будет не жирнее pointer. Для доступа к своему куску: data_ptr = table[page_idx] + offset. Доступ юзеру к началу страницы нужен, чтобы освобождающий поток мог делать работу с заголовком страницы по увеличению счётчика sum_free.