Написание собственного неплохого менеджера памяти

Доброе время суток, читатель. Возможно, вы уже читали мои предыдущие статьи, и знаете, что я занимаюсь написанием собственной ОС. Сегодня мы поговорим, и рассмотрим несложный и достаточно быстрый алгоритм для управления памятью — менеджер памяти — критически важная часть ОС, ведь быстрая, надежная и нерастратная работа с памятью залог хорошей ОС.
Искал я несложные и адекватные идеи для менеджера и в рунете, и на англоязычных сайтах — всё никак не мог найти никаких хороших статей про адекватный, работающий не за O(N) аллокатор. Что же, сегодня мы рассмотрим более хорошую идею для менеджера памяти, продолжение помещаю под кат.

Теория

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

Предлагаю так же перед продолжением прочитать эту статью.

Watermak Allocator

Что же, наверное самый простой из всех аллокаторов — Watermark Allocator. Суть его примерно следующая: вся память разбита на блоки, у блока есть заголовок, в котором лежит размер этого и предыдущего блока, статус блока(занят/свободен), зная адрес блока мы за O(1) можем получить адрес следующего и предыдущего блока.

Выделение памяти

Для выделения памяти нам просто напросто нужно бежать по блокам, и искать блок, размер которого больше или равен размеру требуемой для выделения памяти. Как вы уже поняли, асимптотика O(N) — плохо.

Высвобождение памяти

Для высвобождения памяти нам достаточно установить статус блока как «свободный» — O(1) — супер!

Но, как вы понимаете, могут начать образовываться дыры, в которых 2 и более свободных блоков — память дефрагментированна, при высвобождении можно просматривать соседние блоки, и в случае, когда один или два свободны — мержить их в один.

Аллокатор за логарифмическую скорость

Мы знаем, что нам надо искать только среди свободных блоков. Бегать только по свободным улучшает скорость в среднем в два раза, но это всё равно линия. Что же, зачем нам бегать по всем блокам, ища размер, если мы можем организовать дерево из свободных блоков! Изначально у нас только один свободный блок, а дальше мы добавляем свободные блоки в бинарное дерево поиска, ключом будет — размер блока. Таким образом, чтобы выделить память нам достаточно найти блок в дереве, у которого размер больше или равен тому, что нам нужен. Это мы спокойно делаем за O(log N), просто спускаясь по дереву вниз. Дальше мы либо режем блок на два, либо полностью отдаем его тому, кто запросил память. Дальше мы удаляем блок из дерева за O(1). И, если надо, вставляем оставшуюся часть блока обратно за O(log N). Для высвобождения нам достаточно вставить блок обратно, и не надо забывать про фрагментацию.

Логично, что использовать простое дерево не надо, надо использовать самобалансирующееся дерево, Red-Black или AVL. Хранить дерево блоков можно в статическом массиве, или же придумать как это сделать по-другому.

Собственно, код:

char * malloc(size_t size) {
	if (!size) {
		return 0;
	}
	char * addr = 0;
	int i;
	for (i = 0; i < allocationAvlTree.size; )
	{
		int r;
		node_t *n;
		n = &allocationAvlTree.nodes[i];
		/* couldn't find it */
		if (!n->key) {
			return NULL;
		}
		r = allocationAvlTree.cmp(n->key, size);
		if (r <= 0)
		{
			//We're lucky today.
			//Get memory block header
			alloc_t * block = (size_t)n->val - sizeof(alloc_t);
			//Set to used
			block->status = 1;
			//Set size
			block->size = size;
			alloc_t * next = (size_t)n->val + size;
			next->prev_size = size;
			next->status = 0;
			next->size = n->key - size - 16;
			avltree_remove(&allocationAvlTree, n->key, n->val);
			if (n->key - size - 16)
				avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t));
			memset((size_t)block + sizeof(alloc_t), 0, block->size); 
			block->signature = 0xDEADBEEF;
			unlockTaskSwitch();
			return (size_t)block + sizeof(alloc_t);
		}
		else if (r > 0)
			i = __child_r(i);
		else
			assert(0);
	}
	return 0;
}

void free(void * mem) {
	if (!mem)
		return;
	//Get current alloc
	alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t));
	if (alloc->signature != 0xDEADBEEF)
		return;
	alloc->status = 0;
	alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size);
	if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size)
	{
		//Merge blocks
		if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) {
			left->size += sizeof(alloc_t) + alloc->size;
			alloc = left;
		}
		else assert(0);
	}
	alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size;
	if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF)
	{
		if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t)))
			alloc->size += sizeof(alloc_t) + right->size;
		else assert(0);
	}
	avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t));

}

Удачи и этичного хакинга! Любая объективная критика приветствуется, цель статьи не сказать, что это вах какой аллокатор, а просто рассказать о аллокаторе, который будет лучше, чем тупые реализации простых аллокаторов.