vm_page.c revision 207738
1/*-
2 * Copyright (c) 1991 Regents of the University of California.
3 * All rights reserved.
4 * Copyright (c) 1998 Matthew Dillon.  All Rights Reserved.
5 *
6 * This code is derived from software contributed to Berkeley by
7 * The Mach Operating System project at Carnegie-Mellon University.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in the
16 *    documentation and/or other materials provided with the distribution.
17 * 4. Neither the name of the University nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 *
33 *	from: @(#)vm_page.c	7.4 (Berkeley) 5/7/91
34 */
35
36/*-
37 * Copyright (c) 1987, 1990 Carnegie-Mellon University.
38 * All rights reserved.
39 *
40 * Authors: Avadis Tevanian, Jr., Michael Wayne Young
41 *
42 * Permission to use, copy, modify and distribute this software and
43 * its documentation is hereby granted, provided that both the copyright
44 * notice and this permission notice appear in all copies of the
45 * software, derivative works or modified versions, and any portions
46 * thereof, and that both notices appear in supporting documentation.
47 *
48 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
49 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
50 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
51 *
52 * Carnegie Mellon requests users of this software to return to
53 *
54 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
55 *  School of Computer Science
56 *  Carnegie Mellon University
57 *  Pittsburgh PA 15213-3890
58 *
59 * any improvements or extensions that they make and grant Carnegie the
60 * rights to redistribute these changes.
61 */
62
63/*
64 *			GENERAL RULES ON VM_PAGE MANIPULATION
65 *
66 *	- a pageq mutex is required when adding or removing a page from a
67 *	  page queue (vm_page_queue[]), regardless of other mutexes or the
68 *	  busy state of a page.
69 *
70 *	- a hash chain mutex is required when associating or disassociating
71 *	  a page from the VM PAGE CACHE hash table (vm_page_buckets),
72 *	  regardless of other mutexes or the busy state of a page.
73 *
74 *	- either a hash chain mutex OR a busied page is required in order
75 *	  to modify the page flags.  A hash chain mutex must be obtained in
76 *	  order to busy a page.  A page's flags cannot be modified by a
77 *	  hash chain mutex if the page is marked busy.
78 *
79 *	- The object memq mutex is held when inserting or removing
80 *	  pages from an object (vm_page_insert() or vm_page_remove()).  This
81 *	  is different from the object's main mutex.
82 *
83 *	Generally speaking, you have to be aware of side effects when running
84 *	vm_page ops.  A vm_page_lookup() will return with the hash chain
85 *	locked, whether it was able to lookup the page or not.  vm_page_free(),
86 *	vm_page_cache(), vm_page_activate(), and a number of other routines
87 *	will release the hash chain mutex for you.  Intermediate manipulation
88 *	routines such as vm_page_flag_set() expect the hash chain to be held
89 *	on entry and the hash chain will remain held on return.
90 *
91 *	pageq scanning can only occur with the pageq in question locked.
92 *	We have a known bottleneck with the active queue, but the cache
93 *	and free queues are actually arrays already.
94 */
95
96/*
97 *	Resident memory management module.
98 */
99
100#include <sys/cdefs.h>
101__FBSDID("$FreeBSD: head/sys/vm/vm_page.c 207738 2010-05-07 04:14:07Z alc $");
102
103#include "opt_vm.h"
104
105#include <sys/param.h>
106#include <sys/systm.h>
107#include <sys/lock.h>
108#include <sys/kernel.h>
109#include <sys/limits.h>
110#include <sys/malloc.h>
111#include <sys/mutex.h>
112#include <sys/proc.h>
113#include <sys/sysctl.h>
114#include <sys/vmmeter.h>
115#include <sys/vnode.h>
116
117#include <vm/vm.h>
118#include <vm/pmap.h>
119#include <vm/vm_param.h>
120#include <vm/vm_kern.h>
121#include <vm/vm_object.h>
122#include <vm/vm_page.h>
123#include <vm/vm_pageout.h>
124#include <vm/vm_pager.h>
125#include <vm/vm_phys.h>
126#include <vm/vm_reserv.h>
127#include <vm/vm_extern.h>
128#include <vm/uma.h>
129#include <vm/uma_int.h>
130
131#include <machine/md_var.h>
132
133#if defined(__amd64__) || defined (__i386__)
134extern struct sysctl_oid_list sysctl__vm_pmap_children;
135#else
136SYSCTL_NODE(_vm, OID_AUTO, pmap, CTLFLAG_RD, 0, "VM/pmap parameters");
137#endif
138
139static uint64_t pmap_tryrelock_calls;
140SYSCTL_QUAD(_vm_pmap, OID_AUTO, tryrelock_calls, CTLFLAG_RD,
141    &pmap_tryrelock_calls, 0, "Number of tryrelock calls");
142
143static int pmap_tryrelock_restart;
144SYSCTL_INT(_vm_pmap, OID_AUTO, tryrelock_restart, CTLFLAG_RD,
145    &pmap_tryrelock_restart, 0, "Number of tryrelock restarts");
146
147static int pmap_tryrelock_race;
148SYSCTL_INT(_vm_pmap, OID_AUTO, tryrelock_race, CTLFLAG_RD,
149    &pmap_tryrelock_race, 0, "Number of tryrelock pmap race cases");
150
151/*
152 *	Associated with page of user-allocatable memory is a
153 *	page structure.
154 */
155
156struct vpgqueues vm_page_queues[PQ_COUNT];
157struct vpglocks vm_page_queue_lock;
158struct vpglocks vm_page_queue_free_lock;
159
160struct vpglocks	pa_lock[PA_LOCK_COUNT] __aligned(CACHE_LINE_SIZE);
161
162vm_page_t vm_page_array = 0;
163int vm_page_array_size = 0;
164long first_page = 0;
165int vm_page_zero_count = 0;
166
167static int boot_pages = UMA_BOOT_PAGES;
168TUNABLE_INT("vm.boot_pages", &boot_pages);
169SYSCTL_INT(_vm, OID_AUTO, boot_pages, CTLFLAG_RD, &boot_pages, 0,
170	"number of pages allocated for bootstrapping the VM system");
171
172static void vm_page_enqueue(int queue, vm_page_t m);
173
174/* Make sure that u_long is at least 64 bits when PAGE_SIZE is 32K. */
175#if PAGE_SIZE == 32768
176#ifdef CTASSERT
177CTASSERT(sizeof(u_long) >= 8);
178#endif
179#endif
180
181/*
182 * Try to acquire a physical address lock while a pmap is locked.  If we
183 * fail to trylock we unlock and lock the pmap directly and cache the
184 * locked pa in *locked.  The caller should then restart their loop in case
185 * the virtual to physical mapping has changed.
186 */
187int
188vm_page_pa_tryrelock(pmap_t pmap, vm_paddr_t pa, vm_paddr_t *locked)
189{
190	vm_paddr_t lockpa;
191	uint32_t gen_count;
192
193	gen_count = pmap->pm_gen_count;
194	atomic_add_long((volatile long *)&pmap_tryrelock_calls, 1);
195	lockpa = *locked;
196	*locked = pa;
197	if (lockpa) {
198		PA_LOCK_ASSERT(lockpa, MA_OWNED);
199		if (PA_LOCKPTR(pa) == PA_LOCKPTR(lockpa))
200			return (0);
201		PA_UNLOCK(lockpa);
202	}
203	if (PA_TRYLOCK(pa))
204		return (0);
205	PMAP_UNLOCK(pmap);
206	atomic_add_int((volatile int *)&pmap_tryrelock_restart, 1);
207	PA_LOCK(pa);
208	PMAP_LOCK(pmap);
209
210	if (pmap->pm_gen_count != gen_count + 1) {
211		pmap->pm_retries++;
212		atomic_add_int((volatile int *)&pmap_tryrelock_race, 1);
213		return (EAGAIN);
214	}
215	return (0);
216}
217
218/*
219 *	vm_set_page_size:
220 *
221 *	Sets the page size, perhaps based upon the memory
222 *	size.  Must be called before any use of page-size
223 *	dependent functions.
224 */
225void
226vm_set_page_size(void)
227{
228	if (cnt.v_page_size == 0)
229		cnt.v_page_size = PAGE_SIZE;
230	if (((cnt.v_page_size - 1) & cnt.v_page_size) != 0)
231		panic("vm_set_page_size: page size not a power of two");
232}
233
234/*
235 *	vm_page_blacklist_lookup:
236 *
237 *	See if a physical address in this page has been listed
238 *	in the blacklist tunable.  Entries in the tunable are
239 *	separated by spaces or commas.  If an invalid integer is
240 *	encountered then the rest of the string is skipped.
241 */
242static int
243vm_page_blacklist_lookup(char *list, vm_paddr_t pa)
244{
245	vm_paddr_t bad;
246	char *cp, *pos;
247
248	for (pos = list; *pos != '\0'; pos = cp) {
249		bad = strtoq(pos, &cp, 0);
250		if (*cp != '\0') {
251			if (*cp == ' ' || *cp == ',') {
252				cp++;
253				if (cp == pos)
254					continue;
255			} else
256				break;
257		}
258		if (pa == trunc_page(bad))
259			return (1);
260	}
261	return (0);
262}
263
264/*
265 *	vm_page_startup:
266 *
267 *	Initializes the resident memory module.
268 *
269 *	Allocates memory for the page cells, and
270 *	for the object/offset-to-page hash table headers.
271 *	Each page cell is initialized and placed on the free list.
272 */
273vm_offset_t
274vm_page_startup(vm_offset_t vaddr)
275{
276	vm_offset_t mapped;
277	vm_paddr_t page_range;
278	vm_paddr_t new_end;
279	int i;
280	vm_paddr_t pa;
281	int nblocks;
282	vm_paddr_t last_pa;
283	char *list;
284
285	/* the biggest memory array is the second group of pages */
286	vm_paddr_t end;
287	vm_paddr_t biggestsize;
288	vm_paddr_t low_water, high_water;
289	int biggestone;
290
291	biggestsize = 0;
292	biggestone = 0;
293	nblocks = 0;
294	vaddr = round_page(vaddr);
295
296	for (i = 0; phys_avail[i + 1]; i += 2) {
297		phys_avail[i] = round_page(phys_avail[i]);
298		phys_avail[i + 1] = trunc_page(phys_avail[i + 1]);
299	}
300
301	low_water = phys_avail[0];
302	high_water = phys_avail[1];
303
304	for (i = 0; phys_avail[i + 1]; i += 2) {
305		vm_paddr_t size = phys_avail[i + 1] - phys_avail[i];
306
307		if (size > biggestsize) {
308			biggestone = i;
309			biggestsize = size;
310		}
311		if (phys_avail[i] < low_water)
312			low_water = phys_avail[i];
313		if (phys_avail[i + 1] > high_water)
314			high_water = phys_avail[i + 1];
315		++nblocks;
316	}
317
318#ifdef XEN
319	low_water = 0;
320#endif
321
322	end = phys_avail[biggestone+1];
323
324	/*
325	 * Initialize the locks.
326	 */
327	mtx_init(&vm_page_queue_mtx, "vm page queue mutex", NULL, MTX_DEF |
328	    MTX_RECURSE);
329	mtx_init(&vm_page_queue_free_mtx, "vm page queue free mutex", NULL,
330	    MTX_DEF);
331
332	/* Setup page locks. */
333	for (i = 0; i < PA_LOCK_COUNT; i++)
334		mtx_init(&pa_lock[i].data, "page lock", NULL,
335		    MTX_DEF | MTX_RECURSE | MTX_DUPOK);
336
337	/*
338	 * Initialize the queue headers for the hold queue, the active queue,
339	 * and the inactive queue.
340	 */
341	for (i = 0; i < PQ_COUNT; i++)
342		TAILQ_INIT(&vm_page_queues[i].pl);
343	vm_page_queues[PQ_INACTIVE].cnt = &cnt.v_inactive_count;
344	vm_page_queues[PQ_ACTIVE].cnt = &cnt.v_active_count;
345	vm_page_queues[PQ_HOLD].cnt = &cnt.v_active_count;
346
347	/*
348	 * Allocate memory for use when boot strapping the kernel memory
349	 * allocator.
350	 */
351	new_end = end - (boot_pages * UMA_SLAB_SIZE);
352	new_end = trunc_page(new_end);
353	mapped = pmap_map(&vaddr, new_end, end,
354	    VM_PROT_READ | VM_PROT_WRITE);
355	bzero((void *)mapped, end - new_end);
356	uma_startup((void *)mapped, boot_pages);
357
358#if defined(__amd64__) || defined(__i386__) || defined(__arm__)
359	/*
360	 * Allocate a bitmap to indicate that a random physical page
361	 * needs to be included in a minidump.
362	 *
363	 * The amd64 port needs this to indicate which direct map pages
364	 * need to be dumped, via calls to dump_add_page()/dump_drop_page().
365	 *
366	 * However, i386 still needs this workspace internally within the
367	 * minidump code.  In theory, they are not needed on i386, but are
368	 * included should the sf_buf code decide to use them.
369	 */
370	page_range = phys_avail[(nblocks - 1) * 2 + 1] / PAGE_SIZE;
371	vm_page_dump_size = round_page(roundup2(page_range, NBBY) / NBBY);
372	new_end -= vm_page_dump_size;
373	vm_page_dump = (void *)(uintptr_t)pmap_map(&vaddr, new_end,
374	    new_end + vm_page_dump_size, VM_PROT_READ | VM_PROT_WRITE);
375	bzero((void *)vm_page_dump, vm_page_dump_size);
376#endif
377	/*
378	 * Compute the number of pages of memory that will be available for
379	 * use (taking into account the overhead of a page structure per
380	 * page).
381	 */
382	first_page = low_water / PAGE_SIZE;
383#ifdef VM_PHYSSEG_SPARSE
384	page_range = 0;
385	for (i = 0; phys_avail[i + 1] != 0; i += 2)
386		page_range += atop(phys_avail[i + 1] - phys_avail[i]);
387#elif defined(VM_PHYSSEG_DENSE)
388	page_range = high_water / PAGE_SIZE - first_page;
389#else
390#error "Either VM_PHYSSEG_DENSE or VM_PHYSSEG_SPARSE must be defined."
391#endif
392	end = new_end;
393
394	/*
395	 * Reserve an unmapped guard page to trap access to vm_page_array[-1].
396	 */
397	vaddr += PAGE_SIZE;
398
399	/*
400	 * Initialize the mem entry structures now, and put them in the free
401	 * queue.
402	 */
403	new_end = trunc_page(end - page_range * sizeof(struct vm_page));
404	mapped = pmap_map(&vaddr, new_end, end,
405	    VM_PROT_READ | VM_PROT_WRITE);
406	vm_page_array = (vm_page_t) mapped;
407#if VM_NRESERVLEVEL > 0
408	/*
409	 * Allocate memory for the reservation management system's data
410	 * structures.
411	 */
412	new_end = vm_reserv_startup(&vaddr, new_end, high_water);
413#endif
414#ifdef __amd64__
415	/*
416	 * pmap_map on amd64 comes out of the direct-map, not kvm like i386,
417	 * so the pages must be tracked for a crashdump to include this data.
418	 * This includes the vm_page_array and the early UMA bootstrap pages.
419	 */
420	for (pa = new_end; pa < phys_avail[biggestone + 1]; pa += PAGE_SIZE)
421		dump_add_page(pa);
422#endif
423	phys_avail[biggestone + 1] = new_end;
424
425	/*
426	 * Clear all of the page structures
427	 */
428	bzero((caddr_t) vm_page_array, page_range * sizeof(struct vm_page));
429	for (i = 0; i < page_range; i++)
430		vm_page_array[i].order = VM_NFREEORDER;
431	vm_page_array_size = page_range;
432
433	/*
434	 * Initialize the physical memory allocator.
435	 */
436	vm_phys_init();
437
438	/*
439	 * Add every available physical page that is not blacklisted to
440	 * the free lists.
441	 */
442	cnt.v_page_count = 0;
443	cnt.v_free_count = 0;
444	list = getenv("vm.blacklist");
445	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
446		pa = phys_avail[i];
447		last_pa = phys_avail[i + 1];
448		while (pa < last_pa) {
449			if (list != NULL &&
450			    vm_page_blacklist_lookup(list, pa))
451				printf("Skipping page with pa 0x%jx\n",
452				    (uintmax_t)pa);
453			else
454				vm_phys_add_page(pa);
455			pa += PAGE_SIZE;
456		}
457	}
458	freeenv(list);
459#if VM_NRESERVLEVEL > 0
460	/*
461	 * Initialize the reservation management system.
462	 */
463	vm_reserv_init();
464#endif
465	return (vaddr);
466}
467
468void
469vm_page_flag_set(vm_page_t m, unsigned short bits)
470{
471
472	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
473	m->flags |= bits;
474}
475
476void
477vm_page_flag_clear(vm_page_t m, unsigned short bits)
478{
479
480	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
481	m->flags &= ~bits;
482}
483
484void
485vm_page_busy(vm_page_t m)
486{
487
488	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
489	KASSERT((m->oflags & VPO_BUSY) == 0,
490	    ("vm_page_busy: page already busy!!!"));
491	m->oflags |= VPO_BUSY;
492}
493
494/*
495 *      vm_page_flash:
496 *
497 *      wakeup anyone waiting for the page.
498 */
499void
500vm_page_flash(vm_page_t m)
501{
502
503	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
504	if (m->oflags & VPO_WANTED) {
505		m->oflags &= ~VPO_WANTED;
506		wakeup(m);
507	}
508}
509
510/*
511 *      vm_page_wakeup:
512 *
513 *      clear the VPO_BUSY flag and wakeup anyone waiting for the
514 *      page.
515 *
516 */
517void
518vm_page_wakeup(vm_page_t m)
519{
520
521	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
522	KASSERT(m->oflags & VPO_BUSY, ("vm_page_wakeup: page not busy!!!"));
523	m->oflags &= ~VPO_BUSY;
524	vm_page_flash(m);
525}
526
527void
528vm_page_io_start(vm_page_t m)
529{
530
531	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
532	m->busy++;
533}
534
535void
536vm_page_io_finish(vm_page_t m)
537{
538
539	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
540	m->busy--;
541	if (m->busy == 0)
542		vm_page_flash(m);
543}
544
545/*
546 * Keep page from being freed by the page daemon
547 * much of the same effect as wiring, except much lower
548 * overhead and should be used only for *very* temporary
549 * holding ("wiring").
550 */
551void
552vm_page_hold(vm_page_t mem)
553{
554
555	vm_page_lock_assert(mem, MA_OWNED);
556        mem->hold_count++;
557}
558
559void
560vm_page_unhold(vm_page_t mem)
561{
562
563	vm_page_lock_assert(mem, MA_OWNED);
564	--mem->hold_count;
565	KASSERT(mem->hold_count >= 0, ("vm_page_unhold: hold count < 0!!!"));
566	if (mem->hold_count == 0 && VM_PAGE_INQUEUE2(mem, PQ_HOLD))
567		vm_page_free_toq(mem);
568}
569
570/*
571 *	vm_page_free:
572 *
573 *	Free a page.
574 */
575void
576vm_page_free(vm_page_t m)
577{
578
579	m->flags &= ~PG_ZERO;
580	vm_page_free_toq(m);
581}
582
583/*
584 *	vm_page_free_zero:
585 *
586 *	Free a page to the zerod-pages queue
587 */
588void
589vm_page_free_zero(vm_page_t m)
590{
591
592	m->flags |= PG_ZERO;
593	vm_page_free_toq(m);
594}
595
596/*
597 *	vm_page_sleep:
598 *
599 *	Sleep and release the page and page queues locks.
600 *
601 *	The object containing the given page must be locked.
602 */
603void
604vm_page_sleep(vm_page_t m, const char *msg)
605{
606
607	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
608	if (mtx_owned(&vm_page_queue_mtx))
609		vm_page_unlock_queues();
610	if (mtx_owned(vm_page_lockptr(m)))
611		vm_page_unlock(m);
612
613	/*
614	 * It's possible that while we sleep, the page will get
615	 * unbusied and freed.  If we are holding the object
616	 * lock, we will assume we hold a reference to the object
617	 * such that even if m->object changes, we can re-lock
618	 * it.
619	 */
620	m->oflags |= VPO_WANTED;
621	msleep(m, VM_OBJECT_MTX(m->object), PVM, msg, 0);
622}
623
624/*
625 *	vm_page_dirty:
626 *
627 *	make page all dirty
628 */
629void
630vm_page_dirty(vm_page_t m)
631{
632
633	KASSERT((m->flags & PG_CACHED) == 0,
634	    ("vm_page_dirty: page in cache!"));
635	KASSERT(!VM_PAGE_IS_FREE(m),
636	    ("vm_page_dirty: page is free!"));
637	KASSERT(m->valid == VM_PAGE_BITS_ALL,
638	    ("vm_page_dirty: page is invalid!"));
639	m->dirty = VM_PAGE_BITS_ALL;
640}
641
642/*
643 *	vm_page_splay:
644 *
645 *	Implements Sleator and Tarjan's top-down splay algorithm.  Returns
646 *	the vm_page containing the given pindex.  If, however, that
647 *	pindex is not found in the vm_object, returns a vm_page that is
648 *	adjacent to the pindex, coming before or after it.
649 */
650vm_page_t
651vm_page_splay(vm_pindex_t pindex, vm_page_t root)
652{
653	struct vm_page dummy;
654	vm_page_t lefttreemax, righttreemin, y;
655
656	if (root == NULL)
657		return (root);
658	lefttreemax = righttreemin = &dummy;
659	for (;; root = y) {
660		if (pindex < root->pindex) {
661			if ((y = root->left) == NULL)
662				break;
663			if (pindex < y->pindex) {
664				/* Rotate right. */
665				root->left = y->right;
666				y->right = root;
667				root = y;
668				if ((y = root->left) == NULL)
669					break;
670			}
671			/* Link into the new root's right tree. */
672			righttreemin->left = root;
673			righttreemin = root;
674		} else if (pindex > root->pindex) {
675			if ((y = root->right) == NULL)
676				break;
677			if (pindex > y->pindex) {
678				/* Rotate left. */
679				root->right = y->left;
680				y->left = root;
681				root = y;
682				if ((y = root->right) == NULL)
683					break;
684			}
685			/* Link into the new root's left tree. */
686			lefttreemax->right = root;
687			lefttreemax = root;
688		} else
689			break;
690	}
691	/* Assemble the new root. */
692	lefttreemax->right = root->left;
693	righttreemin->left = root->right;
694	root->left = dummy.right;
695	root->right = dummy.left;
696	return (root);
697}
698
699/*
700 *	vm_page_insert:		[ internal use only ]
701 *
702 *	Inserts the given mem entry into the object and object list.
703 *
704 *	The pagetables are not updated but will presumably fault the page
705 *	in if necessary, or if a kernel page the caller will at some point
706 *	enter the page into the kernel's pmap.  We are not allowed to block
707 *	here so we *can't* do this anyway.
708 *
709 *	The object and page must be locked.
710 *	This routine may not block.
711 */
712void
713vm_page_insert(vm_page_t m, vm_object_t object, vm_pindex_t pindex)
714{
715	vm_page_t root;
716
717	VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
718	if (m->object != NULL)
719		panic("vm_page_insert: page already inserted");
720
721	/*
722	 * Record the object/offset pair in this page
723	 */
724	m->object = object;
725	m->pindex = pindex;
726
727	/*
728	 * Now link into the object's ordered list of backed pages.
729	 */
730	root = object->root;
731	if (root == NULL) {
732		m->left = NULL;
733		m->right = NULL;
734		TAILQ_INSERT_TAIL(&object->memq, m, listq);
735	} else {
736		root = vm_page_splay(pindex, root);
737		if (pindex < root->pindex) {
738			m->left = root->left;
739			m->right = root;
740			root->left = NULL;
741			TAILQ_INSERT_BEFORE(root, m, listq);
742		} else if (pindex == root->pindex)
743			panic("vm_page_insert: offset already allocated");
744		else {
745			m->right = root->right;
746			m->left = root;
747			root->right = NULL;
748			TAILQ_INSERT_AFTER(&object->memq, root, m, listq);
749		}
750	}
751	object->root = m;
752	object->generation++;
753
754	/*
755	 * show that the object has one more resident page.
756	 */
757	object->resident_page_count++;
758	/*
759	 * Hold the vnode until the last page is released.
760	 */
761	if (object->resident_page_count == 1 && object->type == OBJT_VNODE)
762		vhold((struct vnode *)object->handle);
763
764	/*
765	 * Since we are inserting a new and possibly dirty page,
766	 * update the object's OBJ_MIGHTBEDIRTY flag.
767	 */
768	if (m->flags & PG_WRITEABLE)
769		vm_object_set_writeable_dirty(object);
770}
771
772/*
773 *	vm_page_remove:
774 *				NOTE: used by device pager as well -wfj
775 *
776 *	Removes the given mem entry from the object/offset-page
777 *	table and the object page list, but do not invalidate/terminate
778 *	the backing store.
779 *
780 *	The object and page must be locked.
781 *	The underlying pmap entry (if any) is NOT removed here.
782 *	This routine may not block.
783 */
784void
785vm_page_remove(vm_page_t m)
786{
787	vm_object_t object;
788	vm_page_t root;
789
790	if ((m->flags & PG_UNMANAGED) == 0)
791		vm_page_lock_assert(m, MA_OWNED);
792	if ((object = m->object) == NULL)
793		return;
794	VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
795	if (m->oflags & VPO_BUSY) {
796		m->oflags &= ~VPO_BUSY;
797		vm_page_flash(m);
798	}
799
800	/*
801	 * Now remove from the object's list of backed pages.
802	 */
803	if (m != object->root)
804		vm_page_splay(m->pindex, object->root);
805	if (m->left == NULL)
806		root = m->right;
807	else {
808		root = vm_page_splay(m->pindex, m->left);
809		root->right = m->right;
810	}
811	object->root = root;
812	TAILQ_REMOVE(&object->memq, m, listq);
813
814	/*
815	 * And show that the object has one fewer resident page.
816	 */
817	object->resident_page_count--;
818	object->generation++;
819	/*
820	 * The vnode may now be recycled.
821	 */
822	if (object->resident_page_count == 0 && object->type == OBJT_VNODE)
823		vdrop((struct vnode *)object->handle);
824
825	m->object = NULL;
826}
827
828/*
829 *	vm_page_lookup:
830 *
831 *	Returns the page associated with the object/offset
832 *	pair specified; if none is found, NULL is returned.
833 *
834 *	The object must be locked.
835 *	This routine may not block.
836 *	This is a critical path routine
837 */
838vm_page_t
839vm_page_lookup(vm_object_t object, vm_pindex_t pindex)
840{
841	vm_page_t m;
842
843	VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
844	if ((m = object->root) != NULL && m->pindex != pindex) {
845		m = vm_page_splay(pindex, m);
846		if ((object->root = m)->pindex != pindex)
847			m = NULL;
848	}
849	return (m);
850}
851
852/*
853 *	vm_page_rename:
854 *
855 *	Move the given memory entry from its
856 *	current object to the specified target object/offset.
857 *
858 *	The object must be locked.
859 *	This routine may not block.
860 *
861 *	Note: swap associated with the page must be invalidated by the move.  We
862 *	      have to do this for several reasons:  (1) we aren't freeing the
863 *	      page, (2) we are dirtying the page, (3) the VM system is probably
864 *	      moving the page from object A to B, and will then later move
865 *	      the backing store from A to B and we can't have a conflict.
866 *
867 *	Note: we *always* dirty the page.  It is necessary both for the
868 *	      fact that we moved it, and because we may be invalidating
869 *	      swap.  If the page is on the cache, we have to deactivate it
870 *	      or vm_page_dirty() will panic.  Dirty pages are not allowed
871 *	      on the cache.
872 */
873void
874vm_page_rename(vm_page_t m, vm_object_t new_object, vm_pindex_t new_pindex)
875{
876
877	vm_page_remove(m);
878	vm_page_insert(m, new_object, new_pindex);
879	vm_page_dirty(m);
880}
881
882/*
883 *	Convert all of the given object's cached pages that have a
884 *	pindex within the given range into free pages.  If the value
885 *	zero is given for "end", then the range's upper bound is
886 *	infinity.  If the given object is backed by a vnode and it
887 *	transitions from having one or more cached pages to none, the
888 *	vnode's hold count is reduced.
889 */
890void
891vm_page_cache_free(vm_object_t object, vm_pindex_t start, vm_pindex_t end)
892{
893	vm_page_t m, m_next;
894	boolean_t empty;
895
896	mtx_lock(&vm_page_queue_free_mtx);
897	if (__predict_false(object->cache == NULL)) {
898		mtx_unlock(&vm_page_queue_free_mtx);
899		return;
900	}
901	m = object->cache = vm_page_splay(start, object->cache);
902	if (m->pindex < start) {
903		if (m->right == NULL)
904			m = NULL;
905		else {
906			m_next = vm_page_splay(start, m->right);
907			m_next->left = m;
908			m->right = NULL;
909			m = object->cache = m_next;
910		}
911	}
912
913	/*
914	 * At this point, "m" is either (1) a reference to the page
915	 * with the least pindex that is greater than or equal to
916	 * "start" or (2) NULL.
917	 */
918	for (; m != NULL && (m->pindex < end || end == 0); m = m_next) {
919		/*
920		 * Find "m"'s successor and remove "m" from the
921		 * object's cache.
922		 */
923		if (m->right == NULL) {
924			object->cache = m->left;
925			m_next = NULL;
926		} else {
927			m_next = vm_page_splay(start, m->right);
928			m_next->left = m->left;
929			object->cache = m_next;
930		}
931		/* Convert "m" to a free page. */
932		m->object = NULL;
933		m->valid = 0;
934		/* Clear PG_CACHED and set PG_FREE. */
935		m->flags ^= PG_CACHED | PG_FREE;
936		KASSERT((m->flags & (PG_CACHED | PG_FREE)) == PG_FREE,
937		    ("vm_page_cache_free: page %p has inconsistent flags", m));
938		cnt.v_cache_count--;
939		cnt.v_free_count++;
940	}
941	empty = object->cache == NULL;
942	mtx_unlock(&vm_page_queue_free_mtx);
943	if (object->type == OBJT_VNODE && empty)
944		vdrop(object->handle);
945}
946
947/*
948 *	Returns the cached page that is associated with the given
949 *	object and offset.  If, however, none exists, returns NULL.
950 *
951 *	The free page queue must be locked.
952 */
953static inline vm_page_t
954vm_page_cache_lookup(vm_object_t object, vm_pindex_t pindex)
955{
956	vm_page_t m;
957
958	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
959	if ((m = object->cache) != NULL && m->pindex != pindex) {
960		m = vm_page_splay(pindex, m);
961		if ((object->cache = m)->pindex != pindex)
962			m = NULL;
963	}
964	return (m);
965}
966
967/*
968 *	Remove the given cached page from its containing object's
969 *	collection of cached pages.
970 *
971 *	The free page queue must be locked.
972 */
973void
974vm_page_cache_remove(vm_page_t m)
975{
976	vm_object_t object;
977	vm_page_t root;
978
979	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
980	KASSERT((m->flags & PG_CACHED) != 0,
981	    ("vm_page_cache_remove: page %p is not cached", m));
982	object = m->object;
983	if (m != object->cache) {
984		root = vm_page_splay(m->pindex, object->cache);
985		KASSERT(root == m,
986		    ("vm_page_cache_remove: page %p is not cached in object %p",
987		    m, object));
988	}
989	if (m->left == NULL)
990		root = m->right;
991	else if (m->right == NULL)
992		root = m->left;
993	else {
994		root = vm_page_splay(m->pindex, m->left);
995		root->right = m->right;
996	}
997	object->cache = root;
998	m->object = NULL;
999	cnt.v_cache_count--;
1000}
1001
1002/*
1003 *	Transfer all of the cached pages with offset greater than or
1004 *	equal to 'offidxstart' from the original object's cache to the
1005 *	new object's cache.  However, any cached pages with offset
1006 *	greater than or equal to the new object's size are kept in the
1007 *	original object.  Initially, the new object's cache must be
1008 *	empty.  Offset 'offidxstart' in the original object must
1009 *	correspond to offset zero in the new object.
1010 *
1011 *	The new object must be locked.
1012 */
1013void
1014vm_page_cache_transfer(vm_object_t orig_object, vm_pindex_t offidxstart,
1015    vm_object_t new_object)
1016{
1017	vm_page_t m, m_next;
1018
1019	/*
1020	 * Insertion into an object's collection of cached pages
1021	 * requires the object to be locked.  In contrast, removal does
1022	 * not.
1023	 */
1024	VM_OBJECT_LOCK_ASSERT(new_object, MA_OWNED);
1025	KASSERT(new_object->cache == NULL,
1026	    ("vm_page_cache_transfer: object %p has cached pages",
1027	    new_object));
1028	mtx_lock(&vm_page_queue_free_mtx);
1029	if ((m = orig_object->cache) != NULL) {
1030		/*
1031		 * Transfer all of the pages with offset greater than or
1032		 * equal to 'offidxstart' from the original object's
1033		 * cache to the new object's cache.
1034		 */
1035		m = vm_page_splay(offidxstart, m);
1036		if (m->pindex < offidxstart) {
1037			orig_object->cache = m;
1038			new_object->cache = m->right;
1039			m->right = NULL;
1040		} else {
1041			orig_object->cache = m->left;
1042			new_object->cache = m;
1043			m->left = NULL;
1044		}
1045		while ((m = new_object->cache) != NULL) {
1046			if ((m->pindex - offidxstart) >= new_object->size) {
1047				/*
1048				 * Return all of the cached pages with
1049				 * offset greater than or equal to the
1050				 * new object's size to the original
1051				 * object's cache.
1052				 */
1053				new_object->cache = m->left;
1054				m->left = orig_object->cache;
1055				orig_object->cache = m;
1056				break;
1057			}
1058			m_next = vm_page_splay(m->pindex, m->right);
1059			/* Update the page's object and offset. */
1060			m->object = new_object;
1061			m->pindex -= offidxstart;
1062			if (m_next == NULL)
1063				break;
1064			m->right = NULL;
1065			m_next->left = m;
1066			new_object->cache = m_next;
1067		}
1068		KASSERT(new_object->cache == NULL ||
1069		    new_object->type == OBJT_SWAP,
1070		    ("vm_page_cache_transfer: object %p's type is incompatible"
1071		    " with cached pages", new_object));
1072	}
1073	mtx_unlock(&vm_page_queue_free_mtx);
1074}
1075
1076/*
1077 *	vm_page_alloc:
1078 *
1079 *	Allocate and return a memory cell associated
1080 *	with this VM object/offset pair.
1081 *
1082 *	page_req classes:
1083 *	VM_ALLOC_NORMAL		normal process request
1084 *	VM_ALLOC_SYSTEM		system *really* needs a page
1085 *	VM_ALLOC_INTERRUPT	interrupt time request
1086 *	VM_ALLOC_ZERO		zero page
1087 *	VM_ALLOC_WIRED		wire the allocated page
1088 *	VM_ALLOC_NOOBJ		page is not associated with a vm object
1089 *	VM_ALLOC_NOBUSY		do not set the page busy
1090 *	VM_ALLOC_IFNOTCACHED	return NULL, do not reactivate if the page
1091 *				is cached
1092 *
1093 *	This routine may not sleep.
1094 */
1095vm_page_t
1096vm_page_alloc(vm_object_t object, vm_pindex_t pindex, int req)
1097{
1098	struct vnode *vp = NULL;
1099	vm_object_t m_object;
1100	vm_page_t m;
1101	int flags, page_req;
1102
1103	page_req = req & VM_ALLOC_CLASS_MASK;
1104	KASSERT(curthread->td_intr_nesting_level == 0 ||
1105	    page_req == VM_ALLOC_INTERRUPT,
1106	    ("vm_page_alloc(NORMAL|SYSTEM) in interrupt context"));
1107
1108	if ((req & VM_ALLOC_NOOBJ) == 0) {
1109		KASSERT(object != NULL,
1110		    ("vm_page_alloc: NULL object."));
1111		VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
1112	}
1113
1114	/*
1115	 * The pager is allowed to eat deeper into the free page list.
1116	 */
1117	if ((curproc == pageproc) && (page_req != VM_ALLOC_INTERRUPT)) {
1118		page_req = VM_ALLOC_SYSTEM;
1119	};
1120
1121	mtx_lock(&vm_page_queue_free_mtx);
1122	if (cnt.v_free_count + cnt.v_cache_count > cnt.v_free_reserved ||
1123	    (page_req == VM_ALLOC_SYSTEM &&
1124	    cnt.v_free_count + cnt.v_cache_count > cnt.v_interrupt_free_min) ||
1125	    (page_req == VM_ALLOC_INTERRUPT &&
1126	    cnt.v_free_count + cnt.v_cache_count > 0)) {
1127		/*
1128		 * Allocate from the free queue if the number of free pages
1129		 * exceeds the minimum for the request class.
1130		 */
1131		if (object != NULL &&
1132		    (m = vm_page_cache_lookup(object, pindex)) != NULL) {
1133			if ((req & VM_ALLOC_IFNOTCACHED) != 0) {
1134				mtx_unlock(&vm_page_queue_free_mtx);
1135				return (NULL);
1136			}
1137			if (vm_phys_unfree_page(m))
1138				vm_phys_set_pool(VM_FREEPOOL_DEFAULT, m, 0);
1139#if VM_NRESERVLEVEL > 0
1140			else if (!vm_reserv_reactivate_page(m))
1141#else
1142			else
1143#endif
1144				panic("vm_page_alloc: cache page %p is missing"
1145				    " from the free queue", m);
1146		} else if ((req & VM_ALLOC_IFCACHED) != 0) {
1147			mtx_unlock(&vm_page_queue_free_mtx);
1148			return (NULL);
1149#if VM_NRESERVLEVEL > 0
1150		} else if (object == NULL || object->type == OBJT_DEVICE ||
1151		    object->type == OBJT_SG ||
1152		    (object->flags & OBJ_COLORED) == 0 ||
1153		    (m = vm_reserv_alloc_page(object, pindex)) == NULL) {
1154#else
1155		} else {
1156#endif
1157			m = vm_phys_alloc_pages(object != NULL ?
1158			    VM_FREEPOOL_DEFAULT : VM_FREEPOOL_DIRECT, 0);
1159#if VM_NRESERVLEVEL > 0
1160			if (m == NULL && vm_reserv_reclaim_inactive()) {
1161				m = vm_phys_alloc_pages(object != NULL ?
1162				    VM_FREEPOOL_DEFAULT : VM_FREEPOOL_DIRECT,
1163				    0);
1164			}
1165#endif
1166		}
1167	} else {
1168		/*
1169		 * Not allocatable, give up.
1170		 */
1171		mtx_unlock(&vm_page_queue_free_mtx);
1172		atomic_add_int(&vm_pageout_deficit, 1);
1173		pagedaemon_wakeup();
1174		return (NULL);
1175	}
1176
1177	/*
1178	 *  At this point we had better have found a good page.
1179	 */
1180
1181	KASSERT(m != NULL, ("vm_page_alloc: missing page"));
1182	KASSERT(m->queue == PQ_NONE,
1183	    ("vm_page_alloc: page %p has unexpected queue %d", m, m->queue));
1184	KASSERT(m->wire_count == 0, ("vm_page_alloc: page %p is wired", m));
1185	KASSERT(m->hold_count == 0, ("vm_page_alloc: page %p is held", m));
1186	KASSERT(m->busy == 0, ("vm_page_alloc: page %p is busy", m));
1187	KASSERT(m->dirty == 0, ("vm_page_alloc: page %p is dirty", m));
1188	KASSERT(pmap_page_get_memattr(m) == VM_MEMATTR_DEFAULT,
1189	    ("vm_page_alloc: page %p has unexpected memattr %d", m,
1190	    pmap_page_get_memattr(m)));
1191	if ((m->flags & PG_CACHED) != 0) {
1192		KASSERT(m->valid != 0,
1193		    ("vm_page_alloc: cached page %p is invalid", m));
1194		if (m->object == object && m->pindex == pindex)
1195	  		cnt.v_reactivated++;
1196		else
1197			m->valid = 0;
1198		m_object = m->object;
1199		vm_page_cache_remove(m);
1200		if (m_object->type == OBJT_VNODE && m_object->cache == NULL)
1201			vp = m_object->handle;
1202	} else {
1203		KASSERT(VM_PAGE_IS_FREE(m),
1204		    ("vm_page_alloc: page %p is not free", m));
1205		KASSERT(m->valid == 0,
1206		    ("vm_page_alloc: free page %p is valid", m));
1207		cnt.v_free_count--;
1208	}
1209
1210	/*
1211	 * Initialize structure.  Only the PG_ZERO flag is inherited.
1212	 */
1213	flags = 0;
1214	if (m->flags & PG_ZERO) {
1215		vm_page_zero_count--;
1216		if (req & VM_ALLOC_ZERO)
1217			flags = PG_ZERO;
1218	}
1219	if (object == NULL || object->type == OBJT_PHYS)
1220		flags |= PG_UNMANAGED;
1221	m->flags = flags;
1222	if (req & (VM_ALLOC_NOBUSY | VM_ALLOC_NOOBJ))
1223		m->oflags = 0;
1224	else
1225		m->oflags = VPO_BUSY;
1226	if (req & VM_ALLOC_WIRED) {
1227		atomic_add_int(&cnt.v_wire_count, 1);
1228		m->wire_count = 1;
1229	}
1230	m->act_count = 0;
1231	mtx_unlock(&vm_page_queue_free_mtx);
1232
1233	if (object != NULL) {
1234		/* Ignore device objects; the pager sets "memattr" for them. */
1235		if (object->memattr != VM_MEMATTR_DEFAULT &&
1236		    object->type != OBJT_DEVICE && object->type != OBJT_SG)
1237			pmap_page_set_memattr(m, object->memattr);
1238		vm_page_insert(m, object, pindex);
1239	} else
1240		m->pindex = pindex;
1241
1242	/*
1243	 * The following call to vdrop() must come after the above call
1244	 * to vm_page_insert() in case both affect the same object and
1245	 * vnode.  Otherwise, the affected vnode's hold count could
1246	 * temporarily become zero.
1247	 */
1248	if (vp != NULL)
1249		vdrop(vp);
1250
1251	/*
1252	 * Don't wakeup too often - wakeup the pageout daemon when
1253	 * we would be nearly out of memory.
1254	 */
1255	if (vm_paging_needed())
1256		pagedaemon_wakeup();
1257
1258	return (m);
1259}
1260
1261/*
1262 *	vm_wait:	(also see VM_WAIT macro)
1263 *
1264 *	Block until free pages are available for allocation
1265 *	- Called in various places before memory allocations.
1266 */
1267void
1268vm_wait(void)
1269{
1270
1271	mtx_lock(&vm_page_queue_free_mtx);
1272	if (curproc == pageproc) {
1273		vm_pageout_pages_needed = 1;
1274		msleep(&vm_pageout_pages_needed, &vm_page_queue_free_mtx,
1275		    PDROP | PSWP, "VMWait", 0);
1276	} else {
1277		if (!vm_pages_needed) {
1278			vm_pages_needed = 1;
1279			wakeup(&vm_pages_needed);
1280		}
1281		msleep(&cnt.v_free_count, &vm_page_queue_free_mtx, PDROP | PVM,
1282		    "vmwait", 0);
1283	}
1284}
1285
1286/*
1287 *	vm_waitpfault:	(also see VM_WAITPFAULT macro)
1288 *
1289 *	Block until free pages are available for allocation
1290 *	- Called only in vm_fault so that processes page faulting
1291 *	  can be easily tracked.
1292 *	- Sleeps at a lower priority than vm_wait() so that vm_wait()ing
1293 *	  processes will be able to grab memory first.  Do not change
1294 *	  this balance without careful testing first.
1295 */
1296void
1297vm_waitpfault(void)
1298{
1299
1300	mtx_lock(&vm_page_queue_free_mtx);
1301	if (!vm_pages_needed) {
1302		vm_pages_needed = 1;
1303		wakeup(&vm_pages_needed);
1304	}
1305	msleep(&cnt.v_free_count, &vm_page_queue_free_mtx, PDROP | PUSER,
1306	    "pfault", 0);
1307}
1308
1309/*
1310 *	vm_page_requeue:
1311 *
1312 *	If the given page is contained within a page queue, move it to the tail
1313 *	of that queue.
1314 *
1315 *	The page queues must be locked.
1316 */
1317void
1318vm_page_requeue(vm_page_t m)
1319{
1320	int queue = VM_PAGE_GETQUEUE(m);
1321	struct vpgqueues *vpq;
1322
1323	if (queue != PQ_NONE) {
1324		vpq = &vm_page_queues[queue];
1325		TAILQ_REMOVE(&vpq->pl, m, pageq);
1326		TAILQ_INSERT_TAIL(&vpq->pl, m, pageq);
1327	}
1328}
1329
1330/*
1331 *	vm_pageq_remove:
1332 *
1333 *	Remove a page from its queue.
1334 *
1335 *	The queue containing the given page must be locked.
1336 *	This routine may not block.
1337 */
1338void
1339vm_pageq_remove(vm_page_t m)
1340{
1341	int queue = VM_PAGE_GETQUEUE(m);
1342	struct vpgqueues *pq;
1343
1344	if (queue != PQ_NONE) {
1345		VM_PAGE_SETQUEUE2(m, PQ_NONE);
1346		pq = &vm_page_queues[queue];
1347		TAILQ_REMOVE(&pq->pl, m, pageq);
1348		(*pq->cnt)--;
1349	}
1350}
1351
1352/*
1353 *	vm_page_enqueue:
1354 *
1355 *	Add the given page to the specified queue.
1356 *
1357 *	The page queues must be locked.
1358 */
1359static void
1360vm_page_enqueue(int queue, vm_page_t m)
1361{
1362	struct vpgqueues *vpq;
1363
1364	vpq = &vm_page_queues[queue];
1365	VM_PAGE_SETQUEUE2(m, queue);
1366	TAILQ_INSERT_TAIL(&vpq->pl, m, pageq);
1367	++*vpq->cnt;
1368}
1369
1370/*
1371 *	vm_page_activate:
1372 *
1373 *	Put the specified page on the active list (if appropriate).
1374 *	Ensure that act_count is at least ACT_INIT but do not otherwise
1375 *	mess with it.
1376 *
1377 *	The page queues must be locked.
1378 *	This routine may not block.
1379 */
1380void
1381vm_page_activate(vm_page_t m)
1382{
1383
1384	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
1385	vm_page_lock_assert(m, MA_OWNED);
1386	if (VM_PAGE_GETKNOWNQUEUE2(m) != PQ_ACTIVE) {
1387		vm_pageq_remove(m);
1388		if (m->wire_count == 0 && (m->flags & PG_UNMANAGED) == 0) {
1389			if (m->act_count < ACT_INIT)
1390				m->act_count = ACT_INIT;
1391			vm_page_enqueue(PQ_ACTIVE, m);
1392		}
1393	} else {
1394		if (m->act_count < ACT_INIT)
1395			m->act_count = ACT_INIT;
1396	}
1397}
1398
1399/*
1400 *	vm_page_free_wakeup:
1401 *
1402 *	Helper routine for vm_page_free_toq() and vm_page_cache().  This
1403 *	routine is called when a page has been added to the cache or free
1404 *	queues.
1405 *
1406 *	The page queues must be locked.
1407 *	This routine may not block.
1408 */
1409static inline void
1410vm_page_free_wakeup(void)
1411{
1412
1413	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
1414	/*
1415	 * if pageout daemon needs pages, then tell it that there are
1416	 * some free.
1417	 */
1418	if (vm_pageout_pages_needed &&
1419	    cnt.v_cache_count + cnt.v_free_count >= cnt.v_pageout_free_min) {
1420		wakeup(&vm_pageout_pages_needed);
1421		vm_pageout_pages_needed = 0;
1422	}
1423	/*
1424	 * wakeup processes that are waiting on memory if we hit a
1425	 * high water mark. And wakeup scheduler process if we have
1426	 * lots of memory. this process will swapin processes.
1427	 */
1428	if (vm_pages_needed && !vm_page_count_min()) {
1429		vm_pages_needed = 0;
1430		wakeup(&cnt.v_free_count);
1431	}
1432}
1433
1434/*
1435 *	vm_page_free_toq:
1436 *
1437 *	Returns the given page to the free list,
1438 *	disassociating it with any VM object.
1439 *
1440 *	Object and page must be locked prior to entry.
1441 *	This routine may not block.
1442 */
1443
1444void
1445vm_page_free_toq(vm_page_t m)
1446{
1447
1448	if ((m->flags & PG_UNMANAGED) == 0) {
1449		vm_page_lock_assert(m, MA_OWNED);
1450		KASSERT(!pmap_page_is_mapped(m),
1451		    ("vm_page_free_toq: freeing mapped page %p", m));
1452	}
1453	PCPU_INC(cnt.v_tfree);
1454
1455	if (m->busy || VM_PAGE_IS_FREE(m)) {
1456		printf(
1457		"vm_page_free: pindex(%lu), busy(%d), VPO_BUSY(%d), hold(%d)\n",
1458		    (u_long)m->pindex, m->busy, (m->oflags & VPO_BUSY) ? 1 : 0,
1459		    m->hold_count);
1460		if (VM_PAGE_IS_FREE(m))
1461			panic("vm_page_free: freeing free page");
1462		else
1463			panic("vm_page_free: freeing busy page");
1464	}
1465
1466	/*
1467	 * unqueue, then remove page.  Note that we cannot destroy
1468	 * the page here because we do not want to call the pager's
1469	 * callback routine until after we've put the page on the
1470	 * appropriate free queue.
1471	 */
1472	if (VM_PAGE_GETQUEUE(m) != PQ_NONE) {
1473		vm_page_lock_queues();
1474		vm_pageq_remove(m);
1475		vm_page_unlock_queues();
1476	}
1477	vm_page_remove(m);
1478
1479	/*
1480	 * If fictitious remove object association and
1481	 * return, otherwise delay object association removal.
1482	 */
1483	if ((m->flags & PG_FICTITIOUS) != 0) {
1484		return;
1485	}
1486
1487	m->valid = 0;
1488	vm_page_undirty(m);
1489
1490	if (m->wire_count != 0) {
1491		if (m->wire_count > 1) {
1492			panic("vm_page_free: invalid wire count (%d), pindex: 0x%lx",
1493				m->wire_count, (long)m->pindex);
1494		}
1495		panic("vm_page_free: freeing wired page");
1496	}
1497	if (m->hold_count != 0) {
1498		m->flags &= ~PG_ZERO;
1499		vm_page_lock_queues();
1500		vm_page_enqueue(PQ_HOLD, m);
1501		vm_page_unlock_queues();
1502	} else {
1503		/*
1504		 * Restore the default memory attribute to the page.
1505		 */
1506		if (pmap_page_get_memattr(m) != VM_MEMATTR_DEFAULT)
1507			pmap_page_set_memattr(m, VM_MEMATTR_DEFAULT);
1508
1509		/*
1510		 * Insert the page into the physical memory allocator's
1511		 * cache/free page queues.
1512		 */
1513		mtx_lock(&vm_page_queue_free_mtx);
1514		m->flags |= PG_FREE;
1515		cnt.v_free_count++;
1516#if VM_NRESERVLEVEL > 0
1517		if (!vm_reserv_free_page(m))
1518#else
1519		if (TRUE)
1520#endif
1521			vm_phys_free_pages(m, 0);
1522		if ((m->flags & PG_ZERO) != 0)
1523			++vm_page_zero_count;
1524		else
1525			vm_page_zero_idle_wakeup();
1526		vm_page_free_wakeup();
1527		mtx_unlock(&vm_page_queue_free_mtx);
1528	}
1529}
1530
1531/*
1532 *	vm_page_wire:
1533 *
1534 *	Mark this page as wired down by yet
1535 *	another map, removing it from paging queues
1536 *	as necessary.
1537 *
1538 *	The page must be locked.
1539 *	This routine may not block.
1540 */
1541void
1542vm_page_wire(vm_page_t m)
1543{
1544
1545	/*
1546	 * Only bump the wire statistics if the page is not already wired,
1547	 * and only unqueue the page if it is on some queue (if it is unmanaged
1548	 * it is already off the queues).
1549	 */
1550	vm_page_lock_assert(m, MA_OWNED);
1551	if (m->flags & PG_FICTITIOUS)
1552		return;
1553	if (m->wire_count == 0) {
1554		if ((m->flags & PG_UNMANAGED) == 0) {
1555			vm_page_lock_queues();
1556			vm_pageq_remove(m);
1557			vm_page_unlock_queues();
1558		}
1559		atomic_add_int(&cnt.v_wire_count, 1);
1560	}
1561	m->wire_count++;
1562	KASSERT(m->wire_count != 0, ("vm_page_wire: wire_count overflow m=%p", m));
1563}
1564
1565/*
1566 *	vm_page_unwire:
1567 *
1568 *	Release one wiring of this page, potentially
1569 *	enabling it to be paged again.
1570 *
1571 *	Many pages placed on the inactive queue should actually go
1572 *	into the cache, but it is difficult to figure out which.  What
1573 *	we do instead, if the inactive target is well met, is to put
1574 *	clean pages at the head of the inactive queue instead of the tail.
1575 *	This will cause them to be moved to the cache more quickly and
1576 *	if not actively re-referenced, freed more quickly.  If we just
1577 *	stick these pages at the end of the inactive queue, heavy filesystem
1578 *	meta-data accesses can cause an unnecessary paging load on memory bound
1579 *	processes.  This optimization causes one-time-use metadata to be
1580 *	reused more quickly.
1581 *
1582 *	BUT, if we are in a low-memory situation we have no choice but to
1583 *	put clean pages on the cache queue.
1584 *
1585 *	A number of routines use vm_page_unwire() to guarantee that the page
1586 *	will go into either the inactive or active queues, and will NEVER
1587 *	be placed in the cache - for example, just after dirtying a page.
1588 *	dirty pages in the cache are not allowed.
1589 *
1590 *	The page must be locked.
1591 *	This routine may not block.
1592 */
1593void
1594vm_page_unwire(vm_page_t m, int activate)
1595{
1596
1597	if ((m->flags & PG_UNMANAGED) == 0)
1598		vm_page_lock_assert(m, MA_OWNED);
1599	if (m->flags & PG_FICTITIOUS)
1600		return;
1601	if (m->wire_count > 0) {
1602		m->wire_count--;
1603		if (m->wire_count == 0) {
1604			atomic_subtract_int(&cnt.v_wire_count, 1);
1605			if ((m->flags & PG_UNMANAGED) != 0)
1606				return;
1607			vm_page_lock_queues();
1608			if (activate)
1609				vm_page_enqueue(PQ_ACTIVE, m);
1610			else {
1611				vm_page_flag_clear(m, PG_WINATCFLS);
1612				vm_page_enqueue(PQ_INACTIVE, m);
1613			}
1614			vm_page_unlock_queues();
1615		}
1616	} else {
1617		panic("vm_page_unwire: invalid wire count: %d", m->wire_count);
1618	}
1619}
1620
1621/*
1622 * Move the specified page to the inactive queue.
1623 *
1624 * Normally athead is 0 resulting in LRU operation.  athead is set
1625 * to 1 if we want this page to be 'as if it were placed in the cache',
1626 * except without unmapping it from the process address space.
1627 *
1628 * This routine may not block.
1629 */
1630static inline void
1631_vm_page_deactivate(vm_page_t m, int athead)
1632{
1633
1634	vm_page_lock_assert(m, MA_OWNED);
1635
1636	/*
1637	 * Ignore if already inactive.
1638	 */
1639	if (VM_PAGE_INQUEUE2(m, PQ_INACTIVE))
1640		return;
1641	if (m->wire_count == 0 && (m->flags & PG_UNMANAGED) == 0) {
1642		vm_page_lock_queues();
1643		vm_page_flag_clear(m, PG_WINATCFLS);
1644		vm_pageq_remove(m);
1645		if (athead)
1646			TAILQ_INSERT_HEAD(&vm_page_queues[PQ_INACTIVE].pl, m, pageq);
1647		else
1648			TAILQ_INSERT_TAIL(&vm_page_queues[PQ_INACTIVE].pl, m, pageq);
1649		VM_PAGE_SETQUEUE2(m, PQ_INACTIVE);
1650		cnt.v_inactive_count++;
1651		vm_page_unlock_queues();
1652	}
1653}
1654
1655/*
1656 * Move the specified page to the inactive queue.
1657 *
1658 * The page must be locked.
1659 */
1660void
1661vm_page_deactivate(vm_page_t m)
1662{
1663
1664	_vm_page_deactivate(m, 0);
1665}
1666
1667/*
1668 * vm_page_try_to_cache:
1669 *
1670 * Returns 0 on failure, 1 on success
1671 */
1672int
1673vm_page_try_to_cache(vm_page_t m)
1674{
1675
1676	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
1677	vm_page_lock_assert(m, MA_OWNED);
1678	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
1679	if (m->dirty || m->hold_count || m->busy || m->wire_count ||
1680	    (m->oflags & VPO_BUSY) || (m->flags & PG_UNMANAGED)) {
1681		return (0);
1682	}
1683	pmap_remove_all(m);
1684	if (m->dirty)
1685		return (0);
1686	vm_page_cache(m);
1687	return (1);
1688}
1689
1690/*
1691 * vm_page_try_to_free()
1692 *
1693 *	Attempt to free the page.  If we cannot free it, we do nothing.
1694 *	1 is returned on success, 0 on failure.
1695 */
1696int
1697vm_page_try_to_free(vm_page_t m)
1698{
1699
1700	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
1701	vm_page_lock_assert(m, MA_OWNED);
1702	if (m->object != NULL)
1703		VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
1704	if (m->dirty || m->hold_count || m->busy || m->wire_count ||
1705	    (m->oflags & VPO_BUSY) || (m->flags & PG_UNMANAGED)) {
1706		return (0);
1707	}
1708	pmap_remove_all(m);
1709	if (m->dirty)
1710		return (0);
1711	vm_page_free(m);
1712	return (1);
1713}
1714
1715/*
1716 * vm_page_cache
1717 *
1718 * Put the specified page onto the page cache queue (if appropriate).
1719 *
1720 * This routine may not block.
1721 */
1722void
1723vm_page_cache(vm_page_t m)
1724{
1725	vm_object_t object;
1726	vm_page_t root;
1727
1728	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
1729	vm_page_lock_assert(m, MA_OWNED);
1730	object = m->object;
1731	VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
1732	if ((m->flags & PG_UNMANAGED) || (m->oflags & VPO_BUSY) || m->busy ||
1733	    m->hold_count || m->wire_count) {
1734		panic("vm_page_cache: attempting to cache busy page");
1735	}
1736	pmap_remove_all(m);
1737	if (m->dirty != 0)
1738		panic("vm_page_cache: page %p is dirty", m);
1739	if (m->valid == 0 || object->type == OBJT_DEFAULT ||
1740	    (object->type == OBJT_SWAP &&
1741	    !vm_pager_has_page(object, m->pindex, NULL, NULL))) {
1742		/*
1743		 * Hypothesis: A cache-elgible page belonging to a
1744		 * default object or swap object but without a backing
1745		 * store must be zero filled.
1746		 */
1747		vm_page_free(m);
1748		return;
1749	}
1750	KASSERT((m->flags & PG_CACHED) == 0,
1751	    ("vm_page_cache: page %p is already cached", m));
1752	cnt.v_tcached++;
1753
1754	/*
1755	 * Remove the page from the paging queues.
1756	 */
1757	vm_pageq_remove(m);
1758
1759	/*
1760	 * Remove the page from the object's collection of resident
1761	 * pages.
1762	 */
1763	if (m != object->root)
1764		vm_page_splay(m->pindex, object->root);
1765	if (m->left == NULL)
1766		root = m->right;
1767	else {
1768		root = vm_page_splay(m->pindex, m->left);
1769		root->right = m->right;
1770	}
1771	object->root = root;
1772	TAILQ_REMOVE(&object->memq, m, listq);
1773	object->resident_page_count--;
1774	object->generation++;
1775
1776	/*
1777	 * Restore the default memory attribute to the page.
1778	 */
1779	if (pmap_page_get_memattr(m) != VM_MEMATTR_DEFAULT)
1780		pmap_page_set_memattr(m, VM_MEMATTR_DEFAULT);
1781
1782	/*
1783	 * Insert the page into the object's collection of cached pages
1784	 * and the physical memory allocator's cache/free page queues.
1785	 */
1786	vm_page_flag_clear(m, PG_ZERO);
1787	mtx_lock(&vm_page_queue_free_mtx);
1788	m->flags |= PG_CACHED;
1789	cnt.v_cache_count++;
1790	root = object->cache;
1791	if (root == NULL) {
1792		m->left = NULL;
1793		m->right = NULL;
1794	} else {
1795		root = vm_page_splay(m->pindex, root);
1796		if (m->pindex < root->pindex) {
1797			m->left = root->left;
1798			m->right = root;
1799			root->left = NULL;
1800		} else if (__predict_false(m->pindex == root->pindex))
1801			panic("vm_page_cache: offset already cached");
1802		else {
1803			m->right = root->right;
1804			m->left = root;
1805			root->right = NULL;
1806		}
1807	}
1808	object->cache = m;
1809#if VM_NRESERVLEVEL > 0
1810	if (!vm_reserv_free_page(m)) {
1811#else
1812	if (TRUE) {
1813#endif
1814		vm_phys_set_pool(VM_FREEPOOL_CACHE, m, 0);
1815		vm_phys_free_pages(m, 0);
1816	}
1817	vm_page_free_wakeup();
1818	mtx_unlock(&vm_page_queue_free_mtx);
1819
1820	/*
1821	 * Increment the vnode's hold count if this is the object's only
1822	 * cached page.  Decrement the vnode's hold count if this was
1823	 * the object's only resident page.
1824	 */
1825	if (object->type == OBJT_VNODE) {
1826		if (root == NULL && object->resident_page_count != 0)
1827			vhold(object->handle);
1828		else if (root != NULL && object->resident_page_count == 0)
1829			vdrop(object->handle);
1830	}
1831}
1832
1833/*
1834 * vm_page_dontneed
1835 *
1836 *	Cache, deactivate, or do nothing as appropriate.  This routine
1837 *	is typically used by madvise() MADV_DONTNEED.
1838 *
1839 *	Generally speaking we want to move the page into the cache so
1840 *	it gets reused quickly.  However, this can result in a silly syndrome
1841 *	due to the page recycling too quickly.  Small objects will not be
1842 *	fully cached.  On the otherhand, if we move the page to the inactive
1843 *	queue we wind up with a problem whereby very large objects
1844 *	unnecessarily blow away our inactive and cache queues.
1845 *
1846 *	The solution is to move the pages based on a fixed weighting.  We
1847 *	either leave them alone, deactivate them, or move them to the cache,
1848 *	where moving them to the cache has the highest weighting.
1849 *	By forcing some pages into other queues we eventually force the
1850 *	system to balance the queues, potentially recovering other unrelated
1851 *	space from active.  The idea is to not force this to happen too
1852 *	often.
1853 */
1854void
1855vm_page_dontneed(vm_page_t m)
1856{
1857	static int dnweight;
1858	int dnw;
1859	int head;
1860
1861	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
1862	vm_page_lock_assert(m, MA_OWNED);
1863	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
1864	dnw = ++dnweight;
1865
1866	/*
1867	 * occassionally leave the page alone
1868	 */
1869	if ((dnw & 0x01F0) == 0 ||
1870	    VM_PAGE_INQUEUE2(m, PQ_INACTIVE)) {
1871		if (m->act_count >= ACT_INIT)
1872			--m->act_count;
1873		return;
1874	}
1875
1876	/*
1877	 * Clear any references to the page.  Otherwise, the page daemon will
1878	 * immediately reactivate the page.
1879	 */
1880	vm_page_flag_clear(m, PG_REFERENCED);
1881	pmap_clear_reference(m);
1882
1883	if (m->dirty == 0 && pmap_is_modified(m))
1884		vm_page_dirty(m);
1885
1886	if (m->dirty || (dnw & 0x0070) == 0) {
1887		/*
1888		 * Deactivate the page 3 times out of 32.
1889		 */
1890		head = 0;
1891	} else {
1892		/*
1893		 * Cache the page 28 times out of every 32.  Note that
1894		 * the page is deactivated instead of cached, but placed
1895		 * at the head of the queue instead of the tail.
1896		 */
1897		head = 1;
1898	}
1899	_vm_page_deactivate(m, head);
1900}
1901
1902/*
1903 * Grab a page, waiting until we are waken up due to the page
1904 * changing state.  We keep on waiting, if the page continues
1905 * to be in the object.  If the page doesn't exist, first allocate it
1906 * and then conditionally zero it.
1907 *
1908 * This routine may block.
1909 */
1910vm_page_t
1911vm_page_grab(vm_object_t object, vm_pindex_t pindex, int allocflags)
1912{
1913	vm_page_t m;
1914
1915	VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
1916retrylookup:
1917	if ((m = vm_page_lookup(object, pindex)) != NULL) {
1918		if ((m->oflags & VPO_BUSY) != 0 || m->busy != 0) {
1919			if ((allocflags & VM_ALLOC_RETRY) != 0) {
1920				/*
1921				 * Reference the page before unlocking and
1922				 * sleeping so that the page daemon is less
1923				 * likely to reclaim it.
1924				 */
1925				vm_page_lock_queues();
1926				vm_page_flag_set(m, PG_REFERENCED);
1927			}
1928			vm_page_sleep(m, "pgrbwt");
1929			if ((allocflags & VM_ALLOC_RETRY) == 0)
1930				return (NULL);
1931			goto retrylookup;
1932		} else {
1933			if ((allocflags & VM_ALLOC_WIRED) != 0) {
1934				vm_page_lock(m);
1935				vm_page_wire(m);
1936				vm_page_unlock(m);
1937			}
1938			if ((allocflags & VM_ALLOC_NOBUSY) == 0)
1939				vm_page_busy(m);
1940			return (m);
1941		}
1942	}
1943	m = vm_page_alloc(object, pindex, allocflags & ~VM_ALLOC_RETRY);
1944	if (m == NULL) {
1945		VM_OBJECT_UNLOCK(object);
1946		VM_WAIT;
1947		VM_OBJECT_LOCK(object);
1948		if ((allocflags & VM_ALLOC_RETRY) == 0)
1949			return (NULL);
1950		goto retrylookup;
1951	} else if (m->valid != 0)
1952		return (m);
1953	if (allocflags & VM_ALLOC_ZERO && (m->flags & PG_ZERO) == 0)
1954		pmap_zero_page(m);
1955	return (m);
1956}
1957
1958/*
1959 * Mapping function for valid bits or for dirty bits in
1960 * a page.  May not block.
1961 *
1962 * Inputs are required to range within a page.
1963 */
1964int
1965vm_page_bits(int base, int size)
1966{
1967	int first_bit;
1968	int last_bit;
1969
1970	KASSERT(
1971	    base + size <= PAGE_SIZE,
1972	    ("vm_page_bits: illegal base/size %d/%d", base, size)
1973	);
1974
1975	if (size == 0)		/* handle degenerate case */
1976		return (0);
1977
1978	first_bit = base >> DEV_BSHIFT;
1979	last_bit = (base + size - 1) >> DEV_BSHIFT;
1980
1981	return ((2 << last_bit) - (1 << first_bit));
1982}
1983
1984/*
1985 *	vm_page_set_valid:
1986 *
1987 *	Sets portions of a page valid.  The arguments are expected
1988 *	to be DEV_BSIZE aligned but if they aren't the bitmap is inclusive
1989 *	of any partial chunks touched by the range.  The invalid portion of
1990 *	such chunks will be zeroed.
1991 *
1992 *	(base + size) must be less then or equal to PAGE_SIZE.
1993 */
1994void
1995vm_page_set_valid(vm_page_t m, int base, int size)
1996{
1997	int endoff, frag;
1998
1999	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
2000	if (size == 0)	/* handle degenerate case */
2001		return;
2002
2003	/*
2004	 * If the base is not DEV_BSIZE aligned and the valid
2005	 * bit is clear, we have to zero out a portion of the
2006	 * first block.
2007	 */
2008	if ((frag = base & ~(DEV_BSIZE - 1)) != base &&
2009	    (m->valid & (1 << (base >> DEV_BSHIFT))) == 0)
2010		pmap_zero_page_area(m, frag, base - frag);
2011
2012	/*
2013	 * If the ending offset is not DEV_BSIZE aligned and the
2014	 * valid bit is clear, we have to zero out a portion of
2015	 * the last block.
2016	 */
2017	endoff = base + size;
2018	if ((frag = endoff & ~(DEV_BSIZE - 1)) != endoff &&
2019	    (m->valid & (1 << (endoff >> DEV_BSHIFT))) == 0)
2020		pmap_zero_page_area(m, endoff,
2021		    DEV_BSIZE - (endoff & (DEV_BSIZE - 1)));
2022
2023	/*
2024	 * Assert that no previously invalid block that is now being validated
2025	 * is already dirty.
2026	 */
2027	KASSERT((~m->valid & vm_page_bits(base, size) & m->dirty) == 0,
2028	    ("vm_page_set_valid: page %p is dirty", m));
2029
2030	/*
2031	 * Set valid bits inclusive of any overlap.
2032	 */
2033	m->valid |= vm_page_bits(base, size);
2034}
2035
2036/*
2037 *	vm_page_set_validclean:
2038 *
2039 *	Sets portions of a page valid and clean.  The arguments are expected
2040 *	to be DEV_BSIZE aligned but if they aren't the bitmap is inclusive
2041 *	of any partial chunks touched by the range.  The invalid portion of
2042 *	such chunks will be zero'd.
2043 *
2044 *	This routine may not block.
2045 *
2046 *	(base + size) must be less then or equal to PAGE_SIZE.
2047 */
2048void
2049vm_page_set_validclean(vm_page_t m, int base, int size)
2050{
2051	int pagebits;
2052	int frag;
2053	int endoff;
2054
2055	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
2056	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
2057	if (size == 0)	/* handle degenerate case */
2058		return;
2059
2060	/*
2061	 * If the base is not DEV_BSIZE aligned and the valid
2062	 * bit is clear, we have to zero out a portion of the
2063	 * first block.
2064	 */
2065	if ((frag = base & ~(DEV_BSIZE - 1)) != base &&
2066	    (m->valid & (1 << (base >> DEV_BSHIFT))) == 0)
2067		pmap_zero_page_area(m, frag, base - frag);
2068
2069	/*
2070	 * If the ending offset is not DEV_BSIZE aligned and the
2071	 * valid bit is clear, we have to zero out a portion of
2072	 * the last block.
2073	 */
2074	endoff = base + size;
2075	if ((frag = endoff & ~(DEV_BSIZE - 1)) != endoff &&
2076	    (m->valid & (1 << (endoff >> DEV_BSHIFT))) == 0)
2077		pmap_zero_page_area(m, endoff,
2078		    DEV_BSIZE - (endoff & (DEV_BSIZE - 1)));
2079
2080	/*
2081	 * Set valid, clear dirty bits.  If validating the entire
2082	 * page we can safely clear the pmap modify bit.  We also
2083	 * use this opportunity to clear the VPO_NOSYNC flag.  If a process
2084	 * takes a write fault on a MAP_NOSYNC memory area the flag will
2085	 * be set again.
2086	 *
2087	 * We set valid bits inclusive of any overlap, but we can only
2088	 * clear dirty bits for DEV_BSIZE chunks that are fully within
2089	 * the range.
2090	 */
2091	pagebits = vm_page_bits(base, size);
2092	m->valid |= pagebits;
2093#if 0	/* NOT YET */
2094	if ((frag = base & (DEV_BSIZE - 1)) != 0) {
2095		frag = DEV_BSIZE - frag;
2096		base += frag;
2097		size -= frag;
2098		if (size < 0)
2099			size = 0;
2100	}
2101	pagebits = vm_page_bits(base, size & (DEV_BSIZE - 1));
2102#endif
2103	m->dirty &= ~pagebits;
2104	if (base == 0 && size == PAGE_SIZE) {
2105		pmap_clear_modify(m);
2106		m->oflags &= ~VPO_NOSYNC;
2107	}
2108}
2109
2110void
2111vm_page_clear_dirty(vm_page_t m, int base, int size)
2112{
2113
2114	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
2115	m->dirty &= ~vm_page_bits(base, size);
2116}
2117
2118/*
2119 *	vm_page_set_invalid:
2120 *
2121 *	Invalidates DEV_BSIZE'd chunks within a page.  Both the
2122 *	valid and dirty bits for the effected areas are cleared.
2123 *
2124 *	May not block.
2125 */
2126void
2127vm_page_set_invalid(vm_page_t m, int base, int size)
2128{
2129	int bits;
2130
2131	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
2132	bits = vm_page_bits(base, size);
2133	mtx_assert(&vm_page_queue_mtx, MA_OWNED);
2134	if (m->valid == VM_PAGE_BITS_ALL && bits != 0)
2135		pmap_remove_all(m);
2136	m->valid &= ~bits;
2137	m->dirty &= ~bits;
2138	m->object->generation++;
2139}
2140
2141/*
2142 * vm_page_zero_invalid()
2143 *
2144 *	The kernel assumes that the invalid portions of a page contain
2145 *	garbage, but such pages can be mapped into memory by user code.
2146 *	When this occurs, we must zero out the non-valid portions of the
2147 *	page so user code sees what it expects.
2148 *
2149 *	Pages are most often semi-valid when the end of a file is mapped
2150 *	into memory and the file's size is not page aligned.
2151 */
2152void
2153vm_page_zero_invalid(vm_page_t m, boolean_t setvalid)
2154{
2155	int b;
2156	int i;
2157
2158	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
2159	/*
2160	 * Scan the valid bits looking for invalid sections that
2161	 * must be zerod.  Invalid sub-DEV_BSIZE'd areas ( where the
2162	 * valid bit may be set ) have already been zerod by
2163	 * vm_page_set_validclean().
2164	 */
2165	for (b = i = 0; i <= PAGE_SIZE / DEV_BSIZE; ++i) {
2166		if (i == (PAGE_SIZE / DEV_BSIZE) ||
2167		    (m->valid & (1 << i))
2168		) {
2169			if (i > b) {
2170				pmap_zero_page_area(m,
2171				    b << DEV_BSHIFT, (i - b) << DEV_BSHIFT);
2172			}
2173			b = i + 1;
2174		}
2175	}
2176
2177	/*
2178	 * setvalid is TRUE when we can safely set the zero'd areas
2179	 * as being valid.  We can do this if there are no cache consistancy
2180	 * issues.  e.g. it is ok to do with UFS, but not ok to do with NFS.
2181	 */
2182	if (setvalid)
2183		m->valid = VM_PAGE_BITS_ALL;
2184}
2185
2186/*
2187 *	vm_page_is_valid:
2188 *
2189 *	Is (partial) page valid?  Note that the case where size == 0
2190 *	will return FALSE in the degenerate case where the page is
2191 *	entirely invalid, and TRUE otherwise.
2192 *
2193 *	May not block.
2194 */
2195int
2196vm_page_is_valid(vm_page_t m, int base, int size)
2197{
2198	int bits = vm_page_bits(base, size);
2199
2200	VM_OBJECT_LOCK_ASSERT(m->object, MA_OWNED);
2201	if (m->valid && ((m->valid & bits) == bits))
2202		return 1;
2203	else
2204		return 0;
2205}
2206
2207/*
2208 * update dirty bits from pmap/mmu.  May not block.
2209 */
2210void
2211vm_page_test_dirty(vm_page_t m)
2212{
2213	if ((m->dirty != VM_PAGE_BITS_ALL) && pmap_is_modified(m)) {
2214		vm_page_dirty(m);
2215	}
2216}
2217
2218int so_zerocp_fullpage = 0;
2219
2220/*
2221 *	Replace the given page with a copy.  The copied page assumes
2222 *	the portion of the given page's "wire_count" that is not the
2223 *	responsibility of this copy-on-write mechanism.
2224 *
2225 *	The object containing the given page must have a non-zero
2226 *	paging-in-progress count and be locked.
2227 */
2228void
2229vm_page_cowfault(vm_page_t m)
2230{
2231	vm_page_t mnew;
2232	vm_object_t object;
2233	vm_pindex_t pindex;
2234
2235	vm_page_lock_assert(m, MA_OWNED);
2236	object = m->object;
2237	VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
2238	KASSERT(object->paging_in_progress != 0,
2239	    ("vm_page_cowfault: object %p's paging-in-progress count is zero.",
2240	    object));
2241	pindex = m->pindex;
2242
2243 retry_alloc:
2244	pmap_remove_all(m);
2245	vm_page_unlock_queues();
2246	vm_page_remove(m);
2247	mnew = vm_page_alloc(object, pindex, VM_ALLOC_NORMAL | VM_ALLOC_NOBUSY);
2248	if (mnew == NULL) {
2249		vm_page_insert(m, object, pindex);
2250		vm_page_unlock(m);
2251		VM_OBJECT_UNLOCK(object);
2252		VM_WAIT;
2253		VM_OBJECT_LOCK(object);
2254		if (m == vm_page_lookup(object, pindex)) {
2255			vm_page_lock(m);
2256			vm_page_lock_queues();
2257			goto retry_alloc;
2258		} else {
2259			/*
2260			 * Page disappeared during the wait.
2261			 */
2262			return;
2263		}
2264	}
2265
2266	if (m->cow == 0) {
2267		/*
2268		 * check to see if we raced with an xmit complete when
2269		 * waiting to allocate a page.  If so, put things back
2270		 * the way they were
2271		 */
2272		vm_page_unlock(m);
2273		vm_page_lock(mnew);
2274		vm_page_lock_queues();
2275		vm_page_free(mnew);
2276		vm_page_unlock_queues();
2277		vm_page_unlock(mnew);
2278		vm_page_insert(m, object, pindex);
2279	} else { /* clear COW & copy page */
2280		if (!so_zerocp_fullpage)
2281			pmap_copy_page(m, mnew);
2282		mnew->valid = VM_PAGE_BITS_ALL;
2283		vm_page_dirty(mnew);
2284		mnew->wire_count = m->wire_count - m->cow;
2285		m->wire_count = m->cow;
2286		vm_page_unlock(m);
2287	}
2288}
2289
2290void
2291vm_page_cowclear(vm_page_t m)
2292{
2293
2294	vm_page_lock_assert(m, MA_OWNED);
2295	if (m->cow) {
2296		m->cow--;
2297		/*
2298		 * let vm_fault add back write permission  lazily
2299		 */
2300	}
2301	/*
2302	 *  sf_buf_free() will free the page, so we needn't do it here
2303	 */
2304}
2305
2306int
2307vm_page_cowsetup(vm_page_t m)
2308{
2309
2310	vm_page_lock_assert(m, MA_OWNED);
2311	if (m->cow == USHRT_MAX - 1)
2312		return (EBUSY);
2313	m->cow++;
2314	vm_page_lock_queues();
2315	pmap_remove_write(m);
2316	vm_page_unlock_queues();
2317	return (0);
2318}
2319
2320#include "opt_ddb.h"
2321#ifdef DDB
2322#include <sys/kernel.h>
2323
2324#include <ddb/ddb.h>
2325
2326DB_SHOW_COMMAND(page, vm_page_print_page_info)
2327{
2328	db_printf("cnt.v_free_count: %d\n", cnt.v_free_count);
2329	db_printf("cnt.v_cache_count: %d\n", cnt.v_cache_count);
2330	db_printf("cnt.v_inactive_count: %d\n", cnt.v_inactive_count);
2331	db_printf("cnt.v_active_count: %d\n", cnt.v_active_count);
2332	db_printf("cnt.v_wire_count: %d\n", cnt.v_wire_count);
2333	db_printf("cnt.v_free_reserved: %d\n", cnt.v_free_reserved);
2334	db_printf("cnt.v_free_min: %d\n", cnt.v_free_min);
2335	db_printf("cnt.v_free_target: %d\n", cnt.v_free_target);
2336	db_printf("cnt.v_cache_min: %d\n", cnt.v_cache_min);
2337	db_printf("cnt.v_inactive_target: %d\n", cnt.v_inactive_target);
2338}
2339
2340DB_SHOW_COMMAND(pageq, vm_page_print_pageq_info)
2341{
2342
2343	db_printf("PQ_FREE:");
2344	db_printf(" %d", cnt.v_free_count);
2345	db_printf("\n");
2346
2347	db_printf("PQ_CACHE:");
2348	db_printf(" %d", cnt.v_cache_count);
2349	db_printf("\n");
2350
2351	db_printf("PQ_ACTIVE: %d, PQ_INACTIVE: %d\n",
2352		*vm_page_queues[PQ_ACTIVE].cnt,
2353		*vm_page_queues[PQ_INACTIVE].cnt);
2354}
2355#endif /* DDB */
2356