Здравствуйте, Pzz, Вы писали:

Pzz>2. Завести битовый массив занятости, по биту на каждый 64-байтовый блок (можно по байту, для ускорения доступа)

Можно в два раза меньше — по биту на 128-байтовый блок.
Этот блок может быть:
1) полностью чистым — тогда он находится в free-list'е 128 байтных блоков
2) занят на половину
3) занят полностью

Так вот, при освобождении 64-байтного блока нам только требуется информация 2) или 3), потому что 1) — быть не может (так как мы освобождаем его часть — значит этот 128-байтный блок точно не пустой).
Если занят на половину, значит "близнец" свободен, если полностью — то тоже занят.

Pzz>Списки понадобятся двунаправленные, чтобы можно было легко удалять элементы из середины.

Только для 64-байтных блоков. Для 128-байтных достаточно однонаправленного, так как там всегда идёт работа с головой. Это немного уменьшит возню с указателями.

P.S. По ситуации, можно завести дополнительный free-list из 64-байтных блоков, чтобы при аллокации/деаллокации не ходить в битовый массив, по-крайней мере пока не нужно будет заимствовать 128-байтные блоки.
Итого — пока нет заимствования, в битовый массив не мусолится ни 64-байтными операциями, ни 128-байтными. При заимствовании только 64-байтные операции будут дёргать битовый массив, а 128-байтные это никак не затронет.