Paging and Memory Managment

[teodori]

Hello, I wrote a bootloader and a simple kernel. Now I am stuck with the memory manager and paging. The CPU is in 64 bit mode, and paging maps the first MiB of memory (virtual = physical memory). I got a PML4 with 1 entry, a PDP with 1 entry, a PD with 1 entry and 256 out of 512 PT entries. What should I do, when I want to allocate memory to a pointer? Lets say I want a list of uint32_t with 80 entries, so I need 320 bytes. Allocating using one PT entry is an overkill, I don't need 4096 bytes, I need only 320 bytes. And to add a new page, I am forced to look inside all page levels and take the first unused one, then check which memory location is not mapped. To do this lots of memory access has to be done, isn't that slowing down the computer?

My problem is I don't get the principles of paging... Does anyone know where to find good examples or tutorials?

[linguofreak]

Hello, I wrote a bootloader and a simple kernel. Now I am stuck with the memory manager and paging. The CPU is in 64 bit mode, and paging maps the first MiB of memory (virtual = physical memory). I got a PML4 with 1 entry, a PDP with 1 entry, a PD with 1 entry and 256 out of 512 PT entries. What should I do, when I want to allocate memory to a pointer? Lets say I want a list of uint32_t with 80 entries, so I need 320 bytes. Allocating using one PT entry is an overkill, I don't need 4096 bytes, I need only 320 bytes.

You'll actually need three memory managers here:

1) Your physical memory manager. This is the one that decides which page frames from the computer's physical memory to allocate when more physical memory is needed.

2) Your virtual memory manager. When a process needs more virtual address space, this gets page frames from the physical memory manager and puts them in the appropriate spot in the process's virtual address space. Actually, it may not even ask the physical memory manager for a page frame when it receives a request for memory. It may just mark a page in the process's virtual address space as valid so that the process doesn't get killed when it tries to access that page, and then wait for the process to actually try to use the memory before it actually gets and assigns a physical page frame to that page.

The physical and virtual memory managers allocate memory in page-sized chunks.

3) Your heap manager. This takes the virtual address space it has been given by the virtual memory manager and doles it out in response to malloc() and free() calls. If it can fulfill an allocation request without getting more memory from the virtual memory manager, it will do so. So a 320 byte allocation might or might not allocate a page: If the heap manager has more than 320 bytes of space available and you malloc() 320 bytes, the heap manager will just hand you a pointer to the beginning of a 320 byte block. If it doesn't have 320 bytes available, it will ask the virtual memory manager for another page and use the new page to fulfill that allocation. Further allocations will then use the remaining space on the new page.

Your kernel will need a heap manager for its own use, but for user-space programs, the heap manager won't be part of the kernel: it will be part of the program or a library it is using (more likely the second than the first).

[teodori]

Ok for now I only need to allocate memory to kernel itself so that the kernel can do some work. So do I first need to find a free physical memory page, and how do I do that? Do I have to check for each physical page, if it's used in a page table. If yes, go over to the next physical page and check this one. If no, pass the physical page to the virtual memory manager.

Ok lets say 0x0 is the address of PML4 with only the first entry set, 0x1000 is the address of PDP with only the first entry set, 0x2000 is the address of PD with only the first entry set, and 0x3000 is the address of PT with 0x100 entries set. So I have now 1 MiB of virtual memory (0x100 * 0x1000 = 0x100000), and this virtual memory maps the first MiB of physical memory.

Now to find the next free physical page, I have to iterate until I use 0x100000 and see that it is'nt used in one page table.
The last physical page used is PML4[0].PDP[0].PD[0].PT[255] = 0x99000. So the next free physical page is 0x100000, and I put it in PML4[0].PDP[0].PD[0].PT[256]. Now I have 1 MiB and 1 KiB of memory. My kmalloc() can now return PML4[0].PDP[0].PD[0].PT[256].

This is good for 1 MiB of memory, but not if the next free physical page is at the 1 GiB mark. It's not very effectif to check each physical page until I fnd the first free one.

And what about the heap manager how do I implement it...

I am completely lost

[thepowersgang]

You're not quite thinking about it the right way. Why not just keep a stack of unused physical pages and pop one off when you need a new page? Or you could use a bitmap and search that (an O(1) search, but it's not too expensive to do)

As for heap allocators, look up dlmalloc (which iirc is just a simple linked list of used/avaliable blocks)

[teodori]

Ok thank you now I know what to search. I found tutorials.
http://osdev.berlios.de/memory1.html
http://osdev.berlios.de/memory2.html
http://www.brokenthorn.com/Resources/OSDev17.html
http://www.brokenthorn.com/Resources/OSDev18.html

[teodori]

I have a few other questions to ask now.

For the physical memory manager, I can't find examples for the stack based method. If I use the bit map based method and lets say I have 2 MiB (0x200000) of memory, I will need 512 bits to mark physical pages of 0x1000 bytes (0x200000/0x1000=0x200=512), which leads to 64 bytes I will need (512/8=64). Is that correct?

For the virtual memory manager, what does higher half kernel mean? I my example, I go from 32 bit protected mode without paging to 64 bit long mode with paging. Does this mean that virtual memory must map physical memory? If I don't do that a triple fault comes up.

