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