From owner-freebsd-hackers@FreeBSD.ORG Tue Jun 24 09:30:26 2003 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id BA3F737B401; Tue, 24 Jun 2003 09:30:26 -0700 (PDT) Received: from apollo.backplane.com (apollo.backplane.com [216.240.41.2]) by mx1.FreeBSD.org (Postfix) with ESMTP id 1B1E643FB1; Tue, 24 Jun 2003 09:30:26 -0700 (PDT) (envelope-from dillon@apollo.backplane.com) Received: from apollo.backplane.com (localhost [127.0.0.1]) by apollo.backplane.com (8.12.9/8.12.6) with ESMTP id h5OGUPVI094229; Tue, 24 Jun 2003 09:30:25 -0700 (PDT) (envelope-from dillon@apollo.backplane.com) Received: (from dillon@localhost) by apollo.backplane.com (8.12.9/8.12.6/Submit) id h5OGUPU6094228; Tue, 24 Jun 2003 09:30:25 -0700 (PDT) Date: Tue, 24 Jun 2003 09:30:25 -0700 (PDT) From: Matthew Dillon Message-Id: <200306241630.h5OGUPU6094228@apollo.backplane.com> To: Bruce M Simpson References: <20030624111942.GO31354@spc.org> cc: alc@FreeBSD.ORG cc: davidg@FreeBSD.ORG cc: hackers@FreeBSD.ORG Subject: Re: Page Coloring Defines in vm_page.h X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 24 Jun 2003 16:30:27 -0000 : - The page queue structures are sized according to these : defines at boot-time. : : - If someone could fill me in on how the primes are arrived at that : would be very helpful. : :Comments/discussion/correction welcomed, it would be good to get some :feedback on this before I start patching my tree. : :BMS The primes are designed such that the page allocation code covers *ALL* the free lists in the array, so it will still be able to find any available free pages if its first choice(s) are empty. For example, prime number 3 an array size 8 will scan the array in the following order N = (N + PRIME) & (ARRAY_SIZE_MASK). N = (N + 3) & 7: 0 3 6 1 4 7 2 5 ... 0 As you can see, all the array entries are covered before the sequence repeats. So if we want a free page in array slot 0 but the only free pages available happen to be in array slot 5, the above algorithm is guarenteed to find it. Only certain prime number / power-of-2-array size combinations have this effect, but it is very easy to write a little program to test combinations and find the numbers best suited to your goals. -Matt Matthew Dillon