What is next after implementing paging?

[Awe2K]

Hi, I've already implemented simple text output, irq/isr/gdt/idt/etc and very simple paging, so what should be done next? Multitasking or something else?

Also, here's my paging code.
I haven't found good tutorials/examples on how to set paging up, so I've did it myself.

Code: Select all

/*
 * paging.c
 *
 *  Created on: Oct 26, 2015
 *      Author: awe2k
 */

#define MAPPED_TABLES 32
// I mapped (64 tables)*(1024 pages)*(4096 bytes)=128MB
#if !MAPPED_TABLES||MAPPED_TABLES>128*1024*1024/4096/1024
#error "Too much tables would be mapped. We don't have enough RAM"
#endif

#define HAVEFUN 0
// Maps video memory (0xB8000) to (0x0)

unsigned int dirn(unsigned int virt) {
	return virt >> 22;
}

unsigned int tabn(unsigned int virt) {
	return (virt >> 12) % 1024;
}

// Array of pointers to my page tables
unsigned int* page_directory[1024] __attribute__((aligned(4096)));
// Array of my tables, where pages are stored
unsigned int page_tables[MAPPED_TABLES][1024] __attribute__((aligned(4096)));

void map_addr(unsigned int* virt, unsigned int* phys, unsigned int flags) {
	// Both virt and phys MUST BE 0x1000 ALIGNED!
	// I don't care of aligning them, as they're aligned (i*0x1000) in cycle

	unsigned int table_index = (unsigned int) virt / 0x1000 % 1024;
	unsigned int directory_index = (unsigned int) virt / 0x1000 / 1024;
	page_tables[directory_index][table_index] = (unsigned int) phys | 3;
}

extern void loadPageDirectory(unsigned int*);
extern void enablePaging();

void paging() {
	int i, j;
	for (i = 0; i < 1024; i++) {
		// Supervisor, not present, R/W
		page_directory[i] = 0x00000002;
	}
	// For every table that should be mapped
	for (i = 0; i < MAPPED_TABLES; i++)
		// Tell that it's present, R/W, supervisor and leave ptr to it
		page_directory[i] = (unsigned int) page_tables[i] | 3;

	// Size in pages to be mapped
	int sz = MAPPED_TABLES * 1024;

	// Map every page
	for (i = 0; i < sz; i++) {
		map_addr(i * 0x1000, i * 0x1000, 3);
	}


#if HAVEFUN
	page_tables[0][0]=0xB8000|3;
	page_directory[0]=(unsigned int)page_tables[0]|3;
#endif

	// Obviously, loads pagedir
	loadPageDirectory(page_directory);

	put_string("CR0=");
	put_hex(read_cr0());
	put_char('\n');

	// Obviously, enables paging
	enablePaging();

	put_string("CR0=");
	put_hex(read_cr0());
	put_char('\n');
}

Also, added option HAVEFUN to (test?) map video memory to zero.

[Roman]

Hi, I think that the next things are the page allocation and the heap.

[Awe2K]

Hi, I think that the next things are the page allocation and the heap.

So, I just have to use some kind of bitmap to determine which pages are free, or there're other ways to allocate pages?

Does heap mean malloc and free?

[Awe2K]

Also, isn't my code too bad for further going? Just afraid it can crash when I implement something else.

Should page allocator code return pointer to virtual memory or physical?

[Awe2K]

Code: Select all

// Obviously, returns 1 if selected page state is 0
unsigned char isfree(unsigned int* virt) {
	unsigned int table_index = (unsigned int) virt / 0x1000 % 1024; // We assume virt is page-aligned
	unsigned int directory_index = (unsigned int) virt / 0x1000 / 1024;
	return page_alloc_bitmap[directory_index][table_index] == 0;
}

// Obviously, sets state of page (1 - allocated, 0 - free)
void mark(unsigned int* virt, unsigned char state) {
	unsigned int table_index = (unsigned int) virt / 0x1000 % 1024; // We assume virt is page-aligned
	unsigned int directory_index = (unsigned int) virt / 0x1000 / 1024;
	page_alloc_bitmap[directory_index][table_index] = state;
}
void* allocatePage() {
	int i = 0;
	for (i = ((unsigned int)ALLOC_START/0x1000); i < MAPPED_TABLES * 1024; i++) { // Start with ALLOC_START (end of kernel) not to allocate restricted memory
        // Just run through bitmap and check if selected page is free
		unsigned char f = isfree(i * 0x1000);
		if (f) {
        // Then mark it as used and return its address
			mark(i * 0x1000, 1);
			return i * 0x1000;
		}
	}
	put_string("\n\nDammit, no free pages!");
	while (1)
		;
}

