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

Сегодня в этом выпуске мы напишем реализацию менеджера физической памяти. Его задача - найти N свободных физических страниц, пометить их как занятые и отдать адрес первой. А также обратную операцию - пометка блока физических страниц как свободных. Мне известно 4 различных алгоритма:

1) Стек страниц. Создаётся специальная структура данных - массив физических адресов, количество элементов равно количеству страниц физической памяти. При 32-битном адресе это будет лишь 1/1024 всей памяти. Когда нужна очередная страница достаётся верхняя страница стека, когда какая-то страница не нужна, она кладётся на верх стека. Это самый быстрый и простой алгоритм, но он имеет существенный недостаток - невозможность выделения блока последовательных страниц. А между тем это очень нужно драйверам - устройства-то не знают ничего про страничную адресацию.

2) Битовая карта страниц. Аналогично битовой карте в ListFS. Битовая карта занимает 1/32768 физической памяти. Из минусов следует отметить то, что это достаточно медленный вариант, а для оперативной памяти немаловажна скорость выделения (для блоков на жёстком диске такой алгоритм вполне приемлем). К тому же появляются трудности, если память представляет собой не непрерывный блок адресов, а то и вовсе может динамически добавляться.

3) Линейный список регионов памяти. Можно создать массив, в котором будет содержаться начало, конец и тип (занято/свободно) участков памяти. Этот вариант обладает наибольшей скоростью, но достаточно сложен в реализации - список во время работы системы постоянно меняет свою длину и надо как-то освобождать и выделять память под него самого.

4) Двунаправленный связанный список, располагающийся на свободных страницах памяти. Этот вариант немного медленнее третьего, зато обладает достаточной гибкостью и простотой. Суть в том, что в начале свободного блока физической памяти создаётся структура, в которой есть адрес предыдущего свободного блока, адрес следующего и размер текущего блока. С помощью temp_map_page мы можем получить доступ к заголовку любого из блоков. Максимальная сложность alloc_phys_pages - O(N) (N - количество разрозненных свободных блоков). free_phys_pages должен не просто помечать блок как свободный, но и дефрагментировать блоки памяти - если перед и/или после свободного блока памяти впритык существует ещё один их следует объединить. Для упрощения задачи можно поддерживать упорядоченность блоков по возрастанию адресов, тогда сложность free_phys_pages будет так же O(N).

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

Физический адрес первого свободно блока хранится в переменной free_phys_memory_pointer. Список двунаправленный для упрощения удаления и добавления элементов. Он ещё будет и кольцевым, чтобы не делать лишних проверок на NULL.

В первую очередь опишем структуру заголовка блока памяти (размер блока будем хранить в страницах, заодно, пусть некорректным физическим адресом будет -1, а не 0):

Теперь можно написать функцию выделения нового блока памяти из списка свободных:

phyaddr alloc_phys_pages(size_t count) {
	if (free_page_count < count) return -1;
	phyaddr result = -1;
	if (free_phys_memory_pointer != -1) {
		phyaddr cur_block = free_phys_memory_pointer;
		do {
			temp_map_page(cur_block);
			if (((PhysMemoryBlock*)TEMP_PAGE)->size == count) {
				phyaddr next = ((PhysMemoryBlock*)TEMP_PAGE)->next;
				phyaddr prev = ((PhysMemoryBlock*)TEMP_PAGE)->prev;
				temp_map_page(next);
				((PhysMemoryBlock*)TEMP_PAGE)->prev = prev;
				temp_map_page(prev);
				((PhysMemoryBlock*)TEMP_PAGE)->next = next;
				if (cur_block == free_phys_memory_pointer) {
					free_phys_memory_pointer = next;
					if (cur_block == free_phys_memory_pointer) {
						free_phys_memory_pointer = -1;
					}
				}
				result = cur_block;
				break;
			} else if (((PhysMemoryBlock*)TEMP_PAGE)->size > count) {
				((PhysMemoryBlock*)TEMP_PAGE)->size -= count;
				result = cur_block + (((PhysMemoryBlock*)TEMP_PAGE)->size << PAGE_OFFSET_BITS);
				break;
			}
			cur_block = ((PhysMemoryBlock*)TEMP_PAGE)->next;
			
		} while (cur_block != free_phys_memory_pointer);
		if (result != -1) {
			free_page_count -= count;
		} 
	}
	return result;
} 

