[hackers] Re: Page Coloring Defines in vm_page.h

[Alan L. Cox]

David Schultz wrote:
> 
> On Wed, Jun 25, 2003, David Gilbert wrote:
> > >>>>> "Matthew" == Matthew Dillon <dillon at apollo.backplane.com> writes:
> >
> > Matthew>     The primes are designed such that the page allocation
> > Matthew> code covers *ALL* the free lists in the array, so it will
> > Matthew> still be able to find any available free pages if its first
> > Matthew> choice(s) are empty.
> >
> > Matthew>     For example, prime number 3 an array size 8 will scan the
> > Matthew> array in the following order N = (N + PRIME) &
> > Matthew> (ARRAY_SIZE_MASK).  N = (N + 3) & 7:
> >
> > Matthew>     0 3 6 1 4 7 2 5 ... 0
> >
> > Matthew>     As you can see, all the array entries are covered before
> > Matthew> the sequence repeats.  So if we want a free page in array
> > Matthew> slot 0 but the only free pages available happen to be in
> > Matthew> array slot 5, the above algorithm is guarenteed to find it.
> >
> > Matthew>     Only certain prime number / power-of-2-array size
> > Matthew> combinations have this effect, but it is very easy to write a
> > Matthew> little program to test combinations and find the numbers best
> > Matthew> suited to your goals.
> >
> > For the mathematically inclined, 3 would be a 'generator' of the
> > group.
> 
> That's the part I already know.  I want to know why 4 MB and 2 MB
> caches use primes less than 32, 1 MB caches use primes less than
> 16, 512K caches use a non-prime, and 256K caches use primes
> smaller than 8.  The code refers to PQ_HASH_SIZE, which has never
> existed as far as I can tell...

Substitute PQ_L2_SIZE for PQ_HASH_SIZE in those comments.  Going a step
further, globally substituting PQ_COLORS for PQ_L2_SIZE would make
sense.  PQ_L2_SIZE is a misleading name.  (Please consider this
encouragement to commit such a change.  :-))

Alan