// Clone the whole page directory
unsigned int* clone_dir() {
	// Here I allocate memory for directory and tables
	// Pagedir size: 1024*64
	unsigned int* cloned_dir = allocatePage();// 1024 * sizeof(int) = 4096, 1 page is enough
	unsigned int** cloned_tables = allocatePage();// 64 * 1024 * sizeof(int) = 262144, 64 pages for entries + 1 page for pointers

	int i;
	for (i = 0; i < MAPPED_TABLES; i++) {
		cloned_tables[i] = allocatePage();
	}

	// Here I clone it:
	// 1. Clone page tables
	int j;
	for (i = 0; i < MAPPED_TABLES; i++) {
		// I - table index
		// J - page index
		for (j = 0; j < 1024; j++) {
			cloned_tables[i][j] = page_tables[i][j]; // Just copy it
		}
	}
	// 2. Clone the whole directory
	for (i = 0; i < 1024; i++) {
		cloned_dir[i] = page_directory[i]; // both page_directory and page_tables are kernel and mapped to identity
	}

	// 3. Make it point to cloned tables
	for (i = 0; i < MAPPED_TABLES; i++) {
		cloned_dir[i] = (unsigned int) cloned_tables[i] | 3;
	}

	// Return result
	return cloned_dir;
}

Here I clone my kernel page directory. It's identity-mapped. Does using bit maps in allocator hurt my small kernel's performance?

[onlyonemac]

Yes the next thing is the page allocator a.k.a. virtual memory manager. This is not exactly like malloc and free, because malloc and free don't work on a page level but work by allocating one or more pages and then allocating the requested memory from within these pages, but the idea is similar. Basically it's the thing that other parts of your kernel and, in the beginning, user-space programs can go to to say "I need a block of memory, where can I find one" and then it allocates the block of memory and returns a pointer to it. So you want to return pointers to the virtual addresses as the caller doesn't have any concept of physical addresses, and it's up to the allocater to keep track of which virtual addresses map to which physical addresses (actually quite an easy task, if you just read the page tables themselves). And having a bitmap to keep track of allocated pages is a very common way of doing it, so I wouldn't worry about the performance of that - you normally use one bit in the bitmap to correspond to each 4k page.

[Awe2K]

Yes the next thing is the page allocator a.k.a. virtual memory manager. This is not exactly like malloc and free, because malloc and free don't work on a page level but work by allocating one or more pages and then allocating the requested memory from within these pages, but the idea is similar. Basically it's the thing that other parts of your kernel and, in the beginning, user-space programs can go to to say "I need a block of memory, where can I find one" and then it allocates the block of memory and returns a pointer to it. So you want to return pointers to the virtual addresses as the caller doesn't have any concept of physical addresses, and it's up to the allocater to keep track of which virtual addresses map to which physical addresses (actually quite an easy task, if you just read the page tables themselves). And having a bitmap to keep track of allocated pages is a very common way of doing it, so I wouldn't worry about the performance of that - you normally use one bit in the bitmap to correspond to each 4k page.

