Отправляет email-рассылки с помощью сервиса Sendsay

Пишем свою операционную систему

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 200 RSS
←   Август 2012   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
15.08.2012
18:17:14
20:48:06
16
17
18
19
20
21
22
23
24
24.08.2012
04:51:38
04:51:51
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 28-06-2012

Автор
kiv.apple@gmail.com

Статистика

200 подписчиков
0 за неделю
←   Все выпуски   →

Пишем свою операционную систему Менеджер виртуальной памяти


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

Для начала исправим небольшую ошибку в map_pages:

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) {
				size_t prev_page_table = page_table;
				page_table = ((volatile phyaddr*)TEMP_PAGE)[index];
				if (!(page_table & PAGE_PRESENT)) {
					phyaddr addr = alloc_phys_pages(1);
					if (addr != -1) {
						temp_map_page(addr);
						memset((void*)TEMP_PAGE, 0, PAGE_SIZE);
						temp_map_page(prev_page_table);
						((volatile phyaddr*)TEMP_PAGE)[index] = addr | PAGE_PRESENT | PAGE_WRITABLE | PAGE_USER;
						page_table = addr;
					} else {
						return false;
					}
				}
			} else {
				((volatile phyaddr*)TEMP_PAGE)[index] = (paddr & ~PAGE_OFFSET_BITS) | flags;
				flush_page_cache(vaddr);
			}
		}
		vaddr += PAGE_SIZE;
		paddr += PAGE_SIZE;
	}
	return true;
}

Теперь, финальная версия memory_manager.h:

#ifndef MEMORY_MANAGER_H
#define MEMORY_MANAGER_H

#include "stdlib.h"

#define PAGE_SIZE 0x1000
#define PAGE_OFFSET_BITS 12
#define PAGE_OFFSET_MASK 0xFFF
#define PAGE_TABLE_INDEX_BITS 10
#define PAGE_TABLE_INDEX_MASK 0x3FF

#define PHYADDR_BITS 32

#define PAGE_PRESENT		(1 << 0)
#define PAGE_WRITABLE		(1 << 1)
#define PAGE_USER		(1 << 2)
#define PAGE_WRITE_THROUGH	(1 << 3)
#define PAGE_CACHE_DISABLED	(1 << 4)
#define PAGE_ACCESSED		(1 << 5)

#define PAGE_MODIFIED		(1 << 6)
#define PAGE_GLOBAL		(1 << 8)

void KERNEL_BASE();
void KERNEL_CODE_BASE();
void KERNEL_DATA_BASE();
void KERNEL_BSS_BASE();
void KERNEL_END();

#define KERNEL_PAGE_TABLE ((void*)0xFFFFE000)
#define TEMP_PAGE ((void*)0xFFFFF000)
#define TEMP_PAGE_INFO ((size_t)KERNEL_PAGE_TABLE + (((size_t)TEMP_PAGE >> PAGE_OFFSET_BITS) & PAGE_TABLE_INDEX_MASK) * sizeof(phyaddr))

#define USER_MEMORY_START ((void*)0)
#define USER_MEMORY_END ((void*)0x7FFFFFFF)
#define KERNEL_MEMORY_START ((void*)0x80000000)
#define KERNEL_MEMORY_END ((void*)(KERNEL_BASE - 1))

typedef size_t phyaddr;

typedef enum {
	VMB_RESERVED,
	VMB_MEMORY,
	VMB_IO_MEMORY
} VirtMemoryBlockType;

typedef struct {
	VirtMemoryBlockType type;
	void *base;
	size_t length;
} VirtMemoryBlock;

typedef struct {
	phyaddr page_dir;
	void *start;
	void *end;
	size_t block_table_size;
	size_t block_count;
	VirtMemoryBlock *blocks;
} AddressSpace;

phyaddr kernel_page_dir;
size_t memory_size;
AddressSpace kernel_address_space;

void init_memory_manager(void *memory_map);

size_t get_free_memory_size();
phyaddr alloc_phys_pages(size_t count);
void free_phys_pages(phyaddr base, size_t count);

void temp_map_page(phyaddr addr);
bool map_pages(phyaddr page_dir, void *vaddr, phyaddr paddr, size_t count, unsigned int flags);
phyaddr get_page_info(phyaddr page_dir, void *vaddr);

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

#endif

Теперь следует усовершенствовать код memcpy, чтобы он полностью корректно обрабатывал перекрывающиеся блоки памяти (ошибки в коде нет, просто реализация была упрощённой):

void memcpy(void *dest, void *src, size_t count) {
	if (dest < src) {
		asm("movl %0, %%edi \n movl %1, %%esi \n movl %2, %%ecx \n rep movsl"::"a"(dest),"b"(src),"c"(count >> 2));
		asm("movl %0, %%ecx \n rep movsb"::"a"(count & 3));
	} else {
		asm("std");
		asm("movl %0, %%edi \n movl %1, %%esi \n movl %2, %%ecx \n rep movsb"::"a"(dest + count),"b"(src + count),"c"(count & 3));
		asm("movl %0, %%ecx \n rep movsl"::"c"(count >> 2));
		asm("cld");
	}
}

