I've recently been through "VM design issues in FreeBSD" (available through BonaFide tutorials) and there are a few points that are still obscure in my mind.
Roughly, page colouring consist of making sure that we will not degrade caching performance by a poor page allocation. Because the cache has only place for a few pages that are at the same physical address modulo N, we must take care of not overusing pages that are on the same x%N in a contiguous region of the virtual address space (otherwise, the program's locallity doesn't help the cache hit anymore) ...
but ...
- How can one know that 'N', the cache size ? I guess on Pentium, it will be available through CPUID ... and is it necessary to have the exact value or can't we work with a sub-multiple K which would give good performance with many cache size
- So far, i imagine one can implement colouring by having K/pagesize lists or bitmaps rather than a single one for memory management. If we want to allocate a page for address X, we will select a physical page from list X%K, which has the control of pages {\/ n in |N: y = x%K + n}. Is there a better technique ?
- What if the proper sublist / subbitmap is exhausted ? Is there an optimal way of selecting another list / bitmap or just trying the (X%K)+1 then (X%K)+2 give the same kind of performance as a more evoluated technique ?