xref: /freebsd/sys/vm/vm_phys.c (revision c606ab59e7f9423f7027320e9a4514c7db39658d)
111752d88SAlan Cox /*-
2fe267a55SPedro F. Giffuni  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
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 __FBSDID("$FreeBSD$");
4311752d88SAlan Cox 
4411752d88SAlan Cox #include "opt_ddb.h"
45174b5f38SJohn Baldwin #include "opt_vm.h"
4611752d88SAlan Cox 
4711752d88SAlan Cox #include <sys/param.h>
4811752d88SAlan Cox #include <sys/systm.h>
49662e7fa8SMark Johnston #include <sys/domainset.h>
5011752d88SAlan Cox #include <sys/lock.h>
5111752d88SAlan Cox #include <sys/kernel.h>
5211752d88SAlan Cox #include <sys/malloc.h>
5311752d88SAlan Cox #include <sys/mutex.h>
547e226537SAttilio Rao #include <sys/proc.h>
5511752d88SAlan Cox #include <sys/queue.h>
5638d6b2dcSRoger Pau Monné #include <sys/rwlock.h>
5711752d88SAlan Cox #include <sys/sbuf.h>
5811752d88SAlan Cox #include <sys/sysctl.h>
5938d6b2dcSRoger Pau Monné #include <sys/tree.h>
6011752d88SAlan Cox #include <sys/vmmeter.h>
6111752d88SAlan Cox 
6211752d88SAlan Cox #include <ddb/ddb.h>
6311752d88SAlan Cox 
6411752d88SAlan Cox #include <vm/vm.h>
6511752d88SAlan Cox #include <vm/vm_param.h>
6611752d88SAlan Cox #include <vm/vm_kern.h>
6711752d88SAlan Cox #include <vm/vm_object.h>
6811752d88SAlan Cox #include <vm/vm_page.h>
6911752d88SAlan Cox #include <vm/vm_phys.h>
70e2068d0bSJeff Roberson #include <vm/vm_pagequeue.h>
7111752d88SAlan Cox 
72449c2e92SKonstantin Belousov _Static_assert(sizeof(long) * NBBY >= VM_PHYSSEG_MAX,
73449c2e92SKonstantin Belousov     "Too many physsegs.");
7411752d88SAlan Cox 
75b6715dabSJeff Roberson #ifdef NUMA
76cdfeced8SJeff Roberson struct mem_affinity __read_mostly *mem_affinity;
77cdfeced8SJeff Roberson int __read_mostly *mem_locality;
7862d70a81SJohn Baldwin #endif
79a3870a18SJohn Baldwin 
80cdfeced8SJeff Roberson int __read_mostly vm_ndomains = 1;
81463406acSMark Johnston domainset_t __read_mostly all_domains = DOMAINSET_T_INITIALIZER(0x1);
827e226537SAttilio Rao 
83cdfeced8SJeff Roberson struct vm_phys_seg __read_mostly vm_phys_segs[VM_PHYSSEG_MAX];
84cdfeced8SJeff Roberson int __read_mostly vm_phys_nsegs;
8581302f1dSMark Johnston static struct vm_phys_seg vm_phys_early_segs[8];
8681302f1dSMark Johnston static int vm_phys_early_nsegs;
8711752d88SAlan Cox 
8838d6b2dcSRoger Pau Monné struct vm_phys_fictitious_seg;
8938d6b2dcSRoger Pau Monné static int vm_phys_fictitious_cmp(struct vm_phys_fictitious_seg *,
9038d6b2dcSRoger Pau Monné     struct vm_phys_fictitious_seg *);
9138d6b2dcSRoger Pau Monné 
9238d6b2dcSRoger Pau Monné RB_HEAD(fict_tree, vm_phys_fictitious_seg) vm_phys_fictitious_tree =
93b649c2acSDoug Moore     RB_INITIALIZER(&vm_phys_fictitious_tree);
9438d6b2dcSRoger Pau Monné 
9538d6b2dcSRoger Pau Monné struct vm_phys_fictitious_seg {
9638d6b2dcSRoger Pau Monné 	RB_ENTRY(vm_phys_fictitious_seg) node;
9738d6b2dcSRoger Pau Monné 	/* Memory region data */
98b6de32bdSKonstantin Belousov 	vm_paddr_t	start;
99b6de32bdSKonstantin Belousov 	vm_paddr_t	end;
100b6de32bdSKonstantin Belousov 	vm_page_t	first_page;
10138d6b2dcSRoger Pau Monné };
10238d6b2dcSRoger Pau Monné 
10338d6b2dcSRoger Pau Monné RB_GENERATE_STATIC(fict_tree, vm_phys_fictitious_seg, node,
10438d6b2dcSRoger Pau Monné     vm_phys_fictitious_cmp);
10538d6b2dcSRoger Pau Monné 
106cdfeced8SJeff Roberson static struct rwlock_padalign vm_phys_fictitious_reg_lock;
107c0432fc3SMark Johnston MALLOC_DEFINE(M_FICT_PAGES, "vm_fictitious", "Fictitious VM pages");
108b6de32bdSKonstantin Belousov 
109cdfeced8SJeff Roberson static struct vm_freelist __aligned(CACHE_LINE_SIZE)
110f2a496d6SKonstantin Belousov     vm_phys_free_queues[MAXMEMDOM][VM_NFREELIST][VM_NFREEPOOL]
111f2a496d6SKonstantin Belousov     [VM_NFREEORDER_MAX];
11211752d88SAlan Cox 
113cdfeced8SJeff Roberson static int __read_mostly vm_nfreelists;
114d866a563SAlan Cox 
115d866a563SAlan Cox /*
11621943937SJeff Roberson  * These "avail lists" are globals used to communicate boot-time physical
11721943937SJeff Roberson  * memory layout to other parts of the kernel.  Each physically contiguous
11821943937SJeff Roberson  * region of memory is defined by a start address at an even index and an
11921943937SJeff Roberson  * end address at the following odd index.  Each list is terminated by a
12021943937SJeff Roberson  * pair of zero entries.
12121943937SJeff Roberson  *
12221943937SJeff Roberson  * dump_avail tells the dump code what regions to include in a crash dump, and
12321943937SJeff Roberson  * phys_avail is all of the remaining physical memory that is available for
12421943937SJeff Roberson  * the vm system.
12521943937SJeff Roberson  *
12621943937SJeff Roberson  * Initially dump_avail and phys_avail are identical.  Boot time memory
12721943937SJeff Roberson  * allocations remove extents from phys_avail that may still be included
12821943937SJeff Roberson  * in dumps.
12921943937SJeff Roberson  */
13021943937SJeff Roberson vm_paddr_t phys_avail[PHYS_AVAIL_COUNT];
13121943937SJeff Roberson vm_paddr_t dump_avail[PHYS_AVAIL_COUNT];
13221943937SJeff Roberson 
13321943937SJeff Roberson /*
134d866a563SAlan Cox  * Provides the mapping from VM_FREELIST_* to free list indices (flind).
135d866a563SAlan Cox  */
136cdfeced8SJeff Roberson static int __read_mostly vm_freelist_to_flind[VM_NFREELIST];
137d866a563SAlan Cox 
138d866a563SAlan Cox CTASSERT(VM_FREELIST_DEFAULT == 0);
139d866a563SAlan Cox 
140d866a563SAlan Cox #ifdef VM_FREELIST_DMA32
141d866a563SAlan Cox #define	VM_DMA32_BOUNDARY	((vm_paddr_t)1 << 32)
142d866a563SAlan Cox #endif
143d866a563SAlan Cox 
144d866a563SAlan Cox /*
145d866a563SAlan Cox  * Enforce the assumptions made by vm_phys_add_seg() and vm_phys_init() about
146d866a563SAlan Cox  * the ordering of the free list boundaries.
147d866a563SAlan Cox  */
148d866a563SAlan Cox #if defined(VM_LOWMEM_BOUNDARY) && defined(VM_DMA32_BOUNDARY)
149d866a563SAlan Cox CTASSERT(VM_LOWMEM_BOUNDARY < VM_DMA32_BOUNDARY);
150d866a563SAlan Cox #endif
15111752d88SAlan Cox 
15211752d88SAlan Cox static int sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS);
1537029da5cSPawel Biernacki SYSCTL_OID(_vm, OID_AUTO, phys_free,
154114484b7SMark Johnston     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
1557029da5cSPawel Biernacki     sysctl_vm_phys_free, "A",
1567029da5cSPawel Biernacki     "Phys Free Info");
15711752d88SAlan Cox 
15811752d88SAlan Cox static int sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS);
1597029da5cSPawel Biernacki SYSCTL_OID(_vm, OID_AUTO, phys_segs,
160114484b7SMark Johnston     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
1617029da5cSPawel Biernacki     sysctl_vm_phys_segs, "A",
1627029da5cSPawel Biernacki     "Phys Seg Info");
16311752d88SAlan Cox 
164b6715dabSJeff Roberson #ifdef NUMA
165415d7ccaSAdrian Chadd static int sysctl_vm_phys_locality(SYSCTL_HANDLER_ARGS);
1667029da5cSPawel Biernacki SYSCTL_OID(_vm, OID_AUTO, phys_locality,
167114484b7SMark Johnston     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
1687029da5cSPawel Biernacki     sysctl_vm_phys_locality, "A",
1697029da5cSPawel Biernacki     "Phys Locality Info");
1706520495aSAdrian Chadd #endif
171415d7ccaSAdrian Chadd 
1727e226537SAttilio Rao SYSCTL_INT(_vm, OID_AUTO, ndomains, CTLFLAG_RD,
1737e226537SAttilio Rao     &vm_ndomains, 0, "Number of physical memory domains available.");
174a3870a18SJohn Baldwin 
175c869e672SAlan Cox static vm_page_t vm_phys_alloc_seg_contig(struct vm_phys_seg *seg,
176c869e672SAlan Cox     u_long npages, vm_paddr_t low, vm_paddr_t high, u_long alignment,
177c869e672SAlan Cox     vm_paddr_t boundary);
178d866a563SAlan Cox static void _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int domain);
179d866a563SAlan Cox static void vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end);
18011752d88SAlan Cox static void vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl,
181370a338aSAlan Cox     int order, int tail);
182*c606ab59SDoug Moore 
18338d6b2dcSRoger Pau Monné /*
18438d6b2dcSRoger Pau Monné  * Red-black tree helpers for vm fictitious range management.
18538d6b2dcSRoger Pau Monné  */
18638d6b2dcSRoger Pau Monné static inline int
18738d6b2dcSRoger Pau Monné vm_phys_fictitious_in_range(struct vm_phys_fictitious_seg *p,
18838d6b2dcSRoger Pau Monné     struct vm_phys_fictitious_seg *range)
18938d6b2dcSRoger Pau Monné {
19038d6b2dcSRoger Pau Monné 
19138d6b2dcSRoger Pau Monné 	KASSERT(range->start != 0 && range->end != 0,
19238d6b2dcSRoger Pau Monné 	    ("Invalid range passed on search for vm_fictitious page"));
19338d6b2dcSRoger Pau Monné 	if (p->start >= range->end)
19438d6b2dcSRoger Pau Monné 		return (1);
19538d6b2dcSRoger Pau Monné 	if (p->start < range->start)
19638d6b2dcSRoger Pau Monné 		return (-1);
19738d6b2dcSRoger Pau Monné 
19838d6b2dcSRoger Pau Monné 	return (0);
19938d6b2dcSRoger Pau Monné }
20038d6b2dcSRoger Pau Monné 
20138d6b2dcSRoger Pau Monné static int
20238d6b2dcSRoger Pau Monné vm_phys_fictitious_cmp(struct vm_phys_fictitious_seg *p1,
20338d6b2dcSRoger Pau Monné     struct vm_phys_fictitious_seg *p2)
20438d6b2dcSRoger Pau Monné {
20538d6b2dcSRoger Pau Monné 
20638d6b2dcSRoger Pau Monné 	/* Check if this is a search for a page */
20738d6b2dcSRoger Pau Monné 	if (p1->end == 0)
20838d6b2dcSRoger Pau Monné 		return (vm_phys_fictitious_in_range(p1, p2));
20938d6b2dcSRoger Pau Monné 
21038d6b2dcSRoger Pau Monné 	KASSERT(p2->end != 0,
21138d6b2dcSRoger Pau Monné     ("Invalid range passed as second parameter to vm fictitious comparison"));
21238d6b2dcSRoger Pau Monné 
21338d6b2dcSRoger Pau Monné 	/* Searching to add a new range */
21438d6b2dcSRoger Pau Monné 	if (p1->end <= p2->start)
21538d6b2dcSRoger Pau Monné 		return (-1);
21638d6b2dcSRoger Pau Monné 	if (p1->start >= p2->end)
21738d6b2dcSRoger Pau Monné 		return (1);
21838d6b2dcSRoger Pau Monné 
21938d6b2dcSRoger Pau Monné 	panic("Trying to add overlapping vm fictitious ranges:\n"
22038d6b2dcSRoger Pau Monné 	    "[%#jx:%#jx] and [%#jx:%#jx]", (uintmax_t)p1->start,
22138d6b2dcSRoger Pau Monné 	    (uintmax_t)p1->end, (uintmax_t)p2->start, (uintmax_t)p2->end);
22238d6b2dcSRoger Pau Monné }
22338d6b2dcSRoger Pau Monné 
2246f4acaf4SJeff Roberson int
2256f4acaf4SJeff Roberson vm_phys_domain_match(int prefer, vm_paddr_t low, vm_paddr_t high)
226449c2e92SKonstantin Belousov {
227b6715dabSJeff Roberson #ifdef NUMA
2286f4acaf4SJeff Roberson 	domainset_t mask;
2296f4acaf4SJeff Roberson 	int i;
230449c2e92SKonstantin Belousov 
2316f4acaf4SJeff Roberson 	if (vm_ndomains == 1 || mem_affinity == NULL)
2326f4acaf4SJeff Roberson 		return (0);
2336f4acaf4SJeff Roberson 
2346f4acaf4SJeff Roberson 	DOMAINSET_ZERO(&mask);
2356f4acaf4SJeff Roberson 	/*
2366f4acaf4SJeff Roberson 	 * Check for any memory that overlaps low, high.
2376f4acaf4SJeff Roberson 	 */
2386f4acaf4SJeff Roberson 	for (i = 0; mem_affinity[i].end != 0; i++)
2396f4acaf4SJeff Roberson 		if (mem_affinity[i].start <= high &&
2406f4acaf4SJeff Roberson 		    mem_affinity[i].end >= low)
2416f4acaf4SJeff Roberson 			DOMAINSET_SET(mem_affinity[i].domain, &mask);
2426f4acaf4SJeff Roberson 	if (prefer != -1 && DOMAINSET_ISSET(prefer, &mask))
2436f4acaf4SJeff Roberson 		return (prefer);
2446f4acaf4SJeff Roberson 	if (DOMAINSET_EMPTY(&mask))
2456f4acaf4SJeff Roberson 		panic("vm_phys_domain_match:  Impossible constraint");
2466f4acaf4SJeff Roberson 	return (DOMAINSET_FFS(&mask) - 1);
2476f4acaf4SJeff Roberson #else
2486f4acaf4SJeff Roberson 	return (0);
2496f4acaf4SJeff Roberson #endif
250449c2e92SKonstantin Belousov }
251449c2e92SKonstantin Belousov 
25211752d88SAlan Cox /*
25311752d88SAlan Cox  * Outputs the state of the physical memory allocator, specifically,
25411752d88SAlan Cox  * the amount of physical memory in each free list.
25511752d88SAlan Cox  */
25611752d88SAlan Cox static int
25711752d88SAlan Cox sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS)
25811752d88SAlan Cox {
25911752d88SAlan Cox 	struct sbuf sbuf;
26011752d88SAlan Cox 	struct vm_freelist *fl;
2617e226537SAttilio Rao 	int dom, error, flind, oind, pind;
26211752d88SAlan Cox 
26300f0e671SMatthew D Fleming 	error = sysctl_wire_old_buffer(req, 0);
26400f0e671SMatthew D Fleming 	if (error != 0)
26500f0e671SMatthew D Fleming 		return (error);
2667e226537SAttilio Rao 	sbuf_new_for_sysctl(&sbuf, NULL, 128 * vm_ndomains, req);
2677e226537SAttilio Rao 	for (dom = 0; dom < vm_ndomains; dom++) {
268eb2f42fbSAlan Cox 		sbuf_printf(&sbuf,"\nDOMAIN %d:\n", dom);
26911752d88SAlan Cox 		for (flind = 0; flind < vm_nfreelists; flind++) {
270eb2f42fbSAlan Cox 			sbuf_printf(&sbuf, "\nFREE LIST %d:\n"
27111752d88SAlan Cox 			    "\n  ORDER (SIZE)  |  NUMBER"
27211752d88SAlan Cox 			    "\n              ", flind);
27311752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
27411752d88SAlan Cox 				sbuf_printf(&sbuf, "  |  POOL %d", pind);
27511752d88SAlan Cox 			sbuf_printf(&sbuf, "\n--            ");
27611752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
27711752d88SAlan Cox 				sbuf_printf(&sbuf, "-- --      ");
27811752d88SAlan Cox 			sbuf_printf(&sbuf, "--\n");
27911752d88SAlan Cox 			for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
280d689bc00SAlan Cox 				sbuf_printf(&sbuf, "  %2d (%6dK)", oind,
28111752d88SAlan Cox 				    1 << (PAGE_SHIFT - 10 + oind));
28211752d88SAlan Cox 				for (pind = 0; pind < VM_NFREEPOOL; pind++) {
2837e226537SAttilio Rao 				fl = vm_phys_free_queues[dom][flind][pind];
284eb2f42fbSAlan Cox 					sbuf_printf(&sbuf, "  |  %6d",
2857e226537SAttilio Rao 					    fl[oind].lcnt);
28611752d88SAlan Cox 				}
28711752d88SAlan Cox 				sbuf_printf(&sbuf, "\n");
28811752d88SAlan Cox 			}
2897e226537SAttilio Rao 		}
29011752d88SAlan Cox 	}
2914e657159SMatthew D Fleming 	error = sbuf_finish(&sbuf);
29211752d88SAlan Cox 	sbuf_delete(&sbuf);
29311752d88SAlan Cox 	return (error);
29411752d88SAlan Cox }
29511752d88SAlan Cox 
29611752d88SAlan Cox /*
29711752d88SAlan Cox  * Outputs the set of physical memory segments.
29811752d88SAlan Cox  */
29911752d88SAlan Cox static int
30011752d88SAlan Cox sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS)
30111752d88SAlan Cox {
30211752d88SAlan Cox 	struct sbuf sbuf;
30311752d88SAlan Cox 	struct vm_phys_seg *seg;
30411752d88SAlan Cox 	int error, segind;
30511752d88SAlan Cox 
30600f0e671SMatthew D Fleming 	error = sysctl_wire_old_buffer(req, 0);
30700f0e671SMatthew D Fleming 	if (error != 0)
30800f0e671SMatthew D Fleming 		return (error);
3094e657159SMatthew D Fleming 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
31011752d88SAlan Cox 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
31111752d88SAlan Cox 		sbuf_printf(&sbuf, "\nSEGMENT %d:\n\n", segind);
31211752d88SAlan Cox 		seg = &vm_phys_segs[segind];
31311752d88SAlan Cox 		sbuf_printf(&sbuf, "start:     %#jx\n",
31411752d88SAlan Cox 		    (uintmax_t)seg->start);
31511752d88SAlan Cox 		sbuf_printf(&sbuf, "end:       %#jx\n",
31611752d88SAlan Cox 		    (uintmax_t)seg->end);
317a3870a18SJohn Baldwin 		sbuf_printf(&sbuf, "domain:    %d\n", seg->domain);
31811752d88SAlan Cox 		sbuf_printf(&sbuf, "free list: %p\n", seg->free_queues);
31911752d88SAlan Cox 	}
3204e657159SMatthew D Fleming 	error = sbuf_finish(&sbuf);
32111752d88SAlan Cox 	sbuf_delete(&sbuf);
32211752d88SAlan Cox 	return (error);
32311752d88SAlan Cox }
32411752d88SAlan Cox 
325415d7ccaSAdrian Chadd /*
326415d7ccaSAdrian Chadd  * Return affinity, or -1 if there's no affinity information.
327415d7ccaSAdrian Chadd  */
3286520495aSAdrian Chadd int
329415d7ccaSAdrian Chadd vm_phys_mem_affinity(int f, int t)
330415d7ccaSAdrian Chadd {
331415d7ccaSAdrian Chadd 
332b6715dabSJeff Roberson #ifdef NUMA
333415d7ccaSAdrian Chadd 	if (mem_locality == NULL)
334415d7ccaSAdrian Chadd 		return (-1);
335415d7ccaSAdrian Chadd 	if (f >= vm_ndomains || t >= vm_ndomains)
336415d7ccaSAdrian Chadd 		return (-1);
337415d7ccaSAdrian Chadd 	return (mem_locality[f * vm_ndomains + t]);
3386520495aSAdrian Chadd #else
3396520495aSAdrian Chadd 	return (-1);
3406520495aSAdrian Chadd #endif
341415d7ccaSAdrian Chadd }
342415d7ccaSAdrian Chadd 
343b6715dabSJeff Roberson #ifdef NUMA
344415d7ccaSAdrian Chadd /*
345415d7ccaSAdrian Chadd  * Outputs the VM locality table.
346415d7ccaSAdrian Chadd  */
347415d7ccaSAdrian Chadd static int
348415d7ccaSAdrian Chadd sysctl_vm_phys_locality(SYSCTL_HANDLER_ARGS)
349415d7ccaSAdrian Chadd {
350415d7ccaSAdrian Chadd 	struct sbuf sbuf;
351415d7ccaSAdrian Chadd 	int error, i, j;
352415d7ccaSAdrian Chadd 
353415d7ccaSAdrian Chadd 	error = sysctl_wire_old_buffer(req, 0);
354415d7ccaSAdrian Chadd 	if (error != 0)
355415d7ccaSAdrian Chadd 		return (error);
356415d7ccaSAdrian Chadd 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
357415d7ccaSAdrian Chadd 
358415d7ccaSAdrian Chadd 	sbuf_printf(&sbuf, "\n");
359415d7ccaSAdrian Chadd 
360415d7ccaSAdrian Chadd 	for (i = 0; i < vm_ndomains; i++) {
361415d7ccaSAdrian Chadd 		sbuf_printf(&sbuf, "%d: ", i);
362415d7ccaSAdrian Chadd 		for (j = 0; j < vm_ndomains; j++) {
363415d7ccaSAdrian Chadd 			sbuf_printf(&sbuf, "%d ", vm_phys_mem_affinity(i, j));
364415d7ccaSAdrian Chadd 		}
365415d7ccaSAdrian Chadd 		sbuf_printf(&sbuf, "\n");
366415d7ccaSAdrian Chadd 	}
367415d7ccaSAdrian Chadd 	error = sbuf_finish(&sbuf);
368415d7ccaSAdrian Chadd 	sbuf_delete(&sbuf);
369415d7ccaSAdrian Chadd 	return (error);
370415d7ccaSAdrian Chadd }
3716520495aSAdrian Chadd #endif
372415d7ccaSAdrian Chadd 
3737e226537SAttilio Rao static void
3747e226537SAttilio Rao vm_freelist_add(struct vm_freelist *fl, vm_page_t m, int order, int tail)
375a3870a18SJohn Baldwin {
376a3870a18SJohn Baldwin 
3777e226537SAttilio Rao 	m->order = order;
3787e226537SAttilio Rao 	if (tail)
3795cd29d0fSMark Johnston 		TAILQ_INSERT_TAIL(&fl[order].pl, m, listq);
3807e226537SAttilio Rao 	else
3815cd29d0fSMark Johnston 		TAILQ_INSERT_HEAD(&fl[order].pl, m, listq);
3827e226537SAttilio Rao 	fl[order].lcnt++;
383a3870a18SJohn Baldwin }
3847e226537SAttilio Rao 
3857e226537SAttilio Rao static void
3867e226537SAttilio Rao vm_freelist_rem(struct vm_freelist *fl, vm_page_t m, int order)
3877e226537SAttilio Rao {
3887e226537SAttilio Rao 
3895cd29d0fSMark Johnston 	TAILQ_REMOVE(&fl[order].pl, m, listq);
3907e226537SAttilio Rao 	fl[order].lcnt--;
3917e226537SAttilio Rao 	m->order = VM_NFREEORDER;
392a3870a18SJohn Baldwin }
393a3870a18SJohn Baldwin 
39411752d88SAlan Cox /*
39511752d88SAlan Cox  * Create a physical memory segment.
39611752d88SAlan Cox  */
39711752d88SAlan Cox static void
398d866a563SAlan Cox _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int domain)
39911752d88SAlan Cox {
40011752d88SAlan Cox 	struct vm_phys_seg *seg;
40111752d88SAlan Cox 
40211752d88SAlan Cox 	KASSERT(vm_phys_nsegs < VM_PHYSSEG_MAX,
40311752d88SAlan Cox 	    ("vm_phys_create_seg: increase VM_PHYSSEG_MAX"));
404ef435ae7SJeff Roberson 	KASSERT(domain >= 0 && domain < vm_ndomains,
4057e226537SAttilio Rao 	    ("vm_phys_create_seg: invalid domain provided"));
40611752d88SAlan Cox 	seg = &vm_phys_segs[vm_phys_nsegs++];
407271f0f12SAlan Cox 	while (seg > vm_phys_segs && (seg - 1)->start >= end) {
408271f0f12SAlan Cox 		*seg = *(seg - 1);
409271f0f12SAlan Cox 		seg--;
410271f0f12SAlan Cox 	}
41111752d88SAlan Cox 	seg->start = start;
41211752d88SAlan Cox 	seg->end = end;
413a3870a18SJohn Baldwin 	seg->domain = domain;
41411752d88SAlan Cox }
41511752d88SAlan Cox 
416a3870a18SJohn Baldwin static void
417d866a563SAlan Cox vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end)
418a3870a18SJohn Baldwin {
419b6715dabSJeff Roberson #ifdef NUMA
420a3870a18SJohn Baldwin 	int i;
421a3870a18SJohn Baldwin 
422a3870a18SJohn Baldwin 	if (mem_affinity == NULL) {
423d866a563SAlan Cox 		_vm_phys_create_seg(start, end, 0);
424a3870a18SJohn Baldwin 		return;
425a3870a18SJohn Baldwin 	}
426a3870a18SJohn Baldwin 
427a3870a18SJohn Baldwin 	for (i = 0;; i++) {
428a3870a18SJohn Baldwin 		if (mem_affinity[i].end == 0)
429a3870a18SJohn Baldwin 			panic("Reached end of affinity info");
430a3870a18SJohn Baldwin 		if (mem_affinity[i].end <= start)
431a3870a18SJohn Baldwin 			continue;
432a3870a18SJohn Baldwin 		if (mem_affinity[i].start > start)
433a3870a18SJohn Baldwin 			panic("No affinity info for start %jx",
434a3870a18SJohn Baldwin 			    (uintmax_t)start);
435a3870a18SJohn Baldwin 		if (mem_affinity[i].end >= end) {
436d866a563SAlan Cox 			_vm_phys_create_seg(start, end,
437a3870a18SJohn Baldwin 			    mem_affinity[i].domain);
438a3870a18SJohn Baldwin 			break;
439a3870a18SJohn Baldwin 		}
440d866a563SAlan Cox 		_vm_phys_create_seg(start, mem_affinity[i].end,
441a3870a18SJohn Baldwin 		    mem_affinity[i].domain);
442a3870a18SJohn Baldwin 		start = mem_affinity[i].end;
443a3870a18SJohn Baldwin 	}
44462d70a81SJohn Baldwin #else
44562d70a81SJohn Baldwin 	_vm_phys_create_seg(start, end, 0);
44662d70a81SJohn Baldwin #endif
447a3870a18SJohn Baldwin }
448a3870a18SJohn Baldwin 
44911752d88SAlan Cox /*
450271f0f12SAlan Cox  * Add a physical memory segment.
451271f0f12SAlan Cox  */
452271f0f12SAlan Cox void
453271f0f12SAlan Cox vm_phys_add_seg(vm_paddr_t start, vm_paddr_t end)
454271f0f12SAlan Cox {
455d866a563SAlan Cox 	vm_paddr_t paddr;
456271f0f12SAlan Cox 
457271f0f12SAlan Cox 	KASSERT((start & PAGE_MASK) == 0,
458271f0f12SAlan Cox 	    ("vm_phys_define_seg: start is not page aligned"));
459271f0f12SAlan Cox 	KASSERT((end & PAGE_MASK) == 0,
460271f0f12SAlan Cox 	    ("vm_phys_define_seg: end is not page aligned"));
461d866a563SAlan Cox 
462d866a563SAlan Cox 	/*
463d866a563SAlan Cox 	 * Split the physical memory segment if it spans two or more free
464d866a563SAlan Cox 	 * list boundaries.
465d866a563SAlan Cox 	 */
466d866a563SAlan Cox 	paddr = start;
467d866a563SAlan Cox #ifdef	VM_FREELIST_LOWMEM
468d866a563SAlan Cox 	if (paddr < VM_LOWMEM_BOUNDARY && end > VM_LOWMEM_BOUNDARY) {
469d866a563SAlan Cox 		vm_phys_create_seg(paddr, VM_LOWMEM_BOUNDARY);
470d866a563SAlan Cox 		paddr = VM_LOWMEM_BOUNDARY;
471d866a563SAlan Cox 	}
472271f0f12SAlan Cox #endif
473d866a563SAlan Cox #ifdef	VM_FREELIST_DMA32
474d866a563SAlan Cox 	if (paddr < VM_DMA32_BOUNDARY && end > VM_DMA32_BOUNDARY) {
475d866a563SAlan Cox 		vm_phys_create_seg(paddr, VM_DMA32_BOUNDARY);
476d866a563SAlan Cox 		paddr = VM_DMA32_BOUNDARY;
477d866a563SAlan Cox 	}
478d866a563SAlan Cox #endif
479d866a563SAlan Cox 	vm_phys_create_seg(paddr, end);
480271f0f12SAlan Cox }
481271f0f12SAlan Cox 
482271f0f12SAlan Cox /*
48311752d88SAlan Cox  * Initialize the physical memory allocator.
484d866a563SAlan Cox  *
485d866a563SAlan Cox  * Requires that vm_page_array is initialized!
48611752d88SAlan Cox  */
48711752d88SAlan Cox void
48811752d88SAlan Cox vm_phys_init(void)
48911752d88SAlan Cox {
49011752d88SAlan Cox 	struct vm_freelist *fl;
49172aebdd7SAlan Cox 	struct vm_phys_seg *end_seg, *prev_seg, *seg, *tmp_seg;
492d866a563SAlan Cox 	u_long npages;
493d866a563SAlan Cox 	int dom, flind, freelist, oind, pind, segind;
49411752d88SAlan Cox 
495d866a563SAlan Cox 	/*
496d866a563SAlan Cox 	 * Compute the number of free lists, and generate the mapping from the
497d866a563SAlan Cox 	 * manifest constants VM_FREELIST_* to the free list indices.
498d866a563SAlan Cox 	 *
499d866a563SAlan Cox 	 * Initially, the entries of vm_freelist_to_flind[] are set to either
500d866a563SAlan Cox 	 * 0 or 1 to indicate which free lists should be created.
501d866a563SAlan Cox 	 */
502d866a563SAlan Cox 	npages = 0;
503d866a563SAlan Cox 	for (segind = vm_phys_nsegs - 1; segind >= 0; segind--) {
504d866a563SAlan Cox 		seg = &vm_phys_segs[segind];
505d866a563SAlan Cox #ifdef	VM_FREELIST_LOWMEM
506d866a563SAlan Cox 		if (seg->end <= VM_LOWMEM_BOUNDARY)
507d866a563SAlan Cox 			vm_freelist_to_flind[VM_FREELIST_LOWMEM] = 1;
508d866a563SAlan Cox 		else
509d866a563SAlan Cox #endif
510d866a563SAlan Cox #ifdef	VM_FREELIST_DMA32
511d866a563SAlan Cox 		if (
512d866a563SAlan Cox #ifdef	VM_DMA32_NPAGES_THRESHOLD
513d866a563SAlan Cox 		    /*
514d866a563SAlan Cox 		     * Create the DMA32 free list only if the amount of
515d866a563SAlan Cox 		     * physical memory above physical address 4G exceeds the
516d866a563SAlan Cox 		     * given threshold.
517d866a563SAlan Cox 		     */
518d866a563SAlan Cox 		    npages > VM_DMA32_NPAGES_THRESHOLD &&
519d866a563SAlan Cox #endif
520d866a563SAlan Cox 		    seg->end <= VM_DMA32_BOUNDARY)
521d866a563SAlan Cox 			vm_freelist_to_flind[VM_FREELIST_DMA32] = 1;
522d866a563SAlan Cox 		else
523d866a563SAlan Cox #endif
524d866a563SAlan Cox 		{
525d866a563SAlan Cox 			npages += atop(seg->end - seg->start);
526d866a563SAlan Cox 			vm_freelist_to_flind[VM_FREELIST_DEFAULT] = 1;
527d866a563SAlan Cox 		}
528d866a563SAlan Cox 	}
529d866a563SAlan Cox 	/* Change each entry into a running total of the free lists. */
530d866a563SAlan Cox 	for (freelist = 1; freelist < VM_NFREELIST; freelist++) {
531d866a563SAlan Cox 		vm_freelist_to_flind[freelist] +=
532d866a563SAlan Cox 		    vm_freelist_to_flind[freelist - 1];
533d866a563SAlan Cox 	}
534d866a563SAlan Cox 	vm_nfreelists = vm_freelist_to_flind[VM_NFREELIST - 1];
535d866a563SAlan Cox 	KASSERT(vm_nfreelists > 0, ("vm_phys_init: no free lists"));
536d866a563SAlan Cox 	/* Change each entry into a free list index. */
537d866a563SAlan Cox 	for (freelist = 0; freelist < VM_NFREELIST; freelist++)
538d866a563SAlan Cox 		vm_freelist_to_flind[freelist]--;
539d866a563SAlan Cox 
540d866a563SAlan Cox 	/*
541d866a563SAlan Cox 	 * Initialize the first_page and free_queues fields of each physical
542d866a563SAlan Cox 	 * memory segment.
543d866a563SAlan Cox 	 */
544271f0f12SAlan Cox #ifdef VM_PHYSSEG_SPARSE
545d866a563SAlan Cox 	npages = 0;
54611752d88SAlan Cox #endif
547271f0f12SAlan Cox 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
548271f0f12SAlan Cox 		seg = &vm_phys_segs[segind];
549271f0f12SAlan Cox #ifdef VM_PHYSSEG_SPARSE
550d866a563SAlan Cox 		seg->first_page = &vm_page_array[npages];
551d866a563SAlan Cox 		npages += atop(seg->end - seg->start);
552271f0f12SAlan Cox #else
553271f0f12SAlan Cox 		seg->first_page = PHYS_TO_VM_PAGE(seg->start);
55411752d88SAlan Cox #endif
555d866a563SAlan Cox #ifdef	VM_FREELIST_LOWMEM
556d866a563SAlan Cox 		if (seg->end <= VM_LOWMEM_BOUNDARY) {
557d866a563SAlan Cox 			flind = vm_freelist_to_flind[VM_FREELIST_LOWMEM];
558d866a563SAlan Cox 			KASSERT(flind >= 0,
559d866a563SAlan Cox 			    ("vm_phys_init: LOWMEM flind < 0"));
560d866a563SAlan Cox 		} else
561d866a563SAlan Cox #endif
562d866a563SAlan Cox #ifdef	VM_FREELIST_DMA32
563d866a563SAlan Cox 		if (seg->end <= VM_DMA32_BOUNDARY) {
564d866a563SAlan Cox 			flind = vm_freelist_to_flind[VM_FREELIST_DMA32];
565d866a563SAlan Cox 			KASSERT(flind >= 0,
566d866a563SAlan Cox 			    ("vm_phys_init: DMA32 flind < 0"));
567d866a563SAlan Cox 		} else
568d866a563SAlan Cox #endif
569d866a563SAlan Cox 		{
570d866a563SAlan Cox 			flind = vm_freelist_to_flind[VM_FREELIST_DEFAULT];
571d866a563SAlan Cox 			KASSERT(flind >= 0,
572d866a563SAlan Cox 			    ("vm_phys_init: DEFAULT flind < 0"));
57311752d88SAlan Cox 		}
574d866a563SAlan Cox 		seg->free_queues = &vm_phys_free_queues[seg->domain][flind];
575d866a563SAlan Cox 	}
576d866a563SAlan Cox 
577d866a563SAlan Cox 	/*
57872aebdd7SAlan Cox 	 * Coalesce physical memory segments that are contiguous and share the
57972aebdd7SAlan Cox 	 * same per-domain free queues.
58072aebdd7SAlan Cox 	 */
58172aebdd7SAlan Cox 	prev_seg = vm_phys_segs;
58272aebdd7SAlan Cox 	seg = &vm_phys_segs[1];
58372aebdd7SAlan Cox 	end_seg = &vm_phys_segs[vm_phys_nsegs];
58472aebdd7SAlan Cox 	while (seg < end_seg) {
58572aebdd7SAlan Cox 		if (prev_seg->end == seg->start &&
58672aebdd7SAlan Cox 		    prev_seg->free_queues == seg->free_queues) {
58772aebdd7SAlan Cox 			prev_seg->end = seg->end;
58872aebdd7SAlan Cox 			KASSERT(prev_seg->domain == seg->domain,
58972aebdd7SAlan Cox 			    ("vm_phys_init: free queues cannot span domains"));
59072aebdd7SAlan Cox 			vm_phys_nsegs--;
59172aebdd7SAlan Cox 			end_seg--;
59272aebdd7SAlan Cox 			for (tmp_seg = seg; tmp_seg < end_seg; tmp_seg++)
59372aebdd7SAlan Cox 				*tmp_seg = *(tmp_seg + 1);
59472aebdd7SAlan Cox 		} else {
59572aebdd7SAlan Cox 			prev_seg = seg;
59672aebdd7SAlan Cox 			seg++;
59772aebdd7SAlan Cox 		}
59872aebdd7SAlan Cox 	}
59972aebdd7SAlan Cox 
60072aebdd7SAlan Cox 	/*
601d866a563SAlan Cox 	 * Initialize the free queues.
602d866a563SAlan Cox 	 */
6037e226537SAttilio Rao 	for (dom = 0; dom < vm_ndomains; dom++) {
60411752d88SAlan Cox 		for (flind = 0; flind < vm_nfreelists; flind++) {
60511752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
6067e226537SAttilio Rao 				fl = vm_phys_free_queues[dom][flind][pind];
60711752d88SAlan Cox 				for (oind = 0; oind < VM_NFREEORDER; oind++)
60811752d88SAlan Cox 					TAILQ_INIT(&fl[oind].pl);
60911752d88SAlan Cox 			}
61011752d88SAlan Cox 		}
611a3870a18SJohn Baldwin 	}
612d866a563SAlan Cox 
61338d6b2dcSRoger Pau Monné 	rw_init(&vm_phys_fictitious_reg_lock, "vmfctr");
61411752d88SAlan Cox }
61511752d88SAlan Cox 
61611752d88SAlan Cox /*
617662e7fa8SMark Johnston  * Register info about the NUMA topology of the system.
618662e7fa8SMark Johnston  *
619662e7fa8SMark Johnston  * Invoked by platform-dependent code prior to vm_phys_init().
620662e7fa8SMark Johnston  */
621662e7fa8SMark Johnston void
622662e7fa8SMark Johnston vm_phys_register_domains(int ndomains, struct mem_affinity *affinity,
623662e7fa8SMark Johnston     int *locality)
624662e7fa8SMark Johnston {
625662e7fa8SMark Johnston #ifdef NUMA
626b61f3142SMark Johnston 	int d, i;
627662e7fa8SMark Johnston 
628b61f3142SMark Johnston 	/*
629b61f3142SMark Johnston 	 * For now the only override value that we support is 1, which
630b61f3142SMark Johnston 	 * effectively disables NUMA-awareness in the allocators.
631b61f3142SMark Johnston 	 */
632b61f3142SMark Johnston 	d = 0;
633b61f3142SMark Johnston 	TUNABLE_INT_FETCH("vm.numa.disabled", &d);
634b61f3142SMark Johnston 	if (d)
635b61f3142SMark Johnston 		ndomains = 1;
636b61f3142SMark Johnston 
637b61f3142SMark Johnston 	if (ndomains > 1) {
638662e7fa8SMark Johnston 		vm_ndomains = ndomains;
639662e7fa8SMark Johnston 		mem_affinity = affinity;
640662e7fa8SMark Johnston 		mem_locality = locality;
641b61f3142SMark Johnston 	}
642662e7fa8SMark Johnston 
643662e7fa8SMark Johnston 	for (i = 0; i < vm_ndomains; i++)
644662e7fa8SMark Johnston 		DOMAINSET_SET(i, &all_domains);
645662e7fa8SMark Johnston #else
646662e7fa8SMark Johnston 	(void)ndomains;
647662e7fa8SMark Johnston 	(void)affinity;
648662e7fa8SMark Johnston 	(void)locality;
649662e7fa8SMark Johnston #endif
650662e7fa8SMark Johnston }
651662e7fa8SMark Johnston 
652662e7fa8SMark Johnston /*
65311752d88SAlan Cox  * Split a contiguous, power of two-sized set of physical pages.
654370a338aSAlan Cox  *
655370a338aSAlan Cox  * When this function is called by a page allocation function, the caller
656370a338aSAlan Cox  * should request insertion at the head unless the order [order, oind) queues
657370a338aSAlan Cox  * are known to be empty.  The objective being to reduce the likelihood of
658370a338aSAlan Cox  * long-term fragmentation by promoting contemporaneous allocation and
659370a338aSAlan Cox  * (hopefully) deallocation.
66011752d88SAlan Cox  */
66111752d88SAlan Cox static __inline void
662370a338aSAlan Cox vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl, int order,
663370a338aSAlan Cox     int tail)
66411752d88SAlan Cox {
66511752d88SAlan Cox 	vm_page_t m_buddy;
66611752d88SAlan Cox 
66711752d88SAlan Cox 	while (oind > order) {
66811752d88SAlan Cox 		oind--;
66911752d88SAlan Cox 		m_buddy = &m[1 << oind];
67011752d88SAlan Cox 		KASSERT(m_buddy->order == VM_NFREEORDER,
67111752d88SAlan Cox 		    ("vm_phys_split_pages: page %p has unexpected order %d",
67211752d88SAlan Cox 		    m_buddy, m_buddy->order));
673370a338aSAlan Cox 		vm_freelist_add(fl, m_buddy, oind, tail);
67411752d88SAlan Cox         }
67511752d88SAlan Cox }
67611752d88SAlan Cox 
67711752d88SAlan Cox /*
6787493904eSAlan Cox  * Add the physical pages [m, m + npages) at the end of a power-of-two aligned
6797493904eSAlan Cox  * and sized set to the specified free list.
6807493904eSAlan Cox  *
6817493904eSAlan Cox  * When this function is called by a page allocation function, the caller
6827493904eSAlan Cox  * should request insertion at the head unless the lower-order queues are
6837493904eSAlan Cox  * known to be empty.  The objective being to reduce the likelihood of long-
6847493904eSAlan Cox  * term fragmentation by promoting contemporaneous allocation and (hopefully)
6857493904eSAlan Cox  * deallocation.
6867493904eSAlan Cox  *
6877493904eSAlan Cox  * The physical page m's buddy must not be free.
6887493904eSAlan Cox  */
6897493904eSAlan Cox static void
6907493904eSAlan Cox vm_phys_enq_range(vm_page_t m, u_int npages, struct vm_freelist *fl, int tail)
6917493904eSAlan Cox {
6927493904eSAlan Cox 	u_int n;
6937493904eSAlan Cox 	int order;
6947493904eSAlan Cox 
6957493904eSAlan Cox 	KASSERT(npages > 0, ("vm_phys_enq_range: npages is 0"));
6967493904eSAlan Cox 	KASSERT(((VM_PAGE_TO_PHYS(m) + npages * PAGE_SIZE) &
6977493904eSAlan Cox 	    ((PAGE_SIZE << (fls(npages) - 1)) - 1)) == 0,
6987493904eSAlan Cox 	    ("vm_phys_enq_range: page %p and npages %u are misaligned",
6997493904eSAlan Cox 	    m, npages));
7007493904eSAlan Cox 	do {
7017493904eSAlan Cox 		KASSERT(m->order == VM_NFREEORDER,
7027493904eSAlan Cox 		    ("vm_phys_enq_range: page %p has unexpected order %d",
7037493904eSAlan Cox 		    m, m->order));
7047493904eSAlan Cox 		order = ffs(npages) - 1;
7057493904eSAlan Cox 		KASSERT(order < VM_NFREEORDER,
7067493904eSAlan Cox 		    ("vm_phys_enq_range: order %d is out of range", order));
7077493904eSAlan Cox 		vm_freelist_add(fl, m, order, tail);
7087493904eSAlan Cox 		n = 1 << order;
7097493904eSAlan Cox 		m += n;
7107493904eSAlan Cox 		npages -= n;
7117493904eSAlan Cox 	} while (npages > 0);
7127493904eSAlan Cox }
7137493904eSAlan Cox 
7147493904eSAlan Cox /*
7158119cdd3SDoug Moore  * Set the pool for a contiguous, power of two-sized set of physical pages.
7168119cdd3SDoug Moore  */
7178119cdd3SDoug Moore static void
7188119cdd3SDoug Moore vm_phys_set_pool(int pool, vm_page_t m, int order)
7198119cdd3SDoug Moore {
7208119cdd3SDoug Moore 	vm_page_t m_tmp;
7218119cdd3SDoug Moore 
7228119cdd3SDoug Moore 	for (m_tmp = m; m_tmp < &m[1 << order]; m_tmp++)
7238119cdd3SDoug Moore 		m_tmp->pool = pool;
7248119cdd3SDoug Moore }
7258119cdd3SDoug Moore 
7268119cdd3SDoug Moore /*
72789ea39a7SAlan Cox  * Tries to allocate the specified number of pages from the specified pool
72889ea39a7SAlan Cox  * within the specified domain.  Returns the actual number of allocated pages
72989ea39a7SAlan Cox  * and a pointer to each page through the array ma[].
73089ea39a7SAlan Cox  *
73132d81f21SAlan Cox  * The returned pages may not be physically contiguous.  However, in contrast
73232d81f21SAlan Cox  * to performing multiple, back-to-back calls to vm_phys_alloc_pages(..., 0),
73332d81f21SAlan Cox  * calling this function once to allocate the desired number of pages will
73432d81f21SAlan Cox  * avoid wasted time in vm_phys_split_pages().
73589ea39a7SAlan Cox  *
73689ea39a7SAlan Cox  * The free page queues for the specified domain must be locked.
73789ea39a7SAlan Cox  */
73889ea39a7SAlan Cox int
73989ea39a7SAlan Cox vm_phys_alloc_npages(int domain, int pool, int npages, vm_page_t ma[])
74089ea39a7SAlan Cox {
74189ea39a7SAlan Cox 	struct vm_freelist *alt, *fl;
74289ea39a7SAlan Cox 	vm_page_t m;
74389ea39a7SAlan Cox 	int avail, end, flind, freelist, i, need, oind, pind;
74489ea39a7SAlan Cox 
74589ea39a7SAlan Cox 	KASSERT(domain >= 0 && domain < vm_ndomains,
74689ea39a7SAlan Cox 	    ("vm_phys_alloc_npages: domain %d is out of range", domain));
74789ea39a7SAlan Cox 	KASSERT(pool < VM_NFREEPOOL,
74889ea39a7SAlan Cox 	    ("vm_phys_alloc_npages: pool %d is out of range", pool));
74989ea39a7SAlan Cox 	KASSERT(npages <= 1 << (VM_NFREEORDER - 1),
75089ea39a7SAlan Cox 	    ("vm_phys_alloc_npages: npages %d is out of range", npages));
75189ea39a7SAlan Cox 	vm_domain_free_assert_locked(VM_DOMAIN(domain));
75289ea39a7SAlan Cox 	i = 0;
75389ea39a7SAlan Cox 	for (freelist = 0; freelist < VM_NFREELIST; freelist++) {
75489ea39a7SAlan Cox 		flind = vm_freelist_to_flind[freelist];
75589ea39a7SAlan Cox 		if (flind < 0)
75689ea39a7SAlan Cox 			continue;
75789ea39a7SAlan Cox 		fl = vm_phys_free_queues[domain][flind][pool];
75889ea39a7SAlan Cox 		for (oind = 0; oind < VM_NFREEORDER; oind++) {
75989ea39a7SAlan Cox 			while ((m = TAILQ_FIRST(&fl[oind].pl)) != NULL) {
76089ea39a7SAlan Cox 				vm_freelist_rem(fl, m, oind);
76189ea39a7SAlan Cox 				avail = 1 << oind;
76289ea39a7SAlan Cox 				need = imin(npages - i, avail);
76389ea39a7SAlan Cox 				for (end = i + need; i < end;)
76489ea39a7SAlan Cox 					ma[i++] = m++;
76589ea39a7SAlan Cox 				if (need < avail) {
7667493904eSAlan Cox 					/*
7677493904eSAlan Cox 					 * Return excess pages to fl.  Its
7687493904eSAlan Cox 					 * order [0, oind) queues are empty.
7697493904eSAlan Cox 					 */
7707493904eSAlan Cox 					vm_phys_enq_range(m, avail - need, fl,
7717493904eSAlan Cox 					    1);
77289ea39a7SAlan Cox 					return (npages);
77389ea39a7SAlan Cox 				} else if (i == npages)
77489ea39a7SAlan Cox 					return (npages);
77589ea39a7SAlan Cox 			}
77689ea39a7SAlan Cox 		}
77789ea39a7SAlan Cox 		for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
77889ea39a7SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
77989ea39a7SAlan Cox 				alt = vm_phys_free_queues[domain][flind][pind];
78089ea39a7SAlan Cox 				while ((m = TAILQ_FIRST(&alt[oind].pl)) !=
78189ea39a7SAlan Cox 				    NULL) {
78289ea39a7SAlan Cox 					vm_freelist_rem(alt, m, oind);
78389ea39a7SAlan Cox 					vm_phys_set_pool(pool, m, oind);
78489ea39a7SAlan Cox 					avail = 1 << oind;
78589ea39a7SAlan Cox 					need = imin(npages - i, avail);
78689ea39a7SAlan Cox 					for (end = i + need; i < end;)
78789ea39a7SAlan Cox 						ma[i++] = m++;
78889ea39a7SAlan Cox 					if (need < avail) {
7897493904eSAlan Cox 						/*
7907493904eSAlan Cox 						 * Return excess pages to fl.
7917493904eSAlan Cox 						 * Its order [0, oind) queues
7927493904eSAlan Cox 						 * are empty.
7937493904eSAlan Cox 						 */
7947493904eSAlan Cox 						vm_phys_enq_range(m, avail -
7957493904eSAlan Cox 						    need, fl, 1);
79689ea39a7SAlan Cox 						return (npages);
79789ea39a7SAlan Cox 					} else if (i == npages)
79889ea39a7SAlan Cox 						return (npages);
79989ea39a7SAlan Cox 				}
80089ea39a7SAlan Cox 			}
80189ea39a7SAlan Cox 		}
80289ea39a7SAlan Cox 	}
80389ea39a7SAlan Cox 	return (i);
80489ea39a7SAlan Cox }
80589ea39a7SAlan Cox 
80689ea39a7SAlan Cox /*
80711752d88SAlan Cox  * Allocate a contiguous, power of two-sized set of physical pages
80811752d88SAlan Cox  * from the free lists.
8098941dc44SAlan Cox  *
8108941dc44SAlan Cox  * The free page queues must be locked.
81111752d88SAlan Cox  */
81211752d88SAlan Cox vm_page_t
813ef435ae7SJeff Roberson vm_phys_alloc_pages(int domain, int pool, int order)
81411752d88SAlan Cox {
81549ca10d4SJayachandran C. 	vm_page_t m;
8160db2102aSMichael Zhilin 	int freelist;
81749ca10d4SJayachandran C. 
8180db2102aSMichael Zhilin 	for (freelist = 0; freelist < VM_NFREELIST; freelist++) {
8190db2102aSMichael Zhilin 		m = vm_phys_alloc_freelist_pages(domain, freelist, pool, order);
82049ca10d4SJayachandran C. 		if (m != NULL)
82149ca10d4SJayachandran C. 			return (m);
82249ca10d4SJayachandran C. 	}
82349ca10d4SJayachandran C. 	return (NULL);
82449ca10d4SJayachandran C. }
82549ca10d4SJayachandran C. 
82649ca10d4SJayachandran C. /*
827d866a563SAlan Cox  * Allocate a contiguous, power of two-sized set of physical pages from the
828d866a563SAlan Cox  * specified free list.  The free list must be specified using one of the
829d866a563SAlan Cox  * manifest constants VM_FREELIST_*.
830d866a563SAlan Cox  *
831d866a563SAlan Cox  * The free page queues must be locked.
83249ca10d4SJayachandran C.  */
83349ca10d4SJayachandran C. vm_page_t
8340db2102aSMichael Zhilin vm_phys_alloc_freelist_pages(int domain, int freelist, int pool, int order)
83549ca10d4SJayachandran C. {
836ef435ae7SJeff Roberson 	struct vm_freelist *alt, *fl;
83711752d88SAlan Cox 	vm_page_t m;
8380db2102aSMichael Zhilin 	int oind, pind, flind;
83911752d88SAlan Cox 
840ef435ae7SJeff Roberson 	KASSERT(domain >= 0 && domain < vm_ndomains,
841ef435ae7SJeff Roberson 	    ("vm_phys_alloc_freelist_pages: domain %d is out of range",
842ef435ae7SJeff Roberson 	    domain));
8430db2102aSMichael Zhilin 	KASSERT(freelist < VM_NFREELIST,
844d866a563SAlan Cox 	    ("vm_phys_alloc_freelist_pages: freelist %d is out of range",
8455be93778SAndrew Turner 	    freelist));
84611752d88SAlan Cox 	KASSERT(pool < VM_NFREEPOOL,
84749ca10d4SJayachandran C. 	    ("vm_phys_alloc_freelist_pages: pool %d is out of range", pool));
84811752d88SAlan Cox 	KASSERT(order < VM_NFREEORDER,
84949ca10d4SJayachandran C. 	    ("vm_phys_alloc_freelist_pages: order %d is out of range", order));
8506520495aSAdrian Chadd 
8510db2102aSMichael Zhilin 	flind = vm_freelist_to_flind[freelist];
8520db2102aSMichael Zhilin 	/* Check if freelist is present */
8530db2102aSMichael Zhilin 	if (flind < 0)
8540db2102aSMichael Zhilin 		return (NULL);
8550db2102aSMichael Zhilin 
856e2068d0bSJeff Roberson 	vm_domain_free_assert_locked(VM_DOMAIN(domain));
8577e226537SAttilio Rao 	fl = &vm_phys_free_queues[domain][flind][pool][0];
85811752d88SAlan Cox 	for (oind = order; oind < VM_NFREEORDER; oind++) {
85911752d88SAlan Cox 		m = TAILQ_FIRST(&fl[oind].pl);
86011752d88SAlan Cox 		if (m != NULL) {
8617e226537SAttilio Rao 			vm_freelist_rem(fl, m, oind);
862370a338aSAlan Cox 			/* The order [order, oind) queues are empty. */
863370a338aSAlan Cox 			vm_phys_split_pages(m, oind, fl, order, 1);
86411752d88SAlan Cox 			return (m);
86511752d88SAlan Cox 		}
86611752d88SAlan Cox 	}
86711752d88SAlan Cox 
86811752d88SAlan Cox 	/*
86911752d88SAlan Cox 	 * The given pool was empty.  Find the largest
87011752d88SAlan Cox 	 * contiguous, power-of-two-sized set of pages in any
87111752d88SAlan Cox 	 * pool.  Transfer these pages to the given pool, and
87211752d88SAlan Cox 	 * use them to satisfy the allocation.
87311752d88SAlan Cox 	 */
87411752d88SAlan Cox 	for (oind = VM_NFREEORDER - 1; oind >= order; oind--) {
87511752d88SAlan Cox 		for (pind = 0; pind < VM_NFREEPOOL; pind++) {
8767e226537SAttilio Rao 			alt = &vm_phys_free_queues[domain][flind][pind][0];
87711752d88SAlan Cox 			m = TAILQ_FIRST(&alt[oind].pl);
87811752d88SAlan Cox 			if (m != NULL) {
8797e226537SAttilio Rao 				vm_freelist_rem(alt, m, oind);
88011752d88SAlan Cox 				vm_phys_set_pool(pool, m, oind);
881370a338aSAlan Cox 				/* The order [order, oind) queues are empty. */
882370a338aSAlan Cox 				vm_phys_split_pages(m, oind, fl, order, 1);
88311752d88SAlan Cox 				return (m);
88411752d88SAlan Cox 			}
88511752d88SAlan Cox 		}
88611752d88SAlan Cox 	}
88711752d88SAlan Cox 	return (NULL);
88811752d88SAlan Cox }
88911752d88SAlan Cox 
89011752d88SAlan Cox /*
89111752d88SAlan Cox  * Find the vm_page corresponding to the given physical address.
89211752d88SAlan Cox  */
89311752d88SAlan Cox vm_page_t
89411752d88SAlan Cox vm_phys_paddr_to_vm_page(vm_paddr_t pa)
89511752d88SAlan Cox {
89611752d88SAlan Cox 	struct vm_phys_seg *seg;
89711752d88SAlan Cox 	int segind;
89811752d88SAlan Cox 
89911752d88SAlan Cox 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
90011752d88SAlan Cox 		seg = &vm_phys_segs[segind];
90111752d88SAlan Cox 		if (pa >= seg->start && pa < seg->end)
90211752d88SAlan Cox 			return (&seg->first_page[atop(pa - seg->start)]);
90311752d88SAlan Cox 	}
904f06a3a36SAndrew Thompson 	return (NULL);
90511752d88SAlan Cox }
90611752d88SAlan Cox 
907b6de32bdSKonstantin Belousov vm_page_t
908b6de32bdSKonstantin Belousov vm_phys_fictitious_to_vm_page(vm_paddr_t pa)
909b6de32bdSKonstantin Belousov {
91038d6b2dcSRoger Pau Monné 	struct vm_phys_fictitious_seg tmp, *seg;
911b6de32bdSKonstantin Belousov 	vm_page_t m;
912b6de32bdSKonstantin Belousov 
913b6de32bdSKonstantin Belousov 	m = NULL;
91438d6b2dcSRoger Pau Monné 	tmp.start = pa;
91538d6b2dcSRoger Pau Monné 	tmp.end = 0;
91638d6b2dcSRoger Pau Monné 
91738d6b2dcSRoger Pau Monné 	rw_rlock(&vm_phys_fictitious_reg_lock);
91838d6b2dcSRoger Pau Monné 	seg = RB_FIND(fict_tree, &vm_phys_fictitious_tree, &tmp);
91938d6b2dcSRoger Pau Monné 	rw_runlock(&vm_phys_fictitious_reg_lock);
92038d6b2dcSRoger Pau Monné 	if (seg == NULL)
92138d6b2dcSRoger Pau Monné 		return (NULL);
92238d6b2dcSRoger Pau Monné 
923b6de32bdSKonstantin Belousov 	m = &seg->first_page[atop(pa - seg->start)];
92438d6b2dcSRoger Pau Monné 	KASSERT((m->flags & PG_FICTITIOUS) != 0, ("%p not fictitious", m));
92538d6b2dcSRoger Pau Monné 
926b6de32bdSKonstantin Belousov 	return (m);
927b6de32bdSKonstantin Belousov }
928b6de32bdSKonstantin Belousov 
9295ebe728dSRoger Pau Monné static inline void
9305ebe728dSRoger Pau Monné vm_phys_fictitious_init_range(vm_page_t range, vm_paddr_t start,
9315ebe728dSRoger Pau Monné     long page_count, vm_memattr_t memattr)
9325ebe728dSRoger Pau Monné {
9335ebe728dSRoger Pau Monné 	long i;
9345ebe728dSRoger Pau Monné 
935f93f7cf1SMark Johnston 	bzero(range, page_count * sizeof(*range));
9365ebe728dSRoger Pau Monné 	for (i = 0; i < page_count; i++) {
9375ebe728dSRoger Pau Monné 		vm_page_initfake(&range[i], start + PAGE_SIZE * i, memattr);
9385ebe728dSRoger Pau Monné 		range[i].oflags &= ~VPO_UNMANAGED;
9395ebe728dSRoger Pau Monné 		range[i].busy_lock = VPB_UNBUSIED;
9405ebe728dSRoger Pau Monné 	}
9415ebe728dSRoger Pau Monné }
9425ebe728dSRoger Pau Monné 
943b6de32bdSKonstantin Belousov int
944b6de32bdSKonstantin Belousov vm_phys_fictitious_reg_range(vm_paddr_t start, vm_paddr_t end,
945b6de32bdSKonstantin Belousov     vm_memattr_t memattr)
946b6de32bdSKonstantin Belousov {
947b6de32bdSKonstantin Belousov 	struct vm_phys_fictitious_seg *seg;
948b6de32bdSKonstantin Belousov 	vm_page_t fp;
9495ebe728dSRoger Pau Monné 	long page_count;
950b6de32bdSKonstantin Belousov #ifdef VM_PHYSSEG_DENSE
9515ebe728dSRoger Pau Monné 	long pi, pe;
9525ebe728dSRoger Pau Monné 	long dpage_count;
953b6de32bdSKonstantin Belousov #endif
954b6de32bdSKonstantin Belousov 
9555ebe728dSRoger Pau Monné 	KASSERT(start < end,
9565ebe728dSRoger Pau Monné 	    ("Start of segment isn't less than end (start: %jx end: %jx)",
9575ebe728dSRoger Pau Monné 	    (uintmax_t)start, (uintmax_t)end));
9585ebe728dSRoger Pau Monné 
959b6de32bdSKonstantin Belousov 	page_count = (end - start) / PAGE_SIZE;
960b6de32bdSKonstantin Belousov 
961b6de32bdSKonstantin Belousov #ifdef VM_PHYSSEG_DENSE
962b6de32bdSKonstantin Belousov 	pi = atop(start);
9635ebe728dSRoger Pau Monné 	pe = atop(end);
9645ebe728dSRoger Pau Monné 	if (pi >= first_page && (pi - first_page) < vm_page_array_size) {
965b6de32bdSKonstantin Belousov 		fp = &vm_page_array[pi - first_page];
9665ebe728dSRoger Pau Monné 		if ((pe - first_page) > vm_page_array_size) {
9675ebe728dSRoger Pau Monné 			/*
9685ebe728dSRoger Pau Monné 			 * We have a segment that starts inside
9695ebe728dSRoger Pau Monné 			 * of vm_page_array, but ends outside of it.
9705ebe728dSRoger Pau Monné 			 *
9715ebe728dSRoger Pau Monné 			 * Use vm_page_array pages for those that are
9725ebe728dSRoger Pau Monné 			 * inside of the vm_page_array range, and
9735ebe728dSRoger Pau Monné 			 * allocate the remaining ones.
9745ebe728dSRoger Pau Monné 			 */
9755ebe728dSRoger Pau Monné 			dpage_count = vm_page_array_size - (pi - first_page);
9765ebe728dSRoger Pau Monné 			vm_phys_fictitious_init_range(fp, start, dpage_count,
9775ebe728dSRoger Pau Monné 			    memattr);
9785ebe728dSRoger Pau Monné 			page_count -= dpage_count;
9795ebe728dSRoger Pau Monné 			start += ptoa(dpage_count);
9805ebe728dSRoger Pau Monné 			goto alloc;
9815ebe728dSRoger Pau Monné 		}
9825ebe728dSRoger Pau Monné 		/*
9835ebe728dSRoger Pau Monné 		 * We can allocate the full range from vm_page_array,
9845ebe728dSRoger Pau Monné 		 * so there's no need to register the range in the tree.
9855ebe728dSRoger Pau Monné 		 */
9865ebe728dSRoger Pau Monné 		vm_phys_fictitious_init_range(fp, start, page_count, memattr);
9875ebe728dSRoger Pau Monné 		return (0);
9885ebe728dSRoger Pau Monné 	} else if (pe > first_page && (pe - first_page) < vm_page_array_size) {
9895ebe728dSRoger Pau Monné 		/*
9905ebe728dSRoger Pau Monné 		 * We have a segment that ends inside of vm_page_array,
9915ebe728dSRoger Pau Monné 		 * but starts outside of it.
9925ebe728dSRoger Pau Monné 		 */
9935ebe728dSRoger Pau Monné 		fp = &vm_page_array[0];
9945ebe728dSRoger Pau Monné 		dpage_count = pe - first_page;
9955ebe728dSRoger Pau Monné 		vm_phys_fictitious_init_range(fp, ptoa(first_page), dpage_count,
9965ebe728dSRoger Pau Monné 		    memattr);
9975ebe728dSRoger Pau Monné 		end -= ptoa(dpage_count);
9985ebe728dSRoger Pau Monné 		page_count -= dpage_count;
9995ebe728dSRoger Pau Monné 		goto alloc;
10005ebe728dSRoger Pau Monné 	} else if (pi < first_page && pe > (first_page + vm_page_array_size)) {
10015ebe728dSRoger Pau Monné 		/*
10025ebe728dSRoger Pau Monné 		 * Trying to register a fictitious range that expands before
10035ebe728dSRoger Pau Monné 		 * and after vm_page_array.
10045ebe728dSRoger Pau Monné 		 */
10055ebe728dSRoger Pau Monné 		return (EINVAL);
10065ebe728dSRoger Pau Monné 	} else {
10075ebe728dSRoger Pau Monné alloc:
1008b6de32bdSKonstantin Belousov #endif
1009b6de32bdSKonstantin Belousov 		fp = malloc(page_count * sizeof(struct vm_page), M_FICT_PAGES,
1010f93f7cf1SMark Johnston 		    M_WAITOK);
10115ebe728dSRoger Pau Monné #ifdef VM_PHYSSEG_DENSE
1012b6de32bdSKonstantin Belousov 	}
10135ebe728dSRoger Pau Monné #endif
10145ebe728dSRoger Pau Monné 	vm_phys_fictitious_init_range(fp, start, page_count, memattr);
101538d6b2dcSRoger Pau Monné 
101638d6b2dcSRoger Pau Monné 	seg = malloc(sizeof(*seg), M_FICT_PAGES, M_WAITOK | M_ZERO);
1017b6de32bdSKonstantin Belousov 	seg->start = start;
1018b6de32bdSKonstantin Belousov 	seg->end = end;
1019b6de32bdSKonstantin Belousov 	seg->first_page = fp;
102038d6b2dcSRoger Pau Monné 
102138d6b2dcSRoger Pau Monné 	rw_wlock(&vm_phys_fictitious_reg_lock);
102238d6b2dcSRoger Pau Monné 	RB_INSERT(fict_tree, &vm_phys_fictitious_tree, seg);
102338d6b2dcSRoger Pau Monné 	rw_wunlock(&vm_phys_fictitious_reg_lock);
102438d6b2dcSRoger Pau Monné 
1025b6de32bdSKonstantin Belousov 	return (0);
1026b6de32bdSKonstantin Belousov }
1027b6de32bdSKonstantin Belousov 
1028b6de32bdSKonstantin Belousov void
1029b6de32bdSKonstantin Belousov vm_phys_fictitious_unreg_range(vm_paddr_t start, vm_paddr_t end)
1030b6de32bdSKonstantin Belousov {
103138d6b2dcSRoger Pau Monné 	struct vm_phys_fictitious_seg *seg, tmp;
1032b6de32bdSKonstantin Belousov #ifdef VM_PHYSSEG_DENSE
10335ebe728dSRoger Pau Monné 	long pi, pe;
1034b6de32bdSKonstantin Belousov #endif
1035b6de32bdSKonstantin Belousov 
10365ebe728dSRoger Pau Monné 	KASSERT(start < end,
10375ebe728dSRoger Pau Monné 	    ("Start of segment isn't less than end (start: %jx end: %jx)",
10385ebe728dSRoger Pau Monné 	    (uintmax_t)start, (uintmax_t)end));
10395ebe728dSRoger Pau Monné 
1040b6de32bdSKonstantin Belousov #ifdef VM_PHYSSEG_DENSE
1041b6de32bdSKonstantin Belousov 	pi = atop(start);
10425ebe728dSRoger Pau Monné 	pe = atop(end);
10435ebe728dSRoger Pau Monné 	if (pi >= first_page && (pi - first_page) < vm_page_array_size) {
10445ebe728dSRoger Pau Monné 		if ((pe - first_page) <= vm_page_array_size) {
10455ebe728dSRoger Pau Monné 			/*
10465ebe728dSRoger Pau Monné 			 * This segment was allocated using vm_page_array
10475ebe728dSRoger Pau Monné 			 * only, there's nothing to do since those pages
10485ebe728dSRoger Pau Monné 			 * were never added to the tree.
10495ebe728dSRoger Pau Monné 			 */
10505ebe728dSRoger Pau Monné 			return;
10515ebe728dSRoger Pau Monné 		}
10525ebe728dSRoger Pau Monné 		/*
10535ebe728dSRoger Pau Monné 		 * We have a segment that starts inside
10545ebe728dSRoger Pau Monné 		 * of vm_page_array, but ends outside of it.
10555ebe728dSRoger Pau Monné 		 *
10565ebe728dSRoger Pau Monné 		 * Calculate how many pages were added to the
10575ebe728dSRoger Pau Monné 		 * tree and free them.
10585ebe728dSRoger Pau Monné 		 */
10595ebe728dSRoger Pau Monné 		start = ptoa(first_page + vm_page_array_size);
10605ebe728dSRoger Pau Monné 	} else if (pe > first_page && (pe - first_page) < vm_page_array_size) {
10615ebe728dSRoger Pau Monné 		/*
10625ebe728dSRoger Pau Monné 		 * We have a segment that ends inside of vm_page_array,
10635ebe728dSRoger Pau Monné 		 * but starts outside of it.
10645ebe728dSRoger Pau Monné 		 */
10655ebe728dSRoger Pau Monné 		end = ptoa(first_page);
10665ebe728dSRoger Pau Monné 	} else if (pi < first_page && pe > (first_page + vm_page_array_size)) {
10675ebe728dSRoger Pau Monné 		/* Since it's not possible to register such a range, panic. */
10685ebe728dSRoger Pau Monné 		panic(
10695ebe728dSRoger Pau Monné 		    "Unregistering not registered fictitious range [%#jx:%#jx]",
10705ebe728dSRoger Pau Monné 		    (uintmax_t)start, (uintmax_t)end);
10715ebe728dSRoger Pau Monné 	}
1072b6de32bdSKonstantin Belousov #endif
107338d6b2dcSRoger Pau Monné 	tmp.start = start;
107438d6b2dcSRoger Pau Monné 	tmp.end = 0;
1075b6de32bdSKonstantin Belousov 
107638d6b2dcSRoger Pau Monné 	rw_wlock(&vm_phys_fictitious_reg_lock);
107738d6b2dcSRoger Pau Monné 	seg = RB_FIND(fict_tree, &vm_phys_fictitious_tree, &tmp);
107838d6b2dcSRoger Pau Monné 	if (seg->start != start || seg->end != end) {
107938d6b2dcSRoger Pau Monné 		rw_wunlock(&vm_phys_fictitious_reg_lock);
108038d6b2dcSRoger Pau Monné 		panic(
108138d6b2dcSRoger Pau Monné 		    "Unregistering not registered fictitious range [%#jx:%#jx]",
108238d6b2dcSRoger Pau Monné 		    (uintmax_t)start, (uintmax_t)end);
108338d6b2dcSRoger Pau Monné 	}
108438d6b2dcSRoger Pau Monné 	RB_REMOVE(fict_tree, &vm_phys_fictitious_tree, seg);
108538d6b2dcSRoger Pau Monné 	rw_wunlock(&vm_phys_fictitious_reg_lock);
108638d6b2dcSRoger Pau Monné 	free(seg->first_page, M_FICT_PAGES);
108738d6b2dcSRoger Pau Monné 	free(seg, M_FICT_PAGES);
1088b6de32bdSKonstantin Belousov }
1089b6de32bdSKonstantin Belousov 
109011752d88SAlan Cox /*
109111752d88SAlan Cox  * Free a contiguous, power of two-sized set of physical pages.
10928941dc44SAlan Cox  *
10938941dc44SAlan Cox  * The free page queues must be locked.
109411752d88SAlan Cox  */
109511752d88SAlan Cox void
109611752d88SAlan Cox vm_phys_free_pages(vm_page_t m, int order)
109711752d88SAlan Cox {
109811752d88SAlan Cox 	struct vm_freelist *fl;
109911752d88SAlan Cox 	struct vm_phys_seg *seg;
11005c1f2cc4SAlan Cox 	vm_paddr_t pa;
110111752d88SAlan Cox 	vm_page_t m_buddy;
110211752d88SAlan Cox 
110311752d88SAlan Cox 	KASSERT(m->order == VM_NFREEORDER,
11043921068fSJeff Roberson 	    ("vm_phys_free_pages: page %p has unexpected order %d",
11053921068fSJeff Roberson 	    m, m->order));
110611752d88SAlan Cox 	KASSERT(m->pool < VM_NFREEPOOL,
11078941dc44SAlan Cox 	    ("vm_phys_free_pages: page %p has unexpected pool %d",
110811752d88SAlan Cox 	    m, m->pool));
110911752d88SAlan Cox 	KASSERT(order < VM_NFREEORDER,
11108941dc44SAlan Cox 	    ("vm_phys_free_pages: order %d is out of range", order));
111111752d88SAlan Cox 	seg = &vm_phys_segs[m->segind];
1112e2068d0bSJeff Roberson 	vm_domain_free_assert_locked(VM_DOMAIN(seg->domain));
11135c1f2cc4SAlan Cox 	if (order < VM_NFREEORDER - 1) {
11145c1f2cc4SAlan Cox 		pa = VM_PAGE_TO_PHYS(m);
11155c1f2cc4SAlan Cox 		do {
11165c1f2cc4SAlan Cox 			pa ^= ((vm_paddr_t)1 << (PAGE_SHIFT + order));
11175c1f2cc4SAlan Cox 			if (pa < seg->start || pa >= seg->end)
111811752d88SAlan Cox 				break;
11195c1f2cc4SAlan Cox 			m_buddy = &seg->first_page[atop(pa - seg->start)];
112011752d88SAlan Cox 			if (m_buddy->order != order)
112111752d88SAlan Cox 				break;
112211752d88SAlan Cox 			fl = (*seg->free_queues)[m_buddy->pool];
11237e226537SAttilio Rao 			vm_freelist_rem(fl, m_buddy, order);
112411752d88SAlan Cox 			if (m_buddy->pool != m->pool)
112511752d88SAlan Cox 				vm_phys_set_pool(m->pool, m_buddy, order);
112611752d88SAlan Cox 			order++;
11275c1f2cc4SAlan Cox 			pa &= ~(((vm_paddr_t)1 << (PAGE_SHIFT + order)) - 1);
112811752d88SAlan Cox 			m = &seg->first_page[atop(pa - seg->start)];
11295c1f2cc4SAlan Cox 		} while (order < VM_NFREEORDER - 1);
113011752d88SAlan Cox 	}
113111752d88SAlan Cox 	fl = (*seg->free_queues)[m->pool];
11327e226537SAttilio Rao 	vm_freelist_add(fl, m, order, 1);
113311752d88SAlan Cox }
113411752d88SAlan Cox 
113511752d88SAlan Cox /*
1136b8590daeSDoug Moore  * Return the largest possible order of a set of pages starting at m.
11375c1f2cc4SAlan Cox  */
1138b8590daeSDoug Moore static int
1139b8590daeSDoug Moore max_order(vm_page_t m)
11405c1f2cc4SAlan Cox {
11415c1f2cc4SAlan Cox 
11425c1f2cc4SAlan Cox 	/*
11435c1f2cc4SAlan Cox 	 * Unsigned "min" is used here so that "order" is assigned
11445c1f2cc4SAlan Cox 	 * "VM_NFREEORDER - 1" when "m"'s physical address is zero
11455c1f2cc4SAlan Cox 	 * or the low-order bits of its physical address are zero
11465c1f2cc4SAlan Cox 	 * because the size of a physical address exceeds the size of
11475c1f2cc4SAlan Cox 	 * a long.
11485c1f2cc4SAlan Cox 	 */
1149b8590daeSDoug Moore 	return (min(ffsl(VM_PAGE_TO_PHYS(m) >> PAGE_SHIFT) - 1,
1150b8590daeSDoug Moore 	    VM_NFREEORDER - 1));
11515c1f2cc4SAlan Cox }
1152b8590daeSDoug Moore 
1153b8590daeSDoug Moore /*
1154b8590daeSDoug Moore  * Free a contiguous, arbitrarily sized set of physical pages, without
1155b8590daeSDoug Moore  * merging across set boundaries.
1156b8590daeSDoug Moore  *
1157b8590daeSDoug Moore  * The free page queues must be locked.
1158b8590daeSDoug Moore  */
1159b8590daeSDoug Moore void
1160b8590daeSDoug Moore vm_phys_enqueue_contig(vm_page_t m, u_long npages)
1161b8590daeSDoug Moore {
1162b8590daeSDoug Moore 	struct vm_freelist *fl;
1163b8590daeSDoug Moore 	struct vm_phys_seg *seg;
1164b8590daeSDoug Moore 	vm_page_t m_end;
1165b8590daeSDoug Moore 	int order;
1166b8590daeSDoug Moore 
1167b8590daeSDoug Moore 	/*
1168b8590daeSDoug Moore 	 * Avoid unnecessary coalescing by freeing the pages in the largest
1169b8590daeSDoug Moore 	 * possible power-of-two-sized subsets.
1170b8590daeSDoug Moore 	 */
1171b8590daeSDoug Moore 	vm_domain_free_assert_locked(vm_pagequeue_domain(m));
1172b8590daeSDoug Moore 	seg = &vm_phys_segs[m->segind];
1173b8590daeSDoug Moore 	fl = (*seg->free_queues)[m->pool];
1174b8590daeSDoug Moore 	m_end = m + npages;
1175b8590daeSDoug Moore 	/* Free blocks of increasing size. */
1176b8590daeSDoug Moore 	while ((order = max_order(m)) < VM_NFREEORDER - 1 &&
1177b8590daeSDoug Moore 	    m + (1 << order) <= m_end) {
1178b8590daeSDoug Moore 		KASSERT(seg == &vm_phys_segs[m->segind],
1179b8590daeSDoug Moore 		    ("%s: page range [%p,%p) spans multiple segments",
1180b8590daeSDoug Moore 		    __func__, m_end - npages, m));
1181b8590daeSDoug Moore 		vm_freelist_add(fl, m, order, 1);
1182b8590daeSDoug Moore 		m += 1 << order;
11835c1f2cc4SAlan Cox 	}
1184b8590daeSDoug Moore 	/* Free blocks of maximum size. */
1185b8590daeSDoug Moore 	while (m + (1 << order) <= m_end) {
1186b8590daeSDoug Moore 		KASSERT(seg == &vm_phys_segs[m->segind],
1187b8590daeSDoug Moore 		    ("%s: page range [%p,%p) spans multiple segments",
1188b8590daeSDoug Moore 		    __func__, m_end - npages, m));
1189b8590daeSDoug Moore 		vm_freelist_add(fl, m, order, 1);
1190b8590daeSDoug Moore 		m += 1 << order;
1191b8590daeSDoug Moore 	}
1192b8590daeSDoug Moore 	/* Free blocks of diminishing size. */
1193b8590daeSDoug Moore 	while (m < m_end) {
1194b8590daeSDoug Moore 		KASSERT(seg == &vm_phys_segs[m->segind],
1195b8590daeSDoug Moore 		    ("%s: page range [%p,%p) spans multiple segments",
1196b8590daeSDoug Moore 		    __func__, m_end - npages, m));
1197b8590daeSDoug Moore 		order = flsl(m_end - m) - 1;
1198b8590daeSDoug Moore 		vm_freelist_add(fl, m, order, 1);
1199b8590daeSDoug Moore 		m += 1 << order;
1200b8590daeSDoug Moore 	}
1201b8590daeSDoug Moore }
1202b8590daeSDoug Moore 
1203b8590daeSDoug Moore /*
1204b8590daeSDoug Moore  * Free a contiguous, arbitrarily sized set of physical pages.
1205b8590daeSDoug Moore  *
1206b8590daeSDoug Moore  * The free page queues must be locked.
1207b8590daeSDoug Moore  */
1208b8590daeSDoug Moore void
1209b8590daeSDoug Moore vm_phys_free_contig(vm_page_t m, u_long npages)
1210b8590daeSDoug Moore {
1211b8590daeSDoug Moore 	int order_start, order_end;
1212b8590daeSDoug Moore 	vm_page_t m_start, m_end;
1213b8590daeSDoug Moore 
1214b8590daeSDoug Moore 	vm_domain_free_assert_locked(vm_pagequeue_domain(m));
1215b8590daeSDoug Moore 
1216b8590daeSDoug Moore 	m_start = m;
1217b8590daeSDoug Moore 	order_start = max_order(m_start);
1218b8590daeSDoug Moore 	if (order_start < VM_NFREEORDER - 1)
1219b8590daeSDoug Moore 		m_start += 1 << order_start;
1220b8590daeSDoug Moore 	m_end = m + npages;
1221b8590daeSDoug Moore 	order_end = max_order(m_end);
1222b8590daeSDoug Moore 	if (order_end < VM_NFREEORDER - 1)
1223b8590daeSDoug Moore 		m_end -= 1 << order_end;
1224b8590daeSDoug Moore 	/*
1225b8590daeSDoug Moore 	 * Avoid unnecessary coalescing by freeing the pages at the start and
1226b8590daeSDoug Moore 	 * end of the range last.
1227b8590daeSDoug Moore 	 */
1228b8590daeSDoug Moore 	if (m_start < m_end)
1229b8590daeSDoug Moore 		vm_phys_enqueue_contig(m_start, m_end - m_start);
1230b8590daeSDoug Moore 	if (order_start < VM_NFREEORDER - 1)
1231b8590daeSDoug Moore 		vm_phys_free_pages(m, order_start);
1232b8590daeSDoug Moore 	if (order_end < VM_NFREEORDER - 1)
1233b8590daeSDoug Moore 		vm_phys_free_pages(m_end, order_end);
12345c1f2cc4SAlan Cox }
12355c1f2cc4SAlan Cox 
12365c1f2cc4SAlan Cox /*
1237c869e672SAlan Cox  * Scan physical memory between the specified addresses "low" and "high" for a
1238c869e672SAlan Cox  * run of contiguous physical pages that satisfy the specified conditions, and
1239c869e672SAlan Cox  * return the lowest page in the run.  The specified "alignment" determines
1240c869e672SAlan Cox  * the alignment of the lowest physical page in the run.  If the specified
1241c869e672SAlan Cox  * "boundary" is non-zero, then the run of physical pages cannot span a
1242c869e672SAlan Cox  * physical address that is a multiple of "boundary".
1243c869e672SAlan Cox  *
1244c869e672SAlan Cox  * "npages" must be greater than zero.  Both "alignment" and "boundary" must
1245c869e672SAlan Cox  * be a power of two.
1246c869e672SAlan Cox  */
1247c869e672SAlan Cox vm_page_t
12483f289c3fSJeff Roberson vm_phys_scan_contig(int domain, u_long npages, vm_paddr_t low, vm_paddr_t high,
1249c869e672SAlan Cox     u_long alignment, vm_paddr_t boundary, int options)
1250c869e672SAlan Cox {
1251c869e672SAlan Cox 	vm_paddr_t pa_end;
1252c869e672SAlan Cox 	vm_page_t m_end, m_run, m_start;
1253c869e672SAlan Cox 	struct vm_phys_seg *seg;
1254c869e672SAlan Cox 	int segind;
1255c869e672SAlan Cox 
1256c869e672SAlan Cox 	KASSERT(npages > 0, ("npages is 0"));
1257c869e672SAlan Cox 	KASSERT(powerof2(alignment), ("alignment is not a power of 2"));
1258c869e672SAlan Cox 	KASSERT(powerof2(boundary), ("boundary is not a power of 2"));
1259c869e672SAlan Cox 	if (low >= high)
1260c869e672SAlan Cox 		return (NULL);
1261c869e672SAlan Cox 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
1262c869e672SAlan Cox 		seg = &vm_phys_segs[segind];
12633f289c3fSJeff Roberson 		if (seg->domain != domain)
12643f289c3fSJeff Roberson 			continue;
1265c869e672SAlan Cox 		if (seg->start >= high)
1266c869e672SAlan Cox 			break;
1267c869e672SAlan Cox 		if (low >= seg->end)
1268c869e672SAlan Cox 			continue;
1269c869e672SAlan Cox 		if (low <= seg->start)
1270c869e672SAlan Cox 			m_start = seg->first_page;
1271c869e672SAlan Cox 		else
1272c869e672SAlan Cox 			m_start = &seg->first_page[atop(low - seg->start)];
1273c869e672SAlan Cox 		if (high < seg->end)
1274c869e672SAlan Cox 			pa_end = high;
1275c869e672SAlan Cox 		else
1276c869e672SAlan Cox 			pa_end = seg->end;
1277c869e672SAlan Cox 		if (pa_end - VM_PAGE_TO_PHYS(m_start) < ptoa(npages))
1278c869e672SAlan Cox 			continue;
1279c869e672SAlan Cox 		m_end = &seg->first_page[atop(pa_end - seg->start)];
1280c869e672SAlan Cox 		m_run = vm_page_scan_contig(npages, m_start, m_end,
1281c869e672SAlan Cox 		    alignment, boundary, options);
1282c869e672SAlan Cox 		if (m_run != NULL)
1283c869e672SAlan Cox 			return (m_run);
1284c869e672SAlan Cox 	}
1285c869e672SAlan Cox 	return (NULL);
1286c869e672SAlan Cox }
1287c869e672SAlan Cox 
1288c869e672SAlan Cox /*
12899742373aSAlan Cox  * Search for the given physical page "m" in the free lists.  If the search
12909742373aSAlan Cox  * succeeds, remove "m" from the free lists and return TRUE.  Otherwise, return
12919742373aSAlan Cox  * FALSE, indicating that "m" is not in the free lists.
12927bfda801SAlan Cox  *
12937bfda801SAlan Cox  * The free page queues must be locked.
12947bfda801SAlan Cox  */
1295e35395ceSAlan Cox boolean_t
12967bfda801SAlan Cox vm_phys_unfree_page(vm_page_t m)
12977bfda801SAlan Cox {
12987bfda801SAlan Cox 	struct vm_freelist *fl;
12997bfda801SAlan Cox 	struct vm_phys_seg *seg;
13007bfda801SAlan Cox 	vm_paddr_t pa, pa_half;
13017bfda801SAlan Cox 	vm_page_t m_set, m_tmp;
13027bfda801SAlan Cox 	int order;
13037bfda801SAlan Cox 
13047bfda801SAlan Cox 	/*
13057bfda801SAlan Cox 	 * First, find the contiguous, power of two-sized set of free
13067bfda801SAlan Cox 	 * physical pages containing the given physical page "m" and
13077bfda801SAlan Cox 	 * assign it to "m_set".
13087bfda801SAlan Cox 	 */
13097bfda801SAlan Cox 	seg = &vm_phys_segs[m->segind];
1310e2068d0bSJeff Roberson 	vm_domain_free_assert_locked(VM_DOMAIN(seg->domain));
13117bfda801SAlan Cox 	for (m_set = m, order = 0; m_set->order == VM_NFREEORDER &&
1312bc8794a1SAlan Cox 	    order < VM_NFREEORDER - 1; ) {
13137bfda801SAlan Cox 		order++;
13147bfda801SAlan Cox 		pa = m->phys_addr & (~(vm_paddr_t)0 << (PAGE_SHIFT + order));
13152fbced65SAlan Cox 		if (pa >= seg->start)
13167bfda801SAlan Cox 			m_set = &seg->first_page[atop(pa - seg->start)];
1317e35395ceSAlan Cox 		else
1318e35395ceSAlan Cox 			return (FALSE);
13197bfda801SAlan Cox 	}
1320e35395ceSAlan Cox 	if (m_set->order < order)
1321e35395ceSAlan Cox 		return (FALSE);
1322e35395ceSAlan Cox 	if (m_set->order == VM_NFREEORDER)
1323e35395ceSAlan Cox 		return (FALSE);
13247bfda801SAlan Cox 	KASSERT(m_set->order < VM_NFREEORDER,
13257bfda801SAlan Cox 	    ("vm_phys_unfree_page: page %p has unexpected order %d",
13267bfda801SAlan Cox 	    m_set, m_set->order));
13277bfda801SAlan Cox 
13287bfda801SAlan Cox 	/*
13297bfda801SAlan Cox 	 * Next, remove "m_set" from the free lists.  Finally, extract
13307bfda801SAlan Cox 	 * "m" from "m_set" using an iterative algorithm: While "m_set"
13317bfda801SAlan Cox 	 * is larger than a page, shrink "m_set" by returning the half
13327bfda801SAlan Cox 	 * of "m_set" that does not contain "m" to the free lists.
13337bfda801SAlan Cox 	 */
13347bfda801SAlan Cox 	fl = (*seg->free_queues)[m_set->pool];
13357bfda801SAlan Cox 	order = m_set->order;
13367e226537SAttilio Rao 	vm_freelist_rem(fl, m_set, order);
13377bfda801SAlan Cox 	while (order > 0) {
13387bfda801SAlan Cox 		order--;
13397bfda801SAlan Cox 		pa_half = m_set->phys_addr ^ (1 << (PAGE_SHIFT + order));
13407bfda801SAlan Cox 		if (m->phys_addr < pa_half)
13417bfda801SAlan Cox 			m_tmp = &seg->first_page[atop(pa_half - seg->start)];
13427bfda801SAlan Cox 		else {
13437bfda801SAlan Cox 			m_tmp = m_set;
13447bfda801SAlan Cox 			m_set = &seg->first_page[atop(pa_half - seg->start)];
13457bfda801SAlan Cox 		}
13467e226537SAttilio Rao 		vm_freelist_add(fl, m_tmp, order, 0);
13477bfda801SAlan Cox 	}
13487bfda801SAlan Cox 	KASSERT(m_set == m, ("vm_phys_unfree_page: fatal inconsistency"));
1349e35395ceSAlan Cox 	return (TRUE);
13507bfda801SAlan Cox }
13517bfda801SAlan Cox 
13527bfda801SAlan Cox /*
13532f9f48d6SAlan Cox  * Allocate a contiguous set of physical pages of the given size
13542f9f48d6SAlan Cox  * "npages" from the free lists.  All of the physical pages must be at
13552f9f48d6SAlan Cox  * or above the given physical address "low" and below the given
13562f9f48d6SAlan Cox  * physical address "high".  The given value "alignment" determines the
13572f9f48d6SAlan Cox  * alignment of the first physical page in the set.  If the given value
13582f9f48d6SAlan Cox  * "boundary" is non-zero, then the set of physical pages cannot cross
13592f9f48d6SAlan Cox  * any physical address boundary that is a multiple of that value.  Both
136011752d88SAlan Cox  * "alignment" and "boundary" must be a power of two.
136111752d88SAlan Cox  */
136211752d88SAlan Cox vm_page_t
1363ef435ae7SJeff Roberson vm_phys_alloc_contig(int domain, u_long npages, vm_paddr_t low, vm_paddr_t high,
13645c1f2cc4SAlan Cox     u_long alignment, vm_paddr_t boundary)
136511752d88SAlan Cox {
1366c869e672SAlan Cox 	vm_paddr_t pa_end, pa_start;
1367c869e672SAlan Cox 	vm_page_t m_run;
1368c869e672SAlan Cox 	struct vm_phys_seg *seg;
1369ef435ae7SJeff Roberson 	int segind;
137011752d88SAlan Cox 
1371c869e672SAlan Cox 	KASSERT(npages > 0, ("npages is 0"));
1372c869e672SAlan Cox 	KASSERT(powerof2(alignment), ("alignment is not a power of 2"));
1373c869e672SAlan Cox 	KASSERT(powerof2(boundary), ("boundary is not a power of 2"));
1374e2068d0bSJeff Roberson 	vm_domain_free_assert_locked(VM_DOMAIN(domain));
1375c869e672SAlan Cox 	if (low >= high)
1376c869e672SAlan Cox 		return (NULL);
1377c869e672SAlan Cox 	m_run = NULL;
1378477bffbeSAlan Cox 	for (segind = vm_phys_nsegs - 1; segind >= 0; segind--) {
1379c869e672SAlan Cox 		seg = &vm_phys_segs[segind];
1380477bffbeSAlan Cox 		if (seg->start >= high || seg->domain != domain)
138111752d88SAlan Cox 			continue;
1382477bffbeSAlan Cox 		if (low >= seg->end)
1383477bffbeSAlan Cox 			break;
1384c869e672SAlan Cox 		if (low <= seg->start)
1385c869e672SAlan Cox 			pa_start = seg->start;
1386c869e672SAlan Cox 		else
1387c869e672SAlan Cox 			pa_start = low;
1388c869e672SAlan Cox 		if (high < seg->end)
1389c869e672SAlan Cox 			pa_end = high;
1390c869e672SAlan Cox 		else
1391c869e672SAlan Cox 			pa_end = seg->end;
1392c869e672SAlan Cox 		if (pa_end - pa_start < ptoa(npages))
1393c869e672SAlan Cox 			continue;
1394c869e672SAlan Cox 		m_run = vm_phys_alloc_seg_contig(seg, npages, low, high,
1395c869e672SAlan Cox 		    alignment, boundary);
1396c869e672SAlan Cox 		if (m_run != NULL)
1397c869e672SAlan Cox 			break;
1398c869e672SAlan Cox 	}
1399c869e672SAlan Cox 	return (m_run);
1400c869e672SAlan Cox }
140111752d88SAlan Cox 
140211752d88SAlan Cox /*
1403c869e672SAlan Cox  * Allocate a run of contiguous physical pages from the free list for the
1404c869e672SAlan Cox  * specified segment.
1405c869e672SAlan Cox  */
1406c869e672SAlan Cox static vm_page_t
1407c869e672SAlan Cox vm_phys_alloc_seg_contig(struct vm_phys_seg *seg, u_long npages,
1408c869e672SAlan Cox     vm_paddr_t low, vm_paddr_t high, u_long alignment, vm_paddr_t boundary)
1409c869e672SAlan Cox {
1410c869e672SAlan Cox 	struct vm_freelist *fl;
1411c869e672SAlan Cox 	vm_paddr_t pa, pa_end, size;
1412c869e672SAlan Cox 	vm_page_t m, m_ret;
1413c869e672SAlan Cox 	u_long npages_end;
1414c869e672SAlan Cox 	int oind, order, pind;
1415c869e672SAlan Cox 
1416c869e672SAlan Cox 	KASSERT(npages > 0, ("npages is 0"));
1417c869e672SAlan Cox 	KASSERT(powerof2(alignment), ("alignment is not a power of 2"));
1418c869e672SAlan Cox 	KASSERT(powerof2(boundary), ("boundary is not a power of 2"));
1419e2068d0bSJeff Roberson 	vm_domain_free_assert_locked(VM_DOMAIN(seg->domain));
1420c869e672SAlan Cox 	/* Compute the queue that is the best fit for npages. */
14219161b4deSAlan Cox 	order = flsl(npages - 1);
1422c869e672SAlan Cox 	/* Search for a run satisfying the specified conditions. */
1423c869e672SAlan Cox 	size = npages << PAGE_SHIFT;
1424c869e672SAlan Cox 	for (oind = min(order, VM_NFREEORDER - 1); oind < VM_NFREEORDER;
1425c869e672SAlan Cox 	    oind++) {
1426c869e672SAlan Cox 		for (pind = 0; pind < VM_NFREEPOOL; pind++) {
1427c869e672SAlan Cox 			fl = (*seg->free_queues)[pind];
14285cd29d0fSMark Johnston 			TAILQ_FOREACH(m_ret, &fl[oind].pl, listq) {
1429c869e672SAlan Cox 				/*
143011752d88SAlan Cox 				 * Is the size of this allocation request
143111752d88SAlan Cox 				 * larger than the largest block size?
143211752d88SAlan Cox 				 */
143311752d88SAlan Cox 				if (order >= VM_NFREEORDER) {
143411752d88SAlan Cox 					/*
1435c869e672SAlan Cox 					 * Determine if a sufficient number of
1436c869e672SAlan Cox 					 * subsequent blocks to satisfy the
1437c869e672SAlan Cox 					 * allocation request are free.
143811752d88SAlan Cox 					 */
143911752d88SAlan Cox 					pa = VM_PAGE_TO_PHYS(m_ret);
1440c869e672SAlan Cox 					pa_end = pa + size;
144179e9552eSKonstantin Belousov 					if (pa_end < pa)
144279e9552eSKonstantin Belousov 						continue;
144311752d88SAlan Cox 					for (;;) {
1444c869e672SAlan Cox 						pa += 1 << (PAGE_SHIFT +
1445c869e672SAlan Cox 						    VM_NFREEORDER - 1);
1446c869e672SAlan Cox 						if (pa >= pa_end ||
1447c869e672SAlan Cox 						    pa < seg->start ||
144811752d88SAlan Cox 						    pa >= seg->end)
144911752d88SAlan Cox 							break;
1450c869e672SAlan Cox 						m = &seg->first_page[atop(pa -
1451c869e672SAlan Cox 						    seg->start)];
1452c869e672SAlan Cox 						if (m->order != VM_NFREEORDER -
1453c869e672SAlan Cox 						    1)
145411752d88SAlan Cox 							break;
145511752d88SAlan Cox 					}
1456c869e672SAlan Cox 					/* If not, go to the next block. */
1457c869e672SAlan Cox 					if (pa < pa_end)
145811752d88SAlan Cox 						continue;
145911752d88SAlan Cox 				}
146011752d88SAlan Cox 
146111752d88SAlan Cox 				/*
1462c869e672SAlan Cox 				 * Determine if the blocks are within the
1463c869e672SAlan Cox 				 * given range, satisfy the given alignment,
1464c869e672SAlan Cox 				 * and do not cross the given boundary.
146511752d88SAlan Cox 				 */
146611752d88SAlan Cox 				pa = VM_PAGE_TO_PHYS(m_ret);
1467c869e672SAlan Cox 				pa_end = pa + size;
1468d9c9c81cSPedro F. Giffuni 				if (pa >= low && pa_end <= high &&
1469*c606ab59SDoug Moore 				    vm_addr_ok(pa, size, alignment, boundary))
147011752d88SAlan Cox 					goto done;
147111752d88SAlan Cox 			}
147211752d88SAlan Cox 		}
147311752d88SAlan Cox 	}
147411752d88SAlan Cox 	return (NULL);
147511752d88SAlan Cox done:
147611752d88SAlan Cox 	for (m = m_ret; m < &m_ret[npages]; m = &m[1 << oind]) {
147711752d88SAlan Cox 		fl = (*seg->free_queues)[m->pool];
14789161b4deSAlan Cox 		vm_freelist_rem(fl, m, oind);
14799161b4deSAlan Cox 		if (m->pool != VM_FREEPOOL_DEFAULT)
14809161b4deSAlan Cox 			vm_phys_set_pool(VM_FREEPOOL_DEFAULT, m, oind);
148111752d88SAlan Cox 	}
14825c1f2cc4SAlan Cox 	/* Return excess pages to the free lists. */
14839161b4deSAlan Cox 	npages_end = roundup2(npages, 1 << oind);
14847493904eSAlan Cox 	if (npages < npages_end) {
14857493904eSAlan Cox 		fl = (*seg->free_queues)[VM_FREEPOOL_DEFAULT];
14867493904eSAlan Cox 		vm_phys_enq_range(&m_ret[npages], npages_end - npages, fl, 0);
14877493904eSAlan Cox 	}
148811752d88SAlan Cox 	return (m_ret);
148911752d88SAlan Cox }
149011752d88SAlan Cox 
1491b7565d44SJeff Roberson /*
1492b7565d44SJeff Roberson  * Return the index of the first unused slot which may be the terminating
1493b7565d44SJeff Roberson  * entry.
1494b7565d44SJeff Roberson  */
1495b7565d44SJeff Roberson static int
1496b7565d44SJeff Roberson vm_phys_avail_count(void)
1497b7565d44SJeff Roberson {
1498b7565d44SJeff Roberson 	int i;
1499b7565d44SJeff Roberson 
1500b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1]; i += 2)
1501b7565d44SJeff Roberson 		continue;
1502b7565d44SJeff Roberson 	if (i > PHYS_AVAIL_ENTRIES)
1503b7565d44SJeff Roberson 		panic("Improperly terminated phys_avail %d entries", i);
1504b7565d44SJeff Roberson 
1505b7565d44SJeff Roberson 	return (i);
1506b7565d44SJeff Roberson }
1507b7565d44SJeff Roberson 
1508b7565d44SJeff Roberson /*
1509b7565d44SJeff Roberson  * Assert that a phys_avail entry is valid.
1510b7565d44SJeff Roberson  */
1511b7565d44SJeff Roberson static void
1512b7565d44SJeff Roberson vm_phys_avail_check(int i)
1513b7565d44SJeff Roberson {
1514b7565d44SJeff Roberson 	if (phys_avail[i] & PAGE_MASK)
1515b7565d44SJeff Roberson 		panic("Unaligned phys_avail[%d]: %#jx", i,
1516b7565d44SJeff Roberson 		    (intmax_t)phys_avail[i]);
1517b7565d44SJeff Roberson 	if (phys_avail[i+1] & PAGE_MASK)
1518b7565d44SJeff Roberson 		panic("Unaligned phys_avail[%d + 1]: %#jx", i,
1519b7565d44SJeff Roberson 		    (intmax_t)phys_avail[i]);
1520b7565d44SJeff Roberson 	if (phys_avail[i + 1] < phys_avail[i])
1521b7565d44SJeff Roberson 		panic("phys_avail[%d] start %#jx < end %#jx", i,
1522b7565d44SJeff Roberson 		    (intmax_t)phys_avail[i], (intmax_t)phys_avail[i+1]);
1523b7565d44SJeff Roberson }
1524b7565d44SJeff Roberson 
1525b7565d44SJeff Roberson /*
1526b7565d44SJeff Roberson  * Return the index of an overlapping phys_avail entry or -1.
1527b7565d44SJeff Roberson  */
1528be3f5f29SJeff Roberson #ifdef NUMA
1529b7565d44SJeff Roberson static int
1530b7565d44SJeff Roberson vm_phys_avail_find(vm_paddr_t pa)
1531b7565d44SJeff Roberson {
1532b7565d44SJeff Roberson 	int i;
1533b7565d44SJeff Roberson 
1534b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1]; i += 2)
1535b7565d44SJeff Roberson 		if (phys_avail[i] <= pa && phys_avail[i + 1] > pa)
1536b7565d44SJeff Roberson 			return (i);
1537b7565d44SJeff Roberson 	return (-1);
1538b7565d44SJeff Roberson }
1539be3f5f29SJeff Roberson #endif
1540b7565d44SJeff Roberson 
1541b7565d44SJeff Roberson /*
1542b7565d44SJeff Roberson  * Return the index of the largest entry.
1543b7565d44SJeff Roberson  */
1544b7565d44SJeff Roberson int
1545b7565d44SJeff Roberson vm_phys_avail_largest(void)
1546b7565d44SJeff Roberson {
1547b7565d44SJeff Roberson 	vm_paddr_t sz, largesz;
1548b7565d44SJeff Roberson 	int largest;
1549b7565d44SJeff Roberson 	int i;
1550b7565d44SJeff Roberson 
1551b7565d44SJeff Roberson 	largest = 0;
1552b7565d44SJeff Roberson 	largesz = 0;
1553b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1]; i += 2) {
1554b7565d44SJeff Roberson 		sz = vm_phys_avail_size(i);
1555b7565d44SJeff Roberson 		if (sz > largesz) {
1556b7565d44SJeff Roberson 			largesz = sz;
1557b7565d44SJeff Roberson 			largest = i;
1558b7565d44SJeff Roberson 		}
1559b7565d44SJeff Roberson 	}
1560b7565d44SJeff Roberson 
1561b7565d44SJeff Roberson 	return (largest);
1562b7565d44SJeff Roberson }
1563b7565d44SJeff Roberson 
1564b7565d44SJeff Roberson vm_paddr_t
1565b7565d44SJeff Roberson vm_phys_avail_size(int i)
1566b7565d44SJeff Roberson {
1567b7565d44SJeff Roberson 
1568b7565d44SJeff Roberson 	return (phys_avail[i + 1] - phys_avail[i]);
1569b7565d44SJeff Roberson }
1570b7565d44SJeff Roberson 
1571b7565d44SJeff Roberson /*
1572b7565d44SJeff Roberson  * Split an entry at the address 'pa'.  Return zero on success or errno.
1573b7565d44SJeff Roberson  */
1574b7565d44SJeff Roberson static int
1575b7565d44SJeff Roberson vm_phys_avail_split(vm_paddr_t pa, int i)
1576b7565d44SJeff Roberson {
1577b7565d44SJeff Roberson 	int cnt;
1578b7565d44SJeff Roberson 
1579b7565d44SJeff Roberson 	vm_phys_avail_check(i);
1580b7565d44SJeff Roberson 	if (pa <= phys_avail[i] || pa >= phys_avail[i + 1])
1581b7565d44SJeff Roberson 		panic("vm_phys_avail_split: invalid address");
1582b7565d44SJeff Roberson 	cnt = vm_phys_avail_count();
1583b7565d44SJeff Roberson 	if (cnt >= PHYS_AVAIL_ENTRIES)
1584b7565d44SJeff Roberson 		return (ENOSPC);
1585b7565d44SJeff Roberson 	memmove(&phys_avail[i + 2], &phys_avail[i],
1586b7565d44SJeff Roberson 	    (cnt - i) * sizeof(phys_avail[0]));
1587b7565d44SJeff Roberson 	phys_avail[i + 1] = pa;
1588b7565d44SJeff Roberson 	phys_avail[i + 2] = pa;
1589b7565d44SJeff Roberson 	vm_phys_avail_check(i);
1590b7565d44SJeff Roberson 	vm_phys_avail_check(i+2);
1591b7565d44SJeff Roberson 
1592b7565d44SJeff Roberson 	return (0);
1593b7565d44SJeff Roberson }
1594b7565d44SJeff Roberson 
159531991a5aSMitchell Horne /*
159631991a5aSMitchell Horne  * Check if a given physical address can be included as part of a crash dump.
159731991a5aSMitchell Horne  */
159831991a5aSMitchell Horne bool
159931991a5aSMitchell Horne vm_phys_is_dumpable(vm_paddr_t pa)
160031991a5aSMitchell Horne {
160131991a5aSMitchell Horne 	vm_page_t m;
160231991a5aSMitchell Horne 	int i;
160331991a5aSMitchell Horne 
160431991a5aSMitchell Horne 	if ((m = vm_phys_paddr_to_vm_page(pa)) != NULL)
160531991a5aSMitchell Horne 		return ((m->flags & PG_NODUMP) == 0);
160631991a5aSMitchell Horne 
160731991a5aSMitchell Horne 	for (i = 0; dump_avail[i] != 0 || dump_avail[i + 1] != 0; i += 2) {
160831991a5aSMitchell Horne 		if (pa >= dump_avail[i] && pa < dump_avail[i + 1])
160931991a5aSMitchell Horne 			return (true);
161031991a5aSMitchell Horne 	}
161131991a5aSMitchell Horne 	return (false);
161231991a5aSMitchell Horne }
161331991a5aSMitchell Horne 
161481302f1dSMark Johnston void
161581302f1dSMark Johnston vm_phys_early_add_seg(vm_paddr_t start, vm_paddr_t end)
161681302f1dSMark Johnston {
161781302f1dSMark Johnston 	struct vm_phys_seg *seg;
161881302f1dSMark Johnston 
161981302f1dSMark Johnston 	if (vm_phys_early_nsegs == -1)
162081302f1dSMark Johnston 		panic("%s: called after initialization", __func__);
162181302f1dSMark Johnston 	if (vm_phys_early_nsegs == nitems(vm_phys_early_segs))
162281302f1dSMark Johnston 		panic("%s: ran out of early segments", __func__);
162381302f1dSMark Johnston 
162481302f1dSMark Johnston 	seg = &vm_phys_early_segs[vm_phys_early_nsegs++];
162581302f1dSMark Johnston 	seg->start = start;
162681302f1dSMark Johnston 	seg->end = end;
162781302f1dSMark Johnston }
162881302f1dSMark Johnston 
1629b7565d44SJeff Roberson /*
1630b7565d44SJeff Roberson  * This routine allocates NUMA node specific memory before the page
1631b7565d44SJeff Roberson  * allocator is bootstrapped.
1632b7565d44SJeff Roberson  */
1633b7565d44SJeff Roberson vm_paddr_t
1634b7565d44SJeff Roberson vm_phys_early_alloc(int domain, size_t alloc_size)
1635b7565d44SJeff Roberson {
1636b7565d44SJeff Roberson 	int i, mem_index, biggestone;
1637b7565d44SJeff Roberson 	vm_paddr_t pa, mem_start, mem_end, size, biggestsize, align;
1638b7565d44SJeff Roberson 
163981302f1dSMark Johnston 	KASSERT(domain == -1 || (domain >= 0 && domain < vm_ndomains),
164081302f1dSMark Johnston 	    ("%s: invalid domain index %d", __func__, domain));
1641b7565d44SJeff Roberson 
1642b7565d44SJeff Roberson 	/*
1643b7565d44SJeff Roberson 	 * Search the mem_affinity array for the biggest address
1644b7565d44SJeff Roberson 	 * range in the desired domain.  This is used to constrain
1645b7565d44SJeff Roberson 	 * the phys_avail selection below.
1646b7565d44SJeff Roberson 	 */
1647b7565d44SJeff Roberson 	biggestsize = 0;
1648b7565d44SJeff Roberson 	mem_index = 0;
1649b7565d44SJeff Roberson 	mem_start = 0;
1650b7565d44SJeff Roberson 	mem_end = -1;
1651b7565d44SJeff Roberson #ifdef NUMA
1652b7565d44SJeff Roberson 	if (mem_affinity != NULL) {
1653b7565d44SJeff Roberson 		for (i = 0;; i++) {
1654b7565d44SJeff Roberson 			size = mem_affinity[i].end - mem_affinity[i].start;
1655b7565d44SJeff Roberson 			if (size == 0)
1656b7565d44SJeff Roberson 				break;
165781302f1dSMark Johnston 			if (domain != -1 && mem_affinity[i].domain != domain)
1658b7565d44SJeff Roberson 				continue;
1659b7565d44SJeff Roberson 			if (size > biggestsize) {
1660b7565d44SJeff Roberson 				mem_index = i;
1661b7565d44SJeff Roberson 				biggestsize = size;
1662b7565d44SJeff Roberson 			}
1663b7565d44SJeff Roberson 		}
1664b7565d44SJeff Roberson 		mem_start = mem_affinity[mem_index].start;
1665b7565d44SJeff Roberson 		mem_end = mem_affinity[mem_index].end;
1666b7565d44SJeff Roberson 	}
1667b7565d44SJeff Roberson #endif
1668b7565d44SJeff Roberson 
1669b7565d44SJeff Roberson 	/*
1670b7565d44SJeff Roberson 	 * Now find biggest physical segment in within the desired
1671b7565d44SJeff Roberson 	 * numa domain.
1672b7565d44SJeff Roberson 	 */
1673b7565d44SJeff Roberson 	biggestsize = 0;
1674b7565d44SJeff Roberson 	biggestone = 0;
1675b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
1676b7565d44SJeff Roberson 		/* skip regions that are out of range */
1677b7565d44SJeff Roberson 		if (phys_avail[i+1] - alloc_size < mem_start ||
1678b7565d44SJeff Roberson 		    phys_avail[i+1] > mem_end)
1679b7565d44SJeff Roberson 			continue;
1680b7565d44SJeff Roberson 		size = vm_phys_avail_size(i);
1681b7565d44SJeff Roberson 		if (size > biggestsize) {
1682b7565d44SJeff Roberson 			biggestone = i;
1683b7565d44SJeff Roberson 			biggestsize = size;
1684b7565d44SJeff Roberson 		}
1685b7565d44SJeff Roberson 	}
1686b7565d44SJeff Roberson 	alloc_size = round_page(alloc_size);
1687b7565d44SJeff Roberson 
1688b7565d44SJeff Roberson 	/*
1689b7565d44SJeff Roberson 	 * Grab single pages from the front to reduce fragmentation.
1690b7565d44SJeff Roberson 	 */
1691b7565d44SJeff Roberson 	if (alloc_size == PAGE_SIZE) {
1692b7565d44SJeff Roberson 		pa = phys_avail[biggestone];
1693b7565d44SJeff Roberson 		phys_avail[biggestone] += PAGE_SIZE;
1694b7565d44SJeff Roberson 		vm_phys_avail_check(biggestone);
1695b7565d44SJeff Roberson 		return (pa);
1696b7565d44SJeff Roberson 	}
1697b7565d44SJeff Roberson 
1698b7565d44SJeff Roberson 	/*
1699b7565d44SJeff Roberson 	 * Naturally align large allocations.
1700b7565d44SJeff Roberson 	 */
1701b7565d44SJeff Roberson 	align = phys_avail[biggestone + 1] & (alloc_size - 1);
1702b7565d44SJeff Roberson 	if (alloc_size + align > biggestsize)
1703b7565d44SJeff Roberson 		panic("cannot find a large enough size\n");
1704b7565d44SJeff Roberson 	if (align != 0 &&
1705b7565d44SJeff Roberson 	    vm_phys_avail_split(phys_avail[biggestone + 1] - align,
1706b7565d44SJeff Roberson 	    biggestone) != 0)
1707b7565d44SJeff Roberson 		/* Wasting memory. */
1708b7565d44SJeff Roberson 		phys_avail[biggestone + 1] -= align;
1709b7565d44SJeff Roberson 
1710b7565d44SJeff Roberson 	phys_avail[biggestone + 1] -= alloc_size;
1711b7565d44SJeff Roberson 	vm_phys_avail_check(biggestone);
1712b7565d44SJeff Roberson 	pa = phys_avail[biggestone + 1];
1713b7565d44SJeff Roberson 	return (pa);
1714b7565d44SJeff Roberson }
1715b7565d44SJeff Roberson 
1716b7565d44SJeff Roberson void
1717b7565d44SJeff Roberson vm_phys_early_startup(void)
1718b7565d44SJeff Roberson {
171981302f1dSMark Johnston 	struct vm_phys_seg *seg;
1720b7565d44SJeff Roberson 	int i;
1721b7565d44SJeff Roberson 
1722b7565d44SJeff Roberson 	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
1723b7565d44SJeff Roberson 		phys_avail[i] = round_page(phys_avail[i]);
1724b7565d44SJeff Roberson 		phys_avail[i + 1] = trunc_page(phys_avail[i + 1]);
1725b7565d44SJeff Roberson 	}
1726b7565d44SJeff Roberson 
172781302f1dSMark Johnston 	for (i = 0; i < vm_phys_early_nsegs; i++) {
172881302f1dSMark Johnston 		seg = &vm_phys_early_segs[i];
172981302f1dSMark Johnston 		vm_phys_add_seg(seg->start, seg->end);
173081302f1dSMark Johnston 	}
173181302f1dSMark Johnston 	vm_phys_early_nsegs = -1;
173281302f1dSMark Johnston 
1733b7565d44SJeff Roberson #ifdef NUMA
1734b7565d44SJeff Roberson 	/* Force phys_avail to be split by domain. */
1735b7565d44SJeff Roberson 	if (mem_affinity != NULL) {
1736b7565d44SJeff Roberson 		int idx;
1737b7565d44SJeff Roberson 
1738b7565d44SJeff Roberson 		for (i = 0; mem_affinity[i].end != 0; i++) {
1739b7565d44SJeff Roberson 			idx = vm_phys_avail_find(mem_affinity[i].start);
1740b7565d44SJeff Roberson 			if (idx != -1 &&
1741b7565d44SJeff Roberson 			    phys_avail[idx] != mem_affinity[i].start)
1742b7565d44SJeff Roberson 				vm_phys_avail_split(mem_affinity[i].start, idx);
1743b7565d44SJeff Roberson 			idx = vm_phys_avail_find(mem_affinity[i].end);
1744b7565d44SJeff Roberson 			if (idx != -1 &&
1745b7565d44SJeff Roberson 			    phys_avail[idx] != mem_affinity[i].end)
1746b7565d44SJeff Roberson 				vm_phys_avail_split(mem_affinity[i].end, idx);
1747b7565d44SJeff Roberson 		}
1748b7565d44SJeff Roberson 	}
1749b7565d44SJeff Roberson #endif
1750b7565d44SJeff Roberson }
1751b7565d44SJeff Roberson 
175211752d88SAlan Cox #ifdef DDB
175311752d88SAlan Cox /*
175411752d88SAlan Cox  * Show the number of physical pages in each of the free lists.
175511752d88SAlan Cox  */
175611752d88SAlan Cox DB_SHOW_COMMAND(freepages, db_show_freepages)
175711752d88SAlan Cox {
175811752d88SAlan Cox 	struct vm_freelist *fl;
17597e226537SAttilio Rao 	int flind, oind, pind, dom;
176011752d88SAlan Cox 
17617e226537SAttilio Rao 	for (dom = 0; dom < vm_ndomains; dom++) {
17627e226537SAttilio Rao 		db_printf("DOMAIN: %d\n", dom);
176311752d88SAlan Cox 		for (flind = 0; flind < vm_nfreelists; flind++) {
176411752d88SAlan Cox 			db_printf("FREE LIST %d:\n"
176511752d88SAlan Cox 			    "\n  ORDER (SIZE)  |  NUMBER"
176611752d88SAlan Cox 			    "\n              ", flind);
176711752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
176811752d88SAlan Cox 				db_printf("  |  POOL %d", pind);
176911752d88SAlan Cox 			db_printf("\n--            ");
177011752d88SAlan Cox 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
177111752d88SAlan Cox 				db_printf("-- --      ");
177211752d88SAlan Cox 			db_printf("--\n");
177311752d88SAlan Cox 			for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
177411752d88SAlan Cox 				db_printf("  %2.2d (%6.6dK)", oind,
177511752d88SAlan Cox 				    1 << (PAGE_SHIFT - 10 + oind));
177611752d88SAlan Cox 				for (pind = 0; pind < VM_NFREEPOOL; pind++) {
17777e226537SAttilio Rao 				fl = vm_phys_free_queues[dom][flind][pind];
177811752d88SAlan Cox 					db_printf("  |  %6.6d", fl[oind].lcnt);
177911752d88SAlan Cox 				}
178011752d88SAlan Cox 				db_printf("\n");
178111752d88SAlan Cox 			}
178211752d88SAlan Cox 			db_printf("\n");
178311752d88SAlan Cox 		}
17847e226537SAttilio Rao 		db_printf("\n");
17857e226537SAttilio Rao 	}
178611752d88SAlan Cox }
178711752d88SAlan Cox #endif
1788