1 /*-
2 * Copyright (c) 2002-2006 Rice University
3 * Copyright (c) 2007-2011 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 * Superpage reservation management module
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_vm.h"
43
44 #include <sys/param.h>
45 #include <sys/kernel.h>
46 #include <sys/lock.h>
47 #include <sys/malloc.h>
48 #include <sys/mutex.h>
49 #include <sys/queue.h>
50 #include <sys/rwlock.h>
51 #include <sys/sbuf.h>
52 #include <sys/sysctl.h>
53 #include <sys/systm.h>
54
55 #include <vm/vm.h>
56 #include <vm/vm_param.h>
57 #include <vm/vm_object.h>
58 #include <vm/vm_page.h>
59 #include <vm/vm_phys.h>
60 #include <vm/vm_radix.h>
61 #include <vm/vm_reserv.h>
62
63 /*
64 * The reservation system supports the speculative allocation of large physical
65 * pages ("superpages"). Speculative allocation enables the fully-automatic
66 * utilization of superpages by the virtual memory system. In other words, no
67 * programmatic directives are required to use superpages.
68 */
69
70 #if VM_NRESERVLEVEL > 0
71
72 /*
73 * The number of small pages that are contained in a level 0 reservation
74 */
75 #define VM_LEVEL_0_NPAGES (1 << VM_LEVEL_0_ORDER)
76
77 /*
78 * The number of bits by which a physical address is shifted to obtain the
79 * reservation number
80 */
81 #define VM_LEVEL_0_SHIFT (VM_LEVEL_0_ORDER + PAGE_SHIFT)
82
83 /*
84 * The size of a level 0 reservation in bytes
85 */
86 #define VM_LEVEL_0_SIZE (1 << VM_LEVEL_0_SHIFT)
87
88 /*
89 * Computes the index of the small page underlying the given (object, pindex)
90 * within the reservation's array of small pages.
91 */
92 #define VM_RESERV_INDEX(object, pindex) \
93 (((object)->pg_color + (pindex)) & (VM_LEVEL_0_NPAGES - 1))
94
95 /*
96 * The size of a population map entry
97 */
98 typedef u_long popmap_t;
99
100 /*
101 * The number of bits in a population map entry
102 */
103 #define NBPOPMAP (NBBY * sizeof(popmap_t))
104
105 /*
106 * The number of population map entries in a reservation
107 */
108 #define NPOPMAP howmany(VM_LEVEL_0_NPAGES, NBPOPMAP)
109
110 /*
111 * Clear a bit in the population map.
112 */
113 static __inline void
popmap_clear(popmap_t popmap[],int i)114 popmap_clear(popmap_t popmap[], int i)
115 {
116
117 popmap[i / NBPOPMAP] &= ~(1UL << (i % NBPOPMAP));
118 }
119
120 /*
121 * Set a bit in the population map.
122 */
123 static __inline void
popmap_set(popmap_t popmap[],int i)124 popmap_set(popmap_t popmap[], int i)
125 {
126
127 popmap[i / NBPOPMAP] |= 1UL << (i % NBPOPMAP);
128 }
129
130 /*
131 * Is a bit in the population map clear?
132 */
133 #ifdef INVARIANTS
134 static __inline boolean_t
popmap_is_clear(popmap_t popmap[],int i)135 popmap_is_clear(popmap_t popmap[], int i)
136 {
137
138 return ((popmap[i / NBPOPMAP] & (1UL << (i % NBPOPMAP))) == 0);
139 }
140 #endif
141
142 /*
143 * Is a bit in the population map set?
144 */
145 static __inline boolean_t
popmap_is_set(popmap_t popmap[],int i)146 popmap_is_set(popmap_t popmap[], int i)
147 {
148
149 return ((popmap[i / NBPOPMAP] & (1UL << (i % NBPOPMAP))) != 0);
150 }
151
152 /*
153 * The reservation structure
154 *
155 * A reservation structure is constructed whenever a large physical page is
156 * speculatively allocated to an object. The reservation provides the small
157 * physical pages for the range [pindex, pindex + VM_LEVEL_0_NPAGES) of offsets
158 * within that object. The reservation's "popcnt" tracks the number of these
159 * small physical pages that are in use at any given time. When and if the
160 * reservation is not fully utilized, it appears in the queue of partially-
161 * populated reservations. The reservation always appears on the containing
162 * object's list of reservations.
163 *
164 * A partially-populated reservation can be broken and reclaimed at any time.
165 */
166 struct vm_reserv {
167 TAILQ_ENTRY(vm_reserv) partpopq;
168 LIST_ENTRY(vm_reserv) objq;
169 vm_object_t object; /* containing object */
170 vm_pindex_t pindex; /* offset within object */
171 vm_page_t pages; /* first page of a superpage */
172 int popcnt; /* # of pages in use */
173 char inpartpopq;
174 popmap_t popmap[NPOPMAP]; /* bit vector of used pages */
175 };
176
177 /*
178 * The reservation array
179 *
180 * This array is analoguous in function to vm_page_array. It differs in the
181 * respect that it may contain a greater number of useful reservation
182 * structures than there are (physical) superpages. These "invalid"
183 * reservation structures exist to trade-off space for time in the
184 * implementation of vm_reserv_from_page(). Invalid reservation structures are
185 * distinguishable from "valid" reservation structures by inspecting the
186 * reservation's "pages" field. Invalid reservation structures have a NULL
187 * "pages" field.
188 *
189 * vm_reserv_from_page() maps a small (physical) page to an element of this
190 * array by computing a physical reservation number from the page's physical
191 * address. The physical reservation number is used as the array index.
192 *
193 * An "active" reservation is a valid reservation structure that has a non-NULL
194 * "object" field and a non-zero "popcnt" field. In other words, every active
195 * reservation belongs to a particular object. Moreover, every active
196 * reservation has an entry in the containing object's list of reservations.
197 */
198 static vm_reserv_t vm_reserv_array;
199
200 /*
201 * The partially-populated reservation queue
202 *
203 * This queue enables the fast recovery of an unused cached or free small page
204 * from a partially-populated reservation. The reservation at the head of
205 * this queue is the least-recently-changed, partially-populated reservation.
206 *
207 * Access to this queue is synchronized by the free page queue lock.
208 */
209 static TAILQ_HEAD(, vm_reserv) vm_rvq_partpop =
210 TAILQ_HEAD_INITIALIZER(vm_rvq_partpop);
211
212 static SYSCTL_NODE(_vm, OID_AUTO, reserv, CTLFLAG_RD, 0, "Reservation Info");
213
214 static long vm_reserv_broken;
215 SYSCTL_LONG(_vm_reserv, OID_AUTO, broken, CTLFLAG_RD,
216 &vm_reserv_broken, 0, "Cumulative number of broken reservations");
217
218 static long vm_reserv_freed;
219 SYSCTL_LONG(_vm_reserv, OID_AUTO, freed, CTLFLAG_RD,
220 &vm_reserv_freed, 0, "Cumulative number of freed reservations");
221
222 static int sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS);
223
224 SYSCTL_PROC(_vm_reserv, OID_AUTO, fullpop, CTLTYPE_INT | CTLFLAG_RD, NULL, 0,
225 sysctl_vm_reserv_fullpop, "I", "Current number of full reservations");
226
227 static int sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS);
228
229 SYSCTL_OID(_vm_reserv, OID_AUTO, partpopq, CTLTYPE_STRING | CTLFLAG_RD, NULL, 0,
230 sysctl_vm_reserv_partpopq, "A", "Partially-populated reservation queues");
231
232 static long vm_reserv_reclaimed;
233 SYSCTL_LONG(_vm_reserv, OID_AUTO, reclaimed, CTLFLAG_RD,
234 &vm_reserv_reclaimed, 0, "Cumulative number of reclaimed reservations");
235
236 static void vm_reserv_break(vm_reserv_t rv, vm_page_t m);
237 static void vm_reserv_depopulate(vm_reserv_t rv, int index);
238 static vm_reserv_t vm_reserv_from_page(vm_page_t m);
239 static boolean_t vm_reserv_has_pindex(vm_reserv_t rv,
240 vm_pindex_t pindex);
241 static void vm_reserv_populate(vm_reserv_t rv, int index);
242 static void vm_reserv_reclaim(vm_reserv_t rv);
243
244 /*
245 * Returns the current number of full reservations.
246 *
247 * Since the number of full reservations is computed without acquiring the
248 * free page queue lock, the returned value may be inexact.
249 */
250 static int
sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS)251 sysctl_vm_reserv_fullpop(SYSCTL_HANDLER_ARGS)
252 {
253 vm_paddr_t paddr;
254 struct vm_phys_seg *seg;
255 vm_reserv_t rv;
256 int fullpop, segind;
257
258 fullpop = 0;
259 for (segind = 0; segind < vm_phys_nsegs; segind++) {
260 seg = &vm_phys_segs[segind];
261 paddr = roundup2(seg->start, VM_LEVEL_0_SIZE);
262 while (paddr + VM_LEVEL_0_SIZE <= seg->end) {
263 rv = &vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT];
264 fullpop += rv->popcnt == VM_LEVEL_0_NPAGES;
265 paddr += VM_LEVEL_0_SIZE;
266 }
267 }
268 return (sysctl_handle_int(oidp, &fullpop, 0, req));
269 }
270
271 /*
272 * Describes the current state of the partially-populated reservation queue.
273 */
274 static int
sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS)275 sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS)
276 {
277 struct sbuf sbuf;
278 vm_reserv_t rv;
279 int counter, error, level, unused_pages;
280
281 error = sysctl_wire_old_buffer(req, 0);
282 if (error != 0)
283 return (error);
284 sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
285 sbuf_printf(&sbuf, "\nLEVEL SIZE NUMBER\n\n");
286 for (level = -1; level <= VM_NRESERVLEVEL - 2; level++) {
287 counter = 0;
288 unused_pages = 0;
289 mtx_lock(&vm_page_queue_free_mtx);
290 TAILQ_FOREACH(rv, &vm_rvq_partpop/*[level]*/, partpopq) {
291 counter++;
292 unused_pages += VM_LEVEL_0_NPAGES - rv->popcnt;
293 }
294 mtx_unlock(&vm_page_queue_free_mtx);
295 sbuf_printf(&sbuf, "%5d: %6dK, %6d\n", level,
296 unused_pages * ((int)PAGE_SIZE / 1024), counter);
297 }
298 error = sbuf_finish(&sbuf);
299 sbuf_delete(&sbuf);
300 return (error);
301 }
302
303 /*
304 * Reduces the given reservation's population count. If the population count
305 * becomes zero, the reservation is destroyed. Additionally, moves the
306 * reservation to the tail of the partially-populated reservation queue if the
307 * population count is non-zero.
308 *
309 * The free page queue lock must be held.
310 */
311 static void
vm_reserv_depopulate(vm_reserv_t rv,int index)312 vm_reserv_depopulate(vm_reserv_t rv, int index)
313 {
314
315 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
316 KASSERT(rv->object != NULL,
317 ("vm_reserv_depopulate: reserv %p is free", rv));
318 KASSERT(popmap_is_set(rv->popmap, index),
319 ("vm_reserv_depopulate: reserv %p's popmap[%d] is clear", rv,
320 index));
321 KASSERT(rv->popcnt > 0,
322 ("vm_reserv_depopulate: reserv %p's popcnt is corrupted", rv));
323 if (rv->inpartpopq) {
324 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
325 rv->inpartpopq = FALSE;
326 } else {
327 KASSERT(rv->pages->psind == 1,
328 ("vm_reserv_depopulate: reserv %p is already demoted",
329 rv));
330 rv->pages->psind = 0;
331 }
332 popmap_clear(rv->popmap, index);
333 rv->popcnt--;
334 if (rv->popcnt == 0) {
335 LIST_REMOVE(rv, objq);
336 rv->object = NULL;
337 vm_phys_free_pages(rv->pages, VM_LEVEL_0_ORDER);
338 vm_reserv_freed++;
339 } else {
340 rv->inpartpopq = TRUE;
341 TAILQ_INSERT_TAIL(&vm_rvq_partpop, rv, partpopq);
342 }
343 }
344
345 /*
346 * Returns the reservation to which the given page might belong.
347 */
348 static __inline vm_reserv_t
vm_reserv_from_page(vm_page_t m)349 vm_reserv_from_page(vm_page_t m)
350 {
351
352 return (&vm_reserv_array[VM_PAGE_TO_PHYS(m) >> VM_LEVEL_0_SHIFT]);
353 }
354
355 /*
356 * Returns TRUE if the given reservation contains the given page index and
357 * FALSE otherwise.
358 */
359 static __inline boolean_t
vm_reserv_has_pindex(vm_reserv_t rv,vm_pindex_t pindex)360 vm_reserv_has_pindex(vm_reserv_t rv, vm_pindex_t pindex)
361 {
362
363 return (((pindex - rv->pindex) & ~(VM_LEVEL_0_NPAGES - 1)) == 0);
364 }
365
366 /*
367 * Increases the given reservation's population count. Moves the reservation
368 * to the tail of the partially-populated reservation queue.
369 *
370 * The free page queue must be locked.
371 */
372 static void
vm_reserv_populate(vm_reserv_t rv,int index)373 vm_reserv_populate(vm_reserv_t rv, int index)
374 {
375
376 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
377 KASSERT(rv->object != NULL,
378 ("vm_reserv_populate: reserv %p is free", rv));
379 KASSERT(popmap_is_clear(rv->popmap, index),
380 ("vm_reserv_populate: reserv %p's popmap[%d] is set", rv,
381 index));
382 KASSERT(rv->popcnt < VM_LEVEL_0_NPAGES,
383 ("vm_reserv_populate: reserv %p is already full", rv));
384 KASSERT(rv->pages->psind == 0,
385 ("vm_reserv_populate: reserv %p is already promoted", rv));
386 if (rv->inpartpopq) {
387 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
388 rv->inpartpopq = FALSE;
389 }
390 popmap_set(rv->popmap, index);
391 rv->popcnt++;
392 if (rv->popcnt < VM_LEVEL_0_NPAGES) {
393 rv->inpartpopq = TRUE;
394 TAILQ_INSERT_TAIL(&vm_rvq_partpop, rv, partpopq);
395 } else
396 rv->pages->psind = 1;
397 }
398
399 /*
400 * Allocates a contiguous set of physical pages of the given size "npages"
401 * from existing or newly created reservations. All of the physical pages
402 * must be at or above the given physical address "low" and below the given
403 * physical address "high". The given value "alignment" determines the
404 * alignment of the first physical page in the set. If the given value
405 * "boundary" is non-zero, then the set of physical pages cannot cross any
406 * physical address boundary that is a multiple of that value. Both
407 * "alignment" and "boundary" must be a power of two.
408 *
409 * The object and free page queue must be locked.
410 */
411 vm_page_t
vm_reserv_alloc_contig(vm_object_t object,vm_pindex_t pindex,u_long npages,vm_paddr_t low,vm_paddr_t high,u_long alignment,vm_paddr_t boundary)412 vm_reserv_alloc_contig(vm_object_t object, vm_pindex_t pindex, u_long npages,
413 vm_paddr_t low, vm_paddr_t high, u_long alignment, vm_paddr_t boundary)
414 {
415 vm_paddr_t pa, size;
416 vm_page_t m, m_ret, mpred, msucc;
417 vm_pindex_t first, leftcap, rightcap;
418 vm_reserv_t rv;
419 u_long allocpages, maxpages, minpages;
420 int i, index, n;
421
422 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
423 VM_OBJECT_ASSERT_WLOCKED(object);
424 KASSERT(npages != 0, ("vm_reserv_alloc_contig: npages is 0"));
425
426 /*
427 * Is a reservation fundamentally impossible?
428 */
429 if (pindex < VM_RESERV_INDEX(object, pindex) ||
430 pindex + npages > object->size)
431 return (NULL);
432
433 /*
434 * All reservations of a particular size have the same alignment.
435 * Assuming that the first page is allocated from a reservation, the
436 * least significant bits of its physical address can be determined
437 * from its offset from the beginning of the reservation and the size
438 * of the reservation.
439 *
440 * Could the specified index within a reservation of the smallest
441 * possible size satisfy the alignment and boundary requirements?
442 */
443 pa = VM_RESERV_INDEX(object, pindex) << PAGE_SHIFT;
444 if ((pa & (alignment - 1)) != 0)
445 return (NULL);
446 size = npages << PAGE_SHIFT;
447 if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0)
448 return (NULL);
449
450 /*
451 * Look for an existing reservation.
452 */
453 mpred = vm_radix_lookup_le(&object->rtree, pindex);
454 if (mpred != NULL) {
455 KASSERT(mpred->pindex < pindex,
456 ("vm_reserv_alloc_contig: pindex already allocated"));
457 rv = vm_reserv_from_page(mpred);
458 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
459 goto found;
460 msucc = TAILQ_NEXT(mpred, listq);
461 } else
462 msucc = TAILQ_FIRST(&object->memq);
463 if (msucc != NULL) {
464 KASSERT(msucc->pindex > pindex,
465 ("vm_reserv_alloc_contig: pindex already allocated"));
466 rv = vm_reserv_from_page(msucc);
467 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
468 goto found;
469 }
470
471 /*
472 * Could at least one reservation fit between the first index to the
473 * left that can be used ("leftcap") and the first index to the right
474 * that cannot be used ("rightcap")?
475 */
476 first = pindex - VM_RESERV_INDEX(object, pindex);
477 if (mpred != NULL) {
478 if ((rv = vm_reserv_from_page(mpred))->object != object)
479 leftcap = mpred->pindex + 1;
480 else
481 leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
482 if (leftcap > first)
483 return (NULL);
484 }
485 minpages = VM_RESERV_INDEX(object, pindex) + npages;
486 maxpages = roundup2(minpages, VM_LEVEL_0_NPAGES);
487 allocpages = maxpages;
488 if (msucc != NULL) {
489 if ((rv = vm_reserv_from_page(msucc))->object != object)
490 rightcap = msucc->pindex;
491 else
492 rightcap = rv->pindex;
493 if (first + maxpages > rightcap) {
494 if (maxpages == VM_LEVEL_0_NPAGES)
495 return (NULL);
496
497 /*
498 * At least one reservation will fit between "leftcap"
499 * and "rightcap". However, a reservation for the
500 * last of the requested pages will not fit. Reduce
501 * the size of the upcoming allocation accordingly.
502 */
503 allocpages = minpages;
504 }
505 }
506
507 /*
508 * Would the last new reservation extend past the end of the object?
509 */
510 if (first + maxpages > object->size) {
511 /*
512 * Don't allocate the last new reservation if the object is a
513 * vnode or backed by another object that is a vnode.
514 */
515 if (object->type == OBJT_VNODE ||
516 (object->backing_object != NULL &&
517 object->backing_object->type == OBJT_VNODE)) {
518 if (maxpages == VM_LEVEL_0_NPAGES)
519 return (NULL);
520 allocpages = minpages;
521 }
522 /* Speculate that the object may grow. */
523 }
524
525 /*
526 * Allocate the physical pages. The alignment and boundary specified
527 * for this allocation may be different from the alignment and
528 * boundary specified for the requested pages. For instance, the
529 * specified index may not be the first page within the first new
530 * reservation.
531 */
532 m = vm_phys_alloc_contig(allocpages, low, high, ulmax(alignment,
533 VM_LEVEL_0_SIZE), boundary > VM_LEVEL_0_SIZE ? boundary : 0);
534 if (m == NULL)
535 return (NULL);
536
537 /*
538 * The allocated physical pages always begin at a reservation
539 * boundary, but they do not always end at a reservation boundary.
540 * Initialize every reservation that is completely covered by the
541 * allocated physical pages.
542 */
543 m_ret = NULL;
544 index = VM_RESERV_INDEX(object, pindex);
545 do {
546 rv = vm_reserv_from_page(m);
547 KASSERT(rv->pages == m,
548 ("vm_reserv_alloc_contig: reserv %p's pages is corrupted",
549 rv));
550 KASSERT(rv->object == NULL,
551 ("vm_reserv_alloc_contig: reserv %p isn't free", rv));
552 LIST_INSERT_HEAD(&object->rvq, rv, objq);
553 rv->object = object;
554 rv->pindex = first;
555 KASSERT(rv->popcnt == 0,
556 ("vm_reserv_alloc_contig: reserv %p's popcnt is corrupted",
557 rv));
558 KASSERT(!rv->inpartpopq,
559 ("vm_reserv_alloc_contig: reserv %p's inpartpopq is TRUE",
560 rv));
561 for (i = 0; i < NPOPMAP; i++)
562 KASSERT(rv->popmap[i] == 0,
563 ("vm_reserv_alloc_contig: reserv %p's popmap is corrupted",
564 rv));
565 n = ulmin(VM_LEVEL_0_NPAGES - index, npages);
566 for (i = 0; i < n; i++)
567 vm_reserv_populate(rv, index + i);
568 npages -= n;
569 if (m_ret == NULL) {
570 m_ret = &rv->pages[index];
571 index = 0;
572 }
573 m += VM_LEVEL_0_NPAGES;
574 first += VM_LEVEL_0_NPAGES;
575 allocpages -= VM_LEVEL_0_NPAGES;
576 } while (allocpages >= VM_LEVEL_0_NPAGES);
577 return (m_ret);
578
579 /*
580 * Found a matching reservation.
581 */
582 found:
583 index = VM_RESERV_INDEX(object, pindex);
584 /* Does the allocation fit within the reservation? */
585 if (index + npages > VM_LEVEL_0_NPAGES)
586 return (NULL);
587 m = &rv->pages[index];
588 pa = VM_PAGE_TO_PHYS(m);
589 if (pa < low || pa + size > high || (pa & (alignment - 1)) != 0 ||
590 ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0)
591 return (NULL);
592 /* Handle vm_page_rename(m, new_object, ...). */
593 for (i = 0; i < npages; i++)
594 if (popmap_is_set(rv->popmap, index + i))
595 return (NULL);
596 for (i = 0; i < npages; i++)
597 vm_reserv_populate(rv, index + i);
598 return (m);
599 }
600
601 /*
602 * Allocates a page from an existing or newly-created reservation.
603 *
604 * The page "mpred" must immediately precede the offset "pindex" within the
605 * specified object.
606 *
607 * The object and free page queue must be locked.
608 */
609 vm_page_t
vm_reserv_alloc_page(vm_object_t object,vm_pindex_t pindex,vm_page_t mpred)610 vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex, vm_page_t mpred)
611 {
612 vm_page_t m, msucc;
613 vm_pindex_t first, leftcap, rightcap;
614 vm_reserv_t rv;
615 int i, index;
616
617 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
618 VM_OBJECT_ASSERT_WLOCKED(object);
619
620 /*
621 * Is a reservation fundamentally impossible?
622 */
623 if (pindex < VM_RESERV_INDEX(object, pindex) ||
624 pindex >= object->size)
625 return (NULL);
626
627 /*
628 * Look for an existing reservation.
629 */
630 if (mpred != NULL) {
631 KASSERT(mpred->object == object,
632 ("vm_reserv_alloc_page: object doesn't contain mpred"));
633 KASSERT(mpred->pindex < pindex,
634 ("vm_reserv_alloc_page: mpred doesn't precede pindex"));
635 rv = vm_reserv_from_page(mpred);
636 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
637 goto found;
638 msucc = TAILQ_NEXT(mpred, listq);
639 } else
640 msucc = TAILQ_FIRST(&object->memq);
641 if (msucc != NULL) {
642 KASSERT(msucc->pindex > pindex,
643 ("vm_reserv_alloc_page: msucc doesn't succeed pindex"));
644 rv = vm_reserv_from_page(msucc);
645 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
646 goto found;
647 }
648
649 /*
650 * Could a reservation fit between the first index to the left that
651 * can be used and the first index to the right that cannot be used?
652 */
653 first = pindex - VM_RESERV_INDEX(object, pindex);
654 if (mpred != NULL) {
655 if ((rv = vm_reserv_from_page(mpred))->object != object)
656 leftcap = mpred->pindex + 1;
657 else
658 leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
659 if (leftcap > first)
660 return (NULL);
661 }
662 if (msucc != NULL) {
663 if ((rv = vm_reserv_from_page(msucc))->object != object)
664 rightcap = msucc->pindex;
665 else
666 rightcap = rv->pindex;
667 if (first + VM_LEVEL_0_NPAGES > rightcap)
668 return (NULL);
669 }
670
671 /*
672 * Would a new reservation extend past the end of the object?
673 */
674 if (first + VM_LEVEL_0_NPAGES > object->size) {
675 /*
676 * Don't allocate a new reservation if the object is a vnode or
677 * backed by another object that is a vnode.
678 */
679 if (object->type == OBJT_VNODE ||
680 (object->backing_object != NULL &&
681 object->backing_object->type == OBJT_VNODE))
682 return (NULL);
683 /* Speculate that the object may grow. */
684 }
685
686 /*
687 * Allocate and populate the new reservation.
688 */
689 m = vm_phys_alloc_pages(VM_FREEPOOL_DEFAULT, VM_LEVEL_0_ORDER);
690 if (m == NULL)
691 return (NULL);
692 rv = vm_reserv_from_page(m);
693 KASSERT(rv->pages == m,
694 ("vm_reserv_alloc_page: reserv %p's pages is corrupted", rv));
695 KASSERT(rv->object == NULL,
696 ("vm_reserv_alloc_page: reserv %p isn't free", rv));
697 LIST_INSERT_HEAD(&object->rvq, rv, objq);
698 rv->object = object;
699 rv->pindex = first;
700 KASSERT(rv->popcnt == 0,
701 ("vm_reserv_alloc_page: reserv %p's popcnt is corrupted", rv));
702 KASSERT(!rv->inpartpopq,
703 ("vm_reserv_alloc_page: reserv %p's inpartpopq is TRUE", rv));
704 for (i = 0; i < NPOPMAP; i++)
705 KASSERT(rv->popmap[i] == 0,
706 ("vm_reserv_alloc_page: reserv %p's popmap is corrupted",
707 rv));
708 index = VM_RESERV_INDEX(object, pindex);
709 vm_reserv_populate(rv, index);
710 return (&rv->pages[index]);
711
712 /*
713 * Found a matching reservation.
714 */
715 found:
716 index = VM_RESERV_INDEX(object, pindex);
717 m = &rv->pages[index];
718 /* Handle vm_page_rename(m, new_object, ...). */
719 if (popmap_is_set(rv->popmap, index))
720 return (NULL);
721 vm_reserv_populate(rv, index);
722 return (m);
723 }
724
725 /*
726 * Breaks the given reservation. Except for the specified cached or free
727 * page, all cached and free pages in the reservation are returned to the
728 * physical memory allocator. The reservation's population count and map are
729 * reset to their initial state.
730 *
731 * The given reservation must not be in the partially-populated reservation
732 * queue. The free page queue lock must be held.
733 */
734 static void
vm_reserv_break(vm_reserv_t rv,vm_page_t m)735 vm_reserv_break(vm_reserv_t rv, vm_page_t m)
736 {
737 int begin_zeroes, hi, i, lo;
738
739 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
740 KASSERT(rv->object != NULL,
741 ("vm_reserv_break: reserv %p is free", rv));
742 KASSERT(!rv->inpartpopq,
743 ("vm_reserv_break: reserv %p's inpartpopq is TRUE", rv));
744 LIST_REMOVE(rv, objq);
745 rv->object = NULL;
746 if (m != NULL) {
747 /*
748 * Since the reservation is being broken, there is no harm in
749 * abusing the population map to stop "m" from being returned
750 * to the physical memory allocator.
751 */
752 i = m - rv->pages;
753 KASSERT(popmap_is_clear(rv->popmap, i),
754 ("vm_reserv_break: reserv %p's popmap is corrupted", rv));
755 popmap_set(rv->popmap, i);
756 rv->popcnt++;
757 }
758 i = hi = 0;
759 do {
760 /* Find the next 0 bit. Any previous 0 bits are < "hi". */
761 lo = ffsl(~(((1UL << hi) - 1) | rv->popmap[i]));
762 if (lo == 0) {
763 /* Redundantly clears bits < "hi". */
764 rv->popmap[i] = 0;
765 rv->popcnt -= NBPOPMAP - hi;
766 while (++i < NPOPMAP) {
767 lo = ffsl(~rv->popmap[i]);
768 if (lo == 0) {
769 rv->popmap[i] = 0;
770 rv->popcnt -= NBPOPMAP;
771 } else
772 break;
773 }
774 if (i == NPOPMAP)
775 break;
776 hi = 0;
777 }
778 KASSERT(lo > 0, ("vm_reserv_break: lo is %d", lo));
779 /* Convert from ffsl() to ordinary bit numbering. */
780 lo--;
781 if (lo > 0) {
782 /* Redundantly clears bits < "hi". */
783 rv->popmap[i] &= ~((1UL << lo) - 1);
784 rv->popcnt -= lo - hi;
785 }
786 begin_zeroes = NBPOPMAP * i + lo;
787 /* Find the next 1 bit. */
788 do
789 hi = ffsl(rv->popmap[i]);
790 while (hi == 0 && ++i < NPOPMAP);
791 if (i != NPOPMAP)
792 /* Convert from ffsl() to ordinary bit numbering. */
793 hi--;
794 vm_phys_free_contig(&rv->pages[begin_zeroes], NBPOPMAP * i +
795 hi - begin_zeroes);
796 } while (i < NPOPMAP);
797 KASSERT(rv->popcnt == 0,
798 ("vm_reserv_break: reserv %p's popcnt is corrupted", rv));
799 vm_reserv_broken++;
800 }
801
802 /*
803 * Breaks all reservations belonging to the given object.
804 */
805 void
vm_reserv_break_all(vm_object_t object)806 vm_reserv_break_all(vm_object_t object)
807 {
808 vm_reserv_t rv;
809
810 mtx_lock(&vm_page_queue_free_mtx);
811 while ((rv = LIST_FIRST(&object->rvq)) != NULL) {
812 KASSERT(rv->object == object,
813 ("vm_reserv_break_all: reserv %p is corrupted", rv));
814 if (rv->inpartpopq) {
815 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
816 rv->inpartpopq = FALSE;
817 }
818 vm_reserv_break(rv, NULL);
819 }
820 mtx_unlock(&vm_page_queue_free_mtx);
821 }
822
823 /*
824 * Frees the given page if it belongs to a reservation. Returns TRUE if the
825 * page is freed and FALSE otherwise.
826 *
827 * The free page queue lock must be held.
828 */
829 boolean_t
vm_reserv_free_page(vm_page_t m)830 vm_reserv_free_page(vm_page_t m)
831 {
832 vm_reserv_t rv;
833
834 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
835 rv = vm_reserv_from_page(m);
836 if (rv->object == NULL)
837 return (FALSE);
838 vm_reserv_depopulate(rv, m - rv->pages);
839 return (TRUE);
840 }
841
842 /*
843 * Initializes the reservation management system. Specifically, initializes
844 * the reservation array.
845 *
846 * Requires that vm_page_array and first_page are initialized!
847 */
848 void
vm_reserv_init(void)849 vm_reserv_init(void)
850 {
851 vm_paddr_t paddr;
852 struct vm_phys_seg *seg;
853 int segind;
854
855 /*
856 * Initialize the reservation array. Specifically, initialize the
857 * "pages" field for every element that has an underlying superpage.
858 */
859 for (segind = 0; segind < vm_phys_nsegs; segind++) {
860 seg = &vm_phys_segs[segind];
861 paddr = roundup2(seg->start, VM_LEVEL_0_SIZE);
862 while (paddr + VM_LEVEL_0_SIZE <= seg->end) {
863 vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT].pages =
864 PHYS_TO_VM_PAGE(paddr);
865 paddr += VM_LEVEL_0_SIZE;
866 }
867 }
868 }
869
870 /*
871 * Returns true if the given page belongs to a reservation and that page is
872 * free. Otherwise, returns false.
873 */
874 bool
vm_reserv_is_page_free(vm_page_t m)875 vm_reserv_is_page_free(vm_page_t m)
876 {
877 vm_reserv_t rv;
878
879 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
880 rv = vm_reserv_from_page(m);
881 if (rv->object == NULL)
882 return (false);
883 return (popmap_is_clear(rv->popmap, m - rv->pages));
884 }
885
886 /*
887 * If the given page belongs to a reservation, returns the level of that
888 * reservation. Otherwise, returns -1.
889 */
890 int
vm_reserv_level(vm_page_t m)891 vm_reserv_level(vm_page_t m)
892 {
893 vm_reserv_t rv;
894
895 rv = vm_reserv_from_page(m);
896 return (rv->object != NULL ? 0 : -1);
897 }
898
899 /*
900 * Returns a reservation level if the given page belongs to a fully-populated
901 * reservation and -1 otherwise.
902 */
903 int
vm_reserv_level_iffullpop(vm_page_t m)904 vm_reserv_level_iffullpop(vm_page_t m)
905 {
906 vm_reserv_t rv;
907
908 rv = vm_reserv_from_page(m);
909 return (rv->popcnt == VM_LEVEL_0_NPAGES ? 0 : -1);
910 }
911
912 /*
913 * Breaks the given partially-populated reservation, releasing its cached and
914 * free pages to the physical memory allocator.
915 *
916 * The free page queue lock must be held.
917 */
918 static void
vm_reserv_reclaim(vm_reserv_t rv)919 vm_reserv_reclaim(vm_reserv_t rv)
920 {
921
922 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
923 KASSERT(rv->inpartpopq,
924 ("vm_reserv_reclaim: reserv %p's inpartpopq is FALSE", rv));
925 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
926 rv->inpartpopq = FALSE;
927 vm_reserv_break(rv, NULL);
928 vm_reserv_reclaimed++;
929 }
930
931 /*
932 * Breaks the reservation at the head of the partially-populated reservation
933 * queue, releasing its cached and free pages to the physical memory
934 * allocator. Returns TRUE if a reservation is broken and FALSE otherwise.
935 *
936 * The free page queue lock must be held.
937 */
938 boolean_t
vm_reserv_reclaim_inactive(void)939 vm_reserv_reclaim_inactive(void)
940 {
941 vm_reserv_t rv;
942
943 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
944 if ((rv = TAILQ_FIRST(&vm_rvq_partpop)) != NULL) {
945 vm_reserv_reclaim(rv);
946 return (TRUE);
947 }
948 return (FALSE);
949 }
950
951 /*
952 * Searches the partially-populated reservation queue for the least recently
953 * active reservation with unused pages, i.e., cached or free, that satisfy the
954 * given request for contiguous physical memory. If a satisfactory reservation
955 * is found, it is broken. Returns TRUE if a reservation is broken and FALSE
956 * otherwise.
957 *
958 * The free page queue lock must be held.
959 */
960 boolean_t
vm_reserv_reclaim_contig(u_long npages,vm_paddr_t low,vm_paddr_t high,u_long alignment,vm_paddr_t boundary)961 vm_reserv_reclaim_contig(u_long npages, vm_paddr_t low, vm_paddr_t high,
962 u_long alignment, vm_paddr_t boundary)
963 {
964 vm_paddr_t pa, size;
965 vm_reserv_t rv;
966 int hi, i, lo, low_index, next_free;
967
968 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
969 if (npages > VM_LEVEL_0_NPAGES - 1)
970 return (FALSE);
971 size = npages << PAGE_SHIFT;
972 TAILQ_FOREACH(rv, &vm_rvq_partpop, partpopq) {
973 pa = VM_PAGE_TO_PHYS(&rv->pages[VM_LEVEL_0_NPAGES - 1]);
974 if (pa + PAGE_SIZE - size < low) {
975 /* This entire reservation is too low; go to next. */
976 continue;
977 }
978 pa = VM_PAGE_TO_PHYS(&rv->pages[0]);
979 if (pa + size > high) {
980 /* This entire reservation is too high; go to next. */
981 continue;
982 }
983 if (pa < low) {
984 /* Start the search for free pages at "low". */
985 low_index = (low + PAGE_MASK - pa) >> PAGE_SHIFT;
986 i = low_index / NBPOPMAP;
987 hi = low_index % NBPOPMAP;
988 } else
989 i = hi = 0;
990 do {
991 /* Find the next free page. */
992 lo = ffsl(~(((1UL << hi) - 1) | rv->popmap[i]));
993 while (lo == 0 && ++i < NPOPMAP)
994 lo = ffsl(~rv->popmap[i]);
995 if (i == NPOPMAP)
996 break;
997 /* Convert from ffsl() to ordinary bit numbering. */
998 lo--;
999 next_free = NBPOPMAP * i + lo;
1000 pa = VM_PAGE_TO_PHYS(&rv->pages[next_free]);
1001 KASSERT(pa >= low,
1002 ("vm_reserv_reclaim_contig: pa is too low"));
1003 if (pa + size > high) {
1004 /* The rest of this reservation is too high. */
1005 break;
1006 } else if ((pa & (alignment - 1)) != 0 ||
1007 ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) {
1008 /*
1009 * The current page doesn't meet the alignment
1010 * and/or boundary requirements. Continue
1011 * searching this reservation until the rest
1012 * of its free pages are either excluded or
1013 * exhausted.
1014 */
1015 hi = lo + 1;
1016 if (hi >= NBPOPMAP) {
1017 hi = 0;
1018 i++;
1019 }
1020 continue;
1021 }
1022 /* Find the next used page. */
1023 hi = ffsl(rv->popmap[i] & ~((1UL << lo) - 1));
1024 while (hi == 0 && ++i < NPOPMAP) {
1025 if ((NBPOPMAP * i - next_free) * PAGE_SIZE >=
1026 size) {
1027 vm_reserv_reclaim(rv);
1028 return (TRUE);
1029 }
1030 hi = ffsl(rv->popmap[i]);
1031 }
1032 /* Convert from ffsl() to ordinary bit numbering. */
1033 if (i != NPOPMAP)
1034 hi--;
1035 if ((NBPOPMAP * i + hi - next_free) * PAGE_SIZE >=
1036 size) {
1037 vm_reserv_reclaim(rv);
1038 return (TRUE);
1039 }
1040 } while (i < NPOPMAP);
1041 }
1042 return (FALSE);
1043 }
1044
1045 /*
1046 * Breaks the reservation holding the page as long as it is partially
1047 * populated.
1048 */
1049 boolean_t
vm_reserv_reclaim_page(vm_page_t m)1050 vm_reserv_reclaim_page(vm_page_t m)
1051 {
1052 mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
1053 vm_reserv_t rv;
1054
1055 rv = vm_reserv_from_page(m);
1056 if (rv->object == NULL || !rv->inpartpopq)
1057 return (FALSE);
1058 vm_reserv_reclaim(rv);
1059
1060 return (TRUE);
1061 }
1062
1063 /*
1064 * Transfers the reservation underlying the given page to a new object.
1065 *
1066 * The object must be locked.
1067 */
1068 void
vm_reserv_rename(vm_page_t m,vm_object_t new_object,vm_object_t old_object,vm_pindex_t old_object_offset)1069 vm_reserv_rename(vm_page_t m, vm_object_t new_object, vm_object_t old_object,
1070 vm_pindex_t old_object_offset)
1071 {
1072 vm_reserv_t rv;
1073
1074 VM_OBJECT_ASSERT_WLOCKED(new_object);
1075 rv = vm_reserv_from_page(m);
1076 if (rv->object == old_object) {
1077 mtx_lock(&vm_page_queue_free_mtx);
1078 if (rv->object == old_object) {
1079 LIST_REMOVE(rv, objq);
1080 LIST_INSERT_HEAD(&new_object->rvq, rv, objq);
1081 rv->object = new_object;
1082 rv->pindex -= old_object_offset;
1083 }
1084 mtx_unlock(&vm_page_queue_free_mtx);
1085 }
1086 }
1087
1088 /*
1089 * Returns the size (in bytes) of a reservation of the specified level.
1090 */
1091 int
vm_reserv_size(int level)1092 vm_reserv_size(int level)
1093 {
1094
1095 switch (level) {
1096 case 0:
1097 return (VM_LEVEL_0_SIZE);
1098 case -1:
1099 return (PAGE_SIZE);
1100 default:
1101 return (0);
1102 }
1103 }
1104
1105 /*
1106 * Allocates the virtual and physical memory required by the reservation
1107 * management system's data structures, in particular, the reservation array.
1108 */
1109 vm_paddr_t
vm_reserv_startup(vm_offset_t * vaddr,vm_paddr_t end,vm_paddr_t high_water)1110 vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end, vm_paddr_t high_water)
1111 {
1112 vm_paddr_t new_end;
1113 size_t size;
1114
1115 /*
1116 * Calculate the size (in bytes) of the reservation array. Round up
1117 * from "high_water" because every small page is mapped to an element
1118 * in the reservation array based on its physical address. Thus, the
1119 * number of elements in the reservation array can be greater than the
1120 * number of superpages.
1121 */
1122 size = howmany(high_water, VM_LEVEL_0_SIZE) * sizeof(struct vm_reserv);
1123
1124 /*
1125 * Allocate and map the physical memory for the reservation array. The
1126 * next available virtual address is returned by reference.
1127 */
1128 new_end = end - round_page(size);
1129 vm_reserv_array = (void *)(uintptr_t)pmap_map(vaddr, new_end, end,
1130 VM_PROT_READ | VM_PROT_WRITE);
1131 bzero(vm_reserv_array, size);
1132
1133 /*
1134 * Return the next available physical address.
1135 */
1136 return (new_end);
1137 }
1138
1139 #endif /* VM_NRESERVLEVEL > 0 */
1140