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).
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.
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). This works, but I
don't like the inefficiency since small programs still get stuck into
adjacent cache 'pages' and that isn't necessary.
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.
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.
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.
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?
Bob
Robert Hyatt Computer and Information Sciences
hyatt@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
-
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/