I'll start a major rewrite (basically from scratch) of the physical memory allocation scheme. I've discovered that this part of the kernel isn't possible to port to PAE-paging without great difficulties, so I need to do this before I continue with PAE.
I'll use the 4K bitmap approach, with a 4 byte header for each bitmap, as this can be implemented without spinlocks, which is a great advantage.
The header will look like this:
Code: Select all
BitMapHeader struct
{
short int FreePages;
short int CurrentPos;
};
The FreePages field can be updated without spinlocks (lock add FreePages,1 and lock sub FreePages,1), and also give an indication that the current bitmap is empty so it can be switched from. The CurrentPos is only advisory, so doesn't need lock prefix. It indicates where to start to search for free pages. It will be updated as the current dword is 0 (no free pages). As the position wraps around, the block is switched from.
Allocating a bit is done with lock btr. If the operation fails (content was already 0), a new attempt is made. The actual bit to try to allocate is speculative and thus doesn't need locking (probably the algorithm will read a dword at CurrentPos, find a set bit (bsf), and try to allocate it).
Switching active block is done by finding the first block with the largest number of free pages. This is done like that because allocation speed is faster the more free pages a bitmap contains. This search algorithm is lockless.
The current active block is kept per processor core, which would decrease lock contention. Later, it might be possible to improve this further by changing the switching of active block algorithm to favor different blocks for cores.
As an option, I might later decide to change allocation model when physical memory is scarce. Then I might let all frees place the pages in a stack instead, where allocate can retrieve them.
I think I will use 8MB linear address space for the page bitmaps, which would support 256GB of physical memory.
