Managing Used/Free pages

[chris]

What options besides a bitmap or a stack based approach are common in Operating Systems to store which physcial pages are free or not?

[Brendan]

Hi,

What options besides a bitmap or a stack based approach are common in Operating Systems to store which physcial pages are free or not?

There are some implementations that keep track of a linked list of allocated and/or free physical memory ranges.

Free page stacks are the fastest way, but they aren't any good if you need to allocate a block of pages (for ISA DMA for e.g.), or if you use multiple page sizes (2 Mb or 4 Mb, and 4 Kb) because sooner or later you'd need to combine several 4 Kb pages into a larger size. Also you can't keep track of non-RAM areas (BIOS, device memory, etc) with free page stacks. Free page stacks are good because they are fast and require very little overhead to manage (as little as a single pointer to the top page in the stack).

Bitmaps are simple and can be fast (if you keep track of the addresses for the lowest and/or highest free pages). They can also handle multiple page sizes and blocks of pages without much problem. Bitmaps do use more overhead though - 1 byte or 1 bit per 4 Kb page. If you use 1 byte per 4 Kb page then the bitmap (bytemap?) can also handle non-RAM areas.

The linked list approach isn't as fast and can use more overhead (it depends on how fragmented physical memory becomes). It can handle multiple page sizes, blocks of pages and non-RAM areas.

I use a bitmap (1 byte per page) for memory below 16 Mb and free page stacks (up to 512 of them) for free RAM pages above 16 Mb. I've also got a "list of memory areas" which is almost the same as the data you get from "int 0x15 AX=0xE820", and a similar list for NUMA memory ranges. I use 4 Kb pages only.


Cheers,

Brendan

[Pype.Clicker]

alternatively to 'flat' bitmap, you may have a "summary bitmap". Each entry of the 'summary bitmap' tells you if a slice of page in the "flat bitmap" is completely free, completely used or mixes free & used pages...

Another possible technique is to use the "watermark" allocation: you assume memory has two contiguous region: lowest one is "used" and the upper one is "free". When you need memory, you copy the value of the "free" pointer and increment it by the amount of memory you need. As long as allocated memory needn't to be released, it works pretty fine

[chris]

Thanks for you replies.

There are some implementations that keep track of a linked list of allocated and/or free physical memory ranges.

How can a linked list be setup so early at boot (ie. no malloc())?

[Pype.Clicker]

Note that it's a linked list of *physical pages*. Each free page has naturally 4KB of free space in it, so you simply write at the start of a page the frame number of the next free page in the list and voil?.

When 'allocating' a page, all you have to do is:
1. get the frame number of the 'head' free page from a global var.
2. map this page somewhere in memory
3. read the 'next free frame' number and write it in the global var
4. return the frame number

[Legend]

Whenever you find some sort of array (bitmap) or list (stack, at least you can implement it on top of list classes most times ), see if a tree performs better (similiar to that "summary bitmap")

[DennisCGc]

Okay, what I use is the AVAIL bits, I can't figure out why I would use them (three bits ;D )
The last bit of the AVAIL bits is used to determine whether it has been used, or not.

[chris]

Note that it's a linked list of *physical pages*. Each free page has naturally 4KB of free space in it, so you simply write at the start of a page the frame number of the next free page in the list and voil?.

When 'allocating' a page, all you have to do is:
1. get the frame number of the 'head' free page from a global var.
2. map this page somewhere in memory
3. read the 'next free frame' number and write it in the global var
4. return the frame number

Ahh, thanks.

[Pype.Clicker]

Okay, what I use is the AVAIL bits, I can't figure out why I would use them (three bits ;D )
The last bit of the AVAIL bits is used to determine whether it has been used, or not.

hmm ?? are you sure we're talking about the same thing, Dennis ? AVL bits in page tables to store frames usage ? so how do you know what frame you could allocate for a page (say virtual address 0x12345000) ? And how will it keep working when you'll have several address spaces ?

** edit ** linked this thread at the FAQ

[DennisCGc]

I thought we were talking about memory management
Now, I have a simple way, so no virtual memory management.
The original question was:

What options besides a bitmap or a stack based approach are common in Operating Systems to store which physcial pages are free or not?

I'm replying on that question...

And how will it keep working when you'll have several address spaces ?

I don't know sure what you're talking about, but let me give a try.
The "main" (which the kernel use) page tables covers the whole memory. So, this could be use, IMHO, as a normal way of managing your memory.
I'm not talking about virtual mem. management, I have to think about this!

Then there's process management (which I think IMO you're talking about).
How about creating a new pagedirs with pagetables an placing it at a 4k boundary ?
And those pagetables are referring to the app.

I hope I made myself clear. If I didn't ask me

DennisCGc.

[Pype.Clicker]

okay, so you're assuming the existence of a 'kernel process' that will be mapping (preferrably x->x+k) the whole physical memory, right ? (or simply that they'll be enough space in the 'kernel half' of each process to map all physical memory ?)

indeed in that case you could use one of the 'AVL' bits to store the usability information...

However, i think that it will make thing worse than a bitmap, since in a bitmap you can check 32 pages in a row with a single operation (there's at least one page free if dword!=0)