xref: /freebsd/sys/vm/vm_reserv.c (revision f8a47341feed1a067229652b1ca2591e1e0223b6)
1f8a47341SAlan Cox /*-
2f8a47341SAlan Cox  * Copyright (c) 2002-2006 Rice University
3f8a47341SAlan Cox  * Copyright (c) 2007 Alan L. Cox <alc@cs.rice.edu>
4f8a47341SAlan Cox  * All rights reserved.
5f8a47341SAlan Cox  *
6f8a47341SAlan Cox  * This software was developed for the FreeBSD Project by Alan L. Cox,
7f8a47341SAlan Cox  * Olivier Crameri, Peter Druschel, Sitaram Iyer, and Juan Navarro.
8f8a47341SAlan Cox  *
9f8a47341SAlan Cox  * Redistribution and use in source and binary forms, with or without
10f8a47341SAlan Cox  * modification, are permitted provided that the following conditions
11f8a47341SAlan Cox  * are met:
12f8a47341SAlan Cox  * 1. Redistributions of source code must retain the above copyright
13f8a47341SAlan Cox  *    notice, this list of conditions and the following disclaimer.
14f8a47341SAlan Cox  * 2. Redistributions in binary form must reproduce the above copyright
15f8a47341SAlan Cox  *    notice, this list of conditions and the following disclaimer in the
16f8a47341SAlan Cox  *    documentation and/or other materials provided with the distribution.
17f8a47341SAlan Cox  *
18f8a47341SAlan Cox  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19f8a47341SAlan Cox  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20f8a47341SAlan Cox  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21f8a47341SAlan Cox  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
22f8a47341SAlan Cox  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
23f8a47341SAlan Cox  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
24f8a47341SAlan Cox  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
25f8a47341SAlan Cox  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
26f8a47341SAlan Cox  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27f8a47341SAlan Cox  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
28f8a47341SAlan Cox  * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29f8a47341SAlan Cox  * POSSIBILITY OF SUCH DAMAGE.
30f8a47341SAlan Cox  */
31f8a47341SAlan Cox 
32f8a47341SAlan Cox /*
33f8a47341SAlan Cox  *	Superpage reservation management module
34f8a47341SAlan Cox  */
35f8a47341SAlan Cox 
36f8a47341SAlan Cox #include <sys/cdefs.h>
37f8a47341SAlan Cox __FBSDID("$FreeBSD$");
38f8a47341SAlan Cox 
39f8a47341SAlan Cox #include "opt_vm.h"
40f8a47341SAlan Cox 
41f8a47341SAlan Cox #include <sys/param.h>
42f8a47341SAlan Cox #include <sys/kernel.h>
43f8a47341SAlan Cox #include <sys/lock.h>
44f8a47341SAlan Cox #include <sys/malloc.h>
45f8a47341SAlan Cox #include <sys/mutex.h>
46f8a47341SAlan Cox #include <sys/queue.h>
47f8a47341SAlan Cox #include <sys/sbuf.h>
48f8a47341SAlan Cox #include <sys/sysctl.h>
49f8a47341SAlan Cox #include <sys/systm.h>
50f8a47341SAlan Cox 
51f8a47341SAlan Cox #include <vm/vm.h>
52f8a47341SAlan Cox #include <vm/vm_param.h>
53f8a47341SAlan Cox #include <vm/vm_object.h>
54f8a47341SAlan Cox #include <vm/vm_page.h>
55f8a47341SAlan Cox #include <vm/vm_phys.h>
56f8a47341SAlan Cox #include <vm/vm_reserv.h>
57f8a47341SAlan Cox 
58f8a47341SAlan Cox /*
59f8a47341SAlan Cox  * The reservation system supports the speculative allocation of large physical
60f8a47341SAlan Cox  * pages ("superpages").  Speculative allocation enables the fully-automatic
61f8a47341SAlan Cox  * utilization of superpages by the virtual memory system.  In other words, no
62f8a47341SAlan Cox  * programmatic directives are required to use superpages.
63f8a47341SAlan Cox  */
64f8a47341SAlan Cox 
65f8a47341SAlan Cox #if VM_NRESERVLEVEL > 0
66f8a47341SAlan Cox 
67f8a47341SAlan Cox /*
68f8a47341SAlan Cox  * The number of small pages that are contained in a level 0 reservation
69f8a47341SAlan Cox  */
70f8a47341SAlan Cox #define	VM_LEVEL_0_NPAGES	(1 << VM_LEVEL_0_ORDER)
71f8a47341SAlan Cox 
72f8a47341SAlan Cox /*
73f8a47341SAlan Cox  * The number of bits by which a physical address is shifted to obtain the
74f8a47341SAlan Cox  * reservation number
75f8a47341SAlan Cox  */
76f8a47341SAlan Cox #define	VM_LEVEL_0_SHIFT	(VM_LEVEL_0_ORDER + PAGE_SHIFT)
77f8a47341SAlan Cox 
78f8a47341SAlan Cox /*
79f8a47341SAlan Cox  * The size of a level 0 reservation in bytes
80f8a47341SAlan Cox  */
81f8a47341SAlan Cox #define	VM_LEVEL_0_SIZE		(1 << VM_LEVEL_0_SHIFT)
82f8a47341SAlan Cox 
83f8a47341SAlan Cox /*
84f8a47341SAlan Cox  * Computes the index of the small page underlying the given (object, pindex)
85f8a47341SAlan Cox  * within the reservation's array of small pages.
86f8a47341SAlan Cox  */
87f8a47341SAlan Cox #define	VM_RESERV_INDEX(object, pindex)	\
88f8a47341SAlan Cox     (((object)->pg_color + (pindex)) & (VM_LEVEL_0_NPAGES - 1))
89f8a47341SAlan Cox 
90f8a47341SAlan Cox /*
91f8a47341SAlan Cox  * The reservation structure
92f8a47341SAlan Cox  *
93f8a47341SAlan Cox  * A reservation structure is constructed whenever a large physical page is
94f8a47341SAlan Cox  * speculatively allocated to an object.  The reservation provides the small
95f8a47341SAlan Cox  * physical pages for the range [pindex, pindex + VM_LEVEL_0_NPAGES) of offsets
96f8a47341SAlan Cox  * within that object.  The reservation's "popcnt" tracks the number of these
97f8a47341SAlan Cox  * small physical pages that are in use at any given time.  When and if the
98f8a47341SAlan Cox  * reservation is not fully utilized, it appears in the queue of partially-
99f8a47341SAlan Cox  * populated reservations.  The reservation always appears on the containing
100f8a47341SAlan Cox  * object's list of reservations.
101f8a47341SAlan Cox  *
102f8a47341SAlan Cox  * A partially-populated reservation can be broken and reclaimed at any time.
103f8a47341SAlan Cox  */
104f8a47341SAlan Cox struct vm_reserv {
105f8a47341SAlan Cox 	TAILQ_ENTRY(vm_reserv) partpopq;
106f8a47341SAlan Cox 	LIST_ENTRY(vm_reserv) objq;
107f8a47341SAlan Cox 	vm_object_t	object;			/* containing object */
108f8a47341SAlan Cox 	vm_pindex_t	pindex;			/* offset within object */
109f8a47341SAlan Cox 	vm_page_t	pages;			/* first page of a superpage */
110f8a47341SAlan Cox 	int		popcnt;			/* # of pages in use */
111f8a47341SAlan Cox 	char		inpartpopq;
112f8a47341SAlan Cox };
113f8a47341SAlan Cox 
114f8a47341SAlan Cox /*
115f8a47341SAlan Cox  * The reservation array
116f8a47341SAlan Cox  *
117f8a47341SAlan Cox  * This array is analoguous in function to vm_page_array.  It differs in the
118f8a47341SAlan Cox  * respect that it may contain a greater number of useful reservation
119f8a47341SAlan Cox  * structures than there are (physical) superpages.  These "invalid"
120f8a47341SAlan Cox  * reservation structures exist to trade-off space for time in the
121f8a47341SAlan Cox  * implementation of vm_reserv_from_page().  Invalid reservation structures are
122f8a47341SAlan Cox  * distinguishable from "valid" reservation structures by inspecting the
123f8a47341SAlan Cox  * reservation's "pages" field.  Invalid reservation structures have a NULL
124f8a47341SAlan Cox  * "pages" field.
125f8a47341SAlan Cox  *
126f8a47341SAlan Cox  * vm_reserv_from_page() maps a small (physical) page to an element of this
127f8a47341SAlan Cox  * array by computing a physical reservation number from the page's physical
128f8a47341SAlan Cox  * address.  The physical reservation number is used as the array index.
129f8a47341SAlan Cox  *
130f8a47341SAlan Cox  * An "active" reservation is a valid reservation structure that has a non-NULL
131f8a47341SAlan Cox  * "object" field and a non-zero "popcnt" field.  In other words, every active
132f8a47341SAlan Cox  * reservation belongs to a particular object.  Moreover, every active
133f8a47341SAlan Cox  * reservation has an entry in the containing object's list of reservations.
134f8a47341SAlan Cox  */
135f8a47341SAlan Cox static vm_reserv_t vm_reserv_array;
136f8a47341SAlan Cox 
137f8a47341SAlan Cox /*
138f8a47341SAlan Cox  * The partially-populated reservation queue
139f8a47341SAlan Cox  *
140f8a47341SAlan Cox  * This queue enables the fast recovery of an unused cached or free small page
141f8a47341SAlan Cox  * from a partially-populated reservation.  The head of this queue is either
142f8a47341SAlan Cox  * the least-recently-populated or most-recently-depopulated reservation.
143f8a47341SAlan Cox  *
144f8a47341SAlan Cox  * Access to this queue is synchronized by the free page queue lock.
145f8a47341SAlan Cox  */
146f8a47341SAlan Cox static TAILQ_HEAD(, vm_reserv) vm_rvq_partpop =
147f8a47341SAlan Cox 			    TAILQ_HEAD_INITIALIZER(vm_rvq_partpop);
148f8a47341SAlan Cox 
149f8a47341SAlan Cox static SYSCTL_NODE(_vm, OID_AUTO, reserv, CTLFLAG_RD, 0, "Reservation Info");
150f8a47341SAlan Cox 
151f8a47341SAlan Cox static long vm_reserv_broken;
152f8a47341SAlan Cox SYSCTL_LONG(_vm_reserv, OID_AUTO, broken, CTLFLAG_RD,
153f8a47341SAlan Cox     &vm_reserv_broken, 0, "Cumulative number of broken reservations");
154f8a47341SAlan Cox 
155f8a47341SAlan Cox static long vm_reserv_freed;
156f8a47341SAlan Cox SYSCTL_LONG(_vm_reserv, OID_AUTO, freed, CTLFLAG_RD,
157f8a47341SAlan Cox     &vm_reserv_freed, 0, "Cumulative number of freed reservations");
158f8a47341SAlan Cox 
159f8a47341SAlan Cox static int sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS);
160f8a47341SAlan Cox 
161f8a47341SAlan Cox SYSCTL_OID(_vm_reserv, OID_AUTO, partpopq, CTLTYPE_STRING | CTLFLAG_RD, NULL, 0,
162f8a47341SAlan Cox     sysctl_vm_reserv_partpopq, "A", "Partially-populated reservation queues");
163f8a47341SAlan Cox 
164f8a47341SAlan Cox static long vm_reserv_reclaimed;
165f8a47341SAlan Cox SYSCTL_LONG(_vm_reserv, OID_AUTO, reclaimed, CTLFLAG_RD,
166f8a47341SAlan Cox     &vm_reserv_reclaimed, 0, "Cumulative number of reclaimed reservations");
167f8a47341SAlan Cox 
168f8a47341SAlan Cox static void		vm_reserv_depopulate(vm_reserv_t rv);
169f8a47341SAlan Cox static vm_reserv_t	vm_reserv_from_page(vm_page_t m);
170f8a47341SAlan Cox static boolean_t	vm_reserv_has_pindex(vm_reserv_t rv,
171f8a47341SAlan Cox 			    vm_pindex_t pindex);
172f8a47341SAlan Cox static void		vm_reserv_populate(vm_reserv_t rv);
173f8a47341SAlan Cox 
174f8a47341SAlan Cox /*
175f8a47341SAlan Cox  * Describes the current state of the partially-populated reservation queue.
176f8a47341SAlan Cox  */
177f8a47341SAlan Cox static int
178f8a47341SAlan Cox sysctl_vm_reserv_partpopq(SYSCTL_HANDLER_ARGS)
179f8a47341SAlan Cox {
180f8a47341SAlan Cox 	struct sbuf sbuf;
181f8a47341SAlan Cox 	vm_reserv_t rv;
182f8a47341SAlan Cox 	char *cbuf;
183f8a47341SAlan Cox 	const int cbufsize = (VM_NRESERVLEVEL + 1) * 81;
184f8a47341SAlan Cox 	int counter, error, level, unused_pages;
185f8a47341SAlan Cox 
186f8a47341SAlan Cox 	cbuf = malloc(cbufsize, M_TEMP, M_WAITOK | M_ZERO);
187f8a47341SAlan Cox 	sbuf_new(&sbuf, cbuf, cbufsize, SBUF_FIXEDLEN);
188f8a47341SAlan Cox 	sbuf_printf(&sbuf, "\nLEVEL     SIZE  NUMBER\n\n");
189f8a47341SAlan Cox 	for (level = -1; level <= VM_NRESERVLEVEL - 2; level++) {
190f8a47341SAlan Cox 		counter = 0;
191f8a47341SAlan Cox 		unused_pages = 0;
192f8a47341SAlan Cox 		mtx_lock(&vm_page_queue_free_mtx);
193f8a47341SAlan Cox 		TAILQ_FOREACH(rv, &vm_rvq_partpop/*[level]*/, partpopq) {
194f8a47341SAlan Cox 			counter++;
195f8a47341SAlan Cox 			unused_pages += VM_LEVEL_0_NPAGES - rv->popcnt;
196f8a47341SAlan Cox 		}
197f8a47341SAlan Cox 		mtx_unlock(&vm_page_queue_free_mtx);
198f8a47341SAlan Cox 		sbuf_printf(&sbuf, "%5.5d: %6.6dK, %6.6d\n", level,
199f8a47341SAlan Cox 		    unused_pages * (PAGE_SIZE / 1024), counter);
200f8a47341SAlan Cox 	}
201f8a47341SAlan Cox 	sbuf_finish(&sbuf);
202f8a47341SAlan Cox 	error = SYSCTL_OUT(req, sbuf_data(&sbuf), sbuf_len(&sbuf));
203f8a47341SAlan Cox 	sbuf_delete(&sbuf);
204f8a47341SAlan Cox 	free(cbuf, M_TEMP);
205f8a47341SAlan Cox 	return (error);
206f8a47341SAlan Cox }
207f8a47341SAlan Cox 
208f8a47341SAlan Cox /*
209f8a47341SAlan Cox  * Reduces the given reservation's population count.  If the population count
210f8a47341SAlan Cox  * becomes zero, the reservation is destroyed.  Additionally, moves the
211f8a47341SAlan Cox  * reservation to the head of the partially-populated reservations queue if the
212f8a47341SAlan Cox  * population count is non-zero.
213f8a47341SAlan Cox  *
214f8a47341SAlan Cox  * The free page queue lock must be held.
215f8a47341SAlan Cox  */
216f8a47341SAlan Cox static void
217f8a47341SAlan Cox vm_reserv_depopulate(vm_reserv_t rv)
218f8a47341SAlan Cox {
219f8a47341SAlan Cox 
220f8a47341SAlan Cox 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
221f8a47341SAlan Cox 	KASSERT(rv->object != NULL,
222f8a47341SAlan Cox 	    ("vm_reserv_depopulate: reserv %p is free", rv));
223f8a47341SAlan Cox 	KASSERT(rv->popcnt > 0,
224f8a47341SAlan Cox 	    ("vm_reserv_depopulate: reserv %p's popcnt is corrupted", rv));
225f8a47341SAlan Cox 	if (rv->inpartpopq) {
226f8a47341SAlan Cox 		TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
227f8a47341SAlan Cox 		rv->inpartpopq = FALSE;
228f8a47341SAlan Cox 	}
229f8a47341SAlan Cox 	rv->popcnt--;
230f8a47341SAlan Cox 	if (rv->popcnt == 0) {
231f8a47341SAlan Cox 		LIST_REMOVE(rv, objq);
232f8a47341SAlan Cox 		rv->object = NULL;
233f8a47341SAlan Cox 		vm_phys_free_pages(rv->pages, VM_LEVEL_0_ORDER);
234f8a47341SAlan Cox 		vm_reserv_freed++;
235f8a47341SAlan Cox 	} else {
236f8a47341SAlan Cox 		rv->inpartpopq = TRUE;
237f8a47341SAlan Cox 		TAILQ_INSERT_HEAD(&vm_rvq_partpop, rv, partpopq);
238f8a47341SAlan Cox 	}
239f8a47341SAlan Cox }
240f8a47341SAlan Cox 
241f8a47341SAlan Cox /*
242f8a47341SAlan Cox  * Returns the reservation to which the given page might belong.
243f8a47341SAlan Cox  */
244f8a47341SAlan Cox static __inline vm_reserv_t
245f8a47341SAlan Cox vm_reserv_from_page(vm_page_t m)
246f8a47341SAlan Cox {
247f8a47341SAlan Cox 
248f8a47341SAlan Cox 	return (&vm_reserv_array[VM_PAGE_TO_PHYS(m) >> VM_LEVEL_0_SHIFT]);
249f8a47341SAlan Cox }
250f8a47341SAlan Cox 
251f8a47341SAlan Cox /*
252f8a47341SAlan Cox  * Returns TRUE if the given reservation contains the given page index and
253f8a47341SAlan Cox  * FALSE otherwise.
254f8a47341SAlan Cox  */
255f8a47341SAlan Cox static __inline boolean_t
256f8a47341SAlan Cox vm_reserv_has_pindex(vm_reserv_t rv, vm_pindex_t pindex)
257f8a47341SAlan Cox {
258f8a47341SAlan Cox 
259f8a47341SAlan Cox 	return (((pindex - rv->pindex) & ~(VM_LEVEL_0_NPAGES - 1)) == 0);
260f8a47341SAlan Cox }
261f8a47341SAlan Cox 
262f8a47341SAlan Cox /*
263f8a47341SAlan Cox  * Increases the given reservation's population count.  Moves the reservation
264f8a47341SAlan Cox  * to the tail of the partially-populated reservation queue.
265f8a47341SAlan Cox  *
266f8a47341SAlan Cox  * The free page queue must be locked.
267f8a47341SAlan Cox  */
268f8a47341SAlan Cox static void
269f8a47341SAlan Cox vm_reserv_populate(vm_reserv_t rv)
270f8a47341SAlan Cox {
271f8a47341SAlan Cox 
272f8a47341SAlan Cox 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
273f8a47341SAlan Cox 	KASSERT(rv->object != NULL,
274f8a47341SAlan Cox 	    ("vm_reserv_populate: reserv %p is free", rv));
275f8a47341SAlan Cox 	KASSERT(rv->popcnt < VM_LEVEL_0_NPAGES,
276f8a47341SAlan Cox 	    ("vm_reserv_populate: reserv %p is already full", rv));
277f8a47341SAlan Cox 	if (rv->inpartpopq) {
278f8a47341SAlan Cox 		TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
279f8a47341SAlan Cox 		rv->inpartpopq = FALSE;
280f8a47341SAlan Cox 	}
281f8a47341SAlan Cox 	rv->popcnt++;
282f8a47341SAlan Cox 	if (rv->popcnt < VM_LEVEL_0_NPAGES) {
283f8a47341SAlan Cox 		rv->inpartpopq = TRUE;
284f8a47341SAlan Cox 		TAILQ_INSERT_TAIL(&vm_rvq_partpop, rv, partpopq);
285f8a47341SAlan Cox 	}
286f8a47341SAlan Cox }
287f8a47341SAlan Cox 
288f8a47341SAlan Cox /*
289f8a47341SAlan Cox  * Allocates a page from an existing or newly-created reservation.
290f8a47341SAlan Cox  *
291f8a47341SAlan Cox  * The object and free page queue must be locked.
292f8a47341SAlan Cox  */
293f8a47341SAlan Cox vm_page_t
294f8a47341SAlan Cox vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex)
295f8a47341SAlan Cox {
296f8a47341SAlan Cox 	vm_page_t m, mpred, msucc;
297f8a47341SAlan Cox 	vm_pindex_t first, leftcap, rightcap;
298f8a47341SAlan Cox 	vm_reserv_t rv;
299f8a47341SAlan Cox 
300f8a47341SAlan Cox 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
301f8a47341SAlan Cox 
302f8a47341SAlan Cox 	/*
303f8a47341SAlan Cox 	 * Is a reservation fundamentally not possible?
304f8a47341SAlan Cox 	 */
305f8a47341SAlan Cox 	VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
306f8a47341SAlan Cox 	if (pindex < VM_RESERV_INDEX(object, pindex) ||
307f8a47341SAlan Cox 	    pindex >= object->size)
308f8a47341SAlan Cox 		return (NULL);
309f8a47341SAlan Cox 
310f8a47341SAlan Cox 	/*
311f8a47341SAlan Cox 	 * Look for an existing reservation.
312f8a47341SAlan Cox 	 */
313f8a47341SAlan Cox 	msucc = NULL;
314f8a47341SAlan Cox 	mpred = object->root;
315f8a47341SAlan Cox 	while (mpred != NULL) {
316f8a47341SAlan Cox 		KASSERT(mpred->pindex != pindex,
317f8a47341SAlan Cox 		    ("vm_reserv_alloc_page: pindex already allocated"));
318f8a47341SAlan Cox 		rv = vm_reserv_from_page(mpred);
319f8a47341SAlan Cox 		if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) {
320f8a47341SAlan Cox 			m = &rv->pages[VM_RESERV_INDEX(object, pindex)];
321f8a47341SAlan Cox 			/* Handle vm_page_rename(m, new_object, ...). */
322f8a47341SAlan Cox 			if ((m->flags & (PG_CACHED | PG_FREE)) == 0)
323f8a47341SAlan Cox 				return (NULL);
324f8a47341SAlan Cox 			vm_reserv_populate(rv);
325f8a47341SAlan Cox 			return (m);
326f8a47341SAlan Cox 		} else if (mpred->pindex < pindex) {
327f8a47341SAlan Cox 			if (msucc != NULL ||
328f8a47341SAlan Cox 			    (msucc = TAILQ_NEXT(mpred, listq)) == NULL)
329f8a47341SAlan Cox 				break;
330f8a47341SAlan Cox 			KASSERT(msucc->pindex != pindex,
331f8a47341SAlan Cox 			    ("vm_reserv_alloc_page: pindex already allocated"));
332f8a47341SAlan Cox 			rv = vm_reserv_from_page(msucc);
333f8a47341SAlan Cox 			if (rv->object == object &&
334f8a47341SAlan Cox 			    vm_reserv_has_pindex(rv, pindex)) {
335f8a47341SAlan Cox 				m = &rv->pages[VM_RESERV_INDEX(object, pindex)];
336f8a47341SAlan Cox 				/* Handle vm_page_rename(m, new_object, ...). */
337f8a47341SAlan Cox 				if ((m->flags & (PG_CACHED | PG_FREE)) == 0)
338f8a47341SAlan Cox 					return (NULL);
339f8a47341SAlan Cox 				vm_reserv_populate(rv);
340f8a47341SAlan Cox 				return (m);
341f8a47341SAlan Cox 			} else if (pindex < msucc->pindex)
342f8a47341SAlan Cox 				break;
343f8a47341SAlan Cox 		} else if (msucc == NULL) {
344f8a47341SAlan Cox 			msucc = mpred;
345f8a47341SAlan Cox 			mpred = TAILQ_PREV(msucc, pglist, listq);
346f8a47341SAlan Cox 			continue;
347f8a47341SAlan Cox 		}
348f8a47341SAlan Cox 		msucc = NULL;
349f8a47341SAlan Cox 		mpred = object->root = vm_page_splay(pindex, object->root);
350f8a47341SAlan Cox 	}
351f8a47341SAlan Cox 
352f8a47341SAlan Cox 	/*
353f8a47341SAlan Cox 	 * Determine the first index to the left that can be used.
354f8a47341SAlan Cox 	 */
355f8a47341SAlan Cox 	if (mpred == NULL)
356f8a47341SAlan Cox 		leftcap = 0;
357f8a47341SAlan Cox 	else if ((rv = vm_reserv_from_page(mpred))->object != object)
358f8a47341SAlan Cox 		leftcap = mpred->pindex + 1;
359f8a47341SAlan Cox 	else
360f8a47341SAlan Cox 		leftcap = rv->pindex + VM_LEVEL_0_NPAGES;
361f8a47341SAlan Cox 
362f8a47341SAlan Cox 	/*
363f8a47341SAlan Cox 	 * Determine the first index to the right that cannot be used.
364f8a47341SAlan Cox 	 */
365f8a47341SAlan Cox 	if (msucc == NULL)
366f8a47341SAlan Cox 		rightcap = pindex + VM_LEVEL_0_NPAGES;
367f8a47341SAlan Cox 	else if ((rv = vm_reserv_from_page(msucc))->object != object)
368f8a47341SAlan Cox 		rightcap = msucc->pindex;
369f8a47341SAlan Cox 	else
370f8a47341SAlan Cox 		rightcap = rv->pindex;
371f8a47341SAlan Cox 
372f8a47341SAlan Cox 	/*
373f8a47341SAlan Cox 	 * Determine if a reservation fits between the first index to
374f8a47341SAlan Cox 	 * the left that can be used and the first index to the right
375f8a47341SAlan Cox 	 * that cannot be used.
376f8a47341SAlan Cox 	 */
377f8a47341SAlan Cox 	first = pindex - VM_RESERV_INDEX(object, pindex);
378f8a47341SAlan Cox 	if (first < leftcap || first + VM_LEVEL_0_NPAGES > rightcap)
379f8a47341SAlan Cox 		return (NULL);
380f8a47341SAlan Cox 
381f8a47341SAlan Cox 	/*
382f8a47341SAlan Cox 	 * Would a new reservation extend past the end of the given object?
383f8a47341SAlan Cox 	 */
384f8a47341SAlan Cox 	if (object->size < first + VM_LEVEL_0_NPAGES) {
385f8a47341SAlan Cox 		/*
386f8a47341SAlan Cox 		 * Don't allocate a new reservation if the object is a vnode or
387f8a47341SAlan Cox 		 * backed by another object that is a vnode.
388f8a47341SAlan Cox 		 */
389f8a47341SAlan Cox 		if (object->type == OBJT_VNODE ||
390f8a47341SAlan Cox 		    (object->backing_object != NULL &&
391f8a47341SAlan Cox 		    object->backing_object->type == OBJT_VNODE))
392f8a47341SAlan Cox 			return (NULL);
393f8a47341SAlan Cox 		/* Speculate that the object may grow. */
394f8a47341SAlan Cox 	}
395f8a47341SAlan Cox 
396f8a47341SAlan Cox 	/*
397f8a47341SAlan Cox 	 * Allocate a new reservation.
398f8a47341SAlan Cox 	 */
399f8a47341SAlan Cox 	m = vm_phys_alloc_pages(VM_FREEPOOL_DEFAULT, VM_LEVEL_0_ORDER);
400f8a47341SAlan Cox 	if (m != NULL) {
401f8a47341SAlan Cox 		rv = vm_reserv_from_page(m);
402f8a47341SAlan Cox 		KASSERT(rv->pages == m,
403f8a47341SAlan Cox 		    ("vm_reserv_alloc_page: reserv %p's pages is corrupted",
404f8a47341SAlan Cox 		    rv));
405f8a47341SAlan Cox 		KASSERT(rv->object == NULL,
406f8a47341SAlan Cox 		    ("vm_reserv_alloc_page: reserv %p isn't free", rv));
407f8a47341SAlan Cox 		LIST_INSERT_HEAD(&object->rvq, rv, objq);
408f8a47341SAlan Cox 		rv->object = object;
409f8a47341SAlan Cox 		rv->pindex = first;
410f8a47341SAlan Cox 		KASSERT(rv->popcnt == 0,
411f8a47341SAlan Cox 		    ("vm_reserv_alloc_page: reserv %p's popcnt is corrupted",
412f8a47341SAlan Cox 		    rv));
413f8a47341SAlan Cox 		KASSERT(!rv->inpartpopq,
414f8a47341SAlan Cox 		    ("vm_reserv_alloc_page: reserv %p's inpartpopq is TRUE",
415f8a47341SAlan Cox 		    rv));
416f8a47341SAlan Cox 		vm_reserv_populate(rv);
417f8a47341SAlan Cox 		m = &rv->pages[VM_RESERV_INDEX(object, pindex)];
418f8a47341SAlan Cox 	}
419f8a47341SAlan Cox 	return (m);
420f8a47341SAlan Cox }
421f8a47341SAlan Cox 
422f8a47341SAlan Cox /*
423f8a47341SAlan Cox  * Breaks all reservations belonging to the given object.
424f8a47341SAlan Cox  */
425f8a47341SAlan Cox void
426f8a47341SAlan Cox vm_reserv_break_all(vm_object_t object)
427f8a47341SAlan Cox {
428f8a47341SAlan Cox 	vm_reserv_t rv;
429f8a47341SAlan Cox 	int i;
430f8a47341SAlan Cox 
431f8a47341SAlan Cox 	mtx_lock(&vm_page_queue_free_mtx);
432f8a47341SAlan Cox 	while ((rv = LIST_FIRST(&object->rvq)) != NULL) {
433f8a47341SAlan Cox 		KASSERT(rv->object == object,
434f8a47341SAlan Cox 		    ("vm_reserv_break_all: reserv %p is corrupted", rv));
435f8a47341SAlan Cox 		if (rv->inpartpopq) {
436f8a47341SAlan Cox 			TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
437f8a47341SAlan Cox 			rv->inpartpopq = FALSE;
438f8a47341SAlan Cox 		}
439f8a47341SAlan Cox 		LIST_REMOVE(rv, objq);
440f8a47341SAlan Cox 		rv->object = NULL;
441f8a47341SAlan Cox 		for (i = 0; i < VM_LEVEL_0_NPAGES; i++) {
442f8a47341SAlan Cox 			if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0)
443f8a47341SAlan Cox 				vm_phys_free_pages(&rv->pages[i], 0);
444f8a47341SAlan Cox 			else
445f8a47341SAlan Cox 				rv->popcnt--;
446f8a47341SAlan Cox 		}
447f8a47341SAlan Cox 		KASSERT(rv->popcnt == 0,
448f8a47341SAlan Cox 		    ("vm_reserv_break_all: reserv %p's popcnt is corrupted",
449f8a47341SAlan Cox 		    rv));
450f8a47341SAlan Cox 		vm_reserv_broken++;
451f8a47341SAlan Cox 	}
452f8a47341SAlan Cox 	mtx_unlock(&vm_page_queue_free_mtx);
453f8a47341SAlan Cox }
454f8a47341SAlan Cox 
455f8a47341SAlan Cox /*
456f8a47341SAlan Cox  * Frees the given page if it belongs to a reservation.  Returns TRUE if the
457f8a47341SAlan Cox  * page is freed and FALSE otherwise.
458f8a47341SAlan Cox  *
459f8a47341SAlan Cox  * The free page queue lock must be held.
460f8a47341SAlan Cox  */
461f8a47341SAlan Cox boolean_t
462f8a47341SAlan Cox vm_reserv_free_page(vm_page_t m)
463f8a47341SAlan Cox {
464f8a47341SAlan Cox 	vm_reserv_t rv;
465f8a47341SAlan Cox 
466f8a47341SAlan Cox 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
467f8a47341SAlan Cox 	rv = vm_reserv_from_page(m);
468f8a47341SAlan Cox 	if (rv->object != NULL) {
469f8a47341SAlan Cox 		vm_reserv_depopulate(rv);
470f8a47341SAlan Cox 		return (TRUE);
471f8a47341SAlan Cox 	}
472f8a47341SAlan Cox 	return (FALSE);
473f8a47341SAlan Cox }
474f8a47341SAlan Cox 
475f8a47341SAlan Cox /*
476f8a47341SAlan Cox  * Initializes the reservation management system.  Specifically, initializes
477f8a47341SAlan Cox  * the reservation array.
478f8a47341SAlan Cox  *
479f8a47341SAlan Cox  * Requires that vm_page_array and first_page are initialized!
480f8a47341SAlan Cox  */
481f8a47341SAlan Cox void
482f8a47341SAlan Cox vm_reserv_init(void)
483f8a47341SAlan Cox {
484f8a47341SAlan Cox 	vm_paddr_t paddr;
485f8a47341SAlan Cox 	int i;
486f8a47341SAlan Cox 
487f8a47341SAlan Cox 	/*
488f8a47341SAlan Cox 	 * Initialize the reservation array.  Specifically, initialize the
489f8a47341SAlan Cox 	 * "pages" field for every element that has an underlying superpage.
490f8a47341SAlan Cox 	 */
491f8a47341SAlan Cox 	for (i = 0; phys_avail[i + 1] != 0; i += 2) {
492f8a47341SAlan Cox 		paddr = roundup2(phys_avail[i], VM_LEVEL_0_SIZE);
493f8a47341SAlan Cox 		while (paddr + VM_LEVEL_0_SIZE <= phys_avail[i + 1]) {
494f8a47341SAlan Cox 			vm_reserv_array[paddr >> VM_LEVEL_0_SHIFT].pages =
495f8a47341SAlan Cox 			    PHYS_TO_VM_PAGE(paddr);
496f8a47341SAlan Cox 			paddr += VM_LEVEL_0_SIZE;
497f8a47341SAlan Cox 		}
498f8a47341SAlan Cox 	}
499f8a47341SAlan Cox }
500f8a47341SAlan Cox 
501f8a47341SAlan Cox /*
502f8a47341SAlan Cox  * Returns a reservation level if the given page belongs to a fully-populated
503f8a47341SAlan Cox  * reservation and -1 otherwise.
504f8a47341SAlan Cox  */
505f8a47341SAlan Cox int
506f8a47341SAlan Cox vm_reserv_level_iffullpop(vm_page_t m)
507f8a47341SAlan Cox {
508f8a47341SAlan Cox 	vm_reserv_t rv;
509f8a47341SAlan Cox 
510f8a47341SAlan Cox 	rv = vm_reserv_from_page(m);
511f8a47341SAlan Cox 	return (rv->popcnt == VM_LEVEL_0_NPAGES ? 0 : -1);
512f8a47341SAlan Cox }
513f8a47341SAlan Cox 
514f8a47341SAlan Cox /*
515f8a47341SAlan Cox  * Prepare for the reactivation of a cached page.
516f8a47341SAlan Cox  *
517f8a47341SAlan Cox  * First, suppose that the given page "m" was allocated individually, i.e., not
518f8a47341SAlan Cox  * as part of a reservation, and cached.  Then, suppose a reservation
519f8a47341SAlan Cox  * containing "m" is allocated by the same object.  Although "m" and the
520f8a47341SAlan Cox  * reservation belong to the same object, "m"'s pindex may not match the
521f8a47341SAlan Cox  * reservation's.
522f8a47341SAlan Cox  *
523f8a47341SAlan Cox  * The free page queue must be locked.
524f8a47341SAlan Cox  */
525f8a47341SAlan Cox boolean_t
526f8a47341SAlan Cox vm_reserv_reactivate_page(vm_page_t m)
527f8a47341SAlan Cox {
528f8a47341SAlan Cox 	vm_reserv_t rv;
529f8a47341SAlan Cox 	int i, m_index;
530f8a47341SAlan Cox 
531f8a47341SAlan Cox 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
532f8a47341SAlan Cox 	rv = vm_reserv_from_page(m);
533f8a47341SAlan Cox 	if (rv->object == NULL)
534f8a47341SAlan Cox 		return (FALSE);
535f8a47341SAlan Cox 	KASSERT((m->flags & PG_CACHED) != 0,
536f8a47341SAlan Cox 	    ("vm_reserv_uncache_page: page %p is not cached", m));
537f8a47341SAlan Cox 	if (m->object == rv->object &&
538f8a47341SAlan Cox 	    m->pindex - rv->pindex == VM_RESERV_INDEX(m->object, m->pindex))
539f8a47341SAlan Cox 		vm_reserv_populate(rv);
540f8a47341SAlan Cox 	else {
541f8a47341SAlan Cox 		KASSERT(rv->inpartpopq,
542f8a47341SAlan Cox 		    ("vm_reserv_uncache_page: reserv %p's inpartpopq is FALSE",
543f8a47341SAlan Cox 		    rv));
544f8a47341SAlan Cox 		TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
545f8a47341SAlan Cox 		rv->inpartpopq = FALSE;
546f8a47341SAlan Cox 		LIST_REMOVE(rv, objq);
547f8a47341SAlan Cox 		rv->object = NULL;
548f8a47341SAlan Cox 		/* Don't vm_phys_free_pages(m, 0). */
549f8a47341SAlan Cox 		m_index = m - rv->pages;
550f8a47341SAlan Cox 		for (i = 0; i < m_index; i++) {
551f8a47341SAlan Cox 			if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0)
552f8a47341SAlan Cox 				vm_phys_free_pages(&rv->pages[i], 0);
553f8a47341SAlan Cox 			else
554f8a47341SAlan Cox 				rv->popcnt--;
555f8a47341SAlan Cox 		}
556f8a47341SAlan Cox 		for (i++; i < VM_LEVEL_0_NPAGES; i++) {
557f8a47341SAlan Cox 			if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0)
558f8a47341SAlan Cox 				vm_phys_free_pages(&rv->pages[i], 0);
559f8a47341SAlan Cox 			else
560f8a47341SAlan Cox 				rv->popcnt--;
561f8a47341SAlan Cox 		}
562f8a47341SAlan Cox 		KASSERT(rv->popcnt == 0,
563f8a47341SAlan Cox 		    ("vm_reserv_uncache_page: reserv %p's popcnt is corrupted",
564f8a47341SAlan Cox 		    rv));
565f8a47341SAlan Cox 		vm_reserv_broken++;
566f8a47341SAlan Cox 	}
567f8a47341SAlan Cox 	return (TRUE);
568f8a47341SAlan Cox }
569f8a47341SAlan Cox 
570f8a47341SAlan Cox /*
571f8a47341SAlan Cox  * Breaks the reservation at the head of the partially-populated reservation
572f8a47341SAlan Cox  * queue, releasing its cached and free pages to the physical memory
573f8a47341SAlan Cox  * allocator.  Returns TRUE if a reservation is broken and FALSE otherwise.
574f8a47341SAlan Cox  *
575f8a47341SAlan Cox  * The free page queue lock must be held.
576f8a47341SAlan Cox  */
577f8a47341SAlan Cox boolean_t
578f8a47341SAlan Cox vm_reserv_reclaim(void)
579f8a47341SAlan Cox {
580f8a47341SAlan Cox 	vm_reserv_t rv;
581f8a47341SAlan Cox 	int i;
582f8a47341SAlan Cox 
583f8a47341SAlan Cox 	mtx_assert(&vm_page_queue_free_mtx, MA_OWNED);
584f8a47341SAlan Cox 	if ((rv = TAILQ_FIRST(&vm_rvq_partpop)) != NULL) {
585f8a47341SAlan Cox 		KASSERT(rv->inpartpopq,
586f8a47341SAlan Cox 		    ("vm_reserv_reclaim: reserv %p's inpartpopq is corrupted",
587f8a47341SAlan Cox 		    rv));
588f8a47341SAlan Cox 		TAILQ_REMOVE(&vm_rvq_partpop, rv, partpopq);
589f8a47341SAlan Cox 		rv->inpartpopq = FALSE;
590f8a47341SAlan Cox 		KASSERT(rv->object != NULL,
591f8a47341SAlan Cox 		    ("vm_reserv_reclaim: reserv %p is free", rv));
592f8a47341SAlan Cox 		LIST_REMOVE(rv, objq);
593f8a47341SAlan Cox 		rv->object = NULL;
594f8a47341SAlan Cox 		for (i = 0; i < VM_LEVEL_0_NPAGES; i++) {
595f8a47341SAlan Cox 			if ((rv->pages[i].flags & (PG_CACHED | PG_FREE)) != 0)
596f8a47341SAlan Cox 				vm_phys_free_pages(&rv->pages[i], 0);
597f8a47341SAlan Cox 			else
598f8a47341SAlan Cox 				rv->popcnt--;
599f8a47341SAlan Cox 		}
600f8a47341SAlan Cox 		KASSERT(rv->popcnt == 0,
601f8a47341SAlan Cox 		    ("vm_reserv_reclaim: reserv %p's popcnt is corrupted",
602f8a47341SAlan Cox 		    rv));
603f8a47341SAlan Cox 		vm_reserv_reclaimed++;
604f8a47341SAlan Cox 		return (TRUE);
605f8a47341SAlan Cox 	}
606f8a47341SAlan Cox 	return (FALSE);
607f8a47341SAlan Cox }
608f8a47341SAlan Cox 
609f8a47341SAlan Cox /*
610f8a47341SAlan Cox  * Transfers the reservation underlying the given page to a new object.
611f8a47341SAlan Cox  *
612f8a47341SAlan Cox  * The object must be locked.
613f8a47341SAlan Cox  */
614f8a47341SAlan Cox void
615f8a47341SAlan Cox vm_reserv_rename(vm_page_t m, vm_object_t new_object, vm_object_t old_object,
616f8a47341SAlan Cox     vm_pindex_t old_object_offset)
617f8a47341SAlan Cox {
618f8a47341SAlan Cox 	vm_reserv_t rv;
619f8a47341SAlan Cox 
620f8a47341SAlan Cox 	VM_OBJECT_LOCK_ASSERT(new_object, MA_OWNED);
621f8a47341SAlan Cox 	rv = vm_reserv_from_page(m);
622f8a47341SAlan Cox 	if (rv->object == old_object) {
623f8a47341SAlan Cox 		mtx_lock(&vm_page_queue_free_mtx);
624f8a47341SAlan Cox 		if (rv->object == old_object) {
625f8a47341SAlan Cox 			LIST_REMOVE(rv, objq);
626f8a47341SAlan Cox 			LIST_INSERT_HEAD(&new_object->rvq, rv, objq);
627f8a47341SAlan Cox 			rv->object = new_object;
628f8a47341SAlan Cox 			rv->pindex -= old_object_offset;
629f8a47341SAlan Cox 		}
630f8a47341SAlan Cox 		mtx_unlock(&vm_page_queue_free_mtx);
631f8a47341SAlan Cox 	}
632f8a47341SAlan Cox }
633f8a47341SAlan Cox 
634f8a47341SAlan Cox /*
635f8a47341SAlan Cox  * Allocates the virtual and physical memory required by the reservation
636f8a47341SAlan Cox  * management system's data structures, in particular, the reservation array.
637f8a47341SAlan Cox  */
638f8a47341SAlan Cox vm_paddr_t
639f8a47341SAlan Cox vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end, vm_paddr_t high_water)
640f8a47341SAlan Cox {
641f8a47341SAlan Cox 	vm_paddr_t new_end;
642f8a47341SAlan Cox 	size_t size;
643f8a47341SAlan Cox 
644f8a47341SAlan Cox 	/*
645f8a47341SAlan Cox 	 * Calculate the size (in bytes) of the reservation array.  Round up
646f8a47341SAlan Cox 	 * from "high_water" because every small page is mapped to an element
647f8a47341SAlan Cox 	 * in the reservation array based on its physical address.  Thus, the
648f8a47341SAlan Cox 	 * number of elements in the reservation array can be greater than the
649f8a47341SAlan Cox 	 * number of superpages.
650f8a47341SAlan Cox 	 */
651f8a47341SAlan Cox 	size = howmany(high_water, VM_LEVEL_0_SIZE) * sizeof(struct vm_reserv);
652f8a47341SAlan Cox 
653f8a47341SAlan Cox 	/*
654f8a47341SAlan Cox 	 * Allocate and map the physical memory for the reservation array.  The
655f8a47341SAlan Cox 	 * next available virtual address is returned by reference.
656f8a47341SAlan Cox 	 */
657f8a47341SAlan Cox 	new_end = end - round_page(size);
658f8a47341SAlan Cox 	vm_reserv_array = (void *)(uintptr_t)pmap_map(vaddr, new_end, end,
659f8a47341SAlan Cox 	    VM_PROT_READ | VM_PROT_WRITE);
660f8a47341SAlan Cox 	bzero(vm_reserv_array, size);
661f8a47341SAlan Cox 
662f8a47341SAlan Cox 	/*
663f8a47341SAlan Cox 	 * Return the next available physical address.
664f8a47341SAlan Cox 	 */
665f8a47341SAlan Cox 	return (new_end);
666f8a47341SAlan Cox }
667f8a47341SAlan Cox 
668f8a47341SAlan Cox #endif	/* VM_NRESERVLEVEL > 0 */
669