From owner-freebsd-hackers@FreeBSD.ORG  Thu Jun 26 03:33:10 2003
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
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 C473037B401; Thu, 26 Jun 2003 03:33:10 -0700 (PDT)
Received: from HAL9000.homeunix.com (ip114.bella-vista.sfo.interquest.net
	[66.199.86.114])	by mx1.FreeBSD.org (Postfix) with ESMTP
	id 061DB43FF5; Thu, 26 Jun 2003 03:33:10 -0700 (PDT)
	(envelope-from das@FreeBSD.ORG)
Received: from HAL9000.homeunix.com (localhost [127.0.0.1])
	by HAL9000.homeunix.com (8.12.9/8.12.9) with ESMTP id h5QAX7iP096650;
	Thu, 26 Jun 2003 03:33:07 -0700 (PDT)
	(envelope-from das@FreeBSD.ORG)
Received: (from das@localhost)
	by HAL9000.homeunix.com (8.12.9/8.12.9/Submit) id h5QAX7wR096649;
	Thu, 26 Jun 2003 03:33:07 -0700 (PDT)
	(envelope-from das@FreeBSD.ORG)
Date: Thu, 26 Jun 2003 03:33:07 -0700
From: David Schultz <das@FreeBSD.ORG>
To: David Gilbert <dgilbert@velocet.ca>
Message-ID: <20030626103307.GC94891@HAL9000.homeunix.com>
Mail-Followup-To: David Gilbert <dgilbert@velocet.ca>,
	Matthew Dillon <dillon@apollo.backplane.com>, alc@freebsd.org,
	davidg@freebsd.org, hackers@freebsd.org
References: <20030624111942.GO31354@spc.org>
	<200306241630.h5OGUPU6094228@apollo.backplane.com>
	<16121.47185.522249.637280@canoe.velocet.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <16121.47185.522249.637280@canoe.velocet.net>
cc: alc@FreeBSD.ORG
cc: Matthew Dillon <dillon@apollo.backplane.com>
cc: hackers@FreeBSD.ORG
cc: davidg@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
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Thu, 26 Jun 2003 10:33:11 -0000

On Wed, Jun 25, 2003, David Gilbert wrote:
> >>>>> "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.

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