Do you mean my void* allocatePage() and deallocPage functions? (I haven't done deallocPage yet, just clear bitmap[table][page])

[Awe2K]

Also, which steps should I perform to execute binary?

As I know, such as these:

1. Load it into memory (address must be page aligned).
2. Load page directory where virtual address 0x0 points to phys. address where it is loaded.
3. void(*program_entry)(void) = *pointer to entry* (maybe 0)
4. program_entry();
5. Load kernel page dir again. (All memory is identity mapped).

My plan fails on step 4, as I get lots of GPF messages (sent by handler) as a result.

[Octocontrabass]

1. Load it into memory (address must be page aligned).

Load it into memory, correcting alignment to match what the executable header says will be required. Executables may not be aligned to your page size, especially if you're using pages larger than 4kB.

2. Load page directory where virtual address 0x0 points to phys. address where it is loaded.

Load page directory where virtual address specified in the executable header points to physical address where it is loaded. (I'm assuming you aren't using position-independent code yet.) Usually you don't want anything mapped at virtual address 0x0, so that null pointer references are more likely to cause page faults instead of working accidentally.

3. void(*program_entry)(void) = *pointer to entry* (maybe 0)
4. program_entry();

This is the part where you usually want to do a task switch into a lower privilege level, so the program is free to crash without taking your entire OS down with it. I'll admit I'm not too clear on the specifics since I haven't done any work related to tasks/processes/threads yet.

5. Load kernel page dir again. (All memory is identity mapped).

I'm not sure if this is on your roadmap already, but you should consider different memory models for your kernel. Identity mapping everything means you'll have to reload the page directory every time the kernel needs to interact with userspace.

[Awe2K]

1. Load it into memory (address must be page aligned).

Load it into memory, correcting alignment to match what the executable header says will be required. Executables may not be aligned to your page size, especially if you're using pages larger than 4kB.

My page size is equal to 4K, no more, no less. I think page-aligning must be applied to easy map pages where program is.

2. Load page directory where virtual address 0x0 points to phys. address where it is loaded.

Load page directory where virtual address specified in the executable header points to physical address where it is loaded. (I'm assuming you aren't using position-independent code yet.) Usually you don't want anything mapped at virtual address 0x0, so that null pointer references are more likely to cause page faults instead of working accidentally.

But if my program references some memory addresses (for example, compiled program uses memory addr 0x12345 to store some variable), then these "links" may become broken, for example: I load that program at 0x100000 (or other location), but it's code still references 0x12345, but not 0x1012345 as it should go normally.

3. void(*program_entry)(void) = *pointer to entry* (maybe 0)
4. program_entry();

This is the part where you usually want to do a task switch into a lower privilege level, so the program is free to crash without taking your entire OS down with it. I'll admit I'm not too clear on the specifics since I haven't done any work related to tasks/processes/threads yet.

I don't want any kinds of protection in my kernel, because all code is ran in kernel privilege level. I don't care if it could crash kernel. Also if I do implement some user-mode, I have to worry about lots of things such as syscall or something like that.

5. Load kernel page dir again. (All memory is identity mapped).

I'm not sure if this is on your roadmap already, but you should consider different memory models for your kernel. Identity mapping everything means you'll have to reload the page directory every time the kernel needs to interact with userspace.

I've just been thinking my map looks like this:

1. 0x100000 - my kernel
2. 0xC00000 - my program space (no multitasking or other, so just using fixed address)

And when I load my program, 0xC00000 is wanted to become 0x0, so that way my program would reference the RAM properly.
And when I'm returning from program back to kernel, just load kernel directory again, so that kernel code that is at, for example, 0x100123, continues running as before.

[BASICFreak]

But if my program references some memory addresses (for example, compiled program uses memory addr 0x12345 to store some variable), then these "links" may become broken, for example: I load that program at 0x100000 (or other location), but it's code still references 0x12345, but not 0x1012345 as it should go normally.

Well, if the code still references something out of its range, you did not link the executable to the right address. But the invalid reference should cause a #PF, then you will have the choice to fix the problem (if possible) or kill the task (more likely in this situation)

1. 0x100000 - my kernel
2. 0xC00000 - my program space (no multitasking or other, so just using fixed address)

And when I load my program, 0xC00000 is wanted to become 0x0, so that way my program would reference the RAM properly.
And when I'm returning from program back to kernel, just load kernel directory again, so that kernel code that is at, for example, 0x100123, continues running as before.

I would highly recommend a "higher half" kernel layout (e.g. my kernel sits at 0xFF100000 [physically 0x00100000])


I skimmed your code sections and (I may have missed it) I do not see any #PF handler
AND NEVER run code from 0x0000 - Null pointer hell. (if you want something at 0 it should be an error handler for null pointers.)

Now, even though you say you don't want protection or userland (yet) - Your kernel should be mapped in every page directory (especially the IDT and its code)
E.G. Take my mem layout:

Code: Select all

0x00000000 - 0xD0000000 (Free for userland)
0xD0000000 - 0xE0000000 (IPC Message Space)
0xE0000000 - 0xFF000000 (API Functions)
0xFF000000 - 0xFF100000 (BIOS and Bootloader)
0xFF100000 - 0xFFBFF000 (Kernel Space)
0xFFBFF000 - 0xFFFFFFFF (TLB)

All space >= 0xE0000000 are global pages, they are present in every page directory on the system.

Now if you want my opinion here are the steps I took in the kernel:

Code: Select all

Kernel TBL (in start strap)
Phys Mem Man
Virt Mem Man
GDT
IDT
TSS
Task Manager
IPC, API, and Userland comes next

NOTE: All my examples are from my Kernel (which is a micro-kernel like design) - and I may have missed a step or two.

Once you have paging down, it is extremely simple to get away from identity mapping.

[Awe2K]

But if my program references some memory addresses (for example, compiled program uses memory addr 0x12345 to store some variable), then these "links" may become broken, for example: I load that program at 0x100000 (or other location), but it's code still references 0x12345, but not 0x1012345 as it should go normally.

Well, if the code still references something out of its range, you did not link the executable to the right address. But the invalid reference should cause a #PF, then you will have the choice to fix the problem (if possible) or kill the task (more likely in this situation)

1. 0x100000 - my kernel
2. 0xC00000 - my program space (no multitasking or other, so just using fixed address)

And when I load my program, 0xC00000 is wanted to become 0x0, so that way my program would reference the RAM properly.
And when I'm returning from program back to kernel, just load kernel directory again, so that kernel code that is at, for example, 0x100123, continues running as before.

I would highly recommend a "higher half" kernel layout (e.g. my kernel sits at 0xFF100000 [physically 0x00100000])


I skimmed your code sections and (I may have missed it) I do not see any #PF handler
AND NEVER run code from 0x0000 - Null pointer hell. (if you want something at 0 it should be an error handler for null pointers.)

Now, even though you say you don't want protection or userland (yet) - Your kernel should be mapped in every page directory (especially the IDT and its code)
E.G. Take my mem layout:

Code: Select all

0x00000000 - 0xD0000000 (Free for userland)
0xD0000000 - 0xE0000000 (IPC Message Space)
0xE0000000 - 0xFF000000 (API Functions)
0xFF000000 - 0xFF100000 (BIOS and Bootloader)
0xFF100000 - 0xFFBFF000 (Kernel Space)
0xFFBFF000 - 0xFFFFFFFF (TLB)

All space >= 0xE0000000 are global pages, they are present in every page directory on the system.

Now if you want my opinion here are the steps I took in the kernel:

Code: Select all

Kernel TBL (in start strap)
Phys Mem Man
Virt Mem Man
GDT
IDT
TSS
Task Manager
IPC, API, and Userland comes next

NOTE: All my examples are from my Kernel (which is a micro-kernel like design) - and I may have missed a step or two.

Once you have paging down, it is extremely simple to get away from identity mapping.

Actually, I have #PF handling code, it's in kernel.c.
Could you give links or some examples on how to implement mapping you mentioned?
"Higher half" means it's, for example, at 0x100000, but it's virtually at 0xF100000, as in your example?
Also, I would be very glad if you or someone else gave me working example or tutorial on cloning directories (my code works bad), and how to map cloned directories?

[BASICFreak]

Actually, I have #PF handling code, it's in kernel.c.
Could you give links or some examples on how to implement mapping you mentioned?
"Higher half" means it's, for example, at 0x100000, but it's virtually at 0xF100000, as in your example?
Also, I would be very glad if you or someone else gave me working example or tutorial on cloning directories (my code works bad), and how to map cloned directories?

http://wiki.osdev.org/Higher_Half_bare_bones
http://wiki.osdev.org/Higher_Half_Kernel

Here is how I currently clone a dir:

Code: Select all

void *_VMM_copyPDir()
{
#ifdef DEBUG_FULL
	DEBUG_printf("BOS v. 0.0.4\t%s\tCompiled at %s on %s Line %i\tFunction \"%s\"\n", __FILE__, __TIME__, __DATE__, (__LINE__ - 3), __func__);
#endif
	void* PDirLoc = _VMM_newPDir(); // Make A Blank Page Directory (With Kernel Mapped)
	_VMM_map((void*)0, PDirLoc, FALSE, TRUE);

	for(uint32_t x = 0; x < 0x380; x++) {
		//Copy User Tables...
		if((VMM[0].Entry[x] & 0x01)) {
			void* NewTable = _PMM_alloc(PAGESIZE);
			_VMM_map((void*)0x1000, NewTable, FALSE, TRUE);
			memcpy((void*)0x1000, (void*)((x * PAGESIZE) + 0xFFC00000), PAGESIZE);
			((uint32_t*)0)[x] = (((uint32_t)NewTable) | (I86_USER | I86_PRESENT));
			for(int y = 0; y < 1024; y++) {
				((uint32_t*)0x1000)[y] &= 0xFFFFF000;
				((uint32_t*)0x1000)[y] |= (I86_USER | I86_PRESENT);
			}
		}
	}
	_VMM_umap((void*)0x1000);

	_VMM_umap((void*)0);
	return PDirLoc;
}

Note all user pages as set as COW, and the #PF handler actually handles copying. The only new pages created are the page directory and any page tables falling below 0xD0000000.

But my use of conversion and static variables is ugly and being replaced, but it works (in my design).

[Awe2K]

What does umap function mean?

I've already started rewriting my kernel as higher half from a total zero.
I will follow the steps you mentioned. Also, does higher half kernel mean paging is enabled by default?

Edit: if it is, how do I edit page entries in my kernel, after boot.s?

[Awe2K]

Also, how do 4MB pages differ from 4KB in tables? How many entries are in directory and table?