Date: Wed, 25 Jun 2003 10:57:21 -0400 From: David Gilbert <dgilbert@velocet.ca> To: Matthew Dillon <dillon@apollo.backplane.com> Cc: hackers@FreeBSD.ORG Subject: [hackers] Re: Page Coloring Defines in vm_page.h Message-ID: <16121.47185.522249.637280@canoe.velocet.net> In-Reply-To: <200306241630.h5OGUPU6094228@apollo.backplane.com> References: <20030624111942.GO31354@spc.org> <200306241630.h5OGUPU6094228@apollo.backplane.com>
next in thread | previous in thread | raw e-mail | index | archive | help
>>>>> "Matthew" == Matthew Dillon <dillon@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@velocet.net | equal if and only if they | |http://daveg.ca | are precisely opposite. | =========================================================GLO================
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?16121.47185.522249.637280>