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