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); 319e0a63baaSAlan Cox while (paddr + VM_LEVEL_0_SIZE <= seg->end) { 320e0a63baaSAlan Cox rv = &vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT]; 321e0a63baaSAlan Cox fullpop += rv->popcnt == VM_LEVEL_0_NPAGES; 322e0a63baaSAlan Cox paddr += VM_LEVEL_0_SIZE; 323e0a63baaSAlan Cox } 324e0a63baaSAlan Cox } 325e0a63baaSAlan Cox return (sysctl_handle_int(oidp, &fullpop, 0, req)); 326e0a63baaSAlan Cox } 327e0a63baaSAlan Cox 328e0a63baaSAlan Cox /* 3293453bca8SAlan Cox * Describes the current state of the partially populated reservation queue. 330f8a47341SAlan Cox */ 331f8a47341SAlan Cox static int 332f8a47341SAlan Cox sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS) 333f8a47341SAlan Cox { 334f8a47341SAlan Cox struct sbuf sbuf; 335f8a47341SAlan Cox vm_reserv_t rv; 336ef435ae7SJeff Roberson int counter, error, domain, level, unused_pages; 337f8a47341SAlan Cox 33800f0e671SMatthew D Fleming error = sysctl_wire_old_buffer(req, 0); 33900f0e671SMatthew D Fleming if (error != 0) 34000f0e671SMatthew D Fleming return (error); 3414e657159SMatthew D Fleming sbuf_new_for_sysctl(&sbuf, NULL, 128, req); 342ef435ae7SJeff Roberson sbuf_printf(&sbuf, "\nDOMAIN LEVEL SIZE NUMBER\n\n"); 343ef435ae7SJeff Roberson for (domain = 0; domain < vm_ndomains; domain++) { 344f8a47341SAlan Cox for (level = -1; level <= VM_NRESERVLEVEL - 2; level++) { 345f8a47341SAlan Cox counter = 0; 346f8a47341SAlan Cox unused_pages = 0; 3475c930c89SJeff Roberson vm_reserv_domain_lock(domain); 348ef435ae7SJeff Roberson TAILQ_FOREACH(rv, &vm_rvq_partpop[domain], partpopq) { 349f8a47341SAlan Cox counter++; 350f8a47341SAlan Cox unused_pages += VM_LEVEL_0_NPAGES - rv->popcnt; 351f8a47341SAlan Cox } 3525c930c89SJeff Roberson vm_reserv_domain_unlock(domain); 353ef435ae7SJeff Roberson sbuf_printf(&sbuf, "%6d, %7d, %6dK, %6d\n", 354ef435ae7SJeff Roberson domain, level, 3552cf36c8fSAlan Cox unused_pages * ((int)PAGE_SIZE / 1024), counter); 356f8a47341SAlan Cox } 357ef435ae7SJeff Roberson } 3584e657159SMatthew D Fleming error = sbuf_finish(&sbuf); 359f8a47341SAlan Cox sbuf_delete(&sbuf); 360f8a47341SAlan Cox return (error); 361f8a47341SAlan Cox } 362f8a47341SAlan Cox 363f8a47341SAlan Cox /* 364e2068d0bSJeff Roberson * Remove a reservation from the object's objq. 365e2068d0bSJeff Roberson */ 366e2068d0bSJeff Roberson static void 367e2068d0bSJeff Roberson vm_reserv_remove(vm_reserv_t rv) 368e2068d0bSJeff Roberson { 369e2068d0bSJeff Roberson vm_object_t object; 370e2068d0bSJeff Roberson 3715c930c89SJeff Roberson vm_reserv_assert_locked(rv); 3725c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 3735c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 374e2068d0bSJeff Roberson KASSERT(rv->object != NULL, 375e2068d0bSJeff Roberson ("vm_reserv_remove: reserv %p is free", rv)); 376e2068d0bSJeff Roberson KASSERT(!rv->inpartpopq, 377e2068d0bSJeff Roberson ("vm_reserv_remove: reserv %p's inpartpopq is TRUE", rv)); 378e2068d0bSJeff Roberson object = rv->object; 379e2068d0bSJeff Roberson vm_reserv_object_lock(object); 380e2068d0bSJeff Roberson LIST_REMOVE(rv, objq); 381e2068d0bSJeff Roberson rv->object = NULL; 382e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 383e2068d0bSJeff Roberson } 384e2068d0bSJeff Roberson 385e2068d0bSJeff Roberson /* 386e2068d0bSJeff Roberson * Insert a new reservation into the object's objq. 387e2068d0bSJeff Roberson */ 388e2068d0bSJeff Roberson static void 389e2068d0bSJeff Roberson vm_reserv_insert(vm_reserv_t rv, vm_object_t object, vm_pindex_t pindex) 390e2068d0bSJeff Roberson { 391e2068d0bSJeff Roberson int i; 392e2068d0bSJeff Roberson 3935c930c89SJeff Roberson vm_reserv_assert_locked(rv); 3945c930c89SJeff Roberson CTR6(KTR_VM, 3955c930c89SJeff Roberson "%s: rv %p(%p) object %p new %p popcnt %d", 3965c930c89SJeff Roberson __FUNCTION__, rv, rv->pages, rv->object, object, 3975c930c89SJeff Roberson rv->popcnt); 398e2068d0bSJeff Roberson KASSERT(rv->object == NULL, 399e2068d0bSJeff Roberson ("vm_reserv_insert: reserv %p isn't free", rv)); 400e2068d0bSJeff Roberson KASSERT(rv->popcnt == 0, 401e2068d0bSJeff Roberson ("vm_reserv_insert: reserv %p's popcnt is corrupted", rv)); 402e2068d0bSJeff Roberson KASSERT(!rv->inpartpopq, 403e2068d0bSJeff Roberson ("vm_reserv_insert: reserv %p's inpartpopq is TRUE", rv)); 404e2068d0bSJeff Roberson for (i = 0; i < NPOPMAP; i++) 405e2068d0bSJeff Roberson KASSERT(rv->popmap[i] == 0, 406e2068d0bSJeff Roberson ("vm_reserv_insert: reserv %p's popmap is corrupted", rv)); 407e2068d0bSJeff Roberson vm_reserv_object_lock(object); 408e2068d0bSJeff Roberson rv->pindex = pindex; 409e2068d0bSJeff Roberson rv->object = object; 4102ef6727eSJeff Roberson rv->lasttick = ticks; 411e2068d0bSJeff Roberson LIST_INSERT_HEAD(&object->rvq, rv, objq); 412e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 413e2068d0bSJeff Roberson } 414e2068d0bSJeff Roberson 415e2068d0bSJeff Roberson /* 416f8a47341SAlan Cox * Reduces the given reservation's population count. If the population count 417f8a47341SAlan Cox * becomes zero, the reservation is destroyed. Additionally, moves the 4183453bca8SAlan Cox * reservation to the tail of the partially populated reservation queue if the 419f8a47341SAlan Cox * population count is non-zero. 420f8a47341SAlan Cox */ 421f8a47341SAlan Cox static void 422ec179322SAlan Cox vm_reserv_depopulate(vm_reserv_t rv, int index) 423f8a47341SAlan Cox { 4245c930c89SJeff Roberson struct vm_domain *vmd; 425f8a47341SAlan Cox 4265c930c89SJeff Roberson vm_reserv_assert_locked(rv); 4275c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 4285c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 429f8a47341SAlan Cox KASSERT(rv->object != NULL, 430f8a47341SAlan Cox ("vm_reserv_depopulate: reserv %p is free", rv)); 4313180f757SAlan Cox KASSERT(popmap_is_set(rv->popmap, index), 432a08c1515SAlan Cox ("vm_reserv_depopulate: reserv %p's popmap[%d] is clear", rv, 433a08c1515SAlan Cox index)); 434f8a47341SAlan Cox KASSERT(rv->popcnt > 0, 435f8a47341SAlan Cox ("vm_reserv_depopulate: reserv %p's popcnt is corrupted", rv)); 4362d3f4181SJeff Roberson KASSERT(rv->domain < vm_ndomains, 437ef435ae7SJeff Roberson ("vm_reserv_depopulate: reserv %p's domain is corrupted %d", 438ef435ae7SJeff Roberson rv, rv->domain)); 4395c930c89SJeff Roberson if (rv->popcnt == VM_LEVEL_0_NPAGES) { 440dd05fa19SAlan Cox KASSERT(rv->pages->psind == 1, 441dd05fa19SAlan Cox ("vm_reserv_depopulate: reserv %p is already demoted", 442dd05fa19SAlan Cox rv)); 443dd05fa19SAlan Cox rv->pages->psind = 0; 444f8a47341SAlan Cox } 4453180f757SAlan Cox popmap_clear(rv->popmap, index); 446f8a47341SAlan Cox rv->popcnt--; 4472ef6727eSJeff Roberson if ((unsigned)(ticks - rv->lasttick) >= PARTPOPSLOP || 4482ef6727eSJeff Roberson rv->popcnt == 0) { 4495c930c89SJeff Roberson vm_reserv_domain_lock(rv->domain); 4505c930c89SJeff Roberson if (rv->inpartpopq) { 4515c930c89SJeff Roberson TAILQ_REMOVE(&vm_rvq_partpop[rv->domain], rv, partpopq); 4525c930c89SJeff Roberson rv->inpartpopq = FALSE; 4535c930c89SJeff Roberson } 4545c930c89SJeff Roberson if (rv->popcnt != 0) { 455f8a47341SAlan Cox rv->inpartpopq = TRUE; 456ef435ae7SJeff Roberson TAILQ_INSERT_TAIL(&vm_rvq_partpop[rv->domain], rv, partpopq); 457f8a47341SAlan Cox } 4585c930c89SJeff Roberson vm_reserv_domain_unlock(rv->domain); 4592ef6727eSJeff Roberson rv->lasttick = ticks; 4602ef6727eSJeff Roberson } 4615c930c89SJeff Roberson vmd = VM_DOMAIN(rv->domain); 4625c930c89SJeff Roberson if (rv->popcnt == 0) { 4635c930c89SJeff Roberson vm_reserv_remove(rv); 4645c930c89SJeff Roberson vm_domain_free_lock(vmd); 4655c930c89SJeff Roberson vm_phys_free_pages(rv->pages, VM_LEVEL_0_ORDER); 4665c930c89SJeff Roberson vm_domain_free_unlock(vmd); 4675c930c89SJeff Roberson counter_u64_add(vm_reserv_freed, 1); 4685c930c89SJeff Roberson } 4695c930c89SJeff Roberson vm_domain_freecnt_inc(vmd, 1); 470f8a47341SAlan Cox } 471f8a47341SAlan Cox 472f8a47341SAlan Cox /* 473f8a47341SAlan Cox * Returns the reservation to which the given page might belong. 474f8a47341SAlan Cox */ 475f8a47341SAlan Cox static __inline vm_reserv_t 476f8a47341SAlan Cox vm_reserv_from_page(vm_page_t m) 477f8a47341SAlan Cox { 478f8a47341SAlan Cox 479f8a47341SAlan Cox return (&vm_reserv_array[VM_PAGE_TO_PHYS(m) >> VM_LEVEL_0_SHIFT]); 480f8a47341SAlan Cox } 481f8a47341SAlan Cox 482f8a47341SAlan Cox /* 483e2068d0bSJeff Roberson * Returns an existing reservation or NULL and initialized successor pointer. 484e2068d0bSJeff Roberson */ 485e2068d0bSJeff Roberson static vm_reserv_t 486e2068d0bSJeff Roberson vm_reserv_from_object(vm_object_t object, vm_pindex_t pindex, 487e2068d0bSJeff Roberson vm_page_t mpred, vm_page_t *msuccp) 488e2068d0bSJeff Roberson { 489e2068d0bSJeff Roberson vm_reserv_t rv; 490e2068d0bSJeff Roberson vm_page_t msucc; 491e2068d0bSJeff Roberson 492e2068d0bSJeff Roberson msucc = NULL; 493e2068d0bSJeff Roberson if (mpred != NULL) { 494e2068d0bSJeff Roberson KASSERT(mpred->object == object, 495e2068d0bSJeff Roberson ("vm_reserv_from_object: object doesn't contain mpred")); 496e2068d0bSJeff Roberson KASSERT(mpred->pindex < pindex, 497e2068d0bSJeff Roberson ("vm_reserv_from_object: mpred doesn't precede pindex")); 498e2068d0bSJeff Roberson rv = vm_reserv_from_page(mpred); 499e2068d0bSJeff Roberson if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) 500e2068d0bSJeff Roberson goto found; 501e2068d0bSJeff Roberson msucc = TAILQ_NEXT(mpred, listq); 502e2068d0bSJeff Roberson } else 503e2068d0bSJeff Roberson msucc = TAILQ_FIRST(&object->memq); 504e2068d0bSJeff Roberson if (msucc != NULL) { 505e2068d0bSJeff Roberson KASSERT(msucc->pindex > pindex, 506e2068d0bSJeff Roberson ("vm_reserv_from_object: msucc doesn't succeed pindex")); 507e2068d0bSJeff Roberson rv = vm_reserv_from_page(msucc); 508e2068d0bSJeff Roberson if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) 509e2068d0bSJeff Roberson goto found; 510e2068d0bSJeff Roberson } 511e2068d0bSJeff Roberson rv = NULL; 512e2068d0bSJeff Roberson 513e2068d0bSJeff Roberson found: 514e2068d0bSJeff Roberson *msuccp = msucc; 515e2068d0bSJeff Roberson 516e2068d0bSJeff Roberson return (rv); 517e2068d0bSJeff Roberson } 518e2068d0bSJeff Roberson 519e2068d0bSJeff Roberson /* 520f8a47341SAlan Cox * Returns TRUE if the given reservation contains the given page index and 521f8a47341SAlan Cox * FALSE otherwise. 522f8a47341SAlan Cox */ 523f8a47341SAlan Cox static __inline boolean_t 524f8a47341SAlan Cox vm_reserv_has_pindex(vm_reserv_t rv, vm_pindex_t pindex) 525f8a47341SAlan Cox { 526f8a47341SAlan Cox 527f8a47341SAlan Cox return (((pindex - rv->pindex) & ~(VM_LEVEL_0_NPAGES - 1)) == 0); 528f8a47341SAlan Cox } 529f8a47341SAlan Cox 530f8a47341SAlan Cox /* 531f8a47341SAlan Cox * Increases the given reservation's population count. Moves the reservation 5323453bca8SAlan Cox * to the tail of the partially populated reservation queue. 533f8a47341SAlan Cox * 534f8a47341SAlan Cox * The free page queue must be locked. 535f8a47341SAlan Cox */ 536f8a47341SAlan Cox static void 537ec179322SAlan Cox vm_reserv_populate(vm_reserv_t rv, int index) 538f8a47341SAlan Cox { 539f8a47341SAlan Cox 5405c930c89SJeff Roberson vm_reserv_assert_locked(rv); 5415c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 5425c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 543f8a47341SAlan Cox KASSERT(rv->object != NULL, 544f8a47341SAlan Cox ("vm_reserv_populate: reserv %p is free", rv)); 5453180f757SAlan Cox KASSERT(popmap_is_clear(rv->popmap, index), 546a08c1515SAlan Cox ("vm_reserv_populate: reserv %p's popmap[%d] is set", rv, 547a08c1515SAlan Cox index)); 548f8a47341SAlan Cox KASSERT(rv->popcnt < VM_LEVEL_0_NPAGES, 549f8a47341SAlan Cox ("vm_reserv_populate: reserv %p is already full", rv)); 550dd05fa19SAlan Cox KASSERT(rv->pages->psind == 0, 551dd05fa19SAlan Cox ("vm_reserv_populate: reserv %p is already promoted", rv)); 5522d3f4181SJeff Roberson KASSERT(rv->domain < vm_ndomains, 553ef435ae7SJeff Roberson ("vm_reserv_populate: reserv %p's domain is corrupted %d", 554ef435ae7SJeff Roberson rv, rv->domain)); 5555c930c89SJeff Roberson popmap_set(rv->popmap, index); 5565c930c89SJeff Roberson rv->popcnt++; 5572ef6727eSJeff Roberson if ((unsigned)(ticks - rv->lasttick) < PARTPOPSLOP && 5582ef6727eSJeff Roberson rv->inpartpopq && rv->popcnt != VM_LEVEL_0_NPAGES) 5592ef6727eSJeff Roberson return; 5602ef6727eSJeff Roberson rv->lasttick = ticks; 5615c930c89SJeff Roberson vm_reserv_domain_lock(rv->domain); 562f8a47341SAlan Cox if (rv->inpartpopq) { 563ef435ae7SJeff Roberson TAILQ_REMOVE(&vm_rvq_partpop[rv->domain], rv, partpopq); 564f8a47341SAlan Cox rv->inpartpopq = FALSE; 565f8a47341SAlan Cox } 566f8a47341SAlan Cox if (rv->popcnt < VM_LEVEL_0_NPAGES) { 567f8a47341SAlan Cox rv->inpartpopq = TRUE; 568ef435ae7SJeff Roberson TAILQ_INSERT_TAIL(&vm_rvq_partpop[rv->domain], rv, partpopq); 5695c930c89SJeff Roberson } else { 5705c930c89SJeff Roberson KASSERT(rv->pages->psind == 0, 5715c930c89SJeff Roberson ("vm_reserv_populate: reserv %p is already promoted", 5725c930c89SJeff Roberson rv)); 573dd05fa19SAlan Cox rv->pages->psind = 1; 574f8a47341SAlan Cox } 5755c930c89SJeff Roberson vm_reserv_domain_unlock(rv->domain); 5765c930c89SJeff Roberson } 577f8a47341SAlan Cox 578f8a47341SAlan Cox /* 579e2068d0bSJeff Roberson * Allocates a contiguous set of physical pages of the given size "npages" 5802d5039dbSAlan Cox * from existing or newly created reservations. All of the physical pages 581e2068d0bSJeff Roberson * must be at or above the given physical address "low" and below the given 582e2068d0bSJeff Roberson * physical address "high". The given value "alignment" determines the 583e2068d0bSJeff Roberson * alignment of the first physical page in the set. If the given value 584e2068d0bSJeff Roberson * "boundary" is non-zero, then the set of physical pages cannot cross any 585e2068d0bSJeff Roberson * physical address boundary that is a multiple of that value. Both 586e2068d0bSJeff Roberson * "alignment" and "boundary" must be a power of two. 587e2068d0bSJeff Roberson * 588e2068d0bSJeff Roberson * The page "mpred" must immediately precede the offset "pindex" within the 589e2068d0bSJeff Roberson * specified object. 590e2068d0bSJeff Roberson * 5912d5039dbSAlan Cox * The object must be locked. 592e2068d0bSJeff Roberson */ 593e2068d0bSJeff Roberson vm_page_t 5942d5039dbSAlan Cox vm_reserv_alloc_contig(vm_object_t object, vm_pindex_t pindex, int domain, 5952d5039dbSAlan Cox int req, vm_page_t mpred, u_long npages, vm_paddr_t low, vm_paddr_t high, 5962d5039dbSAlan Cox u_long alignment, vm_paddr_t boundary) 597c68c3537SAlan Cox { 5985c930c89SJeff Roberson struct vm_domain *vmd; 599c68c3537SAlan Cox vm_paddr_t pa, size; 600920da7e4SAlan Cox vm_page_t m, m_ret, msucc; 601c68c3537SAlan Cox vm_pindex_t first, leftcap, rightcap; 602c68c3537SAlan Cox vm_reserv_t rv; 603c68c3537SAlan Cox u_long allocpages, maxpages, minpages; 604c68c3537SAlan Cox int i, index, n; 605c68c3537SAlan Cox 60689f6b863SAttilio Rao VM_OBJECT_ASSERT_WLOCKED(object); 607c68c3537SAlan Cox KASSERT(npages != 0, ("vm_reserv_alloc_contig: npages is 0")); 608c68c3537SAlan Cox 609c68c3537SAlan Cox /* 610c68c3537SAlan Cox * Is a reservation fundamentally impossible? 611c68c3537SAlan Cox */ 612c68c3537SAlan Cox if (pindex < VM_RESERV_INDEX(object, pindex) || 613c68c3537SAlan Cox pindex + npages > object->size) 614c68c3537SAlan Cox return (NULL); 615c68c3537SAlan Cox 616c68c3537SAlan Cox /* 617c68c3537SAlan Cox * All reservations of a particular size have the same alignment. 618c68c3537SAlan Cox * Assuming that the first page is allocated from a reservation, the 619c68c3537SAlan Cox * least significant bits of its physical address can be determined 620c68c3537SAlan Cox * from its offset from the beginning of the reservation and the size 621c68c3537SAlan Cox * of the reservation. 622c68c3537SAlan Cox * 623c68c3537SAlan Cox * Could the specified index within a reservation of the smallest 624c68c3537SAlan Cox * possible size satisfy the alignment and boundary requirements? 625c68c3537SAlan Cox */ 626c68c3537SAlan Cox pa = VM_RESERV_INDEX(object, pindex) << PAGE_SHIFT; 627c68c3537SAlan Cox if ((pa & (alignment - 1)) != 0) 628c68c3537SAlan Cox return (NULL); 629c68c3537SAlan Cox size = npages << PAGE_SHIFT; 630c68c3537SAlan Cox if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) 631c68c3537SAlan Cox return (NULL); 632c68c3537SAlan Cox 633c68c3537SAlan Cox /* 6342d5039dbSAlan Cox * Look for an existing reservation. 635c68c3537SAlan Cox */ 636e2068d0bSJeff Roberson rv = vm_reserv_from_object(object, pindex, mpred, &msucc); 6372d5039dbSAlan Cox if (rv != NULL) { 6382d5039dbSAlan Cox KASSERT(object != kernel_object || rv->domain == domain, 6392d5039dbSAlan Cox ("vm_reserv_alloc_contig: domain mismatch")); 6402d5039dbSAlan Cox index = VM_RESERV_INDEX(object, pindex); 6412d5039dbSAlan Cox /* Does the allocation fit within the reservation? */ 6422d5039dbSAlan Cox if (index + npages > VM_LEVEL_0_NPAGES) 643e2068d0bSJeff Roberson return (NULL); 6442d5039dbSAlan Cox domain = rv->domain; 6452d5039dbSAlan Cox vmd = VM_DOMAIN(domain); 6462d5039dbSAlan Cox vm_reserv_lock(rv); 6472d5039dbSAlan Cox /* Handle reclaim race. */ 6482d5039dbSAlan Cox if (rv->object != object) 6492d5039dbSAlan Cox goto out; 6502d5039dbSAlan Cox m = &rv->pages[index]; 6512d5039dbSAlan Cox pa = VM_PAGE_TO_PHYS(m); 6522d5039dbSAlan Cox if (pa < low || pa + size > high || 6532d5039dbSAlan Cox (pa & (alignment - 1)) != 0 || 6542d5039dbSAlan Cox ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) 6552d5039dbSAlan Cox goto out; 6562d5039dbSAlan Cox /* Handle vm_page_rename(m, new_object, ...). */ 6572d5039dbSAlan Cox for (i = 0; i < npages; i++) 6582d5039dbSAlan Cox if (popmap_is_set(rv->popmap, index + i)) 6592d5039dbSAlan Cox goto out; 6602d5039dbSAlan Cox if (!vm_domain_allocate(vmd, req, npages)) 6612d5039dbSAlan Cox goto out; 6622d5039dbSAlan Cox for (i = 0; i < npages; i++) 6632d5039dbSAlan Cox vm_reserv_populate(rv, index + i); 6642d5039dbSAlan Cox vm_reserv_unlock(rv); 6652d5039dbSAlan Cox return (m); 6662d5039dbSAlan Cox out: 6672d5039dbSAlan Cox vm_reserv_unlock(rv); 6682d5039dbSAlan Cox return (NULL); 6692d5039dbSAlan Cox } 670c68c3537SAlan Cox 671c68c3537SAlan Cox /* 672c68c3537SAlan Cox * Could at least one reservation fit between the first index to the 67364f096eeSAlan Cox * left that can be used ("leftcap") and the first index to the right 67464f096eeSAlan Cox * that cannot be used ("rightcap")? 675e2068d0bSJeff Roberson * 676e2068d0bSJeff Roberson * We must synchronize with the reserv object lock to protect the 677e2068d0bSJeff Roberson * pindex/object of the resulting reservations against rename while 678e2068d0bSJeff Roberson * we are inspecting. 679c68c3537SAlan Cox */ 680c68c3537SAlan Cox first = pindex - VM_RESERV_INDEX(object, pindex); 681e2068d0bSJeff Roberson minpages = VM_RESERV_INDEX(object, pindex) + npages; 682e2068d0bSJeff Roberson maxpages = roundup2(minpages, VM_LEVEL_0_NPAGES); 683e2068d0bSJeff Roberson allocpages = maxpages; 684e2068d0bSJeff Roberson vm_reserv_object_lock(object); 685c68c3537SAlan Cox if (mpred != NULL) { 686c68c3537SAlan Cox if ((rv = vm_reserv_from_page(mpred))->object != object) 687c68c3537SAlan Cox leftcap = mpred->pindex + 1; 688c68c3537SAlan Cox else 689c68c3537SAlan Cox leftcap = rv->pindex + VM_LEVEL_0_NPAGES; 690e2068d0bSJeff Roberson if (leftcap > first) { 691e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 692c68c3537SAlan Cox return (NULL); 693c68c3537SAlan Cox } 694e2068d0bSJeff Roberson } 695c68c3537SAlan Cox if (msucc != NULL) { 696c68c3537SAlan Cox if ((rv = vm_reserv_from_page(msucc))->object != object) 697c68c3537SAlan Cox rightcap = msucc->pindex; 698c68c3537SAlan Cox else 699c68c3537SAlan Cox rightcap = rv->pindex; 700c68c3537SAlan Cox if (first + maxpages > rightcap) { 701e2068d0bSJeff Roberson if (maxpages == VM_LEVEL_0_NPAGES) { 702e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 703c68c3537SAlan Cox return (NULL); 704e2068d0bSJeff Roberson } 70564f096eeSAlan Cox 70664f096eeSAlan Cox /* 70764f096eeSAlan Cox * At least one reservation will fit between "leftcap" 70864f096eeSAlan Cox * and "rightcap". However, a reservation for the 70964f096eeSAlan Cox * last of the requested pages will not fit. Reduce 71064f096eeSAlan Cox * the size of the upcoming allocation accordingly. 71164f096eeSAlan Cox */ 712c68c3537SAlan Cox allocpages = minpages; 713c68c3537SAlan Cox } 714c68c3537SAlan Cox } 715e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 716c68c3537SAlan Cox 717c68c3537SAlan Cox /* 718c68c3537SAlan Cox * Would the last new reservation extend past the end of the object? 719c68c3537SAlan Cox */ 720c68c3537SAlan Cox if (first + maxpages > object->size) { 721c68c3537SAlan Cox /* 722c68c3537SAlan Cox * Don't allocate the last new reservation if the object is a 723c68c3537SAlan Cox * vnode or backed by another object that is a vnode. 724c68c3537SAlan Cox */ 725c68c3537SAlan Cox if (object->type == OBJT_VNODE || 726c68c3537SAlan Cox (object->backing_object != NULL && 727c68c3537SAlan Cox object->backing_object->type == OBJT_VNODE)) { 728c68c3537SAlan Cox if (maxpages == VM_LEVEL_0_NPAGES) 729c68c3537SAlan Cox return (NULL); 730c68c3537SAlan Cox allocpages = minpages; 731c68c3537SAlan Cox } 732c68c3537SAlan Cox /* Speculate that the object may grow. */ 733c68c3537SAlan Cox } 734c68c3537SAlan Cox 735c68c3537SAlan Cox /* 73664f096eeSAlan Cox * Allocate the physical pages. The alignment and boundary specified 73764f096eeSAlan Cox * for this allocation may be different from the alignment and 73864f096eeSAlan Cox * boundary specified for the requested pages. For instance, the 73964f096eeSAlan Cox * specified index may not be the first page within the first new 74064f096eeSAlan Cox * reservation. 741c68c3537SAlan Cox */ 7425c930c89SJeff Roberson m = NULL; 7435c930c89SJeff Roberson vmd = VM_DOMAIN(domain); 7445c930c89SJeff Roberson if (vm_domain_allocate(vmd, req, npages)) { 7455c930c89SJeff Roberson vm_domain_free_lock(vmd); 7465c930c89SJeff Roberson m = vm_phys_alloc_contig(domain, allocpages, low, high, 7475c930c89SJeff Roberson ulmax(alignment, VM_LEVEL_0_SIZE), 7485c930c89SJeff Roberson boundary > VM_LEVEL_0_SIZE ? boundary : 0); 7495c930c89SJeff Roberson vm_domain_free_unlock(vmd); 7505c930c89SJeff Roberson if (m == NULL) { 7515c930c89SJeff Roberson vm_domain_freecnt_inc(vmd, npages); 7525c930c89SJeff Roberson return (NULL); 7535c930c89SJeff Roberson } 7545c930c89SJeff Roberson } else 755c68c3537SAlan Cox return (NULL); 756e2068d0bSJeff Roberson KASSERT(vm_phys_domain(m) == domain, 7577a469c8eSJeff Roberson ("vm_reserv_alloc_contig: Page domain does not match requested.")); 75864f096eeSAlan Cox 75964f096eeSAlan Cox /* 76064f096eeSAlan Cox * The allocated physical pages always begin at a reservation 76164f096eeSAlan Cox * boundary, but they do not always end at a reservation boundary. 76264f096eeSAlan Cox * Initialize every reservation that is completely covered by the 76364f096eeSAlan Cox * allocated physical pages. 76464f096eeSAlan Cox */ 765c68c3537SAlan Cox m_ret = NULL; 766c68c3537SAlan Cox index = VM_RESERV_INDEX(object, pindex); 767c68c3537SAlan Cox do { 768c68c3537SAlan Cox rv = vm_reserv_from_page(m); 769c68c3537SAlan Cox KASSERT(rv->pages == m, 770c68c3537SAlan Cox ("vm_reserv_alloc_contig: reserv %p's pages is corrupted", 771c68c3537SAlan Cox rv)); 7725c930c89SJeff Roberson vm_reserv_lock(rv); 773e2068d0bSJeff Roberson vm_reserv_insert(rv, object, first); 774c68c3537SAlan Cox n = ulmin(VM_LEVEL_0_NPAGES - index, npages); 775c68c3537SAlan Cox for (i = 0; i < n; i++) 776ec179322SAlan Cox vm_reserv_populate(rv, index + i); 777c68c3537SAlan Cox npages -= n; 778c68c3537SAlan Cox if (m_ret == NULL) { 779c68c3537SAlan Cox m_ret = &rv->pages[index]; 780c68c3537SAlan Cox index = 0; 781c68c3537SAlan Cox } 7825c930c89SJeff Roberson vm_reserv_unlock(rv); 783c68c3537SAlan Cox m += VM_LEVEL_0_NPAGES; 784c68c3537SAlan Cox first += VM_LEVEL_0_NPAGES; 785c68c3537SAlan Cox allocpages -= VM_LEVEL_0_NPAGES; 78664f096eeSAlan Cox } while (allocpages >= VM_LEVEL_0_NPAGES); 787c68c3537SAlan Cox return (m_ret); 788e2068d0bSJeff Roberson } 789c68c3537SAlan Cox 790c68c3537SAlan Cox /* 7912d5039dbSAlan Cox * Allocate a physical page from an existing or newly created reservation. 792e2068d0bSJeff Roberson * 793e2068d0bSJeff Roberson * The page "mpred" must immediately precede the offset "pindex" within the 794e2068d0bSJeff Roberson * specified object. 795e2068d0bSJeff Roberson * 796e2068d0bSJeff Roberson * The object must be locked. 797c68c3537SAlan Cox */ 798e2068d0bSJeff Roberson vm_page_t 7992d5039dbSAlan Cox vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex, int domain, 8002d5039dbSAlan Cox int req, vm_page_t mpred) 801e2068d0bSJeff Roberson { 802e2068d0bSJeff Roberson struct vm_domain *vmd; 803e2068d0bSJeff Roberson vm_page_t m, msucc; 8042d5039dbSAlan Cox vm_pindex_t first, leftcap, rightcap; 805e2068d0bSJeff Roberson vm_reserv_t rv; 80630fbfddaSJeff Roberson int index; 807e2068d0bSJeff Roberson 808e2068d0bSJeff Roberson VM_OBJECT_ASSERT_WLOCKED(object); 809e2068d0bSJeff Roberson 810e2068d0bSJeff Roberson /* 8112d5039dbSAlan Cox * Is a reservation fundamentally impossible? 812e2068d0bSJeff Roberson */ 813e2068d0bSJeff Roberson if (pindex < VM_RESERV_INDEX(object, pindex) || 8142d5039dbSAlan Cox pindex >= object->size) 815e2068d0bSJeff Roberson return (NULL); 816e2068d0bSJeff Roberson 817e2068d0bSJeff Roberson /* 818e2068d0bSJeff Roberson * Look for an existing reservation. 819e2068d0bSJeff Roberson */ 820e2068d0bSJeff Roberson rv = vm_reserv_from_object(object, pindex, mpred, &msucc); 8212d5039dbSAlan Cox if (rv != NULL) { 822e2068d0bSJeff Roberson KASSERT(object != kernel_object || rv->domain == domain, 8232d5039dbSAlan Cox ("vm_reserv_alloc_page: domain mismatch")); 824e2068d0bSJeff Roberson domain = rv->domain; 825e2068d0bSJeff Roberson vmd = VM_DOMAIN(domain); 826c68c3537SAlan Cox index = VM_RESERV_INDEX(object, pindex); 827c68c3537SAlan Cox m = &rv->pages[index]; 8285c930c89SJeff Roberson vm_reserv_lock(rv); 829e2068d0bSJeff Roberson /* Handle reclaim race. */ 8305c930c89SJeff Roberson if (rv->object != object || 831c68c3537SAlan Cox /* Handle vm_page_rename(m, new_object, ...). */ 8325c930c89SJeff Roberson popmap_is_set(rv->popmap, index)) { 833e2068d0bSJeff Roberson m = NULL; 8345c930c89SJeff Roberson goto out; 83530fbfddaSJeff Roberson } 8365c930c89SJeff Roberson if (vm_domain_allocate(vmd, req, 1) == 0) 8375c930c89SJeff Roberson m = NULL; 8385c930c89SJeff Roberson else 8395c930c89SJeff Roberson vm_reserv_populate(rv, index); 8405c930c89SJeff Roberson out: 8415c930c89SJeff Roberson vm_reserv_unlock(rv); 842c68c3537SAlan Cox return (m); 843c68c3537SAlan Cox } 844c68c3537SAlan Cox 845c68c3537SAlan Cox /* 846c68c3537SAlan Cox * Could a reservation fit between the first index to the left that 847c68c3537SAlan Cox * can be used and the first index to the right that cannot be used? 848e2068d0bSJeff Roberson * 849e2068d0bSJeff Roberson * We must synchronize with the reserv object lock to protect the 850e2068d0bSJeff Roberson * pindex/object of the resulting reservations against rename while 851e2068d0bSJeff Roberson * we are inspecting. 852f8a47341SAlan Cox */ 853c68c3537SAlan Cox first = pindex - VM_RESERV_INDEX(object, pindex); 854e2068d0bSJeff Roberson vm_reserv_object_lock(object); 855c68c3537SAlan Cox if (mpred != NULL) { 856c68c3537SAlan Cox if ((rv = vm_reserv_from_page(mpred))->object != object) 857f8a47341SAlan Cox leftcap = mpred->pindex + 1; 858f8a47341SAlan Cox else 859f8a47341SAlan Cox leftcap = rv->pindex + VM_LEVEL_0_NPAGES; 860e2068d0bSJeff Roberson if (leftcap > first) { 861e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 862c68c3537SAlan Cox return (NULL); 863c68c3537SAlan Cox } 864e2068d0bSJeff Roberson } 865c68c3537SAlan Cox if (msucc != NULL) { 866c68c3537SAlan Cox if ((rv = vm_reserv_from_page(msucc))->object != object) 867f8a47341SAlan Cox rightcap = msucc->pindex; 868f8a47341SAlan Cox else 869f8a47341SAlan Cox rightcap = rv->pindex; 870e2068d0bSJeff Roberson if (first + VM_LEVEL_0_NPAGES > rightcap) { 871e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 872f8a47341SAlan Cox return (NULL); 873c68c3537SAlan Cox } 874e2068d0bSJeff Roberson } 875e2068d0bSJeff Roberson vm_reserv_object_unlock(object); 876f8a47341SAlan Cox 877f8a47341SAlan Cox /* 878c68c3537SAlan Cox * Would a new reservation extend past the end of the object? 879f8a47341SAlan Cox */ 880c68c3537SAlan Cox if (first + VM_LEVEL_0_NPAGES > object->size) { 881f8a47341SAlan Cox /* 882f8a47341SAlan Cox * Don't allocate a new reservation if the object is a vnode or 883f8a47341SAlan Cox * backed by another object that is a vnode. 884f8a47341SAlan Cox */ 885f8a47341SAlan Cox if (object->type == OBJT_VNODE || 886f8a47341SAlan Cox (object->backing_object != NULL && 887f8a47341SAlan Cox object->backing_object->type == OBJT_VNODE)) 888f8a47341SAlan Cox return (NULL); 889f8a47341SAlan Cox /* Speculate that the object may grow. */ 890f8a47341SAlan Cox } 891f8a47341SAlan Cox 892f8a47341SAlan Cox /* 893c68c3537SAlan Cox * Allocate and populate the new reservation. 894f8a47341SAlan Cox */ 8955c930c89SJeff Roberson m = NULL; 8965c930c89SJeff Roberson vmd = VM_DOMAIN(domain); 8975c930c89SJeff Roberson if (vm_domain_allocate(vmd, req, 1)) { 8985c930c89SJeff Roberson vm_domain_free_lock(vmd); 8995c930c89SJeff Roberson m = vm_phys_alloc_pages(domain, VM_FREEPOOL_DEFAULT, 9005c930c89SJeff Roberson VM_LEVEL_0_ORDER); 9015c930c89SJeff Roberson vm_domain_free_unlock(vmd); 9025c930c89SJeff Roberson if (m == NULL) { 9035c930c89SJeff Roberson vm_domain_freecnt_inc(vmd, 1); 9045c930c89SJeff Roberson return (NULL); 9055c930c89SJeff Roberson } 9065c930c89SJeff Roberson } else 907c68c3537SAlan Cox return (NULL); 908f8a47341SAlan Cox rv = vm_reserv_from_page(m); 9095c930c89SJeff Roberson vm_reserv_lock(rv); 910f8a47341SAlan Cox KASSERT(rv->pages == m, 911c68c3537SAlan Cox ("vm_reserv_alloc_page: reserv %p's pages is corrupted", rv)); 912e2068d0bSJeff Roberson vm_reserv_insert(rv, object, first); 913ec179322SAlan Cox index = VM_RESERV_INDEX(object, pindex); 914ec179322SAlan Cox vm_reserv_populate(rv, index); 9155c930c89SJeff Roberson vm_reserv_unlock(rv); 9165c930c89SJeff Roberson 917ec179322SAlan Cox return (&rv->pages[index]); 918f8a47341SAlan Cox } 919f8a47341SAlan Cox 920f8a47341SAlan Cox /* 921ada27a3bSKonstantin Belousov * Breaks the given reservation. All free pages in the reservation 922ada27a3bSKonstantin Belousov * are returned to the physical memory allocator. The reservation's 923ada27a3bSKonstantin Belousov * population count and map are reset to their initial state. 924ec179322SAlan Cox * 9253453bca8SAlan Cox * The given reservation must not be in the partially populated reservation 926ec179322SAlan Cox * queue. The free page queue lock must be held. 927ec179322SAlan Cox */ 928ec179322SAlan Cox static void 929ada27a3bSKonstantin Belousov vm_reserv_break(vm_reserv_t rv) 930ec179322SAlan Cox { 931e67a5068SDoug Moore u_long changes; 932e67a5068SDoug Moore int bitpos, hi, i, lo; 933ec179322SAlan Cox 9345c930c89SJeff Roberson vm_reserv_assert_locked(rv); 9355c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 9365c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 937e2068d0bSJeff Roberson vm_reserv_remove(rv); 938c4be9169SKonstantin Belousov rv->pages->psind = 0; 939e67a5068SDoug Moore hi = lo = -1; 940e67a5068SDoug Moore for (i = 0; i <= NPOPMAP; i++) { 941e67a5068SDoug Moore /* 942e67a5068SDoug Moore * "changes" is a bitmask that marks where a new sequence of 943e67a5068SDoug Moore * 0s or 1s begins in popmap[i], with last bit in popmap[i-1] 944e67a5068SDoug Moore * considered to be 1 if and only if lo == hi. The bits of 945e67a5068SDoug Moore * popmap[-1] and popmap[NPOPMAP] are considered all 1s. 946e67a5068SDoug Moore */ 947ec179322SAlan Cox if (i == NPOPMAP) 948e67a5068SDoug Moore changes = lo != hi; 949e67a5068SDoug Moore else { 950e67a5068SDoug Moore changes = rv->popmap[i]; 951e67a5068SDoug Moore changes ^= (changes << 1) | (lo == hi); 952e67a5068SDoug Moore rv->popmap[i] = 0; 953ec179322SAlan Cox } 954e67a5068SDoug Moore while (changes != 0) { 955e67a5068SDoug Moore /* 956e67a5068SDoug Moore * If the next change marked begins a run of 0s, set 957e67a5068SDoug Moore * lo to mark that position. Otherwise set hi and 958e67a5068SDoug Moore * free pages from lo up to hi. 959e67a5068SDoug Moore */ 960e67a5068SDoug Moore bitpos = ffsl(changes) - 1; 961e67a5068SDoug Moore changes ^= 1UL << bitpos; 962e67a5068SDoug Moore if (lo == hi) 963e67a5068SDoug Moore lo = NBPOPMAP * i + bitpos; 964e67a5068SDoug Moore else { 965e67a5068SDoug Moore hi = NBPOPMAP * i + bitpos; 9665c930c89SJeff Roberson vm_domain_free_lock(VM_DOMAIN(rv->domain)); 967b8590daeSDoug Moore vm_phys_enqueue_contig(&rv->pages[lo], hi - lo); 9685c930c89SJeff Roberson vm_domain_free_unlock(VM_DOMAIN(rv->domain)); 969e67a5068SDoug Moore lo = hi; 970e67a5068SDoug Moore } 971e67a5068SDoug Moore } 972e67a5068SDoug Moore } 973e67a5068SDoug Moore rv->popcnt = 0; 9745c930c89SJeff Roberson counter_u64_add(vm_reserv_broken, 1); 975ec179322SAlan Cox } 976ec179322SAlan Cox 977ec179322SAlan Cox /* 978f8a47341SAlan Cox * Breaks all reservations belonging to the given object. 979f8a47341SAlan Cox */ 980f8a47341SAlan Cox void 981f8a47341SAlan Cox vm_reserv_break_all(vm_object_t object) 982f8a47341SAlan Cox { 983f8a47341SAlan Cox vm_reserv_t rv; 984f8a47341SAlan Cox 985e2068d0bSJeff Roberson /* 986e2068d0bSJeff Roberson * This access of object->rvq is unsynchronized so that the 987e2068d0bSJeff Roberson * object rvq lock can nest after the domain_free lock. We 988e2068d0bSJeff Roberson * must check for races in the results. However, the object 989e2068d0bSJeff Roberson * lock prevents new additions, so we are guaranteed that when 990e2068d0bSJeff Roberson * it returns NULL the object is properly empty. 991e2068d0bSJeff Roberson */ 992f8a47341SAlan Cox while ((rv = LIST_FIRST(&object->rvq)) != NULL) { 9935c930c89SJeff Roberson vm_reserv_lock(rv); 994e2068d0bSJeff Roberson /* Reclaim race. */ 9955c930c89SJeff Roberson if (rv->object != object) { 9965c930c89SJeff Roberson vm_reserv_unlock(rv); 997e2068d0bSJeff Roberson continue; 9985c930c89SJeff Roberson } 9995c930c89SJeff Roberson vm_reserv_domain_lock(rv->domain); 1000f8a47341SAlan Cox if (rv->inpartpopq) { 1001ef435ae7SJeff Roberson TAILQ_REMOVE(&vm_rvq_partpop[rv->domain], rv, partpopq); 1002f8a47341SAlan Cox rv->inpartpopq = FALSE; 1003f8a47341SAlan Cox } 10045c930c89SJeff Roberson vm_reserv_domain_unlock(rv->domain); 1005ada27a3bSKonstantin Belousov vm_reserv_break(rv); 10065c930c89SJeff Roberson vm_reserv_unlock(rv); 1007f8a47341SAlan Cox } 1008f8a47341SAlan Cox } 1009f8a47341SAlan Cox 1010f8a47341SAlan Cox /* 1011f8a47341SAlan Cox * Frees the given page if it belongs to a reservation. Returns TRUE if the 1012f8a47341SAlan Cox * page is freed and FALSE otherwise. 1013f8a47341SAlan Cox * 1014f8a47341SAlan Cox * The free page queue lock must be held. 1015f8a47341SAlan Cox */ 1016f8a47341SAlan Cox boolean_t 1017f8a47341SAlan Cox vm_reserv_free_page(vm_page_t m) 1018f8a47341SAlan Cox { 1019f8a47341SAlan Cox vm_reserv_t rv; 10205c930c89SJeff Roberson boolean_t ret; 1021f8a47341SAlan Cox 1022f8a47341SAlan Cox rv = vm_reserv_from_page(m); 1023908e3da1SAlan Cox if (rv->object == NULL) 1024908e3da1SAlan Cox return (FALSE); 10255c930c89SJeff Roberson vm_reserv_lock(rv); 10265c930c89SJeff Roberson /* Re-validate after lock. */ 10275c930c89SJeff Roberson if (rv->object != NULL) { 1028ec179322SAlan Cox vm_reserv_depopulate(rv, m - rv->pages); 10295c930c89SJeff Roberson ret = TRUE; 10305c930c89SJeff Roberson } else 10315c930c89SJeff Roberson ret = FALSE; 10325c930c89SJeff Roberson vm_reserv_unlock(rv); 10335c930c89SJeff Roberson 10345c930c89SJeff Roberson return (ret); 1035f8a47341SAlan Cox } 1036f8a47341SAlan Cox 1037f8a47341SAlan Cox /* 1038f8a47341SAlan Cox * Initializes the reservation management system. Specifically, initializes 1039f8a47341SAlan Cox * the reservation array. 1040f8a47341SAlan Cox * 1041f8a47341SAlan Cox * Requires that vm_page_array and first_page are initialized! 1042f8a47341SAlan Cox */ 1043f8a47341SAlan Cox void 1044f8a47341SAlan Cox vm_reserv_init(void) 1045f8a47341SAlan Cox { 1046f8a47341SAlan Cox vm_paddr_t paddr; 104709e5f3c4SAlan Cox struct vm_phys_seg *seg; 10485c930c89SJeff Roberson struct vm_reserv *rv; 1049ef435ae7SJeff Roberson int i, segind; 1050f8a47341SAlan Cox 1051f8a47341SAlan Cox /* 1052f8a47341SAlan Cox * Initialize the reservation array. Specifically, initialize the 1053f8a47341SAlan Cox * "pages" field for every element that has an underlying superpage. 1054f8a47341SAlan Cox */ 105509e5f3c4SAlan Cox for (segind = 0; segind < vm_phys_nsegs; segind++) { 105609e5f3c4SAlan Cox seg = &vm_phys_segs[segind]; 105709e5f3c4SAlan Cox paddr = roundup2(seg->start, VM_LEVEL_0_SIZE); 105809e5f3c4SAlan Cox while (paddr + VM_LEVEL_0_SIZE <= seg->end) { 10595c930c89SJeff Roberson rv = &vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT]; 10605c930c89SJeff Roberson rv->pages = PHYS_TO_VM_PAGE(paddr); 10615c930c89SJeff Roberson rv->domain = seg->domain; 10625c930c89SJeff Roberson mtx_init(&rv->lock, "vm reserv", NULL, MTX_DEF); 1063f8a47341SAlan Cox paddr += VM_LEVEL_0_SIZE; 1064f8a47341SAlan Cox } 1065f8a47341SAlan Cox } 10665c930c89SJeff Roberson for (i = 0; i < MAXMEMDOM; i++) { 10675c930c89SJeff Roberson mtx_init(&vm_reserv_domain_locks[i], "VM reserv domain", NULL, 10685c930c89SJeff Roberson MTX_DEF); 1069ef435ae7SJeff Roberson TAILQ_INIT(&vm_rvq_partpop[i]); 1070f8a47341SAlan Cox } 1071f8a47341SAlan Cox 10725c930c89SJeff Roberson for (i = 0; i < VM_RESERV_OBJ_LOCK_COUNT; i++) 10735c930c89SJeff Roberson mtx_init(&vm_reserv_object_mtx[i], "resv obj lock", NULL, 10745c930c89SJeff Roberson MTX_DEF); 10755c930c89SJeff Roberson } 10765c930c89SJeff Roberson 1077f8a47341SAlan Cox /* 1078c869e672SAlan Cox * Returns true if the given page belongs to a reservation and that page is 1079c869e672SAlan Cox * free. Otherwise, returns false. 1080c869e672SAlan Cox */ 1081c869e672SAlan Cox bool 1082c869e672SAlan Cox vm_reserv_is_page_free(vm_page_t m) 1083c869e672SAlan Cox { 1084c869e672SAlan Cox vm_reserv_t rv; 1085c869e672SAlan Cox 1086c869e672SAlan Cox rv = vm_reserv_from_page(m); 1087c869e672SAlan Cox if (rv->object == NULL) 1088c869e672SAlan Cox return (false); 1089c869e672SAlan Cox return (popmap_is_clear(rv->popmap, m - rv->pages)); 1090c869e672SAlan Cox } 1091c869e672SAlan Cox 1092c869e672SAlan Cox /* 1093c869e672SAlan Cox * If the given page belongs to a reservation, returns the level of that 1094c869e672SAlan Cox * reservation. Otherwise, returns -1. 1095c869e672SAlan Cox */ 1096c869e672SAlan Cox int 1097c869e672SAlan Cox vm_reserv_level(vm_page_t m) 1098c869e672SAlan Cox { 1099c869e672SAlan Cox vm_reserv_t rv; 1100c869e672SAlan Cox 1101c869e672SAlan Cox rv = vm_reserv_from_page(m); 1102c869e672SAlan Cox return (rv->object != NULL ? 0 : -1); 1103c869e672SAlan Cox } 1104c869e672SAlan Cox 1105c869e672SAlan Cox /* 11063453bca8SAlan Cox * Returns a reservation level if the given page belongs to a fully populated 1107f8a47341SAlan Cox * reservation and -1 otherwise. 1108f8a47341SAlan Cox */ 1109f8a47341SAlan Cox int 1110f8a47341SAlan Cox vm_reserv_level_iffullpop(vm_page_t m) 1111f8a47341SAlan Cox { 1112f8a47341SAlan Cox vm_reserv_t rv; 1113f8a47341SAlan Cox 1114f8a47341SAlan Cox rv = vm_reserv_from_page(m); 1115f8a47341SAlan Cox return (rv->popcnt == VM_LEVEL_0_NPAGES ? 0 : -1); 1116f8a47341SAlan Cox } 1117f8a47341SAlan Cox 1118f8a47341SAlan Cox /* 11193453bca8SAlan Cox * Breaks the given partially populated reservation, releasing its free pages 11203453bca8SAlan Cox * to the physical memory allocator. 1121f8a47341SAlan Cox * 1122f8a47341SAlan Cox * The free page queue lock must be held. 1123f8a47341SAlan Cox */ 112444aab2c3SAlan Cox static void 112544aab2c3SAlan Cox vm_reserv_reclaim(vm_reserv_t rv) 1126f8a47341SAlan Cox { 1127f8a47341SAlan Cox 11285c930c89SJeff Roberson vm_reserv_assert_locked(rv); 11295c930c89SJeff Roberson CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d", 11305c930c89SJeff Roberson __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq); 11315c930c89SJeff Roberson vm_reserv_domain_lock(rv->domain); 1132f8a47341SAlan Cox KASSERT(rv->inpartpopq, 1133ec179322SAlan Cox ("vm_reserv_reclaim: reserv %p's inpartpopq is FALSE", rv)); 11342d3f4181SJeff Roberson KASSERT(rv->domain < vm_ndomains, 1135ef435ae7SJeff Roberson ("vm_reserv_reclaim: reserv %p's domain is corrupted %d", 1136ef435ae7SJeff Roberson rv, rv->domain)); 1137ef435ae7SJeff Roberson TAILQ_REMOVE(&vm_rvq_partpop[rv->domain], rv, partpopq); 1138f8a47341SAlan Cox rv->inpartpopq = FALSE; 11395c930c89SJeff Roberson vm_reserv_domain_unlock(rv->domain); 1140ada27a3bSKonstantin Belousov vm_reserv_break(rv); 11415c930c89SJeff Roberson counter_u64_add(vm_reserv_reclaimed, 1); 114244aab2c3SAlan Cox } 114344aab2c3SAlan Cox 114444aab2c3SAlan Cox /* 11453453bca8SAlan Cox * Breaks the reservation at the head of the partially populated reservation 11463453bca8SAlan Cox * queue, releasing its free pages to the physical memory allocator. Returns 11473453bca8SAlan Cox * TRUE if a reservation is broken and FALSE otherwise. 114844aab2c3SAlan Cox * 114944aab2c3SAlan Cox * The free page queue lock must be held. 115044aab2c3SAlan Cox */ 115144aab2c3SAlan Cox boolean_t 1152ef435ae7SJeff Roberson vm_reserv_reclaim_inactive(int domain) 115344aab2c3SAlan Cox { 115444aab2c3SAlan Cox vm_reserv_t rv; 115544aab2c3SAlan Cox 11565c930c89SJeff Roberson while ((rv = TAILQ_FIRST(&vm_rvq_partpop[domain])) != NULL) { 11575c930c89SJeff Roberson vm_reserv_lock(rv); 11585c930c89SJeff Roberson if (rv != TAILQ_FIRST(&vm_rvq_partpop[domain])) { 11595c930c89SJeff Roberson vm_reserv_unlock(rv); 11605c930c89SJeff Roberson continue; 11615c930c89SJeff Roberson } 116244aab2c3SAlan Cox vm_reserv_reclaim(rv); 11635c930c89SJeff Roberson vm_reserv_unlock(rv); 1164f8a47341SAlan Cox return (TRUE); 1165f8a47341SAlan Cox } 1166f8a47341SAlan Cox return (FALSE); 1167f8a47341SAlan Cox } 1168f8a47341SAlan Cox 1169f8a47341SAlan Cox /* 1170*f96e8a0bSDoug Moore * Determine whether this reservation has free pages that satisfy the given 1171*f96e8a0bSDoug Moore * request for contiguous physical memory. Start searching from the lower 1172*f96e8a0bSDoug Moore * bound, defined by low_index. 1173*f96e8a0bSDoug Moore * 1174*f96e8a0bSDoug Moore * The free page queue lock must be held. 1175*f96e8a0bSDoug Moore */ 1176*f96e8a0bSDoug Moore static bool 1177*f96e8a0bSDoug Moore vm_reserv_test_contig(vm_reserv_t rv, u_long npages, vm_paddr_t low, 1178*f96e8a0bSDoug Moore vm_paddr_t high, u_long alignment, vm_paddr_t boundary) 1179*f96e8a0bSDoug Moore { 1180*f96e8a0bSDoug Moore vm_paddr_t pa, size; 1181*f96e8a0bSDoug Moore u_long changes; 1182*f96e8a0bSDoug Moore int bitpos, bits_left, i, hi, lo, n; 1183*f96e8a0bSDoug Moore 1184*f96e8a0bSDoug Moore vm_reserv_assert_locked(rv); 1185*f96e8a0bSDoug Moore size = npages << PAGE_SHIFT; 1186*f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[0]); 1187*f96e8a0bSDoug Moore lo = (pa < low) ? 1188*f96e8a0bSDoug Moore ((low + PAGE_MASK - pa) >> PAGE_SHIFT) : 0; 1189*f96e8a0bSDoug Moore i = lo / NBPOPMAP; 1190*f96e8a0bSDoug Moore changes = rv->popmap[i] | ((1UL << (lo % NBPOPMAP)) - 1); 1191*f96e8a0bSDoug Moore hi = (pa + VM_LEVEL_0_SIZE > high) ? 1192*f96e8a0bSDoug Moore ((high + PAGE_MASK - pa) >> PAGE_SHIFT) : VM_LEVEL_0_NPAGES; 1193*f96e8a0bSDoug Moore n = hi / NBPOPMAP; 1194*f96e8a0bSDoug Moore bits_left = hi % NBPOPMAP; 1195*f96e8a0bSDoug Moore hi = lo = -1; 1196*f96e8a0bSDoug Moore for (;;) { 1197*f96e8a0bSDoug Moore /* 1198*f96e8a0bSDoug Moore * "changes" is a bitmask that marks where a new sequence of 1199*f96e8a0bSDoug Moore * 0s or 1s begins in popmap[i], with last bit in popmap[i-1] 1200*f96e8a0bSDoug Moore * considered to be 1 if and only if lo == hi. The bits of 1201*f96e8a0bSDoug Moore * popmap[-1] and popmap[NPOPMAP] are considered all 1s. 1202*f96e8a0bSDoug Moore */ 1203*f96e8a0bSDoug Moore changes ^= (changes << 1) | (lo == hi); 1204*f96e8a0bSDoug Moore while (changes != 0) { 1205*f96e8a0bSDoug Moore /* 1206*f96e8a0bSDoug Moore * If the next change marked begins a run of 0s, set 1207*f96e8a0bSDoug Moore * lo to mark that position. Otherwise set hi and 1208*f96e8a0bSDoug Moore * look for a satisfactory first page from lo up to hi. 1209*f96e8a0bSDoug Moore */ 1210*f96e8a0bSDoug Moore bitpos = ffsl(changes) - 1; 1211*f96e8a0bSDoug Moore changes ^= 1UL << bitpos; 1212*f96e8a0bSDoug Moore if (lo == hi) { 1213*f96e8a0bSDoug Moore lo = NBPOPMAP * i + bitpos; 1214*f96e8a0bSDoug Moore continue; 1215*f96e8a0bSDoug Moore } 1216*f96e8a0bSDoug Moore hi = NBPOPMAP * i + bitpos; 1217*f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); 1218*f96e8a0bSDoug Moore if ((pa & (alignment - 1)) != 0) { 1219*f96e8a0bSDoug Moore /* Skip to next aligned page. */ 1220*f96e8a0bSDoug Moore lo += (((pa - 1) | (alignment - 1)) + 1) >> 1221*f96e8a0bSDoug Moore PAGE_SHIFT; 1222*f96e8a0bSDoug Moore if (lo >= VM_LEVEL_0_NPAGES) 1223*f96e8a0bSDoug Moore return (false); 1224*f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); 1225*f96e8a0bSDoug Moore } 1226*f96e8a0bSDoug Moore if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) { 1227*f96e8a0bSDoug Moore /* Skip to next boundary-matching page. */ 1228*f96e8a0bSDoug Moore lo += (((pa - 1) | (boundary - 1)) + 1) >> 1229*f96e8a0bSDoug Moore PAGE_SHIFT; 1230*f96e8a0bSDoug Moore if (lo >= VM_LEVEL_0_NPAGES) 1231*f96e8a0bSDoug Moore return (false); 1232*f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); 1233*f96e8a0bSDoug Moore } 1234*f96e8a0bSDoug Moore if (lo * PAGE_SIZE + size <= hi * PAGE_SIZE) 1235*f96e8a0bSDoug Moore return (true); 1236*f96e8a0bSDoug Moore lo = hi; 1237*f96e8a0bSDoug Moore } 1238*f96e8a0bSDoug Moore if (++i < n) 1239*f96e8a0bSDoug Moore changes = rv->popmap[i]; 1240*f96e8a0bSDoug Moore else if (i == n) 1241*f96e8a0bSDoug Moore changes = bits_left == 0 ? -1UL : 1242*f96e8a0bSDoug Moore (rv->popmap[n] | (-1UL << bits_left)); 1243*f96e8a0bSDoug Moore else 1244*f96e8a0bSDoug Moore return (false); 1245*f96e8a0bSDoug Moore } 1246*f96e8a0bSDoug Moore } 1247*f96e8a0bSDoug Moore 1248*f96e8a0bSDoug Moore /* 12493453bca8SAlan Cox * Searches the partially populated reservation queue for the least recently 12503453bca8SAlan Cox * changed reservation with free pages that satisfy the given request for 12513453bca8SAlan Cox * contiguous physical memory. If a satisfactory reservation is found, it is 1252*f96e8a0bSDoug Moore * broken. Returns true if a reservation is broken and false otherwise. 125344aab2c3SAlan Cox * 125444aab2c3SAlan Cox * The free page queue lock must be held. 125544aab2c3SAlan Cox */ 125644aab2c3SAlan Cox boolean_t 1257ef435ae7SJeff Roberson vm_reserv_reclaim_contig(int domain, u_long npages, vm_paddr_t low, 1258ef435ae7SJeff Roberson vm_paddr_t high, u_long alignment, vm_paddr_t boundary) 125944aab2c3SAlan Cox { 1260ec179322SAlan Cox vm_paddr_t pa, size; 12615c930c89SJeff Roberson vm_reserv_t rv, rvn; 126244aab2c3SAlan Cox 1263c68c3537SAlan Cox if (npages > VM_LEVEL_0_NPAGES - 1) 1264*f96e8a0bSDoug Moore return (false); 1265c68c3537SAlan Cox size = npages << PAGE_SHIFT; 12665c930c89SJeff Roberson vm_reserv_domain_lock(domain); 12675c930c89SJeff Roberson again: 12685c930c89SJeff Roberson for (rv = TAILQ_FIRST(&vm_rvq_partpop[domain]); rv != NULL; rv = rvn) { 12695c930c89SJeff Roberson rvn = TAILQ_NEXT(rv, partpopq); 1270*f96e8a0bSDoug Moore pa = VM_PAGE_TO_PHYS(&rv->pages[0]); 1271*f96e8a0bSDoug Moore if (pa + VM_LEVEL_0_SIZE - size < low) { 1272ec179322SAlan Cox /* This entire reservation is too low; go to next. */ 127344aab2c3SAlan Cox continue; 127444aab2c3SAlan Cox } 127544aab2c3SAlan Cox if (pa + size > high) { 1276ec179322SAlan Cox /* This entire reservation is too high; go to next. */ 1277ec179322SAlan Cox continue; 127885f2a0c9SMax Laier } 12795c930c89SJeff Roberson if (vm_reserv_trylock(rv) == 0) { 12805c930c89SJeff Roberson vm_reserv_domain_unlock(domain); 12815c930c89SJeff Roberson vm_reserv_lock(rv); 12825c930c89SJeff Roberson if (!rv->inpartpopq) { 12835c930c89SJeff Roberson vm_reserv_domain_lock(domain); 12845c930c89SJeff Roberson if (!rvn->inpartpopq) 12855c930c89SJeff Roberson goto again; 12865c930c89SJeff Roberson continue; 12875c930c89SJeff Roberson } 12885c930c89SJeff Roberson } else 12895c930c89SJeff Roberson vm_reserv_domain_unlock(domain); 1290*f96e8a0bSDoug Moore if (vm_reserv_test_contig(rv, npages, low, high, 1291*f96e8a0bSDoug Moore alignment, boundary)) { 129244aab2c3SAlan Cox vm_reserv_reclaim(rv); 12935c930c89SJeff Roberson vm_reserv_unlock(rv); 1294*f96e8a0bSDoug Moore return (true); 129544aab2c3SAlan Cox } 12965c930c89SJeff Roberson vm_reserv_unlock(rv); 12975c930c89SJeff Roberson vm_reserv_domain_lock(domain); 12985c930c89SJeff Roberson if (rvn != NULL && !rvn->inpartpopq) 12995c930c89SJeff Roberson goto again; 130044aab2c3SAlan Cox } 13015c930c89SJeff Roberson vm_reserv_domain_unlock(domain); 1302*f96e8a0bSDoug Moore return (false); 130344aab2c3SAlan Cox } 130444aab2c3SAlan Cox 130544aab2c3SAlan Cox /* 1306f8a47341SAlan Cox * Transfers the reservation underlying the given page to a new object. 1307f8a47341SAlan Cox * 1308f8a47341SAlan Cox * The object must be locked. 1309f8a47341SAlan Cox */ 1310f8a47341SAlan Cox void 1311f8a47341SAlan Cox vm_reserv_rename(vm_page_t m, vm_object_t new_object, vm_object_t old_object, 1312f8a47341SAlan Cox vm_pindex_t old_object_offset) 1313f8a47341SAlan Cox { 1314f8a47341SAlan Cox vm_reserv_t rv; 1315f8a47341SAlan Cox 131689f6b863SAttilio Rao VM_OBJECT_ASSERT_WLOCKED(new_object); 1317f8a47341SAlan Cox rv = vm_reserv_from_page(m); 1318f8a47341SAlan Cox if (rv->object == old_object) { 13195c930c89SJeff Roberson vm_reserv_lock(rv); 13205c930c89SJeff Roberson CTR6(KTR_VM, 13215c930c89SJeff Roberson "%s: rv %p object %p new %p popcnt %d inpartpop %d", 13225c930c89SJeff Roberson __FUNCTION__, rv, rv->object, new_object, rv->popcnt, 13235c930c89SJeff Roberson rv->inpartpopq); 1324f8a47341SAlan Cox if (rv->object == old_object) { 1325e2068d0bSJeff Roberson vm_reserv_object_lock(old_object); 1326e2068d0bSJeff Roberson rv->object = NULL; 1327f8a47341SAlan Cox LIST_REMOVE(rv, objq); 1328e2068d0bSJeff Roberson vm_reserv_object_unlock(old_object); 1329e2068d0bSJeff Roberson vm_reserv_object_lock(new_object); 1330f8a47341SAlan Cox rv->object = new_object; 1331f8a47341SAlan Cox rv->pindex -= old_object_offset; 1332e2068d0bSJeff Roberson LIST_INSERT_HEAD(&new_object->rvq, rv, objq); 1333e2068d0bSJeff Roberson vm_reserv_object_unlock(new_object); 1334f8a47341SAlan Cox } 13355c930c89SJeff Roberson vm_reserv_unlock(rv); 1336f8a47341SAlan Cox } 1337f8a47341SAlan Cox } 1338f8a47341SAlan Cox 1339f8a47341SAlan Cox /* 1340c869e672SAlan Cox * Returns the size (in bytes) of a reservation of the specified level. 1341c869e672SAlan Cox */ 1342c869e672SAlan Cox int 1343c869e672SAlan Cox vm_reserv_size(int level) 1344c869e672SAlan Cox { 1345c869e672SAlan Cox 1346c869e672SAlan Cox switch (level) { 1347c869e672SAlan Cox case 0: 1348c869e672SAlan Cox return (VM_LEVEL_0_SIZE); 1349c869e672SAlan Cox case -1: 1350c869e672SAlan Cox return (PAGE_SIZE); 1351c869e672SAlan Cox default: 1352c869e672SAlan Cox return (0); 1353c869e672SAlan Cox } 1354c869e672SAlan Cox } 1355c869e672SAlan Cox 1356c869e672SAlan Cox /* 1357f8a47341SAlan Cox * Allocates the virtual and physical memory required by the reservation 1358f8a47341SAlan Cox * management system's data structures, in particular, the reservation array. 1359f8a47341SAlan Cox */ 1360f8a47341SAlan Cox vm_paddr_t 1361f8a47341SAlan Cox vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end, vm_paddr_t high_water) 1362f8a47341SAlan Cox { 1363f8a47341SAlan Cox vm_paddr_t new_end; 1364f8a47341SAlan Cox size_t size; 1365f8a47341SAlan Cox 1366f8a47341SAlan Cox /* 1367f8a47341SAlan Cox * Calculate the size (in bytes) of the reservation array. Round up 1368f8a47341SAlan Cox * from "high_water" because every small page is mapped to an element 1369f8a47341SAlan Cox * in the reservation array based on its physical address. Thus, the 1370f8a47341SAlan Cox * number of elements in the reservation array can be greater than the 1371f8a47341SAlan Cox * number of superpages. 1372f8a47341SAlan Cox */ 1373f8a47341SAlan Cox size = howmany(high_water, VM_LEVEL_0_SIZE) * sizeof(struct vm_reserv); 1374f8a47341SAlan Cox 1375f8a47341SAlan Cox /* 1376f8a47341SAlan Cox * Allocate and map the physical memory for the reservation array. The 1377f8a47341SAlan Cox * next available virtual address is returned by reference. 1378f8a47341SAlan Cox */ 1379f8a47341SAlan Cox new_end = end - round_page(size); 1380f8a47341SAlan Cox vm_reserv_array = (void *)(uintptr_t)pmap_map(vaddr, new_end, end, 1381f8a47341SAlan Cox VM_PROT_READ | VM_PROT_WRITE); 1382f8a47341SAlan Cox bzero(vm_reserv_array, size); 1383f8a47341SAlan Cox 1384f8a47341SAlan Cox /* 1385f8a47341SAlan Cox * Return the next available physical address. 1386f8a47341SAlan Cox */ 1387f8a47341SAlan Cox return (new_end); 1388f8a47341SAlan Cox } 1389f8a47341SAlan Cox 13908b5e1472SAlan Cox /* 13915c930c89SJeff Roberson * Initializes the reservation management system. Specifically, initializes 13925c930c89SJeff Roberson * the reservation counters. 13935c930c89SJeff Roberson */ 13945c930c89SJeff Roberson static void 13955c930c89SJeff Roberson vm_reserv_counter_init(void *unused) 13965c930c89SJeff Roberson { 13975c930c89SJeff Roberson 13985c930c89SJeff Roberson vm_reserv_freed = counter_u64_alloc(M_WAITOK); 13995c930c89SJeff Roberson vm_reserv_broken = counter_u64_alloc(M_WAITOK); 14005c930c89SJeff Roberson vm_reserv_reclaimed = counter_u64_alloc(M_WAITOK); 14015c930c89SJeff Roberson } 14025c930c89SJeff Roberson SYSINIT(vm_reserv_counter_init, SI_SUB_CPU, SI_ORDER_ANY, 14035c930c89SJeff Roberson vm_reserv_counter_init, NULL); 14045c930c89SJeff Roberson 14055c930c89SJeff Roberson /* 14068b5e1472SAlan Cox * Returns the superpage containing the given page. 14078b5e1472SAlan Cox */ 14088b5e1472SAlan Cox vm_page_t 14098b5e1472SAlan Cox vm_reserv_to_superpage(vm_page_t m) 14108b5e1472SAlan Cox { 14118b5e1472SAlan Cox vm_reserv_t rv; 14128b5e1472SAlan Cox 14138b5e1472SAlan Cox VM_OBJECT_ASSERT_LOCKED(m->object); 14148b5e1472SAlan Cox rv = vm_reserv_from_page(m); 14155c930c89SJeff Roberson if (rv->object == m->object && rv->popcnt == VM_LEVEL_0_NPAGES) 14165c930c89SJeff Roberson m = rv->pages; 14175c930c89SJeff Roberson else 14185c930c89SJeff Roberson m = NULL; 14195c930c89SJeff Roberson 14205c930c89SJeff Roberson return (m); 14218b5e1472SAlan Cox } 14228b5e1472SAlan Cox 1423f8a47341SAlan Cox #endif /* VM_NRESERVLEVEL > 0 */ 1424