1 /*
2 * Copyright (c) 2000-2021 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
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.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
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
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
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.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28 /*
29 * @OSF_COPYRIGHT@
30 */
31 /*
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
34 * All Rights Reserved.
35 *
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.
41 *
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.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 * Software Distribution Coordinator or [email protected]
49 * School of Computer Science
50 * Carnegie Mellon University
51 * Pittsburgh PA 15213-3890
52 *
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 <mach/boolean.h>
68 #include <mach/sdt.h>
69 #include <mach/machine/vm_types.h>
70 #include <mach/vm_param.h>
71 #include <kern/misc_protos.h>
72 #include <kern/counter.h>
73 #include <kern/zalloc_internal.h>
74 #include <kern/kalloc.h>
75 #include <kern/ledger.h>
76 #include <kern/backtrace.h>
77 #include <vm/vm_kern.h>
78 #include <vm/vm_object.h>
79 #include <vm/vm_map.h>
80 #include <sys/kdebug.h>
81
82 #include <os/hash.h>
83 #include <san/kasan.h>
84 #include <libkern/section_keywords.h>
85 #include <libkern/prelink.h>
86
87 SCALABLE_COUNTER_DEFINE(kalloc_large_count);
88 SCALABLE_COUNTER_DEFINE(kalloc_large_total);
89
90 #pragma mark initialization
91
92 /*
93 * All allocations of size less than KHEAP_MAX_SIZE are rounded to the next nearest
94 * sized zone. This allocator is built on top of the zone allocator. A zone
95 * is created for each potential size that we are willing to get in small
96 * blocks.
97 *
98 * Allocations of size greater than KHEAP_MAX_SIZE, are allocated from the VM.
99 */
100
101 /*
102 * The kt_zone_cfg table defines the configuration of zones on various
103 * platforms for kalloc_type fixed size allocations. The currently defined
104 * list of zones and their per-CPU caching behavior are as follows
105 *
106 * X:zone not present
107 * N:zone present no cpu-caching
108 * Y:zone present with cpu-caching
109 *
110 * Size macOS(64-bit) embedded(32-bit) embedded(64-bit)
111 *-------- ---------------- ---------------- ----------------
112 *
113 * 8 X Y X
114 * 16 Y Y Y
115 * 24 X Y X
116 * 32 Y Y Y
117 * 40 X Y X
118 * 48 Y Y Y
119 * 64 Y Y Y
120 * 72 X Y X
121 * 80 Y X Y
122 * 88 X Y X
123 * 96 Y X Y
124 * 112 X Y X
125 * 128 Y Y Y
126 * 160 Y X Y
127 * 192 Y Y Y
128 * 224 Y X Y
129 * 256 Y Y Y
130 * 288 Y Y Y
131 * 368 Y X Y
132 * 384 X Y X
133 * 400 Y X Y
134 * 440 X Y X
135 * 512 Y Y Y
136 * 576 Y N N
137 * 768 Y N N
138 * 1024 Y Y Y
139 * 1152 N N N
140 * 1280 N N N
141 * 1536 X N X
142 * 1664 N X N
143 * 2048 Y N N
144 * 2128 X N X
145 * 3072 X N X
146 * 4096 Y N N
147 * 6144 N N N
148 * 8192 Y N N
149 * 12288 N X X
150 * 16384 N X N
151 * 32768 X X N
152 *
153 */
154 struct kalloc_zone_cfg {
155 bool kzc_caching;
156 uint32_t kzc_size;
157 char kzc_name[MAX_ZONE_NAME];
158 };
159
160 #define KZC_ENTRY(SIZE, caching) { \
161 .kzc_caching = (caching), \
162 .kzc_size = (SIZE), \
163 .kzc_name = "kalloc." #SIZE \
164 }
165 static SECURITY_READ_ONLY_LATE(struct kalloc_zone_cfg) kt_zone_cfg[] = {
166 #if !defined(XNU_TARGET_OS_OSX)
167
168 #if KALLOC_MINSIZE == 16 && KALLOC_LOG2_MINALIGN == 4
169 /* Zone config for embedded 64-bit platforms */
170 KZC_ENTRY(16, true),
171 KZC_ENTRY(32, true),
172 KZC_ENTRY(48, true),
173 KZC_ENTRY(64, true),
174 KZC_ENTRY(80, true),
175 KZC_ENTRY(96, true),
176 KZC_ENTRY(128, true),
177 KZC_ENTRY(160, true),
178 KZC_ENTRY(192, true),
179 KZC_ENTRY(224, true),
180 KZC_ENTRY(256, true),
181 KZC_ENTRY(288, true),
182 KZC_ENTRY(368, true),
183 KZC_ENTRY(400, true),
184 KZC_ENTRY(512, true),
185 KZC_ENTRY(576, false),
186 KZC_ENTRY(768, false),
187 KZC_ENTRY(1024, true),
188 KZC_ENTRY(1152, false),
189 KZC_ENTRY(1280, false),
190 KZC_ENTRY(1664, false),
191 KZC_ENTRY(2048, false),
192 KZC_ENTRY(4096, false),
193 KZC_ENTRY(6144, false),
194 KZC_ENTRY(8192, false),
195 KZC_ENTRY(16384, false),
196 KZC_ENTRY(32768, false),
197
198 #elif KALLOC_MINSIZE == 8 && KALLOC_LOG2_MINALIGN == 3
199 /* Zone config for embedded 32-bit platforms */
200 KZC_ENTRY(8, true),
201 KZC_ENTRY(16, true),
202 KZC_ENTRY(24, true),
203 KZC_ENTRY(32, true),
204 KZC_ENTRY(40, true),
205 KZC_ENTRY(48, true),
206 KZC_ENTRY(64, true),
207 KZC_ENTRY(72, true),
208 KZC_ENTRY(88, true),
209 KZC_ENTRY(112, true),
210 KZC_ENTRY(128, true),
211 KZC_ENTRY(192, true),
212 KZC_ENTRY(256, true),
213 KZC_ENTRY(288, true),
214 KZC_ENTRY(384, true),
215 KZC_ENTRY(440, true),
216 KZC_ENTRY(512, true),
217 KZC_ENTRY(576, false),
218 KZC_ENTRY(768, false),
219 KZC_ENTRY(1024, true),
220 KZC_ENTRY(1152, false),
221 KZC_ENTRY(1280, false),
222 KZC_ENTRY(1536, false),
223 KZC_ENTRY(2048, false),
224 KZC_ENTRY(2128, false),
225 KZC_ENTRY(3072, false),
226 KZC_ENTRY(4096, false),
227 KZC_ENTRY(6144, false),
228 KZC_ENTRY(8192, false),
229 /* To limit internal fragmentation, only add the following zones if the
230 * page size is greater than 4K.
231 * Note that we use ARM_PGBYTES here (instead of one of the VM macros)
232 * since it's guaranteed to be a compile time constant.
233 */
234 #if ARM_PGBYTES > 4096
235 KZC_ENTRY(16384, false),
236 KZC_ENTRY(32768, false),
237 #endif /* ARM_PGBYTES > 4096 */
238
239 #else
240 #error missing or invalid zone size parameters for kalloc
241 #endif
242
243 #else /* !defined(XNU_TARGET_OS_OSX) */
244
245 /* Zone config for macOS 64-bit platforms */
246 KZC_ENTRY(16, true),
247 KZC_ENTRY(32, true),
248 KZC_ENTRY(48, true),
249 KZC_ENTRY(64, true),
250 KZC_ENTRY(80, true),
251 KZC_ENTRY(96, true),
252 KZC_ENTRY(128, true),
253 KZC_ENTRY(160, true),
254 KZC_ENTRY(192, true),
255 KZC_ENTRY(224, true),
256 KZC_ENTRY(256, true),
257 KZC_ENTRY(288, true),
258 KZC_ENTRY(368, true),
259 KZC_ENTRY(400, true),
260 KZC_ENTRY(512, true),
261 KZC_ENTRY(576, true),
262 KZC_ENTRY(768, true),
263 KZC_ENTRY(1024, true),
264 KZC_ENTRY(1152, false),
265 KZC_ENTRY(1280, false),
266 KZC_ENTRY(1664, false),
267 KZC_ENTRY(2048, true),
268 KZC_ENTRY(4096, true),
269 KZC_ENTRY(6144, false),
270 KZC_ENTRY(8192, true),
271 #if __x86_64__
272 KZC_ENTRY(12288, false),
273 #endif /* __x86_64__ */
274 KZC_ENTRY(16384, false),
275 #if __arm64__
276 KZC_ENTRY(32768, false),
277 #endif
278 #endif /* !defined(XNU_TARGET_OS_OSX) */
279 };
280 #undef KZC_ENTRY
281
282 #define MAX_K_ZONE(kzc) (uint32_t)(sizeof(kzc) / sizeof(kzc[0]))
283
284 /*
285 * kalloc_type callsites are assigned a zone during early boot. They
286 * use the dlut[] (direct lookup table), indexed by size normalized
287 * to the minimum alignment to find the right zone index quickly.
288 */
289 #define INDEX_ZDLUT(size) (((size) + KALLOC_MINALIGN - 1) / KALLOC_MINALIGN)
290 #define KALLOC_DLUT_SIZE (KHEAP_MAX_SIZE / KALLOC_MINALIGN)
291 #define MAX_SIZE_ZDLUT ((KALLOC_DLUT_SIZE - 1) * KALLOC_MINALIGN)
292 __startup_data uint8_t kalloc_type_dlut[KALLOC_DLUT_SIZE];
293 __startup_data size_t kheap_zsize[KHEAP_NUM_ZONES];
294
295 #if VM_TAG_SIZECLASSES
296 static_assert(VM_TAG_SIZECLASSES >= MAX_K_ZONE(kt_zone_cfg));
297 #endif
298
299 const char * const kalloc_heap_names[] = {
300 [KHEAP_ID_NONE] = "",
301 [KHEAP_ID_DEFAULT] = "default.",
302 [KHEAP_ID_DATA_BUFFERS] = "data.",
303 [KHEAP_ID_KT_VAR] = "",
304 };
305
306 /*
307 * Default kalloc heap configuration
308 */
309 SECURITY_READ_ONLY_LATE(struct kalloc_heap) KHEAP_DEFAULT[1] = {
310 {
311 .kh_name = "default.",
312 .kh_heap_id = KHEAP_ID_DEFAULT,
313 .kh_tag = VM_KERN_MEMORY_KALLOC
314 }
315 };
316
317
318 /*
319 * Bag of bytes heap configuration
320 */
321 SECURITY_READ_ONLY_LATE(struct kalloc_heap) KHEAP_DATA_BUFFERS[1] = {
322 {
323 .kh_name = "data.",
324 .kh_heap_id = KHEAP_ID_DATA_BUFFERS,
325 .kh_tag = VM_KERN_MEMORY_KALLOC_DATA,
326 }
327 };
328
329 /*
330 * Configuration of variable kalloc type heaps
331 */
332 SECURITY_READ_ONLY_LATE(struct kheap_info)
333 kalloc_type_heap_array[KT_VAR_MAX_HEAPS] = {};
334 SECURITY_READ_ONLY_LATE(struct kalloc_heap) KHEAP_KT_VAR[1] = {
335 {
336 .kh_name = "kalloc.type.var",
337 .kh_heap_id = KHEAP_ID_KT_VAR,
338 .kh_tag = VM_KERN_MEMORY_KALLOC_TYPE
339 }
340 };
341
342 __startup_func
343 static void
kalloc_zsize_compute(void)344 kalloc_zsize_compute(void)
345 {
346 size_t step = KHEAP_STEP_START;
347 uint32_t start = 0;
348 /*
349 * Manually initialize extra initial zones
350 */
351 kheap_zsize[start] = 16;
352 kheap_zsize[start + 1] = KHEAP_START_SIZE;
353
354 /*
355 * Compute sizes for remaining zones
356 */
357 for (uint32_t i = 0; i < KHEAP_NUM_STEPS; i++) {
358 uint32_t step_idx = (i * 2) + KHEAP_EXTRA_ZONES;
359 kheap_zsize[step_idx] = kheap_zsize[step_idx - 1] + step;
360 kheap_zsize[step_idx + 1] = kheap_zsize[step_idx] + step;
361 step *= 2;
362 }
363 }
364
365 static zone_t
kalloc_zone_for_size_with_flags(zone_id_t zid,vm_size_t size,zalloc_flags_t flags)366 kalloc_zone_for_size_with_flags(
367 zone_id_t zid,
368 vm_size_t size,
369 zalloc_flags_t flags)
370 {
371 vm_size_t max_size = KHEAP_MAX_SIZE;
372 bool forcopyin = flags & Z_MAY_COPYINMAP;
373
374 if (forcopyin) {
375 #if __x86_64__
376 /*
377 * On Intel, the OSData() ABI used to allocate
378 * from the kernel map starting at PAGE_SIZE.
379 *
380 * If only vm_map_copyin() or a wrapper is used,
381 * then everything will work fine because vm_map_copy_t
382 * will perform an actual copy if the data is smaller
383 * than msg_ool_size_small (== KHEAP_MAX_SIZE).
384 *
385 * However, if anyone is trying to call mach_vm_remap(),
386 * then bad things (TM) happen.
387 *
388 * Avoid this by preserving the ABI and moving
389 * to kalloc_large() earlier.
390 *
391 * Any recent code really ought to use IOMemoryDescriptor
392 * for this purpose however.
393 */
394 max_size = PAGE_SIZE - 1;
395 #endif
396 }
397
398 if (size <= max_size) {
399 uint32_t idx;
400
401 if (size <= KHEAP_START_SIZE) {
402 zid += (size > 16);
403 } else {
404 /*
405 * . log2down(size - 1) is log2up(size) - 1
406 * . (size - 1) >> (log2down(size - 1) - 1) is either 0x2 or 0x3
407 */
408 size -= 1;
409 idx = kalloc_log2down((uint32_t)size);
410 zid += KHEAP_EXTRA_ZONES +
411 2 * (idx - KHEAP_START_IDX) +
412 ((uint32_t)size >> (idx - 1)) - 2;
413 }
414 return zone_array + zid;
415 }
416
417 return ZONE_NULL;
418 }
419
420 zone_t
kalloc_zone_for_size(zone_id_t zid,size_t size)421 kalloc_zone_for_size(zone_id_t zid, size_t size)
422 {
423 return kalloc_zone_for_size_with_flags(zid, size, Z_WAITOK);
424 }
425
426 static inline bool
kheap_size_from_zone(void * addr,vm_size_t size,zalloc_flags_t flags)427 kheap_size_from_zone(
428 void *addr,
429 vm_size_t size,
430 zalloc_flags_t flags)
431 {
432 vm_size_t max_size = KHEAP_MAX_SIZE;
433 bool forcopyin = flags & Z_MAY_COPYINMAP;
434
435 #if __x86_64__
436 /*
437 * If Z_FULLSIZE is used, then due to kalloc_zone_for_size_with_flags()
438 * behavior, then the element could have a PAGE_SIZE reported size,
439 * yet still be from a zone for Z_MAY_COPYINMAP.
440 */
441 if (forcopyin) {
442 if (size == PAGE_SIZE &&
443 zone_id_for_element(addr, size) != ZONE_ID_INVALID) {
444 return true;
445 }
446
447 max_size = PAGE_SIZE - 1;
448 }
449 #else
450 #pragma unused(addr, forcopyin)
451 #endif
452
453 return size <= max_size;
454 }
455
456 __startup_func
457 static void
kalloc_zone_init(const char * kheap_name,zone_kheap_id_t kheap_id,zone_id_t * kheap_zstart,zone_create_flags_t zc_flags)458 kalloc_zone_init(
459 const char *kheap_name,
460 zone_kheap_id_t kheap_id,
461 zone_id_t *kheap_zstart,
462 zone_create_flags_t zc_flags)
463 {
464 zc_flags |= (ZC_KASAN_NOREDZONE | ZC_KASAN_NOQUARANTINE | ZC_PGZ_USE_GUARDS);
465
466 for (uint32_t i = 0; i < KHEAP_NUM_ZONES; i++) {
467 char *z_name = zalloc_permanent(MAX_ZONE_NAME, ZALIGN_NONE);
468 snprintf(z_name, MAX_ZONE_NAME, "%s.%zu", kheap_name, kheap_zsize[i]);
469 zone_t z_ptr = zone_create_ext(z_name, kheap_zsize[i], zc_flags,
470 ZONE_ID_ANY, ^(zone_t z){
471 uint32_t size = z->z_elem_size;
472 uint32_t scale = kalloc_log2down(size) - 1;
473
474 zone_security_array[zone_index(z)].z_kheap_id = (uint16_t)kheap_id;
475 z->z_array_size_class = 2 * scale | ((size >> scale) & 1);
476 });
477 if (i == 0) {
478 *kheap_zstart = zone_index(z_ptr);
479 }
480 }
481 }
482
483 __startup_func
484 static void
kalloc_heap_init(struct kalloc_heap * kheap)485 kalloc_heap_init(struct kalloc_heap *kheap)
486 {
487 kalloc_zone_init("kalloc", kheap->kh_heap_id, &kheap->kh_zstart,
488 ZC_NONE);
489 /*
490 * Count all the "raw" views for zones in the heap.
491 */
492 zone_view_count += KHEAP_NUM_ZONES;
493 }
494
495 __startup_func
496 static void
kalloc_init(void)497 kalloc_init(void)
498 {
499 static_assert(KHEAP_MAX_SIZE >= KALLOC_SAFE_ALLOC_SIZE);
500 kalloc_zsize_compute();
501
502 /* Initialize kalloc default heap */
503 kalloc_heap_init(KHEAP_DEFAULT);
504
505 #if ZSECURITY_CONFIG(SUBMAP_USER_DATA)
506 /* Initialize kalloc data buffers heap */
507 kalloc_heap_init(KHEAP_DATA_BUFFERS);
508 #else
509 *KHEAP_DATA_BUFFERS = *KHEAP_DEFAULT;
510 #endif
511 }
512 STARTUP(ZALLOC, STARTUP_RANK_THIRD, kalloc_init);
513
514 #define KEXT_ALIGN_SHIFT 6
515 #define KEXT_ALIGN_BYTES (1<< KEXT_ALIGN_SHIFT)
516 #define KEXT_ALIGN_MASK (KEXT_ALIGN_BYTES-1)
517 #define kt_scratch_size (256ul << 10)
518 #define KALLOC_TYPE_SECTION(type) \
519 (type == KTV_FIXED? "__kalloc_type": "__kalloc_var")
520
521 /*
522 * Enum to specify the kalloc_type variant being used.
523 */
524 __options_decl(kalloc_type_variant_t, uint16_t, {
525 KTV_FIXED = 0x0001,
526 KTV_VAR = 0x0002,
527 });
528
529 /*
530 * Macros that generate the appropriate kalloc_type variant (i.e fixed or
531 * variable) of the desired variable/function.
532 */
533 #define kalloc_type_var(type, var) \
534 ((type) == KTV_FIXED? \
535 (vm_offset_t) kalloc_type_##var##_fixed: \
536 (vm_offset_t) kalloc_type_##var##_var)
537 #define kalloc_type_func(type, func, ...) \
538 ((type) == KTV_FIXED? \
539 kalloc_type_##func##_fixed(__VA_ARGS__): \
540 kalloc_type_##func##_var(__VA_ARGS__))
541
542 TUNABLE(kalloc_type_options_t, kt_options, "kt", 0);
543 TUNABLE(uint16_t, kt_var_heaps, "kt_var_heaps",
544 ZSECURITY_CONFIG_KT_VAR_BUDGET);
545 /*
546 * Section start/end for fixed kalloc_type views
547 */
548 extern struct kalloc_type_view kalloc_type_sec_start_fixed[]
549 __SECTION_START_SYM(KALLOC_TYPE_SEGMENT, "__kalloc_type");
550
551 extern struct kalloc_type_view kalloc_type_sec_end_fixed[]
552 __SECTION_END_SYM(KALLOC_TYPE_SEGMENT, "__kalloc_type");
553
554 /*
555 * Section start/end for variable kalloc_type views
556 */
557 extern struct kalloc_type_var_view kalloc_type_sec_start_var[]
558 __SECTION_START_SYM(KALLOC_TYPE_SEGMENT, "__kalloc_var");
559
560 extern struct kalloc_type_var_view kalloc_type_sec_end_var[]
561 __SECTION_END_SYM(KALLOC_TYPE_SEGMENT, "__kalloc_var");
562
563 __startup_data
564 static kalloc_type_views_t *kt_buffer = NULL;
565 __startup_data
566 static uint64_t kt_count;
567 __startup_data
568 uint32_t kalloc_type_hash_seed;
569
570 _Static_assert(__builtin_popcount(KT_SUMMARY_MASK_TYPE_BITS) == (KT_GRANULE_MAX + 1),
571 "KT_SUMMARY_MASK_TYPE_BITS doesn't match KT_GRANULE_MAX");
572
573 /*
574 * For use by lldb to iterate over kalloc types
575 */
576 SECURITY_READ_ONLY_LATE(uint64_t) num_kt_sizeclass = MAX_K_ZONE(kt_zone_cfg);
577 SECURITY_READ_ONLY_LATE(zone_t) kalloc_type_zarray[MAX_K_ZONE(kt_zone_cfg)];
578
579 #define KT_GET_HASH(flags) (uint16_t)((flags & KT_HASH) >> 16)
580 static_assert(KT_HASH >> 16 == (KMEM_RANGE_MASK | KMEM_HASH_SET |
581 KMEM_DIRECTION_MASK),
582 "Insufficient bits to represent range and dir for VM allocations");
583 static_assert(MAX_K_ZONE(kt_zone_cfg) < KALLOC_TYPE_IDX_MASK,
584 "validate idx mask");
585 /* qsort routines */
586 typedef int (*cmpfunc_t)(const void *a, const void *b);
587 extern void qsort(void *a, size_t n, size_t es, cmpfunc_t cmp);
588
589 static inline uint16_t
kalloc_type_get_idx(uint32_t kt_size)590 kalloc_type_get_idx(uint32_t kt_size)
591 {
592 return (uint16_t) (kt_size >> KALLOC_TYPE_IDX_SHIFT);
593 }
594
595 static inline uint32_t
kalloc_type_set_idx(uint32_t kt_size,uint16_t idx)596 kalloc_type_set_idx(uint32_t kt_size, uint16_t idx)
597 {
598 return kt_size | ((uint32_t) idx << KALLOC_TYPE_IDX_SHIFT);
599 }
600
601 static void
kalloc_type_build_dlut(void)602 kalloc_type_build_dlut(void)
603 {
604 vm_size_t size = 0;
605 for (int i = 0; i <= KALLOC_DLUT_SIZE; i++, size += KALLOC_MINALIGN) {
606 uint8_t zindex = 0;
607 while ((vm_size_t)(kt_zone_cfg[zindex].kzc_size) < size) {
608 zindex++;
609 }
610 kalloc_type_dlut[i] = zindex;
611 }
612 }
613
614 static uint32_t
kalloc_type_idx_for_size(uint32_t size)615 kalloc_type_idx_for_size(uint32_t size)
616 {
617 assert(size <= KHEAP_MAX_SIZE);
618 uint16_t idx = kalloc_type_dlut[INDEX_ZDLUT(size)];
619 return kalloc_type_set_idx(size, idx);
620 }
621
622 static void
kalloc_type_assign_zone_fixed(kalloc_type_view_t * cur,kalloc_type_view_t * end,zone_t z)623 kalloc_type_assign_zone_fixed(kalloc_type_view_t *cur, kalloc_type_view_t *end,
624 zone_t z)
625 {
626 /*
627 * Assign the zone created for every kalloc_type_view
628 * of the same unique signature
629 */
630 bool need_raw_view = false;
631 while (cur < end) {
632 kalloc_type_view_t kt = *cur;
633 struct zone_view *zv = &kt->kt_zv;
634 zv->zv_zone = z;
635 kalloc_type_flags_t kt_flags = kt->kt_flags;
636
637 if (kt_flags & KT_SLID) {
638 kt->kt_signature -= vm_kernel_slide;
639 kt->kt_zv.zv_name -= vm_kernel_slide;
640 }
641
642 if ((kt_flags & KT_PRIV_ACCT) ||
643 ((kt_options & KT_OPTIONS_ACCT) && (kt_flags & KT_DEFAULT))) {
644 zv->zv_stats = zalloc_percpu_permanent_type(
645 struct zone_stats);
646 need_raw_view = true;
647 zone_view_count += 1;
648 } else {
649 zv->zv_stats = z->z_stats;
650 }
651 zv->zv_next = (zone_view_t) z->z_views;
652 zv->zv_zone->z_views = (zone_view_t) kt;
653 cur++;
654 }
655 if (need_raw_view) {
656 zone_view_count += 1;
657 }
658 }
659
660 __startup_func
661 static void
kalloc_type_assign_zone_var(kalloc_type_var_view_t * cur,kalloc_type_var_view_t * end,uint32_t heap_idx)662 kalloc_type_assign_zone_var(kalloc_type_var_view_t *cur,
663 kalloc_type_var_view_t *end, uint32_t heap_idx)
664 {
665 struct kheap_info *cfg = &kalloc_type_heap_array[heap_idx];
666 while (cur < end) {
667 kalloc_type_var_view_t kt = *cur;
668 kt->kt_heap_start = cfg->kh_zstart;
669 kalloc_type_flags_t kt_flags = kt->kt_flags;
670
671 if (kt_flags & KT_SLID) {
672 if (kt->kt_sig_hdr) {
673 kt->kt_sig_hdr -= vm_kernel_slide;
674 }
675 kt->kt_sig_type -= vm_kernel_slide;
676 kt->kt_name -= vm_kernel_slide;
677 }
678
679 if ((kt_flags & KT_PRIV_ACCT) ||
680 ((kt_options & KT_OPTIONS_ACCT) && (kt_flags & KT_DEFAULT))) {
681 kt->kt_stats = zalloc_percpu_permanent_type(struct zone_stats);
682 zone_view_count += 1;
683 }
684
685 kt->kt_next = (zone_view_t) cfg->kt_views;
686 cfg->kt_views = kt;
687 cur++;
688 }
689 }
690
691 __startup_func
692 static inline void
kalloc_type_slide_fixed(vm_offset_t addr)693 kalloc_type_slide_fixed(vm_offset_t addr)
694 {
695 kalloc_type_view_t ktv = (struct kalloc_type_view *) addr;
696 ktv->kt_signature += vm_kernel_slide;
697 ktv->kt_zv.zv_name += vm_kernel_slide;
698 ktv->kt_flags |= KT_SLID;
699 }
700
701 __startup_func
702 static inline void
kalloc_type_slide_var(vm_offset_t addr)703 kalloc_type_slide_var(vm_offset_t addr)
704 {
705 kalloc_type_var_view_t ktv = (struct kalloc_type_var_view *) addr;
706 if (ktv->kt_sig_hdr) {
707 ktv->kt_sig_hdr += vm_kernel_slide;
708 }
709 ktv->kt_sig_type += vm_kernel_slide;
710 ktv->kt_name += vm_kernel_slide;
711 ktv->kt_flags |= KT_SLID;
712 }
713
714 __startup_func
715 static void
kalloc_type_validate_flags(kalloc_type_flags_t kt_flags,const char * kt_name,uuid_string_t kext_uuid)716 kalloc_type_validate_flags(
717 kalloc_type_flags_t kt_flags,
718 const char *kt_name,
719 uuid_string_t kext_uuid)
720 {
721 if (!(kt_flags & KT_CHANGED) || !(kt_flags & KT_CHANGED2)) {
722 panic("kalloc_type_view(%s) from kext(%s) hasn't been rebuilt with "
723 "required xnu headers", kt_name, kext_uuid);
724 }
725 }
726
727 static kalloc_type_flags_t
kalloc_type_get_flags_fixed(vm_offset_t addr,uuid_string_t kext_uuid)728 kalloc_type_get_flags_fixed(vm_offset_t addr, uuid_string_t kext_uuid)
729 {
730 kalloc_type_view_t ktv = (kalloc_type_view_t) addr;
731 kalloc_type_validate_flags(ktv->kt_flags, ktv->kt_zv.zv_name, kext_uuid);
732 return ktv->kt_flags;
733 }
734
735 static kalloc_type_flags_t
kalloc_type_get_flags_var(vm_offset_t addr,uuid_string_t kext_uuid)736 kalloc_type_get_flags_var(vm_offset_t addr, uuid_string_t kext_uuid)
737 {
738 kalloc_type_var_view_t ktv = (kalloc_type_var_view_t) addr;
739 kalloc_type_validate_flags(ktv->kt_flags, ktv->kt_name, kext_uuid);
740 return ktv->kt_flags;
741 }
742
743 /*
744 * Check if signature of type is made up of only data and padding
745 */
746 static bool
kalloc_type_is_data(kalloc_type_flags_t kt_flags)747 kalloc_type_is_data(kalloc_type_flags_t kt_flags)
748 {
749 assert(kt_flags & KT_CHANGED);
750 return kt_flags & KT_DATA_ONLY;
751 }
752
753 /*
754 * Check if signature of type is made up of only pointers
755 */
756 static bool
kalloc_type_is_ptr_array(kalloc_type_flags_t kt_flags)757 kalloc_type_is_ptr_array(kalloc_type_flags_t kt_flags)
758 {
759 assert(kt_flags & KT_CHANGED2);
760 return kt_flags & KT_PTR_ARRAY;
761 }
762
763 static bool
kalloc_type_from_vm(kalloc_type_flags_t kt_flags)764 kalloc_type_from_vm(kalloc_type_flags_t kt_flags)
765 {
766 assert(kt_flags & KT_CHANGED);
767 return kt_flags & KT_VM;
768 }
769
770 __startup_func
771 static inline vm_size_t
kalloc_type_view_sz_fixed(void)772 kalloc_type_view_sz_fixed(void)
773 {
774 return sizeof(struct kalloc_type_view);
775 }
776
777 __startup_func
778 static inline vm_size_t
kalloc_type_view_sz_var(void)779 kalloc_type_view_sz_var(void)
780 {
781 return sizeof(struct kalloc_type_var_view);
782 }
783
784 __startup_func
785 static inline uint64_t
kalloc_type_view_count(kalloc_type_variant_t type,vm_offset_t start,vm_offset_t end)786 kalloc_type_view_count(kalloc_type_variant_t type, vm_offset_t start,
787 vm_offset_t end)
788 {
789 return (end - start) / kalloc_type_func(type, view_sz);
790 }
791
792 __startup_func
793 static inline void
kalloc_type_buffer_copy_fixed(kalloc_type_views_t * buffer,vm_offset_t ktv)794 kalloc_type_buffer_copy_fixed(kalloc_type_views_t *buffer, vm_offset_t ktv)
795 {
796 buffer->ktv_fixed = (kalloc_type_view_t) ktv;
797 }
798
799 __startup_func
800 static inline void
kalloc_type_buffer_copy_var(kalloc_type_views_t * buffer,vm_offset_t ktv)801 kalloc_type_buffer_copy_var(kalloc_type_views_t *buffer, vm_offset_t ktv)
802 {
803 buffer->ktv_var = (kalloc_type_var_view_t) ktv;
804 }
805
806 __startup_func
807 static void
kalloc_type_handle_data_view_fixed(vm_offset_t addr)808 kalloc_type_handle_data_view_fixed(vm_offset_t addr)
809 {
810 kalloc_type_view_t cur_data_view = (kalloc_type_view_t) addr;
811 zone_t z = kalloc_zone_for_size(KHEAP_DATA_BUFFERS->kh_zstart,
812 cur_data_view->kt_size);
813 kalloc_type_assign_zone_fixed(&cur_data_view, &cur_data_view + 1, z);
814 }
815
816 __startup_func
817 static void
kalloc_type_handle_data_view_var(vm_offset_t addr)818 kalloc_type_handle_data_view_var(vm_offset_t addr)
819 {
820 kalloc_type_var_view_t ktv = (kalloc_type_var_view_t) addr;
821 kalloc_type_assign_zone_var(&ktv, &ktv + 1, KT_VAR_DATA_HEAP);
822 }
823
824 __startup_func
825 static void
kalloc_type_handle_parray_var(vm_offset_t addr)826 kalloc_type_handle_parray_var(vm_offset_t addr)
827 {
828 kalloc_type_var_view_t ktv = (kalloc_type_var_view_t) addr;
829 kalloc_type_assign_zone_var(&ktv, &ktv + 1, KT_VAR_PTR_HEAP);
830 }
831
832 __startup_func
833 static uint32_t
kalloc_hash_adjust(uint32_t hash,uint32_t shift)834 kalloc_hash_adjust(uint32_t hash, uint32_t shift)
835 {
836 /*
837 * Limit range_id to ptr ranges
838 */
839 uint32_t range_id = kmem_adjust_range_id(hash);
840 uint32_t direction = hash & 0x8000;
841 return (range_id | KMEM_HASH_SET | direction) << shift;
842 }
843
844 __startup_func
845 static void
kalloc_type_set_type_hash(const char * sig_ty,const char * sig_hdr,kalloc_type_flags_t * kt_flags)846 kalloc_type_set_type_hash(const char *sig_ty, const char *sig_hdr,
847 kalloc_type_flags_t *kt_flags)
848 {
849 uint32_t hash = 0;
850
851 assert(sig_ty != NULL);
852 hash = os_hash_jenkins_update(sig_ty, strlen(sig_ty),
853 kalloc_type_hash_seed);
854 if (sig_hdr) {
855 hash = os_hash_jenkins_update(sig_hdr, strlen(sig_hdr), hash);
856 }
857 os_hash_jenkins_finish(hash);
858 hash &= (KMEM_RANGE_MASK | KMEM_DIRECTION_MASK);
859
860 *kt_flags = *kt_flags | kalloc_hash_adjust(hash, 16);
861 }
862
863 __startup_func
864 static void
kalloc_type_set_type_hash_fixed(vm_offset_t addr)865 kalloc_type_set_type_hash_fixed(vm_offset_t addr)
866 {
867 /*
868 * Use backtraces on fixed as we don't have signatures for types that go
869 * to the VM due to rdar://85182551.
870 */
871 (void) addr;
872 }
873
874 __startup_func
875 static void
kalloc_type_set_type_hash_var(vm_offset_t addr)876 kalloc_type_set_type_hash_var(vm_offset_t addr)
877 {
878 kalloc_type_var_view_t ktv = (kalloc_type_var_view_t) addr;
879 kalloc_type_set_type_hash(ktv->kt_sig_type, ktv->kt_sig_hdr,
880 &ktv->kt_flags);
881 }
882
883 __startup_func
884 static void
kalloc_type_mark_processed_fixed(vm_offset_t addr)885 kalloc_type_mark_processed_fixed(vm_offset_t addr)
886 {
887 kalloc_type_view_t ktv = (kalloc_type_view_t) addr;
888 ktv->kt_flags |= KT_PROCESSED;
889 }
890
891 __startup_func
892 static void
kalloc_type_mark_processed_var(vm_offset_t addr)893 kalloc_type_mark_processed_var(vm_offset_t addr)
894 {
895 kalloc_type_var_view_t ktv = (kalloc_type_var_view_t) addr;
896 ktv->kt_flags |= KT_PROCESSED;
897 }
898
899 __startup_func
900 static void
kalloc_type_update_view_fixed(vm_offset_t addr)901 kalloc_type_update_view_fixed(vm_offset_t addr)
902 {
903 kalloc_type_view_t ktv = (kalloc_type_view_t) addr;
904 ktv->kt_size = kalloc_type_idx_for_size(ktv->kt_size);
905 }
906
907 __startup_func
908 static void
kalloc_type_update_view_var(vm_offset_t addr)909 kalloc_type_update_view_var(vm_offset_t addr)
910 {
911 (void) addr;
912 }
913
914 __startup_func
915 static void
kalloc_type_view_copy(const kalloc_type_variant_t type,vm_offset_t start,vm_offset_t end,uint64_t * cur_count,bool slide,uuid_string_t kext_uuid)916 kalloc_type_view_copy(
917 const kalloc_type_variant_t type,
918 vm_offset_t start,
919 vm_offset_t end,
920 uint64_t *cur_count,
921 bool slide,
922 uuid_string_t kext_uuid)
923 {
924 uint64_t count = kalloc_type_view_count(type, start, end);
925 if (count + *cur_count >= kt_count) {
926 panic("kalloc_type_view_copy: Insufficient space in scratch buffer");
927 }
928 vm_offset_t cur = start;
929 while (cur < end) {
930 if (slide) {
931 kalloc_type_func(type, slide, cur);
932 }
933 kalloc_type_flags_t kt_flags = kalloc_type_func(type, get_flags, cur,
934 kext_uuid);
935 kalloc_type_func(type, mark_processed, cur);
936 /*
937 * Skip views that go to the VM
938 */
939 if (kalloc_type_from_vm(kt_flags)) {
940 cur += kalloc_type_func(type, view_sz);
941 continue;
942 }
943
944 /*
945 * If signature indicates that the entire allocation is data move it to
946 * KHEAP_DATA_BUFFERS. Note that KT_VAR_DATA_HEAP is a fake "data" heap,
947 * variable kalloc_type handles the actual redirection in the entry points
948 * kalloc/kfree_type_var_impl.
949 */
950 if (kalloc_type_is_data(kt_flags)) {
951 kalloc_type_func(type, handle_data_view, cur);
952 cur += kalloc_type_func(type, view_sz);
953 continue;
954 }
955
956 /*
957 * Set type hash that is used by kmem_*_guard
958 */
959 kalloc_type_func(type, set_type_hash, cur);
960
961 /*
962 * Redirect variable sized pointer arrays to KT_VAR_PTR_HEAP
963 */
964 if (type == KTV_VAR && kalloc_type_is_ptr_array(kt_flags)) {
965 kalloc_type_handle_parray_var(cur);
966 cur += kalloc_type_func(type, view_sz);
967 continue;
968 }
969
970 kalloc_type_func(type, update_view, cur);
971 kalloc_type_func(type, buffer_copy, &kt_buffer[*cur_count], cur);
972 cur += kalloc_type_func(type, view_sz);
973 *cur_count = *cur_count + 1;
974 }
975 }
976
977 __startup_func
978 static uint64_t
kalloc_type_view_parse(const kalloc_type_variant_t type)979 kalloc_type_view_parse(const kalloc_type_variant_t type)
980 {
981 kc_format_t kc_format;
982 uint64_t cur_count = 0;
983
984 if (!PE_get_primary_kc_format(&kc_format)) {
985 panic("kalloc_type_view_parse: wasn't able to determine kc format");
986 }
987
988 if (kc_format == KCFormatStatic) {
989 /*
990 * If kc is static or KCGEN, __kalloc_type sections from kexts and
991 * xnu are coalesced.
992 */
993 kalloc_type_view_copy(type,
994 kalloc_type_var(type, sec_start),
995 kalloc_type_var(type, sec_end),
996 &cur_count, false, NULL);
997 } else if (kc_format == KCFormatFileset) {
998 /*
999 * If kc uses filesets, traverse __kalloc_type section for each
1000 * macho in the BootKC.
1001 */
1002 kernel_mach_header_t *kc_mh = NULL;
1003 kernel_mach_header_t *kext_mh = NULL;
1004
1005 kc_mh = (kernel_mach_header_t *)PE_get_kc_header(KCKindPrimary);
1006 struct load_command *lc =
1007 (struct load_command *)((vm_offset_t)kc_mh + sizeof(*kc_mh));
1008 for (uint32_t i = 0; i < kc_mh->ncmds;
1009 i++, lc = (struct load_command *)((vm_offset_t)lc + lc->cmdsize)) {
1010 if (lc->cmd != LC_FILESET_ENTRY) {
1011 continue;
1012 }
1013 struct fileset_entry_command *fse =
1014 (struct fileset_entry_command *)(vm_offset_t)lc;
1015 kext_mh = (kernel_mach_header_t *)fse->vmaddr;
1016 kernel_section_t *sect = (kernel_section_t *)getsectbynamefromheader(
1017 kext_mh, KALLOC_TYPE_SEGMENT, KALLOC_TYPE_SECTION(type));
1018 if (sect != NULL) {
1019 unsigned long uuidlen = 0;
1020 void *kext_uuid = getuuidfromheader(kext_mh, &uuidlen);
1021 uuid_string_t kext_uuid_str;
1022 if ((kext_uuid != NULL) && (uuidlen == sizeof(uuid_t))) {
1023 uuid_unparse_upper(*(uuid_t *)kext_uuid, kext_uuid_str);
1024 }
1025 kalloc_type_view_copy(type, sect->addr, sect->addr + sect->size,
1026 &cur_count, false, kext_uuid_str);
1027 }
1028 }
1029 } else if (kc_format == KCFormatKCGEN) {
1030 /*
1031 * Parse __kalloc_type section from xnu
1032 */
1033 kalloc_type_view_copy(type,
1034 kalloc_type_var(type, sec_start),
1035 kalloc_type_var(type, sec_end), &cur_count, false, NULL);
1036
1037 /*
1038 * Parse __kalloc_type section for kexts
1039 *
1040 * Note: We don't process the kalloc_type_views for kexts on armv7
1041 * as this platform has insufficient memory for type based
1042 * segregation. kalloc_type_impl_external will direct callsites
1043 * based on their size.
1044 */
1045 kernel_mach_header_t *xnu_mh = &_mh_execute_header;
1046 vm_offset_t cur = 0;
1047 vm_offset_t end = 0;
1048
1049 /*
1050 * Kext machos are in the __PRELINK_TEXT segment. Extract the segment
1051 * and traverse it.
1052 */
1053 kernel_section_t *prelink_sect = getsectbynamefromheader(
1054 xnu_mh, kPrelinkTextSegment, kPrelinkTextSection);
1055 assert(prelink_sect);
1056 cur = prelink_sect->addr;
1057 end = prelink_sect->addr + prelink_sect->size;
1058
1059 while (cur < end) {
1060 uint64_t kext_text_sz = 0;
1061 kernel_mach_header_t *kext_mh = (kernel_mach_header_t *) cur;
1062
1063 if (kext_mh->magic == 0) {
1064 /*
1065 * Assert that we have processed all kexts and all that is left
1066 * is padding
1067 */
1068 assert(memcmp_zero_ptr_aligned((void *)kext_mh, end - cur) == 0);
1069 break;
1070 } else if (kext_mh->magic != MH_MAGIC_64 &&
1071 kext_mh->magic != MH_CIGAM_64) {
1072 panic("kalloc_type_view_parse: couldn't find kext @ offset:%lx",
1073 cur);
1074 }
1075
1076 /*
1077 * Kext macho found, iterate through its segments
1078 */
1079 struct load_command *lc =
1080 (struct load_command *)(cur + sizeof(kernel_mach_header_t));
1081 bool isSplitKext = false;
1082
1083 for (uint32_t i = 0; i < kext_mh->ncmds && (vm_offset_t)lc < end;
1084 i++, lc = (struct load_command *)((vm_offset_t)lc + lc->cmdsize)) {
1085 if (lc->cmd == LC_SEGMENT_SPLIT_INFO) {
1086 isSplitKext = true;
1087 continue;
1088 } else if (lc->cmd != LC_SEGMENT_64) {
1089 continue;
1090 }
1091
1092 kernel_segment_command_t *seg_cmd =
1093 (struct segment_command_64 *)(vm_offset_t)lc;
1094 /*
1095 * Parse kalloc_type section
1096 */
1097 if (strcmp(seg_cmd->segname, KALLOC_TYPE_SEGMENT) == 0) {
1098 kernel_section_t *kt_sect = getsectbynamefromseg(seg_cmd,
1099 KALLOC_TYPE_SEGMENT, KALLOC_TYPE_SECTION(type));
1100 if (kt_sect) {
1101 kalloc_type_view_copy(type, kt_sect->addr + vm_kernel_slide,
1102 kt_sect->addr + kt_sect->size + vm_kernel_slide, &cur_count,
1103 true, NULL);
1104 }
1105 }
1106 /*
1107 * If the kext has a __TEXT segment, that is the only thing that
1108 * will be in the special __PRELINK_TEXT KC segment, so the next
1109 * macho is right after.
1110 */
1111 if (strcmp(seg_cmd->segname, "__TEXT") == 0) {
1112 kext_text_sz = seg_cmd->filesize;
1113 }
1114 }
1115 /*
1116 * If the kext did not have a __TEXT segment (special xnu kexts with
1117 * only a __LINKEDIT segment) then the next macho will be after all the
1118 * header commands.
1119 */
1120 if (!kext_text_sz) {
1121 kext_text_sz = kext_mh->sizeofcmds;
1122 } else if (!isSplitKext) {
1123 panic("kalloc_type_view_parse: No support for non-split seg KCs");
1124 break;
1125 }
1126
1127 cur += ((kext_text_sz + (KEXT_ALIGN_BYTES - 1)) & (~KEXT_ALIGN_MASK));
1128 }
1129 } else {
1130 /*
1131 * When kc_format is KCFormatDynamic or KCFormatUnknown, we don't handle
1132 * parsing kalloc_type_view structs during startup.
1133 */
1134 panic("kalloc_type_view_parse: couldn't parse kalloc_type_view structs"
1135 " for kc_format = %d\n", kc_format);
1136 }
1137 return cur_count;
1138 }
1139
1140 __startup_func
1141 static int
kalloc_type_cmp_fixed(const void * a,const void * b)1142 kalloc_type_cmp_fixed(const void *a, const void *b)
1143 {
1144 const kalloc_type_view_t ktA = *(const kalloc_type_view_t *)a;
1145 const kalloc_type_view_t ktB = *(const kalloc_type_view_t *)b;
1146
1147 const uint16_t idxA = kalloc_type_get_idx(ktA->kt_size);
1148 const uint16_t idxB = kalloc_type_get_idx(ktB->kt_size);
1149 /*
1150 * If the kalloc_type_views are in the same kalloc bucket, sort by
1151 * signature else sort by size
1152 */
1153 if (idxA == idxB) {
1154 int result = strcmp(ktA->kt_signature, ktB->kt_signature);
1155 /*
1156 * If the kalloc_type_views have the same signature sort by site
1157 * name
1158 */
1159 if (result == 0) {
1160 return strcmp(ktA->kt_zv.zv_name, ktB->kt_zv.zv_name);
1161 }
1162 return result;
1163 }
1164 const uint32_t sizeA = kalloc_type_get_size(ktA->kt_size);
1165 const uint32_t sizeB = kalloc_type_get_size(ktB->kt_size);
1166 return (int)(sizeA - sizeB);
1167 }
1168
1169 __startup_func
1170 static int
kalloc_type_cmp_var(const void * a,const void * b)1171 kalloc_type_cmp_var(const void *a, const void *b)
1172 {
1173 const kalloc_type_var_view_t ktA = *(const kalloc_type_var_view_t *)a;
1174 const kalloc_type_var_view_t ktB = *(const kalloc_type_var_view_t *)b;
1175
1176 const char *ktA_hdr = ktA->kt_sig_hdr ?: "";
1177 const char *ktB_hdr = ktB->kt_sig_hdr ?: "";
1178
1179 int result = strcmp(ktA->kt_sig_type, ktB->kt_sig_type);
1180 if (result == 0) {
1181 return strcmp(ktA_hdr, ktB_hdr);
1182 }
1183 return result;
1184 }
1185
1186 __startup_func
1187 static uint16_t *
kalloc_type_create_iterators_fixed(uint16_t * kt_skip_list_start,uint16_t * kt_freq_list,uint16_t * kt_freq_list_total,uint64_t count)1188 kalloc_type_create_iterators_fixed(uint16_t *kt_skip_list_start,
1189 uint16_t *kt_freq_list, uint16_t *kt_freq_list_total, uint64_t count)
1190 {
1191 uint16_t *kt_skip_list = kt_skip_list_start;
1192 /*
1193 * cur and prev kalloc size bucket
1194 */
1195 uint16_t p_idx = 0;
1196 uint16_t c_idx = 0;
1197
1198 /*
1199 * Init values
1200 */
1201 uint16_t unique_sig = 1;
1202 uint16_t total_sig = 0;
1203 kt_skip_list++;
1204 const char *p_sig = "";
1205 const char *p_name = "";
1206
1207 /*
1208 * Walk over each kalloc_type_view
1209 */
1210 for (uint16_t i = 0; i < count; i++) {
1211 kalloc_type_view_t kt = kt_buffer[i].ktv_fixed;
1212 c_idx = kalloc_type_get_idx(kt->kt_size);
1213 /*
1214 * When current kalloc_type_view is in a different kalloc size
1215 * bucket than the previous, it means we have processed all in
1216 * the previous size bucket, so store the accumulated values
1217 * and advance the indices.
1218 */
1219 if (c_idx != p_idx) {
1220 /*
1221 * Updates for frequency lists
1222 */
1223 kt_freq_list[p_idx] = unique_sig;
1224 unique_sig = 1;
1225 kt_freq_list_total[p_idx] = total_sig;
1226 total_sig = 1;
1227 p_idx = c_idx;
1228
1229 /*
1230 * Updates to signature skip list
1231 */
1232 *kt_skip_list = i;
1233 kt_skip_list++;
1234 p_sig = kt->kt_signature;
1235 continue;
1236 }
1237
1238 /*
1239 * When current kalloc_type_views is in the kalloc size bucket as
1240 * previous, analyze the siganture to see if it is unique.
1241 *
1242 * Signatures are collapsible if one is a substring of the next.
1243 */
1244 const char *c_sig = kt->kt_signature;
1245 if (strncmp(c_sig, p_sig, strlen(p_sig)) != 0) {
1246 /*
1247 * Unique signature detected. Update counts and advance index
1248 */
1249 unique_sig++;
1250 *kt_skip_list = i;
1251 kt_skip_list++;
1252 }
1253
1254 /*
1255 * Check if current kalloc_type_view corresponds to a new type
1256 */
1257 const char *c_name = kt->kt_zv.zv_name;
1258 if (strlen(p_name) != strlen(c_name) || strcmp(p_name, c_name) != 0) {
1259 total_sig++;
1260 }
1261 p_name = c_name;
1262 p_sig = c_sig;
1263 }
1264 /*
1265 * Final update
1266 */
1267 assert(c_idx == p_idx);
1268 assert(kt_freq_list[c_idx] == 0);
1269 kt_freq_list[c_idx] = unique_sig;
1270 kt_freq_list_total[c_idx] = (uint16_t) total_sig;
1271 *kt_skip_list = (uint16_t) count;
1272 return ++kt_skip_list;
1273 }
1274
1275 #if ZSECURITY_CONFIG(KALLOC_TYPE)
1276 __startup_func
1277 static uint32_t
kalloc_type_create_iterators_var(uint32_t * kt_skip_list_start)1278 kalloc_type_create_iterators_var(uint32_t *kt_skip_list_start)
1279 {
1280 uint32_t *kt_skip_list = kt_skip_list_start;
1281 uint32_t n = 0;
1282 kt_skip_list[n] = 0;
1283 assert(kt_count > 1);
1284 for (uint32_t i = 1; i < kt_count; i++) {
1285 kalloc_type_var_view_t ktA = kt_buffer[i - 1].ktv_var;
1286 kalloc_type_var_view_t ktB = kt_buffer[i].ktv_var;
1287 const char *ktA_hdr = ktA->kt_sig_hdr ?: "";
1288 const char *ktB_hdr = ktB->kt_sig_hdr ?: "";
1289 if (strcmp(ktA_hdr, ktB_hdr) != 0 ||
1290 strcmp(ktA->kt_sig_type, ktB->kt_sig_type) != 0) {
1291 n++;
1292 kt_skip_list[n] = i;
1293 }
1294 }
1295 /*
1296 * Final update
1297 */
1298 n++;
1299 kt_skip_list[n] = (uint32_t) kt_count;
1300 return n;
1301 }
1302
1303 __startup_func
1304 static uint16_t
kalloc_type_apply_policy(uint16_t * kt_freq_list,uint16_t * kt_zones,uint16_t zone_budget)1305 kalloc_type_apply_policy(uint16_t *kt_freq_list, uint16_t *kt_zones,
1306 uint16_t zone_budget)
1307 {
1308 uint16_t total_sig = 0;
1309 uint16_t min_sig = 0;
1310 uint16_t assigned_zones = 0;
1311 uint16_t remaining_zones = zone_budget;
1312 uint16_t min_zones_per_size = 2;
1313
1314 #if DEBUG || DEVELOPMENT
1315 if (startup_phase < STARTUP_SUB_LOCKDOWN) {
1316 uint16_t current_zones = os_atomic_load(&num_zones, relaxed);
1317 assert(zone_budget + current_zones <= MAX_ZONES);
1318 }
1319 #endif
1320
1321 for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {
1322 uint16_t sig_freq = kt_freq_list[i];
1323 uint16_t min_zones = min_zones_per_size;
1324 if (sig_freq < min_zones_per_size) {
1325 min_zones = sig_freq;
1326 }
1327 total_sig += sig_freq;
1328 kt_zones[i] = min_zones;
1329 min_sig += min_zones;
1330 }
1331 if (remaining_zones > total_sig) {
1332 remaining_zones = total_sig;
1333 }
1334 assert(remaining_zones >= min_sig);
1335 remaining_zones -= min_sig;
1336 total_sig -= min_sig;
1337 assigned_zones += min_sig;
1338 uint16_t modulo = 0;
1339 for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {
1340 uint16_t freq = kt_freq_list[i];
1341 if (freq < min_zones_per_size) {
1342 continue;
1343 }
1344 uint32_t numer = (freq - min_zones_per_size) * remaining_zones;
1345 uint16_t n_zones = (uint16_t) numer / total_sig;
1346
1347 /*
1348 * Accumulate remainder and increment n_zones when it goes above
1349 * denominator
1350 */
1351 modulo += numer % total_sig;
1352 if (modulo >= total_sig) {
1353 n_zones++;
1354 modulo -= total_sig;
1355 }
1356
1357 /*
1358 * Cap the total number of zones to the unique signatures
1359 */
1360 if ((n_zones + min_zones_per_size) > freq) {
1361 uint16_t extra_zones = n_zones + min_zones_per_size - freq;
1362 modulo += (extra_zones * total_sig);
1363 n_zones -= extra_zones;
1364 }
1365 kt_zones[i] += n_zones;
1366 assigned_zones += n_zones;
1367 }
1368
1369 if (kt_options & KT_OPTIONS_DEBUG) {
1370 printf("kalloc_type_apply_policy: assigned %u zones wasted %u zones\n",
1371 assigned_zones, remaining_zones + min_sig - assigned_zones);
1372 }
1373 return remaining_zones + min_sig - assigned_zones;
1374 }
1375
1376 __startup_func
1377 static void
kalloc_type_create_zone_for_size(zone_t * kt_zones_for_size,uint16_t kt_zones,vm_size_t z_size)1378 kalloc_type_create_zone_for_size(zone_t *kt_zones_for_size,
1379 uint16_t kt_zones, vm_size_t z_size)
1380 {
1381 zone_t p_zone = NULL;
1382
1383 for (uint16_t i = 0; i < kt_zones; i++) {
1384 char *z_name = zalloc_permanent(MAX_ZONE_NAME, ZALIGN_NONE);
1385 snprintf(z_name, MAX_ZONE_NAME, "kalloc.type%u.%zu", i,
1386 (size_t) z_size);
1387 zone_t z = zone_create(z_name, z_size, ZC_KALLOC_TYPE);
1388 if (i != 0) {
1389 p_zone->z_kt_next = z;
1390 }
1391 p_zone = z;
1392 kt_zones_for_size[i] = z;
1393 }
1394 }
1395 #endif /* ZSECURITY_CONFIG(KALLOC_TYPE) */
1396
1397 __startup_func
1398 static void
kalloc_type_create_zones_fixed(uint16_t * kt_skip_list_start,uint16_t * kt_freq_list,uint16_t * kt_freq_list_total,uint16_t * kt_shuffle_buf)1399 kalloc_type_create_zones_fixed(uint16_t *kt_skip_list_start,
1400 uint16_t *kt_freq_list, uint16_t *kt_freq_list_total,
1401 uint16_t *kt_shuffle_buf)
1402 {
1403 uint16_t *kt_skip_list = kt_skip_list_start;
1404 uint16_t p_j = 0;
1405
1406 uint16_t kt_zones[MAX_K_ZONE(kt_zone_cfg)] = {};
1407
1408 #if DEBUG || DEVELOPMENT
1409 uint64_t kt_shuffle_count = ((vm_address_t) kt_shuffle_buf -
1410 (vm_address_t) kt_buffer) / sizeof(uint16_t);
1411 #endif
1412 /*
1413 * Apply policy to determine how many zones to create for each size
1414 * class.
1415 */
1416 #if ZSECURITY_CONFIG(KALLOC_TYPE)
1417 kalloc_type_apply_policy(kt_freq_list, kt_zones,
1418 ZSECURITY_CONFIG_KT_BUDGET);
1419 /*
1420 * Print stats when KT_OPTIONS_DEBUG boot-arg present
1421 */
1422 if (kt_options & KT_OPTIONS_DEBUG) {
1423 printf("Size\ttotal_sig\tunique_signatures\tzones\n");
1424 for (uint32_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {
1425 printf("%u\t%u\t%u\t%u\n", kt_zone_cfg[i].kzc_size,
1426 kt_freq_list_total[i], kt_freq_list[i], kt_zones[i]);
1427 }
1428 }
1429 #else /* ZSECURITY_CONFIG(KALLOC_TYPE) */
1430 #pragma unused(kt_freq_list_total)
1431 #endif /* !ZSECURITY_CONFIG(KALLOC_TYPE) */
1432
1433 for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {
1434 uint16_t n_unique_sig = kt_freq_list[i];
1435 vm_size_t z_size = kt_zone_cfg[i].kzc_size;
1436 uint16_t n_zones = kt_zones[i];
1437
1438 if (n_unique_sig == 0) {
1439 continue;
1440 }
1441
1442 assert(n_zones <= 20);
1443 zone_t kt_zones_for_size[20] = {};
1444 #if ZSECURITY_CONFIG(KALLOC_TYPE)
1445 kalloc_type_create_zone_for_size(kt_zones_for_size,
1446 n_zones, z_size);
1447 #else /* ZSECURITY_CONFIG(KALLOC_TYPE) */
1448 /*
1449 * Default to using KHEAP_DEFAULT if this feature is off
1450 */
1451 n_zones = 1;
1452 kt_zones_for_size[0] = kalloc_zone_for_size(
1453 KHEAP_DEFAULT->kh_zstart, z_size);
1454 #endif /* !ZSECURITY_CONFIG(KALLOC_TYPE) */
1455
1456 kalloc_type_zarray[i] = kt_zones_for_size[0];
1457 /*
1458 * Ensure that there is enough space to shuffle n_unique_sig
1459 * indices
1460 */
1461 assert(n_unique_sig < kt_shuffle_count);
1462
1463 /*
1464 * Get a shuffled set of signature indices
1465 */
1466 *kt_shuffle_buf = 0;
1467 if (n_unique_sig > 1) {
1468 kmem_shuffle(kt_shuffle_buf, n_unique_sig);
1469 }
1470
1471 for (uint16_t j = 0; j < n_unique_sig; j++) {
1472 /*
1473 * For every size that has unique types
1474 */
1475 uint16_t shuffle_idx = kt_shuffle_buf[j];
1476 uint16_t cur = kt_skip_list[shuffle_idx + p_j];
1477 uint16_t end = kt_skip_list[shuffle_idx + p_j + 1];
1478 zone_t zone = kt_zones_for_size[j % n_zones];
1479 kalloc_type_assign_zone_fixed(&kt_buffer[cur].ktv_fixed,
1480 &kt_buffer[end].ktv_fixed, zone);
1481 }
1482 p_j += n_unique_sig;
1483 }
1484 }
1485
1486 __startup_func
1487 static void
kalloc_type_view_init_fixed(void)1488 kalloc_type_view_init_fixed(void)
1489 {
1490 kalloc_type_hash_seed = (uint32_t) early_random();
1491 kalloc_type_build_dlut();
1492 /*
1493 * Parse __kalloc_type sections and build array of pointers to
1494 * all kalloc type views in kt_buffer.
1495 */
1496 kt_count = kalloc_type_view_parse(KTV_FIXED);
1497 assert(kt_count < KALLOC_TYPE_SIZE_MASK);
1498
1499 #if DEBUG || DEVELOPMENT
1500 vm_size_t sig_slist_size = (size_t) kt_count * sizeof(uint16_t);
1501 vm_size_t kt_buffer_size = (size_t) kt_count * sizeof(kalloc_type_view_t);
1502 assert(kt_scratch_size >= kt_buffer_size + sig_slist_size);
1503 #endif
1504
1505 /*
1506 * Sort based on size class and signature
1507 */
1508 qsort(kt_buffer, (size_t) kt_count, sizeof(kalloc_type_view_t),
1509 kalloc_type_cmp_fixed);
1510
1511 /*
1512 * Build a skip list that holds starts of unique signatures and a
1513 * frequency list of number of unique and total signatures per kalloc
1514 * size class
1515 */
1516 uint16_t *kt_skip_list_start = (uint16_t *)(kt_buffer + kt_count);
1517 uint16_t kt_freq_list[MAX_K_ZONE(kt_zone_cfg)] = { 0 };
1518 uint16_t kt_freq_list_total[MAX_K_ZONE(kt_zone_cfg)] = { 0 };
1519 uint16_t *kt_shuffle_buf = kalloc_type_create_iterators_fixed(
1520 kt_skip_list_start, kt_freq_list, kt_freq_list_total, kt_count);
1521
1522 /*
1523 * Create zones based on signatures
1524 */
1525 kalloc_type_create_zones_fixed(kt_skip_list_start, kt_freq_list,
1526 kt_freq_list_total, kt_shuffle_buf);
1527 }
1528
1529 #if ZSECURITY_CONFIG(KALLOC_TYPE)
1530 __startup_func
1531 static void
kalloc_type_heap_init(void)1532 kalloc_type_heap_init(void)
1533 {
1534 assert(kt_var_heaps + 1 <= KT_VAR_MAX_HEAPS);
1535 char kh_name[MAX_ZONE_NAME];
1536
1537 for (uint32_t i = KT_VAR_PTR_HEAP; i < KT_VAR_PTR_HEAP + kt_var_heaps; i++) {
1538 snprintf(&kh_name[0], MAX_ZONE_NAME, "%s%u", KHEAP_KT_VAR->kh_name, i);
1539 kalloc_zone_init((const char *)&kh_name[0], KHEAP_ID_KT_VAR,
1540 &kalloc_type_heap_array[i].kh_zstart, ZC_KALLOC_TYPE);
1541 }
1542 /*
1543 * All variable kalloc type allocations are collapsed into a single
1544 * stat. Individual accounting can be requested via KT_PRIV_ACCT
1545 */
1546 KHEAP_KT_VAR->kh_stats = zalloc_percpu_permanent_type(struct zone_stats);
1547 zone_view_count += 1;
1548 }
1549
1550 __startup_func
1551 static void
kalloc_type_view_init_var(void)1552 kalloc_type_view_init_var(void)
1553 {
1554 /*
1555 * Zones are created prior to parsing the views as zone budget is fixed
1556 * per sizeclass and special types identified while parsing are redirected
1557 * as they are discovered.
1558 */
1559 kalloc_type_heap_init();
1560
1561 /*
1562 * Parse __kalloc_var sections and build array of pointers to views that
1563 * aren't rediected in kt_buffer.
1564 */
1565 kt_count = kalloc_type_view_parse(KTV_VAR);
1566 assert(kt_count < UINT32_MAX);
1567
1568 #if DEBUG || DEVELOPMENT
1569 vm_size_t sig_slist_size = (size_t) kt_count * sizeof(uint32_t);
1570 vm_size_t kt_buffer_size = (size_t) kt_count * sizeof(kalloc_type_views_t);
1571 assert(kt_scratch_size >= kt_buffer_size + sig_slist_size);
1572 #endif
1573
1574 /*
1575 * Sort based on size class and signature
1576 */
1577 qsort(kt_buffer, (size_t) kt_count, sizeof(kalloc_type_var_view_t),
1578 kalloc_type_cmp_var);
1579
1580 /*
1581 * Build a skip list that holds starts of unique signatures
1582 */
1583 uint32_t *kt_skip_list_start = (uint32_t *)(kt_buffer + kt_count);
1584 uint32_t unique_sig = kalloc_type_create_iterators_var(kt_skip_list_start);
1585 uint16_t fixed_heaps = KT_VAR__FIRST_FLEXIBLE_HEAP;
1586 /*
1587 * If we have only one heap then other elements share heap with pointer
1588 * arrays
1589 */
1590 if (kt_var_heaps < KT_VAR__FIRST_FLEXIBLE_HEAP) {
1591 fixed_heaps = KT_VAR_PTR_HEAP;
1592 }
1593
1594 for (uint32_t i = 1; i <= unique_sig; i++) {
1595 uint32_t heap_id = kmem_get_random16(kt_var_heaps - fixed_heaps) +
1596 fixed_heaps;
1597 uint32_t start = kt_skip_list_start[i - 1];
1598 uint32_t end = kt_skip_list_start[i];
1599 kalloc_type_assign_zone_var(&kt_buffer[start].ktv_var,
1600 &kt_buffer[end].ktv_var, heap_id);
1601 }
1602 }
1603 #else /* ZSECURITY_CONFIG(KALLOC_TYPE) */
1604 __startup_func
1605 static void
kalloc_type_view_init_var(void)1606 kalloc_type_view_init_var(void)
1607 {
1608 *KHEAP_KT_VAR = *KHEAP_DEFAULT;
1609 }
1610 #endif /* !ZSECURITY_CONFIG(KALLOC_TYPE) */
1611
1612 __startup_func
1613 static void
kalloc_type_views_init(void)1614 kalloc_type_views_init(void)
1615 {
1616 /*
1617 * Allocate scratch space to parse kalloc_type_views and create
1618 * other structures necessary to process them.
1619 */
1620 uint64_t max_count = kt_count = kt_scratch_size / sizeof(kalloc_type_views_t);
1621
1622 kmem_alloc(kernel_map, (vm_offset_t *)&kt_buffer, kt_scratch_size,
1623 KMA_NOFAIL | KMA_ZERO | KMA_KOBJECT, VM_KERN_MEMORY_KALLOC);
1624
1625 /*
1626 * Handle fixed size views
1627 */
1628 kalloc_type_view_init_fixed();
1629
1630 /*
1631 * Reset
1632 */
1633 bzero(kt_buffer, kt_scratch_size);
1634 kt_count = max_count;
1635
1636 /*
1637 * Handle variable size views
1638 */
1639 kalloc_type_view_init_var();
1640
1641 /*
1642 * Free resources used
1643 */
1644 kmem_free(kernel_map, (vm_offset_t) kt_buffer, kt_scratch_size);
1645 }
1646 STARTUP(ZALLOC, STARTUP_RANK_FOURTH, kalloc_type_views_init);
1647
1648 #pragma mark accessors
1649
1650 #define KFREE_ABSURD_SIZE \
1651 ((VM_MAX_KERNEL_ADDRESS - VM_MIN_KERNEL_AND_KEXT_ADDRESS) / 2)
1652
1653 /*
1654 * This is used to sanitize size for kasan or OOB adjustments.
1655 * It assumes that size is [0, KFREE_ABSURD_SIZE) valued.
1656 */
1657 __header_always_inline vm_size_t
K_SANE_SIZE(vm_size_t size)1658 K_SANE_SIZE(vm_size_t size)
1659 {
1660 return MAX(size, 1);
1661 }
1662
1663 static void
KALLOC_ZINFO_SALLOC(vm_size_t bytes)1664 KALLOC_ZINFO_SALLOC(vm_size_t bytes)
1665 {
1666 thread_t thr = current_thread();
1667 ledger_debit_thread(thr, thr->t_ledger, task_ledgers.tkm_shared, bytes);
1668 }
1669
1670 static void
KALLOC_ZINFO_SFREE(vm_size_t bytes)1671 KALLOC_ZINFO_SFREE(vm_size_t bytes)
1672 {
1673 thread_t thr = current_thread();
1674 ledger_credit_thread(thr, thr->t_ledger, task_ledgers.tkm_shared, bytes);
1675 }
1676
1677 static kmem_guard_t
kalloc_guard(vm_tag_t tag,uint16_t type_hash,const void * owner)1678 kalloc_guard(vm_tag_t tag, uint16_t type_hash, const void *owner)
1679 {
1680 kmem_guard_t guard = {
1681 .kmg_atomic = true,
1682 .kmg_tag = tag,
1683 .kmg_type_hash = type_hash,
1684 .kmg_context = os_hash_kernel_pointer(owner),
1685 };
1686
1687 /*
1688 * TODO: this use is really not sufficiently smart.
1689 */
1690
1691 return guard;
1692 }
1693
1694 #if __arm64e__
1695
1696 #define KALLOC_ARRAY_TYPE_SHIFT (64 - T1SZ_BOOT - 2)
1697
1698 SECURITY_READ_ONLY_LATE(uint32_t) kalloc_array_type_shift = KALLOC_ARRAY_TYPE_SHIFT;
1699
1700 /*
1701 * Zone encoding is:
1702 *
1703 * <PAC SIG><1><2 bits of type><PTR value><4 bits of size class>
1704 *
1705 * VM encoding is:
1706 *
1707 * <PAC SIG><1><2 bits of 0><PTR value><14 bits of page count>
1708 */
1709
1710 static_assert(T1SZ_BOOT + 2 + VM_KERNEL_POINTER_SIGNIFICANT_BITS <= 64);
1711
1712 __attribute__((always_inline))
1713 struct kalloc_result
__kalloc_array_decode(vm_address_t ptr)1714 __kalloc_array_decode(vm_address_t ptr)
1715 {
1716 struct kalloc_result kr;
1717 vm_address_t type = (ptr >> KALLOC_ARRAY_TYPE_SHIFT) & 0x3;
1718
1719 if (type) {
1720 kr.size = type << (ptr & 0xf);
1721 ptr &= ~0xfull;
1722 } else {
1723 kr.size = (ptr & PAGE_MASK) << PAGE_SHIFT;
1724 ptr &= ~PAGE_MASK;
1725 }
1726 ptr |= 3ull << KALLOC_ARRAY_TYPE_SHIFT;
1727
1728 kr.addr = (void *)ptr;
1729 return kr;
1730 }
1731
1732 static inline void *
__kalloc_array_encode_zone(zone_t z,void * ptr,vm_size_t size __unused)1733 __kalloc_array_encode_zone(zone_t z, void *ptr, vm_size_t size __unused)
1734 {
1735 vm_address_t addr = (vm_address_t)ptr;
1736 vm_address_t idx = z->z_array_size_class;
1737
1738 if ((idx & 1) == 0) {
1739 addr &= ~(0x1ull << KALLOC_ARRAY_TYPE_SHIFT);
1740 }
1741 addr |= (idx >> 1);
1742
1743 return (void *)addr;
1744 }
1745
1746 static inline vm_address_t
__kalloc_array_encode_vm(vm_address_t addr,vm_size_t size)1747 __kalloc_array_encode_vm(vm_address_t addr, vm_size_t size)
1748 {
1749 addr &= ~(0x3ull << KALLOC_ARRAY_TYPE_SHIFT);
1750
1751 return addr | atop(size);
1752 }
1753
1754 #else
1755
1756 SECURITY_READ_ONLY_LATE(uint32_t) kalloc_array_type_shift = 0;
1757
1758 /*
1759 * Encoding is:
1760 * bits 0..46: pointer value
1761 * bits 47..47: 0: zones, 1: VM
1762 * bits 48..63: zones: elem size, VM: number of pages
1763 */
1764
1765 #define KALLOC_ARRAY_TYPE_BIT 47
1766 static_assert(KALLOC_ARRAY_TYPE_BIT > VM_KERNEL_POINTER_SIGNIFICANT_BITS);
1767 static_assert(__builtin_clzll(KHEAP_MAX_SIZE) > KALLOC_ARRAY_TYPE_BIT);
1768
1769 __attribute__((always_inline))
1770 struct kalloc_result
__kalloc_array_decode(vm_address_t ptr)1771 __kalloc_array_decode(vm_address_t ptr)
1772 {
1773 struct kalloc_result kr;
1774
1775 kr.size = ptr >> (KALLOC_ARRAY_TYPE_BIT + 1);
1776 if (ptr & (1ull << KALLOC_ARRAY_TYPE_BIT)) {
1777 kr.size <<= PAGE_SHIFT;
1778 }
1779 kr.addr = (void *)(ptr | ~0ull << KALLOC_ARRAY_TYPE_BIT);
1780
1781 return kr;
1782 }
1783
1784 static inline void *
__kalloc_array_encode_zone(zone_t z __unused,void * ptr,vm_size_t size)1785 __kalloc_array_encode_zone(zone_t z __unused, void *ptr, vm_size_t size)
1786 {
1787 vm_address_t addr = (vm_address_t)ptr;
1788
1789 addr &= (1ull << KALLOC_ARRAY_TYPE_BIT) - 1; /* clear bit */
1790 addr |= size << (KALLOC_ARRAY_TYPE_BIT + 1);
1791
1792 return (void *)addr;
1793 }
1794
1795 static inline vm_address_t
__kalloc_array_encode_vm(vm_address_t addr,vm_size_t size)1796 __kalloc_array_encode_vm(vm_address_t addr, vm_size_t size)
1797 {
1798 addr &= (2ull << KALLOC_ARRAY_TYPE_BIT) - 1; /* keep bit */
1799 addr |= size << (KALLOC_ARRAY_TYPE_BIT + 1 - PAGE_SHIFT);
1800
1801 return addr;
1802 }
1803
1804 #endif
1805
1806 vm_size_t
kalloc_next_good_size(vm_size_t size,uint32_t period)1807 kalloc_next_good_size(vm_size_t size, uint32_t period)
1808 {
1809 uint32_t scale = kalloc_log2down((uint32_t)size);
1810 vm_size_t step;
1811
1812 if (size < KHEAP_STEP_START) {
1813 return KHEAP_STEP_START;
1814 }
1815 if (size < 2 * KHEAP_STEP_START) {
1816 return 2 * KHEAP_STEP_START;
1817 }
1818 if (size < KHEAP_MAX_SIZE) {
1819 step = 1ul << (scale - 1);
1820 } else {
1821 step = round_page(1ul << (scale - kalloc_log2down(period)));
1822 }
1823
1824 return (size + step) & -step;
1825 }
1826
1827
1828 #pragma mark kalloc
1829
1830 static inline kalloc_heap_t
kalloc_type_get_heap(kalloc_type_var_view_t kt_view,bool kt_free __unused)1831 kalloc_type_get_heap(kalloc_type_var_view_t kt_view, bool kt_free __unused)
1832 {
1833 kalloc_heap_t fallback = KHEAP_DEFAULT;
1834
1835 /*
1836 * Redirect data-only views
1837 */
1838 if (kalloc_type_is_data(kt_view->kt_flags)) {
1839 return KHEAP_DATA_BUFFERS;
1840 }
1841
1842 if (kt_view->kt_flags & KT_PROCESSED) {
1843 return KHEAP_KT_VAR;
1844 }
1845
1846 /*
1847 * Views from kexts not in BootKC on macOS
1848 */
1849 #if !ZSECURITY_CONFIG(STRICT_IOKIT_FREE)
1850 if (kt_free) {
1851 fallback = KHEAP_ANY;
1852 }
1853 #endif
1854
1855 return fallback;
1856 }
1857
1858 __attribute__((noinline))
1859 static struct kalloc_result
kalloc_large(kalloc_heap_t kheap,vm_size_t req_size,zalloc_flags_t flags,uint16_t kt_hash,void * owner __unused)1860 kalloc_large(
1861 kalloc_heap_t kheap,
1862 vm_size_t req_size,
1863 zalloc_flags_t flags,
1864 uint16_t kt_hash,
1865 void *owner __unused)
1866 {
1867 int kma_flags = KMA_NONE;
1868 vm_tag_t tag;
1869 vm_offset_t addr, size;
1870
1871 if (flags & Z_NOFAIL) {
1872 panic("trying to kalloc(Z_NOFAIL) with a large size (%zd)",
1873 (size_t)req_size);
1874 }
1875
1876 /*
1877 * kmem_alloc could block so we return if noblock
1878 *
1879 * also, reject sizes larger than our address space is quickly,
1880 * as kt_size or IOMallocArraySize() expect this.
1881 */
1882 if ((flags & Z_NOWAIT) ||
1883 (req_size >> VM_KERNEL_POINTER_SIGNIFICANT_BITS)) {
1884 return (struct kalloc_result){ };
1885 }
1886
1887 if ((flags & Z_KALLOC_ARRAY) && req_size > KALLOC_ARRAY_SIZE_MAX) {
1888 return (struct kalloc_result){ };
1889 }
1890
1891 #ifndef __x86_64__
1892 /*
1893 * (73465472) on Intel we didn't use to pass this flag,
1894 * which in turned allowed kalloc_large() memory to be shared
1895 * with user directly.
1896 *
1897 * We're bound by this unfortunate ABI.
1898 */
1899 if ((flags & Z_MAY_COPYINMAP) == 0) {
1900 kma_flags |= KMA_KOBJECT;
1901 } else {
1902 assert(kheap == KHEAP_DATA_BUFFERS);
1903 }
1904 #endif
1905 if (flags & Z_NOPAGEWAIT) {
1906 kma_flags |= KMA_NOPAGEWAIT;
1907 }
1908 if (flags & Z_ZERO) {
1909 kma_flags |= KMA_ZERO;
1910 }
1911 if (kheap == KHEAP_DATA_BUFFERS) {
1912 kma_flags |= KMA_DATA;
1913 }
1914
1915 tag = zalloc_flags_get_tag(flags);
1916 if (flags & Z_VM_TAG_BT_BIT) {
1917 tag = vm_tag_bt() ?: tag;
1918 }
1919 if (tag == VM_KERN_MEMORY_NONE) {
1920 tag = kheap->kh_tag;
1921 }
1922
1923 #if KASAN_KALLOC
1924 if (flags & Z_KALLOC_ARRAY) {
1925 req_size = round_page(req_size);
1926 }
1927 /* large allocation - use guard pages instead of small redzones */
1928 size = round_page(kasan_alloc_resize(req_size) + ptoa(2));
1929 #else
1930 size = round_page(req_size);
1931 if (flags & (Z_FULLSIZE | Z_KALLOC_ARRAY)) {
1932 req_size = size;
1933 }
1934 #endif
1935
1936 addr = kmem_alloc_guard(kernel_map, size, 0,
1937 kma_flags, kalloc_guard(tag, kt_hash, owner)).kmr_address;
1938
1939 if (addr != 0) {
1940 counter_inc(&kalloc_large_count);
1941 counter_add(&kalloc_large_total, size);
1942 KALLOC_ZINFO_SALLOC(size);
1943 #if KASAN_KALLOC
1944 /* fixup the return address to skip the redzone */
1945 addr = kasan_alloc(addr, size, req_size, PAGE_SIZE);
1946 #else
1947 #if CONFIG_KERNEL_TBI && KASAN_TBI
1948 if ((flags & Z_MAY_COPYINMAP) == 0) {
1949 addr = kasan_tbi_tag_large_alloc(addr, size, req_size);
1950 }
1951 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
1952 #endif
1953 if (flags & Z_KALLOC_ARRAY) {
1954 addr = __kalloc_array_encode_vm(addr, req_size);
1955 }
1956 } else {
1957 addr = 0;
1958 }
1959
1960 DTRACE_VM3(kalloc, vm_size_t, size, vm_size_t, req_size, void*, addr);
1961 return (struct kalloc_result){ .addr = (void *)addr, .size = req_size };
1962 }
1963
1964 static inline struct kalloc_result
kalloc_zone(zone_t z,zone_stats_t zstats,zalloc_flags_t flags,vm_size_t req_size)1965 kalloc_zone(
1966 zone_t z,
1967 zone_stats_t zstats,
1968 zalloc_flags_t flags,
1969 vm_size_t req_size)
1970 {
1971 struct kalloc_result kr;
1972 vm_size_t esize;
1973
1974 kr = zalloc_ext(z, zstats ?: z->z_stats, flags | Z_SKIP_KASAN);
1975 esize = kr.size;
1976
1977 if (__probable(kr.addr)) {
1978 #if KASAN_KALLOC
1979 flags &= ~Z_FULLSIZE;
1980 #endif /* KASAN_KALLOC */
1981 if (flags & (Z_FULLSIZE | Z_KALLOC_ARRAY)) {
1982 #if KASAN_CLASSIC
1983 kr.size -= kasan_alloc_resize(req_size) - req_size;
1984 #endif
1985 req_size = kr.size;
1986 } else {
1987 kr.size = req_size;
1988 }
1989 #if ZSECURITY_CONFIG(PGZ_OOB_ADJUST)
1990 kr.addr = zone_element_pgz_oob_adjust(kr.addr, req_size, esize);
1991 #endif /* !ZSECURITY_CONFIG(PGZ_OOB_ADJUST) */
1992 #if KASAN_KALLOC
1993 kr.addr = (void *)kasan_alloc((vm_offset_t)kr.addr, esize,
1994 kr.size, KASAN_GUARD_SIZE);
1995 __nosan_bzero((char *)kr.addr, kr.size);
1996 #endif /* KASAN_KALLOC */
1997 #if CONFIG_KERNEL_TBI && KASAN_TBI
1998 /*
1999 * Kasan-TBI at least needs to tag one byte so that
2000 * we can prove the allocation was live at kfree_ext()
2001 * time by doing a manual __asan_loadN check.
2002 */
2003 kr.addr = (void *)kasan_tbi_tag_zalloc((vm_offset_t)kr.addr,
2004 esize, K_SANE_SIZE(kr.size), false);
2005 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
2006
2007 if (flags & Z_KALLOC_ARRAY) {
2008 kr.addr = __kalloc_array_encode_zone(z, kr.addr, kr.size);
2009 }
2010 }
2011
2012 DTRACE_VM3(kalloc, vm_size_t, req_size, vm_size_t, esize, void*, kr.addr);
2013 return kr;
2014 }
2015
2016 #undef kalloc_ext
2017
2018 struct kalloc_result
kalloc_ext(void * kheap_or_kt_view,vm_size_t req_size,zalloc_flags_t flags,void * owner)2019 kalloc_ext(
2020 void *kheap_or_kt_view,
2021 vm_size_t req_size,
2022 zalloc_flags_t flags,
2023 void *owner)
2024 {
2025 kalloc_type_var_view_t kt_view;
2026 kalloc_heap_t kheap;
2027 zone_stats_t zstats = NULL;
2028 vm_size_t size;
2029 zone_t z;
2030 uint16_t kt_hash;
2031 zone_id_t zstart;
2032
2033 if (kt_is_var_view(kheap_or_kt_view)) {
2034 kt_view = kt_demangle_var_view(kheap_or_kt_view);
2035 kheap = kalloc_type_get_heap(kt_view, false);
2036 /*
2037 * Use stats from view if present, else use stats from kheap.
2038 * KHEAP_KT_VAR accumulates stats for all allocations going to
2039 * kalloc.type.var zones, while KHEAP_DEFAULT and KHEAP_DATA_BUFFERS
2040 * use stats from the respective zones.
2041 */
2042 zstats = kt_view->kt_stats;
2043 kt_hash = (uint16_t) KT_GET_HASH(kt_view->kt_flags);
2044 #if ZSECURITY_CONFIG(KALLOC_TYPE)
2045 zstart = kt_view->kt_heap_start ?: kheap->kh_zstart;
2046 #else
2047 zstart = KHEAP_DEFAULT->kh_zstart;
2048 #endif
2049 } else {
2050 kt_view = NULL;
2051 kheap = kheap_or_kt_view;
2052 kt_hash = kheap->kh_type_hash;
2053 zstart = kheap->kh_zstart;
2054 }
2055
2056 if (!zstats) {
2057 zstats = kheap->kh_stats;
2058 }
2059
2060 #if KASAN_KALLOC
2061 /*
2062 * Kasan for kalloc heaps will put the redzones *inside*
2063 * the allocation, and hence augment its size.
2064 *
2065 * kalloc heaps do not use zone_t::z_kasan_redzone.
2066 */
2067 size = kasan_alloc_resize(req_size);
2068 #else
2069 size = req_size;
2070 #endif
2071
2072 z = kalloc_zone_for_size_with_flags(zstart, size, flags);
2073 if (z) {
2074 return kalloc_zone(z, zstats, flags, req_size);
2075 } else {
2076 return kalloc_large(kheap, req_size, flags, kt_hash, owner);
2077 }
2078 }
2079
2080 void *
2081 kalloc_external(vm_size_t size);
2082 void *
kalloc_external(vm_size_t size)2083 kalloc_external(vm_size_t size)
2084 {
2085 zalloc_flags_t flags = Z_VM_TAG_BT(Z_WAITOK, VM_KERN_MEMORY_KALLOC);
2086 return kheap_alloc(KHEAP_DEFAULT, size, flags);
2087 }
2088
2089 void *
2090 kalloc_data_external(vm_size_t size, zalloc_flags_t flags);
2091 void *
kalloc_data_external(vm_size_t size,zalloc_flags_t flags)2092 kalloc_data_external(vm_size_t size, zalloc_flags_t flags)
2093 {
2094 flags = Z_VM_TAG_BT(flags & Z_KPI_MASK, VM_KERN_MEMORY_KALLOC_DATA);
2095 return kheap_alloc(KHEAP_DATA_BUFFERS, size, flags);
2096 }
2097
2098 #if ZSECURITY_CONFIG(SUBMAP_USER_DATA)
2099
2100 __abortlike
2101 static void
kalloc_data_require_panic(void * addr,vm_size_t size)2102 kalloc_data_require_panic(void *addr, vm_size_t size)
2103 {
2104 zone_id_t zid = zone_id_for_element(addr, size);
2105
2106 if (zid != ZONE_ID_INVALID) {
2107 zone_t z = &zone_array[zid];
2108 zone_security_flags_t zsflags = zone_security_array[zid];
2109
2110 if (zsflags.z_kheap_id != KHEAP_ID_DATA_BUFFERS) {
2111 panic("kalloc_data_require failed: address %p in [%s%s]",
2112 addr, zone_heap_name(z), zone_name(z));
2113 }
2114
2115 panic("kalloc_data_require failed: address %p in [%s%s], "
2116 "size too large %zd > %zd", addr,
2117 zone_heap_name(z), zone_name(z),
2118 (size_t)size, (size_t)zone_elem_size(z));
2119 } else {
2120 panic("kalloc_data_require failed: address %p not in zone native map",
2121 addr);
2122 }
2123 }
2124
2125 __abortlike
2126 static void
kalloc_non_data_require_panic(void * addr,vm_size_t size)2127 kalloc_non_data_require_panic(void *addr, vm_size_t size)
2128 {
2129 zone_id_t zid = zone_id_for_element(addr, size);
2130
2131 if (zid != ZONE_ID_INVALID) {
2132 zone_t z = &zone_array[zid];
2133 zone_security_flags_t zsflags = zone_security_array[zid];
2134
2135 switch (zsflags.z_kheap_id) {
2136 case KHEAP_ID_NONE:
2137 case KHEAP_ID_DATA_BUFFERS:
2138 case KHEAP_ID_KT_VAR:
2139 panic("kalloc_non_data_require failed: address %p in [%s%s]",
2140 addr, zone_heap_name(z), zone_name(z));
2141 default:
2142 break;
2143 }
2144
2145 panic("kalloc_non_data_require failed: address %p in [%s%s], "
2146 "size too large %zd > %zd", addr,
2147 zone_heap_name(z), zone_name(z),
2148 (size_t)size, (size_t)zone_elem_size(z));
2149 } else {
2150 panic("kalloc_non_data_require failed: address %p not in zone native map",
2151 addr);
2152 }
2153 }
2154
2155 #endif /* ZSECURITY_CONFIG(SUBMAP_USER_DATA) */
2156
2157 void
kalloc_data_require(void * addr,vm_size_t size)2158 kalloc_data_require(void *addr, vm_size_t size)
2159 {
2160 #if ZSECURITY_CONFIG(SUBMAP_USER_DATA)
2161 zone_id_t zid = zone_id_for_element(addr, size);
2162
2163 if (zid != ZONE_ID_INVALID) {
2164 zone_t z = &zone_array[zid];
2165 zone_security_flags_t zsflags = zone_security_array[zid];
2166 if (zsflags.z_kheap_id == KHEAP_ID_DATA_BUFFERS &&
2167 size <= zone_elem_size(z)) {
2168 return;
2169 }
2170 } else if (kmem_range_id_contains(KMEM_RANGE_ID_DATA,
2171 (vm_address_t)pgz_decode(addr, size), size)) {
2172 return;
2173 }
2174
2175 kalloc_data_require_panic(addr, size);
2176 #else
2177 #pragma unused(addr, size)
2178 #endif
2179 }
2180
2181 void
kalloc_non_data_require(void * addr,vm_size_t size)2182 kalloc_non_data_require(void *addr, vm_size_t size)
2183 {
2184 #if ZSECURITY_CONFIG(SUBMAP_USER_DATA)
2185 zone_id_t zid = zone_id_for_element(addr, size);
2186
2187 if (zid != ZONE_ID_INVALID) {
2188 zone_t z = &zone_array[zid];
2189 zone_security_flags_t zsflags = zone_security_array[zid];
2190 switch (zsflags.z_kheap_id) {
2191 case KHEAP_ID_NONE:
2192 if (!zsflags.z_kalloc_type) {
2193 break;
2194 }
2195 OS_FALLTHROUGH;
2196 case KHEAP_ID_DEFAULT:
2197 case KHEAP_ID_KT_VAR:
2198 if (size < zone_elem_size(z)) {
2199 return;
2200 }
2201 break;
2202 default:
2203 break;
2204 }
2205 } else if (!kmem_range_id_contains(KMEM_RANGE_ID_DATA,
2206 (vm_address_t)pgz_decode(addr, size), size)) {
2207 return;
2208 }
2209
2210 kalloc_non_data_require_panic(addr, size);
2211 #else
2212 #pragma unused(addr, size)
2213 #endif
2214 }
2215
2216 void *
kalloc_type_impl_external(kalloc_type_view_t kt_view,zalloc_flags_t flags)2217 kalloc_type_impl_external(kalloc_type_view_t kt_view, zalloc_flags_t flags)
2218 {
2219 /*
2220 * Callsites from a kext that aren't in the BootKC on macOS or
2221 * any callsites on armv7 are not processed during startup,
2222 * default to using kheap_alloc
2223 *
2224 * Additionally when size is greater KHEAP_MAX_SIZE zone is left
2225 * NULL as we need to use the vm for the allocation
2226 *
2227 */
2228 if (__improbable(kt_view->kt_zv.zv_zone == ZONE_NULL)) {
2229 vm_size_t size = kalloc_type_get_size(kt_view->kt_size);
2230 flags = Z_VM_TAG_BT(flags & Z_KPI_MASK, VM_KERN_MEMORY_KALLOC);
2231 return kalloc_ext(KHEAP_DEFAULT, size, flags, NULL).addr;
2232 }
2233
2234 flags = Z_VM_TAG_BT(flags & Z_KPI_MASK, VM_KERN_MEMORY_KALLOC);
2235 return zalloc_flags(kt_view, flags);
2236 }
2237
2238 void *
2239 kalloc_type_var_impl_external(
2240 kalloc_type_var_view_t kt_view,
2241 vm_size_t size,
2242 zalloc_flags_t flags,
2243 void *owner);
2244 void *
kalloc_type_var_impl_external(kalloc_type_var_view_t kt_view,vm_size_t size,zalloc_flags_t flags,void * owner)2245 kalloc_type_var_impl_external(
2246 kalloc_type_var_view_t kt_view,
2247 vm_size_t size,
2248 zalloc_flags_t flags,
2249 void *owner)
2250 {
2251 flags = Z_VM_TAG_BT(flags & Z_KPI_MASK, VM_KERN_MEMORY_KALLOC);
2252 return kalloc_type_var_impl(kt_view, size, flags, owner);
2253 }
2254
2255 #pragma mark kfree
2256
2257 __abortlike
2258 static void
kfree_heap_confusion_panic(kalloc_heap_t kheap,void * data,size_t size,zone_t z)2259 kfree_heap_confusion_panic(kalloc_heap_t kheap, void *data, size_t size, zone_t z)
2260 {
2261 zone_security_flags_t zsflags = zone_security_config(z);
2262 const char *kheap_name = "";
2263
2264 if (kheap == KHEAP_ANY) {
2265 kheap_name = "KHEAP_ANY (default/kalloc type var)";
2266 } else {
2267 kheap_name = kalloc_heap_names[kheap->kh_heap_id];
2268 }
2269
2270 if (zsflags.z_kalloc_type) {
2271 panic_include_kalloc_types = true;
2272 kalloc_type_src_zone = z;
2273 panic("kfree: addr %p found in kalloc type zone '%s'"
2274 "but being freed to %s heap", data, z->z_name, kheap_name);
2275 }
2276
2277 if (zsflags.z_kheap_id == KHEAP_ID_NONE) {
2278 panic("kfree: addr %p, size %zd found in regular zone '%s%s'",
2279 data, size, zone_heap_name(z), z->z_name);
2280 } else {
2281 panic("kfree: addr %p, size %zd found in heap %s* instead of %s*",
2282 data, size, zone_heap_name(z), kheap_name);
2283 }
2284 }
2285
2286 __abortlike
2287 static void
kfree_size_confusion_panic(zone_t z,void * data,size_t oob_offs,size_t size,size_t zsize)2288 kfree_size_confusion_panic(zone_t z, void *data,
2289 size_t oob_offs, size_t size, size_t zsize)
2290 {
2291 if (z) {
2292 panic("kfree: addr %p, size %zd (offs:%zd) found in zone '%s%s' "
2293 "with elem_size %zd",
2294 data, size, oob_offs, zone_heap_name(z), z->z_name, zsize);
2295 } else {
2296 panic("kfree: addr %p, size %zd (offs:%zd) not found in any zone",
2297 data, size, oob_offs);
2298 }
2299 }
2300
2301 __abortlike
2302 static void
kfree_size_invalid_panic(void * data,size_t size)2303 kfree_size_invalid_panic(void *data, size_t size)
2304 {
2305 panic("kfree: addr %p trying to free with nonsensical size %zd",
2306 data, size);
2307 }
2308
2309 __abortlike
2310 static void
kfree_size_require_panic(void * data,size_t size,size_t min_size,size_t max_size)2311 kfree_size_require_panic(void *data, size_t size, size_t min_size,
2312 size_t max_size)
2313 {
2314 panic("kfree: addr %p has size %zd, not in specified bounds [%zd - %zd]",
2315 data, size, min_size, max_size);
2316 }
2317
2318 static void
kfree_size_require(kalloc_heap_t kheap,void * addr,vm_size_t min_size,vm_size_t max_size)2319 kfree_size_require(
2320 kalloc_heap_t kheap,
2321 void *addr,
2322 vm_size_t min_size,
2323 vm_size_t max_size)
2324 {
2325 assert3u(min_size, <=, max_size);
2326 #if KASAN_KALLOC
2327 max_size = kasan_alloc_resize(max_size);
2328 #endif
2329 zone_t max_zone = kalloc_zone_for_size(kheap->kh_zstart, max_size);
2330 vm_size_t max_zone_size = max_zone->z_elem_size;
2331 vm_size_t elem_size = zone_element_size(addr, NULL, false, NULL);
2332 if (elem_size > max_zone_size || elem_size < min_size) {
2333 kfree_size_require_panic(addr, elem_size, min_size, max_zone_size);
2334 }
2335 }
2336
2337 static void
kfree_large(vm_offset_t addr,vm_size_t size,kmf_flags_t flags,void * owner)2338 kfree_large(
2339 vm_offset_t addr,
2340 vm_size_t size,
2341 kmf_flags_t flags,
2342 void *owner)
2343 {
2344 #if CONFIG_KERNEL_TBI && KASAN_TBI
2345 if (flags & KMF_GUESS_SIZE) {
2346 size = kmem_size_guard(kernel_map, VM_KERNEL_TBI_FILL(addr),
2347 kalloc_guard(VM_KERN_MEMORY_NONE, 0, owner));
2348 flags &= ~KMF_GUESS_SIZE;
2349 }
2350 addr = kasan_tbi_tag_large_free(addr, size);
2351 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
2352 #if KASAN_KALLOC
2353 /* TODO: quarantine for kasan large that works with guards */
2354 kasan_poison_range(addr, size, ASAN_VALID);
2355 #endif
2356
2357 size = kmem_free_guard(kernel_map, addr, size, flags,
2358 kalloc_guard(VM_KERN_MEMORY_NONE, 0, owner));
2359
2360 counter_dec(&kalloc_large_count);
2361 counter_add(&kalloc_large_total, -(uint64_t)size);
2362 KALLOC_ZINFO_SFREE(size);
2363 DTRACE_VM3(kfree, vm_size_t, size, vm_size_t, size, void*, addr);
2364 }
2365
2366 static void
kfree_zone(void * kheap_or_kt_view __unsafe_indexable,void * data,vm_size_t size,zone_t z,vm_size_t zsize)2367 kfree_zone(
2368 void *kheap_or_kt_view __unsafe_indexable,
2369 void *data,
2370 vm_size_t size,
2371 zone_t z,
2372 vm_size_t zsize)
2373 {
2374 zone_security_flags_t zsflags = zone_security_config(z);
2375 kalloc_type_var_view_t kt_view;
2376 kalloc_heap_t kheap;
2377 zone_stats_t zstats;
2378
2379 if (kt_is_var_view(kheap_or_kt_view)) {
2380 kt_view = kt_demangle_var_view(kheap_or_kt_view);
2381 kheap = kalloc_type_get_heap(kt_view, true);
2382 zstats = kt_view->kt_stats;
2383 } else {
2384 kt_view = NULL;
2385 kheap = kheap_or_kt_view;
2386 zstats = kheap ? kheap->kh_stats : NULL;
2387 }
2388
2389 zsflags = zone_security_config(z);
2390 if (kheap != KHEAP_ANY && kheap != KHEAP_KT_VAR) {
2391 if (kheap->kh_heap_id != zsflags.z_kheap_id) {
2392 kfree_heap_confusion_panic(kheap, data, size, z);
2393 }
2394 } else if (zsflags.z_kheap_id == KHEAP_ID_KT_VAR) {
2395 /*
2396 * Allocations from kalloc.type.var zones use stats from KHEAP_KT_VAR
2397 * if they don't have private accounting. We need to use the kheap_id here
2398 * as we allow cross frees between default and KT_VAR and we may use
2399 * KHEAP_ANY which will skew the stats if we relie on stats from kheap.
2400 */
2401 if (zstats == NULL) {
2402 zstats = KHEAP_KT_VAR->kh_stats;
2403 }
2404 } else if (zsflags.z_kheap_id != KHEAP_ID_DEFAULT) {
2405 kfree_heap_confusion_panic(kheap, data, size, z);
2406 }
2407
2408 DTRACE_VM3(kfree, vm_size_t, size, vm_size_t, zsize, void*, data);
2409
2410 #if KASAN_KALLOC
2411 /*
2412 * Hand the allocation to the quarantine, data might become NULL.
2413 * FIXME: this breaks accounting because we do not remember `zstats`
2414 */
2415 kasan_free(&data, &zsize, KASAN_HEAP_KALLOC, &z, size);
2416 if (data == NULL) {
2417 return;
2418 }
2419 #else
2420 /* needs to be __nosan because the user size might be partial */
2421 __nosan_bzero(data, zsize);
2422 #endif /* !KASAN_ZALLOC */
2423 zfree_ext(z, zstats ?: z->z_stats, data, zsize);
2424 }
2425
2426 void
kfree_ext(void * kheap_or_kt_view __unsafe_indexable,void * data __unsafe_indexable,vm_size_t size)2427 kfree_ext(
2428 void *kheap_or_kt_view __unsafe_indexable,
2429 void *data __unsafe_indexable,
2430 vm_size_t size)
2431 {
2432 vm_size_t adj_size, bucket_size;
2433 zone_t z;
2434
2435 if (data == NULL) {
2436 return;
2437 }
2438
2439 if (size > KFREE_ABSURD_SIZE) {
2440 kfree_size_invalid_panic(data, size);
2441 }
2442
2443 #if KASAN_KALLOC
2444 adj_size = kasan_alloc_resize(size);
2445 kasan_check_free((vm_address_t)data, size, KASAN_HEAP_KALLOC);
2446 #else
2447 adj_size = size;
2448 #if CONFIG_KERNEL_TBI && KASAN_TBI
2449 __asan_loadN((vm_offset_t)data, K_SANE_SIZE(size));
2450 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
2451 #endif /* KASAN_KALLOC */
2452
2453 if (adj_size <= KHEAP_MAX_SIZE) {
2454 vm_size_t oob_offs;
2455
2456 bucket_size = zone_element_size(data, &z, true, &oob_offs);
2457 if (size + oob_offs > bucket_size || bucket_size == 0) {
2458 kfree_size_confusion_panic(z, data,
2459 oob_offs, size, bucket_size);
2460 }
2461
2462 data = (char *)data - oob_offs;
2463 __builtin_assume(z != ZONE_NULL);
2464 } else {
2465 z = ZONE_NULL;
2466 }
2467
2468 #if KASAN_KALLOC
2469 /*
2470 * Resize back to the real allocation size.
2471 */
2472 vm_size_t real_size = size;
2473 data = (void *)kasan_dealloc((vm_address_t)data, &real_size);
2474 if (z) {
2475 bucket_size = real_size;
2476 } else {
2477 size = real_size;
2478 }
2479 #endif /* KASAN_KALLOC */
2480
2481 if (z) {
2482 kfree_zone(kheap_or_kt_view, data, size, z, bucket_size);
2483 } else {
2484 kfree_large((vm_offset_t)data, size, KMF_NONE, NULL);
2485 }
2486 }
2487
2488 void
kfree_addr_ext(kalloc_heap_t kheap,void * data)2489 kfree_addr_ext(kalloc_heap_t kheap, void *data)
2490 {
2491 if (data == NULL) {
2492 return;
2493 }
2494
2495 #if KASAN_KALLOC
2496 kfree_ext(kheap, data, kasan_user_size((vm_offset_t)data));
2497 #else
2498 vm_offset_t oob_offs;
2499 vm_size_t size;
2500 zone_t z;
2501
2502 #if CONFIG_KERNEL_TBI && KASAN_TBI
2503 __asan_loadN((vm_offset_t)data, KALLOC_MINSIZE);
2504 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
2505
2506 size = zone_element_size(data, &z, true, &oob_offs);
2507 if (size) {
2508 data = (char *)data - oob_offs;
2509 kfree_zone(kheap, data, size - oob_offs, z, size);
2510 } else {
2511 kfree_large((vm_offset_t)data, 0, KMF_GUESS_SIZE, NULL);
2512 }
2513 #endif /* !KASAN_KALLOC */
2514 }
2515
2516 void
2517 kfree_external(void *addr, vm_size_t size);
2518 void
kfree_external(void * addr,vm_size_t size)2519 kfree_external(void *addr, vm_size_t size)
2520 {
2521 kfree_ext(KHEAP_ANY, addr, size);
2522 }
2523
2524 void
2525 (kheap_free_bounded)(kalloc_heap_t kheap, void *addr,
2526 vm_size_t min_sz, vm_size_t max_sz)
2527 {
2528 if (__improbable(addr == NULL)) {
2529 return;
2530 }
2531 kfree_size_require(kheap, addr, min_sz, max_sz);
2532 kfree_addr_ext(kheap, addr);
2533 }
2534
2535 void
kfree_type_impl_external(kalloc_type_view_t kt_view,void * ptr)2536 kfree_type_impl_external(kalloc_type_view_t kt_view, void *ptr)
2537 {
2538 /*
2539 * If callsite is from a kext that isn't in the BootKC, it wasn't
2540 * processed during startup so default to using kheap_alloc
2541 *
2542 * Additionally when size is greater KHEAP_MAX_SIZE zone is left
2543 * NULL as we need to use the vm for the allocation/free
2544 */
2545 if (kt_view->kt_zv.zv_zone == ZONE_NULL) {
2546 return kheap_free(KHEAP_DEFAULT, ptr,
2547 kalloc_type_get_size(kt_view->kt_size));
2548 }
2549 if (__improbable(ptr == NULL)) {
2550 return;
2551 }
2552 return zfree(kt_view, ptr);
2553 }
2554
2555 void
2556 kfree_type_var_impl_external(
2557 kalloc_type_var_view_t kt_view,
2558 void *ptr,
2559 vm_size_t size);
2560 void
kfree_type_var_impl_external(kalloc_type_var_view_t kt_view,void * ptr,vm_size_t size)2561 kfree_type_var_impl_external(
2562 kalloc_type_var_view_t kt_view,
2563 void *ptr,
2564 vm_size_t size)
2565 {
2566 return kfree_type_var_impl(kt_view, ptr, size);
2567 }
2568
2569 void
2570 kfree_data_external(void *ptr, vm_size_t size);
2571 void
kfree_data_external(void * ptr,vm_size_t size)2572 kfree_data_external(void *ptr, vm_size_t size)
2573 {
2574 return kheap_free(KHEAP_DATA_BUFFERS, ptr, size);
2575 }
2576
2577 void
2578 kfree_data_addr_external(void *ptr);
2579 void
kfree_data_addr_external(void * ptr)2580 kfree_data_addr_external(void *ptr)
2581 {
2582 return kheap_free_addr(KHEAP_DATA_BUFFERS, ptr);
2583 }
2584
2585 #pragma mark krealloc
2586
2587 __abortlike
2588 static void
krealloc_size_invalid_panic(void * data,size_t size)2589 krealloc_size_invalid_panic(void *data, size_t size)
2590 {
2591 panic("krealloc: addr %p trying to free with nonsensical size %zd",
2592 data, size);
2593 }
2594
2595 __attribute__((noinline))
2596 static struct kalloc_result
krealloc_large(kalloc_heap_t kheap,vm_offset_t addr,vm_size_t old_size,vm_size_t new_size,zalloc_flags_t flags,uint16_t kt_hash,void * owner __unused)2597 krealloc_large(
2598 kalloc_heap_t kheap,
2599 vm_offset_t addr,
2600 vm_size_t old_size,
2601 vm_size_t new_size,
2602 zalloc_flags_t flags,
2603 uint16_t kt_hash,
2604 void *owner __unused)
2605 {
2606 int kmr_flags = KMR_FREEOLD;
2607 vm_size_t new_req_size = new_size;
2608 vm_size_t old_req_size = old_size;
2609 uint64_t delta;
2610 kmem_return_t kmr;
2611 vm_tag_t tag;
2612
2613 if (flags & Z_NOFAIL) {
2614 panic("trying to kalloc(Z_NOFAIL) with a large size (%zd)",
2615 (size_t)new_req_size);
2616 }
2617
2618 /*
2619 * kmem_alloc could block so we return if noblock
2620 *
2621 * also, reject sizes larger than our address space is quickly,
2622 * as kt_size or IOMallocArraySize() expect this.
2623 */
2624 if ((flags & Z_NOWAIT) ||
2625 (new_req_size >> VM_KERNEL_POINTER_SIGNIFICANT_BITS)) {
2626 return (struct kalloc_result){ };
2627 }
2628
2629 #ifndef __x86_64__
2630 /*
2631 * (73465472) on Intel we didn't use to pass this flag,
2632 * which in turned allowed kalloc_large() memory to be shared
2633 * with user directly.
2634 *
2635 * We're bound by this unfortunate ABI.
2636 */
2637 if ((flags & Z_MAY_COPYINMAP) == 0) {
2638 kmr_flags |= KMR_KOBJECT;
2639 } else {
2640 assert(kheap == KHEAP_DATA_BUFFERS);
2641 }
2642 #endif
2643 if (flags & Z_NOPAGEWAIT) {
2644 kmr_flags |= KMR_NOPAGEWAIT;
2645 }
2646 if (flags & Z_ZERO) {
2647 kmr_flags |= KMR_ZERO;
2648 }
2649 if (kheap == KHEAP_DATA_BUFFERS) {
2650 kmr_flags |= KMR_DATA;
2651 }
2652 if (flags & Z_REALLOCF) {
2653 kmr_flags |= KMR_REALLOCF;
2654 }
2655
2656 tag = zalloc_flags_get_tag(flags);
2657 if (flags & Z_VM_TAG_BT_BIT) {
2658 tag = vm_tag_bt() ?: tag;
2659 }
2660 if (tag == VM_KERN_MEMORY_NONE) {
2661 tag = kheap->kh_tag;
2662 }
2663
2664 #if KASAN_KALLOC
2665 /* large allocation - use guard pages instead of small redzones */
2666 if (addr) {
2667 addr = kasan_dealloc(addr, &old_size);
2668 kasan_poison_range(addr, old_size, ASAN_VALID);
2669 }
2670 new_size = round_page(kasan_alloc_resize(new_req_size) + ptoa(2));
2671 #else
2672 new_size = round_page(new_req_size);
2673 old_size = round_page(old_req_size);
2674 #endif
2675
2676 #if CONFIG_KERNEL_TBI && KASAN_TBI
2677 if ((flags & Z_MAY_COPYINMAP) == 0) {
2678 addr = kasan_tbi_tag_large_free(addr, old_size);
2679 }
2680 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
2681
2682 kmr = kmem_realloc_guard(kernel_map, addr, old_size, new_size,
2683 kmr_flags, kalloc_guard(tag, kt_hash, owner));
2684
2685 if (kmr.kmr_address != 0) {
2686 delta = (uint64_t)(new_size - old_size);
2687 } else if (flags & Z_REALLOCF) {
2688 counter_dec(&kalloc_large_count);
2689 delta = (uint64_t)(-old_size);
2690 } else {
2691 delta = 0;
2692 }
2693
2694 counter_add(&kalloc_large_total, delta);
2695 KALLOC_ZINFO_SALLOC(delta);
2696
2697 if (addr != 0) {
2698 DTRACE_VM3(kfree, vm_size_t, old_size, vm_size_t, old_req_size,
2699 void*, addr);
2700 }
2701 if (__improbable(kmr.kmr_address == 0)) {
2702 return (struct kalloc_result){ };
2703 }
2704
2705 #if KASAN_KALLOC
2706 /* fixup the return address to skip the redzone */
2707 kmr.kmr_address = kasan_alloc(kmr.kmr_address,
2708 new_size, new_req_size, PAGE_SIZE);
2709
2710 /*
2711 * kasan stores backtraces in the page in the right red-zone,
2712 * if we realloced, kmem dutifully preserved it, so we need
2713 * to clear it.
2714 */
2715 if ((flags & Z_ZERO) && old_req_size < new_req_size) {
2716 vm_size_t needs_zero_end = PAGE_SIZE + round_page(old_req_size);
2717
2718 __nosan_bzero((char *)kmr.kmr_address + old_req_size,
2719 MIN(needs_zero_end, new_req_size) - old_req_size);
2720 }
2721 #else
2722 #if CONFIG_KERNEL_TBI && KASAN_TBI
2723 if ((flags & Z_MAY_COPYINMAP) == 0) {
2724 kmr.kmr_address = kasan_tbi_tag_large_alloc(kmr.kmr_address,
2725 new_size, new_req_size);
2726 }
2727 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
2728 #endif
2729
2730 DTRACE_VM3(kalloc, vm_size_t, new_size, vm_size_t, new_req_size,
2731 void*, kmr.kmr_address);
2732 return (struct kalloc_result){ .addr = kmr.kmr_ptr, .size = new_req_size };
2733 }
2734
2735 #undef krealloc_ext
2736
2737 struct kalloc_result
krealloc_ext(void * kheap_or_kt_view __unsafe_indexable,void * addr,vm_size_t old_size,vm_size_t new_size,zalloc_flags_t flags,void * owner)2738 krealloc_ext(
2739 void *kheap_or_kt_view __unsafe_indexable,
2740 void *addr,
2741 vm_size_t old_size,
2742 vm_size_t new_size,
2743 zalloc_flags_t flags,
2744 void *owner)
2745 {
2746 vm_size_t old_bucket_size, new_bucket_size, min_size;
2747 vm_size_t adj_new_size, adj_old_size;
2748 kalloc_type_var_view_t kt_view;
2749 kalloc_heap_t kheap;
2750 zone_stats_t zstats = NULL;
2751 struct kalloc_result kr;
2752 vm_offset_t oob_offs = 0;
2753 zone_t old_z, new_z;
2754 uint16_t kt_hash = 0;
2755 zone_id_t zstart;
2756
2757 if (old_size > KFREE_ABSURD_SIZE) {
2758 krealloc_size_invalid_panic(addr, old_size);
2759 }
2760
2761 if (addr == NULL && new_size == 0) {
2762 return (struct kalloc_result){ };
2763 }
2764
2765 #if KASAN_KALLOC
2766 /*
2767 * Adjust sizes to account for kasan redzones
2768 */
2769 adj_new_size = kasan_alloc_resize(new_size);
2770 adj_old_size = kasan_alloc_resize(old_size);
2771 if (addr) {
2772 kasan_check_free((vm_address_t)addr, old_size, KASAN_HEAP_KALLOC);
2773 }
2774 #else
2775 adj_old_size = old_size;
2776 adj_new_size = new_size;
2777 #if CONFIG_KERNEL_TBI && KASAN_TBI
2778 if (addr) {
2779 __asan_loadN((vm_offset_t)addr, K_SANE_SIZE(old_size));
2780 }
2781 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
2782 #endif /* KASAN_KALLOC */
2783
2784 if (kt_is_var_view(kheap_or_kt_view)) {
2785 kt_view = kt_demangle_var_view(kheap_or_kt_view);
2786 kheap = kalloc_type_get_heap(kt_view, false);
2787 /*
2788 * Similar to kalloc_ext: Use stats from view if present, else use stats
2789 * from kheap. krealloc_type isn't exposed to kexts, so we don't need to
2790 * handle cross frees or KHEAP_ANY for typed allocations and can relie on
2791 * stats from view or kheap.
2792 */
2793 zstats = kt_view->kt_stats;
2794 kt_hash = KT_GET_HASH(kt_view->kt_flags);
2795 #if ZSECURITY_CONFIG(KALLOC_TYPE)
2796 zstart = kt_view->kt_heap_start ?: kheap->kh_zstart;
2797 #else
2798 zstart = KHEAP_DEFAULT->kh_zstart;
2799 #endif
2800 } else {
2801 kt_view = NULL;
2802 kheap = kheap_or_kt_view;
2803 kt_hash = kheap->kh_type_hash;
2804 zstart = kheap->kh_zstart;
2805 }
2806
2807 if (!zstats && kheap) {
2808 zstats = kheap->kh_stats;
2809 }
2810 /*
2811 * Find out the size of the bucket in which the new sized allocation
2812 * would land. If it matches the bucket of the original allocation,
2813 * simply return the same address.
2814 */
2815 if (new_size == 0) {
2816 new_z = ZONE_NULL;
2817 new_bucket_size = adj_new_size = 0;
2818 } else {
2819 new_z = kalloc_zone_for_size_with_flags(zstart, adj_new_size, flags);
2820 new_bucket_size = new_z ? zone_elem_size(new_z) : round_page(adj_new_size);
2821 }
2822 #if !KASAN_KALLOC
2823 if (flags & Z_FULLSIZE) {
2824 adj_new_size = new_size = new_bucket_size;
2825 }
2826 #endif /* !KASAN_KALLOC */
2827
2828 if (addr == NULL) {
2829 old_z = ZONE_NULL;
2830 old_size = old_bucket_size = adj_old_size = 0;
2831 } else if (kheap_size_from_zone(addr, adj_old_size, flags)) {
2832 old_bucket_size = zone_element_size(addr, &old_z, true, &oob_offs);
2833 if (old_size + oob_offs > old_bucket_size || old_bucket_size == 0) {
2834 kfree_size_confusion_panic(old_z, addr,
2835 oob_offs, old_size, old_bucket_size);
2836 }
2837 __builtin_assume(old_z != ZONE_NULL);
2838 } else {
2839 old_z = ZONE_NULL;
2840 old_bucket_size = round_page(adj_old_size);
2841 }
2842 min_size = MIN(old_size, new_size);
2843
2844 if (old_bucket_size == new_bucket_size) {
2845 kr.addr = (char *)addr - oob_offs;
2846 kr.size = new_size;
2847 #if ZSECURITY_CONFIG(PGZ_OOB_ADJUST)
2848 if (old_z) {
2849 kr.addr = zone_element_pgz_oob_adjust(kr.addr,
2850 new_size, new_bucket_size);
2851 if (kr.addr != addr) {
2852 memmove(kr.addr, addr, min_size);
2853 bzero((char *)kr.addr + min_size,
2854 kr.size - min_size);
2855 }
2856 }
2857 #endif /* !ZSECURITY_CONFIG(PGZ_OOB_ADJUST) */
2858 #if KASAN_KALLOC
2859 /*
2860 * Adjust right redzone in the element and poison it correctly
2861 */
2862 kr.addr = (void *)kasan_realloc((vm_offset_t)addr,
2863 new_bucket_size + ptoa(old_z ? 0 : 2), kr.size,
2864 old_z ? KASAN_GUARD_SIZE : PAGE_SIZE);
2865 __nosan_bzero((char *)kr.addr + min_size, kr.size - min_size);
2866 #endif /* KASAN_KALLOC */
2867 #if CONFIG_KERNEL_TBI && KASAN_TBI
2868 /*
2869 * Validate the current buffer, then generate a new tag,
2870 * even if the address is stable, it's a "new" allocation.
2871 */
2872 if (old_z) {
2873 kr.addr = (void *)kasan_tbi_tag_zalloc((vm_offset_t)kr.addr,
2874 new_bucket_size, kr.size, false);
2875 } else {
2876 kr.addr = (void *)kasan_tbi_tag_large_alloc((vm_offset_t)kr.addr,
2877 new_bucket_size, kr.size);
2878 }
2879 #endif /* CONFIG_KERNEL_TBI && KASAN_TBI */
2880 return kr;
2881 }
2882
2883 if (addr && !old_z && new_size && !new_z) {
2884 return krealloc_large(kheap, (vm_offset_t)addr,
2885 old_size, new_size, flags, kt_hash, owner);
2886 }
2887
2888 if (!new_size) {
2889 kr.addr = NULL;
2890 kr.size = 0;
2891 } else if (new_z) {
2892 kr = kalloc_zone(new_z, zstats, flags, new_size);
2893 } else if (old_z || addr == NULL) {
2894 kr = kalloc_large(kheap, new_size, flags, kt_hash, owner);
2895 }
2896
2897 if (addr && kr.addr) {
2898 __nosan_memcpy(kr.addr, addr, min_size);
2899 }
2900
2901 if (addr && (kr.addr || (flags & Z_REALLOCF) || !new_size)) {
2902 #if KASAN_KALLOC
2903 /*
2904 * Resize back to the real allocation size.
2905 */
2906 vm_size_t real_size = old_size;
2907 addr = (void *)kasan_dealloc((vm_address_t)addr, &real_size);
2908 if (old_z) {
2909 old_bucket_size = real_size;
2910 } else {
2911 old_size = real_size;
2912 }
2913 #endif /* KASAN_KALLOC */
2914
2915 if (old_z) {
2916 kfree_zone(kheap_or_kt_view,
2917 (char *)addr - oob_offs, old_size,
2918 old_z, old_bucket_size);
2919 } else {
2920 kfree_large((vm_offset_t)addr, old_size, KMF_NONE, owner);
2921 }
2922 }
2923 return kr;
2924 }
2925
2926 void *
2927 krealloc_data_external(
2928 void *ptr,
2929 vm_size_t old_size,
2930 vm_size_t new_size,
2931 zalloc_flags_t flags);
2932 void *
krealloc_data_external(void * ptr,vm_size_t old_size,vm_size_t new_size,zalloc_flags_t flags)2933 krealloc_data_external(
2934 void *ptr,
2935 vm_size_t old_size,
2936 vm_size_t new_size,
2937 zalloc_flags_t flags)
2938 {
2939 flags = Z_VM_TAG_BT(flags & Z_KPI_MASK, VM_KERN_MEMORY_KALLOC_DATA);
2940 return krealloc_ext(KHEAP_DATA_BUFFERS, ptr, old_size, new_size, flags, NULL).addr;
2941 }
2942
2943 __startup_func
2944 void
kheap_startup_init(kalloc_heap_t kheap)2945 kheap_startup_init(kalloc_heap_t kheap)
2946 {
2947 kalloc_heap_t parent_heap;
2948
2949 switch (kheap->kh_heap_id) {
2950 case KHEAP_ID_DEFAULT:
2951 parent_heap = KHEAP_DEFAULT;
2952 break;
2953 case KHEAP_ID_DATA_BUFFERS:
2954 parent_heap = KHEAP_DATA_BUFFERS;
2955 break;
2956 default:
2957 panic("kalloc_heap_startup_init: invalid KHEAP_ID: %d",
2958 kheap->kh_heap_id);
2959 }
2960
2961 kheap->kh_zstart = parent_heap->kh_zstart;
2962 kheap->kh_heap_id = parent_heap->kh_heap_id;
2963 kheap->kh_tag = parent_heap->kh_tag;
2964 kheap->kh_stats = zalloc_percpu_permanent_type(struct zone_stats);
2965 kheap->kh_views = parent_heap->kh_views;
2966 parent_heap->kh_views = kheap;
2967 zone_view_count += 1;
2968
2969 #if XNU_PLATFORM_MacOSX
2970 if (kheap == KERN_OS_MALLOC) {
2971 kheap->kh_type_hash = (uint16_t) kalloc_hash_adjust(
2972 (uint32_t) early_random(), 0);
2973 }
2974 #endif
2975 }
2976
2977 #pragma mark IOKit/libkern helpers
2978
2979 #if XNU_PLATFORM_MacOSX
2980
2981 void *
2982 kern_os_malloc_external(size_t size);
2983 void *
kern_os_malloc_external(size_t size)2984 kern_os_malloc_external(size_t size)
2985 {
2986 if (size == 0) {
2987 return NULL;
2988 }
2989
2990 return kheap_alloc(KERN_OS_MALLOC, size,
2991 Z_VM_TAG_BT(Z_WAITOK_ZERO, VM_KERN_MEMORY_LIBKERN));
2992 }
2993
2994 void
2995 kern_os_free_external(void *addr);
2996 void
kern_os_free_external(void * addr)2997 kern_os_free_external(void *addr)
2998 {
2999 kheap_free_addr(KERN_OS_MALLOC, addr);
3000 }
3001
3002 void *
3003 kern_os_realloc_external(void *addr, size_t nsize);
3004 void *
kern_os_realloc_external(void * addr,size_t nsize)3005 kern_os_realloc_external(void *addr, size_t nsize)
3006 {
3007 zalloc_flags_t flags = Z_VM_TAG_BT(Z_WAITOK_ZERO, VM_KERN_MEMORY_LIBKERN);
3008 vm_size_t osize, oob_offs = 0;
3009
3010 if (addr == NULL) {
3011 return kern_os_malloc_external(nsize);
3012 }
3013
3014 #if KASAN_KALLOC
3015 osize = kasan_user_size((vm_offset_t)addr);
3016 #else
3017 osize = zone_element_size(addr, NULL, false, &oob_offs);
3018 if (osize == 0) {
3019 osize = kmem_size_guard(kernel_map, (vm_offset_t)addr,
3020 kalloc_guard(VM_KERN_MEMORY_LIBKERN, 0, NULL));
3021 }
3022 #endif
3023 return __kheap_realloc(KERN_OS_MALLOC, addr, osize - oob_offs, nsize, flags, NULL);
3024 }
3025
3026 #endif /* XNU_PLATFORM_MacOSX */
3027
3028 void
kern_os_zfree(zone_t zone,void * addr,vm_size_t size)3029 kern_os_zfree(zone_t zone, void *addr, vm_size_t size)
3030 {
3031 #if ZSECURITY_CONFIG(STRICT_IOKIT_FREE)
3032 #pragma unused(size)
3033 zfree(zone, addr);
3034 #else
3035 if (zone_owns(zone, addr)) {
3036 zfree(zone, addr);
3037 } else {
3038 /*
3039 * Third party kexts might not know about the operator new
3040 * and be allocated from the default heap
3041 */
3042 printf("kern_os_zfree: kheap_free called for object from zone %s\n",
3043 zone->z_name);
3044 kheap_free(KHEAP_DEFAULT, addr, size);
3045 }
3046 #endif
3047 }
3048
3049 bool
IOMallocType_from_vm(kalloc_type_view_t ktv)3050 IOMallocType_from_vm(kalloc_type_view_t ktv)
3051 {
3052 return kalloc_type_from_vm(ktv->kt_flags);
3053 }
3054
3055 void
kern_os_typed_free(kalloc_type_view_t ktv,void * addr,vm_size_t esize)3056 kern_os_typed_free(kalloc_type_view_t ktv, void *addr, vm_size_t esize)
3057 {
3058 #if ZSECURITY_CONFIG(STRICT_IOKIT_FREE) || !ZSECURITY_CONFIG(KALLOC_TYPE)
3059 #pragma unused(esize)
3060 #else
3061 /*
3062 * For third party kexts that have been compiled with sdk pre macOS 11,
3063 * an allocation of an OSObject that is defined in xnu or first pary
3064 * kexts, by directly calling new will lead to using the default heap
3065 * as it will call OSObject_operator_new_external. If this object
3066 * is freed by xnu, it panics as xnu uses the typed free which
3067 * requires the object to have been allocated in a kalloc.type zone.
3068 * To workaround this issue, detect if the allocation being freed is
3069 * from the default heap and allow freeing to it.
3070 */
3071 zone_id_t zid = zone_id_for_element(addr, esize);
3072 if (__probable(zid < MAX_ZONES)) {
3073 zone_security_flags_t zsflags = zone_security_array[zid];
3074 if (zsflags.z_kheap_id == KHEAP_ID_DEFAULT) {
3075 return kheap_free(KHEAP_DEFAULT, addr, esize);
3076 }
3077 }
3078 #endif
3079 kfree_type_impl_external(ktv, addr);
3080 }
3081
3082 #pragma mark tests
3083 #if DEBUG || DEVELOPMENT
3084
3085 #include <sys/random.h>
3086 /*
3087 * Ensure that the feature is on when the ZSECURITY_CONFIG is present.
3088 *
3089 * Note: Presence of zones with name kalloc.type* is used to
3090 * determine if the feature is on.
3091 */
3092 static int
kalloc_type_feature_on(void)3093 kalloc_type_feature_on(void)
3094 {
3095 /*
3096 * ZSECURITY_CONFIG not present
3097 */
3098 #if !ZSECURITY_CONFIG(KALLOC_TYPE)
3099 return 1;
3100 #endif /* !ZSECURITY_CONFIG(KALLOC_TYPE) */
3101
3102 boolean_t zone_found = false;
3103 const char kalloc_type_str[] = "kalloc.type";
3104 for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {
3105 zone_t z = kalloc_type_zarray[i];
3106 while (z != NULL) {
3107 zone_found = true;
3108 if (strncmp(z->z_name, kalloc_type_str,
3109 strlen(kalloc_type_str)) != 0) {
3110 return 0;
3111 }
3112 z = z->z_kt_next;
3113 }
3114 }
3115
3116 if (!zone_found) {
3117 return 0;
3118 }
3119
3120 return 1;
3121 }
3122
3123 /*
3124 * Ensure that the policy uses the zone budget completely
3125 */
3126 #if ZSECURITY_CONFIG(KALLOC_TYPE)
3127 static int
kalloc_type_test_policy(int64_t in)3128 kalloc_type_test_policy(int64_t in)
3129 {
3130 uint16_t zone_budget = (uint16_t) in;
3131 uint16_t max_bucket_freq = 25;
3132 uint16_t freq_list[MAX_K_ZONE(kt_zone_cfg)] = {};
3133 uint16_t zones_per_bucket[MAX_K_ZONE(kt_zone_cfg)] = {};
3134 uint16_t random[MAX_K_ZONE(kt_zone_cfg)];
3135 int ret = 0;
3136
3137 /*
3138 * Need a minimum of 2 zones per size class
3139 */
3140 if (zone_budget < MAX_K_ZONE(kt_zone_cfg) * 2) {
3141 return ret;
3142 }
3143 read_random((void *)&random[0], sizeof(random));
3144 for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {
3145 freq_list[i] = random[i] % max_bucket_freq;
3146 }
3147 uint16_t wasted_zone_budget = kalloc_type_apply_policy(freq_list,
3148 zones_per_bucket, zone_budget);
3149 if (wasted_zone_budget == 0) {
3150 ret = 1;
3151 }
3152 return ret;
3153 }
3154 #else /* ZSECURITY_CONFIG(KALLOC_TYPE) */
3155 static int
kalloc_type_test_policy(int64_t in)3156 kalloc_type_test_policy(int64_t in)
3157 {
3158 #pragma unused(in)
3159 return 1;
3160 }
3161 #endif /* !ZSECURITY_CONFIG(KALLOC_TYPE) */
3162
3163 /*
3164 * Ensure that size of adopters of kalloc_type fit in the zone
3165 * they have been assigned.
3166 */
3167 static int
kalloc_type_check_size(zone_t z)3168 kalloc_type_check_size(zone_t z)
3169 {
3170 uint16_t elem_size = z->z_elem_size;
3171 kalloc_type_view_t kt_cur = (kalloc_type_view_t) z->z_views;
3172 const char site_str[] = "site.";
3173 const size_t site_str_len = strlen(site_str);
3174 while (kt_cur != NULL) {
3175 /*
3176 * Process only kalloc_type_views and skip the zone_views when
3177 * feature is off.
3178 */
3179 #if !ZSECURITY_CONFIG(KALLOC_TYPE)
3180 if (strncmp(kt_cur->kt_zv.zv_name, site_str, site_str_len) != 0) {
3181 kt_cur = (kalloc_type_view_t) kt_cur->kt_zv.zv_next;
3182 continue;
3183 }
3184 #else /* !ZSECURITY_CONFIG(KALLOC_TYPE) */
3185 #pragma unused(site_str, site_str_len)
3186 #endif /* ZSECURITY_CONFIG(KALLOC_TYPE) */
3187 if (kalloc_type_get_size(kt_cur->kt_size) > elem_size) {
3188 return 0;
3189 }
3190 kt_cur = (kalloc_type_view_t) kt_cur->kt_zv.zv_next;
3191 }
3192 return 1;
3193 }
3194
3195 struct test_kt_data {
3196 int a;
3197 };
3198
3199 static int
kalloc_type_test_data_redirect(void)3200 kalloc_type_test_data_redirect(void)
3201 {
3202 struct kalloc_type_view ktv_data = {
3203 .kt_flags = KALLOC_TYPE_ADJUST_FLAGS(KT_SHARED_ACCT, struct test_kt_data),
3204 .kt_signature = KALLOC_TYPE_EMIT_SIG(struct test_kt_data),
3205 };
3206 if (!kalloc_type_is_data(ktv_data.kt_flags)) {
3207 printf("%s: data redirect failed\n", __func__);
3208 return 0;
3209 }
3210 return 1;
3211 }
3212
3213 static int
run_kalloc_type_test(int64_t in,int64_t * out)3214 run_kalloc_type_test(int64_t in, int64_t *out)
3215 {
3216 *out = 0;
3217 for (uint16_t i = 0; i < MAX_K_ZONE(kt_zone_cfg); i++) {
3218 zone_t z = kalloc_type_zarray[i];
3219 while (z != NULL) {
3220 if (!kalloc_type_check_size(z)) {
3221 printf("%s: size check failed\n", __func__);
3222 return 0;
3223 }
3224 z = z->z_kt_next;
3225 }
3226 }
3227
3228 if (!kalloc_type_test_policy(in)) {
3229 printf("%s: policy check failed\n", __func__);
3230 return 0;
3231 }
3232
3233 if (!kalloc_type_feature_on()) {
3234 printf("%s: boot-arg is on but feature isn't\n", __func__);
3235 return 0;
3236 }
3237
3238 if (!kalloc_type_test_data_redirect()) {
3239 printf("%s: kalloc_type redirect for all data signature failed\n",
3240 __func__);
3241 return 0;
3242 }
3243
3244 printf("%s: test passed\n", __func__);
3245
3246 *out = 1;
3247 return 0;
3248 }
3249 SYSCTL_TEST_REGISTER(kalloc_type, run_kalloc_type_test);
3250
3251 static vm_size_t
test_bucket_size(kalloc_heap_t kheap,vm_size_t size)3252 test_bucket_size(kalloc_heap_t kheap, vm_size_t size)
3253 {
3254 zone_t z = kalloc_zone_for_size(kheap->kh_zstart, size);
3255
3256 return z ? zone_elem_size(z) : round_page(size);
3257 }
3258
3259 static int
run_kalloc_test(int64_t in __unused,int64_t * out)3260 run_kalloc_test(int64_t in __unused, int64_t *out)
3261 {
3262 *out = 0;
3263 uint64_t *data_ptr;
3264 void *strippedp_old, *strippedp_new;
3265 size_t alloc_size = 0, old_alloc_size = 0;
3266 struct kalloc_result kr = {};
3267
3268 printf("%s: test running\n", __func__);
3269
3270 /*
3271 * Test size 0: alloc, free, realloc
3272 */
3273 data_ptr = kalloc_ext(KHEAP_DATA_BUFFERS, alloc_size, Z_WAITOK | Z_NOFAIL,
3274 NULL).addr;
3275 if (!data_ptr) {
3276 printf("%s: kalloc 0 returned null\n", __func__);
3277 return 0;
3278 }
3279 kheap_free(KHEAP_DATA_BUFFERS, data_ptr, alloc_size);
3280
3281 data_ptr = kalloc_ext(KHEAP_DATA_BUFFERS, alloc_size, Z_WAITOK | Z_NOFAIL,
3282 NULL).addr;
3283 alloc_size = sizeof(uint64_t) + 1;
3284 data_ptr = krealloc_ext(KHEAP_DATA_BUFFERS, kr.addr, old_alloc_size,
3285 alloc_size, Z_WAITOK | Z_NOFAIL, NULL).addr;
3286 if (!data_ptr) {
3287 printf("%s: krealloc -> old size 0 failed\n", __func__);
3288 return 0;
3289 }
3290 *data_ptr = 0;
3291
3292 /*
3293 * Test krealloc: same sizeclass, different size classes, 2pgs,
3294 * VM (with owner)
3295 */
3296 old_alloc_size = alloc_size;
3297 alloc_size++;
3298 kr = krealloc_ext(KHEAP_DATA_BUFFERS, data_ptr, old_alloc_size, alloc_size,
3299 Z_WAITOK | Z_NOFAIL, NULL);
3300
3301 #if CONFIG_KERNEL_TBI
3302 strippedp_old = VM_KERNEL_TBI_FILL(data_ptr);
3303 strippedp_new = VM_KERNEL_TBI_FILL(kr.addr);
3304 #else /* CONFIG_KERNEL_TBI */
3305 strippedp_old = data_ptr;
3306 strippedp_new = kr.addr;
3307 #endif /* !CONFIG_KERNEL_TBI */
3308
3309 if (!kr.addr || (strippedp_old != strippedp_new) ||
3310 (test_bucket_size(KHEAP_DATA_BUFFERS, kr.size) !=
3311 test_bucket_size(KHEAP_DATA_BUFFERS, old_alloc_size))) {
3312 printf("%s: krealloc -> same size class failed\n", __func__);
3313 return 0;
3314 }
3315 data_ptr = kr.addr;
3316 *data_ptr = 0;
3317
3318 old_alloc_size = alloc_size;
3319 alloc_size *= 2;
3320 kr = krealloc_ext(KHEAP_DATA_BUFFERS, data_ptr, old_alloc_size, alloc_size,
3321 Z_WAITOK | Z_NOFAIL, NULL);
3322
3323 #if CONFIG_KERNEL_TBI
3324 strippedp_old = VM_KERNEL_TBI_FILL(data_ptr);
3325 strippedp_new = VM_KERNEL_TBI_FILL(kr.addr);
3326 #else /* CONFIG_KERNEL_TBI */
3327 strippedp_old = data_ptr;
3328 strippedp_new = kr.addr;
3329 #endif /* !CONFIG_KERNEL_TBI */
3330
3331 if (!kr.addr || (strippedp_old == strippedp_new) ||
3332 (test_bucket_size(KHEAP_DATA_BUFFERS, kr.size) ==
3333 test_bucket_size(KHEAP_DATA_BUFFERS, old_alloc_size))) {
3334 printf("%s: krealloc -> different size class failed\n", __func__);
3335 return 0;
3336 }
3337 data_ptr = kr.addr;
3338 *data_ptr = 0;
3339
3340 kheap_free(KHEAP_DATA_BUFFERS, kr.addr, alloc_size);
3341
3342 alloc_size = 3544;
3343 data_ptr = kalloc_ext(KHEAP_DATA_BUFFERS, alloc_size,
3344 Z_WAITOK | Z_FULLSIZE, &data_ptr).addr;
3345 if (!data_ptr) {
3346 printf("%s: kalloc 3544 with owner and Z_FULLSIZE returned not null\n",
3347 __func__);
3348 return 0;
3349 }
3350 *data_ptr = 0;
3351
3352 data_ptr = krealloc_ext(KHEAP_DATA_BUFFERS, data_ptr, alloc_size,
3353 PAGE_SIZE * 2, Z_REALLOCF | Z_WAITOK, &data_ptr).addr;
3354 if (!data_ptr) {
3355 printf("%s: krealloc -> 2pgs returned not null\n", __func__);
3356 return 0;
3357 }
3358 *data_ptr = 0;
3359
3360 data_ptr = krealloc_ext(KHEAP_DATA_BUFFERS, data_ptr, PAGE_SIZE * 2,
3361 KHEAP_MAX_SIZE * 2, Z_REALLOCF | Z_WAITOK, &data_ptr).addr;
3362 if (!data_ptr) {
3363 printf("%s: krealloc -> VM1 returned not null\n", __func__);
3364 return 0;
3365 }
3366 *data_ptr = 0;
3367
3368 data_ptr = krealloc_ext(KHEAP_DATA_BUFFERS, data_ptr, KHEAP_MAX_SIZE * 2,
3369 KHEAP_MAX_SIZE * 4, Z_REALLOCF | Z_WAITOK, &data_ptr).addr;
3370 *data_ptr = 0;
3371 if (!data_ptr) {
3372 printf("%s: krealloc -> VM2 returned not null\n", __func__);
3373 return 0;
3374 }
3375
3376 krealloc_ext(KHEAP_DATA_BUFFERS, data_ptr, KHEAP_MAX_SIZE * 4,
3377 0, Z_REALLOCF | Z_WAITOK, &data_ptr);
3378
3379 printf("%s: test passed\n", __func__);
3380 *out = 1;
3381 return 0;
3382 }
3383 SYSCTL_TEST_REGISTER(kalloc, run_kalloc_test);
3384
3385 #endif
3386