91527c636c32a443d005f7a9b7bd518f2a9d6900
[dragonfly.git] / sys / vm / vm_page.c
1 /*
2  * (MPSAFE)
3  *
4  * Copyright (c) 1991 Regents of the University of California.
5  * All rights reserved.
6  *
7  * This code is derived from software contributed to Berkeley by
8  * The Mach Operating System project at Carnegie-Mellon University.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 4. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  *
34  *      from: @(#)vm_page.c     7.4 (Berkeley) 5/7/91
35  * $FreeBSD: src/sys/vm/vm_page.c,v 1.147.2.18 2002/03/10 05:03:19 alc Exp $
36  */
37
38 /*
39  * Copyright (c) 1987, 1990 Carnegie-Mellon University.
40  * All rights reserved.
41  *
42  * Authors: Avadis Tevanian, Jr., Michael Wayne Young
43  *
44  * Permission to use, copy, modify and distribute this software and
45  * its documentation is hereby granted, provided that both the copyright
46  * notice and this permission notice appear in all copies of the
47  * software, derivative works or modified versions, and any portions
48  * thereof, and that both notices appear in supporting documentation.
49  *
50  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
51  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
52  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
53  *
54  * Carnegie Mellon requests users of this software to return to
55  *
56  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
57  *  School of Computer Science
58  *  Carnegie Mellon University
59  *  Pittsburgh PA 15213-3890
60  *
61  * any improvements or extensions that they make and grant Carnegie the
62  * rights to redistribute these changes.
63  */
64 /*
65  * Resident memory management module.  The module manipulates 'VM pages'.
66  * A VM page is the core building block for memory management.
67  */
68
69 #include <sys/param.h>
70 #include <sys/systm.h>
71 #include <sys/malloc.h>
72 #include <sys/proc.h>
73 #include <sys/vmmeter.h>
74 #include <sys/vnode.h>
75 #include <sys/kernel.h>
76
77 #include <vm/vm.h>
78 #include <vm/vm_param.h>
79 #include <sys/lock.h>
80 #include <vm/vm_kern.h>
81 #include <vm/pmap.h>
82 #include <vm/vm_map.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 #include <vm/swap_pager.h>
89
90 #include <machine/md_var.h>
91
92 #include <vm/vm_page2.h>
93
94 #define VMACTION_HSIZE  256
95 #define VMACTION_HMASK  (VMACTION_HSIZE - 1)
96
97 static void vm_page_queue_init(void);
98 static void vm_page_free_wakeup(void);
99 static vm_page_t vm_page_select_cache(vm_object_t, vm_pindex_t);
100 static vm_page_t _vm_page_list_find2(int basequeue, int index);
101
102 struct vpgqueues vm_page_queues[PQ_COUNT]; /* Array of tailq lists */
103
104 LIST_HEAD(vm_page_action_list, vm_page_action);
105 struct vm_page_action_list      action_list[VMACTION_HSIZE];
106 static volatile int vm_pages_waiting;
107
108
109 RB_GENERATE2(vm_page_rb_tree, vm_page, rb_entry, rb_vm_page_compare,
110              vm_pindex_t, pindex);
111
112 static void
113 vm_page_queue_init(void) 
114 {
115         int i;
116
117         for (i = 0; i < PQ_L2_SIZE; i++)
118                 vm_page_queues[PQ_FREE+i].cnt = &vmstats.v_free_count;
119         for (i = 0; i < PQ_L2_SIZE; i++)
120                 vm_page_queues[PQ_CACHE+i].cnt = &vmstats.v_cache_count;
121
122         vm_page_queues[PQ_INACTIVE].cnt = &vmstats.v_inactive_count;
123         vm_page_queues[PQ_ACTIVE].cnt = &vmstats.v_active_count;
124         vm_page_queues[PQ_HOLD].cnt = &vmstats.v_active_count;
125         /* PQ_NONE has no queue */
126
127         for (i = 0; i < PQ_COUNT; i++)
128                 TAILQ_INIT(&vm_page_queues[i].pl);
129
130         for (i = 0; i < VMACTION_HSIZE; i++)
131                 LIST_INIT(&action_list[i]);
132 }
133
134 /*
135  * note: place in initialized data section?  Is this necessary?
136  */
137 long first_page = 0;
138 int vm_page_array_size = 0;
139 int vm_page_zero_count = 0;
140 vm_page_t vm_page_array = 0;
141
142 /*
143  * (low level boot)
144  *
145  * Sets the page size, perhaps based upon the memory size.
146  * Must be called before any use of page-size dependent functions.
147  */
148 void
149 vm_set_page_size(void)
150 {
151         if (vmstats.v_page_size == 0)
152                 vmstats.v_page_size = PAGE_SIZE;
153         if (((vmstats.v_page_size - 1) & vmstats.v_page_size) != 0)
154                 panic("vm_set_page_size: page size not a power of two");
155 }
156
157 /*
158  * (low level boot)
159  *
160  * Add a new page to the freelist for use by the system.  New pages
161  * are added to both the head and tail of the associated free page
162  * queue in a bottom-up fashion, so both zero'd and non-zero'd page
163  * requests pull 'recent' adds (higher physical addresses) first.
164  *
165  * Must be called in a critical section.
166  */
167 static vm_page_t
168 vm_add_new_page(vm_paddr_t pa)
169 {
170         struct vpgqueues *vpq;
171         vm_page_t m;
172
173         ++vmstats.v_page_count;
174         ++vmstats.v_free_count;
175         m = PHYS_TO_VM_PAGE(pa);
176         m->phys_addr = pa;
177         m->flags = 0;
178         m->pc = (pa >> PAGE_SHIFT) & PQ_L2_MASK;
179         m->queue = m->pc + PQ_FREE;
180         KKASSERT(m->dirty == 0);
181
182         vpq = &vm_page_queues[m->queue];
183         if (vpq->flipflop)
184                 TAILQ_INSERT_TAIL(&vpq->pl, m, pageq);
185         else
186                 TAILQ_INSERT_HEAD(&vpq->pl, m, pageq);
187         vpq->flipflop = 1 - vpq->flipflop;
188
189         vm_page_queues[m->queue].lcnt++;
190         return (m);
191 }
192
193 /*
194  * (low level boot)
195  *
196  * Initializes the resident memory module.
197  *
198  * Preallocates memory for critical VM structures and arrays prior to
199  * kernel_map becoming available.
200  *
201  * Memory is allocated from (virtual2_start, virtual2_end) if available,
202  * otherwise memory is allocated from (virtual_start, virtual_end).
203  *
204  * On x86-64 (virtual_start, virtual_end) is only 2GB and may not be
205  * large enough to hold vm_page_array & other structures for machines with
206  * large amounts of ram, so we want to use virtual2* when available.
207  */
208 void
209 vm_page_startup(void)
210 {
211         vm_offset_t vaddr = virtual2_start ? virtual2_start : virtual_start;
212         vm_offset_t mapped;
213         vm_size_t npages;
214         vm_paddr_t page_range;
215         vm_paddr_t new_end;
216         int i;
217         vm_paddr_t pa;
218         int nblocks;
219         vm_paddr_t last_pa;
220         vm_paddr_t end;
221         vm_paddr_t biggestone, biggestsize;
222         vm_paddr_t total;
223
224         total = 0;
225         biggestsize = 0;
226         biggestone = 0;
227         nblocks = 0;
228         vaddr = round_page(vaddr);
229
230         for (i = 0; phys_avail[i + 1]; i += 2) {
231                 phys_avail[i] = round_page64(phys_avail[i]);
232                 phys_avail[i + 1] = trunc_page64(phys_avail[i + 1]);
233         }
234
235         for (i = 0; phys_avail[i + 1]; i += 2) {
236                 vm_paddr_t size = phys_avail[i + 1] - phys_avail[i];
237
238                 if (size > biggestsize) {
239                         biggestone = i;
240                         biggestsize = size;
241                 }
242                 ++nblocks;
243                 total += size;
244         }
245
246         end = phys_avail[biggestone+1];
247         end = trunc_page(end);
248
249         /*
250          * Initialize the queue headers for the free queue, the active queue
251          * and the inactive queue.
252          */
253
254         vm_page_queue_init();
255
256         /* VKERNELs don't support minidumps and as such don't need vm_page_dump */
257 #if !defined(_KERNEL_VIRTUAL)
258         /*
259          * Allocate a bitmap to indicate that a random physical page
260          * needs to be included in a minidump.
261          *
262          * The amd64 port needs this to indicate which direct map pages
263          * need to be dumped, via calls to dump_add_page()/dump_drop_page().
264          *
265          * However, i386 still needs this workspace internally within the
266          * minidump code.  In theory, they are not needed on i386, but are
267          * included should the sf_buf code decide to use them.
268          */
269         page_range = phys_avail[(nblocks - 1) * 2 + 1] / PAGE_SIZE;
270         vm_page_dump_size = round_page(roundup2(page_range, NBBY) / NBBY);
271         end -= vm_page_dump_size;
272         vm_page_dump = (void *)pmap_map(&vaddr, end, end + vm_page_dump_size,
273             VM_PROT_READ | VM_PROT_WRITE);
274         bzero((void *)vm_page_dump, vm_page_dump_size);
275 #endif
276
277         /*
278          * Compute the number of pages of memory that will be available for
279          * use (taking into account the overhead of a page structure per
280          * page).
281          */
282         first_page = phys_avail[0] / PAGE_SIZE;
283         page_range = phys_avail[(nblocks - 1) * 2 + 1] / PAGE_SIZE - first_page;
284         npages = (total - (page_range * sizeof(struct vm_page))) / PAGE_SIZE;
285
286         /*
287          * Initialize the mem entry structures now, and put them in the free
288          * queue.
289          */
290         new_end = trunc_page(end - page_range * sizeof(struct vm_page));
291         mapped = pmap_map(&vaddr, new_end, end,
292             VM_PROT_READ | VM_PROT_WRITE);
293         vm_page_array = (vm_page_t)mapped;
294
295 #if defined(__x86_64__) && !defined(_KERNEL_VIRTUAL)
296         /*
297          * since pmap_map on amd64 returns stuff out of a direct-map region,
298          * we have to manually add these pages to the minidump tracking so
299          * that they can be dumped, including the vm_page_array.
300          */
301         for (pa = new_end; pa < phys_avail[biggestone + 1]; pa += PAGE_SIZE)
302                 dump_add_page(pa);
303 #endif
304
305         /*
306          * Clear all of the page structures
307          */
308         bzero((caddr_t) vm_page_array, page_range * sizeof(struct vm_page));
309         vm_page_array_size = page_range;
310
311         /*
312          * Construct the free queue(s) in ascending order (by physical
313          * address) so that the first 16MB of physical memory is allocated
314          * last rather than first.  On large-memory machines, this avoids
315          * the exhaustion of low physical memory before isa_dmainit has run.
316          */
317         vmstats.v_page_count = 0;
318         vmstats.v_free_count = 0;
319         for (i = 0; phys_avail[i + 1] && npages > 0; i += 2) {
320                 pa = phys_avail[i];
321                 if (i == biggestone)
322                         last_pa = new_end;
323                 else
324                         last_pa = phys_avail[i + 1];
325                 while (pa < last_pa && npages-- > 0) {
326                         vm_add_new_page(pa);
327                         pa += PAGE_SIZE;
328                 }
329         }
330         if (virtual2_start)
331                 virtual2_start = vaddr;
332         else
333                 virtual_start = vaddr;
334 }
335
336 /*
337  * Scan comparison function for Red-Black tree scans.  An inclusive
338  * (start,end) is expected.  Other fields are not used.
339  */
340 int
341 rb_vm_page_scancmp(struct vm_page *p, void *data)
342 {
343         struct rb_vm_page_scan_info *info = data;
344
345         if (p->pindex < info->start_pindex)
346                 return(-1);
347         if (p->pindex > info->end_pindex)
348                 return(1);
349         return(0);
350 }
351
352 int
353 rb_vm_page_compare(struct vm_page *p1, struct vm_page *p2)
354 {
355         if (p1->pindex < p2->pindex)
356                 return(-1);
357         if (p1->pindex > p2->pindex)
358                 return(1);
359         return(0);
360 }
361
362 /*
363  * Holding a page keeps it from being reused.  Other parts of the system
364  * can still disassociate the page from its current object and free it, or
365  * perform read or write I/O on it and/or otherwise manipulate the page,
366  * but if the page is held the VM system will leave the page and its data
367  * intact and not reuse the page for other purposes until the last hold
368  * reference is released.  (see vm_page_wire() if you want to prevent the
369  * page from being disassociated from its object too).
370  *
371  * The caller must hold vm_token.
372  *
373  * The caller must still validate the contents of the page and, if necessary,
374  * wait for any pending I/O (e.g. vm_page_sleep_busy() loop) to complete
375  * before manipulating the page.
376  */
377 void
378 vm_page_hold(vm_page_t m)
379 {
380         ASSERT_LWKT_TOKEN_HELD(&vm_token);
381         ++m->hold_count;
382 }
383
384 /*
385  * The opposite of vm_page_hold().  A page can be freed while being held,
386  * which places it on the PQ_HOLD queue.  We must call vm_page_free_toq()
387  * in this case to actually free it once the hold count drops to 0.
388  *
389  * The caller must hold vm_token if non-blocking operation is desired,
390  * but otherwise does not need to.
391  */
392 void
393 vm_page_unhold(vm_page_t m)
394 {
395         lwkt_gettoken(&vm_token);
396         --m->hold_count;
397         KASSERT(m->hold_count >= 0, ("vm_page_unhold: hold count < 0!!!"));
398         if (m->hold_count == 0 && m->queue == PQ_HOLD) {
399                 vm_page_busy(m);
400                 vm_page_free_toq(m);
401         }
402         lwkt_reltoken(&vm_token);
403 }
404
405 /*
406  * Inserts the given vm_page into the object and object list.
407  *
408  * The pagetables are not updated but will presumably fault the page
409  * in if necessary, or if a kernel page the caller will at some point
410  * enter the page into the kernel's pmap.  We are not allowed to block
411  * here so we *can't* do this anyway.
412  *
413  * This routine may not block.
414  * This routine must be called with the vm_token held.
415  * This routine must be called with the vm_object held.
416  * This routine must be called with a critical section held.
417  */
418 void
419 vm_page_insert(vm_page_t m, vm_object_t object, vm_pindex_t pindex)
420 {
421         ASSERT_LWKT_TOKEN_HELD(&vm_token);
422         if (m->object != NULL)
423                 panic("vm_page_insert: already inserted");
424
425         /*
426          * Record the object/offset pair in this page
427          */
428         m->object = object;
429         m->pindex = pindex;
430
431         /*
432          * Insert it into the object.
433          */
434         vm_page_rb_tree_RB_INSERT(&object->rb_memq, m);
435         object->generation++;
436
437         /*
438          * show that the object has one more resident page.
439          */
440         object->resident_page_count++;
441
442         /*
443          * Add the pv_list_cout of the page when its inserted in
444          * the object
445         */
446         object->agg_pv_list_count = object->agg_pv_list_count + m->md.pv_list_count;
447
448         /*
449          * Since we are inserting a new and possibly dirty page,
450          * update the object's OBJ_WRITEABLE and OBJ_MIGHTBEDIRTY flags.
451          */
452         if ((m->valid & m->dirty) || (m->flags & PG_WRITEABLE))
453                 vm_object_set_writeable_dirty(object);
454
455         /*
456          * Checks for a swap assignment and sets PG_SWAPPED if appropriate.
457          */
458         swap_pager_page_inserted(m);
459 }
460
461 /*
462  * Removes the given vm_page_t from the global (object,index) hash table
463  * and from the object's memq.
464  *
465  * The underlying pmap entry (if any) is NOT removed here.
466  * This routine may not block.
467  *
468  * The page must be BUSY and will remain BUSY on return.
469  * No other requirements.
470  *
471  * NOTE: FreeBSD side effect was to unbusy the page on return.  We leave
472  *       it busy.
473  */
474 void
475 vm_page_remove(vm_page_t m)
476 {
477         vm_object_t object;
478
479         lwkt_gettoken(&vm_token);
480         if (m->object == NULL) {
481                 lwkt_reltoken(&vm_token);
482                 return;
483         }
484
485         if ((m->flags & PG_BUSY) == 0)
486                 panic("vm_page_remove: page not busy");
487
488         object = m->object;
489
490         vm_object_hold(object);
491
492         /*
493          * Remove the page from the object and update the object.
494          */
495         vm_page_rb_tree_RB_REMOVE(&object->rb_memq, m);
496         object->resident_page_count--;
497         object->agg_pv_list_count = object->agg_pv_list_count - m->md.pv_list_count;
498         object->generation++;
499         m->object = NULL;
500
501         vm_object_drop(object);
502
503         lwkt_reltoken(&vm_token);
504 }
505
506 /*
507  * Locate and return the page at (object, pindex), or NULL if the
508  * page could not be found.
509  *
510  * The caller must hold vm_token.
511  */
512 vm_page_t
513 vm_page_lookup(vm_object_t object, vm_pindex_t pindex)
514 {
515         vm_page_t m;
516
517         /*
518          * Search the hash table for this object/offset pair
519          */
520         ASSERT_LWKT_TOKEN_HELD(&vm_token);
521         m = vm_page_rb_tree_RB_LOOKUP(&object->rb_memq, pindex);
522         KKASSERT(m == NULL || (m->object == object && m->pindex == pindex));
523         return(m);
524 }
525
526 /*
527  * vm_page_rename()
528  *
529  * Move the given memory entry from its current object to the specified
530  * target object/offset.
531  *
532  * The object must be locked.
533  * This routine may not block.
534  *
535  * Note: This routine will raise itself to splvm(), the caller need not. 
536  *
537  * Note: Swap associated with the page must be invalidated by the move.  We
538  *       have to do this for several reasons:  (1) we aren't freeing the
539  *       page, (2) we are dirtying the page, (3) the VM system is probably
540  *       moving the page from object A to B, and will then later move
541  *       the backing store from A to B and we can't have a conflict.
542  *
543  * Note: We *always* dirty the page.  It is necessary both for the
544  *       fact that we moved it, and because we may be invalidating
545  *       swap.  If the page is on the cache, we have to deactivate it
546  *       or vm_page_dirty() will panic.  Dirty pages are not allowed
547  *       on the cache.
548  */
549 void
550 vm_page_rename(vm_page_t m, vm_object_t new_object, vm_pindex_t new_pindex)
551 {
552         lwkt_gettoken(&vm_token);
553         vm_object_hold(new_object);
554         vm_page_remove(m);
555         vm_page_insert(m, new_object, new_pindex);
556         if (m->queue - m->pc == PQ_CACHE)
557                 vm_page_deactivate(m);
558         vm_page_dirty(m);
559         vm_page_wakeup(m);
560         vm_object_drop(new_object);
561         lwkt_reltoken(&vm_token);
562 }
563
564 /*
565  * vm_page_unqueue() without any wakeup.  This routine is used when a page
566  * is being moved between queues or otherwise is to remain BUSYied by the
567  * caller.
568  *
569  * The caller must hold vm_token
570  * This routine may not block.
571  */
572 void
573 vm_page_unqueue_nowakeup(vm_page_t m)
574 {
575         int queue = m->queue;
576         struct vpgqueues *pq;
577
578         ASSERT_LWKT_TOKEN_HELD(&vm_token);
579         if (queue != PQ_NONE) {
580                 pq = &vm_page_queues[queue];
581                 m->queue = PQ_NONE;
582                 TAILQ_REMOVE(&pq->pl, m, pageq);
583                 (*pq->cnt)--;
584                 pq->lcnt--;
585         }
586 }
587
588 /*
589  * vm_page_unqueue() - Remove a page from its queue, wakeup the pagedemon
590  * if necessary.
591  *
592  * The caller must hold vm_token
593  * This routine may not block.
594  */
595 void
596 vm_page_unqueue(vm_page_t m)
597 {
598         int queue = m->queue;
599         struct vpgqueues *pq;
600
601         ASSERT_LWKT_TOKEN_HELD(&vm_token);
602         if (queue != PQ_NONE) {
603                 m->queue = PQ_NONE;
604                 pq = &vm_page_queues[queue];
605                 TAILQ_REMOVE(&pq->pl, m, pageq);
606                 (*pq->cnt)--;
607                 pq->lcnt--;
608                 if ((queue - m->pc) == PQ_CACHE || (queue - m->pc) == PQ_FREE)
609                         pagedaemon_wakeup();
610         }
611 }
612
613 /*
614  * vm_page_list_find()
615  *
616  * Find a page on the specified queue with color optimization.
617  *
618  * The page coloring optimization attempts to locate a page that does
619  * not overload other nearby pages in the object in the cpu's L1 or L2
620  * caches.  We need this optimization because cpu caches tend to be
621  * physical caches, while object spaces tend to be virtual.
622  *
623  * Must be called with vm_token held.
624  * This routine may not block.
625  *
626  * Note that this routine is carefully inlined.  A non-inlined version
627  * is available for outside callers but the only critical path is
628  * from within this source file.
629  */
630 static __inline
631 vm_page_t
632 _vm_page_list_find(int basequeue, int index, boolean_t prefer_zero)
633 {
634         vm_page_t m;
635
636         if (prefer_zero)
637                 m = TAILQ_LAST(&vm_page_queues[basequeue+index].pl, pglist);
638         else
639                 m = TAILQ_FIRST(&vm_page_queues[basequeue+index].pl);
640         if (m == NULL)
641                 m = _vm_page_list_find2(basequeue, index);
642         return(m);
643 }
644
645 static vm_page_t
646 _vm_page_list_find2(int basequeue, int index)
647 {
648         int i;
649         vm_page_t m = NULL;
650         struct vpgqueues *pq;
651
652         pq = &vm_page_queues[basequeue];
653
654         /*
655          * Note that for the first loop, index+i and index-i wind up at the
656          * same place.  Even though this is not totally optimal, we've already
657          * blown it by missing the cache case so we do not care.
658          */
659
660         for(i = PQ_L2_SIZE / 2; i > 0; --i) {
661                 if ((m = TAILQ_FIRST(&pq[(index + i) & PQ_L2_MASK].pl)) != NULL)
662                         break;
663
664                 if ((m = TAILQ_FIRST(&pq[(index - i) & PQ_L2_MASK].pl)) != NULL)
665                         break;
666         }
667         return(m);
668 }
669
670 /*
671  * Must be called with vm_token held if the caller desired non-blocking
672  * operation and a stable result.
673  */
674 vm_page_t
675 vm_page_list_find(int basequeue, int index, boolean_t prefer_zero)
676 {
677         return(_vm_page_list_find(basequeue, index, prefer_zero));
678 }
679
680 /*
681  * Find a page on the cache queue with color optimization.  As pages
682  * might be found, but not applicable, they are deactivated.  This
683  * keeps us from using potentially busy cached pages.
684  *
685  * This routine may not block.
686  * Must be called with vm_token held.
687  */
688 vm_page_t
689 vm_page_select_cache(vm_object_t object, vm_pindex_t pindex)
690 {
691         vm_page_t m;
692
693         ASSERT_LWKT_TOKEN_HELD(&vm_token);
694         while (TRUE) {
695                 m = _vm_page_list_find(
696                     PQ_CACHE,
697                     (pindex + object->pg_color) & PQ_L2_MASK,
698                     FALSE
699                 );
700                 if (m && ((m->flags & (PG_BUSY|PG_UNMANAGED)) || m->busy ||
701                                m->hold_count || m->wire_count)) {
702                         /* cache page found busy */
703                         vm_page_deactivate(m);
704 #ifdef INVARIANTS
705                         kprintf("Warning: busy page %p found in cache\n", m);
706 #endif
707                         continue;
708                 }
709                 return m;
710         }
711         /* not reached */
712 }
713
714 /*
715  * Find a free or zero page, with specified preference.  We attempt to
716  * inline the nominal case and fall back to _vm_page_select_free() 
717  * otherwise.
718  *
719  * This routine must be called with a critical section held.
720  * This routine may not block.
721  */
722 static __inline vm_page_t
723 vm_page_select_free(vm_object_t object, vm_pindex_t pindex, boolean_t prefer_zero)
724 {
725         vm_page_t m;
726
727         m = _vm_page_list_find(
728                 PQ_FREE,
729                 (pindex + object->pg_color) & PQ_L2_MASK,
730                 prefer_zero
731         );
732         return(m);
733 }
734
735 /*
736  * vm_page_alloc()
737  *
738  * Allocate and return a memory cell associated with this VM object/offset
739  * pair.
740  *
741  *      page_req classes:
742  *
743  *      VM_ALLOC_NORMAL         allow use of cache pages, nominal free drain
744  *      VM_ALLOC_QUICK          like normal but cannot use cache
745  *      VM_ALLOC_SYSTEM         greater free drain
746  *      VM_ALLOC_INTERRUPT      allow free list to be completely drained
747  *      VM_ALLOC_ZERO           advisory request for pre-zero'd page
748  *
749  * The object must be locked.
750  * This routine may not block.
751  * The returned page will be marked PG_BUSY
752  *
753  * Additional special handling is required when called from an interrupt
754  * (VM_ALLOC_INTERRUPT).  We are not allowed to mess with the page cache
755  * in this case.
756  */
757 vm_page_t
758 vm_page_alloc(vm_object_t object, vm_pindex_t pindex, int page_req)
759 {
760         vm_page_t m = NULL;
761
762         lwkt_gettoken(&vm_token);
763         
764         KKASSERT(object != NULL);
765         KASSERT(!vm_page_lookup(object, pindex),
766                 ("vm_page_alloc: page already allocated"));
767         KKASSERT(page_req & 
768                 (VM_ALLOC_NORMAL|VM_ALLOC_QUICK|
769                  VM_ALLOC_INTERRUPT|VM_ALLOC_SYSTEM));
770
771         /*
772          * Certain system threads (pageout daemon, buf_daemon's) are
773          * allowed to eat deeper into the free page list.
774          */
775         if (curthread->td_flags & TDF_SYSTHREAD)
776                 page_req |= VM_ALLOC_SYSTEM;
777
778 loop:
779         if (vmstats.v_free_count > vmstats.v_free_reserved ||
780             ((page_req & VM_ALLOC_INTERRUPT) && vmstats.v_free_count > 0) ||
781             ((page_req & VM_ALLOC_SYSTEM) && vmstats.v_cache_count == 0 &&
782                 vmstats.v_free_count > vmstats.v_interrupt_free_min)
783         ) {
784                 /*
785                  * The free queue has sufficient free pages to take one out.
786                  */
787                 if (page_req & VM_ALLOC_ZERO)
788                         m = vm_page_select_free(object, pindex, TRUE);
789                 else
790                         m = vm_page_select_free(object, pindex, FALSE);
791         } else if (page_req & VM_ALLOC_NORMAL) {
792                 /*
793                  * Allocatable from the cache (non-interrupt only).  On
794                  * success, we must free the page and try again, thus
795                  * ensuring that vmstats.v_*_free_min counters are replenished.
796                  */
797 #ifdef INVARIANTS
798                 if (curthread->td_preempted) {
799                         kprintf("vm_page_alloc(): warning, attempt to allocate"
800                                 " cache page from preempting interrupt\n");
801                         m = NULL;
802                 } else {
803                         m = vm_page_select_cache(object, pindex);
804                 }
805 #else
806                 m = vm_page_select_cache(object, pindex);
807 #endif
808                 /*
809                  * On success move the page into the free queue and loop.
810                  */
811                 if (m != NULL) {
812                         KASSERT(m->dirty == 0,
813                             ("Found dirty cache page %p", m));
814                         vm_page_busy(m);
815                         vm_page_protect(m, VM_PROT_NONE);
816                         vm_page_free(m);
817                         goto loop;
818                 }
819
820                 /*
821                  * On failure return NULL
822                  */
823                 lwkt_reltoken(&vm_token);
824 #if defined(DIAGNOSTIC)
825                 if (vmstats.v_cache_count > 0)
826                         kprintf("vm_page_alloc(NORMAL): missing pages on cache queue: %d\n", vmstats.v_cache_count);
827 #endif
828                 vm_pageout_deficit++;
829                 pagedaemon_wakeup();
830                 return (NULL);
831         } else {
832                 /*
833                  * No pages available, wakeup the pageout daemon and give up.
834                  */
835                 lwkt_reltoken(&vm_token);
836                 vm_pageout_deficit++;
837                 pagedaemon_wakeup();
838                 return (NULL);
839         }
840
841         /*
842          * Good page found.  The page has not yet been busied.  We are in
843          * a critical section.
844          */
845         KASSERT(m != NULL, ("vm_page_alloc(): missing page on free queue\n"));
846         KASSERT(m->dirty == 0, 
847                 ("vm_page_alloc: free/cache page %p was dirty", m));
848
849         /*
850          * Remove from free queue
851          */
852         vm_page_unqueue_nowakeup(m);
853
854         /*
855          * Initialize structure.  Only the PG_ZERO flag is inherited.  Set
856          * the page PG_BUSY
857          */
858         if (m->flags & PG_ZERO) {
859                 vm_page_zero_count--;
860                 m->flags = PG_ZERO | PG_BUSY;
861         } else {
862                 m->flags = PG_BUSY;
863         }
864         m->wire_count = 0;
865         m->hold_count = 0;
866         m->act_count = 0;
867         m->busy = 0;
868         m->valid = 0;
869
870         /*
871          * vm_page_insert() is safe while holding vm_token.  Note also that
872          * inserting a page here does not insert it into the pmap (which
873          * could cause us to block allocating memory).  We cannot block 
874          * anywhere.
875          */
876         vm_page_insert(m, object, pindex);
877
878         /*
879          * Don't wakeup too often - wakeup the pageout daemon when
880          * we would be nearly out of memory.
881          */
882         pagedaemon_wakeup();
883
884         lwkt_reltoken(&vm_token);
885
886         /*
887          * A PG_BUSY page is returned.
888          */
889         return (m);
890 }
891
892 /*
893  * Wait for sufficient free memory for nominal heavy memory use kernel
894  * operations.
895  */
896 void
897 vm_wait_nominal(void)
898 {
899         while (vm_page_count_min(0))
900                 vm_wait(0);
901 }
902
903 /*
904  * Test if vm_wait_nominal() would block.
905  */
906 int
907 vm_test_nominal(void)
908 {
909         if (vm_page_count_min(0))
910                 return(1);
911         return(0);
912 }
913
914 /*
915  * Block until free pages are available for allocation, called in various
916  * places before memory allocations.
917  *
918  * The caller may loop if vm_page_count_min() == FALSE so we cannot be
919  * more generous then that.
920  */
921 void
922 vm_wait(int timo)
923 {
924         /*
925          * never wait forever
926          */
927         if (timo == 0)
928                 timo = hz;
929         lwkt_gettoken(&vm_token);
930
931         if (curthread == pagethread) {
932                 /*
933                  * The pageout daemon itself needs pages, this is bad.
934                  */
935                 if (vm_page_count_min(0)) {
936                         vm_pageout_pages_needed = 1;
937                         tsleep(&vm_pageout_pages_needed, 0, "VMWait", timo);
938                 }
939         } else {
940                 /*
941                  * Wakeup the pageout daemon if necessary and wait.
942                  */
943                 if (vm_page_count_target()) {
944                         if (vm_pages_needed == 0) {
945                                 vm_pages_needed = 1;
946                                 wakeup(&vm_pages_needed);
947                         }
948                         ++vm_pages_waiting;     /* SMP race ok */
949                         tsleep(&vmstats.v_free_count, 0, "vmwait", timo);
950                 }
951         }
952         lwkt_reltoken(&vm_token);
953 }
954
955 /*
956  * Block until free pages are available for allocation
957  *
958  * Called only from vm_fault so that processes page faulting can be
959  * easily tracked.
960  */
961 void
962 vm_waitpfault(void)
963 {
964         /*
965          * Wakeup the pageout daemon if necessary and wait.
966          */
967         if (vm_page_count_target()) {
968                 lwkt_gettoken(&vm_token);
969                 if (vm_page_count_target()) {
970                         if (vm_pages_needed == 0) {
971                                 vm_pages_needed = 1;
972                                 wakeup(&vm_pages_needed);
973                         }
974                         ++vm_pages_waiting;     /* SMP race ok */
975                         tsleep(&vmstats.v_free_count, 0, "pfault", hz);
976                 }
977                 lwkt_reltoken(&vm_token);
978         }
979 }
980
981 /*
982  * Put the specified page on the active list (if appropriate).  Ensure
983  * that act_count is at least ACT_INIT but do not otherwise mess with it.
984  *
985  * The page queues must be locked.
986  * This routine may not block.
987  */
988 void
989 vm_page_activate(vm_page_t m)
990 {
991         lwkt_gettoken(&vm_token);
992         if (m->queue != PQ_ACTIVE) {
993                 if ((m->queue - m->pc) == PQ_CACHE)
994                         mycpu->gd_cnt.v_reactivated++;
995
996                 vm_page_unqueue(m);
997
998                 if (m->wire_count == 0 && (m->flags & PG_UNMANAGED) == 0) {
999                         m->queue = PQ_ACTIVE;
1000                         vm_page_queues[PQ_ACTIVE].lcnt++;
1001                         TAILQ_INSERT_TAIL(&vm_page_queues[PQ_ACTIVE].pl,
1002                                             m, pageq);
1003                         if (m->act_count < ACT_INIT)
1004                                 m->act_count = ACT_INIT;
1005                         vmstats.v_active_count++;
1006                 }
1007         } else {
1008                 if (m->act_count < ACT_INIT)
1009                         m->act_count = ACT_INIT;
1010         }
1011         lwkt_reltoken(&vm_token);
1012 }
1013
1014 /*
1015  * Helper routine for vm_page_free_toq() and vm_page_cache().  This
1016  * routine is called when a page has been added to the cache or free
1017  * queues.
1018  *
1019  * This routine may not block.
1020  * This routine must be called at splvm()
1021  */
1022 static __inline void
1023 vm_page_free_wakeup(void)
1024 {
1025         /*
1026          * If the pageout daemon itself needs pages, then tell it that
1027          * there are some free.
1028          */
1029         if (vm_pageout_pages_needed &&
1030             vmstats.v_cache_count + vmstats.v_free_count >= 
1031             vmstats.v_pageout_free_min
1032         ) {
1033                 wakeup(&vm_pageout_pages_needed);
1034                 vm_pageout_pages_needed = 0;
1035         }
1036
1037         /*
1038          * Wakeup processes that are waiting on memory.
1039          *
1040          * NOTE: vm_paging_target() is the pageout daemon's target, while
1041          *       vm_page_count_target() is somewhere inbetween.  We want
1042          *       to wake processes up prior to the pageout daemon reaching
1043          *       its target to provide some hysteresis.
1044          */
1045         if (vm_pages_waiting) {
1046                 if (!vm_page_count_target()) {
1047                         /*
1048                          * Plenty of pages are free, wakeup everyone.
1049                          */
1050                         vm_pages_waiting = 0;
1051                         wakeup(&vmstats.v_free_count);
1052                         ++mycpu->gd_cnt.v_ppwakeups;
1053                 } else if (!vm_page_count_min(0)) {
1054                         /*
1055                          * Some pages are free, wakeup someone.
1056                          */
1057                         int wcount = vm_pages_waiting;
1058                         if (wcount > 0)
1059                                 --wcount;
1060                         vm_pages_waiting = wcount;
1061                         wakeup_one(&vmstats.v_free_count);
1062                         ++mycpu->gd_cnt.v_ppwakeups;
1063                 }
1064         }
1065 }
1066
1067 /*
1068  *      vm_page_free_toq:
1069  *
1070  *      Returns the given page to the PQ_FREE list, disassociating it with
1071  *      any VM object.
1072  *
1073  *      The vm_page must be PG_BUSY on entry.  PG_BUSY will be released on
1074  *      return (the page will have been freed).  No particular spl is required
1075  *      on entry.
1076  *
1077  *      This routine may not block.
1078  */
1079 void
1080 vm_page_free_toq(vm_page_t m)
1081 {
1082         struct vpgqueues *pq;
1083
1084         lwkt_gettoken(&vm_token);
1085         mycpu->gd_cnt.v_tfree++;
1086
1087         KKASSERT((m->flags & PG_MAPPED) == 0);
1088
1089         if (m->busy || ((m->queue - m->pc) == PQ_FREE)) {
1090                 kprintf(
1091                 "vm_page_free: pindex(%lu), busy(%d), PG_BUSY(%d), hold(%d)\n",
1092                     (u_long)m->pindex, m->busy, (m->flags & PG_BUSY) ? 1 : 0,
1093                     m->hold_count);
1094                 if ((m->queue - m->pc) == PQ_FREE)
1095                         panic("vm_page_free: freeing free page");
1096                 else
1097                         panic("vm_page_free: freeing busy page");
1098         }
1099
1100         /*
1101          * unqueue, then remove page.  Note that we cannot destroy
1102          * the page here because we do not want to call the pager's
1103          * callback routine until after we've put the page on the
1104          * appropriate free queue.
1105          */
1106         vm_page_unqueue_nowakeup(m);
1107         vm_page_remove(m);
1108
1109         /*
1110          * No further management of fictitious pages occurs beyond object
1111          * and queue removal.
1112          */
1113         if ((m->flags & PG_FICTITIOUS) != 0) {
1114                 vm_page_wakeup(m);
1115                 lwkt_reltoken(&vm_token);
1116                 return;
1117         }
1118
1119         m->valid = 0;
1120         vm_page_undirty(m);
1121
1122         if (m->wire_count != 0) {
1123                 if (m->wire_count > 1) {
1124                     panic(
1125                         "vm_page_free: invalid wire count (%d), pindex: 0x%lx",
1126                         m->wire_count, (long)m->pindex);
1127                 }
1128                 panic("vm_page_free: freeing wired page");
1129         }
1130
1131         /*
1132          * Clear the UNMANAGED flag when freeing an unmanaged page.
1133          */
1134         if (m->flags & PG_UNMANAGED) {
1135             vm_page_flag_clear(m, PG_UNMANAGED);
1136         }
1137
1138         if (m->hold_count != 0) {
1139                 vm_page_flag_clear(m, PG_ZERO);
1140                 m->queue = PQ_HOLD;
1141         } else {
1142                 m->queue = PQ_FREE + m->pc;
1143         }
1144         pq = &vm_page_queues[m->queue];
1145         pq->lcnt++;
1146         ++(*pq->cnt);
1147
1148         /*
1149          * Put zero'd pages on the end ( where we look for zero'd pages
1150          * first ) and non-zerod pages at the head.
1151          */
1152         if (m->flags & PG_ZERO) {
1153                 TAILQ_INSERT_TAIL(&pq->pl, m, pageq);
1154                 ++vm_page_zero_count;
1155         } else {
1156                 TAILQ_INSERT_HEAD(&pq->pl, m, pageq);
1157         }
1158         vm_page_wakeup(m);
1159         vm_page_free_wakeup();
1160         lwkt_reltoken(&vm_token);
1161 }
1162
1163 /*
1164  * vm_page_free_fromq_fast()
1165  *
1166  * Remove a non-zero page from one of the free queues; the page is removed for
1167  * zeroing, so do not issue a wakeup.
1168  *
1169  * MPUNSAFE
1170  */
1171 vm_page_t
1172 vm_page_free_fromq_fast(void)
1173 {
1174         static int qi;
1175         vm_page_t m;
1176         int i;
1177
1178         lwkt_gettoken(&vm_token);
1179         for (i = 0; i < PQ_L2_SIZE; ++i) {
1180                 m = vm_page_list_find(PQ_FREE, qi, FALSE);
1181                 qi = (qi + PQ_PRIME2) & PQ_L2_MASK;
1182                 if (m && (m->flags & PG_ZERO) == 0) {
1183                         KKASSERT(m->busy == 0 && (m->flags & PG_BUSY) == 0);
1184                         vm_page_unqueue_nowakeup(m);
1185                         vm_page_busy(m);
1186                         break;
1187                 }
1188                 m = NULL;
1189         }
1190         lwkt_reltoken(&vm_token);
1191         return (m);
1192 }
1193
1194 /*
1195  * vm_page_unmanage()
1196  *
1197  * Prevent PV management from being done on the page.  The page is
1198  * removed from the paging queues as if it were wired, and as a 
1199  * consequence of no longer being managed the pageout daemon will not
1200  * touch it (since there is no way to locate the pte mappings for the
1201  * page).  madvise() calls that mess with the pmap will also no longer
1202  * operate on the page.
1203  *
1204  * Beyond that the page is still reasonably 'normal'.  Freeing the page
1205  * will clear the flag.
1206  *
1207  * This routine is used by OBJT_PHYS objects - objects using unswappable
1208  * physical memory as backing store rather then swap-backed memory and
1209  * will eventually be extended to support 4MB unmanaged physical 
1210  * mappings.
1211  *
1212  * Must be called with a critical section held.
1213  * Must be called with vm_token held.
1214  */
1215 void
1216 vm_page_unmanage(vm_page_t m)
1217 {
1218         ASSERT_LWKT_TOKEN_HELD(&vm_token);
1219         if ((m->flags & PG_UNMANAGED) == 0) {
1220                 if (m->wire_count == 0)
1221                         vm_page_unqueue(m);
1222         }
1223         vm_page_flag_set(m, PG_UNMANAGED);
1224 }
1225
1226 /*
1227  * Mark this page as wired down by yet another map, removing it from
1228  * paging queues as necessary.
1229  *
1230  * The page queues must be locked.
1231  * This routine may not block.
1232  */
1233 void
1234 vm_page_wire(vm_page_t m)
1235 {
1236         /*
1237          * Only bump the wire statistics if the page is not already wired,
1238          * and only unqueue the page if it is on some queue (if it is unmanaged
1239          * it is already off the queues).  Don't do anything with fictitious
1240          * pages because they are always wired.
1241          */
1242         lwkt_gettoken(&vm_token);
1243         if ((m->flags & PG_FICTITIOUS) == 0) {
1244                 if (m->wire_count == 0) {
1245                         if ((m->flags & PG_UNMANAGED) == 0)
1246                                 vm_page_unqueue(m);
1247                         vmstats.v_wire_count++;
1248                 }
1249                 m->wire_count++;
1250                 KASSERT(m->wire_count != 0,
1251                         ("vm_page_wire: wire_count overflow m=%p", m));
1252         }
1253         lwkt_reltoken(&vm_token);
1254 }
1255
1256 /*
1257  * Release one wiring of this page, potentially enabling it to be paged again.
1258  *
1259  * Many pages placed on the inactive queue should actually go
1260  * into the cache, but it is difficult to figure out which.  What
1261  * we do instead, if the inactive target is well met, is to put
1262  * clean pages at the head of the inactive queue instead of the tail.
1263  * This will cause them to be moved to the cache more quickly and
1264  * if not actively re-referenced, freed more quickly.  If we just
1265  * stick these pages at the end of the inactive queue, heavy filesystem
1266  * meta-data accesses can cause an unnecessary paging load on memory bound 
1267  * processes.  This optimization causes one-time-use metadata to be
1268  * reused more quickly.
1269  *
1270  * BUT, if we are in a low-memory situation we have no choice but to
1271  * put clean pages on the cache queue.
1272  *
1273  * A number of routines use vm_page_unwire() to guarantee that the page
1274  * will go into either the inactive or active queues, and will NEVER
1275  * be placed in the cache - for example, just after dirtying a page.
1276  * dirty pages in the cache are not allowed.
1277  *
1278  * The page queues must be locked.
1279  * This routine may not block.
1280  */
1281 void
1282 vm_page_unwire(vm_page_t m, int activate)
1283 {
1284         lwkt_gettoken(&vm_token);
1285         if (m->flags & PG_FICTITIOUS) {
1286                 /* do nothing */
1287         } else if (m->wire_count <= 0) {
1288                 panic("vm_page_unwire: invalid wire count: %d", m->wire_count);
1289         } else {
1290                 if (--m->wire_count == 0) {
1291                         --vmstats.v_wire_count;
1292                         if (m->flags & PG_UNMANAGED) {
1293                                 ;
1294                         } else if (activate) {
1295                                 TAILQ_INSERT_TAIL(
1296                                     &vm_page_queues[PQ_ACTIVE].pl, m, pageq);
1297                                 m->queue = PQ_ACTIVE;
1298                                 vm_page_queues[PQ_ACTIVE].lcnt++;
1299                                 vmstats.v_active_count++;
1300                         } else {
1301                                 vm_page_flag_clear(m, PG_WINATCFLS);
1302                                 TAILQ_INSERT_TAIL(
1303                                     &vm_page_queues[PQ_INACTIVE].pl, m, pageq);
1304                                 m->queue = PQ_INACTIVE;
1305                                 vm_page_queues[PQ_INACTIVE].lcnt++;
1306                                 vmstats.v_inactive_count++;
1307                                 ++vm_swapcache_inactive_heuristic;
1308                         }
1309                 }
1310         }
1311         lwkt_reltoken(&vm_token);
1312 }
1313
1314
1315 /*
1316  * Move the specified page to the inactive queue.  If the page has
1317  * any associated swap, the swap is deallocated.
1318  *
1319  * Normally athead is 0 resulting in LRU operation.  athead is set
1320  * to 1 if we want this page to be 'as if it were placed in the cache',
1321  * except without unmapping it from the process address space.
1322  *
1323  * This routine may not block.
1324  * The caller must hold vm_token.
1325  */
1326 static __inline void
1327 _vm_page_deactivate(vm_page_t m, int athead)
1328 {
1329         /*
1330          * Ignore if already inactive.
1331          */
1332         if (m->queue == PQ_INACTIVE)
1333                 return;
1334
1335         if (m->wire_count == 0 && (m->flags & PG_UNMANAGED) == 0) {
1336                 if ((m->queue - m->pc) == PQ_CACHE)
1337                         mycpu->gd_cnt.v_reactivated++;
1338                 vm_page_flag_clear(m, PG_WINATCFLS);
1339                 vm_page_unqueue(m);
1340                 if (athead) {
1341                         TAILQ_INSERT_HEAD(&vm_page_queues[PQ_INACTIVE].pl,
1342                                           m, pageq);
1343                 } else {
1344                         TAILQ_INSERT_TAIL(&vm_page_queues[PQ_INACTIVE].pl,
1345                                           m, pageq);
1346                         ++vm_swapcache_inactive_heuristic;
1347                 }
1348                 m->queue = PQ_INACTIVE;
1349                 vm_page_queues[PQ_INACTIVE].lcnt++;
1350                 vmstats.v_inactive_count++;
1351         }
1352 }
1353
1354 /*
1355  * Attempt to deactivate a page.
1356  *
1357  * No requirements.
1358  */
1359 void
1360 vm_page_deactivate(vm_page_t m)
1361 {
1362         lwkt_gettoken(&vm_token);
1363         _vm_page_deactivate(m, 0);
1364         lwkt_reltoken(&vm_token);
1365 }
1366
1367 /*
1368  * Attempt to move a page to PQ_CACHE.
1369  * Returns 0 on failure, 1 on success
1370  *
1371  * No requirements.
1372  */
1373 int
1374 vm_page_try_to_cache(vm_page_t m)
1375 {
1376         lwkt_gettoken(&vm_token);
1377         if (m->dirty || m->hold_count || m->busy || m->wire_count ||
1378             (m->flags & (PG_BUSY|PG_UNMANAGED))) {
1379                 lwkt_reltoken(&vm_token);
1380                 return(0);
1381         }
1382         vm_page_busy(m);
1383         vm_page_test_dirty(m);
1384         if (m->dirty) {
1385                 vm_page_wakeup(m);
1386                 lwkt_reltoken(&vm_token);
1387                 return(0);
1388         }
1389         vm_page_cache(m);
1390         lwkt_reltoken(&vm_token);
1391         return(1);
1392 }
1393
1394 /*
1395  * Attempt to free the page.  If we cannot free it, we do nothing.
1396  * 1 is returned on success, 0 on failure.
1397  *
1398  * No requirements.
1399  */
1400 int
1401 vm_page_try_to_free(vm_page_t m)
1402 {
1403         lwkt_gettoken(&vm_token);
1404         if (m->dirty || m->hold_count || m->busy || m->wire_count ||
1405             (m->flags & (PG_BUSY|PG_UNMANAGED))) {
1406                 lwkt_reltoken(&vm_token);
1407                 return(0);
1408         }
1409         vm_page_test_dirty(m);
1410         if (m->dirty) {
1411                 lwkt_reltoken(&vm_token);
1412                 return(0);
1413         }
1414         vm_page_busy(m);
1415         vm_page_protect(m, VM_PROT_NONE);
1416         vm_page_free(m);
1417         lwkt_reltoken(&vm_token);
1418         return(1);
1419 }
1420
1421 /*
1422  * vm_page_cache
1423  *
1424  * Put the specified page onto the page cache queue (if appropriate).
1425  *
1426  * The caller must hold vm_token.
1427  * This routine may not block.
1428  * The page must be busy, and this routine will release the busy and
1429  * possibly even free the page.
1430  */
1431 void
1432 vm_page_cache(vm_page_t m)
1433 {
1434         ASSERT_LWKT_TOKEN_HELD(&vm_token);
1435
1436         if ((m->flags & PG_UNMANAGED) || m->busy ||
1437             m->wire_count || m->hold_count) {
1438                 kprintf("vm_page_cache: attempting to cache busy/held page\n");
1439                 vm_page_wakeup(m);
1440                 return;
1441         }
1442
1443         /*
1444          * Already in the cache (and thus not mapped)
1445          */
1446         if ((m->queue - m->pc) == PQ_CACHE) {
1447                 KKASSERT((m->flags & PG_MAPPED) == 0);
1448                 vm_page_wakeup(m);
1449                 return;
1450         }
1451
1452         /*
1453          * Caller is required to test m->dirty, but note that the act of
1454          * removing the page from its maps can cause it to become dirty
1455          * on an SMP system due to another cpu running in usermode.
1456          */
1457         if (m->dirty) {
1458                 panic("vm_page_cache: caching a dirty page, pindex: %ld",
1459                         (long)m->pindex);
1460         }
1461
1462         /*
1463          * Remove all pmaps and indicate that the page is not
1464          * writeable or mapped.  Our vm_page_protect() call may
1465          * have blocked (especially w/ VM_PROT_NONE), so recheck
1466          * everything.
1467          */
1468         vm_page_protect(m, VM_PROT_NONE);
1469         if ((m->flags & (PG_UNMANAGED|PG_MAPPED)) || m->busy ||
1470                         m->wire_count || m->hold_count) {
1471                 vm_page_wakeup(m);
1472         } else if (m->dirty) {
1473                 vm_page_deactivate(m);
1474                 vm_page_wakeup(m);
1475         } else {
1476                 vm_page_unqueue_nowakeup(m);
1477                 m->queue = PQ_CACHE + m->pc;
1478                 vm_page_queues[m->queue].lcnt++;
1479                 TAILQ_INSERT_TAIL(&vm_page_queues[m->queue].pl, m, pageq);
1480                 vmstats.v_cache_count++;
1481                 vm_page_wakeup(m);
1482                 vm_page_free_wakeup();
1483         }
1484 }
1485
1486 /*
1487  * vm_page_dontneed()
1488  *
1489  * Cache, deactivate, or do nothing as appropriate.  This routine
1490  * is typically used by madvise() MADV_DONTNEED.
1491  *
1492  * Generally speaking we want to move the page into the cache so
1493  * it gets reused quickly.  However, this can result in a silly syndrome
1494  * due to the page recycling too quickly.  Small objects will not be
1495  * fully cached.  On the otherhand, if we move the page to the inactive
1496  * queue we wind up with a problem whereby very large objects 
1497  * unnecessarily blow away our inactive and cache queues.
1498  *
1499  * The solution is to move the pages based on a fixed weighting.  We
1500  * either leave them alone, deactivate them, or move them to the cache,
1501  * where moving them to the cache has the highest weighting.
1502  * By forcing some pages into other queues we eventually force the
1503  * system to balance the queues, potentially recovering other unrelated
1504  * space from active.  The idea is to not force this to happen too
1505  * often.
1506  *
1507  * No requirements.
1508  */
1509 void
1510 vm_page_dontneed(vm_page_t m)
1511 {
1512         static int dnweight;
1513         int dnw;
1514         int head;
1515
1516         dnw = ++dnweight;
1517
1518         /*
1519          * occassionally leave the page alone
1520          */
1521         lwkt_gettoken(&vm_token);
1522         if ((dnw & 0x01F0) == 0 ||
1523             m->queue == PQ_INACTIVE || 
1524             m->queue - m->pc == PQ_CACHE
1525         ) {
1526                 if (m->act_count >= ACT_INIT)
1527                         --m->act_count;
1528                 lwkt_reltoken(&vm_token);
1529                 return;
1530         }
1531
1532         if (m->dirty == 0)
1533                 vm_page_test_dirty(m);
1534
1535         if (m->dirty || (dnw & 0x0070) == 0) {
1536                 /*
1537                  * Deactivate the page 3 times out of 32.
1538                  */
1539                 head = 0;
1540         } else {
1541                 /*
1542                  * Cache the page 28 times out of every 32.  Note that
1543                  * the page is deactivated instead of cached, but placed
1544                  * at the head of the queue instead of the tail.
1545                  */
1546                 head = 1;
1547         }
1548         _vm_page_deactivate(m, head);
1549         lwkt_reltoken(&vm_token);
1550 }
1551
1552 /*
1553  * Grab a page, blocking if it is busy and allocating a page if necessary.
1554  * A busy page is returned or NULL.
1555  *
1556  * If VM_ALLOC_RETRY is specified VM_ALLOC_NORMAL must also be specified.
1557  * If VM_ALLOC_RETRY is not specified
1558  *
1559  * This routine may block, but if VM_ALLOC_RETRY is not set then NULL is
1560  * always returned if we had blocked.  
1561  * This routine will never return NULL if VM_ALLOC_RETRY is set.
1562  * This routine may not be called from an interrupt.
1563  * The returned page may not be entirely valid.
1564  *
1565  * This routine may be called from mainline code without spl protection and
1566  * be guarenteed a busied page associated with the object at the specified
1567  * index.
1568  *
1569  * No requirements.
1570  */
1571 vm_page_t
1572 vm_page_grab(vm_object_t object, vm_pindex_t pindex, int allocflags)
1573 {
1574         vm_page_t m;
1575         int generation;
1576
1577         KKASSERT(allocflags &
1578                 (VM_ALLOC_NORMAL|VM_ALLOC_INTERRUPT|VM_ALLOC_SYSTEM));
1579         lwkt_gettoken(&vm_token);
1580         vm_object_hold(object);
1581 retrylookup:
1582         if ((m = vm_page_lookup(object, pindex)) != NULL) {
1583                 if (m->busy || (m->flags & PG_BUSY)) {
1584                         generation = object->generation;
1585
1586                         while ((object->generation == generation) &&
1587                                         (m->busy || (m->flags & PG_BUSY))) {
1588                                 vm_page_flag_set(m, PG_WANTED | PG_REFERENCED);
1589                                 tsleep(m, 0, "pgrbwt", 0);
1590                                 if ((allocflags & VM_ALLOC_RETRY) == 0) {
1591                                         m = NULL;
1592                                         goto done;
1593                                 }
1594                         }
1595                         goto retrylookup;
1596                 } else {
1597                         vm_page_busy(m);
1598                         goto done;
1599                 }
1600         }
1601         m = vm_page_alloc(object, pindex, allocflags & ~VM_ALLOC_RETRY);
1602         if (m == NULL) {
1603                 vm_wait(0);
1604                 if ((allocflags & VM_ALLOC_RETRY) == 0)
1605                         goto done;
1606                 goto retrylookup;
1607         }
1608 done:
1609         vm_object_drop(object);
1610         lwkt_reltoken(&vm_token);
1611         return(m);
1612 }
1613
1614 /*
1615  * Mapping function for valid bits or for dirty bits in
1616  * a page.  May not block.
1617  *
1618  * Inputs are required to range within a page.
1619  *
1620  * No requirements.
1621  * Non blocking.
1622  */
1623 int
1624 vm_page_bits(int base, int size)
1625 {
1626         int first_bit;
1627         int last_bit;
1628
1629         KASSERT(
1630             base + size <= PAGE_SIZE,
1631             ("vm_page_bits: illegal base/size %d/%d", base, size)
1632         );
1633
1634         if (size == 0)          /* handle degenerate case */
1635                 return(0);
1636
1637         first_bit = base >> DEV_BSHIFT;
1638         last_bit = (base + size - 1) >> DEV_BSHIFT;
1639
1640         return ((2 << last_bit) - (1 << first_bit));
1641 }
1642
1643 /*
1644  * Sets portions of a page valid and clean.  The arguments are expected
1645  * to be DEV_BSIZE aligned but if they aren't the bitmap is inclusive
1646  * of any partial chunks touched by the range.  The invalid portion of
1647  * such chunks will be zero'd.
1648  *
1649  * NOTE: When truncating a buffer vnode_pager_setsize() will automatically
1650  *       align base to DEV_BSIZE so as not to mark clean a partially
1651  *       truncated device block.  Otherwise the dirty page status might be
1652  *       lost.
1653  *
1654  * This routine may not block.
1655  *
1656  * (base + size) must be less then or equal to PAGE_SIZE.
1657  */
1658 static void
1659 _vm_page_zero_valid(vm_page_t m, int base, int size)
1660 {
1661         int frag;
1662         int endoff;
1663
1664         if (size == 0)  /* handle degenerate case */
1665                 return;
1666
1667         /*
1668          * If the base is not DEV_BSIZE aligned and the valid
1669          * bit is clear, we have to zero out a portion of the
1670          * first block.
1671          */
1672
1673         if ((frag = base & ~(DEV_BSIZE - 1)) != base &&
1674             (m->valid & (1 << (base >> DEV_BSHIFT))) == 0
1675         ) {
1676                 pmap_zero_page_area(
1677                     VM_PAGE_TO_PHYS(m),
1678                     frag,
1679                     base - frag
1680                 );
1681         }
1682
1683         /*
1684          * If the ending offset is not DEV_BSIZE aligned and the 
1685          * valid bit is clear, we have to zero out a portion of
1686          * the last block.
1687          */
1688
1689         endoff = base + size;
1690
1691         if ((frag = endoff & ~(DEV_BSIZE - 1)) != endoff &&
1692             (m->valid & (1 << (endoff >> DEV_BSHIFT))) == 0
1693         ) {
1694                 pmap_zero_page_area(
1695                     VM_PAGE_TO_PHYS(m),
1696                     endoff,
1697                     DEV_BSIZE - (endoff & (DEV_BSIZE - 1))
1698                 );
1699         }
1700 }
1701
1702 /*
1703  * Set valid, clear dirty bits.  If validating the entire
1704  * page we can safely clear the pmap modify bit.  We also
1705  * use this opportunity to clear the PG_NOSYNC flag.  If a process
1706  * takes a write fault on a MAP_NOSYNC memory area the flag will
1707  * be set again.
1708  *
1709  * We set valid bits inclusive of any overlap, but we can only
1710  * clear dirty bits for DEV_BSIZE chunks that are fully within
1711  * the range.
1712  *
1713  * Page must be busied?
1714  * No other requirements.
1715  */
1716 void
1717 vm_page_set_valid(vm_page_t m, int base, int size)
1718 {
1719         _vm_page_zero_valid(m, base, size);
1720         m->valid |= vm_page_bits(base, size);
1721 }
1722
1723
1724 /*
1725  * Set valid bits and clear dirty bits.
1726  *
1727  * NOTE: This function does not clear the pmap modified bit.
1728  *       Also note that e.g. NFS may use a byte-granular base
1729  *       and size.
1730  *
1731  * WARNING: Page must be busied?  But vfs_clean_one_page() will call
1732  *          this without necessarily busying the page (via bdwrite()).
1733  *          So for now vm_token must also be held.
1734  *
1735  * No other requirements.
1736  */
1737 void
1738 vm_page_set_validclean(vm_page_t m, int base, int size)
1739 {
1740         int pagebits;
1741
1742         _vm_page_zero_valid(m, base, size);
1743         pagebits = vm_page_bits(base, size);
1744         m->valid |= pagebits;
1745         m->dirty &= ~pagebits;
1746         if (base == 0 && size == PAGE_SIZE) {
1747                 /*pmap_clear_modify(m);*/
1748                 vm_page_flag_clear(m, PG_NOSYNC);
1749         }
1750 }
1751
1752 /*
1753  * Set valid & dirty.  Used by buwrite()
1754  *
1755  * WARNING: Page must be busied?  But vfs_dirty_one_page() will
1756  *          call this function in buwrite() so for now vm_token must
1757  *          be held.
1758  *
1759  * No other requirements.
1760  */
1761 void
1762 vm_page_set_validdirty(vm_page_t m, int base, int size)
1763 {
1764         int pagebits;
1765
1766         pagebits = vm_page_bits(base, size);
1767         m->valid |= pagebits;
1768         m->dirty |= pagebits;
1769         if (m->object)
1770                 vm_object_set_writeable_dirty(m->object);
1771 }
1772
1773 /*
1774  * Clear dirty bits.
1775  *
1776  * NOTE: This function does not clear the pmap modified bit.
1777  *       Also note that e.g. NFS may use a byte-granular base
1778  *       and size.
1779  *
1780  * Page must be busied?
1781  * No other requirements.
1782  */
1783 void
1784 vm_page_clear_dirty(vm_page_t m, int base, int size)
1785 {
1786         m->dirty &= ~vm_page_bits(base, size);
1787         if (base == 0 && size == PAGE_SIZE) {
1788                 /*pmap_clear_modify(m);*/
1789                 vm_page_flag_clear(m, PG_NOSYNC);
1790         }
1791 }
1792
1793 /*
1794  * Make the page all-dirty.
1795  *
1796  * Also make sure the related object and vnode reflect the fact that the
1797  * object may now contain a dirty page.
1798  *
1799  * Page must be busied?
1800  * No other requirements.
1801  */
1802 void
1803 vm_page_dirty(vm_page_t m)
1804 {
1805 #ifdef INVARIANTS
1806         int pqtype = m->queue - m->pc;
1807 #endif
1808         KASSERT(pqtype != PQ_CACHE && pqtype != PQ_FREE,
1809                 ("vm_page_dirty: page in free/cache queue!"));
1810         if (m->dirty != VM_PAGE_BITS_ALL) {
1811                 m->dirty = VM_PAGE_BITS_ALL;
1812                 if (m->object)
1813                         vm_object_set_writeable_dirty(m->object);
1814         }
1815 }
1816
1817 /*
1818  * Invalidates DEV_BSIZE'd chunks within a page.  Both the
1819  * valid and dirty bits for the effected areas are cleared.
1820  *
1821  * Page must be busied?
1822  * Does not block.
1823  * No other requirements.
1824  */
1825 void
1826 vm_page_set_invalid(vm_page_t m, int base, int size)
1827 {
1828         int bits;
1829
1830         bits = vm_page_bits(base, size);
1831         m->valid &= ~bits;
1832         m->dirty &= ~bits;
1833         m->object->generation++;
1834 }
1835
1836 /*
1837  * The kernel assumes that the invalid portions of a page contain 
1838  * garbage, but such pages can be mapped into memory by user code.
1839  * When this occurs, we must zero out the non-valid portions of the
1840  * page so user code sees what it expects.
1841  *
1842  * Pages are most often semi-valid when the end of a file is mapped 
1843  * into memory and the file's size is not page aligned.
1844  *
1845  * Page must be busied?
1846  * No other requirements.
1847  */
1848 void
1849 vm_page_zero_invalid(vm_page_t m, boolean_t setvalid)
1850 {
1851         int b;
1852         int i;
1853
1854         /*
1855          * Scan the valid bits looking for invalid sections that
1856          * must be zerod.  Invalid sub-DEV_BSIZE'd areas ( where the
1857          * valid bit may be set ) have already been zerod by
1858          * vm_page_set_validclean().
1859          */
1860         for (b = i = 0; i <= PAGE_SIZE / DEV_BSIZE; ++i) {
1861                 if (i == (PAGE_SIZE / DEV_BSIZE) || 
1862                     (m->valid & (1 << i))
1863                 ) {
1864                         if (i > b) {
1865                                 pmap_zero_page_area(
1866                                     VM_PAGE_TO_PHYS(m), 
1867                                     b << DEV_BSHIFT,
1868                                     (i - b) << DEV_BSHIFT
1869                                 );
1870                         }
1871                         b = i + 1;
1872                 }
1873         }
1874
1875         /*
1876          * setvalid is TRUE when we can safely set the zero'd areas
1877          * as being valid.  We can do this if there are no cache consistency
1878          * issues.  e.g. it is ok to do with UFS, but not ok to do with NFS.
1879          */
1880         if (setvalid)
1881                 m->valid = VM_PAGE_BITS_ALL;
1882 }
1883
1884 /*
1885  * Is a (partial) page valid?  Note that the case where size == 0
1886  * will return FALSE in the degenerate case where the page is entirely
1887  * invalid, and TRUE otherwise.
1888  *
1889  * Does not block.
1890  * No other requirements.
1891  */
1892 int
1893 vm_page_is_valid(vm_page_t m, int base, int size)
1894 {
1895         int bits = vm_page_bits(base, size);
1896
1897         if (m->valid && ((m->valid & bits) == bits))
1898                 return 1;
1899         else
1900                 return 0;
1901 }
1902
1903 /*
1904  * update dirty bits from pmap/mmu.  May not block.
1905  *
1906  * Caller must hold vm_token if non-blocking operation desired.
1907  * No other requirements.
1908  */
1909 void
1910 vm_page_test_dirty(vm_page_t m)
1911 {
1912         if ((m->dirty != VM_PAGE_BITS_ALL) && pmap_is_modified(m)) {
1913                 vm_page_dirty(m);
1914         }
1915 }
1916
1917 /*
1918  * Register an action, associating it with its vm_page
1919  */
1920 void
1921 vm_page_register_action(vm_page_action_t action, vm_page_event_t event)
1922 {
1923         struct vm_page_action_list *list;
1924         int hv;
1925
1926         hv = (int)((intptr_t)action->m >> 8) & VMACTION_HMASK;
1927         list = &action_list[hv];
1928
1929         lwkt_gettoken(&vm_token);
1930         vm_page_flag_set(action->m, PG_ACTIONLIST);
1931         action->event = event;
1932         LIST_INSERT_HEAD(list, action, entry);
1933         lwkt_reltoken(&vm_token);
1934 }
1935
1936 /*
1937  * Unregister an action, disassociating it from its related vm_page
1938  */
1939 void
1940 vm_page_unregister_action(vm_page_action_t action)
1941 {
1942         struct vm_page_action_list *list;
1943         int hv;
1944
1945         lwkt_gettoken(&vm_token);
1946         if (action->event != VMEVENT_NONE) {
1947                 action->event = VMEVENT_NONE;
1948                 LIST_REMOVE(action, entry);
1949
1950                 hv = (int)((intptr_t)action->m >> 8) & VMACTION_HMASK;
1951                 list = &action_list[hv];
1952                 if (LIST_EMPTY(list))
1953                         vm_page_flag_clear(action->m, PG_ACTIONLIST);
1954         }
1955         lwkt_reltoken(&vm_token);
1956 }
1957
1958 /*
1959  * Issue an event on a VM page.  Corresponding action structures are
1960  * removed from the page's list and called.
1961  *
1962  * If the vm_page has no more pending action events we clear its
1963  * PG_ACTIONLIST flag.
1964  */
1965 void
1966 vm_page_event_internal(vm_page_t m, vm_page_event_t event)
1967 {
1968         struct vm_page_action_list *list;
1969         struct vm_page_action *scan;
1970         struct vm_page_action *next;
1971         int hv;
1972         int all;
1973
1974         hv = (int)((intptr_t)m >> 8) & VMACTION_HMASK;
1975         list = &action_list[hv];
1976         all = 1;
1977
1978         lwkt_gettoken(&vm_token);
1979         LIST_FOREACH_MUTABLE(scan, list, entry, next) {
1980                 if (scan->m == m) {
1981                         if (scan->event == event) {
1982                                 scan->event = VMEVENT_NONE;
1983                                 LIST_REMOVE(scan, entry);
1984                                 scan->func(m, scan);
1985                                 /* XXX */
1986                         } else {
1987                                 all = 0;
1988                         }
1989                 }
1990         }
1991         if (all)
1992                 vm_page_flag_clear(m, PG_ACTIONLIST);
1993         lwkt_reltoken(&vm_token);
1994 }
1995
1996 #include "opt_ddb.h"
1997 #ifdef DDB
1998 #include <sys/kernel.h>
1999
2000 #include <ddb/ddb.h>
2001
2002 DB_SHOW_COMMAND(page, vm_page_print_page_info)
2003 {
2004         db_printf("vmstats.v_free_count: %d\n", vmstats.v_free_count);
2005         db_printf("vmstats.v_cache_count: %d\n", vmstats.v_cache_count);
2006         db_printf("vmstats.v_inactive_count: %d\n", vmstats.v_inactive_count);
2007         db_printf("vmstats.v_active_count: %d\n", vmstats.v_active_count);
2008         db_printf("vmstats.v_wire_count: %d\n", vmstats.v_wire_count);
2009         db_printf("vmstats.v_free_reserved: %d\n", vmstats.v_free_reserved);
2010         db_printf("vmstats.v_free_min: %d\n", vmstats.v_free_min);
2011         db_printf("vmstats.v_free_target: %d\n", vmstats.v_free_target);
2012         db_printf("vmstats.v_cache_min: %d\n", vmstats.v_cache_min);
2013         db_printf("vmstats.v_inactive_target: %d\n", vmstats.v_inactive_target);
2014 }
2015
2016 DB_SHOW_COMMAND(pageq, vm_page_print_pageq_info)
2017 {
2018         int i;
2019         db_printf("PQ_FREE:");
2020         for(i=0;i<PQ_L2_SIZE;i++) {
2021                 db_printf(" %d", vm_page_queues[PQ_FREE + i].lcnt);
2022         }
2023         db_printf("\n");
2024                 
2025         db_printf("PQ_CACHE:");
2026         for(i=0;i<PQ_L2_SIZE;i++) {
2027                 db_printf(" %d", vm_page_queues[PQ_CACHE + i].lcnt);
2028         }
2029         db_printf("\n");
2030
2031         db_printf("PQ_ACTIVE: %d, PQ_INACTIVE: %d\n",
2032                 vm_page_queues[PQ_ACTIVE].lcnt,
2033                 vm_page_queues[PQ_INACTIVE].lcnt);
2034 }
2035 #endif /* DDB */