Hi,
ces_mohab wrote:How to allocate multiple contiguous pages?
With free page stacks, you can't allocate contiguous pages, but, for most things the OS doesn't need contiguous pages.
The only place where contiguous pages might be needed is DMA buffers for device drivers. For this there can be other restrictions - must be below 16 MB and can't cross a 64 KB boundary (for ISA DMA), or must be below 4 GB (for 32 bit PCI devices).
To solve this, I use a free page bitmap for all memory below 16 MB. I also have different free page stacks for physical memory above 4 GB and below 4 GB. This means that a 32-bit PCI device that supports "scatter-gather" I/O can use memory from 16 MB to 4 GB, and an ISA device or a 32-bit PCI device that needs a contiguous buffer can use contiguous pages below 16 MB.
There's also a problem with cache efficiency (cache misses are extremely expensive, so reducing the chance of cache misses isn't such a bad idea). Almost all of the CPU's caches are "N-way set associative", which means for any given cache line there's only N positions in the cache where it can go. The position in the cache is determined by some of the bits in the cache line's starting address.
For example, for a given cache the physical address might be broken up such that bits 12 to 15 determine which position it can go in the cache (or the page colour). In this case it can be impossible for a 128 KB array or data structure to fit in a 1 MB cache because bits 12 to 15 of the physical addresses used match. Worst case would be if bits 12 to 15 in all of the physical pages used are identical (or all physical pages have the same page colour), where you might only be able to fit 16 KB of it in the cache at any time (for a 4-way set associative cache). Of course all of this depends on the exact "shape" of the cache.
To make sure this doesn't happen (and improve cache efficiency) some systems use "page colouring" (Windows, Solaris, FreeBSD, etc). The basic idea here is to make sure that contiguous pages in linear memory use physical pages with contiguous "important bits".
The easiest way to do this is to make sure that the important bits in the physical address of a page are the same as the important bits in the linear address of the page. This works, but some linear addresses are used more often than others (for example, most executables might be loaded at linear address 0x00001000). This can lead to uneven usage, where you run out of physical pages for one page colour while there's plenty of free pages for other page colours. This is easily prevented by giving each address space it's own starting page colour.
To implement page colouring using free page stacks, you need a seperate free page stack for each page colour. Then you'd use something like "free_page_stack = (physical_address >> M) & N" to determine which page stack a physical page should be put onto (when freeing pages), and "free_page_stack = ((linear_address >> M) + starting_colour) & N" when allocating a page. The hard part is determining M and N, which depend on the "shape" of the CPUs caches. If you get these values wrong you end up with reduced cache efficiency or a higher chance of uneven page colour usage (worst case would be similar performance to a system that doesn't implement page colouring).
Cheers,
Brendan