Функция работает достаточно просто - если список свободных блоков пуст, либо общий объём свободной памяти меньше нужного, то она тут же возвращает -1, иначе же начинает перебирать все свободные блоки. Если попадается блок, который равен по размеру запрошенному, то его адрес возвращается в качестве результата, а сам блок удаляется из списка (рассматривается вариант, когда это был первый блок в списке, тогда надо изменить free_phys_memory_pointer, а также когда в списке больше не осталось элементов). Иначе, если блок был больше искомого, от его конца отрезается нужное число страниц и возвращается базовый адрес такого блока. Если в результате поиска блок нужного размера так и не был найден (хотя суммарно все регионы и подходят по размеру, но нет ни одного непрерывного блока нужной длинны), то функция завершается, возвращая -1. Для запросов небольшого количества страниц (чаще всего требуется 1 страница) эта функция вернётся уже после первой итерации цикла поиска.

Функция free_phys_pages сложнее, потому что её не только нужно вставить блок в нужное место в списке, но и по возможности слить его с другими. Возможно три варианта соседства блоков:

1) Новый блок после другого. Создавать новый блок не нужно, лишь увеличить size предыдущего.
2) Новый блок перед другим. Следует удалить следующий блок, а при создании предыдущего указать size больше.
3) Новый блок окружён двумя. Следует удалить следующих блок, а размер предыдущего увеличить на сумму размеров освобождаемого блока и следующего за ним.

Обработку этих ситуаций упростит упорядоченность списка блоков по базовым адресам.

void free_phys_pages(phyaddr base, size_t count) {
	if (free_phys_memory_pointer == -1) {
		temp_map_page(base);
		((PhysMemoryBlock*)TEMP_PAGE)->next = base;
		((PhysMemoryBlock*)TEMP_PAGE)->prev = base;
		((PhysMemoryBlock*)TEMP_PAGE)->size = count;
		free_phys_memory_pointer = base;
	} else {
		phyaddr cur_block = free_phys_memory_pointer;
		do {
			temp_map_page(cur_block);
			if (cur_block + (((PhysMemoryBlock*)TEMP_PAGE)->size << PAGE_OFFSET_BITS) == base) {
				((PhysMemoryBlock*)TEMP_PAGE)->size += count;
				if (((PhysMemoryBlock*)TEMP_PAGE)->next == base + (count << PAGE_OFFSET_BITS)) {
					phyaddr next1 = ((PhysMemoryBlock*)TEMP_PAGE)->next;
					temp_map_page(next1);
					phyaddr next2 = ((PhysMemoryBlock*)TEMP_PAGE)->next;
					size_t new_count = ((PhysMemoryBlock*)TEMP_PAGE)->size;
					temp_map_page(next2);
					((PhysMemoryBlock*)TEMP_PAGE)->prev = cur_block;
					temp_map_page(cur_block);
					((PhysMemoryBlock*)TEMP_PAGE)->next = next2;
					((PhysMemoryBlock*)TEMP_PAGE)->size += new_count;
				}
				break;
			} else if (base + (count << PAGE_OFFSET_BITS) == cur_block) {
				size_t old_count = ((PhysMemoryBlock*)TEMP_PAGE)->size;
				phyaddr next = ((PhysMemoryBlock*)TEMP_PAGE)->next;
				phyaddr prev = ((PhysMemoryBlock*)TEMP_PAGE)->prev;
				temp_map_page(next);
				((PhysMemoryBlock*)TEMP_PAGE)->prev = base;
				temp_map_page(prev);
				((PhysMemoryBlock*)TEMP_PAGE)->next = base;
				temp_map_page(base);
				((PhysMemoryBlock*)TEMP_PAGE)->next = next;
				((PhysMemoryBlock*)TEMP_PAGE)->prev = prev;
				((PhysMemoryBlock*)TEMP_PAGE)->size = count + old_count;
				break;
			} else if ((cur_block > base) || (((PhysMemoryBlock*)TEMP_PAGE)->next == free_phys_memory_pointer)) {
				phyaddr prev = ((PhysMemoryBlock*)TEMP_PAGE)->next;
				((PhysMemoryBlock*)TEMP_PAGE)->prev = base;
				temp_map_page(prev);
				((PhysMemoryBlock*)TEMP_PAGE)->next = base;
				temp_map_page(base);
				((PhysMemoryBlock*)TEMP_PAGE)->next = cur_block;
				((PhysMemoryBlock*)TEMP_PAGE)->prev = prev;
				((PhysMemoryBlock*)TEMP_PAGE)->size = count;
				break;
			}
			cur_block = ((PhysMemoryBlock*)TEMP_PAGE)->next;
		} while (cur_block != free_phys_memory_pointer);
		if (base < free_phys_memory_pointer) {
			free_phys_memory_pointer = base;
		}
		
	}
	free_page_count += count;
} 

