Page Frame Allocator

[kdx7214]

I'm now at the point of writing my page frame allocator. I've gone through the various articles on the wiki and have come up with something of a hybrid of what Brendan mentioned in one thread.

Basically the idea is that a pointer (8-byte) is stored somewhere in the kernel and it points to the first free page. The first 8-bytes of the page itself points to the next free page. Continue until free memory used up. This has the advantage of not taking large amounts of space for a bitmap but retains ease of use. It does, however, require initialization of each page when building the free page list - which could take a small amount of time on systems with large amounts of ram.

The question I have arises from the inability to check to see if a page is currently mapped or not. Is this something that's going to be a problem in a more developed kernel? I've been considering it and cannot think of any real reason to need that capability but thought I should ask people with more experience before I get neck deep in code again.

Thanks!
Mike

[Nessphoro]

I use bitmaps, you know what I think about them? Set it, and forget it!

But really for 4GB of memory you need ~131KB of bitmap, and more over you can check 32 pages at a time (64 on AMD64) ( and do tricks like bitmap!=0xFFFFFFFF), so really I do not see anything that you gain with your approach.

Cheers

P.S. Heck you could even fit that into BIOS VRAM(0xA0000)

[gerryg400]

There is lots of information that you may need/want to store for each physical page besides whether it is mapped or not.

1. A reference count of the number of mappings that use the page. You may need this on an SMP system even if you don't support shared memory so the mm doesn't free a page that the kernel is still using.
2. LRU information to decide when the page can be considered for swapping.
3. Status information (dirty, locked, zeroed etc.)
4. Information about which process owns the page and how it is being used.
5. Reverse lookup information.

I have a small structure for every physical page in the mm. Besides the above info it also stores a doubly linked list node. This allows for O(1) insertion and deletion. I think it's about 32 bytes per page (0.78 % of total physical memory). The structure may get bigger as I add more feature to my mm.

[Edit] for 4GB of ram I need about 128MB of structures to track the memory. Quite a bit more (1000x) than Nessphoro's bitmap but considerably more flexible.

[Nessphoro]

Ah, well I use only bare minimum bitmaps.

[kdx7214]

Gerry: Thanks for the insight! I knew there had to be some reason what I thought of wouldn't work too well. I hadn't even considered the SMP aspects of the situation. I'm currently looking at 16 bytes per 4k page. I'm not fond of the memory footprint (albeit small) but it gives the most flexibility.

To be honest, I can't figure out how to make a bitmap work w/o having to include bitmaps for all the unmapped areas (holes, etc...) and then how does one mark them as missing with a single bit?

I'll go back and rethink this some more and go from there. If anyone has any other suggestions please feel free to chime in. I'm always looking for new ways to do stuff.

Thanks again!
Mike

[Nessphoro]

James Molloy describes how to use bitmaps,

http://www.jamesmolloy.co.uk/tutorial_h ... aging.html

[xyzzy]

To be honest, I can't figure out how to make a bitmap work w/o having to include bitmaps for all the unmapped areas (holes, etc...) and then how does one mark them as missing with a single bit?

You could have a separate bitmap for each free memory range, rather than just one for the whole of physical memory, and use an array of structs like this:

Code: Select all

struct Memory_range {
        uint64_t start;
        uint64_t end;
        uint8_t *bitmap;
};

Then to free, you would search through the array to find the range containing the page you're freeing, subtract the base address of that range from the page's address and use that to calculate the bit to clear. This does add a little bit of overhead, as you have to loop through the array on each alloc/free. However, there shouldn't be too many entries in the array: my physical memory manager uses this method for looking up the Page structure for a page, and my test box with 2GB of RAM ends up with 4 entries in its array.