The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/vm/vm_page.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: 4deafc2a21f65735ab8ae82312651884


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.