Messages in this thread | | | Date | Sat, 30 Jan 1999 11:45:48 -0600 (CST) | From | "Robert M. Hyatt" <> |
| |
Apologies if I am going back over old stuff... but I've thought about the page coloring idea and have some comments:
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/
| |