xref: /freebsd/sys/vm/vm_phys.c (revision c415cfc8be1b732a80f1ada6d52091e08eeb9ab5)
111752d88SAlan Cox /*-
24d846d26SWarner Losh  * SPDX-License-Identifier: BSD-2-Clause
3fe267a55SPedro F. Giffuni  *
411752d88SAlan Cox  * Copyright (c) 2002-2006 Rice University
511752d88SAlan Cox  * Copyright (c) 2007 Alan L. Cox <alc@cs.rice.edu>
611752d88SAlan Cox  * All rights reserved.
711752d88SAlan Cox  *
811752d88SAlan Cox  * This software was developed for the FreeBSD Project by Alan L. Cox,
911752d88SAlan Cox  * Olivier Crameri, Peter Druschel, Sitaram Iyer, and Juan Navarro.
1011752d88SAlan Cox  *
1111752d88SAlan Cox  * Redistribution and use in source and binary forms, with or without
1211752d88SAlan Cox  * modification, are permitted provided that the following conditions
1311752d88SAlan Cox  * are met:
1411752d88SAlan Cox  * 1. Redistributions of source code must retain the above copyright
1511752d88SAlan Cox  *    notice, this list of conditions and the following disclaimer.
1611752d88SAlan Cox  * 2. Redistributions in binary form must reproduce the above copyright
1711752d88SAlan Cox  *    notice, this list of conditions and the following disclaimer in the
1811752d88SAlan Cox  *    documentation and/or other materials provided with the distribution.
1911752d88SAlan Cox  *
2011752d88SAlan Cox  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2111752d88SAlan Cox  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2211752d88SAlan Cox  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2311752d88SAlan Cox  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
2411752d88SAlan Cox  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
2511752d88SAlan Cox  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
2611752d88SAlan Cox  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
2711752d88SAlan Cox  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
2811752d88SAlan Cox  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
2911752d88SAlan Cox  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
3011752d88SAlan Cox  * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
3111752d88SAlan Cox  * POSSIBILITY OF SUCH DAMAGE.
3211752d88SAlan Cox  */
3311752d88SAlan Cox 
34fbd80bd0SAlan Cox /*
35fbd80bd0SAlan Cox  *	Physical memory system implementation
36fbd80bd0SAlan Cox  *
37fbd80bd0SAlan Cox  * Any external functions defined by this module are only to be used by the
38fbd80bd0SAlan Cox  * virtual memory system.
39fbd80bd0SAlan Cox  */
40fbd80bd0SAlan Cox 
4111752d88SAlan Cox #include <sys/cdefs.h>
4211752d88SAlan Cox #include "opt_ddb.h"
43174b5f38SJohn Baldwin #include "opt_vm.h"
4411752d88SAlan Cox 
4511752d88SAlan Cox #include <sys/param.h>
4611752d88SAlan Cox #include <sys/systm.h>
47662e7fa8SMark Johnston #include <sys/domainset.h>
4811752d88SAlan Cox #include <sys/lock.h>
4911752d88SAlan Cox #include <sys/kernel.h>
5011752d88SAlan Cox #include <sys/malloc.h>
5111752d88SAlan Cox #include <sys/mutex.h>
527e226537SAttilio Rao #include <sys/proc.h>
5311752d88SAlan Cox #include <sys/queue.h>
5438d6b2dcSRoger Pau Monné #include <sys/rwlock.h>
5511752d88SAlan Cox #include <sys/sbuf.h>
5611752d88SAlan Cox #include <sys/sysctl.h>
5738d6b2dcSRoger Pau Monné #include <sys/tree.h>
5811752d88SAlan Cox #include <sys/vmmeter.h>
5911752d88SAlan Cox 
6011752d88SAlan Cox #include <ddb/ddb.h>
6111752d88SAlan Cox 
6211752d88SAlan Cox #include <vm/vm.h>
6301e115abSDoug Moore #include <vm/vm_extern.h>
6411752d88SAlan Cox #include <vm/vm_param.h>
6511752d88SAlan Cox #include <vm/vm_kern.h>
6611752d88SAlan Cox #include <vm/vm_object.h>
6711752d88SAlan Cox #include <vm/vm_page.h>
6811752d88SAlan Cox #include <vm/vm_phys.h>
69e2068d0bSJeff Roberson #include <vm/vm_pagequeue.h>
7011752d88SAlan Cox 
71449c2e92SKonstantin Belousov _Static_assert(sizeof(long) * NBBY >= VM_PHYSSEG_MAX,
72449c2e92SKonstantin Belousov     "Too many physsegs.");
73c9b06fa5SDoug Moore _Static_assert(sizeof(long long) >= sizeof(vm_paddr_t),
74c9b06fa5SDoug Moore     "vm_paddr_t too big for ffsll, flsll.");
7511752d88SAlan Cox 
76b6715dabSJeff Roberson #ifdef NUMA
77cdfeced8SJeff Roberson struct mem_affinity __read_mostly *mem_affinity;
78cdfeced8SJeff Roberson int __read_mostly *mem_locality;
79*c415cfc8SZhenlei Huang 
80*c415cfc8SZhenlei Huang static int numa_disabled;
81*c415cfc8SZhenlei Huang static SYSCTL_NODE(_vm, OID_AUTO, numa, CTLFLAG_RD | CTLFLAG_MPSAFE, 0,
82*c415cfc8SZhenlei Huang     "NUMA options");
83*c415cfc8SZhenlei Huang SYSCTL_INT(_vm_numa, OID_AUTO, disabled, CTLFLAG_RDTUN | CTLFLAG_NOFETCH,
84*c415cfc8SZhenlei Huang     &numa_disabled, 0, "NUMA-awareness in the allocators is disabled");
8562d70a81SJohn Baldwin #endif
86a3870a18SJohn Baldwin 
87cdfeced8SJeff Roberson int __read_mostly vm_ndomains = 1;
88463406acSMark Johnston domainset_t __read_mostly all_domains = DOMAINSET_T_INITIALIZER(0x1);
897e226537SAttilio Rao 
90cdfeced8SJeff Roberson struct vm_phys_seg __read_mostly vm_phys_segs[VM_PHYSSEG_MAX];
91cdfeced8SJeff Roberson int __read_mostly vm_phys_nsegs;
9281302f1dSMark Johnston static struct vm_phys_seg vm_phys_early_segs[8];
9381302f1dSMark Johnston static int vm_phys_early_nsegs;
9411752d88SAlan Cox 
9538d6b2dcSRoger Pau Monné struct vm_phys_fictitious_seg;
9638d6b2dcSRoger Pau Monné static int vm_phys_fictitious_cmp(struct vm_phys_fictitious_seg *,
9738d6b2dcSRoger Pau Monné     struct vm_phys_fictitious_seg *);
9838d6b2dcSRoger Pau Monné 
9938d6b2dcSRoger Pau Monné RB_HEAD(fict_tree, vm_phys_fictitious_seg) vm_phys_fictitious_tree =
100b649c2acSDoug Moore     RB_INITIALIZER(&vm_phys_fictitious_tree);
10138d6b2dcSRoger Pau Monné 
10238d6b2dcSRoger Pau Monné struct vm_phys_fictitious_seg {
10338d6b2dcSRoger Pau Monné 	RB_ENTRY(vm_phys_fictitious_seg) node;
10438d6b2dcSRoger Pau Monné 	/* Memory region data */
105b6de32bdSKonstantin Belousov 	vm_paddr_t	start;
106b6de32bdSKonstantin Belousov 	vm_paddr_t	end;
107b6de32bdSKonstantin Belousov 	vm_page_t	first_page;
10838d6b2dcSRoger Pau Monné };
10938d6b2dcSRoger Pau Monné 
11038d6b2dcSRoger Pau Monné RB_GENERATE_STATIC(fict_tree, vm_phys_fictitious_seg, node,
11138d6b2dcSRoger Pau Monné     vm_phys_fictitious_cmp);
11238d6b2dcSRoger Pau Monné 
113cdfeced8SJeff Roberson static struct rwlock_padalign vm_phys_fictitious_reg_lock;
114c0432fc3SMark Johnston MALLOC_DEFINE(M_FICT_PAGES, "vm_fictitious", "Fictitious VM pages");
115b6de32bdSKonstantin Belousov 
116cdfeced8SJeff Roberson static struct vm_freelist __aligned(CACHE_LINE_SIZE)
117f2a496d6SKonstantin Belousov     vm_phys_free_queues[MAXMEMDOM][VM_NFREELIST][VM_NFREEPOOL]
118f2a496d6SKonstantin Belousov     [VM_NFREEORDER_MAX];
11911752d88SAlan Cox 
120cdfeced8SJeff Roberson static int __read_mostly vm_nfreelists;
121d866a563SAlan Cox 
122d866a563SAlan Cox /*
12321943937SJeff Roberson  * These "avail lists" are globals used to communicate boot-time physical
12421943937SJeff Roberson  * memory layout to other parts of the kernel.  Each physically contiguous
12521943937SJeff Roberson  * region of memory is defined by a start address at an even index and an
12621943937SJeff Roberson  * end address at the following odd index.  Each list is terminated by a
12721943937SJeff Roberson  * pair of zero entries.
12821943937SJeff Roberson  *
12921943937SJeff Roberson  * dump_avail tells the dump code what regions to include in a crash dump, and
13021943937SJeff Roberson  * phys_avail is all of the remaining physical memory that is available for
13121943937SJeff Roberson  * the vm system.
13221943937SJeff Roberson  *
13321943937SJeff Roberson  * Initially dump_avail and phys_avail are identical.  Boot time memory
13421943937SJeff Roberson  * allocations remove extents from phys_avail that may still be included
13521943937SJeff Roberson  * in dumps.
13621943937SJeff Roberson  */
13721943937SJeff Roberson vm_paddr_t phys_avail[PHYS_AVAIL_COUNT];
13821943937SJeff Roberson vm_paddr_t dump_avail[PHYS_AVAIL_COUNT];
13921943937SJeff Roberson 
14021943937SJeff Roberson /*
141d866a563SAlan Cox  * Provides the mapping from VM_FREELIST_* to free list indices (flind).
142d866a563SAlan Cox  */
143cdfeced8SJeff Roberson static int __read_mostly vm_freelist_to_flind[VM_NFREELIST];
144d866a563SAlan Cox 
145d866a563SAlan Cox CTASSERT(VM_FREELIST_DEFAULT == 0);
146d866a563SAlan Cox 
147d866a563SAlan Cox #ifdef VM_FREELIST_DMA32
148d866a563SAlan Cox #define	VM_DMA32_BOUNDARY	((vm_paddr_t)1 << 32)
149d866a563SAlan Cox #endif
150d866a563SAlan Cox 
151d866a563SAlan Cox /*
152d866a563SAlan Cox  * Enforce the assumptions made by vm_phys_add_seg() and vm_phys_init() about
153d866a563SAlan Cox  * the ordering of the free list boundaries.
154d866a563SAlan Cox  */
155d866a563SAlan Cox #if defined(VM_LOWMEM_BOUNDARY) && defined(VM_DMA32_BOUNDARY)
156d866a563SAlan Cox CTASSERT(VM_LOWMEM_BOUNDARY < VM_DMA32_BOUNDARY);
157d866a563SAlan Cox #endif
15811752d88SAlan Cox 
15911752d88SAlan Cox static int sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS);
1607029da5cSPawel Biernacki SYSCTL_OID(_vm, OID_AUTO, phys_free,
161114484b7SMark Johnston     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
1627029da5cSPawel Biernacki     sysctl_vm_phys_free, "A",
1637029da5cSPawel Biernacki     "Phys Free Info");
16411752d88SAlan Cox 
16511752d88SAlan Cox static int sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS);
1667029da5cSPawel Biernacki SYSCTL_OID(_vm, OID_AUTO, phys_segs,
167114484b7SMark Johnston     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
1687029da5cSPawel Biernacki     sysctl_vm_phys_segs, "A",
1697029da5cSPawel Biernacki     "Phys Seg Info");
17011752d88SAlan Cox 
171b6715dabSJeff Roberson #ifdef NUMA
172415d7ccaSAdrian Chadd static int sysctl_vm_phys_locality(SYSCTL_HANDLER_ARGS);
1737029da5cSPawel Biernacki SYSCTL_OID(_vm, OID_AUTO, phys_locality,
174114484b7SMark Johnston     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
1757029da5cSPawel Biernacki     sysctl_vm_phys_locality, "A",
1767029da5cSPawel Biernacki     "Phys Locality Info");
1776520495aSAdrian Chadd #endif
178415d7ccaSAdrian Chadd 
1797e226537SAttilio Rao SYSCTL_INT(_vm, OID_AUTO, ndomains, CTLFLAG_RD,
1807e226537SAttilio Rao     &vm_ndomains, 0, "Number of physical memory domains available.");
181a3870a18SJohn Baldwin 
182d866a563SAlan Cox static void _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int domain);
183d866a563SAlan Cox static void vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end);
18411752d88SAlan Cox static void vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl,
185370a338aSAlan Cox     int order, int tail);
186c606ab59SDoug Moore 
18738d6b2dcSRoger Pau Monné /*
18838d6b2dcSRoger Pau Monné  * Red-black tree helpers for vm fictitious range management.
18938d6b2dcSRoger Pau Monné  */
19038d6b2dcSRoger Pau Monné static inline int
19138d6b2dcSRoger Pau Monné vm_phys_fictitious_in_range(struct vm_phys_fictitious_seg *p,
19238d6b2dcSRoger Pau Monné     struct vm_phys_fictitious_seg *range)
19338d6b2dcSRoger Pau Monné {
19438d6b2dcSRoger Pau Monné 
19538d6b2dcSRoger Pau Monné 	KASSERT(range->start != 0 && range->end != 0,
19638d6b2dcSRoger Pau Monné 	    ("Invalid range passed on search for vm_fictitious page"));
19738d6b2dcSRoger Pau Monné 	if (p->start >= range->end)
19838d6b2dcSRoger Pau Monné 		return (1);
19938d6b2dcSRoger Pau Monné 	if (p->start < range->start)
20038d6b2dcSRoger Pau Monné 		return (-1);
20138d6b2dcSRoger Pau Monné 
20238d6b2dcSRoger Pau Monné 	return (0);
20338d6b2dcSRoger Pau Monné }
20438d6b2dcSRoger Pau Monné 
20538d6b2dcSRoger Pau Monné static int
20638d6b2dcSRoger Pau Monné vm_phys_fictitious_cmp(struct vm_phys_fictitious_seg *p1,
20738d6b2dcSRoger Pau Monné     struct vm_phys_fictitious_seg *p2)
20838d6b2dcSRoger Pau Monné {
20938d6b2dcSRoger Pau Monné 
21038d6b2dcSRoger Pau Monné 	/* Check if this is a search for a page */
21138d6b2dcSRoger Pau Monné 	if (p1->end == 0)
21238d6b2dcSRoger Pau Monné 		return (vm_phys_fictitious_in_range(p1, p2));
21338d6b2dcSRoger Pau Monné 
21438d6b2dcSRoger Pau Monné 	KASSERT(p2->end != 0,
21538d6b2dcSRoger Pau Monné     ("Invalid range passed as second parameter to vm fictitious comparison"));
21638d6b2dcSRoger Pau Monné 
21738d6b2dcSRoger Pau Monné 	/* Searching to add a new range */
21838d6b2dcSRoger Pau Monné 	if (p1->end <= p2->start)
21938d6b2dcSRoger Pau Monné 		return (-1);
22038d6b2dcSRoger Pau Monné 	if (p1->start >= p2->end)
22138d6b2dcSRoger Pau Monné 		return (1);
22238d6b2dcSRoger Pau Monné 
22338d6b2dcSRoger Pau Monné 	panic("Trying to add overlapping vm fictitious ranges:\n"
22438d6b2dcSRoger Pau Monné 	    "[%#jx:%#jx] and [%#jx:%#jx]", (uintmax_t)p1->start,
22538d6b2dcSRoger Pau Monné 	    (uintmax_t)p1->end, (uintmax_t)p2->start, (uintmax_t)p2->end);
22638d6b2dcSRoger Pau Monné }
22738d6b2dcSRoger Pau Monné 
2286f4acaf4SJeff Roberson int
2296f4acaf4SJeff Roberson vm_phys_domain_match(int prefer, vm_paddr_t low, vm_paddr_t high)
230449c2e92SKonstantin Belousov {
231b6715dabSJeff Roberson #ifdef NUMA
2326f4acaf4SJeff Roberson 	domainset_t mask;
2336f4acaf4SJeff Roberson 	int i;
234449c2e92SKonstantin Belousov 
2356f4acaf4SJeff Roberson 	if (vm_ndomains == 1 || mem_affinity == NULL)
2366f4acaf4SJeff Roberson 		return (0);
2376f4acaf4SJeff Roberson 
2386f4acaf4SJeff Roberson 	DOMAINSET_ZERO(&mask);
2396f4acaf4SJeff Roberson 	/*
2406f4acaf4SJeff Roberson 	 * Check for any memory that overlaps low, high.
2416f4acaf4SJeff Roberson 	 */
2426f4acaf4SJeff Roberson 	for (i = 0; mem_affinity[i].end != 0; i++)
2436f4acaf4SJeff Roberson 		if (mem_affinity[i].start <= high &&
2446f4acaf4SJeff Roberson 		    mem_affinity[i].end >= low)
2456f4acaf4SJeff Roberson 			DOMAINSET_SET(mem_affinity[i].domain, &mask);
2466f4acaf4SJeff Roberson 	if (prefer != -1 && DOMAINSET_ISSET(prefer, &mask))
2476f4acaf4SJeff Roberson 		return (prefer);
2486f4acaf4SJeff Roberson 	if (DOMAINSET_EMPTY(&mask))
2496f4acaf4SJeff Roberson 		panic("vm_phys_domain_match:  Impossible constraint");
2506f4acaf4SJeff Roberson 	return (DOMAINSET_FFS(&mask) - 1);
2516f4acaf4SJeff Roberson #else
2526f4acaf4SJeff Roberson 	return (0);
2536f4acaf4SJeff Roberson #endif
254449c2e92SKonstantin Belousov }
255449c2e92SKonstantin Belousov 
25611752d88SAlan Cox /*
25711752d88SAlan Cox  * Outputs the state of the physical memory allocator, specifically,
25811752d88SAlan Cox  * the amount of physical memory in each free list.
25911752d88SAlan Cox  */
26011752d88SAlan Cox static int
26111752d88SAlan Cox sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS)
26211752d88SAlan Cox {
26311752d88SAlan Cox 	struct sbuf sbuf;
26411752d88SAlan Cox 	struct vm_freelist *fl;
2657e226537SAttilio Rao 	int dom, error, flind, oind, pind;
26611752d88SAlan Cox 
26700f0e671SMatthew D Fleming 	error = sysctl_wire_old_buffer(req, 0);
26800f0e671SMatthew D Fleming 	if (error != 0)
26900f0e671SMatthew D Fleming 		return (error);
2707e226537SAttilio Rao 	sbuf_new_for_sysctl(&sbuf, NULL, 128 * vm_ndomains, req);
2717e226537SAttilio Rao 	for (dom = 0; dom < vm_ndomains; dom++) {
272eb2f42fbSAlan Cox 		sbuf_printf(&sbuf,"\nDOMAIN %d:\n", dom);
27311752d88SAlan Cox 		for (flind = 0; flind < vm_nfreelists; flind++) {
274eb2f42fbSAlan Cox 			sbuf_printf(&sbuf, "\nFREE LIST %d:\n"
27511752d88SAlan Cox 			    "\n  ORDER (SIZE)  |  NUMBER"
27611752d88SAlan Cox 			    "\n              ", flind);
27711752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
27811752d88SAlan Cox 				sbuf_printf(&sbuf, "  |  POOL %d", pind);
27911752d88SAlan Cox 			sbuf_printf(&sbuf, "\n--            ");
28011752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
28111752d88SAlan Cox 				sbuf_printf(&sbuf, "-- --      ");
28211752d88SAlan Cox 			sbuf_printf(&sbuf, "--\n");
28311752d88SAlan Cox 			for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
284d689bc00SAlan Cox 				sbuf_printf(&sbuf, "  %2d (%6dK)", oind,
28511752d88SAlan Cox 				    1 << (PAGE_SHIFT - 10 + oind));
28611752d88SAlan Cox 				for (pind = 0; pind < VM_NFREEPOOL; pind++) {
2877e226537SAttilio Rao 				fl = vm_phys_free_queues[dom][flind][pind];
288eb2f42fbSAlan Cox 					sbuf_printf(&sbuf, "  |  %6d",
2897e226537SAttilio Rao 					    fl[oind].lcnt);
29011752d88SAlan Cox 				}
29111752d88SAlan Cox 				sbuf_printf(&sbuf, "\n");
29211752d88SAlan Cox 			}
2937e226537SAttilio Rao 		}
29411752d88SAlan Cox 	}
2954e657159SMatthew D Fleming 	error = sbuf_finish(&sbuf);
29611752d88SAlan Cox 	sbuf_delete(&sbuf);
29711752d88SAlan Cox 	return (error);
29811752d88SAlan Cox }
29911752d88SAlan Cox 
30011752d88SAlan Cox /*
30111752d88SAlan Cox  * Outputs the set of physical memory segments.
30211752d88SAlan Cox  */
30311752d88SAlan Cox static int
30411752d88SAlan Cox sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS)
30511752d88SAlan Cox {
30611752d88SAlan Cox 	struct sbuf sbuf;
30711752d88SAlan Cox 	struct vm_phys_seg *seg;
30811752d88SAlan Cox 	int error, segind;
30911752d88SAlan Cox 
31000f0e671SMatthew D Fleming 	error = sysctl_wire_old_buffer(req, 0);
31100f0e671SMatthew D Fleming 	if (error != 0)
31200f0e671SMatthew D Fleming 		return (error);
3134e657159SMatthew D Fleming 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
31411752d88SAlan Cox 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
31511752d88SAlan Cox 		sbuf_printf(&sbuf, "\nSEGMENT %d:\n\n", segind);
31611752d88SAlan Cox 		seg = &vm_phys_segs[segind];
31711752d88SAlan Cox 		sbuf_printf(&sbuf, "start:     %#jx\n",
31811752d88SAlan Cox 		    (uintmax_t)seg->start);
31911752d88SAlan Cox 		sbuf_printf(&sbuf, "end:       %#jx\n",
32011752d88SAlan Cox 		    (uintmax_t)seg->end);
321a3870a18SJohn Baldwin 		sbuf_printf(&sbuf, "domain:    %d\n", seg->domain);
32211752d88SAlan Cox 		sbuf_printf(&sbuf, "free list: %p\n", seg->free_queues);
32311752d88SAlan Cox 	}
3244e657159SMatthew D Fleming 	error = sbuf_finish(&sbuf);
32511752d88SAlan Cox 	sbuf_delete(&sbuf);
32611752d88SAlan Cox 	return (error);
32711752d88SAlan Cox }
32811752d88SAlan Cox 
329415d7ccaSAdrian Chadd /*
330415d7ccaSAdrian Chadd  * Return affinity, or -1 if there's no affinity information.
331415d7ccaSAdrian Chadd  */
3326520495aSAdrian Chadd int
333415d7ccaSAdrian Chadd vm_phys_mem_affinity(int f, int t)
334415d7ccaSAdrian Chadd {
335415d7ccaSAdrian Chadd 
336b6715dabSJeff Roberson #ifdef NUMA
337415d7ccaSAdrian Chadd 	if (mem_locality == NULL)
338415d7ccaSAdrian Chadd 		return (-1);
339415d7ccaSAdrian Chadd 	if (f >= vm_ndomains || t >= vm_ndomains)
340415d7ccaSAdrian Chadd 		return (-1);
341415d7ccaSAdrian Chadd 	return (mem_locality[f * vm_ndomains + t]);
3426520495aSAdrian Chadd #else
3436520495aSAdrian Chadd 	return (-1);
3446520495aSAdrian Chadd #endif
345415d7ccaSAdrian Chadd }
346415d7ccaSAdrian Chadd 
347b6715dabSJeff Roberson #ifdef NUMA
348415d7ccaSAdrian Chadd /*
349415d7ccaSAdrian Chadd  * Outputs the VM locality table.
350415d7ccaSAdrian Chadd  */
351415d7ccaSAdrian Chadd static int
352415d7ccaSAdrian Chadd sysctl_vm_phys_locality(SYSCTL_HANDLER_ARGS)
353415d7ccaSAdrian Chadd {
354415d7ccaSAdrian Chadd 	struct sbuf sbuf;
355415d7ccaSAdrian Chadd 	int error, i, j;
356415d7ccaSAdrian Chadd 
357415d7ccaSAdrian Chadd 	error = sysctl_wire_old_buffer(req, 0);
358415d7ccaSAdrian Chadd 	if (error != 0)
359415d7ccaSAdrian Chadd 		return (error);
360415d7ccaSAdrian Chadd 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
361415d7ccaSAdrian Chadd 
362415d7ccaSAdrian Chadd 	sbuf_printf(&sbuf, "\n");
363415d7ccaSAdrian Chadd 
364415d7ccaSAdrian Chadd 	for (i = 0; i < vm_ndomains; i++) {
365415d7ccaSAdrian Chadd 		sbuf_printf(&sbuf, "%d: ", i);
366415d7ccaSAdrian Chadd 		for (j = 0; j < vm_ndomains; j++) {
367415d7ccaSAdrian Chadd 			sbuf_printf(&sbuf, "%d ", vm_phys_mem_affinity(i, j));
368415d7ccaSAdrian Chadd 		}
369415d7ccaSAdrian Chadd 		sbuf_printf(&sbuf, "\n");
370415d7ccaSAdrian Chadd 	}
371415d7ccaSAdrian Chadd 	error = sbuf_finish(&sbuf);
372415d7ccaSAdrian Chadd 	sbuf_delete(&sbuf);
373415d7ccaSAdrian Chadd 	return (error);
374415d7ccaSAdrian Chadd }
3756520495aSAdrian Chadd #endif
376415d7ccaSAdrian Chadd 
3777e226537SAttilio Rao static void
3787e226537SAttilio Rao vm_freelist_add(struct vm_freelist *fl, vm_page_t m, int order, int tail)
379a3870a18SJohn Baldwin {
380a3870a18SJohn Baldwin 
3817e226537SAttilio Rao 	m->order = order;
3827e226537SAttilio Rao 	if (tail)
3835cd29d0fSMark Johnston 		TAILQ_INSERT_TAIL(&fl[order].pl, m, listq);
3847e226537SAttilio Rao 	else
3855cd29d0fSMark Johnston 		TAILQ_INSERT_HEAD(&fl[order].pl, m, listq);
3867e226537SAttilio Rao 	fl[order].lcnt++;
387a3870a18SJohn Baldwin }
3887e226537SAttilio Rao 
3897e226537SAttilio Rao static void
3907e226537SAttilio Rao vm_freelist_rem(struct vm_freelist *fl, vm_page_t m, int order)
3917e226537SAttilio Rao {
3927e226537SAttilio Rao 
3935cd29d0fSMark Johnston 	TAILQ_REMOVE(&fl[order].pl, m, listq);
3947e226537SAttilio Rao 	fl[order].lcnt--;
3957e226537SAttilio Rao 	m->order = VM_NFREEORDER;
396a3870a18SJohn Baldwin }
397a3870a18SJohn Baldwin 
39811752d88SAlan Cox /*
39911752d88SAlan Cox  * Create a physical memory segment.
40011752d88SAlan Cox  */
40111752d88SAlan Cox static void
402d866a563SAlan Cox _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int domain)
40311752d88SAlan Cox {
40411752d88SAlan Cox 	struct vm_phys_seg *seg;
40511752d88SAlan Cox 
40611752d88SAlan Cox 	KASSERT(vm_phys_nsegs < VM_PHYSSEG_MAX,
40711752d88SAlan Cox 	    ("vm_phys_create_seg: increase VM_PHYSSEG_MAX"));
408ef435ae7SJeff Roberson 	KASSERT(domain >= 0 && domain < vm_ndomains,
4097e226537SAttilio Rao 	    ("vm_phys_create_seg: invalid domain provided"));
41011752d88SAlan Cox 	seg = &vm_phys_segs[vm_phys_nsegs++];
411271f0f12SAlan Cox 	while (seg > vm_phys_segs && (seg - 1)->start >= end) {
412271f0f12SAlan Cox 		*seg = *(seg - 1);
413271f0f12SAlan Cox 		seg--;
414271f0f12SAlan Cox 	}
41511752d88SAlan Cox 	seg->start = start;
41611752d88SAlan Cox 	seg->end = end;
417a3870a18SJohn Baldwin 	seg->domain = domain;
41811752d88SAlan Cox }
41911752d88SAlan Cox 
420a3870a18SJohn Baldwin static void
421d866a563SAlan Cox vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end)
422a3870a18SJohn Baldwin {
423b6715dabSJeff Roberson #ifdef NUMA
424a3870a18SJohn Baldwin 	int i;
425a3870a18SJohn Baldwin 
426a3870a18SJohn Baldwin 	if (mem_affinity == NULL) {
427d866a563SAlan Cox 		_vm_phys_create_seg(start, end, 0);
428a3870a18SJohn Baldwin 		return;
429a3870a18SJohn Baldwin 	}
430a3870a18SJohn Baldwin 
431a3870a18SJohn Baldwin 	for (i = 0;; i++) {
432a3870a18SJohn Baldwin 		if (mem_affinity[i].end == 0)
433a3870a18SJohn Baldwin 			panic("Reached end of affinity info");
434a3870a18SJohn Baldwin 		if (mem_affinity[i].end <= start)
435a3870a18SJohn Baldwin 			continue;
436a3870a18SJohn Baldwin 		if (mem_affinity[i].start > start)
437a3870a18SJohn Baldwin 			panic("No affinity info for start %jx",
438a3870a18SJohn Baldwin 			    (uintmax_t)start);
439a3870a18SJohn Baldwin 		if (mem_affinity[i].end >= end) {
440d866a563SAlan Cox 			_vm_phys_create_seg(start, end,
441a3870a18SJohn Baldwin 			    mem_affinity[i].domain);
442a3870a18SJohn Baldwin 			break;
443a3870a18SJohn Baldwin 		}
444d866a563SAlan Cox 		_vm_phys_create_seg(start, mem_affinity[i].end,
445a3870a18SJohn Baldwin 		    mem_affinity[i].domain);
446a3870a18SJohn Baldwin 		start = mem_affinity[i].end;
447a3870a18SJohn Baldwin 	}
44862d70a81SJohn Baldwin #else
44962d70a81SJohn Baldwin 	_vm_phys_create_seg(start, end, 0);
45062d70a81SJohn Baldwin #endif
451a3870a18SJohn Baldwin }
452a3870a18SJohn Baldwin 
45311752d88SAlan Cox /*
454271f0f12SAlan Cox  * Add a physical memory segment.
455271f0f12SAlan Cox  */
456271f0f12SAlan Cox void
457271f0f12SAlan Cox vm_phys_add_seg(vm_paddr_t start, vm_paddr_t end)
458271f0f12SAlan Cox {
459d866a563SAlan Cox 	vm_paddr_t paddr;
460271f0f12SAlan Cox 
461271f0f12SAlan Cox 	KASSERT((start & PAGE_MASK) == 0,
462271f0f12SAlan Cox 	    ("vm_phys_define_seg: start is not page aligned"));
463271f0f12SAlan Cox 	KASSERT((end & PAGE_MASK) == 0,
464271f0f12SAlan Cox 	    ("vm_phys_define_seg: end is not page aligned"));
465d866a563SAlan Cox 
466d866a563SAlan Cox 	/*
467d866a563SAlan Cox 	 * Split the physical memory segment if it spans two or more free
468d866a563SAlan Cox 	 * list boundaries.
469d866a563SAlan Cox 	 */
470d866a563SAlan Cox 	paddr = start;
471d866a563SAlan Cox #ifdef	VM_FREELIST_LOWMEM
472d866a563SAlan Cox 	if (paddr < VM_LOWMEM_BOUNDARY && end > VM_LOWMEM_BOUNDARY) {
473d866a563SAlan Cox 		vm_phys_create_seg(paddr, VM_LOWMEM_BOUNDARY);
474d866a563SAlan Cox 		paddr = VM_LOWMEM_BOUNDARY;
475d866a563SAlan Cox 	}
476271f0f12SAlan Cox #endif
477d866a563SAlan Cox #ifdef	VM_FREELIST_DMA32
478d866a563SAlan Cox 	if (paddr < VM_DMA32_BOUNDARY && end > VM_DMA32_BOUNDARY) {
479d866a563SAlan Cox 		vm_phys_create_seg(paddr, VM_DMA32_BOUNDARY);
480d866a563SAlan Cox 		paddr = VM_DMA32_BOUNDARY;
481d866a563SAlan Cox 	}
482d866a563SAlan Cox #endif
483d866a563SAlan Cox 	vm_phys_create_seg(paddr, end);
484271f0f12SAlan Cox }
485271f0f12SAlan Cox 
486271f0f12SAlan Cox /*
48711752d88SAlan Cox  * Initialize the physical memory allocator.
488d866a563SAlan Cox  *
489d866a563SAlan Cox  * Requires that vm_page_array is initialized!
49011752d88SAlan Cox  */
49111752d88SAlan Cox void
49211752d88SAlan Cox vm_phys_init(void)
49311752d88SAlan Cox {
49411752d88SAlan Cox 	struct vm_freelist *fl;
49572aebdd7SAlan Cox 	struct vm_phys_seg *end_seg, *prev_seg, *seg, *tmp_seg;
49652526922SJohn Baldwin #if defined(VM_DMA32_NPAGES_THRESHOLD) || defined(VM_PHYSSEG_SPARSE)
497d866a563SAlan Cox 	u_long npages;
49852526922SJohn Baldwin #endif
499d866a563SAlan Cox 	int dom, flind, freelist, oind, pind, segind;
50011752d88SAlan Cox 
501d866a563SAlan Cox 	/*
502d866a563SAlan Cox 	 * Compute the number of free lists, and generate the mapping from the
503d866a563SAlan Cox 	 * manifest constants VM_FREELIST_* to the free list indices.
504d866a563SAlan Cox 	 *
505d866a563SAlan Cox 	 * Initially, the entries of vm_freelist_to_flind[] are set to either
506d866a563SAlan Cox 	 * 0 or 1 to indicate which free lists should be created.
507d866a563SAlan Cox 	 */
50852526922SJohn Baldwin #ifdef	VM_DMA32_NPAGES_THRESHOLD
509d866a563SAlan Cox 	npages = 0;
51052526922SJohn Baldwin #endif
511d866a563SAlan Cox 	for (segind = vm_phys_nsegs - 1; segind >= 0; segind--) {
512d866a563SAlan Cox 		seg = &vm_phys_segs[segind];
513d866a563SAlan Cox #ifdef	VM_FREELIST_LOWMEM
514d866a563SAlan Cox 		if (seg->end <= VM_LOWMEM_BOUNDARY)
515d866a563SAlan Cox 			vm_freelist_to_flind[VM_FREELIST_LOWMEM] = 1;
516d866a563SAlan Cox 		else
517d866a563SAlan Cox #endif
518d866a563SAlan Cox #ifdef	VM_FREELIST_DMA32
519d866a563SAlan Cox 		if (
520d866a563SAlan Cox #ifdef	VM_DMA32_NPAGES_THRESHOLD
521d866a563SAlan Cox 		    /*
522d866a563SAlan Cox 		     * Create the DMA32 free list only if the amount of
523d866a563SAlan Cox 		     * physical memory above physical address 4G exceeds the
524d866a563SAlan Cox 		     * given threshold.
525d866a563SAlan Cox 		     */
526d866a563SAlan Cox 		    npages > VM_DMA32_NPAGES_THRESHOLD &&
527d866a563SAlan Cox #endif
528d866a563SAlan Cox 		    seg->end <= VM_DMA32_BOUNDARY)
529d866a563SAlan Cox 			vm_freelist_to_flind[VM_FREELIST_DMA32] = 1;
530d866a563SAlan Cox 		else
531d866a563SAlan Cox #endif
532d866a563SAlan Cox 		{
53352526922SJohn Baldwin #ifdef	VM_DMA32_NPAGES_THRESHOLD
534d866a563SAlan Cox 			npages += atop(seg->end - seg->start);
53552526922SJohn Baldwin #endif
536d866a563SAlan Cox 			vm_freelist_to_flind[VM_FREELIST_DEFAULT] = 1;
537d866a563SAlan Cox 		}
538d866a563SAlan Cox 	}
539d866a563SAlan Cox 	/* Change each entry into a running total of the free lists. */
540d866a563SAlan Cox 	for (freelist = 1; freelist < VM_NFREELIST; freelist++) {
541d866a563SAlan Cox 		vm_freelist_to_flind[freelist] +=
542d866a563SAlan Cox 		    vm_freelist_to_flind[freelist - 1];
543d866a563SAlan Cox 	}
544d866a563SAlan Cox 	vm_nfreelists = vm_freelist_to_flind[VM_NFREELIST - 1];
545d866a563SAlan Cox 	KASSERT(vm_nfreelists > 0, ("vm_phys_init: no free lists"));
546d866a563SAlan Cox 	/* Change each entry into a free list index. */
547d866a563SAlan Cox 	for (freelist = 0; freelist < VM_NFREELIST; freelist++)
548d866a563SAlan Cox 		vm_freelist_to_flind[freelist]--;
549d866a563SAlan Cox 
550d866a563SAlan Cox 	/*
551d866a563SAlan Cox 	 * Initialize the first_page and free_queues fields of each physical
552d866a563SAlan Cox 	 * memory segment.
553d866a563SAlan Cox 	 */
554271f0f12SAlan Cox #ifdef VM_PHYSSEG_SPARSE
555d866a563SAlan Cox 	npages = 0;
55611752d88SAlan Cox #endif
557271f0f12SAlan Cox 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
558271f0f12SAlan Cox 		seg = &vm_phys_segs[segind];
559271f0f12SAlan Cox #ifdef VM_PHYSSEG_SPARSE
560d866a563SAlan Cox 		seg->first_page = &vm_page_array[npages];
561d866a563SAlan Cox 		npages += atop(seg->end - seg->start);
562271f0f12SAlan Cox #else
563271f0f12SAlan Cox 		seg->first_page = PHYS_TO_VM_PAGE(seg->start);
56411752d88SAlan Cox #endif
565d866a563SAlan Cox #ifdef	VM_FREELIST_LOWMEM
566d866a563SAlan Cox 		if (seg->end <= VM_LOWMEM_BOUNDARY) {
567d866a563SAlan Cox 			flind = vm_freelist_to_flind[VM_FREELIST_LOWMEM];
568d866a563SAlan Cox 			KASSERT(flind >= 0,
569d866a563SAlan Cox 			    ("vm_phys_init: LOWMEM flind < 0"));
570d866a563SAlan Cox 		} else
571d866a563SAlan Cox #endif
572d866a563SAlan Cox #ifdef	VM_FREELIST_DMA32
573d866a563SAlan Cox 		if (seg->end <= VM_DMA32_BOUNDARY) {
574d866a563SAlan Cox 			flind = vm_freelist_to_flind[VM_FREELIST_DMA32];
575d866a563SAlan Cox 			KASSERT(flind >= 0,
576d866a563SAlan Cox 			    ("vm_phys_init: DMA32 flind < 0"));
577d866a563SAlan Cox 		} else
578d866a563SAlan Cox #endif
579d866a563SAlan Cox 		{
580d866a563SAlan Cox 			flind = vm_freelist_to_flind[VM_FREELIST_DEFAULT];
581d866a563SAlan Cox 			KASSERT(flind >= 0,
582d866a563SAlan Cox 			    ("vm_phys_init: DEFAULT flind < 0"));
58311752d88SAlan Cox 		}
584d866a563SAlan Cox 		seg->free_queues = &vm_phys_free_queues[seg->domain][flind];
585d866a563SAlan Cox 	}
586d866a563SAlan Cox 
587d866a563SAlan Cox 	/*
58872aebdd7SAlan Cox 	 * Coalesce physical memory segments that are contiguous and share the
58972aebdd7SAlan Cox 	 * same per-domain free queues.
59072aebdd7SAlan Cox 	 */
59172aebdd7SAlan Cox 	prev_seg = vm_phys_segs;
59272aebdd7SAlan Cox 	seg = &vm_phys_segs[1];
59372aebdd7SAlan Cox 	end_seg = &vm_phys_segs[vm_phys_nsegs];
59472aebdd7SAlan Cox 	while (seg < end_seg) {
59572aebdd7SAlan Cox 		if (prev_seg->end == seg->start &&
59672aebdd7SAlan Cox 		    prev_seg->free_queues == seg->free_queues) {
59772aebdd7SAlan Cox 			prev_seg->end = seg->end;
59872aebdd7SAlan Cox 			KASSERT(prev_seg->domain == seg->domain,
59972aebdd7SAlan Cox 			    ("vm_phys_init: free queues cannot span domains"));
60072aebdd7SAlan Cox 			vm_phys_nsegs--;
60172aebdd7SAlan Cox 			end_seg--;
60272aebdd7SAlan Cox 			for (tmp_seg = seg; tmp_seg < end_seg; tmp_seg++)
60372aebdd7SAlan Cox 				*tmp_seg = *(tmp_seg + 1);
60472aebdd7SAlan Cox 		} else {
60572aebdd7SAlan Cox 			prev_seg = seg;
60672aebdd7SAlan Cox 			seg++;
60772aebdd7SAlan Cox 		}
60872aebdd7SAlan Cox 	}
60972aebdd7SAlan Cox 
61072aebdd7SAlan Cox 	/*
611d866a563SAlan Cox 	 * Initialize the free queues.
612d866a563SAlan Cox 	 */
6137e226537SAttilio Rao 	for (dom = 0; dom < vm_ndomains; dom++) {
61411752d88SAlan Cox 		for (flind = 0; flind < vm_nfreelists; flind++) {
61511752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
6167e226537SAttilio Rao 				fl = vm_phys_free_queues[dom][flind][pind];
61711752d88SAlan Cox 				for (oind = 0; oind < VM_NFREEORDER; oind++)
61811752d88SAlan Cox 					TAILQ_INIT(&fl[oind].pl);
61911752d88SAlan Cox 			}
62011752d88SAlan Cox 		}
621a3870a18SJohn Baldwin 	}
622d866a563SAlan Cox 
62338d6b2dcSRoger Pau Monné 	rw_init(&vm_phys_fictitious_reg_lock, "vmfctr");
62411752d88SAlan Cox }
62511752d88SAlan Cox 
62611752d88SAlan Cox /*
627662e7fa8SMark Johnston  * Register info about the NUMA topology of the system.
628662e7fa8SMark Johnston  *
629662e7fa8SMark Johnston  * Invoked by platform-dependent code prior to vm_phys_init().
630662e7fa8SMark Johnston  */
631662e7fa8SMark Johnston void
632662e7fa8SMark Johnston vm_phys_register_domains(int ndomains, struct mem_affinity *affinity,
633662e7fa8SMark Johnston     int *locality)
634662e7fa8SMark Johnston {
635662e7fa8SMark Johnston #ifdef NUMA
636*c415cfc8SZhenlei Huang 	int i;
637662e7fa8SMark Johnston 
638b61f3142SMark Johnston 	/*
639b61f3142SMark Johnston 	 * For now the only override value that we support is 1, which
640b61f3142SMark Johnston 	 * effectively disables NUMA-awareness in the allocators.
641b61f3142SMark Johnston 	 */
642*c415cfc8SZhenlei Huang 	TUNABLE_INT_FETCH("vm.numa.disabled", &numa_disabled);
643*c415cfc8SZhenlei Huang 	if (numa_disabled)
644b61f3142SMark Johnston 		ndomains = 1;
645b61f3142SMark Johnston 
646b61f3142SMark Johnston 	if (ndomains > 1) {
647662e7fa8SMark Johnston 		vm_ndomains = ndomains;
648662e7fa8SMark Johnston 		mem_affinity = affinity;
649662e7fa8SMark Johnston 		mem_locality = locality;
650b61f3142SMark Johnston 	}
651662e7fa8SMark Johnston 
652662e7fa8SMark Johnston 	for (i = 0; i < vm_ndomains; i++)
653662e7fa8SMark Johnston 		DOMAINSET_SET(i, &all_domains);
654662e7fa8SMark Johnston #else
655662e7fa8SMark Johnston 	(void)ndomains;
656662e7fa8SMark Johnston 	(void)affinity;
657662e7fa8SMark Johnston 	(void)locality;
658662e7fa8SMark Johnston #endif
659662e7fa8SMark Johnston }
660662e7fa8SMark Johnston 
661662e7fa8SMark Johnston /*
66211752d88SAlan Cox  * Split a contiguous, power of two-sized set of physical pages.
663370a338aSAlan Cox  *
664370a338aSAlan Cox  * When this function is called by a page allocation function, the caller
665370a338aSAlan Cox  * should request insertion at the head unless the order [order, oind) queues
666370a338aSAlan Cox  * are known to be empty.  The objective being to reduce the likelihood of
667370a338aSAlan Cox  * long-term fragmentation by promoting contemporaneous allocation and
668370a338aSAlan Cox  * (hopefully) deallocation.
66911752d88SAlan Cox  */
67011752d88SAlan Cox static __inline void
671370a338aSAlan Cox vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl, int order,
672370a338aSAlan Cox     int tail)
67311752d88SAlan Cox {
67411752d88SAlan Cox 	vm_page_t m_buddy;
67511752d88SAlan Cox 
67611752d88SAlan Cox 	while (oind > order) {
67711752d88SAlan Cox 		oind--;
67811752d88SAlan Cox 		m_buddy = &m[1 << oind];
67911752d88SAlan Cox 		KASSERT(m_buddy->order == VM_NFREEORDER,
68011752d88SAlan Cox 		    ("vm_phys_split_pages: page %p has unexpected order %d",
68111752d88SAlan Cox 		    m_buddy, m_buddy->order));
682370a338aSAlan Cox 		vm_freelist_add(fl, m_buddy, oind, tail);
68311752d88SAlan Cox         }
68411752d88SAlan Cox }
68511752d88SAlan Cox 
68611752d88SAlan Cox /*
687e77f4e7fSDoug Moore  * Add the physical pages [m, m + npages) at the beginning of a power-of-two
688e77f4e7fSDoug Moore  * aligned and sized set to the specified free list.
689e77f4e7fSDoug Moore  *
690e77f4e7fSDoug Moore  * When this function is called by a page allocation function, the caller
691e77f4e7fSDoug Moore  * should request insertion at the head unless the lower-order queues are
692e77f4e7fSDoug Moore  * known to be empty.  The objective being to reduce the likelihood of long-
693e77f4e7fSDoug Moore  * term fragmentation by promoting contemporaneous allocation and (hopefully)
694e77f4e7fSDoug Moore  * deallocation.
695e77f4e7fSDoug Moore  *
696e77f4e7fSDoug Moore  * The physical page m's buddy must not be free.
697e77f4e7fSDoug Moore  */
698e77f4e7fSDoug Moore static void
699e77f4e7fSDoug Moore vm_phys_enq_beg(vm_page_t m, u_int npages, struct vm_freelist *fl, int tail)
700e77f4e7fSDoug Moore {
701e77f4e7fSDoug Moore         int order;
702e77f4e7fSDoug Moore 
703e77f4e7fSDoug Moore 	KASSERT(npages == 0 ||
704e77f4e7fSDoug Moore 	    (VM_PAGE_TO_PHYS(m) &
705e77f4e7fSDoug Moore 	    ((PAGE_SIZE << (fls(npages) - 1)) - 1)) == 0,
706e77f4e7fSDoug Moore 	    ("%s: page %p and npages %u are misaligned",
707e77f4e7fSDoug Moore 	    __func__, m, npages));
708e77f4e7fSDoug Moore         while (npages > 0) {
709e77f4e7fSDoug Moore 		KASSERT(m->order == VM_NFREEORDER,
710e77f4e7fSDoug Moore 		    ("%s: page %p has unexpected order %d",
711e77f4e7fSDoug Moore 		    __func__, m, m->order));
712e77f4e7fSDoug Moore                 order = fls(npages) - 1;
713e77f4e7fSDoug Moore 		KASSERT(order < VM_NFREEORDER,
714e77f4e7fSDoug Moore 		    ("%s: order %d is out of range", __func__, order));
715e77f4e7fSDoug Moore                 vm_freelist_add(fl, m, order, tail);
716e77f4e7fSDoug Moore 		m += 1 << order;
717e77f4e7fSDoug Moore                 npages -= 1 << order;
718e77f4e7fSDoug Moore         }
719e77f4e7fSDoug Moore }
720e77f4e7fSDoug Moore 
721e77f4e7fSDoug Moore /*
7227493904eSAlan Cox  * Add the physical pages [m, m + npages) at the end of a power-of-two aligned
7237493904eSAlan Cox  * and sized set to the specified free list.
7247493904eSAlan Cox  *
7257493904eSAlan Cox  * When this function is called by a page allocation function, the caller
7267493904eSAlan Cox  * should request insertion at the head unless the lower-order queues are
7277493904eSAlan Cox  * known to be empty.  The objective being to reduce the likelihood of long-
7287493904eSAlan Cox  * term fragmentation by promoting contemporaneous allocation and (hopefully)
7297493904eSAlan Cox  * deallocation.
7307493904eSAlan Cox  *
731ccdb2827SDoug Moore  * If npages is zero, this function does nothing and ignores the physical page
732ccdb2827SDoug Moore  * parameter m.  Otherwise, the physical page m's buddy must not be free.
7337493904eSAlan Cox  */
734c9b06fa5SDoug Moore static vm_page_t
7357493904eSAlan Cox vm_phys_enq_range(vm_page_t m, u_int npages, struct vm_freelist *fl, int tail)
7367493904eSAlan Cox {
7377493904eSAlan Cox 	int order;
7387493904eSAlan Cox 
739ccdb2827SDoug Moore 	KASSERT(npages == 0 ||
740ccdb2827SDoug Moore 	    ((VM_PAGE_TO_PHYS(m) + npages * PAGE_SIZE) &
741ccdb2827SDoug Moore 	    ((PAGE_SIZE << (fls(npages) - 1)) - 1)) == 0,
7427493904eSAlan Cox 	    ("vm_phys_enq_range: page %p and npages %u are misaligned",
7437493904eSAlan Cox 	    m, npages));
744c9b06fa5SDoug Moore 	while (npages > 0) {
7457493904eSAlan Cox 		KASSERT(m->order == VM_NFREEORDER,
7467493904eSAlan Cox 		    ("vm_phys_enq_range: page %p has unexpected order %d",
7477493904eSAlan Cox 		    m, m->order));
7487493904eSAlan Cox 		order = ffs(npages) - 1;
7497493904eSAlan Cox 		KASSERT(order < VM_NFREEORDER,
7507493904eSAlan Cox 		    ("vm_phys_enq_range: order %d is out of range", order));
7517493904eSAlan Cox 		vm_freelist_add(fl, m, order, tail);
752c9b06fa5SDoug Moore 		m += 1 << order;
753c9b06fa5SDoug Moore 		npages -= 1 << order;
754c9b06fa5SDoug Moore 	}
755c9b06fa5SDoug Moore 	return (m);
7567493904eSAlan Cox }
7577493904eSAlan Cox 
7587493904eSAlan Cox /*
7598119cdd3SDoug Moore  * Set the pool for a contiguous, power of two-sized set of physical pages.
7608119cdd3SDoug Moore  */
7618119cdd3SDoug Moore static void
7628119cdd3SDoug Moore vm_phys_set_pool(int pool, vm_page_t m, int order)
7638119cdd3SDoug Moore {
7648119cdd3SDoug Moore 	vm_page_t m_tmp;
7658119cdd3SDoug Moore 
7668119cdd3SDoug Moore 	for (m_tmp = m; m_tmp < &m[1 << order]; m_tmp++)
7678119cdd3SDoug Moore 		m_tmp->pool = pool;
7688119cdd3SDoug Moore }
7698119cdd3SDoug Moore 
7708119cdd3SDoug Moore /*
77189ea39a7SAlan Cox  * Tries to allocate the specified number of pages from the specified pool
77289ea39a7SAlan Cox  * within the specified domain.  Returns the actual number of allocated pages
77389ea39a7SAlan Cox  * and a pointer to each page through the array ma[].
77489ea39a7SAlan Cox  *
77532d81f21SAlan Cox  * The returned pages may not be physically contiguous.  However, in contrast
77632d81f21SAlan Cox  * to performing multiple, back-to-back calls to vm_phys_alloc_pages(..., 0),
77732d81f21SAlan Cox  * calling this function once to allocate the desired number of pages will
77832d81f21SAlan Cox  * avoid wasted time in vm_phys_split_pages().
77989ea39a7SAlan Cox  *
78089ea39a7SAlan Cox  * The free page queues for the specified domain must be locked.
78189ea39a7SAlan Cox  */
78289ea39a7SAlan Cox int
78389ea39a7SAlan Cox vm_phys_alloc_npages(int domain, int pool, int npages, vm_page_t ma[])
78489ea39a7SAlan Cox {
78589ea39a7SAlan Cox 	struct vm_freelist *alt, *fl;
78689ea39a7SAlan Cox 	vm_page_t m;
787c9b06fa5SDoug Moore 	int avail, end, flind, freelist, i, oind, pind;
78889ea39a7SAlan Cox 
78989ea39a7SAlan Cox 	KASSERT(domain >= 0 && domain < vm_ndomains,
79089ea39a7SAlan Cox 	    ("vm_phys_alloc_npages: domain %d is out of range", domain));
79189ea39a7SAlan Cox 	KASSERT(pool < VM_NFREEPOOL,
79289ea39a7SAlan Cox 	    ("vm_phys_alloc_npages: pool %d is out of range", pool));
79389ea39a7SAlan Cox 	KASSERT(npages <= 1 << (VM_NFREEORDER - 1),
79489ea39a7SAlan Cox 	    ("vm_phys_alloc_npages: npages %d is out of range", npages));
79589ea39a7SAlan Cox 	vm_domain_free_assert_locked(VM_DOMAIN(domain));
79689ea39a7SAlan Cox 	i = 0;
79789ea39a7SAlan Cox 	for (freelist = 0; freelist < VM_NFREELIST; freelist++) {
79889ea39a7SAlan Cox 		flind = vm_freelist_to_flind[freelist];
79989ea39a7SAlan Cox 		if (flind < 0)
80089ea39a7SAlan Cox 			continue;
80189ea39a7SAlan Cox 		fl = vm_phys_free_queues[domain][flind][pool];
80289ea39a7SAlan Cox 		for (oind = 0; oind < VM_NFREEORDER; oind++) {
80389ea39a7SAlan Cox 			while ((m = TAILQ_FIRST(&fl[oind].pl)) != NULL) {
80489ea39a7SAlan Cox 				vm_freelist_rem(fl, m, oind);
805c9b06fa5SDoug Moore 				avail = i + (1 << oind);
806c9b06fa5SDoug Moore 				end = imin(npages, avail);
807c9b06fa5SDoug Moore 				while (i < end)
80889ea39a7SAlan Cox 					ma[i++] = m++;
809c9b06fa5SDoug Moore 				if (i == npages) {
8107493904eSAlan Cox 					/*
811c9b06fa5SDoug Moore 					 * Return excess pages to fl.  Its order
812c9b06fa5SDoug Moore 					 * [0, oind) queues are empty.
8137493904eSAlan Cox 					 */
814c9b06fa5SDoug Moore 					vm_phys_enq_range(m, avail - i, fl, 1);
81589ea39a7SAlan Cox 					return (npages);
816c9b06fa5SDoug Moore 				}
81789ea39a7SAlan Cox 			}
81889ea39a7SAlan Cox 		}
81989ea39a7SAlan Cox 		for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
82089ea39a7SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
82189ea39a7SAlan Cox 				alt = vm_phys_free_queues[domain][flind][pind];
82289ea39a7SAlan Cox 				while ((m = TAILQ_FIRST(&alt[oind].pl)) !=
82389ea39a7SAlan Cox 				    NULL) {
82489ea39a7SAlan Cox 					vm_freelist_rem(alt, m, oind);
82589ea39a7SAlan Cox 					vm_phys_set_pool(pool, m, oind);
826c9b06fa5SDoug Moore 					avail = i + (1 << oind);
827c9b06fa5SDoug Moore 					end = imin(npages, avail);
828c9b06fa5SDoug Moore 					while (i < end)
82989ea39a7SAlan Cox 						ma[i++] = m++;
830c9b06fa5SDoug Moore 					if (i == npages) {
8317493904eSAlan Cox 						/*
8327493904eSAlan Cox 						 * Return excess pages to fl.
8337493904eSAlan Cox 						 * Its order [0, oind) queues
8347493904eSAlan Cox 						 * are empty.
8357493904eSAlan Cox 						 */
836c9b06fa5SDoug Moore 						vm_phys_enq_range(m, avail - i,
837c9b06fa5SDoug Moore 						    fl, 1);
83889ea39a7SAlan Cox 						return (npages);
839c9b06fa5SDoug Moore 					}
84089ea39a7SAlan Cox 				}
84189ea39a7SAlan Cox 			}
84289ea39a7SAlan Cox 		}
84389ea39a7SAlan Cox 	}
84489ea39a7SAlan Cox 	return (i);
84589ea39a7SAlan Cox }
84689ea39a7SAlan Cox 
84789ea39a7SAlan Cox /*
84811752d88SAlan Cox  * Allocate a contiguous, power of two-sized set of physical pages
84911752d88SAlan Cox  * from the free lists.
8508941dc44SAlan Cox  *
8518941dc44SAlan Cox  * The free page queues must be locked.
85211752d88SAlan Cox  */
85311752d88SAlan Cox vm_page_t
854ef435ae7SJeff Roberson vm_phys_alloc_pages(int domain, int pool, int order)
85511752d88SAlan Cox {
85649ca10d4SJayachandran C. 	vm_page_t m;
8570db2102aSMichael Zhilin 	int freelist;
85849ca10d4SJayachandran C. 
8590db2102aSMichael Zhilin 	for (freelist = 0; freelist < VM_NFREELIST; freelist++) {
8600db2102aSMichael Zhilin 		m = vm_phys_alloc_freelist_pages(domain, freelist, pool, order);
86149ca10d4SJayachandran C. 		if (m != NULL)
86249ca10d4SJayachandran C. 			return (m);
86349ca10d4SJayachandran C. 	}
86449ca10d4SJayachandran C. 	return (NULL);
86549ca10d4SJayachandran C. }
86649ca10d4SJayachandran C. 
86749ca10d4SJayachandran C. /*
868d866a563SAlan Cox  * Allocate a contiguous, power of two-sized set of physical pages from the
869d866a563SAlan Cox  * specified free list.  The free list must be specified using one of the
870d866a563SAlan Cox  * manifest constants VM_FREELIST_*.
871d866a563SAlan Cox  *
872d866a563SAlan Cox  * The free page queues must be locked.
87349ca10d4SJayachandran C.  */
87449ca10d4SJayachandran C. vm_page_t
8750db2102aSMichael Zhilin vm_phys_alloc_freelist_pages(int domain, int freelist, int pool, int order)
87649ca10d4SJayachandran C. {
877ef435ae7SJeff Roberson 	struct vm_freelist *alt, *fl;
87811752d88SAlan Cox 	vm_page_t m;
8790db2102aSMichael Zhilin 	int oind, pind, flind;
88011752d88SAlan Cox 
881ef435ae7SJeff Roberson 	KASSERT(domain >= 0 && domain < vm_ndomains,
882ef435ae7SJeff Roberson 	    ("vm_phys_alloc_freelist_pages: domain %d is out of range",
883ef435ae7SJeff Roberson 	    domain));
8840db2102aSMichael Zhilin 	KASSERT(freelist < VM_NFREELIST,
885d866a563SAlan Cox 	    ("vm_phys_alloc_freelist_pages: freelist %d is out of range",
8865be93778SAndrew Turner 	    freelist));
88711752d88SAlan Cox 	KASSERT(pool < VM_NFREEPOOL,
88849ca10d4SJayachandran C. 	    ("vm_phys_alloc_freelist_pages: pool %d is out of range", pool));
88911752d88SAlan Cox 	KASSERT(order < VM_NFREEORDER,
89049ca10d4SJayachandran C. 	    ("vm_phys_alloc_freelist_pages: order %d is out of range", order));
8916520495aSAdrian Chadd 
8920db2102aSMichael Zhilin 	flind = vm_freelist_to_flind[freelist];
8930db2102aSMichael Zhilin 	/* Check if freelist is present */
8940db2102aSMichael Zhilin 	if (flind < 0)
8950db2102aSMichael Zhilin 		return (NULL);
8960db2102aSMichael Zhilin 
897e2068d0bSJeff Roberson 	vm_domain_free_assert_locked(VM_DOMAIN(domain));
8987e226537SAttilio Rao 	fl = &vm_phys_free_queues[domain][flind][pool][0];
89911752d88SAlan Cox 	for (oind = order; oind < VM_NFREEORDER; oind++) {
90011752d88SAlan Cox 		m = TAILQ_FIRST(&fl[oind].pl);
90111752d88SAlan Cox 		if (m != NULL) {
9027e226537SAttilio Rao 			vm_freelist_rem(fl, m, oind);
903370a338aSAlan Cox 			/* The order [order, oind) queues are empty. */
904370a338aSAlan Cox 			vm_phys_split_pages(m, oind, fl, order, 1);
90511752d88SAlan Cox 			return (m);
90611752d88SAlan Cox 		}
90711752d88SAlan Cox 	}
90811752d88SAlan Cox 
90911752d88SAlan Cox 	/*
91011752d88SAlan Cox 	 * The given pool was empty.  Find the largest
91111752d88SAlan Cox 	 * contiguous, power-of-two-sized set of pages in any
91211752d88SAlan Cox 	 * pool.  Transfer these pages to the given pool, and
91311752d88SAlan Cox 	 * use them to satisfy the allocation.
91411752d88SAlan Cox 	 */
91511752d88SAlan Cox 	for (oind = VM_NFREEORDER - 1; oind >= order; oind--) {
91611752d88SAlan Cox 		for (pind = 0; pind < VM_NFREEPOOL; pind++) {
9177e226537SAttilio Rao 			alt = &vm_phys_free_queues[domain][flind][pind][0];
91811752d88SAlan Cox 			m = TAILQ_FIRST(&alt[oind].pl);
91911752d88SAlan Cox 			if (m != NULL) {
9207e226537SAttilio Rao 				vm_freelist_rem(alt, m, oind);
92111752d88SAlan Cox 				vm_phys_set_pool(pool, m, oind);
922370a338aSAlan Cox 				/* The order [order, oind) queues are empty. */
923370a338aSAlan Cox 				vm_phys_split_pages(m, oind, fl, order, 1);
92411752d88SAlan Cox 				return (m);
92511752d88SAlan Cox 			}
92611752d88SAlan Cox 		}
92711752d88SAlan Cox 	}
92811752d88SAlan Cox 	return (NULL);
92911752d88SAlan Cox }
93011752d88SAlan Cox 
93111752d88SAlan Cox /*
93211752d88SAlan Cox  * Find the vm_page corresponding to the given physical address.
93311752d88SAlan Cox  */
93411752d88SAlan Cox vm_page_t
93511752d88SAlan Cox vm_phys_paddr_to_vm_page(vm_paddr_t pa)
93611752d88SAlan Cox {
93711752d88SAlan Cox 	struct vm_phys_seg *seg;
93811752d88SAlan Cox 
9399e817428SDoug Moore 	if ((seg = vm_phys_paddr_to_seg(pa)) != NULL)
94011752d88SAlan Cox 		return (&seg->first_page[atop(pa - seg->start)]);
941f06a3a36SAndrew Thompson 	return (NULL);
94211752d88SAlan Cox }
94311752d88SAlan Cox 
944b6de32bdSKonstantin Belousov vm_page_t
945b6de32bdSKonstantin Belousov vm_phys_fictitious_to_vm_page(vm_paddr_t pa)
946b6de32bdSKonstantin Belousov {
94738d6b2dcSRoger Pau Monné 	struct vm_phys_fictitious_seg tmp, *seg;
948b6de32bdSKonstantin Belousov 	vm_page_t m;
949b6de32bdSKonstantin Belousov 
950b6de32bdSKonstantin Belousov 	m = NULL;
95138d6b2dcSRoger Pau Monné 	tmp.start = pa;
95238d6b2dcSRoger Pau Monné 	tmp.end = 0;
95338d6b2dcSRoger Pau Monné 
95438d6b2dcSRoger Pau Monné 	rw_rlock(&vm_phys_fictitious_reg_lock);
95538d6b2dcSRoger Pau Monné 	seg = RB_FIND(fict_tree, &vm_phys_fictitious_tree, &tmp);
95638d6b2dcSRoger Pau Monné 	rw_runlock(&vm_phys_fictitious_reg_lock);
95738d6b2dcSRoger Pau Monné 	if (seg == NULL)
95838d6b2dcSRoger Pau Monné 		return (NULL);
95938d6b2dcSRoger Pau Monné 
960b6de32bdSKonstantin Belousov 	m = &seg->first_page[atop(pa - seg->start)];
96138d6b2dcSRoger Pau Monné 	KASSERT((m->flags & PG_FICTITIOUS) != 0, ("%p not fictitious", m));
96238d6b2dcSRoger Pau Monné 
963b6de32bdSKonstantin Belousov 	return (m);
964b6de32bdSKonstantin Belousov }
965b6de32bdSKonstantin Belousov 
9665ebe728dSRoger Pau Monné static inline void
9675ebe728dSRoger Pau Monné vm_phys_fictitious_init_range(vm_page_t range, vm_paddr_t start,
9685ebe728dSRoger Pau Monné     long page_count, vm_memattr_t memattr)
9695ebe728dSRoger Pau Monné {
9705ebe728dSRoger Pau Monné 	long i;
9715ebe728dSRoger Pau Monné 
972f93f7cf1SMark Johnston 	bzero(range, page_count * sizeof(*range));
9735ebe728dSRoger Pau Monné 	for (i = 0; i < page_count; i++) {
9745ebe728dSRoger Pau Monné 		vm_page_initfake(&range[i], start + PAGE_SIZE * i, memattr);
9755ebe728dSRoger Pau Monné 		range[i].oflags &= ~VPO_UNMANAGED;
9765ebe728dSRoger Pau Monné 		range[i].busy_lock = VPB_UNBUSIED;
9775ebe728dSRoger Pau Monné 	}
9785ebe728dSRoger Pau Monné }
9795ebe728dSRoger Pau Monné 
980b6de32bdSKonstantin Belousov int
981b6de32bdSKonstantin Belousov vm_phys_fictitious_reg_range(vm_paddr_t start, vm_paddr_t end,
982b6de32bdSKonstantin Belousov     vm_memattr_t memattr)
983b6de32bdSKonstantin Belousov {
984b6de32bdSKonstantin Belousov 	struct vm_phys_fictitious_seg *seg;
985b6de32bdSKonstantin Belousov 	vm_page_t fp;
9865ebe728dSRoger Pau Monné 	long page_count;
987b6de32bdSKonstantin Belousov #ifdef VM_PHYSSEG_DENSE
9885ebe728dSRoger Pau Monné 	long pi, pe;
9895ebe728dSRoger Pau Monné 	long dpage_count;
990b6de32bdSKonstantin Belousov #endif
991b6de32bdSKonstantin Belousov 
9925ebe728dSRoger Pau Monné 	KASSERT(start < end,
9935ebe728dSRoger Pau Monné 	    ("Start of segment isn't less than end (start: %jx end: %jx)",
9945ebe728dSRoger Pau Monné 	    (uintmax_t)start, (uintmax_t)end));
9955ebe728dSRoger Pau Monné 
996b6de32bdSKonstantin Belousov 	page_count = (end - start) / PAGE_SIZE;
997b6de32bdSKonstantin Belousov 
998b6de32bdSKonstantin Belousov #ifdef VM_PHYSSEG_DENSE
999b6de32bdSKonstantin Belousov 	pi = atop(start);
10005ebe728dSRoger Pau Monné 	pe = atop(end);
10015ebe728dSRoger Pau Monné 	if (pi >= first_page && (pi - first_page) < vm_page_array_size) {
1002b6de32bdSKonstantin Belousov 		fp = &vm_page_array[pi - first_page];
10035ebe728dSRoger Pau Monné 		if ((pe - first_page) > vm_page_array_size) {
10045ebe728dSRoger Pau Monné 			/*
10055ebe728dSRoger Pau Monné 			 * We have a segment that starts inside
10065ebe728dSRoger Pau Monné 			 * of vm_page_array, but ends outside of it.
10075ebe728dSRoger Pau Monné 			 *
10085ebe728dSRoger Pau Monné 			 * Use vm_page_array pages for those that are
10095ebe728dSRoger Pau Monné 			 * inside of the vm_page_array range, and
10105ebe728dSRoger Pau Monné 			 * allocate the remaining ones.
10115ebe728dSRoger Pau Monné 			 */
10125ebe728dSRoger Pau Monné 			dpage_count = vm_page_array_size - (pi - first_page);
10135ebe728dSRoger Pau Monné 			vm_phys_fictitious_init_range(fp, start, dpage_count,
10145ebe728dSRoger Pau Monné 			    memattr);
10155ebe728dSRoger Pau Monné 			page_count -= dpage_count;
10165ebe728dSRoger Pau Monné 			start += ptoa(dpage_count);
10175ebe728dSRoger Pau Monné 			goto alloc;
10185ebe728dSRoger Pau Monné 		}
10195ebe728dSRoger Pau Monné 		/*
10205ebe728dSRoger Pau Monné 		 * We can allocate the full range from vm_page_array,
10215ebe728dSRoger Pau Monné 		 * so there's no need to register the range in the tree.
10225ebe728dSRoger Pau Monné 		 */
10235ebe728dSRoger Pau Monné 		vm_phys_fictitious_init_range(fp, start, page_count, memattr);
10245ebe728dSRoger Pau Monné 		return (0);
10255ebe728dSRoger Pau Monné 	} else if (pe > first_page && (pe - first_page) < vm_page_array_size) {
10265ebe728dSRoger Pau Monné 		/*
10275ebe728dSRoger Pau Monné 		 * We have a segment that ends inside of vm_page_array,
10285ebe728dSRoger Pau Monné 		 * but starts outside of it.
10295ebe728dSRoger Pau Monné 		 */
10305ebe728dSRoger Pau Monné 		fp = &vm_page_array[0];
10315ebe728dSRoger Pau Monné 		dpage_count = pe - first_page;
10325ebe728dSRoger Pau Monné 		vm_phys_fictitious_init_range(fp, ptoa(first_page), dpage_count,
10335ebe728dSRoger Pau Monné 		    memattr);
10345ebe728dSRoger Pau Monné 		end -= ptoa(dpage_count);
10355ebe728dSRoger Pau Monné 		page_count -= dpage_count;
10365ebe728dSRoger Pau Monné 		goto alloc;
10375ebe728dSRoger Pau Monné 	} else if (pi < first_page && pe > (first_page + vm_page_array_size)) {
10385ebe728dSRoger Pau Monné 		/*
10395ebe728dSRoger Pau Monné 		 * Trying to register a fictitious range that expands before
10405ebe728dSRoger Pau Monné 		 * and after vm_page_array.
10415ebe728dSRoger Pau Monné 		 */
10425ebe728dSRoger Pau Monné 		return (EINVAL);
10435ebe728dSRoger Pau Monné 	} else {
10445ebe728dSRoger Pau Monné alloc:
1045b6de32bdSKonstantin Belousov #endif
1046b6de32bdSKonstantin Belousov 		fp = malloc(page_count * sizeof(struct vm_page), M_FICT_PAGES,
1047f93f7cf1SMark Johnston 		    M_WAITOK);
10485ebe728dSRoger Pau Monné #ifdef VM_PHYSSEG_DENSE
1049b6de32bdSKonstantin Belousov 	}
10505ebe728dSRoger Pau Monné #endif
10515ebe728dSRoger Pau Monné 	vm_phys_fictitious_init_range(fp, start, page_count, memattr);
105238d6b2dcSRoger Pau Monné 
105338d6b2dcSRoger Pau Monné 	seg = malloc(sizeof(*seg), M_FICT_PAGES, M_WAITOK | M_ZERO);
1054b6de32bdSKonstantin Belousov 	seg->start = start;
1055b6de32bdSKonstantin Belousov 	seg->end = end;
1056b6de32bdSKonstantin Belousov 	seg->first_page = fp;
105738d6b2dcSRoger Pau Monné 
105838d6b2dcSRoger Pau Monné 	rw_wlock(&vm_phys_fictitious_reg_lock);
105938d6b2dcSRoger Pau Monné 	RB_INSERT(fict_tree, &vm_phys_fictitious_tree, seg);
106038d6b2dcSRoger Pau Monné 	rw_wunlock(&vm_phys_fictitious_reg_lock);
106138d6b2dcSRoger Pau Monné 
1062b6de32bdSKonstantin Belousov 	return (0);
1063b6de32bdSKonstantin Belousov }
1064b6de32bdSKonstantin Belousov 
1065b6de32bdSKonstantin Belousov void
1066b6de32bdSKonstantin Belousov vm_phys_fictitious_unreg_range(vm_paddr_t start, vm_paddr_t end)
1067b6de32bdSKonstantin Belousov {
106838d6b2dcSRoger Pau Monné 	struct vm_phys_fictitious_seg *seg, tmp;
1069b6de32bdSKonstantin Belousov #ifdef VM_PHYSSEG_DENSE
10705ebe728dSRoger Pau Monné 	long pi, pe;
1071b6de32bdSKonstantin Belousov #endif
1072b6de32bdSKonstantin Belousov 
10735ebe728dSRoger Pau Monné 	KASSERT(start < end,
10745ebe728dSRoger Pau Monné 	    ("Start of segment isn't less than end (start: %jx end: %jx)",
10755ebe728dSRoger Pau Monné 	    (uintmax_t)start, (uintmax_t)end));
10765ebe728dSRoger Pau Monné 
1077b6de32bdSKonstantin Belousov #ifdef VM_PHYSSEG_DENSE
1078b6de32bdSKonstantin Belousov 	pi = atop(start);
10795ebe728dSRoger Pau Monné 	pe = atop(end);
10805ebe728dSRoger Pau Monné 	if (pi >= first_page && (pi - first_page) < vm_page_array_size) {
10815ebe728dSRoger Pau Monné 		if ((pe - first_page) <= vm_page_array_size) {
10825ebe728dSRoger Pau Monné 			/*
10835ebe728dSRoger Pau Monné 			 * This segment was allocated using vm_page_array
10845ebe728dSRoger Pau Monné 			 * only, there's nothing to do since those pages
10855ebe728dSRoger Pau Monné 			 * were never added to the tree.
10865ebe728dSRoger Pau Monné 			 */
10875ebe728dSRoger Pau Monné 			return;
10885ebe728dSRoger Pau Monné 		}
10895ebe728dSRoger Pau Monné 		/*
10905ebe728dSRoger Pau Monné 		 * We have a segment that starts inside
10915ebe728dSRoger Pau Monné 		 * of vm_page_array, but ends outside of it.
10925ebe728dSRoger Pau Monné 		 *
10935ebe728dSRoger Pau Monné 		 * Calculate how many pages were added to the
10945ebe728dSRoger Pau Monné 		 * tree and free them.
10955ebe728dSRoger Pau Monné 		 */
10965ebe728dSRoger Pau Monné 		start = ptoa(first_page + vm_page_array_size);
10975ebe728dSRoger Pau Monné 	} else if (pe > first_page && (pe - first_page) < vm_page_array_size) {
10985ebe728dSRoger Pau Monné 		/*
10995ebe728dSRoger Pau Monné 		 * We have a segment that ends inside of vm_page_array,
11005ebe728dSRoger Pau Monné 		 * but starts outside of it.
11015ebe728dSRoger Pau Monné 		 */
11025ebe728dSRoger Pau Monné 		end = ptoa(first_page);
11035ebe728dSRoger Pau Monné 	} else if (pi < first_page && pe > (first_page + vm_page_array_size)) {
11045ebe728dSRoger Pau Monné 		/* Since it's not possible to register such a range, panic. */
11055ebe728dSRoger Pau Monné 		panic(
11065ebe728dSRoger Pau Monné 		    "Unregistering not registered fictitious range [%#jx:%#jx]",
11075ebe728dSRoger Pau Monné 		    (uintmax_t)start, (uintmax_t)end);
11085ebe728dSRoger Pau Monné 	}
1109b6de32bdSKonstantin Belousov #endif
111038d6b2dcSRoger Pau Monné 	tmp.start = start;
111138d6b2dcSRoger Pau Monné 	tmp.end = 0;
1112b6de32bdSKonstantin Belousov 
111338d6b2dcSRoger Pau Monné 	rw_wlock(&vm_phys_fictitious_reg_lock);
111438d6b2dcSRoger Pau Monné 	seg = RB_FIND(fict_tree, &vm_phys_fictitious_tree, &tmp);
111538d6b2dcSRoger Pau Monné 	if (seg->start != start || seg->end != end) {
111638d6b2dcSRoger Pau Monné 		rw_wunlock(&vm_phys_fictitious_reg_lock);
111738d6b2dcSRoger Pau Monné 		panic(
111838d6b2dcSRoger Pau Monné 		    "Unregistering not registered fictitious range [%#jx:%#jx]",
111938d6b2dcSRoger Pau Monné 		    (uintmax_t)start, (uintmax_t)end);
112038d6b2dcSRoger Pau Monné 	}
112138d6b2dcSRoger Pau Monné 	RB_REMOVE(fict_tree, &vm_phys_fictitious_tree, seg);
112238d6b2dcSRoger Pau Monné 	rw_wunlock(&vm_phys_fictitious_reg_lock);
112338d6b2dcSRoger Pau Monné 	free(seg->first_page, M_FICT_PAGES);
112438d6b2dcSRoger Pau Monné 	free(seg, M_FICT_PAGES);
1125b6de32bdSKonstantin Belousov }
1126b6de32bdSKonstantin Belousov 
112711752d88SAlan Cox /*
112811752d88SAlan Cox  * Free a contiguous, power of two-sized set of physical pages.
11298941dc44SAlan Cox  *
11308941dc44SAlan Cox  * The free page queues must be locked.
113111752d88SAlan Cox  */
113211752d88SAlan Cox void
113311752d88SAlan Cox vm_phys_free_pages(vm_page_t m, int order)
113411752d88SAlan Cox {
113511752d88SAlan Cox 	struct vm_freelist *fl;
113611752d88SAlan Cox 	struct vm_phys_seg *seg;
11375c1f2cc4SAlan Cox 	vm_paddr_t pa;
113811752d88SAlan Cox 	vm_page_t m_buddy;
113911752d88SAlan Cox 
114011752d88SAlan Cox 	KASSERT(m->order == VM_NFREEORDER,
11413921068fSJeff Roberson 	    ("vm_phys_free_pages: page %p has unexpected order %d",
11423921068fSJeff Roberson 	    m, m->order));
114311752d88SAlan Cox 	KASSERT(m->pool < VM_NFREEPOOL,
11448941dc44SAlan Cox 	    ("vm_phys_free_pages: page %p has unexpected pool %d",
114511752d88SAlan Cox 	    m, m->pool));
114611752d88SAlan Cox 	KASSERT(order < VM_NFREEORDER,
11478941dc44SAlan Cox 	    ("vm_phys_free_pages: order %d is out of range", order));
114811752d88SAlan Cox 	seg = &vm_phys_segs[m->segind];
1149e2068d0bSJeff Roberson 	vm_domain_free_assert_locked(VM_DOMAIN(seg->domain));
11505c1f2cc4SAlan Cox 	if (order < VM_NFREEORDER - 1) {
11515c1f2cc4SAlan Cox 		pa = VM_PAGE_TO_PHYS(m);
11525c1f2cc4SAlan Cox 		do {
11535c1f2cc4SAlan Cox 			pa ^= ((vm_paddr_t)1 << (PAGE_SHIFT + order));
11545c1f2cc4SAlan Cox 			if (pa < seg->start || pa >= seg->end)
115511752d88SAlan Cox 				break;
11565c1f2cc4SAlan Cox 			m_buddy = &seg->first_page[atop(pa - seg->start)];
115711752d88SAlan Cox 			if (m_buddy->order != order)
115811752d88SAlan Cox 				break;
115911752d88SAlan Cox 			fl = (*seg->free_queues)[m_buddy->pool];
11607e226537SAttilio Rao 			vm_freelist_rem(fl, m_buddy, order);
116111752d88SAlan Cox 			if (m_buddy->pool != m->pool)
116211752d88SAlan Cox 				vm_phys_set_pool(m->pool, m_buddy, order);
116311752d88SAlan Cox 			order++;
11645c1f2cc4SAlan Cox 			pa &= ~(((vm_paddr_t)1 << (PAGE_SHIFT + order)) - 1);
116511752d88SAlan Cox 			m = &seg->first_page[atop(pa - seg->start)];
11665c1f2cc4SAlan Cox 		} while (order < VM_NFREEORDER - 1);
116711752d88SAlan Cox 	}
116811752d88SAlan Cox 	fl = (*seg->free_queues)[m->pool];
11697e226537SAttilio Rao 	vm_freelist_add(fl, m, order, 1);
117011752d88SAlan Cox }
117111752d88SAlan Cox 
117211752d88SAlan Cox /*
1173b8590daeSDoug Moore  * Return the largest possible order of a set of pages starting at m.
11745c1f2cc4SAlan Cox  */
1175b8590daeSDoug Moore static int
1176b8590daeSDoug Moore max_order(vm_page_t m)
11775c1f2cc4SAlan Cox {
11785c1f2cc4SAlan Cox 
11795c1f2cc4SAlan Cox 	/*
11805c1f2cc4SAlan Cox 	 * Unsigned "min" is used here so that "order" is assigned
11815c1f2cc4SAlan Cox 	 * "VM_NFREEORDER - 1" when "m"'s physical address is zero
11825c1f2cc4SAlan Cox 	 * or the low-order bits of its physical address are zero
11835c1f2cc4SAlan Cox 	 * because the size of a physical address exceeds the size of
11845c1f2cc4SAlan Cox 	 * a long.
11855c1f2cc4SAlan Cox 	 */
1186c9b06fa5SDoug Moore 	return (min(ffsll(VM_PAGE_TO_PHYS(m) >> PAGE_SHIFT) - 1,
1187b8590daeSDoug Moore 	    VM_NFREEORDER - 1));
11885c1f2cc4SAlan Cox }
1189b8590daeSDoug Moore 
1190b8590daeSDoug Moore /*
1191b8590daeSDoug Moore  * Free a contiguous, arbitrarily sized set of physical pages, without
1192b8590daeSDoug Moore  * merging across set boundaries.
1193b8590daeSDoug Moore  *
1194b8590daeSDoug Moore  * The free page queues must be locked.
1195b8590daeSDoug Moore  */
1196b8590daeSDoug Moore void
1197b8590daeSDoug Moore vm_phys_enqueue_contig(vm_page_t m, u_long npages)
1198b8590daeSDoug Moore {
1199b8590daeSDoug Moore 	struct vm_freelist *fl;
1200b8590daeSDoug Moore 	struct vm_phys_seg *seg;
1201b8590daeSDoug Moore 	vm_page_t m_end;
1202c9b06fa5SDoug Moore 	vm_paddr_t diff, lo;
1203b8590daeSDoug Moore 	int order;
1204b8590daeSDoug Moore 
1205b8590daeSDoug Moore 	/*
1206b8590daeSDoug Moore 	 * Avoid unnecessary coalescing by freeing the pages in the largest
1207b8590daeSDoug Moore 	 * possible power-of-two-sized subsets.
1208b8590daeSDoug Moore 	 */
1209b8590daeSDoug Moore 	vm_domain_free_assert_locked(vm_pagequeue_domain(m));
1210b8590daeSDoug Moore 	seg = &vm_phys_segs[m->segind];
1211b8590daeSDoug Moore 	fl = (*seg->free_queues)[m->pool];
1212b8590daeSDoug Moore 	m_end = m + npages;
1213b8590daeSDoug Moore 	/* Free blocks of increasing size. */
1214c9b06fa5SDoug Moore 	lo = VM_PAGE_TO_PHYS(m) >> PAGE_SHIFT;
1215c9b06fa5SDoug Moore 	if (m < m_end &&
1216c9b06fa5SDoug Moore 	    (diff = lo ^ (lo + npages - 1)) != 0) {
1217c9b06fa5SDoug Moore 		order = min(flsll(diff) - 1, VM_NFREEORDER - 1);
1218c9b06fa5SDoug Moore 		m = vm_phys_enq_range(m, roundup2(lo, 1 << order) - lo, fl, 1);
12195c1f2cc4SAlan Cox 	}
1220c9b06fa5SDoug Moore 
1221b8590daeSDoug Moore 	/* Free blocks of maximum size. */
1222c9b06fa5SDoug Moore 	order = VM_NFREEORDER - 1;
1223b8590daeSDoug Moore 	while (m + (1 << order) <= m_end) {
1224b8590daeSDoug Moore 		KASSERT(seg == &vm_phys_segs[m->segind],
1225b8590daeSDoug Moore 		    ("%s: page range [%p,%p) spans multiple segments",
1226b8590daeSDoug Moore 		    __func__, m_end - npages, m));
1227b8590daeSDoug Moore 		vm_freelist_add(fl, m, order, 1);
1228b8590daeSDoug Moore 		m += 1 << order;
1229b8590daeSDoug Moore 	}
1230b8590daeSDoug Moore 	/* Free blocks of diminishing size. */
1231e77f4e7fSDoug Moore 	vm_phys_enq_beg(m, m_end - m, fl, 1);
1232b8590daeSDoug Moore }
1233b8590daeSDoug Moore 
1234b8590daeSDoug Moore /*
1235b8590daeSDoug Moore  * Free a contiguous, arbitrarily sized set of physical pages.
1236b8590daeSDoug Moore  *
1237b8590daeSDoug Moore  * The free page queues must be locked.
1238b8590daeSDoug Moore  */
1239b8590daeSDoug Moore void
1240b8590daeSDoug Moore vm_phys_free_contig(vm_page_t m, u_long npages)
1241b8590daeSDoug Moore {
1242b8590daeSDoug Moore 	int order_start, order_end;
1243b8590daeSDoug Moore 	vm_page_t m_start, m_end;
1244b8590daeSDoug Moore 
1245b8590daeSDoug Moore 	vm_domain_free_assert_locked(vm_pagequeue_domain(m));
1246b8590daeSDoug Moore 
1247b8590daeSDoug Moore 	m_start = m;
1248b8590daeSDoug Moore 	order_start = max_order(m_start);
1249b8590daeSDoug Moore 	if (order_start < VM_NFREEORDER - 1)
1250b8590daeSDoug Moore 		m_start += 1 << order_start;
1251b8590daeSDoug Moore 	m_end = m + npages;
1252b8590daeSDoug Moore 	order_end = max_order(m_end);
1253b8590daeSDoug Moore 	if (order_end < VM_NFREEORDER - 1)
1254b8590daeSDoug Moore 		m_end -= 1 << order_end;
1255b8590daeSDoug Moore 	/*
1256b8590daeSDoug Moore 	 * Avoid unnecessary coalescing by freeing the pages at the start and
1257b8590daeSDoug Moore 	 * end of the range last.
1258b8590daeSDoug Moore 	 */
1259b8590daeSDoug Moore 	if (m_start < m_end)
1260b8590daeSDoug Moore 		vm_phys_enqueue_contig(m_start, m_end - m_start);
1261b8590daeSDoug Moore 	if (order_start < VM_NFREEORDER - 1)
1262b8590daeSDoug Moore 		vm_phys_free_pages(m, order_start);
1263b8590daeSDoug Moore 	if (order_end < VM_NFREEORDER - 1)
1264b8590daeSDoug Moore 		vm_phys_free_pages(m_end, order_end);
12655c1f2cc4SAlan Cox }
12665c1f2cc4SAlan Cox 
12675c1f2cc4SAlan Cox /*
12689e817428SDoug Moore  * Identify the first address range within segment segind or greater
12699e817428SDoug Moore  * that matches the domain, lies within the low/high range, and has
12709e817428SDoug Moore  * enough pages.  Return -1 if there is none.
1271c869e672SAlan Cox  */
12729e817428SDoug Moore int
12739e817428SDoug Moore vm_phys_find_range(vm_page_t bounds[], int segind, int domain,
12749e817428SDoug Moore     u_long npages, vm_paddr_t low, vm_paddr_t high)
1275c869e672SAlan Cox {
12769e817428SDoug Moore 	vm_paddr_t pa_end, pa_start;
12779e817428SDoug Moore 	struct vm_phys_seg *end_seg, *seg;
1278c869e672SAlan Cox 
12799e817428SDoug Moore 	KASSERT(npages > 0, ("npages is zero"));
128058d42717SAlan Cox 	KASSERT(domain >= 0 && domain < vm_ndomains, ("domain out of range"));
12819e817428SDoug Moore 	end_seg = &vm_phys_segs[vm_phys_nsegs];
12829e817428SDoug Moore 	for (seg = &vm_phys_segs[segind]; seg < end_seg; seg++) {
12833f289c3fSJeff Roberson 		if (seg->domain != domain)
12843f289c3fSJeff Roberson 			continue;
1285c869e672SAlan Cox 		if (seg->start >= high)
12869e817428SDoug Moore 			return (-1);
12879e817428SDoug Moore 		pa_start = MAX(low, seg->start);
12889e817428SDoug Moore 		pa_end = MIN(high, seg->end);
12899e817428SDoug Moore 		if (pa_end - pa_start < ptoa(npages))
1290c869e672SAlan Cox 			continue;
12919e817428SDoug Moore 		bounds[0] = &seg->first_page[atop(pa_start - seg->start)];
12929e817428SDoug Moore 		bounds[1] = &seg->first_page[atop(pa_end - seg->start)];
12939e817428SDoug Moore 		return (seg - vm_phys_segs);
1294c869e672SAlan Cox 	}
12959e817428SDoug Moore 	return (-1);
1296c869e672SAlan Cox }
1297c869e672SAlan Cox 
1298c869e672SAlan Cox /*
12999742373aSAlan Cox  * Search for the given physical page "m" in the free lists.  If the search
13006062d9faSMark Johnston  * succeeds, remove "m" from the free lists and return true.  Otherwise, return
13016062d9faSMark Johnston  * false, indicating that "m" is not in the free lists.
13027bfda801SAlan Cox  *
13037bfda801SAlan Cox  * The free page queues must be locked.
13047bfda801SAlan Cox  */
13056062d9faSMark Johnston bool
13067bfda801SAlan Cox vm_phys_unfree_page(vm_page_t m)
13077bfda801SAlan Cox {
13087bfda801SAlan Cox 	struct vm_freelist *fl;
13097bfda801SAlan Cox 	struct vm_phys_seg *seg;
13107bfda801SAlan Cox 	vm_paddr_t pa, pa_half;
13117bfda801SAlan Cox 	vm_page_t m_set, m_tmp;
13127bfda801SAlan Cox 	int order;
13137bfda801SAlan Cox 
13147bfda801SAlan Cox 	/*
13157bfda801SAlan Cox 	 * First, find the contiguous, power of two-sized set of free
13167bfda801SAlan Cox 	 * physical pages containing the given physical page "m" and
13177bfda801SAlan Cox 	 * assign it to "m_set".
13187bfda801SAlan Cox 	 */
13197bfda801SAlan Cox 	seg = &vm_phys_segs[m->segind];
1320e2068d0bSJeff Roberson 	vm_domain_free_assert_locked(VM_DOMAIN(seg->domain));
13217bfda801SAlan Cox 	for (m_set = m, order = 0; m_set->order == VM_NFREEORDER &&
1322bc8794a1SAlan Cox 	    order < VM_NFREEORDER - 1; ) {
13237bfda801SAlan Cox 		order++;
13247bfda801SAlan Cox 		pa = m->phys_addr & (~(vm_paddr_t)0 << (PAGE_SHIFT + order));
13252fbced65SAlan Cox 		if (pa >= seg->start)
13267bfda801SAlan Cox 			m_set = &seg->first_page[atop(pa - seg->start)];
1327e35395ceSAlan Cox 		else
13286062d9faSMark Johnston 			return (false);
13297bfda801SAlan Cox 	}
1330e35395ceSAlan Cox 	if (m_set->order < order)
13316062d9faSMark Johnston 		return (false);
1332e35395ceSAlan Cox 	if (m_set->order == VM_NFREEORDER)
13336062d9faSMark Johnston 		return (false);
13347bfda801SAlan Cox 	KASSERT(m_set->order < VM_NFREEORDER,
13357bfda801SAlan Cox 	    ("vm_phys_unfree_page: page %p has unexpected order %d",
13367bfda801SAlan Cox 	    m_set, m_set->order));
13377bfda801SAlan Cox 
13387bfda801SAlan Cox 	/*
13397bfda801SAlan Cox 	 * Next, remove "m_set" from the free lists.  Finally, extract
13407bfda801SAlan Cox 	 * "m" from "m_set" using an iterative algorithm: While "m_set"
13417bfda801SAlan Cox 	 * is larger than a page, shrink "m_set" by returning the half
13427bfda801SAlan Cox 	 * of "m_set" that does not contain "m" to the free lists.
13437bfda801SAlan Cox 	 */
13447bfda801SAlan Cox 	fl = (*seg->free_queues)[m_set->pool];
13457bfda801SAlan Cox 	order = m_set->order;
13467e226537SAttilio Rao 	vm_freelist_rem(fl, m_set, order);
13477bfda801SAlan Cox 	while (order > 0) {
13487bfda801SAlan Cox 		order--;
13497bfda801SAlan Cox 		pa_half = m_set->phys_addr ^ (1 << (PAGE_SHIFT + order));
13507bfda801SAlan Cox 		if (m->phys_addr < pa_half)
13517bfda801SAlan Cox 			m_tmp = &seg->first_page[atop(pa_half - seg->start)];
13527bfda801SAlan Cox 		else {
13537bfda801SAlan Cox 			m_tmp = m_set;
13547bfda801SAlan Cox 			m_set = &seg->first_page[atop(pa_half - seg->start)];
13557bfda801SAlan Cox 		}
13567e226537SAttilio Rao 		vm_freelist_add(fl, m_tmp, order, 0);
13577bfda801SAlan Cox 	}
13587bfda801SAlan Cox 	KASSERT(m_set == m, ("vm_phys_unfree_page: fatal inconsistency"));
13596062d9faSMark Johnston 	return (true);
13607bfda801SAlan Cox }
13617bfda801SAlan Cox 
13627bfda801SAlan Cox /*
1363fa8a6585SDoug Moore  * Find a run of contiguous physical pages from the specified page list.
1364fa8a6585SDoug Moore  */
1365fa8a6585SDoug Moore static vm_page_t
1366fa8a6585SDoug Moore vm_phys_find_freelist_contig(struct vm_freelist *fl, int oind, u_long npages,
1367fa8a6585SDoug Moore     vm_paddr_t low, vm_paddr_t high, u_long alignment, vm_paddr_t boundary)
1368fa8a6585SDoug Moore {
1369fa8a6585SDoug Moore 	struct vm_phys_seg *seg;
1370fa8a6585SDoug Moore 	vm_paddr_t frag, lbound, pa, page_size, pa_end, pa_pre, size;
1371fa8a6585SDoug Moore 	vm_page_t m, m_listed, m_ret;
1372fa8a6585SDoug Moore 	int order;
1373fa8a6585SDoug Moore 
1374fa8a6585SDoug Moore 	KASSERT(npages > 0, ("npages is 0"));
1375fa8a6585SDoug Moore 	KASSERT(powerof2(alignment), ("alignment is not a power of 2"));
1376fa8a6585SDoug Moore 	KASSERT(powerof2(boundary), ("boundary is not a power of 2"));
1377fa8a6585SDoug Moore 	/* Search for a run satisfying the specified conditions. */
1378fa8a6585SDoug Moore 	page_size = PAGE_SIZE;
1379fa8a6585SDoug Moore 	size = npages << PAGE_SHIFT;
1380fa8a6585SDoug Moore 	frag = (npages & ~(~0UL << oind)) << PAGE_SHIFT;
1381fa8a6585SDoug Moore 	TAILQ_FOREACH(m_listed, &fl[oind].pl, listq) {
1382fa8a6585SDoug Moore 		/*
1383fa8a6585SDoug Moore 		 * Determine if the address range starting at pa is
1384fa8a6585SDoug Moore 		 * too low.
1385fa8a6585SDoug Moore 		 */
1386fa8a6585SDoug Moore 		pa = VM_PAGE_TO_PHYS(m_listed);
1387fa8a6585SDoug Moore 		if (pa < low)
1388fa8a6585SDoug Moore 			continue;
1389fa8a6585SDoug Moore 
1390fa8a6585SDoug Moore 		/*
1391fa8a6585SDoug Moore 		 * If this is not the first free oind-block in this range, bail
1392fa8a6585SDoug Moore 		 * out. We have seen the first free block already, or will see
1393fa8a6585SDoug Moore 		 * it before failing to find an appropriate range.
1394fa8a6585SDoug Moore 		 */
1395fa8a6585SDoug Moore 		seg = &vm_phys_segs[m_listed->segind];
1396fa8a6585SDoug Moore 		lbound = low > seg->start ? low : seg->start;
1397fa8a6585SDoug Moore 		pa_pre = pa - (page_size << oind);
1398fa8a6585SDoug Moore 		m = &seg->first_page[atop(pa_pre - seg->start)];
1399fa8a6585SDoug Moore 		if (pa != 0 && pa_pre >= lbound && m->order == oind)
1400fa8a6585SDoug Moore 			continue;
1401fa8a6585SDoug Moore 
1402fa8a6585SDoug Moore 		if (!vm_addr_align_ok(pa, alignment))
1403fa8a6585SDoug Moore 			/* Advance to satisfy alignment condition. */
1404fa8a6585SDoug Moore 			pa = roundup2(pa, alignment);
1405fa8a6585SDoug Moore 		else if (frag != 0 && lbound + frag <= pa) {
1406fa8a6585SDoug Moore 			/*
1407fa8a6585SDoug Moore 			 * Back up to the first aligned free block in this
1408fa8a6585SDoug Moore 			 * range, without moving below lbound.
1409fa8a6585SDoug Moore 			 */
1410fa8a6585SDoug Moore 			pa_end = pa;
1411fa8a6585SDoug Moore 			for (order = oind - 1; order >= 0; order--) {
1412fa8a6585SDoug Moore 				pa_pre = pa_end - (page_size << order);
1413fa8a6585SDoug Moore 				if (!vm_addr_align_ok(pa_pre, alignment))
1414fa8a6585SDoug Moore 					break;
1415fa8a6585SDoug Moore 				m = &seg->first_page[atop(pa_pre - seg->start)];
1416fa8a6585SDoug Moore 				if (pa_pre >= lbound && m->order == order)
1417fa8a6585SDoug Moore 					pa_end = pa_pre;
1418fa8a6585SDoug Moore 			}
1419fa8a6585SDoug Moore 			/*
1420fa8a6585SDoug Moore 			 * If the extra small blocks are enough to complete the
1421fa8a6585SDoug Moore 			 * fragment, use them.  Otherwise, look to allocate the
1422fa8a6585SDoug Moore 			 * fragment at the other end.
1423fa8a6585SDoug Moore 			 */
1424fa8a6585SDoug Moore 			if (pa_end + frag <= pa)
1425fa8a6585SDoug Moore 				pa = pa_end;
1426fa8a6585SDoug Moore 		}
1427fa8a6585SDoug Moore 
1428fa8a6585SDoug Moore 		/* Advance as necessary to satisfy boundary conditions. */
1429fa8a6585SDoug Moore 		if (!vm_addr_bound_ok(pa, size, boundary))
1430fa8a6585SDoug Moore 			pa = roundup2(pa + 1, boundary);
1431fa8a6585SDoug Moore 		pa_end = pa + size;
1432fa8a6585SDoug Moore 
1433fa8a6585SDoug Moore 		/*
1434fa8a6585SDoug Moore 		 * Determine if the address range is valid (without overflow in
1435fa8a6585SDoug Moore 		 * pa_end calculation), and fits within the segment.
1436fa8a6585SDoug Moore 		 */
1437fa8a6585SDoug Moore 		if (pa_end < pa || seg->end < pa_end)
1438fa8a6585SDoug Moore 			continue;
1439fa8a6585SDoug Moore 
1440fa8a6585SDoug Moore 		m_ret = &seg->first_page[atop(pa - seg->start)];
1441fa8a6585SDoug Moore 
1442fa8a6585SDoug Moore 		/*
1443fa8a6585SDoug Moore 		 * Determine whether there are enough free oind-blocks here to
1444fa8a6585SDoug Moore 		 * satisfy the allocation request.
1445fa8a6585SDoug Moore 		 */
1446fa8a6585SDoug Moore 		pa = VM_PAGE_TO_PHYS(m_listed);
1447fa8a6585SDoug Moore 		do {
1448fa8a6585SDoug Moore 			pa += page_size << oind;
1449fa8a6585SDoug Moore 			if (pa >= pa_end)
1450fa8a6585SDoug Moore 				return (m_ret);
1451fa8a6585SDoug Moore 			m = &seg->first_page[atop(pa - seg->start)];
1452fa8a6585SDoug Moore 		} while (oind == m->order);
1453fa8a6585SDoug Moore 
1454fa8a6585SDoug Moore 		/*
1455fa8a6585SDoug Moore 		 * Determine if an additional series of free blocks of
1456fa8a6585SDoug Moore 		 * diminishing size can help to satisfy the allocation request.
1457fa8a6585SDoug Moore 		 */
1458fa8a6585SDoug Moore 		while (m->order < oind &&
1459fa8a6585SDoug Moore 		    pa + 2 * (page_size << m->order) > pa_end) {
1460fa8a6585SDoug Moore 			pa += page_size << m->order;
1461fa8a6585SDoug Moore 			if (pa >= pa_end)
1462fa8a6585SDoug Moore 				return (m_ret);
1463fa8a6585SDoug Moore 			m = &seg->first_page[atop(pa - seg->start)];
1464fa8a6585SDoug Moore 		}
1465fa8a6585SDoug Moore 	}
1466fa8a6585SDoug Moore 	return (NULL);
1467fa8a6585SDoug Moore }
1468fa8a6585SDoug Moore 
1469fa8a6585SDoug Moore /*
1470fa8a6585SDoug Moore  * Find a run of contiguous physical pages from the specified free list
1471342056faSDoug Moore  * table.
1472c869e672SAlan Cox  */
1473c869e672SAlan Cox static vm_page_t
1474fa8a6585SDoug Moore vm_phys_find_queues_contig(
1475342056faSDoug Moore     struct vm_freelist (*queues)[VM_NFREEPOOL][VM_NFREEORDER_MAX],
1476342056faSDoug Moore     u_long npages, vm_paddr_t low, vm_paddr_t high,
1477342056faSDoug Moore     u_long alignment, vm_paddr_t boundary)
1478c869e672SAlan Cox {
1479c869e672SAlan Cox 	struct vm_freelist *fl;
1480fa8a6585SDoug Moore 	vm_page_t m_ret;
1481c869e672SAlan Cox 	vm_paddr_t pa, pa_end, size;
1482c869e672SAlan Cox 	int oind, order, pind;
1483c869e672SAlan Cox 
1484c869e672SAlan Cox 	KASSERT(npages > 0, ("npages is 0"));
1485c869e672SAlan Cox 	KASSERT(powerof2(alignment), ("alignment is not a power of 2"));
1486c869e672SAlan Cox 	KASSERT(powerof2(boundary), ("boundary is not a power of 2"));
1487c869e672SAlan Cox 	/* Compute the queue that is the best fit for npages. */
14889161b4deSAlan Cox 	order = flsl(npages - 1);
1489fa8a6585SDoug Moore 	/* Search for a large enough free block. */
1490c869e672SAlan Cox 	size = npages << PAGE_SHIFT;
1491fa8a6585SDoug Moore 	for (oind = order; oind < VM_NFREEORDER; oind++) {
1492c869e672SAlan Cox 		for (pind = 0; pind < VM_NFREEPOOL; pind++) {
1493342056faSDoug Moore 			fl = (*queues)[pind];
14945cd29d0fSMark Johnston 			TAILQ_FOREACH(m_ret, &fl[oind].pl, listq) {
1495c869e672SAlan Cox 				/*
1496da92ecbcSDoug Moore 				 * Determine if the address range starting at pa
1497da92ecbcSDoug Moore 				 * is within the given range, satisfies the
1498da92ecbcSDoug Moore 				 * given alignment, and does not cross the given
1499da92ecbcSDoug Moore 				 * boundary.
150011752d88SAlan Cox 				 */
1501da92ecbcSDoug Moore 				pa = VM_PAGE_TO_PHYS(m_ret);
1502da92ecbcSDoug Moore 				pa_end = pa + size;
1503fa8a6585SDoug Moore 				if (low <= pa && pa_end <= high &&
1504fa8a6585SDoug Moore 				    vm_addr_ok(pa, size, alignment, boundary))
1505fa8a6585SDoug Moore 					return (m_ret);
1506fa8a6585SDoug Moore 			}
1507fa8a6585SDoug Moore 		}
1508fa8a6585SDoug Moore 	}
1509da92ecbcSDoug Moore 	if (order < VM_NFREEORDER)
1510fa8a6585SDoug Moore 		return (NULL);
1511fa8a6585SDoug Moore 	/* Search for a long-enough sequence of small blocks. */
1512fa8a6585SDoug Moore 	oind = VM_NFREEORDER - 1;
1513fa8a6585SDoug Moore 	for (pind = 0; pind < VM_NFREEPOOL; pind++) {
1514fa8a6585SDoug Moore 		fl = (*queues)[pind];
1515fa8a6585SDoug Moore 		m_ret = vm_phys_find_freelist_contig(fl, oind, npages,
1516fa8a6585SDoug Moore 		    low, high, alignment, boundary);
1517fa8a6585SDoug Moore 		if (m_ret != NULL)
1518fa8a6585SDoug Moore 			return (m_ret);
151911752d88SAlan Cox 	}
152011752d88SAlan Cox 	return (NULL);
152111752d88SAlan Cox }
152211752d88SAlan Cox 
1523b7565d44SJeff Roberson /*
1524342056faSDoug Moore  * Allocate a contiguous set of physical pages of the given size
1525342056faSDoug Moore  * "npages" from the free lists.  All of the physical pages must be at
1526342056faSDoug Moore  * or above the given physical address "low" and below the given
1527342056faSDoug Moore  * physical address "high".  The given value "alignment" determines the
1528342056faSDoug Moore  * alignment of the first physical page in the set.  If the given value
1529342056faSDoug Moore  * "boundary" is non-zero, then the set of physical pages cannot cross
1530342056faSDoug Moore  * any physical address boundary that is a multiple of that value.  Both
1531342056faSDoug Moore  * "alignment" and "boundary" must be a power of two.
1532342056faSDoug Moore  */
1533342056faSDoug Moore vm_page_t
1534342056faSDoug Moore vm_phys_alloc_contig(int domain, u_long npages, vm_paddr_t low, vm_paddr_t high,
1535342056faSDoug Moore     u_long alignment, vm_paddr_t boundary)
1536342056faSDoug Moore {
1537342056faSDoug Moore 	vm_paddr_t pa_end, pa_start;
1538fa8a6585SDoug Moore 	struct vm_freelist *fl;
1539fa8a6585SDoug Moore 	vm_page_t m, m_run;
1540342056faSDoug Moore 	struct vm_phys_seg *seg;
1541342056faSDoug Moore 	struct vm_freelist (*queues)[VM_NFREEPOOL][VM_NFREEORDER_MAX];
1542fa8a6585SDoug Moore 	int oind, segind;
1543342056faSDoug Moore 
1544342056faSDoug Moore 	KASSERT(npages > 0, ("npages is 0"));
1545342056faSDoug Moore 	KASSERT(powerof2(alignment), ("alignment is not a power of 2"));
1546342056faSDoug Moore 	KASSERT(powerof2(boundary), ("boundary is not a power of 2"));
1547342056faSDoug Moore 	vm_domain_free_assert_locked(VM_DOMAIN(domain));
1548342056faSDoug Moore 	if (low >= high)
1549342056faSDoug Moore 		return (NULL);
1550342056faSDoug Moore 	queues = NULL;
1551342056faSDoug Moore 	m_run = NULL;
1552342056faSDoug Moore 	for (segind = vm_phys_nsegs - 1; segind >= 0; segind--) {
1553342056faSDoug Moore 		seg = &vm_phys_segs[segind];
1554342056faSDoug Moore 		if (seg->start >= high || seg->domain != domain)
1555342056faSDoug Moore 			continue;
1556342056faSDoug Moore 		if (low >= seg->end)
1557342056faSDoug Moore 			break;
1558342056faSDoug Moore 		if (low <= seg->start)
1559342056faSDoug Moore 			pa_start = seg->start;
1560342056faSDoug Moore 		else
1561342056faSDoug Moore 			pa_start = low;
1562342056faSDoug Moore 		if (high < seg->end)
1563342056faSDoug Moore 			pa_end = high;
1564342056faSDoug Moore 		else
1565342056faSDoug Moore 			pa_end = seg->end;
1566342056faSDoug Moore 		if (pa_end - pa_start < ptoa(npages))
1567342056faSDoug Moore 			continue;
1568342056faSDoug Moore 		/*
1569342056faSDoug Moore 		 * If a previous segment led to a search using
1570342056faSDoug Moore 		 * the same free lists as would this segment, then
1571342056faSDoug Moore 		 * we've actually already searched within this
1572342056faSDoug Moore 		 * too.  So skip it.
1573342056faSDoug Moore 		 */
1574342056faSDoug Moore 		if (seg->free_queues == queues)
1575342056faSDoug Moore 			continue;
1576342056faSDoug Moore 		queues = seg->free_queues;
1577fa8a6585SDoug Moore 		m_run = vm_phys_find_queues_contig(queues, npages,
1578342056faSDoug Moore 		    low, high, alignment, boundary);
1579342056faSDoug Moore 		if (m_run != NULL)
1580342056faSDoug Moore 			break;
1581342056faSDoug Moore 	}
1582fa8a6585SDoug Moore 	if (m_run == NULL)
1583fa8a6585SDoug Moore 		return (NULL);
1584fa8a6585SDoug Moore 
1585fa8a6585SDoug Moore 	/* Allocate pages from the page-range found. */
1586fa8a6585SDoug Moore 	for (m = m_run; m < &m_run[npages]; m = &m[1 << oind]) {
1587fa8a6585SDoug Moore 		fl = (*queues)[m->pool];
1588fa8a6585SDoug Moore 		oind = m->order;
1589fa8a6585SDoug Moore 		vm_freelist_rem(fl, m, oind);
1590fa8a6585SDoug Moore 		if (m->pool != VM_FREEPOOL_DEFAULT)
1591fa8a6585SDoug Moore 			vm_phys_set_pool(VM_FREEPOOL_DEFAULT, m, oind);
1592fa8a6585SDoug Moore 	}
1593fa8a6585SDoug Moore 	/* Return excess pages to the free lists. */
1594fa8a6585SDoug Moore 	fl = (*queues)[VM_FREEPOOL_DEFAULT];
1595fa8a6585SDoug Moore 	vm_phys_enq_range(&m_run[npages], m - &m_run[npages], fl, 0);
1596342056faSDoug Moore 	return (m_run);
1597342056faSDoug Moore }
1598342056faSDoug Moore 
1599342056faSDoug Moore /*
1600b7565d44SJeff Roberson  * Return the index of the first unused slot which may be the terminating
1601b7565d44SJeff Roberson  * entry.
1602b7565d44SJeff Roberson  */
1603b7565d44SJeff Roberson static int
1604b7565d44SJeff Roberson vm_phys_avail_count(void)
1605b7565d44SJeff Roberson {
1606b7565d44SJeff Roberson 	int i;
1607b7565d44SJeff Roberson 
1608b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1]; i += 2)
1609b7565d44SJeff Roberson 		continue;
1610b7565d44SJeff Roberson 	if (i > PHYS_AVAIL_ENTRIES)
1611b7565d44SJeff Roberson 		panic("Improperly terminated phys_avail %d entries", i);
1612b7565d44SJeff Roberson 
1613b7565d44SJeff Roberson 	return (i);
1614b7565d44SJeff Roberson }
1615b7565d44SJeff Roberson 
1616b7565d44SJeff Roberson /*
1617b7565d44SJeff Roberson  * Assert that a phys_avail entry is valid.
1618b7565d44SJeff Roberson  */
1619b7565d44SJeff Roberson static void
1620b7565d44SJeff Roberson vm_phys_avail_check(int i)
1621b7565d44SJeff Roberson {
1622b7565d44SJeff Roberson 	if (phys_avail[i] & PAGE_MASK)
1623b7565d44SJeff Roberson 		panic("Unaligned phys_avail[%d]: %#jx", i,
1624b7565d44SJeff Roberson 		    (intmax_t)phys_avail[i]);
1625b7565d44SJeff Roberson 	if (phys_avail[i+1] & PAGE_MASK)
1626b7565d44SJeff Roberson 		panic("Unaligned phys_avail[%d + 1]: %#jx", i,
1627b7565d44SJeff Roberson 		    (intmax_t)phys_avail[i]);
1628b7565d44SJeff Roberson 	if (phys_avail[i + 1] < phys_avail[i])
1629b7565d44SJeff Roberson 		panic("phys_avail[%d] start %#jx < end %#jx", i,
1630b7565d44SJeff Roberson 		    (intmax_t)phys_avail[i], (intmax_t)phys_avail[i+1]);
1631b7565d44SJeff Roberson }
1632b7565d44SJeff Roberson 
1633b7565d44SJeff Roberson /*
1634b7565d44SJeff Roberson  * Return the index of an overlapping phys_avail entry or -1.
1635b7565d44SJeff Roberson  */
1636be3f5f29SJeff Roberson #ifdef NUMA
1637b7565d44SJeff Roberson static int
1638b7565d44SJeff Roberson vm_phys_avail_find(vm_paddr_t pa)
1639b7565d44SJeff Roberson {
1640b7565d44SJeff Roberson 	int i;
1641b7565d44SJeff Roberson 
1642b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1]; i += 2)
1643b7565d44SJeff Roberson 		if (phys_avail[i] <= pa && phys_avail[i + 1] > pa)
1644b7565d44SJeff Roberson 			return (i);
1645b7565d44SJeff Roberson 	return (-1);
1646b7565d44SJeff Roberson }
1647be3f5f29SJeff Roberson #endif
1648b7565d44SJeff Roberson 
1649b7565d44SJeff Roberson /*
1650b7565d44SJeff Roberson  * Return the index of the largest entry.
1651b7565d44SJeff Roberson  */
1652b7565d44SJeff Roberson int
1653b7565d44SJeff Roberson vm_phys_avail_largest(void)
1654b7565d44SJeff Roberson {
1655b7565d44SJeff Roberson 	vm_paddr_t sz, largesz;
1656b7565d44SJeff Roberson 	int largest;
1657b7565d44SJeff Roberson 	int i;
1658b7565d44SJeff Roberson 
1659b7565d44SJeff Roberson 	largest = 0;
1660b7565d44SJeff Roberson 	largesz = 0;
1661b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1]; i += 2) {
1662b7565d44SJeff Roberson 		sz = vm_phys_avail_size(i);
1663b7565d44SJeff Roberson 		if (sz > largesz) {
1664b7565d44SJeff Roberson 			largesz = sz;
1665b7565d44SJeff Roberson 			largest = i;
1666b7565d44SJeff Roberson 		}
1667b7565d44SJeff Roberson 	}
1668b7565d44SJeff Roberson 
1669b7565d44SJeff Roberson 	return (largest);
1670b7565d44SJeff Roberson }
1671b7565d44SJeff Roberson 
1672b7565d44SJeff Roberson vm_paddr_t
1673b7565d44SJeff Roberson vm_phys_avail_size(int i)
1674b7565d44SJeff Roberson {
1675b7565d44SJeff Roberson 
1676b7565d44SJeff Roberson 	return (phys_avail[i + 1] - phys_avail[i]);
1677b7565d44SJeff Roberson }
1678b7565d44SJeff Roberson 
1679b7565d44SJeff Roberson /*
1680b7565d44SJeff Roberson  * Split an entry at the address 'pa'.  Return zero on success or errno.
1681b7565d44SJeff Roberson  */
1682b7565d44SJeff Roberson static int
1683b7565d44SJeff Roberson vm_phys_avail_split(vm_paddr_t pa, int i)
1684b7565d44SJeff Roberson {
1685b7565d44SJeff Roberson 	int cnt;
1686b7565d44SJeff Roberson 
1687b7565d44SJeff Roberson 	vm_phys_avail_check(i);
1688b7565d44SJeff Roberson 	if (pa <= phys_avail[i] || pa >= phys_avail[i + 1])
1689b7565d44SJeff Roberson 		panic("vm_phys_avail_split: invalid address");
1690b7565d44SJeff Roberson 	cnt = vm_phys_avail_count();
1691b7565d44SJeff Roberson 	if (cnt >= PHYS_AVAIL_ENTRIES)
1692b7565d44SJeff Roberson 		return (ENOSPC);
1693b7565d44SJeff Roberson 	memmove(&phys_avail[i + 2], &phys_avail[i],
1694b7565d44SJeff Roberson 	    (cnt - i) * sizeof(phys_avail[0]));
1695b7565d44SJeff Roberson 	phys_avail[i + 1] = pa;
1696b7565d44SJeff Roberson 	phys_avail[i + 2] = pa;
1697b7565d44SJeff Roberson 	vm_phys_avail_check(i);
1698b7565d44SJeff Roberson 	vm_phys_avail_check(i+2);
1699b7565d44SJeff Roberson 
1700b7565d44SJeff Roberson 	return (0);
1701b7565d44SJeff Roberson }
1702b7565d44SJeff Roberson 
170331991a5aSMitchell Horne /*
170431991a5aSMitchell Horne  * Check if a given physical address can be included as part of a crash dump.
170531991a5aSMitchell Horne  */
170631991a5aSMitchell Horne bool
170731991a5aSMitchell Horne vm_phys_is_dumpable(vm_paddr_t pa)
170831991a5aSMitchell Horne {
170931991a5aSMitchell Horne 	vm_page_t m;
171031991a5aSMitchell Horne 	int i;
171131991a5aSMitchell Horne 
171231991a5aSMitchell Horne 	if ((m = vm_phys_paddr_to_vm_page(pa)) != NULL)
171331991a5aSMitchell Horne 		return ((m->flags & PG_NODUMP) == 0);
171431991a5aSMitchell Horne 
171531991a5aSMitchell Horne 	for (i = 0; dump_avail[i] != 0 || dump_avail[i + 1] != 0; i += 2) {
171631991a5aSMitchell Horne 		if (pa >= dump_avail[i] && pa < dump_avail[i + 1])
171731991a5aSMitchell Horne 			return (true);
171831991a5aSMitchell Horne 	}
171931991a5aSMitchell Horne 	return (false);
172031991a5aSMitchell Horne }
172131991a5aSMitchell Horne 
172281302f1dSMark Johnston void
172381302f1dSMark Johnston vm_phys_early_add_seg(vm_paddr_t start, vm_paddr_t end)
172481302f1dSMark Johnston {
172581302f1dSMark Johnston 	struct vm_phys_seg *seg;
172681302f1dSMark Johnston 
172781302f1dSMark Johnston 	if (vm_phys_early_nsegs == -1)
172881302f1dSMark Johnston 		panic("%s: called after initialization", __func__);
172981302f1dSMark Johnston 	if (vm_phys_early_nsegs == nitems(vm_phys_early_segs))
173081302f1dSMark Johnston 		panic("%s: ran out of early segments", __func__);
173181302f1dSMark Johnston 
173281302f1dSMark Johnston 	seg = &vm_phys_early_segs[vm_phys_early_nsegs++];
173381302f1dSMark Johnston 	seg->start = start;
173481302f1dSMark Johnston 	seg->end = end;
173581302f1dSMark Johnston }
173681302f1dSMark Johnston 
1737b7565d44SJeff Roberson /*
1738b7565d44SJeff Roberson  * This routine allocates NUMA node specific memory before the page
1739b7565d44SJeff Roberson  * allocator is bootstrapped.
1740b7565d44SJeff Roberson  */
1741b7565d44SJeff Roberson vm_paddr_t
1742b7565d44SJeff Roberson vm_phys_early_alloc(int domain, size_t alloc_size)
1743b7565d44SJeff Roberson {
17442e7838aeSJohn Baldwin #ifdef NUMA
17452e7838aeSJohn Baldwin 	int mem_index;
17462e7838aeSJohn Baldwin #endif
17472e7838aeSJohn Baldwin 	int i, biggestone;
1748b7565d44SJeff Roberson 	vm_paddr_t pa, mem_start, mem_end, size, biggestsize, align;
1749b7565d44SJeff Roberson 
175081302f1dSMark Johnston 	KASSERT(domain == -1 || (domain >= 0 && domain < vm_ndomains),
175181302f1dSMark Johnston 	    ("%s: invalid domain index %d", __func__, domain));
1752b7565d44SJeff Roberson 
1753b7565d44SJeff Roberson 	/*
1754b7565d44SJeff Roberson 	 * Search the mem_affinity array for the biggest address
1755b7565d44SJeff Roberson 	 * range in the desired domain.  This is used to constrain
1756b7565d44SJeff Roberson 	 * the phys_avail selection below.
1757b7565d44SJeff Roberson 	 */
1758b7565d44SJeff Roberson 	biggestsize = 0;
1759b7565d44SJeff Roberson 	mem_start = 0;
1760b7565d44SJeff Roberson 	mem_end = -1;
1761b7565d44SJeff Roberson #ifdef NUMA
17622e7838aeSJohn Baldwin 	mem_index = 0;
1763b7565d44SJeff Roberson 	if (mem_affinity != NULL) {
1764b7565d44SJeff Roberson 		for (i = 0;; i++) {
1765b7565d44SJeff Roberson 			size = mem_affinity[i].end - mem_affinity[i].start;
1766b7565d44SJeff Roberson 			if (size == 0)
1767b7565d44SJeff Roberson 				break;
176881302f1dSMark Johnston 			if (domain != -1 && mem_affinity[i].domain != domain)
1769b7565d44SJeff Roberson 				continue;
1770b7565d44SJeff Roberson 			if (size > biggestsize) {
1771b7565d44SJeff Roberson 				mem_index = i;
1772b7565d44SJeff Roberson 				biggestsize = size;
1773b7565d44SJeff Roberson 			}
1774b7565d44SJeff Roberson 		}
1775b7565d44SJeff Roberson 		mem_start = mem_affinity[mem_index].start;
1776b7565d44SJeff Roberson 		mem_end = mem_affinity[mem_index].end;
1777b7565d44SJeff Roberson 	}
1778b7565d44SJeff Roberson #endif
1779b7565d44SJeff Roberson 
1780b7565d44SJeff Roberson 	/*
1781b7565d44SJeff Roberson 	 * Now find biggest physical segment in within the desired
1782b7565d44SJeff Roberson 	 * numa domain.
1783b7565d44SJeff Roberson 	 */
1784b7565d44SJeff Roberson 	biggestsize = 0;
1785b7565d44SJeff Roberson 	biggestone = 0;
1786b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
1787b7565d44SJeff Roberson 		/* skip regions that are out of range */
1788b7565d44SJeff Roberson 		if (phys_avail[i+1] - alloc_size < mem_start ||
1789b7565d44SJeff Roberson 		    phys_avail[i+1] > mem_end)
1790b7565d44SJeff Roberson 			continue;
1791b7565d44SJeff Roberson 		size = vm_phys_avail_size(i);
1792b7565d44SJeff Roberson 		if (size > biggestsize) {
1793b7565d44SJeff Roberson 			biggestone = i;
1794b7565d44SJeff Roberson 			biggestsize = size;
1795b7565d44SJeff Roberson 		}
1796b7565d44SJeff Roberson 	}
1797b7565d44SJeff Roberson 	alloc_size = round_page(alloc_size);
1798b7565d44SJeff Roberson 
1799b7565d44SJeff Roberson 	/*
1800b7565d44SJeff Roberson 	 * Grab single pages from the front to reduce fragmentation.
1801b7565d44SJeff Roberson 	 */
1802b7565d44SJeff Roberson 	if (alloc_size == PAGE_SIZE) {
1803b7565d44SJeff Roberson 		pa = phys_avail[biggestone];
1804b7565d44SJeff Roberson 		phys_avail[biggestone] += PAGE_SIZE;
1805b7565d44SJeff Roberson 		vm_phys_avail_check(biggestone);
1806b7565d44SJeff Roberson 		return (pa);
1807b7565d44SJeff Roberson 	}
1808b7565d44SJeff Roberson 
1809b7565d44SJeff Roberson 	/*
1810b7565d44SJeff Roberson 	 * Naturally align large allocations.
1811b7565d44SJeff Roberson 	 */
1812b7565d44SJeff Roberson 	align = phys_avail[biggestone + 1] & (alloc_size - 1);
1813b7565d44SJeff Roberson 	if (alloc_size + align > biggestsize)
1814b7565d44SJeff Roberson 		panic("cannot find a large enough size\n");
1815b7565d44SJeff Roberson 	if (align != 0 &&
1816b7565d44SJeff Roberson 	    vm_phys_avail_split(phys_avail[biggestone + 1] - align,
1817b7565d44SJeff Roberson 	    biggestone) != 0)
1818b7565d44SJeff Roberson 		/* Wasting memory. */
1819b7565d44SJeff Roberson 		phys_avail[biggestone + 1] -= align;
1820b7565d44SJeff Roberson 
1821b7565d44SJeff Roberson 	phys_avail[biggestone + 1] -= alloc_size;
1822b7565d44SJeff Roberson 	vm_phys_avail_check(biggestone);
1823b7565d44SJeff Roberson 	pa = phys_avail[biggestone + 1];
1824b7565d44SJeff Roberson 	return (pa);
1825b7565d44SJeff Roberson }
1826b7565d44SJeff Roberson 
1827b7565d44SJeff Roberson void
1828b7565d44SJeff Roberson vm_phys_early_startup(void)
1829b7565d44SJeff Roberson {
183081302f1dSMark Johnston 	struct vm_phys_seg *seg;
1831b7565d44SJeff Roberson 	int i;
1832b7565d44SJeff Roberson 
1833b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
1834b7565d44SJeff Roberson 		phys_avail[i] = round_page(phys_avail[i]);
1835b7565d44SJeff Roberson 		phys_avail[i + 1] = trunc_page(phys_avail[i + 1]);
1836b7565d44SJeff Roberson 	}
1837b7565d44SJeff Roberson 
183881302f1dSMark Johnston 	for (i = 0; i < vm_phys_early_nsegs; i++) {
183981302f1dSMark Johnston 		seg = &vm_phys_early_segs[i];
184081302f1dSMark Johnston 		vm_phys_add_seg(seg->start, seg->end);
184181302f1dSMark Johnston 	}
184281302f1dSMark Johnston 	vm_phys_early_nsegs = -1;
184381302f1dSMark Johnston 
1844b7565d44SJeff Roberson #ifdef NUMA
1845b7565d44SJeff Roberson 	/* Force phys_avail to be split by domain. */
1846b7565d44SJeff Roberson 	if (mem_affinity != NULL) {
1847b7565d44SJeff Roberson 		int idx;
1848b7565d44SJeff Roberson 
1849b7565d44SJeff Roberson 		for (i = 0; mem_affinity[i].end != 0; i++) {
1850b7565d44SJeff Roberson 			idx = vm_phys_avail_find(mem_affinity[i].start);
1851b7565d44SJeff Roberson 			if (idx != -1 &&
1852b7565d44SJeff Roberson 			    phys_avail[idx] != mem_affinity[i].start)
1853b7565d44SJeff Roberson 				vm_phys_avail_split(mem_affinity[i].start, idx);
1854b7565d44SJeff Roberson 			idx = vm_phys_avail_find(mem_affinity[i].end);
1855b7565d44SJeff Roberson 			if (idx != -1 &&
1856b7565d44SJeff Roberson 			    phys_avail[idx] != mem_affinity[i].end)
1857b7565d44SJeff Roberson 				vm_phys_avail_split(mem_affinity[i].end, idx);
1858b7565d44SJeff Roberson 		}
1859b7565d44SJeff Roberson 	}
1860b7565d44SJeff Roberson #endif
1861b7565d44SJeff Roberson }
1862b7565d44SJeff Roberson 
186311752d88SAlan Cox #ifdef DDB
186411752d88SAlan Cox /*
186511752d88SAlan Cox  * Show the number of physical pages in each of the free lists.
186611752d88SAlan Cox  */
1867c84c5e00SMitchell Horne DB_SHOW_COMMAND_FLAGS(freepages, db_show_freepages, DB_CMD_MEMSAFE)
186811752d88SAlan Cox {
186911752d88SAlan Cox 	struct vm_freelist *fl;
18707e226537SAttilio Rao 	int flind, oind, pind, dom;
187111752d88SAlan Cox 
18727e226537SAttilio Rao 	for (dom = 0; dom < vm_ndomains; dom++) {
18737e226537SAttilio Rao 		db_printf("DOMAIN: %d\n", dom);
187411752d88SAlan Cox 		for (flind = 0; flind < vm_nfreelists; flind++) {
187511752d88SAlan Cox 			db_printf("FREE LIST %d:\n"
187611752d88SAlan Cox 			    "\n  ORDER (SIZE)  |  NUMBER"
187711752d88SAlan Cox 			    "\n              ", flind);
187811752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
187911752d88SAlan Cox 				db_printf("  |  POOL %d", pind);
188011752d88SAlan Cox 			db_printf("\n--            ");
188111752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
188211752d88SAlan Cox 				db_printf("-- --      ");
188311752d88SAlan Cox 			db_printf("--\n");
188411752d88SAlan Cox 			for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
188511752d88SAlan Cox 				db_printf("  %2.2d (%6.6dK)", oind,
188611752d88SAlan Cox 				    1 << (PAGE_SHIFT - 10 + oind));
188711752d88SAlan Cox 				for (pind = 0; pind < VM_NFREEPOOL; pind++) {
18887e226537SAttilio Rao 				fl = vm_phys_free_queues[dom][flind][pind];
188911752d88SAlan Cox 					db_printf("  |  %6.6d", fl[oind].lcnt);
189011752d88SAlan Cox 				}
189111752d88SAlan Cox 				db_printf("\n");
189211752d88SAlan Cox 			}
189311752d88SAlan Cox 			db_printf("\n");
189411752d88SAlan Cox 		}
18957e226537SAttilio Rao 		db_printf("\n");
18967e226537SAttilio Rao 	}
189711752d88SAlan Cox }
189811752d88SAlan Cox #endif
1899