Creating Pages Beforehand

[Creature]

Because I experienced some problems with my previous approach of paging, I decided to do it another way this time. It does work, but I'm not sure if it's a correct approach. My idea was to, instead of creating pages in the page table whenever needed, create all the pages in the page-table before doing anything with paging at all. So what I'm talking about is something like this:

Code: Select all

	/* ... */

	/* Make a page directory. */
	KernelDir = (PageDirectory *) AllocAlign(sizeof(PageDirectory));
	memset(KernelDir, 0, sizeof(PageDirectory));
	KernelDir->Address = (unsigned) KernelDir->TablesPhys;

	/* Allocate 1024 page-tables for the page directory (do this now so the addresses can be identity mapped and frozen). */
	size_t PhysAddr;
	size_t i;

	for(i = 0; i < 1024; )
	{
		KernelDir->PageTables[i] = reinterpret_cast<PageTable *>(AllocAlignGetPhys(sizeof(PageTable), &PhysAddr));
		memset(KernelDir->PageTables[i], 0, sizeof(PageTable));

		KernelDir->TablesPhys[i++] = PhysAddr | 0x7; /* The physical address with the 'Present', 'Read-Write' and 'UserMode' set. */
	}

	i = 0;

	/* Identity map. */
	while(i < CurAddress + PAGE_SIZE)
	{
		AllocateFrame(PAGE_GET(i, KernelDir), false, false);
		i += PAGE_SIZE;
	}

	/* Allocate frames for the heap's pages (now that everything is identity mapped). */
	for(i = HEAP_START; i < HEAP_START + HEAP_START_SIZE; i += PAGE_SIZE)
		AllocateFrame(PAGE_GET(i, KernelDir), false, false);

	/* Switch page directories and enable paging. */
	SwitchPageDir(KernelDir);

As you can see, I do all the identity mapping and such as is required, but instead of creating pages whenever needed, I create the entire directory with its tables and everything before use. So my question was: is this a good/correct approach? Am I doing something seriously wrong here or can this have 'negative effects' on other code that makes use of paging?

The entire source file is located here.

Thanks for your help,
Creature

[kop99]

Creature, I think the linux kernel is doing similiar way.
Linux kernel use directly mapping first 896MB of Phys RAM to 3G~4G virtual address space.

[salil_bhagurkar]

http://forum.osdev.org/viewtopic.php?f=1&t=13009

[JamesM]

Creature, I think the linux kernel is doing similiar way.
Linux kernel use directly mapping first 896MB of Phys RAM to 3G~4G virtual address space.

What rubbish.

OP: You're wasting space. Each page table you allocate unnecessarily wastes an additional 4KB of space. Thats why the approach you take is not done generally.

[earlz]

Creature, I think the linux kernel is doing similiar way.
Linux kernel use directly mapping first 896MB of Phys RAM to 3G~4G virtual address space.

What rubbish.

OP: You're wasting space. Each page table you allocate unnecessarily wastes an additional 4KB of space. Thats why the approach you take is not done generally.

But you have to create a page table to use the memory your "wasting" Now, allocating the whole 4G ahead of time is a waste cause you might not need to(The only case where you do is when a big application uses a crap load of virtual memory or you have 4G of ram).

