]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - sys/vm/vm_reserv.c
Merge ACPICA 20130517.
[FreeBSD/FreeBSD.git] / sys / vm / vm_reserv.c
1 /*-
2  * Copyright (c) 2002-2006 Rice University
3  * Copyright (c) 2007-2008 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 reservation structure
97  *
98  * A reservation structure is constructed whenever a large physical page is
99  * speculatively allocated to an object.  The reservation provides the small
100  * physical pages for the range [pindex, pindex + VM_LEVEL_0_NPAGES) of offsets
101  * within that object.  The reservation's "popcnt" tracks the number of these
102  * small physical pages that are in use at any given time.  When and if the
103  * reservation is not fully utilized, it appears in the queue of partially-
104  * populated reservations.  The reservation always appears on the containing
105  * object's list of reservations.
106  *
107  * A partially-populated reservation can be broken and reclaimed at any time.
108  */
109 struct vm_reserv {
110         TAILQ_ENTRY(vm_reserv) partpopq;
111         LIST_ENTRY(vm_reserv) objq;
112         vm_object_t     object;                 /* containing object */
113         vm_pindex_t     pindex;                 /* offset within object */
114         vm_page_t       pages;                  /* first page of a superpage */
115         int             popcnt;                 /* # of pages in use */
116         char            inpartpopq;
117 };
118
119 /*
120  * The reservation array
121  *
122  * This array is analoguous in function to vm_page_array.  It differs in the
123  * respect that it may contain a greater number of useful reservation
124  * structures than there are (physical) superpages.  These "invalid"
125  * reservation structures exist to trade-off space for time in the
126  * implementation of vm_reserv_from_page().  Invalid reservation structures are
127  * distinguishable from "valid" reservation structures by inspecting the
128  * reservation's "pages" field.  Invalid reservation structures have a NULL
129  * "pages" field.
130  *
131  * vm_reserv_from_page() maps a small (physical) page to an element of this
132  * array by computing a physical reservation number from the page's physical
133  * address.  The physical reservation number is used as the array index.
134  *
135  * An "active" reservation is a valid reservation structure that has a non-NULL
136  * "object" field and a non-zero "popcnt" field.  In other words, every active
137  * reservation belongs to a particular object.  Moreover, every active
138  * reservation has an entry in the containing object's list of reservations.  
139  */
140 static vm_reserv_t vm_reserv_array;
141
142 /*
143  * The partially-populated reservation queue
144  *
145  * This queue enables the fast recovery of an unused cached or free small page
146  * from a partially-populated reservation.  The reservation at the head of
147  * this queue is the least-recently-changed, partially-populated reservation.
148  *
149  * Access to this queue is synchronized by the free page queue lock.
150  */
151 static TAILQ_HEAD(, vm_reserv) vm_rvq_partpop =
152                             TAILQ_HEAD_INITIALIZER(vm_rvq_partpop);
153
154 static SYSCTL_NODE(_vm, OID_AUTO, reserv, CTLFLAG_RD, 0, "Reservation Info");
155
156 static long vm_reserv_broken;
157 SYSCTL_LONG(_vm_reserv, OID_AUTO, broken, CTLFLAG_RD,
158     &vm_reserv_broken, 0, "Cumulative number of broken reservations");
159
160 static long vm_reserv_freed;
161 SYSCTL_LONG(_vm_reserv, OID_AUTO, freed, CTLFLAG_RD,
162     &vm_reserv_freed, 0, "Cumulative number of freed reservations");
163
164 static int sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS);
165
166 SYSCTL_OID(_vm_reserv, OID_AUTO, partpopq, CTLTYPE_STRING | CTLFLAG_RD, NULL, 0,
167     sysctl_vm_reserv_partpopq, "A", "Partially-populated reservation queues");
168
169 static long vm_reserv_reclaimed;
170 SYSCTL_LONG(_vm_reserv, OID_AUTO, reclaimed, CTLFLAG_RD,
171     &vm_reserv_reclaimed, 0, "Cumulative number of reclaimed reservations");
172
173 static void             vm_reserv_depopulate(vm_reserv_t rv);
174 static vm_reserv_t      vm_reserv_from_page(vm_page_t m);
175 static boolean_t        vm_reserv_has_pindex(vm_reserv_t rv,
176                             vm_pindex_t pindex);
177 static void             vm_reserv_populate(vm_reserv_t rv);
178 static void             vm_reserv_reclaim(vm_reserv_t rv);
179
180 /*
181  * Describes the current state of the partially-populated reservation queue.
182  */
183 static int
184 sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS)
185 {
186         struct sbuf sbuf;
187         vm_reserv_t rv;
188         int counter, error, level, unused_pages;
189
190         error = sysctl_wire_old_buffer(req, 0);
191         if (error != 0)
192                 return (error);
193         sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
194         sbuf_printf(&sbuf, "\nLEVEL     SIZE  NUMBER\n\n");
195         for (level = -1; level <= VM_NRESERVLEVEL - 2; level++) {
196                 counter = 0;
197                 unused_pages = 0;
198                 mtx_lock(&vm_page_queue_free_mtx);
199                 TAILQ_FOREACH(rv, &vm_rvq_partpop/*[level]*/, partpopq) {
200                         counter++;
201                         unused_pages += VM_LEVEL_0_NPAGES - rv->popcnt;
202                 }
203                 mtx_unlock(&vm_page_queue_free_mtx);
204                 sbuf_printf(&sbuf, "%5d: %6dK, %6d\n", level,
205                     unused_pages * ((int)PAGE_SIZE / 1024), counter);
206         }
207         error = sbuf_finish(&sbuf);
208         sbuf_delete(&sbuf);
209         return (error);
210 }
211
212 /*
213  * Reduces the given reservation's population count.  If the population count
214  * becomes zero, the reservation is destroyed.  Additionally, moves the
215  * reservation to the tail of the partially-populated reservations queue if the
216  * population count is non-zero.
217  *
218  * The free page queue lock must be held.
219  */
220 static void
221 vm_reserv_depopulate(vm_reserv_t rv)
222 {
223
224         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
225         KASSERT(rv->object != NULL,
226             ("vm_reserv_depopulate: reserv %p is free", rv));
227         KASSERT(rv->popcnt > 0,
228             ("vm_reserv_depopulate: reserv %p's popcnt is corrupted", rv));
229         if (rv->inpartpopq) {
230                 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
231                 rv->inpartpopq = FALSE;
232         }
233         rv->popcnt--;
234         if (rv->popcnt == 0) {
235                 LIST_REMOVE(rv, objq);
236                 rv->object = NULL;
237                 vm_phys_free_pages(rv->pages, VM_LEVEL_0_ORDER);
238                 vm_reserv_freed++;
239         } else {
240                 rv->inpartpopq = TRUE;
241                 TAILQ_INSERT_TAIL(&vm_rvq_partpop, rv, partpopq);
242         }
243 }
244
245 /*
246  * Returns the reservation to which the given page might belong.
247  */
248 static __inline vm_reserv_t
249 vm_reserv_from_page(vm_page_t m)
250 {
251
252         return (&vm_reserv_array[VM_PAGE_TO_PHYS(m) >> VM_LEVEL_0_SHIFT]);
253 }
254
255 /*
256  * Returns TRUE if the given reservation contains the given page index and
257  * FALSE otherwise.
258  */
259 static __inline boolean_t
260 vm_reserv_has_pindex(vm_reserv_t rv, vm_pindex_t pindex)
261 {
262
263         return (((pindex - rv->pindex) & ~(VM_LEVEL_0_NPAGES - 1)) == 0);
264 }
265
266 /*
267  * Increases the given reservation's population count.  Moves the reservation
268  * to the tail of the partially-populated reservation queue.
269  *
270  * The free page queue must be locked.
271  */
272 static void
273 vm_reserv_populate(vm_reserv_t rv)
274 {
275
276         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
277         KASSERT(rv->object != NULL,
278             ("vm_reserv_populate: reserv %p is free", rv));
279         KASSERT(rv->popcnt < VM_LEVEL_0_NPAGES,
280             ("vm_reserv_populate: reserv %p is already full", rv));
281         if (rv->inpartpopq) {
282                 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
283                 rv->inpartpopq = FALSE;
284         }
285         rv->popcnt++;
286         if (rv->popcnt < VM_LEVEL_0_NPAGES) {
287                 rv->inpartpopq = TRUE;
288                 TAILQ_INSERT_TAIL(&vm_rvq_partpop, rv, partpopq);
289         }
290 }
291
292 /*
293  * Allocates a contiguous set of physical pages of the given size "npages"
294  * from an existing or newly-created reservation.  All of the physical pages
295  * must be at or above the given physical address "low" and below the given
296  * physical address "high".  The given value "alignment" determines the
297  * alignment of the first physical page in the set.  If the given value
298  * "boundary" is non-zero, then the set of physical pages cannot cross any
299  * physical address boundary that is a multiple of that value.  Both
300  * "alignment" and "boundary" must be a power of two.
301  *
302  * The object and free page queue must be locked.
303  */
304 vm_page_t
305 vm_reserv_alloc_contig(vm_object_t object, vm_pindex_t pindex, u_long npages,
306     vm_paddr_t low, vm_paddr_t high, u_long alignment, vm_paddr_t boundary)
307 {
308         vm_paddr_t pa, size;
309         vm_page_t m, m_ret, mpred, msucc;
310         vm_pindex_t first, leftcap, rightcap;
311         vm_reserv_t rv;
312         u_long allocpages, maxpages, minpages;
313         int i, index, n;
314
315         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
316         VM_OBJECT_ASSERT_WLOCKED(object);
317         KASSERT(npages != 0, ("vm_reserv_alloc_contig: npages is 0"));
318
319         /*
320          * Is a reservation fundamentally impossible?
321          */
322         if (pindex < VM_RESERV_INDEX(object, pindex) ||
323             pindex + npages > object->size)
324                 return (NULL);
325
326         /*
327          * All reservations of a particular size have the same alignment.
328          * Assuming that the first page is allocated from a reservation, the
329          * least significant bits of its physical address can be determined
330          * from its offset from the beginning of the reservation and the size
331          * of the reservation.
332          *
333          * Could the specified index within a reservation of the smallest
334          * possible size satisfy the alignment and boundary requirements?
335          */
336         pa = VM_RESERV_INDEX(object, pindex) << PAGE_SHIFT;
337         if ((pa & (alignment - 1)) != 0)
338                 return (NULL);
339         size = npages << PAGE_SHIFT;
340         if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0)
341                 return (NULL);
342
343         /*
344          * Look for an existing reservation.
345          */
346         mpred = vm_radix_lookup_le(&object->rtree, pindex);
347         if (mpred != NULL) {
348                 KASSERT(mpred->pindex < pindex,
349                     ("vm_reserv_alloc_contig: pindex already allocated"));
350                 rv = vm_reserv_from_page(mpred);
351                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
352                         goto found;
353                 msucc = TAILQ_NEXT(mpred, listq);
354         } else
355                 msucc = TAILQ_FIRST(&object->memq);
356         if (msucc != NULL) {
357                 KASSERT(msucc->pindex > pindex,
358                     ("vm_reserv_alloc_page: pindex already allocated"));
359                 rv = vm_reserv_from_page(msucc);
360                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
361                         goto found;
362         }
363
364         /*
365          * Could at least one reservation fit between the first index to the
366          * left that can be used and the first index to the right that cannot
367          * be used?
368          */
369         first = pindex - VM_RESERV_INDEX(object, pindex);
370         if (mpred != NULL) {
371                 if ((rv = vm_reserv_from_page(mpred))->object != object)
372                         leftcap = mpred->pindex + 1;
373                 else
374                         leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
375                 if (leftcap > first)
376                         return (NULL);
377         }
378         minpages = VM_RESERV_INDEX(object, pindex) + npages;
379         maxpages = roundup2(minpages, VM_LEVEL_0_NPAGES);
380         allocpages = maxpages;
381         if (msucc != NULL) {
382                 if ((rv = vm_reserv_from_page(msucc))->object != object)
383                         rightcap = msucc->pindex;
384                 else
385                         rightcap = rv->pindex;
386                 if (first + maxpages > rightcap) {
387                         if (maxpages == VM_LEVEL_0_NPAGES)
388                                 return (NULL);
389                         allocpages = minpages;
390                 }
391         }
392
393         /*
394          * Would the last new reservation extend past the end of the object?
395          */
396         if (first + maxpages > object->size) {
397                 /*
398                  * Don't allocate the last new reservation if the object is a
399                  * vnode or backed by another object that is a vnode. 
400                  */
401                 if (object->type == OBJT_VNODE ||
402                     (object->backing_object != NULL &&
403                     object->backing_object->type == OBJT_VNODE)) {
404                         if (maxpages == VM_LEVEL_0_NPAGES)
405                                 return (NULL);
406                         allocpages = minpages;
407                 }
408                 /* Speculate that the object may grow. */
409         }
410
411         /*
412          * Allocate and populate the new reservations.  The alignment and
413          * boundary specified for this allocation may be different from the
414          * alignment and boundary specified for the requested pages.  For
415          * instance, the specified index may not be the first page within the
416          * first new reservation.
417          */
418         m = vm_phys_alloc_contig(allocpages, low, high, ulmax(alignment,
419             VM_LEVEL_0_SIZE), boundary > VM_LEVEL_0_SIZE ? boundary : 0);
420         if (m == NULL)
421                 return (NULL);
422         m_ret = NULL;
423         index = VM_RESERV_INDEX(object, pindex);
424         do {
425                 rv = vm_reserv_from_page(m);
426                 KASSERT(rv->pages == m,
427                     ("vm_reserv_alloc_contig: reserv %p's pages is corrupted",
428                     rv));
429                 KASSERT(rv->object == NULL,
430                     ("vm_reserv_alloc_contig: reserv %p isn't free", rv));
431                 LIST_INSERT_HEAD(&object->rvq, rv, objq);
432                 rv->object = object;
433                 rv->pindex = first;
434                 KASSERT(rv->popcnt == 0,
435                     ("vm_reserv_alloc_contig: reserv %p's popcnt is corrupted",
436                     rv));
437                 KASSERT(!rv->inpartpopq,
438                     ("vm_reserv_alloc_contig: reserv %p's inpartpopq is TRUE",
439                     rv));
440                 n = ulmin(VM_LEVEL_0_NPAGES - index, npages);
441                 for (i = 0; i < n; i++)
442                         vm_reserv_populate(rv);
443                 npages -= n;
444                 if (m_ret == NULL) {
445                         m_ret = &rv->pages[index];
446                         index = 0;
447                 }
448                 m += VM_LEVEL_0_NPAGES;
449                 first += VM_LEVEL_0_NPAGES;
450                 allocpages -= VM_LEVEL_0_NPAGES;
451         } while (allocpages > 0);
452         return (m_ret);
453
454         /*
455          * Found a matching reservation.
456          */
457 found:
458         index = VM_RESERV_INDEX(object, pindex);
459         /* Does the allocation fit within the reservation? */
460         if (index + npages > VM_LEVEL_0_NPAGES)
461                 return (NULL);
462         m = &rv->pages[index];
463         pa = VM_PAGE_TO_PHYS(m);
464         if (pa < low || pa + size > high || (pa & (alignment - 1)) != 0 ||
465             ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0)
466                 return (NULL);
467         /* Handle vm_page_rename(m, new_object, ...). */
468         for (i = 0; i < npages; i++)
469                 if ((rv->pages[index + i].flags & (PG_CACHED | PG_FREE)) == 0)
470                         return (NULL);
471         for (i = 0; i < npages; i++)
472                 vm_reserv_populate(rv);
473         return (m);
474 }
475
476 /*
477  * Allocates a page from an existing or newly-created reservation.
478  *
479  * The page "mpred" must immediately precede the offset "pindex" within the
480  * specified object.
481  *
482  * The object and free page queue must be locked.
483  */
484 vm_page_t
485 vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex, vm_page_t mpred)
486 {
487         vm_page_t m, msucc;
488         vm_pindex_t first, leftcap, rightcap;
489         vm_reserv_t rv;
490
491         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
492         VM_OBJECT_ASSERT_WLOCKED(object);
493
494         /*
495          * Is a reservation fundamentally impossible?
496          */
497         if (pindex < VM_RESERV_INDEX(object, pindex) ||
498             pindex >= object->size)
499                 return (NULL);
500
501         /*
502          * Look for an existing reservation.
503          */
504         if (mpred != NULL) {
505                 KASSERT(mpred->object == object ||
506                     (mpred->flags & PG_SLAB) != 0,
507                     ("vm_reserv_alloc_page: object doesn't contain mpred"));
508                 KASSERT(mpred->pindex < pindex,
509                     ("vm_reserv_alloc_page: mpred doesn't precede pindex"));
510                 rv = vm_reserv_from_page(mpred);
511                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
512                         goto found;
513                 msucc = TAILQ_NEXT(mpred, listq);
514         } else
515                 msucc = TAILQ_FIRST(&object->memq);
516         if (msucc != NULL) {
517                 KASSERT(msucc->pindex > pindex,
518                     ("vm_reserv_alloc_page: msucc doesn't succeed pindex"));
519                 rv = vm_reserv_from_page(msucc);
520                 if (rv->object == object && vm_reserv_has_pindex(rv, pindex))
521                         goto found;
522         }
523
524         /*
525          * Could a reservation fit between the first index to the left that
526          * can be used and the first index to the right that cannot be used?
527          */
528         first = pindex - VM_RESERV_INDEX(object, pindex);
529         if (mpred != NULL) {
530                 if ((rv = vm_reserv_from_page(mpred))->object != object)
531                         leftcap = mpred->pindex + 1;
532                 else
533                         leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
534                 if (leftcap > first)
535                         return (NULL);
536         }
537         if (msucc != NULL) {
538                 if ((rv = vm_reserv_from_page(msucc))->object != object)
539                         rightcap = msucc->pindex;
540                 else
541                         rightcap = rv->pindex;
542                 if (first + VM_LEVEL_0_NPAGES > rightcap)
543                         return (NULL);
544         }
545
546         /*
547          * Would a new reservation extend past the end of the object? 
548          */
549         if (first + VM_LEVEL_0_NPAGES > object->size) {
550                 /*
551                  * Don't allocate a new reservation if the object is a vnode or
552                  * backed by another object that is a vnode. 
553                  */
554                 if (object->type == OBJT_VNODE ||
555                     (object->backing_object != NULL &&
556                     object->backing_object->type == OBJT_VNODE))
557                         return (NULL);
558                 /* Speculate that the object may grow. */
559         }
560
561         /*
562          * Allocate and populate the new reservation.
563          */
564         m = vm_phys_alloc_pages(VM_FREEPOOL_DEFAULT, VM_LEVEL_0_ORDER);
565         if (m == NULL)
566                 return (NULL);
567         rv = vm_reserv_from_page(m);
568         KASSERT(rv->pages == m,
569             ("vm_reserv_alloc_page: reserv %p's pages is corrupted", rv));
570         KASSERT(rv->object == NULL,
571             ("vm_reserv_alloc_page: reserv %p isn't free", rv));
572         LIST_INSERT_HEAD(&object->rvq, rv, objq);
573         rv->object = object;
574         rv->pindex = first;
575         KASSERT(rv->popcnt == 0,
576             ("vm_reserv_alloc_page: reserv %p's popcnt is corrupted", rv));
577         KASSERT(!rv->inpartpopq,
578             ("vm_reserv_alloc_page: reserv %p's inpartpopq is TRUE", rv));
579         vm_reserv_populate(rv);
580         return (&rv->pages[VM_RESERV_INDEX(object, pindex)]);
581
582         /*
583          * Found a matching reservation.
584          */
585 found:
586         m = &rv->pages[VM_RESERV_INDEX(object, pindex)];
587         /* Handle vm_page_rename(m, new_object, ...). */
588         if ((m->flags & (PG_CACHED | PG_FREE)) == 0)
589                 return (NULL);
590         vm_reserv_populate(rv);
591         return (m);
592 }
593
594 /*
595  * Breaks all reservations belonging to the given object.
596  */
597 void
598 vm_reserv_break_all(vm_object_t object)
599 {
600         vm_reserv_t rv;
601         int i;
602
603         mtx_lock(&vm_page_queue_free_mtx);
604         while ((rv = LIST_FIRST(&object->rvq)) != NULL) {
605                 KASSERT(rv->object == object,
606                     ("vm_reserv_break_all: reserv %p is corrupted", rv));
607                 if (rv->inpartpopq) {
608                         TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
609                         rv->inpartpopq = FALSE;
610                 }
611                 LIST_REMOVE(rv, objq);
612                 rv->object = NULL;
613                 for (i = 0; i < VM_LEVEL_0_NPAGES; i++) {
614                         if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0)
615                                 vm_phys_free_pages(&rv->pages[i], 0);
616                         else
617                                 rv->popcnt--;
618                 }
619                 KASSERT(rv->popcnt == 0,
620                     ("vm_reserv_break_all: reserv %p's popcnt is corrupted",
621                     rv));
622                 vm_reserv_broken++;
623         }
624         mtx_unlock(&vm_page_queue_free_mtx);
625 }
626
627 /*
628  * Frees the given page if it belongs to a reservation.  Returns TRUE if the
629  * page is freed and FALSE otherwise.
630  *
631  * The free page queue lock must be held.
632  */
633 boolean_t
634 vm_reserv_free_page(vm_page_t m)
635 {
636         vm_reserv_t rv;
637
638         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
639         rv = vm_reserv_from_page(m);
640         if (rv->object == NULL)
641                 return (FALSE);
642         if ((m->flags & PG_CACHED) != 0 && m->pool != VM_FREEPOOL_CACHE)
643                 vm_phys_set_pool(VM_FREEPOOL_CACHE, rv->pages,
644                     VM_LEVEL_0_ORDER);
645         vm_reserv_depopulate(rv);
646         return (TRUE);
647 }
648
649 /*
650  * Initializes the reservation management system.  Specifically, initializes
651  * the reservation array.
652  *
653  * Requires that vm_page_array and first_page are initialized!
654  */
655 void
656 vm_reserv_init(void)
657 {
658         vm_paddr_t paddr;
659         int i;
660
661         /*
662          * Initialize the reservation array.  Specifically, initialize the
663          * "pages" field for every element that has an underlying superpage.
664          */
665         for (i = 0; phys_avail[i + 1] != 0; i += 2) {
666                 paddr = roundup2(phys_avail[i], VM_LEVEL_0_SIZE);
667                 while (paddr + VM_LEVEL_0_SIZE <= phys_avail[i + 1]) {
668                         vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT].pages =
669                             PHYS_TO_VM_PAGE(paddr);
670                         paddr += VM_LEVEL_0_SIZE;
671                 }
672         }
673 }
674
675 /*
676  * Returns a reservation level if the given page belongs to a fully-populated
677  * reservation and -1 otherwise.
678  */
679 int
680 vm_reserv_level_iffullpop(vm_page_t m)
681 {
682         vm_reserv_t rv;
683
684         rv = vm_reserv_from_page(m);
685         return (rv->popcnt == VM_LEVEL_0_NPAGES ? 0 : -1);
686 }
687
688 /*
689  * Prepare for the reactivation of a cached page.
690  *
691  * First, suppose that the given page "m" was allocated individually, i.e., not
692  * as part of a reservation, and cached.  Then, suppose a reservation
693  * containing "m" is allocated by the same object.  Although "m" and the
694  * reservation belong to the same object, "m"'s pindex may not match the
695  * reservation's.
696  *
697  * The free page queue must be locked.
698  */
699 boolean_t
700 vm_reserv_reactivate_page(vm_page_t m)
701 {
702         vm_reserv_t rv;
703         int i, m_index;
704
705         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
706         rv = vm_reserv_from_page(m);
707         if (rv->object == NULL)
708                 return (FALSE);
709         KASSERT((m->flags & PG_CACHED) != 0,
710             ("vm_reserv_uncache_page: page %p is not cached", m));
711         if (m->object == rv->object &&
712             m->pindex - rv->pindex == VM_RESERV_INDEX(m->object, m->pindex))
713                 vm_reserv_populate(rv);
714         else {
715                 KASSERT(rv->inpartpopq,
716                     ("vm_reserv_uncache_page: reserv %p's inpartpopq is FALSE",
717                     rv));
718                 TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
719                 rv->inpartpopq = FALSE;
720                 LIST_REMOVE(rv, objq);
721                 rv->object = NULL;
722                 /* Don't vm_phys_free_pages(m, 0). */
723                 m_index = m - rv->pages;
724                 for (i = 0; i < m_index; i++) {
725                         if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0)
726                                 vm_phys_free_pages(&rv->pages[i], 0);
727                         else
728                                 rv->popcnt--;
729                 }
730                 for (i++; i < VM_LEVEL_0_NPAGES; i++) {
731                         if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0)
732                                 vm_phys_free_pages(&rv->pages[i], 0);
733                         else
734                                 rv->popcnt--;
735                 }
736                 KASSERT(rv->popcnt == 0,
737                     ("vm_reserv_uncache_page: reserv %p's popcnt is corrupted",
738                     rv));
739                 vm_reserv_broken++;
740         }
741         return (TRUE);
742 }
743
744 /*
745  * Breaks the given partially-populated reservation, releasing its cached and
746  * free pages to the physical memory allocator.
747  *
748  * The free page queue lock must be held.
749  */
750 static void
751 vm_reserv_reclaim(vm_reserv_t rv)
752 {
753         int i;
754
755         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
756         KASSERT(rv->inpartpopq,
757             ("vm_reserv_reclaim: reserv %p's inpartpopq is corrupted", rv));
758         TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
759         rv->inpartpopq = FALSE;
760         KASSERT(rv->object != NULL,
761             ("vm_reserv_reclaim: reserv %p is free", rv));
762         LIST_REMOVE(rv, objq);
763         rv->object = NULL;
764         for (i = 0; i < VM_LEVEL_0_NPAGES; i++) {
765                 if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0)
766                         vm_phys_free_pages(&rv->pages[i], 0);
767                 else
768                         rv->popcnt--;
769         }
770         KASSERT(rv->popcnt == 0,
771             ("vm_reserv_reclaim: reserv %p's popcnt is corrupted", rv));
772         vm_reserv_reclaimed++;
773 }
774
775 /*
776  * Breaks the reservation at the head of the partially-populated reservation
777  * queue, releasing its cached and free pages to the physical memory
778  * allocator.  Returns TRUE if a reservation is broken and FALSE otherwise.
779  *
780  * The free page queue lock must be held.
781  */
782 boolean_t
783 vm_reserv_reclaim_inactive(void)
784 {
785         vm_reserv_t rv;
786
787         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
788         if ((rv = TAILQ_FIRST(&vm_rvq_partpop)) != NULL) {
789                 vm_reserv_reclaim(rv);
790                 return (TRUE);
791         }
792         return (FALSE);
793 }
794
795 /*
796  * Searches the partially-populated reservation queue for the least recently
797  * active reservation with unused pages, i.e., cached or free, that satisfy the
798  * given request for contiguous physical memory.  If a satisfactory reservation
799  * is found, it is broken.  Returns TRUE if a reservation is broken and FALSE
800  * otherwise.
801  *
802  * The free page queue lock must be held.
803  */
804 boolean_t
805 vm_reserv_reclaim_contig(u_long npages, vm_paddr_t low, vm_paddr_t high,
806     u_long alignment, vm_paddr_t boundary)
807 {
808         vm_paddr_t pa, pa_length, size;
809         vm_reserv_t rv;
810         int i;
811
812         mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
813         if (npages > VM_LEVEL_0_NPAGES - 1)
814                 return (FALSE);
815         size = npages << PAGE_SHIFT;
816         TAILQ_FOREACH(rv, &vm_rvq_partpop, partpopq) {
817                 pa = VM_PAGE_TO_PHYS(&rv->pages[VM_LEVEL_0_NPAGES - 1]);
818                 if (pa + PAGE_SIZE - size < low) {
819                         /* this entire reservation is too low; go to next */
820                         continue;
821                 }
822                 pa_length = 0;
823                 for (i = 0; i < VM_LEVEL_0_NPAGES; i++)
824                         if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0) {
825                                 pa_length += PAGE_SIZE;
826                                 if (pa_length == PAGE_SIZE) {
827                                         pa = VM_PAGE_TO_PHYS(&rv->pages[i]);
828                                         if (pa + size > high) {
829                                                 /* skip to next reservation */
830                                                 break;
831                                         } else if (pa < low ||
832                                             (pa & (alignment - 1)) != 0 ||
833                                             ((pa ^ (pa + size - 1)) &
834                                             ~(boundary - 1)) != 0)
835                                                 pa_length = 0;
836                                 }
837                                 if (pa_length >= size) {
838                                         vm_reserv_reclaim(rv);
839                                         return (TRUE);
840                                 }
841                         } else
842                                 pa_length = 0;
843         }
844         return (FALSE);
845 }
846
847 /*
848  * Transfers the reservation underlying the given page to a new object.
849  *
850  * The object must be locked.
851  */
852 void
853 vm_reserv_rename(vm_page_t m, vm_object_t new_object, vm_object_t old_object,
854     vm_pindex_t old_object_offset)
855 {
856         vm_reserv_t rv;
857
858         VM_OBJECT_ASSERT_WLOCKED(new_object);
859         rv = vm_reserv_from_page(m);
860         if (rv->object == old_object) {
861                 mtx_lock(&vm_page_queue_free_mtx);
862                 if (rv->object == old_object) {
863                         LIST_REMOVE(rv, objq);
864                         LIST_INSERT_HEAD(&new_object->rvq, rv, objq);
865                         rv->object = new_object;
866                         rv->pindex -= old_object_offset;
867                 }
868                 mtx_unlock(&vm_page_queue_free_mtx);
869         }
870 }
871
872 /*
873  * Allocates the virtual and physical memory required by the reservation
874  * management system's data structures, in particular, the reservation array.
875  */
876 vm_paddr_t
877 vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end, vm_paddr_t high_water)
878 {
879         vm_paddr_t new_end;
880         size_t size;
881
882         /*
883          * Calculate the size (in bytes) of the reservation array.  Round up
884          * from "high_water" because every small page is mapped to an element
885          * in the reservation array based on its physical address.  Thus, the
886          * number of elements in the reservation array can be greater than the
887          * number of superpages. 
888          */
889         size = howmany(high_water, VM_LEVEL_0_SIZE) * sizeof(struct vm_reserv);
890
891         /*
892          * Allocate and map the physical memory for the reservation array.  The
893          * next available virtual address is returned by reference.
894          */
895         new_end = end - round_page(size);
896         vm_reserv_array = (void *)(uintptr_t)pmap_map(vaddr, new_end, end,
897             VM_PROT_READ | VM_PROT_WRITE);
898         bzero(vm_reserv_array, size);
899
900         /*
901          * Return the next available physical address.
902          */
903         return (new_end);
904 }
905
906 #endif  /* VM_NRESERVLEVEL > 0 */