vm_page.c revision 49305
1178825Sdfr/*
2178825Sdfr * Copyright (c) 1991 Regents of the University of California.
3178825Sdfr * All rights reserved.
4178825Sdfr *
5178825Sdfr * This code is derived from software contributed to Berkeley by
6178825Sdfr * The Mach Operating System project at Carnegie-Mellon University.
7178825Sdfr *
8178825Sdfr * Redistribution and use in source and binary forms, with or without
9178825Sdfr * modification, are permitted provided that the following conditions
10178825Sdfr * are met:
11178825Sdfr * 1. Redistributions of source code must retain the above copyright
12178825Sdfr *    notice, this list of conditions and the following disclaimer.
13178825Sdfr * 2. Redistributions in binary form must reproduce the above copyright
14178825Sdfr *    notice, this list of conditions and the following disclaimer in the
15178825Sdfr *    documentation and/or other materials provided with the distribution.
16178825Sdfr * 3. All advertising materials mentioning features or use of this software
17178825Sdfr *    must display the following acknowledgement:
18178825Sdfr *	This product includes software developed by the University of
19178825Sdfr *	California, Berkeley and its contributors.
20178825Sdfr * 4. Neither the name of the University nor the names of its contributors
21178825Sdfr *    may be used to endorse or promote products derived from this software
22178825Sdfr *    without specific prior written permission.
23178825Sdfr *
24178825Sdfr * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25178825Sdfr * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26178825Sdfr * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27178825Sdfr * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28178825Sdfr * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29178825Sdfr * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30178825Sdfr * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31178825Sdfr * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32178825Sdfr * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33178825Sdfr * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34178825Sdfr * SUCH DAMAGE.
35178825Sdfr *
36178825Sdfr *	from: @(#)vm_page.c	7.4 (Berkeley) 5/7/91
37178825Sdfr *	$Id: vm_page.c,v 1.134 1999/07/01 19:53:42 peter Exp $
38178825Sdfr */
39178825Sdfr
40178825Sdfr/*
41178825Sdfr * Copyright (c) 1987, 1990 Carnegie-Mellon University.
42178825Sdfr * All rights reserved.
43178825Sdfr *
44178825Sdfr * Authors: Avadis Tevanian, Jr., Michael Wayne Young
45178825Sdfr *
46178825Sdfr * Permission to use, copy, modify and distribute this software and
47178825Sdfr * its documentation is hereby granted, provided that both the copyright
48178825Sdfr * notice and this permission notice appear in all copies of the
49178825Sdfr * software, derivative works or modified versions, and any portions
50178825Sdfr * thereof, and that both notices appear in supporting documentation.
51178825Sdfr *
52178825Sdfr * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
53178825Sdfr * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
54178825Sdfr * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
55178825Sdfr *
56178825Sdfr * Carnegie Mellon requests users of this software to return to
57178825Sdfr *
58178825Sdfr *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
59178825Sdfr *  School of Computer Science
60178825Sdfr *  Carnegie Mellon University
61178825Sdfr *  Pittsburgh PA 15213-3890
62178825Sdfr *
63178825Sdfr * any improvements or extensions that they make and grant Carnegie the
64178825Sdfr * rights to redistribute these changes.
65178825Sdfr */
66178825Sdfr
67178825Sdfr/*
68178825Sdfr *	Resident memory management module.
69178825Sdfr */
70178825Sdfr
71178825Sdfr#include <sys/param.h>
72178825Sdfr#include <sys/systm.h>
73178825Sdfr#include <sys/malloc.h>
74178825Sdfr#include <sys/proc.h>
75178825Sdfr#include <sys/vmmeter.h>
76178825Sdfr#include <sys/vnode.h>
77178825Sdfr
78#include <vm/vm.h>
79#include <vm/vm_param.h>
80#include <vm/vm_prot.h>
81#include <sys/lock.h>
82#include <vm/vm_kern.h>
83#include <vm/vm_object.h>
84#include <vm/vm_page.h>
85#include <vm/vm_pageout.h>
86#include <vm/vm_pager.h>
87#include <vm/vm_extern.h>
88
89static void	vm_page_queue_init __P((void));
90static vm_page_t vm_page_select_cache __P((vm_object_t, vm_pindex_t));
91
92/*
93 *	Associated with page of user-allocatable memory is a
94 *	page structure.
95 */
96
97static struct vm_page **vm_page_buckets; /* Array of buckets */
98static int vm_page_bucket_count;	/* How big is array? */
99static int vm_page_hash_mask;		/* Mask for hash function */
100static volatile int vm_page_bucket_generation;
101
102struct pglist vm_page_queue_free[PQ_L2_SIZE] = {{0}};
103struct pglist vm_page_queue_active = {0};
104struct pglist vm_page_queue_inactive = {0};
105struct pglist vm_page_queue_cache[PQ_L2_SIZE] = {{0}};
106
107struct vpgqueues vm_page_queues[PQ_COUNT] = {{0}};
108static int pqcnt[PQ_COUNT] = {0};
109
110static void
111vm_page_queue_init(void) {
112	int i;
113
114	for(i=0;i<PQ_L2_SIZE;i++) {
115		vm_page_queues[PQ_FREE+i].pl = &vm_page_queue_free[i];
116		vm_page_queues[PQ_FREE+i].cnt = &cnt.v_free_count;
117	}
118	vm_page_queues[PQ_INACTIVE].pl = &vm_page_queue_inactive;
119	vm_page_queues[PQ_INACTIVE].cnt = &cnt.v_inactive_count;
120
121	vm_page_queues[PQ_ACTIVE].pl = &vm_page_queue_active;
122	vm_page_queues[PQ_ACTIVE].cnt = &cnt.v_active_count;
123	for(i=0;i<PQ_L2_SIZE;i++) {
124		vm_page_queues[PQ_CACHE+i].pl = &vm_page_queue_cache[i];
125		vm_page_queues[PQ_CACHE+i].cnt = &cnt.v_cache_count;
126	}
127	for(i=PQ_FREE;i<PQ_COUNT;i++) {
128		if (vm_page_queues[i].pl) {
129			TAILQ_INIT(vm_page_queues[i].pl);
130		} else {
131			panic("vm_page_queue_init: queue %d is null", i);
132		}
133		vm_page_queues[i].lcnt = &pqcnt[i];
134	}
135}
136
137vm_page_t vm_page_array = 0;
138static int vm_page_array_size = 0;
139long first_page = 0;
140int vm_page_zero_count = 0;
141
142static __inline int vm_page_hash __P((vm_object_t object, vm_pindex_t pindex));
143static void vm_page_free_wakeup __P((void));
144
145/*
146 *	vm_set_page_size:
147 *
148 *	Sets the page size, perhaps based upon the memory
149 *	size.  Must be called before any use of page-size
150 *	dependent functions.
151 */
152void
153vm_set_page_size()
154{
155	if (cnt.v_page_size == 0)
156		cnt.v_page_size = PAGE_SIZE;
157	if (((cnt.v_page_size - 1) & cnt.v_page_size) != 0)
158		panic("vm_set_page_size: page size not a power of two");
159}
160
161/*
162 *	vm_page_startup:
163 *
164 *	Initializes the resident memory module.
165 *
166 *	Allocates memory for the page cells, and
167 *	for the object/offset-to-page hash table headers.
168 *	Each page cell is initialized and placed on the free list.
169 */
170
171vm_offset_t
172vm_page_startup(starta, enda, vaddr)
173	register vm_offset_t starta;
174	vm_offset_t enda;
175	register vm_offset_t vaddr;
176{
177	register vm_offset_t mapped;
178	register vm_page_t m;
179	register struct vm_page **bucket;
180	vm_size_t npages, page_range;
181	register vm_offset_t new_start;
182	int i;
183	vm_offset_t pa;
184	int nblocks;
185	vm_offset_t first_managed_page;
186
187	/* the biggest memory array is the second group of pages */
188	vm_offset_t start;
189	vm_offset_t biggestone, biggestsize;
190
191	vm_offset_t total;
192
193	total = 0;
194	biggestsize = 0;
195	biggestone = 0;
196	nblocks = 0;
197	vaddr = round_page(vaddr);
198
199	for (i = 0; phys_avail[i + 1]; i += 2) {
200		phys_avail[i] = round_page(phys_avail[i]);
201		phys_avail[i + 1] = trunc_page(phys_avail[i + 1]);
202	}
203
204	for (i = 0; phys_avail[i + 1]; i += 2) {
205		int size = phys_avail[i + 1] - phys_avail[i];
206
207		if (size > biggestsize) {
208			biggestone = i;
209			biggestsize = size;
210		}
211		++nblocks;
212		total += size;
213	}
214
215	start = phys_avail[biggestone];
216
217	/*
218	 * Initialize the queue headers for the free queue, the active queue
219	 * and the inactive queue.
220	 */
221
222	vm_page_queue_init();
223
224	/*
225	 * Allocate (and initialize) the hash table buckets.
226	 *
227	 * The number of buckets MUST BE a power of 2, and the actual value is
228	 * the next power of 2 greater than the number of physical pages in
229	 * the system.
230	 *
231	 * We make the hash table approximately 2x the number of pages to
232	 * reduce the chain length.  This is about the same size using the
233	 * singly-linked list as the 1x hash table we were using before
234	 * using TAILQ but the chain length will be smaller.
235	 *
236	 * Note: This computation can be tweaked if desired.
237	 */
238	vm_page_buckets = (struct vm_page **)vaddr;
239	bucket = vm_page_buckets;
240	if (vm_page_bucket_count == 0) {
241		vm_page_bucket_count = 1;
242		while (vm_page_bucket_count < atop(total))
243			vm_page_bucket_count <<= 1;
244	}
245	vm_page_bucket_count <<= 1;
246	vm_page_hash_mask = vm_page_bucket_count - 1;
247
248	/*
249	 * Validate these addresses.
250	 */
251
252	new_start = start + vm_page_bucket_count * sizeof(struct vm_page *);
253	new_start = round_page(new_start);
254	mapped = round_page(vaddr);
255	vaddr = pmap_map(mapped, start, new_start,
256	    VM_PROT_READ | VM_PROT_WRITE);
257	start = new_start;
258	vaddr = round_page(vaddr);
259	bzero((caddr_t) mapped, vaddr - mapped);
260
261	for (i = 0; i < vm_page_bucket_count; i++) {
262		*bucket = NULL;
263		bucket++;
264	}
265
266	/*
267	 * Compute the number of pages of memory that will be available for
268	 * use (taking into account the overhead of a page structure per
269	 * page).
270	 */
271
272	first_page = phys_avail[0] / PAGE_SIZE;
273
274	page_range = phys_avail[(nblocks - 1) * 2 + 1] / PAGE_SIZE - first_page;
275	npages = (total - (page_range * sizeof(struct vm_page)) -
276	    (start - phys_avail[biggestone])) / PAGE_SIZE;
277
278	/*
279	 * Initialize the mem entry structures now, and put them in the free
280	 * queue.
281	 */
282	vm_page_array = (vm_page_t) vaddr;
283	mapped = vaddr;
284
285	/*
286	 * Validate these addresses.
287	 */
288	new_start = round_page(start + page_range * sizeof(struct vm_page));
289	mapped = pmap_map(mapped, start, new_start,
290	    VM_PROT_READ | VM_PROT_WRITE);
291	start = new_start;
292
293	first_managed_page = start / PAGE_SIZE;
294
295	/*
296	 * Clear all of the page structures
297	 */
298	bzero((caddr_t) vm_page_array, page_range * sizeof(struct vm_page));
299	vm_page_array_size = page_range;
300
301	/*
302	 * Construct the free queue(s) in descending order (by physical
303	 * address) so that the first 16MB of physical memory is allocated
304	 * last rather than first.  On large-memory machines, this avoids
305	 * the exhaustion of low physical memory before isa_dmainit has run.
306	 */
307	cnt.v_page_count = 0;
308	cnt.v_free_count = 0;
309	for (i = 0; phys_avail[i + 1] && npages > 0; i += 2) {
310		if (i == biggestone)
311			pa = ptoa(first_managed_page);
312		else
313			pa = phys_avail[i];
314		while (pa < phys_avail[i + 1] && npages-- > 0) {
315			++cnt.v_page_count;
316			++cnt.v_free_count;
317			m = PHYS_TO_VM_PAGE(pa);
318			m->phys_addr = pa;
319			m->flags = 0;
320			m->pc = (pa >> PAGE_SHIFT) & PQ_L2_MASK;
321			m->queue = m->pc + PQ_FREE;
322			TAILQ_INSERT_HEAD(vm_page_queues[m->queue].pl, m, pageq);
323			++(*vm_page_queues[m->queue].lcnt);
324			pa += PAGE_SIZE;
325		}
326	}
327	return (mapped);
328}
329
330/*
331 *	vm_page_hash:
332 *
333 *	Distributes the object/offset key pair among hash buckets.
334 *
335 *	NOTE:  This macro depends on vm_page_bucket_count being a power of 2.
336 *	This routine may not block.
337 *
338 *	We try to randomize the hash based on the object to spread the pages
339 *	out in the hash table without it costing us too much.
340 */
341static __inline int
342vm_page_hash(object, pindex)
343	vm_object_t object;
344	vm_pindex_t pindex;
345{
346	int i = ((uintptr_t)object + pindex) ^ object->hash_rand;
347
348	return(i & vm_page_hash_mask);
349}
350
351/*
352 *	vm_page_insert:		[ internal use only ]
353 *
354 *	Inserts the given mem entry into the object and object list.
355 *
356 *	The pagetables are not updated but will presumably fault the page
357 *	in if necessary, or if a kernel page the caller will at some point
358 *	enter the page into the kernel's pmap.  We are not allowed to block
359 *	here so we *can't* do this anyway.
360 *
361 *	The object and page must be locked, and must be splhigh.
362 *	This routine may not block.
363 */
364
365void
366vm_page_insert(m, object, pindex)
367	register vm_page_t m;
368	register vm_object_t object;
369	register vm_pindex_t pindex;
370{
371	register struct vm_page **bucket;
372
373	if (m->object != NULL)
374		panic("vm_page_insert: already inserted");
375
376	/*
377	 * Record the object/offset pair in this page
378	 */
379
380	m->object = object;
381	m->pindex = pindex;
382
383	/*
384	 * Insert it into the object_object/offset hash table
385	 */
386
387	bucket = &vm_page_buckets[vm_page_hash(object, pindex)];
388	m->hnext = *bucket;
389	*bucket = m;
390	vm_page_bucket_generation++;
391
392	/*
393	 * Now link into the object's list of backed pages.
394	 */
395
396	TAILQ_INSERT_TAIL(&object->memq, m, listq);
397	object->generation++;
398
399	/*
400	 * show that the object has one more resident page.
401	 */
402
403	object->resident_page_count++;
404
405	/*
406	 * Since we are inserting a new and possibly dirty page,
407	 * update the object's OBJ_WRITEABLE and OBJ_MIGHTBEDIRTY flags.
408	 */
409	if (m->flags & PG_WRITEABLE)
410	    vm_object_set_flag(object, OBJ_WRITEABLE|OBJ_MIGHTBEDIRTY);
411}
412
413/*
414 *	vm_page_remove:
415 *				NOTE: used by device pager as well -wfj
416 *
417 *	Removes the given mem entry from the object/offset-page
418 *	table and the object page list, but do not invalidate/terminate
419 *	the backing store.
420 *
421 *	The object and page must be locked, and at splhigh.
422 *	The underlying pmap entry (if any) is NOT removed here.
423 *	This routine may not block.
424 */
425
426void
427vm_page_remove(m)
428	vm_page_t m;
429{
430	vm_object_t object;
431
432	if (m->object == NULL)
433		return;
434
435#if !defined(MAX_PERF)
436	if ((m->flags & PG_BUSY) == 0) {
437		panic("vm_page_remove: page not busy");
438	}
439#endif
440
441	/*
442	 * Basically destroy the page.
443	 */
444
445	vm_page_wakeup(m);
446
447	object = m->object;
448
449	/*
450	 * Remove from the object_object/offset hash table.  The object
451	 * must be on the hash queue, we will panic if it isn't
452	 *
453	 * Note: we must NULL-out m->hnext to prevent loops in detached
454	 * buffers with vm_page_lookup().
455	 */
456
457	{
458		struct vm_page **bucket;
459
460		bucket = &vm_page_buckets[vm_page_hash(m->object, m->pindex)];
461		while (*bucket != m) {
462#if !defined(MAX_PERF)
463			if (*bucket == NULL)
464				panic("vm_page_remove(): page not found in hash");
465#endif
466			bucket = &(*bucket)->hnext;
467		}
468		*bucket = m->hnext;
469		m->hnext = NULL;
470		vm_page_bucket_generation++;
471	}
472
473	/*
474	 * Now remove from the object's list of backed pages.
475	 */
476
477	TAILQ_REMOVE(&object->memq, m, listq);
478
479	/*
480	 * And show that the object has one fewer resident page.
481	 */
482
483	object->resident_page_count--;
484	object->generation++;
485
486	m->object = NULL;
487}
488
489/*
490 *	vm_page_lookup:
491 *
492 *	Returns the page associated with the object/offset
493 *	pair specified; if none is found, NULL is returned.
494 *
495 *	NOTE: the code below does not lock.  It will operate properly if
496 *	an interrupt makes a change, but the generation algorithm will not
497 *	operate properly in an SMP environment where both cpu's are able to run
498 *	kernel code simultaniously.
499 *
500 *	The object must be locked.  No side effects.
501 *	This routine may not block.
502 *	This is a critical path routine
503 */
504
505vm_page_t
506vm_page_lookup(object, pindex)
507	register vm_object_t object;
508	register vm_pindex_t pindex;
509{
510	register vm_page_t m;
511	register struct vm_page **bucket;
512	int generation;
513
514	/*
515	 * Search the hash table for this object/offset pair
516	 */
517
518retry:
519	generation = vm_page_bucket_generation;
520	bucket = &vm_page_buckets[vm_page_hash(object, pindex)];
521	for (m = *bucket; m != NULL; m = m->hnext) {
522		if ((m->object == object) && (m->pindex == pindex)) {
523			if (vm_page_bucket_generation != generation)
524				goto retry;
525			return (m);
526		}
527	}
528	if (vm_page_bucket_generation != generation)
529		goto retry;
530	return (NULL);
531}
532
533/*
534 *	vm_page_rename:
535 *
536 *	Move the given memory entry from its
537 *	current object to the specified target object/offset.
538 *
539 *	The object must be locked.
540 *	This routine may not block.
541 *
542 *	Note: this routine will raise itself to splvm(), the caller need not.
543 *
544 *	Note: swap associated with the page must be invalidated by the move.  We
545 *	      have to do this for several reasons:  (1) we aren't freeing the
546 *	      page, (2) we are dirtying the page, (3) the VM system is probably
547 *	      moving the page from object A to B, and will then later move
548 *	      the backing store from A to B and we can't have a conflict.
549 *
550 *	Note: we *always* dirty the page.  It is necessary both for the
551 *	      fact that we moved it, and because we may be invalidating
552 *	      swap.  If the page is on the cache, we have to deactivate it
553 *	      or vm_page_dirty() will panic.  Dirty pages are not allowed
554 *	      on the cache.
555 */
556
557void
558vm_page_rename(m, new_object, new_pindex)
559	register vm_page_t m;
560	register vm_object_t new_object;
561	vm_pindex_t new_pindex;
562{
563	int s;
564
565	s = splvm();
566	vm_page_remove(m);
567	vm_page_insert(m, new_object, new_pindex);
568	if (m->queue - m->pc == PQ_CACHE)
569		vm_page_deactivate(m);
570	vm_page_dirty(m);
571	splx(s);
572}
573
574/*
575 * vm_page_unqueue_nowakeup:
576 *
577 * 	vm_page_unqueue() without any wakeup
578 *
579 *	This routine must be called at splhigh().
580 *	This routine may not block.
581 */
582
583void
584vm_page_unqueue_nowakeup(m)
585	vm_page_t m;
586{
587	int queue = m->queue;
588	struct vpgqueues *pq;
589	if (queue != PQ_NONE) {
590		pq = &vm_page_queues[queue];
591		m->queue = PQ_NONE;
592		TAILQ_REMOVE(pq->pl, m, pageq);
593		(*pq->cnt)--;
594		(*pq->lcnt)--;
595	}
596}
597
598/*
599 * vm_page_unqueue:
600 *
601 *	Remove a page from its queue.
602 *
603 *	This routine must be called at splhigh().
604 *	This routine may not block.
605 */
606
607void
608vm_page_unqueue(m)
609	vm_page_t m;
610{
611	int queue = m->queue;
612	struct vpgqueues *pq;
613	if (queue != PQ_NONE) {
614		m->queue = PQ_NONE;
615		pq = &vm_page_queues[queue];
616		TAILQ_REMOVE(pq->pl, m, pageq);
617		(*pq->cnt)--;
618		(*pq->lcnt)--;
619		if ((queue - m->pc) == PQ_CACHE) {
620			if ((cnt.v_cache_count + cnt.v_free_count) <
621				(cnt.v_free_reserved + cnt.v_cache_min))
622				pagedaemon_wakeup();
623		}
624	}
625}
626
627#if PQ_L2_SIZE > 1
628
629/*
630 *	vm_page_list_find:
631 *
632 *	Find a page on the specified queue with color optimization.
633 *
634 *	The page coloring optimization attempts to locate a page
635 *	that does not overload other nearby pages in the object in
636 *	the cpu's L1 or L2 caches.  We need this optmization because
637 *	cpu caches tend to be physical caches, while object spaces tend
638 *	to be virtual.
639 *
640 *	This routine must be called at splvm().
641 *	This routine may not block.
642 *
643 *	This routine may only be called from the vm_page_list_find() macro
644 *	in vm_page.h
645 */
646vm_page_t
647_vm_page_list_find(basequeue, index)
648	int basequeue, index;
649{
650	int i;
651	vm_page_t m = NULL;
652	struct vpgqueues *pq;
653
654	pq = &vm_page_queues[basequeue];
655
656	/*
657	 * Note that for the first loop, index+i and index-i wind up at the
658	 * same place.  Even though this is not totally optimal, we've already
659	 * blown it by missing the cache case so we do not care.
660	 */
661
662	for(i = PQ_L2_SIZE / 2; i > 0; --i) {
663		if ((m = TAILQ_FIRST(pq[(index + i) & PQ_L2_MASK].pl)) != NULL)
664			break;
665
666		if ((m = TAILQ_FIRST(pq[(index - i) & PQ_L2_MASK].pl)) != NULL)
667			break;
668	}
669	return(m);
670}
671
672#endif
673
674/*
675 *	vm_page_select_cache:
676 *
677 *	Find a page on the cache queue with color optimization.  As pages
678 *	might be found, but not applicable, they are deactivated.  This
679 *	keeps us from using potentially busy cached pages.
680 *
681 *	This routine must be called at splvm().
682 *	This routine may not block.
683 */
684vm_page_t
685vm_page_select_cache(object, pindex)
686	vm_object_t object;
687	vm_pindex_t pindex;
688{
689	vm_page_t m;
690
691	while (TRUE) {
692		m = vm_page_list_find(
693		    PQ_CACHE,
694		    (pindex + object->pg_color) & PQ_L2_MASK,
695		    FALSE
696		);
697		if (m && ((m->flags & PG_BUSY) || m->busy ||
698			       m->hold_count || m->wire_count)) {
699			vm_page_deactivate(m);
700			continue;
701		}
702		return m;
703	}
704}
705
706/*
707 *	vm_page_select_free:
708 *
709 *	Find a free or zero page, with specified preference.  We attempt to
710 *	inline the nominal case and fall back to _vm_page_select_free()
711 *	otherwise.
712 *
713 *	This routine must be called at splvm().
714 *	This routine may not block.
715 */
716
717static __inline vm_page_t
718vm_page_select_free(vm_object_t object, vm_pindex_t pindex, boolean_t prefer_zero)
719{
720	vm_page_t m;
721
722	m = vm_page_list_find(
723		PQ_FREE,
724		(pindex + object->pg_color) & PQ_L2_MASK,
725		prefer_zero
726	);
727	return(m);
728}
729
730/*
731 *	vm_page_alloc:
732 *
733 *	Allocate and return a memory cell associated
734 *	with this VM object/offset pair.
735 *
736 *	page_req classes:
737 *	VM_ALLOC_NORMAL		normal process request
738 *	VM_ALLOC_SYSTEM		system *really* needs a page
739 *	VM_ALLOC_INTERRUPT	interrupt time request
740 *	VM_ALLOC_ZERO		zero page
741 *
742 *	Object must be locked.
743 *	This routine may not block.
744 *
745 *	Additional special handling is required when called from an
746 *	interrupt (VM_ALLOC_INTERRUPT).  We are not allowed to mess with
747 *	the page cache in this case.
748 */
749
750vm_page_t
751vm_page_alloc(object, pindex, page_req)
752	vm_object_t object;
753	vm_pindex_t pindex;
754	int page_req;
755{
756	register vm_page_t m = NULL;
757	int s;
758
759	KASSERT(!vm_page_lookup(object, pindex),
760		("vm_page_alloc: page already allocated"));
761
762	/*
763	 * The pager is allowed to eat deeper into the free page list.
764	 */
765
766	if ((curproc == pageproc) && (page_req != VM_ALLOC_INTERRUPT)) {
767		page_req = VM_ALLOC_SYSTEM;
768	};
769
770	s = splvm();
771
772loop:
773	if (cnt.v_free_count > cnt.v_free_reserved) {
774		/*
775		 * Allocate from the free queue if there are plenty of pages
776		 * in it.
777		 */
778		if (page_req == VM_ALLOC_ZERO)
779			m = vm_page_select_free(object, pindex, TRUE);
780		else
781			m = vm_page_select_free(object, pindex, FALSE);
782	} else if (
783	    (page_req == VM_ALLOC_SYSTEM &&
784	     cnt.v_cache_count == 0 &&
785	     cnt.v_free_count > cnt.v_interrupt_free_min) ||
786	    (page_req == VM_ALLOC_INTERRUPT && cnt.v_free_count > 0)
787	) {
788		/*
789		 * Interrupt or system, dig deeper into the free list.
790		 */
791		m = vm_page_select_free(object, pindex, FALSE);
792	} else if (page_req != VM_ALLOC_INTERRUPT) {
793		/*
794		 * Allocateable from cache (non-interrupt only).  On success,
795		 * we must free the page and try again, thus ensuring that
796		 * cnt.v_*_free_min counters are replenished.
797		 */
798		m = vm_page_select_cache(object, pindex);
799		if (m == NULL) {
800			splx(s);
801#if defined(DIAGNOSTIC)
802			if (cnt.v_cache_count > 0)
803				printf("vm_page_alloc(NORMAL): missing pages on cache queue: %d\n", cnt.v_cache_count);
804#endif
805			vm_pageout_deficit++;
806			pagedaemon_wakeup();
807			return (NULL);
808		}
809		KASSERT(m->dirty == 0, ("Found dirty cache page %p", m));
810		vm_page_busy(m);
811		vm_page_protect(m, VM_PROT_NONE);
812		vm_page_free(m);
813		goto loop;
814	} else {
815		/*
816		 * Not allocateable from cache from interrupt, give up.
817		 */
818		splx(s);
819		vm_pageout_deficit++;
820		pagedaemon_wakeup();
821		return (NULL);
822	}
823
824	/*
825	 *  At this point we had better have found a good page.
826	 */
827
828	KASSERT(
829	    m != NULL,
830	    ("vm_page_alloc(): missing page on free queue\n")
831	);
832
833	/*
834	 * Remove from free queue
835	 */
836
837	{
838		struct vpgqueues *pq = &vm_page_queues[m->queue];
839
840		TAILQ_REMOVE(pq->pl, m, pageq);
841		(*pq->cnt)--;
842		(*pq->lcnt)--;
843	}
844
845	/*
846	 * Initialize structure.  Only the PG_ZERO flag is inherited.
847	 */
848
849	if (m->flags & PG_ZERO) {
850		vm_page_zero_count--;
851		m->flags = PG_ZERO | PG_BUSY;
852	} else {
853		m->flags = PG_BUSY;
854	}
855	m->wire_count = 0;
856	m->hold_count = 0;
857	m->act_count = 0;
858	m->busy = 0;
859	m->valid = 0;
860	m->dirty = 0;
861	m->queue = PQ_NONE;
862
863	/*
864	 * vm_page_insert() is safe prior to the splx().  Note also that
865	 * inserting a page here does not insert it into the pmap (which
866	 * could cause us to block allocating memory).  We cannot block
867	 * anywhere.
868	 */
869
870	vm_page_insert(m, object, pindex);
871
872	/*
873	 * Don't wakeup too often - wakeup the pageout daemon when
874	 * we would be nearly out of memory.
875	 */
876	if (((cnt.v_free_count + cnt.v_cache_count) <
877		(cnt.v_free_reserved + cnt.v_cache_min)) ||
878			(cnt.v_free_count < cnt.v_pageout_free_min))
879		pagedaemon_wakeup();
880
881	splx(s);
882
883	return (m);
884}
885
886/*
887 *	vm_wait:	(also see VM_WAIT macro)
888 *
889 *	Block until free pages are available for allocation
890 */
891
892void
893vm_wait()
894{
895	int s;
896
897	s = splvm();
898	if (curproc == pageproc) {
899		vm_pageout_pages_needed = 1;
900		tsleep(&vm_pageout_pages_needed, PSWP, "vmwait", 0);
901	} else {
902		if (!vm_pages_needed) {
903			vm_pages_needed++;
904			wakeup(&vm_pages_needed);
905		}
906		tsleep(&cnt.v_free_count, PVM, "vmwait", 0);
907	}
908	splx(s);
909}
910
911/*
912 *	vm_await:	(also see VM_AWAIT macro)
913 *
914 *	asleep on an event that will signal when free pages are available
915 *	for allocation.
916 */
917
918void
919vm_await()
920{
921	int s;
922
923	s = splvm();
924	if (curproc == pageproc) {
925		vm_pageout_pages_needed = 1;
926		asleep(&vm_pageout_pages_needed, PSWP, "vmwait", 0);
927	} else {
928		if (!vm_pages_needed) {
929			vm_pages_needed++;
930			wakeup(&vm_pages_needed);
931		}
932		asleep(&cnt.v_free_count, PVM, "vmwait", 0);
933	}
934	splx(s);
935}
936
937#if 0
938/*
939 *	vm_page_sleep:
940 *
941 *	Block until page is no longer busy.
942 */
943
944int
945vm_page_sleep(vm_page_t m, char *msg, char *busy) {
946	int slept = 0;
947	if ((busy && *busy) || (m->flags & PG_BUSY)) {
948		int s;
949		s = splvm();
950		if ((busy && *busy) || (m->flags & PG_BUSY)) {
951			vm_page_flag_set(m, PG_WANTED);
952			tsleep(m, PVM, msg, 0);
953			slept = 1;
954		}
955		splx(s);
956	}
957	return slept;
958}
959
960#endif
961
962#if 0
963
964/*
965 *	vm_page_asleep:
966 *
967 *	Similar to vm_page_sleep(), but does not block.  Returns 0 if
968 *	the page is not busy, or 1 if the page is busy.
969 *
970 *	This routine has the side effect of calling asleep() if the page
971 *	was busy (1 returned).
972 */
973
974int
975vm_page_asleep(vm_page_t m, char *msg, char *busy) {
976	int slept = 0;
977	if ((busy && *busy) || (m->flags & PG_BUSY)) {
978		int s;
979		s = splvm();
980		if ((busy && *busy) || (m->flags & PG_BUSY)) {
981			vm_page_flag_set(m, PG_WANTED);
982			asleep(m, PVM, msg, 0);
983			slept = 1;
984		}
985		splx(s);
986	}
987	return slept;
988}
989
990#endif
991
992/*
993 *	vm_page_activate:
994 *
995 *	Put the specified page on the active list (if appropriate).
996 *
997 *	The page queues must be locked.
998 *	This routine may not block.
999 */
1000void
1001vm_page_activate(m)
1002	register vm_page_t m;
1003{
1004	int s;
1005
1006	s = splvm();
1007	if (m->queue != PQ_ACTIVE) {
1008		if ((m->queue - m->pc) == PQ_CACHE)
1009			cnt.v_reactivated++;
1010
1011		vm_page_unqueue(m);
1012
1013		if (m->wire_count == 0) {
1014			m->queue = PQ_ACTIVE;
1015			++(*vm_page_queues[PQ_ACTIVE].lcnt);
1016			TAILQ_INSERT_TAIL(&vm_page_queue_active, m, pageq);
1017			if (m->act_count < ACT_INIT)
1018				m->act_count = ACT_INIT;
1019			cnt.v_active_count++;
1020		}
1021	} else {
1022		if (m->act_count < ACT_INIT)
1023			m->act_count = ACT_INIT;
1024	}
1025
1026	splx(s);
1027}
1028
1029/*
1030 *	vm_page_free_wakeup:
1031 *
1032 *	Helper routine for vm_page_free_toq() and vm_page_cache().  This
1033 *	routine is called when a page has been added to the cache or free
1034 *	queues.
1035 *
1036 *	This routine may not block.
1037 *	This routine must be called at splvm()
1038 */
1039static __inline void
1040vm_page_free_wakeup()
1041{
1042	/*
1043	 * if pageout daemon needs pages, then tell it that there are
1044	 * some free.
1045	 */
1046	if (vm_pageout_pages_needed) {
1047		wakeup(&vm_pageout_pages_needed);
1048		vm_pageout_pages_needed = 0;
1049	}
1050	/*
1051	 * wakeup processes that are waiting on memory if we hit a
1052	 * high water mark. And wakeup scheduler process if we have
1053	 * lots of memory. this process will swapin processes.
1054	 */
1055	if (vm_pages_needed &&
1056		((cnt.v_free_count + cnt.v_cache_count) >= cnt.v_free_min)) {
1057		wakeup(&cnt.v_free_count);
1058		vm_pages_needed = 0;
1059	}
1060}
1061
1062/*
1063 *	vm_page_free_toq:
1064 *
1065 *	Returns the given page to the PQ_FREE or PQ_ZERO list,
1066 *	disassociating it with any VM object.
1067 *
1068 *	Object and page must be locked prior to entry.
1069 *	This routine may not block.
1070 */
1071
1072void
1073vm_page_free_toq(vm_page_t m)
1074{
1075	int s;
1076	struct vpgqueues *pq;
1077	vm_object_t object = m->object;
1078
1079	s = splvm();
1080
1081	cnt.v_tfree++;
1082
1083#if !defined(MAX_PERF)
1084	if (m->busy || ((m->queue - m->pc) == PQ_FREE) ||
1085		(m->hold_count != 0)) {
1086		printf(
1087		"vm_page_free: pindex(%lu), busy(%d), PG_BUSY(%d), hold(%d)\n",
1088		    (u_long)m->pindex, m->busy, (m->flags & PG_BUSY) ? 1 : 0,
1089		    m->hold_count);
1090		if ((m->queue - m->pc) == PQ_FREE)
1091			panic("vm_page_free: freeing free page");
1092		else
1093			panic("vm_page_free: freeing busy page");
1094	}
1095#endif
1096
1097	/*
1098	 * unqueue, then remove page.  Note that we cannot destroy
1099	 * the page here because we do not want to call the pager's
1100	 * callback routine until after we've put the page on the
1101	 * appropriate free queue.
1102	 */
1103
1104	vm_page_unqueue_nowakeup(m);
1105	vm_page_remove(m);
1106
1107	/*
1108	 * If fictitious remove object association and
1109	 * return, otherwise delay object association removal.
1110	 */
1111
1112	if ((m->flags & PG_FICTITIOUS) != 0) {
1113		splx(s);
1114		return;
1115	}
1116
1117	m->valid = 0;
1118
1119	if (m->wire_count != 0) {
1120#if !defined(MAX_PERF)
1121		if (m->wire_count > 1) {
1122			panic("vm_page_free: invalid wire count (%d), pindex: 0x%lx",
1123				m->wire_count, (long)m->pindex);
1124		}
1125#endif
1126		printf("vm_page_free: freeing wired page\n");
1127		m->wire_count = 0;
1128		cnt.v_wire_count--;
1129	}
1130
1131	/*
1132	 * If we've exhausted the object's resident pages we want to free
1133	 * it up.
1134	 */
1135
1136	if (object &&
1137	    (object->type == OBJT_VNODE) &&
1138	    ((object->flags & OBJ_DEAD) == 0)
1139	) {
1140		struct vnode *vp = (struct vnode *)object->handle;
1141
1142		if (vp && VSHOULDFREE(vp)) {
1143			if ((vp->v_flag & (VTBFREE|VDOOMED|VFREE)) == 0) {
1144				TAILQ_INSERT_TAIL(&vnode_tobefree_list, vp, v_freelist);
1145				vp->v_flag |= VTBFREE;
1146			}
1147		}
1148	}
1149
1150#ifdef __alpha__
1151	pmap_page_is_free(m);
1152#endif
1153
1154	m->queue = PQ_FREE + m->pc;
1155	pq = &vm_page_queues[m->queue];
1156	++(*pq->lcnt);
1157	++(*pq->cnt);
1158
1159	/*
1160	 * Put zero'd pages on the end ( where we look for zero'd pages
1161	 * first ) and non-zerod pages at the head.
1162	 */
1163
1164	if (m->flags & PG_ZERO) {
1165		TAILQ_INSERT_TAIL(pq->pl, m, pageq);
1166		++vm_page_zero_count;
1167	} else if (curproc == pageproc) {
1168		/*
1169		 * If the pageout daemon is freeing pages, the pages are
1170		 * likely to NOT be in the L1 or L2 caches due to their age.
1171		 * For now we do not try to do anything special with this
1172		 * info.
1173		 */
1174		TAILQ_INSERT_HEAD(pq->pl, m, pageq);
1175	} else {
1176		TAILQ_INSERT_HEAD(pq->pl, m, pageq);
1177	}
1178
1179	vm_page_free_wakeup();
1180
1181	splx(s);
1182}
1183
1184/*
1185 *	vm_page_wire:
1186 *
1187 *	Mark this page as wired down by yet
1188 *	another map, removing it from paging queues
1189 *	as necessary.
1190 *
1191 *	The page queues must be locked.
1192 *	This routine may not block.
1193 */
1194void
1195vm_page_wire(m)
1196	register vm_page_t m;
1197{
1198	int s;
1199
1200	s = splvm();
1201	if (m->wire_count == 0) {
1202		vm_page_unqueue(m);
1203		cnt.v_wire_count++;
1204	}
1205	m->wire_count++;
1206	splx(s);
1207	vm_page_flag_set(m, PG_MAPPED);
1208}
1209
1210/*
1211 *	vm_page_unwire:
1212 *
1213 *	Release one wiring of this page, potentially
1214 *	enabling it to be paged again.
1215 *
1216 *	Many pages placed on the inactive queue should actually go
1217 *	into the cache, but it is difficult to figure out which.  What
1218 *	we do instead, if the inactive target is well met, is to put
1219 *	clean pages at the head of the inactive queue instead of the tail.
1220 *	This will cause them to be moved to the cache more quickly and
1221 *	if not actively re-referenced, freed more quickly.  If we just
1222 *	stick these pages at the end of the inactive queue, heavy filesystem
1223 *	meta-data accesses can cause an unnecessary paging load on memory bound
1224 *	processes.  This optimization causes one-time-use metadata to be
1225 *	reused more quickly.
1226 *
1227 *	A number of routines use vm_page_unwire() to guarentee that the page
1228 *	will go into either the inactive or active queues, and will NEVER
1229 *	be placed in the cache - for example, just after dirtying a page.
1230 *	dirty pages in the cache are not allowed.
1231 *
1232 *	The page queues must be locked.
1233 *	This routine may not block.
1234 */
1235void
1236vm_page_unwire(m, activate)
1237	register vm_page_t m;
1238	int activate;
1239{
1240	int s;
1241
1242	s = splvm();
1243
1244	if (m->wire_count > 0) {
1245		m->wire_count--;
1246		if (m->wire_count == 0) {
1247			cnt.v_wire_count--;
1248			if (activate) {
1249				TAILQ_INSERT_TAIL(&vm_page_queue_active, m, pageq);
1250				m->queue = PQ_ACTIVE;
1251				(*vm_page_queues[PQ_ACTIVE].lcnt)++;
1252				cnt.v_active_count++;
1253			} else {
1254				TAILQ_INSERT_TAIL(&vm_page_queue_inactive, m, pageq);
1255				m->queue = PQ_INACTIVE;
1256				(*vm_page_queues[PQ_INACTIVE].lcnt)++;
1257				cnt.v_inactive_count++;
1258			}
1259		}
1260	} else {
1261#if !defined(MAX_PERF)
1262		panic("vm_page_unwire: invalid wire count: %d\n", m->wire_count);
1263#endif
1264	}
1265	splx(s);
1266}
1267
1268
1269/*
1270 * Move the specified page to the inactive queue.  If the page has
1271 * any associated swap, the swap is deallocated.
1272 *
1273 * This routine may not block.
1274 */
1275void
1276vm_page_deactivate(m)
1277	register vm_page_t m;
1278{
1279	int s;
1280
1281	/*
1282	 * Ignore if already inactive.
1283	 */
1284	if (m->queue == PQ_INACTIVE)
1285		return;
1286
1287	s = splvm();
1288	if (m->wire_count == 0) {
1289		if ((m->queue - m->pc) == PQ_CACHE)
1290			cnt.v_reactivated++;
1291		vm_page_unqueue(m);
1292		TAILQ_INSERT_TAIL(&vm_page_queue_inactive, m, pageq);
1293		m->queue = PQ_INACTIVE;
1294		++(*vm_page_queues[PQ_INACTIVE].lcnt);
1295		cnt.v_inactive_count++;
1296	}
1297	splx(s);
1298}
1299
1300/*
1301 * vm_page_cache
1302 *
1303 * Put the specified page onto the page cache queue (if appropriate).
1304 *
1305 * This routine may not block.
1306 */
1307void
1308vm_page_cache(m)
1309	register vm_page_t m;
1310{
1311	int s;
1312
1313#if !defined(MAX_PERF)
1314	if ((m->flags & PG_BUSY) || m->busy || m->wire_count) {
1315		printf("vm_page_cache: attempting to cache busy page\n");
1316		return;
1317	}
1318#endif
1319	if ((m->queue - m->pc) == PQ_CACHE)
1320		return;
1321
1322	/*
1323	 * Remove all pmaps and indicate that the page is not
1324	 * writeable or mapped.
1325	 */
1326
1327	vm_page_protect(m, VM_PROT_NONE);
1328#if !defined(MAX_PERF)
1329	if (m->dirty != 0) {
1330		panic("vm_page_cache: caching a dirty page, pindex: %ld",
1331			(long)m->pindex);
1332	}
1333#endif
1334	s = splvm();
1335	vm_page_unqueue_nowakeup(m);
1336	m->queue = PQ_CACHE + m->pc;
1337	(*vm_page_queues[m->queue].lcnt)++;
1338	TAILQ_INSERT_TAIL(vm_page_queues[m->queue].pl, m, pageq);
1339	cnt.v_cache_count++;
1340	vm_page_free_wakeup();
1341	splx(s);
1342}
1343
1344/*
1345 * Grab a page, waiting until we are waken up due to the page
1346 * changing state.  We keep on waiting, if the page continues
1347 * to be in the object.  If the page doesn't exist, allocate it.
1348 *
1349 * This routine may block.
1350 */
1351vm_page_t
1352vm_page_grab(object, pindex, allocflags)
1353	vm_object_t object;
1354	vm_pindex_t pindex;
1355	int allocflags;
1356{
1357
1358	vm_page_t m;
1359	int s, generation;
1360
1361retrylookup:
1362	if ((m = vm_page_lookup(object, pindex)) != NULL) {
1363		if (m->busy || (m->flags & PG_BUSY)) {
1364			generation = object->generation;
1365
1366			s = splvm();
1367			while ((object->generation == generation) &&
1368					(m->busy || (m->flags & PG_BUSY))) {
1369				vm_page_flag_set(m, PG_WANTED | PG_REFERENCED);
1370				tsleep(m, PVM, "pgrbwt", 0);
1371				if ((allocflags & VM_ALLOC_RETRY) == 0) {
1372					splx(s);
1373					return NULL;
1374				}
1375			}
1376			splx(s);
1377			goto retrylookup;
1378		} else {
1379			vm_page_busy(m);
1380			return m;
1381		}
1382	}
1383
1384	m = vm_page_alloc(object, pindex, allocflags & ~VM_ALLOC_RETRY);
1385	if (m == NULL) {
1386		VM_WAIT;
1387		if ((allocflags & VM_ALLOC_RETRY) == 0)
1388			return NULL;
1389		goto retrylookup;
1390	}
1391
1392	return m;
1393}
1394
1395/*
1396 * Mapping function for valid bits or for dirty bits in
1397 * a page.  May not block.
1398 *
1399 * Inputs are required to range within a page.
1400 */
1401
1402__inline int
1403vm_page_bits(int base, int size)
1404{
1405	int first_bit;
1406	int last_bit;
1407
1408	KASSERT(
1409	    base + size <= PAGE_SIZE,
1410	    ("vm_page_bits: illegal base/size %d/%d", base, size)
1411	);
1412
1413	if (size == 0)		/* handle degenerate case */
1414		return(0);
1415
1416	first_bit = base >> DEV_BSHIFT;
1417	last_bit = (base + size - 1) >> DEV_BSHIFT;
1418
1419	return ((2 << last_bit) - (1 << first_bit));
1420}
1421
1422/*
1423 *	vm_page_set_validclean:
1424 *
1425 *	Sets portions of a page valid and clean.  The arguments are expected
1426 *	to be DEV_BSIZE aligned but if they aren't the bitmap is inclusive
1427 *	of any partial chunks touched by the range.  The invalid portion of
1428 *	such chunks will be zero'd.
1429 *
1430 *	This routine may not block.
1431 *
1432 *	(base + size) must be less then or equal to PAGE_SIZE.
1433 */
1434void
1435vm_page_set_validclean(m, base, size)
1436	vm_page_t m;
1437	int base;
1438	int size;
1439{
1440	int pagebits;
1441	int frag;
1442	int endoff;
1443
1444	if (size == 0)	/* handle degenerate case */
1445		return;
1446
1447	/*
1448	 * If the base is not DEV_BSIZE aligned and the valid
1449	 * bit is clear, we have to zero out a portion of the
1450	 * first block.
1451	 */
1452
1453	if ((frag = base & ~(DEV_BSIZE - 1)) != base &&
1454	    (m->valid & (1 << (base >> DEV_BSHIFT))) == 0
1455	) {
1456		pmap_zero_page_area(
1457		    VM_PAGE_TO_PHYS(m),
1458		    frag,
1459		    base - frag
1460		);
1461	}
1462
1463	/*
1464	 * If the ending offset is not DEV_BSIZE aligned and the
1465	 * valid bit is clear, we have to zero out a portion of
1466	 * the last block.
1467	 */
1468
1469	endoff = base + size;
1470
1471	if ((frag = endoff & ~(DEV_BSIZE - 1)) != endoff &&
1472	    (m->valid & (1 << (endoff >> DEV_BSHIFT))) == 0
1473	) {
1474		pmap_zero_page_area(
1475		    VM_PAGE_TO_PHYS(m),
1476		    endoff,
1477		    DEV_BSIZE - (endoff & (DEV_BSIZE - 1))
1478		);
1479	}
1480
1481	/*
1482	 * Set valid, clear dirty bits.  If validating the entire
1483	 * page we can safely clear the pmap modify bit.
1484	 */
1485
1486	pagebits = vm_page_bits(base, size);
1487	m->valid |= pagebits;
1488	m->dirty &= ~pagebits;
1489
1490	if (base == 0 && size == PAGE_SIZE)
1491		pmap_clear_modify(VM_PAGE_TO_PHYS(m));
1492}
1493
1494#if 0
1495
1496void
1497vm_page_set_dirty(m, base, size)
1498	vm_page_t m;
1499	int base;
1500	int size;
1501{
1502	m->dirty |= vm_page_bits(base, size);
1503}
1504
1505#endif
1506
1507void
1508vm_page_clear_dirty(m, base, size)
1509	vm_page_t m;
1510	int base;
1511	int size;
1512{
1513	m->dirty &= ~vm_page_bits(base, size);
1514}
1515
1516/*
1517 *	vm_page_set_invalid:
1518 *
1519 *	Invalidates DEV_BSIZE'd chunks within a page.  Both the
1520 *	valid and dirty bits for the effected areas are cleared.
1521 *
1522 *	May not block.
1523 */
1524void
1525vm_page_set_invalid(m, base, size)
1526	vm_page_t m;
1527	int base;
1528	int size;
1529{
1530	int bits;
1531
1532	bits = vm_page_bits(base, size);
1533	m->valid &= ~bits;
1534	m->dirty &= ~bits;
1535	m->object->generation++;
1536}
1537
1538/*
1539 * vm_page_zero_invalid()
1540 *
1541 *	The kernel assumes that the invalid portions of a page contain
1542 *	garbage, but such pages can be mapped into memory by user code.
1543 *	When this occurs, we must zero out the non-valid portions of the
1544 *	page so user code sees what it expects.
1545 *
1546 *	Pages are most often semi-valid when the end of a file is mapped
1547 *	into memory and the file's size is not page aligned.
1548 */
1549
1550void
1551vm_page_zero_invalid(vm_page_t m, boolean_t setvalid)
1552{
1553	int b;
1554	int i;
1555
1556	/*
1557	 * Scan the valid bits looking for invalid sections that
1558	 * must be zerod.  Invalid sub-DEV_BSIZE'd areas ( where the
1559	 * valid bit may be set ) have already been zerod by
1560	 * vm_page_set_validclean().
1561	 */
1562
1563	for (b = i = 0; i <= PAGE_SIZE / DEV_BSIZE; ++i) {
1564		if (i == (PAGE_SIZE / DEV_BSIZE) ||
1565		    (m->valid & (1 << i))
1566		) {
1567			if (i > b) {
1568				pmap_zero_page_area(
1569				    VM_PAGE_TO_PHYS(m),
1570				    b << DEV_BSHIFT,
1571				    (i - b) << DEV_BSHIFT
1572				);
1573			}
1574			b = i + 1;
1575		}
1576	}
1577
1578	/*
1579	 * setvalid is TRUE when we can safely set the zero'd areas
1580	 * as being valid.  We can do this if there are no cache consistancy
1581	 * issues.  e.g. it is ok to do with UFS, but not ok to do with NFS.
1582	 */
1583
1584	if (setvalid)
1585		m->valid = VM_PAGE_BITS_ALL;
1586}
1587
1588/*
1589 *	vm_page_is_valid:
1590 *
1591 *	Is (partial) page valid?  Note that the case where size == 0
1592 *	will return FALSE in the degenerate case where the page is
1593 *	entirely invalid, and TRUE otherwise.
1594 *
1595 *	May not block.
1596 */
1597
1598int
1599vm_page_is_valid(m, base, size)
1600	vm_page_t m;
1601	int base;
1602	int size;
1603{
1604	int bits = vm_page_bits(base, size);
1605
1606	if (m->valid && ((m->valid & bits) == bits))
1607		return 1;
1608	else
1609		return 0;
1610}
1611
1612/*
1613 * update dirty bits from pmap/mmu.  May not block.
1614 */
1615
1616void
1617vm_page_test_dirty(m)
1618	vm_page_t m;
1619{
1620	if ((m->dirty != VM_PAGE_BITS_ALL) &&
1621	    pmap_is_modified(VM_PAGE_TO_PHYS(m))) {
1622		vm_page_dirty(m);
1623	}
1624}
1625
1626/*
1627 * This interface is for merging with malloc() someday.
1628 * Even if we never implement compaction so that contiguous allocation
1629 * works after initialization time, malloc()'s data structures are good
1630 * for statistics and for allocations of less than a page.
1631 */
1632void *
1633contigmalloc1(size, type, flags, low, high, alignment, boundary, map)
1634	unsigned long size;	/* should be size_t here and for malloc() */
1635	struct malloc_type *type;
1636	int flags;
1637	unsigned long low;
1638	unsigned long high;
1639	unsigned long alignment;
1640	unsigned long boundary;
1641	vm_map_t map;
1642{
1643	int i, s, start;
1644	vm_offset_t addr, phys, tmp_addr;
1645	int pass;
1646	vm_page_t pga = vm_page_array;
1647
1648	size = round_page(size);
1649#if !defined(MAX_PERF)
1650	if (size == 0)
1651		panic("contigmalloc1: size must not be 0");
1652	if ((alignment & (alignment - 1)) != 0)
1653		panic("contigmalloc1: alignment must be a power of 2");
1654	if ((boundary & (boundary - 1)) != 0)
1655		panic("contigmalloc1: boundary must be a power of 2");
1656#endif
1657
1658	start = 0;
1659	for (pass = 0; pass <= 1; pass++) {
1660		s = splvm();
1661again:
1662		/*
1663		 * Find first page in array that is free, within range, aligned, and
1664		 * such that the boundary won't be crossed.
1665		 */
1666		for (i = start; i < cnt.v_page_count; i++) {
1667			int pqtype;
1668			phys = VM_PAGE_TO_PHYS(&pga[i]);
1669			pqtype = pga[i].queue - pga[i].pc;
1670			if (((pqtype == PQ_FREE) || (pqtype == PQ_CACHE)) &&
1671			    (phys >= low) && (phys < high) &&
1672			    ((phys & (alignment - 1)) == 0) &&
1673			    (((phys ^ (phys + size - 1)) & ~(boundary - 1)) == 0))
1674				break;
1675		}
1676
1677		/*
1678		 * If the above failed or we will exceed the upper bound, fail.
1679		 */
1680		if ((i == cnt.v_page_count) ||
1681			((VM_PAGE_TO_PHYS(&pga[i]) + size) > high)) {
1682			vm_page_t m, next;
1683
1684again1:
1685			for (m = TAILQ_FIRST(&vm_page_queue_inactive);
1686				m != NULL;
1687				m = next) {
1688
1689				if (m->queue != PQ_INACTIVE) {
1690					break;
1691				}
1692
1693				next = TAILQ_NEXT(m, pageq);
1694				if (vm_page_sleep_busy(m, TRUE, "vpctw0"))
1695					goto again1;
1696				vm_page_test_dirty(m);
1697				if (m->dirty) {
1698					if (m->object->type == OBJT_VNODE) {
1699						vn_lock(m->object->handle, LK_EXCLUSIVE | LK_RETRY, curproc);
1700						vm_object_page_clean(m->object, 0, 0, OBJPC_SYNC);
1701						VOP_UNLOCK(m->object->handle, 0, curproc);
1702						goto again1;
1703					} else if (m->object->type == OBJT_SWAP ||
1704								m->object->type == OBJT_DEFAULT) {
1705						vm_pageout_flush(&m, 1, 0);
1706						goto again1;
1707					}
1708				}
1709				if ((m->dirty == 0) && (m->busy == 0) && (m->hold_count == 0))
1710					vm_page_cache(m);
1711			}
1712
1713			for (m = TAILQ_FIRST(&vm_page_queue_active);
1714				m != NULL;
1715				m = next) {
1716
1717				if (m->queue != PQ_ACTIVE) {
1718					break;
1719				}
1720
1721				next = TAILQ_NEXT(m, pageq);
1722				if (vm_page_sleep_busy(m, TRUE, "vpctw1"))
1723					goto again1;
1724				vm_page_test_dirty(m);
1725				if (m->dirty) {
1726					if (m->object->type == OBJT_VNODE) {
1727						vn_lock(m->object->handle, LK_EXCLUSIVE | LK_RETRY, curproc);
1728						vm_object_page_clean(m->object, 0, 0, OBJPC_SYNC);
1729						VOP_UNLOCK(m->object->handle, 0, curproc);
1730						goto again1;
1731					} else if (m->object->type == OBJT_SWAP ||
1732								m->object->type == OBJT_DEFAULT) {
1733						vm_pageout_flush(&m, 1, 0);
1734						goto again1;
1735					}
1736				}
1737				if ((m->dirty == 0) && (m->busy == 0) && (m->hold_count == 0))
1738					vm_page_cache(m);
1739			}
1740
1741			splx(s);
1742			continue;
1743		}
1744		start = i;
1745
1746		/*
1747		 * Check successive pages for contiguous and free.
1748		 */
1749		for (i = start + 1; i < (start + size / PAGE_SIZE); i++) {
1750			int pqtype;
1751			pqtype = pga[i].queue - pga[i].pc;
1752			if ((VM_PAGE_TO_PHYS(&pga[i]) !=
1753			    (VM_PAGE_TO_PHYS(&pga[i - 1]) + PAGE_SIZE)) ||
1754			    ((pqtype != PQ_FREE) && (pqtype != PQ_CACHE))) {
1755				start++;
1756				goto again;
1757			}
1758		}
1759
1760		for (i = start; i < (start + size / PAGE_SIZE); i++) {
1761			int pqtype;
1762			vm_page_t m = &pga[i];
1763
1764			pqtype = m->queue - m->pc;
1765			if (pqtype == PQ_CACHE) {
1766				vm_page_busy(m);
1767				vm_page_free(m);
1768			}
1769
1770			TAILQ_REMOVE(vm_page_queues[m->queue].pl, m, pageq);
1771			(*vm_page_queues[m->queue].lcnt)--;
1772			cnt.v_free_count--;
1773			m->valid = VM_PAGE_BITS_ALL;
1774			m->flags = 0;
1775			m->dirty = 0;
1776			m->wire_count = 0;
1777			m->busy = 0;
1778			m->queue = PQ_NONE;
1779			m->object = NULL;
1780			vm_page_wire(m);
1781		}
1782
1783		/*
1784		 * We've found a contiguous chunk that meets are requirements.
1785		 * Allocate kernel VM, unfree and assign the physical pages to it and
1786		 * return kernel VM pointer.
1787		 */
1788		tmp_addr = addr = kmem_alloc_pageable(map, size);
1789		if (addr == 0) {
1790			/*
1791			 * XXX We almost never run out of kernel virtual
1792			 * space, so we don't make the allocated memory
1793			 * above available.
1794			 */
1795			splx(s);
1796			return (NULL);
1797		}
1798
1799		for (i = start; i < (start + size / PAGE_SIZE); i++) {
1800			vm_page_t m = &pga[i];
1801			vm_page_insert(m, kernel_object,
1802				OFF_TO_IDX(tmp_addr - VM_MIN_KERNEL_ADDRESS));
1803			pmap_kenter(tmp_addr, VM_PAGE_TO_PHYS(m));
1804			tmp_addr += PAGE_SIZE;
1805		}
1806
1807		splx(s);
1808		return ((void *)addr);
1809	}
1810	return NULL;
1811}
1812
1813void *
1814contigmalloc(size, type, flags, low, high, alignment, boundary)
1815	unsigned long size;	/* should be size_t here and for malloc() */
1816	struct malloc_type *type;
1817	int flags;
1818	unsigned long low;
1819	unsigned long high;
1820	unsigned long alignment;
1821	unsigned long boundary;
1822{
1823	return contigmalloc1(size, type, flags, low, high, alignment, boundary,
1824			     kernel_map);
1825}
1826
1827vm_offset_t
1828vm_page_alloc_contig(size, low, high, alignment)
1829	vm_offset_t size;
1830	vm_offset_t low;
1831	vm_offset_t high;
1832	vm_offset_t alignment;
1833{
1834	return ((vm_offset_t)contigmalloc1(size, M_DEVBUF, M_NOWAIT, low, high,
1835					  alignment, 0ul, kernel_map));
1836}
1837
1838#include "opt_ddb.h"
1839#ifdef DDB
1840#include <sys/kernel.h>
1841
1842#include <ddb/ddb.h>
1843
1844DB_SHOW_COMMAND(page, vm_page_print_page_info)
1845{
1846	db_printf("cnt.v_free_count: %d\n", cnt.v_free_count);
1847	db_printf("cnt.v_cache_count: %d\n", cnt.v_cache_count);
1848	db_printf("cnt.v_inactive_count: %d\n", cnt.v_inactive_count);
1849	db_printf("cnt.v_active_count: %d\n", cnt.v_active_count);
1850	db_printf("cnt.v_wire_count: %d\n", cnt.v_wire_count);
1851	db_printf("cnt.v_free_reserved: %d\n", cnt.v_free_reserved);
1852	db_printf("cnt.v_free_min: %d\n", cnt.v_free_min);
1853	db_printf("cnt.v_free_target: %d\n", cnt.v_free_target);
1854	db_printf("cnt.v_cache_min: %d\n", cnt.v_cache_min);
1855	db_printf("cnt.v_inactive_target: %d\n", cnt.v_inactive_target);
1856}
1857
1858DB_SHOW_COMMAND(pageq, vm_page_print_pageq_info)
1859{
1860	int i;
1861	db_printf("PQ_FREE:");
1862	for(i=0;i<PQ_L2_SIZE;i++) {
1863		db_printf(" %d", *vm_page_queues[PQ_FREE + i].lcnt);
1864	}
1865	db_printf("\n");
1866
1867	db_printf("PQ_CACHE:");
1868	for(i=0;i<PQ_L2_SIZE;i++) {
1869		db_printf(" %d", *vm_page_queues[PQ_CACHE + i].lcnt);
1870	}
1871	db_printf("\n");
1872
1873	db_printf("PQ_ACTIVE: %d, PQ_INACTIVE: %d\n",
1874		*vm_page_queues[PQ_ACTIVE].lcnt,
1875		*vm_page_queues[PQ_INACTIVE].lcnt);
1876}
1877#endif /* DDB */
1878