Memory Management Overview

[JoshuaP]

Sorry to post yet another memory related thread, but I didn't want to hijack anyone else's thread.

I've been trying to figure out how to add memory management to my kernel for the past week. I've read the FAQ and numerous threads here on the forum, but I'm still not sure about the whole process. I've read a lot about paging, physical & virtual memory management, but I don't know how to fit them all together to produce a working model.

Unfortunately my kernel code is on another computer with only a floppy drive, and no CD burner. My internet machine doesn't have a floppy drive so I don't have a way to transfer files from my development machine.

Here's what I've found so far about memory management, but it isn't enough to write a functional manager:

- The physical memory manager keeps track of free areas of the actual RAM.
- The virtual memory manager uses paging to map virtual addresses to physical ones, among other things.

The problem is getting it all to fit together. If anyone has more details about the overall process, I would *highly* appreciate it.

Thanks,
Josh

[Crazed123]

Well... To start, write a physical memory manager. This should keep track of the status of each page frame of memory usable by the operating system. Which page frames are usable can be found in a GRUB or BIOS memory map. There are several different types of algorithms used, most of them involving a bitmap that holds the status of each page, a stack of page numbers that holds the number of each free page, or some combination thereof. I know it sounds boring, but you can still be creative with it.

Paging is a funny little topic that should be handled seperately from your physical memory manager. It maps 4096-byte chunks of memory to wherever in a virtual (not necessarily real/physical) address space you want them to go, and is incredibly useful! Usually, you'll want your kernel linked to some high address so normal programs can be at the low addresses (or vice versa), and so you'll want to enable paging relatively early in the kernel. Some people do it in their assembler stub before the high-level language kernel is even called, while others use something called Tim's Segmentation Trick to make addresses valid temporarily before paging is enabled. Paging is done with page tables that hold the physical addresses of the physical page frames. On the x86 there is also a page directory that saves space by holding pointers to page tables rather than page frames.

Virtual memory handling is what ties the previous two together. It's the responsibility of the virtual memory handler to keep data on every page in virtual address space that should be accessible to the current task (process, kernel-space, whatever...), where that page is in physical memory, how its page table entry is, and information related to swapping pages out to disk. I can't really tell you much about algorithms to use here, except that Linux apparently uses a binary search tree for its VMM, and people say that's the fastest and best. I'm still making my own inquiries into the subject.

I hope this whole shpeil helped!

[JoshuaP]

Thanks, it definitely helped clear things up some. Of course, the details are still missing, but I'll take all I can get. ;D

I've determined how much RAM the machine has via multiboot & GRUB, but I've encountered some troubles initializing paging. The following (in my kernel that was working beforehand) makes the machine reboot. The faulty line in the write_cr0 one. Here's my code, from the paging tutorial on OsDever.net (link):

Code: Select all

/* vmm.c */

#include <kernel/vmm.h> /* nothing in it but the defs for the functions. */

unsigned long *page_directory = (unsigned long*)0x9C000;

int InitPaging() {
   int i;

   for (i=0; i < 1024; i ++) {
      page_directory[i] = 0;
   }
   
   /* write_cr3, write_cr0, & read_cr0 are in kstart.asm */
   write_cr3(page_directory);

   /* this is the call that resets the machine */
   write_cr0(read_cr0() | 0x80000000);

   return 1;
}

Now there are two things I think this could be:

1. Since page_directory is empty, writing it to cr3 could be bad.
2. There is some problem calling write_cr0.

Any ideas?

EDIT: It doesn't make the machine reboot, because I've only tested it in BOCHS, however it makes BOCHS do a virtual restart.

[Crazed123]

Your first problem is #1. The page directory ABSOLUTELY MUST have page tables set in the proper places so that once paging is on code and data references to unaltered addresses will still be valid. Usually, this is called Identity Paging. You use it first, change all the pointers so that they point to the new addresses, and turn it off.

Glad I could be of service, though if I wanted to give you all the little details the best thing to do would be hand over my source code or rewrite some research paper on paging from the 1970s .

[Pype.Clicker]

Unfortunately my kernel code is on another computer with only a floppy drive, and no CD burner. My internet machine doesn't have a floppy drive so I don't have a way to transfer files from my development machine.

You might like to get a null modem cable, or a parrallel PC-to-PC cable, or just a couple of network card and some feet of ethernet wire...

[JoshuaP]

Your first problem is #1. The page directory ABSOLUTELY MUST have page tables set in the proper places so that once paging is on code and data references to unaltered addresses will still be valid. Usually, this is called Identity Paging. You use it first, change all the pointers so that they point to the new addresses, and turn it off.

Yes, I discovered that last night. I finally got paging working. However, I have a new problem. I cannot seem to find a way to track the free memory without using a structure such as a linked list, which requires a way to allocate new memory.

