]> git.saurik.com Git - apple/xnu.git/blame - osfmk/kern/kalloc.c
xnu-6153.141.1.tar.gz
[apple/xnu.git] / osfmk / kern / kalloc.c
CommitLineData
1c79356b 1/*
316670eb 2 * Copyright (c) 2000-2011 Apple Computer, Inc. All rights reserved.
1c79356b 3 *
2d21ac55 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
0a7de745 5 *
2d21ac55
A
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
0a7de745 14 *
2d21ac55
A
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
0a7de745 17 *
2d21ac55
A
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
8f6c56a5
A
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
2d21ac55
A
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
0a7de745 25 *
2d21ac55 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
1c79356b
A
27 */
28/*
29 * @OSF_COPYRIGHT@
30 */
0a7de745 31/*
1c79356b
A
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
34 * All Rights Reserved.
0a7de745 35 *
1c79356b
A
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
0a7de745 41 *
1c79356b
A
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
0a7de745 45 *
1c79356b 46 * Carnegie Mellon requests users of this software to return to
0a7de745 47 *
1c79356b
A
48 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
49 * School of Computer Science
50 * Carnegie Mellon University
51 * Pittsburgh PA 15213-3890
0a7de745 52 *
1c79356b
A
53 * any improvements or extensions that they make and grant Carnegie Mellon
54 * the rights to redistribute these changes.
55 */
56/*
57 */
58/*
59 * File: kern/kalloc.c
60 * Author: Avadis Tevanian, Jr.
61 * Date: 1985
62 *
63 * General kernel memory allocator. This allocator is designed
64 * to be used by the kernel to manage dynamic memory fast.
65 */
66
67#include <zone_debug.h>
68
69#include <mach/boolean.h>
a39ff7e2 70#include <mach/sdt.h>
1c79356b
A
71#include <mach/machine/vm_types.h>
72#include <mach/vm_param.h>
73#include <kern/misc_protos.h>
74#include <kern/zalloc.h>
75#include <kern/kalloc.h>
316670eb 76#include <kern/ledger.h>
1c79356b
A
77#include <vm/vm_kern.h>
78#include <vm/vm_object.h>
79#include <vm/vm_map.h>
91447636 80#include <libkern/OSMalloc.h>
39037602 81#include <sys/kdebug.h>
1c79356b 82
5ba3f43e
A
83#include <san/kasan.h>
84
1c79356b
A
85#ifdef MACH_BSD
86zone_t kalloc_zone(vm_size_t);
87#endif
88
2d21ac55
A
89#define KALLOC_MAP_SIZE_MIN (16 * 1024 * 1024)
90#define KALLOC_MAP_SIZE_MAX (128 * 1024 * 1024)
1c79356b 91vm_map_t kalloc_map;
1c79356b
A
92vm_size_t kalloc_max;
93vm_size_t kalloc_max_prerounded;
0a7de745 94vm_size_t kalloc_kernmap_size; /* size of kallocs that can come from kernel map */
1c79356b 95
3e170ce0
A
96/* how many times we couldn't allocate out of kalloc_map and fell back to kernel_map */
97unsigned long kalloc_fallback_count;
98
cb323159
A
99uint_t kalloc_large_inuse;
100vm_size_t kalloc_large_total;
101vm_size_t kalloc_large_max;
102vm_size_t kalloc_largest_allocated = 0;
103uint64_t kalloc_large_sum;
6d2010ae 104
0a7de745 105int kalloc_fake_zone_index = -1; /* index of our fake zone in statistics arrays */
b0d623f7 106
0a7de745
A
107vm_offset_t kalloc_map_min;
108vm_offset_t kalloc_map_max;
1c79356b 109
0a7de745 110#ifdef MUTEX_ZONE
6d2010ae
A
111/*
112 * Diagnostic code to track mutexes separately rather than via the 2^ zones
113 */
0a7de745 114zone_t lck_mtx_zone;
6d2010ae
A
115#endif
116
117static void
118KALLOC_ZINFO_SALLOC(vm_size_t bytes)
119{
120 thread_t thr = current_thread();
316670eb 121 ledger_debit(thr->t_ledger, task_ledgers.tkm_shared, bytes);
6d2010ae
A
122}
123
124static void
125KALLOC_ZINFO_SFREE(vm_size_t bytes)
126{
127 thread_t thr = current_thread();
316670eb 128 ledger_credit(thr->t_ledger, task_ledgers.tkm_shared, bytes);
6d2010ae
A
129}
130
1c79356b 131/*
a39ff7e2
A
132 * All allocations of size less than kalloc_max are rounded to the next nearest
133 * sized zone. This allocator is built on top of the zone allocator. A zone
134 * is created for each potential size that we are willing to get in small
135 * blocks.
1c79356b 136 *
a39ff7e2 137 * We assume that kalloc_max is not greater than 64K;
1c79356b 138 *
a39ff7e2
A
139 * Note that kalloc_max is somewhat confusingly named. It represents the first
140 * power of two for which no zone exists. kalloc_max_prerounded is the
141 * smallest allocation size, before rounding, for which no zone exists.
316670eb 142 *
a39ff7e2
A
143 * Also if the allocation size is more than kalloc_kernmap_size then allocate
144 * from kernel map rather than kalloc_map.
316670eb
A
145 */
146
a39ff7e2
A
147#define KALLOC_MINALIGN (1 << KALLOC_LOG2_MINALIGN)
148#define KiB(x) (1024 * (x))
316670eb 149
0a7de745
A
150/*
151 * The k_zone_config table defines the configuration of zones on various platforms.
152 * The currently defined list of zones and their per-CPU caching behavior are as
153 * follows (X:zone not present; N:zone present no cpu-caching; Y:zone present with cpu-caching):
154 *
155 * Size macOS(64-bit) embedded(32-bit) embedded(64-bit)
156 *-------- ---------------- ---------------- ----------------
157 *
158 * 8 X Y X
159 * 16 Y Y Y
160 * 24 X Y X
161 * 32 Y Y Y
162 * 40 X Y X
163 * 48 Y Y Y
164 * 64 Y Y Y
165 * 72 X Y X
166 * 80 Y X Y
167 * 88 X Y X
168 * 96 Y X Y
169 * 112 X Y X
170 * 128 Y Y Y
171 * 160 Y X Y
172 * 192 Y Y Y
173 * 224 Y X Y
174 * 256 Y Y Y
175 * 288 Y Y Y
176 * 368 Y X Y
177 * 384 X Y X
178 * 400 Y X Y
179 * 440 X Y X
180 * 512 Y Y Y
181 * 576 Y N N
182 * 768 Y N N
183 * 1024 Y Y Y
184 * 1152 N N N
185 * 1280 N N N
186 * 1536 X N X
187 * 1664 N X N
188 * 2048 Y N N
189 * 2128 X N X
190 * 3072 X N X
191 * 4096 Y N N
192 * 6144 N N N
193 * 8192 Y N N
cb323159 194 * 12288 N X X
94ff46dc
A
195 * 16384 N X N
196 * 32768 X X N
0a7de745
A
197 *
198 */
a39ff7e2 199static const struct kalloc_zone_config {
0a7de745 200 bool kzc_caching;
a39ff7e2
A
201 int kzc_size;
202 const char *kzc_name;
203} k_zone_config[] = {
0a7de745
A
204#define KZC_ENTRY(SIZE, caching) { .kzc_caching = (caching), .kzc_size = (SIZE), .kzc_name = "kalloc." #SIZE }
205
206#if CONFIG_EMBEDDED
316670eb 207
a39ff7e2 208#if KALLOC_MINSIZE == 16 && KALLOC_LOG2_MINALIGN == 4
0a7de745
A
209 /* Zone config for embedded 64-bit platforms */
210 KZC_ENTRY(16, true),
211 KZC_ENTRY(32, true),
212 KZC_ENTRY(48, true),
213 KZC_ENTRY(64, true),
214 KZC_ENTRY(80, true),
215 KZC_ENTRY(96, true),
216 KZC_ENTRY(128, true),
217 KZC_ENTRY(160, true),
218 KZC_ENTRY(192, true),
219 KZC_ENTRY(224, true),
220 KZC_ENTRY(256, true),
221 KZC_ENTRY(288, true),
222 KZC_ENTRY(368, true),
223 KZC_ENTRY(400, true),
224 KZC_ENTRY(512, true),
225 KZC_ENTRY(576, false),
226 KZC_ENTRY(768, false),
227 KZC_ENTRY(1024, true),
228 KZC_ENTRY(1152, false),
229 KZC_ENTRY(1280, false),
230 KZC_ENTRY(1664, false),
231 KZC_ENTRY(2048, false),
232 KZC_ENTRY(4096, false),
233 KZC_ENTRY(6144, false),
234 KZC_ENTRY(8192, false),
235 KZC_ENTRY(16384, false),
236 KZC_ENTRY(32768, false),
237
316670eb 238#elif KALLOC_MINSIZE == 8 && KALLOC_LOG2_MINALIGN == 3
0a7de745
A
239 /* Zone config for embedded 32-bit platforms */
240 KZC_ENTRY(8, true),
241 KZC_ENTRY(16, true),
242 KZC_ENTRY(24, true),
243 KZC_ENTRY(32, true),
244 KZC_ENTRY(40, true),
245 KZC_ENTRY(48, true),
246 KZC_ENTRY(64, true),
247 KZC_ENTRY(72, true),
248 KZC_ENTRY(88, true),
249 KZC_ENTRY(112, true),
250 KZC_ENTRY(128, true),
251 KZC_ENTRY(192, true),
252 KZC_ENTRY(256, true),
253 KZC_ENTRY(288, true),
254 KZC_ENTRY(384, true),
255 KZC_ENTRY(440, true),
256 KZC_ENTRY(512, true),
257 KZC_ENTRY(576, false),
258 KZC_ENTRY(768, false),
259 KZC_ENTRY(1024, true),
260 KZC_ENTRY(1152, false),
261 KZC_ENTRY(1280, false),
262 KZC_ENTRY(1536, false),
263 KZC_ENTRY(2048, false),
264 KZC_ENTRY(2128, false),
265 KZC_ENTRY(3072, false),
266 KZC_ENTRY(4096, false),
267 KZC_ENTRY(6144, false),
268 KZC_ENTRY(8192, false),
94ff46dc
A
269 /* To limit internal fragmentation, only add the following zones if the
270 * page size is greater than 4K.
271 * Note that we use ARM_PGBYTES here (instead of one of the VM macros)
272 * since it's guaranteed to be a compile time constant.
273 */
274#if ARM_PGBYTES > 4096
0a7de745
A
275 KZC_ENTRY(16384, false),
276 KZC_ENTRY(32768, false),
94ff46dc 277#endif /* ARM_PGBYTES > 4096 */
0a7de745 278
316670eb 279#else
5c9f4661 280#error missing or invalid zone size parameters for kalloc
316670eb
A
281#endif
282
0a7de745
A
283#else /* CONFIG_EMBEDDED */
284
285 /* Zone config for macOS 64-bit platforms */
286 KZC_ENTRY(16, true),
287 KZC_ENTRY(32, true),
288 KZC_ENTRY(48, true),
289 KZC_ENTRY(64, true),
290 KZC_ENTRY(80, true),
291 KZC_ENTRY(96, true),
292 KZC_ENTRY(128, true),
293 KZC_ENTRY(160, true),
294 KZC_ENTRY(192, true),
295 KZC_ENTRY(224, true),
296 KZC_ENTRY(256, true),
297 KZC_ENTRY(288, true),
298 KZC_ENTRY(368, true),
299 KZC_ENTRY(400, true),
300 KZC_ENTRY(512, true),
301 KZC_ENTRY(576, true),
302 KZC_ENTRY(768, true),
303 KZC_ENTRY(1024, true),
304 KZC_ENTRY(1152, false),
305 KZC_ENTRY(1280, false),
306 KZC_ENTRY(1664, false),
307 KZC_ENTRY(2048, true),
308 KZC_ENTRY(4096, true),
309 KZC_ENTRY(6144, false),
310 KZC_ENTRY(8192, true),
cb323159
A
311 KZC_ENTRY(12288, false),
312 KZC_ENTRY(16384, false)
0a7de745
A
313
314#endif /* CONFIG_EMBEDDED */
315
a39ff7e2 316#undef KZC_ENTRY
316670eb
A
317};
318
a39ff7e2 319#define MAX_K_ZONE (int)(sizeof(k_zone_config) / sizeof(k_zone_config[0]))
316670eb
A
320
321/*
322 * Many kalloc() allocations are for small structures containing a few
323 * pointers and longs - the k_zone_dlut[] direct lookup table, indexed by
324 * size normalized to the minimum alignment, finds the right zone index
325 * for them in one dereference.
326 */
327
0a7de745
A
328#define INDEX_ZDLUT(size) \
329 (((size) + KALLOC_MINALIGN - 1) / KALLOC_MINALIGN)
330#define N_K_ZDLUT (2048 / KALLOC_MINALIGN)
331/* covers sizes [0 .. 2048 - KALLOC_MINALIGN] */
332#define MAX_SIZE_ZDLUT ((N_K_ZDLUT - 1) * KALLOC_MINALIGN)
316670eb 333
0a7de745 334static int8_t k_zone_dlut[N_K_ZDLUT]; /* table of indices into k_zone[] */
316670eb
A
335
336/*
337 * If there's no hit in the DLUT, then start searching from k_zindex_start.
338 */
339static int k_zindex_start;
340
3e170ce0 341static zone_t k_zone[MAX_K_ZONE];
1c79356b 342
316670eb
A
343/* #define KALLOC_DEBUG 1 */
344
91447636 345/* forward declarations */
91447636 346
3e170ce0 347lck_grp_t kalloc_lck_grp;
6d2010ae
A
348lck_mtx_t kalloc_lock;
349
0a7de745
A
350#define kalloc_spin_lock() lck_mtx_lock_spin(&kalloc_lock)
351#define kalloc_unlock() lck_mtx_unlock(&kalloc_lock)
6d2010ae
A
352
353
91447636
A
354/* OSMalloc local data declarations */
355static
356queue_head_t OSMalloc_tag_list;
357
6d2010ae
A
358lck_grp_t *OSMalloc_tag_lck_grp;
359lck_mtx_t OSMalloc_tag_lock;
360
0a7de745
A
361#define OSMalloc_tag_spin_lock() lck_mtx_lock_spin(&OSMalloc_tag_lock)
362#define OSMalloc_tag_unlock() lck_mtx_unlock(&OSMalloc_tag_lock)
6d2010ae 363
91447636
A
364
365/* OSMalloc forward declarations */
366void OSMalloc_init(void);
0a7de745
A
367void OSMalloc_Tagref(OSMallocTag tag);
368void OSMalloc_Tagrele(OSMallocTag tag);
91447636 369
1c79356b
A
370/*
371 * Initialize the memory allocator. This should be called only
372 * once on a system wide basis (i.e. first processor to get here
373 * does the initialization).
374 *
375 * This initializes all of the zones.
376 */
377
378void
379kalloc_init(
380 void)
381{
382 kern_return_t retval;
383 vm_offset_t min;
2d21ac55 384 vm_size_t size, kalloc_map_size;
5ba3f43e 385 vm_map_kernel_flags_t vmk_flags;
1c79356b 386
0a7de745
A
387 /*
388 * Scale the kalloc_map_size to physical memory size: stay below
b0d623f7 389 * 1/8th the total zone map size, or 128 MB (for a 32-bit kernel).
2d21ac55 390 */
b0d623f7
A
391 kalloc_map_size = (vm_size_t)(sane_size >> 5);
392#if !__LP64__
0a7de745 393 if (kalloc_map_size > KALLOC_MAP_SIZE_MAX) {
2d21ac55 394 kalloc_map_size = KALLOC_MAP_SIZE_MAX;
0a7de745 395 }
b0d623f7 396#endif /* !__LP64__ */
0a7de745 397 if (kalloc_map_size < KALLOC_MAP_SIZE_MIN) {
2d21ac55 398 kalloc_map_size = KALLOC_MAP_SIZE_MIN;
0a7de745 399 }
2d21ac55 400
5ba3f43e
A
401 vmk_flags = VM_MAP_KERNEL_FLAGS_NONE;
402 vmk_flags.vmkf_permanent = TRUE;
403
1c79356b 404 retval = kmem_suballoc(kernel_map, &min, kalloc_map_size,
0a7de745
A
405 FALSE,
406 (VM_FLAGS_ANYWHERE),
407 vmk_flags,
408 VM_KERN_MEMORY_KALLOC,
409 &kalloc_map);
91447636 410
0a7de745 411 if (retval != KERN_SUCCESS) {
1c79356b 412 panic("kalloc_init: kmem_suballoc failed");
0a7de745 413 }
1c79356b 414
b0d623f7
A
415 kalloc_map_min = min;
416 kalloc_map_max = min + kalloc_map_size - 1;
417
cb323159 418 kalloc_max = (k_zone_config[MAX_K_ZONE - 1].kzc_size << 1);
3e170ce0 419 if (kalloc_max < KiB(16)) {
0a7de745 420 kalloc_max = KiB(16);
3e170ce0
A
421 }
422 assert(kalloc_max <= KiB(64)); /* assumption made in size arrays */
1c79356b 423
1c79356b 424 kalloc_max_prerounded = kalloc_max / 2 + 1;
3e170ce0 425 /* allocations larger than 16 times kalloc_max go directly to kernel map */
0c530ab8 426 kalloc_kernmap_size = (kalloc_max * 16) + 1;
b0d623f7 427 kalloc_largest_allocated = kalloc_kernmap_size;
1c79356b
A
428
429 /*
a39ff7e2 430 * Allocate a zone for each size we are going to handle.
1c79356b 431 */
a39ff7e2
A
432 for (int i = 0; i < MAX_K_ZONE && (size = k_zone_config[i].kzc_size) < kalloc_max; i++) {
433 k_zone[i] = zinit(size, size, size, k_zone_config[i].kzc_name);
434
435 /*
436 * Don't charge the caller for the allocation, as we aren't sure how
437 * the memory will be handled.
438 */
6d2010ae 439 zone_change(k_zone[i], Z_CALLERACCT, FALSE);
5ba3f43e 440#if VM_MAX_TAG_ZONES
0a7de745
A
441 if (zone_tagging_on) {
442 zone_change(k_zone[i], Z_TAGS_ENABLED, TRUE);
443 }
5ba3f43e
A
444#endif
445 zone_change(k_zone[i], Z_KASAN_QUARANTINE, FALSE);
0a7de745
A
446 if (k_zone_config[i].kzc_caching) {
447 zone_change(k_zone[i], Z_CACHING_ENABLED, TRUE);
448 }
1c79356b 449 }
316670eb
A
450
451 /*
452 * Build the Direct LookUp Table for small allocations
453 */
a39ff7e2
A
454 size = 0;
455 for (int i = 0; i <= N_K_ZDLUT; i++, size += KALLOC_MINALIGN) {
316670eb
A
456 int zindex = 0;
457
0a7de745 458 while ((vm_size_t)k_zone_config[zindex].kzc_size < size) {
316670eb 459 zindex++;
0a7de745 460 }
316670eb
A
461
462 if (i == N_K_ZDLUT) {
463 k_zindex_start = zindex;
464 break;
465 }
466 k_zone_dlut[i] = (int8_t)zindex;
467 }
468
469#ifdef KALLOC_DEBUG
470 printf("kalloc_init: k_zindex_start %d\n", k_zindex_start);
471
472 /*
473 * Do a quick synthesis to see how well/badly we can
474 * find-a-zone for a given size.
475 * Useful when debugging/tweaking the array of zone sizes.
476 * Cache misses probably more critical than compare-branches!
477 */
a39ff7e2
A
478 for (int i = 0; i < MAX_K_ZONE; i++) {
479 vm_size_t testsize = (vm_size_t)k_zone_config[i].kzc_size - 1;
316670eb
A
480 int compare = 0;
481 int zindex;
482
483 if (testsize < MAX_SIZE_ZDLUT) {
0a7de745 484 compare += 1; /* 'if' (T) */
316670eb
A
485
486 long dindex = INDEX_ZDLUT(testsize);
487 zindex = (int)k_zone_dlut[dindex];
316670eb 488 } else if (testsize < kalloc_max_prerounded) {
0a7de745 489 compare += 2; /* 'if' (F), 'if' (T) */
316670eb
A
490
491 zindex = k_zindex_start;
a39ff7e2 492 while ((vm_size_t)k_zone_config[zindex].kzc_size < testsize) {
316670eb 493 zindex++;
0a7de745 494 compare++; /* 'while' (T) */
316670eb 495 }
0a7de745
A
496 compare++; /* 'while' (F) */
497 } else {
498 break; /* not zone-backed */
499 }
316670eb
A
500 zone_t z = k_zone[zindex];
501 printf("kalloc_init: req size %4lu: %11s took %d compare%s\n",
502 (unsigned long)testsize, z->zone_name, compare,
503 compare == 1 ? "" : "s");
504 }
505#endif
3e170ce0
A
506
507 lck_grp_init(&kalloc_lck_grp, "kalloc.large", LCK_GRP_ATTR_NULL);
508 lck_mtx_init(&kalloc_lock, &kalloc_lck_grp, LCK_ATTR_NULL);
91447636 509 OSMalloc_init();
0a7de745
A
510#ifdef MUTEX_ZONE
511 lck_mtx_zone = zinit(sizeof(struct _lck_mtx_), 1024 * 256, 4096, "lck_mtx");
3e170ce0 512#endif
316670eb 513}
6d2010ae 514
316670eb
A
515/*
516 * Given an allocation size, return the kalloc zone it belongs to.
517 * Direct LookUp Table variant.
518 */
519static __inline zone_t
520get_zone_dlut(vm_size_t size)
521{
522 long dindex = INDEX_ZDLUT(size);
523 int zindex = (int)k_zone_dlut[dindex];
0a7de745 524 return k_zone[zindex];
316670eb
A
525}
526
a39ff7e2 527/* As above, but linear search k_zone_config[] for the next zone that fits. */
316670eb
A
528
529static __inline zone_t
530get_zone_search(vm_size_t size, int zindex)
531{
532 assert(size < kalloc_max_prerounded);
533
0a7de745 534 while ((vm_size_t)k_zone_config[zindex].kzc_size < size) {
316670eb 535 zindex++;
0a7de745 536 }
316670eb 537
a39ff7e2
A
538 assert(zindex < MAX_K_ZONE &&
539 (vm_size_t)k_zone_config[zindex].kzc_size < kalloc_max);
316670eb 540
0a7de745 541 return k_zone[zindex];
1c79356b
A
542}
543
39037602
A
544static vm_size_t
545vm_map_lookup_kalloc_entry_locked(
0a7de745
A
546 vm_map_t map,
547 void *addr)
39037602
A
548{
549 boolean_t ret;
550 vm_map_entry_t vm_entry = NULL;
0a7de745 551
39037602
A
552 ret = vm_map_lookup_entry(map, (vm_map_offset_t)addr, &vm_entry);
553 if (!ret) {
0a7de745
A
554 panic("Attempting to lookup/free an address not allocated via kalloc! (vm_map_lookup_entry() failed map: %p, addr: %p)\n",
555 map, addr);
39037602
A
556 }
557 if (vm_entry->vme_start != (vm_map_offset_t)addr) {
558 panic("Attempting to lookup/free the middle of a kalloc'ed element! (map: %p, addr: %p, entry: %p)\n",
0a7de745 559 map, addr, vm_entry);
39037602
A
560 }
561 if (!vm_entry->vme_atomic) {
562 panic("Attempting to lookup/free an address not managed by kalloc! (map: %p, addr: %p, entry: %p)\n",
0a7de745 563 map, addr, vm_entry);
39037602 564 }
0a7de745 565 return vm_entry->vme_end - vm_entry->vme_start;
39037602
A
566}
567
5ba3f43e
A
568#if KASAN_KALLOC
569/*
570 * KASAN kalloc stashes the original user-requested size away in the poisoned
571 * area. Return that directly.
572 */
573vm_size_t
574kalloc_size(void *addr)
575{
576 (void)vm_map_lookup_kalloc_entry_locked; /* silence warning */
577 return kasan_user_size((vm_offset_t)addr);
578}
579#else
39037602
A
580vm_size_t
581kalloc_size(
0a7de745 582 void *addr)
39037602 583{
0a7de745
A
584 vm_map_t map;
585 vm_size_t size;
39037602
A
586
587 size = zone_element_size(addr, NULL);
588 if (size) {
589 return size;
590 }
591 if (((vm_offset_t)addr >= kalloc_map_min) && ((vm_offset_t)addr < kalloc_map_max)) {
592 map = kalloc_map;
593 } else {
594 map = kernel_map;
595 }
596 vm_map_lock_read(map);
597 size = vm_map_lookup_kalloc_entry_locked(map, addr);
598 vm_map_unlock_read(map);
599 return size;
600}
5ba3f43e 601#endif
39037602
A
602
603vm_size_t
604kalloc_bucket_size(
0a7de745 605 vm_size_t size)
39037602 606{
0a7de745
A
607 zone_t z;
608 vm_map_t map;
609
39037602
A
610 if (size < MAX_SIZE_ZDLUT) {
611 z = get_zone_dlut(size);
612 return z->elem_size;
0a7de745
A
613 }
614
39037602
A
615 if (size < kalloc_max_prerounded) {
616 z = get_zone_search(size, k_zindex_start);
617 return z->elem_size;
618 }
619
0a7de745 620 if (size >= kalloc_kernmap_size) {
39037602 621 map = kernel_map;
0a7de745 622 } else {
39037602 623 map = kalloc_map;
0a7de745
A
624 }
625
39037602
A
626 return vm_map_round_page(size, VM_MAP_PAGE_MASK(map));
627}
628
5ba3f43e
A
629#if KASAN_KALLOC
630vm_size_t
0a7de745 631(kfree_addr)(void *addr)
5ba3f43e
A
632{
633 vm_size_t origsz = kalloc_size(addr);
634 kfree(addr, origsz);
635 return origsz;
636}
637#else
39037602 638vm_size_t
0a7de745
A
639(kfree_addr)(
640 void *addr)
39037602
A
641{
642 vm_map_t map;
643 vm_size_t size = 0;
0a7de745
A
644 kern_return_t ret;
645 zone_t z;
39037602
A
646
647 size = zone_element_size(addr, &z);
648 if (size) {
a39ff7e2 649 DTRACE_VM3(kfree, vm_size_t, -1, vm_size_t, z->elem_size, void*, addr);
39037602
A
650 zfree(z, addr);
651 return size;
652 }
653
654 if (((vm_offset_t)addr >= kalloc_map_min) && ((vm_offset_t)addr < kalloc_map_max)) {
655 map = kalloc_map;
656 } else {
657 map = kernel_map;
658 }
659 if ((vm_offset_t)addr < VM_MIN_KERNEL_AND_KEXT_ADDRESS) {
660 panic("kfree on an address not in the kernel & kext address range! addr: %p\n", addr);
661 }
662
663 vm_map_lock(map);
664 size = vm_map_lookup_kalloc_entry_locked(map, addr);
665 ret = vm_map_remove_locked(map,
0a7de745
A
666 vm_map_trunc_page((vm_map_offset_t)addr,
667 VM_MAP_PAGE_MASK(map)),
668 vm_map_round_page((vm_map_offset_t)addr + size,
669 VM_MAP_PAGE_MASK(map)),
670 VM_MAP_REMOVE_KUNWIRE);
39037602
A
671 if (ret != KERN_SUCCESS) {
672 panic("vm_map_remove_locked() failed for kalloc vm_entry! addr: %p, map: %p ret: %d\n",
0a7de745 673 addr, map, ret);
39037602
A
674 }
675 vm_map_unlock(map);
a39ff7e2 676 DTRACE_VM3(kfree, vm_size_t, -1, vm_size_t, size, void*, addr);
0a7de745 677
39037602 678 kalloc_spin_lock();
cb323159 679 assert(kalloc_large_total >= size);
39037602
A
680 kalloc_large_total -= size;
681 kalloc_large_inuse--;
682 kalloc_unlock();
683
684 KALLOC_ZINFO_SFREE(size);
685 return size;
686}
5ba3f43e
A
687#endif
688
91447636 689void *
1c79356b 690kalloc_canblock(
cb323159
A
691 vm_size_t *psize,
692 boolean_t canblock,
693 vm_allocation_site_t *site)
1c79356b 694{
316670eb 695 zone_t z;
39037602 696 vm_size_t size;
5ba3f43e
A
697 void *addr;
698 vm_tag_t tag;
39037602 699
5ba3f43e 700 tag = VM_KERN_MEMORY_KALLOC;
39037602 701 size = *psize;
316670eb 702
5ba3f43e
A
703#if KASAN_KALLOC
704 /* expand the allocation to accomodate redzones */
705 vm_size_t req_size = size;
706 size = kasan_alloc_resize(req_size);
707#endif
708
0a7de745 709 if (size < MAX_SIZE_ZDLUT) {
316670eb 710 z = get_zone_dlut(size);
0a7de745 711 } else if (size < kalloc_max_prerounded) {
316670eb 712 z = get_zone_search(size, k_zindex_start);
0a7de745 713 } else {
316670eb
A
714 /*
715 * If size is too large for a zone, then use kmem_alloc.
716 * (We use kmem_alloc instead of kmem_alloc_kobject so that
717 * krealloc can use kmem_realloc.)
718 */
719 vm_map_t alloc_map;
1c79356b
A
720
721 /* kmem_alloc could block so we return if noblock */
722 if (!canblock) {
0a7de745 723 return NULL;
1c79356b 724 }
0c530ab8 725
5ba3f43e
A
726#if KASAN_KALLOC
727 /* large allocation - use guard pages instead of small redzones */
728 size = round_page(req_size + 2 * PAGE_SIZE);
729 assert(size >= MAX_SIZE_ZDLUT && size >= kalloc_max_prerounded);
cb323159
A
730#else
731 size = round_page(size);
5ba3f43e
A
732#endif
733
0a7de745
A
734 if (size >= kalloc_kernmap_size) {
735 alloc_map = kernel_map;
736 } else {
0c530ab8 737 alloc_map = kalloc_map;
0a7de745 738 }
0c530ab8 739
0a7de745
A
740 if (site) {
741 tag = vm_tag_alloc(site);
742 }
3e170ce0 743
39037602 744 if (kmem_alloc_flags(alloc_map, (vm_offset_t *)&addr, size, tag, KMA_ATOMIC) != KERN_SUCCESS) {
b0d623f7 745 if (alloc_map != kernel_map) {
3e170ce0
A
746 if (kalloc_fallback_count++ == 0) {
747 printf("%s: falling back to kernel_map\n", __func__);
748 }
0a7de745 749 if (kmem_alloc_flags(kernel_map, (vm_offset_t *)&addr, size, tag, KMA_ATOMIC) != KERN_SUCCESS) {
b0d623f7 750 addr = NULL;
0a7de745
A
751 }
752 } else {
b0d623f7 753 addr = NULL;
0a7de745 754 }
b0d623f7 755 }
1c79356b 756
b0d623f7 757 if (addr != NULL) {
6d2010ae
A
758 kalloc_spin_lock();
759 /*
760 * Thread-safe version of the workaround for 4740071
761 * (a double FREE())
762 */
0a7de745 763 if (size > kalloc_largest_allocated) {
6d2010ae 764 kalloc_largest_allocated = size;
0a7de745 765 }
6d2010ae 766
0a7de745 767 kalloc_large_inuse++;
cb323159 768 assert(kalloc_large_total + size >= kalloc_large_total); /* no wrap around */
0a7de745 769 kalloc_large_total += size;
6d2010ae 770 kalloc_large_sum += size;
1c79356b 771
0a7de745
A
772 if (kalloc_large_total > kalloc_large_max) {
773 kalloc_large_max = kalloc_large_total;
774 }
6d2010ae
A
775
776 kalloc_unlock();
777
778 KALLOC_ZINFO_SALLOC(size);
1c79356b 779 }
5ba3f43e
A
780#if KASAN_KALLOC
781 /* fixup the return address to skip the redzone */
782 addr = (void *)kasan_alloc((vm_offset_t)addr, size, req_size, PAGE_SIZE);
783#else
cb323159 784 *psize = size;
5ba3f43e 785#endif
a39ff7e2 786 DTRACE_VM3(kalloc, vm_size_t, size, vm_size_t, *psize, void*, addr);
0a7de745 787 return addr;
1c79356b 788 }
316670eb 789#ifdef KALLOC_DEBUG
0a7de745 790 if (size > z->elem_size) {
316670eb
A
791 panic("%s: z %p (%s) but requested size %lu", __func__,
792 z, z->zone_name, (unsigned long)size);
0a7de745 793 }
316670eb 794#endif
5ba3f43e 795
316670eb 796 assert(size <= z->elem_size);
5ba3f43e
A
797
798#if VM_MAX_TAG_ZONES
0a7de745 799 if (z->tags && site) {
5ba3f43e 800 tag = vm_tag_alloc(site);
0a7de745
A
801 if (!canblock && !vm_allocation_zone_totals[tag]) {
802 tag = VM_KERN_MEMORY_KALLOC;
803 }
804 }
5ba3f43e
A
805#endif
806
807 addr = zalloc_canblock_tag(z, canblock, size, tag);
808
809#if KASAN_KALLOC
810 /* fixup the return address to skip the redzone */
811 addr = (void *)kasan_alloc((vm_offset_t)addr, z->elem_size, req_size, KASAN_GUARD_SIZE);
812
813 /* For KASan, the redzone lives in any additional space, so don't
814 * expand the allocation. */
815#else
39037602 816 *psize = z->elem_size;
5ba3f43e
A
817#endif
818
a39ff7e2 819 DTRACE_VM3(kalloc, vm_size_t, size, vm_size_t, *psize, void*, addr);
39037602 820 return addr;
1c79356b
A
821}
822
91447636 823void *
3e170ce0 824kalloc_external(
0a7de745 825 vm_size_t size);
91447636 826void *
3e170ce0 827kalloc_external(
0a7de745 828 vm_size_t size)
1c79356b 829{
0a7de745 830 return kalloc_tag_bt(size, VM_KERN_MEMORY_KALLOC);
1c79356b
A
831}
832
1c79356b 833void
0a7de745
A
834(kfree)(
835 void *data,
836 vm_size_t size)
1c79356b 837{
316670eb
A
838 zone_t z;
839
5ba3f43e
A
840#if KASAN_KALLOC
841 /*
842 * Resize back to the real allocation size and hand off to the KASan
843 * quarantine. `data` may then point to a different allocation.
844 */
845 vm_size_t user_size = size;
846 kasan_check_free((vm_address_t)data, size, KASAN_HEAP_KALLOC);
847 data = (void *)kasan_dealloc((vm_address_t)data, &size);
848 kasan_free(&data, &size, KASAN_HEAP_KALLOC, NULL, user_size, true);
849 if (!data) {
850 return;
851 }
852#endif
853
0a7de745 854 if (size < MAX_SIZE_ZDLUT) {
316670eb 855 z = get_zone_dlut(size);
0a7de745 856 } else if (size < kalloc_max_prerounded) {
316670eb 857 z = get_zone_search(size, k_zindex_start);
0a7de745 858 } else {
316670eb 859 /* if size was too large for a zone, then use kmem_free */
1c79356b 860
316670eb 861 vm_map_t alloc_map = kernel_map;
ea3f0419 862 size = round_page(size);
1c79356b 863
0a7de745 864 if ((((vm_offset_t) data) >= kalloc_map_min) && (((vm_offset_t) data) <= kalloc_map_max)) {
b0d623f7 865 alloc_map = kalloc_map;
0a7de745 866 }
b0d623f7 867 if (size > kalloc_largest_allocated) {
d9a64523 868 panic("kfree: size %lu > kalloc_largest_allocated %lu", (unsigned long)size, (unsigned long)kalloc_largest_allocated);
b0d623f7 869 }
0c530ab8 870 kmem_free(alloc_map, (vm_offset_t)data, size);
6d2010ae
A
871 kalloc_spin_lock();
872
cb323159 873 assert(kalloc_large_total >= size);
1c79356b
A
874 kalloc_large_total -= size;
875 kalloc_large_inuse--;
876
6d2010ae
A
877 kalloc_unlock();
878
a39ff7e2
A
879#if !KASAN_KALLOC
880 DTRACE_VM3(kfree, vm_size_t, size, vm_size_t, size, void*, data);
881#endif
882
6d2010ae 883 KALLOC_ZINFO_SFREE(size);
1c79356b
A
884 return;
885 }
886
1c79356b 887 /* free to the appropriate zone */
316670eb 888#ifdef KALLOC_DEBUG
0a7de745 889 if (size > z->elem_size) {
316670eb
A
890 panic("%s: z %p (%s) but requested size %lu", __func__,
891 z, z->zone_name, (unsigned long)size);
0a7de745 892 }
316670eb
A
893#endif
894 assert(size <= z->elem_size);
d9a64523 895#if !KASAN_KALLOC
a39ff7e2 896 DTRACE_VM3(kfree, vm_size_t, size, vm_size_t, z->elem_size, void*, data);
d9a64523 897#endif
316670eb 898 zfree(z, data);
1c79356b
A
899}
900
901#ifdef MACH_BSD
902zone_t
903kalloc_zone(
904 vm_size_t size)
905{
0a7de745
A
906 if (size < MAX_SIZE_ZDLUT) {
907 return get_zone_dlut(size);
908 }
909 if (size <= kalloc_max) {
910 return get_zone_search(size, k_zindex_start);
911 }
912 return ZONE_NULL;
1c79356b
A
913}
914#endif
915
91447636
A
916void
917OSMalloc_init(
918 void)
919{
920 queue_init(&OSMalloc_tag_list);
6d2010ae
A
921
922 OSMalloc_tag_lck_grp = lck_grp_alloc_init("OSMalloc_tag", LCK_GRP_ATTR_NULL);
923 lck_mtx_init(&OSMalloc_tag_lock, OSMalloc_tag_lck_grp, LCK_ATTR_NULL);
91447636
A
924}
925
926OSMallocTag
927OSMalloc_Tagalloc(
0a7de745
A
928 const char *str,
929 uint32_t flags)
91447636
A
930{
931 OSMallocTag OSMTag;
932
933 OSMTag = (OSMallocTag)kalloc(sizeof(*OSMTag));
934
935 bzero((void *)OSMTag, sizeof(*OSMTag));
936
0a7de745 937 if (flags & OSMT_PAGEABLE) {
91447636 938 OSMTag->OSMT_attr = OSMT_ATTR_PAGEABLE;
0a7de745 939 }
91447636
A
940
941 OSMTag->OSMT_refcnt = 1;
942
3e170ce0 943 strlcpy(OSMTag->OSMT_name, str, OSMT_MAX_NAME);
91447636 944
6d2010ae 945 OSMalloc_tag_spin_lock();
91447636 946 enqueue_tail(&OSMalloc_tag_list, (queue_entry_t)OSMTag);
6d2010ae 947 OSMalloc_tag_unlock();
91447636 948 OSMTag->OSMT_state = OSMT_VALID;
0a7de745 949 return OSMTag;
91447636
A
950}
951
952void
953OSMalloc_Tagref(
0a7de745 954 OSMallocTag tag)
91447636 955{
0a7de745 956 if (!((tag->OSMT_state & OSMT_VALID_MASK) == OSMT_VALID)) {
316670eb 957 panic("OSMalloc_Tagref():'%s' has bad state 0x%08X\n", tag->OSMT_name, tag->OSMT_state);
0a7de745 958 }
91447636 959
cb323159 960 os_atomic_inc(&tag->OSMT_refcnt, relaxed);
91447636
A
961}
962
963void
964OSMalloc_Tagrele(
0a7de745 965 OSMallocTag tag)
91447636 966{
0a7de745 967 if (!((tag->OSMT_state & OSMT_VALID_MASK) == OSMT_VALID)) {
316670eb 968 panic("OSMalloc_Tagref():'%s' has bad state 0x%08X\n", tag->OSMT_name, tag->OSMT_state);
0a7de745 969 }
91447636 970
cb323159
A
971 if (os_atomic_dec(&tag->OSMT_refcnt, relaxed) == 0) {
972 if (os_atomic_cmpxchg(&tag->OSMT_state, OSMT_VALID | OSMT_RELEASED, OSMT_VALID | OSMT_RELEASED, acq_rel)) {
6d2010ae 973 OSMalloc_tag_spin_lock();
91447636 974 (void)remque((queue_entry_t)tag);
6d2010ae 975 OSMalloc_tag_unlock();
0a7de745
A
976 kfree(tag, sizeof(*tag));
977 } else {
316670eb 978 panic("OSMalloc_Tagrele():'%s' has refcnt 0\n", tag->OSMT_name);
0a7de745 979 }
91447636
A
980 }
981}
982
983void
984OSMalloc_Tagfree(
0a7de745 985 OSMallocTag tag)
91447636 986{
cb323159 987 if (!os_atomic_cmpxchg(&tag->OSMT_state, OSMT_VALID, OSMT_VALID | OSMT_RELEASED, acq_rel)) {
316670eb 988 panic("OSMalloc_Tagfree():'%s' has bad state 0x%08X \n", tag->OSMT_name, tag->OSMT_state);
0a7de745 989 }
91447636 990
cb323159 991 if (os_atomic_dec(&tag->OSMT_refcnt, relaxed) == 0) {
6d2010ae 992 OSMalloc_tag_spin_lock();
91447636 993 (void)remque((queue_entry_t)tag);
6d2010ae 994 OSMalloc_tag_unlock();
0a7de745 995 kfree(tag, sizeof(*tag));
91447636
A
996 }
997}
998
999void *
1000OSMalloc(
0a7de745
A
1001 uint32_t size,
1002 OSMallocTag tag)
91447636 1003{
0a7de745
A
1004 void *addr = NULL;
1005 kern_return_t kr;
91447636
A
1006
1007 OSMalloc_Tagref(tag);
1008 if ((tag->OSMT_attr & OSMT_PAGEABLE)
1009 && (size & ~PAGE_MASK)) {
0a7de745 1010 if ((kr = kmem_alloc_pageable_external(kernel_map, (vm_offset_t *)&addr, size)) != KERN_SUCCESS) {
2d21ac55 1011 addr = NULL;
0a7de745
A
1012 }
1013 } else {
3e170ce0 1014 addr = kalloc_tag_bt((vm_size_t)size, VM_KERN_MEMORY_KALLOC);
0a7de745 1015 }
91447636 1016
0a7de745 1017 if (!addr) {
2d21ac55 1018 OSMalloc_Tagrele(tag);
0a7de745 1019 }
2d21ac55 1020
0a7de745 1021 return addr;
91447636
A
1022}
1023
1024void *
1025OSMalloc_nowait(
0a7de745
A
1026 uint32_t size,
1027 OSMallocTag tag)
91447636 1028{
0a7de745 1029 void *addr = NULL;
91447636 1030
0a7de745
A
1031 if (tag->OSMT_attr & OSMT_PAGEABLE) {
1032 return NULL;
1033 }
91447636
A
1034
1035 OSMalloc_Tagref(tag);
1036 /* XXX: use non-blocking kalloc for now */
3e170ce0 1037 addr = kalloc_noblock_tag_bt((vm_size_t)size, VM_KERN_MEMORY_KALLOC);
0a7de745 1038 if (addr == NULL) {
91447636 1039 OSMalloc_Tagrele(tag);
0a7de745 1040 }
91447636 1041
0a7de745 1042 return addr;
91447636
A
1043}
1044
1045void *
1046OSMalloc_noblock(
0a7de745
A
1047 uint32_t size,
1048 OSMallocTag tag)
91447636 1049{
0a7de745 1050 void *addr = NULL;
91447636 1051
0a7de745
A
1052 if (tag->OSMT_attr & OSMT_PAGEABLE) {
1053 return NULL;
1054 }
91447636
A
1055
1056 OSMalloc_Tagref(tag);
3e170ce0 1057 addr = kalloc_noblock_tag_bt((vm_size_t)size, VM_KERN_MEMORY_KALLOC);
0a7de745 1058 if (addr == NULL) {
91447636 1059 OSMalloc_Tagrele(tag);
0a7de745 1060 }
91447636 1061
0a7de745 1062 return addr;
91447636
A
1063}
1064
1065void
1066OSFree(
0a7de745
A
1067 void *addr,
1068 uint32_t size,
1069 OSMallocTag tag)
91447636
A
1070{
1071 if ((tag->OSMT_attr & OSMT_PAGEABLE)
1072 && (size & ~PAGE_MASK)) {
1073 kmem_free(kernel_map, (vm_offset_t)addr, size);
0a7de745
A
1074 } else {
1075 kfree(addr, size);
1076 }
91447636
A
1077
1078 OSMalloc_Tagrele(tag);
1079}
39037602
A
1080
1081uint32_t
1082OSMalloc_size(
0a7de745 1083 void *addr)
39037602
A
1084{
1085 return (uint32_t)kalloc_size(addr);
1086}