I'd like to mention that I am very happy that this has become an area of
work in the kernel - it's been a thorn in my side for about 5 years that
Linux hasn't had this. I'm looking forward to seeing the final version
of whatever code ends up doing this.
On Tue, Apr 11, 2000 at 05:24:48PM -0400, Joseph A. Martin wrote:
> A simple but effective page coloring patch
> ------------------------------------------
> Page coloring is the assignment of physical pages to virtual mappings
> in a manner which attempts to avoid cache conflicts. One approach is
> to match (modulo the cache size) the addresses of virtual and physical
> pages. The approach taken by this patch is to assemble non-colliding,
> cache-filling collections of physical pages and then to distribute
> them in order as single user pages are requested.
Actually, the alg I've seen most is as follows:
suppose you have a cache which can hold 256 pages (1MB w/ 4K pages)
take all the physical pages and divide them into 256 buckets based
on their page number modulo 256.
take the virtual address, convert to a page number, the (this is
very important) add the process id (or some other randomizing
but unchanging value) to the page number and modulo by 256.
The point is to make sure that address 0, for example, ends up in a different
location for each process. Every OS has some addresses which are "special",
i.e., used in each process. Some people put the string "(null)\n" at 0
so that you can do stupid stuff like "printf("%s\n", 0); Other examples
are the dynamic linker's table - this one doesn't always land at the same
place but the way the code works, it usually lands at the same place, etc.
So you want the randomizer.
> Characteristics (the ones I can think of at the moment):
> - small, self-contained text and data additions to the kernel
Yeah, I like this part but I'm not so sure about the actual logic of the
changes.
One way to see what you've done quickly is to run LMbench and then look at
the memory graphs. If you have perfect coloring (and on an idle system there
is no reason you shouldn't) then the graph should look like
b
+-------------------------
|
|
|
|
|
|
a |
+-----------+
|
|
|
-----------+
You are looking for a perfect "step" function and where the page coloring
effects show up is on the second step, which is the level 2 cache (yeah,
it will be different on an alpha with 3 levels of caches, but you get the
idea).
Without page coloring, what you will see is a jagged line between points
a and b, with the area under the jagged line being lost performance to
any applications which wants even caching over a sequential cached sized
chunk of pages.
I'd really like to see the LMbench results. If you do 5 before/after
runs and mail me the results, I'll convert them to gifs and put them
up on our website. We could compare them with Dave's version of this
code which looks quite good.
I'm more than a little concerned with the effects of this code on the
kernel build benchmark. My experience is that the kernel build benchmark
is a really bad one to screw up - there are a lot of applications which,
while very different, tend to tickle the system in a similar way. So if
the kernel build is screwed up then there are other things which will be
screwed up.
Thanks!
-- --- Larry McVoy lm@bitmover.com http://www.bitmover.com/lm- 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/
This archive was generated by hypermail 2b29 : Sat Apr 15 2000 - 21:00:21 EST