А теперь собственно реализация функций alloc_virt_pages и free_virt_pages:

/* Highlevel virtual memory manager */

static inline bool is_blocks_overlapped(void *base1, size_t size1, void *base2, size_t size2) {
	return ((base1 >= base2) && (base1 < base2 + size2)) || ((base2 >= base1) && (base2 < base1 + size1));
}

void *alloc_virt_pages(AddressSpace *address_space, void *vaddr, phyaddr paddr, size_t count, unsigned int flags) {
	VirtMemoryBlockType type = VMB_IO_MEMORY;
	size_t i;
	if (vaddr == NULL) {
		vaddr = address_space->end - (count << PAGE_OFFSET_BITS) + 1;
		for (i = 0; i < address_space->block_count; i++) {
			if (is_blocks_overlapped(address_space->blocks[i].base, address_space->blocks[i].length, vaddr, count)) {
				vaddr = address_space->blocks[i].base - (count << PAGE_OFFSET_BITS);
			} else {
				break;
			}
		}
	} else {
		if ((vaddr >= address_space->start) && (vaddr + (count << PAGE_OFFSET_BITS) < address_space->end)) {
			for (i = 0; i < address_space->block_count; i++) {
				if (is_blocks_overlapped(address_space->blocks[i].base, address_space->blocks[i].length, vaddr, count << PAGE_OFFSET_BITS)) {
					vaddr = NULL;
					break;
				} else if (address_space->blocks[i].base < vaddr) {
					break;
				}
			}
		} else {
			vaddr = NULL;
		}
	}
	if (vaddr != NULL) {
		if (paddr == -1) {
			paddr = alloc_phys_pages(count);
			type = VMB_MEMORY;
		}
		if (paddr != -1) {
			if (map_pages(address_space->page_dir, vaddr, paddr, count, flags)) {
				if (address_space->block_count == address_space->block_table_size) {
					size_t new_size = address_space->block_table_size * sizeof(VirtMemoryBlock);
					new_size = (new_size + PAGE_OFFSET_MASK) & ~PAGE_OFFSET_MASK;
					new_size += PAGE_SIZE;
					new_size = new_size >> PAGE_OFFSET_BITS;
					if (&kernel_address_space != address_space) {
						VirtMemoryBlock *new_table = alloc_virt_pages(&kernel_address_space, NULL, -1, new_size,	
							PAGE_PRESENT | PAGE_WRITABLE);
						if (new_table) {
							memcpy(new_table, address_space->blocks, address_space->block_table_size * sizeof(VirtMemoryBlock));
							free_virt_pages(&kernel_address_space, address_space->blocks, 0);
							address_space->blocks = new_table;
						} else {
							goto fail;
						}
					} else {
						phyaddr new_page = alloc_phys_pages(1);
						if (new_page == -1) {
							goto fail;
						} else {
							VirtMemoryBlock *main_block = &(address_space->blocks[address_space->block_count - 1]);
							if (map_pages(address_space->page_dir, main_block->base + main_block->length, new_page, 1,
									PAGE_PRESENT | PAGE_WRITABLE)) {
								main_block->length += PAGE_SIZE;
							} else {
								free_phys_pages(new_page, 1);
							}
						}
					}
					address_space->block_table_size = (new_size << PAGE_OFFSET_BITS) / sizeof(VirtMemoryBlock);
				}
				memcpy(address_space->blocks + i + 1, address_space->blocks + i,
					(address_space->block_count - i) * sizeof(VirtMemoryBlock));
				address_space->block_count++;
				address_space->blocks[i].type = type;
				address_space->blocks[i].base = vaddr;
				address_space->blocks[i].length = count << PAGE_OFFSET_BITS;
			} else {
fail:
				map_pages(address_space->page_dir, vaddr, 0, count, 0);
				free_phys_pages(paddr, count);
				vaddr = NULL;
			}
		}
	}
	return vaddr;
}

bool free_virt_pages(AddressSpace *address_space, void *vaddr, unsigned int flags) {
	size_t i;
	for (i = 0; i < address_space->block_count; i++) {
		if ((address_space->blocks[i].base <= vaddr) && (address_space->blocks[i].base + address_space->blocks[i].length > vaddr)) {
			break;
		}
	}
	if (i < address_space->block_count) {
		if (address_space->blocks[i].type = VMB_MEMORY) {
			free_phys_pages(get_page_info(address_space->page_dir, vaddr) & ~PAGE_OFFSET_MASK, address_space->blocks[i].length >> PAGE_OFFSET_BITS);
		}
		address_space->block_count--;
		memcpy(address_space->blocks + i, address_space->blocks + i + 1, (address_space->block_count - i) * sizeof(VirtMemoryBlock));
		return true;
	} else {
		return false;
	}
} 