Now the problem is where do I put the physical memory manager's data? At the 1MiB mark and make virtual = physical. How much size does it need if I have 8GB of RAM?

Here is the part of my source code where I jump to long mode:

Code: Select all

.section .text

.globl start

start:

	.code16

	# Read in Control Register 0
	# Enable Protected Mode (Bit 0)
	# Write to Control Register 0
	movl %cr0, %eax
	orl $(1<<0), %eax
	movl %eax, %cr0

	# Load Global Descriptor Table
	lgdt gdt32ptr

	# Setup all Segment Registers
	# and reload Code Segment, Instruction Pointer
	movw $0x0010, %ax
	movw %ax, %ds
	movw %ax, %es
	movw %ax, %fs
	movw %ax, %gs
	movw %ax, %ss
	ljmp $0x0008, $jump_to_pm
jump_to_pm:

	.code32

	# Set A Register to 0x0000
	# Set C Register to 0x1000
	# Set Destination Index to 0x0000
	# Store A Register times C Register
	clrl %eax
	movl $0x1000, %ecx
	clrl %edi
	rep stosl

	# Set Page Present (Bit 0)
	# Set Page Read & Write (Bit 1)
	# Enable Page-Level Writethrough (Bit 3)
	# Disable Page-Level Cache (Bit 4)	
	clrl %ebx
	orl $(1<<0), %ebx
	orl $(1<<1), %ebx
	orl $(1<<3), %ebx
	orl $(1<<4), %ebx

	movl $0x0003, %ecx
	movl $0x0000, %edi
create_pt_entry_0:
	movl %edi, %eax
	addl $0x1000, %eax
	orl %ebx, %eax
	movl %eax, (%edi)
	addl $0x1000, %edi
	loop create_pt_entry_0

	clrl %eax
	movl $0x0100, %ecx
create_pt_entry_1:
	orl %ebx, %eax
	movl %eax, (%edi)
	addl $0x1000, %eax
	addl $0x0008, %edi
	loop create_pt_entry_1

	# Use Model Specific Register 0xc0000080
	# Read in Model Specific Register
	# Enable System-Call Extension (Bit 0)
	# Enable Long Mode (Bit 8)
	# Enable No Execute (Bit 11)
	# Write to Model Specific Register
	movl $0xc0000080, %ecx
	rdmsr
	orl $(1<<0), %eax
	orl $(1<<8), %eax
	orl $(1<<11), %eax
	wrmsr

	# Read in Control Register 4
	# Enable Physical Address Extension (Bit 5)
	# Enable Page Global Enabled (Bit 7)
	# Write to Control Register 4
	movl %cr4, %eax
	orl $(1<<5), %eax
	orl $(1<<7), %eax
	movl %eax, %cr4

	# Set PML4 address
	# Enable Page-Level Writethrough (Bit 3)
	# Disable Page-Level Cache (Bit 4)
	# Store Control Register 3
	clrl %eax
	orl $(1<<3), %eax
	orl $(1<<4), %eax
	movl %eax, %cr3

	# Read in Control Register 0
	# Enable Paging (Bit 31)
	# Write to Control Register 0
	movl %cr0, %eax
	orl $(1<<31), %eax
	movl %eax, %cr0

	# Load Global Descriptor Table
	# Load Interrupt Descriptor Table
	lgdt gdt64ptr
	lidt idt64ptr

	# Setup all Segment Registers
	# and reload Code Segment, Instruction Pointer
	movw $0x0020, %ax
	movw %ax, %ds
	movw %ax, %es
	movw %ax, %fs
	movw %ax, %gs
	movw %ax, %ss
	ljmp $0x0008, $jump_to_lm
jump_to_lm:

	.code64

	# Setup the stack
	movq $0x7e00, %rbp
	movq %rbp, %rsp

	# Call Main Function
	call kmain

hang:
	# Halt the CPU
	# Infinit loop if Halt doesn't work
	hlt
	jmp hang

[Combuster]

For the virtual memory manager, what does higher half kernel mean?

Higher half means the kernel lives at the top end of virtual memory, and userspace at the lower end, with a hard cut in between (typically halfway for 64-bits and 3G/1G for 32 bits). Lower half means the opposite ordering, and is occasionally abused for cases with no hard separation. In practice, this means that higher half kernels can't have virtual=physical addressing and need paging, and for 64-bit you also get different memory models for kernel and userspace.

I my example, I go from 32 bit protected mode without paging to 64 bit long mode with paging. Does this mean that virtual memory must map physical memory? If I don't do that a triple fault comes up.

When paging, the code you're running to do it must be mapped virtual=physical. After that, any virtual address can be mapped to any physical address.

Now the problem is where do I put the physical memory manager's data? At the 1MiB mark and make virtual = physical. How much size does it need if I have 8GB of RAM?

You know the math to calculate the needed size. You don't need to do any allocations to find a space where you can put that data given a list of RAM segments and a list of regions that are still needed (kernel, multiboot structures). The physical memory manager is always designed to start up without needing itself.

Here is the part of my source code where I jump to long mode

And what relevancy does this have?