1f8a47341SAlan Cox /*- 2fe267a55SPedro F. Giffuni * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3fe267a55SPedro F. Giffuni * 4f8a47341SAlan Cox * Copyright (c) 2002-2006 Rice University 5ec179322SAlan Cox * Copyright (c) 2007-2011 Alan L. Cox <alc@cs.rice.edu> 6f8a47341SAlan Cox * All rights reserved. 7f8a47341SAlan Cox * 8f8a47341SAlan Cox * This software was developed for the FreeBSD Project by Alan L. Cox, 9f8a47341SAlan Cox * Olivier Crameri, Peter Druschel, Sitaram Iyer, and Juan Navarro. 10f8a47341SAlan Cox * 11f8a47341SAlan Cox * Redistribution and use in source and binary forms, with or without 12f8a47341SAlan Cox * modification, are permitted provided that the following conditions 13f8a47341SAlan Cox * are met: 14f8a47341SAlan Cox * 1. Redistributions of source code must retain the above copyright 15f8a47341SAlan Cox * notice, this list of conditions and the following disclaimer. 16f8a47341SAlan Cox * 2. Redistributions in binary form must reproduce the above copyright 17f8a47341SAlan Cox * notice, this list of conditions and the following disclaimer in the 18f8a47341SAlan Cox * documentation and/or other materials provided with the distribution. 19f8a47341SAlan Cox * 20f8a47341SAlan Cox * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21f8a47341SAlan Cox * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22f8a47341SAlan Cox * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 23f8a47341SAlan Cox * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 24f8a47341SAlan Cox * HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 25f8a47341SAlan Cox * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 26f8a47341SAlan Cox * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 27f8a47341SAlan Cox * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 28f8a47341SAlan Cox * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29f8a47341SAlan Cox * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY 30f8a47341SAlan Cox * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 31f8a47341SAlan Cox * POSSIBILITY OF SUCH DAMAGE. 32f8a47341SAlan Cox */ 33f8a47341SAlan Cox 34f8a47341SAlan Cox /* 35f8a47341SAlan Cox * Superpage reservation management module 36c68c3537SAlan Cox * 37c68c3537SAlan Cox * Any external functions defined by this module are only to be used by the 38c68c3537SAlan Cox * virtual memory system. 39f8a47341SAlan Cox */ 40f8a47341SAlan Cox 41f8a47341SAlan Cox #include <sys/cdefs.h> 42f8a47341SAlan Cox __FBSDID("$FreeBSD$"); 43f8a47341SAlan Cox 44f8a47341SAlan Cox #include "opt_vm.h" 45f8a47341SAlan Cox 46f8a47341SAlan Cox #include <sys/param.h> 47f8a47341SAlan Cox #include <sys/kernel.h> 48f8a47341SAlan Cox #include <sys/lock.h> 49f8a47341SAlan Cox #include <sys/malloc.h> 50f8a47341SAlan Cox #include <sys/mutex.h> 51f8a47341SAlan Cox #include <sys/queue.h> 5289f6b863SAttilio Rao #include <sys/rwlock.h> 53f8a47341SAlan Cox #include <sys/sbuf.h> 54f8a47341SAlan Cox #include <sys/sysctl.h> 55f8a47341SAlan Cox #include <sys/systm.h> 5672346b22SCy Schubert #include <sys/counter.h> 5772346b22SCy Schubert #include <sys/ktr.h> 589ed01c32SGleb Smirnoff #include <sys/vmmeter.h> 595c930c89SJeff Roberson #include <sys/smp.h> 60f8a47341SAlan Cox 61f8a47341SAlan Cox #include <vm/vm.h> 62f8a47341SAlan Cox #include <vm/vm_param.h> 63f8a47341SAlan Cox #include <vm/vm_object.h> 64f8a47341SAlan Cox #include <vm/vm_page.h> 65e2068d0bSJeff Roberson #include <vm/vm_pageout.h> 66f8a47341SAlan Cox #include <vm/vm_phys.h> 67e2068d0bSJeff Roberson #include <vm/vm_pagequeue.h> 68774d251dSAttilio Rao #include <vm/vm_radix.h> 69f8a47341SAlan Cox #include <vm/vm_reserv.h> 70f8a47341SAlan Cox 71f8a47341SAlan Cox /* 72f8a47341SAlan Cox * The reservation system supports the speculative allocation of large physical 733453bca8SAlan Cox * pages ("superpages"). Speculative allocation enables the fully automatic 74f8a47341SAlan Cox * utilization of superpages by the virtual memory system. In other words, no 75f8a47341SAlan Cox * programmatic directives are required to use superpages. 76f8a47341SAlan Cox */ 77f8a47341SAlan Cox 78f8a47341SAlan Cox #if VM_NRESERVLEVEL > 0 79f8a47341SAlan Cox 80f2a496d6SKonstantin Belousov #ifndef VM_LEVEL_0_ORDER_MAX 81f2a496d6SKonstantin Belousov #define VM_LEVEL_0_ORDER_MAX VM_LEVEL_0_ORDER 82f2a496d6SKonstantin Belousov #endif 83f2a496d6SKonstantin Belousov 84f8a47341SAlan Cox /* 85f8a47341SAlan Cox * The number of small pages that are contained in a level 0 reservation 86f8a47341SAlan Cox */ 87f8a47341SAlan Cox #define VM_LEVEL_0_NPAGES (1 << VM_LEVEL_0_ORDER) 88f2a496d6SKonstantin Belousov #define VM_LEVEL_0_NPAGES_MAX (1 << VM_LEVEL_0_ORDER_MAX) 89f8a47341SAlan Cox 90f8a47341SAlan Cox /* 91f8a47341SAlan Cox * The number of bits by which a physical address is shifted to obtain the 92f8a47341SAlan Cox * reservation number 93f8a47341SAlan Cox */ 94f8a47341SAlan Cox #define VM_LEVEL_0_SHIFT (VM_LEVEL_0_ORDER + PAGE_SHIFT) 95f8a47341SAlan Cox 96f8a47341SAlan Cox /* 97f8a47341SAlan Cox * The size of a level 0 reservation in bytes 98f8a47341SAlan Cox */ 99f8a47341SAlan Cox #define VM_LEVEL_0_SIZE (1 << VM_LEVEL_0_SHIFT) 100f8a47341SAlan Cox 101f8a47341SAlan Cox /* 102f8a47341SAlan Cox * Computes the index of the small page underlying the given (object, pindex) 103f8a47341SAlan Cox * within the reservation's array of small pages. 104f8a47341SAlan Cox */ 105f8a47341SAlan Cox #define VM_RESERV_INDEX(object, pindex) \ 106f8a47341SAlan Cox (((object)->pg_color + (pindex)) & (VM_LEVEL_0_NPAGES - 1)) 107f8a47341SAlan Cox 108f8a47341SAlan Cox /* 109ec179322SAlan Cox * The size of a population map entry 110ec179322SAlan Cox */ 111ec179322SAlan Cox typedef u_long popmap_t; 112ec179322SAlan Cox 113ec179322SAlan Cox /* 114ec179322SAlan Cox * The number of bits in a population map entry 115ec179322SAlan Cox */ 116ec179322SAlan Cox #define NBPOPMAP (NBBY * sizeof(popmap_t)) 117ec179322SAlan Cox 118ec179322SAlan Cox /* 119ec179322SAlan Cox * The number of population map entries in a reservation 120ec179322SAlan Cox */ 121ec179322SAlan Cox #define NPOPMAP howmany(VM_LEVEL_0_NPAGES, NBPOPMAP) 122f2a496d6SKonstantin Belousov #define NPOPMAP_MAX howmany(VM_LEVEL_0_NPAGES_MAX, NBPOPMAP) 123ec179322SAlan Cox 124ec179322SAlan Cox /* 1252ef6727eSJeff Roberson * Number of elapsed ticks before we update the LRU queue position. Used 1262ef6727eSJeff Roberson * to reduce contention and churn on the list. 1272ef6727eSJeff Roberson */ 1282ef6727eSJeff Roberson #define PARTPOPSLOP 1 1292ef6727eSJeff Roberson 1302ef6727eSJeff Roberson /* 1313180f757SAlan Cox * Clear a bit in the population map. 1323180f757SAlan Cox */ 1333180f757SAlan Cox static __inline void 1343180f757SAlan Cox popmap_clear(popmap_t popmap[], int i) 1353180f757SAlan Cox { 1363180f757SAlan Cox 1373180f757SAlan Cox popmap[i / NBPOPMAP] &= ~(1UL << (i % NBPOPMAP)); 1383180f757SAlan Cox } 1393180f757SAlan Cox 1403180f757SAlan Cox /* 1413180f757SAlan Cox * Set a bit in the population map. 1423180f757SAlan Cox */ 1433180f757SAlan Cox static __inline void 1443180f757SAlan Cox popmap_set(popmap_t popmap[], int i) 1453180f757SAlan Cox { 1463180f757SAlan Cox 1473180f757SAlan Cox popmap[i / NBPOPMAP] |= 1UL << (i % NBPOPMAP); 1483180f757SAlan Cox } 1493180f757SAlan Cox 1503180f757SAlan Cox /* 1513180f757SAlan Cox * Is a bit in the population map clear? 1523180f757SAlan Cox */ 1533180f757SAlan Cox static __inline boolean_t 1543180f757SAlan Cox popmap_is_clear(popmap_t popmap[], int i) 1553180f757SAlan Cox { 1563180f757SAlan Cox 1573180f757SAlan Cox return ((popmap[i / NBPOPMAP] & (1UL << (i % NBPOPMAP))) == 0); 1583180f757SAlan Cox } 1593180f757SAlan Cox 1603180f757SAlan Cox /* 1613180f757SAlan Cox * Is a bit in the population map set? 1623180f757SAlan Cox */ 1633180f757SAlan Cox static __inline boolean_t 1643180f757SAlan Cox popmap_is_set(popmap_t popmap[], int i) 1653180f757SAlan Cox { 1663180f757SAlan Cox 1673180f757SAlan Cox return ((popmap[i / NBPOPMAP] & (1UL << (i % NBPOPMAP))) != 0); 1683180f757SAlan Cox } 1693180f757SAlan Cox 1703180f757SAlan Cox /* 171f8a47341SAlan Cox * The reservation structure 172f8a47341SAlan Cox * 173f8a47341SAlan Cox * A reservation structure is constructed whenever a large physical page is 174f8a47341SAlan Cox * speculatively allocated to an object. The reservation provides the small 175f8a47341SAlan Cox * physical pages for the range [pindex, pindex + VM_LEVEL_0_NPAGES) of offsets 176f8a47341SAlan Cox * within that object. The reservation's "popcnt" tracks the number of these 177f8a47341SAlan Cox * small physical pages that are in use at any given time. When and if the 1783453bca8SAlan Cox * reservation is not fully utilized, it appears in the queue of partially 179f8a47341SAlan Cox * populated reservations. The reservation always appears on the containing 180f8a47341SAlan Cox * object's list of reservations. 181f8a47341SAlan Cox * 1823453bca8SAlan Cox * A partially populated reservation can be broken and reclaimed at any time. 183e2068d0bSJeff Roberson * 1845c930c89SJeff Roberson * r - vm_reserv_lock 1855c930c89SJeff Roberson * d - vm_reserv_domain_lock 186e2068d0bSJeff Roberson * o - vm_reserv_object_lock 187e2068d0bSJeff Roberson * c - constant after boot 188f8a47341SAlan Cox */ 189f8a47341SAlan Cox struct vm_reserv { 1905c930c89SJeff Roberson struct mtx lock; /* reservation lock. */ 1915c930c89SJeff Roberson TAILQ_ENTRY(vm_reserv) partpopq; /* (d) per-domain queue. */ 1925c930c89SJeff Roberson LIST_ENTRY(vm_reserv) objq; /* (o, r) object queue */ 1935c930c89SJeff Roberson vm_object_t object; /* (o, r) containing object */ 1945c930c89SJeff Roberson vm_pindex_t pindex; /* (o, r) offset in object */ 195e2068d0bSJeff Roberson vm_page_t pages; /* (c) first page */ 1965c930c89SJeff Roberson uint16_t domain; /* (c) NUMA domain. */ 1975c930c89SJeff Roberson uint16_t popcnt; /* (r) # of pages in use */ 1982ef6727eSJeff Roberson int lasttick; /* (r) last pop update tick. */ 1995c930c89SJeff Roberson char inpartpopq; /* (d) */ 200f2a496d6SKonstantin Belousov popmap_t popmap[NPOPMAP_MAX]; /* (r) bit vector, used pages */ 201f8a47341SAlan Cox }; 202f8a47341SAlan Cox 2035c930c89SJeff Roberson #define vm_reserv_lockptr(rv) (&(rv)->lock) 2045c930c89SJeff Roberson #define vm_reserv_assert_locked(rv) \ 2055c930c89SJeff Roberson mtx_assert(vm_reserv_lockptr(rv), MA_OWNED) 2065c930c89SJeff Roberson #define vm_reserv_lock(rv) mtx_lock(vm_reserv_lockptr(rv)) 2075c930c89SJeff Roberson #define vm_reserv_trylock(rv) mtx_trylock(vm_reserv_lockptr(rv)) 2085c930c89SJeff Roberson #define vm_reserv_unlock(rv) mtx_unlock(vm_reserv_lockptr(rv)) 2095c930c89SJeff Roberson 2105c930c89SJeff Roberson static struct mtx_padalign vm_reserv_domain_locks[MAXMEMDOM]; 2115c930c89SJeff Roberson 2125c930c89SJeff Roberson #define vm_reserv_domain_lockptr(d) &vm_reserv_domain_locks[(d)] 2135c930c89SJeff Roberson #define vm_reserv_domain_lock(d) mtx_lock(vm_reserv_domain_lockptr(d)) 2145c930c89SJeff Roberson #define vm_reserv_domain_unlock(d) mtx_unlock(vm_reserv_domain_lockptr(d)) 2155c930c89SJeff Roberson 216f8a47341SAlan Cox /* 217f8a47341SAlan Cox * The reservation array 218f8a47341SAlan Cox * 219f8a47341SAlan Cox * This array is analoguous in function to vm_page_array. It differs in the 220f8a47341SAlan Cox * respect that it may contain a greater number of useful reservation 221f8a47341SAlan Cox * structures than there are (physical) superpages. These "invalid" 222f8a47341SAlan Cox * reservation structures exist to trade-off space for time in the 223f8a47341SAlan Cox * implementation of vm_reserv_from_page(). Invalid reservation structures are 224f8a47341SAlan Cox * distinguishable from "valid" reservation structures by inspecting the 225f8a47341SAlan Cox * reservation's "pages" field. Invalid reservation structures have a NULL 226f8a47341SAlan Cox * "pages" field. 227f8a47341SAlan Cox * 228f8a47341SAlan Cox * vm_reserv_from_page() maps a small (physical) page to an element of this 229f8a47341SAlan Cox * array by computing a physical reservation number from the page's physical 230f8a47341SAlan Cox * address. The physical reservation number is used as the array index. 231f8a47341SAlan Cox * 232f8a47341SAlan Cox * An "active" reservation is a valid reservation structure that has a non-NULL 233f8a47341SAlan Cox * "object" field and a non-zero "popcnt" field. In other words, every active 234f8a47341SAlan Cox * reservation belongs to a particular object. Moreover, every active 235f8a47341SAlan Cox * reservation has an entry in the containing object's list of reservations. 236f8a47341SAlan Cox */ 237f8a47341SAlan Cox static vm_reserv_t vm_reserv_array; 238f8a47341SAlan Cox 239f8a47341SAlan Cox /* 2403453bca8SAlan Cox * The partially populated reservation queue 241f8a47341SAlan Cox * 2423453bca8SAlan Cox * This queue enables the fast recovery of an unused free small page from a 2433453bca8SAlan Cox * partially populated reservation. The reservation at the head of this queue 2443453bca8SAlan Cox * is the least recently changed, partially populated reservation. 245f8a47341SAlan Cox * 246f8a47341SAlan Cox * Access to this queue is synchronized by the free page queue lock. 247f8a47341SAlan Cox */ 248ef435ae7SJeff Roberson static TAILQ_HEAD(, vm_reserv) vm_rvq_partpop[MAXMEMDOM]; 249f8a47341SAlan Cox 250f8a47341SAlan Cox static SYSCTL_NODE(_vm, OID_AUTO, reserv, CTLFLAG_RD, 0, "Reservation Info"); 251f8a47341SAlan Cox 2525c930c89SJeff Roberson static counter_u64_t vm_reserv_broken = EARLY_COUNTER; 2535c930c89SJeff Roberson SYSCTL_COUNTER_U64(_vm_reserv, OID_AUTO, broken, CTLFLAG_RD, 2545c930c89SJeff Roberson &vm_reserv_broken, "Cumulative number of broken reservations"); 255f8a47341SAlan Cox 2565c930c89SJeff Roberson static counter_u64_t vm_reserv_freed = EARLY_COUNTER; 2575c930c89SJeff Roberson SYSCTL_COUNTER_U64(_vm_reserv, OID_AUTO, freed, CTLFLAG_RD, 2585c930c89SJeff Roberson &vm_reserv_freed, "Cumulative number of freed reservations"); 259f8a47341SAlan Cox 260e0a63baaSAlan Cox static int sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS); 261e0a63baaSAlan Cox 262e0a63baaSAlan Cox SYSCTL_PROC(_vm_reserv, OID_AUTO, fullpop, CTLTYPE_INT | CTLFLAG_RD, NULL, 0, 263e0a63baaSAlan Cox sysctl_vm_reserv_fullpop, "I", "Current number of full reservations"); 264e0a63baaSAlan Cox 265f8a47341SAlan Cox static int sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS); 266f8a47341SAlan Cox 267f8a47341SAlan Cox SYSCTL_OID(_vm_reserv, OID_AUTO, partpopq, CTLTYPE_STRING | CTLFLAG_RD, NULL, 0, 2683453bca8SAlan Cox sysctl_vm_reserv_partpopq, "A", "Partially populated reservation queues"); 269f8a47341SAlan Cox 2705c930c89SJeff Roberson static counter_u64_t vm_reserv_reclaimed = EARLY_COUNTER; 2715c930c89SJeff Roberson SYSCTL_COUNTER_U64(_vm_reserv, OID_AUTO, reclaimed, CTLFLAG_RD, 2725c930c89SJeff Roberson &vm_reserv_reclaimed, "Cumulative number of reclaimed reservations"); 273f8a47341SAlan Cox 274e2068d0bSJeff Roberson /* 275e2068d0bSJeff Roberson * The object lock pool is used to synchronize the rvq. We can not use a 276e2068d0bSJeff Roberson * pool mutex because it is required before malloc works. 277e2068d0bSJeff Roberson * 278e2068d0bSJeff Roberson * The "hash" function could be made faster without divide and modulo. 279e2068d0bSJeff Roberson */ 280e2068d0bSJeff Roberson #define VM_RESERV_OBJ_LOCK_COUNT MAXCPU 281e2068d0bSJeff Roberson 282e2068d0bSJeff Roberson struct mtx_padalign vm_reserv_object_mtx[VM_RESERV_OBJ_LOCK_COUNT]; 283e2068d0bSJeff Roberson 284e2068d0bSJeff Roberson #define vm_reserv_object_lock_idx(object) \ 285e2068d0bSJeff Roberson (((uintptr_t)object / sizeof(*object)) % VM_RESERV_OBJ_LOCK_COUNT) 286e2068d0bSJeff Roberson #define vm_reserv_object_lock_ptr(object) \ 287e2068d0bSJeff Roberson &vm_reserv_object_mtx[vm_reserv_object_lock_idx((object))] 288e2068d0bSJeff Roberson #define vm_reserv_object_lock(object) \ 289e2068d0bSJeff Roberson mtx_lock(vm_reserv_object_lock_ptr((object))) 290e2068d0bSJeff Roberson #define vm_reserv_object_unlock(object) \ 291e2068d0bSJeff Roberson mtx_unlock(vm_reserv_object_lock_ptr((object))) 292e2068d0bSJeff Roberson 293ada27a3bSKonstantin Belousov static void vm_reserv_break(vm_reserv_t rv); 294ec179322SAlan Cox static void vm_reserv_depopulate(vm_reserv_t rv, int index); 295f8a47341SAlan Cox static vm_reserv_t vm_reserv_from_page(vm_page_t m); 296f8a47341SAlan Cox static boolean_t vm_reserv_has_pindex(vm_reserv_t rv, 297f8a47341SAlan Cox vm_pindex_t pindex); 298ec179322SAlan Cox static void vm_reserv_populate(vm_reserv_t rv, int index); 29944aab2c3SAlan Cox static void vm_reserv_reclaim(vm_reserv_t rv); 300f8a47341SAlan Cox 301f8a47341SAlan Cox /* 302e0a63baaSAlan Cox * Returns the current number of full reservations. 303e0a63baaSAlan Cox * 304e0a63baaSAlan Cox * Since the number of full reservations is computed without acquiring the 305e0a63baaSAlan Cox * free page queue lock, the returned value may be inexact. 306e0a63baaSAlan Cox */ 307e0a63baaSAlan Cox static int 308e0a63baaSAlan Cox sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS) 309e0a63baaSAlan Cox { 310e0a63baaSAlan Cox vm_paddr_t paddr; 311e0a63baaSAlan Cox struct vm_phys_seg *seg; 312e0a63baaSAlan Cox vm_reserv_t rv; 313e0a63baaSAlan Cox int fullpop, segind; 314e0a63baaSAlan Cox 315e0a63baaSAlan Cox fullpop = 0; 316e0a63baaSAlan Cox for (segind = 0; segind < vm_phys_nsegs; segind++) { 317e0a63baaSAlan Cox seg = &vm_phys_segs[segind]; 318e0a63baaSAlan Cox paddr = roundup2(seg->start, VM_LEVEL_0_SIZE); 3196b821a74SAleksandr Rybalko while (paddr + VM_LEVEL_0_SIZE > paddr && paddr + 3206b821a74SAleksandr Rybalko VM_LEVEL_0_SIZE <= seg->end) { 321e0a63baaSAlan Cox rv = &vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT]; 322e0a63baaSAlan Cox fullpop += rv->popcnt == VM_LEVEL_0_NPAGES; 323e0a63baaSAlan Cox paddr += VM_LEVEL_0_SIZE; 324e0a63baaSAlan Cox } 325e0a63baaSAlan Cox } 326e0a63baaSAlan Cox return (sysctl_handle_int(oidp, &fullpop, 0, req)); 327e0a63baaSAlan Cox } 328e0a63baaSAlan Cox 329e0a63baaSAlan Cox /* 3303453bca8SAlan Cox * Describes the current state of the partially populated reservation queue. 331f8a47341SAlan Cox */ 332f8a47341SAlan Cox static int 333f8a47341SAlan Cox sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS) 334f8a47341SAlan Cox { 335f8a47341SAlan Cox struct sbuf sbuf; 336f8a47341SAlan Cox vm_reserv_t rv; 337ef435ae7SJeff Roberson int counter, error, domain, level, unused_pages; 338f8a47341SAlan Cox 33900f0e671SMatthew D Fleming error = sysctl_wire_old_buffer(req, 0); 34000f0e671SMatthew D Fleming if (error != 0) 34100f0e671SMatthew D Fleming return (error); 3424e657159SMatthew D Fleming sbuf_new_for_sysctl(&sbuf, NULL, 128, req); 343ef435ae7SJeff Roberson sbuf_printf(&sbuf, "\nDOMAIN LEVEL SIZE NUMBER\n\n"); 344ef435ae7SJeff Roberson for (domain = 0; domain < vm_ndomains; domain++) { 345f8a47341SAlan Cox for (level = -1; level <= VM_NRESERVLEVEL - 2; level++) { 346f8a47341SAlan Cox counter = 0; 347f8a47341SAlan Cox unused_pages = 0; 3485c930c89SJeff Roberson vm_reserv_domain_lock(domain); 349ef435ae7SJeff Roberson TAILQ_FOREACH(rv, &vm_rvq_partpop[domain], partpopq) { 350f8a47341SAlan Cox counter++; 351f8a47341SAlan Cox unused_pages += VM_LEVEL_0_NPAGES - rv->popcnt; 352f8a47341SAlan Cox } 3535c930c89SJeff Roberson vm_reserv_domain_unlock(domain); 354ef435ae7SJeff Roberson sbuf_printf(&sbuf, "%6d, %7d, %6dK, %6d\n", 355ef435ae7SJeff Roberson domain, level, 3562cf36c8fSAlan Cox unused_pages * ((int)PAGE_SIZE / 1024), counter); 357f8a47341SAlan Cox } 358ef435ae7SJeff Roberson } 3594e657159SMatthew D Fleming error = sbuf_finish(&sbuf); 360f8a47341SAlan Cox sbuf_delete(&sbuf); 361f8a47341SAlan Cox return (error); 362f8a47341SAlan Cox } 363f8a47341SAlan Cox 364f8a47341SAlan Cox /* 365e2068d0bSJeff Roberson * Remove a reservation from the object's objq. 366e2068d0bSJeff Roberson */ 367e2068d0bSJeff Roberson static void 368e2068d0bSJeff Roberson vm_reserv_remove(vm_reserv_t rv) 369e2068d0bSJeff Roberson { 370e2068d0bSJeff Roberson vm_object_t object; 371e2068d0bSJeff Roberson 3725c930c89SJeff Roberson vm_reserv_assert_locked(rv); 3735c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 3745c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 375e2068d0bSJeff Roberson KASSERT(rv->object != NULL, 376e2068d0bSJeff Roberson ("vm_reserv_remove: reserv %p is free", rv)); 377e2068d0bSJeff Roberson KASSERT(!rv->inpartpopq, 378e2068d0bSJeff Roberson ("vm_reserv_remove: reserv %p's inpartpopq is TRUE", rv)); 379e2068d0bSJeff Roberson object = rv->object; 380e2068d0bSJeff Roberson vm_reserv_object_lock(object); 381e2068d0bSJeff Roberson LIST_REMOVE(rv, objq); 382e2068d0bSJeff Roberson rv->object = NULL; 383e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 384e2068d0bSJeff Roberson } 385e2068d0bSJeff Roberson 386e2068d0bSJeff Roberson /* 387e2068d0bSJeff Roberson * Insert a new reservation into the object's objq. 388e2068d0bSJeff Roberson */ 389e2068d0bSJeff Roberson static void 390e2068d0bSJeff Roberson vm_reserv_insert(vm_reserv_t rv, vm_object_t object, vm_pindex_t pindex) 391e2068d0bSJeff Roberson { 392e2068d0bSJeff Roberson int i; 393e2068d0bSJeff Roberson 3945c930c89SJeff Roberson vm_reserv_assert_locked(rv); 3955c930c89SJeff Roberson CTR6(KTR_VM, 3965c930c89SJeff Roberson "%s: rv %p(%p) object %p new %p popcnt %d", 3975c930c89SJeff Roberson __FUNCTION__, rv, rv->pages, rv->object, object, 3985c930c89SJeff Roberson rv->popcnt); 399e2068d0bSJeff Roberson KASSERT(rv->object == NULL, 400e2068d0bSJeff Roberson ("vm_reserv_insert: reserv %p isn't free", rv)); 401e2068d0bSJeff Roberson KASSERT(rv->popcnt == 0, 402e2068d0bSJeff Roberson ("vm_reserv_insert: reserv %p's popcnt is corrupted", rv)); 403e2068d0bSJeff Roberson KASSERT(!rv->inpartpopq, 404e2068d0bSJeff Roberson ("vm_reserv_insert: reserv %p's inpartpopq is TRUE", rv)); 405e2068d0bSJeff Roberson for (i = 0; i < NPOPMAP; i++) 406e2068d0bSJeff Roberson KASSERT(rv->popmap[i] == 0, 407e2068d0bSJeff Roberson ("vm_reserv_insert: reserv %p's popmap is corrupted", rv)); 408e2068d0bSJeff Roberson vm_reserv_object_lock(object); 409e2068d0bSJeff Roberson rv->pindex = pindex; 410e2068d0bSJeff Roberson rv->object = object; 4112ef6727eSJeff Roberson rv->lasttick = ticks; 412e2068d0bSJeff Roberson LIST_INSERT_HEAD(&object->rvq, rv, objq); 413e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 414e2068d0bSJeff Roberson } 415e2068d0bSJeff Roberson 416e2068d0bSJeff Roberson /* 417f8a47341SAlan Cox * Reduces the given reservation's population count. If the population count 418f8a47341SAlan Cox * becomes zero, the reservation is destroyed. Additionally, moves the 4193453bca8SAlan Cox * reservation to the tail of the partially populated reservation queue if the 420f8a47341SAlan Cox * population count is non-zero. 421f8a47341SAlan Cox */ 422f8a47341SAlan Cox static void 423ec179322SAlan Cox vm_reserv_depopulate(vm_reserv_t rv, int index) 424f8a47341SAlan Cox { 4255c930c89SJeff Roberson struct vm_domain *vmd; 426f8a47341SAlan Cox 4275c930c89SJeff Roberson vm_reserv_assert_locked(rv); 4285c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 4295c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 430f8a47341SAlan Cox KASSERT(rv->object != NULL, 431f8a47341SAlan Cox ("vm_reserv_depopulate: reserv %p is free", rv)); 4323180f757SAlan Cox KASSERT(popmap_is_set(rv->popmap, index), 433a08c1515SAlan Cox ("vm_reserv_depopulate: reserv %p's popmap[%d] is clear", rv, 434a08c1515SAlan Cox index)); 435f8a47341SAlan Cox KASSERT(rv->popcnt > 0, 436f8a47341SAlan Cox ("vm_reserv_depopulate: reserv %p's popcnt is corrupted", rv)); 4372d3f4181SJeff Roberson KASSERT(rv->domain < vm_ndomains, 438ef435ae7SJeff Roberson ("vm_reserv_depopulate: reserv %p's domain is corrupted %d", 439ef435ae7SJeff Roberson rv, rv->domain)); 4405c930c89SJeff Roberson if (rv->popcnt == VM_LEVEL_0_NPAGES) { 441dd05fa19SAlan Cox KASSERT(rv->pages->psind == 1, 442dd05fa19SAlan Cox ("vm_reserv_depopulate: reserv %p is already demoted", 443dd05fa19SAlan Cox rv)); 444dd05fa19SAlan Cox rv->pages->psind = 0; 445f8a47341SAlan Cox } 4463180f757SAlan Cox popmap_clear(rv->popmap, index); 447f8a47341SAlan Cox rv->popcnt--; 4482ef6727eSJeff Roberson if ((unsigned)(ticks - rv->lasttick) >= PARTPOPSLOP || 4492ef6727eSJeff Roberson rv->popcnt == 0) { 4505c930c89SJeff Roberson vm_reserv_domain_lock(rv->domain); 4515c930c89SJeff Roberson if (rv->inpartpopq) { 4525c930c89SJeff Roberson TAILQ_REMOVE(&vm_rvq_partpop[rv->domain], rv, partpopq); 4535c930c89SJeff Roberson rv->inpartpopq = FALSE; 4545c930c89SJeff Roberson } 4555c930c89SJeff Roberson if (rv->popcnt != 0) { 456f8a47341SAlan Cox rv->inpartpopq = TRUE; 457ef435ae7SJeff Roberson TAILQ_INSERT_TAIL(&vm_rvq_partpop[rv->domain], rv, partpopq); 458f8a47341SAlan Cox } 4595c930c89SJeff Roberson vm_reserv_domain_unlock(rv->domain); 4602ef6727eSJeff Roberson rv->lasttick = ticks; 4612ef6727eSJeff Roberson } 4625c930c89SJeff Roberson vmd = VM_DOMAIN(rv->domain); 4635c930c89SJeff Roberson if (rv->popcnt == 0) { 4645c930c89SJeff Roberson vm_reserv_remove(rv); 4655c930c89SJeff Roberson vm_domain_free_lock(vmd); 4665c930c89SJeff Roberson vm_phys_free_pages(rv->pages, VM_LEVEL_0_ORDER); 4675c930c89SJeff Roberson vm_domain_free_unlock(vmd); 4685c930c89SJeff Roberson counter_u64_add(vm_reserv_freed, 1); 4695c930c89SJeff Roberson } 4705c930c89SJeff Roberson vm_domain_freecnt_inc(vmd, 1); 471f8a47341SAlan Cox } 472f8a47341SAlan Cox 473f8a47341SAlan Cox /* 474f8a47341SAlan Cox * Returns the reservation to which the given page might belong. 475f8a47341SAlan Cox */ 476f8a47341SAlan Cox static __inline vm_reserv_t 477f8a47341SAlan Cox vm_reserv_from_page(vm_page_t m) 478f8a47341SAlan Cox { 479f8a47341SAlan Cox 480f8a47341SAlan Cox return (&vm_reserv_array[VM_PAGE_TO_PHYS(m) >> VM_LEVEL_0_SHIFT]); 481f8a47341SAlan Cox } 482f8a47341SAlan Cox 483f8a47341SAlan Cox /* 484e2068d0bSJeff Roberson * Returns an existing reservation or NULL and initialized successor pointer. 485e2068d0bSJeff Roberson */ 486e2068d0bSJeff Roberson static vm_reserv_t 487e2068d0bSJeff Roberson vm_reserv_from_object(vm_object_t object, vm_pindex_t pindex, 488e2068d0bSJeff Roberson vm_page_t mpred, vm_page_t *msuccp) 489e2068d0bSJeff Roberson { 490e2068d0bSJeff Roberson vm_reserv_t rv; 491e2068d0bSJeff Roberson vm_page_t msucc; 492e2068d0bSJeff Roberson 493e2068d0bSJeff Roberson msucc = NULL; 494e2068d0bSJeff Roberson if (mpred != NULL) { 495e2068d0bSJeff Roberson KASSERT(mpred->object == object, 496e2068d0bSJeff Roberson ("vm_reserv_from_object: object doesn't contain mpred")); 497e2068d0bSJeff Roberson KASSERT(mpred->pindex < pindex, 498e2068d0bSJeff Roberson ("vm_reserv_from_object: mpred doesn't precede pindex")); 499e2068d0bSJeff Roberson rv = vm_reserv_from_page(mpred); 500e2068d0bSJeff Roberson if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) 501e2068d0bSJeff Roberson goto found; 502e2068d0bSJeff Roberson msucc = TAILQ_NEXT(mpred, listq); 503e2068d0bSJeff Roberson } else 504e2068d0bSJeff Roberson msucc = TAILQ_FIRST(&object->memq); 505e2068d0bSJeff Roberson if (msucc != NULL) { 506e2068d0bSJeff Roberson KASSERT(msucc->pindex > pindex, 507e2068d0bSJeff Roberson ("vm_reserv_from_object: msucc doesn't succeed pindex")); 508e2068d0bSJeff Roberson rv = vm_reserv_from_page(msucc); 509e2068d0bSJeff Roberson if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) 510e2068d0bSJeff Roberson goto found; 511e2068d0bSJeff Roberson } 512e2068d0bSJeff Roberson rv = NULL; 513e2068d0bSJeff Roberson 514e2068d0bSJeff Roberson found: 515e2068d0bSJeff Roberson *msuccp = msucc; 516e2068d0bSJeff Roberson 517e2068d0bSJeff Roberson return (rv); 518e2068d0bSJeff Roberson } 519e2068d0bSJeff Roberson 520e2068d0bSJeff Roberson /* 521f8a47341SAlan Cox * Returns TRUE if the given reservation contains the given page index and 522f8a47341SAlan Cox * FALSE otherwise. 523f8a47341SAlan Cox */ 524f8a47341SAlan Cox static __inline boolean_t 525f8a47341SAlan Cox vm_reserv_has_pindex(vm_reserv_t rv, vm_pindex_t pindex) 526f8a47341SAlan Cox { 527f8a47341SAlan Cox 528f8a47341SAlan Cox return (((pindex - rv->pindex) & ~(VM_LEVEL_0_NPAGES - 1)) == 0); 529f8a47341SAlan Cox } 530f8a47341SAlan Cox 531f8a47341SAlan Cox /* 532f8a47341SAlan Cox * Increases the given reservation's population count. Moves the reservation 5333453bca8SAlan Cox * to the tail of the partially populated reservation queue. 534f8a47341SAlan Cox * 535f8a47341SAlan Cox * The free page queue must be locked. 536f8a47341SAlan Cox */ 537f8a47341SAlan Cox static void 538ec179322SAlan Cox vm_reserv_populate(vm_reserv_t rv, int index) 539f8a47341SAlan Cox { 540f8a47341SAlan Cox 5415c930c89SJeff Roberson vm_reserv_assert_locked(rv); 5425c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 5435c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 544f8a47341SAlan Cox KASSERT(rv->object != NULL, 545f8a47341SAlan Cox ("vm_reserv_populate: reserv %p is free", rv)); 5463180f757SAlan Cox KASSERT(popmap_is_clear(rv->popmap, index), 547a08c1515SAlan Cox ("vm_reserv_populate: reserv %p's popmap[%d] is set", rv, 548a08c1515SAlan Cox index)); 549f8a47341SAlan Cox KASSERT(rv->popcnt < VM_LEVEL_0_NPAGES, 550f8a47341SAlan Cox ("vm_reserv_populate: reserv %p is already full", rv)); 551dd05fa19SAlan Cox KASSERT(rv->pages->psind == 0, 552dd05fa19SAlan Cox ("vm_reserv_populate: reserv %p is already promoted", rv)); 5532d3f4181SJeff Roberson KASSERT(rv->domain < vm_ndomains, 554ef435ae7SJeff Roberson ("vm_reserv_populate: reserv %p's domain is corrupted %d", 555ef435ae7SJeff Roberson rv, rv->domain)); 5565c930c89SJeff Roberson popmap_set(rv->popmap, index); 5575c930c89SJeff Roberson rv->popcnt++; 5582ef6727eSJeff Roberson if ((unsigned)(ticks - rv->lasttick) < PARTPOPSLOP && 5592ef6727eSJeff Roberson rv->inpartpopq && rv->popcnt != VM_LEVEL_0_NPAGES) 5602ef6727eSJeff Roberson return; 5612ef6727eSJeff Roberson rv->lasttick = ticks; 5625c930c89SJeff Roberson vm_reserv_domain_lock(rv->domain); 563f8a47341SAlan Cox if (rv->inpartpopq) { 564ef435ae7SJeff Roberson TAILQ_REMOVE(&vm_rvq_partpop[rv->domain], rv, partpopq); 565f8a47341SAlan Cox rv->inpartpopq = FALSE; 566f8a47341SAlan Cox } 567f8a47341SAlan Cox if (rv->popcnt < VM_LEVEL_0_NPAGES) { 568f8a47341SAlan Cox rv->inpartpopq = TRUE; 569ef435ae7SJeff Roberson TAILQ_INSERT_TAIL(&vm_rvq_partpop[rv->domain], rv, partpopq); 5705c930c89SJeff Roberson } else { 5715c930c89SJeff Roberson KASSERT(rv->pages->psind == 0, 5725c930c89SJeff Roberson ("vm_reserv_populate: reserv %p is already promoted", 5735c930c89SJeff Roberson rv)); 574dd05fa19SAlan Cox rv->pages->psind = 1; 575f8a47341SAlan Cox } 5765c930c89SJeff Roberson vm_reserv_domain_unlock(rv->domain); 5775c930c89SJeff Roberson } 578f8a47341SAlan Cox 579f8a47341SAlan Cox /* 580e2068d0bSJeff Roberson * Allocates a contiguous set of physical pages of the given size "npages" 5812d5039dbSAlan Cox * from existing or newly created reservations. All of the physical pages 582e2068d0bSJeff Roberson * must be at or above the given physical address "low" and below the given 583e2068d0bSJeff Roberson * physical address "high". The given value "alignment" determines the 584e2068d0bSJeff Roberson * alignment of the first physical page in the set. If the given value 585e2068d0bSJeff Roberson * "boundary" is non-zero, then the set of physical pages cannot cross any 586e2068d0bSJeff Roberson * physical address boundary that is a multiple of that value. Both 587e2068d0bSJeff Roberson * "alignment" and "boundary" must be a power of two. 588e2068d0bSJeff Roberson * 589e2068d0bSJeff Roberson * The page "mpred" must immediately precede the offset "pindex" within the 590e2068d0bSJeff Roberson * specified object. 591e2068d0bSJeff Roberson * 5922d5039dbSAlan Cox * The object must be locked. 593e2068d0bSJeff Roberson */ 594e2068d0bSJeff Roberson vm_page_t 5952d5039dbSAlan Cox vm_reserv_alloc_contig(vm_object_t object, vm_pindex_t pindex, int domain, 5962d5039dbSAlan Cox int req, vm_page_t mpred, u_long npages, vm_paddr_t low, vm_paddr_t high, 5972d5039dbSAlan Cox u_long alignment, vm_paddr_t boundary) 598c68c3537SAlan Cox { 5995c930c89SJeff Roberson struct vm_domain *vmd; 600c68c3537SAlan Cox vm_paddr_t pa, size; 601920da7e4SAlan Cox vm_page_t m, m_ret, msucc; 602c68c3537SAlan Cox vm_pindex_t first, leftcap, rightcap; 603c68c3537SAlan Cox vm_reserv_t rv; 604c68c3537SAlan Cox u_long allocpages, maxpages, minpages; 605c68c3537SAlan Cox int i, index, n; 606c68c3537SAlan Cox 60789f6b863SAttilio Rao VM_OBJECT_ASSERT_WLOCKED(object); 608c68c3537SAlan Cox KASSERT(npages != 0, ("vm_reserv_alloc_contig: npages is 0")); 609c68c3537SAlan Cox 610c68c3537SAlan Cox /* 611c68c3537SAlan Cox * Is a reservation fundamentally impossible? 612c68c3537SAlan Cox */ 613c68c3537SAlan Cox if (pindex < VM_RESERV_INDEX(object, pindex) || 614c68c3537SAlan Cox pindex + npages > object->size) 615c68c3537SAlan Cox return (NULL); 616c68c3537SAlan Cox 617c68c3537SAlan Cox /* 618c68c3537SAlan Cox * All reservations of a particular size have the same alignment. 619c68c3537SAlan Cox * Assuming that the first page is allocated from a reservation, the 620c68c3537SAlan Cox * least significant bits of its physical address can be determined 621c68c3537SAlan Cox * from its offset from the beginning of the reservation and the size 622c68c3537SAlan Cox * of the reservation. 623c68c3537SAlan Cox * 624c68c3537SAlan Cox * Could the specified index within a reservation of the smallest 625c68c3537SAlan Cox * possible size satisfy the alignment and boundary requirements? 626c68c3537SAlan Cox */ 627c68c3537SAlan Cox pa = VM_RESERV_INDEX(object, pindex) << PAGE_SHIFT; 628c68c3537SAlan Cox if ((pa & (alignment - 1)) != 0) 629c68c3537SAlan Cox return (NULL); 630c68c3537SAlan Cox size = npages << PAGE_SHIFT; 631c68c3537SAlan Cox if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) 632c68c3537SAlan Cox return (NULL); 633c68c3537SAlan Cox 634c68c3537SAlan Cox /* 6352d5039dbSAlan Cox * Look for an existing reservation. 636c68c3537SAlan Cox */ 637e2068d0bSJeff Roberson rv = vm_reserv_from_object(object, pindex, mpred, &msucc); 6382d5039dbSAlan Cox if (rv != NULL) { 6392d5039dbSAlan Cox KASSERT(object != kernel_object || rv->domain == domain, 6402d5039dbSAlan Cox ("vm_reserv_alloc_contig: domain mismatch")); 6412d5039dbSAlan Cox index = VM_RESERV_INDEX(object, pindex); 6422d5039dbSAlan Cox /* Does the allocation fit within the reservation? */ 6432d5039dbSAlan Cox if (index + npages > VM_LEVEL_0_NPAGES) 644e2068d0bSJeff Roberson return (NULL); 6452d5039dbSAlan Cox domain = rv->domain; 6462d5039dbSAlan Cox vmd = VM_DOMAIN(domain); 6472d5039dbSAlan Cox vm_reserv_lock(rv); 6482d5039dbSAlan Cox /* Handle reclaim race. */ 6492d5039dbSAlan Cox if (rv->object != object) 6502d5039dbSAlan Cox goto out; 6512d5039dbSAlan Cox m = &rv->pages[index]; 6522d5039dbSAlan Cox pa = VM_PAGE_TO_PHYS(m); 6532d5039dbSAlan Cox if (pa < low || pa + size > high || 6542d5039dbSAlan Cox (pa & (alignment - 1)) != 0 || 6552d5039dbSAlan Cox ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) 6562d5039dbSAlan Cox goto out; 6572d5039dbSAlan Cox /* Handle vm_page_rename(m, new_object, ...). */ 6582d5039dbSAlan Cox for (i = 0; i < npages; i++) 6592d5039dbSAlan Cox if (popmap_is_set(rv->popmap, index + i)) 6602d5039dbSAlan Cox goto out; 6612d5039dbSAlan Cox if (!vm_domain_allocate(vmd, req, npages)) 6622d5039dbSAlan Cox goto out; 6632d5039dbSAlan Cox for (i = 0; i < npages; i++) 6642d5039dbSAlan Cox vm_reserv_populate(rv, index + i); 6652d5039dbSAlan Cox vm_reserv_unlock(rv); 6662d5039dbSAlan Cox return (m); 6672d5039dbSAlan Cox out: 6682d5039dbSAlan Cox vm_reserv_unlock(rv); 6692d5039dbSAlan Cox return (NULL); 6702d5039dbSAlan Cox } 671c68c3537SAlan Cox 672c68c3537SAlan Cox /* 673c68c3537SAlan Cox * Could at least one reservation fit between the first index to the 67464f096eeSAlan Cox * left that can be used ("leftcap") and the first index to the right 67564f096eeSAlan Cox * that cannot be used ("rightcap")? 676e2068d0bSJeff Roberson * 677e2068d0bSJeff Roberson * We must synchronize with the reserv object lock to protect the 678e2068d0bSJeff Roberson * pindex/object of the resulting reservations against rename while 679e2068d0bSJeff Roberson * we are inspecting. 680c68c3537SAlan Cox */ 681c68c3537SAlan Cox first = pindex - VM_RESERV_INDEX(object, pindex); 682e2068d0bSJeff Roberson minpages = VM_RESERV_INDEX(object, pindex) + npages; 683e2068d0bSJeff Roberson maxpages = roundup2(minpages, VM_LEVEL_0_NPAGES); 684e2068d0bSJeff Roberson allocpages = maxpages; 685e2068d0bSJeff Roberson vm_reserv_object_lock(object); 686c68c3537SAlan Cox if (mpred != NULL) { 687c68c3537SAlan Cox if ((rv = vm_reserv_from_page(mpred))->object != object) 688c68c3537SAlan Cox leftcap = mpred->pindex + 1; 689c68c3537SAlan Cox else 690c68c3537SAlan Cox leftcap = rv->pindex + VM_LEVEL_0_NPAGES; 691e2068d0bSJeff Roberson if (leftcap > first) { 692e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 693c68c3537SAlan Cox return (NULL); 694c68c3537SAlan Cox } 695e2068d0bSJeff Roberson } 696c68c3537SAlan Cox if (msucc != NULL) { 697c68c3537SAlan Cox if ((rv = vm_reserv_from_page(msucc))->object != object) 698c68c3537SAlan Cox rightcap = msucc->pindex; 699c68c3537SAlan Cox else 700c68c3537SAlan Cox rightcap = rv->pindex; 701c68c3537SAlan Cox if (first + maxpages > rightcap) { 702e2068d0bSJeff Roberson if (maxpages == VM_LEVEL_0_NPAGES) { 703e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 704c68c3537SAlan Cox return (NULL); 705e2068d0bSJeff Roberson } 70664f096eeSAlan Cox 70764f096eeSAlan Cox /* 70864f096eeSAlan Cox * At least one reservation will fit between "leftcap" 70964f096eeSAlan Cox * and "rightcap". However, a reservation for the 71064f096eeSAlan Cox * last of the requested pages will not fit. Reduce 71164f096eeSAlan Cox * the size of the upcoming allocation accordingly. 71264f096eeSAlan Cox */ 713c68c3537SAlan Cox allocpages = minpages; 714c68c3537SAlan Cox } 715c68c3537SAlan Cox } 716e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 717c68c3537SAlan Cox 718c68c3537SAlan Cox /* 719c68c3537SAlan Cox * Would the last new reservation extend past the end of the object? 720c68c3537SAlan Cox */ 721c68c3537SAlan Cox if (first + maxpages > object->size) { 722c68c3537SAlan Cox /* 723c68c3537SAlan Cox * Don't allocate the last new reservation if the object is a 724c68c3537SAlan Cox * vnode or backed by another object that is a vnode. 725c68c3537SAlan Cox */ 726c68c3537SAlan Cox if (object->type == OBJT_VNODE || 727c68c3537SAlan Cox (object->backing_object != NULL && 728c68c3537SAlan Cox object->backing_object->type == OBJT_VNODE)) { 729c68c3537SAlan Cox if (maxpages == VM_LEVEL_0_NPAGES) 730c68c3537SAlan Cox return (NULL); 731c68c3537SAlan Cox allocpages = minpages; 732c68c3537SAlan Cox } 733c68c3537SAlan Cox /* Speculate that the object may grow. */ 734c68c3537SAlan Cox } 735c68c3537SAlan Cox 736c68c3537SAlan Cox /* 73764f096eeSAlan Cox * Allocate the physical pages. The alignment and boundary specified 73864f096eeSAlan Cox * for this allocation may be different from the alignment and 73964f096eeSAlan Cox * boundary specified for the requested pages. For instance, the 74064f096eeSAlan Cox * specified index may not be the first page within the first new 74164f096eeSAlan Cox * reservation. 742c68c3537SAlan Cox */ 7435c930c89SJeff Roberson m = NULL; 7445c930c89SJeff Roberson vmd = VM_DOMAIN(domain); 7455c930c89SJeff Roberson if (vm_domain_allocate(vmd, req, npages)) { 7465c930c89SJeff Roberson vm_domain_free_lock(vmd); 7475c930c89SJeff Roberson m = vm_phys_alloc_contig(domain, allocpages, low, high, 7485c930c89SJeff Roberson ulmax(alignment, VM_LEVEL_0_SIZE), 7495c930c89SJeff Roberson boundary > VM_LEVEL_0_SIZE ? boundary : 0); 7505c930c89SJeff Roberson vm_domain_free_unlock(vmd); 7515c930c89SJeff Roberson if (m == NULL) { 7525c930c89SJeff Roberson vm_domain_freecnt_inc(vmd, npages); 7535c930c89SJeff Roberson return (NULL); 7545c930c89SJeff Roberson } 7555c930c89SJeff Roberson } else 756c68c3537SAlan Cox return (NULL); 757e2068d0bSJeff Roberson KASSERT(vm_phys_domain(m) == domain, 7587a469c8eSJeff Roberson ("vm_reserv_alloc_contig: Page domain does not match requested.")); 75964f096eeSAlan Cox 76064f096eeSAlan Cox /* 76164f096eeSAlan Cox * The allocated physical pages always begin at a reservation 76264f096eeSAlan Cox * boundary, but they do not always end at a reservation boundary. 76364f096eeSAlan Cox * Initialize every reservation that is completely covered by the 76464f096eeSAlan Cox * allocated physical pages. 76564f096eeSAlan Cox */ 766c68c3537SAlan Cox m_ret = NULL; 767c68c3537SAlan Cox index = VM_RESERV_INDEX(object, pindex); 768c68c3537SAlan Cox do { 769c68c3537SAlan Cox rv = vm_reserv_from_page(m); 770c68c3537SAlan Cox KASSERT(rv->pages == m, 771c68c3537SAlan Cox ("vm_reserv_alloc_contig: reserv %p's pages is corrupted", 772c68c3537SAlan Cox rv)); 7735c930c89SJeff Roberson vm_reserv_lock(rv); 774e2068d0bSJeff Roberson vm_reserv_insert(rv, object, first); 775c68c3537SAlan Cox n = ulmin(VM_LEVEL_0_NPAGES - index, npages); 776c68c3537SAlan Cox for (i = 0; i < n; i++) 777ec179322SAlan Cox vm_reserv_populate(rv, index + i); 778c68c3537SAlan Cox npages -= n; 779c68c3537SAlan Cox if (m_ret == NULL) { 780c68c3537SAlan Cox m_ret = &rv->pages[index]; 781c68c3537SAlan Cox index = 0; 782c68c3537SAlan Cox } 7835c930c89SJeff Roberson vm_reserv_unlock(rv); 784c68c3537SAlan Cox m += VM_LEVEL_0_NPAGES; 785c68c3537SAlan Cox first += VM_LEVEL_0_NPAGES; 786c68c3537SAlan Cox allocpages -= VM_LEVEL_0_NPAGES; 78764f096eeSAlan Cox } while (allocpages >= VM_LEVEL_0_NPAGES); 788c68c3537SAlan Cox return (m_ret); 789e2068d0bSJeff Roberson } 790c68c3537SAlan Cox 791c68c3537SAlan Cox /* 7922d5039dbSAlan Cox * Allocate a physical page from an existing or newly created reservation. 793e2068d0bSJeff Roberson * 794e2068d0bSJeff Roberson * The page "mpred" must immediately precede the offset "pindex" within the 795e2068d0bSJeff Roberson * specified object. 796e2068d0bSJeff Roberson * 797e2068d0bSJeff Roberson * The object must be locked. 798c68c3537SAlan Cox */ 799e2068d0bSJeff Roberson vm_page_t 8002d5039dbSAlan Cox vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex, int domain, 8012d5039dbSAlan Cox int req, vm_page_t mpred) 802e2068d0bSJeff Roberson { 803e2068d0bSJeff Roberson struct vm_domain *vmd; 804e2068d0bSJeff Roberson vm_page_t m, msucc; 8052d5039dbSAlan Cox vm_pindex_t first, leftcap, rightcap; 806e2068d0bSJeff Roberson vm_reserv_t rv; 80730fbfddaSJeff Roberson int index; 808e2068d0bSJeff Roberson 809e2068d0bSJeff Roberson VM_OBJECT_ASSERT_WLOCKED(object); 810e2068d0bSJeff Roberson 811e2068d0bSJeff Roberson /* 8122d5039dbSAlan Cox * Is a reservation fundamentally impossible? 813e2068d0bSJeff Roberson */ 814e2068d0bSJeff Roberson if (pindex < VM_RESERV_INDEX(object, pindex) || 8152d5039dbSAlan Cox pindex >= object->size) 816e2068d0bSJeff Roberson return (NULL); 817e2068d0bSJeff Roberson 818e2068d0bSJeff Roberson /* 819e2068d0bSJeff Roberson * Look for an existing reservation. 820e2068d0bSJeff Roberson */ 821e2068d0bSJeff Roberson rv = vm_reserv_from_object(object, pindex, mpred, &msucc); 8222d5039dbSAlan Cox if (rv != NULL) { 823e2068d0bSJeff Roberson KASSERT(object != kernel_object || rv->domain == domain, 8242d5039dbSAlan Cox ("vm_reserv_alloc_page: domain mismatch")); 825e2068d0bSJeff Roberson domain = rv->domain; 826e2068d0bSJeff Roberson vmd = VM_DOMAIN(domain); 827c68c3537SAlan Cox index = VM_RESERV_INDEX(object, pindex); 828c68c3537SAlan Cox m = &rv->pages[index]; 8295c930c89SJeff Roberson vm_reserv_lock(rv); 830e2068d0bSJeff Roberson /* Handle reclaim race. */ 8315c930c89SJeff Roberson if (rv->object != object || 832c68c3537SAlan Cox /* Handle vm_page_rename(m, new_object, ...). */ 8335c930c89SJeff Roberson popmap_is_set(rv->popmap, index)) { 834e2068d0bSJeff Roberson m = NULL; 8355c930c89SJeff Roberson goto out; 83630fbfddaSJeff Roberson } 8375c930c89SJeff Roberson if (vm_domain_allocate(vmd, req, 1) == 0) 8385c930c89SJeff Roberson m = NULL; 8395c930c89SJeff Roberson else 8405c930c89SJeff Roberson vm_reserv_populate(rv, index); 8415c930c89SJeff Roberson out: 8425c930c89SJeff Roberson vm_reserv_unlock(rv); 843c68c3537SAlan Cox return (m); 844c68c3537SAlan Cox } 845c68c3537SAlan Cox 846c68c3537SAlan Cox /* 847c68c3537SAlan Cox * Could a reservation fit between the first index to the left that 848c68c3537SAlan Cox * can be used and the first index to the right that cannot be used? 849e2068d0bSJeff Roberson * 850e2068d0bSJeff Roberson * We must synchronize with the reserv object lock to protect the 851e2068d0bSJeff Roberson * pindex/object of the resulting reservations against rename while 852e2068d0bSJeff Roberson * we are inspecting. 853f8a47341SAlan Cox */ 854c68c3537SAlan Cox first = pindex - VM_RESERV_INDEX(object, pindex); 855e2068d0bSJeff Roberson vm_reserv_object_lock(object); 856c68c3537SAlan Cox if (mpred != NULL) { 857c68c3537SAlan Cox if ((rv = vm_reserv_from_page(mpred))->object != object) 858f8a47341SAlan Cox leftcap = mpred->pindex + 1; 859f8a47341SAlan Cox else 860f8a47341SAlan Cox leftcap = rv->pindex + VM_LEVEL_0_NPAGES; 861e2068d0bSJeff Roberson if (leftcap > first) { 862e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 863c68c3537SAlan Cox return (NULL); 864c68c3537SAlan Cox } 865e2068d0bSJeff Roberson } 866c68c3537SAlan Cox if (msucc != NULL) { 867c68c3537SAlan Cox if ((rv = vm_reserv_from_page(msucc))->object != object) 868f8a47341SAlan Cox rightcap = msucc->pindex; 869f8a47341SAlan Cox else 870f8a47341SAlan Cox rightcap = rv->pindex; 871e2068d0bSJeff Roberson if (first + VM_LEVEL_0_NPAGES > rightcap) { 872e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 873f8a47341SAlan Cox return (NULL); 874c68c3537SAlan Cox } 875e2068d0bSJeff Roberson } 876e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 877f8a47341SAlan Cox 878f8a47341SAlan Cox /* 879c68c3537SAlan Cox * Would a new reservation extend past the end of the object? 880f8a47341SAlan Cox */ 881c68c3537SAlan Cox if (first + VM_LEVEL_0_NPAGES > object->size) { 882f8a47341SAlan Cox /* 883f8a47341SAlan Cox * Don't allocate a new reservation if the object is a vnode or 884f8a47341SAlan Cox * backed by another object that is a vnode. 885f8a47341SAlan Cox */ 886f8a47341SAlan Cox if (object->type == OBJT_VNODE || 887f8a47341SAlan Cox (object->backing_object != NULL && 888f8a47341SAlan Cox object->backing_object->type == OBJT_VNODE)) 889f8a47341SAlan Cox return (NULL); 890f8a47341SAlan Cox /* Speculate that the object may grow. */ 891f8a47341SAlan Cox } 892f8a47341SAlan Cox 893f8a47341SAlan Cox /* 894c68c3537SAlan Cox * Allocate and populate the new reservation. 895f8a47341SAlan Cox */ 8965c930c89SJeff Roberson m = NULL; 8975c930c89SJeff Roberson vmd = VM_DOMAIN(domain); 8985c930c89SJeff Roberson if (vm_domain_allocate(vmd, req, 1)) { 8995c930c89SJeff Roberson vm_domain_free_lock(vmd); 9005c930c89SJeff Roberson m = vm_phys_alloc_pages(domain, VM_FREEPOOL_DEFAULT, 9015c930c89SJeff Roberson VM_LEVEL_0_ORDER); 9025c930c89SJeff Roberson vm_domain_free_unlock(vmd); 9035c930c89SJeff Roberson if (m == NULL) { 9045c930c89SJeff Roberson vm_domain_freecnt_inc(vmd, 1); 9055c930c89SJeff Roberson return (NULL); 9065c930c89SJeff Roberson } 9075c930c89SJeff Roberson } else 908c68c3537SAlan Cox return (NULL); 909f8a47341SAlan Cox rv = vm_reserv_from_page(m); 9105c930c89SJeff Roberson vm_reserv_lock(rv); 911f8a47341SAlan Cox KASSERT(rv->pages == m, 912c68c3537SAlan Cox ("vm_reserv_alloc_page: reserv %p's pages is corrupted", rv)); 913e2068d0bSJeff Roberson vm_reserv_insert(rv, object, first); 914ec179322SAlan Cox index = VM_RESERV_INDEX(object, pindex); 915ec179322SAlan Cox vm_reserv_populate(rv, index); 9165c930c89SJeff Roberson vm_reserv_unlock(rv); 9175c930c89SJeff Roberson 918ec179322SAlan Cox return (&rv->pages[index]); 919f8a47341SAlan Cox } 920f8a47341SAlan Cox 921f8a47341SAlan Cox /* 922ada27a3bSKonstantin Belousov * Breaks the given reservation. All free pages in the reservation 923ada27a3bSKonstantin Belousov * are returned to the physical memory allocator. The reservation's 924ada27a3bSKonstantin Belousov * population count and map are reset to their initial state. 925ec179322SAlan Cox * 9263453bca8SAlan Cox * The given reservation must not be in the partially populated reservation 927ec179322SAlan Cox * queue. The free page queue lock must be held. 928ec179322SAlan Cox */ 929ec179322SAlan Cox static void 930ada27a3bSKonstantin Belousov vm_reserv_break(vm_reserv_t rv) 931ec179322SAlan Cox { 932e67a5068SDoug Moore u_long changes; 933e67a5068SDoug Moore int bitpos, hi, i, lo; 934ec179322SAlan Cox 9355c930c89SJeff Roberson vm_reserv_assert_locked(rv); 9365c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 9375c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 938e2068d0bSJeff Roberson vm_reserv_remove(rv); 939c4be9169SKonstantin Belousov rv->pages->psind = 0; 940e67a5068SDoug Moore hi = lo = -1; 941e67a5068SDoug Moore for (i = 0; i <= NPOPMAP; i++) { 942e67a5068SDoug Moore /* 943e67a5068SDoug Moore * "changes" is a bitmask that marks where a new sequence of 944e67a5068SDoug Moore * 0s or 1s begins in popmap[i], with last bit in popmap[i-1] 945e67a5068SDoug Moore * considered to be 1 if and only if lo == hi. The bits of 946e67a5068SDoug Moore * popmap[-1] and popmap[NPOPMAP] are considered all 1s. 947e67a5068SDoug Moore */ 948ec179322SAlan Cox if (i == NPOPMAP) 949e67a5068SDoug Moore changes = lo != hi; 950e67a5068SDoug Moore else { 951e67a5068SDoug Moore changes = rv->popmap[i]; 952e67a5068SDoug Moore changes ^= (changes << 1) | (lo == hi); 953e67a5068SDoug Moore rv->popmap[i] = 0; 954ec179322SAlan Cox } 955e67a5068SDoug Moore while (changes != 0) { 956e67a5068SDoug Moore /* 957e67a5068SDoug Moore * If the next change marked begins a run of 0s, set 958e67a5068SDoug Moore * lo to mark that position. Otherwise set hi and 959e67a5068SDoug Moore * free pages from lo up to hi. 960e67a5068SDoug Moore */ 961e67a5068SDoug Moore bitpos = ffsl(changes) - 1; 962e67a5068SDoug Moore changes ^= 1UL << bitpos; 963e67a5068SDoug Moore if (lo == hi) 964e67a5068SDoug Moore lo = NBPOPMAP * i + bitpos; 965e67a5068SDoug Moore else { 966e67a5068SDoug Moore hi = NBPOPMAP * i + bitpos; 9675c930c89SJeff Roberson vm_domain_free_lock(VM_DOMAIN(rv->domain)); 968b8590daeSDoug Moore vm_phys_enqueue_contig(&rv->pages[lo], hi - lo); 9695c930c89SJeff Roberson vm_domain_free_unlock(VM_DOMAIN(rv->domain)); 970e67a5068SDoug Moore lo = hi; 971e67a5068SDoug Moore } 972e67a5068SDoug Moore } 973e67a5068SDoug Moore } 974e67a5068SDoug Moore rv->popcnt = 0; 9755c930c89SJeff Roberson counter_u64_add(vm_reserv_broken, 1); 976ec179322SAlan Cox } 977ec179322SAlan Cox 978ec179322SAlan Cox /* 979f8a47341SAlan Cox * Breaks all reservations belonging to the given object. 980f8a47341SAlan Cox */ 981f8a47341SAlan Cox void 982f8a47341SAlan Cox vm_reserv_break_all(vm_object_t object) 983f8a47341SAlan Cox { 984f8a47341SAlan Cox vm_reserv_t rv; 985f8a47341SAlan Cox 986e2068d0bSJeff Roberson /* 987e2068d0bSJeff Roberson * This access of object->rvq is unsynchronized so that the 988e2068d0bSJeff Roberson * object rvq lock can nest after the domain_free lock. We 989e2068d0bSJeff Roberson * must check for races in the results. However, the object 990e2068d0bSJeff Roberson * lock prevents new additions, so we are guaranteed that when 991e2068d0bSJeff Roberson * it returns NULL the object is properly empty. 992e2068d0bSJeff Roberson */ 993f8a47341SAlan Cox while ((rv = LIST_FIRST(&object->rvq)) != NULL) { 9945c930c89SJeff Roberson vm_reserv_lock(rv); 995e2068d0bSJeff Roberson /* Reclaim race. */ 9965c930c89SJeff Roberson if (rv->object != object) { 9975c930c89SJeff Roberson vm_reserv_unlock(rv); 998e2068d0bSJeff Roberson continue; 9995c930c89SJeff Roberson } 10005c930c89SJeff Roberson vm_reserv_domain_lock(rv->domain); 1001f8a47341SAlan Cox if (rv->inpartpopq) { 1002ef435ae7SJeff Roberson TAILQ_REMOVE(&vm_rvq_partpop[rv->domain], rv, partpopq); 1003f8a47341SAlan Cox rv->inpartpopq = FALSE; 1004f8a47341SAlan Cox } 10055c930c89SJeff Roberson vm_reserv_domain_unlock(rv->domain); 1006ada27a3bSKonstantin Belousov vm_reserv_break(rv); 10075c930c89SJeff Roberson vm_reserv_unlock(rv); 1008f8a47341SAlan Cox } 1009f8a47341SAlan Cox } 1010f8a47341SAlan Cox 1011f8a47341SAlan Cox /* 1012f8a47341SAlan Cox * Frees the given page if it belongs to a reservation. Returns TRUE if the 1013f8a47341SAlan Cox * page is freed and FALSE otherwise. 1014f8a47341SAlan Cox * 1015f8a47341SAlan Cox * The free page queue lock must be held. 1016f8a47341SAlan Cox */ 1017f8a47341SAlan Cox boolean_t 1018f8a47341SAlan Cox vm_reserv_free_page(vm_page_t m) 1019f8a47341SAlan Cox { 1020f8a47341SAlan Cox vm_reserv_t rv; 10215c930c89SJeff Roberson boolean_t ret; 1022f8a47341SAlan Cox 1023f8a47341SAlan Cox rv = vm_reserv_from_page(m); 1024908e3da1SAlan Cox if (rv->object == NULL) 1025908e3da1SAlan Cox return (FALSE); 10265c930c89SJeff Roberson vm_reserv_lock(rv); 10275c930c89SJeff Roberson /* Re-validate after lock. */ 10285c930c89SJeff Roberson if (rv->object != NULL) { 1029ec179322SAlan Cox vm_reserv_depopulate(rv, m - rv->pages); 10305c930c89SJeff Roberson ret = TRUE; 10315c930c89SJeff Roberson } else 10325c930c89SJeff Roberson ret = FALSE; 10335c930c89SJeff Roberson vm_reserv_unlock(rv); 10345c930c89SJeff Roberson 10355c930c89SJeff Roberson return (ret); 1036f8a47341SAlan Cox } 1037f8a47341SAlan Cox 1038f8a47341SAlan Cox /* 1039f8a47341SAlan Cox * Initializes the reservation management system. Specifically, initializes 1040f8a47341SAlan Cox * the reservation array. 1041f8a47341SAlan Cox * 1042f8a47341SAlan Cox * Requires that vm_page_array and first_page are initialized! 1043f8a47341SAlan Cox */ 1044f8a47341SAlan Cox void 1045f8a47341SAlan Cox vm_reserv_init(void) 1046f8a47341SAlan Cox { 1047f8a47341SAlan Cox vm_paddr_t paddr; 104809e5f3c4SAlan Cox struct vm_phys_seg *seg; 10495c930c89SJeff Roberson struct vm_reserv *rv; 1050ef435ae7SJeff Roberson int i, segind; 1051f8a47341SAlan Cox 1052f8a47341SAlan Cox /* 1053f8a47341SAlan Cox * Initialize the reservation array. Specifically, initialize the 1054f8a47341SAlan Cox * "pages" field for every element that has an underlying superpage. 1055f8a47341SAlan Cox */ 105609e5f3c4SAlan Cox for (segind = 0; segind < vm_phys_nsegs; segind++) { 105709e5f3c4SAlan Cox seg = &vm_phys_segs[segind]; 105809e5f3c4SAlan Cox paddr = roundup2(seg->start, VM_LEVEL_0_SIZE); 10596b821a74SAleksandr Rybalko while (paddr + VM_LEVEL_0_SIZE > paddr && paddr + 10606b821a74SAleksandr Rybalko VM_LEVEL_0_SIZE <= seg->end) { 10615c930c89SJeff Roberson rv = &vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT]; 10625c930c89SJeff Roberson rv->pages = PHYS_TO_VM_PAGE(paddr); 10635c930c89SJeff Roberson rv->domain = seg->domain; 10645c930c89SJeff Roberson mtx_init(&rv->lock, "vm reserv", NULL, MTX_DEF); 1065f8a47341SAlan Cox paddr += VM_LEVEL_0_SIZE; 1066f8a47341SAlan Cox } 1067f8a47341SAlan Cox } 10685c930c89SJeff Roberson for (i = 0; i < MAXMEMDOM; i++) { 10695c930c89SJeff Roberson mtx_init(&vm_reserv_domain_locks[i], "VM reserv domain", NULL, 10705c930c89SJeff Roberson MTX_DEF); 1071ef435ae7SJeff Roberson TAILQ_INIT(&vm_rvq_partpop[i]); 1072f8a47341SAlan Cox } 1073f8a47341SAlan Cox 10745c930c89SJeff Roberson for (i = 0; i < VM_RESERV_OBJ_LOCK_COUNT; i++) 10755c930c89SJeff Roberson mtx_init(&vm_reserv_object_mtx[i], "resv obj lock", NULL, 10765c930c89SJeff Roberson MTX_DEF); 10775c930c89SJeff Roberson } 10785c930c89SJeff Roberson 1079f8a47341SAlan Cox /* 1080c869e672SAlan Cox * Returns true if the given page belongs to a reservation and that page is 1081c869e672SAlan Cox * free. Otherwise, returns false. 1082c869e672SAlan Cox */ 1083c869e672SAlan Cox bool 1084c869e672SAlan Cox vm_reserv_is_page_free(vm_page_t m) 1085c869e672SAlan Cox { 1086c869e672SAlan Cox vm_reserv_t rv; 1087c869e672SAlan Cox 1088c869e672SAlan Cox rv = vm_reserv_from_page(m); 1089c869e672SAlan Cox if (rv->object == NULL) 1090c869e672SAlan Cox return (false); 1091c869e672SAlan Cox return (popmap_is_clear(rv->popmap, m - rv->pages)); 1092c869e672SAlan Cox } 1093c869e672SAlan Cox 1094c869e672SAlan Cox /* 1095c869e672SAlan Cox * If the given page belongs to a reservation, returns the level of that 1096c869e672SAlan Cox * reservation. Otherwise, returns -1. 1097c869e672SAlan Cox */ 1098c869e672SAlan Cox int 1099c869e672SAlan Cox vm_reserv_level(vm_page_t m) 1100c869e672SAlan Cox { 1101c869e672SAlan Cox vm_reserv_t rv; 1102c869e672SAlan Cox 1103c869e672SAlan Cox rv = vm_reserv_from_page(m); 1104c869e672SAlan Cox return (rv->object != NULL ? 0 : -1); 1105c869e672SAlan Cox } 1106c869e672SAlan Cox 1107c869e672SAlan Cox /* 11083453bca8SAlan Cox * Returns a reservation level if the given page belongs to a fully populated 1109f8a47341SAlan Cox * reservation and -1 otherwise. 1110f8a47341SAlan Cox */ 1111f8a47341SAlan Cox int 1112f8a47341SAlan Cox vm_reserv_level_iffullpop(vm_page_t m) 1113f8a47341SAlan Cox { 1114f8a47341SAlan Cox vm_reserv_t rv; 1115f8a47341SAlan Cox 1116f8a47341SAlan Cox rv = vm_reserv_from_page(m); 1117f8a47341SAlan Cox return (rv->popcnt == VM_LEVEL_0_NPAGES ? 0 : -1); 1118f8a47341SAlan Cox } 1119f8a47341SAlan Cox 1120f8a47341SAlan Cox /* 11213453bca8SAlan Cox * Breaks the given partially populated reservation, releasing its free pages 11223453bca8SAlan Cox * to the physical memory allocator. 1123f8a47341SAlan Cox * 1124f8a47341SAlan Cox * The free page queue lock must be held. 1125f8a47341SAlan Cox */ 112644aab2c3SAlan Cox static void 112744aab2c3SAlan Cox vm_reserv_reclaim(vm_reserv_t rv) 1128f8a47341SAlan Cox { 1129f8a47341SAlan Cox 11305c930c89SJeff Roberson vm_reserv_assert_locked(rv); 11315c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 11325c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 11335c930c89SJeff Roberson vm_reserv_domain_lock(rv->domain); 1134f8a47341SAlan Cox KASSERT(rv->inpartpopq, 1135ec179322SAlan Cox ("vm_reserv_reclaim: reserv %p's inpartpopq is FALSE", rv)); 11362d3f4181SJeff Roberson KASSERT(rv->domain < vm_ndomains, 1137ef435ae7SJeff Roberson ("vm_reserv_reclaim: reserv %p's domain is corrupted %d", 1138ef435ae7SJeff Roberson rv, rv->domain)); 1139ef435ae7SJeff Roberson TAILQ_REMOVE(&vm_rvq_partpop[rv->domain], rv, partpopq); 1140f8a47341SAlan Cox rv->inpartpopq = FALSE; 11415c930c89SJeff Roberson vm_reserv_domain_unlock(rv->domain); 1142ada27a3bSKonstantin Belousov vm_reserv_break(rv); 11435c930c89SJeff Roberson counter_u64_add(vm_reserv_reclaimed, 1); 114444aab2c3SAlan Cox } 114544aab2c3SAlan Cox 114644aab2c3SAlan Cox /* 11473453bca8SAlan Cox * Breaks the reservation at the head of the partially populated reservation 11483453bca8SAlan Cox * queue, releasing its free pages to the physical memory allocator. Returns 11493453bca8SAlan Cox * TRUE if a reservation is broken and FALSE otherwise. 115044aab2c3SAlan Cox * 115144aab2c3SAlan Cox * The free page queue lock must be held. 115244aab2c3SAlan Cox */ 115344aab2c3SAlan Cox boolean_t 1154ef435ae7SJeff Roberson vm_reserv_reclaim_inactive(int domain) 115544aab2c3SAlan Cox { 115644aab2c3SAlan Cox vm_reserv_t rv; 115744aab2c3SAlan Cox 11585c930c89SJeff Roberson while ((rv = TAILQ_FIRST(&vm_rvq_partpop[domain])) != NULL) { 11595c930c89SJeff Roberson vm_reserv_lock(rv); 11605c930c89SJeff Roberson if (rv != TAILQ_FIRST(&vm_rvq_partpop[domain])) { 11615c930c89SJeff Roberson vm_reserv_unlock(rv); 11625c930c89SJeff Roberson continue; 11635c930c89SJeff Roberson } 116444aab2c3SAlan Cox vm_reserv_reclaim(rv); 11655c930c89SJeff Roberson vm_reserv_unlock(rv); 1166f8a47341SAlan Cox return (TRUE); 1167f8a47341SAlan Cox } 1168f8a47341SAlan Cox return (FALSE); 1169f8a47341SAlan Cox } 1170f8a47341SAlan Cox 1171f8a47341SAlan Cox /* 1172f96e8a0bSDoug Moore * Determine whether this reservation has free pages that satisfy the given 1173f96e8a0bSDoug Moore * request for contiguous physical memory. Start searching from the lower 1174f96e8a0bSDoug Moore * bound, defined by low_index. 1175f96e8a0bSDoug Moore * 1176f96e8a0bSDoug Moore * The free page queue lock must be held. 1177f96e8a0bSDoug Moore */ 1178f96e8a0bSDoug Moore static bool 1179f96e8a0bSDoug Moore vm_reserv_test_contig(vm_reserv_t rv, u_long npages, vm_paddr_t low, 1180f96e8a0bSDoug Moore vm_paddr_t high, u_long alignment, vm_paddr_t boundary) 1181f96e8a0bSDoug Moore { 1182f96e8a0bSDoug Moore vm_paddr_t pa, size; 1183f96e8a0bSDoug Moore u_long changes; 1184f96e8a0bSDoug Moore int bitpos, bits_left, i, hi, lo, n; 1185f96e8a0bSDoug Moore 1186f96e8a0bSDoug Moore vm_reserv_assert_locked(rv); 1187f96e8a0bSDoug Moore size = npages << PAGE_SHIFT; 1188f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[0]); 1189f96e8a0bSDoug Moore lo = (pa < low) ? 1190f96e8a0bSDoug Moore ((low + PAGE_MASK - pa) >> PAGE_SHIFT) : 0; 1191f96e8a0bSDoug Moore i = lo / NBPOPMAP; 1192f96e8a0bSDoug Moore changes = rv->popmap[i] | ((1UL << (lo % NBPOPMAP)) - 1); 1193f96e8a0bSDoug Moore hi = (pa + VM_LEVEL_0_SIZE > high) ? 1194f96e8a0bSDoug Moore ((high + PAGE_MASK - pa) >> PAGE_SHIFT) : VM_LEVEL_0_NPAGES; 1195f96e8a0bSDoug Moore n = hi / NBPOPMAP; 1196f96e8a0bSDoug Moore bits_left = hi % NBPOPMAP; 1197f96e8a0bSDoug Moore hi = lo = -1; 1198f96e8a0bSDoug Moore for (;;) { 1199f96e8a0bSDoug Moore /* 1200f96e8a0bSDoug Moore * "changes" is a bitmask that marks where a new sequence of 1201f96e8a0bSDoug Moore * 0s or 1s begins in popmap[i], with last bit in popmap[i-1] 1202f96e8a0bSDoug Moore * considered to be 1 if and only if lo == hi. The bits of 1203f96e8a0bSDoug Moore * popmap[-1] and popmap[NPOPMAP] are considered all 1s. 1204f96e8a0bSDoug Moore */ 1205f96e8a0bSDoug Moore changes ^= (changes << 1) | (lo == hi); 1206f96e8a0bSDoug Moore while (changes != 0) { 1207f96e8a0bSDoug Moore /* 1208f96e8a0bSDoug Moore * If the next change marked begins a run of 0s, set 1209f96e8a0bSDoug Moore * lo to mark that position. Otherwise set hi and 1210f96e8a0bSDoug Moore * look for a satisfactory first page from lo up to hi. 1211f96e8a0bSDoug Moore */ 1212f96e8a0bSDoug Moore bitpos = ffsl(changes) - 1; 1213f96e8a0bSDoug Moore changes ^= 1UL << bitpos; 1214f96e8a0bSDoug Moore if (lo == hi) { 1215f96e8a0bSDoug Moore lo = NBPOPMAP * i + bitpos; 1216f96e8a0bSDoug Moore continue; 1217f96e8a0bSDoug Moore } 1218f96e8a0bSDoug Moore hi = NBPOPMAP * i + bitpos; 1219f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); 1220f96e8a0bSDoug Moore if ((pa & (alignment - 1)) != 0) { 1221f96e8a0bSDoug Moore /* Skip to next aligned page. */ 1222f96e8a0bSDoug Moore lo += (((pa - 1) | (alignment - 1)) + 1) >> 1223f96e8a0bSDoug Moore PAGE_SHIFT; 1224f96e8a0bSDoug Moore if (lo >= VM_LEVEL_0_NPAGES) 1225f96e8a0bSDoug Moore return (false); 1226f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); 1227f96e8a0bSDoug Moore } 1228f96e8a0bSDoug Moore if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) { 1229f96e8a0bSDoug Moore /* Skip to next boundary-matching page. */ 1230f96e8a0bSDoug Moore lo += (((pa - 1) | (boundary - 1)) + 1) >> 1231f96e8a0bSDoug Moore PAGE_SHIFT; 1232f96e8a0bSDoug Moore if (lo >= VM_LEVEL_0_NPAGES) 1233f96e8a0bSDoug Moore return (false); 1234f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); 1235f96e8a0bSDoug Moore } 1236f96e8a0bSDoug Moore if (lo * PAGE_SIZE + size <= hi * PAGE_SIZE) 1237f96e8a0bSDoug Moore return (true); 1238f96e8a0bSDoug Moore lo = hi; 1239f96e8a0bSDoug Moore } 1240f96e8a0bSDoug Moore if (++i < n) 1241f96e8a0bSDoug Moore changes = rv->popmap[i]; 1242f96e8a0bSDoug Moore else if (i == n) 1243f96e8a0bSDoug Moore changes = bits_left == 0 ? -1UL : 1244f96e8a0bSDoug Moore (rv->popmap[n] | (-1UL << bits_left)); 1245f96e8a0bSDoug Moore else 1246f96e8a0bSDoug Moore return (false); 1247f96e8a0bSDoug Moore } 1248f96e8a0bSDoug Moore } 1249f96e8a0bSDoug Moore 1250f96e8a0bSDoug Moore /* 12513453bca8SAlan Cox * Searches the partially populated reservation queue for the least recently 12523453bca8SAlan Cox * changed reservation with free pages that satisfy the given request for 12533453bca8SAlan Cox * contiguous physical memory. If a satisfactory reservation is found, it is 1254f96e8a0bSDoug Moore * broken. Returns true if a reservation is broken and false otherwise. 125544aab2c3SAlan Cox * 125644aab2c3SAlan Cox * The free page queue lock must be held. 125744aab2c3SAlan Cox */ 125844aab2c3SAlan Cox boolean_t 1259ef435ae7SJeff Roberson vm_reserv_reclaim_contig(int domain, u_long npages, vm_paddr_t low, 1260ef435ae7SJeff Roberson vm_paddr_t high, u_long alignment, vm_paddr_t boundary) 126144aab2c3SAlan Cox { 1262ec179322SAlan Cox vm_paddr_t pa, size; 12635c930c89SJeff Roberson vm_reserv_t rv, rvn; 126444aab2c3SAlan Cox 1265c68c3537SAlan Cox if (npages > VM_LEVEL_0_NPAGES - 1) 1266f96e8a0bSDoug Moore return (false); 1267c68c3537SAlan Cox size = npages << PAGE_SHIFT; 12685c930c89SJeff Roberson vm_reserv_domain_lock(domain); 12695c930c89SJeff Roberson again: 12705c930c89SJeff Roberson for (rv = TAILQ_FIRST(&vm_rvq_partpop[domain]); rv != NULL; rv = rvn) { 12715c930c89SJeff Roberson rvn = TAILQ_NEXT(rv, partpopq); 1272f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[0]); 1273f96e8a0bSDoug Moore if (pa + VM_LEVEL_0_SIZE - size < low) { 1274ec179322SAlan Cox /* This entire reservation is too low; go to next. */ 127544aab2c3SAlan Cox continue; 127644aab2c3SAlan Cox } 127744aab2c3SAlan Cox if (pa + size > high) { 1278ec179322SAlan Cox /* This entire reservation is too high; go to next. */ 1279ec179322SAlan Cox continue; 128085f2a0c9SMax Laier } 12815c930c89SJeff Roberson if (vm_reserv_trylock(rv) == 0) { 12825c930c89SJeff Roberson vm_reserv_domain_unlock(domain); 12835c930c89SJeff Roberson vm_reserv_lock(rv); 12845c930c89SJeff Roberson if (!rv->inpartpopq) { 12855c930c89SJeff Roberson vm_reserv_domain_lock(domain); 12865c930c89SJeff Roberson if (!rvn->inpartpopq) 12875c930c89SJeff Roberson goto again; 12885c930c89SJeff Roberson continue; 12895c930c89SJeff Roberson } 12905c930c89SJeff Roberson } else 12915c930c89SJeff Roberson vm_reserv_domain_unlock(domain); 1292f96e8a0bSDoug Moore if (vm_reserv_test_contig(rv, npages, low, high, 1293f96e8a0bSDoug Moore alignment, boundary)) { 129444aab2c3SAlan Cox vm_reserv_reclaim(rv); 12955c930c89SJeff Roberson vm_reserv_unlock(rv); 1296f96e8a0bSDoug Moore return (true); 129744aab2c3SAlan Cox } 12985c930c89SJeff Roberson vm_reserv_unlock(rv); 12995c930c89SJeff Roberson vm_reserv_domain_lock(domain); 13005c930c89SJeff Roberson if (rvn != NULL && !rvn->inpartpopq) 13015c930c89SJeff Roberson goto again; 130244aab2c3SAlan Cox } 13035c930c89SJeff Roberson vm_reserv_domain_unlock(domain); 1304f96e8a0bSDoug Moore return (false); 130544aab2c3SAlan Cox } 130644aab2c3SAlan Cox 130744aab2c3SAlan Cox /* 1308f8a47341SAlan Cox * Transfers the reservation underlying the given page to a new object. 1309f8a47341SAlan Cox * 1310f8a47341SAlan Cox * The object must be locked. 1311f8a47341SAlan Cox */ 1312f8a47341SAlan Cox void 1313f8a47341SAlan Cox vm_reserv_rename(vm_page_t m, vm_object_t new_object, vm_object_t old_object, 1314f8a47341SAlan Cox vm_pindex_t old_object_offset) 1315f8a47341SAlan Cox { 1316f8a47341SAlan Cox vm_reserv_t rv; 1317f8a47341SAlan Cox 131889f6b863SAttilio Rao VM_OBJECT_ASSERT_WLOCKED(new_object); 1319f8a47341SAlan Cox rv = vm_reserv_from_page(m); 1320f8a47341SAlan Cox if (rv->object == old_object) { 13215c930c89SJeff Roberson vm_reserv_lock(rv); 13225c930c89SJeff Roberson CTR6(KTR_VM, 13235c930c89SJeff Roberson "%s: rv %p object %p new %p popcnt %d inpartpop %d", 13245c930c89SJeff Roberson __FUNCTION__, rv, rv->object, new_object, rv->popcnt, 13255c930c89SJeff Roberson rv->inpartpopq); 1326f8a47341SAlan Cox if (rv->object == old_object) { 1327e2068d0bSJeff Roberson vm_reserv_object_lock(old_object); 1328e2068d0bSJeff Roberson rv->object = NULL; 1329f8a47341SAlan Cox LIST_REMOVE(rv, objq); 1330e2068d0bSJeff Roberson vm_reserv_object_unlock(old_object); 1331e2068d0bSJeff Roberson vm_reserv_object_lock(new_object); 1332f8a47341SAlan Cox rv->object = new_object; 1333f8a47341SAlan Cox rv->pindex -= old_object_offset; 1334e2068d0bSJeff Roberson LIST_INSERT_HEAD(&new_object->rvq, rv, objq); 1335e2068d0bSJeff Roberson vm_reserv_object_unlock(new_object); 1336f8a47341SAlan Cox } 13375c930c89SJeff Roberson vm_reserv_unlock(rv); 1338f8a47341SAlan Cox } 1339f8a47341SAlan Cox } 1340f8a47341SAlan Cox 1341f8a47341SAlan Cox /* 1342c869e672SAlan Cox * Returns the size (in bytes) of a reservation of the specified level. 1343c869e672SAlan Cox */ 1344c869e672SAlan Cox int 1345c869e672SAlan Cox vm_reserv_size(int level) 1346c869e672SAlan Cox { 1347c869e672SAlan Cox 1348c869e672SAlan Cox switch (level) { 1349c869e672SAlan Cox case 0: 1350c869e672SAlan Cox return (VM_LEVEL_0_SIZE); 1351c869e672SAlan Cox case -1: 1352c869e672SAlan Cox return (PAGE_SIZE); 1353c869e672SAlan Cox default: 1354c869e672SAlan Cox return (0); 1355c869e672SAlan Cox } 1356c869e672SAlan Cox } 1357c869e672SAlan Cox 1358c869e672SAlan Cox /* 1359f8a47341SAlan Cox * Allocates the virtual and physical memory required by the reservation 1360f8a47341SAlan Cox * management system's data structures, in particular, the reservation array. 1361f8a47341SAlan Cox */ 1362f8a47341SAlan Cox vm_paddr_t 1363*3e5e1b51SJeff Roberson vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end) 1364f8a47341SAlan Cox { 1365*3e5e1b51SJeff Roberson vm_paddr_t new_end, high_water; 1366f8a47341SAlan Cox size_t size; 1367*3e5e1b51SJeff Roberson int i; 1368*3e5e1b51SJeff Roberson 1369*3e5e1b51SJeff Roberson high_water = phys_avail[1]; 1370*3e5e1b51SJeff Roberson for (i = 0; i < vm_phys_nsegs; i++) { 1371*3e5e1b51SJeff Roberson if (vm_phys_segs[i].end > high_water) 1372*3e5e1b51SJeff Roberson high_water = vm_phys_segs[i].end; 1373*3e5e1b51SJeff Roberson } 1374*3e5e1b51SJeff Roberson 1375*3e5e1b51SJeff Roberson /* Skip the first chunk. It is already accounted for. */ 1376*3e5e1b51SJeff Roberson for (i = 2; phys_avail[i + 1] != 0; i += 2) { 1377*3e5e1b51SJeff Roberson if (phys_avail[i + 1] > high_water) 1378*3e5e1b51SJeff Roberson high_water = phys_avail[i + 1]; 1379*3e5e1b51SJeff Roberson } 1380f8a47341SAlan Cox 1381f8a47341SAlan Cox /* 1382f8a47341SAlan Cox * Calculate the size (in bytes) of the reservation array. Round up 1383f8a47341SAlan Cox * from "high_water" because every small page is mapped to an element 1384f8a47341SAlan Cox * in the reservation array based on its physical address. Thus, the 1385f8a47341SAlan Cox * number of elements in the reservation array can be greater than the 1386f8a47341SAlan Cox * number of superpages. 1387f8a47341SAlan Cox */ 1388f8a47341SAlan Cox size = howmany(high_water, VM_LEVEL_0_SIZE) * sizeof(struct vm_reserv); 1389f8a47341SAlan Cox 1390f8a47341SAlan Cox /* 1391f8a47341SAlan Cox * Allocate and map the physical memory for the reservation array. The 1392f8a47341SAlan Cox * next available virtual address is returned by reference. 1393f8a47341SAlan Cox */ 1394f8a47341SAlan Cox new_end = end - round_page(size); 1395f8a47341SAlan Cox vm_reserv_array = (void *)(uintptr_t)pmap_map(vaddr, new_end, end, 1396f8a47341SAlan Cox VM_PROT_READ | VM_PROT_WRITE); 1397f8a47341SAlan Cox bzero(vm_reserv_array, size); 1398f8a47341SAlan Cox 1399f8a47341SAlan Cox /* 1400f8a47341SAlan Cox * Return the next available physical address. 1401f8a47341SAlan Cox */ 1402f8a47341SAlan Cox return (new_end); 1403f8a47341SAlan Cox } 1404f8a47341SAlan Cox 14058b5e1472SAlan Cox /* 14065c930c89SJeff Roberson * Initializes the reservation management system. Specifically, initializes 14075c930c89SJeff Roberson * the reservation counters. 14085c930c89SJeff Roberson */ 14095c930c89SJeff Roberson static void 14105c930c89SJeff Roberson vm_reserv_counter_init(void *unused) 14115c930c89SJeff Roberson { 14125c930c89SJeff Roberson 14135c930c89SJeff Roberson vm_reserv_freed = counter_u64_alloc(M_WAITOK); 14145c930c89SJeff Roberson vm_reserv_broken = counter_u64_alloc(M_WAITOK); 14155c930c89SJeff Roberson vm_reserv_reclaimed = counter_u64_alloc(M_WAITOK); 14165c930c89SJeff Roberson } 14175c930c89SJeff Roberson SYSINIT(vm_reserv_counter_init, SI_SUB_CPU, SI_ORDER_ANY, 14185c930c89SJeff Roberson vm_reserv_counter_init, NULL); 14195c930c89SJeff Roberson 14205c930c89SJeff Roberson /* 14218b5e1472SAlan Cox * Returns the superpage containing the given page. 14228b5e1472SAlan Cox */ 14238b5e1472SAlan Cox vm_page_t 14248b5e1472SAlan Cox vm_reserv_to_superpage(vm_page_t m) 14258b5e1472SAlan Cox { 14268b5e1472SAlan Cox vm_reserv_t rv; 14278b5e1472SAlan Cox 14288b5e1472SAlan Cox VM_OBJECT_ASSERT_LOCKED(m->object); 14298b5e1472SAlan Cox rv = vm_reserv_from_page(m); 14305c930c89SJeff Roberson if (rv->object == m->object && rv->popcnt == VM_LEVEL_0_NPAGES) 14315c930c89SJeff Roberson m = rv->pages; 14325c930c89SJeff Roberson else 14335c930c89SJeff Roberson m = NULL; 14345c930c89SJeff Roberson 14355c930c89SJeff Roberson return (m); 14368b5e1472SAlan Cox } 14378b5e1472SAlan Cox 1438f8a47341SAlan Cox #endif /* VM_NRESERVLEVEL > 0 */ 1439