sys/vm/vm_reserv.c

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