Это, пожалуй, одна из самых запутанных функций нашего ядра, но я провёл различные проверки - она работает так, как нужно.

Итак, менеджер физической памяти готов, доведём до ума выделение памяти памяти под таблицу прерываний:

void init_interrupts() {
	map_pages(kernel_page_dir, idt, alloc_phys_pages(1), 1, PAGE_VALID | PAGE_WRITABLE);
	memset(idt, 0, 256 * sizeof(IntDesc));
	IDTR idtr = {256 * sizeof(IntDesc), idt};
	asm("lidt (,%0,)"::"a"(&idtr));
	irq_base = 0x20;
	irq_count = 16;
	outportb(0x20, 0x11);
	outportb(0x21, irq_base);
	outportb(0x21, 4);
	outportb(0x21, 1);
	outportb(0xA0, 0x11);
	outportb(0xA1, irq_base + 8);
	outportb(0xA1, 2);
	outportb(0xA1, 1);
	set_int_handler(irq_base, timer_int_handler, 0x8E);
	asm("sti");
} 

На этом заканчиваю сегодняшний выпуск, разве, что приведу полный код memory_manager.c, потому что мы его активно меняли:

#include "stdlib.h"
#include "memory_manager.h"

typedef struct {
	uint64 base;
	uint64 length;
	uint32 type;
	uint32 acpi_ext_attrs;
} __attribute__((packed)) MemoryMapEntry;

typedef struct {
	phyaddr next;
	phyaddr prev;
	size_t size;
} PhysMemoryBlock;

size_t free_page_count = 0;
phyaddr free_phys_memory_pointer = -1;

void init_memory_manager(void *memory_map) {
	asm("movl %%cr3, %0":"=a"(kernel_page_dir));
	memory_size = 0x100000;
	MemoryMapEntry *entry;
	for (entry = memory_map; entry->type; entry++) {
		if ((entry->type == 1) && (entry->base >= 0x100000)) {
			free_phys_pages(entry->base, entry->length >> PAGE_OFFSET_BITS);
			memory_size += entry->length;
		}
	}
}

/* Physical memory manager */

void temp_map_page(phyaddr addr) {
	*((phyaddr*)TEMP_PAGE_INFO) = (addr & ~PAGE_OFFSET_MASK) | PAGE_VALID | PAGE_WRITABLE;
	asm("invlpg (,%0,)"::"a"(TEMP_PAGE));
}

size_t get_free_memory_size() {
	return free_page_count << PAGE_OFFSET_BITS;
}

phyaddr alloc_phys_pages(size_t count) {
	if (free_page_count < count) return -1;
	phyaddr result = -1;
	if (free_phys_memory_pointer != -1) {
		phyaddr cur_block = free_phys_memory_pointer;
		do {
			temp_map_page(cur_block);
			if (((PhysMemoryBlock*)TEMP_PAGE)->size == count) {
				phyaddr next = ((PhysMemoryBlock*)TEMP_PAGE)->next;
				phyaddr prev = ((PhysMemoryBlock*)TEMP_PAGE)->prev;
				temp_map_page(next);
				((PhysMemoryBlock*)TEMP_PAGE)->prev = prev;
				temp_map_page(prev);
				((PhysMemoryBlock*)TEMP_PAGE)->next = next;
				if (cur_block == free_phys_memory_pointer) {
					free_phys_memory_pointer = next;
					if (cur_block == free_phys_memory_pointer) {
						free_phys_memory_pointer = -1;
					}
				}
				result = cur_block;
				break;
			} else if (((PhysMemoryBlock*)TEMP_PAGE)->size > count) {
				((PhysMemoryBlock*)TEMP_PAGE)->size -= count;
				result = cur_block + (((PhysMemoryBlock*)TEMP_PAGE)->size << PAGE_OFFSET_BITS);
				break;
			}
			cur_block = ((PhysMemoryBlock*)TEMP_PAGE)->next;
			
		} while (cur_block != free_phys_memory_pointer);
		if (result != -1) {
			free_page_count -= count;
		} 
	}
	return result;
}

