Physical Memory Manager

[Candamir]

Ok, as the thread from Nuno Silva has now moved off-topic, I decided to create this new one, also in order to increase readability (forgive my arrogance).

I have now meditated about the pmm and, using great part of the Bona Fide tutorial 'Implementing Basic Paging', I expanded it to what I think could be a first attempt of a physical memory manager. Please have a look at my code:

This is file paging.c

Code: Select all

#include "system.h"

unsigned long *page_directory;

// CR access functions, doc found in cr_access.asm

extern unsigned long read_cr0(void);
extern void write_cr0(unsigned long cr0);
extern unsigned long read_cr3(void);
extern void write_cr3(unsigned long *cr3);

/** Enables paging.
 * Maps only 4MB of memory.
 */

void enable_paging()
{
   page_directory = (unsigned long *)0x9C000; // TODO: Find out where kernel ends
   unsigned long *page_table     = (unsigned long *)0x9D000;
   unsigned long address         = 0;
   unsigned int  i;
   
   //Map first 4MB of memory
   for (i = 0; i < 1024; i++)
   {
      page_table[i] = address | 3;
      address = address + 4096;
   };
   
   // fill the first entry of the page directory (the only one we actually set up)
   page_directory[0] = (unsigned long)page_table;
   page_directory[0] = page_directory[0] | 3; // supervisor level, read/write, present
   
   // Fill in the other 1023 entries (the ones we haven't done yet)
   for (i = 1; i < 1024; i++)
   {
      page_directory[i] = 0 | 2; // supervisor level, read/write, not present
   };
   
   write_cr3(page_directory); // page directory address into CR3
   write_cr0(read_cr0() | 0x80000000); // set paging bit in CRO to 1
}

/** Enables paging.
 * The bitmap is automatic, as this first version will use the avail bytes of the page table entries.
 * Must be called first thing.
 */

void paging_init()
{
   enable_paging();
}

/** Allocates the first single page found.
 * In order to achieve this, it sets all avail bits.
 * Returns 0 if it doesn't find any page available.
 */

void *page_alloc()
{
   unsigned long pde;
   
   // Loop variables
   unsigned int i;
   unsigned int j;
   for (i = 0; i < 1024; i++)
   {
      pde = page_directory[i]; // TODO: Better read cr3 in order to be more efficient
      if ((pde & 1) == 1) // Check bit 0 (present)
      {
         unsigned long *pt = (unsigned long *)(pde >> 12); // Is this correct?
         unsigned long pe;
         for (j = 0; j < 1024; j++)
         {
            pe = pt[i];
            if ((pe & 0xE01) == 1) // check present & 3 avail bits (avail bits MUST NOT be set)
            {
               pe = pe | 0xE00; // Set bits 11,10 and 9 (made available by Intel, I think)
               return (void *)(pe >> 12);
            }
         }
      }
   }
   return 0;
}

/** Frees a given page.
 * Unmarks bytes 11,10 and 9
 */

void page_free(void *ptr)
{
   // TODO
}

And the cr functions come here, in file cr_access.asm

Code: Select all

; In CR0, we must set bit 31 to 1 to tell the processor that paging is enabled.
; But first, we must put the address of our page directory into CR3.
; Other bits?

[global _read_cr0]
_read_cr0:
   mov eax, cr0
   retn

[global _write_cr0]
_write_cr0:
   push ebp
   mov ebp, esp
   mov eax, [ebp+8]
   mov cr0,  eax
   pop ebp
   retn

; In CR3, we store the pointer to our page directory.
; Aftwerwards, we set bit 31 of CR0 to 1 in order to enable paging.

[global _read_cr3]
_read_cr3:
   mov eax, cr3
   retn

[global _write_cr3]
_write_cr3:
   push ebp
   mov ebp, esp
   mov eax, [ebp+8]
   mov cr3, eax
   pop ebp
   retn

It compiles even with -Wall -Werror and also links. Could you guys just have a look at it and tell me what's it like? I know I'll have to implement a better bitmap/stack later, but it's just the beginning...

Thanks

Candamir

[Candamir]

Or can't I use paging at this step? One thing I still haven't understood is that once I have paging enabled, how can I get the virtual address of a page frame knowing its physical address...

[Warrior]

I was always under the impression a physical memory manager didnt involve paging at all.

For example it could be designed into different layers.

Physical memory manager has a heap which is used to allocate things like page tables and is served up in 4KB peices.

The page layer then used this and held functions to map memory regions and the like.

Then ontop of this was the "Final" manager which deals with virtual addressing and uses a virtual heap which can be anywhere.

Libraries would be wrapped around this "final" manager such as malloc()/free() and the others.

