Re: "Colo[u]rs"

[Robert Love <rml@tech9.net>]

On Mon, 2001-12-10 at 03:00, Stevie O wrote:

> For the n-way associative deal:

If the cache is n-way associative, it can store n lines at each
mapping.  So even though two virtual addresses map to the same cache
line, they can both be stored.  Of course, if you have k addresses such
that k>n, then you reach the same problem as direct map (the case where
n=1) caches.

To reiterate, the point of coloring would be to prevent the case of
multiple addresses mapping to the same line.  Let me give you a
real-life example.  We recently have been trying to color the kernel
stack.  If every process's stack lies at the same address (let alone the
same page multiple and offset), then they all map to the same place in
the cache and we can effectively only cache one of them (and
subsequently cache miss on every other access).  If we "color" the
location of the stack, we make sure they don't all map to the same
place.  This obviously involves some knowledge of the cache system, but
it tends to be general enough that we can get it right for all cases.

If you are _really_ interested in this, an excellent and very thorough
book is UNIX Systems for Modern Architectures: Symmetric Multiprocessing
and Caching for Kernel Programmers, by Curt Schimmel.

	Robert Love