I made a few attempts at using a linked list and kind of "jumpstarting" it using a stack memory as the head, but it resulted in a recursive infinite loop.

You might like to get a null modem cable, or a parrallel PC-to-PC cable, or just a couple of network card and some feet of ethernet wire...

I'll look into that. Thanks!

Hopefully I'll be able to get a better development machine, since anything will be better than a 266 MHz laptop...

[Brendan]

Hi,

I finally got paging working. However, I have a new problem. I cannot seem to find a way to track the free memory without using a structure such as a linked list, which requires a way to allocate new memory.

There are 2 common methods of keeping track of free physical memory - a bitmap/array or a free page stack.

For the bitmap/array method, either one bit or one array element (e.g. a byte) represents the state of each physical page. In this case it's easiest to pre-allocate all space needed for the bitmap or array. At one bit per physical page, the bitmap consumes 128 KB for 4 GB of RAM. At 1 byte per physical page you'd be using 1 MB for 4 GB of RAM. For performance this method can be good if it's done right, but searching through the bitmap/array for a free page is unavoidable.

For the free page stack method, the first dword of each free page contains the physical address of the next free page. Because everything is stored in free pages this actually doesn't consume any memory (except for the physical address of the page on the top of the stack - 4 bytes). As there isn't any need to search for a free page this method is faster than the bitmap/array method. The problem is that if you need N contiguous pages (e.g. for a DMA buffer) it won't work.

IMHO it's not a bad idea to use both methods. For example, use the bitmap/array approach for memory below 16 MB and free page stacks for anything above 16 MB. That way you get the best features of both.

