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