[lkml]   [1999]   [Jan]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
Robert M. Hyatt writes:
> Apologies if I am going back over old stuff... but I've thought about
> the page coloring idea and have some comments:

This is exactly one of the things I was hoping for when I put out my
patch: to stir discussions about efficient page colouring algorithms.

> First, a definition, since I don't have a good term to use... 'alias
> index'. I am defining this as the cache-size / page-size... this
> gives me the number of pages that fit into cache at one time. And
> when you think about the aliasing problem, the page numbers you
> allocate to a process (assuming his program completely fits into
> cache) have to be different in the low order bits (low order bits =
> log2(alias number).

DaveM and I just called that NUM_COLOURS.

> For my xeon, cache=512K. I assume page-size=4k, but if that is wrong,
> just plug in the right number. So the 'alias index' == 128 (512K/4K).
> This means that when I allocate pages, assuming my program is _exactly_
> 128 pages (512K) long, the physical pages I want to allocate must be
> different in the low order 7 bits. Which means every physical page
> will map to a different group of lines in cache, exactly what I want.

That low 7 bits is what we're calling the colour.

> I see two (at least) ways to do this:
> I believe what Richard is doing is to allocate the first page, then
> try to find the next page in ascending sequence (hopefully in the
> alias index bits only but I didn't look at his code carefully).

I alllocate in ascending colour numbers (aka. alias index bits). This
number rolls over at NUM_COLOURS. You can see where I do the test:
if (goal++ >= NUM_COLOURS) goal = 0;
where goal is the current colour.
> This works, but I don't like the inefficiency since small programs
> still get stuck into adjacent cache 'pages' and that isn't
> necessary.

I agree it's inefficient. I'm unsure whether the ascending colours
requirement is necessary or not.

> way 2 is cuter: create a 128 bit 'map'. Allocate a page for the
> program and set the 'alias index bit' for that page in this map.
> when the next page is requested, call the code to return a free pte,
> and all that is needed is to extract the 'alias index' from the page
> number and check that bit in the 'map'. If set, this page
> 'collides' and should be 'returned'. If it doesn't, we are done.
> We keep doing this until the map gets pretty full where efficiency
> drops to the same level as what Richard is doing in his patch, but
> note that for small programs, this isn't inefficient at all, which
> has to be a goal if this becomes a standard part of the MM code.

This is an interesting approach. I think it's definately worth
trying. Are you planning on implementing this? I think it would be
worthwhile to do so and preserve both coloured page allocation schemes
so lots of people can compare them (using an ioctl() to chose on a per
process basis). If I receive such a patch I'll be happy to include it
in my patch.

The one concern I have about this (probably because I'm too lazy to
think hard about the implications), is what happens if you allocate
far more than the cache size (in my case, a dataset of ~13
MBytes) and you access that dataset in some fashion (say for(y) for(x)
for(z) where x is contiguous in memory).

Obviously, once you've filled the bitmap, you clear it again and
esentially start "fresh" for the next set of allocations. What I'm
wondering is whether the bitmap scheme could result in page
allocations which are less favourable for the access pattern I
mentioned above.

> problems:
> cache size affects the size of the collision map. For a 2M cache
> xeon, we need 512 bits rather than 128. Not exactly bad, but maybe
> Linux might not want to see that added to _every_ proc struct.

I shouldn't worry about that for the moment. You would only need to
allocate the bitmap for each process that turns on page colouring.
And anyway, 64 bytes is trivial.

> this sure becomes 'architecture' dependent, but we _could_ assume
> that cache is 4M (1024 bits which is still not real big (32 words)
> and we could allocate based on that, which would work great for
> caches 4M or smaller, and now this code doesn't have to know if you
> have 512 or 1024 or whatever. There is a minor performance hit,
> since we would be 'working hard' to do really optimal mapping for
> smaller cache machines, but it would work quite well... And the +
> for using a 1024 bit alias map is that programs < 1024 pages would
> 'map fast'. But this is not quite optimal for my 512K xeon, since I
> could still map 4 physical pages to the same cache line if I assume
> there is really 2M. Needs some thought, as in maybe a hybrid, where
> we don't allow mapping to the high 3/4 of the alias map until the
> lower 1/4 is nearly full. And we don't allow mapping to the high
> 1/2 until the lower 1/2 is nearly full.

I prefer the fully dynamic approach where you allocate the bitmap
according to the cache size.

> And note that once the map is full, or if a pass thru all available
> pte's doesn't find a physical page that has the right 'alias bits'
> set, we just clear the map and start over, assuming we have filled
> the 'first page of coloring' as well as possible.


> I'm really interested in playing with this now, but before I start,
> any comments, suggestions, flaws, improvements, etc?

Please go ahead and send me a patch. I'm happy to integrate it into my
patch and distribute it if you like.


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:50    [from the cache]
©2003-2011 Jasper Spaans