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 an existing or newly-created reservation.  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_page: 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 and the first index to the right that cannot
 440          * be used?
 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                         allocpages = minpages;
 463                 }
 464         }
 465
 466         /*
 467          * Would the last new reservation extend past the end of the object?
 468          */
 469         if (first + maxpages > object->size) {
 470                 /*
 471                  * Don't allocate the last new reservation if the object is a
 472                  * vnode or backed by another object that is a vnode.
 473                  */
 474                 if (object->type == OBJT_VNODE ||
 475                     (object->backing_object != NULL &&
 476                     object->backing_object->type == OBJT_VNODE)) {
 477                         if (maxpages == VM_LEVEL_0_NPAGES)
 478                                 return (NULL);
 479                         allocpages = minpages;
 480                 }
 481                 /* Speculate that the object may grow. */
 482         }
 483
 484         /*
 485          * Allocate and populate the new reservations.  The alignment and
 486          * boundary specified for this allocation may be different from the
 487          * alignment and boundary specified for the requested pages.  For
 488          * instance, the specified index may not be the first page within the
 489          * first new reservation.
 490          */
 491         m = vm_phys_alloc_contig(allocpages, low, high, ulmax(alignment,
 492             VM_LEVEL_0_SIZE), boundary > VM_LEVEL_0_SIZE ? boundary : 0);
 493         if (m == NULL)
 494                 return (NULL);
 495         m_ret = NULL;
 496         index = VM_RESERV_INDEX(object, pindex);
 497         do {
 498                 rv = vm_reserv_from_page(m);
 499                 KASSERT(rv->pages == m,
 500                     ("vm_reserv_alloc_contig: reserv %p's pages is corrupted",
 501                     rv));
 502                 KASSERT(rv->object == NULL,
 503                     ("vm_reserv_alloc_contig: reserv %p isn't free", rv));
 504                 LIST_INSERT_HEAD(&object->rvq, rv, objq);
 505                 rv->object = object;
 506                 rv->pindex = first;
 507                 KASSERT(rv->popcnt == 0,
 508                     ("vm_reserv_alloc_contig: reserv %p's popcnt is corrupted",
 509                     rv));
 510                 KASSERT(!rv->inpartpopq,
 511                     ("vm_reserv_alloc_contig: reserv %p's inpartpopq is TRUE",
 512                     rv));
 513                 for (i = 0; i < NPOPMAP; i++)
 514                         KASSERT(rv->popmap[i] == 0,
 515                     ("vm_reserv_alloc_contig: reserv %p's popmap is corrupted",
 516                             rv));
 517                 n = ulmin(VM_LEVEL_0_NPAGES - index, npages);
 518                 for (i = 0; i < n; i++)
 519                         vm_reserv_populate(rv, index + i);
 520                 npages -= n;
 521                 if (m_ret == NULL) {
 522                         m_ret = &rv->pages[index];
 523                         index = 0;
 524                 }
 525                 m += VM_LEVEL_0_NPAGES;
 526                 first += VM_LEVEL_0_NPAGES;
 527                 allocpages -= VM_LEVEL_0_NPAGES;
 528         } while (allocpages > 0);
 529         return (m_ret);
 530
 531         /*
 532          * Found a matching reservation.
 533          */
 534 found:
 535         index = VM_RESERV_INDEX(object, pindex);
 536         /* Does the allocation fit within the reservation? */
 537         if (index + npages > VM_LEVEL_0_NPAGES)
 538                 return (NULL);
 539         m = &rv->pages[index];
 540         pa = VM_PAGE_TO_PHYS(m);
 541         if (pa < low || pa + size > high || (pa & (alignment - 1)) != 0 ||
 542             ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0)
 543                 return (NULL);
 544         /* Handle vm_page_rename(m, new_object, ...). */
 545         for (i = 0; i < npages; i++)
 546                 if (popmap_is_set(rv->popmap, index + i))
 547                         return (NULL);
 548         for (i = 0; i < npages; i++)
 549                 vm_reserv_populate(rv, index + i);
 550         return (m);
 551 }
 552
 553 /*
 554  * Allocates a page from an existing or newly-created reservation.
 555  *
 556  * The page "mpred" must immediately precede the offset "pindex" within the
 557  * specified object.
 558  *
 559  * The object and free page queue must be locked.
 560  */
 561 vm_page_t
 562 vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex, vm_page_t mpred)
 563 {
 564         vm_page_t m, msucc;
 565         vm_pindex_t first, leftcap, rightcap;
 566         vm_reserv_t rv;
 567         int i, index;
 568
 569         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 570         VM_OBJECT_ASSERT_WLOCKED(object);
 571
 572         /*
 573          * Is a reservation fundamentally impossible?
 574          */
 575         if (pindex < VM_RESERV_INDEX(object, pindex) ||
 576             pindex >= object->size)
 577                 return (NULL);
 578
 579         /*
 580          * Look for an existing reservation.
 581          */
 582         if (mpred != NULL) {
 583                 KASSERT(mpred->object == object,
 584                     ("vm_reserv_alloc_page: object doesn't contain mpred"));
 585                 KASSERT(mpred->pindex < pindex,
 586                     ("vm_reserv_alloc_page: mpred doesn't precede pindex"));
 587                 rv = vm_reserv_from_page(mpred);
 588                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
 589                         goto found;
 590                 msucc = TAILQ_NEXT(mpred, listq);
 591         } else
 592                 msucc = TAILQ_FIRST(&object->memq);
 593         if (msucc != NULL) {
 594                 KASSERT(msucc->pindex > pindex,
 595                     ("vm_reserv_alloc_page: msucc doesn't succeed pindex"));
 596                 rv = vm_reserv_from_page(msucc);
 597                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
 598                         goto found;
 599         }
 600
 601         /*
 602          * Could a reservation fit between the first index to the left that
 603          * can be used and the first index to the right that cannot be used?
 604          */
 605         first = pindex - VM_RESERV_INDEX(object, pindex);
 606         if (mpred != NULL) {
 607                 if ((rv = vm_reserv_from_page(mpred))->object != object)
 608                         leftcap = mpred->pindex + 1;
 609                 else
 610                         leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
 611                 if (leftcap > first)
 612                         return (NULL);
 613         }
 614         if (msucc != NULL) {
 615                 if ((rv = vm_reserv_from_page(msucc))->object != object)
 616                         rightcap = msucc->pindex;
 617                 else
 618                         rightcap = rv->pindex;
 619                 if (first + VM_LEVEL_0_NPAGES > rightcap)
 620                         return (NULL);
 621         }
 622
 623         /*
 624          * Would a new reservation extend past the end of the object?
 625          */
 626         if (first + VM_LEVEL_0_NPAGES > object->size) {
 627                 /*
 628                  * Don't allocate a new reservation if the object is a vnode or
 629                  * backed by another object that is a vnode.
 630                  */
 631                 if (object->type == OBJT_VNODE ||
 632                     (object->backing_object != NULL &&
 633                     object->backing_object->type == OBJT_VNODE))
 634                         return (NULL);
 635                 /* Speculate that the object may grow. */
 636         }
 637
 638         /*
 639          * Allocate and populate the new reservation.
 640          */
 641         m = vm_phys_alloc_pages(VM_FREEPOOL_DEFAULT, VM_LEVEL_0_ORDER);
 642         if (m == NULL)
 643                 return (NULL);
 644         rv = vm_reserv_from_page(m);
 645         KASSERT(rv->pages == m,
 646             ("vm_reserv_alloc_page: reserv %p's pages is corrupted", rv));
 647         KASSERT(rv->object == NULL,
 648             ("vm_reserv_alloc_page: reserv %p isn't free", rv));
 649         LIST_INSERT_HEAD(&object->rvq, rv, objq);
 650         rv->object = object;
 651         rv->pindex = first;
 652         KASSERT(rv->popcnt == 0,
 653             ("vm_reserv_alloc_page: reserv %p's popcnt is corrupted", rv));
 654         KASSERT(!rv->inpartpopq,
 655             ("vm_reserv_alloc_page: reserv %p's inpartpopq is TRUE", rv));
 656         for (i = 0; i < NPOPMAP; i++)
 657                 KASSERT(rv->popmap[i] == 0,
 658                     ("vm_reserv_alloc_page: reserv %p's popmap is corrupted",
 659                     rv));
 660         index = VM_RESERV_INDEX(object, pindex);
 661         vm_reserv_populate(rv, index);
 662         return (&rv->pages[index]);
 663
 664         /*
 665          * Found a matching reservation.
 666          */
 667 found:
 668         index = VM_RESERV_INDEX(object, pindex);
 669         m = &rv->pages[index];
 670         /* Handle vm_page_rename(m, new_object, ...). */
 671         if (popmap_is_set(rv->popmap, index))
 672                 return (NULL);
 673         vm_reserv_populate(rv, index);
 674         return (m);
 675 }
 676
 677 /*
 678  * Breaks the given reservation.  Except for the specified cached or free
 679  * page, all cached and free pages in the reservation are returned to the
 680  * physical memory allocator.  The reservation's population count and map are
 681  * reset to their initial state.
 682  *
 683  * The given reservation must not be in the partially-populated reservation
 684  * queue.  The free page queue lock must be held.
 685  */
 686 static void
 687 vm_reserv_break(vm_reserv_t rv, vm_page_t m)
 688 {
 689         int begin_zeroes, hi, i, lo;
 690
 691         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 692         KASSERT(rv->object != NULL,
 693             ("vm_reserv_break: reserv %p is free", rv));
 694         KASSERT(!rv->inpartpopq,
 695             ("vm_reserv_break: reserv %p's inpartpopq is TRUE", rv));
 696         LIST_REMOVE(rv, objq);
 697         rv->object = NULL;
 698         if (m != NULL) {
 699                 /*
 700                  * Since the reservation is being broken, there is no harm in
 701                  * abusing the population map to stop "m" from being returned
 702                  * to the physical memory allocator.
 703                  */
 704                 i = m - rv->pages;
 705                 KASSERT(popmap_is_clear(rv->popmap, i),
 706                     ("vm_reserv_break: reserv %p's popmap is corrupted", rv));
 707                 popmap_set(rv->popmap, i);
 708                 rv->popcnt++;
 709         }
 710         i = hi = 0;
 711         do {
 712                 /* Find the next 0 bit.  Any previous 0 bits are < "hi". */
 713                 lo = ffsl(~(((1UL << hi) - 1) | rv->popmap[i]));
 714                 if (lo == 0) {
 715                         /* Redundantly clears bits < "hi". */
 716                         rv->popmap[i] = 0;
 717                         rv->popcnt -= NBPOPMAP - hi;
 718                         while (++i < NPOPMAP) {
 719                                 lo = ffsl(~rv->popmap[i]);
 720                                 if (lo == 0) {
 721                                         rv->popmap[i] = 0;
 722                                         rv->popcnt -= NBPOPMAP;
 723                                 } else
 724                                         break;
 725                         }
 726                         if (i == NPOPMAP)
 727                                 break;
 728                         hi = 0;
 729                 }
 730                 KASSERT(lo > 0, ("vm_reserv_break: lo is %d", lo));
 731                 /* Convert from ffsl() to ordinary bit numbering. */
 732                 lo--;
 733                 if (lo > 0) {
 734                         /* Redundantly clears bits < "hi". */
 735                         rv->popmap[i] &= ~((1UL << lo) - 1);
 736                         rv->popcnt -= lo - hi;
 737                 }
 738                 begin_zeroes = NBPOPMAP * i + lo;
 739                 /* Find the next 1 bit. */
 740                 do
 741                         hi = ffsl(rv->popmap[i]);
 742                 while (hi == 0 && ++i < NPOPMAP);
 743                 if (i != NPOPMAP)
 744                         /* Convert from ffsl() to ordinary bit numbering. */
 745                         hi--;
 746                 vm_phys_free_contig(&rv->pages[begin_zeroes], NBPOPMAP * i +
 747                     hi - begin_zeroes);
 748         } while (i < NPOPMAP);
 749         KASSERT(rv->popcnt == 0,
 750             ("vm_reserv_break: reserv %p's popcnt is corrupted", rv));
 751         vm_reserv_broken++;
 752 }
 753
 754 /*
 755  * Breaks all reservations belonging to the given object.
 756  */
 757 void
 758 vm_reserv_break_all(vm_object_t object)
 759 {
 760         vm_reserv_t rv;
 761
 762         mtx_lock(&vm_page_queue_free_mtx);
 763         while ((rv = LIST_FIRST(&object->rvq)) != NULL) {
 764                 KASSERT(rv->object == object,
 765                     ("vm_reserv_break_all: reserv %p is corrupted", rv));
 766                 if (rv->inpartpopq) {
 767                         TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
 768                         rv->inpartpopq = FALSE;
 769                 }
 770                 vm_reserv_break(rv, NULL);
 771         }
 772         mtx_unlock(&vm_page_queue_free_mtx);
 773 }
 774
 775 /*
 776  * Frees the given page if it belongs to a reservation.  Returns TRUE if the
 777  * page is freed and FALSE otherwise.
 778  *
 779  * The free page queue lock must be held.
 780  */
 781 boolean_t
 782 vm_reserv_free_page(vm_page_t m)
 783 {
 784         vm_reserv_t rv;
 785
 786         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 787         rv = vm_reserv_from_page(m);
 788         if (rv->object == NULL)
 789                 return (FALSE);
 790         if ((m->flags & PG_CACHED) != 0 && m->pool != VM_FREEPOOL_CACHE)
 791                 vm_phys_set_pool(VM_FREEPOOL_CACHE, rv->pages,
 792                     VM_LEVEL_0_ORDER);
 793         vm_reserv_depopulate(rv, m - rv->pages);
 794         return (TRUE);
 795 }
 796
 797 /*
 798  * Initializes the reservation management system.  Specifically, initializes
 799  * the reservation array.
 800  *
 801  * Requires that vm_page_array and first_page are initialized!
 802  */
 803 void
 804 vm_reserv_init(void)
 805 {
 806         vm_paddr_t paddr;
 807         int i;
 808
 809         /*
 810          * Initialize the reservation array.  Specifically, initialize the
 811          * "pages" field for every element that has an underlying superpage.
 812          */
 813         for (i = 0; phys_avail[i + 1] != 0; i += 2) {
 814                 paddr = roundup2(phys_avail[i], VM_LEVEL_0_SIZE);
 815                 while (paddr + VM_LEVEL_0_SIZE <= phys_avail[i + 1]) {
 816                         vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT].pages =
 817                             PHYS_TO_VM_PAGE(paddr);
 818                         paddr += VM_LEVEL_0_SIZE;
 819                 }
 820         }
 821 }
 822
 823 /*
 824  * Returns a reservation level if the given page belongs to a fully-populated
 825  * reservation and -1 otherwise.
 826  */
 827 int
 828 vm_reserv_level_iffullpop(vm_page_t m)
 829 {
 830         vm_reserv_t rv;
 831
 832         rv = vm_reserv_from_page(m);
 833         return (rv->popcnt == VM_LEVEL_0_NPAGES ? 0 : -1);
 834 }
 835
 836 /*
 837  * Prepare for the reactivation of a cached page.
 838  *
 839  * First, suppose that the given page "m" was allocated individually, i.e., not
 840  * as part of a reservation, and cached.  Then, suppose a reservation
 841  * containing "m" is allocated by the same object.  Although "m" and the
 842  * reservation belong to the same object, "m"'s pindex may not match the
 843  * reservation's.
 844  *
 845  * The free page queue must be locked.
 846  */
 847 boolean_t
 848 vm_reserv_reactivate_page(vm_page_t m)
 849 {
 850         vm_reserv_t rv;
 851         int index;
 852
 853         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 854         rv = vm_reserv_from_page(m);
 855         if (rv->object == NULL)
 856                 return (FALSE);
 857         KASSERT((m->flags & PG_CACHED) != 0,
 858             ("vm_reserv_reactivate_page: page %p is not cached", m));
 859         if (m->object == rv->object &&
 860             m->pindex - rv->pindex == (index = VM_RESERV_INDEX(m->object,
 861             m->pindex)))
 862                 vm_reserv_populate(rv, index);
 863         else {
 864                 KASSERT(rv->inpartpopq,
 865             ("vm_reserv_reactivate_page: reserv %p's inpartpopq is FALSE",
 866                     rv));
 867                 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
 868                 rv->inpartpopq = FALSE;
 869                 /* Don't release "m" to the physical memory allocator. */
 870                 vm_reserv_break(rv, m);
 871         }
 872         return (TRUE);
 873 }
 874
 875 /*
 876  * Breaks the given partially-populated reservation, releasing its cached and
 877  * free pages to the physical memory allocator.
 878  *
 879  * The free page queue lock must be held.
 880  */
 881 static void
 882 vm_reserv_reclaim(vm_reserv_t rv)
 883 {
 884
 885         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 886         KASSERT(rv->inpartpopq,
 887             ("vm_reserv_reclaim: reserv %p's inpartpopq is FALSE", rv));
 888         TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
 889         rv->inpartpopq = FALSE;
 890         vm_reserv_break(rv, NULL);
 891         vm_reserv_reclaimed++;
 892 }
 893
 894 /*
 895  * Breaks the reservation at the head of the partially-populated reservation
 896  * queue, releasing its cached and free pages to the physical memory
 897  * allocator.  Returns TRUE if a reservation is broken and FALSE otherwise.
 898  *
 899  * The free page queue lock must be held.
 900  */
 901 boolean_t
 902 vm_reserv_reclaim_inactive(void)
 903 {
 904         vm_reserv_t rv;
 905
 906         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 907         if ((rv = TAILQ_FIRST(&vm_rvq_partpop)) != NULL) {
 908                 vm_reserv_reclaim(rv);
 909                 return (TRUE);
 910         }
 911         return (FALSE);
 912 }
 913
 914 /*
 915  * Searches the partially-populated reservation queue for the least recently
 916  * active reservation with unused pages, i.e., cached or free, that satisfy the
 917  * given request for contiguous physical memory.  If a satisfactory reservation
 918  * is found, it is broken.  Returns TRUE if a reservation is broken and FALSE
 919  * otherwise.
 920  *
 921  * The free page queue lock must be held.
 922  */
 923 boolean_t
 924 vm_reserv_reclaim_contig(u_long npages, vm_paddr_t low, vm_paddr_t high,
 925     u_long alignment, vm_paddr_t boundary)
 926 {
 927         vm_paddr_t pa, size;
 928         vm_reserv_t rv;
 929         int hi, i, lo, next_free;
 930
 931         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
 932         if (npages > VM_LEVEL_0_NPAGES - 1)
 933                 return (FALSE);
 934         size = npages << PAGE_SHIFT;
 935         TAILQ_FOREACH(rv, &vm_rvq_partpop, partpopq) {
 936                 pa = VM_PAGE_TO_PHYS(&rv->pages[VM_LEVEL_0_NPAGES - 1]);
 937                 if (pa + PAGE_SIZE - size < low) {
 938                         /* This entire reservation is too low; go to next. */
 939                         continue;
 940                 }
 941                 pa = VM_PAGE_TO_PHYS(&rv->pages[0]);
 942                 if (pa + size > high) {
 943                         /* This entire reservation is too high; go to next. */
 944                         continue;
 945                 }
 946                 if (pa < low) {
 947                         /* Start the search for free pages at "low". */
 948                         i = (low - pa) / NBPOPMAP;
 949                         hi = (low - pa) % NBPOPMAP;
 950                 } else
 951                         i = hi = 0;
 952                 do {
 953                         /* Find the next free page. */
 954                         lo = ffsl(~(((1UL << hi) - 1) | rv->popmap[i]));
 955                         while (lo == 0 && ++i < NPOPMAP)
 956                                 lo = ffsl(~rv->popmap[i]);
 957                         if (i == NPOPMAP)
 958                                 break;
 959                         /* Convert from ffsl() to ordinary bit numbering. */
 960                         lo--;
 961                         next_free = NBPOPMAP * i + lo;
 962                         pa = VM_PAGE_TO_PHYS(&rv->pages[next_free]);
 963                         KASSERT(pa >= low,
 964                             ("vm_reserv_reclaim_contig: pa is too low"));
 965                         if (pa + size > high) {
 966                                 /* The rest of this reservation is too high. */
 967                                 break;
 968                         } else if ((pa & (alignment - 1)) != 0 ||
 969                             ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) {
 970                                 /* Continue with this reservation. */
 971                                 hi = lo;
 972                                 continue;
 973                         }
 974                         /* Find the next used page. */
 975                         hi = ffsl(rv->popmap[i] & ~((1UL << lo) - 1));
 976                         while (hi == 0 && ++i < NPOPMAP) {
 977                                 if ((NBPOPMAP * i - next_free) * PAGE_SIZE >=
 978                                     size) {
 979                                         vm_reserv_reclaim(rv);
 980                                         return (TRUE);
 981                                 }
 982                                 hi = ffsl(rv->popmap[i]);
 983                         }
 984                         /* Convert from ffsl() to ordinary bit numbering. */
 985                         if (i != NPOPMAP)
 986                                 hi--;
 987                         if ((NBPOPMAP * i + hi - next_free) * PAGE_SIZE >=
 988                             size) {
 989                                 vm_reserv_reclaim(rv);
 990                                 return (TRUE);
 991                         }
 992                 } while (i < NPOPMAP);
 993         }
 994         return (FALSE);
 995 }
 996
 997 /*
 998  * Transfers the reservation underlying the given page to a new object.
 999  *
1000  * The object must be locked.
1001  */
1002 void
1003 vm_reserv_rename(vm_page_t m, vm_object_t new_object, vm_object_t old_object,
1004     vm_pindex_t old_object_offset)
1005 {
1006         vm_reserv_t rv;
1007
1008         VM_OBJECT_ASSERT_WLOCKED(new_object);
1009         rv = vm_reserv_from_page(m);
1010         if (rv->object == old_object) {
1011                 mtx_lock(&vm_page_queue_free_mtx);
1012                 if (rv->object == old_object) {
1013                         LIST_REMOVE(rv, objq);
1014                         LIST_INSERT_HEAD(&new_object->rvq, rv, objq);
1015                         rv->object = new_object;
1016                         rv->pindex -= old_object_offset;
1017                 }
1018                 mtx_unlock(&vm_page_queue_free_mtx);
1019         }
1020 }
1021
1022 /*
1023  * Allocates the virtual and physical memory required by the reservation
1024  * management system's data structures, in particular, the reservation array.
1025  */
1026 vm_paddr_t
1027 vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end, vm_paddr_t high_water)
1028 {
1029         vm_paddr_t new_end;
1030         size_t size;
1031
1032         /*
1033          * Calculate the size (in bytes) of the reservation array.  Round up
1034          * from "high_water" because every small page is mapped to an element
1035          * in the reservation array based on its physical address.  Thus, the
1036          * number of elements in the reservation array can be greater than the
1037          * number of superpages.
1038          */
1039         size = howmany(high_water, VM_LEVEL_0_SIZE) * sizeof(struct vm_reserv);
1040
1041         /*
1042          * Allocate and map the physical memory for the reservation array.  The
1043          * next available virtual address is returned by reference.
1044          */
1045         new_end = end - round_page(size);
1046         vm_reserv_array = (void *)(uintptr_t)pmap_map(vaddr, new_end, end,
1047             VM_PROT_READ | VM_PROT_WRITE);
1048         bzero(vm_reserv_array, size);
1049
1050         /*
1051          * Return the next available physical address.
1052          */
1053         return (new_end);
1054 }
1055
1056 #endif  /* VM_NRESERVLEVEL > 0 */