xref: /freebsd/sys/vm/uma_core.c (revision e4b0a90e771b94e4b043729a6f0f5564f1d01aca)
1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3  *
4  * Copyright (c) 2002-2005, 2009, 2013 Jeffrey Roberson <jeff@FreeBSD.org>
5  * Copyright (c) 2004, 2005 Bosko Milekic <bmilekic@FreeBSD.org>
6  * Copyright (c) 2004-2006 Robert N. M. Watson
7  * All rights reserved.
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 unmodified, this list of conditions, and the following
14  *    disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30 
31 /*
32  * uma_core.c  Implementation of the Universal Memory allocator
33  *
34  * This allocator is intended to replace the multitude of similar object caches
35  * in the standard FreeBSD kernel.  The intent is to be flexible as well as
36  * efficient.  A primary design goal is to return unused memory to the rest of
37  * the system.  This will make the system as a whole more flexible due to the
38  * ability to move memory to subsystems which most need it instead of leaving
39  * pools of reserved memory unused.
40  *
41  * The basic ideas stem from similar slab/zone based allocators whose algorithms
42  * are well known.
43  *
44  */
45 
46 /*
47  * TODO:
48  *	- Improve memory usage for large allocations
49  *	- Investigate cache size adjustments
50  */
51 
52 #include <sys/cdefs.h>
53 __FBSDID("$FreeBSD$");
54 
55 #include "opt_ddb.h"
56 #include "opt_param.h"
57 #include "opt_vm.h"
58 
59 #include <sys/param.h>
60 #include <sys/systm.h>
61 #include <sys/bitset.h>
62 #include <sys/eventhandler.h>
63 #include <sys/kernel.h>
64 #include <sys/types.h>
65 #include <sys/limits.h>
66 #include <sys/queue.h>
67 #include <sys/malloc.h>
68 #include <sys/ktr.h>
69 #include <sys/lock.h>
70 #include <sys/sysctl.h>
71 #include <sys/mutex.h>
72 #include <sys/proc.h>
73 #include <sys/random.h>
74 #include <sys/rwlock.h>
75 #include <sys/sbuf.h>
76 #include <sys/sched.h>
77 #include <sys/smp.h>
78 #include <sys/taskqueue.h>
79 #include <sys/vmmeter.h>
80 
81 #include <vm/vm.h>
82 #include <vm/vm_object.h>
83 #include <vm/vm_page.h>
84 #include <vm/vm_pageout.h>
85 #include <vm/vm_param.h>
86 #include <vm/vm_phys.h>
87 #include <vm/vm_map.h>
88 #include <vm/vm_kern.h>
89 #include <vm/vm_extern.h>
90 #include <vm/uma.h>
91 #include <vm/uma_int.h>
92 #include <vm/uma_dbg.h>
93 
94 #include <ddb/ddb.h>
95 
96 #ifdef DEBUG_MEMGUARD
97 #include <vm/memguard.h>
98 #endif
99 
100 /*
101  * This is the zone and keg from which all zones are spawned.
102  */
103 static uma_zone_t kegs;
104 static uma_zone_t zones;
105 
106 /* This is the zone from which all offpage uma_slab_ts are allocated. */
107 static uma_zone_t slabzone;
108 
109 /*
110  * The initial hash tables come out of this zone so they can be allocated
111  * prior to malloc coming up.
112  */
113 static uma_zone_t hashzone;
114 
115 /* The boot-time adjusted value for cache line alignment. */
116 int uma_align_cache = 64 - 1;
117 
118 static MALLOC_DEFINE(M_UMAHASH, "UMAHash", "UMA Hash Buckets");
119 
120 /*
121  * Are we allowed to allocate buckets?
122  */
123 static int bucketdisable = 1;
124 
125 /* Linked list of all kegs in the system */
126 static LIST_HEAD(,uma_keg) uma_kegs = LIST_HEAD_INITIALIZER(uma_kegs);
127 
128 /* Linked list of all cache-only zones in the system */
129 static LIST_HEAD(,uma_zone) uma_cachezones =
130     LIST_HEAD_INITIALIZER(uma_cachezones);
131 
132 /* This RW lock protects the keg list */
133 static struct rwlock_padalign __exclusive_cache_line uma_rwlock;
134 
135 /*
136  * Pointer and counter to pool of pages, that is preallocated at
137  * startup to bootstrap UMA.
138  */
139 static char *bootmem;
140 static int boot_pages;
141 
142 static struct sx uma_drain_lock;
143 
144 /* kmem soft limit. */
145 static unsigned long uma_kmem_limit = LONG_MAX;
146 static volatile unsigned long uma_kmem_total;
147 
148 /* Is the VM done starting up? */
149 static enum { BOOT_COLD = 0, BOOT_STRAPPED, BOOT_PAGEALLOC, BOOT_BUCKETS,
150     BOOT_RUNNING } booted = BOOT_COLD;
151 
152 /*
153  * This is the handle used to schedule events that need to happen
154  * outside of the allocation fast path.
155  */
156 static struct callout uma_callout;
157 #define	UMA_TIMEOUT	20		/* Seconds for callout interval. */
158 
159 /*
160  * This structure is passed as the zone ctor arg so that I don't have to create
161  * a special allocation function just for zones.
162  */
163 struct uma_zctor_args {
164 	const char *name;
165 	size_t size;
166 	uma_ctor ctor;
167 	uma_dtor dtor;
168 	uma_init uminit;
169 	uma_fini fini;
170 	uma_import import;
171 	uma_release release;
172 	void *arg;
173 	uma_keg_t keg;
174 	int align;
175 	uint32_t flags;
176 };
177 
178 struct uma_kctor_args {
179 	uma_zone_t zone;
180 	size_t size;
181 	uma_init uminit;
182 	uma_fini fini;
183 	int align;
184 	uint32_t flags;
185 };
186 
187 struct uma_bucket_zone {
188 	uma_zone_t	ubz_zone;
189 	char		*ubz_name;
190 	int		ubz_entries;	/* Number of items it can hold. */
191 	int		ubz_maxsize;	/* Maximum allocation size per-item. */
192 };
193 
194 /*
195  * Compute the actual number of bucket entries to pack them in power
196  * of two sizes for more efficient space utilization.
197  */
198 #define	BUCKET_SIZE(n)						\
199     (((sizeof(void *) * (n)) - sizeof(struct uma_bucket)) / sizeof(void *))
200 
201 #define	BUCKET_MAX	BUCKET_SIZE(256)
202 
203 struct uma_bucket_zone bucket_zones[] = {
204 	{ NULL, "4 Bucket", BUCKET_SIZE(4), 4096 },
205 	{ NULL, "6 Bucket", BUCKET_SIZE(6), 3072 },
206 	{ NULL, "8 Bucket", BUCKET_SIZE(8), 2048 },
207 	{ NULL, "12 Bucket", BUCKET_SIZE(12), 1536 },
208 	{ NULL, "16 Bucket", BUCKET_SIZE(16), 1024 },
209 	{ NULL, "32 Bucket", BUCKET_SIZE(32), 512 },
210 	{ NULL, "64 Bucket", BUCKET_SIZE(64), 256 },
211 	{ NULL, "128 Bucket", BUCKET_SIZE(128), 128 },
212 	{ NULL, "256 Bucket", BUCKET_SIZE(256), 64 },
213 	{ NULL, NULL, 0}
214 };
215 
216 /*
217  * Flags and enumerations to be passed to internal functions.
218  */
219 enum zfreeskip { SKIP_NONE = 0, SKIP_DTOR, SKIP_FINI };
220 
221 #define	UMA_ANYDOMAIN	-1	/* Special value for domain search. */
222 
223 /* Prototypes.. */
224 
225 int	uma_startup_count(int);
226 void	uma_startup(void *, int);
227 void	uma_startup1(void);
228 void	uma_startup2(void);
229 
230 static void *noobj_alloc(uma_zone_t, vm_size_t, int, uint8_t *, int);
231 static void *page_alloc(uma_zone_t, vm_size_t, int, uint8_t *, int);
232 static void *startup_alloc(uma_zone_t, vm_size_t, int, uint8_t *, int);
233 static void page_free(void *, vm_size_t, uint8_t);
234 static uma_slab_t keg_alloc_slab(uma_keg_t, uma_zone_t, int, int);
235 static void cache_drain(uma_zone_t);
236 static void bucket_drain(uma_zone_t, uma_bucket_t);
237 static void bucket_cache_drain(uma_zone_t zone);
238 static int keg_ctor(void *, int, void *, int);
239 static void keg_dtor(void *, int, void *);
240 static int zone_ctor(void *, int, void *, int);
241 static void zone_dtor(void *, int, void *);
242 static int zero_init(void *, int, int);
243 static void keg_small_init(uma_keg_t keg);
244 static void keg_large_init(uma_keg_t keg);
245 static void zone_foreach(void (*zfunc)(uma_zone_t));
246 static void zone_timeout(uma_zone_t zone);
247 static int hash_alloc(struct uma_hash *);
248 static int hash_expand(struct uma_hash *, struct uma_hash *);
249 static void hash_free(struct uma_hash *hash);
250 static void uma_timeout(void *);
251 static void uma_startup3(void);
252 static void *zone_alloc_item(uma_zone_t, void *, int, int);
253 static void zone_free_item(uma_zone_t, void *, void *, enum zfreeskip);
254 static void bucket_enable(void);
255 static void bucket_init(void);
256 static uma_bucket_t bucket_alloc(uma_zone_t zone, void *, int);
257 static void bucket_free(uma_zone_t zone, uma_bucket_t, void *);
258 static void bucket_zone_drain(void);
259 static uma_bucket_t zone_alloc_bucket(uma_zone_t, void *, int, int);
260 static uma_slab_t zone_fetch_slab(uma_zone_t, uma_keg_t, int, int);
261 static uma_slab_t zone_fetch_slab_multi(uma_zone_t, uma_keg_t, int, int);
262 static void *slab_alloc_item(uma_keg_t keg, uma_slab_t slab);
263 static void slab_free_item(uma_keg_t keg, uma_slab_t slab, void *item);
264 static uma_keg_t uma_kcreate(uma_zone_t zone, size_t size, uma_init uminit,
265     uma_fini fini, int align, uint32_t flags);
266 static int zone_import(uma_zone_t, void **, int, int, int);
267 static void zone_release(uma_zone_t, void **, int);
268 static void uma_zero_item(void *, uma_zone_t);
269 
270 void uma_print_zone(uma_zone_t);
271 void uma_print_stats(void);
272 static int sysctl_vm_zone_count(SYSCTL_HANDLER_ARGS);
273 static int sysctl_vm_zone_stats(SYSCTL_HANDLER_ARGS);
274 
275 #ifdef INVARIANTS
276 static bool uma_dbg_kskip(uma_keg_t keg, void *mem);
277 static bool uma_dbg_zskip(uma_zone_t zone, void *mem);
278 static void uma_dbg_free(uma_zone_t zone, uma_slab_t slab, void *item);
279 static void uma_dbg_alloc(uma_zone_t zone, uma_slab_t slab, void *item);
280 
281 static SYSCTL_NODE(_vm, OID_AUTO, debug, CTLFLAG_RD, 0,
282     "Memory allocation debugging");
283 
284 static u_int dbg_divisor = 1;
285 SYSCTL_UINT(_vm_debug, OID_AUTO, divisor,
286     CTLFLAG_RDTUN | CTLFLAG_NOFETCH, &dbg_divisor, 0,
287     "Debug & thrash every this item in memory allocator");
288 
289 static counter_u64_t uma_dbg_cnt = EARLY_COUNTER;
290 static counter_u64_t uma_skip_cnt = EARLY_COUNTER;
291 SYSCTL_COUNTER_U64(_vm_debug, OID_AUTO, trashed, CTLFLAG_RD,
292     &uma_dbg_cnt, "memory items debugged");
293 SYSCTL_COUNTER_U64(_vm_debug, OID_AUTO, skipped, CTLFLAG_RD,
294     &uma_skip_cnt, "memory items skipped, not debugged");
295 #endif
296 
297 SYSINIT(uma_startup3, SI_SUB_VM_CONF, SI_ORDER_SECOND, uma_startup3, NULL);
298 
299 SYSCTL_PROC(_vm, OID_AUTO, zone_count, CTLFLAG_RD|CTLTYPE_INT,
300     0, 0, sysctl_vm_zone_count, "I", "Number of UMA zones");
301 
302 SYSCTL_PROC(_vm, OID_AUTO, zone_stats, CTLFLAG_RD|CTLTYPE_STRUCT,
303     0, 0, sysctl_vm_zone_stats, "s,struct uma_type_header", "Zone Stats");
304 
305 static int zone_warnings = 1;
306 SYSCTL_INT(_vm, OID_AUTO, zone_warnings, CTLFLAG_RWTUN, &zone_warnings, 0,
307     "Warn when UMA zones becomes full");
308 
309 /* Adjust bytes under management by UMA. */
310 static inline void
311 uma_total_dec(unsigned long size)
312 {
313 
314 	atomic_subtract_long(&uma_kmem_total, size);
315 }
316 
317 static inline void
318 uma_total_inc(unsigned long size)
319 {
320 
321 	if (atomic_fetchadd_long(&uma_kmem_total, size) > uma_kmem_limit)
322 		uma_reclaim_wakeup();
323 }
324 
325 /*
326  * This routine checks to see whether or not it's safe to enable buckets.
327  */
328 static void
329 bucket_enable(void)
330 {
331 	bucketdisable = vm_page_count_min();
332 }
333 
334 /*
335  * Initialize bucket_zones, the array of zones of buckets of various sizes.
336  *
337  * For each zone, calculate the memory required for each bucket, consisting
338  * of the header and an array of pointers.
339  */
340 static void
341 bucket_init(void)
342 {
343 	struct uma_bucket_zone *ubz;
344 	int size;
345 
346 	for (ubz = &bucket_zones[0]; ubz->ubz_entries != 0; ubz++) {
347 		size = roundup(sizeof(struct uma_bucket), sizeof(void *));
348 		size += sizeof(void *) * ubz->ubz_entries;
349 		ubz->ubz_zone = uma_zcreate(ubz->ubz_name, size,
350 		    NULL, NULL, NULL, NULL, UMA_ALIGN_PTR,
351 		    UMA_ZONE_MTXCLASS | UMA_ZFLAG_BUCKET | UMA_ZONE_NUMA);
352 	}
353 }
354 
355 /*
356  * Given a desired number of entries for a bucket, return the zone from which
357  * to allocate the bucket.
358  */
359 static struct uma_bucket_zone *
360 bucket_zone_lookup(int entries)
361 {
362 	struct uma_bucket_zone *ubz;
363 
364 	for (ubz = &bucket_zones[0]; ubz->ubz_entries != 0; ubz++)
365 		if (ubz->ubz_entries >= entries)
366 			return (ubz);
367 	ubz--;
368 	return (ubz);
369 }
370 
371 static int
372 bucket_select(int size)
373 {
374 	struct uma_bucket_zone *ubz;
375 
376 	ubz = &bucket_zones[0];
377 	if (size > ubz->ubz_maxsize)
378 		return MAX((ubz->ubz_maxsize * ubz->ubz_entries) / size, 1);
379 
380 	for (; ubz->ubz_entries != 0; ubz++)
381 		if (ubz->ubz_maxsize < size)
382 			break;
383 	ubz--;
384 	return (ubz->ubz_entries);
385 }
386 
387 static uma_bucket_t
388 bucket_alloc(uma_zone_t zone, void *udata, int flags)
389 {
390 	struct uma_bucket_zone *ubz;
391 	uma_bucket_t bucket;
392 
393 	/*
394 	 * This is to stop us from allocating per cpu buckets while we're
395 	 * running out of vm.boot_pages.  Otherwise, we would exhaust the
396 	 * boot pages.  This also prevents us from allocating buckets in
397 	 * low memory situations.
398 	 */
399 	if (bucketdisable)
400 		return (NULL);
401 	/*
402 	 * To limit bucket recursion we store the original zone flags
403 	 * in a cookie passed via zalloc_arg/zfree_arg.  This allows the
404 	 * NOVM flag to persist even through deep recursions.  We also
405 	 * store ZFLAG_BUCKET once we have recursed attempting to allocate
406 	 * a bucket for a bucket zone so we do not allow infinite bucket
407 	 * recursion.  This cookie will even persist to frees of unused
408 	 * buckets via the allocation path or bucket allocations in the
409 	 * free path.
410 	 */
411 	if ((zone->uz_flags & UMA_ZFLAG_BUCKET) == 0)
412 		udata = (void *)(uintptr_t)zone->uz_flags;
413 	else {
414 		if ((uintptr_t)udata & UMA_ZFLAG_BUCKET)
415 			return (NULL);
416 		udata = (void *)((uintptr_t)udata | UMA_ZFLAG_BUCKET);
417 	}
418 	if ((uintptr_t)udata & UMA_ZFLAG_CACHEONLY)
419 		flags |= M_NOVM;
420 	ubz = bucket_zone_lookup(zone->uz_count);
421 	if (ubz->ubz_zone == zone && (ubz + 1)->ubz_entries != 0)
422 		ubz++;
423 	bucket = uma_zalloc_arg(ubz->ubz_zone, udata, flags);
424 	if (bucket) {
425 #ifdef INVARIANTS
426 		bzero(bucket->ub_bucket, sizeof(void *) * ubz->ubz_entries);
427 #endif
428 		bucket->ub_cnt = 0;
429 		bucket->ub_entries = ubz->ubz_entries;
430 	}
431 
432 	return (bucket);
433 }
434 
435 static void
436 bucket_free(uma_zone_t zone, uma_bucket_t bucket, void *udata)
437 {
438 	struct uma_bucket_zone *ubz;
439 
440 	KASSERT(bucket->ub_cnt == 0,
441 	    ("bucket_free: Freeing a non free bucket."));
442 	if ((zone->uz_flags & UMA_ZFLAG_BUCKET) == 0)
443 		udata = (void *)(uintptr_t)zone->uz_flags;
444 	ubz = bucket_zone_lookup(bucket->ub_entries);
445 	uma_zfree_arg(ubz->ubz_zone, bucket, udata);
446 }
447 
448 static void
449 bucket_zone_drain(void)
450 {
451 	struct uma_bucket_zone *ubz;
452 
453 	for (ubz = &bucket_zones[0]; ubz->ubz_entries != 0; ubz++)
454 		zone_drain(ubz->ubz_zone);
455 }
456 
457 static void
458 zone_log_warning(uma_zone_t zone)
459 {
460 	static const struct timeval warninterval = { 300, 0 };
461 
462 	if (!zone_warnings || zone->uz_warning == NULL)
463 		return;
464 
465 	if (ratecheck(&zone->uz_ratecheck, &warninterval))
466 		printf("[zone: %s] %s\n", zone->uz_name, zone->uz_warning);
467 }
468 
469 static inline void
470 zone_maxaction(uma_zone_t zone)
471 {
472 
473 	if (zone->uz_maxaction.ta_func != NULL)
474 		taskqueue_enqueue(taskqueue_thread, &zone->uz_maxaction);
475 }
476 
477 static void
478 zone_foreach_keg(uma_zone_t zone, void (*kegfn)(uma_keg_t))
479 {
480 	uma_klink_t klink;
481 
482 	LIST_FOREACH(klink, &zone->uz_kegs, kl_link)
483 		kegfn(klink->kl_keg);
484 }
485 
486 /*
487  * Routine called by timeout which is used to fire off some time interval
488  * based calculations.  (stats, hash size, etc.)
489  *
490  * Arguments:
491  *	arg   Unused
492  *
493  * Returns:
494  *	Nothing
495  */
496 static void
497 uma_timeout(void *unused)
498 {
499 	bucket_enable();
500 	zone_foreach(zone_timeout);
501 
502 	/* Reschedule this event */
503 	callout_reset(&uma_callout, UMA_TIMEOUT * hz, uma_timeout, NULL);
504 }
505 
506 /*
507  * Routine to perform timeout driven calculations.  This expands the
508  * hashes and does per cpu statistics aggregation.
509  *
510  *  Returns nothing.
511  */
512 static void
513 keg_timeout(uma_keg_t keg)
514 {
515 
516 	KEG_LOCK(keg);
517 	/*
518 	 * Expand the keg hash table.
519 	 *
520 	 * This is done if the number of slabs is larger than the hash size.
521 	 * What I'm trying to do here is completely reduce collisions.  This
522 	 * may be a little aggressive.  Should I allow for two collisions max?
523 	 */
524 	if (keg->uk_flags & UMA_ZONE_HASH &&
525 	    keg->uk_pages / keg->uk_ppera >= keg->uk_hash.uh_hashsize) {
526 		struct uma_hash newhash;
527 		struct uma_hash oldhash;
528 		int ret;
529 
530 		/*
531 		 * This is so involved because allocating and freeing
532 		 * while the keg lock is held will lead to deadlock.
533 		 * I have to do everything in stages and check for
534 		 * races.
535 		 */
536 		newhash = keg->uk_hash;
537 		KEG_UNLOCK(keg);
538 		ret = hash_alloc(&newhash);
539 		KEG_LOCK(keg);
540 		if (ret) {
541 			if (hash_expand(&keg->uk_hash, &newhash)) {
542 				oldhash = keg->uk_hash;
543 				keg->uk_hash = newhash;
544 			} else
545 				oldhash = newhash;
546 
547 			KEG_UNLOCK(keg);
548 			hash_free(&oldhash);
549 			return;
550 		}
551 	}
552 	KEG_UNLOCK(keg);
553 }
554 
555 static void
556 zone_timeout(uma_zone_t zone)
557 {
558 
559 	zone_foreach_keg(zone, &keg_timeout);
560 }
561 
562 /*
563  * Allocate and zero fill the next sized hash table from the appropriate
564  * backing store.
565  *
566  * Arguments:
567  *	hash  A new hash structure with the old hash size in uh_hashsize
568  *
569  * Returns:
570  *	1 on success and 0 on failure.
571  */
572 static int
573 hash_alloc(struct uma_hash *hash)
574 {
575 	int oldsize;
576 	int alloc;
577 
578 	oldsize = hash->uh_hashsize;
579 
580 	/* We're just going to go to a power of two greater */
581 	if (oldsize)  {
582 		hash->uh_hashsize = oldsize * 2;
583 		alloc = sizeof(hash->uh_slab_hash[0]) * hash->uh_hashsize;
584 		hash->uh_slab_hash = (struct slabhead *)malloc(alloc,
585 		    M_UMAHASH, M_NOWAIT);
586 	} else {
587 		alloc = sizeof(hash->uh_slab_hash[0]) * UMA_HASH_SIZE_INIT;
588 		hash->uh_slab_hash = zone_alloc_item(hashzone, NULL,
589 		    UMA_ANYDOMAIN, M_WAITOK);
590 		hash->uh_hashsize = UMA_HASH_SIZE_INIT;
591 	}
592 	if (hash->uh_slab_hash) {
593 		bzero(hash->uh_slab_hash, alloc);
594 		hash->uh_hashmask = hash->uh_hashsize - 1;
595 		return (1);
596 	}
597 
598 	return (0);
599 }
600 
601 /*
602  * Expands the hash table for HASH zones.  This is done from zone_timeout
603  * to reduce collisions.  This must not be done in the regular allocation
604  * path, otherwise, we can recurse on the vm while allocating pages.
605  *
606  * Arguments:
607  *	oldhash  The hash you want to expand
608  *	newhash  The hash structure for the new table
609  *
610  * Returns:
611  *	Nothing
612  *
613  * Discussion:
614  */
615 static int
616 hash_expand(struct uma_hash *oldhash, struct uma_hash *newhash)
617 {
618 	uma_slab_t slab;
619 	int hval;
620 	int i;
621 
622 	if (!newhash->uh_slab_hash)
623 		return (0);
624 
625 	if (oldhash->uh_hashsize >= newhash->uh_hashsize)
626 		return (0);
627 
628 	/*
629 	 * I need to investigate hash algorithms for resizing without a
630 	 * full rehash.
631 	 */
632 
633 	for (i = 0; i < oldhash->uh_hashsize; i++)
634 		while (!SLIST_EMPTY(&oldhash->uh_slab_hash[i])) {
635 			slab = SLIST_FIRST(&oldhash->uh_slab_hash[i]);
636 			SLIST_REMOVE_HEAD(&oldhash->uh_slab_hash[i], us_hlink);
637 			hval = UMA_HASH(newhash, slab->us_data);
638 			SLIST_INSERT_HEAD(&newhash->uh_slab_hash[hval],
639 			    slab, us_hlink);
640 		}
641 
642 	return (1);
643 }
644 
645 /*
646  * Free the hash bucket to the appropriate backing store.
647  *
648  * Arguments:
649  *	slab_hash  The hash bucket we're freeing
650  *	hashsize   The number of entries in that hash bucket
651  *
652  * Returns:
653  *	Nothing
654  */
655 static void
656 hash_free(struct uma_hash *hash)
657 {
658 	if (hash->uh_slab_hash == NULL)
659 		return;
660 	if (hash->uh_hashsize == UMA_HASH_SIZE_INIT)
661 		zone_free_item(hashzone, hash->uh_slab_hash, NULL, SKIP_NONE);
662 	else
663 		free(hash->uh_slab_hash, M_UMAHASH);
664 }
665 
666 /*
667  * Frees all outstanding items in a bucket
668  *
669  * Arguments:
670  *	zone   The zone to free to, must be unlocked.
671  *	bucket The free/alloc bucket with items, cpu queue must be locked.
672  *
673  * Returns:
674  *	Nothing
675  */
676 
677 static void
678 bucket_drain(uma_zone_t zone, uma_bucket_t bucket)
679 {
680 	int i;
681 
682 	if (bucket == NULL)
683 		return;
684 
685 	if (zone->uz_fini)
686 		for (i = 0; i < bucket->ub_cnt; i++)
687 			zone->uz_fini(bucket->ub_bucket[i], zone->uz_size);
688 	zone->uz_release(zone->uz_arg, bucket->ub_bucket, bucket->ub_cnt);
689 	bucket->ub_cnt = 0;
690 }
691 
692 /*
693  * Drains the per cpu caches for a zone.
694  *
695  * NOTE: This may only be called while the zone is being turn down, and not
696  * during normal operation.  This is necessary in order that we do not have
697  * to migrate CPUs to drain the per-CPU caches.
698  *
699  * Arguments:
700  *	zone     The zone to drain, must be unlocked.
701  *
702  * Returns:
703  *	Nothing
704  */
705 static void
706 cache_drain(uma_zone_t zone)
707 {
708 	uma_cache_t cache;
709 	int cpu;
710 
711 	/*
712 	 * XXX: It is safe to not lock the per-CPU caches, because we're
713 	 * tearing down the zone anyway.  I.e., there will be no further use
714 	 * of the caches at this point.
715 	 *
716 	 * XXX: It would good to be able to assert that the zone is being
717 	 * torn down to prevent improper use of cache_drain().
718 	 *
719 	 * XXX: We lock the zone before passing into bucket_cache_drain() as
720 	 * it is used elsewhere.  Should the tear-down path be made special
721 	 * there in some form?
722 	 */
723 	CPU_FOREACH(cpu) {
724 		cache = &zone->uz_cpu[cpu];
725 		bucket_drain(zone, cache->uc_allocbucket);
726 		bucket_drain(zone, cache->uc_freebucket);
727 		if (cache->uc_allocbucket != NULL)
728 			bucket_free(zone, cache->uc_allocbucket, NULL);
729 		if (cache->uc_freebucket != NULL)
730 			bucket_free(zone, cache->uc_freebucket, NULL);
731 		cache->uc_allocbucket = cache->uc_freebucket = NULL;
732 	}
733 	ZONE_LOCK(zone);
734 	bucket_cache_drain(zone);
735 	ZONE_UNLOCK(zone);
736 }
737 
738 static void
739 cache_shrink(uma_zone_t zone)
740 {
741 
742 	if (zone->uz_flags & UMA_ZFLAG_INTERNAL)
743 		return;
744 
745 	ZONE_LOCK(zone);
746 	zone->uz_count = (zone->uz_count_min + zone->uz_count) / 2;
747 	ZONE_UNLOCK(zone);
748 }
749 
750 static void
751 cache_drain_safe_cpu(uma_zone_t zone)
752 {
753 	uma_cache_t cache;
754 	uma_bucket_t b1, b2;
755 	int domain;
756 
757 	if (zone->uz_flags & UMA_ZFLAG_INTERNAL)
758 		return;
759 
760 	b1 = b2 = NULL;
761 	ZONE_LOCK(zone);
762 	critical_enter();
763 	if (zone->uz_flags & UMA_ZONE_NUMA)
764 		domain = PCPU_GET(domain);
765 	else
766 		domain = 0;
767 	cache = &zone->uz_cpu[curcpu];
768 	if (cache->uc_allocbucket) {
769 		if (cache->uc_allocbucket->ub_cnt != 0)
770 			LIST_INSERT_HEAD(&zone->uz_domain[domain].uzd_buckets,
771 			    cache->uc_allocbucket, ub_link);
772 		else
773 			b1 = cache->uc_allocbucket;
774 		cache->uc_allocbucket = NULL;
775 	}
776 	if (cache->uc_freebucket) {
777 		if (cache->uc_freebucket->ub_cnt != 0)
778 			LIST_INSERT_HEAD(&zone->uz_domain[domain].uzd_buckets,
779 			    cache->uc_freebucket, ub_link);
780 		else
781 			b2 = cache->uc_freebucket;
782 		cache->uc_freebucket = NULL;
783 	}
784 	critical_exit();
785 	ZONE_UNLOCK(zone);
786 	if (b1)
787 		bucket_free(zone, b1, NULL);
788 	if (b2)
789 		bucket_free(zone, b2, NULL);
790 }
791 
792 /*
793  * Safely drain per-CPU caches of a zone(s) to alloc bucket.
794  * This is an expensive call because it needs to bind to all CPUs
795  * one by one and enter a critical section on each of them in order
796  * to safely access their cache buckets.
797  * Zone lock must not be held on call this function.
798  */
799 static void
800 cache_drain_safe(uma_zone_t zone)
801 {
802 	int cpu;
803 
804 	/*
805 	 * Polite bucket sizes shrinking was not enouth, shrink aggressively.
806 	 */
807 	if (zone)
808 		cache_shrink(zone);
809 	else
810 		zone_foreach(cache_shrink);
811 
812 	CPU_FOREACH(cpu) {
813 		thread_lock(curthread);
814 		sched_bind(curthread, cpu);
815 		thread_unlock(curthread);
816 
817 		if (zone)
818 			cache_drain_safe_cpu(zone);
819 		else
820 			zone_foreach(cache_drain_safe_cpu);
821 	}
822 	thread_lock(curthread);
823 	sched_unbind(curthread);
824 	thread_unlock(curthread);
825 }
826 
827 /*
828  * Drain the cached buckets from a zone.  Expects a locked zone on entry.
829  */
830 static void
831 bucket_cache_drain(uma_zone_t zone)
832 {
833 	uma_zone_domain_t zdom;
834 	uma_bucket_t bucket;
835 	int i;
836 
837 	/*
838 	 * Drain the bucket queues and free the buckets.
839 	 */
840 	for (i = 0; i < vm_ndomains; i++) {
841 		zdom = &zone->uz_domain[i];
842 		while ((bucket = LIST_FIRST(&zdom->uzd_buckets)) != NULL) {
843 			LIST_REMOVE(bucket, ub_link);
844 			ZONE_UNLOCK(zone);
845 			bucket_drain(zone, bucket);
846 			bucket_free(zone, bucket, NULL);
847 			ZONE_LOCK(zone);
848 		}
849 	}
850 
851 	/*
852 	 * Shrink further bucket sizes.  Price of single zone lock collision
853 	 * is probably lower then price of global cache drain.
854 	 */
855 	if (zone->uz_count > zone->uz_count_min)
856 		zone->uz_count--;
857 }
858 
859 static void
860 keg_free_slab(uma_keg_t keg, uma_slab_t slab, int start)
861 {
862 	uint8_t *mem;
863 	int i;
864 	uint8_t flags;
865 
866 	CTR4(KTR_UMA, "keg_free_slab keg %s(%p) slab %p, returning %d bytes",
867 	    keg->uk_name, keg, slab, PAGE_SIZE * keg->uk_ppera);
868 
869 	mem = slab->us_data;
870 	flags = slab->us_flags;
871 	i = start;
872 	if (keg->uk_fini != NULL) {
873 		for (i--; i > -1; i--)
874 #ifdef INVARIANTS
875 		/*
876 		 * trash_fini implies that dtor was trash_dtor. trash_fini
877 		 * would check that memory hasn't been modified since free,
878 		 * which executed trash_dtor.
879 		 * That's why we need to run uma_dbg_kskip() check here,
880 		 * albeit we don't make skip check for other init/fini
881 		 * invocations.
882 		 */
883 		if (!uma_dbg_kskip(keg, slab->us_data + (keg->uk_rsize * i)) ||
884 		    keg->uk_fini != trash_fini)
885 #endif
886 			keg->uk_fini(slab->us_data + (keg->uk_rsize * i),
887 			    keg->uk_size);
888 	}
889 	if (keg->uk_flags & UMA_ZONE_OFFPAGE)
890 		zone_free_item(keg->uk_slabzone, slab, NULL, SKIP_NONE);
891 	keg->uk_freef(mem, PAGE_SIZE * keg->uk_ppera, flags);
892 	uma_total_dec(PAGE_SIZE * keg->uk_ppera);
893 }
894 
895 /*
896  * Frees pages from a keg back to the system.  This is done on demand from
897  * the pageout daemon.
898  *
899  * Returns nothing.
900  */
901 static void
902 keg_drain(uma_keg_t keg)
903 {
904 	struct slabhead freeslabs = { 0 };
905 	uma_domain_t dom;
906 	uma_slab_t slab, tmp;
907 	int i;
908 
909 	/*
910 	 * We don't want to take pages from statically allocated kegs at this
911 	 * time
912 	 */
913 	if (keg->uk_flags & UMA_ZONE_NOFREE || keg->uk_freef == NULL)
914 		return;
915 
916 	CTR3(KTR_UMA, "keg_drain %s(%p) free items: %u",
917 	    keg->uk_name, keg, keg->uk_free);
918 	KEG_LOCK(keg);
919 	if (keg->uk_free == 0)
920 		goto finished;
921 
922 	for (i = 0; i < vm_ndomains; i++) {
923 		dom = &keg->uk_domain[i];
924 		LIST_FOREACH_SAFE(slab, &dom->ud_free_slab, us_link, tmp) {
925 			/* We have nowhere to free these to. */
926 			if (slab->us_flags & UMA_SLAB_BOOT)
927 				continue;
928 
929 			LIST_REMOVE(slab, us_link);
930 			keg->uk_pages -= keg->uk_ppera;
931 			keg->uk_free -= keg->uk_ipers;
932 
933 			if (keg->uk_flags & UMA_ZONE_HASH)
934 				UMA_HASH_REMOVE(&keg->uk_hash, slab,
935 				    slab->us_data);
936 
937 			SLIST_INSERT_HEAD(&freeslabs, slab, us_hlink);
938 		}
939 	}
940 
941 finished:
942 	KEG_UNLOCK(keg);
943 
944 	while ((slab = SLIST_FIRST(&freeslabs)) != NULL) {
945 		SLIST_REMOVE(&freeslabs, slab, uma_slab, us_hlink);
946 		keg_free_slab(keg, slab, keg->uk_ipers);
947 	}
948 }
949 
950 static void
951 zone_drain_wait(uma_zone_t zone, int waitok)
952 {
953 
954 	/*
955 	 * Set draining to interlock with zone_dtor() so we can release our
956 	 * locks as we go.  Only dtor() should do a WAITOK call since it
957 	 * is the only call that knows the structure will still be available
958 	 * when it wakes up.
959 	 */
960 	ZONE_LOCK(zone);
961 	while (zone->uz_flags & UMA_ZFLAG_DRAINING) {
962 		if (waitok == M_NOWAIT)
963 			goto out;
964 		msleep(zone, zone->uz_lockptr, PVM, "zonedrain", 1);
965 	}
966 	zone->uz_flags |= UMA_ZFLAG_DRAINING;
967 	bucket_cache_drain(zone);
968 	ZONE_UNLOCK(zone);
969 	/*
970 	 * The DRAINING flag protects us from being freed while
971 	 * we're running.  Normally the uma_rwlock would protect us but we
972 	 * must be able to release and acquire the right lock for each keg.
973 	 */
974 	zone_foreach_keg(zone, &keg_drain);
975 	ZONE_LOCK(zone);
976 	zone->uz_flags &= ~UMA_ZFLAG_DRAINING;
977 	wakeup(zone);
978 out:
979 	ZONE_UNLOCK(zone);
980 }
981 
982 void
983 zone_drain(uma_zone_t zone)
984 {
985 
986 	zone_drain_wait(zone, M_NOWAIT);
987 }
988 
989 /*
990  * Allocate a new slab for a keg.  This does not insert the slab onto a list.
991  *
992  * Arguments:
993  *	wait  Shall we wait?
994  *
995  * Returns:
996  *	The slab that was allocated or NULL if there is no memory and the
997  *	caller specified M_NOWAIT.
998  */
999 static uma_slab_t
1000 keg_alloc_slab(uma_keg_t keg, uma_zone_t zone, int domain, int wait)
1001 {
1002 	uma_alloc allocf;
1003 	uma_slab_t slab;
1004 	unsigned long size;
1005 	uint8_t *mem;
1006 	uint8_t flags;
1007 	int i;
1008 
1009 	KASSERT(domain >= 0 && domain < vm_ndomains,
1010 	    ("keg_alloc_slab: domain %d out of range", domain));
1011 	mtx_assert(&keg->uk_lock, MA_OWNED);
1012 	slab = NULL;
1013 	mem = NULL;
1014 
1015 	allocf = keg->uk_allocf;
1016 	KEG_UNLOCK(keg);
1017 	size = keg->uk_ppera * PAGE_SIZE;
1018 
1019 	if (keg->uk_flags & UMA_ZONE_OFFPAGE) {
1020 		slab = zone_alloc_item(keg->uk_slabzone, NULL, domain, wait);
1021 		if (slab == NULL)
1022 			goto out;
1023 	}
1024 
1025 	/*
1026 	 * This reproduces the old vm_zone behavior of zero filling pages the
1027 	 * first time they are added to a zone.
1028 	 *
1029 	 * Malloced items are zeroed in uma_zalloc.
1030 	 */
1031 
1032 	if ((keg->uk_flags & UMA_ZONE_MALLOC) == 0)
1033 		wait |= M_ZERO;
1034 	else
1035 		wait &= ~M_ZERO;
1036 
1037 	if (keg->uk_flags & UMA_ZONE_NODUMP)
1038 		wait |= M_NODUMP;
1039 
1040 	/* zone is passed for legacy reasons. */
1041 	mem = allocf(zone, size, domain, &flags, wait);
1042 	if (mem == NULL) {
1043 		if (keg->uk_flags & UMA_ZONE_OFFPAGE)
1044 			zone_free_item(keg->uk_slabzone, slab, NULL, SKIP_NONE);
1045 		slab = NULL;
1046 		goto out;
1047 	}
1048 	uma_total_inc(size);
1049 
1050 	/* Point the slab into the allocated memory */
1051 	if (!(keg->uk_flags & UMA_ZONE_OFFPAGE))
1052 		slab = (uma_slab_t )(mem + keg->uk_pgoff);
1053 
1054 	if (keg->uk_flags & UMA_ZONE_VTOSLAB)
1055 		for (i = 0; i < keg->uk_ppera; i++)
1056 			vsetslab((vm_offset_t)mem + (i * PAGE_SIZE), slab);
1057 
1058 	slab->us_keg = keg;
1059 	slab->us_data = mem;
1060 	slab->us_freecount = keg->uk_ipers;
1061 	slab->us_flags = flags;
1062 	slab->us_domain = domain;
1063 	BIT_FILL(SLAB_SETSIZE, &slab->us_free);
1064 #ifdef INVARIANTS
1065 	BIT_ZERO(SLAB_SETSIZE, &slab->us_debugfree);
1066 #endif
1067 
1068 	if (keg->uk_init != NULL) {
1069 		for (i = 0; i < keg->uk_ipers; i++)
1070 			if (keg->uk_init(slab->us_data + (keg->uk_rsize * i),
1071 			    keg->uk_size, wait) != 0)
1072 				break;
1073 		if (i != keg->uk_ipers) {
1074 			keg_free_slab(keg, slab, i);
1075 			slab = NULL;
1076 			goto out;
1077 		}
1078 	}
1079 out:
1080 	KEG_LOCK(keg);
1081 
1082 	CTR3(KTR_UMA, "keg_alloc_slab: allocated slab %p for %s(%p)",
1083 	    slab, keg->uk_name, keg);
1084 
1085 	if (slab != NULL) {
1086 		if (keg->uk_flags & UMA_ZONE_HASH)
1087 			UMA_HASH_INSERT(&keg->uk_hash, slab, mem);
1088 
1089 		keg->uk_pages += keg->uk_ppera;
1090 		keg->uk_free += keg->uk_ipers;
1091 	}
1092 
1093 	return (slab);
1094 }
1095 
1096 /*
1097  * This function is intended to be used early on in place of page_alloc() so
1098  * that we may use the boot time page cache to satisfy allocations before
1099  * the VM is ready.
1100  */
1101 static void *
1102 startup_alloc(uma_zone_t zone, vm_size_t bytes, int domain, uint8_t *pflag,
1103     int wait)
1104 {
1105 	uma_keg_t keg;
1106 	void *mem;
1107 	int pages;
1108 
1109 	keg = zone_first_keg(zone);
1110 
1111 	/*
1112 	 * If we are in BOOT_BUCKETS or higher, than switch to real
1113 	 * allocator.  Zones with page sized slabs switch at BOOT_PAGEALLOC.
1114 	 */
1115 	switch (booted) {
1116 		case BOOT_COLD:
1117 		case BOOT_STRAPPED:
1118 			break;
1119 		case BOOT_PAGEALLOC:
1120 			if (keg->uk_ppera > 1)
1121 				break;
1122 		case BOOT_BUCKETS:
1123 		case BOOT_RUNNING:
1124 #ifdef UMA_MD_SMALL_ALLOC
1125 			keg->uk_allocf = (keg->uk_ppera > 1) ?
1126 			    page_alloc : uma_small_alloc;
1127 #else
1128 			keg->uk_allocf = page_alloc;
1129 #endif
1130 			return keg->uk_allocf(zone, bytes, domain, pflag, wait);
1131 	}
1132 
1133 	/*
1134 	 * Check our small startup cache to see if it has pages remaining.
1135 	 */
1136 	pages = howmany(bytes, PAGE_SIZE);
1137 	KASSERT(pages > 0, ("%s can't reserve 0 pages", __func__));
1138 	if (pages > boot_pages)
1139 		panic("UMA zone \"%s\": Increase vm.boot_pages", zone->uz_name);
1140 #ifdef DIAGNOSTIC
1141 	printf("%s from \"%s\", %d boot pages left\n", __func__, zone->uz_name,
1142 	    boot_pages);
1143 #endif
1144 	mem = bootmem;
1145 	boot_pages -= pages;
1146 	bootmem += pages * PAGE_SIZE;
1147 	*pflag = UMA_SLAB_BOOT;
1148 
1149 	return (mem);
1150 }
1151 
1152 /*
1153  * Allocates a number of pages from the system
1154  *
1155  * Arguments:
1156  *	bytes  The number of bytes requested
1157  *	wait  Shall we wait?
1158  *
1159  * Returns:
1160  *	A pointer to the alloced memory or possibly
1161  *	NULL if M_NOWAIT is set.
1162  */
1163 static void *
1164 page_alloc(uma_zone_t zone, vm_size_t bytes, int domain, uint8_t *pflag,
1165     int wait)
1166 {
1167 	void *p;	/* Returned page */
1168 
1169 	*pflag = UMA_SLAB_KERNEL;
1170 	p = (void *) kmem_malloc_domain(kernel_arena, domain, bytes, wait);
1171 
1172 	return (p);
1173 }
1174 
1175 /*
1176  * Allocates a number of pages from within an object
1177  *
1178  * Arguments:
1179  *	bytes  The number of bytes requested
1180  *	wait   Shall we wait?
1181  *
1182  * Returns:
1183  *	A pointer to the alloced memory or possibly
1184  *	NULL if M_NOWAIT is set.
1185  */
1186 static void *
1187 noobj_alloc(uma_zone_t zone, vm_size_t bytes, int domain, uint8_t *flags,
1188     int wait)
1189 {
1190 	TAILQ_HEAD(, vm_page) alloctail;
1191 	u_long npages;
1192 	vm_offset_t retkva, zkva;
1193 	vm_page_t p, p_next;
1194 	uma_keg_t keg;
1195 
1196 	TAILQ_INIT(&alloctail);
1197 	keg = zone_first_keg(zone);
1198 
1199 	npages = howmany(bytes, PAGE_SIZE);
1200 	while (npages > 0) {
1201 		p = vm_page_alloc_domain(NULL, 0, domain, VM_ALLOC_INTERRUPT |
1202 		    VM_ALLOC_WIRED | VM_ALLOC_NOOBJ |
1203 		    ((wait & M_WAITOK) != 0 ? VM_ALLOC_WAITOK :
1204 		    VM_ALLOC_NOWAIT));
1205 		if (p != NULL) {
1206 			/*
1207 			 * Since the page does not belong to an object, its
1208 			 * listq is unused.
1209 			 */
1210 			TAILQ_INSERT_TAIL(&alloctail, p, listq);
1211 			npages--;
1212 			continue;
1213 		}
1214 		/*
1215 		 * Page allocation failed, free intermediate pages and
1216 		 * exit.
1217 		 */
1218 		TAILQ_FOREACH_SAFE(p, &alloctail, listq, p_next) {
1219 			vm_page_unwire(p, PQ_NONE);
1220 			vm_page_free(p);
1221 		}
1222 		return (NULL);
1223 	}
1224 	*flags = UMA_SLAB_PRIV;
1225 	zkva = keg->uk_kva +
1226 	    atomic_fetchadd_long(&keg->uk_offset, round_page(bytes));
1227 	retkva = zkva;
1228 	TAILQ_FOREACH(p, &alloctail, listq) {
1229 		pmap_qenter(zkva, &p, 1);
1230 		zkva += PAGE_SIZE;
1231 	}
1232 
1233 	return ((void *)retkva);
1234 }
1235 
1236 /*
1237  * Frees a number of pages to the system
1238  *
1239  * Arguments:
1240  *	mem   A pointer to the memory to be freed
1241  *	size  The size of the memory being freed
1242  *	flags The original p->us_flags field
1243  *
1244  * Returns:
1245  *	Nothing
1246  */
1247 static void
1248 page_free(void *mem, vm_size_t size, uint8_t flags)
1249 {
1250 	struct vmem *vmem;
1251 
1252 	if (flags & UMA_SLAB_KERNEL)
1253 		vmem = kernel_arena;
1254 	else
1255 		panic("UMA: page_free used with invalid flags %x", flags);
1256 
1257 	kmem_free(vmem, (vm_offset_t)mem, size);
1258 }
1259 
1260 /*
1261  * Zero fill initializer
1262  *
1263  * Arguments/Returns follow uma_init specifications
1264  */
1265 static int
1266 zero_init(void *mem, int size, int flags)
1267 {
1268 	bzero(mem, size);
1269 	return (0);
1270 }
1271 
1272 /*
1273  * Finish creating a small uma keg.  This calculates ipers, and the keg size.
1274  *
1275  * Arguments
1276  *	keg  The zone we should initialize
1277  *
1278  * Returns
1279  *	Nothing
1280  */
1281 static void
1282 keg_small_init(uma_keg_t keg)
1283 {
1284 	u_int rsize;
1285 	u_int memused;
1286 	u_int wastedspace;
1287 	u_int shsize;
1288 	u_int slabsize;
1289 
1290 	if (keg->uk_flags & UMA_ZONE_PCPU) {
1291 		u_int ncpus = (mp_maxid + 1) ? (mp_maxid + 1) : MAXCPU;
1292 
1293 		slabsize = sizeof(struct pcpu);
1294 		keg->uk_ppera = howmany(ncpus * sizeof(struct pcpu),
1295 		    PAGE_SIZE);
1296 	} else {
1297 		slabsize = UMA_SLAB_SIZE;
1298 		keg->uk_ppera = 1;
1299 	}
1300 
1301 	/*
1302 	 * Calculate the size of each allocation (rsize) according to
1303 	 * alignment.  If the requested size is smaller than we have
1304 	 * allocation bits for we round it up.
1305 	 */
1306 	rsize = keg->uk_size;
1307 	if (rsize < slabsize / SLAB_SETSIZE)
1308 		rsize = slabsize / SLAB_SETSIZE;
1309 	if (rsize & keg->uk_align)
1310 		rsize = (rsize & ~keg->uk_align) + (keg->uk_align + 1);
1311 	keg->uk_rsize = rsize;
1312 
1313 	KASSERT((keg->uk_flags & UMA_ZONE_PCPU) == 0 ||
1314 	    keg->uk_rsize < sizeof(struct pcpu),
1315 	    ("%s: size %u too large", __func__, keg->uk_rsize));
1316 
1317 	if (keg->uk_flags & UMA_ZONE_OFFPAGE)
1318 		shsize = 0;
1319 	else
1320 		shsize = sizeof(struct uma_slab);
1321 
1322 	if (rsize <= slabsize - shsize)
1323 		keg->uk_ipers = (slabsize - shsize) / rsize;
1324 	else {
1325 		/* Handle special case when we have 1 item per slab, so
1326 		 * alignment requirement can be relaxed. */
1327 		KASSERT(keg->uk_size <= slabsize - shsize,
1328 		    ("%s: size %u greater than slab", __func__, keg->uk_size));
1329 		keg->uk_ipers = 1;
1330 	}
1331 	KASSERT(keg->uk_ipers > 0 && keg->uk_ipers <= SLAB_SETSIZE,
1332 	    ("%s: keg->uk_ipers %u", __func__, keg->uk_ipers));
1333 
1334 	memused = keg->uk_ipers * rsize + shsize;
1335 	wastedspace = slabsize - memused;
1336 
1337 	/*
1338 	 * We can't do OFFPAGE if we're internal or if we've been
1339 	 * asked to not go to the VM for buckets.  If we do this we
1340 	 * may end up going to the VM  for slabs which we do not
1341 	 * want to do if we're UMA_ZFLAG_CACHEONLY as a result
1342 	 * of UMA_ZONE_VM, which clearly forbids it.
1343 	 */
1344 	if ((keg->uk_flags & UMA_ZFLAG_INTERNAL) ||
1345 	    (keg->uk_flags & UMA_ZFLAG_CACHEONLY))
1346 		return;
1347 
1348 	/*
1349 	 * See if using an OFFPAGE slab will limit our waste.  Only do
1350 	 * this if it permits more items per-slab.
1351 	 *
1352 	 * XXX We could try growing slabsize to limit max waste as well.
1353 	 * Historically this was not done because the VM could not
1354 	 * efficiently handle contiguous allocations.
1355 	 */
1356 	if ((wastedspace >= slabsize / UMA_MAX_WASTE) &&
1357 	    (keg->uk_ipers < (slabsize / keg->uk_rsize))) {
1358 		keg->uk_ipers = slabsize / keg->uk_rsize;
1359 		KASSERT(keg->uk_ipers > 0 && keg->uk_ipers <= SLAB_SETSIZE,
1360 		    ("%s: keg->uk_ipers %u", __func__, keg->uk_ipers));
1361 		CTR6(KTR_UMA, "UMA decided we need offpage slab headers for "
1362 		    "keg: %s(%p), calculated wastedspace = %d, "
1363 		    "maximum wasted space allowed = %d, "
1364 		    "calculated ipers = %d, "
1365 		    "new wasted space = %d\n", keg->uk_name, keg, wastedspace,
1366 		    slabsize / UMA_MAX_WASTE, keg->uk_ipers,
1367 		    slabsize - keg->uk_ipers * keg->uk_rsize);
1368 		keg->uk_flags |= UMA_ZONE_OFFPAGE;
1369 	}
1370 
1371 	if ((keg->uk_flags & UMA_ZONE_OFFPAGE) &&
1372 	    (keg->uk_flags & UMA_ZONE_VTOSLAB) == 0)
1373 		keg->uk_flags |= UMA_ZONE_HASH;
1374 }
1375 
1376 /*
1377  * Finish creating a large (> UMA_SLAB_SIZE) uma kegs.  Just give in and do
1378  * OFFPAGE for now.  When I can allow for more dynamic slab sizes this will be
1379  * more complicated.
1380  *
1381  * Arguments
1382  *	keg  The keg we should initialize
1383  *
1384  * Returns
1385  *	Nothing
1386  */
1387 static void
1388 keg_large_init(uma_keg_t keg)
1389 {
1390 	u_int shsize;
1391 
1392 	KASSERT(keg != NULL, ("Keg is null in keg_large_init"));
1393 	KASSERT((keg->uk_flags & UMA_ZFLAG_CACHEONLY) == 0,
1394 	    ("keg_large_init: Cannot large-init a UMA_ZFLAG_CACHEONLY keg"));
1395 	KASSERT((keg->uk_flags & UMA_ZONE_PCPU) == 0,
1396 	    ("%s: Cannot large-init a UMA_ZONE_PCPU keg", __func__));
1397 
1398 	keg->uk_ppera = howmany(keg->uk_size, PAGE_SIZE);
1399 	keg->uk_ipers = 1;
1400 	keg->uk_rsize = keg->uk_size;
1401 
1402 	/* Check whether we have enough space to not do OFFPAGE. */
1403 	if ((keg->uk_flags & UMA_ZONE_OFFPAGE) == 0) {
1404 		shsize = sizeof(struct uma_slab);
1405 		if (shsize & UMA_ALIGN_PTR)
1406 			shsize = (shsize & ~UMA_ALIGN_PTR) +
1407 			    (UMA_ALIGN_PTR + 1);
1408 
1409 		if (PAGE_SIZE * keg->uk_ppera - keg->uk_rsize < shsize) {
1410 			/*
1411 			 * We can't do OFFPAGE if we're internal, in which case
1412 			 * we need an extra page per allocation to contain the
1413 			 * slab header.
1414 			 */
1415 			if ((keg->uk_flags & UMA_ZFLAG_INTERNAL) == 0)
1416 				keg->uk_flags |= UMA_ZONE_OFFPAGE;
1417 			else
1418 				keg->uk_ppera++;
1419 		}
1420 	}
1421 
1422 	if ((keg->uk_flags & UMA_ZONE_OFFPAGE) &&
1423 	    (keg->uk_flags & UMA_ZONE_VTOSLAB) == 0)
1424 		keg->uk_flags |= UMA_ZONE_HASH;
1425 }
1426 
1427 static void
1428 keg_cachespread_init(uma_keg_t keg)
1429 {
1430 	int alignsize;
1431 	int trailer;
1432 	int pages;
1433 	int rsize;
1434 
1435 	KASSERT((keg->uk_flags & UMA_ZONE_PCPU) == 0,
1436 	    ("%s: Cannot cachespread-init a UMA_ZONE_PCPU keg", __func__));
1437 
1438 	alignsize = keg->uk_align + 1;
1439 	rsize = keg->uk_size;
1440 	/*
1441 	 * We want one item to start on every align boundary in a page.  To
1442 	 * do this we will span pages.  We will also extend the item by the
1443 	 * size of align if it is an even multiple of align.  Otherwise, it
1444 	 * would fall on the same boundary every time.
1445 	 */
1446 	if (rsize & keg->uk_align)
1447 		rsize = (rsize & ~keg->uk_align) + alignsize;
1448 	if ((rsize & alignsize) == 0)
1449 		rsize += alignsize;
1450 	trailer = rsize - keg->uk_size;
1451 	pages = (rsize * (PAGE_SIZE / alignsize)) / PAGE_SIZE;
1452 	pages = MIN(pages, (128 * 1024) / PAGE_SIZE);
1453 	keg->uk_rsize = rsize;
1454 	keg->uk_ppera = pages;
1455 	keg->uk_ipers = ((pages * PAGE_SIZE) + trailer) / rsize;
1456 	keg->uk_flags |= UMA_ZONE_OFFPAGE | UMA_ZONE_VTOSLAB;
1457 	KASSERT(keg->uk_ipers <= SLAB_SETSIZE,
1458 	    ("%s: keg->uk_ipers too high(%d) increase max_ipers", __func__,
1459 	    keg->uk_ipers));
1460 }
1461 
1462 /*
1463  * Keg header ctor.  This initializes all fields, locks, etc.  And inserts
1464  * the keg onto the global keg list.
1465  *
1466  * Arguments/Returns follow uma_ctor specifications
1467  *	udata  Actually uma_kctor_args
1468  */
1469 static int
1470 keg_ctor(void *mem, int size, void *udata, int flags)
1471 {
1472 	struct uma_kctor_args *arg = udata;
1473 	uma_keg_t keg = mem;
1474 	uma_zone_t zone;
1475 
1476 	bzero(keg, size);
1477 	keg->uk_size = arg->size;
1478 	keg->uk_init = arg->uminit;
1479 	keg->uk_fini = arg->fini;
1480 	keg->uk_align = arg->align;
1481 	keg->uk_cursor = 0;
1482 	keg->uk_free = 0;
1483 	keg->uk_reserve = 0;
1484 	keg->uk_pages = 0;
1485 	keg->uk_flags = arg->flags;
1486 	keg->uk_slabzone = NULL;
1487 
1488 	/*
1489 	 * The master zone is passed to us at keg-creation time.
1490 	 */
1491 	zone = arg->zone;
1492 	keg->uk_name = zone->uz_name;
1493 
1494 	if (arg->flags & UMA_ZONE_VM)
1495 		keg->uk_flags |= UMA_ZFLAG_CACHEONLY;
1496 
1497 	if (arg->flags & UMA_ZONE_ZINIT)
1498 		keg->uk_init = zero_init;
1499 
1500 	if (arg->flags & UMA_ZONE_MALLOC)
1501 		keg->uk_flags |= UMA_ZONE_VTOSLAB;
1502 
1503 	if (arg->flags & UMA_ZONE_PCPU)
1504 #ifdef SMP
1505 		keg->uk_flags |= UMA_ZONE_OFFPAGE;
1506 #else
1507 		keg->uk_flags &= ~UMA_ZONE_PCPU;
1508 #endif
1509 
1510 	if (keg->uk_flags & UMA_ZONE_CACHESPREAD) {
1511 		keg_cachespread_init(keg);
1512 	} else {
1513 		if (keg->uk_size > UMA_SLAB_SPACE)
1514 			keg_large_init(keg);
1515 		else
1516 			keg_small_init(keg);
1517 	}
1518 
1519 	if (keg->uk_flags & UMA_ZONE_OFFPAGE)
1520 		keg->uk_slabzone = slabzone;
1521 
1522 	/*
1523 	 * If we haven't booted yet we need allocations to go through the
1524 	 * startup cache until the vm is ready.
1525 	 */
1526 	if (booted < BOOT_PAGEALLOC)
1527 		keg->uk_allocf = startup_alloc;
1528 #ifdef UMA_MD_SMALL_ALLOC
1529 	else if (keg->uk_ppera == 1)
1530 		keg->uk_allocf = uma_small_alloc;
1531 #endif
1532 	else
1533 		keg->uk_allocf = page_alloc;
1534 #ifdef UMA_MD_SMALL_ALLOC
1535 	if (keg->uk_ppera == 1)
1536 		keg->uk_freef = uma_small_free;
1537 	else
1538 #endif
1539 		keg->uk_freef = page_free;
1540 
1541 	/*
1542 	 * Initialize keg's lock
1543 	 */
1544 	KEG_LOCK_INIT(keg, (arg->flags & UMA_ZONE_MTXCLASS));
1545 
1546 	/*
1547 	 * If we're putting the slab header in the actual page we need to
1548 	 * figure out where in each page it goes.  This calculates a right
1549 	 * justified offset into the memory on an ALIGN_PTR boundary.
1550 	 */
1551 	if (!(keg->uk_flags & UMA_ZONE_OFFPAGE)) {
1552 		u_int totsize;
1553 
1554 		/* Size of the slab struct and free list */
1555 		totsize = sizeof(struct uma_slab);
1556 
1557 		if (totsize & UMA_ALIGN_PTR)
1558 			totsize = (totsize & ~UMA_ALIGN_PTR) +
1559 			    (UMA_ALIGN_PTR + 1);
1560 		keg->uk_pgoff = (PAGE_SIZE * keg->uk_ppera) - totsize;
1561 
1562 		/*
1563 		 * The only way the following is possible is if with our
1564 		 * UMA_ALIGN_PTR adjustments we are now bigger than
1565 		 * UMA_SLAB_SIZE.  I haven't checked whether this is
1566 		 * mathematically possible for all cases, so we make
1567 		 * sure here anyway.
1568 		 */
1569 		totsize = keg->uk_pgoff + sizeof(struct uma_slab);
1570 		if (totsize > PAGE_SIZE * keg->uk_ppera) {
1571 			printf("zone %s ipers %d rsize %d size %d\n",
1572 			    zone->uz_name, keg->uk_ipers, keg->uk_rsize,
1573 			    keg->uk_size);
1574 			panic("UMA slab won't fit.");
1575 		}
1576 	}
1577 
1578 	if (keg->uk_flags & UMA_ZONE_HASH)
1579 		hash_alloc(&keg->uk_hash);
1580 
1581 	CTR5(KTR_UMA, "keg_ctor %p zone %s(%p) out %d free %d\n",
1582 	    keg, zone->uz_name, zone,
1583 	    (keg->uk_pages / keg->uk_ppera) * keg->uk_ipers - keg->uk_free,
1584 	    keg->uk_free);
1585 
1586 	LIST_INSERT_HEAD(&keg->uk_zones, zone, uz_link);
1587 
1588 	rw_wlock(&uma_rwlock);
1589 	LIST_INSERT_HEAD(&uma_kegs, keg, uk_link);
1590 	rw_wunlock(&uma_rwlock);
1591 	return (0);
1592 }
1593 
1594 /*
1595  * Zone header ctor.  This initializes all fields, locks, etc.
1596  *
1597  * Arguments/Returns follow uma_ctor specifications
1598  *	udata  Actually uma_zctor_args
1599  */
1600 static int
1601 zone_ctor(void *mem, int size, void *udata, int flags)
1602 {
1603 	struct uma_zctor_args *arg = udata;
1604 	uma_zone_t zone = mem;
1605 	uma_zone_t z;
1606 	uma_keg_t keg;
1607 
1608 	bzero(zone, size);
1609 	zone->uz_name = arg->name;
1610 	zone->uz_ctor = arg->ctor;
1611 	zone->uz_dtor = arg->dtor;
1612 	zone->uz_slab = zone_fetch_slab;
1613 	zone->uz_init = NULL;
1614 	zone->uz_fini = NULL;
1615 	zone->uz_allocs = 0;
1616 	zone->uz_frees = 0;
1617 	zone->uz_fails = 0;
1618 	zone->uz_sleeps = 0;
1619 	zone->uz_count = 0;
1620 	zone->uz_count_min = 0;
1621 	zone->uz_flags = 0;
1622 	zone->uz_warning = NULL;
1623 	/* The domain structures follow the cpu structures. */
1624 	zone->uz_domain = (struct uma_zone_domain *)&zone->uz_cpu[mp_ncpus];
1625 	timevalclear(&zone->uz_ratecheck);
1626 	keg = arg->keg;
1627 
1628 	ZONE_LOCK_INIT(zone, (arg->flags & UMA_ZONE_MTXCLASS));
1629 
1630 	/*
1631 	 * This is a pure cache zone, no kegs.
1632 	 */
1633 	if (arg->import) {
1634 		if (arg->flags & UMA_ZONE_VM)
1635 			arg->flags |= UMA_ZFLAG_CACHEONLY;
1636 		zone->uz_flags = arg->flags;
1637 		zone->uz_size = arg->size;
1638 		zone->uz_import = arg->import;
1639 		zone->uz_release = arg->release;
1640 		zone->uz_arg = arg->arg;
1641 		zone->uz_lockptr = &zone->uz_lock;
1642 		rw_wlock(&uma_rwlock);
1643 		LIST_INSERT_HEAD(&uma_cachezones, zone, uz_link);
1644 		rw_wunlock(&uma_rwlock);
1645 		goto out;
1646 	}
1647 
1648 	/*
1649 	 * Use the regular zone/keg/slab allocator.
1650 	 */
1651 	zone->uz_import = (uma_import)zone_import;
1652 	zone->uz_release = (uma_release)zone_release;
1653 	zone->uz_arg = zone;
1654 
1655 	if (arg->flags & UMA_ZONE_SECONDARY) {
1656 		KASSERT(arg->keg != NULL, ("Secondary zone on zero'd keg"));
1657 		zone->uz_init = arg->uminit;
1658 		zone->uz_fini = arg->fini;
1659 		zone->uz_lockptr = &keg->uk_lock;
1660 		zone->uz_flags |= UMA_ZONE_SECONDARY;
1661 		rw_wlock(&uma_rwlock);
1662 		ZONE_LOCK(zone);
1663 		LIST_FOREACH(z, &keg->uk_zones, uz_link) {
1664 			if (LIST_NEXT(z, uz_link) == NULL) {
1665 				LIST_INSERT_AFTER(z, zone, uz_link);
1666 				break;
1667 			}
1668 		}
1669 		ZONE_UNLOCK(zone);
1670 		rw_wunlock(&uma_rwlock);
1671 	} else if (keg == NULL) {
1672 		if ((keg = uma_kcreate(zone, arg->size, arg->uminit, arg->fini,
1673 		    arg->align, arg->flags)) == NULL)
1674 			return (ENOMEM);
1675 	} else {
1676 		struct uma_kctor_args karg;
1677 		int error;
1678 
1679 		/* We should only be here from uma_startup() */
1680 		karg.size = arg->size;
1681 		karg.uminit = arg->uminit;
1682 		karg.fini = arg->fini;
1683 		karg.align = arg->align;
1684 		karg.flags = arg->flags;
1685 		karg.zone = zone;
1686 		error = keg_ctor(arg->keg, sizeof(struct uma_keg), &karg,
1687 		    flags);
1688 		if (error)
1689 			return (error);
1690 	}
1691 
1692 	/*
1693 	 * Link in the first keg.
1694 	 */
1695 	zone->uz_klink.kl_keg = keg;
1696 	LIST_INSERT_HEAD(&zone->uz_kegs, &zone->uz_klink, kl_link);
1697 	zone->uz_lockptr = &keg->uk_lock;
1698 	zone->uz_size = keg->uk_size;
1699 	zone->uz_flags |= (keg->uk_flags &
1700 	    (UMA_ZONE_INHERIT | UMA_ZFLAG_INHERIT));
1701 
1702 	/*
1703 	 * Some internal zones don't have room allocated for the per cpu
1704 	 * caches.  If we're internal, bail out here.
1705 	 */
1706 	if (keg->uk_flags & UMA_ZFLAG_INTERNAL) {
1707 		KASSERT((zone->uz_flags & UMA_ZONE_SECONDARY) == 0,
1708 		    ("Secondary zone requested UMA_ZFLAG_INTERNAL"));
1709 		return (0);
1710 	}
1711 
1712 out:
1713 	KASSERT((arg->flags & (UMA_ZONE_MAXBUCKET | UMA_ZONE_NOBUCKET)) !=
1714 	    (UMA_ZONE_MAXBUCKET | UMA_ZONE_NOBUCKET),
1715 	    ("Invalid zone flag combination"));
1716 	if ((arg->flags & UMA_ZONE_MAXBUCKET) != 0)
1717 		zone->uz_count = BUCKET_MAX;
1718 	else if ((arg->flags & UMA_ZONE_NOBUCKET) != 0)
1719 		zone->uz_count = 0;
1720 	else
1721 		zone->uz_count = bucket_select(zone->uz_size);
1722 	zone->uz_count_min = zone->uz_count;
1723 
1724 	return (0);
1725 }
1726 
1727 /*
1728  * Keg header dtor.  This frees all data, destroys locks, frees the hash
1729  * table and removes the keg from the global list.
1730  *
1731  * Arguments/Returns follow uma_dtor specifications
1732  *	udata  unused
1733  */
1734 static void
1735 keg_dtor(void *arg, int size, void *udata)
1736 {
1737 	uma_keg_t keg;
1738 
1739 	keg = (uma_keg_t)arg;
1740 	KEG_LOCK(keg);
1741 	if (keg->uk_free != 0) {
1742 		printf("Freed UMA keg (%s) was not empty (%d items). "
1743 		    " Lost %d pages of memory.\n",
1744 		    keg->uk_name ? keg->uk_name : "",
1745 		    keg->uk_free, keg->uk_pages);
1746 	}
1747 	KEG_UNLOCK(keg);
1748 
1749 	hash_free(&keg->uk_hash);
1750 
1751 	KEG_LOCK_FINI(keg);
1752 }
1753 
1754 /*
1755  * Zone header dtor.
1756  *
1757  * Arguments/Returns follow uma_dtor specifications
1758  *	udata  unused
1759  */
1760 static void
1761 zone_dtor(void *arg, int size, void *udata)
1762 {
1763 	uma_klink_t klink;
1764 	uma_zone_t zone;
1765 	uma_keg_t keg;
1766 
1767 	zone = (uma_zone_t)arg;
1768 	keg = zone_first_keg(zone);
1769 
1770 	if (!(zone->uz_flags & UMA_ZFLAG_INTERNAL))
1771 		cache_drain(zone);
1772 
1773 	rw_wlock(&uma_rwlock);
1774 	LIST_REMOVE(zone, uz_link);
1775 	rw_wunlock(&uma_rwlock);
1776 	/*
1777 	 * XXX there are some races here where
1778 	 * the zone can be drained but zone lock
1779 	 * released and then refilled before we
1780 	 * remove it... we dont care for now
1781 	 */
1782 	zone_drain_wait(zone, M_WAITOK);
1783 	/*
1784 	 * Unlink all of our kegs.
1785 	 */
1786 	while ((klink = LIST_FIRST(&zone->uz_kegs)) != NULL) {
1787 		klink->kl_keg = NULL;
1788 		LIST_REMOVE(klink, kl_link);
1789 		if (klink == &zone->uz_klink)
1790 			continue;
1791 		free(klink, M_TEMP);
1792 	}
1793 	/*
1794 	 * We only destroy kegs from non secondary zones.
1795 	 */
1796 	if (keg != NULL && (zone->uz_flags & UMA_ZONE_SECONDARY) == 0)  {
1797 		rw_wlock(&uma_rwlock);
1798 		LIST_REMOVE(keg, uk_link);
1799 		rw_wunlock(&uma_rwlock);
1800 		zone_free_item(kegs, keg, NULL, SKIP_NONE);
1801 	}
1802 	ZONE_LOCK_FINI(zone);
1803 }
1804 
1805 /*
1806  * Traverses every zone in the system and calls a callback
1807  *
1808  * Arguments:
1809  *	zfunc  A pointer to a function which accepts a zone
1810  *		as an argument.
1811  *
1812  * Returns:
1813  *	Nothing
1814  */
1815 static void
1816 zone_foreach(void (*zfunc)(uma_zone_t))
1817 {
1818 	uma_keg_t keg;
1819 	uma_zone_t zone;
1820 
1821 	rw_rlock(&uma_rwlock);
1822 	LIST_FOREACH(keg, &uma_kegs, uk_link) {
1823 		LIST_FOREACH(zone, &keg->uk_zones, uz_link)
1824 			zfunc(zone);
1825 	}
1826 	rw_runlock(&uma_rwlock);
1827 }
1828 
1829 /*
1830  * Count how many pages do we need to bootstrap.  VM supplies
1831  * its need in early zones in the argument, we add up our zones,
1832  * which consist of: UMA Slabs, UMA Hash and 9 Bucket zones. The
1833  * zone of zones and zone of kegs are accounted separately.
1834  */
1835 #define	UMA_BOOT_ZONES	11
1836 /* Zone of zones and zone of kegs have arbitrary alignment. */
1837 #define	UMA_BOOT_ALIGN	32
1838 static int zsize, ksize;
1839 int
1840 uma_startup_count(int vm_zones)
1841 {
1842 	int zones, pages;
1843 
1844 	ksize = sizeof(struct uma_keg) +
1845 	    (sizeof(struct uma_domain) * vm_ndomains);
1846 	zsize = sizeof(struct uma_zone) +
1847 	    (sizeof(struct uma_cache) * (mp_maxid + 1)) +
1848 	    (sizeof(struct uma_zone_domain) * vm_ndomains);
1849 
1850 	/*
1851 	 * Memory for the zone of kegs and its keg,
1852 	 * and for zone of zones.
1853 	 */
1854 	pages = howmany(roundup(zsize, CACHE_LINE_SIZE) * 2 +
1855 	    roundup(ksize, CACHE_LINE_SIZE), PAGE_SIZE);
1856 
1857 #ifdef	UMA_MD_SMALL_ALLOC
1858 	zones = UMA_BOOT_ZONES;
1859 #else
1860 	zones = UMA_BOOT_ZONES + vm_zones;
1861 	vm_zones = 0;
1862 #endif
1863 
1864 	/* Memory for the rest of startup zones, UMA and VM, ... */
1865 	if (zsize > UMA_SLAB_SPACE)
1866 		pages += (zones + vm_zones) *
1867 		    howmany(roundup2(zsize, UMA_BOOT_ALIGN), UMA_SLAB_SIZE);
1868 	else if (roundup2(zsize, UMA_BOOT_ALIGN) > UMA_SLAB_SPACE)
1869 		pages += zones;
1870 	else
1871 		pages += howmany(zones,
1872 		    UMA_SLAB_SPACE / roundup2(zsize, UMA_BOOT_ALIGN));
1873 
1874 	/* ... and their kegs. Note that zone of zones allocates a keg! */
1875 	pages += howmany(zones + 1,
1876 	    UMA_SLAB_SPACE / roundup2(ksize, UMA_BOOT_ALIGN));
1877 
1878 	/*
1879 	 * Most of startup zones are not going to be offpages, that's
1880 	 * why we use UMA_SLAB_SPACE instead of UMA_SLAB_SIZE in all
1881 	 * calculations.  Some large bucket zones will be offpage, and
1882 	 * thus will allocate hashes.  We take conservative approach
1883 	 * and assume that all zones may allocate hash.  This may give
1884 	 * us some positive inaccuracy, usually an extra single page.
1885 	 */
1886 	pages += howmany(zones, UMA_SLAB_SPACE /
1887 	    (sizeof(struct slabhead *) * UMA_HASH_SIZE_INIT));
1888 
1889 	return (pages);
1890 }
1891 
1892 void
1893 uma_startup(void *mem, int npages)
1894 {
1895 	struct uma_zctor_args args;
1896 	uma_keg_t masterkeg;
1897 	uintptr_t m;
1898 
1899 #ifdef DIAGNOSTIC
1900 	printf("Entering %s with %d boot pages configured\n", __func__, npages);
1901 #endif
1902 
1903 	rw_init(&uma_rwlock, "UMA lock");
1904 
1905 	/* Use bootpages memory for the zone of zones and zone of kegs. */
1906 	m = (uintptr_t)mem;
1907 	zones = (uma_zone_t)m;
1908 	m += roundup(zsize, CACHE_LINE_SIZE);
1909 	kegs = (uma_zone_t)m;
1910 	m += roundup(zsize, CACHE_LINE_SIZE);
1911 	masterkeg = (uma_keg_t)m;
1912 	m += roundup(ksize, CACHE_LINE_SIZE);
1913 	m = roundup(m, PAGE_SIZE);
1914 	npages -= (m - (uintptr_t)mem) / PAGE_SIZE;
1915 	mem = (void *)m;
1916 
1917 	/* "manually" create the initial zone */
1918 	memset(&args, 0, sizeof(args));
1919 	args.name = "UMA Kegs";
1920 	args.size = ksize;
1921 	args.ctor = keg_ctor;
1922 	args.dtor = keg_dtor;
1923 	args.uminit = zero_init;
1924 	args.fini = NULL;
1925 	args.keg = masterkeg;
1926 	args.align = UMA_BOOT_ALIGN - 1;
1927 	args.flags = UMA_ZFLAG_INTERNAL;
1928 	zone_ctor(kegs, zsize, &args, M_WAITOK);
1929 
1930 	bootmem = mem;
1931 	boot_pages = npages;
1932 
1933 	args.name = "UMA Zones";
1934 	args.size = zsize;
1935 	args.ctor = zone_ctor;
1936 	args.dtor = zone_dtor;
1937 	args.uminit = zero_init;
1938 	args.fini = NULL;
1939 	args.keg = NULL;
1940 	args.align = UMA_BOOT_ALIGN - 1;
1941 	args.flags = UMA_ZFLAG_INTERNAL;
1942 	zone_ctor(zones, zsize, &args, M_WAITOK);
1943 
1944 	/* Now make a zone for slab headers */
1945 	slabzone = uma_zcreate("UMA Slabs",
1946 				sizeof(struct uma_slab),
1947 				NULL, NULL, NULL, NULL,
1948 				UMA_ALIGN_PTR, UMA_ZFLAG_INTERNAL);
1949 
1950 	hashzone = uma_zcreate("UMA Hash",
1951 	    sizeof(struct slabhead *) * UMA_HASH_SIZE_INIT,
1952 	    NULL, NULL, NULL, NULL,
1953 	    UMA_ALIGN_PTR, UMA_ZFLAG_INTERNAL);
1954 
1955 	bucket_init();
1956 
1957 	booted = BOOT_STRAPPED;
1958 }
1959 
1960 void
1961 uma_startup1(void)
1962 {
1963 
1964 #ifdef DIAGNOSTIC
1965 	printf("Entering %s with %d boot pages left\n", __func__, boot_pages);
1966 #endif
1967 	booted = BOOT_PAGEALLOC;
1968 }
1969 
1970 void
1971 uma_startup2(void)
1972 {
1973 
1974 #ifdef DIAGNOSTIC
1975 	printf("Entering %s with %d boot pages left\n", __func__, boot_pages);
1976 #endif
1977 	booted = BOOT_BUCKETS;
1978 	sx_init(&uma_drain_lock, "umadrain");
1979 	bucket_enable();
1980 }
1981 
1982 /*
1983  * Initialize our callout handle
1984  *
1985  */
1986 static void
1987 uma_startup3(void)
1988 {
1989 
1990 #ifdef INVARIANTS
1991 	TUNABLE_INT_FETCH("vm.debug.divisor", &dbg_divisor);
1992 	uma_dbg_cnt = counter_u64_alloc(M_WAITOK);
1993 	uma_skip_cnt = counter_u64_alloc(M_WAITOK);
1994 #endif
1995 	callout_init(&uma_callout, 1);
1996 	callout_reset(&uma_callout, UMA_TIMEOUT * hz, uma_timeout, NULL);
1997 	booted = BOOT_RUNNING;
1998 }
1999 
2000 static uma_keg_t
2001 uma_kcreate(uma_zone_t zone, size_t size, uma_init uminit, uma_fini fini,
2002 		int align, uint32_t flags)
2003 {
2004 	struct uma_kctor_args args;
2005 
2006 	args.size = size;
2007 	args.uminit = uminit;
2008 	args.fini = fini;
2009 	args.align = (align == UMA_ALIGN_CACHE) ? uma_align_cache : align;
2010 	args.flags = flags;
2011 	args.zone = zone;
2012 	return (zone_alloc_item(kegs, &args, UMA_ANYDOMAIN, M_WAITOK));
2013 }
2014 
2015 /* Public functions */
2016 /* See uma.h */
2017 void
2018 uma_set_align(int align)
2019 {
2020 
2021 	if (align != UMA_ALIGN_CACHE)
2022 		uma_align_cache = align;
2023 }
2024 
2025 /* See uma.h */
2026 uma_zone_t
2027 uma_zcreate(const char *name, size_t size, uma_ctor ctor, uma_dtor dtor,
2028 		uma_init uminit, uma_fini fini, int align, uint32_t flags)
2029 
2030 {
2031 	struct uma_zctor_args args;
2032 	uma_zone_t res;
2033 	bool locked;
2034 
2035 	KASSERT(powerof2(align + 1), ("invalid zone alignment %d for \"%s\"",
2036 	    align, name));
2037 
2038 	/* This stuff is essential for the zone ctor */
2039 	memset(&args, 0, sizeof(args));
2040 	args.name = name;
2041 	args.size = size;
2042 	args.ctor = ctor;
2043 	args.dtor = dtor;
2044 	args.uminit = uminit;
2045 	args.fini = fini;
2046 #ifdef  INVARIANTS
2047 	/*
2048 	 * If a zone is being created with an empty constructor and
2049 	 * destructor, pass UMA constructor/destructor which checks for
2050 	 * memory use after free.
2051 	 */
2052 	if ((!(flags & (UMA_ZONE_ZINIT | UMA_ZONE_NOFREE))) &&
2053 	    ctor == NULL && dtor == NULL && uminit == NULL && fini == NULL) {
2054 		args.ctor = trash_ctor;
2055 		args.dtor = trash_dtor;
2056 		args.uminit = trash_init;
2057 		args.fini = trash_fini;
2058 	}
2059 #endif
2060 	args.align = align;
2061 	args.flags = flags;
2062 	args.keg = NULL;
2063 
2064 	if (booted < BOOT_BUCKETS) {
2065 		locked = false;
2066 	} else {
2067 		sx_slock(&uma_drain_lock);
2068 		locked = true;
2069 	}
2070 	res = zone_alloc_item(zones, &args, UMA_ANYDOMAIN, M_WAITOK);
2071 	if (locked)
2072 		sx_sunlock(&uma_drain_lock);
2073 	return (res);
2074 }
2075 
2076 /* See uma.h */
2077 uma_zone_t
2078 uma_zsecond_create(char *name, uma_ctor ctor, uma_dtor dtor,
2079 		    uma_init zinit, uma_fini zfini, uma_zone_t master)
2080 {
2081 	struct uma_zctor_args args;
2082 	uma_keg_t keg;
2083 	uma_zone_t res;
2084 	bool locked;
2085 
2086 	keg = zone_first_keg(master);
2087 	memset(&args, 0, sizeof(args));
2088 	args.name = name;
2089 	args.size = keg->uk_size;
2090 	args.ctor = ctor;
2091 	args.dtor = dtor;
2092 	args.uminit = zinit;
2093 	args.fini = zfini;
2094 	args.align = keg->uk_align;
2095 	args.flags = keg->uk_flags | UMA_ZONE_SECONDARY;
2096 	args.keg = keg;
2097 
2098 	if (booted < BOOT_BUCKETS) {
2099 		locked = false;
2100 	} else {
2101 		sx_slock(&uma_drain_lock);
2102 		locked = true;
2103 	}
2104 	/* XXX Attaches only one keg of potentially many. */
2105 	res = zone_alloc_item(zones, &args, UMA_ANYDOMAIN, M_WAITOK);
2106 	if (locked)
2107 		sx_sunlock(&uma_drain_lock);
2108 	return (res);
2109 }
2110 
2111 /* See uma.h */
2112 uma_zone_t
2113 uma_zcache_create(char *name, int size, uma_ctor ctor, uma_dtor dtor,
2114 		    uma_init zinit, uma_fini zfini, uma_import zimport,
2115 		    uma_release zrelease, void *arg, int flags)
2116 {
2117 	struct uma_zctor_args args;
2118 
2119 	memset(&args, 0, sizeof(args));
2120 	args.name = name;
2121 	args.size = size;
2122 	args.ctor = ctor;
2123 	args.dtor = dtor;
2124 	args.uminit = zinit;
2125 	args.fini = zfini;
2126 	args.import = zimport;
2127 	args.release = zrelease;
2128 	args.arg = arg;
2129 	args.align = 0;
2130 	args.flags = flags;
2131 
2132 	return (zone_alloc_item(zones, &args, UMA_ANYDOMAIN, M_WAITOK));
2133 }
2134 
2135 static void
2136 zone_lock_pair(uma_zone_t a, uma_zone_t b)
2137 {
2138 	if (a < b) {
2139 		ZONE_LOCK(a);
2140 		mtx_lock_flags(b->uz_lockptr, MTX_DUPOK);
2141 	} else {
2142 		ZONE_LOCK(b);
2143 		mtx_lock_flags(a->uz_lockptr, MTX_DUPOK);
2144 	}
2145 }
2146 
2147 static void
2148 zone_unlock_pair(uma_zone_t a, uma_zone_t b)
2149 {
2150 
2151 	ZONE_UNLOCK(a);
2152 	ZONE_UNLOCK(b);
2153 }
2154 
2155 int
2156 uma_zsecond_add(uma_zone_t zone, uma_zone_t master)
2157 {
2158 	uma_klink_t klink;
2159 	uma_klink_t kl;
2160 	int error;
2161 
2162 	error = 0;
2163 	klink = malloc(sizeof(*klink), M_TEMP, M_WAITOK | M_ZERO);
2164 
2165 	zone_lock_pair(zone, master);
2166 	/*
2167 	 * zone must use vtoslab() to resolve objects and must already be
2168 	 * a secondary.
2169 	 */
2170 	if ((zone->uz_flags & (UMA_ZONE_VTOSLAB | UMA_ZONE_SECONDARY))
2171 	    != (UMA_ZONE_VTOSLAB | UMA_ZONE_SECONDARY)) {
2172 		error = EINVAL;
2173 		goto out;
2174 	}
2175 	/*
2176 	 * The new master must also use vtoslab().
2177 	 */
2178 	if ((zone->uz_flags & UMA_ZONE_VTOSLAB) != UMA_ZONE_VTOSLAB) {
2179 		error = EINVAL;
2180 		goto out;
2181 	}
2182 
2183 	/*
2184 	 * The underlying object must be the same size.  rsize
2185 	 * may be different.
2186 	 */
2187 	if (master->uz_size != zone->uz_size) {
2188 		error = E2BIG;
2189 		goto out;
2190 	}
2191 	/*
2192 	 * Put it at the end of the list.
2193 	 */
2194 	klink->kl_keg = zone_first_keg(master);
2195 	LIST_FOREACH(kl, &zone->uz_kegs, kl_link) {
2196 		if (LIST_NEXT(kl, kl_link) == NULL) {
2197 			LIST_INSERT_AFTER(kl, klink, kl_link);
2198 			break;
2199 		}
2200 	}
2201 	klink = NULL;
2202 	zone->uz_flags |= UMA_ZFLAG_MULTI;
2203 	zone->uz_slab = zone_fetch_slab_multi;
2204 
2205 out:
2206 	zone_unlock_pair(zone, master);
2207 	if (klink != NULL)
2208 		free(klink, M_TEMP);
2209 
2210 	return (error);
2211 }
2212 
2213 
2214 /* See uma.h */
2215 void
2216 uma_zdestroy(uma_zone_t zone)
2217 {
2218 
2219 	sx_slock(&uma_drain_lock);
2220 	zone_free_item(zones, zone, NULL, SKIP_NONE);
2221 	sx_sunlock(&uma_drain_lock);
2222 }
2223 
2224 void
2225 uma_zwait(uma_zone_t zone)
2226 {
2227 	void *item;
2228 
2229 	item = uma_zalloc_arg(zone, NULL, M_WAITOK);
2230 	uma_zfree(zone, item);
2231 }
2232 
2233 void *
2234 uma_zalloc_pcpu_arg(uma_zone_t zone, void *udata, int flags)
2235 {
2236 	void *item;
2237 #ifdef SMP
2238 	int i;
2239 
2240 	MPASS(zone->uz_flags & UMA_ZONE_PCPU);
2241 #endif
2242 	item = uma_zalloc_arg(zone, udata, flags &~ M_ZERO);
2243 	if (item != NULL && (flags & M_ZERO)) {
2244 #ifdef SMP
2245 		CPU_FOREACH(i)
2246 			bzero(zpcpu_get_cpu(item, i), zone->uz_size);
2247 #else
2248 		bzero(item, zone->uz_size);
2249 #endif
2250 	}
2251 	return (item);
2252 }
2253 
2254 /*
2255  * A stub while both regular and pcpu cases are identical.
2256  */
2257 void
2258 uma_zfree_pcpu_arg(uma_zone_t zone, void *item, void *udata)
2259 {
2260 
2261 #ifdef SMP
2262 	MPASS(zone->uz_flags & UMA_ZONE_PCPU);
2263 #endif
2264 	uma_zfree_arg(zone, item, udata);
2265 }
2266 
2267 /* See uma.h */
2268 void *
2269 uma_zalloc_arg(uma_zone_t zone, void *udata, int flags)
2270 {
2271 	uma_zone_domain_t zdom;
2272 	uma_bucket_t bucket;
2273 	uma_cache_t cache;
2274 	void *item;
2275 	int cpu, domain, lockfail;
2276 #ifdef INVARIANTS
2277 	bool skipdbg;
2278 #endif
2279 
2280 	/* Enable entropy collection for RANDOM_ENABLE_UMA kernel option */
2281 	random_harvest_fast_uma(&zone, sizeof(zone), 1, RANDOM_UMA);
2282 
2283 	/* This is the fast path allocation */
2284 	CTR4(KTR_UMA, "uma_zalloc_arg thread %x zone %s(%p) flags %d",
2285 	    curthread, zone->uz_name, zone, flags);
2286 
2287 	if (flags & M_WAITOK) {
2288 		WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
2289 		    "uma_zalloc_arg: zone \"%s\"", zone->uz_name);
2290 	}
2291 	KASSERT((flags & M_EXEC) == 0, ("uma_zalloc_arg: called with M_EXEC"));
2292 	KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(),
2293 	    ("uma_zalloc_arg: called with spinlock or critical section held"));
2294 	if (zone->uz_flags & UMA_ZONE_PCPU)
2295 		KASSERT((flags & M_ZERO) == 0, ("allocating from a pcpu zone "
2296 		    "with M_ZERO passed"));
2297 
2298 #ifdef DEBUG_MEMGUARD
2299 	if (memguard_cmp_zone(zone)) {
2300 		item = memguard_alloc(zone->uz_size, flags);
2301 		if (item != NULL) {
2302 			if (zone->uz_init != NULL &&
2303 			    zone->uz_init(item, zone->uz_size, flags) != 0)
2304 				return (NULL);
2305 			if (zone->uz_ctor != NULL &&
2306 			    zone->uz_ctor(item, zone->uz_size, udata,
2307 			    flags) != 0) {
2308 			    	zone->uz_fini(item, zone->uz_size);
2309 				return (NULL);
2310 			}
2311 			return (item);
2312 		}
2313 		/* This is unfortunate but should not be fatal. */
2314 	}
2315 #endif
2316 	/*
2317 	 * If possible, allocate from the per-CPU cache.  There are two
2318 	 * requirements for safe access to the per-CPU cache: (1) the thread
2319 	 * accessing the cache must not be preempted or yield during access,
2320 	 * and (2) the thread must not migrate CPUs without switching which
2321 	 * cache it accesses.  We rely on a critical section to prevent
2322 	 * preemption and migration.  We release the critical section in
2323 	 * order to acquire the zone mutex if we are unable to allocate from
2324 	 * the current cache; when we re-acquire the critical section, we
2325 	 * must detect and handle migration if it has occurred.
2326 	 */
2327 	critical_enter();
2328 	cpu = curcpu;
2329 	cache = &zone->uz_cpu[cpu];
2330 
2331 zalloc_start:
2332 	bucket = cache->uc_allocbucket;
2333 	if (bucket != NULL && bucket->ub_cnt > 0) {
2334 		bucket->ub_cnt--;
2335 		item = bucket->ub_bucket[bucket->ub_cnt];
2336 #ifdef INVARIANTS
2337 		bucket->ub_bucket[bucket->ub_cnt] = NULL;
2338 #endif
2339 		KASSERT(item != NULL, ("uma_zalloc: Bucket pointer mangled."));
2340 		cache->uc_allocs++;
2341 		critical_exit();
2342 #ifdef INVARIANTS
2343 		skipdbg = uma_dbg_zskip(zone, item);
2344 #endif
2345 		if (zone->uz_ctor != NULL &&
2346 #ifdef INVARIANTS
2347 		    (!skipdbg || zone->uz_ctor != trash_ctor ||
2348 		    zone->uz_dtor != trash_dtor) &&
2349 #endif
2350 		    zone->uz_ctor(item, zone->uz_size, udata, flags) != 0) {
2351 			atomic_add_long(&zone->uz_fails, 1);
2352 			zone_free_item(zone, item, udata, SKIP_DTOR);
2353 			return (NULL);
2354 		}
2355 #ifdef INVARIANTS
2356 		if (!skipdbg)
2357 			uma_dbg_alloc(zone, NULL, item);
2358 #endif
2359 		if (flags & M_ZERO)
2360 			uma_zero_item(item, zone);
2361 		return (item);
2362 	}
2363 
2364 	/*
2365 	 * We have run out of items in our alloc bucket.
2366 	 * See if we can switch with our free bucket.
2367 	 */
2368 	bucket = cache->uc_freebucket;
2369 	if (bucket != NULL && bucket->ub_cnt > 0) {
2370 		CTR2(KTR_UMA,
2371 		    "uma_zalloc: zone %s(%p) swapping empty with alloc",
2372 		    zone->uz_name, zone);
2373 		cache->uc_freebucket = cache->uc_allocbucket;
2374 		cache->uc_allocbucket = bucket;
2375 		goto zalloc_start;
2376 	}
2377 
2378 	/*
2379 	 * Discard any empty allocation bucket while we hold no locks.
2380 	 */
2381 	bucket = cache->uc_allocbucket;
2382 	cache->uc_allocbucket = NULL;
2383 	critical_exit();
2384 	if (bucket != NULL)
2385 		bucket_free(zone, bucket, udata);
2386 
2387 	if (zone->uz_flags & UMA_ZONE_NUMA)
2388 		domain = PCPU_GET(domain);
2389 	else
2390 		domain = UMA_ANYDOMAIN;
2391 
2392 	/* Short-circuit for zones without buckets and low memory. */
2393 	if (zone->uz_count == 0 || bucketdisable)
2394 		goto zalloc_item;
2395 
2396 	/*
2397 	 * Attempt to retrieve the item from the per-CPU cache has failed, so
2398 	 * we must go back to the zone.  This requires the zone lock, so we
2399 	 * must drop the critical section, then re-acquire it when we go back
2400 	 * to the cache.  Since the critical section is released, we may be
2401 	 * preempted or migrate.  As such, make sure not to maintain any
2402 	 * thread-local state specific to the cache from prior to releasing
2403 	 * the critical section.
2404 	 */
2405 	lockfail = 0;
2406 	if (ZONE_TRYLOCK(zone) == 0) {
2407 		/* Record contention to size the buckets. */
2408 		ZONE_LOCK(zone);
2409 		lockfail = 1;
2410 	}
2411 	critical_enter();
2412 	cpu = curcpu;
2413 	cache = &zone->uz_cpu[cpu];
2414 
2415 	/* See if we lost the race to fill the cache. */
2416 	if (cache->uc_allocbucket != NULL) {
2417 		ZONE_UNLOCK(zone);
2418 		goto zalloc_start;
2419 	}
2420 
2421 	/*
2422 	 * Check the zone's cache of buckets.
2423 	 */
2424 	if (domain == UMA_ANYDOMAIN)
2425 		zdom = &zone->uz_domain[0];
2426 	else
2427 		zdom = &zone->uz_domain[domain];
2428 	if ((bucket = LIST_FIRST(&zdom->uzd_buckets)) != NULL) {
2429 		KASSERT(bucket->ub_cnt != 0,
2430 		    ("uma_zalloc_arg: Returning an empty bucket."));
2431 
2432 		LIST_REMOVE(bucket, ub_link);
2433 		cache->uc_allocbucket = bucket;
2434 		ZONE_UNLOCK(zone);
2435 		goto zalloc_start;
2436 	}
2437 	/* We are no longer associated with this CPU. */
2438 	critical_exit();
2439 
2440 	/*
2441 	 * We bump the uz count when the cache size is insufficient to
2442 	 * handle the working set.
2443 	 */
2444 	if (lockfail && zone->uz_count < BUCKET_MAX)
2445 		zone->uz_count++;
2446 	ZONE_UNLOCK(zone);
2447 
2448 	/*
2449 	 * Now lets just fill a bucket and put it on the free list.  If that
2450 	 * works we'll restart the allocation from the beginning and it
2451 	 * will use the just filled bucket.
2452 	 */
2453 	bucket = zone_alloc_bucket(zone, udata, domain, flags);
2454 	CTR3(KTR_UMA, "uma_zalloc: zone %s(%p) bucket zone returned %p",
2455 	    zone->uz_name, zone, bucket);
2456 	if (bucket != NULL) {
2457 		ZONE_LOCK(zone);
2458 		critical_enter();
2459 		cpu = curcpu;
2460 		cache = &zone->uz_cpu[cpu];
2461 		/*
2462 		 * See if we lost the race or were migrated.  Cache the
2463 		 * initialized bucket to make this less likely or claim
2464 		 * the memory directly.
2465 		 */
2466 		if (cache->uc_allocbucket != NULL ||
2467 		    (zone->uz_flags & UMA_ZONE_NUMA &&
2468 		    domain != PCPU_GET(domain)))
2469 			LIST_INSERT_HEAD(&zdom->uzd_buckets, bucket, ub_link);
2470 		else
2471 			cache->uc_allocbucket = bucket;
2472 		ZONE_UNLOCK(zone);
2473 		goto zalloc_start;
2474 	}
2475 
2476 	/*
2477 	 * We may not be able to get a bucket so return an actual item.
2478 	 */
2479 zalloc_item:
2480 	item = zone_alloc_item(zone, udata, domain, flags);
2481 
2482 	return (item);
2483 }
2484 
2485 void *
2486 uma_zalloc_domain(uma_zone_t zone, void *udata, int domain, int flags)
2487 {
2488 
2489 	/* Enable entropy collection for RANDOM_ENABLE_UMA kernel option */
2490 	random_harvest_fast_uma(&zone, sizeof(zone), 1, RANDOM_UMA);
2491 
2492 	/* This is the fast path allocation */
2493 	CTR5(KTR_UMA,
2494 	    "uma_zalloc_domain thread %x zone %s(%p) domain %d flags %d",
2495 	    curthread, zone->uz_name, zone, domain, flags);
2496 
2497 	if (flags & M_WAITOK) {
2498 		WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
2499 		    "uma_zalloc_domain: zone \"%s\"", zone->uz_name);
2500 	}
2501 	KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(),
2502 	    ("uma_zalloc_domain: called with spinlock or critical section held"));
2503 
2504 	return (zone_alloc_item(zone, udata, domain, flags));
2505 }
2506 
2507 /*
2508  * Find a slab with some space.  Prefer slabs that are partially used over those
2509  * that are totally full.  This helps to reduce fragmentation.
2510  *
2511  * If 'rr' is 1, search all domains starting from 'domain'.  Otherwise check
2512  * only 'domain'.
2513  */
2514 static uma_slab_t
2515 keg_first_slab(uma_keg_t keg, int domain, int rr)
2516 {
2517 	uma_domain_t dom;
2518 	uma_slab_t slab;
2519 	int start;
2520 
2521 	KASSERT(domain >= 0 && domain < vm_ndomains,
2522 	    ("keg_first_slab: domain %d out of range", domain));
2523 
2524 	slab = NULL;
2525 	start = domain;
2526 	do {
2527 		dom = &keg->uk_domain[domain];
2528 		if (!LIST_EMPTY(&dom->ud_part_slab))
2529 			return (LIST_FIRST(&dom->ud_part_slab));
2530 		if (!LIST_EMPTY(&dom->ud_free_slab)) {
2531 			slab = LIST_FIRST(&dom->ud_free_slab);
2532 			LIST_REMOVE(slab, us_link);
2533 			LIST_INSERT_HEAD(&dom->ud_part_slab, slab, us_link);
2534 			return (slab);
2535 		}
2536 		if (rr)
2537 			domain = (domain + 1) % vm_ndomains;
2538 	} while (domain != start);
2539 
2540 	return (NULL);
2541 }
2542 
2543 static uma_slab_t
2544 keg_fetch_slab(uma_keg_t keg, uma_zone_t zone, int rdomain, int flags)
2545 {
2546 	uma_domain_t dom;
2547 	uma_slab_t slab;
2548 	int allocflags, domain, reserve, rr, start;
2549 
2550 	mtx_assert(&keg->uk_lock, MA_OWNED);
2551 	slab = NULL;
2552 	reserve = 0;
2553 	allocflags = flags;
2554 	if ((flags & M_USE_RESERVE) == 0)
2555 		reserve = keg->uk_reserve;
2556 
2557 	/*
2558 	 * Round-robin for non first-touch zones when there is more than one
2559 	 * domain.
2560 	 */
2561 	if (vm_ndomains == 1)
2562 		rdomain = 0;
2563 	rr = rdomain == UMA_ANYDOMAIN;
2564 	if (rr) {
2565 		keg->uk_cursor = (keg->uk_cursor + 1) % vm_ndomains;
2566 		domain = start = keg->uk_cursor;
2567 		/* Only block on the second pass. */
2568 		if ((flags & (M_WAITOK | M_NOVM)) == M_WAITOK)
2569 			allocflags = (allocflags & ~M_WAITOK) | M_NOWAIT;
2570 	} else
2571 		domain = start = rdomain;
2572 
2573 again:
2574 	do {
2575 		if (keg->uk_free > reserve &&
2576 		    (slab = keg_first_slab(keg, domain, rr)) != NULL) {
2577 			MPASS(slab->us_keg == keg);
2578 			return (slab);
2579 		}
2580 
2581 		/*
2582 		 * M_NOVM means don't ask at all!
2583 		 */
2584 		if (flags & M_NOVM)
2585 			break;
2586 
2587 		if (keg->uk_maxpages && keg->uk_pages >= keg->uk_maxpages) {
2588 			keg->uk_flags |= UMA_ZFLAG_FULL;
2589 			/*
2590 			 * If this is not a multi-zone, set the FULL bit.
2591 			 * Otherwise slab_multi() takes care of it.
2592 			 */
2593 			if ((zone->uz_flags & UMA_ZFLAG_MULTI) == 0) {
2594 				zone->uz_flags |= UMA_ZFLAG_FULL;
2595 				zone_log_warning(zone);
2596 				zone_maxaction(zone);
2597 			}
2598 			if (flags & M_NOWAIT)
2599 				return (NULL);
2600 			zone->uz_sleeps++;
2601 			msleep(keg, &keg->uk_lock, PVM, "keglimit", 0);
2602 			continue;
2603 		}
2604 		slab = keg_alloc_slab(keg, zone, domain, allocflags);
2605 		/*
2606 		 * If we got a slab here it's safe to mark it partially used
2607 		 * and return.  We assume that the caller is going to remove
2608 		 * at least one item.
2609 		 */
2610 		if (slab) {
2611 			MPASS(slab->us_keg == keg);
2612 			dom = &keg->uk_domain[slab->us_domain];
2613 			LIST_INSERT_HEAD(&dom->ud_part_slab, slab, us_link);
2614 			return (slab);
2615 		}
2616 		if (rr) {
2617 			keg->uk_cursor = (keg->uk_cursor + 1) % vm_ndomains;
2618 			domain = keg->uk_cursor;
2619 		}
2620 	} while (domain != start);
2621 
2622 	/* Retry domain scan with blocking. */
2623 	if (allocflags != flags) {
2624 		allocflags = flags;
2625 		goto again;
2626 	}
2627 
2628 	/*
2629 	 * We might not have been able to get a slab but another cpu
2630 	 * could have while we were unlocked.  Check again before we
2631 	 * fail.
2632 	 */
2633 	if (keg->uk_free > reserve &&
2634 	    (slab = keg_first_slab(keg, domain, rr)) != NULL) {
2635 		MPASS(slab->us_keg == keg);
2636 		return (slab);
2637 	}
2638 	return (NULL);
2639 }
2640 
2641 static uma_slab_t
2642 zone_fetch_slab(uma_zone_t zone, uma_keg_t keg, int domain, int flags)
2643 {
2644 	uma_slab_t slab;
2645 
2646 	if (keg == NULL) {
2647 		keg = zone_first_keg(zone);
2648 		KEG_LOCK(keg);
2649 	}
2650 
2651 	for (;;) {
2652 		slab = keg_fetch_slab(keg, zone, domain, flags);
2653 		if (slab)
2654 			return (slab);
2655 		if (flags & (M_NOWAIT | M_NOVM))
2656 			break;
2657 	}
2658 	KEG_UNLOCK(keg);
2659 	return (NULL);
2660 }
2661 
2662 /*
2663  * uma_zone_fetch_slab_multi:  Fetches a slab from one available keg.  Returns
2664  * with the keg locked.  On NULL no lock is held.
2665  *
2666  * The last pointer is used to seed the search.  It is not required.
2667  */
2668 static uma_slab_t
2669 zone_fetch_slab_multi(uma_zone_t zone, uma_keg_t last, int domain, int rflags)
2670 {
2671 	uma_klink_t klink;
2672 	uma_slab_t slab;
2673 	uma_keg_t keg;
2674 	int flags;
2675 	int empty;
2676 	int full;
2677 
2678 	/*
2679 	 * Don't wait on the first pass.  This will skip limit tests
2680 	 * as well.  We don't want to block if we can find a provider
2681 	 * without blocking.
2682 	 */
2683 	flags = (rflags & ~M_WAITOK) | M_NOWAIT;
2684 	/*
2685 	 * Use the last slab allocated as a hint for where to start
2686 	 * the search.
2687 	 */
2688 	if (last != NULL) {
2689 		slab = keg_fetch_slab(last, zone, domain, flags);
2690 		if (slab)
2691 			return (slab);
2692 		KEG_UNLOCK(last);
2693 	}
2694 	/*
2695 	 * Loop until we have a slab incase of transient failures
2696 	 * while M_WAITOK is specified.  I'm not sure this is 100%
2697 	 * required but we've done it for so long now.
2698 	 */
2699 	for (;;) {
2700 		empty = 0;
2701 		full = 0;
2702 		/*
2703 		 * Search the available kegs for slabs.  Be careful to hold the
2704 		 * correct lock while calling into the keg layer.
2705 		 */
2706 		LIST_FOREACH(klink, &zone->uz_kegs, kl_link) {
2707 			keg = klink->kl_keg;
2708 			KEG_LOCK(keg);
2709 			if ((keg->uk_flags & UMA_ZFLAG_FULL) == 0) {
2710 				slab = keg_fetch_slab(keg, zone, domain, flags);
2711 				if (slab)
2712 					return (slab);
2713 			}
2714 			if (keg->uk_flags & UMA_ZFLAG_FULL)
2715 				full++;
2716 			else
2717 				empty++;
2718 			KEG_UNLOCK(keg);
2719 		}
2720 		if (rflags & (M_NOWAIT | M_NOVM))
2721 			break;
2722 		flags = rflags;
2723 		/*
2724 		 * All kegs are full.  XXX We can't atomically check all kegs
2725 		 * and sleep so just sleep for a short period and retry.
2726 		 */
2727 		if (full && !empty) {
2728 			ZONE_LOCK(zone);
2729 			zone->uz_flags |= UMA_ZFLAG_FULL;
2730 			zone->uz_sleeps++;
2731 			zone_log_warning(zone);
2732 			zone_maxaction(zone);
2733 			msleep(zone, zone->uz_lockptr, PVM,
2734 			    "zonelimit", hz/100);
2735 			zone->uz_flags &= ~UMA_ZFLAG_FULL;
2736 			ZONE_UNLOCK(zone);
2737 			continue;
2738 		}
2739 	}
2740 	return (NULL);
2741 }
2742 
2743 static void *
2744 slab_alloc_item(uma_keg_t keg, uma_slab_t slab)
2745 {
2746 	uma_domain_t dom;
2747 	void *item;
2748 	uint8_t freei;
2749 
2750 	MPASS(keg == slab->us_keg);
2751 	mtx_assert(&keg->uk_lock, MA_OWNED);
2752 
2753 	freei = BIT_FFS(SLAB_SETSIZE, &slab->us_free) - 1;
2754 	BIT_CLR(SLAB_SETSIZE, freei, &slab->us_free);
2755 	item = slab->us_data + (keg->uk_rsize * freei);
2756 	slab->us_freecount--;
2757 	keg->uk_free--;
2758 
2759 	/* Move this slab to the full list */
2760 	if (slab->us_freecount == 0) {
2761 		LIST_REMOVE(slab, us_link);
2762 		dom = &keg->uk_domain[slab->us_domain];
2763 		LIST_INSERT_HEAD(&dom->ud_full_slab, slab, us_link);
2764 	}
2765 
2766 	return (item);
2767 }
2768 
2769 static int
2770 zone_import(uma_zone_t zone, void **bucket, int max, int domain, int flags)
2771 {
2772 	uma_slab_t slab;
2773 	uma_keg_t keg;
2774 	int stripe;
2775 	int i;
2776 
2777 	slab = NULL;
2778 	keg = NULL;
2779 	/* Try to keep the buckets totally full */
2780 	for (i = 0; i < max; ) {
2781 		if ((slab = zone->uz_slab(zone, keg, domain, flags)) == NULL)
2782 			break;
2783 		keg = slab->us_keg;
2784 		stripe = howmany(max, vm_ndomains);
2785 		while (slab->us_freecount && i < max) {
2786 			bucket[i++] = slab_alloc_item(keg, slab);
2787 			if (keg->uk_free <= keg->uk_reserve)
2788 				break;
2789 #ifdef NUMA
2790 			/*
2791 			 * If the zone is striped we pick a new slab for every
2792 			 * N allocations.  Eliminating this conditional will
2793 			 * instead pick a new domain for each bucket rather
2794 			 * than stripe within each bucket.  The current option
2795 			 * produces more fragmentation and requires more cpu
2796 			 * time but yields better distribution.
2797 			 */
2798 			if ((zone->uz_flags & UMA_ZONE_NUMA) == 0 &&
2799 			    vm_ndomains > 1 && --stripe == 0)
2800 				break;
2801 #endif
2802 		}
2803 		/* Don't block if we allocated any successfully. */
2804 		flags &= ~M_WAITOK;
2805 		flags |= M_NOWAIT;
2806 	}
2807 	if (slab != NULL)
2808 		KEG_UNLOCK(keg);
2809 
2810 	return i;
2811 }
2812 
2813 static uma_bucket_t
2814 zone_alloc_bucket(uma_zone_t zone, void *udata, int domain, int flags)
2815 {
2816 	uma_bucket_t bucket;
2817 	int max;
2818 
2819 	/* Don't wait for buckets, preserve caller's NOVM setting. */
2820 	bucket = bucket_alloc(zone, udata, M_NOWAIT | (flags & M_NOVM));
2821 	if (bucket == NULL)
2822 		return (NULL);
2823 
2824 	max = MIN(bucket->ub_entries, zone->uz_count);
2825 	bucket->ub_cnt = zone->uz_import(zone->uz_arg, bucket->ub_bucket,
2826 	    max, domain, flags);
2827 
2828 	/*
2829 	 * Initialize the memory if necessary.
2830 	 */
2831 	if (bucket->ub_cnt != 0 && zone->uz_init != NULL) {
2832 		int i;
2833 
2834 		for (i = 0; i < bucket->ub_cnt; i++)
2835 			if (zone->uz_init(bucket->ub_bucket[i], zone->uz_size,
2836 			    flags) != 0)
2837 				break;
2838 		/*
2839 		 * If we couldn't initialize the whole bucket, put the
2840 		 * rest back onto the freelist.
2841 		 */
2842 		if (i != bucket->ub_cnt) {
2843 			zone->uz_release(zone->uz_arg, &bucket->ub_bucket[i],
2844 			    bucket->ub_cnt - i);
2845 #ifdef INVARIANTS
2846 			bzero(&bucket->ub_bucket[i],
2847 			    sizeof(void *) * (bucket->ub_cnt - i));
2848 #endif
2849 			bucket->ub_cnt = i;
2850 		}
2851 	}
2852 
2853 	if (bucket->ub_cnt == 0) {
2854 		bucket_free(zone, bucket, udata);
2855 		atomic_add_long(&zone->uz_fails, 1);
2856 		return (NULL);
2857 	}
2858 
2859 	return (bucket);
2860 }
2861 
2862 /*
2863  * Allocates a single item from a zone.
2864  *
2865  * Arguments
2866  *	zone   The zone to alloc for.
2867  *	udata  The data to be passed to the constructor.
2868  *	domain The domain to allocate from or UMA_ANYDOMAIN.
2869  *	flags  M_WAITOK, M_NOWAIT, M_ZERO.
2870  *
2871  * Returns
2872  *	NULL if there is no memory and M_NOWAIT is set
2873  *	An item if successful
2874  */
2875 
2876 static void *
2877 zone_alloc_item(uma_zone_t zone, void *udata, int domain, int flags)
2878 {
2879 	void *item;
2880 #ifdef INVARIANTS
2881 	bool skipdbg;
2882 #endif
2883 
2884 	item = NULL;
2885 
2886 	if (zone->uz_import(zone->uz_arg, &item, 1, domain, flags) != 1)
2887 		goto fail;
2888 	atomic_add_long(&zone->uz_allocs, 1);
2889 
2890 #ifdef INVARIANTS
2891 	skipdbg = uma_dbg_zskip(zone, item);
2892 #endif
2893 	/*
2894 	 * We have to call both the zone's init (not the keg's init)
2895 	 * and the zone's ctor.  This is because the item is going from
2896 	 * a keg slab directly to the user, and the user is expecting it
2897 	 * to be both zone-init'd as well as zone-ctor'd.
2898 	 */
2899 	if (zone->uz_init != NULL) {
2900 		if (zone->uz_init(item, zone->uz_size, flags) != 0) {
2901 			zone_free_item(zone, item, udata, SKIP_FINI);
2902 			goto fail;
2903 		}
2904 	}
2905 	if (zone->uz_ctor != NULL &&
2906 #ifdef INVARIANTS
2907 	    (!skipdbg || zone->uz_ctor != trash_ctor ||
2908 	    zone->uz_dtor != trash_dtor) &&
2909 #endif
2910 	    zone->uz_ctor(item, zone->uz_size, udata, flags) != 0) {
2911 		zone_free_item(zone, item, udata, SKIP_DTOR);
2912 		goto fail;
2913 	}
2914 #ifdef INVARIANTS
2915 	if (!skipdbg)
2916 		uma_dbg_alloc(zone, NULL, item);
2917 #endif
2918 	if (flags & M_ZERO)
2919 		uma_zero_item(item, zone);
2920 
2921 	CTR3(KTR_UMA, "zone_alloc_item item %p from %s(%p)", item,
2922 	    zone->uz_name, zone);
2923 
2924 	return (item);
2925 
2926 fail:
2927 	CTR2(KTR_UMA, "zone_alloc_item failed from %s(%p)",
2928 	    zone->uz_name, zone);
2929 	atomic_add_long(&zone->uz_fails, 1);
2930 	return (NULL);
2931 }
2932 
2933 /* See uma.h */
2934 void
2935 uma_zfree_arg(uma_zone_t zone, void *item, void *udata)
2936 {
2937 	uma_cache_t cache;
2938 	uma_bucket_t bucket;
2939 	uma_zone_domain_t zdom;
2940 	int cpu, domain, lockfail;
2941 #ifdef INVARIANTS
2942 	bool skipdbg;
2943 #endif
2944 
2945 	/* Enable entropy collection for RANDOM_ENABLE_UMA kernel option */
2946 	random_harvest_fast_uma(&zone, sizeof(zone), 1, RANDOM_UMA);
2947 
2948 	CTR2(KTR_UMA, "uma_zfree_arg thread %x zone %s", curthread,
2949 	    zone->uz_name);
2950 
2951 	KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(),
2952 	    ("uma_zfree_arg: called with spinlock or critical section held"));
2953 
2954         /* uma_zfree(..., NULL) does nothing, to match free(9). */
2955         if (item == NULL)
2956                 return;
2957 #ifdef DEBUG_MEMGUARD
2958 	if (is_memguard_addr(item)) {
2959 		if (zone->uz_dtor != NULL)
2960 			zone->uz_dtor(item, zone->uz_size, udata);
2961 		if (zone->uz_fini != NULL)
2962 			zone->uz_fini(item, zone->uz_size);
2963 		memguard_free(item);
2964 		return;
2965 	}
2966 #endif
2967 #ifdef INVARIANTS
2968 	skipdbg = uma_dbg_zskip(zone, item);
2969 	if (skipdbg == false) {
2970 		if (zone->uz_flags & UMA_ZONE_MALLOC)
2971 			uma_dbg_free(zone, udata, item);
2972 		else
2973 			uma_dbg_free(zone, NULL, item);
2974 	}
2975 	if (zone->uz_dtor != NULL && (!skipdbg ||
2976 	    zone->uz_dtor != trash_dtor || zone->uz_ctor != trash_ctor))
2977 #else
2978 	if (zone->uz_dtor != NULL)
2979 #endif
2980 		zone->uz_dtor(item, zone->uz_size, udata);
2981 
2982 	/*
2983 	 * The race here is acceptable.  If we miss it we'll just have to wait
2984 	 * a little longer for the limits to be reset.
2985 	 */
2986 	if (zone->uz_flags & UMA_ZFLAG_FULL)
2987 		goto zfree_item;
2988 
2989 	/*
2990 	 * If possible, free to the per-CPU cache.  There are two
2991 	 * requirements for safe access to the per-CPU cache: (1) the thread
2992 	 * accessing the cache must not be preempted or yield during access,
2993 	 * and (2) the thread must not migrate CPUs without switching which
2994 	 * cache it accesses.  We rely on a critical section to prevent
2995 	 * preemption and migration.  We release the critical section in
2996 	 * order to acquire the zone mutex if we are unable to free to the
2997 	 * current cache; when we re-acquire the critical section, we must
2998 	 * detect and handle migration if it has occurred.
2999 	 */
3000 zfree_restart:
3001 	critical_enter();
3002 	cpu = curcpu;
3003 	cache = &zone->uz_cpu[cpu];
3004 
3005 zfree_start:
3006 	/*
3007 	 * Try to free into the allocbucket first to give LIFO ordering
3008 	 * for cache-hot datastructures.  Spill over into the freebucket
3009 	 * if necessary.  Alloc will swap them if one runs dry.
3010 	 */
3011 	bucket = cache->uc_allocbucket;
3012 	if (bucket == NULL || bucket->ub_cnt >= bucket->ub_entries)
3013 		bucket = cache->uc_freebucket;
3014 	if (bucket != NULL && bucket->ub_cnt < bucket->ub_entries) {
3015 		KASSERT(bucket->ub_bucket[bucket->ub_cnt] == NULL,
3016 		    ("uma_zfree: Freeing to non free bucket index."));
3017 		bucket->ub_bucket[bucket->ub_cnt] = item;
3018 		bucket->ub_cnt++;
3019 		cache->uc_frees++;
3020 		critical_exit();
3021 		return;
3022 	}
3023 
3024 	/*
3025 	 * We must go back the zone, which requires acquiring the zone lock,
3026 	 * which in turn means we must release and re-acquire the critical
3027 	 * section.  Since the critical section is released, we may be
3028 	 * preempted or migrate.  As such, make sure not to maintain any
3029 	 * thread-local state specific to the cache from prior to releasing
3030 	 * the critical section.
3031 	 */
3032 	critical_exit();
3033 	if (zone->uz_count == 0 || bucketdisable)
3034 		goto zfree_item;
3035 
3036 	lockfail = 0;
3037 	if (ZONE_TRYLOCK(zone) == 0) {
3038 		/* Record contention to size the buckets. */
3039 		ZONE_LOCK(zone);
3040 		lockfail = 1;
3041 	}
3042 	critical_enter();
3043 	cpu = curcpu;
3044 	cache = &zone->uz_cpu[cpu];
3045 
3046 	/*
3047 	 * Since we have locked the zone we may as well send back our stats.
3048 	 */
3049 	atomic_add_long(&zone->uz_allocs, cache->uc_allocs);
3050 	atomic_add_long(&zone->uz_frees, cache->uc_frees);
3051 	cache->uc_allocs = 0;
3052 	cache->uc_frees = 0;
3053 
3054 	bucket = cache->uc_freebucket;
3055 	if (bucket != NULL && bucket->ub_cnt < bucket->ub_entries) {
3056 		ZONE_UNLOCK(zone);
3057 		goto zfree_start;
3058 	}
3059 	cache->uc_freebucket = NULL;
3060 	/* We are no longer associated with this CPU. */
3061 	critical_exit();
3062 
3063 	if ((zone->uz_flags & UMA_ZONE_NUMA) != 0)
3064 		domain = PCPU_GET(domain);
3065 	else
3066 		domain = 0;
3067 	zdom = &zone->uz_domain[0];
3068 
3069 	/* Can we throw this on the zone full list? */
3070 	if (bucket != NULL) {
3071 		CTR3(KTR_UMA,
3072 		    "uma_zfree: zone %s(%p) putting bucket %p on free list",
3073 		    zone->uz_name, zone, bucket);
3074 		/* ub_cnt is pointing to the last free item */
3075 		KASSERT(bucket->ub_cnt != 0,
3076 		    ("uma_zfree: Attempting to insert an empty bucket onto the full list.\n"));
3077 		if ((zone->uz_flags & UMA_ZONE_NOBUCKETCACHE) != 0) {
3078 			ZONE_UNLOCK(zone);
3079 			bucket_drain(zone, bucket);
3080 			bucket_free(zone, bucket, udata);
3081 			goto zfree_restart;
3082 		} else
3083 			LIST_INSERT_HEAD(&zdom->uzd_buckets, bucket, ub_link);
3084 	}
3085 
3086 	/*
3087 	 * We bump the uz count when the cache size is insufficient to
3088 	 * handle the working set.
3089 	 */
3090 	if (lockfail && zone->uz_count < BUCKET_MAX)
3091 		zone->uz_count++;
3092 	ZONE_UNLOCK(zone);
3093 
3094 	bucket = bucket_alloc(zone, udata, M_NOWAIT);
3095 	CTR3(KTR_UMA, "uma_zfree: zone %s(%p) allocated bucket %p",
3096 	    zone->uz_name, zone, bucket);
3097 	if (bucket) {
3098 		critical_enter();
3099 		cpu = curcpu;
3100 		cache = &zone->uz_cpu[cpu];
3101 		if (cache->uc_freebucket == NULL &&
3102 		    ((zone->uz_flags & UMA_ZONE_NUMA) == 0 ||
3103 		    domain == PCPU_GET(domain))) {
3104 			cache->uc_freebucket = bucket;
3105 			goto zfree_start;
3106 		}
3107 		/*
3108 		 * We lost the race, start over.  We have to drop our
3109 		 * critical section to free the bucket.
3110 		 */
3111 		critical_exit();
3112 		bucket_free(zone, bucket, udata);
3113 		goto zfree_restart;
3114 	}
3115 
3116 	/*
3117 	 * If nothing else caught this, we'll just do an internal free.
3118 	 */
3119 zfree_item:
3120 	zone_free_item(zone, item, udata, SKIP_DTOR);
3121 
3122 	return;
3123 }
3124 
3125 void
3126 uma_zfree_domain(uma_zone_t zone, void *item, void *udata)
3127 {
3128 
3129 	/* Enable entropy collection for RANDOM_ENABLE_UMA kernel option */
3130 	random_harvest_fast_uma(&zone, sizeof(zone), 1, RANDOM_UMA);
3131 
3132 	CTR2(KTR_UMA, "uma_zfree_domain thread %x zone %s", curthread,
3133 	    zone->uz_name);
3134 
3135 	KASSERT(curthread->td_critnest == 0 || SCHEDULER_STOPPED(),
3136 	    ("uma_zfree_domain: called with spinlock or critical section held"));
3137 
3138         /* uma_zfree(..., NULL) does nothing, to match free(9). */
3139         if (item == NULL)
3140                 return;
3141 	zone_free_item(zone, item, udata, SKIP_NONE);
3142 }
3143 
3144 static void
3145 slab_free_item(uma_keg_t keg, uma_slab_t slab, void *item)
3146 {
3147 	uma_domain_t dom;
3148 	uint8_t freei;
3149 
3150 	mtx_assert(&keg->uk_lock, MA_OWNED);
3151 	MPASS(keg == slab->us_keg);
3152 
3153 	dom = &keg->uk_domain[slab->us_domain];
3154 
3155 	/* Do we need to remove from any lists? */
3156 	if (slab->us_freecount+1 == keg->uk_ipers) {
3157 		LIST_REMOVE(slab, us_link);
3158 		LIST_INSERT_HEAD(&dom->ud_free_slab, slab, us_link);
3159 	} else if (slab->us_freecount == 0) {
3160 		LIST_REMOVE(slab, us_link);
3161 		LIST_INSERT_HEAD(&dom->ud_part_slab, slab, us_link);
3162 	}
3163 
3164 	/* Slab management. */
3165 	freei = ((uintptr_t)item - (uintptr_t)slab->us_data) / keg->uk_rsize;
3166 	BIT_SET(SLAB_SETSIZE, freei, &slab->us_free);
3167 	slab->us_freecount++;
3168 
3169 	/* Keg statistics. */
3170 	keg->uk_free++;
3171 }
3172 
3173 static void
3174 zone_release(uma_zone_t zone, void **bucket, int cnt)
3175 {
3176 	void *item;
3177 	uma_slab_t slab;
3178 	uma_keg_t keg;
3179 	uint8_t *mem;
3180 	int clearfull;
3181 	int i;
3182 
3183 	clearfull = 0;
3184 	keg = zone_first_keg(zone);
3185 	KEG_LOCK(keg);
3186 	for (i = 0; i < cnt; i++) {
3187 		item = bucket[i];
3188 		if (!(zone->uz_flags & UMA_ZONE_VTOSLAB)) {
3189 			mem = (uint8_t *)((uintptr_t)item & (~UMA_SLAB_MASK));
3190 			if (zone->uz_flags & UMA_ZONE_HASH) {
3191 				slab = hash_sfind(&keg->uk_hash, mem);
3192 			} else {
3193 				mem += keg->uk_pgoff;
3194 				slab = (uma_slab_t)mem;
3195 			}
3196 		} else {
3197 			slab = vtoslab((vm_offset_t)item);
3198 			if (slab->us_keg != keg) {
3199 				KEG_UNLOCK(keg);
3200 				keg = slab->us_keg;
3201 				KEG_LOCK(keg);
3202 			}
3203 		}
3204 		slab_free_item(keg, slab, item);
3205 		if (keg->uk_flags & UMA_ZFLAG_FULL) {
3206 			if (keg->uk_pages < keg->uk_maxpages) {
3207 				keg->uk_flags &= ~UMA_ZFLAG_FULL;
3208 				clearfull = 1;
3209 			}
3210 
3211 			/*
3212 			 * We can handle one more allocation. Since we're
3213 			 * clearing ZFLAG_FULL, wake up all procs blocked
3214 			 * on pages. This should be uncommon, so keeping this
3215 			 * simple for now (rather than adding count of blocked
3216 			 * threads etc).
3217 			 */
3218 			wakeup(keg);
3219 		}
3220 	}
3221 	KEG_UNLOCK(keg);
3222 	if (clearfull) {
3223 		ZONE_LOCK(zone);
3224 		zone->uz_flags &= ~UMA_ZFLAG_FULL;
3225 		wakeup(zone);
3226 		ZONE_UNLOCK(zone);
3227 	}
3228 
3229 }
3230 
3231 /*
3232  * Frees a single item to any zone.
3233  *
3234  * Arguments:
3235  *	zone   The zone to free to
3236  *	item   The item we're freeing
3237  *	udata  User supplied data for the dtor
3238  *	skip   Skip dtors and finis
3239  */
3240 static void
3241 zone_free_item(uma_zone_t zone, void *item, void *udata, enum zfreeskip skip)
3242 {
3243 #ifdef INVARIANTS
3244 	bool skipdbg;
3245 
3246 	skipdbg = uma_dbg_zskip(zone, item);
3247 	if (skip == SKIP_NONE && !skipdbg) {
3248 		if (zone->uz_flags & UMA_ZONE_MALLOC)
3249 			uma_dbg_free(zone, udata, item);
3250 		else
3251 			uma_dbg_free(zone, NULL, item);
3252 	}
3253 
3254 	if (skip < SKIP_DTOR && zone->uz_dtor != NULL &&
3255 	    (!skipdbg || zone->uz_dtor != trash_dtor ||
3256 	    zone->uz_ctor != trash_ctor))
3257 #else
3258 	if (skip < SKIP_DTOR && zone->uz_dtor != NULL)
3259 #endif
3260 		zone->uz_dtor(item, zone->uz_size, udata);
3261 
3262 	if (skip < SKIP_FINI && zone->uz_fini)
3263 		zone->uz_fini(item, zone->uz_size);
3264 
3265 	atomic_add_long(&zone->uz_frees, 1);
3266 	zone->uz_release(zone->uz_arg, &item, 1);
3267 }
3268 
3269 /* See uma.h */
3270 int
3271 uma_zone_set_max(uma_zone_t zone, int nitems)
3272 {
3273 	uma_keg_t keg;
3274 
3275 	keg = zone_first_keg(zone);
3276 	if (keg == NULL)
3277 		return (0);
3278 	KEG_LOCK(keg);
3279 	keg->uk_maxpages = (nitems / keg->uk_ipers) * keg->uk_ppera;
3280 	if (keg->uk_maxpages * keg->uk_ipers < nitems)
3281 		keg->uk_maxpages += keg->uk_ppera;
3282 	nitems = (keg->uk_maxpages / keg->uk_ppera) * keg->uk_ipers;
3283 	KEG_UNLOCK(keg);
3284 
3285 	return (nitems);
3286 }
3287 
3288 /* See uma.h */
3289 int
3290 uma_zone_get_max(uma_zone_t zone)
3291 {
3292 	int nitems;
3293 	uma_keg_t keg;
3294 
3295 	keg = zone_first_keg(zone);
3296 	if (keg == NULL)
3297 		return (0);
3298 	KEG_LOCK(keg);
3299 	nitems = (keg->uk_maxpages / keg->uk_ppera) * keg->uk_ipers;
3300 	KEG_UNLOCK(keg);
3301 
3302 	return (nitems);
3303 }
3304 
3305 /* See uma.h */
3306 void
3307 uma_zone_set_warning(uma_zone_t zone, const char *warning)
3308 {
3309 
3310 	ZONE_LOCK(zone);
3311 	zone->uz_warning = warning;
3312 	ZONE_UNLOCK(zone);
3313 }
3314 
3315 /* See uma.h */
3316 void
3317 uma_zone_set_maxaction(uma_zone_t zone, uma_maxaction_t maxaction)
3318 {
3319 
3320 	ZONE_LOCK(zone);
3321 	TASK_INIT(&zone->uz_maxaction, 0, (task_fn_t *)maxaction, zone);
3322 	ZONE_UNLOCK(zone);
3323 }
3324 
3325 /* See uma.h */
3326 int
3327 uma_zone_get_cur(uma_zone_t zone)
3328 {
3329 	int64_t nitems;
3330 	u_int i;
3331 
3332 	ZONE_LOCK(zone);
3333 	nitems = zone->uz_allocs - zone->uz_frees;
3334 	CPU_FOREACH(i) {
3335 		/*
3336 		 * See the comment in sysctl_vm_zone_stats() regarding the
3337 		 * safety of accessing the per-cpu caches. With the zone lock
3338 		 * held, it is safe, but can potentially result in stale data.
3339 		 */
3340 		nitems += zone->uz_cpu[i].uc_allocs -
3341 		    zone->uz_cpu[i].uc_frees;
3342 	}
3343 	ZONE_UNLOCK(zone);
3344 
3345 	return (nitems < 0 ? 0 : nitems);
3346 }
3347 
3348 /* See uma.h */
3349 void
3350 uma_zone_set_init(uma_zone_t zone, uma_init uminit)
3351 {
3352 	uma_keg_t keg;
3353 
3354 	keg = zone_first_keg(zone);
3355 	KASSERT(keg != NULL, ("uma_zone_set_init: Invalid zone type"));
3356 	KEG_LOCK(keg);
3357 	KASSERT(keg->uk_pages == 0,
3358 	    ("uma_zone_set_init on non-empty keg"));
3359 	keg->uk_init = uminit;
3360 	KEG_UNLOCK(keg);
3361 }
3362 
3363 /* See uma.h */
3364 void
3365 uma_zone_set_fini(uma_zone_t zone, uma_fini fini)
3366 {
3367 	uma_keg_t keg;
3368 
3369 	keg = zone_first_keg(zone);
3370 	KASSERT(keg != NULL, ("uma_zone_set_fini: Invalid zone type"));
3371 	KEG_LOCK(keg);
3372 	KASSERT(keg->uk_pages == 0,
3373 	    ("uma_zone_set_fini on non-empty keg"));
3374 	keg->uk_fini = fini;
3375 	KEG_UNLOCK(keg);
3376 }
3377 
3378 /* See uma.h */
3379 void
3380 uma_zone_set_zinit(uma_zone_t zone, uma_init zinit)
3381 {
3382 
3383 	ZONE_LOCK(zone);
3384 	KASSERT(zone_first_keg(zone)->uk_pages == 0,
3385 	    ("uma_zone_set_zinit on non-empty keg"));
3386 	zone->uz_init = zinit;
3387 	ZONE_UNLOCK(zone);
3388 }
3389 
3390 /* See uma.h */
3391 void
3392 uma_zone_set_zfini(uma_zone_t zone, uma_fini zfini)
3393 {
3394 
3395 	ZONE_LOCK(zone);
3396 	KASSERT(zone_first_keg(zone)->uk_pages == 0,
3397 	    ("uma_zone_set_zfini on non-empty keg"));
3398 	zone->uz_fini = zfini;
3399 	ZONE_UNLOCK(zone);
3400 }
3401 
3402 /* See uma.h */
3403 /* XXX uk_freef is not actually used with the zone locked */
3404 void
3405 uma_zone_set_freef(uma_zone_t zone, uma_free freef)
3406 {
3407 	uma_keg_t keg;
3408 
3409 	keg = zone_first_keg(zone);
3410 	KASSERT(keg != NULL, ("uma_zone_set_freef: Invalid zone type"));
3411 	KEG_LOCK(keg);
3412 	keg->uk_freef = freef;
3413 	KEG_UNLOCK(keg);
3414 }
3415 
3416 /* See uma.h */
3417 /* XXX uk_allocf is not actually used with the zone locked */
3418 void
3419 uma_zone_set_allocf(uma_zone_t zone, uma_alloc allocf)
3420 {
3421 	uma_keg_t keg;
3422 
3423 	keg = zone_first_keg(zone);
3424 	KEG_LOCK(keg);
3425 	keg->uk_allocf = allocf;
3426 	KEG_UNLOCK(keg);
3427 }
3428 
3429 /* See uma.h */
3430 void
3431 uma_zone_reserve(uma_zone_t zone, int items)
3432 {
3433 	uma_keg_t keg;
3434 
3435 	keg = zone_first_keg(zone);
3436 	if (keg == NULL)
3437 		return;
3438 	KEG_LOCK(keg);
3439 	keg->uk_reserve = items;
3440 	KEG_UNLOCK(keg);
3441 
3442 	return;
3443 }
3444 
3445 /* See uma.h */
3446 int
3447 uma_zone_reserve_kva(uma_zone_t zone, int count)
3448 {
3449 	uma_keg_t keg;
3450 	vm_offset_t kva;
3451 	u_int pages;
3452 
3453 	keg = zone_first_keg(zone);
3454 	if (keg == NULL)
3455 		return (0);
3456 	pages = count / keg->uk_ipers;
3457 
3458 	if (pages * keg->uk_ipers < count)
3459 		pages++;
3460 	pages *= keg->uk_ppera;
3461 
3462 #ifdef UMA_MD_SMALL_ALLOC
3463 	if (keg->uk_ppera > 1) {
3464 #else
3465 	if (1) {
3466 #endif
3467 		kva = kva_alloc((vm_size_t)pages * PAGE_SIZE);
3468 		if (kva == 0)
3469 			return (0);
3470 	} else
3471 		kva = 0;
3472 	KEG_LOCK(keg);
3473 	keg->uk_kva = kva;
3474 	keg->uk_offset = 0;
3475 	keg->uk_maxpages = pages;
3476 #ifdef UMA_MD_SMALL_ALLOC
3477 	keg->uk_allocf = (keg->uk_ppera > 1) ? noobj_alloc : uma_small_alloc;
3478 #else
3479 	keg->uk_allocf = noobj_alloc;
3480 #endif
3481 	keg->uk_flags |= UMA_ZONE_NOFREE;
3482 	KEG_UNLOCK(keg);
3483 
3484 	return (1);
3485 }
3486 
3487 /* See uma.h */
3488 void
3489 uma_prealloc(uma_zone_t zone, int items)
3490 {
3491 	uma_domain_t dom;
3492 	uma_slab_t slab;
3493 	uma_keg_t keg;
3494 	int domain, slabs;
3495 
3496 	keg = zone_first_keg(zone);
3497 	if (keg == NULL)
3498 		return;
3499 	KEG_LOCK(keg);
3500 	slabs = items / keg->uk_ipers;
3501 	domain = 0;
3502 	if (slabs * keg->uk_ipers < items)
3503 		slabs++;
3504 	while (slabs > 0) {
3505 		slab = keg_alloc_slab(keg, zone, domain, M_WAITOK);
3506 		if (slab == NULL)
3507 			break;
3508 		MPASS(slab->us_keg == keg);
3509 		dom = &keg->uk_domain[slab->us_domain];
3510 		LIST_INSERT_HEAD(&dom->ud_free_slab, slab, us_link);
3511 		slabs--;
3512 		domain = (domain + 1) % vm_ndomains;
3513 	}
3514 	KEG_UNLOCK(keg);
3515 }
3516 
3517 /* See uma.h */
3518 static void
3519 uma_reclaim_locked(bool kmem_danger)
3520 {
3521 
3522 	CTR0(KTR_UMA, "UMA: vm asked us to release pages!");
3523 	sx_assert(&uma_drain_lock, SA_XLOCKED);
3524 	bucket_enable();
3525 	zone_foreach(zone_drain);
3526 	if (vm_page_count_min() || kmem_danger) {
3527 		cache_drain_safe(NULL);
3528 		zone_foreach(zone_drain);
3529 	}
3530 	/*
3531 	 * Some slabs may have been freed but this zone will be visited early
3532 	 * we visit again so that we can free pages that are empty once other
3533 	 * zones are drained.  We have to do the same for buckets.
3534 	 */
3535 	zone_drain(slabzone);
3536 	bucket_zone_drain();
3537 }
3538 
3539 void
3540 uma_reclaim(void)
3541 {
3542 
3543 	sx_xlock(&uma_drain_lock);
3544 	uma_reclaim_locked(false);
3545 	sx_xunlock(&uma_drain_lock);
3546 }
3547 
3548 static volatile int uma_reclaim_needed;
3549 
3550 void
3551 uma_reclaim_wakeup(void)
3552 {
3553 
3554 	if (atomic_fetchadd_int(&uma_reclaim_needed, 1) == 0)
3555 		wakeup(uma_reclaim);
3556 }
3557 
3558 void
3559 uma_reclaim_worker(void *arg __unused)
3560 {
3561 
3562 	for (;;) {
3563 		sx_xlock(&uma_drain_lock);
3564 		while (atomic_load_int(&uma_reclaim_needed) == 0)
3565 			sx_sleep(uma_reclaim, &uma_drain_lock, PVM, "umarcl",
3566 			    hz);
3567 		sx_xunlock(&uma_drain_lock);
3568 		EVENTHANDLER_INVOKE(vm_lowmem, VM_LOW_KMEM);
3569 		sx_xlock(&uma_drain_lock);
3570 		uma_reclaim_locked(true);
3571 		atomic_store_int(&uma_reclaim_needed, 0);
3572 		sx_xunlock(&uma_drain_lock);
3573 		/* Don't fire more than once per-second. */
3574 		pause("umarclslp", hz);
3575 	}
3576 }
3577 
3578 /* See uma.h */
3579 int
3580 uma_zone_exhausted(uma_zone_t zone)
3581 {
3582 	int full;
3583 
3584 	ZONE_LOCK(zone);
3585 	full = (zone->uz_flags & UMA_ZFLAG_FULL);
3586 	ZONE_UNLOCK(zone);
3587 	return (full);
3588 }
3589 
3590 int
3591 uma_zone_exhausted_nolock(uma_zone_t zone)
3592 {
3593 	return (zone->uz_flags & UMA_ZFLAG_FULL);
3594 }
3595 
3596 void *
3597 uma_large_malloc_domain(vm_size_t size, int domain, int wait)
3598 {
3599 	struct vmem *arena;
3600 	vm_offset_t addr;
3601 	uma_slab_t slab;
3602 
3603 #if VM_NRESERVLEVEL > 0
3604 	if (__predict_true((wait & M_EXEC) == 0))
3605 		arena = kernel_arena;
3606 	else
3607 		arena = kernel_rwx_arena;
3608 #else
3609 	arena = kernel_arena;
3610 #endif
3611 
3612 	slab = zone_alloc_item(slabzone, NULL, domain, wait);
3613 	if (slab == NULL)
3614 		return (NULL);
3615 	if (domain == UMA_ANYDOMAIN)
3616 		addr = kmem_malloc(arena, size, wait);
3617 	else
3618 		addr = kmem_malloc_domain(arena, domain, size, wait);
3619 	if (addr != 0) {
3620 		vsetslab(addr, slab);
3621 		slab->us_data = (void *)addr;
3622 		slab->us_flags = UMA_SLAB_KERNEL | UMA_SLAB_MALLOC;
3623 #if VM_NRESERVLEVEL > 0
3624 		if (__predict_false(arena == kernel_rwx_arena))
3625 			slab->us_flags |= UMA_SLAB_KRWX;
3626 #endif
3627 		slab->us_size = size;
3628 		slab->us_domain = vm_phys_domain(PHYS_TO_VM_PAGE(
3629 		    pmap_kextract(addr)));
3630 		uma_total_inc(size);
3631 	} else {
3632 		zone_free_item(slabzone, slab, NULL, SKIP_NONE);
3633 	}
3634 
3635 	return ((void *)addr);
3636 }
3637 
3638 void *
3639 uma_large_malloc(vm_size_t size, int wait)
3640 {
3641 
3642 	return uma_large_malloc_domain(size, UMA_ANYDOMAIN, wait);
3643 }
3644 
3645 void
3646 uma_large_free(uma_slab_t slab)
3647 {
3648 	struct vmem *arena;
3649 
3650 	KASSERT((slab->us_flags & UMA_SLAB_KERNEL) != 0,
3651 	    ("uma_large_free:  Memory not allocated with uma_large_malloc."));
3652 #if VM_NRESERVLEVEL > 0
3653 	if (__predict_true((slab->us_flags & UMA_SLAB_KRWX) == 0))
3654 		arena = kernel_arena;
3655 	else
3656 		arena = kernel_rwx_arena;
3657 #else
3658 	arena = kernel_arena;
3659 #endif
3660 	kmem_free(arena, (vm_offset_t)slab->us_data, slab->us_size);
3661 	uma_total_dec(slab->us_size);
3662 	zone_free_item(slabzone, slab, NULL, SKIP_NONE);
3663 }
3664 
3665 static void
3666 uma_zero_item(void *item, uma_zone_t zone)
3667 {
3668 
3669 	bzero(item, zone->uz_size);
3670 }
3671 
3672 unsigned long
3673 uma_limit(void)
3674 {
3675 
3676 	return (uma_kmem_limit);
3677 }
3678 
3679 void
3680 uma_set_limit(unsigned long limit)
3681 {
3682 
3683 	uma_kmem_limit = limit;
3684 }
3685 
3686 unsigned long
3687 uma_size(void)
3688 {
3689 
3690 	return (uma_kmem_total);
3691 }
3692 
3693 long
3694 uma_avail(void)
3695 {
3696 
3697 	return (uma_kmem_limit - uma_kmem_total);
3698 }
3699 
3700 void
3701 uma_print_stats(void)
3702 {
3703 	zone_foreach(uma_print_zone);
3704 }
3705 
3706 static void
3707 slab_print(uma_slab_t slab)
3708 {
3709 	printf("slab: keg %p, data %p, freecount %d\n",
3710 		slab->us_keg, slab->us_data, slab->us_freecount);
3711 }
3712 
3713 static void
3714 cache_print(uma_cache_t cache)
3715 {
3716 	printf("alloc: %p(%d), free: %p(%d)\n",
3717 		cache->uc_allocbucket,
3718 		cache->uc_allocbucket?cache->uc_allocbucket->ub_cnt:0,
3719 		cache->uc_freebucket,
3720 		cache->uc_freebucket?cache->uc_freebucket->ub_cnt:0);
3721 }
3722 
3723 static void
3724 uma_print_keg(uma_keg_t keg)
3725 {
3726 	uma_domain_t dom;
3727 	uma_slab_t slab;
3728 	int i;
3729 
3730 	printf("keg: %s(%p) size %d(%d) flags %#x ipers %d ppera %d "
3731 	    "out %d free %d limit %d\n",
3732 	    keg->uk_name, keg, keg->uk_size, keg->uk_rsize, keg->uk_flags,
3733 	    keg->uk_ipers, keg->uk_ppera,
3734 	    (keg->uk_pages / keg->uk_ppera) * keg->uk_ipers - keg->uk_free,
3735 	    keg->uk_free, (keg->uk_maxpages / keg->uk_ppera) * keg->uk_ipers);
3736 	for (i = 0; i < vm_ndomains; i++) {
3737 		dom = &keg->uk_domain[i];
3738 		printf("Part slabs:\n");
3739 		LIST_FOREACH(slab, &dom->ud_part_slab, us_link)
3740 			slab_print(slab);
3741 		printf("Free slabs:\n");
3742 		LIST_FOREACH(slab, &dom->ud_free_slab, us_link)
3743 			slab_print(slab);
3744 		printf("Full slabs:\n");
3745 		LIST_FOREACH(slab, &dom->ud_full_slab, us_link)
3746 			slab_print(slab);
3747 	}
3748 }
3749 
3750 void
3751 uma_print_zone(uma_zone_t zone)
3752 {
3753 	uma_cache_t cache;
3754 	uma_klink_t kl;
3755 	int i;
3756 
3757 	printf("zone: %s(%p) size %d flags %#x\n",
3758 	    zone->uz_name, zone, zone->uz_size, zone->uz_flags);
3759 	LIST_FOREACH(kl, &zone->uz_kegs, kl_link)
3760 		uma_print_keg(kl->kl_keg);
3761 	CPU_FOREACH(i) {
3762 		cache = &zone->uz_cpu[i];
3763 		printf("CPU %d Cache:\n", i);
3764 		cache_print(cache);
3765 	}
3766 }
3767 
3768 #ifdef DDB
3769 /*
3770  * Generate statistics across both the zone and its per-cpu cache's.  Return
3771  * desired statistics if the pointer is non-NULL for that statistic.
3772  *
3773  * Note: does not update the zone statistics, as it can't safely clear the
3774  * per-CPU cache statistic.
3775  *
3776  * XXXRW: Following the uc_allocbucket and uc_freebucket pointers here isn't
3777  * safe from off-CPU; we should modify the caches to track this information
3778  * directly so that we don't have to.
3779  */
3780 static void
3781 uma_zone_sumstat(uma_zone_t z, int *cachefreep, uint64_t *allocsp,
3782     uint64_t *freesp, uint64_t *sleepsp)
3783 {
3784 	uma_cache_t cache;
3785 	uint64_t allocs, frees, sleeps;
3786 	int cachefree, cpu;
3787 
3788 	allocs = frees = sleeps = 0;
3789 	cachefree = 0;
3790 	CPU_FOREACH(cpu) {
3791 		cache = &z->uz_cpu[cpu];
3792 		if (cache->uc_allocbucket != NULL)
3793 			cachefree += cache->uc_allocbucket->ub_cnt;
3794 		if (cache->uc_freebucket != NULL)
3795 			cachefree += cache->uc_freebucket->ub_cnt;
3796 		allocs += cache->uc_allocs;
3797 		frees += cache->uc_frees;
3798 	}
3799 	allocs += z->uz_allocs;
3800 	frees += z->uz_frees;
3801 	sleeps += z->uz_sleeps;
3802 	if (cachefreep != NULL)
3803 		*cachefreep = cachefree;
3804 	if (allocsp != NULL)
3805 		*allocsp = allocs;
3806 	if (freesp != NULL)
3807 		*freesp = frees;
3808 	if (sleepsp != NULL)
3809 		*sleepsp = sleeps;
3810 }
3811 #endif /* DDB */
3812 
3813 static int
3814 sysctl_vm_zone_count(SYSCTL_HANDLER_ARGS)
3815 {
3816 	uma_keg_t kz;
3817 	uma_zone_t z;
3818 	int count;
3819 
3820 	count = 0;
3821 	rw_rlock(&uma_rwlock);
3822 	LIST_FOREACH(kz, &uma_kegs, uk_link) {
3823 		LIST_FOREACH(z, &kz->uk_zones, uz_link)
3824 			count++;
3825 	}
3826 	rw_runlock(&uma_rwlock);
3827 	return (sysctl_handle_int(oidp, &count, 0, req));
3828 }
3829 
3830 static int
3831 sysctl_vm_zone_stats(SYSCTL_HANDLER_ARGS)
3832 {
3833 	struct uma_stream_header ush;
3834 	struct uma_type_header uth;
3835 	struct uma_percpu_stat *ups;
3836 	uma_bucket_t bucket;
3837 	uma_zone_domain_t zdom;
3838 	struct sbuf sbuf;
3839 	uma_cache_t cache;
3840 	uma_klink_t kl;
3841 	uma_keg_t kz;
3842 	uma_zone_t z;
3843 	uma_keg_t k;
3844 	int count, error, i;
3845 
3846 	error = sysctl_wire_old_buffer(req, 0);
3847 	if (error != 0)
3848 		return (error);
3849 	sbuf_new_for_sysctl(&sbuf, NULL, 128, req);
3850 	sbuf_clear_flags(&sbuf, SBUF_INCLUDENUL);
3851 	ups = malloc((mp_maxid + 1) * sizeof(*ups), M_TEMP, M_WAITOK);
3852 
3853 	count = 0;
3854 	rw_rlock(&uma_rwlock);
3855 	LIST_FOREACH(kz, &uma_kegs, uk_link) {
3856 		LIST_FOREACH(z, &kz->uk_zones, uz_link)
3857 			count++;
3858 	}
3859 
3860 	/*
3861 	 * Insert stream header.
3862 	 */
3863 	bzero(&ush, sizeof(ush));
3864 	ush.ush_version = UMA_STREAM_VERSION;
3865 	ush.ush_maxcpus = (mp_maxid + 1);
3866 	ush.ush_count = count;
3867 	(void)sbuf_bcat(&sbuf, &ush, sizeof(ush));
3868 
3869 	LIST_FOREACH(kz, &uma_kegs, uk_link) {
3870 		LIST_FOREACH(z, &kz->uk_zones, uz_link) {
3871 			bzero(&uth, sizeof(uth));
3872 			ZONE_LOCK(z);
3873 			strlcpy(uth.uth_name, z->uz_name, UTH_MAX_NAME);
3874 			uth.uth_align = kz->uk_align;
3875 			uth.uth_size = kz->uk_size;
3876 			uth.uth_rsize = kz->uk_rsize;
3877 			LIST_FOREACH(kl, &z->uz_kegs, kl_link) {
3878 				k = kl->kl_keg;
3879 				uth.uth_maxpages += k->uk_maxpages;
3880 				uth.uth_pages += k->uk_pages;
3881 				uth.uth_keg_free += k->uk_free;
3882 				uth.uth_limit = (k->uk_maxpages / k->uk_ppera)
3883 				    * k->uk_ipers;
3884 			}
3885 
3886 			/*
3887 			 * A zone is secondary is it is not the first entry
3888 			 * on the keg's zone list.
3889 			 */
3890 			if ((z->uz_flags & UMA_ZONE_SECONDARY) &&
3891 			    (LIST_FIRST(&kz->uk_zones) != z))
3892 				uth.uth_zone_flags = UTH_ZONE_SECONDARY;
3893 
3894 			for (i = 0; i < vm_ndomains; i++) {
3895 				zdom = &z->uz_domain[i];
3896 				LIST_FOREACH(bucket, &zdom->uzd_buckets,
3897 				    ub_link)
3898 					uth.uth_zone_free += bucket->ub_cnt;
3899 			}
3900 			uth.uth_allocs = z->uz_allocs;
3901 			uth.uth_frees = z->uz_frees;
3902 			uth.uth_fails = z->uz_fails;
3903 			uth.uth_sleeps = z->uz_sleeps;
3904 			/*
3905 			 * While it is not normally safe to access the cache
3906 			 * bucket pointers while not on the CPU that owns the
3907 			 * cache, we only allow the pointers to be exchanged
3908 			 * without the zone lock held, not invalidated, so
3909 			 * accept the possible race associated with bucket
3910 			 * exchange during monitoring.
3911 			 */
3912 			for (i = 0; i < mp_maxid + 1; i++) {
3913 				bzero(&ups[i], sizeof(*ups));
3914 				if (kz->uk_flags & UMA_ZFLAG_INTERNAL ||
3915 				    CPU_ABSENT(i))
3916 					continue;
3917 				cache = &z->uz_cpu[i];
3918 				if (cache->uc_allocbucket != NULL)
3919 					ups[i].ups_cache_free +=
3920 					    cache->uc_allocbucket->ub_cnt;
3921 				if (cache->uc_freebucket != NULL)
3922 					ups[i].ups_cache_free +=
3923 					    cache->uc_freebucket->ub_cnt;
3924 				ups[i].ups_allocs = cache->uc_allocs;
3925 				ups[i].ups_frees = cache->uc_frees;
3926 			}
3927 			ZONE_UNLOCK(z);
3928 			(void)sbuf_bcat(&sbuf, &uth, sizeof(uth));
3929 			for (i = 0; i < mp_maxid + 1; i++)
3930 				(void)sbuf_bcat(&sbuf, &ups[i], sizeof(ups[i]));
3931 		}
3932 	}
3933 	rw_runlock(&uma_rwlock);
3934 	error = sbuf_finish(&sbuf);
3935 	sbuf_delete(&sbuf);
3936 	free(ups, M_TEMP);
3937 	return (error);
3938 }
3939 
3940 int
3941 sysctl_handle_uma_zone_max(SYSCTL_HANDLER_ARGS)
3942 {
3943 	uma_zone_t zone = *(uma_zone_t *)arg1;
3944 	int error, max;
3945 
3946 	max = uma_zone_get_max(zone);
3947 	error = sysctl_handle_int(oidp, &max, 0, req);
3948 	if (error || !req->newptr)
3949 		return (error);
3950 
3951 	uma_zone_set_max(zone, max);
3952 
3953 	return (0);
3954 }
3955 
3956 int
3957 sysctl_handle_uma_zone_cur(SYSCTL_HANDLER_ARGS)
3958 {
3959 	uma_zone_t zone = *(uma_zone_t *)arg1;
3960 	int cur;
3961 
3962 	cur = uma_zone_get_cur(zone);
3963 	return (sysctl_handle_int(oidp, &cur, 0, req));
3964 }
3965 
3966 #ifdef INVARIANTS
3967 static uma_slab_t
3968 uma_dbg_getslab(uma_zone_t zone, void *item)
3969 {
3970 	uma_slab_t slab;
3971 	uma_keg_t keg;
3972 	uint8_t *mem;
3973 
3974 	mem = (uint8_t *)((uintptr_t)item & (~UMA_SLAB_MASK));
3975 	if (zone->uz_flags & UMA_ZONE_VTOSLAB) {
3976 		slab = vtoslab((vm_offset_t)mem);
3977 	} else {
3978 		/*
3979 		 * It is safe to return the slab here even though the
3980 		 * zone is unlocked because the item's allocation state
3981 		 * essentially holds a reference.
3982 		 */
3983 		ZONE_LOCK(zone);
3984 		keg = LIST_FIRST(&zone->uz_kegs)->kl_keg;
3985 		if (keg->uk_flags & UMA_ZONE_HASH)
3986 			slab = hash_sfind(&keg->uk_hash, mem);
3987 		else
3988 			slab = (uma_slab_t)(mem + keg->uk_pgoff);
3989 		ZONE_UNLOCK(zone);
3990 	}
3991 
3992 	return (slab);
3993 }
3994 
3995 static bool
3996 uma_dbg_zskip(uma_zone_t zone, void *mem)
3997 {
3998 	uma_keg_t keg;
3999 
4000 	if ((keg = zone_first_keg(zone)) == NULL)
4001 		return (true);
4002 
4003 	return (uma_dbg_kskip(keg, mem));
4004 }
4005 
4006 static bool
4007 uma_dbg_kskip(uma_keg_t keg, void *mem)
4008 {
4009 	uintptr_t idx;
4010 
4011 	if (dbg_divisor == 0)
4012 		return (true);
4013 
4014 	if (dbg_divisor == 1)
4015 		return (false);
4016 
4017 	idx = (uintptr_t)mem >> PAGE_SHIFT;
4018 	if (keg->uk_ipers > 1) {
4019 		idx *= keg->uk_ipers;
4020 		idx += ((uintptr_t)mem & PAGE_MASK) / keg->uk_rsize;
4021 	}
4022 
4023 	if ((idx / dbg_divisor) * dbg_divisor != idx) {
4024 		counter_u64_add(uma_skip_cnt, 1);
4025 		return (true);
4026 	}
4027 	counter_u64_add(uma_dbg_cnt, 1);
4028 
4029 	return (false);
4030 }
4031 
4032 /*
4033  * Set up the slab's freei data such that uma_dbg_free can function.
4034  *
4035  */
4036 static void
4037 uma_dbg_alloc(uma_zone_t zone, uma_slab_t slab, void *item)
4038 {
4039 	uma_keg_t keg;
4040 	int freei;
4041 
4042 	if (slab == NULL) {
4043 		slab = uma_dbg_getslab(zone, item);
4044 		if (slab == NULL)
4045 			panic("uma: item %p did not belong to zone %s\n",
4046 			    item, zone->uz_name);
4047 	}
4048 	keg = slab->us_keg;
4049 	freei = ((uintptr_t)item - (uintptr_t)slab->us_data) / keg->uk_rsize;
4050 
4051 	if (BIT_ISSET(SLAB_SETSIZE, freei, &slab->us_debugfree))
4052 		panic("Duplicate alloc of %p from zone %p(%s) slab %p(%d)\n",
4053 		    item, zone, zone->uz_name, slab, freei);
4054 	BIT_SET_ATOMIC(SLAB_SETSIZE, freei, &slab->us_debugfree);
4055 
4056 	return;
4057 }
4058 
4059 /*
4060  * Verifies freed addresses.  Checks for alignment, valid slab membership
4061  * and duplicate frees.
4062  *
4063  */
4064 static void
4065 uma_dbg_free(uma_zone_t zone, uma_slab_t slab, void *item)
4066 {
4067 	uma_keg_t keg;
4068 	int freei;
4069 
4070 	if (slab == NULL) {
4071 		slab = uma_dbg_getslab(zone, item);
4072 		if (slab == NULL)
4073 			panic("uma: Freed item %p did not belong to zone %s\n",
4074 			    item, zone->uz_name);
4075 	}
4076 	keg = slab->us_keg;
4077 	freei = ((uintptr_t)item - (uintptr_t)slab->us_data) / keg->uk_rsize;
4078 
4079 	if (freei >= keg->uk_ipers)
4080 		panic("Invalid free of %p from zone %p(%s) slab %p(%d)\n",
4081 		    item, zone, zone->uz_name, slab, freei);
4082 
4083 	if (((freei * keg->uk_rsize) + slab->us_data) != item)
4084 		panic("Unaligned free of %p from zone %p(%s) slab %p(%d)\n",
4085 		    item, zone, zone->uz_name, slab, freei);
4086 
4087 	if (!BIT_ISSET(SLAB_SETSIZE, freei, &slab->us_debugfree))
4088 		panic("Duplicate free of %p from zone %p(%s) slab %p(%d)\n",
4089 		    item, zone, zone->uz_name, slab, freei);
4090 
4091 	BIT_CLR_ATOMIC(SLAB_SETSIZE, freei, &slab->us_debugfree);
4092 }
4093 #endif /* INVARIANTS */
4094 
4095 #ifdef DDB
4096 DB_SHOW_COMMAND(uma, db_show_uma)
4097 {
4098 	uma_bucket_t bucket;
4099 	uma_keg_t kz;
4100 	uma_zone_t z;
4101 	uma_zone_domain_t zdom;
4102 	uint64_t allocs, frees, sleeps;
4103 	int cachefree, i;
4104 
4105 	db_printf("%18s %8s %8s %8s %12s %8s %8s\n", "Zone", "Size", "Used",
4106 	    "Free", "Requests", "Sleeps", "Bucket");
4107 	LIST_FOREACH(kz, &uma_kegs, uk_link) {
4108 		LIST_FOREACH(z, &kz->uk_zones, uz_link) {
4109 			if (kz->uk_flags & UMA_ZFLAG_INTERNAL) {
4110 				allocs = z->uz_allocs;
4111 				frees = z->uz_frees;
4112 				sleeps = z->uz_sleeps;
4113 				cachefree = 0;
4114 			} else
4115 				uma_zone_sumstat(z, &cachefree, &allocs,
4116 				    &frees, &sleeps);
4117 			if (!((z->uz_flags & UMA_ZONE_SECONDARY) &&
4118 			    (LIST_FIRST(&kz->uk_zones) != z)))
4119 				cachefree += kz->uk_free;
4120 			for (i = 0; i < vm_ndomains; i++) {
4121 				zdom = &z->uz_domain[i];
4122 				LIST_FOREACH(bucket, &zdom->uzd_buckets,
4123 				    ub_link)
4124 					cachefree += bucket->ub_cnt;
4125 			}
4126 			db_printf("%18s %8ju %8jd %8d %12ju %8ju %8u\n",
4127 			    z->uz_name, (uintmax_t)kz->uk_size,
4128 			    (intmax_t)(allocs - frees), cachefree,
4129 			    (uintmax_t)allocs, sleeps, z->uz_count);
4130 			if (db_pager_quit)
4131 				return;
4132 		}
4133 	}
4134 }
4135 
4136 DB_SHOW_COMMAND(umacache, db_show_umacache)
4137 {
4138 	uma_bucket_t bucket;
4139 	uma_zone_t z;
4140 	uma_zone_domain_t zdom;
4141 	uint64_t allocs, frees;
4142 	int cachefree, i;
4143 
4144 	db_printf("%18s %8s %8s %8s %12s %8s\n", "Zone", "Size", "Used", "Free",
4145 	    "Requests", "Bucket");
4146 	LIST_FOREACH(z, &uma_cachezones, uz_link) {
4147 		uma_zone_sumstat(z, &cachefree, &allocs, &frees, NULL);
4148 		for (i = 0; i < vm_ndomains; i++) {
4149 			zdom = &z->uz_domain[i];
4150 			LIST_FOREACH(bucket, &zdom->uzd_buckets, ub_link)
4151 				cachefree += bucket->ub_cnt;
4152 		}
4153 		db_printf("%18s %8ju %8jd %8d %12ju %8u\n",
4154 		    z->uz_name, (uintmax_t)z->uz_size,
4155 		    (intmax_t)(allocs - frees), cachefree,
4156 		    (uintmax_t)allocs, z->uz_count);
4157 		if (db_pager_quit)
4158 			return;
4159 	}
4160 }
4161 #endif	/* DDB */
4162