sys/vm/vm_reserv.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2002-2006 Rice University
   5  * Copyright (c) 2007-2011 Alan L. Cox <alc@cs.rice.edu>
   6  * All rights reserved.
   7  *
   8  * This software was developed for the FreeBSD Project by Alan L. Cox,
   9  * Olivier Crameri, Peter Druschel, Sitaram Iyer, and Juan Navarro.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  23  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
  24  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
  27  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  28  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
  30  * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31  * POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 /*
  35  *      Superpage reservation management module
  36  *
  37  * Any external functions defined by this module are only to be used by the
  38  * virtual memory system.
  39  */
  40
  41 #include <sys/cdefs.h>
  42 __FBSDID("$FreeBSD$");
  43
  44 #include "opt_vm.h"
  45
  46 #include <sys/param.h>
  47 #include <sys/kernel.h>
  48 #include <sys/lock.h>
  49 #include <sys/malloc.h>
  50 #include <sys/mutex.h>
  51 #include <sys/queue.h>
  52 #include <sys/rwlock.h>
  53 #include <sys/sbuf.h>
  54 #include <sys/sysctl.h>
  55 #include <sys/systm.h>
  56 #include <sys/bitstring.h>
  57 #include <sys/counter.h>
  58 #include <sys/ktr.h>
  59 #include <sys/vmmeter.h>
  60 #include <sys/smp.h>
  61
  62 #include <vm/vm.h>
  63 #include <vm/vm_extern.h>
  64 #include <vm/vm_param.h>
  65 #include <vm/vm_object.h>
  66 #include <vm/vm_page.h>
  67 #include <vm/vm_pageout.h>
  68 #include <vm/vm_pagequeue.h>
  69 #include <vm/vm_phys.h>
  70 #include <vm/vm_radix.h>
  71 #include <vm/vm_reserv.h>
  72
  73 /*
  74  * The reservation system supports the speculative allocation of large physical
  75  * pages ("superpages").  Speculative allocation enables the fully automatic
  76  * utilization of superpages by the virtual memory system.  In other words, no
  77  * programmatic directives are required to use superpages.
  78  */
  79
  80 #if VM_NRESERVLEVEL > 0
  81
  82 #ifndef VM_LEVEL_0_ORDER_MAX
  83 #define VM_LEVEL_0_ORDER_MAX    VM_LEVEL_0_ORDER
  84 #endif
  85
  86 /*
  87  * The number of small pages that are contained in a level 0 reservation
  88  */
  89 #define VM_LEVEL_0_NPAGES       (1 << VM_LEVEL_0_ORDER)
  90 #define VM_LEVEL_0_NPAGES_MAX   (1 << VM_LEVEL_0_ORDER_MAX)
  91
  92 /*
  93  * The number of bits by which a physical address is shifted to obtain the
  94  * reservation number
  95  */
  96 #define VM_LEVEL_0_SHIFT        (VM_LEVEL_0_ORDER + PAGE_SHIFT)
  97
  98 /*
  99  * The size of a level 0 reservation in bytes
 100  */
 101 #define VM_LEVEL_0_SIZE         (1 << VM_LEVEL_0_SHIFT)
 102
 103 /*
 104  * Computes the index of the small page underlying the given (object, pindex)
 105  * within the reservation's array of small pages.
 106  */
 107 #define VM_RESERV_INDEX(object, pindex) \
 108     (((object)->pg_color + (pindex)) & (VM_LEVEL_0_NPAGES - 1))
 109
 110 /*
 111  * Number of elapsed ticks before we update the LRU queue position.  Used
 112  * to reduce contention and churn on the list.
 113  */
 114 #define PARTPOPSLOP     1
 115
 116 /*
 117  * The reservation structure
 118  *
 119  * A reservation structure is constructed whenever a large physical page is
 120  * speculatively allocated to an object.  The reservation provides the small
 121  * physical pages for the range [pindex, pindex + VM_LEVEL_0_NPAGES) of offsets
 122  * within that object.  The reservation's "popcnt" tracks the number of these
 123  * small physical pages that are in use at any given time.  When and if the
 124  * reservation is not fully utilized, it appears in the queue of partially
 125  * populated reservations.  The reservation always appears on the containing
 126  * object's list of reservations.
 127  *
 128  * A partially populated reservation can be broken and reclaimed at any time.
 129  *
 130  * c - constant after boot
 131  * d - vm_reserv_domain_lock
 132  * o - vm_reserv_object_lock
 133  * r - vm_reserv_lock
 134  * s - vm_reserv_domain_scan_lock
 135  */
 136 struct vm_reserv {
 137         struct mtx      lock;                   /* reservation lock. */
 138         TAILQ_ENTRY(vm_reserv) partpopq;        /* (d, r) per-domain queue. */
 139         LIST_ENTRY(vm_reserv) objq;             /* (o, r) object queue */
 140         vm_object_t     object;                 /* (o, r) containing object */
 141         vm_pindex_t     pindex;                 /* (o, r) offset in object */
 142         vm_page_t       pages;                  /* (c) first page  */
 143         uint16_t        popcnt;                 /* (r) # of pages in use */
 144         uint8_t         domain;                 /* (c) NUMA domain. */
 145         char            inpartpopq;             /* (d, r) */
 146         int             lasttick;               /* (r) last pop update tick. */
 147         bitstr_t        bit_decl(popmap, VM_LEVEL_0_NPAGES_MAX);
 148                                                 /* (r) bit vector, used pages */
 149 };
 150
 151 TAILQ_HEAD(vm_reserv_queue, vm_reserv);
 152
 153 #define vm_reserv_lockptr(rv)           (&(rv)->lock)
 154 #define vm_reserv_assert_locked(rv)                                     \
 155             mtx_assert(vm_reserv_lockptr(rv), MA_OWNED)
 156 #define vm_reserv_lock(rv)              mtx_lock(vm_reserv_lockptr(rv))
 157 #define vm_reserv_trylock(rv)           mtx_trylock(vm_reserv_lockptr(rv))
 158 #define vm_reserv_unlock(rv)            mtx_unlock(vm_reserv_lockptr(rv))
 159
 160 /*
 161  * The reservation array
 162  *
 163  * This array is analoguous in function to vm_page_array.  It differs in the
 164  * respect that it may contain a greater number of useful reservation
 165  * structures than there are (physical) superpages.  These "invalid"
 166  * reservation structures exist to trade-off space for time in the
 167  * implementation of vm_reserv_from_page().  Invalid reservation structures are
 168  * distinguishable from "valid" reservation structures by inspecting the
 169  * reservation's "pages" field.  Invalid reservation structures have a NULL
 170  * "pages" field.
 171  *
 172  * vm_reserv_from_page() maps a small (physical) page to an element of this
 173  * array by computing a physical reservation number from the page's physical
 174  * address.  The physical reservation number is used as the array index.
 175  *
 176  * An "active" reservation is a valid reservation structure that has a non-NULL
 177  * "object" field and a non-zero "popcnt" field.  In other words, every active
 178  * reservation belongs to a particular object.  Moreover, every active
 179  * reservation has an entry in the containing object's list of reservations.
 180  */
 181 static vm_reserv_t vm_reserv_array;
 182
 183 /*
 184  * The per-domain partially populated reservation queues
 185  *
 186  * These queues enable the fast recovery of an unused free small page from a
 187  * partially populated reservation.  The reservation at the head of a queue
 188  * is the least recently changed, partially populated reservation.
 189  *
 190  * Access to this queue is synchronized by the per-domain reservation lock.
 191  * Threads reclaiming free pages from the queue must hold the per-domain scan
 192  * lock.
 193  */
 194 struct vm_reserv_domain {
 195         struct mtx              lock;
 196         struct vm_reserv_queue  partpop;        /* (d) */
 197         struct vm_reserv        marker;         /* (d, s) scan marker/lock */
 198 } __aligned(CACHE_LINE_SIZE);
 199
 200 static struct vm_reserv_domain vm_rvd[MAXMEMDOM];
 201
 202 #define vm_reserv_domain_lockptr(d)     (&vm_rvd[(d)].lock)
 203 #define vm_reserv_domain_assert_locked(d)       \
 204         mtx_assert(vm_reserv_domain_lockptr(d), MA_OWNED)
 205 #define vm_reserv_domain_lock(d)        mtx_lock(vm_reserv_domain_lockptr(d))
 206 #define vm_reserv_domain_unlock(d)      mtx_unlock(vm_reserv_domain_lockptr(d))
 207
 208 #define vm_reserv_domain_scan_lock(d)   mtx_lock(&vm_rvd[(d)].marker.lock)
 209 #define vm_reserv_domain_scan_unlock(d) mtx_unlock(&vm_rvd[(d)].marker.lock)
 210
 211 static SYSCTL_NODE(_vm, OID_AUTO, reserv, CTLFLAG_RD | CTLFLAG_MPSAFE, 0,
 212     "Reservation Info");
 213
 214 static COUNTER_U64_DEFINE_EARLY(vm_reserv_broken);
 215 SYSCTL_COUNTER_U64(_vm_reserv, OID_AUTO, broken, CTLFLAG_RD,
 216     &vm_reserv_broken, "Cumulative number of broken reservations");
 217
 218 static COUNTER_U64_DEFINE_EARLY(vm_reserv_freed);
 219 SYSCTL_COUNTER_U64(_vm_reserv, OID_AUTO, freed, CTLFLAG_RD,
 220     &vm_reserv_freed, "Cumulative number of freed reservations");
 221
 222 static int sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS);
 223
 224 SYSCTL_PROC(_vm_reserv, OID_AUTO, fullpop, CTLTYPE_INT | CTLFLAG_MPSAFE | CTLFLAG_RD,
 225     NULL, 0, sysctl_vm_reserv_fullpop, "I", "Current number of full reservations");
 226
 227 static int sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS);
 228
 229 SYSCTL_OID(_vm_reserv, OID_AUTO, partpopq,
 230     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
 231     sysctl_vm_reserv_partpopq, "A",
 232     "Partially populated reservation queues");
 233
 234 static COUNTER_U64_DEFINE_EARLY(vm_reserv_reclaimed);
 235 SYSCTL_COUNTER_U64(_vm_reserv, OID_AUTO, reclaimed, CTLFLAG_RD,
 236     &vm_reserv_reclaimed, "Cumulative number of reclaimed reservations");
 237
 238 /*
 239  * The object lock pool is used to synchronize the rvq.  We can not use a
 240  * pool mutex because it is required before malloc works.
 241  *
 242  * The "hash" function could be made faster without divide and modulo.
 243  */
 244 #define VM_RESERV_OBJ_LOCK_COUNT        MAXCPU
 245
 246 struct mtx_padalign vm_reserv_object_mtx[VM_RESERV_OBJ_LOCK_COUNT];
 247
 248 #define vm_reserv_object_lock_idx(object)                       \
 249             (((uintptr_t)object / sizeof(*object)) % VM_RESERV_OBJ_LOCK_COUNT)
 250 #define vm_reserv_object_lock_ptr(object)                       \
 251             &vm_reserv_object_mtx[vm_reserv_object_lock_idx((object))]
 252 #define vm_reserv_object_lock(object)                           \
 253             mtx_lock(vm_reserv_object_lock_ptr((object)))
 254 #define vm_reserv_object_unlock(object)                         \
 255             mtx_unlock(vm_reserv_object_lock_ptr((object)))
 256
 257 static void             vm_reserv_break(vm_reserv_t rv);
 258 static void             vm_reserv_depopulate(vm_reserv_t rv, int index);
 259 static vm_reserv_t      vm_reserv_from_page(vm_page_t m);
 260 static boolean_t        vm_reserv_has_pindex(vm_reserv_t rv,
 261                             vm_pindex_t pindex);
 262 static void             vm_reserv_populate(vm_reserv_t rv, int index);
 263 static void             vm_reserv_reclaim(vm_reserv_t rv);
 264
 265 /*
 266  * Returns the current number of full reservations.
 267  *
 268  * Since the number of full reservations is computed without acquiring any
 269  * locks, the returned value is inexact.
 270  */
 271 static int
 272 sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS)
 273 {
 274         vm_paddr_t paddr;
 275         struct vm_phys_seg *seg;
 276         vm_reserv_t rv;
 277         int fullpop, segind;
 278
 279         fullpop = 0;
 280         for (segind = 0; segind < vm_phys_nsegs; segind++) {
 281                 seg = &vm_phys_segs[segind];
 282                 paddr = roundup2(seg->start, VM_LEVEL_0_SIZE);
 283 #ifdef VM_PHYSSEG_SPARSE
 284                 rv = seg->first_reserv + (paddr >> VM_LEVEL_0_SHIFT) -
 285                     (seg->start >> VM_LEVEL_0_SHIFT);
 286 #else
 287                 rv = &vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT];
 288 #endif
 289                 while (paddr + VM_LEVEL_0_SIZE > paddr && paddr +
 290                     VM_LEVEL_0_SIZE <= seg->end) {
 291                         fullpop += rv->popcnt == VM_LEVEL_0_NPAGES;
 292                         paddr += VM_LEVEL_0_SIZE;
 293                         rv++;
 294                 }
 295         }
 296         return (sysctl_handle_int(oidp, &fullpop, 0, req));
 297 }
 298
 299 /*
 300  * Describes the current state of the partially populated reservation queue.
 301  */
 302 static int
 303 sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS)
 304 {
 305         struct sbuf sbuf;
 306         vm_reserv_t rv;
 307         int counter, error, domain, level, unused_pages;
 308
 309         error = sysctl_wire_old_buffer(req, 0);
 310         if (error != 0)
 311                 return (error);
 312         sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
 313         sbuf_printf(&sbuf, "\nDOMAIN    LEVEL     SIZE  NUMBER\n\n");
 314         for (domain = 0; domain < vm_ndomains; domain++) {
 315                 for (level = -1; level <= VM_NRESERVLEVEL - 2; level++) {
 316                         counter = 0;
 317                         unused_pages = 0;
 318                         vm_reserv_domain_lock(domain);
 319                         TAILQ_FOREACH(rv, &vm_rvd[domain].partpop, partpopq) {
 320                                 if (rv == &vm_rvd[domain].marker)
 321                                         continue;
 322                                 counter++;
 323                                 unused_pages += VM_LEVEL_0_NPAGES - rv->popcnt;
 324                         }
 325                         vm_reserv_domain_unlock(domain);
 326                         sbuf_printf(&sbuf, "%6d, %7d, %6dK, %6d\n",
 327                             domain, level,
 328                             unused_pages * ((int)PAGE_SIZE / 1024), counter);
 329                 }
 330         }
 331         error = sbuf_finish(&sbuf);
 332         sbuf_delete(&sbuf);
 333         return (error);
 334 }
 335
 336 /*
 337  * Remove a reservation from the object's objq.
 338  */
 339 static void
 340 vm_reserv_remove(vm_reserv_t rv)
 341 {
 342         vm_object_t object;
 343
 344         vm_reserv_assert_locked(rv);
 345         CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d",
 346             __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq);
 347         KASSERT(rv->object != NULL,
 348             ("vm_reserv_remove: reserv %p is free", rv));
 349         KASSERT(!rv->inpartpopq,
 350             ("vm_reserv_remove: reserv %p's inpartpopq is TRUE", rv));
 351         object = rv->object;
 352         vm_reserv_object_lock(object);
 353         LIST_REMOVE(rv, objq);
 354         rv->object = NULL;
 355         vm_reserv_object_unlock(object);
 356 }
 357
 358 /*
 359  * Insert a new reservation into the object's objq.
 360  */
 361 static void
 362 vm_reserv_insert(vm_reserv_t rv, vm_object_t object, vm_pindex_t pindex)
 363 {
 364
 365         vm_reserv_assert_locked(rv);
 366         CTR6(KTR_VM,
 367             "%s: rv %p(%p) object %p new %p popcnt %d",
 368             __FUNCTION__, rv, rv->pages, rv->object, object,
 369            rv->popcnt);
 370         KASSERT(rv->object == NULL,
 371             ("vm_reserv_insert: reserv %p isn't free", rv));
 372         KASSERT(rv->popcnt == 0,
 373             ("vm_reserv_insert: reserv %p's popcnt is corrupted", rv));
 374         KASSERT(!rv->inpartpopq,
 375             ("vm_reserv_insert: reserv %p's inpartpopq is TRUE", rv));
 376         KASSERT(bit_ntest(rv->popmap, 0, VM_LEVEL_0_NPAGES - 1, 0),
 377             ("vm_reserv_insert: reserv %p's popmap is corrupted", rv));
 378         vm_reserv_object_lock(object);
 379         rv->pindex = pindex;
 380         rv->object = object;
 381         rv->lasttick = ticks;
 382         LIST_INSERT_HEAD(&object->rvq, rv, objq);
 383         vm_reserv_object_unlock(object);
 384 }
 385
 386 /*
 387  * Reduces the given reservation's population count.  If the population count
 388  * becomes zero, the reservation is destroyed.  Additionally, moves the
 389  * reservation to the tail of the partially populated reservation queue if the
 390  * population count is non-zero.
 391  */
 392 static void
 393 vm_reserv_depopulate(vm_reserv_t rv, int index)
 394 {
 395         struct vm_domain *vmd;
 396
 397         vm_reserv_assert_locked(rv);
 398         CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d",
 399             __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq);
 400         KASSERT(rv->object != NULL,
 401             ("vm_reserv_depopulate: reserv %p is free", rv));
 402         KASSERT(bit_test(rv->popmap, index),
 403             ("vm_reserv_depopulate: reserv %p's popmap[%d] is clear", rv,
 404             index));
 405         KASSERT(rv->popcnt > 0,
 406             ("vm_reserv_depopulate: reserv %p's popcnt is corrupted", rv));
 407         KASSERT(rv->domain < vm_ndomains,
 408             ("vm_reserv_depopulate: reserv %p's domain is corrupted %d",
 409             rv, rv->domain));
 410         if (rv->popcnt == VM_LEVEL_0_NPAGES) {
 411                 KASSERT(rv->pages->psind == 1,
 412                     ("vm_reserv_depopulate: reserv %p is already demoted",
 413                     rv));
 414                 rv->pages->psind = 0;
 415         }
 416         bit_clear(rv->popmap, index);
 417         rv->popcnt--;
 418         if ((unsigned)(ticks - rv->lasttick) >= PARTPOPSLOP ||
 419             rv->popcnt == 0) {
 420                 vm_reserv_domain_lock(rv->domain);
 421                 if (rv->inpartpopq) {
 422                         TAILQ_REMOVE(&vm_rvd[rv->domain].partpop, rv, partpopq);
 423                         rv->inpartpopq = FALSE;
 424                 }
 425                 if (rv->popcnt != 0) {
 426                         rv->inpartpopq = TRUE;
 427                         TAILQ_INSERT_TAIL(&vm_rvd[rv->domain].partpop, rv,
 428                             partpopq);
 429                 }
 430                 vm_reserv_domain_unlock(rv->domain);
 431                 rv->lasttick = ticks;
 432         }
 433         vmd = VM_DOMAIN(rv->domain);
 434         if (rv->popcnt == 0) {
 435                 vm_reserv_remove(rv);
 436                 vm_domain_free_lock(vmd);
 437                 vm_phys_free_pages(rv->pages, VM_LEVEL_0_ORDER);
 438                 vm_domain_free_unlock(vmd);
 439                 counter_u64_add(vm_reserv_freed, 1);
 440         }
 441         vm_domain_freecnt_inc(vmd, 1);
 442 }
 443
 444 /*
 445  * Returns the reservation to which the given page might belong.
 446  */
 447 static __inline vm_reserv_t
 448 vm_reserv_from_page(vm_page_t m)
 449 {
 450 #ifdef VM_PHYSSEG_SPARSE
 451         struct vm_phys_seg *seg;
 452
 453         seg = &vm_phys_segs[m->segind];
 454         return (seg->first_reserv + (VM_PAGE_TO_PHYS(m) >> VM_LEVEL_0_SHIFT) -
 455             (seg->start >> VM_LEVEL_0_SHIFT));
 456 #else
 457         return (&vm_reserv_array[VM_PAGE_TO_PHYS(m) >> VM_LEVEL_0_SHIFT]);
 458 #endif
 459 }
 460
 461 /*
 462  * Returns an existing reservation or NULL and initialized successor pointer.
 463  */
 464 static vm_reserv_t
 465 vm_reserv_from_object(vm_object_t object, vm_pindex_t pindex,
 466     vm_page_t mpred, vm_page_t *msuccp)
 467 {
 468         vm_reserv_t rv;
 469         vm_page_t msucc;
 470
 471         msucc = NULL;
 472         if (mpred != NULL) {
 473                 KASSERT(mpred->object == object,
 474                     ("vm_reserv_from_object: object doesn't contain mpred"));
 475                 KASSERT(mpred->pindex < pindex,
 476                     ("vm_reserv_from_object: mpred doesn't precede pindex"));
 477                 rv = vm_reserv_from_page(mpred);
 478                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
 479                         goto found;
 480                 msucc = TAILQ_NEXT(mpred, listq);
 481         } else
 482                 msucc = TAILQ_FIRST(&object->memq);
 483         if (msucc != NULL) {
 484                 KASSERT(msucc->pindex > pindex,
 485                     ("vm_reserv_from_object: msucc doesn't succeed pindex"));
 486                 rv = vm_reserv_from_page(msucc);
 487                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
 488                         goto found;
 489         }
 490         rv = NULL;
 491
 492 found:
 493         *msuccp = msucc;
 494
 495         return (rv);
 496 }
 497
 498 /*
 499  * Returns TRUE if the given reservation contains the given page index and
 500  * FALSE otherwise.
 501  */
 502 static __inline boolean_t
 503 vm_reserv_has_pindex(vm_reserv_t rv, vm_pindex_t pindex)
 504 {
 505
 506         return (((pindex - rv->pindex) & ~(VM_LEVEL_0_NPAGES - 1)) == 0);
 507 }
 508
 509 /*
 510  * Increases the given reservation's population count.  Moves the reservation
 511  * to the tail of the partially populated reservation queue.
 512  */
 513 static void
 514 vm_reserv_populate(vm_reserv_t rv, int index)
 515 {
 516
 517         vm_reserv_assert_locked(rv);
 518         CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d",
 519             __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq);
 520         KASSERT(rv->object != NULL,
 521             ("vm_reserv_populate: reserv %p is free", rv));
 522         KASSERT(!bit_test(rv->popmap, index),
 523             ("vm_reserv_populate: reserv %p's popmap[%d] is set", rv,
 524             index));
 525         KASSERT(rv->popcnt < VM_LEVEL_0_NPAGES,
 526             ("vm_reserv_populate: reserv %p is already full", rv));
 527         KASSERT(rv->pages->psind == 0,
 528             ("vm_reserv_populate: reserv %p is already promoted", rv));
 529         KASSERT(rv->domain < vm_ndomains,
 530             ("vm_reserv_populate: reserv %p's domain is corrupted %d",
 531             rv, rv->domain));
 532         bit_set(rv->popmap, index);
 533         rv->popcnt++;
 534         if ((unsigned)(ticks - rv->lasttick) < PARTPOPSLOP &&
 535             rv->inpartpopq && rv->popcnt != VM_LEVEL_0_NPAGES)
 536                 return;
 537         rv->lasttick = ticks;
 538         vm_reserv_domain_lock(rv->domain);
 539         if (rv->inpartpopq) {
 540                 TAILQ_REMOVE(&vm_rvd[rv->domain].partpop, rv, partpopq);
 541                 rv->inpartpopq = FALSE;
 542         }
 543         if (rv->popcnt < VM_LEVEL_0_NPAGES) {
 544                 rv->inpartpopq = TRUE;
 545                 TAILQ_INSERT_TAIL(&vm_rvd[rv->domain].partpop, rv, partpopq);
 546         } else {
 547                 KASSERT(rv->pages->psind == 0,
 548                     ("vm_reserv_populate: reserv %p is already promoted",
 549                     rv));
 550                 rv->pages->psind = 1;
 551         }
 552         vm_reserv_domain_unlock(rv->domain);
 553 }
 554
 555 /*
 556  * Allocates a contiguous set of physical pages of the given size "npages"
 557  * from existing or newly created reservations.  All of the physical pages
 558  * must be at or above the given physical address "low" and below the given
 559  * physical address "high".  The given value "alignment" determines the
 560  * alignment of the first physical page in the set.  If the given value
 561  * "boundary" is non-zero, then the set of physical pages cannot cross any
 562  * physical address boundary that is a multiple of that value.  Both
 563  * "alignment" and "boundary" must be a power of two.
 564  *
 565  * The page "mpred" must immediately precede the offset "pindex" within the
 566  * specified object.
 567  *
 568  * The object must be locked.
 569  */
 570 vm_page_t
 571 vm_reserv_alloc_contig(vm_object_t object, vm_pindex_t pindex, int domain,
 572     int req, vm_page_t mpred, u_long npages, vm_paddr_t low, vm_paddr_t high,
 573     u_long alignment, vm_paddr_t boundary)
 574 {
 575         struct vm_domain *vmd;
 576         vm_paddr_t pa, size;
 577         vm_page_t m, m_ret, msucc;
 578         vm_pindex_t first, leftcap, rightcap;
 579         vm_reserv_t rv;
 580         u_long allocpages, maxpages, minpages;
 581         int i, index, n;
 582
 583         VM_OBJECT_ASSERT_WLOCKED(object);
 584         KASSERT(npages != 0, ("vm_reserv_alloc_contig: npages is 0"));
 585
 586         /*
 587          * Is a reservation fundamentally impossible?
 588          */
 589         if (pindex < VM_RESERV_INDEX(object, pindex) ||
 590             pindex + npages > object->size)
 591                 return (NULL);
 592
 593         /*
 594          * All reservations of a particular size have the same alignment.
 595          * Assuming that the first page is allocated from a reservation, the
 596          * least significant bits of its physical address can be determined
 597          * from its offset from the beginning of the reservation and the size
 598          * of the reservation.
 599          *
 600          * Could the specified index within a reservation of the smallest
 601          * possible size satisfy the alignment and boundary requirements?
 602          */
 603         pa = VM_RESERV_INDEX(object, pindex) << PAGE_SHIFT;
 604         size = npages << PAGE_SHIFT;
 605         if (!vm_addr_ok(pa, size, alignment, boundary))
 606                 return (NULL);
 607
 608         /*
 609          * Look for an existing reservation.
 610          */
 611         rv = vm_reserv_from_object(object, pindex, mpred, &msucc);
 612         if (rv != NULL) {
 613                 KASSERT(object != kernel_object || rv->domain == domain,
 614                     ("vm_reserv_alloc_contig: domain mismatch"));
 615                 index = VM_RESERV_INDEX(object, pindex);
 616                 /* Does the allocation fit within the reservation? */
 617                 if (index + npages > VM_LEVEL_0_NPAGES)
 618                         return (NULL);
 619                 domain = rv->domain;
 620                 vmd = VM_DOMAIN(domain);
 621                 vm_reserv_lock(rv);
 622                 /* Handle reclaim race. */
 623                 if (rv->object != object)
 624                         goto out;
 625                 m = &rv->pages[index];
 626                 pa = VM_PAGE_TO_PHYS(m);
 627                 if (pa < low || pa + size > high ||
 628                     !vm_addr_ok(pa, size, alignment, boundary))
 629                         goto out;
 630                 /* Handle vm_page_rename(m, new_object, ...). */
 631                 if (!bit_ntest(rv->popmap, index, index + npages - 1, 0))
 632                         goto out;
 633                 if (!vm_domain_allocate(vmd, req, npages))
 634                         goto out;
 635                 for (i = 0; i < npages; i++)
 636                         vm_reserv_populate(rv, index + i);
 637                 vm_reserv_unlock(rv);
 638                 return (m);
 639 out:
 640                 vm_reserv_unlock(rv);
 641                 return (NULL);
 642         }
 643
 644         /*
 645          * Could at least one reservation fit between the first index to the
 646          * left that can be used ("leftcap") and the first index to the right
 647          * that cannot be used ("rightcap")?
 648          *
 649          * We must synchronize with the reserv object lock to protect the
 650          * pindex/object of the resulting reservations against rename while
 651          * we are inspecting.
 652          */
 653         first = pindex - VM_RESERV_INDEX(object, pindex);
 654         minpages = VM_RESERV_INDEX(object, pindex) + npages;
 655         maxpages = roundup2(minpages, VM_LEVEL_0_NPAGES);
 656         allocpages = maxpages;
 657         vm_reserv_object_lock(object);
 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                         vm_reserv_object_unlock(object);
 665                         return (NULL);
 666                 }
 667         }
 668         if (msucc != NULL) {
 669                 if ((rv = vm_reserv_from_page(msucc))->object != object)
 670                         rightcap = msucc->pindex;
 671                 else
 672                         rightcap = rv->pindex;
 673                 if (first + maxpages > rightcap) {
 674                         if (maxpages == VM_LEVEL_0_NPAGES) {
 675                                 vm_reserv_object_unlock(object);
 676                                 return (NULL);
 677                         }
 678
 679                         /*
 680                          * At least one reservation will fit between "leftcap"
 681                          * and "rightcap".  However, a reservation for the
 682                          * last of the requested pages will not fit.  Reduce
 683                          * the size of the upcoming allocation accordingly.
 684                          */
 685                         allocpages = minpages;
 686                 }
 687         }
 688         vm_reserv_object_unlock(object);
 689
 690         /*
 691          * Would the last new reservation extend past the end of the object?
 692          *
 693          * If the object is unlikely to grow don't allocate a reservation for
 694          * the tail.
 695          */
 696         if ((object->flags & OBJ_ANON) == 0 &&
 697             first + maxpages > object->size) {
 698                 if (maxpages == VM_LEVEL_0_NPAGES)
 699                         return (NULL);
 700                 allocpages = minpages;
 701         }
 702
 703         /*
 704          * Allocate the physical pages.  The alignment and boundary specified
 705          * for this allocation may be different from the alignment and
 706          * boundary specified for the requested pages.  For instance, the
 707          * specified index may not be the first page within the first new
 708          * reservation.
 709          */
 710         m = NULL;
 711         vmd = VM_DOMAIN(domain);
 712         if (vm_domain_allocate(vmd, req, npages)) {
 713                 vm_domain_free_lock(vmd);
 714                 m = vm_phys_alloc_contig(domain, allocpages, low, high,
 715                     ulmax(alignment, VM_LEVEL_0_SIZE),
 716                     boundary > VM_LEVEL_0_SIZE ? boundary : 0);
 717                 vm_domain_free_unlock(vmd);
 718                 if (m == NULL) {
 719                         vm_domain_freecnt_inc(vmd, npages);
 720                         return (NULL);
 721                 }
 722         } else
 723                 return (NULL);
 724         KASSERT(vm_page_domain(m) == domain,
 725             ("vm_reserv_alloc_contig: Page domain does not match requested."));
 726
 727         /*
 728          * The allocated physical pages always begin at a reservation
 729          * boundary, but they do not always end at a reservation boundary.
 730          * Initialize every reservation that is completely covered by the
 731          * allocated physical pages.
 732          */
 733         m_ret = NULL;
 734         index = VM_RESERV_INDEX(object, pindex);
 735         do {
 736                 rv = vm_reserv_from_page(m);
 737                 KASSERT(rv->pages == m,
 738                     ("vm_reserv_alloc_contig: reserv %p's pages is corrupted",
 739                     rv));
 740                 vm_reserv_lock(rv);
 741                 vm_reserv_insert(rv, object, first);
 742                 n = ulmin(VM_LEVEL_0_NPAGES - index, npages);
 743                 for (i = 0; i < n; i++)
 744                         vm_reserv_populate(rv, index + i);
 745                 npages -= n;
 746                 if (m_ret == NULL) {
 747                         m_ret = &rv->pages[index];
 748                         index = 0;
 749                 }
 750                 vm_reserv_unlock(rv);
 751                 m += VM_LEVEL_0_NPAGES;
 752                 first += VM_LEVEL_0_NPAGES;
 753                 allocpages -= VM_LEVEL_0_NPAGES;
 754         } while (allocpages >= VM_LEVEL_0_NPAGES);
 755         return (m_ret);
 756 }
 757
 758 /*
 759  * Allocate a physical page from an existing or newly created reservation.
 760  *
 761  * The page "mpred" must immediately precede the offset "pindex" within the
 762  * specified object.
 763  *
 764  * The object must be locked.
 765  */
 766 vm_page_t
 767 vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex, int domain,
 768     int req, vm_page_t mpred)
 769 {
 770         struct vm_domain *vmd;
 771         vm_page_t m, msucc;
 772         vm_pindex_t first, leftcap, rightcap;
 773         vm_reserv_t rv;
 774         int index;
 775
 776         VM_OBJECT_ASSERT_WLOCKED(object);
 777
 778         /*
 779          * Is a reservation fundamentally impossible?
 780          */
 781         if (pindex < VM_RESERV_INDEX(object, pindex) ||
 782             pindex >= object->size)
 783                 return (NULL);
 784
 785         /*
 786          * Look for an existing reservation.
 787          */
 788         rv = vm_reserv_from_object(object, pindex, mpred, &msucc);
 789         if (rv != NULL) {
 790                 KASSERT(object != kernel_object || rv->domain == domain,
 791                     ("vm_reserv_alloc_page: domain mismatch"));
 792                 domain = rv->domain;
 793                 vmd = VM_DOMAIN(domain);
 794                 index = VM_RESERV_INDEX(object, pindex);
 795                 m = &rv->pages[index];
 796                 vm_reserv_lock(rv);
 797                 /* Handle reclaim race. */
 798                 if (rv->object != object ||
 799                     /* Handle vm_page_rename(m, new_object, ...). */
 800                     bit_test(rv->popmap, index)) {
 801                         m = NULL;
 802                         goto out;
 803                 }
 804                 if (vm_domain_allocate(vmd, req, 1) == 0)
 805                         m = NULL;
 806                 else
 807                         vm_reserv_populate(rv, index);
 808 out:
 809                 vm_reserv_unlock(rv);
 810                 return (m);
 811         }
 812
 813         /*
 814          * Could a reservation fit between the first index to the left that
 815          * can be used and the first index to the right that cannot be used?
 816          *
 817          * We must synchronize with the reserv object lock to protect the
 818          * pindex/object of the resulting reservations against rename while
 819          * we are inspecting.
 820          */
 821         first = pindex - VM_RESERV_INDEX(object, pindex);
 822         vm_reserv_object_lock(object);
 823         if (mpred != NULL) {
 824                 if ((rv = vm_reserv_from_page(mpred))->object != object)
 825                         leftcap = mpred->pindex + 1;
 826                 else
 827                         leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
 828                 if (leftcap > first) {
 829                         vm_reserv_object_unlock(object);
 830                         return (NULL);
 831                 }
 832         }
 833         if (msucc != NULL) {
 834                 if ((rv = vm_reserv_from_page(msucc))->object != object)
 835                         rightcap = msucc->pindex;
 836                 else
 837                         rightcap = rv->pindex;
 838                 if (first + VM_LEVEL_0_NPAGES > rightcap) {
 839                         vm_reserv_object_unlock(object);
 840                         return (NULL);
 841                 }
 842         }
 843         vm_reserv_object_unlock(object);
 844
 845         /*
 846          * Would the last new reservation extend past the end of the object?
 847          *
 848          * If the object is unlikely to grow don't allocate a reservation for
 849          * the tail.
 850          */
 851         if ((object->flags & OBJ_ANON) == 0 &&
 852             first + VM_LEVEL_0_NPAGES > object->size)
 853                 return (NULL);
 854
 855         /*
 856          * Allocate and populate the new reservation.
 857          */
 858         m = NULL;
 859         vmd = VM_DOMAIN(domain);
 860         if (vm_domain_allocate(vmd, req, 1)) {
 861                 vm_domain_free_lock(vmd);
 862                 m = vm_phys_alloc_pages(domain, VM_FREEPOOL_DEFAULT,
 863                     VM_LEVEL_0_ORDER);
 864                 vm_domain_free_unlock(vmd);
 865                 if (m == NULL) {
 866                         vm_domain_freecnt_inc(vmd, 1);
 867                         return (NULL);
 868                 }
 869         } else
 870                 return (NULL);
 871         rv = vm_reserv_from_page(m);
 872         vm_reserv_lock(rv);
 873         KASSERT(rv->pages == m,
 874             ("vm_reserv_alloc_page: reserv %p's pages is corrupted", rv));
 875         vm_reserv_insert(rv, object, first);
 876         index = VM_RESERV_INDEX(object, pindex);
 877         vm_reserv_populate(rv, index);
 878         vm_reserv_unlock(rv);
 879
 880         return (&rv->pages[index]);
 881 }
 882
 883 /*
 884  * Breaks the given reservation.  All free pages in the reservation
 885  * are returned to the physical memory allocator.  The reservation's
 886  * population count and map are reset to their initial state.
 887  *
 888  * The given reservation must not be in the partially populated reservation
 889  * queue.
 890  */
 891 static void
 892 vm_reserv_break(vm_reserv_t rv)
 893 {
 894         int hi, lo, pos;
 895
 896         vm_reserv_assert_locked(rv);
 897         CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d",
 898             __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq);
 899         vm_reserv_remove(rv);
 900         rv->pages->psind = 0;
 901         hi = lo = -1;
 902         pos = 0;
 903         for (;;) {
 904                 bit_ff_at(rv->popmap, pos, VM_LEVEL_0_NPAGES, lo != hi, &pos);
 905                 if (lo == hi) {
 906                         if (pos == -1)
 907                                 break;
 908                         lo = pos;
 909                         continue;
 910                 }
 911                 if (pos == -1)
 912                         pos = VM_LEVEL_0_NPAGES;
 913                 hi = pos;
 914                 vm_domain_free_lock(VM_DOMAIN(rv->domain));
 915                 vm_phys_enqueue_contig(&rv->pages[lo], hi - lo);
 916                 vm_domain_free_unlock(VM_DOMAIN(rv->domain));
 917                 lo = hi;
 918         }
 919         bit_nclear(rv->popmap, 0, VM_LEVEL_0_NPAGES - 1);
 920         rv->popcnt = 0;
 921         counter_u64_add(vm_reserv_broken, 1);
 922 }
 923
 924 /*
 925  * Breaks all reservations belonging to the given object.
 926  */
 927 void
 928 vm_reserv_break_all(vm_object_t object)
 929 {
 930         vm_reserv_t rv;
 931
 932         /*
 933          * This access of object->rvq is unsynchronized so that the
 934          * object rvq lock can nest after the domain_free lock.  We
 935          * must check for races in the results.  However, the object
 936          * lock prevents new additions, so we are guaranteed that when
 937          * it returns NULL the object is properly empty.
 938          */
 939         while ((rv = LIST_FIRST(&object->rvq)) != NULL) {
 940                 vm_reserv_lock(rv);
 941                 /* Reclaim race. */
 942                 if (rv->object != object) {
 943                         vm_reserv_unlock(rv);
 944                         continue;
 945                 }
 946                 vm_reserv_domain_lock(rv->domain);
 947                 if (rv->inpartpopq) {
 948                         TAILQ_REMOVE(&vm_rvd[rv->domain].partpop, rv, partpopq);
 949                         rv->inpartpopq = FALSE;
 950                 }
 951                 vm_reserv_domain_unlock(rv->domain);
 952                 vm_reserv_break(rv);
 953                 vm_reserv_unlock(rv);
 954         }
 955 }
 956
 957 /*
 958  * Frees the given page if it belongs to a reservation.  Returns TRUE if the
 959  * page is freed and FALSE otherwise.
 960  */
 961 boolean_t
 962 vm_reserv_free_page(vm_page_t m)
 963 {
 964         vm_reserv_t rv;
 965         boolean_t ret;
 966
 967         rv = vm_reserv_from_page(m);
 968         if (rv->object == NULL)
 969                 return (FALSE);
 970         vm_reserv_lock(rv);
 971         /* Re-validate after lock. */
 972         if (rv->object != NULL) {
 973                 vm_reserv_depopulate(rv, m - rv->pages);
 974                 ret = TRUE;
 975         } else
 976                 ret = FALSE;
 977         vm_reserv_unlock(rv);
 978
 979         return (ret);
 980 }
 981
 982 /*
 983  * Initializes the reservation management system.  Specifically, initializes
 984  * the reservation array.
 985  *
 986  * Requires that vm_page_array and first_page are initialized!
 987  */
 988 void
 989 vm_reserv_init(void)
 990 {
 991         vm_paddr_t paddr;
 992         struct vm_phys_seg *seg;
 993         struct vm_reserv *rv;
 994         struct vm_reserv_domain *rvd;
 995 #ifdef VM_PHYSSEG_SPARSE
 996         vm_pindex_t used;
 997 #endif
 998         int i, segind;
 999
1000         /*
1001          * Initialize the reservation array.  Specifically, initialize the
1002          * "pages" field for every element that has an underlying superpage.
1003          */
1004 #ifdef VM_PHYSSEG_SPARSE
1005         used = 0;
1006 #endif
1007         for (segind = 0; segind < vm_phys_nsegs; segind++) {
1008                 seg = &vm_phys_segs[segind];
1009 #ifdef VM_PHYSSEG_SPARSE
1010                 seg->first_reserv = &vm_reserv_array[used];
1011                 used += howmany(seg->end, VM_LEVEL_0_SIZE) -
1012                     seg->start / VM_LEVEL_0_SIZE;
1013 #else
1014                 seg->first_reserv =
1015                     &vm_reserv_array[seg->start >> VM_LEVEL_0_SHIFT];
1016 #endif
1017                 paddr = roundup2(seg->start, VM_LEVEL_0_SIZE);
1018                 rv = seg->first_reserv + (paddr >> VM_LEVEL_0_SHIFT) -
1019                     (seg->start >> VM_LEVEL_0_SHIFT);
1020                 while (paddr + VM_LEVEL_0_SIZE > paddr && paddr +
1021                     VM_LEVEL_0_SIZE <= seg->end) {
1022                         rv->pages = PHYS_TO_VM_PAGE(paddr);
1023                         rv->domain = seg->domain;
1024                         mtx_init(&rv->lock, "vm reserv", NULL, MTX_DEF);
1025                         paddr += VM_LEVEL_0_SIZE;
1026                         rv++;
1027                 }
1028         }
1029         for (i = 0; i < MAXMEMDOM; i++) {
1030                 rvd = &vm_rvd[i];
1031                 mtx_init(&rvd->lock, "vm reserv domain", NULL, MTX_DEF);
1032                 TAILQ_INIT(&rvd->partpop);
1033                 mtx_init(&rvd->marker.lock, "vm reserv marker", NULL, MTX_DEF);
1034
1035                 /*
1036                  * Fully populated reservations should never be present in the
1037                  * partially populated reservation queues.
1038                  */
1039                 rvd->marker.popcnt = VM_LEVEL_0_NPAGES;
1040                 bit_nset(rvd->marker.popmap, 0, VM_LEVEL_0_NPAGES - 1);
1041         }
1042
1043         for (i = 0; i < VM_RESERV_OBJ_LOCK_COUNT; i++)
1044                 mtx_init(&vm_reserv_object_mtx[i], "resv obj lock", NULL,
1045                     MTX_DEF);
1046 }
1047
1048 /*
1049  * Returns true if the given page belongs to a reservation and that page is
1050  * free.  Otherwise, returns false.
1051  */
1052 bool
1053 vm_reserv_is_page_free(vm_page_t m)
1054 {
1055         vm_reserv_t rv;
1056
1057         rv = vm_reserv_from_page(m);
1058         if (rv->object == NULL)
1059                 return (false);
1060         return (!bit_test(rv->popmap, m - rv->pages));
1061 }
1062
1063 /*
1064  * If the given page belongs to a reservation, returns the level of that
1065  * reservation.  Otherwise, returns -1.
1066  */
1067 int
1068 vm_reserv_level(vm_page_t m)
1069 {
1070         vm_reserv_t rv;
1071
1072         rv = vm_reserv_from_page(m);
1073         return (rv->object != NULL ? 0 : -1);
1074 }
1075
1076 /*
1077  * Returns a reservation level if the given page belongs to a fully populated
1078  * reservation and -1 otherwise.
1079  */
1080 int
1081 vm_reserv_level_iffullpop(vm_page_t m)
1082 {
1083         vm_reserv_t rv;
1084
1085         rv = vm_reserv_from_page(m);
1086         return (rv->popcnt == VM_LEVEL_0_NPAGES ? 0 : -1);
1087 }
1088
1089 /*
1090  * Remove a partially populated reservation from the queue.
1091  */
1092 static void
1093 vm_reserv_dequeue(vm_reserv_t rv)
1094 {
1095
1096         vm_reserv_domain_assert_locked(rv->domain);
1097         vm_reserv_assert_locked(rv);
1098         CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d",
1099             __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq);
1100         KASSERT(rv->inpartpopq,
1101             ("vm_reserv_reclaim: reserv %p's inpartpopq is FALSE", rv));
1102
1103         TAILQ_REMOVE(&vm_rvd[rv->domain].partpop, rv, partpopq);
1104         rv->inpartpopq = FALSE;
1105 }
1106
1107 /*
1108  * Breaks the given partially populated reservation, releasing its free pages
1109  * to the physical memory allocator.
1110  */
1111 static void
1112 vm_reserv_reclaim(vm_reserv_t rv)
1113 {
1114
1115         vm_reserv_assert_locked(rv);
1116         CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d",
1117             __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq);
1118         if (rv->inpartpopq) {
1119                 vm_reserv_domain_lock(rv->domain);
1120                 vm_reserv_dequeue(rv);
1121                 vm_reserv_domain_unlock(rv->domain);
1122         }
1123         vm_reserv_break(rv);
1124         counter_u64_add(vm_reserv_reclaimed, 1);
1125 }
1126
1127 /*
1128  * Breaks a reservation near the head of the partially populated reservation
1129  * queue, releasing its free pages to the physical memory allocator.  Returns
1130  * TRUE if a reservation is broken and FALSE otherwise.
1131  */
1132 bool
1133 vm_reserv_reclaim_inactive(int domain)
1134 {
1135         vm_reserv_t rv;
1136
1137         vm_reserv_domain_lock(domain);
1138         TAILQ_FOREACH(rv, &vm_rvd[domain].partpop, partpopq) {
1139                 /*
1140                  * A locked reservation is likely being updated or reclaimed,
1141                  * so just skip ahead.
1142                  */
1143                 if (rv != &vm_rvd[domain].marker && vm_reserv_trylock(rv)) {
1144                         vm_reserv_dequeue(rv);
1145                         break;
1146                 }
1147         }
1148         vm_reserv_domain_unlock(domain);
1149         if (rv != NULL) {
1150                 vm_reserv_reclaim(rv);
1151                 vm_reserv_unlock(rv);
1152                 return (true);
1153         }
1154         return (false);
1155 }
1156
1157 /*
1158  * Determine whether this reservation has free pages that satisfy the given
1159  * request for contiguous physical memory.  Start searching from the lower
1160  * bound, defined by lo, and stop at the upper bound, hi.  Return the index
1161  * of the first satisfactory free page, or -1 if none is found.
1162  */
1163 static int
1164 vm_reserv_find_contig(vm_reserv_t rv, int npages, int lo,
1165     int hi, int ppn_align, int ppn_bound)
1166 {
1167
1168         vm_reserv_assert_locked(rv);
1169         KASSERT(npages <= VM_LEVEL_0_NPAGES - 1,
1170             ("%s: Too many pages", __func__));
1171         KASSERT(ppn_bound <= VM_LEVEL_0_NPAGES,
1172             ("%s: Too big a boundary for reservation size", __func__));
1173         KASSERT(npages <= ppn_bound,
1174             ("%s: Too many pages for given boundary", __func__));
1175         KASSERT(ppn_align != 0 && powerof2(ppn_align),
1176             ("ppn_align is not a positive power of 2"));
1177         KASSERT(ppn_bound != 0 && powerof2(ppn_bound),
1178             ("ppn_bound is not a positive power of 2"));
1179         while (bit_ffc_area_at(rv->popmap, lo, hi, npages, &lo), lo != -1) {
1180                 if (lo < roundup2(lo, ppn_align)) {
1181                         /* Skip to next aligned page. */
1182                         lo = roundup2(lo, ppn_align);
1183                 } else if (roundup2(lo + 1, ppn_bound) >= lo + npages)
1184                         return (lo);
1185                 if (roundup2(lo + 1, ppn_bound) < lo + npages) {
1186                         /* Skip to next boundary-matching page. */
1187                         lo = roundup2(lo + 1, ppn_bound);
1188                 }
1189         }
1190         return (-1);
1191 }
1192
1193 /*
1194  * Searches the partially populated reservation queue for the least recently
1195  * changed reservation with free pages that satisfy the given request for
1196  * contiguous physical memory.  If a satisfactory reservation is found, it is
1197  * broken.  Returns true if a reservation is broken and false otherwise.
1198  */
1199 vm_page_t
1200 vm_reserv_reclaim_contig(int domain, u_long npages, vm_paddr_t low,
1201     vm_paddr_t high, u_long alignment, vm_paddr_t boundary)
1202 {
1203         struct vm_reserv_queue *queue;
1204         vm_paddr_t pa, size;
1205         vm_page_t m_ret;
1206         vm_reserv_t marker, rv, rvn;
1207         int hi, lo, posn, ppn_align, ppn_bound;
1208
1209         KASSERT(npages > 0, ("npages is 0"));
1210         KASSERT(powerof2(alignment), ("alignment is not a power of 2"));
1211         KASSERT(powerof2(boundary), ("boundary is not a power of 2"));
1212         if (npages > VM_LEVEL_0_NPAGES - 1)
1213                 return (false);
1214         size = npages << PAGE_SHIFT;
1215         /*
1216          * Ensure that a free range starting at a boundary-multiple
1217          * doesn't include a boundary-multiple within it.  Otherwise,
1218          * no boundary-constrained allocation is possible.
1219          */
1220         if (!vm_addr_bound_ok(0, size, boundary))
1221                 return (NULL);
1222         marker = &vm_rvd[domain].marker;
1223         queue = &vm_rvd[domain].partpop;
1224         /*
1225          * Compute shifted alignment, boundary values for page-based
1226          * calculations.  Constrain to range [1, VM_LEVEL_0_NPAGES] to
1227          * avoid overflow.
1228          */
1229         ppn_align = (int)(ulmin(ulmax(PAGE_SIZE, alignment),
1230             VM_LEVEL_0_SIZE) >> PAGE_SHIFT);
1231         ppn_bound = boundary == 0 ? VM_LEVEL_0_NPAGES :
1232             (int)(MIN(MAX(PAGE_SIZE, boundary),
1233             VM_LEVEL_0_SIZE) >> PAGE_SHIFT);
1234
1235         vm_reserv_domain_scan_lock(domain);
1236         vm_reserv_domain_lock(domain);
1237         TAILQ_FOREACH_SAFE(rv, queue, partpopq, rvn) {
1238                 pa = VM_PAGE_TO_PHYS(&rv->pages[0]);
1239                 if (pa + VM_LEVEL_0_SIZE - size < low) {
1240                         /* This entire reservation is too low; go to next. */
1241                         continue;
1242                 }
1243                 if (pa + size > high) {
1244                         /* This entire reservation is too high; go to next. */
1245                         continue;
1246                 }
1247                 if (!vm_addr_align_ok(pa, alignment)) {
1248                         /* This entire reservation is unaligned; go to next. */
1249                         continue;
1250                 }
1251
1252                 if (vm_reserv_trylock(rv) == 0) {
1253                         TAILQ_INSERT_AFTER(queue, rv, marker, partpopq);
1254                         vm_reserv_domain_unlock(domain);
1255                         vm_reserv_lock(rv);
1256                         if (TAILQ_PREV(marker, vm_reserv_queue, partpopq) !=
1257                             rv) {
1258                                 vm_reserv_unlock(rv);
1259                                 vm_reserv_domain_lock(domain);
1260                                 rvn = TAILQ_NEXT(marker, partpopq);
1261                                 TAILQ_REMOVE(queue, marker, partpopq);
1262                                 continue;
1263                         }
1264                         vm_reserv_domain_lock(domain);
1265                         TAILQ_REMOVE(queue, marker, partpopq);
1266                 }
1267                 vm_reserv_domain_unlock(domain);
1268                 lo = (pa >= low) ? 0 :
1269                     (int)((low + PAGE_MASK - pa) >> PAGE_SHIFT);
1270                 hi = (pa + VM_LEVEL_0_SIZE <= high) ? VM_LEVEL_0_NPAGES :
1271                     (int)((high - pa) >> PAGE_SHIFT);
1272                 posn = vm_reserv_find_contig(rv, (int)npages, lo, hi,
1273                     ppn_align, ppn_bound);
1274                 if (posn >= 0) {
1275                         vm_reserv_domain_scan_unlock(domain);
1276                         /* Allocate requested space */
1277                         rv->popcnt += npages;
1278                         bit_nset(rv->popmap, posn, posn + npages - 1);
1279                         vm_reserv_reclaim(rv);
1280                         vm_reserv_unlock(rv);
1281                         m_ret = &rv->pages[posn];
1282                         pa = VM_PAGE_TO_PHYS(m_ret);
1283                         KASSERT(vm_addr_ok(pa, size, alignment, boundary),
1284                             ("%s: adjusted address not aligned/bounded to "
1285                              "%lx/%jx",
1286                              __func__, alignment, (uintmax_t)boundary));
1287                         return (m_ret);
1288                 }
1289                 vm_reserv_domain_lock(domain);
1290                 rvn = TAILQ_NEXT(rv, partpopq);
1291                 vm_reserv_unlock(rv);
1292         }
1293         vm_reserv_domain_unlock(domain);
1294         vm_reserv_domain_scan_unlock(domain);
1295         return (NULL);
1296 }
1297
1298 /*
1299  * Transfers the reservation underlying the given page to a new object.
1300  *
1301  * The object must be locked.
1302  */
1303 void
1304 vm_reserv_rename(vm_page_t m, vm_object_t new_object, vm_object_t old_object,
1305     vm_pindex_t old_object_offset)
1306 {
1307         vm_reserv_t rv;
1308
1309         VM_OBJECT_ASSERT_WLOCKED(new_object);
1310         rv = vm_reserv_from_page(m);
1311         if (rv->object == old_object) {
1312                 vm_reserv_lock(rv);
1313                 CTR6(KTR_VM,
1314                     "%s: rv %p object %p new %p popcnt %d inpartpop %d",
1315                     __FUNCTION__, rv, rv->object, new_object, rv->popcnt,
1316                     rv->inpartpopq);
1317                 if (rv->object == old_object) {
1318                         vm_reserv_object_lock(old_object);
1319                         rv->object = NULL;
1320                         LIST_REMOVE(rv, objq);
1321                         vm_reserv_object_unlock(old_object);
1322                         vm_reserv_object_lock(new_object);
1323                         rv->object = new_object;
1324                         rv->pindex -= old_object_offset;
1325                         LIST_INSERT_HEAD(&new_object->rvq, rv, objq);
1326                         vm_reserv_object_unlock(new_object);
1327                 }
1328                 vm_reserv_unlock(rv);
1329         }
1330 }
1331
1332 /*
1333  * Returns the size (in bytes) of a reservation of the specified level.
1334  */
1335 int
1336 vm_reserv_size(int level)
1337 {
1338
1339         switch (level) {
1340         case 0:
1341                 return (VM_LEVEL_0_SIZE);
1342         case -1:
1343                 return (PAGE_SIZE);
1344         default:
1345                 return (0);
1346         }
1347 }
1348
1349 /*
1350  * Allocates the virtual and physical memory required by the reservation
1351  * management system's data structures, in particular, the reservation array.
1352  */
1353 vm_paddr_t
1354 vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end)
1355 {
1356         vm_paddr_t new_end;
1357         vm_pindex_t count;
1358         size_t size;
1359         int i;
1360
1361         count = 0;
1362         for (i = 0; i < vm_phys_nsegs; i++) {
1363 #ifdef VM_PHYSSEG_SPARSE
1364                 count += howmany(vm_phys_segs[i].end, VM_LEVEL_0_SIZE) -
1365                     vm_phys_segs[i].start / VM_LEVEL_0_SIZE;
1366 #else
1367                 count = MAX(count,
1368                     howmany(vm_phys_segs[i].end, VM_LEVEL_0_SIZE));
1369 #endif
1370         }
1371
1372         for (i = 0; phys_avail[i + 1] != 0; i += 2) {
1373 #ifdef VM_PHYSSEG_SPARSE
1374                 count += howmany(phys_avail[i + 1], VM_LEVEL_0_SIZE) -
1375                     phys_avail[i] / VM_LEVEL_0_SIZE;
1376 #else
1377                 count = MAX(count,
1378                     howmany(phys_avail[i + 1], VM_LEVEL_0_SIZE));
1379 #endif
1380         }
1381
1382         /*
1383          * Calculate the size (in bytes) of the reservation array.  Rounding up
1384          * for partial superpages at boundaries, as every small page is mapped
1385          * to an element in the reservation array based on its physical address.
1386          * Thus, the number of elements in the reservation array can be greater
1387          * than the number of superpages.
1388          */
1389         size = count * sizeof(struct vm_reserv);
1390
1391         /*
1392          * Allocate and map the physical memory for the reservation array.  The
1393          * next available virtual address is returned by reference.
1394          */
1395         new_end = end - round_page(size);
1396         vm_reserv_array = (void *)(uintptr_t)pmap_map(vaddr, new_end, end,
1397             VM_PROT_READ | VM_PROT_WRITE);
1398         bzero(vm_reserv_array, size);
1399
1400         /*
1401          * Return the next available physical address.
1402          */
1403         return (new_end);
1404 }
1405
1406 /*
1407  * Returns the superpage containing the given page.
1408  */
1409 vm_page_t
1410 vm_reserv_to_superpage(vm_page_t m)
1411 {
1412         vm_reserv_t rv;
1413
1414         VM_OBJECT_ASSERT_LOCKED(m->object);
1415         rv = vm_reserv_from_page(m);
1416         if (rv->object == m->object && rv->popcnt == VM_LEVEL_0_NPAGES)
1417                 m = rv->pages;
1418         else
1419                 m = NULL;
1420
1421         return (m);
1422 }
1423
1424 #endif  /* VM_NRESERVLEVEL > 0 */