xref: /freebsd/sys/vm/vm_phys.c (revision fb2971ccd2bab42f5406f919812ceb8e014773ea)
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 #include <sys/cdefs.h>
33 __FBSDID("$FreeBSD$");
34 
35 #include "opt_ddb.h"
36 
37 #include <sys/param.h>
38 #include <sys/systm.h>
39 #include <sys/lock.h>
40 #include <sys/kernel.h>
41 #include <sys/malloc.h>
42 #include <sys/mutex.h>
43 #include <sys/queue.h>
44 #include <sys/sbuf.h>
45 #include <sys/sysctl.h>
46 #include <sys/vmmeter.h>
47 #include <sys/vnode.h>
48 
49 #include <ddb/ddb.h>
50 
51 #include <vm/vm.h>
52 #include <vm/vm_param.h>
53 #include <vm/vm_kern.h>
54 #include <vm/vm_object.h>
55 #include <vm/vm_page.h>
56 #include <vm/vm_phys.h>
57 #include <vm/vm_reserv.h>
58 
59 /*
60  * VM_FREELIST_DEFAULT is split into VM_NDOMAIN lists, one for each
61  * domain.  These extra lists are stored at the end of the regular
62  * free lists starting with VM_NFREELIST.
63  */
64 #define VM_RAW_NFREELIST	(VM_NFREELIST + VM_NDOMAIN - 1)
65 
66 struct vm_freelist {
67 	struct pglist pl;
68 	int lcnt;
69 };
70 
71 struct vm_phys_seg {
72 	vm_paddr_t	start;
73 	vm_paddr_t	end;
74 	vm_page_t	first_page;
75 	int		domain;
76 	struct vm_freelist (*free_queues)[VM_NFREEPOOL][VM_NFREEORDER];
77 };
78 
79 struct mem_affinity *mem_affinity;
80 
81 static struct vm_phys_seg vm_phys_segs[VM_PHYSSEG_MAX];
82 
83 static int vm_phys_nsegs;
84 
85 static struct vm_freelist
86     vm_phys_free_queues[VM_RAW_NFREELIST][VM_NFREEPOOL][VM_NFREEORDER];
87 static struct vm_freelist
88 (*vm_phys_lookup_lists[VM_NDOMAIN][VM_RAW_NFREELIST])[VM_NFREEPOOL][VM_NFREEORDER];
89 
90 static int vm_nfreelists = VM_FREELIST_DEFAULT + 1;
91 
92 static int cnt_prezero;
93 SYSCTL_INT(_vm_stats_misc, OID_AUTO, cnt_prezero, CTLFLAG_RD,
94     &cnt_prezero, 0, "The number of physical pages prezeroed at idle time");
95 
96 static int sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS);
97 SYSCTL_OID(_vm, OID_AUTO, phys_free, CTLTYPE_STRING | CTLFLAG_RD,
98     NULL, 0, sysctl_vm_phys_free, "A", "Phys Free Info");
99 
100 static int sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS);
101 SYSCTL_OID(_vm, OID_AUTO, phys_segs, CTLTYPE_STRING | CTLFLAG_RD,
102     NULL, 0, sysctl_vm_phys_segs, "A", "Phys Seg Info");
103 
104 #if VM_NDOMAIN > 1
105 static int sysctl_vm_phys_lookup_lists(SYSCTL_HANDLER_ARGS);
106 SYSCTL_OID(_vm, OID_AUTO, phys_lookup_lists, CTLTYPE_STRING | CTLFLAG_RD,
107     NULL, 0, sysctl_vm_phys_lookup_lists, "A", "Phys Lookup Lists");
108 #endif
109 
110 static void _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind,
111     int domain);
112 static void vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind);
113 static int vm_phys_paddr_to_segind(vm_paddr_t pa);
114 static void vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl,
115     int order);
116 
117 /*
118  * Outputs the state of the physical memory allocator, specifically,
119  * the amount of physical memory in each free list.
120  */
121 static int
122 sysctl_vm_phys_free(SYSCTL_HANDLER_ARGS)
123 {
124 	struct sbuf sbuf;
125 	struct vm_freelist *fl;
126 	int error, flind, oind, pind;
127 
128 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
129 	for (flind = 0; flind < vm_nfreelists; flind++) {
130 		sbuf_printf(&sbuf, "\nFREE LIST %d:\n"
131 		    "\n  ORDER (SIZE)  |  NUMBER"
132 		    "\n              ", flind);
133 		for (pind = 0; pind < VM_NFREEPOOL; pind++)
134 			sbuf_printf(&sbuf, "  |  POOL %d", pind);
135 		sbuf_printf(&sbuf, "\n--            ");
136 		for (pind = 0; pind < VM_NFREEPOOL; pind++)
137 			sbuf_printf(&sbuf, "-- --      ");
138 		sbuf_printf(&sbuf, "--\n");
139 		for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
140 			sbuf_printf(&sbuf, "  %2d (%6dK)", oind,
141 			    1 << (PAGE_SHIFT - 10 + oind));
142 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
143 				fl = vm_phys_free_queues[flind][pind];
144 				sbuf_printf(&sbuf, "  |  %6d", fl[oind].lcnt);
145 			}
146 			sbuf_printf(&sbuf, "\n");
147 		}
148 	}
149 	error = sbuf_finish(&sbuf);
150 	sbuf_delete(&sbuf);
151 	return (error);
152 }
153 
154 /*
155  * Outputs the set of physical memory segments.
156  */
157 static int
158 sysctl_vm_phys_segs(SYSCTL_HANDLER_ARGS)
159 {
160 	struct sbuf sbuf;
161 	struct vm_phys_seg *seg;
162 	int error, segind;
163 
164 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
165 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
166 		sbuf_printf(&sbuf, "\nSEGMENT %d:\n\n", segind);
167 		seg = &vm_phys_segs[segind];
168 		sbuf_printf(&sbuf, "start:     %#jx\n",
169 		    (uintmax_t)seg->start);
170 		sbuf_printf(&sbuf, "end:       %#jx\n",
171 		    (uintmax_t)seg->end);
172 		sbuf_printf(&sbuf, "domain:    %d\n", seg->domain);
173 		sbuf_printf(&sbuf, "free list: %p\n", seg->free_queues);
174 	}
175 	error = sbuf_finish(&sbuf);
176 	sbuf_delete(&sbuf);
177 	return (error);
178 }
179 
180 #if VM_NDOMAIN > 1
181 /*
182  * Outputs the set of free list lookup lists.
183  */
184 static int
185 sysctl_vm_phys_lookup_lists(SYSCTL_HANDLER_ARGS)
186 {
187 	struct sbuf sbuf;
188 	int domain, error, flind, ndomains;
189 
190 	ndomains = vm_nfreelists - VM_NFREELIST + 1;
191 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
192 	for (domain = 0; domain < ndomains; domain++) {
193 		sbuf_printf(&sbuf, "\nDOMAIN %d:\n\n", domain);
194 		for (flind = 0; flind < vm_nfreelists; flind++)
195 			sbuf_printf(&sbuf, "  [%d]:\t%p\n", flind,
196 			    vm_phys_lookup_lists[domain][flind]);
197 	}
198 	error = sbuf_finish(&sbuf);
199 	sbuf_delete(&sbuf);
200 	return (error);
201 }
202 #endif
203 
204 /*
205  * Create a physical memory segment.
206  */
207 static void
208 _vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind, int domain)
209 {
210 	struct vm_phys_seg *seg;
211 #ifdef VM_PHYSSEG_SPARSE
212 	long pages;
213 	int segind;
214 
215 	pages = 0;
216 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
217 		seg = &vm_phys_segs[segind];
218 		pages += atop(seg->end - seg->start);
219 	}
220 #endif
221 	KASSERT(vm_phys_nsegs < VM_PHYSSEG_MAX,
222 	    ("vm_phys_create_seg: increase VM_PHYSSEG_MAX"));
223 	seg = &vm_phys_segs[vm_phys_nsegs++];
224 	seg->start = start;
225 	seg->end = end;
226 	seg->domain = domain;
227 #ifdef VM_PHYSSEG_SPARSE
228 	seg->first_page = &vm_page_array[pages];
229 #else
230 	seg->first_page = PHYS_TO_VM_PAGE(start);
231 #endif
232 #if VM_NDOMAIN > 1
233 	if (flind == VM_FREELIST_DEFAULT && domain != 0) {
234 		flind = VM_NFREELIST + (domain - 1);
235 		if (flind >= vm_nfreelists)
236 			vm_nfreelists = flind + 1;
237 	}
238 #endif
239 	seg->free_queues = &vm_phys_free_queues[flind];
240 }
241 
242 static void
243 vm_phys_create_seg(vm_paddr_t start, vm_paddr_t end, int flind)
244 {
245 	int i;
246 
247 	if (mem_affinity == NULL) {
248 		_vm_phys_create_seg(start, end, flind, 0);
249 		return;
250 	}
251 
252 	for (i = 0;; i++) {
253 		if (mem_affinity[i].end == 0)
254 			panic("Reached end of affinity info");
255 		if (mem_affinity[i].end <= start)
256 			continue;
257 		if (mem_affinity[i].start > start)
258 			panic("No affinity info for start %jx",
259 			    (uintmax_t)start);
260 		if (mem_affinity[i].end >= end) {
261 			_vm_phys_create_seg(start, end, flind,
262 			    mem_affinity[i].domain);
263 			break;
264 		}
265 		_vm_phys_create_seg(start, mem_affinity[i].end, flind,
266 		    mem_affinity[i].domain);
267 		start = mem_affinity[i].end;
268 	}
269 }
270 
271 /*
272  * Initialize the physical memory allocator.
273  */
274 void
275 vm_phys_init(void)
276 {
277 	struct vm_freelist *fl;
278 	int flind, i, oind, pind;
279 #if VM_NDOMAIN > 1
280 	int ndomains, j;
281 #endif
282 
283 	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
284 #ifdef	VM_FREELIST_ISADMA
285 		if (phys_avail[i] < 16777216) {
286 			if (phys_avail[i + 1] > 16777216) {
287 				vm_phys_create_seg(phys_avail[i], 16777216,
288 				    VM_FREELIST_ISADMA);
289 				vm_phys_create_seg(16777216, phys_avail[i + 1],
290 				    VM_FREELIST_DEFAULT);
291 			} else {
292 				vm_phys_create_seg(phys_avail[i],
293 				    phys_avail[i + 1], VM_FREELIST_ISADMA);
294 			}
295 			if (VM_FREELIST_ISADMA >= vm_nfreelists)
296 				vm_nfreelists = VM_FREELIST_ISADMA + 1;
297 		} else
298 #endif
299 #ifdef	VM_FREELIST_HIGHMEM
300 		if (phys_avail[i + 1] > VM_HIGHMEM_ADDRESS) {
301 			if (phys_avail[i] < VM_HIGHMEM_ADDRESS) {
302 				vm_phys_create_seg(phys_avail[i],
303 				    VM_HIGHMEM_ADDRESS, VM_FREELIST_DEFAULT);
304 				vm_phys_create_seg(VM_HIGHMEM_ADDRESS,
305 				    phys_avail[i + 1], VM_FREELIST_HIGHMEM);
306 			} else {
307 				vm_phys_create_seg(phys_avail[i],
308 				    phys_avail[i + 1], VM_FREELIST_HIGHMEM);
309 			}
310 			if (VM_FREELIST_HIGHMEM >= vm_nfreelists)
311 				vm_nfreelists = VM_FREELIST_HIGHMEM + 1;
312 		} else
313 #endif
314 		vm_phys_create_seg(phys_avail[i], phys_avail[i + 1],
315 		    VM_FREELIST_DEFAULT);
316 	}
317 	for (flind = 0; flind < vm_nfreelists; flind++) {
318 		for (pind = 0; pind < VM_NFREEPOOL; pind++) {
319 			fl = vm_phys_free_queues[flind][pind];
320 			for (oind = 0; oind < VM_NFREEORDER; oind++)
321 				TAILQ_INIT(&fl[oind].pl);
322 		}
323 	}
324 #if VM_NDOMAIN > 1
325 	/*
326 	 * Build a free list lookup list for each domain.  All of the
327 	 * memory domain lists are inserted at the VM_FREELIST_DEFAULT
328 	 * index in a round-robin order starting with the current
329 	 * domain.
330 	 */
331 	ndomains = vm_nfreelists - VM_NFREELIST + 1;
332 	for (flind = 0; flind < VM_FREELIST_DEFAULT; flind++)
333 		for (i = 0; i < ndomains; i++)
334 			vm_phys_lookup_lists[i][flind] =
335 			    &vm_phys_free_queues[flind];
336 	for (i = 0; i < ndomains; i++)
337 		for (j = 0; j < ndomains; j++) {
338 			flind = (i + j) % ndomains;
339 			if (flind == 0)
340 				flind = VM_FREELIST_DEFAULT;
341 			else
342 				flind += VM_NFREELIST - 1;
343 			vm_phys_lookup_lists[i][VM_FREELIST_DEFAULT + j] =
344 			    &vm_phys_free_queues[flind];
345 		}
346 	for (flind = VM_FREELIST_DEFAULT + 1; flind < VM_NFREELIST;
347 	     flind++)
348 		for (i = 0; i < ndomains; i++)
349 			vm_phys_lookup_lists[i][flind + ndomains - 1] =
350 			    &vm_phys_free_queues[flind];
351 #else
352 	for (flind = 0; flind < vm_nfreelists; flind++)
353 		vm_phys_lookup_lists[0][flind] = &vm_phys_free_queues[flind];
354 #endif
355 }
356 
357 /*
358  * Split a contiguous, power of two-sized set of physical pages.
359  */
360 static __inline void
361 vm_phys_split_pages(vm_page_t m, int oind, struct vm_freelist *fl, int order)
362 {
363 	vm_page_t m_buddy;
364 
365 	while (oind > order) {
366 		oind--;
367 		m_buddy = &m[1 << oind];
368 		KASSERT(m_buddy->order == VM_NFREEORDER,
369 		    ("vm_phys_split_pages: page %p has unexpected order %d",
370 		    m_buddy, m_buddy->order));
371 		m_buddy->order = oind;
372 		TAILQ_INSERT_HEAD(&fl[oind].pl, m_buddy, pageq);
373 		fl[oind].lcnt++;
374         }
375 }
376 
377 /*
378  * Initialize a physical page and add it to the free lists.
379  */
380 void
381 vm_phys_add_page(vm_paddr_t pa)
382 {
383 	vm_page_t m;
384 
385 	cnt.v_page_count++;
386 	m = vm_phys_paddr_to_vm_page(pa);
387 	m->phys_addr = pa;
388 	m->segind = vm_phys_paddr_to_segind(pa);
389 	m->flags = PG_FREE;
390 	KASSERT(m->order == VM_NFREEORDER,
391 	    ("vm_phys_add_page: page %p has unexpected order %d",
392 	    m, m->order));
393 	m->pool = VM_FREEPOOL_DEFAULT;
394 	pmap_page_init(m);
395 	mtx_lock(&vm_page_queue_free_mtx);
396 	cnt.v_free_count++;
397 	vm_phys_free_pages(m, 0);
398 	mtx_unlock(&vm_page_queue_free_mtx);
399 }
400 
401 /*
402  * Allocate a contiguous, power of two-sized set of physical pages
403  * from the free lists.
404  *
405  * The free page queues must be locked.
406  */
407 vm_page_t
408 vm_phys_alloc_pages(int pool, int order)
409 {
410 	vm_page_t m;
411 	int flind;
412 
413 	for (flind = 0; flind < vm_nfreelists; flind++) {
414 		m = vm_phys_alloc_freelist_pages(flind, pool, order);
415 		if (m != NULL)
416 			return (m);
417 	}
418 	return (NULL);
419 }
420 
421 /*
422  * Find and dequeue a free page on the given free list, with the
423  * specified pool and order
424  */
425 vm_page_t
426 vm_phys_alloc_freelist_pages(int flind, int pool, int order)
427 {
428 	struct vm_freelist *fl;
429 	struct vm_freelist *alt;
430 	int domain, oind, pind;
431 	vm_page_t m;
432 
433 	KASSERT(flind < VM_NFREELIST,
434 	    ("vm_phys_alloc_freelist_pages: freelist %d is out of range", flind));
435 	KASSERT(pool < VM_NFREEPOOL,
436 	    ("vm_phys_alloc_freelist_pages: pool %d is out of range", pool));
437 	KASSERT(order < VM_NFREEORDER,
438 	    ("vm_phys_alloc_freelist_pages: order %d is out of range", order));
439 
440 #if VM_NDOMAIN > 1
441 	domain = PCPU_GET(domain);
442 #else
443 	domain = 0;
444 #endif
445 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
446 	fl = (*vm_phys_lookup_lists[domain][flind])[pool];
447 	for (oind = order; oind < VM_NFREEORDER; oind++) {
448 		m = TAILQ_FIRST(&fl[oind].pl);
449 		if (m != NULL) {
450 			TAILQ_REMOVE(&fl[oind].pl, m, pageq);
451 			fl[oind].lcnt--;
452 			m->order = VM_NFREEORDER;
453 			vm_phys_split_pages(m, oind, fl, order);
454 			return (m);
455 		}
456 	}
457 
458 	/*
459 	 * The given pool was empty.  Find the largest
460 	 * contiguous, power-of-two-sized set of pages in any
461 	 * pool.  Transfer these pages to the given pool, and
462 	 * use them to satisfy the allocation.
463 	 */
464 	for (oind = VM_NFREEORDER - 1; oind >= order; oind--) {
465 		for (pind = 0; pind < VM_NFREEPOOL; pind++) {
466 			alt = (*vm_phys_lookup_lists[domain][flind])[pind];
467 			m = TAILQ_FIRST(&alt[oind].pl);
468 			if (m != NULL) {
469 				TAILQ_REMOVE(&alt[oind].pl, m, pageq);
470 				alt[oind].lcnt--;
471 				m->order = VM_NFREEORDER;
472 				vm_phys_set_pool(pool, m, oind);
473 				vm_phys_split_pages(m, oind, fl, order);
474 				return (m);
475 			}
476 		}
477 	}
478 	return (NULL);
479 }
480 
481 /*
482  * Allocate physical memory from phys_avail[].
483  */
484 vm_paddr_t
485 vm_phys_bootstrap_alloc(vm_size_t size, unsigned long alignment)
486 {
487 	vm_paddr_t pa;
488 	int i;
489 
490 	size = round_page(size);
491 	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
492 		if (phys_avail[i + 1] - phys_avail[i] < size)
493 			continue;
494 		pa = phys_avail[i];
495 		phys_avail[i] += size;
496 		return (pa);
497 	}
498 	panic("vm_phys_bootstrap_alloc");
499 }
500 
501 /*
502  * Find the vm_page corresponding to the given physical address.
503  */
504 vm_page_t
505 vm_phys_paddr_to_vm_page(vm_paddr_t pa)
506 {
507 	struct vm_phys_seg *seg;
508 	int segind;
509 
510 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
511 		seg = &vm_phys_segs[segind];
512 		if (pa >= seg->start && pa < seg->end)
513 			return (&seg->first_page[atop(pa - seg->start)]);
514 	}
515 	return (NULL);
516 }
517 
518 /*
519  * Find the segment containing the given physical address.
520  */
521 static int
522 vm_phys_paddr_to_segind(vm_paddr_t pa)
523 {
524 	struct vm_phys_seg *seg;
525 	int segind;
526 
527 	for (segind = 0; segind < vm_phys_nsegs; segind++) {
528 		seg = &vm_phys_segs[segind];
529 		if (pa >= seg->start && pa < seg->end)
530 			return (segind);
531 	}
532 	panic("vm_phys_paddr_to_segind: paddr %#jx is not in any segment" ,
533 	    (uintmax_t)pa);
534 }
535 
536 /*
537  * Free a contiguous, power of two-sized set of physical pages.
538  *
539  * The free page queues must be locked.
540  */
541 void
542 vm_phys_free_pages(vm_page_t m, int order)
543 {
544 	struct vm_freelist *fl;
545 	struct vm_phys_seg *seg;
546 	vm_paddr_t pa, pa_buddy;
547 	vm_page_t m_buddy;
548 
549 	KASSERT(m->order == VM_NFREEORDER,
550 	    ("vm_phys_free_pages: page %p has unexpected order %d",
551 	    m, m->order));
552 	KASSERT(m->pool < VM_NFREEPOOL,
553 	    ("vm_phys_free_pages: page %p has unexpected pool %d",
554 	    m, m->pool));
555 	KASSERT(order < VM_NFREEORDER,
556 	    ("vm_phys_free_pages: order %d is out of range", order));
557 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
558 	pa = VM_PAGE_TO_PHYS(m);
559 	seg = &vm_phys_segs[m->segind];
560 	while (order < VM_NFREEORDER - 1) {
561 		pa_buddy = pa ^ (1 << (PAGE_SHIFT + order));
562 		if (pa_buddy < seg->start ||
563 		    pa_buddy >= seg->end)
564 			break;
565 		m_buddy = &seg->first_page[atop(pa_buddy - seg->start)];
566 		if (m_buddy->order != order)
567 			break;
568 		fl = (*seg->free_queues)[m_buddy->pool];
569 		TAILQ_REMOVE(&fl[m_buddy->order].pl, m_buddy, pageq);
570 		fl[m_buddy->order].lcnt--;
571 		m_buddy->order = VM_NFREEORDER;
572 		if (m_buddy->pool != m->pool)
573 			vm_phys_set_pool(m->pool, m_buddy, order);
574 		order++;
575 		pa &= ~((1 << (PAGE_SHIFT + order)) - 1);
576 		m = &seg->first_page[atop(pa - seg->start)];
577 	}
578 	m->order = order;
579 	fl = (*seg->free_queues)[m->pool];
580 	TAILQ_INSERT_TAIL(&fl[order].pl, m, pageq);
581 	fl[order].lcnt++;
582 }
583 
584 /*
585  * Set the pool for a contiguous, power of two-sized set of physical pages.
586  */
587 void
588 vm_phys_set_pool(int pool, vm_page_t m, int order)
589 {
590 	vm_page_t m_tmp;
591 
592 	for (m_tmp = m; m_tmp < &m[1 << order]; m_tmp++)
593 		m_tmp->pool = pool;
594 }
595 
596 /*
597  * Search for the given physical page "m" in the free lists.  If the search
598  * succeeds, remove "m" from the free lists and return TRUE.  Otherwise, return
599  * FALSE, indicating that "m" is not in the free lists.
600  *
601  * The free page queues must be locked.
602  */
603 boolean_t
604 vm_phys_unfree_page(vm_page_t m)
605 {
606 	struct vm_freelist *fl;
607 	struct vm_phys_seg *seg;
608 	vm_paddr_t pa, pa_half;
609 	vm_page_t m_set, m_tmp;
610 	int order;
611 
612 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
613 
614 	/*
615 	 * First, find the contiguous, power of two-sized set of free
616 	 * physical pages containing the given physical page "m" and
617 	 * assign it to "m_set".
618 	 */
619 	seg = &vm_phys_segs[m->segind];
620 	for (m_set = m, order = 0; m_set->order == VM_NFREEORDER &&
621 	    order < VM_NFREEORDER - 1; ) {
622 		order++;
623 		pa = m->phys_addr & (~(vm_paddr_t)0 << (PAGE_SHIFT + order));
624 		if (pa >= seg->start)
625 			m_set = &seg->first_page[atop(pa - seg->start)];
626 		else
627 			return (FALSE);
628 	}
629 	if (m_set->order < order)
630 		return (FALSE);
631 	if (m_set->order == VM_NFREEORDER)
632 		return (FALSE);
633 	KASSERT(m_set->order < VM_NFREEORDER,
634 	    ("vm_phys_unfree_page: page %p has unexpected order %d",
635 	    m_set, m_set->order));
636 
637 	/*
638 	 * Next, remove "m_set" from the free lists.  Finally, extract
639 	 * "m" from "m_set" using an iterative algorithm: While "m_set"
640 	 * is larger than a page, shrink "m_set" by returning the half
641 	 * of "m_set" that does not contain "m" to the free lists.
642 	 */
643 	fl = (*seg->free_queues)[m_set->pool];
644 	order = m_set->order;
645 	TAILQ_REMOVE(&fl[order].pl, m_set, pageq);
646 	fl[order].lcnt--;
647 	m_set->order = VM_NFREEORDER;
648 	while (order > 0) {
649 		order--;
650 		pa_half = m_set->phys_addr ^ (1 << (PAGE_SHIFT + order));
651 		if (m->phys_addr < pa_half)
652 			m_tmp = &seg->first_page[atop(pa_half - seg->start)];
653 		else {
654 			m_tmp = m_set;
655 			m_set = &seg->first_page[atop(pa_half - seg->start)];
656 		}
657 		m_tmp->order = order;
658 		TAILQ_INSERT_HEAD(&fl[order].pl, m_tmp, pageq);
659 		fl[order].lcnt++;
660 	}
661 	KASSERT(m_set == m, ("vm_phys_unfree_page: fatal inconsistency"));
662 	return (TRUE);
663 }
664 
665 /*
666  * Try to zero one physical page.  Used by an idle priority thread.
667  */
668 boolean_t
669 vm_phys_zero_pages_idle(void)
670 {
671 	static struct vm_freelist *fl = vm_phys_free_queues[0][0];
672 	static int flind, oind, pind;
673 	vm_page_t m, m_tmp;
674 
675 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
676 	for (;;) {
677 		TAILQ_FOREACH_REVERSE(m, &fl[oind].pl, pglist, pageq) {
678 			for (m_tmp = m; m_tmp < &m[1 << oind]; m_tmp++) {
679 				if ((m_tmp->flags & (PG_CACHED | PG_ZERO)) == 0) {
680 					vm_phys_unfree_page(m_tmp);
681 					cnt.v_free_count--;
682 					mtx_unlock(&vm_page_queue_free_mtx);
683 					pmap_zero_page_idle(m_tmp);
684 					m_tmp->flags |= PG_ZERO;
685 					mtx_lock(&vm_page_queue_free_mtx);
686 					cnt.v_free_count++;
687 					vm_phys_free_pages(m_tmp, 0);
688 					vm_page_zero_count++;
689 					cnt_prezero++;
690 					return (TRUE);
691 				}
692 			}
693 		}
694 		oind++;
695 		if (oind == VM_NFREEORDER) {
696 			oind = 0;
697 			pind++;
698 			if (pind == VM_NFREEPOOL) {
699 				pind = 0;
700 				flind++;
701 				if (flind == vm_nfreelists)
702 					flind = 0;
703 			}
704 			fl = vm_phys_free_queues[flind][pind];
705 		}
706 	}
707 }
708 
709 /*
710  * Allocate a contiguous set of physical pages of the given size
711  * "npages" from the free lists.  All of the physical pages must be at
712  * or above the given physical address "low" and below the given
713  * physical address "high".  The given value "alignment" determines the
714  * alignment of the first physical page in the set.  If the given value
715  * "boundary" is non-zero, then the set of physical pages cannot cross
716  * any physical address boundary that is a multiple of that value.  Both
717  * "alignment" and "boundary" must be a power of two.
718  */
719 vm_page_t
720 vm_phys_alloc_contig(unsigned long npages, vm_paddr_t low, vm_paddr_t high,
721     unsigned long alignment, unsigned long boundary)
722 {
723 	struct vm_freelist *fl;
724 	struct vm_phys_seg *seg;
725 	struct vnode *vp;
726 	vm_paddr_t pa, pa_last, size;
727 	vm_page_t deferred_vdrop_list, m, m_ret;
728 	int domain, flind, i, oind, order, pind;
729 
730 #if VM_NDOMAIN > 1
731 	domain = PCPU_GET(domain);
732 #else
733 	domain = 0;
734 #endif
735 	size = npages << PAGE_SHIFT;
736 	KASSERT(size != 0,
737 	    ("vm_phys_alloc_contig: size must not be 0"));
738 	KASSERT((alignment & (alignment - 1)) == 0,
739 	    ("vm_phys_alloc_contig: alignment must be a power of 2"));
740 	KASSERT((boundary & (boundary - 1)) == 0,
741 	    ("vm_phys_alloc_contig: boundary must be a power of 2"));
742 	deferred_vdrop_list = NULL;
743 	/* Compute the queue that is the best fit for npages. */
744 	for (order = 0; (1 << order) < npages; order++);
745 	mtx_lock(&vm_page_queue_free_mtx);
746 #if VM_NRESERVLEVEL > 0
747 retry:
748 #endif
749 	for (flind = 0; flind < vm_nfreelists; flind++) {
750 		for (oind = min(order, VM_NFREEORDER - 1); oind < VM_NFREEORDER; oind++) {
751 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
752 				fl = (*vm_phys_lookup_lists[domain][flind])
753 				    [pind];
754 				TAILQ_FOREACH(m_ret, &fl[oind].pl, pageq) {
755 					/*
756 					 * A free list may contain physical pages
757 					 * from one or more segments.
758 					 */
759 					seg = &vm_phys_segs[m_ret->segind];
760 					if (seg->start > high ||
761 					    low >= seg->end)
762 						continue;
763 
764 					/*
765 					 * Is the size of this allocation request
766 					 * larger than the largest block size?
767 					 */
768 					if (order >= VM_NFREEORDER) {
769 						/*
770 						 * Determine if a sufficient number
771 						 * of subsequent blocks to satisfy
772 						 * the allocation request are free.
773 						 */
774 						pa = VM_PAGE_TO_PHYS(m_ret);
775 						pa_last = pa + size;
776 						for (;;) {
777 							pa += 1 << (PAGE_SHIFT + VM_NFREEORDER - 1);
778 							if (pa >= pa_last)
779 								break;
780 							if (pa < seg->start ||
781 							    pa >= seg->end)
782 								break;
783 							m = &seg->first_page[atop(pa - seg->start)];
784 							if (m->order != VM_NFREEORDER - 1)
785 								break;
786 						}
787 						/* If not, continue to the next block. */
788 						if (pa < pa_last)
789 							continue;
790 					}
791 
792 					/*
793 					 * Determine if the blocks are within the given range,
794 					 * satisfy the given alignment, and do not cross the
795 					 * given boundary.
796 					 */
797 					pa = VM_PAGE_TO_PHYS(m_ret);
798 					if (pa >= low &&
799 					    pa + size <= high &&
800 					    (pa & (alignment - 1)) == 0 &&
801 					    ((pa ^ (pa + size - 1)) & ~(boundary - 1)) == 0)
802 						goto done;
803 				}
804 			}
805 		}
806 	}
807 #if VM_NRESERVLEVEL > 0
808 	if (vm_reserv_reclaim_contig(size, low, high, alignment, boundary))
809 		goto retry;
810 #endif
811 	mtx_unlock(&vm_page_queue_free_mtx);
812 	return (NULL);
813 done:
814 	for (m = m_ret; m < &m_ret[npages]; m = &m[1 << oind]) {
815 		fl = (*seg->free_queues)[m->pool];
816 		TAILQ_REMOVE(&fl[m->order].pl, m, pageq);
817 		fl[m->order].lcnt--;
818 		m->order = VM_NFREEORDER;
819 	}
820 	if (m_ret->pool != VM_FREEPOOL_DEFAULT)
821 		vm_phys_set_pool(VM_FREEPOOL_DEFAULT, m_ret, oind);
822 	fl = (*seg->free_queues)[m_ret->pool];
823 	vm_phys_split_pages(m_ret, oind, fl, order);
824 	for (i = 0; i < npages; i++) {
825 		m = &m_ret[i];
826 		vp = vm_page_alloc_init(m);
827 		if (vp != NULL) {
828 			/*
829 			 * Enqueue the vnode for deferred vdrop().
830 			 *
831 			 * Unmanaged pages don't use "pageq", so it
832 			 * can be safely abused to construct a short-
833 			 * lived queue of vnodes.
834 			 */
835 			m->pageq.tqe_prev = (void *)vp;
836 			m->pageq.tqe_next = deferred_vdrop_list;
837 			deferred_vdrop_list = m;
838 		}
839 	}
840 	for (; i < roundup2(npages, 1 << imin(oind, order)); i++) {
841 		m = &m_ret[i];
842 		KASSERT(m->order == VM_NFREEORDER,
843 		    ("vm_phys_alloc_contig: page %p has unexpected order %d",
844 		    m, m->order));
845 		vm_phys_free_pages(m, 0);
846 	}
847 	mtx_unlock(&vm_page_queue_free_mtx);
848 	while (deferred_vdrop_list != NULL) {
849 		vdrop((struct vnode *)deferred_vdrop_list->pageq.tqe_prev);
850 		deferred_vdrop_list = deferred_vdrop_list->pageq.tqe_next;
851 	}
852 	return (m_ret);
853 }
854 
855 #ifdef DDB
856 /*
857  * Show the number of physical pages in each of the free lists.
858  */
859 DB_SHOW_COMMAND(freepages, db_show_freepages)
860 {
861 	struct vm_freelist *fl;
862 	int flind, oind, pind;
863 
864 	for (flind = 0; flind < vm_nfreelists; flind++) {
865 		db_printf("FREE LIST %d:\n"
866 		    "\n  ORDER (SIZE)  |  NUMBER"
867 		    "\n              ", flind);
868 		for (pind = 0; pind < VM_NFREEPOOL; pind++)
869 			db_printf("  |  POOL %d", pind);
870 		db_printf("\n--            ");
871 		for (pind = 0; pind < VM_NFREEPOOL; pind++)
872 			db_printf("-- --      ");
873 		db_printf("--\n");
874 		for (oind = VM_NFREEORDER - 1; oind >= 0; oind--) {
875 			db_printf("  %2.2d (%6.6dK)", oind,
876 			    1 << (PAGE_SHIFT - 10 + oind));
877 			for (pind = 0; pind < VM_NFREEPOOL; pind++) {
878 				fl = vm_phys_free_queues[flind][pind];
879 				db_printf("  |  %6.6d", fl[oind].lcnt);
880 			}
881 			db_printf("\n");
882 		}
883 		db_printf("\n");
884 	}
885 }
886 #endif
887