not done "generally"? Well, the linux kernel does it (according to that guy, I really don't know)

[Creature]

Creature, I think the linux kernel is doing similiar way.
Linux kernel use directly mapping first 896MB of Phys RAM to 3G~4G virtual address space.

What rubbish.

OP: You're wasting space. Each page table you allocate unnecessarily wastes an additional 4KB of space. Thats why the approach you take is not done generally.

I see, so a better approach would be to simply create the tables whenever they are actually being used (and they don't exist yet)? What if I would use a heap and paging algorithm similar to your tutorials, wouldn't it run into an infinite loop when expanding the heap? Since the expansion code allocates space for the new page tables, which then in turn needs to allocate memory, which brings it to the extended allocation function (it checks if the heap exists, and it does, so it goes straight back to the heap, which wants to expand again, ...). Or am I doing something terribly wrong there?

[JohnnyTheDon]

Creature, I think the linux kernel is doing similiar way.
Linux kernel use directly mapping first 896MB of Phys RAM to 3G~4G virtual address space.

What rubbish.

He is partially right. From the Linux Memory Management Wiki:

Memory above the physical address of 896MB are temporarily mapped into kernel virtual memory whenever the kernel needs to access that memory
Data which the kernel frequently needs to access is allocated in the lower 896MB of memory (ZONE_NORMAL) and can be immediately accessed by the kernel

[NickJohnson]

Creature, I think the linux kernel is doing similiar way.
Linux kernel use directly mapping first 896MB of Phys RAM to 3G~4G virtual address space.

What rubbish.

OP: You're wasting space. Each page table you allocate unnecessarily wastes an additional 4KB of space. Thats why the approach you take is not done generally.

I see, so a better approach would be to simply create the tables whenever they are actually being used (and they don't exist yet)? What if I would use a heap and paging algorithm similar to your tutorials, wouldn't it run into an infinite loop when expanding the heap? Since the expansion code allocates space for the new page tables, which then in turn needs to allocate memory, which brings it to the extended allocation function (it checks if the heap exists, and it does, so it goes straight back to the heap, which wants to expand again, ...). Or am I doing something terribly wrong there?

Pre-allocating the tables is what stops that infinite looping, but you don't have to pre-allocate *all* of the address space. Just do it for the kernel heap's address space, which should be much smaller than 4 GB, and will only be allocated once and linked in all address spaces. I do that, and it only takes up 128KB extra... not too bad.

[Creature]

Pre-allocating the tables is what stops that infinite looping, but you don't have to pre-allocate *all* of the address space. Just do it for the kernel heap's address space, which should be much smaller than 4 GB, and will only be allocated once and linked in all address spaces. I do that, and it only takes up 128KB extra... not too bad.

I think I understand what you mean, but I don't really have an idea about how to go about it. So what you're saying is, I should still create all the page tables like I'm doing right now, but only fewer of them. So suppose I do this:

Code: Select all

for(i = HEAP_START; i < HEAP_START + HEAP_START_SIZE; i += PAGE_SIZE)
		RetrievePage(i, KernelDir, true);

It would create all the pages needed by the heap when it starts (obviously). If I let the heap expand, it will need new pages, and will infinitely loop. But, if I would create the pages beforehand on my old way, the heap can just allocate frames whenever needed, but the actual page tables (with their pages) will no longer need to be created.

I'm a little confused, could you perhaps show me an example of what you mean (for some reason examples always make me understand things ).

Thanks for your feedback.

[NickJohnson]

Yeah, that's exactly what I mean. You can also increment i by one page table worth, not just one page, and save yourself a lot (1024 times too many) of redundant loops:

Code: Select all

for(i = HEAP_START; i < HEAP_START + HEAP_START_SIZE; i += PAGE_SIZE * 1024)
		RetrievePage(i, KernelDir, true);

The amount of memory this uses obviously depends on your heap size, but regardless it is only allocated once, so you "waste" at most 4 MB ever, although it's probably more like 1-2 MB.

Alternatively, you could reserve a 4 MB sized stack-based heap somewhere in kernelspace, and use it exclusively for heap page table allocations. You would have to make an exception in the heap resizing functions, but otherwise it would be pretty simple.

Because my heap is relatively small (< 1/32 of the address space), I can do the pre-allocation without worrying about memory usage, but it all depends on other factors. If I were you, I would just stick with your current method, for simplicity.

[Creature]

I think I know what you mean now; because the RetrievePage function creates an entire table when needed anyway, I should better increment the i with PAGE_SIZE * 1024 since otherwise the table would be created on the first new table and then it would loop about 1023 times trying to create the same table and seeing that it already exists.

Would making a stack of 4 MB have any specific advantages to just allocating everything beforehand (which is practically the same, except that the stack memory is only actually assigned when a table needs to be created)? I presume the result is that with the stack, booting the OS and initializing will be faster but the page tables will sometimes need to be created if the heap expands (and if it doesn't expand, they won't be created at all) and the pre-allocation method will make the booting slower, but will 'hog' the OS less when the heap needs to expand itself later on. The most negative point of the pre-allocation method would be that if the heap never expands, the page tables are still created for it but will never be used (and thus take up an extra amount of space).

The usual approach; not using a stack, not pre-allocating anything but just creating page-tables whenever they're needed will result in an infinite loop when the heap needs to expand (page-tables need space to be allocated, the allocation is directed to the heap and the heap wants to have more page-tables again), so it's not really an option.

[NickJohnson]

The only advantage to reserving a separate stack based allocator is memory usage; the amount of time it takes to allocate a kernel heap's worth of page tables is negligible even on the slowest system. Conversely, the only advantage of preallocating is less complexity; you don't have to worry about making exceptions in your page allocation functions to accommodate a special allocator. Unless 1-2 MB is a lot on the system you're going to be using (i.e. if you're planning to be running it on an actual 80386), I would just stick with what you have.

[kop99]

JamesM said.

What rubbish.

OP: You're wasting space. Each page table you allocate unnecessarily wastes an additional 4KB of space. Thats why the approach you take is not done generally.

But it only need 896k for entire kernel directly mapping, and it will speed up for memory management!

Instead of mapping all physical ram to virtual address space, only 0~896M of physical ram is mapped to kernel virtual address space(generally 0xC0000000~0xFFFFFFFF).
And rest of physical memory is managed by high memory.