From owner-freebsd-hackers@FreeBSD.ORG Thu Jun 26 09:28:40 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 2C5E937B401 for ; Thu, 26 Jun 2003 09:28:40 -0700 (PDT) Received: from mail26c.sbc-webhosting.com (mail26c.sbc-webhosting.com [216.173.237.166]) by mx1.FreeBSD.org (Postfix) with SMTP id ECB5943FE3 for ; Thu, 26 Jun 2003 09:28:38 -0700 (PDT) (envelope-from alc@imimic.com) Received: from www.imimic.com (64.143.12.21)2-0173544777; Thu, 26 Jun 2003 12:26:17 -0400 (EDT) Sender: alc@FreeBSD.ORG Message-ID: <3EFB1EAA.4AB12892@imimic.com> Date: Thu, 26 Jun 2003 11:26:18 -0500 From: "Alan L. Cox" Organization: iMimic Networking, Inc. X-Mailer: Mozilla 4.8 [en] (X11; U; Linux 2.4.2 i386) X-Accept-Language: en MIME-Version: 1.0 To: David Schultz References: <20030624111942.GO31354@spc.org> <200306241630.h5OGUPU6094228@apollo.backplane.com> <16121.47185.522249.637280@canoe.velocet.net> <20030626103307.GC94891@HAL9000.homeunix.com> Content-Type: text/plain; charset=x-user-defined Content-Transfer-Encoding: 7bit X-Loop-Detect: 1 cc: alc@FreeBSD.ORG cc: David Gilbert cc: davidg@FreeBSD.ORG cc: Matthew Dillon cc: hackers@FreeBSD.ORG Subject: Re: [hackers] 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: Thu, 26 Jun 2003 16:28:40 -0000 David Schultz wrote: > > On Wed, Jun 25, 2003, David Gilbert wrote: > > >>>>> "Matthew" == Matthew Dillon 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