void free_phys_pages(phyaddr base, size_t count) {
	if (free_phys_memory_pointer == -1) {
		temp_map_page(base);
		((PhysMemoryBlock*)TEMP_PAGE)->next = base;
		((PhysMemoryBlock*)TEMP_PAGE)->prev = base;
		((PhysMemoryBlock*)TEMP_PAGE)->size = count;
		free_phys_memory_pointer = base;
	} else {
		phyaddr cur_block = free_phys_memory_pointer;
		do {
			temp_map_page(cur_block);
			if (cur_block + (((PhysMemoryBlock*)TEMP_PAGE)->size << PAGE_OFFSET_BITS) == base) {
				((PhysMemoryBlock*)TEMP_PAGE)->size += count;
				if (((PhysMemoryBlock*)TEMP_PAGE)->next == base + (count << PAGE_OFFSET_BITS)) {
					phyaddr next1 = ((PhysMemoryBlock*)TEMP_PAGE)->next;
					temp_map_page(next1);
					phyaddr next2 = ((PhysMemoryBlock*)TEMP_PAGE)->next;
					size_t new_count = ((PhysMemoryBlock*)TEMP_PAGE)->size;
					temp_map_page(next2);
					((PhysMemoryBlock*)TEMP_PAGE)->prev = cur_block;
					temp_map_page(cur_block);
					((PhysMemoryBlock*)TEMP_PAGE)->next = next2;
					((PhysMemoryBlock*)TEMP_PAGE)->size += new_count;
				}
				break;
			} else if (base + (count << PAGE_OFFSET_BITS) == cur_block) {
				size_t old_count = ((PhysMemoryBlock*)TEMP_PAGE)->size;
				phyaddr next = ((PhysMemoryBlock*)TEMP_PAGE)->next;
				phyaddr prev = ((PhysMemoryBlock*)TEMP_PAGE)->prev;
				temp_map_page(next);
				((PhysMemoryBlock*)TEMP_PAGE)->prev = base;
				temp_map_page(prev);
				((PhysMemoryBlock*)TEMP_PAGE)->next = base;
				temp_map_page(base);
				((PhysMemoryBlock*)TEMP_PAGE)->next = next;
				((PhysMemoryBlock*)TEMP_PAGE)->prev = prev;
				((PhysMemoryBlock*)TEMP_PAGE)->size = count + old_count;
				break;
			} else if ((cur_block > base) || (((PhysMemoryBlock*)TEMP_PAGE)->next == free_phys_memory_pointer)) {
				phyaddr prev = ((PhysMemoryBlock*)TEMP_PAGE)->next;
				((PhysMemoryBlock*)TEMP_PAGE)->prev = base;
				temp_map_page(prev);
				((PhysMemoryBlock*)TEMP_PAGE)->next = base;
				temp_map_page(base);
				((PhysMemoryBlock*)TEMP_PAGE)->next = cur_block;
				((PhysMemoryBlock*)TEMP_PAGE)->prev = prev;
				((PhysMemoryBlock*)TEMP_PAGE)->size = count;
				break;
			}
			cur_block = ((PhysMemoryBlock*)TEMP_PAGE)->next;
		} while (cur_block != free_phys_memory_pointer);
		if (base < free_phys_memory_pointer) {
			free_phys_memory_pointer = base;
		}
		
	}
	free_page_count += count;
}

/* Virtual memory manager */

