Page Coloring Defines in vm_page.h

[Terry Lambert]

Bruce M Simpson wrote:
> Something occurred to me whilst I was re-reading the 'Design Elements'
> article over the weekend; our page coloring algorithm, as it stands,
> might not be optimal for non-Intel CPUs.

Actually, it does very well for most architectures, and was originally
developed into product for SPARC and MIPS (by Sun and MIPS Inc.,
respectively).

There are 29 research papers that specifically mention "page coloring";
here is the citation:

	http://citeseer.nj.nec.com/cs?q=page+coloring&cs=1

I'm going to claim that this is one of the better ones (;^)), mostly
because it has some nice real statistics, and represents a rather fun
approach to the problem, which doesn't actually involve page coloring,
and touches on the rather neat idea of doing cache affinity as part of
the scheduler operation:

	http://citeseer.nj.nec.com/410298.html

Also, it has a couple of nice references to related works you aren't
going to find online: you will need to find yourself a technical
library; references 1, 6, 8, 9, and 12 especially.


>    - Why is this important? The vm code as it stands assumes that we
>      colour for L2 cache. This might not be optimal for all architectures,
>      or, indeed, forthcoming x86 chips.

The code previously colored for both L1 and L2.  It turns out
that the penalty you pay for L1 set overlap is relatively low,
comparatively, due to the difference in comparative size between
L1 and L2.  See also:

	http://citeseer.nj.nec.com/kessler92page.html

>   - The defines in vm_page.h seem to assume a 4-way set associative
>     cache organization.

Yes.  This was the most common L2 cache hardware arrangement at
the time.

There were a couple of good postings on page coloring on the
FreeBSD lists back in the mid 1990's by John Dyson, who was the
original implementor of both the page coloring code and the
unified VM and buffer cache code, which Poul was complaining was
incomplete, in the recent FS stacking thread on -arch.  You can
probably find them in the archives on Minnie (Warren Toomey's
archival machine).


>   - If someone could fill me in on how the primes are arrived at that
>     would be very helpful.

It's an attempt to get a perfect hash without collision; page
coloring relies on avoiding cache line overlap, if at all possible
(sometimes it isn't, which is why the page coloring compiler work
and the cache affinity scheduler are such intriguing ideas, to me
at least, though the compiler work would probably be incredibly
hard to tune in any useful fashion to work across an entire CPU
family, rather than specific CPU instances).

-- Terry