OSDEV: Разработка аллокатора на С++ часть 1. Неявный список свободных блоков с граничными тегами

Доброго времени суток.

При разработке ОС на с++ мы сталкиваемся с рядом трудностей, таких как отсутствие стандартной библиотеки и ABI с++ и прочее в этом духе. При чем перед реализацией PageAllocator и прочих аппаратных механизмов хотелось бы иметь какую то стандартную библиотеку позволяющую делать хоть что то. Об этом и пойдет речь.

Далее я расскажу о своем опыте разработки таких алгоритмов для своей ОС и о том, как их тестировать у себя на системе с юнит тестами и прочим прикручивая в итоговую демку проверенный тестами код, и начну я с аллокатора.

Речь пойдет о немного переделанном алгоритме Кнута "неявный список блоков с граничными тегами" который описан в конце третьего тома в разделе "Распределение памяти". Его идея предельно проста:

Мы берем некоторый отрезок памяти, назовем его кучей и разбиваем его на блоки такого вида: