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_reserv.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) 2002-2006 Rice University
    3  * Copyright (c) 2007-2011 Alan L. Cox <alc@cs.rice.edu>
    4  * All rights reserved.
    5  *
    6  * This software was developed for the FreeBSD Project by Alan L. Cox,
    7  * Olivier Crameri, Peter Druschel, Sitaram Iyer, and Juan Navarro.
    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  *
   18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   19  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   21  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
   22  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   24  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
   25  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
   26  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
   28  * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   29  * POSSIBILITY OF SUCH DAMAGE.
   30  */
   31 
   32 /*
   33  *      Superpage reservation management module
   34  *
   35  * Any external functions defined by this module are only to be used by the
   36  * virtual memory system.
   37  */
   38 
   39 #include <sys/cdefs.h>
   40 __FBSDID("$FreeBSD: releng/11.2/sys/vm/vm_reserv.c 331017 2018-03-15 19:08:33Z kevans $");
   41 
   42 #include "opt_vm.h"
   43 
   44 #include <sys/param.h>
   45 #include <sys/kernel.h>
   46 #include <sys/lock.h>
   47 #include <sys/malloc.h>
   48 #include <sys/mutex.h>
   49 #include <sys/queue.h>
   50 #include <sys/rwlock.h>
   51 #include <sys/sbuf.h>
   52 #include <sys/sysctl.h>
   53 #include <sys/systm.h>
   54 #include <sys/vmmeter.h>
   55 
   56 #include <vm/vm.h>
   57 #include <vm/vm_param.h>
   58 #include <vm/vm_object.h>
   59 #include <vm/vm_page.h>
   60 #include <vm/vm_phys.h>
   61 #include <vm/vm_radix.h>
   62 #include <vm/vm_reserv.h>
   63 
   64 /*
   65  * The reservation system supports the speculative allocation of large physical
   66  * pages ("superpages").  Speculative allocation enables the fully automatic
   67  * utilization of superpages by the virtual memory system.  In other words, no
   68  * programmatic directives are required to use superpages.
   69  */
   70 
   71 #if VM_NRESERVLEVEL > 0
   72 
   73 /*
   74  * The number of small pages that are contained in a level 0 reservation
   75  */
   76 #define VM_LEVEL_0_NPAGES       (1 << VM_LEVEL_0_ORDER)
   77 
   78 /*
   79  * The number of bits by which a physical address is shifted to obtain the
   80  * reservation number
   81  */
   82 #define VM_LEVEL_0_SHIFT        (VM_LEVEL_0_ORDER + PAGE_SHIFT)
   83 
   84 /*
   85  * The size of a level 0 reservation in bytes
   86  */
   87 #define VM_LEVEL_0_SIZE         (1 << VM_LEVEL_0_SHIFT)
   88 
   89 /*
   90  * Computes the index of the small page underlying the given (object, pindex)
   91  * within the reservation's array of small pages.
   92  */
   93 #define VM_RESERV_INDEX(object, pindex) \
   94     (((object)->pg_color + (pindex)) & (VM_LEVEL_0_NPAGES - 1))
   95 
   96 /*
   97  * The size of a population map entry
   98  */
   99 typedef u_long          popmap_t;
  100 
  101 /*
  102  * The number of bits in a population map entry
  103  */
  104 #define NBPOPMAP        (NBBY * sizeof(popmap_t))
  105 
  106 /*
  107  * The number of population map entries in a reservation
  108  */
  109 #define NPOPMAP         howmany(VM_LEVEL_0_NPAGES, NBPOPMAP)
  110 
  111 /*
  112  * Clear a bit in the population map.
  113  */
  114 static __inline void
  115 popmap_clear(popmap_t popmap[], int i)
  116 {
  117 
  118         popmap[i / NBPOPMAP] &= ~(1UL << (i % NBPOPMAP));
  119 }
  120 
  121 /*
  122  * Set a bit in the population map.
  123  */
  124 static __inline void
  125 popmap_set(popmap_t popmap[], int i)
  126 {
  127 
  128         popmap[i / NBPOPMAP] |= 1UL << (i % NBPOPMAP);
  129 }
  130 
  131 /*
  132  * Is a bit in the population map clear?
  133  */
  134 static __inline boolean_t
  135 popmap_is_clear(popmap_t popmap[], int i)
  136 {
  137 
  138         return ((popmap[i / NBPOPMAP] & (1UL << (i % NBPOPMAP))) == 0);
  139 }
  140 
  141 /*
  142  * Is a bit in the population map set?
  143  */
  144 static __inline boolean_t
  145 popmap_is_set(popmap_t popmap[], int i)
  146 {
  147 
  148         return ((popmap[i / NBPOPMAP] & (1UL << (i % NBPOPMAP))) != 0);
  149 }
  150 
  151 /*
  152  * The reservation structure
  153  *
  154  * A reservation structure is constructed whenever a large physical page is
  155  * speculatively allocated to an object.  The reservation provides the small
  156  * physical pages for the range [pindex, pindex + VM_LEVEL_0_NPAGES) of offsets
  157  * within that object.  The reservation's "popcnt" tracks the number of these
  158  * small physical pages that are in use at any given time.  When and if the
  159  * reservation is not fully utilized, it appears in the queue of partially
  160  * populated reservations.  The reservation always appears on the containing
  161  * object's list of reservations.
  162  *
  163  * A partially populated reservation can be broken and reclaimed at any time.
  164  */
  165 struct vm_reserv {
  166         TAILQ_ENTRY(vm_reserv) partpopq;
  167         LIST_ENTRY(vm_reserv) objq;
  168         vm_object_t     object;                 /* containing object */
  169         vm_pindex_t     pindex;                 /* offset within object */
  170         vm_page_t       pages;                  /* first page of a superpage */
  171         int             popcnt;                 /* # of pages in use */
  172         char            inpartpopq;
  173         popmap_t        popmap[NPOPMAP];        /* bit vector of used pages */
  174 };
  175 
  176 /*
  177  * The reservation array
  178  *
  179  * This array is analoguous in function to vm_page_array.  It differs in the
  180  * respect that it may contain a greater number of useful reservation
  181  * structures than there are (physical) superpages.  These "invalid"
  182  * reservation structures exist to trade-off space for time in the
  183  * implementation of vm_reserv_from_page().  Invalid reservation structures are
  184  * distinguishable from "valid" reservation structures by inspecting the
  185  * reservation's "pages" field.  Invalid reservation structures have a NULL
  186  * "pages" field.
  187  *
  188  * vm_reserv_from_page() maps a small (physical) page to an element of this
  189  * array by computing a physical reservation number from the page's physical
  190  * address.  The physical reservation number is used as the array index.
  191  *
  192  * An "active" reservation is a valid reservation structure that has a non-NULL
  193  * "object" field and a non-zero "popcnt" field.  In other words, every active
  194  * reservation belongs to a particular object.  Moreover, every active
  195  * reservation has an entry in the containing object's list of reservations.  
  196  */
  197 static vm_reserv_t vm_reserv_array;
  198 
  199 /*
  200  * The partially populated reservation queue
  201  *
  202  * This queue enables the fast recovery of an unused free small page from a
  203  * partially populated reservation.  The reservation at the head of this queue
  204  * is the least recently changed, partially populated reservation.
  205  *
  206  * Access to this queue is synchronized by the free page queue lock.
  207  */
  208 static TAILQ_HEAD(, vm_reserv) vm_rvq_partpop =
  209                             TAILQ_HEAD_INITIALIZER(vm_rvq_partpop);
  210 
  211 static SYSCTL_NODE(_vm, OID_AUTO, reserv, CTLFLAG_RD, 0, "Reservation Info");
  212 
  213 static long vm_reserv_broken;
  214 SYSCTL_LONG(_vm_reserv, OID_AUTO, broken, CTLFLAG_RD,
  215     &vm_reserv_broken, 0, "Cumulative number of broken reservations");
  216 
  217 static long vm_reserv_freed;
  218 SYSCTL_LONG(_vm_reserv, OID_AUTO, freed, CTLFLAG_RD,
  219     &vm_reserv_freed, 0, "Cumulative number of freed reservations");
  220 
  221 static int sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS);
  222 
  223 SYSCTL_PROC(_vm_reserv, OID_AUTO, fullpop, CTLTYPE_INT | CTLFLAG_RD, NULL, 0,
  224     sysctl_vm_reserv_fullpop, "I", "Current number of full reservations");
  225 
  226 static int sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS);
  227 
  228 SYSCTL_OID(_vm_reserv, OID_AUTO, partpopq, CTLTYPE_STRING | CTLFLAG_RD, NULL, 0,
  229     sysctl_vm_reserv_partpopq, "A", "Partially populated reservation queues");
  230 
  231 static long vm_reserv_reclaimed;
  232 SYSCTL_LONG(_vm_reserv, OID_AUTO, reclaimed, CTLFLAG_RD,
  233     &vm_reserv_reclaimed, 0, "Cumulative number of reclaimed reservations");
  234 
  235 static void             vm_reserv_break(vm_reserv_t rv);
  236 static void             vm_reserv_depopulate(vm_reserv_t rv, int index);
  237 static vm_reserv_t      vm_reserv_from_page(vm_page_t m);
  238 static boolean_t        vm_reserv_has_pindex(vm_reserv_t rv,
  239                             vm_pindex_t pindex);
  240 static void             vm_reserv_populate(vm_reserv_t rv, int index);
  241 static void             vm_reserv_reclaim(vm_reserv_t rv);
  242 
  243 /*
  244  * Returns the current number of full reservations.
  245  *
  246  * Since the number of full reservations is computed without acquiring the
  247  * free page queue lock, the returned value may be inexact.
  248  */
  249 static int
  250 sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS)
  251 {
  252         vm_paddr_t paddr;
  253         struct vm_phys_seg *seg;
  254         vm_reserv_t rv;
  255         int fullpop, segind;
  256 
  257         fullpop = 0;
  258         for (segind = 0; segind < vm_phys_nsegs; segind++) {
  259                 seg = &vm_phys_segs[segind];
  260                 paddr = roundup2(seg->start, VM_LEVEL_0_SIZE);
  261                 while (paddr + VM_LEVEL_0_SIZE <= seg->end) {
  262                         rv = &vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT];
  263                         fullpop += rv->popcnt == VM_LEVEL_0_NPAGES;
  264                         paddr += VM_LEVEL_0_SIZE;
  265                 }
  266         }
  267         return (sysctl_handle_int(oidp, &fullpop, 0, req));
  268 }
  269 
  270 /*
  271  * Describes the current state of the partially populated reservation queue.
  272  */
  273 static int
  274 sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS)
  275 {
  276         struct sbuf sbuf;
  277         vm_reserv_t rv;
  278         int counter, error, level, unused_pages;
  279 
  280         error = sysctl_wire_old_buffer(req, 0);
  281         if (error != 0)
  282                 return (error);
  283         sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
  284         sbuf_printf(&sbuf, "\nLEVEL     SIZE  NUMBER\n\n");
  285         for (level = -1; level <= VM_NRESERVLEVEL - 2; level++) {
  286                 counter = 0;
  287                 unused_pages = 0;
  288                 mtx_lock(&vm_page_queue_free_mtx);
  289                 TAILQ_FOREACH(rv, &vm_rvq_partpop/*[level]*/, partpopq) {
  290                         counter++;
  291                         unused_pages += VM_LEVEL_0_NPAGES - rv->popcnt;
  292                 }
  293                 mtx_unlock(&vm_page_queue_free_mtx);
  294                 sbuf_printf(&sbuf, "%5d: %6dK, %6d\n", level,
  295                     unused_pages * ((int)PAGE_SIZE / 1024), counter);
  296         }
  297         error = sbuf_finish(&sbuf);
  298         sbuf_delete(&sbuf);
  299         return (error);
  300 }
  301 
  302 /*
  303  * Reduces the given reservation's population count.  If the population count
  304  * becomes zero, the reservation is destroyed.  Additionally, moves the
  305  * reservation to the tail of the partially populated reservation queue if the
  306  * population count is non-zero.
  307  *
  308  * The free page queue lock must be held.
  309  */
  310 static void
  311 vm_reserv_depopulate(vm_reserv_t rv, int index)
  312 {
  313 
  314         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  315         KASSERT(rv->object != NULL,
  316             ("vm_reserv_depopulate: reserv %p is free", rv));
  317         KASSERT(popmap_is_set(rv->popmap, index),
  318             ("vm_reserv_depopulate: reserv %p's popmap[%d] is clear", rv,
  319             index));
  320         KASSERT(rv->popcnt > 0,
  321             ("vm_reserv_depopulate: reserv %p's popcnt is corrupted", rv));
  322         if (rv->inpartpopq) {
  323                 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
  324                 rv->inpartpopq = FALSE;
  325         } else {
  326                 KASSERT(rv->pages->psind == 1,
  327                     ("vm_reserv_depopulate: reserv %p is already demoted",
  328                     rv));
  329                 rv->pages->psind = 0;
  330         }
  331         popmap_clear(rv->popmap, index);
  332         rv->popcnt--;
  333         if (rv->popcnt == 0) {
  334                 LIST_REMOVE(rv, objq);
  335                 rv->object = NULL;
  336                 vm_phys_free_pages(rv->pages, VM_LEVEL_0_ORDER);
  337                 vm_reserv_freed++;
  338         } else {
  339                 rv->inpartpopq = TRUE;
  340                 TAILQ_INSERT_TAIL(&vm_rvq_partpop, rv, partpopq);
  341         }
  342 }
  343 
  344 /*
  345  * Returns the reservation to which the given page might belong.
  346  */
  347 static __inline vm_reserv_t
  348 vm_reserv_from_page(vm_page_t m)
  349 {
  350 
  351         return (&vm_reserv_array[VM_PAGE_TO_PHYS(m) >> VM_LEVEL_0_SHIFT]);
  352 }
  353 
  354 /*
  355  * Returns TRUE if the given reservation contains the given page index and
  356  * FALSE otherwise.
  357  */
  358 static __inline boolean_t
  359 vm_reserv_has_pindex(vm_reserv_t rv, vm_pindex_t pindex)
  360 {
  361 
  362         return (((pindex - rv->pindex) & ~(VM_LEVEL_0_NPAGES - 1)) == 0);
  363 }
  364 
  365 /*
  366  * Increases the given reservation's population count.  Moves the reservation
  367  * to the tail of the partially populated reservation queue.
  368  *
  369  * The free page queue must be locked.
  370  */
  371 static void
  372 vm_reserv_populate(vm_reserv_t rv, int index)
  373 {
  374 
  375         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  376         KASSERT(rv->object != NULL,
  377             ("vm_reserv_populate: reserv %p is free", rv));
  378         KASSERT(popmap_is_clear(rv->popmap, index),
  379             ("vm_reserv_populate: reserv %p's popmap[%d] is set", rv,
  380             index));
  381         KASSERT(rv->popcnt < VM_LEVEL_0_NPAGES,
  382             ("vm_reserv_populate: reserv %p is already full", rv));
  383         KASSERT(rv->pages->psind == 0,
  384             ("vm_reserv_populate: reserv %p is already promoted", rv));
  385         if (rv->inpartpopq) {
  386                 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
  387                 rv->inpartpopq = FALSE;
  388         }
  389         popmap_set(rv->popmap, index);
  390         rv->popcnt++;
  391         if (rv->popcnt < VM_LEVEL_0_NPAGES) {
  392                 rv->inpartpopq = TRUE;
  393                 TAILQ_INSERT_TAIL(&vm_rvq_partpop, rv, partpopq);
  394         } else
  395                 rv->pages->psind = 1;
  396 }
  397 
  398 /*
  399  * Allocates a contiguous set of physical pages of the given size "npages"
  400  * from existing or newly created reservations.  All of the physical pages
  401  * must be at or above the given physical address "low" and below the given
  402  * physical address "high".  The given value "alignment" determines the
  403  * alignment of the first physical page in the set.  If the given value
  404  * "boundary" is non-zero, then the set of physical pages cannot cross any
  405  * physical address boundary that is a multiple of that value.  Both
  406  * "alignment" and "boundary" must be a power of two.
  407  *
  408  * The page "mpred" must immediately precede the offset "pindex" within the
  409  * specified object.
  410  *
  411  * The object and free page queue must be locked.
  412  */
  413 vm_page_t
  414 vm_reserv_alloc_contig(vm_object_t object, vm_pindex_t pindex, u_long npages,
  415     vm_paddr_t low, vm_paddr_t high, u_long alignment, vm_paddr_t boundary,
  416     vm_page_t mpred)
  417 {
  418         vm_paddr_t pa, size;
  419         vm_page_t m, m_ret, msucc;
  420         vm_pindex_t first, leftcap, rightcap;
  421         vm_reserv_t rv;
  422         u_long allocpages, maxpages, minpages;
  423         int i, index, n;
  424 
  425         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  426         VM_OBJECT_ASSERT_WLOCKED(object);
  427         KASSERT(npages != 0, ("vm_reserv_alloc_contig: npages is 0"));
  428 
  429         /*
  430          * Is a reservation fundamentally impossible?
  431          */
  432         if (pindex < VM_RESERV_INDEX(object, pindex) ||
  433             pindex + npages > object->size)
  434                 return (NULL);
  435 
  436         /*
  437          * All reservations of a particular size have the same alignment.
  438          * Assuming that the first page is allocated from a reservation, the
  439          * least significant bits of its physical address can be determined
  440          * from its offset from the beginning of the reservation and the size
  441          * of the reservation.
  442          *
  443          * Could the specified index within a reservation of the smallest
  444          * possible size satisfy the alignment and boundary requirements?
  445          */
  446         pa = VM_RESERV_INDEX(object, pindex) << PAGE_SHIFT;
  447         if ((pa & (alignment - 1)) != 0)
  448                 return (NULL);
  449         size = npages << PAGE_SHIFT;
  450         if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0)
  451                 return (NULL);
  452 
  453         /*
  454          * Look for an existing reservation.
  455          */
  456         if (mpred != NULL) {
  457                 KASSERT(mpred->object == object,
  458                     ("vm_reserv_alloc_contig: object doesn't contain mpred"));
  459                 KASSERT(mpred->pindex < pindex,
  460                     ("vm_reserv_alloc_contig: mpred doesn't precede pindex"));
  461                 rv = vm_reserv_from_page(mpred);
  462                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
  463                         goto found;
  464                 msucc = TAILQ_NEXT(mpred, listq);
  465         } else
  466                 msucc = TAILQ_FIRST(&object->memq);
  467         if (msucc != NULL) {
  468                 KASSERT(msucc->pindex > pindex,
  469                     ("vm_reserv_alloc_contig: msucc doesn't succeed pindex"));
  470                 rv = vm_reserv_from_page(msucc);
  471                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
  472                         goto found;
  473         }
  474 
  475         /*
  476          * Could at least one reservation fit between the first index to the
  477          * left that can be used ("leftcap") and the first index to the right
  478          * that cannot be used ("rightcap")?
  479          */
  480         first = pindex - VM_RESERV_INDEX(object, pindex);
  481         if (mpred != NULL) {
  482                 if ((rv = vm_reserv_from_page(mpred))->object != object)
  483                         leftcap = mpred->pindex + 1;
  484                 else
  485                         leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
  486                 if (leftcap > first)
  487                         return (NULL);
  488         }
  489         minpages = VM_RESERV_INDEX(object, pindex) + npages;
  490         maxpages = roundup2(minpages, VM_LEVEL_0_NPAGES);
  491         allocpages = maxpages;
  492         if (msucc != NULL) {
  493                 if ((rv = vm_reserv_from_page(msucc))->object != object)
  494                         rightcap = msucc->pindex;
  495                 else
  496                         rightcap = rv->pindex;
  497                 if (first + maxpages > rightcap) {
  498                         if (maxpages == VM_LEVEL_0_NPAGES)
  499                                 return (NULL);
  500 
  501                         /*
  502                          * At least one reservation will fit between "leftcap"
  503                          * and "rightcap".  However, a reservation for the
  504                          * last of the requested pages will not fit.  Reduce
  505                          * the size of the upcoming allocation accordingly.
  506                          */
  507                         allocpages = minpages;
  508                 }
  509         }
  510 
  511         /*
  512          * Would the last new reservation extend past the end of the object?
  513          */
  514         if (first + maxpages > object->size) {
  515                 /*
  516                  * Don't allocate the last new reservation if the object is a
  517                  * vnode or backed by another object that is a vnode. 
  518                  */
  519                 if (object->type == OBJT_VNODE ||
  520                     (object->backing_object != NULL &&
  521                     object->backing_object->type == OBJT_VNODE)) {
  522                         if (maxpages == VM_LEVEL_0_NPAGES)
  523                                 return (NULL);
  524                         allocpages = minpages;
  525                 }
  526                 /* Speculate that the object may grow. */
  527         }
  528 
  529         /*
  530          * Allocate the physical pages.  The alignment and boundary specified
  531          * for this allocation may be different from the alignment and
  532          * boundary specified for the requested pages.  For instance, the
  533          * specified index may not be the first page within the first new
  534          * reservation.
  535          */
  536         m = vm_phys_alloc_contig(allocpages, low, high, ulmax(alignment,
  537             VM_LEVEL_0_SIZE), boundary > VM_LEVEL_0_SIZE ? boundary : 0);
  538         if (m == NULL)
  539                 return (NULL);
  540 
  541         /*
  542          * The allocated physical pages always begin at a reservation
  543          * boundary, but they do not always end at a reservation boundary.
  544          * Initialize every reservation that is completely covered by the
  545          * allocated physical pages.
  546          */
  547         m_ret = NULL;
  548         index = VM_RESERV_INDEX(object, pindex);
  549         do {
  550                 rv = vm_reserv_from_page(m);
  551                 KASSERT(rv->pages == m,
  552                     ("vm_reserv_alloc_contig: reserv %p's pages is corrupted",
  553                     rv));
  554                 KASSERT(rv->object == NULL,
  555                     ("vm_reserv_alloc_contig: reserv %p isn't free", rv));
  556                 LIST_INSERT_HEAD(&object->rvq, rv, objq);
  557                 rv->object = object;
  558                 rv->pindex = first;
  559                 KASSERT(rv->popcnt == 0,
  560                     ("vm_reserv_alloc_contig: reserv %p's popcnt is corrupted",
  561                     rv));
  562                 KASSERT(!rv->inpartpopq,
  563                     ("vm_reserv_alloc_contig: reserv %p's inpartpopq is TRUE",
  564                     rv));
  565                 for (i = 0; i < NPOPMAP; i++)
  566                         KASSERT(rv->popmap[i] == 0,
  567                     ("vm_reserv_alloc_contig: reserv %p's popmap is corrupted",
  568                             rv));
  569                 n = ulmin(VM_LEVEL_0_NPAGES - index, npages);
  570                 for (i = 0; i < n; i++)
  571                         vm_reserv_populate(rv, index + i);
  572                 npages -= n;
  573                 if (m_ret == NULL) {
  574                         m_ret = &rv->pages[index];
  575                         index = 0;
  576                 }
  577                 m += VM_LEVEL_0_NPAGES;
  578                 first += VM_LEVEL_0_NPAGES;
  579                 allocpages -= VM_LEVEL_0_NPAGES;
  580         } while (allocpages >= VM_LEVEL_0_NPAGES);
  581         return (m_ret);
  582 
  583         /*
  584          * Found a matching reservation.
  585          */
  586 found:
  587         index = VM_RESERV_INDEX(object, pindex);
  588         /* Does the allocation fit within the reservation? */
  589         if (index + npages > VM_LEVEL_0_NPAGES)
  590                 return (NULL);
  591         m = &rv->pages[index];
  592         pa = VM_PAGE_TO_PHYS(m);
  593         if (pa < low || pa + size > high || (pa & (alignment - 1)) != 0 ||
  594             ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0)
  595                 return (NULL);
  596         /* Handle vm_page_rename(m, new_object, ...). */
  597         for (i = 0; i < npages; i++)
  598                 if (popmap_is_set(rv->popmap, index + i))
  599                         return (NULL);
  600         for (i = 0; i < npages; i++)
  601                 vm_reserv_populate(rv, index + i);
  602         return (m);
  603 }
  604 
  605 /*
  606  * Allocates a page from an existing or newly created reservation.
  607  *
  608  * The page "mpred" must immediately precede the offset "pindex" within the
  609  * specified object.
  610  *
  611  * The object and free page queue must be locked.
  612  */
  613 vm_page_t
  614 vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex, vm_page_t mpred)
  615 {
  616         vm_page_t m, msucc;
  617         vm_pindex_t first, leftcap, rightcap;
  618         vm_reserv_t rv;
  619         int i, index;
  620 
  621         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  622         VM_OBJECT_ASSERT_WLOCKED(object);
  623 
  624         /*
  625          * Is a reservation fundamentally impossible?
  626          */
  627         if (pindex < VM_RESERV_INDEX(object, pindex) ||
  628             pindex >= object->size)
  629                 return (NULL);
  630 
  631         /*
  632          * Look for an existing reservation.
  633          */
  634         if (mpred != NULL) {
  635                 KASSERT(mpred->object == object,
  636                     ("vm_reserv_alloc_page: object doesn't contain mpred"));
  637                 KASSERT(mpred->pindex < pindex,
  638                     ("vm_reserv_alloc_page: mpred doesn't precede pindex"));
  639                 rv = vm_reserv_from_page(mpred);
  640                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
  641                         goto found;
  642                 msucc = TAILQ_NEXT(mpred, listq);
  643         } else
  644                 msucc = TAILQ_FIRST(&object->memq);
  645         if (msucc != NULL) {
  646                 KASSERT(msucc->pindex > pindex,
  647                     ("vm_reserv_alloc_page: msucc doesn't succeed pindex"));
  648                 rv = vm_reserv_from_page(msucc);
  649                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
  650                         goto found;
  651         }
  652 
  653         /*
  654          * Could a reservation fit between the first index to the left that
  655          * can be used and the first index to the right that cannot be used?
  656          */
  657         first = pindex - VM_RESERV_INDEX(object, pindex);
  658         if (mpred != NULL) {
  659                 if ((rv = vm_reserv_from_page(mpred))->object != object)
  660                         leftcap = mpred->pindex + 1;
  661                 else
  662                         leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
  663                 if (leftcap > first)
  664                         return (NULL);
  665         }
  666         if (msucc != NULL) {
  667                 if ((rv = vm_reserv_from_page(msucc))->object != object)
  668                         rightcap = msucc->pindex;
  669                 else
  670                         rightcap = rv->pindex;
  671                 if (first + VM_LEVEL_0_NPAGES > rightcap)
  672                         return (NULL);
  673         }
  674 
  675         /*
  676          * Would a new reservation extend past the end of the object? 
  677          */
  678         if (first + VM_LEVEL_0_NPAGES > object->size) {
  679                 /*
  680                  * Don't allocate a new reservation if the object is a vnode or
  681                  * backed by another object that is a vnode. 
  682                  */
  683                 if (object->type == OBJT_VNODE ||
  684                     (object->backing_object != NULL &&
  685                     object->backing_object->type == OBJT_VNODE))
  686                         return (NULL);
  687                 /* Speculate that the object may grow. */
  688         }
  689 
  690         /*
  691          * Allocate and populate the new reservation.
  692          */
  693         m = vm_phys_alloc_pages(VM_FREEPOOL_DEFAULT, VM_LEVEL_0_ORDER);
  694         if (m == NULL)
  695                 return (NULL);
  696         rv = vm_reserv_from_page(m);
  697         KASSERT(rv->pages == m,
  698             ("vm_reserv_alloc_page: reserv %p's pages is corrupted", rv));
  699         KASSERT(rv->object == NULL,
  700             ("vm_reserv_alloc_page: reserv %p isn't free", rv));
  701         LIST_INSERT_HEAD(&object->rvq, rv, objq);
  702         rv->object = object;
  703         rv->pindex = first;
  704         KASSERT(rv->popcnt == 0,
  705             ("vm_reserv_alloc_page: reserv %p's popcnt is corrupted", rv));
  706         KASSERT(!rv->inpartpopq,
  707             ("vm_reserv_alloc_page: reserv %p's inpartpopq is TRUE", rv));
  708         for (i = 0; i < NPOPMAP; i++)
  709                 KASSERT(rv->popmap[i] == 0,
  710                     ("vm_reserv_alloc_page: reserv %p's popmap is corrupted",
  711                     rv));
  712         index = VM_RESERV_INDEX(object, pindex);
  713         vm_reserv_populate(rv, index);
  714         return (&rv->pages[index]);
  715 
  716         /*
  717          * Found a matching reservation.
  718          */
  719 found:
  720         index = VM_RESERV_INDEX(object, pindex);
  721         m = &rv->pages[index];
  722         /* Handle vm_page_rename(m, new_object, ...). */
  723         if (popmap_is_set(rv->popmap, index))
  724                 return (NULL);
  725         vm_reserv_populate(rv, index);
  726         return (m);
  727 }
  728 
  729 /*
  730  * Breaks the given reservation.  All free pages in the reservation
  731  * are returned to the physical memory allocator.  The reservation's
  732  * population count and map are reset to their initial state.
  733  *
  734  * The given reservation must not be in the partially populated reservation
  735  * queue.  The free page queue lock must be held.
  736  */
  737 static void
  738 vm_reserv_break(vm_reserv_t rv)
  739 {
  740         int begin_zeroes, hi, i, lo;
  741 
  742         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  743         KASSERT(rv->object != NULL,
  744             ("vm_reserv_break: reserv %p is free", rv));
  745         KASSERT(!rv->inpartpopq,
  746             ("vm_reserv_break: reserv %p's inpartpopq is TRUE", rv));
  747         LIST_REMOVE(rv, objq);
  748         rv->object = NULL;
  749         rv->pages->psind = 0;
  750         i = hi = 0;
  751         do {
  752                 /* Find the next 0 bit.  Any previous 0 bits are < "hi". */
  753                 lo = ffsl(~(((1UL << hi) - 1) | rv->popmap[i]));
  754                 if (lo == 0) {
  755                         /* Redundantly clears bits < "hi". */
  756                         rv->popmap[i] = 0;
  757                         rv->popcnt -= NBPOPMAP - hi;
  758                         while (++i < NPOPMAP) {
  759                                 lo = ffsl(~rv->popmap[i]);
  760                                 if (lo == 0) {
  761                                         rv->popmap[i] = 0;
  762                                         rv->popcnt -= NBPOPMAP;
  763                                 } else
  764                                         break;
  765                         }
  766                         if (i == NPOPMAP)
  767                                 break;
  768                         hi = 0;
  769                 }
  770                 KASSERT(lo > 0, ("vm_reserv_break: lo is %d", lo));
  771                 /* Convert from ffsl() to ordinary bit numbering. */
  772                 lo--;
  773                 if (lo > 0) {
  774                         /* Redundantly clears bits < "hi". */
  775                         rv->popmap[i] &= ~((1UL << lo) - 1);
  776                         rv->popcnt -= lo - hi;
  777                 }
  778                 begin_zeroes = NBPOPMAP * i + lo;
  779                 /* Find the next 1 bit. */
  780                 do
  781                         hi = ffsl(rv->popmap[i]);
  782                 while (hi == 0 && ++i < NPOPMAP);
  783                 if (i != NPOPMAP)
  784                         /* Convert from ffsl() to ordinary bit numbering. */
  785                         hi--;
  786                 vm_phys_free_contig(&rv->pages[begin_zeroes], NBPOPMAP * i +
  787                     hi - begin_zeroes);
  788         } while (i < NPOPMAP);
  789         KASSERT(rv->popcnt == 0,
  790             ("vm_reserv_break: reserv %p's popcnt is corrupted", rv));
  791         vm_reserv_broken++;
  792 }
  793 
  794 /*
  795  * Breaks all reservations belonging to the given object.
  796  */
  797 void
  798 vm_reserv_break_all(vm_object_t object)
  799 {
  800         vm_reserv_t rv;
  801 
  802         mtx_lock(&vm_page_queue_free_mtx);
  803         while ((rv = LIST_FIRST(&object->rvq)) != NULL) {
  804                 KASSERT(rv->object == object,
  805                     ("vm_reserv_break_all: reserv %p is corrupted", rv));
  806                 if (rv->inpartpopq) {
  807                         TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
  808                         rv->inpartpopq = FALSE;
  809                 }
  810                 vm_reserv_break(rv);
  811         }
  812         mtx_unlock(&vm_page_queue_free_mtx);
  813 }
  814 
  815 /*
  816  * Frees the given page if it belongs to a reservation.  Returns TRUE if the
  817  * page is freed and FALSE otherwise.
  818  *
  819  * The free page queue lock must be held.
  820  */
  821 boolean_t
  822 vm_reserv_free_page(vm_page_t m)
  823 {
  824         vm_reserv_t rv;
  825 
  826         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  827         rv = vm_reserv_from_page(m);
  828         if (rv->object == NULL)
  829                 return (FALSE);
  830         vm_reserv_depopulate(rv, m - rv->pages);
  831         return (TRUE);
  832 }
  833 
  834 /*
  835  * Initializes the reservation management system.  Specifically, initializes
  836  * the reservation array.
  837  *
  838  * Requires that vm_page_array and first_page are initialized!
  839  */
  840 void
  841 vm_reserv_init(void)
  842 {
  843         vm_paddr_t paddr;
  844         struct vm_phys_seg *seg;
  845         int segind;
  846 
  847         /*
  848          * Initialize the reservation array.  Specifically, initialize the
  849          * "pages" field for every element that has an underlying superpage.
  850          */
  851         for (segind = 0; segind < vm_phys_nsegs; segind++) {
  852                 seg = &vm_phys_segs[segind];
  853                 paddr = roundup2(seg->start, VM_LEVEL_0_SIZE);
  854                 while (paddr + VM_LEVEL_0_SIZE <= seg->end) {
  855                         vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT].pages =
  856                             PHYS_TO_VM_PAGE(paddr);
  857                         paddr += VM_LEVEL_0_SIZE;
  858                 }
  859         }
  860 }
  861 
  862 /*
  863  * Returns true if the given page belongs to a reservation and that page is
  864  * free.  Otherwise, returns false.
  865  */
  866 bool
  867 vm_reserv_is_page_free(vm_page_t m)
  868 {
  869         vm_reserv_t rv;
  870 
  871         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  872         rv = vm_reserv_from_page(m);
  873         if (rv->object == NULL)
  874                 return (false);
  875         return (popmap_is_clear(rv->popmap, m - rv->pages));
  876 }
  877 
  878 /*
  879  * If the given page belongs to a reservation, returns the level of that
  880  * reservation.  Otherwise, returns -1.
  881  */
  882 int
  883 vm_reserv_level(vm_page_t m)
  884 {
  885         vm_reserv_t rv;
  886 
  887         rv = vm_reserv_from_page(m);
  888         return (rv->object != NULL ? 0 : -1);
  889 }
  890 
  891 /*
  892  * Returns a reservation level if the given page belongs to a fully populated
  893  * reservation and -1 otherwise.
  894  */
  895 int
  896 vm_reserv_level_iffullpop(vm_page_t m)
  897 {
  898         vm_reserv_t rv;
  899 
  900         rv = vm_reserv_from_page(m);
  901         return (rv->popcnt == VM_LEVEL_0_NPAGES ? 0 : -1);
  902 }
  903 
  904 /*
  905  * Breaks the given partially populated reservation, releasing its free pages
  906  * to the physical memory allocator.
  907  *
  908  * The free page queue lock must be held.
  909  */
  910 static void
  911 vm_reserv_reclaim(vm_reserv_t rv)
  912 {
  913 
  914         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  915         KASSERT(rv->inpartpopq,
  916             ("vm_reserv_reclaim: reserv %p's inpartpopq is FALSE", rv));
  917         TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
  918         rv->inpartpopq = FALSE;
  919         vm_reserv_break(rv);
  920         vm_reserv_reclaimed++;
  921 }
  922 
  923 /*
  924  * Breaks the reservation at the head of the partially populated reservation
  925  * queue, releasing its free pages to the physical memory allocator.  Returns
  926  * TRUE if a reservation is broken and FALSE otherwise.
  927  *
  928  * The free page queue lock must be held.
  929  */
  930 boolean_t
  931 vm_reserv_reclaim_inactive(void)
  932 {
  933         vm_reserv_t rv;
  934 
  935         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  936         if ((rv = TAILQ_FIRST(&vm_rvq_partpop)) != NULL) {
  937                 vm_reserv_reclaim(rv);
  938                 return (TRUE);
  939         }
  940         return (FALSE);
  941 }
  942 
  943 /*
  944  * Searches the partially populated reservation queue for the least recently
  945  * changed reservation with free pages that satisfy the given request for
  946  * contiguous physical memory.  If a satisfactory reservation is found, it is
  947  * broken.  Returns TRUE if a reservation is broken and FALSE otherwise.
  948  *
  949  * The free page queue lock must be held.
  950  */
  951 boolean_t
  952 vm_reserv_reclaim_contig(u_long npages, vm_paddr_t low, vm_paddr_t high,
  953     u_long alignment, vm_paddr_t boundary)
  954 {
  955         vm_paddr_t pa, size;
  956         vm_reserv_t rv;
  957         int hi, i, lo, low_index, next_free;
  958 
  959         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
  960         if (npages > VM_LEVEL_0_NPAGES - 1)
  961                 return (FALSE);
  962         size = npages << PAGE_SHIFT;
  963         TAILQ_FOREACH(rv, &vm_rvq_partpop, partpopq) {
  964                 pa = VM_PAGE_TO_PHYS(&rv->pages[VM_LEVEL_0_NPAGES - 1]);
  965                 if (pa + PAGE_SIZE - size < low) {
  966                         /* This entire reservation is too low; go to next. */
  967                         continue;
  968                 }
  969                 pa = VM_PAGE_TO_PHYS(&rv->pages[0]);
  970                 if (pa + size > high) {
  971                         /* This entire reservation is too high; go to next. */
  972                         continue;
  973                 }
  974                 if (pa < low) {
  975                         /* Start the search for free pages at "low". */
  976                         low_index = (low + PAGE_MASK - pa) >> PAGE_SHIFT;
  977                         i = low_index / NBPOPMAP;
  978                         hi = low_index % NBPOPMAP;
  979                 } else
  980                         i = hi = 0;
  981                 do {
  982                         /* Find the next free page. */
  983                         lo = ffsl(~(((1UL << hi) - 1) | rv->popmap[i]));
  984                         while (lo == 0 && ++i < NPOPMAP)
  985                                 lo = ffsl(~rv->popmap[i]);
  986                         if (i == NPOPMAP)
  987                                 break;
  988                         /* Convert from ffsl() to ordinary bit numbering. */
  989                         lo--;
  990                         next_free = NBPOPMAP * i + lo;
  991                         pa = VM_PAGE_TO_PHYS(&rv->pages[next_free]);
  992                         KASSERT(pa >= low,
  993                             ("vm_reserv_reclaim_contig: pa is too low"));
  994                         if (pa + size > high) {
  995                                 /* The rest of this reservation is too high. */
  996                                 break;
  997                         } else if ((pa & (alignment - 1)) != 0 ||
  998                             ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) {
  999                                 /*
 1000                                  * The current page doesn't meet the alignment
 1001                                  * and/or boundary requirements.  Continue
 1002                                  * searching this reservation until the rest
 1003                                  * of its free pages are either excluded or
 1004                                  * exhausted.
 1005                                  */
 1006                                 hi = lo + 1;
 1007                                 if (hi >= NBPOPMAP) {
 1008                                         hi = 0;
 1009                                         i++;
 1010                                 }
 1011                                 continue;
 1012                         }
 1013                         /* Find the next used page. */
 1014                         hi = ffsl(rv->popmap[i] & ~((1UL << lo) - 1));
 1015                         while (hi == 0 && ++i < NPOPMAP) {
 1016                                 if ((NBPOPMAP * i - next_free) * PAGE_SIZE >=
 1017                                     size) {
 1018                                         vm_reserv_reclaim(rv);
 1019                                         return (TRUE);
 1020                                 }
 1021                                 hi = ffsl(rv->popmap[i]);
 1022                         }
 1023                         /* Convert from ffsl() to ordinary bit numbering. */
 1024                         if (i != NPOPMAP)
 1025                                 hi--;
 1026                         if ((NBPOPMAP * i + hi - next_free) * PAGE_SIZE >=
 1027                             size) {
 1028                                 vm_reserv_reclaim(rv);
 1029                                 return (TRUE);
 1030                         }
 1031                 } while (i < NPOPMAP);
 1032         }
 1033         return (FALSE);
 1034 }
 1035 
 1036 /*
 1037  * Transfers the reservation underlying the given page to a new object.
 1038  *
 1039  * The object must be locked.
 1040  */
 1041 void
 1042 vm_reserv_rename(vm_page_t m, vm_object_t new_object, vm_object_t old_object,
 1043     vm_pindex_t old_object_offset)
 1044 {
 1045         vm_reserv_t rv;
 1046 
 1047         VM_OBJECT_ASSERT_WLOCKED(new_object);
 1048         rv = vm_reserv_from_page(m);
 1049         if (rv->object == old_object) {
 1050                 mtx_lock(&vm_page_queue_free_mtx);
 1051                 if (rv->object == old_object) {
 1052                         LIST_REMOVE(rv, objq);
 1053                         LIST_INSERT_HEAD(&new_object->rvq, rv, objq);
 1054                         rv->object = new_object;
 1055                         rv->pindex -= old_object_offset;
 1056                 }
 1057                 mtx_unlock(&vm_page_queue_free_mtx);
 1058         }
 1059 }
 1060 
 1061 /*
 1062  * Returns the size (in bytes) of a reservation of the specified level.
 1063  */
 1064 int
 1065 vm_reserv_size(int level)
 1066 {
 1067 
 1068         switch (level) {
 1069         case 0:
 1070                 return (VM_LEVEL_0_SIZE);
 1071         case -1:
 1072                 return (PAGE_SIZE);
 1073         default:
 1074                 return (0);
 1075         }
 1076 }
 1077 
 1078 /*
 1079  * Allocates the virtual and physical memory required by the reservation
 1080  * management system's data structures, in particular, the reservation array.
 1081  */
 1082 vm_paddr_t
 1083 vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end, vm_paddr_t high_water)
 1084 {
 1085         vm_paddr_t new_end;
 1086         size_t size;
 1087 
 1088         /*
 1089          * Calculate the size (in bytes) of the reservation array.  Round up
 1090          * from "high_water" because every small page is mapped to an element
 1091          * in the reservation array based on its physical address.  Thus, the
 1092          * number of elements in the reservation array can be greater than the
 1093          * number of superpages. 
 1094          */
 1095         size = howmany(high_water, VM_LEVEL_0_SIZE) * sizeof(struct vm_reserv);
 1096 
 1097         /*
 1098          * Allocate and map the physical memory for the reservation array.  The
 1099          * next available virtual address is returned by reference.
 1100          */
 1101         new_end = end - round_page(size);
 1102         vm_reserv_array = (void *)(uintptr_t)pmap_map(vaddr, new_end, end,
 1103             VM_PROT_READ | VM_PROT_WRITE);
 1104         bzero(vm_reserv_array, size);
 1105 
 1106         /*
 1107          * Return the next available physical address.
 1108          */
 1109         return (new_end);
 1110 }
 1111 
 1112 /*
 1113  * Returns the superpage containing the given page.
 1114  */
 1115 vm_page_t
 1116 vm_reserv_to_superpage(vm_page_t m)
 1117 {
 1118         vm_reserv_t rv;
 1119 
 1120         VM_OBJECT_ASSERT_LOCKED(m->object);
 1121         rv = vm_reserv_from_page(m);
 1122         return (rv->object == m->object && rv->popcnt == VM_LEVEL_0_NPAGES ?
 1123             rv->pages : NULL);
 1124 }
 1125 
 1126 #endif  /* VM_NRESERVLEVEL > 0 */

Cache object: a480564175fae3eedc331ae78cab602c


[ 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.