Physical memory management alongside paging

[kraks]

Hi,

I'm thinking and thinking but can't find a satisfying solution. My problem in short: Should the data of the Physical-MM be able to grow itself or not.

My first approach was a bitmap for P-MM, id-paged somewhere. My problem with this: Allocation of continous memory is hard/slow (and I don't like the idea of using buddy).
Second approach was a free-chunk-list. The list of chunks could be expanded dynamically since allocation didn't aquire a growth of the list. But that's hard to combine with paging since when the list of chunks relocates itself and a new page-table must be allocated. Pre-allocating space for a page-table would be an option but this gets horrible I think.
My third one was to use pre-allocated space for the chunk-list (not be able to grow then) and id-page this. Unfortunately a waste of memory.

So this raises the one question for me:
Should I use fixed-size memory or not? Fixed-size has the advantage of easy maintainance, it would just run. If the data-structures grow (and shrink) on demand, the code becomes way more complex, especially because relocation requires an adjustment of the page-tables.

edit: Huh, the text reads a little confusing, sorry for that but I currently can't express myself more specific. Or more to the point.

[frank]

The total amount of memory in the system will hardly ever change, unless you want to support hot-plugable memory (does it even exist?) so you could preallocate the maximum amount of space needed for the free page list.

Or this way is a bit more complicated and I forgot where I read about it you could keep a start of free physical memory pointer. Then at the beginning of each unused page you store the address of the next free page. When you allocate a new page you read the next free page pointer at the beginning of the block before you hand it to the process and update the start of free physical memory pointer. Since all of the pointers are stored in unused blocks you only have to have space for the start of free physical memory pointer.

[geppyfx]

You should have done a search.

For physical I like fixed size.
1) Bitmap in preallocated physical ram & prealocated virtual memory. Bitmap is smallest data structure considering maximum fragmentation is achieved. No space for pointers to waste.
2) Linked list or linked list+bitmap in unused physical ram. One 4kb page points to another for as long as you don't use them. 0 bytes wasted because your entire list is in unused ram.

[Combuster]

unless you want to support hot-plugable memory (does it even exist?)

On several chipsets, you can reclaim the memory under 0xA0000-0xFFFFF, or part thereof. Most people like to count that as "hotpluggable" since you don't have it at boot and you can add it later. Similarly, you could use video memory as a place to store data when system memory runs out (knowing paging to disk is much slower).

1) Bitmap in preallocated physical ram & prealocated virtual memory. Bitmap is smallest data structure

The pointer queue as mentioned, or any stack-based approach are both fast and only require memory when it is unused. If you use all memory, the stack contains 0 items, and therefore need not occupy any space. A bitmap will always use part of the address space, and is in comparison very slow. (allocation in linear time vs constant time)

You should have done a search.

Google query wanted. And please tell me how the OP knew about the buddy allocator and chunk lists.

[Brendan]

Hi,

unless you want to support hot-plugable memory (does it even exist?)

Yes, hot-plug RAM does exist, mostly in high-end servers. IMHO it wouldn't be very hard to support "hot-add" RAM ("hot-remove" is harder). The ACPI tables (the SRAT) will tell you which areas of RAM support hot-plug, and you can compare this with detected RAM to find out which areas are currently present and not present. This also means that you can work out the maximum amount of RAM that could be plugged in and allow for that.

On several chipsets, you can reclaim the memory under 0xA0000-0xFFFFF, or part thereof. Most people like to count that as "hotpluggable" since you don't have it at boot and you can add it later. Similarly, you could use video memory as a place to store data when system memory runs out (knowing paging to disk is much slower).

Once you've got the framework in place, I'd also use if for more mundane things (like reclaiming the "ACPI reclaimable" areas).

