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