bool map_pages(phyaddr page_dir, void *vaddr, phyaddr paddr, size_t count, unsigned int flags) {
	for (; count; count--) {
		phyaddr page_table = page_dir;
		char shift;
		for (shift = PHYADDR_BITS - PAGE_TABLE_INDEX_BITS; shift >= PAGE_OFFSET_BITS; shift -= PAGE_TABLE_INDEX_BITS) {
			unsigned int index = ((size_t)vaddr >> shift) & PAGE_TABLE_INDEX_MASK;
			temp_map_page(page_table);
			if (shift > PAGE_OFFSET_BITS) {
				page_table = ((phyaddr*)TEMP_PAGE)[index];
				if (!(page_table & PAGE_VALID)) {
					phyaddr addr = alloc_phys_pages(1);
					if (addr != -1) {
						temp_map_page(paddr);
						memset((void*)TEMP_PAGE, 0, PAGE_SIZE);
						temp_map_page(page_table);
						((phyaddr*)TEMP_PAGE)[index] = addr | PAGE_VALID | PAGE_WRITABLE | PAGE_USER;
						page_table = addr;
					} else {
						return false;
					}
				}
			} else {
				((phyaddr*)TEMP_PAGE)[index] = (paddr & ~PAGE_OFFSET_BITS) | flags;
				asm("invlpg (,%0,)"::"a"(vaddr));
			}
		}
		vaddr += PAGE_SIZE;
		paddr += PAGE_SIZE;
	}
	return true;
}

phyaddr get_page_info(phyaddr page_dir, void *vaddr) {
	phyaddr page_table = page_dir;
	char shift;
	for (shift = PHYADDR_BITS - PAGE_TABLE_INDEX_BITS; shift >= PAGE_OFFSET_BITS; shift -= PAGE_TABLE_INDEX_BITS) {
		unsigned int index = ((size_t)vaddr >> shift) & PAGE_TABLE_INDEX_MASK;
		temp_map_page(page_table);
		if (shift > PAGE_OFFSET_BITS) {
			page_table = ((phyaddr*)TEMP_PAGE)[index];
			if (!(page_table & PAGE_VALID)) {
				return 0;
			}
		} else {
			return ((phyaddr*)TEMP_PAGE)[index];
		}
	}
} 

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

typedef struct {
        phyaddr page_dir;
        void *start;
        void *end;
} AddressSpace;

void *alloc_virt_pages(AddressSpace *as, void *vaddr, phyaddr paddr, size_t count, unsigned int flags);
void free_virt_pages(AddressSpace *as, void *vaddr, size_t count, unsigned int flags);

Опишу параметры каждой из функций:

alloc_virt_pages:
as - адресное пространство, в котором производится работа. Структура AddressSpace может содержать дополнительную информацию (нужную для поиска свободных страниц). У каждого процесса в системе свой AddressSpace (всегда нижние 2 ГБ), плюс у ядра свой AddressSpace общий для всех каталогов страниц (верхние 2 ГБ). Возвращённый функцией адрес должен принадлежать региону от as->start до as->end, либо NULL в случае ошибки.
vaddr - Желаемый виртуальный адрес. Если равен NULL, функция должна найти сама свободный виртуальный адрес, куда можно примонтировать count страниц (это и есть самое сложное - как искать лучше), иначе функция должна спроецировать страницы по этому адресу при условии, что он не выходит за пределы AddressSpace (as->start <= vaddr < as->end) и на этом месте ничего не примонтировано до этого вызова.
paddr - Желаемый физический адрес. Например, драйвер может захотеть примонтировать страницу 0xB8000 для работы с текстовым экраном. Если равно -1, функция должна вызвать alloc_phys_pages(count) и использовать его результат (если не произойдёт ошибки выделения памяти, тогда придётся вернуть NULL и ничего не проецировать).
count - Количество страниц для проецирования.
flags - Атрибуты доступа для проецирования. Аналогично одноимённому параметры map_pages.

free_virt_pages:
as - Аналогично alloc_virt_pages.
vaddr - Виртуальный адрес блока страниц, который следует освободить. Должен принадлежать адресному пространству as и быть не равен NULL.
count - Количество страниц для освобождения.
flags - Флаги освобождения. Позволяет запретить функции освобождать страницы без флага PAGE_USER. Нужно для того, чтобы не дать приложению уничтожить системные структуры.

Вот так. Свои предложения по механизму хранения свободных страниц и их поиска, можете присылать мне на почту: kiv.apple@gmail.com. До встречи! ;-)