Home | History | Annotate | Line # | Download | only in uvm
uvm_page.c revision 1.18
      1 /*	$NetBSD: uvm_page.c,v 1.18 1999/04/11 04:04:11 chs Exp $	*/
      2 
      3 /*
      4  * Copyright (c) 1997 Charles D. Cranor and Washington University.
      5  * Copyright (c) 1991, 1993, The Regents of the University of California.
      6  *
      7  * All rights reserved.
      8  *
      9  * This code is derived from software contributed to Berkeley by
     10  * The Mach Operating System project at Carnegie-Mellon University.
     11  *
     12  * Redistribution and use in source and binary forms, with or without
     13  * modification, are permitted provided that the following conditions
     14  * are met:
     15  * 1. Redistributions of source code must retain the above copyright
     16  *    notice, this list of conditions and the following disclaimer.
     17  * 2. Redistributions in binary form must reproduce the above copyright
     18  *    notice, this list of conditions and the following disclaimer in the
     19  *    documentation and/or other materials provided with the distribution.
     20  * 3. All advertising materials mentioning features or use of this software
     21  *    must display the following acknowledgement:
     22  *	This product includes software developed by Charles D. Cranor,
     23  *      Washington University, the University of California, Berkeley and
     24  *      its contributors.
     25  * 4. Neither the name of the University nor the names of its contributors
     26  *    may be used to endorse or promote products derived from this software
     27  *    without specific prior written permission.
     28  *
     29  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     30  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     31  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     32  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     33  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     34  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     35  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     37  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     38  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     39  * SUCH DAMAGE.
     40  *
     41  *	@(#)vm_page.c   8.3 (Berkeley) 3/21/94
     42  * from: Id: uvm_page.c,v 1.1.2.18 1998/02/06 05:24:42 chs Exp
     43  *
     44  *
     45  * Copyright (c) 1987, 1990 Carnegie-Mellon University.
     46  * All rights reserved.
     47  *
     48  * Permission to use, copy, modify and distribute this software and
     49  * its documentation is hereby granted, provided that both the copyright
     50  * notice and this permission notice appear in all copies of the
     51  * software, derivative works or modified versions, and any portions
     52  * thereof, and that both notices appear in supporting documentation.
     53  *
     54  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
     55  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
     56  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
     57  *
     58  * Carnegie Mellon requests users of this software to return to
     59  *
     60  *  Software Distribution Coordinator  or  Software.Distribution (at) CS.CMU.EDU
     61  *  School of Computer Science
     62  *  Carnegie Mellon University
     63  *  Pittsburgh PA 15213-3890
     64  *
     65  * any improvements or extensions that they make and grant Carnegie the
     66  * rights to redistribute these changes.
     67  */
     68 
     69 /*
     70  * uvm_page.c: page ops.
     71  */
     72 
     73 #include "opt_pmap_new.h"
     74 
     75 #include <sys/param.h>
     76 #include <sys/systm.h>
     77 #include <sys/malloc.h>
     78 #include <sys/proc.h>
     79 
     80 #include <vm/vm.h>
     81 #include <vm/vm_page.h>
     82 #include <vm/vm_kern.h>
     83 
     84 #define UVM_PAGE                /* pull in uvm_page.h functions */
     85 #include <uvm/uvm.h>
     86 
     87 /*
     88  * global vars... XXXCDC: move to uvm. structure.
     89  */
     90 
     91 /*
     92  * physical memory config is stored in vm_physmem.
     93  */
     94 
     95 struct vm_physseg vm_physmem[VM_PHYSSEG_MAX];	/* XXXCDC: uvm.physmem */
     96 int vm_nphysseg = 0;				/* XXXCDC: uvm.nphysseg */
     97 
     98 /*
     99  * local variables
    100  */
    101 
    102 /*
    103  * these variables record the values returned by vm_page_bootstrap,
    104  * for debugging purposes.  The implementation of uvm_pageboot_alloc
    105  * and pmap_startup here also uses them internally.
    106  */
    107 
    108 static vaddr_t      virtual_space_start;
    109 static vaddr_t      virtual_space_end;
    110 
    111 /*
    112  * we use a hash table with only one bucket during bootup.  we will
    113  * later rehash (resize) the hash table once malloc() is ready.
    114  * we static allocate the bootstrap bucket below...
    115  */
    116 
    117 static struct pglist uvm_bootbucket;
    118 
    119 /*
    120  * local prototypes
    121  */
    122 
    123 static void uvm_pageinsert __P((struct vm_page *));
    124 
    125 
    126 /*
    127  * inline functions
    128  */
    129 
    130 /*
    131  * uvm_pageinsert: insert a page in the object and the hash table
    132  *
    133  * => caller must lock object
    134  * => caller must lock page queues
    135  * => call should have already set pg's object and offset pointers
    136  *    and bumped the version counter
    137  */
    138 
    139 __inline static void
    140 uvm_pageinsert(pg)
    141 	struct vm_page *pg;
    142 {
    143 	struct pglist *buck;
    144 	int s;
    145 
    146 #ifdef DIAGNOSTIC
    147 	if (pg->flags & PG_TABLED)
    148 		panic("uvm_pageinsert: already inserted");
    149 #endif
    150 
    151 	buck = &uvm.page_hash[uvm_pagehash(pg->uobject,pg->offset)];
    152 	s = splimp();
    153 	simple_lock(&uvm.hashlock);
    154 	TAILQ_INSERT_TAIL(buck, pg, hashq);	/* put in hash */
    155 	simple_unlock(&uvm.hashlock);
    156 	splx(s);
    157 
    158 	TAILQ_INSERT_TAIL(&pg->uobject->memq, pg, listq); /* put in object */
    159 	pg->flags |= PG_TABLED;
    160 	pg->uobject->uo_npages++;
    161 
    162 }
    163 
    164 /*
    165  * uvm_page_remove: remove page from object and hash
    166  *
    167  * => caller must lock object
    168  * => caller must lock page queues
    169  */
    170 
    171 void __inline
    172 uvm_pageremove(pg)
    173 	struct vm_page *pg;
    174 {
    175 	struct pglist *buck;
    176 	int s;
    177 
    178 #ifdef DIAGNOSTIC
    179 	if ((pg->flags & (PG_FAULTING)) != 0)
    180 		panic("uvm_pageremove: page is faulting");
    181 #endif
    182 
    183 	if ((pg->flags & PG_TABLED) == 0)
    184 		return;				/* XXX: log */
    185 
    186 	buck = &uvm.page_hash[uvm_pagehash(pg->uobject,pg->offset)];
    187 	s = splimp();
    188 	simple_lock(&uvm.hashlock);
    189 	TAILQ_REMOVE(buck, pg, hashq);
    190 	simple_unlock(&uvm.hashlock);
    191 	splx(s);
    192 
    193 	/* object should be locked */
    194 	TAILQ_REMOVE(&pg->uobject->memq, pg, listq);
    195 
    196 	pg->flags &= ~PG_TABLED;
    197 	pg->uobject->uo_npages--;
    198 	pg->uobject = NULL;
    199 	pg->version++;
    200 
    201 }
    202 
    203 /*
    204  * uvm_page_init: init the page system.   called from uvm_init().
    205  *
    206  * => we return the range of kernel virtual memory in kvm_startp/kvm_endp
    207  */
    208 
    209 void
    210 uvm_page_init(kvm_startp, kvm_endp)
    211 	vaddr_t *kvm_startp, *kvm_endp;
    212 {
    213 	int freepages, pagecount;
    214 	vm_page_t pagearray;
    215 	int lcv, n, i;
    216 	paddr_t paddr;
    217 
    218 
    219 	/*
    220 	 * step 1: init the page queues and page queue locks
    221 	 */
    222 	for (lcv = 0; lcv < VM_NFREELIST; lcv++)
    223 	  TAILQ_INIT(&uvm.page_free[lcv]);
    224 	TAILQ_INIT(&uvm.page_active);
    225 	TAILQ_INIT(&uvm.page_inactive_swp);
    226 	TAILQ_INIT(&uvm.page_inactive_obj);
    227 	simple_lock_init(&uvm.pageqlock);
    228 	simple_lock_init(&uvm.fpageqlock);
    229 
    230 	/*
    231 	 * step 2: init the <obj,offset> => <page> hash table. for now
    232 	 * we just have one bucket (the bootstrap bucket).   later on we
    233 	 * will malloc() new buckets as we dynamically resize the hash table.
    234 	 */
    235 
    236 	uvm.page_nhash = 1;			/* 1 bucket */
    237 	uvm.page_hashmask = 0;		/* mask for hash function */
    238 	uvm.page_hash = &uvm_bootbucket;	/* install bootstrap bucket */
    239 	TAILQ_INIT(uvm.page_hash);		/* init hash table */
    240 	simple_lock_init(&uvm.hashlock);	/* init hash table lock */
    241 
    242 	/*
    243 	 * step 3: allocate vm_page structures.
    244 	 */
    245 
    246 	/*
    247 	 * sanity check:
    248 	 * before calling this function the MD code is expected to register
    249 	 * some free RAM with the uvm_page_physload() function.   our job
    250 	 * now is to allocate vm_page structures for this memory.
    251 	 */
    252 
    253 	if (vm_nphysseg == 0)
    254 		panic("vm_page_bootstrap: no memory pre-allocated");
    255 
    256 	/*
    257 	 * first calculate the number of free pages...
    258 	 *
    259 	 * note that we use start/end rather than avail_start/avail_end.
    260 	 * this allows us to allocate extra vm_page structures in case we
    261 	 * want to return some memory to the pool after booting.
    262 	 */
    263 
    264 	freepages = 0;
    265 	for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
    266 		freepages += (vm_physmem[lcv].end - vm_physmem[lcv].start);
    267 
    268 	/*
    269 	 * we now know we have (PAGE_SIZE * freepages) bytes of memory we can
    270 	 * use.   for each page of memory we use we need a vm_page structure.
    271 	 * thus, the total number of pages we can use is the total size of
    272 	 * the memory divided by the PAGE_SIZE plus the size of the vm_page
    273 	 * structure.   we add one to freepages as a fudge factor to avoid
    274 	 * truncation errors (since we can only allocate in terms of whole
    275 	 * pages).
    276 	 */
    277 
    278 	pagecount = ((freepages + 1) << PAGE_SHIFT) /
    279 	    (PAGE_SIZE + sizeof(struct vm_page));
    280 	pagearray = (vm_page_t)uvm_pageboot_alloc(pagecount *
    281 	    sizeof(struct vm_page));
    282 	memset(pagearray, 0, pagecount * sizeof(struct vm_page));
    283 
    284 	/*
    285 	 * step 4: init the vm_page structures and put them in the correct
    286 	 * place...
    287 	 */
    288 
    289 	for (lcv = 0 ; lcv < vm_nphysseg ; lcv++) {
    290 
    291 		n = vm_physmem[lcv].end - vm_physmem[lcv].start;
    292 		if (n > pagecount) {
    293 			printf("uvm_page_init: lost %d page(s) in init\n",
    294 			    n - pagecount);
    295 			panic("uvm_page_init");  /* XXXCDC: shouldn't happen? */
    296 			/* n = pagecount; */
    297 		}
    298 		/* set up page array pointers */
    299 		vm_physmem[lcv].pgs = pagearray;
    300 		pagearray += n;
    301 		pagecount -= n;
    302 		vm_physmem[lcv].lastpg = vm_physmem[lcv].pgs + (n - 1);
    303 
    304 		/* init and free vm_pages (we've already zeroed them) */
    305 		paddr = ptoa(vm_physmem[lcv].start);
    306 		for (i = 0 ; i < n ; i++, paddr += PAGE_SIZE) {
    307 			vm_physmem[lcv].pgs[i].phys_addr = paddr;
    308 			if (atop(paddr) >= vm_physmem[lcv].avail_start &&
    309 			    atop(paddr) <= vm_physmem[lcv].avail_end) {
    310 				uvmexp.npages++;
    311 				/* add page to free pool */
    312 				uvm_pagefree(&vm_physmem[lcv].pgs[i]);
    313 			}
    314 		}
    315 	}
    316 	/*
    317 	 * step 5: pass up the values of virtual_space_start and
    318 	 * virtual_space_end (obtained by uvm_pageboot_alloc) to the upper
    319 	 * layers of the VM.
    320 	 */
    321 
    322 	*kvm_startp = round_page(virtual_space_start);
    323 	*kvm_endp = trunc_page(virtual_space_end);
    324 
    325 	/*
    326 	 * step 6: init pagedaemon lock
    327 	 */
    328 
    329 	simple_lock_init(&uvm.pagedaemon_lock);
    330 
    331 	/*
    332 	 * step 7: init reserve thresholds
    333 	 * XXXCDC - values may need adjusting
    334 	 */
    335 	uvmexp.reserve_pagedaemon = 1;
    336 	uvmexp.reserve_kernel = 5;
    337 
    338 	/*
    339 	 * done!
    340 	 */
    341 
    342 }
    343 
    344 /*
    345  * uvm_setpagesize: set the page size
    346  *
    347  * => sets page_shift and page_mask from uvmexp.pagesize.
    348  * => XXXCDC: move global vars.
    349  */
    350 
    351 void
    352 uvm_setpagesize()
    353 {
    354 	if (uvmexp.pagesize == 0)
    355 		uvmexp.pagesize = DEFAULT_PAGE_SIZE;
    356 	uvmexp.pagemask = uvmexp.pagesize - 1;
    357 	if ((uvmexp.pagemask & uvmexp.pagesize) != 0)
    358 		panic("uvm_setpagesize: page size not a power of two");
    359 	for (uvmexp.pageshift = 0; ; uvmexp.pageshift++)
    360 		if ((1 << uvmexp.pageshift) == uvmexp.pagesize)
    361 			break;
    362 }
    363 
    364 /*
    365  * uvm_pageboot_alloc: steal memory from physmem for bootstrapping
    366  */
    367 
    368 vaddr_t
    369 uvm_pageboot_alloc(size)
    370 	vsize_t size;
    371 {
    372 #if defined(PMAP_STEAL_MEMORY)
    373 	vaddr_t addr;
    374 
    375 	/*
    376 	 * defer bootstrap allocation to MD code (it may want to allocate
    377 	 * from a direct-mapped segment).  pmap_steal_memory should round
    378 	 * off virtual_space_start/virtual_space_end.
    379 	 */
    380 
    381 	addr = pmap_steal_memory(size, &virtual_space_start,
    382 	    &virtual_space_end);
    383 
    384 	return(addr);
    385 
    386 #else /* !PMAP_STEAL_MEMORY */
    387 
    388 	vaddr_t addr, vaddr;
    389 	paddr_t paddr;
    390 
    391 	/* round to page size */
    392 	size = round_page(size);
    393 
    394 	/*
    395 	 * on first call to this function init ourselves.   we detect this
    396 	 * by checking virtual_space_start/end which are in the zero'd BSS area.
    397 	 */
    398 
    399 	if (virtual_space_start == virtual_space_end) {
    400 		pmap_virtual_space(&virtual_space_start, &virtual_space_end);
    401 
    402 		/* round it the way we like it */
    403 		virtual_space_start = round_page(virtual_space_start);
    404 		virtual_space_end = trunc_page(virtual_space_end);
    405 	}
    406 
    407 	/*
    408 	 * allocate virtual memory for this request
    409 	 */
    410 
    411 	addr = virtual_space_start;
    412 	virtual_space_start += size;
    413 
    414 	/*
    415 	 * allocate and mapin physical pages to back new virtual pages
    416 	 */
    417 
    418 	for (vaddr = round_page(addr) ; vaddr < addr + size ;
    419 	    vaddr += PAGE_SIZE) {
    420 
    421 		if (!uvm_page_physget(&paddr))
    422 			panic("uvm_pageboot_alloc: out of memory");
    423 
    424 		/* XXX: should be wired, but some pmaps don't like that ... */
    425 #if defined(PMAP_NEW)
    426 		pmap_kenter_pa(vaddr, paddr, VM_PROT_READ|VM_PROT_WRITE);
    427 #else
    428 		pmap_enter(pmap_kernel(), vaddr, paddr,
    429 		    VM_PROT_READ|VM_PROT_WRITE, FALSE,
    430 		    VM_PROT_READ|VM_PROT_WRITE);
    431 #endif
    432 
    433 	}
    434 	return(addr);
    435 #endif	/* PMAP_STEAL_MEMORY */
    436 }
    437 
    438 #if !defined(PMAP_STEAL_MEMORY)
    439 /*
    440  * uvm_page_physget: "steal" one page from the vm_physmem structure.
    441  *
    442  * => attempt to allocate it off the end of a segment in which the "avail"
    443  *    values match the start/end values.   if we can't do that, then we
    444  *    will advance both values (making them equal, and removing some
    445  *    vm_page structures from the non-avail area).
    446  * => return false if out of memory.
    447  */
    448 
    449 boolean_t
    450 uvm_page_physget(paddrp)
    451 	paddr_t *paddrp;
    452 {
    453 	int lcv, x;
    454 
    455 	/* pass 1: try allocating from a matching end */
    456 #if (VM_PHYSSEG_STRAT == VM_PSTRAT_BIGFIRST)
    457 	for (lcv = vm_nphysseg - 1 ; lcv >= 0 ; lcv--)
    458 #else
    459 	for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
    460 #endif
    461 	{
    462 
    463 		if (vm_physmem[lcv].pgs)
    464 			panic("vm_page_physget: called _after_ bootstrap");
    465 
    466 		/* try from front */
    467 		if (vm_physmem[lcv].avail_start == vm_physmem[lcv].start &&
    468 		    vm_physmem[lcv].avail_start < vm_physmem[lcv].avail_end) {
    469 			*paddrp = ptoa(vm_physmem[lcv].avail_start);
    470 			vm_physmem[lcv].avail_start++;
    471 			vm_physmem[lcv].start++;
    472 			/* nothing left?   nuke it */
    473 			if (vm_physmem[lcv].avail_start ==
    474 			    vm_physmem[lcv].end) {
    475 				if (vm_nphysseg == 1)
    476 				    panic("vm_page_physget: out of memory!");
    477 				vm_nphysseg--;
    478 				for (x = lcv ; x < vm_nphysseg ; x++)
    479 					/* structure copy */
    480 					vm_physmem[x] = vm_physmem[x+1];
    481 			}
    482 			return (TRUE);
    483 		}
    484 
    485 		/* try from rear */
    486 		if (vm_physmem[lcv].avail_end == vm_physmem[lcv].end &&
    487 		    vm_physmem[lcv].avail_start < vm_physmem[lcv].avail_end) {
    488 			*paddrp = ptoa(vm_physmem[lcv].avail_end - 1);
    489 			vm_physmem[lcv].avail_end--;
    490 			vm_physmem[lcv].end--;
    491 			/* nothing left?   nuke it */
    492 			if (vm_physmem[lcv].avail_end ==
    493 			    vm_physmem[lcv].start) {
    494 				if (vm_nphysseg == 1)
    495 				    panic("vm_page_physget: out of memory!");
    496 				vm_nphysseg--;
    497 				for (x = lcv ; x < vm_nphysseg ; x++)
    498 					/* structure copy */
    499 					vm_physmem[x] = vm_physmem[x+1];
    500 			}
    501 			return (TRUE);
    502 		}
    503 	}
    504 
    505 	/* pass2: forget about matching ends, just allocate something */
    506 #if (VM_PHYSSEG_STRAT == VM_PSTRAT_BIGFIRST)
    507 	for (lcv = vm_nphysseg - 1 ; lcv >= 0 ; lcv--)
    508 #else
    509 	for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
    510 #endif
    511 	{
    512 
    513 		/* any room in this bank? */
    514 		if (vm_physmem[lcv].avail_start >= vm_physmem[lcv].avail_end)
    515 			continue;  /* nope */
    516 
    517 		*paddrp = ptoa(vm_physmem[lcv].avail_start);
    518 		vm_physmem[lcv].avail_start++;
    519 		/* truncate! */
    520 		vm_physmem[lcv].start = vm_physmem[lcv].avail_start;
    521 
    522 		/* nothing left?   nuke it */
    523 		if (vm_physmem[lcv].avail_start == vm_physmem[lcv].end) {
    524 			if (vm_nphysseg == 1)
    525 				panic("vm_page_physget: out of memory!");
    526 			vm_nphysseg--;
    527 			for (x = lcv ; x < vm_nphysseg ; x++)
    528 				/* structure copy */
    529 				vm_physmem[x] = vm_physmem[x+1];
    530 		}
    531 		return (TRUE);
    532 	}
    533 
    534 	return (FALSE);        /* whoops! */
    535 }
    536 #endif /* PMAP_STEAL_MEMORY */
    537 
    538 /*
    539  * uvm_page_physload: load physical memory into VM system
    540  *
    541  * => all args are PFs
    542  * => all pages in start/end get vm_page structures
    543  * => areas marked by avail_start/avail_end get added to the free page pool
    544  * => we are limited to VM_PHYSSEG_MAX physical memory segments
    545  */
    546 
    547 void
    548 uvm_page_physload(start, end, avail_start, avail_end, free_list)
    549 	vaddr_t start, end, avail_start, avail_end;
    550 	int free_list;
    551 {
    552 	int preload, lcv;
    553 	psize_t npages;
    554 	struct vm_page *pgs;
    555 	struct vm_physseg *ps;
    556 
    557 	if (uvmexp.pagesize == 0)
    558 		panic("vm_page_physload: page size not set!");
    559 
    560 	if (free_list >= VM_NFREELIST || free_list < VM_FREELIST_DEFAULT)
    561 		panic("uvm_page_physload: bad free list %d\n", free_list);
    562 
    563 	/*
    564 	 * do we have room?
    565 	 */
    566 	if (vm_nphysseg == VM_PHYSSEG_MAX) {
    567 		printf("vm_page_physload: unable to load physical memory "
    568 		    "segment\n");
    569 		printf("\t%d segments allocated, ignoring 0x%lx -> 0x%lx\n",
    570 		    VM_PHYSSEG_MAX, start, end);
    571 		return;
    572 	}
    573 
    574 	/*
    575 	 * check to see if this is a "preload" (i.e. uvm_mem_init hasn't been
    576 	 * called yet, so malloc is not available).
    577 	 */
    578 	for (lcv = 0 ; lcv < vm_nphysseg ; lcv++) {
    579 		if (vm_physmem[lcv].pgs)
    580 			break;
    581 	}
    582 	preload = (lcv == vm_nphysseg);
    583 
    584 	/*
    585 	 * if VM is already running, attempt to malloc() vm_page structures
    586 	 */
    587 	if (!preload) {
    588 #if defined(VM_PHYSSEG_NOADD)
    589 		panic("vm_page_physload: tried to add RAM after vm_mem_init");
    590 #else
    591 		/* XXXCDC: need some sort of lockout for this case */
    592 		paddr_t paddr;
    593 		npages = end - start;  /* # of pages */
    594 		MALLOC(pgs, struct vm_page *, sizeof(struct vm_page) * npages,
    595 					 M_VMPAGE, M_NOWAIT);
    596 		if (pgs == NULL) {
    597 			printf("vm_page_physload: can not malloc vm_page "
    598 			    "structs for segment\n");
    599 			printf("\tignoring 0x%lx -> 0x%lx\n", start, end);
    600 			return;
    601 		}
    602 		/* zero data, init phys_addr and free_list, and free pages */
    603 		memset(pgs, 0, sizeof(struct vm_page) * npages);
    604 		for (lcv = 0, paddr = ptoa(start) ;
    605 				 lcv < npages ; lcv++, paddr += PAGE_SIZE) {
    606 			pgs[lcv].phys_addr = paddr;
    607 			pgs[lcv].free_list = free_list;
    608 			if (atop(paddr) >= avail_start &&
    609 			    atop(paddr) <= avail_end)
    610 				uvm_pagefree(&pgs[lcv]);
    611 		}
    612 		/* XXXCDC: incomplete: need to update uvmexp.free, what else? */
    613 		/* XXXCDC: need hook to tell pmap to rebuild pv_list, etc... */
    614 #endif
    615 	} else {
    616 
    617 		/* gcc complains if these don't get init'd */
    618 		pgs = NULL;
    619 		npages = 0;
    620 
    621 	}
    622 
    623 	/*
    624 	 * now insert us in the proper place in vm_physmem[]
    625 	 */
    626 
    627 #if (VM_PHYSSEG_STRAT == VM_PSTRAT_RANDOM)
    628 
    629 	/* random: put it at the end (easy!) */
    630 	ps = &vm_physmem[vm_nphysseg];
    631 
    632 #elif (VM_PHYSSEG_STRAT == VM_PSTRAT_BSEARCH)
    633 
    634 	{
    635 		int x;
    636 		/* sort by address for binary search */
    637 		for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
    638 			if (start < vm_physmem[lcv].start)
    639 				break;
    640 		ps = &vm_physmem[lcv];
    641 		/* move back other entries, if necessary ... */
    642 		for (x = vm_nphysseg ; x > lcv ; x--)
    643 			/* structure copy */
    644 			vm_physmem[x] = vm_physmem[x - 1];
    645 	}
    646 
    647 #elif (VM_PHYSSEG_STRAT == VM_PSTRAT_BIGFIRST)
    648 
    649 	{
    650 		int x;
    651 		/* sort by largest segment first */
    652 		for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
    653 			if ((end - start) >
    654 			    (vm_physmem[lcv].end - vm_physmem[lcv].start))
    655 				break;
    656 		ps = &vm_physmem[lcv];
    657 		/* move back other entries, if necessary ... */
    658 		for (x = vm_nphysseg ; x > lcv ; x--)
    659 			/* structure copy */
    660 			vm_physmem[x] = vm_physmem[x - 1];
    661 	}
    662 
    663 #else
    664 
    665 	panic("vm_page_physload: unknown physseg strategy selected!");
    666 
    667 #endif
    668 
    669 	ps->start = start;
    670 	ps->end = end;
    671 	ps->avail_start = avail_start;
    672 	ps->avail_end = avail_end;
    673 	if (preload) {
    674 		ps->pgs = NULL;
    675 	} else {
    676 		ps->pgs = pgs;
    677 		ps->lastpg = pgs + npages - 1;
    678 	}
    679 	ps->free_list = free_list;
    680 	vm_nphysseg++;
    681 
    682 	/*
    683 	 * done!
    684 	 */
    685 
    686 	if (!preload)
    687 		uvm_page_rehash();
    688 
    689 	return;
    690 }
    691 
    692 /*
    693  * uvm_page_rehash: reallocate hash table based on number of free pages.
    694  */
    695 
    696 void
    697 uvm_page_rehash()
    698 {
    699 	int freepages, lcv, bucketcount, s, oldcount;
    700 	struct pglist *newbuckets, *oldbuckets;
    701 	struct vm_page *pg;
    702 
    703 	/*
    704 	 * compute number of pages that can go in the free pool
    705 	 */
    706 
    707 	freepages = 0;
    708 	for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
    709 		freepages +=
    710 		    (vm_physmem[lcv].avail_end - vm_physmem[lcv].avail_start);
    711 
    712 	/*
    713 	 * compute number of buckets needed for this number of pages
    714 	 */
    715 
    716 	bucketcount = 1;
    717 	while (bucketcount < freepages)
    718 		bucketcount = bucketcount * 2;
    719 
    720 	/*
    721 	 * malloc new buckets
    722 	 */
    723 
    724 	MALLOC(newbuckets, struct pglist *, sizeof(struct pglist) * bucketcount,
    725 					 M_VMPBUCKET, M_NOWAIT);
    726 	if (newbuckets == NULL) {
    727 		printf("vm_page_physrehash: WARNING: could not grow page "
    728 		    "hash table\n");
    729 		return;
    730 	}
    731 	for (lcv = 0 ; lcv < bucketcount ; lcv++)
    732 		TAILQ_INIT(&newbuckets[lcv]);
    733 
    734 	/*
    735 	 * now replace the old buckets with the new ones and rehash everything
    736 	 */
    737 
    738 	s = splimp();
    739 	simple_lock(&uvm.hashlock);
    740 	/* swap old for new ... */
    741 	oldbuckets = uvm.page_hash;
    742 	oldcount = uvm.page_nhash;
    743 	uvm.page_hash = newbuckets;
    744 	uvm.page_nhash = bucketcount;
    745 	uvm.page_hashmask = bucketcount - 1;  /* power of 2 */
    746 
    747 	/* ... and rehash */
    748 	for (lcv = 0 ; lcv < oldcount ; lcv++) {
    749 		while ((pg = oldbuckets[lcv].tqh_first) != NULL) {
    750 			TAILQ_REMOVE(&oldbuckets[lcv], pg, hashq);
    751 			TAILQ_INSERT_TAIL(
    752 			  &uvm.page_hash[uvm_pagehash(pg->uobject, pg->offset)],
    753 			  pg, hashq);
    754 		}
    755 	}
    756 	simple_unlock(&uvm.hashlock);
    757 	splx(s);
    758 
    759 	/*
    760 	 * free old bucket array if we malloc'd it previously
    761 	 */
    762 
    763 	if (oldbuckets != &uvm_bootbucket)
    764 		FREE(oldbuckets, M_VMPBUCKET);
    765 
    766 	/*
    767 	 * done
    768 	 */
    769 	return;
    770 }
    771 
    772 
    773 #if 1 /* XXXCDC: TMP TMP TMP DEBUG DEBUG DEBUG */
    774 
    775 void uvm_page_physdump __P((void)); /* SHUT UP GCC */
    776 
    777 /* call from DDB */
    778 void
    779 uvm_page_physdump()
    780 {
    781 	int lcv;
    782 
    783 	printf("rehash: physical memory config [segs=%d of %d]:\n",
    784 				 vm_nphysseg, VM_PHYSSEG_MAX);
    785 	for (lcv = 0 ; lcv < vm_nphysseg ; lcv++)
    786 		printf("0x%lx->0x%lx [0x%lx->0x%lx]\n", vm_physmem[lcv].start,
    787 		    vm_physmem[lcv].end, vm_physmem[lcv].avail_start,
    788 		    vm_physmem[lcv].avail_end);
    789 	printf("STRATEGY = ");
    790 	switch (VM_PHYSSEG_STRAT) {
    791 	case VM_PSTRAT_RANDOM: printf("RANDOM\n"); break;
    792 	case VM_PSTRAT_BSEARCH: printf("BSEARCH\n"); break;
    793 	case VM_PSTRAT_BIGFIRST: printf("BIGFIRST\n"); break;
    794 	default: printf("<<UNKNOWN>>!!!!\n");
    795 	}
    796 	printf("number of buckets = %d\n", uvm.page_nhash);
    797 }
    798 #endif
    799 
    800 /*
    801  * uvm_pagealloc_strat: allocate vm_page from a particular free list.
    802  *
    803  * => return null if no pages free
    804  * => wake up pagedaemon if number of free pages drops below low water mark
    805  * => if obj != NULL, obj must be locked (to put in hash)
    806  * => if anon != NULL, anon must be locked (to put in anon)
    807  * => only one of obj or anon can be non-null
    808  * => caller must activate/deactivate page if it is not wired.
    809  * => free_list is ignored if strat == UVM_PGA_STRAT_NORMAL.
    810  */
    811 
    812 struct vm_page *
    813 uvm_pagealloc_strat(obj, off, anon, flags, strat, free_list)
    814 	struct uvm_object *obj;
    815 	vaddr_t off;
    816 	int flags;
    817 	struct vm_anon *anon;
    818 	int strat, free_list;
    819 {
    820 	int lcv, s;
    821 	struct vm_page *pg;
    822 	struct pglist *freeq;
    823 	boolean_t use_reserve;
    824 
    825 #ifdef DIAGNOSTIC
    826 	/* sanity check */
    827 	if (obj && anon)
    828 		panic("uvm_pagealloc: obj and anon != NULL");
    829 #endif
    830 
    831 	s = splimp();
    832 
    833 	uvm_lock_fpageq();		/* lock free page queue */
    834 
    835 	/*
    836 	 * check to see if we need to generate some free pages waking
    837 	 * the pagedaemon.
    838 	 */
    839 
    840 	if (uvmexp.free < uvmexp.freemin || (uvmexp.free < uvmexp.freetarg &&
    841 	    uvmexp.inactive < uvmexp.inactarg))
    842 		thread_wakeup(&uvm.pagedaemon);
    843 
    844 	/*
    845 	 * fail if any of these conditions is true:
    846 	 * [1]  there really are no free pages, or
    847 	 * [2]  only kernel "reserved" pages remain and
    848 	 *        the page isn't being allocated to a kernel object.
    849 	 * [3]  only pagedaemon "reserved" pages remain and
    850 	 *        the requestor isn't the pagedaemon.
    851 	 */
    852 
    853 	use_reserve = (flags & UVM_PGA_USERESERVE) ||
    854 		(obj && obj->uo_refs == UVM_OBJ_KERN);
    855 	if ((uvmexp.free <= uvmexp.reserve_kernel && !use_reserve) ||
    856 	    (uvmexp.free <= uvmexp.reserve_pagedaemon &&
    857 	     !(use_reserve && curproc == uvm.pagedaemon_proc)))
    858 		goto fail;
    859 
    860  again:
    861 	switch (strat) {
    862 	case UVM_PGA_STRAT_NORMAL:
    863 		/* Check all freelists in descending priority order. */
    864 		for (lcv = 0; lcv < VM_NFREELIST; lcv++) {
    865 			freeq = &uvm.page_free[lcv];
    866 			if ((pg = freeq->tqh_first) != NULL)
    867 				goto gotit;
    868 		}
    869 
    870 		/* No pages free! */
    871 		goto fail;
    872 
    873 	case UVM_PGA_STRAT_ONLY:
    874 	case UVM_PGA_STRAT_FALLBACK:
    875 		/* Attempt to allocate from the specified free list. */
    876 #ifdef DIAGNOSTIC
    877 		if (free_list >= VM_NFREELIST || free_list < 0)
    878 			panic("uvm_pagealloc_strat: bad free list %d",
    879 			    free_list);
    880 #endif
    881 		freeq = &uvm.page_free[free_list];
    882 		if ((pg = freeq->tqh_first) != NULL)
    883 			goto gotit;
    884 
    885 		/* Fall back, if possible. */
    886 		if (strat == UVM_PGA_STRAT_FALLBACK) {
    887 			strat = UVM_PGA_STRAT_NORMAL;
    888 			goto again;
    889 		}
    890 
    891 		/* No pages free! */
    892 		goto fail;
    893 
    894 	default:
    895 		panic("uvm_pagealloc_strat: bad strat %d", strat);
    896 		/* NOTREACHED */
    897 	}
    898 
    899  gotit:
    900 	TAILQ_REMOVE(freeq, pg, pageq);
    901 	uvmexp.free--;
    902 
    903 	uvm_unlock_fpageq();		/* unlock free page queue */
    904 	splx(s);
    905 
    906 	pg->offset = off;
    907 	pg->uobject = obj;
    908 	pg->uanon = anon;
    909 	pg->flags = PG_BUSY|PG_CLEAN|PG_FAKE;
    910 	pg->version++;
    911 	pg->wire_count = 0;
    912 	pg->loan_count = 0;
    913 	if (anon) {
    914 		anon->u.an_page = pg;
    915 		pg->pqflags = PQ_ANON;
    916 	} else {
    917 		if (obj)
    918 			uvm_pageinsert(pg);
    919 		pg->pqflags = 0;
    920 	}
    921 #if defined(UVM_PAGE_TRKOWN)
    922 	pg->owner_tag = NULL;
    923 #endif
    924 	UVM_PAGE_OWN(pg, "new alloc");
    925 
    926 	return(pg);
    927 
    928  fail:
    929 	uvm_unlock_fpageq();
    930 	splx(s);
    931 	return (NULL);
    932 }
    933 
    934 /*
    935  * uvm_pagerealloc: reallocate a page from one object to another
    936  *
    937  * => both objects must be locked
    938  */
    939 
    940 void
    941 uvm_pagerealloc(pg, newobj, newoff)
    942 	struct vm_page *pg;
    943 	struct uvm_object *newobj;
    944 	vaddr_t newoff;
    945 {
    946 	/*
    947 	 * remove it from the old object
    948 	 */
    949 
    950 	if (pg->uobject) {
    951 		uvm_pageremove(pg);
    952 	}
    953 
    954 	/*
    955 	 * put it in the new object
    956 	 */
    957 
    958 	if (newobj) {
    959 		pg->uobject = newobj;
    960 		pg->offset = newoff;
    961 		pg->version++;
    962 		uvm_pageinsert(pg);
    963 	}
    964 
    965 	return;
    966 }
    967 
    968 
    969 /*
    970  * uvm_pagefree: free page
    971  *
    972  * => erase page's identity (i.e. remove from hash/object)
    973  * => put page on free list
    974  * => caller must lock owning object (either anon or uvm_object)
    975  * => caller must lock page queues
    976  * => assumes all valid mappings of pg are gone
    977  */
    978 
    979 void uvm_pagefree(pg)
    980 
    981 struct vm_page *pg;
    982 
    983 {
    984 	int s;
    985 	int saved_loan_count = pg->loan_count;
    986 
    987 	/*
    988 	 * if the page was an object page (and thus "TABLED"), remove it
    989 	 * from the object.
    990 	 */
    991 
    992 	if (pg->flags & PG_TABLED) {
    993 
    994 		/*
    995 		 * if the object page is on loan we are going to drop ownership.
    996 		 * it is possible that an anon will take over as owner for this
    997 		 * page later on.   the anon will want a !PG_CLEAN page so that
    998 		 * it knows it needs to allocate swap if it wants to page the
    999 		 * page out.
   1000 		 */
   1001 
   1002 		if (saved_loan_count)
   1003 			pg->flags &= ~PG_CLEAN;	/* in case an anon takes over */
   1004 
   1005 		uvm_pageremove(pg);
   1006 
   1007 		/*
   1008 		 * if our page was on loan, then we just lost control over it
   1009 		 * (in fact, if it was loaned to an anon, the anon may have
   1010 		 * already taken over ownership of the page by now and thus
   1011 		 * changed the loan_count [e.g. in uvmfault_anonget()]) we just
   1012 		 * return (when the last loan is dropped, then the page can be
   1013 		 * freed by whatever was holding the last loan).
   1014 		 */
   1015 		if (saved_loan_count)
   1016 			return;
   1017 
   1018 	} else if (saved_loan_count && (pg->pqflags & PQ_ANON)) {
   1019 
   1020 		/*
   1021 		 * if our page is owned by an anon and is loaned out to the
   1022 		 * kernel then we just want to drop ownership and return.
   1023 		 * the kernel must free the page when all its loans clear ...
   1024 		 * note that the kernel can't change the loan status of our
   1025 		 * page as long as we are holding PQ lock.
   1026 		 */
   1027 		pg->pqflags &= ~PQ_ANON;
   1028 		pg->uanon = NULL;
   1029 		return;
   1030 	}
   1031 
   1032 #ifdef DIAGNOSTIC
   1033 	if (saved_loan_count) {
   1034 		printf("uvm_pagefree: warning: freeing page with a loan "
   1035 		    "count of %d\n", saved_loan_count);
   1036 		panic("uvm_pagefree: loan count");
   1037 	}
   1038 #endif
   1039 
   1040 
   1041 	/*
   1042 	 * now remove the page from the queues
   1043 	 */
   1044 
   1045 	if (pg->pqflags & PQ_ACTIVE) {
   1046 		TAILQ_REMOVE(&uvm.page_active, pg, pageq);
   1047 		pg->pqflags &= ~PQ_ACTIVE;
   1048 		uvmexp.active--;
   1049 	}
   1050 	if (pg->pqflags & PQ_INACTIVE) {
   1051 		if (pg->pqflags & PQ_SWAPBACKED)
   1052 			TAILQ_REMOVE(&uvm.page_inactive_swp, pg, pageq);
   1053 		else
   1054 			TAILQ_REMOVE(&uvm.page_inactive_obj, pg, pageq);
   1055 		pg->pqflags &= ~PQ_INACTIVE;
   1056 		uvmexp.inactive--;
   1057 	}
   1058 
   1059 	/*
   1060 	 * if the page was wired, unwire it now.
   1061 	 */
   1062 	if (pg->wire_count)
   1063 	{
   1064 		pg->wire_count = 0;
   1065 		uvmexp.wired--;
   1066 	}
   1067 
   1068 	/*
   1069 	 * and put on free queue
   1070 	 */
   1071 
   1072 	s = splimp();
   1073 	uvm_lock_fpageq();
   1074 	TAILQ_INSERT_TAIL(&uvm.page_free[uvm_page_lookup_freelist(pg)],
   1075 	    pg, pageq);
   1076 	pg->pqflags = PQ_FREE;
   1077 #ifdef DEBUG
   1078 	pg->uobject = (void *)0xdeadbeef;
   1079 	pg->offset = 0xdeadbeef;
   1080 	pg->uanon = (void *)0xdeadbeef;
   1081 #endif
   1082 	uvmexp.free++;
   1083 	uvm_unlock_fpageq();
   1084 	splx(s);
   1085 }
   1086 
   1087 #if defined(UVM_PAGE_TRKOWN)
   1088 /*
   1089  * uvm_page_own: set or release page ownership
   1090  *
   1091  * => this is a debugging function that keeps track of who sets PG_BUSY
   1092  *	and where they do it.   it can be used to track down problems
   1093  *	such a process setting "PG_BUSY" and never releasing it.
   1094  * => page's object [if any] must be locked
   1095  * => if "tag" is NULL then we are releasing page ownership
   1096  */
   1097 void
   1098 uvm_page_own(pg, tag)
   1099 	struct vm_page *pg;
   1100 	char *tag;
   1101 {
   1102 	/* gain ownership? */
   1103 	if (tag) {
   1104 		if (pg->owner_tag) {
   1105 			printf("uvm_page_own: page %p already owned "
   1106 			    "by proc %d [%s]\n", pg,
   1107 			     pg->owner, pg->owner_tag);
   1108 			panic("uvm_page_own");
   1109 		}
   1110 		pg->owner = (curproc) ? curproc->p_pid :  (pid_t) -1;
   1111 		pg->owner_tag = tag;
   1112 		return;
   1113 	}
   1114 
   1115 	/* drop ownership */
   1116 	if (pg->owner_tag == NULL) {
   1117 		printf("uvm_page_own: dropping ownership of an non-owned "
   1118 		    "page (%p)\n", pg);
   1119 		panic("uvm_page_own");
   1120 	}
   1121 	pg->owner_tag = NULL;
   1122 	return;
   1123 }
   1124 #endif
   1125