Note: In general it'd probably be better to use excess video memory as swap space, as it doesn't behave quite the same as normal RAM from a performance/caching perspective (however this doesn't necessarily apply to onboard video where the video uses part of main RAM, as you might be able to resize the amount of RAM used for video and adjust MTRRs to suit).

[EDIT] Also, for some computers (e.g. 4 GiB of RAM where the motherboard doesn't support relocating RAM above 4 GiB) it'd probably be possible to relocate memory mapped PCI devices, then increase the amount of RAM that's actually usable, so that (for e.g.) rather than only being able to use 3 GiB of the 4 GiB of RAM you might be able to use 3.75 GiB of the 4 GiB of RAM.[/EDIT]

As always, for physical memory management, bitmaps are only good if you need contiguous physical pages (which is mostly only needed for DMA buffers). In all other cases free page stack/s (or a variation on this theme) are better; and I usually recommend using both (e.g. a bitmap for physical memory below 16 MiB so the OS can satisfy requests for contiguous physical pages, and free page stack/s for all other RAM). In both cases "hot-add" is easy - you set bits in the bitmap and/or "push" pages onto the correct free page stack. For "hot-remove" a bitmap has an advantage (you can find free pages that are about to be removed easily), but this is a relatively small advantage when you consider finding "still in use" pages that are about to be removed...


Cheers,

Brendan

[kraks]

Thank you for the answers! Unfortunately, I don't really get the way your suggestions work. I hope you don't mind answering these additional questions:

@Linked list in unused RAM: How do I handle this in a paging-environment? Seems like I would have to either keep the full area paged or to create mappings whenever there's a free page which can't be accessed with the current page-tables? At least it sounds like a very good system for lower memory which I keep id-mapped anyway.

@Stack-based memory allocator: Do you really mean a "real stack", where stuff needs to be freed in reverse order than allocated? In which situations would that apply, I don't think I could base all my allocations on that..?

@Bitmaps for continuous pages: I'm quite confused now as I thought that bitmaps work well for allocating single pages only. Or do you use it only for counts of 8/16/32/64 continuous pages while ignoring the "border-crossing" free regions?

[Mark139]

I used a stack for my physical memory manager.

It's a very simple solution. Basically you need to use some free ram to store a list of physical page boundary addresses. You hand them out as needed and put them back in when no longer needed. It's quite efficient in that, if required, you can hand out all physical pages. The last one you hand out is the last holding your stack. When the next page is returned that can become the start of a new stack.

The api only needs 2 functions. GetPage() ReturnPage() or whatever names you want.

Of course there are complications regarding loosing pages if threads die etc.

[Brendan]

Hi,

@Linked list in unused RAM: How do I handle this in a paging-environment? Seems like I would have to either keep the full area paged or to create mappings whenever there's a free page which can't be accessed with the current page-tables? At least it sounds like a very good system for lower memory which I keep id-mapped anyway.

There's a trick to it. When you free a page, you store a link to the next page on the stack in the page before the page is freed (while it's still mapped into the virtual address space) and only then free it. When you allocate a page you map it into the virtual address space, and then get the link to the next page on the stack. In this way you only need a "physical address of the first page on the stack" variable for each free page stack.

Note: a free page stack keeps track of free pages, not allocated pages. Basically freeing a page means pushing the page onto the top of the stack, and allocating a page means popping it off the top of the stack.

@Bitmaps for continuous pages: I'm quite confused now as I thought that bitmaps work well for allocating single pages only. Or do you use it only for counts of 8/16/32/64 continuous pages while ignoring the "border-crossing" free regions?

For allocating single pages, there's no way to avoid searching the bitmap (e.g. searching for the next free page or searching for the next set/clear bit in the bitmap). The best you can do is keep track of the lowest and highest potentially free page.

For example, imagine a small bitmap that looks like "FxxxxFFFFxxxxF" (where 'F' represents a free page). The "lowest potentially free page" variable points to the first page. Now, if you allocate the first page it becomes "xxxxxFFFFxxxxF", and you know the first page can't be the lowest potentially free page anymore you increment the "lowest potentially free page" variable. Now the "lowest potentially free page" points to the second entry, which isn't free. You could search for the next free page (and keep track of the lowest and highest guaranteed free page), but that is slower because you may have searched for no reason (e.g. a page that is lower than the current "lowest guaranteed free page" may be freed before another page is allocated). Instead, you search when you allocate a page (starting at wherever the "lowest potentially free page" variable points).

I'm not too sure if this will make sense to you. Just in case, here's some untested/unusable/example code that might help...

Version 1 (lowest potentially free page):

Code: Select all

void *allocate_one_page(void) {
    while( myBitmap[lowest_potentially_free_page] != FREE) lowest_potentially_free_page++;
    page_number = lowest_potentially_free_page++;
    myBitmap[page_number] = NOT_FREE;
    return page_number * 4096;
}

void free_one_page(void *address) {
    page_number = address / 4096;
    myBitmap[page_number] = FREE;
    if(page_number < lowest_potentially_free_page) lowest_potentially_free_page = page_number;
}

Version 2 (lowest free page):

Code: Select all

void *allocate_one_page(void) {
    page_number = lowest_free_page++;
    myBitmap[page_number] = NOT_FREE;
    while( myBitmap[lowest_free_page] != FREE) lowest_free_page++;
    return page_number * 4096;
}

void free_one_page(void *address) {
    page_number = address / 4096;
    myBitmap[page_number] = FREE;
    if(page_number < lowest_free_page) lowest_free_page = page_number;
}

If you think about it, the first version is faster because it can avoid a pointless search. For a "worst case" example, imagine if there's no free pages left and you do:

Code: Select all

    free_one_page(0x10000000);
    free_one_page(0x00000000);
    for(;;) {
        address = allocate_one_page();
        free_one_page(address);
    }

In this "worst case" example, the first version wouldn't search the bitmap at all, and the second version would repeatedly search millions of entries for no reason.

For free page stacks there is never any searching - it's guaranteed to be "O(1)" in all cases.

However, the order of pages popped off of a free page stack depends on the order they were pushed on the stack, which means there's no way to ensure that allocated pages are contiguous. For bitmaps you can search for any number of contiguous pages (e.g. search for a run of N set/clear bits in the bitmap).

Bitmaps also allow you to search based on other restrictions. For example, you can search for contiguous pages that don't cross a 64 KiB boundary (which is something you probably will want to be able to do, due to restrictions in the old ISA DMA controllers).


Cheers,

Brendan

[kraks]

Ok so I do understand everything now, thank you very much!

PS: The linked-list in used RAM-trick is really tricky, very cool.