Все таблицы блоков хранятся в адресном пространстве ядра. При необходимости они могут расширяться (по сути это динамический массив). Выделение адресов начинается с конца адресного пространства. Почти полностью реализована обработка ошибок выделения памяти (для личных адресных пространств процессов полностью, для адресного пространства ядра - нет).

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

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;
		}
	}
	map_pages(kernel_page_dir, KERNEL_CODE_BASE, get_page_info(kernel_page_dir, KERNEL_CODE_BASE),
		((size_t)KERNEL_DATA_BASE - (size_t)KERNEL_CODE_BASE) >> PAGE_OFFSET_BITS, PAGE_PRESENT | PAGE_GLOBAL);
	map_pages(kernel_page_dir, KERNEL_DATA_BASE, get_page_info(kernel_page_dir, KERNEL_DATA_BASE),
		((size_t)KERNEL_END - (size_t)KERNEL_DATA_BASE) >> PAGE_OFFSET_BITS, PAGE_PRESENT | PAGE_WRITABLE | PAGE_GLOBAL);
	map_pages(kernel_page_dir, KERNEL_PAGE_TABLE, get_page_info(kernel_page_dir, KERNEL_PAGE_TABLE), 1, PAGE_PRESENT | PAGE_WRITABLE | PAGE_GLOBAL);
	kernel_address_space.page_dir = kernel_page_dir;
	kernel_address_space.start = KERNEL_MEMORY_START;
	kernel_address_space.end = KERNEL_MEMORY_END;
	kernel_address_space.block_table_size = PAGE_SIZE / sizeof(VirtMemoryBlock);
	kernel_address_space.blocks = KERNEL_MEMORY_START;
	kernel_address_space.block_count = 1;
	map_pages(kernel_page_dir, kernel_address_space.blocks, alloc_phys_pages(1), 1, PAGE_PRESENT | PAGE_WRITABLE);
	kernel_address_space.blocks[0].type = VMB_RESERVED;
	kernel_address_space.blocks[0].base = kernel_address_space.blocks;
	kernel_address_space.blocks[0].length = PAGE_SIZE;
} 

Ну вот и готово. В качестве демонстрации будем выделять память для видео-буфера и таблицы прерываний динамически.

interrupts.c:

...

IntDesc *idt;

void timer_int_handler();

void init_interrupts() {
	idt = alloc_virt_pages(&kernel_address_space, NULL, -1, 1, PAGE_PRESENT | PAGE_WRITABLE | PAGE_GLOBAL);
	memset(idt, 0, 256 * sizeof(IntDesc));
	volatile IDTR idtr = {256 * sizeof(IntDesc), idt};
	asm("lidt (,%0,)"::"a"(&idtr));
	irq_base = 0x20;
	irq_count = 16;
        ... 

tty.c:

#include <stdarg.h>
#include "stdlib.h"
#include "memory_manager.h"
#include "interrupts.h"
#include "tty.h"
#include "scancodes.h"

 ...

void init_tty() {
	tty_buffer = alloc_virt_pages(&kernel_address_space, NULL, 0xB8000, 1, PAGE_PRESENT | PAGE_WRITABLE);
	tty_width = *((uint16*)0x44A);
	tty_height = 25;
	tty_io_port = *((uint16*)0x463);
	cursor = (*((uint8*)0x451)) * tty_width + (*((uint8*)0x450));
	text_attr = 7;
	set_int_handler(irq_base + 1, keyboard_int_handler, 0x8E);
} 

А в kernel_main добавим необязательную демонстрацию внутренностей управления памятью:

#include "stdlib.h"
#include "memory_manager.h"
#include "interrupts.h"
#include "tty.h"

typedef struct {
	uint64 base;
	uint64 size;
} BootModuleInfo;

uint32 *idt;

void kernel_main(uint8 boot_disk_id, void *memory_map, BootModuleInfo *boot_module_list) {
	init_memory_manager(memory_map);
	init_interrupts();
	init_tty();
	set_text_attr(15);
	printf("Welcome to MyOS!\n");
	int i;
	for (i = 0; i < kernel_address_space.block_count; i++) {
		printf("type = %d, base = 0x%x, length = 0x%x\n", kernel_address_space.blocks[i].type, kernel_address_space.blocks[i].base,
			kernel_address_space.blocks[i].length);
	}
	char string[10];
	in_string(string, sizeof(string));
	out_string(string);
} 

Вот и всё! Теперь у нас есть относительно полноценный менеджер памяти (не хватает только реализации подкачки памяти и выделения блоков произвольного размера, а не только кратного размеру страницы, однако первое нам пока делать рано, а второе можно переложить на плечи прикладных программ, если писать микроядро).

Замечание по использованию менеджера памяти:

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

2) В init_memory_manager, init_interrupts и init_tty я не произвожу проверку успешности выделения оперативной памяти, потому что вряд ли нашу ОС запустят на компьютере с объёмом памяти менее двух мегабайт. Да и если такие извращенцы найдутся, то не вижу ничего плохого в том, чтобы система упала - всё равно у нас даже драйвер экрана без верхней (выше 1 МБ) памяти не сможет работать. Однако вы, особенно если будете манипулировать большими блоками памяти, должны проверять, что alloc_virt_pages вернул не NULL (признак того, что по какой-то причине выделить память не удалось).

На этом заканчиваю этот выпуск. Все вопросы вы можете задать на мой электронный адрес - kiv.apple@gmail.com. 
В избранное