2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (c) 2017, Jeffrey Roberson <jeff@freebsd.org>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice unmodified, this list of conditions, and the following
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 #include <sys/cdefs.h>
31 __FBSDID("$FreeBSD$");
35 #include <sys/param.h>
36 #include <sys/systm.h>
37 #include <sys/bitset.h>
38 #include <sys/domainset.h>
41 #include <sys/mutex.h>
42 #include <sys/malloc.h>
43 #include <sys/vmmeter.h>
46 #include <vm/vm_param.h>
47 #include <vm/vm_domainset.h>
48 #include <vm/vm_object.h>
49 #include <vm/vm_page.h>
50 #include <vm/vm_phys.h>
54 * Iterators are written such that the first nowait pass has as short a
55 * codepath as possible to eliminate bloat from the allocator. It is
56 * assumed that most allocations are successful.
59 static int vm_domainset_default_stride = 64;
62 * Determine which policy is to be used for this allocation.
65 vm_domainset_iter_init(struct vm_domainset_iter *di, struct vm_object *obj,
68 struct domainset *domain;
72 * object policy takes precedence over thread policy. The policies
73 * are immutable and unsynchronized. Updates can race but pointer
74 * loads are assumed to be atomic.
76 if (obj != NULL && (domain = obj->domain.dr_policy) != NULL) {
77 di->di_domain = domain;
78 di->di_iter = &obj->domain.dr_iterator;
81 di->di_domain = td->td_domain.dr_policy;
82 di->di_iter = &td->td_domain.dr_iterator;
84 di->di_policy = di->di_domain->ds_policy;
85 if (di->di_policy == DOMAINSET_POLICY_INTERLEAVE) {
86 #if VM_NRESERVLEVEL > 0
87 if (vm_object_reserv(obj)) {
89 * Color the pindex so we end up on the correct
90 * reservation boundary.
92 pindex += obj->pg_color;
93 pindex >>= VM_LEVEL_0_ORDER;
96 pindex /= vm_domainset_default_stride;
98 * Offset pindex so the first page of each object does
99 * not end up in domain 0.
102 pindex += (((uintptr_t)obj) / sizeof(*obj));
103 di->di_offset = pindex;
105 /* Skip domains below min on the first pass. */
106 di->di_minskip = true;
110 vm_domainset_iter_rr(struct vm_domainset_iter *di, int *domain)
113 *domain = di->di_domain->ds_order[
114 ++(*di->di_iter) % di->di_domain->ds_cnt];
118 vm_domainset_iter_prefer(struct vm_domainset_iter *di, int *domain)
123 d = di->di_domain->ds_order[
124 ++(*di->di_iter) % di->di_domain->ds_cnt];
125 } while (d == di->di_domain->ds_prefer);
130 vm_domainset_iter_interleave(struct vm_domainset_iter *di, int *domain)
134 d = di->di_offset % di->di_domain->ds_cnt;
136 *domain = di->di_domain->ds_order[d];
140 vm_domainset_iter_next(struct vm_domainset_iter *di, int *domain)
143 KASSERT(di->di_n > 0,
144 ("vm_domainset_iter_first: Invalid n %d", di->di_n));
145 switch (di->di_policy) {
146 case DOMAINSET_POLICY_FIRSTTOUCH:
148 * To prevent impossible allocations we convert an invalid
149 * first-touch to round-robin.
152 case DOMAINSET_POLICY_INTERLEAVE:
154 case DOMAINSET_POLICY_ROUNDROBIN:
155 vm_domainset_iter_rr(di, domain);
157 case DOMAINSET_POLICY_PREFER:
158 vm_domainset_iter_prefer(di, domain);
161 panic("vm_domainset_iter_first: Unknown policy %d",
164 KASSERT(*domain < vm_ndomains,
165 ("vm_domainset_iter_next: Invalid domain %d", *domain));
169 vm_domainset_iter_first(struct vm_domainset_iter *di, int *domain)
172 switch (di->di_policy) {
173 case DOMAINSET_POLICY_FIRSTTOUCH:
174 *domain = PCPU_GET(domain);
175 if (DOMAINSET_ISSET(*domain, &di->di_domain->ds_mask)) {
177 * Add an extra iteration because we will visit the
178 * current domain a second time in the rr iterator.
180 di->di_n = di->di_domain->ds_cnt + 1;
184 * To prevent impossible allocations we convert an invalid
185 * first-touch to round-robin.
188 case DOMAINSET_POLICY_ROUNDROBIN:
189 di->di_n = di->di_domain->ds_cnt;
190 vm_domainset_iter_rr(di, domain);
192 case DOMAINSET_POLICY_PREFER:
193 *domain = di->di_domain->ds_prefer;
194 di->di_n = di->di_domain->ds_cnt;
196 case DOMAINSET_POLICY_INTERLEAVE:
197 vm_domainset_iter_interleave(di, domain);
198 di->di_n = di->di_domain->ds_cnt;
201 panic("vm_domainset_iter_first: Unknown policy %d",
204 KASSERT(di->di_n > 0,
205 ("vm_domainset_iter_first: Invalid n %d", di->di_n));
206 KASSERT(*domain < vm_ndomains,
207 ("vm_domainset_iter_first: Invalid domain %d", *domain));
211 vm_domainset_iter_page_init(struct vm_domainset_iter *di, struct vm_object *obj,
212 vm_pindex_t pindex, int *domain, int *req)
215 vm_domainset_iter_init(di, obj, pindex);
217 *req = (di->di_flags & ~(VM_ALLOC_WAITOK | VM_ALLOC_WAITFAIL)) |
219 vm_domainset_iter_first(di, domain);
220 if (vm_page_count_min_domain(*domain))
221 vm_domainset_iter_page(di, domain, req);
225 vm_domainset_iter_page(struct vm_domainset_iter *di, int *domain, int *req)
229 * If we exhausted all options with NOWAIT and did a WAITFAIL it
230 * is time to return an error to the caller.
232 if ((*req & VM_ALLOC_WAITFAIL) != 0)
235 /* If there are more domains to visit we run the iterator. */
236 while (--di->di_n != 0) {
237 vm_domainset_iter_next(di, domain);
238 if (!di->di_minskip || !vm_page_count_min_domain(*domain))
241 if (di->di_minskip) {
242 di->di_minskip = false;
243 vm_domainset_iter_first(di, domain);
247 /* If we visited all domains and this was a NOWAIT we return error. */
248 if ((di->di_flags & (VM_ALLOC_WAITOK | VM_ALLOC_WAITFAIL)) == 0)
252 * We have visited all domains with non-blocking allocations, try
253 * from the beginning with a blocking allocation.
255 vm_domainset_iter_first(di, domain);
263 vm_domainset_iter_malloc_init(struct vm_domainset_iter *di,
264 struct vm_object *obj, int *domain, int *flags)
267 vm_domainset_iter_init(di, obj, 0);
268 if (di->di_policy == DOMAINSET_POLICY_INTERLEAVE)
269 di->di_policy = DOMAINSET_POLICY_ROUNDROBIN;
270 di->di_flags = *flags;
271 *flags = (di->di_flags & ~M_WAITOK) | M_NOWAIT;
272 vm_domainset_iter_first(di, domain);
273 if (vm_page_count_min_domain(*domain))
274 vm_domainset_iter_malloc(di, domain, flags);
278 vm_domainset_iter_malloc(struct vm_domainset_iter *di, int *domain, int *flags)
281 /* If there are more domains to visit we run the iterator. */
282 while (--di->di_n != 0) {
283 vm_domainset_iter_next(di, domain);
284 if (!di->di_minskip || !vm_page_count_min_domain(*domain))
288 /* If we skipped domains below min restart the search. */
289 if (di->di_minskip) {
290 di->di_minskip = false;
291 vm_domainset_iter_first(di, domain);
295 /* If we visited all domains and this was a NOWAIT we return error. */
296 if ((di->di_flags & M_WAITOK) == 0)
300 * We have visited all domains with non-blocking allocations, try
301 * from the beginning with a blocking allocation.
303 vm_domainset_iter_first(di, domain);
304 *flags = di->di_flags;
311 vm_domainset_iter_page(struct vm_domainset_iter *di, int *domain, int *flags)
314 return (EJUSTRETURN);
318 vm_domainset_iter_page_init(struct vm_domainset_iter *di,
319 struct vm_object *obj, vm_pindex_t pindex, int *domain, int *flags)
326 vm_domainset_iter_malloc(struct vm_domainset_iter *di, int *domain, int *flags)
329 return (EJUSTRETURN);
333 vm_domainset_iter_malloc_init(struct vm_domainset_iter *di,
334 struct vm_object *obj, int *domain, int *flags)