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