[LWN Logo]

To:	linux-kernel@vger.rutgers.edu
Subject: Page coloring HOWTO [ans]
From:	lm@bitmover.com (Larry McVoy)
Date:	Sat, 30 Jan 1999 13:20:22 -0800

[ lots of stuff on how to do page coloring deleted ]

I've seen how this was done twice, both at Sun and SGI.  Here's what they
do.  This assumes a direct mapped level 2 cache, which is typical.  It's
different if it is set associative, how it is different is an exercise
left for the reader.

This alg will do two critical things:

    (a) make sure that each process maps the same virtual addresses to 
        different locations in the cache, if possible.
    (b) make sure that a contiguous chunk of virtual address space in
        one process occupies a contiguous chunk of cache, if possible.

The first thing you do is to take your page free list and turn it into a
hash list, where the # of buckets in hash list is your cache size divided
by page size.

Then take each page, hash on physical address, stick it in the appropriate
bucket.

Page allocation becomes hash on virtual address and take a page from
the bucket.However, here's the trick that fans them out in the cache,
you hash on virtual address plus pid (I don't remember the exact details
but you'll get it immeditately when you implement it - you just process
0 to take page 0 from bucket 0, process 1 to take page 0 from bucket 1,
and so on).

This works really well; Linus may object because it puts some logic in
the alloc_page/free_page path that isn't there right now, so we should
figure out how to measure that and see what it costs.  I don't have a
good feel for the page alloc/free rate under various loads, does anyone?

The nice thing about this model, by the way, is that it makes the
system much more deterministic in its performance.  Some programs will
go faster, some will go slower, but the nice thing is that unlike the
current situation, you can figure out which programs go slower and
shuffle their data around to make them go faster.  Under the current
model, you're screwed because you get different results each time you
run and there isn't a damn thing you can do about it.

The point is that we should *not* use the fact that some programs go
slower to mean that page coloring is bad.  Fix the programs.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/