xref: /freebsd/sys/vm/vm_phys.c (revision 3dcf5eb70598c88befd62f61f81e283e568ec519)
1 /*-
2  * Copyright (c) 2002-2006 Rice University
3  * Copyright (c) 2007 Alan L. Cox <alc@cs.rice.edu>
4  * All rights reserved.
5  *
6  * This software was developed for the FreeBSD Project by Alan L. Cox,
7  * Olivier Crameri, Peter Druschel, Sitaram Iyer, and Juan Navarro.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in the
16  *    documentation and/or other materials provided with the distribution.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
22  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
24  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
25  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
26  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
28  * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29  * POSSIBILITY OF SUCH DAMAGE.
30  */
31 
32 /*
33  *	Physical memory system implementation
34  *
35  * Any external functions defined by this module are only to be used by the
36  * virtual memory system.
37  */
38 
39 #include <sys/cdefs.h>
40 __FBSDID("$FreeBSD$");
41 
42 #include "opt_ddb.h"
43 #include "opt_vm.h"
44 
45 #include <sys/param.h>
46 #include <sys/systm.h>
47 #include <sys/lock.h>
48 #include <sys/kernel.h>
49 #include <sys/malloc.h>
50 #include <sys/mutex.h>
51 #if MAXMEMDOM > 1
52 #include <sys/proc.h>
53 #endif
54 #include <sys/queue.h>
55 #include <sys/rwlock.h>
56 #include <sys/sbuf.h>
57 #include <sys/sysctl.h>
58 #include <sys/tree.h>
59 #include <sys/vmmeter.h>
60 
61 #include <ddb/ddb.h>
62 
63 #include <vm/vm.h>
64 #include <vm/vm_param.h>
65 #include <vm/vm_kern.h>
66 #include <vm/vm_object.h>
67 #include <vm/vm_page.h>
68 #include <vm/vm_phys.h>
69 
70 _Static_assert(sizeof(long) * NBBY >= VM_PHYSSEG_MAX,
71     "Too many physsegs.");
72 
73 struct mem_affinity *mem_affinity;
74 
75 int vm_ndomains = 1;
76 
77 struct vm_phys_seg vm_phys_segs[VM_PHYSSEG_MAX];
78 int vm_phys_nsegs;
79 
80 struct vm_phys_fictitious_seg;
81 static int vm_phys_fictitious_cmp(struct vm_phys_fictitious_seg *,
82     struct vm_phys_fictitious_seg *);
83 
84 RB_HEAD(fict_tree, vm_phys_fictitious_seg) vm_phys_fictitious_tree =
85     RB_INITIALIZER(_vm_phys_fictitious_tree);
86 
87 struct vm_phys_fictitious_seg {
88 	RB_ENTRY(vm_phys_fictitious_seg) node;
89 	/* Memory region data */
90 	vm_paddr_t	start;
91 	vm_paddr_t	end;
92 	vm_page_t	first_page;
93 };
94 
95 RB_GENERATE_STATIC(fict_tree, vm_phys_fictitious_seg, node,
96     vm_phys_fictitious_cmp);
97 
98 static struct rwlock vm_phys_fictitious_reg_lock;
99 MALLOC_DEFINE(M_FICT_PAGES, "vm_fictitious", "Fictitious VM pages");
100 
101 static struct vm_freelist
102     vm_phys_free_queues[MAXMEMDOM][VM_NFREELIST][VM_NFREEPOOL][VM_NFREEORDER];
103 
104 static int vm_nfreelists = VM_FREELIST_DEFAULT + 1;
105 
106 static int cnt_prezero;
107 SYSCTL_INT(_vm_stats_misc, OID_AUTO, cnt_prezero, CTLFLAG_RD,
108     &cnt_prezero, 0, "The number of physical pages prezeroed at idle time");
109 
110 static int sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS);
111 SYSCTL_OID(_vm, OID_AUTO, phys_free, CTLTYPE_STRING | CTLFLAG_RD,
112     NULL, 0, sysctl_vm_phys_free, "A", "Phys Free Info");
113 
114 static int sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS);
115 SYSCTL_OID(_vm, OID_AUTO, phys_segs, CTLTYPE_STRING | CTLFLAG_RD,
116     NULL, 0, sysctl_vm_phys_segs, "A", "Phys Seg Info");
117 
118 SYSCTL_INT(_vm, OID_AUTO, ndomains, CTLFLAG_RD,
119     &vm_ndomains, 0, "Number of physical memory domains available.");
120 
121 static vm_page_t vm_phys_alloc_domain_pages(int domain, int flind, int pool,
122     int order);
123 static void _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind,
124     int domain);
125 static void vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind);
126 static int vm_phys_paddr_to_segind(vm_paddr_t pa);
127 static void vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl,
128     int order);
129 
130 /*
131  * Red-black tree helpers for vm fictitious range management.
132  */
133 static inline int
134 vm_phys_fictitious_in_range(struct vm_phys_fictitious_seg *p,
135     struct vm_phys_fictitious_seg *range)
136 {
137 
138 	KASSERT(range->start != 0 && range->end != 0,
139 	    ("Invalid range passed on search for vm_fictitious page"));
140 	if (p->start >= range->end)
141 		return (1);
142 	if (p->start < range->start)
143 		return (-1);
144 
145 	return (0);
146 }
147 
148 static int
149 vm_phys_fictitious_cmp(struct vm_phys_fictitious_seg *p1,
150     struct vm_phys_fictitious_seg *p2)
151 {
152 
153 	/* Check if this is a search for a page */
154 	if (p1->end == 0)
155 		return (vm_phys_fictitious_in_range(p1, p2));
156 
157 	KASSERT(p2->end != 0,
158     ("Invalid range passed as second parameter to vm fictitious comparison"));
159 
160 	/* Searching to add a new range */
161 	if (p1->end <= p2->start)
162 		return (-1);
163 	if (p1->start >= p2->end)
164 		return (1);
165 
166 	panic("Trying to add overlapping vm fictitious ranges:\n"
167 	    "[%#jx:%#jx] and [%#jx:%#jx]", (uintmax_t)p1->start,
168 	    (uintmax_t)p1->end, (uintmax_t)p2->start, (uintmax_t)p2->end);
169 }
170 
171 static __inline int
172 vm_rr_selectdomain(void)
173 {
174 #if MAXMEMDOM > 1
175 	struct thread *td;
176 
177 	td = curthread;
178 
179 	td->td_dom_rr_idx++;
180 	td->td_dom_rr_idx %= vm_ndomains;
181 	return (td->td_dom_rr_idx);
182 #else
183 	return (0);
184 #endif
185 }
186 
187 boolean_t
188 vm_phys_domain_intersects(long mask, vm_paddr_t low, vm_paddr_t high)
189 {
190 	struct vm_phys_seg *s;
191 	int idx;
192 
193 	while ((idx = ffsl(mask)) != 0) {
194 		idx--;	/* ffsl counts from 1 */
195 		mask &= ~(1UL << idx);
196 		s = &vm_phys_segs[idx];
197 		if (low < s->end && high > s->start)
198 			return (TRUE);
199 	}
200 	return (FALSE);
201 }
202 
203 /*
204  * Outputs the state of the physical memory allocator, specifically,
205  * the amount of physical memory in each free list.
206  */
207 static int
208 sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS)
209 {
210 	struct sbuf sbuf;
211 	struct vm_freelist *fl;
212 	int dom, error, flind, oind, pind;
213 
214 	error = sysctl_wire_old_buffer(req, 0);
215 	if (error != 0)
216 		return (error);
217 	sbuf_new_for_sysctl(&sbuf, NULL, 128 * vm_ndomains, req);
218 	for (dom = 0; dom < vm_ndomains; dom++) {
219 		sbuf_printf(&sbuf,"\nDOMAIN %d:\n", dom);
220 		for (flind = 0; flind < vm_nfreelists; flind++) {
221 			sbuf_printf(&sbuf, "\nFREE LIST %d:\n"
222 			    "\n  ORDER (SIZE)  |  NUMBER"
223 			    "\n              ", flind);
224 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
225 				sbuf_printf(&sbuf, "  |  POOL %d", pind);
226 			sbuf_printf(&sbuf, "\n--            ");
227 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
228 				sbuf_printf(&sbuf, "-- --      ");
229 			sbuf_printf(&sbuf, "--\n");
230 			for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
231 				sbuf_printf(&sbuf, "  %2d (%6dK)", oind,
232 				    1 << (PAGE_SHIFT - 10 + oind));
233 				for (pind = 0; pind < VM_NFREEPOOL; pind++) {
234 				fl = vm_phys_free_queues[dom][flind][pind];
235 					sbuf_printf(&sbuf, "  |  %6d",
236 					    fl[oind].lcnt);
237 				}
238 				sbuf_printf(&sbuf, "\n");
239 			}
240 		}
241 	}
242 	error = sbuf_finish(&sbuf);
243 	sbuf_delete(&sbuf);
244 	return (error);
245 }
246 
247 /*
248  * Outputs the set of physical memory segments.
249  */
250 static int
251 sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS)
252 {
253 	struct sbuf sbuf;
254 	struct vm_phys_seg *seg;
255 	int error, segind;
256 
257 	error = sysctl_wire_old_buffer(req, 0);
258 	if (error != 0)
259 		return (error);
260 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
261 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
262 		sbuf_printf(&sbuf, "\nSEGMENT %d:\n\n", segind);
263 		seg = &vm_phys_segs[segind];
264 		sbuf_printf(&sbuf, "start:     %#jx\n",
265 		    (uintmax_t)seg->start);
266 		sbuf_printf(&sbuf, "end:       %#jx\n",
267 		    (uintmax_t)seg->end);
268 		sbuf_printf(&sbuf, "domain:    %d\n", seg->domain);
269 		sbuf_printf(&sbuf, "free list: %p\n", seg->free_queues);
270 	}
271 	error = sbuf_finish(&sbuf);
272 	sbuf_delete(&sbuf);
273 	return (error);
274 }
275 
276 static void
277 vm_freelist_add(struct vm_freelist *fl, vm_page_t m, int order, int tail)
278 {
279 
280 	m->order = order;
281 	if (tail)
282 		TAILQ_INSERT_TAIL(&fl[order].pl, m, plinks.q);
283 	else
284 		TAILQ_INSERT_HEAD(&fl[order].pl, m, plinks.q);
285 	fl[order].lcnt++;
286 }
287 
288 static void
289 vm_freelist_rem(struct vm_freelist *fl, vm_page_t m, int order)
290 {
291 
292 	TAILQ_REMOVE(&fl[order].pl, m, plinks.q);
293 	fl[order].lcnt--;
294 	m->order = VM_NFREEORDER;
295 }
296 
297 /*
298  * Create a physical memory segment.
299  */
300 static void
301 _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind, int domain)
302 {
303 	struct vm_phys_seg *seg;
304 #ifdef VM_PHYSSEG_SPARSE
305 	long pages;
306 	int segind;
307 
308 	pages = 0;
309 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
310 		seg = &vm_phys_segs[segind];
311 		pages += atop(seg->end - seg->start);
312 	}
313 #endif
314 	KASSERT(vm_phys_nsegs < VM_PHYSSEG_MAX,
315 	    ("vm_phys_create_seg: increase VM_PHYSSEG_MAX"));
316 	KASSERT(domain < vm_ndomains,
317 	    ("vm_phys_create_seg: invalid domain provided"));
318 	seg = &vm_phys_segs[vm_phys_nsegs++];
319 	seg->start = start;
320 	seg->end = end;
321 	seg->domain = domain;
322 #ifdef VM_PHYSSEG_SPARSE
323 	seg->first_page = &vm_page_array[pages];
324 #else
325 	seg->first_page = PHYS_TO_VM_PAGE(start);
326 #endif
327 	seg->free_queues = &vm_phys_free_queues[domain][flind];
328 }
329 
330 static void
331 vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind)
332 {
333 	int i;
334 
335 	if (mem_affinity == NULL) {
336 		_vm_phys_create_seg(start, end, flind, 0);
337 		return;
338 	}
339 
340 	for (i = 0;; i++) {
341 		if (mem_affinity[i].end == 0)
342 			panic("Reached end of affinity info");
343 		if (mem_affinity[i].end <= start)
344 			continue;
345 		if (mem_affinity[i].start > start)
346 			panic("No affinity info for start %jx",
347 			    (uintmax_t)start);
348 		if (mem_affinity[i].end >= end) {
349 			_vm_phys_create_seg(start, end, flind,
350 			    mem_affinity[i].domain);
351 			break;
352 		}
353 		_vm_phys_create_seg(start, mem_affinity[i].end, flind,
354 		    mem_affinity[i].domain);
355 		start = mem_affinity[i].end;
356 	}
357 }
358 
359 /*
360  * Initialize the physical memory allocator.
361  */
362 void
363 vm_phys_init(void)
364 {
365 	struct vm_freelist *fl;
366 	int dom, flind, i, oind, pind;
367 
368 	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
369 #ifdef	VM_FREELIST_ISADMA
370 		if (phys_avail[i] < 16777216) {
371 			if (phys_avail[i + 1] > 16777216) {
372 				vm_phys_create_seg(phys_avail[i], 16777216,
373 				    VM_FREELIST_ISADMA);
374 				vm_phys_create_seg(16777216, phys_avail[i + 1],
375 				    VM_FREELIST_DEFAULT);
376 			} else {
377 				vm_phys_create_seg(phys_avail[i],
378 				    phys_avail[i + 1], VM_FREELIST_ISADMA);
379 			}
380 			if (VM_FREELIST_ISADMA >= vm_nfreelists)
381 				vm_nfreelists = VM_FREELIST_ISADMA + 1;
382 		} else
383 #endif
384 #ifdef	VM_FREELIST_HIGHMEM
385 		if (phys_avail[i + 1] > VM_HIGHMEM_ADDRESS) {
386 			if (phys_avail[i] < VM_HIGHMEM_ADDRESS) {
387 				vm_phys_create_seg(phys_avail[i],
388 				    VM_HIGHMEM_ADDRESS, VM_FREELIST_DEFAULT);
389 				vm_phys_create_seg(VM_HIGHMEM_ADDRESS,
390 				    phys_avail[i + 1], VM_FREELIST_HIGHMEM);
391 			} else {
392 				vm_phys_create_seg(phys_avail[i],
393 				    phys_avail[i + 1], VM_FREELIST_HIGHMEM);
394 			}
395 			if (VM_FREELIST_HIGHMEM >= vm_nfreelists)
396 				vm_nfreelists = VM_FREELIST_HIGHMEM + 1;
397 		} else
398 #endif
399 		vm_phys_create_seg(phys_avail[i], phys_avail[i + 1],
400 		    VM_FREELIST_DEFAULT);
401 	}
402 	for (dom = 0; dom < vm_ndomains; dom++) {
403 		for (flind = 0; flind < vm_nfreelists; flind++) {
404 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
405 				fl = vm_phys_free_queues[dom][flind][pind];
406 				for (oind = 0; oind < VM_NFREEORDER; oind++)
407 					TAILQ_INIT(&fl[oind].pl);
408 			}
409 		}
410 	}
411 	rw_init(&vm_phys_fictitious_reg_lock, "vmfctr");
412 }
413 
414 /*
415  * Split a contiguous, power of two-sized set of physical pages.
416  */
417 static __inline void
418 vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl, int order)
419 {
420 	vm_page_t m_buddy;
421 
422 	while (oind > order) {
423 		oind--;
424 		m_buddy = &m[1 << oind];
425 		KASSERT(m_buddy->order == VM_NFREEORDER,
426 		    ("vm_phys_split_pages: page %p has unexpected order %d",
427 		    m_buddy, m_buddy->order));
428 		vm_freelist_add(fl, m_buddy, oind, 0);
429         }
430 }
431 
432 /*
433  * Initialize a physical page and add it to the free lists.
434  */
435 void
436 vm_phys_add_page(vm_paddr_t pa)
437 {
438 	vm_page_t m;
439 	struct vm_domain *vmd;
440 
441 	vm_cnt.v_page_count++;
442 	m = vm_phys_paddr_to_vm_page(pa);
443 	m->phys_addr = pa;
444 	m->queue = PQ_NONE;
445 	m->segind = vm_phys_paddr_to_segind(pa);
446 	vmd = vm_phys_domain(m);
447 	vmd->vmd_page_count++;
448 	vmd->vmd_segs |= 1UL << m->segind;
449 	KASSERT(m->order == VM_NFREEORDER,
450 	    ("vm_phys_add_page: page %p has unexpected order %d",
451 	    m, m->order));
452 	m->pool = VM_FREEPOOL_DEFAULT;
453 	pmap_page_init(m);
454 	mtx_lock(&vm_page_queue_free_mtx);
455 	vm_phys_freecnt_adj(m, 1);
456 	vm_phys_free_pages(m, 0);
457 	mtx_unlock(&vm_page_queue_free_mtx);
458 }
459 
460 /*
461  * Allocate a contiguous, power of two-sized set of physical pages
462  * from the free lists.
463  *
464  * The free page queues must be locked.
465  */
466 vm_page_t
467 vm_phys_alloc_pages(int pool, int order)
468 {
469 	vm_page_t m;
470 	int dom, domain, flind;
471 
472 	KASSERT(pool < VM_NFREEPOOL,
473 	    ("vm_phys_alloc_pages: pool %d is out of range", pool));
474 	KASSERT(order < VM_NFREEORDER,
475 	    ("vm_phys_alloc_pages: order %d is out of range", order));
476 
477 	for (dom = 0; dom < vm_ndomains; dom++) {
478 		domain = vm_rr_selectdomain();
479 		for (flind = 0; flind < vm_nfreelists; flind++) {
480 			m = vm_phys_alloc_domain_pages(domain, flind, pool,
481 			    order);
482 			if (m != NULL)
483 				return (m);
484 		}
485 	}
486 	return (NULL);
487 }
488 
489 /*
490  * Find and dequeue a free page on the given free list, with the
491  * specified pool and order
492  */
493 vm_page_t
494 vm_phys_alloc_freelist_pages(int flind, int pool, int order)
495 {
496 	vm_page_t m;
497 	int dom, domain;
498 
499 	KASSERT(flind < VM_NFREELIST,
500 	    ("vm_phys_alloc_freelist_pages: freelist %d is out of range", flind));
501 	KASSERT(pool < VM_NFREEPOOL,
502 	    ("vm_phys_alloc_freelist_pages: pool %d is out of range", pool));
503 	KASSERT(order < VM_NFREEORDER,
504 	    ("vm_phys_alloc_freelist_pages: order %d is out of range", order));
505 
506 	for (dom = 0; dom < vm_ndomains; dom++) {
507 		domain = vm_rr_selectdomain();
508 		m = vm_phys_alloc_domain_pages(domain, flind, pool, order);
509 		if (m != NULL)
510 			return (m);
511 	}
512 	return (NULL);
513 }
514 
515 static vm_page_t
516 vm_phys_alloc_domain_pages(int domain, int flind, int pool, int order)
517 {
518 	struct vm_freelist *fl;
519 	struct vm_freelist *alt;
520 	int oind, pind;
521 	vm_page_t m;
522 
523 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
524 	fl = &vm_phys_free_queues[domain][flind][pool][0];
525 	for (oind = order; oind < VM_NFREEORDER; oind++) {
526 		m = TAILQ_FIRST(&fl[oind].pl);
527 		if (m != NULL) {
528 			vm_freelist_rem(fl, m, oind);
529 			vm_phys_split_pages(m, oind, fl, order);
530 			return (m);
531 		}
532 	}
533 
534 	/*
535 	 * The given pool was empty.  Find the largest
536 	 * contiguous, power-of-two-sized set of pages in any
537 	 * pool.  Transfer these pages to the given pool, and
538 	 * use them to satisfy the allocation.
539 	 */
540 	for (oind = VM_NFREEORDER - 1; oind >= order; oind--) {
541 		for (pind = 0; pind < VM_NFREEPOOL; pind++) {
542 			alt = &vm_phys_free_queues[domain][flind][pind][0];
543 			m = TAILQ_FIRST(&alt[oind].pl);
544 			if (m != NULL) {
545 				vm_freelist_rem(alt, m, oind);
546 				vm_phys_set_pool(pool, m, oind);
547 				vm_phys_split_pages(m, oind, fl, order);
548 				return (m);
549 			}
550 		}
551 	}
552 	return (NULL);
553 }
554 
555 /*
556  * Find the vm_page corresponding to the given physical address.
557  */
558 vm_page_t
559 vm_phys_paddr_to_vm_page(vm_paddr_t pa)
560 {
561 	struct vm_phys_seg *seg;
562 	int segind;
563 
564 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
565 		seg = &vm_phys_segs[segind];
566 		if (pa >= seg->start && pa < seg->end)
567 			return (&seg->first_page[atop(pa - seg->start)]);
568 	}
569 	return (NULL);
570 }
571 
572 vm_page_t
573 vm_phys_fictitious_to_vm_page(vm_paddr_t pa)
574 {
575 	struct vm_phys_fictitious_seg tmp, *seg;
576 	vm_page_t m;
577 
578 	m = NULL;
579 	tmp.start = pa;
580 	tmp.end = 0;
581 
582 	rw_rlock(&vm_phys_fictitious_reg_lock);
583 	seg = RB_FIND(fict_tree, &vm_phys_fictitious_tree, &tmp);
584 	rw_runlock(&vm_phys_fictitious_reg_lock);
585 	if (seg == NULL)
586 		return (NULL);
587 
588 	m = &seg->first_page[atop(pa - seg->start)];
589 	KASSERT((m->flags & PG_FICTITIOUS) != 0, ("%p not fictitious", m));
590 
591 	return (m);
592 }
593 
594 int
595 vm_phys_fictitious_reg_range(vm_paddr_t start, vm_paddr_t end,
596     vm_memattr_t memattr)
597 {
598 	struct vm_phys_fictitious_seg *seg;
599 	vm_page_t fp;
600 	long i, page_count;
601 #ifdef VM_PHYSSEG_DENSE
602 	long pi;
603 #endif
604 
605 	page_count = (end - start) / PAGE_SIZE;
606 
607 #ifdef VM_PHYSSEG_DENSE
608 	pi = atop(start);
609 	if (pi >= first_page && pi < vm_page_array_size + first_page) {
610 		if (atop(end) >= vm_page_array_size + first_page)
611 			return (EINVAL);
612 		fp = &vm_page_array[pi - first_page];
613 	} else
614 #endif
615 	{
616 		fp = malloc(page_count * sizeof(struct vm_page), M_FICT_PAGES,
617 		    M_WAITOK | M_ZERO);
618 	}
619 	for (i = 0; i < page_count; i++) {
620 		vm_page_initfake(&fp[i], start + PAGE_SIZE * i, memattr);
621 		fp[i].oflags &= ~VPO_UNMANAGED;
622 		fp[i].busy_lock = VPB_UNBUSIED;
623 	}
624 
625 	seg = malloc(sizeof(*seg), M_FICT_PAGES, M_WAITOK | M_ZERO);
626 	seg->start = start;
627 	seg->end = end;
628 	seg->first_page = fp;
629 
630 	rw_wlock(&vm_phys_fictitious_reg_lock);
631 	RB_INSERT(fict_tree, &vm_phys_fictitious_tree, seg);
632 	rw_wunlock(&vm_phys_fictitious_reg_lock);
633 
634 	return (0);
635 }
636 
637 void
638 vm_phys_fictitious_unreg_range(vm_paddr_t start, vm_paddr_t end)
639 {
640 	struct vm_phys_fictitious_seg *seg, tmp;
641 #ifdef VM_PHYSSEG_DENSE
642 	long pi;
643 #endif
644 
645 #ifdef VM_PHYSSEG_DENSE
646 	pi = atop(start);
647 #endif
648 	tmp.start = start;
649 	tmp.end = 0;
650 
651 	rw_wlock(&vm_phys_fictitious_reg_lock);
652 	seg = RB_FIND(fict_tree, &vm_phys_fictitious_tree, &tmp);
653 	if (seg->start != start || seg->end != end) {
654 		rw_wunlock(&vm_phys_fictitious_reg_lock);
655 		panic(
656 		    "Unregistering not registered fictitious range [%#jx:%#jx]",
657 		    (uintmax_t)start, (uintmax_t)end);
658 	}
659 	RB_REMOVE(fict_tree, &vm_phys_fictitious_tree, seg);
660 	rw_wunlock(&vm_phys_fictitious_reg_lock);
661 #ifdef VM_PHYSSEG_DENSE
662 	if (pi < first_page || atop(end) >= vm_page_array_size)
663 #endif
664 		free(seg->first_page, M_FICT_PAGES);
665 	free(seg, M_FICT_PAGES);
666 }
667 
668 /*
669  * Find the segment containing the given physical address.
670  */
671 static int
672 vm_phys_paddr_to_segind(vm_paddr_t pa)
673 {
674 	struct vm_phys_seg *seg;
675 	int segind;
676 
677 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
678 		seg = &vm_phys_segs[segind];
679 		if (pa >= seg->start && pa < seg->end)
680 			return (segind);
681 	}
682 	panic("vm_phys_paddr_to_segind: paddr %#jx is not in any segment" ,
683 	    (uintmax_t)pa);
684 }
685 
686 /*
687  * Free a contiguous, power of two-sized set of physical pages.
688  *
689  * The free page queues must be locked.
690  */
691 void
692 vm_phys_free_pages(vm_page_t m, int order)
693 {
694 	struct vm_freelist *fl;
695 	struct vm_phys_seg *seg;
696 	vm_paddr_t pa;
697 	vm_page_t m_buddy;
698 
699 	KASSERT(m->order == VM_NFREEORDER,
700 	    ("vm_phys_free_pages: page %p has unexpected order %d",
701 	    m, m->order));
702 	KASSERT(m->pool < VM_NFREEPOOL,
703 	    ("vm_phys_free_pages: page %p has unexpected pool %d",
704 	    m, m->pool));
705 	KASSERT(order < VM_NFREEORDER,
706 	    ("vm_phys_free_pages: order %d is out of range", order));
707 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
708 	seg = &vm_phys_segs[m->segind];
709 	if (order < VM_NFREEORDER - 1) {
710 		pa = VM_PAGE_TO_PHYS(m);
711 		do {
712 			pa ^= ((vm_paddr_t)1 << (PAGE_SHIFT + order));
713 			if (pa < seg->start || pa >= seg->end)
714 				break;
715 			m_buddy = &seg->first_page[atop(pa - seg->start)];
716 			if (m_buddy->order != order)
717 				break;
718 			fl = (*seg->free_queues)[m_buddy->pool];
719 			vm_freelist_rem(fl, m_buddy, order);
720 			if (m_buddy->pool != m->pool)
721 				vm_phys_set_pool(m->pool, m_buddy, order);
722 			order++;
723 			pa &= ~(((vm_paddr_t)1 << (PAGE_SHIFT + order)) - 1);
724 			m = &seg->first_page[atop(pa - seg->start)];
725 		} while (order < VM_NFREEORDER - 1);
726 	}
727 	fl = (*seg->free_queues)[m->pool];
728 	vm_freelist_add(fl, m, order, 1);
729 }
730 
731 /*
732  * Free a contiguous, arbitrarily sized set of physical pages.
733  *
734  * The free page queues must be locked.
735  */
736 void
737 vm_phys_free_contig(vm_page_t m, u_long npages)
738 {
739 	u_int n;
740 	int order;
741 
742 	/*
743 	 * Avoid unnecessary coalescing by freeing the pages in the largest
744 	 * possible power-of-two-sized subsets.
745 	 */
746 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
747 	for (;; npages -= n) {
748 		/*
749 		 * Unsigned "min" is used here so that "order" is assigned
750 		 * "VM_NFREEORDER - 1" when "m"'s physical address is zero
751 		 * or the low-order bits of its physical address are zero
752 		 * because the size of a physical address exceeds the size of
753 		 * a long.
754 		 */
755 		order = min(ffsl(VM_PAGE_TO_PHYS(m) >> PAGE_SHIFT) - 1,
756 		    VM_NFREEORDER - 1);
757 		n = 1 << order;
758 		if (npages < n)
759 			break;
760 		vm_phys_free_pages(m, order);
761 		m += n;
762 	}
763 	/* The residual "npages" is less than "1 << (VM_NFREEORDER - 1)". */
764 	for (; npages > 0; npages -= n) {
765 		order = flsl(npages) - 1;
766 		n = 1 << order;
767 		vm_phys_free_pages(m, order);
768 		m += n;
769 	}
770 }
771 
772 /*
773  * Set the pool for a contiguous, power of two-sized set of physical pages.
774  */
775 void
776 vm_phys_set_pool(int pool, vm_page_t m, int order)
777 {
778 	vm_page_t m_tmp;
779 
780 	for (m_tmp = m; m_tmp < &m[1 << order]; m_tmp++)
781 		m_tmp->pool = pool;
782 }
783 
784 /*
785  * Search for the given physical page "m" in the free lists.  If the search
786  * succeeds, remove "m" from the free lists and return TRUE.  Otherwise, return
787  * FALSE, indicating that "m" is not in the free lists.
788  *
789  * The free page queues must be locked.
790  */
791 boolean_t
792 vm_phys_unfree_page(vm_page_t m)
793 {
794 	struct vm_freelist *fl;
795 	struct vm_phys_seg *seg;
796 	vm_paddr_t pa, pa_half;
797 	vm_page_t m_set, m_tmp;
798 	int order;
799 
800 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
801 
802 	/*
803 	 * First, find the contiguous, power of two-sized set of free
804 	 * physical pages containing the given physical page "m" and
805 	 * assign it to "m_set".
806 	 */
807 	seg = &vm_phys_segs[m->segind];
808 	for (m_set = m, order = 0; m_set->order == VM_NFREEORDER &&
809 	    order < VM_NFREEORDER - 1; ) {
810 		order++;
811 		pa = m->phys_addr & (~(vm_paddr_t)0 << (PAGE_SHIFT + order));
812 		if (pa >= seg->start)
813 			m_set = &seg->first_page[atop(pa - seg->start)];
814 		else
815 			return (FALSE);
816 	}
817 	if (m_set->order < order)
818 		return (FALSE);
819 	if (m_set->order == VM_NFREEORDER)
820 		return (FALSE);
821 	KASSERT(m_set->order < VM_NFREEORDER,
822 	    ("vm_phys_unfree_page: page %p has unexpected order %d",
823 	    m_set, m_set->order));
824 
825 	/*
826 	 * Next, remove "m_set" from the free lists.  Finally, extract
827 	 * "m" from "m_set" using an iterative algorithm: While "m_set"
828 	 * is larger than a page, shrink "m_set" by returning the half
829 	 * of "m_set" that does not contain "m" to the free lists.
830 	 */
831 	fl = (*seg->free_queues)[m_set->pool];
832 	order = m_set->order;
833 	vm_freelist_rem(fl, m_set, order);
834 	while (order > 0) {
835 		order--;
836 		pa_half = m_set->phys_addr ^ (1 << (PAGE_SHIFT + order));
837 		if (m->phys_addr < pa_half)
838 			m_tmp = &seg->first_page[atop(pa_half - seg->start)];
839 		else {
840 			m_tmp = m_set;
841 			m_set = &seg->first_page[atop(pa_half - seg->start)];
842 		}
843 		vm_freelist_add(fl, m_tmp, order, 0);
844 	}
845 	KASSERT(m_set == m, ("vm_phys_unfree_page: fatal inconsistency"));
846 	return (TRUE);
847 }
848 
849 /*
850  * Try to zero one physical page.  Used by an idle priority thread.
851  */
852 boolean_t
853 vm_phys_zero_pages_idle(void)
854 {
855 	static struct vm_freelist *fl;
856 	static int flind, oind, pind;
857 	vm_page_t m, m_tmp;
858 	int domain;
859 
860 	domain = vm_rr_selectdomain();
861 	fl = vm_phys_free_queues[domain][0][0];
862 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
863 	for (;;) {
864 		TAILQ_FOREACH_REVERSE(m, &fl[oind].pl, pglist, plinks.q) {
865 			for (m_tmp = m; m_tmp < &m[1 << oind]; m_tmp++) {
866 				if ((m_tmp->flags & (PG_CACHED | PG_ZERO)) == 0) {
867 					vm_phys_unfree_page(m_tmp);
868 					vm_phys_freecnt_adj(m, -1);
869 					mtx_unlock(&vm_page_queue_free_mtx);
870 					pmap_zero_page_idle(m_tmp);
871 					m_tmp->flags |= PG_ZERO;
872 					mtx_lock(&vm_page_queue_free_mtx);
873 					vm_phys_freecnt_adj(m, 1);
874 					vm_phys_free_pages(m_tmp, 0);
875 					vm_page_zero_count++;
876 					cnt_prezero++;
877 					return (TRUE);
878 				}
879 			}
880 		}
881 		oind++;
882 		if (oind == VM_NFREEORDER) {
883 			oind = 0;
884 			pind++;
885 			if (pind == VM_NFREEPOOL) {
886 				pind = 0;
887 				flind++;
888 				if (flind == vm_nfreelists)
889 					flind = 0;
890 			}
891 			fl = vm_phys_free_queues[domain][flind][pind];
892 		}
893 	}
894 }
895 
896 /*
897  * Allocate a contiguous set of physical pages of the given size
898  * "npages" from the free lists.  All of the physical pages must be at
899  * or above the given physical address "low" and below the given
900  * physical address "high".  The given value "alignment" determines the
901  * alignment of the first physical page in the set.  If the given value
902  * "boundary" is non-zero, then the set of physical pages cannot cross
903  * any physical address boundary that is a multiple of that value.  Both
904  * "alignment" and "boundary" must be a power of two.
905  */
906 vm_page_t
907 vm_phys_alloc_contig(u_long npages, vm_paddr_t low, vm_paddr_t high,
908     u_long alignment, vm_paddr_t boundary)
909 {
910 	struct vm_freelist *fl;
911 	struct vm_phys_seg *seg;
912 	vm_paddr_t pa, pa_last, size;
913 	vm_page_t m, m_ret;
914 	u_long npages_end;
915 	int dom, domain, flind, oind, order, pind;
916 
917 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
918 	size = npages << PAGE_SHIFT;
919 	KASSERT(size != 0,
920 	    ("vm_phys_alloc_contig: size must not be 0"));
921 	KASSERT((alignment & (alignment - 1)) == 0,
922 	    ("vm_phys_alloc_contig: alignment must be a power of 2"));
923 	KASSERT((boundary & (boundary - 1)) == 0,
924 	    ("vm_phys_alloc_contig: boundary must be a power of 2"));
925 	/* Compute the queue that is the best fit for npages. */
926 	for (order = 0; (1 << order) < npages; order++);
927 	dom = 0;
928 restartdom:
929 	domain = vm_rr_selectdomain();
930 	for (flind = 0; flind < vm_nfreelists; flind++) {
931 		for (oind = min(order, VM_NFREEORDER - 1); oind < VM_NFREEORDER; oind++) {
932 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
933 				fl = &vm_phys_free_queues[domain][flind][pind][0];
934 				TAILQ_FOREACH(m_ret, &fl[oind].pl, plinks.q) {
935 					/*
936 					 * A free list may contain physical pages
937 					 * from one or more segments.
938 					 */
939 					seg = &vm_phys_segs[m_ret->segind];
940 					if (seg->start > high ||
941 					    low >= seg->end)
942 						continue;
943 
944 					/*
945 					 * Is the size of this allocation request
946 					 * larger than the largest block size?
947 					 */
948 					if (order >= VM_NFREEORDER) {
949 						/*
950 						 * Determine if a sufficient number
951 						 * of subsequent blocks to satisfy
952 						 * the allocation request are free.
953 						 */
954 						pa = VM_PAGE_TO_PHYS(m_ret);
955 						pa_last = pa + size;
956 						for (;;) {
957 							pa += 1 << (PAGE_SHIFT + VM_NFREEORDER - 1);
958 							if (pa >= pa_last)
959 								break;
960 							if (pa < seg->start ||
961 							    pa >= seg->end)
962 								break;
963 							m = &seg->first_page[atop(pa - seg->start)];
964 							if (m->order != VM_NFREEORDER - 1)
965 								break;
966 						}
967 						/* If not, continue to the next block. */
968 						if (pa < pa_last)
969 							continue;
970 					}
971 
972 					/*
973 					 * Determine if the blocks are within the given range,
974 					 * satisfy the given alignment, and do not cross the
975 					 * given boundary.
976 					 */
977 					pa = VM_PAGE_TO_PHYS(m_ret);
978 					if (pa >= low &&
979 					    pa + size <= high &&
980 					    (pa & (alignment - 1)) == 0 &&
981 					    ((pa ^ (pa + size - 1)) & ~(boundary - 1)) == 0)
982 						goto done;
983 				}
984 			}
985 		}
986 	}
987 	if (++dom < vm_ndomains)
988 		goto restartdom;
989 	return (NULL);
990 done:
991 	for (m = m_ret; m < &m_ret[npages]; m = &m[1 << oind]) {
992 		fl = (*seg->free_queues)[m->pool];
993 		vm_freelist_rem(fl, m, m->order);
994 	}
995 	if (m_ret->pool != VM_FREEPOOL_DEFAULT)
996 		vm_phys_set_pool(VM_FREEPOOL_DEFAULT, m_ret, oind);
997 	fl = (*seg->free_queues)[m_ret->pool];
998 	vm_phys_split_pages(m_ret, oind, fl, order);
999 	/* Return excess pages to the free lists. */
1000 	npages_end = roundup2(npages, 1 << imin(oind, order));
1001 	if (npages < npages_end)
1002 		vm_phys_free_contig(&m_ret[npages], npages_end - npages);
1003 	return (m_ret);
1004 }
1005 
1006 #ifdef DDB
1007 /*
1008  * Show the number of physical pages in each of the free lists.
1009  */
1010 DB_SHOW_COMMAND(freepages, db_show_freepages)
1011 {
1012 	struct vm_freelist *fl;
1013 	int flind, oind, pind, dom;
1014 
1015 	for (dom = 0; dom < vm_ndomains; dom++) {
1016 		db_printf("DOMAIN: %d\n", dom);
1017 		for (flind = 0; flind < vm_nfreelists; flind++) {
1018 			db_printf("FREE LIST %d:\n"
1019 			    "\n  ORDER (SIZE)  |  NUMBER"
1020 			    "\n              ", flind);
1021 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
1022 				db_printf("  |  POOL %d", pind);
1023 			db_printf("\n--            ");
1024 			for (pind = 0; pind < VM_NFREEPOOL; pind++)
1025 				db_printf("-- --      ");
1026 			db_printf("--\n");
1027 			for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
1028 				db_printf("  %2.2d (%6.6dK)", oind,
1029 				    1 << (PAGE_SHIFT - 10 + oind));
1030 				for (pind = 0; pind < VM_NFREEPOOL; pind++) {
1031 				fl = vm_phys_free_queues[dom][flind][pind];
1032 					db_printf("  |  %6.6d", fl[oind].lcnt);
1033 				}
1034 				db_printf("\n");
1035 			}
1036 			db_printf("\n");
1037 		}
1038 		db_printf("\n");
1039 	}
1040 }
1041 #endif
1042