I should mention that free page stacks can be a little tricky. To do it right it needs some interaction with the linear memory manager (which IMHO should be seperate, but life's like that). For example:

Code: Select all

void *address_of_next_free_page;

allocatePage {
   if(no_free_pages_left) implement_swap_space_one_day();
   else {
      page_table_entry = address_of_next_free_page | flags;
      invalidate_the_TLB_for_the_allocated_page();
      address_of_next_free_page = value_at_start_of_page_in_linear_memory;
   }
}

freePage {
   value_at_start_of_page_in_linear_memory = address_of_next_free_page;
   address_of_next_free_page = page_table_entry & 0xFFFFF000;
   page_table_entry = 0;
   invalidate_the_TLB_for_the_freed_page();
}

Hopefully this makes sense!


Cheers,

Brendan

[JoeKayzA]

Yes, I discovered that last night. I finally got paging working. However, I have a new problem. I cannot seem to find a way to track the free memory without using a structure such as a linked list, which requires a way to allocate new memory.

A linked list probably consists of node-structures, that all have the same size. So you could perfectly implement a linked list without a dynamic 'malloc'-like mechanism like this:

You have an area of pre-allocated memory, or you allocate memory in large chunks (like page-sized chunks). Then you divide it into chunks of node-size, that is your node-pool. Every node should have a flag that indicates whether it is used or not. When you need a node-structure then, instead of using malloc, you pick it out of this pool, and then set its used-bit. This is the way my virtual-memory-allocator works.

cheers Joe

[JoshuaP]

@Brendan: I really like the stack approach, but like you said the bitmap & stack combonation would be best. I think I will setup the bitmap one for the first 16MB to make sure everything is working then move on to the stack.

@JoeKayzA: Thank you for your tips. They will definitely come in handy when I try to implement that in my VMM.

Thanks for the help guys. Tonight I will try these ideas and we'll see from there.

[Crazed123]

You can also write a kernel heap and malloc, then implement linked lists and things on top of that.

[JoshuaP]

@Crazed123: When I tried implementing my linked-list system it was to run the kernel malloc system, which of course resulted in the infinite recursive loop (called malloc, which split a "free" node, which caused another call to malloc, which then called... and so on) I'm going to try and figure out how to do it without that problem, but I've been working all day and I haven't had a chance to program.

[Colonel Kernel]

I should mention that free page stacks can be a little tricky. To do it right it needs some interaction with the linear memory manager (which IMHO should be seperate, but life's like that).

I don't understand why you need to mess with page tables in your example... Why not keep all of physical memory mapped somewhere in kernel space and just follow the pointers...?

Also, when allocating many pages, wouldn't that scheme potentially thrash the cache by reading memory from all over the place (i.e. -- it exhibits poor locality of reference)?

[Brendan]

Hi,

I should mention that free page stacks can be a little tricky. To do it right it needs some interaction with the linear memory manager (which IMHO should be seperate, but life's like that).

I don't understand why you need to mess with page tables in your example... Why not keep all of physical memory mapped somewhere in kernel space and just follow the pointers...?

The problem with mapping all of physical memory into kernel space is that kernel space is simply not big enough. An easy example would be a computer with 3584 MB of RAM. A more complex example would be an OS the uses PAE (up to 64 GB of RAM while the virtual address space is still only 4 GB). You can add memory mapped devices to this too - a pair of 256 MB video cards wouldn't help.

This makes it a problem for servers already. If you've seen Microsoft's requirements for "LongHornyVista" you'd realise that normal desktop computers with 2 GB of RAM (or more) will be common relatively soon. I'm thinking they've replaced 2D animated icons with miniature 3D worlds being rendered in real-time, but I might be wrong (perhaps they've found a way to use the current user's DNA as an encryption key) .

Also, when allocating many pages, wouldn't that scheme potentially thrash the cache by reading memory from all over the place (i.e. -- it exhibits poor locality of reference)?

Worst case would be a TLB invalidation (required in any case) and a cache miss. Because the first thing that normally happens after a page is allocated is that software stores some data in it, the cache miss will happen eventually anyway, and it won't matter much if it's during the memory allocation or just after the memory allocation. At least this is the case for memory mapped files, swap space management, small explicit allocations and allocation on demand.

For software that allocates a large (> 4 KB) amount of memory that does not access all allocated pages soon after, you have a valid point (but in this case I'd accuse the software of wasting RAM before worrying about cache misses, and suggest they use allocation on demand instead).

[EDIT]
Doh - you'd have the same cache miss for free page stack/s even when the physical memory is mapped into kernel space! The only way it could be avoided is to use a different method (e.g. bitmap/array) or to modify the free page stack's implementation to use an index page (where one free page contains the address of up to 1023 more free pages, which would/could reduce any extra cache misses).
[/EDIT]


Cheers,

Brendan

[Colonel Kernel]

The problem with mapping all of physical memory into kernel space is that kernel space is simply not big enough.

<smacks_forehead/>

Please excuse me... my mental gear slipped to 64-bit address spaces. Sometimes it really doesn't pay to be forward-looking when you're trying to accomplish something in the here and now.

If you've seen Microsoft's requirements for "LongHornyVista"

ROFL! ;D

[EDIT]Doh - you'd have the same cache miss for free page stack/s even when the physical memory is mapped into kernel space![/EDIT]

Yeah, I know. My two questions weren't related. I guess the disadvantage to storing the linked list in a separate structure is the potential space overhead (e.g. -- up to 8MB for an array of <frame address/next array index> pairs).

[Crazed123]

@Crazed123: When I tried implementing my linked-list system it was to run the kernel malloc system, which of course resulted in the infinite recursive loop (called malloc, which split a "free" node, which caused another call to malloc, which then called... and so on) I'm going to try and figure out how to do it without that problem, but I've been working all day and I haven't had a chance to program.

When actually implementing malloc you avoid making calls to malloc by storing internal variables containing the linked lists that span the heap. The key is to start out with a fixed-length heap so that one free node (or several smaller ones more likely to fit a request, depending on your algorithm) completely contain it, and then whenever any of those are split or coalesced they stay within those exact boundaries, thus not requiring a call to malloc for more memory.

An example. If I have a completely free page of memory set up to use malloc under my algorithm it would look like this:

Code: Select all

LLLLAPLFBPNFB...............LLLL

Each of those letters is a single byte, and the ....s are the rest of the page. LLLL is the length of the block, not counting allocation overhead that's used when the page is allocated, A is a Boolean stating whether the page is allocated or not, PLFB is a pointer to the last free block, PNFB is a pointer to the next free block, and the final LLLL is another length (designed to have the same value as the first) that is used to check for block validity. The two pointers to free blocks are NULL, A is false (free block), and the lengths are the appropriate numbers. Now, if I allocate a block out of that I get:

Code: Select all

LLLLA..............LLLLllllaplfbpnfb.........llll

Where the capital letter block is allocated now (A=true), and the two pointers have disappeared into the allocated space. The lowercase l's contain the length of the new free block split off from the old one, and the other fields are alike too, but lowercase. Now let's say I free the first block, but there's no coalescence of free blocks quite yet:

Code: Select all

LLLLAPLFBPNFB...............LLLLllllaplfbpnfb.......llll

Where the capital PNFB now points to the first lowercase l, the lowercase plfb points to the first capital L in memory (before A), and the a's and lengths are set appropriately.

Now coalescence just liquifies the second set of capital L's (the barrier tags), the lowercase allocation data, calls them part of its data, thereby adding their lengths and the length stored in the lowercase l's to the length in the first LLLL, and changes the final llll to an LLLL barrier tag.

That was a hopefully understandable rundown of a fairly simple malloc. There are probably better, faster, smaller-overhead algorithms out there to use, and I encourage you to find them. Just get a solid understanding that malloc is based around WHAT you put in a FIXED length of data, thereby creating allocation data and a heap where before only existed a few empty pages.