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

[David Gilbert]

>>>>> "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.

Dave.

-- 
============================================================================
|David Gilbert, Velocet Communications.       | Two things can only be     |
|Mail:       dgilbert at velocet.net             |  equal if and only if they |
|http://daveg.ca                              |   are precisely opposite.  |
=========================================================GLO================