Stack-based memory allocation

[AndreaOrru]

Hi all,
I am currently using a bitmap in order to keep track of the physical memory in use, but I'm planning to use the combination of a bitmap (which can easily allocate contiguous physical blocks) for the first MBs, and of a stack of free pages (which is faster for non-contiguous blocks) for the rest of the memory.

I just want to know if I have got it right: with 4GB of RAM, would the page stack permanently take up 8MB of memory? Or is there some tricks that I don't know?

[Brendan]

Hi,

I just want to know if I have got it right: with 4GB of RAM, would the page stack permanently take up 8MB of memory? Or is there some tricks that I don't know?

The minimum you need is 4 bytes.

Assume the free page stack is empty, and you've got a "physical address of the next free page on the stack" pointer which is NULL. When someone frees a page they tell you the current linear address of the page and the physical address of the page; and you store the current "physical address of the next free page on the stack" at this linear address, then set the new "physical address of the next free page on the stack" pointer to the physical address of the free page. Then the page is removed from the linear address space. Now you're using 4 bytes for the pointer, plus 4 bytes in the free page (which doesn't really matter because the page is free and wouldn't be used for anything else anyway). You can keep doing this and you still only end up needing 4 bytes (plus the first 4 bytes of each free page, which doesn't really matter).

When someone allocates a page you tell them the physical address of the first page on the stack, they map it into the address space and tell you where, then you get the physical address of the next page on the stack from this linear address.

The only real problem with this approach is that you end up with TLB misses.

There are variations on this that are intended to reduce the TLB misses. One idea is to have a stack of "index pages", where the top "index page" is mapped into the address space and contains the physical addresses of up to 512 or 1024 more free pages. In this case it costs you 4100 or 4104 bytes per free page stack (but in theory you get a lot less TLB misses).

I use the first method. Partly because it's very likely that a newly allocated page will be accessed soon, and the TLB miss will happen anyway, so there isn't too much point trying to avoid it; and there are other benefits...

For pages that are above 0x0000000100000000 you'd need to use 8 bytes (64-bit physical addresses). However, it's a good idea to use 2 free page stacks (one for pages below 0x0000000100000000 and one for pages above 0x0000000100000000), because sometimes you need to allocate a page that has a 32-bit physical address (e.g. for a "page directory pointer table" when you're using PAE, or for some 32-bit PCI devices, or for some 64-bit PCI devices that are behind a dodgy "32-bit only" PCI to PCI bridge).

However, why stop at just 2 free page stacks? For each free page stack you'll probably need a re-entrancy lock, and you don't want all the CPUs (potentially) fighting for the same lock at the same time. If you increase the number of free page stacks for no reason at all, then you'd have more locks and less lock contention, and because of that you'll get better performance on "many CPU" systems (with almost no extra overhead).

However, if you're going to have lots of free page stacks, why not use them for different things? It's easy to implement page colouring by having one free page stack per page/cache colour, and that will improve performance by improving cache efficiency. It's also possible to have a different group of free page stacks for each NUMA domain (to improve performance by minimizing "distant" RAM accesses), or have different groups of free page stacks for other purposes.

The previous version of my OS used 1024 free page stacks (but the new version will probably use many more). At 8 or 16 bytes per free page stack I could probably have millions of them without any problem; but at 4104 bytes per free page stack it starts to get expensive...


Cheers,

Brendan

[AndreaOrru]

Thank you very much for your explanation, Brandon.

The only thing I don't like is the need to merge physical and virtual memory management...

[Brendan]

Hi,

The only thing I don't like is the need to merge physical and virtual memory management...

I don't like that part of it so much either.

To keep the physical memory manager and the linear memory manager separated I use callbacks. For e.g. for allocating a page the physical memory manager acquires the re-entrancy lock for a free page stack, and returns the physical address of the next free page and the address of a function that needs to be called after the page is mapped into an address space. When this callback is called the physical memory manager updates the "next page" pointer and releases the re-entrancy lock. Freeing a page can be done in a single operation though.

I also use the "allocated page" callback for something else though - my physical memory manager may also test the page to see if it's become faulty, which means even when the bitmap is being used to allocate pages (and not the free page stack) there's still a callback (where the callback might return an error, indicating that the page wasn't usable and the linear memory manager needs to retry the allocation).

That's another reason for using more free page stacks - I have one set of free page stacks to keep track of "clean" pages and another set of free page stacks to keep track of "dirty" pages; where clean pages have already been filled with zeros and (optionally) tested, and dirty pages haven't been filled with zeros or (optionally) tested. Then I have idle threads that convert dirty pages into clean pages when the CPU/s have nothing else to do, so that this cleaning/testing doesn't happen when a page is allocated unless there's no clean pages left. This works well (the overhead of cleaning/testing doesn't effect normal tasks too often), but there is one problem: if a page is faulty, then I can't assume that the "pointer to the next free page" that's stored in that page wasn't corrupted, and need to discard the entire free page stack. Of course faulty RAM is fairly rare, and (for e.g.) with 1024 free page stacks and 2 GiB of free RAM it'd only discard 2 MiB of RAM on average (and more free page stacks means less discarded RAM).


Cheers,

Brendan

[egos]

...I'm planning to use the combination of a bitmap (which can easily allocate contiguous physical blocks) for the first MBs, and of a stack of free pages (which is faster for non-contiguous blocks) for the rest of the memory.

Hi andreaorru, I'm using exactly like this PMM structures.

I just want to know if I have got it right: with 4GB of RAM, would the page stack permanently take up 8MB of memory? Or is there some tricks that I don't know?

For the systems that support 32-bit physical addressing 4 mb region of virt addr space is more than enough if you plan to store in the stack the physical address for every page. Now I use the method when own stack pages are unmapping for allocation only if the stack is empty, i.e. main stack counter is equal to 0. In this way the memory assigned by the stack (its amount depends on amount of available memory in the system) really will not reduce until the stack is empty.

[AndreaOrru]

...I'm planning to use the combination of a bitmap (which can easily allocate contiguous physical blocks) for the first MBs, and of a stack of free pages (which is faster for non-contiguous blocks) for the rest of the memory.

Hi andreaorru, I'm using exactly like this PMM structures.

I just want to know if I have got it right: with 4GB of RAM, would the page stack permanently take up 8MB of memory? Or is there some tricks that I don't know?

For the systems that support 32-bit physical addressing 4 mb region of virt addr space is more than enough if you plan to store in the stack the physical address for every page. Now I use the method when own stack pages are unmapping for allocation only if the stack is empty, i.e. main stack counter is equal to 0. In this way the memory assigned by the stack (its amount depends on amount of available memory in the system) really will not reduce until the stack is empty.

I'm in long mode, so every address is 8 byte in size. The stack would occupy the 0.195% of all the memory.

What about this?
http://forum.osdev.org/viewtopic.php?t=11320#p77052
"free page index tables"

[egos]

I'm in long mode, so every address is 8 byte in size. The stack would occupy the 0.195% of all the memory.

Long mode can be based on 32-bit physical addressing. You can determine maximum supported size of the RAM for your system by yourself. The stack size will depend on this one.

What about this?
http://forum.osdev.org/viewtopic.php?t=11320#p77052
"free page index tables"

For large physical address space they can be used, but I'm not using them, because now my kernel only supports 32-bit physical addressing. By this cause it is not required to map/unmap own stack pages while the stack (FPT, Free Page Table) contains at least one free page address, so that's very good.

[AndreaOrru]

I'm in long mode, so every address is 8 byte in size. The stack would occupy the 0.195% of all the memory.

Long mode can be based on 32-bit physical addressing. You can determine maximum supported size of the RAM for your system by yourself. The stack size will depend on this one.

I know, I used a percentage!

What about this?
http://forum.osdev.org/viewtopic.php?t=11320#p77052
"free page index tables"

For large physical address space they can be used, but I'm not using them, because now my kernel only supports 32-bit physical addressing. By this cause it is not required to map/unmap own stack pages while the stack (FPT, Free Page Table) contains at least one free page address, so that's very good.

It's comfortable, that's for sure =)