Of course the physical heap for the pmm would be mapped to the same virtual place as well (I'd guess)

Does this all seem right?

[Candamir]

Ok, now I still don't understand how to implement paging, but give me a few hours to implement a basic physical memory manager. I think I managed to understand those concepts by now, and then I'll move on to tackle the next problem...

[Solar]

Does this all seem right?

Pages and virtual addressing are the same thing. You could of course identity-map all pages, but the moment you activate the MMU (protected mode), you're using virtual-to-physical mapping. At least on the x86.

[Candamir]

First of all, I'm sorry 1) of asking so much and 2) of posting such a piece of crap as a pmm. But now, this second allocator I've written should work:

File pmm.c

Code: Select all

/** The stack pointer.
 */

unsigned long *stack_start;

/** The top element of the stack.
 */

unsigned int stack_top;

/** Starts our stack of free pages.
 * The free pages begin just after the stack
 */

void stack_setup()
{
   stack_start = (unsigned long *)0x9C000; // TODO: Map just after the kernel
   // For the beginning, I will only map 1024 pages, each 4kb in size
   // Later on, I shall map all RAM into the stack
   unsigned int stack_num = 1024;
   unsigned int page_size = 4096;
   unsigned long heap_start = (unsigned long)stack_start 
                      + stack_num * sizeof(unsigned long);
   unsigned int i; // Loop variable
   unsigned long address = heap_start;
   for (i = 0; i < stack_num; i++)
   {
      stack_start[i] = address;
      address = address + page_size;
   }
   stack_top = stack_num - 1;
}

/** Starts the physical memory manager.
 */

void pmm_init()
{
   stack_setup();
}

/** Allocates a page, 4kb
 * Returns null if there aren't any free pages left.
 */

void *pmm_alloc()
{
   if (stack_top == -1)
   {
      return 0;
   }
   else
   {
      unsigned long *ret = (unsigned long *)stack_start[stack_top];
      stack_start[stack_top] = -1;
      stack_top = stack_top - 1;
      return (void *)ret;
   }
}

/** Frees a given page.
 */

void pmm_free(void *ptr)
{
   stack_top = stack_top + 1;
   stack_start[stack_top] = (unsigned long)ptr;
}

If this isn't a physical memory manager (although a very basic one), but as far as I understood the code I wrote , this one shouldn't use any outside resources such as paging...

If just someone could spare 5 min of his time and read the code and say if it's ok, it would be great!

The limitations of this code are the following (I'll be modest ):

- The stack should start immediately after the kernel and not just "somewhere out there", but at least, the address is 4k-aligned
- The stack should map all memory, but I didn't want get things complicated at first.

Thank you all for your comments,

Candamir

PS: I have decided to not post as much questions as I have done recently, but rather search old posts of the forum (I bet this very topic has been discussed over and over a thousand times) and only post when I have some code that I know will at least do a reasonable attempt to do its work... (But I'll be nevertheless happy if you check the code, only to tell me if I'm on my way or completely lost...)

[Warrior]

Does this all seem right?

Pages and virtual addressing are the same thing. You could of course identity-map all pages, but the moment you activate the MMU (protected mode), you're using virtual-to-physical mapping. At least on the x86.

Well I was thinking of setting the specified entries in the PTs to effectively map a physical one to a virtual one.

[Solar]

I'm in a hurry so I only browsed through the code swiftly. Three things:

Code: Select all

   unsigned long heap_start = (unsigned long)stack_start 
                      + stack_num * sizeof(unsigned long);

Check your knowledge on pointer arithmetics. If you have a pointer to long (stack_start), and increment it by 1, you are pointing to the next long, not the next byte. (It's like the compiler is already doing the ... * sizeof() thing, and you are doing it again, so your heap_start is placed much too high in memory. There might be other bugs like this, but this was the most obvious.

And, your allocation function only ever passes out one page. Consider that there might be clients that require more than 4096 bytes en bloc.

Then there's the issue of the actually available memory. Let's say you have 256 MByte. Those might be divided into two or more chunks. You have to know where everything is, which parts are "special" (framebuffer), etc. - if I were you, I wouldn't worry that much about a memory manager before you have a pretty good map of where your memory is. (The FAQ can help you there. Or GRUB. )

[Candamir]

Well, I use gcc (djgpp) and I found that line you pointed out to be false to work perfectly: stack_start => 9C000, heap_start => 9D000 with stack_num to be 1024. I think that's because I convert stack_start into a long first and work with it as a long and not as a pointer.

In the following two lines, both have the same output:

Code: Select all

unsigned long heap_start = (unsigned long)stack_start + stack_num * sizeof(unsigned long);
unsigned long *heap_start_addr = stack_start + stack_num;

When I also multiplied stack_num in the second line with sizeof(long), it returned A0000. Then, I checked this:

(9D000 - 9C000) / (A0000 - 9C000) = 4 = sizeof(long)

Nevertheless, you are obviously more than right what concerns the other two points you mentioned.

Thank you,

Candamir

[Senaus]

I've been reading Windows Internals lately, and I find Windows' Physical Memory Manager particularly intriguing. According to this book, the mm keeps an array of structures, one element for each page on the system. I first thought that this method must use a massive amount of memory, as opposed to the stack and bitmap managers I was used to. 16MB for a 1GB system (assuming a 4096 byte page and a 64 byte structure) is a lot of memory.

But then I realised that a structure will need to be allocated when a page is committed to a process address space for stack/bitmap managers, so the overhead of the manager will increase as more pages are committed. When all physical memory is in use, the stack/bitmap method will probably use just as much, if not more memory than the Windows method.

So correct me if i'm wrong, but isn't the Windows method far superior to the stack and bitmap methods commonly used in the OSdev community? With a linked list of free pages built into the array, single page allocations are almost instantaneous. Contiguous page allocations are easy, as you simply traverse the array. Plus this system saves an allocation when the page is assigned to the process address space. It all seems too good to be true...

[Brendan]

Hi,

But then I realised that a structure will need to be allocated when a page is committed to a process address space for stack/bitmap managers, so the overhead of the manager will increase as more pages are committed. When all physical memory is in use, the stack/bitmap method will probably use just as much, if not more memory than the Windows method.

For the bitmap method, you'd always use a fixed size "bitmap" (either one byte per page or one bit per page). For 16 MB, this works out to 512 bytes (1 bit per page) or 4096 bytes (1 byte per page) regardless of how many free pages there are.

For the free page stack method, normally the stack itself is stored in the free pages and no space needs to be allocated to manage it, except for keeping track of the physical address of the first page on the stack and the number of free pages on the stack. When no RAM is free you'd end up using a total of between 8 and 16 bytes (depending if those 2 values are 32 bit or 64 bit). When lots of RAM is free you're still only using between 8 and 16 bytes (whatever you store in the free pages doesn't count).

The real question here (IMHO) is, why would you need to to allocate a structure when a page is committed to a process address space?

If you mean a page table entry or page directory entry, then this can't be easily avoided (but I'd call it "linear memory manager" overhead, which has nothing to do with physical memory management).

You could mean some sort of structure used by the swap space manager to work out how often a page was used (for determining the "best" page to send to swap), but there's other ways to do this (and I'd call it "virtual memory manager" overhead, which has nothing to do with physical memory management).

If you mean that the physical memory manager needs to know where an allocated page ended up so that it can "revoke" that page, then I'd need to ask why the physical memory manager would ever need to revoke a page...


Cheers,

Brendan

[Senaus]

The real question here (IMHO) is, why would you need to to allocate a structure when a page is committed to a process address space?

The main reason behind the structure is reference counting for COW and shared memory, plus a pointer/handle to the backing store associated with the page. Linux has [tt]struct page[/tt] and Windows has the PFN Database. I think the Windows method is better, and I can't see any other way of keeping a reference count without allocating a structure.

[Brendan]

Hi,

The main reason behind the structure is reference counting for COW and shared memory, plus a pointer/handle to the backing store associated with the page. Linux has [tt]struct page[/tt] and Windows has the PFN Database. I think the Windows method is better, and I can't see any other way of keeping a reference count without allocating a structure.

I'd call this "virtual memory manager overhead" (rather than "phyical memory manager overhead).

The number of structures needed could be reduced - you don't need one structure per allocated page. For example, you could use a flag in the page table entry to indicate if the page is shared or COW, and then only have a structure if this bit is set.

Alternatively, you could have a structure for each area. For e.g. for a shared memory area the structure could contain the starting linear address, the size of the area and the number of address spaces that are sharing it. Then each process would need a list of which "area structures" apply to it.

I haven't thought about shared memory or COW much though (I don't intend to support either of them).


Cheers,

Brendan

[Colonel Kernel]

I'd call this "virtual memory manager overhead" (rather than "phyical memory manager overhead).

When talking about a memory manager like NT's, this distinction is academic, since the same PF database serves both purposes. IIRC, Senaus' real question was about overall overhead of the entire memory manager, not just the physical memory manager.

I haven't thought about shared memory or COW much though (I don't intend to support either of them).

This is why you probably always find yourself asking why people are doing things the hard way. Remember that your OS architecture is rather "special" in many respects...

[Candy]

So correct me if i'm wrong, but isn't the Windows method far superior to the stack and bitmap methods commonly used in the OSdev community? With a linked list of free pages built into the array, single page allocations are almost instantaneous. Contiguous page allocations are easy, as you simply traverse the array. Plus this system saves an allocation when the page is assigned to the process address space. It all seems too good to be true...

I'm not going to comment on it, but my memory manager backing tables have been mostly based on the Windows design and not on stack/bitmap design. Note that it is equal to an expanded bitmap with both advantages in one.