]> git.saurik.com Git - apple/xnu.git/blob - osfmk/kern/kalloc.c
xnu-4570.20.62.tar.gz
[apple/xnu.git] / osfmk / kern / kalloc.c
1 /*
2 * Copyright (c) 2000-2011 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 Software.Distribution@CS.CMU.EDU
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 <zone_debug.h>
68
69 #include <mach/boolean.h>
70 #include <mach/machine/vm_types.h>
71 #include <mach/vm_param.h>
72 #include <kern/misc_protos.h>
73 #include <kern/zalloc.h>
74 #include <kern/kalloc.h>
75 #include <kern/ledger.h>
76 #include <vm/vm_kern.h>
77 #include <vm/vm_object.h>
78 #include <vm/vm_map.h>
79 #include <libkern/OSMalloc.h>
80 #include <sys/kdebug.h>
81
82 #include <san/kasan.h>
83
84 #ifdef MACH_BSD
85 zone_t kalloc_zone(vm_size_t);
86 #endif
87
88 #define KALLOC_MAP_SIZE_MIN (16 * 1024 * 1024)
89 #define KALLOC_MAP_SIZE_MAX (128 * 1024 * 1024)
90 vm_map_t kalloc_map;
91 vm_size_t kalloc_max;
92 vm_size_t kalloc_max_prerounded;
93 vm_size_t kalloc_kernmap_size; /* size of kallocs that can come from kernel map */
94
95 /* how many times we couldn't allocate out of kalloc_map and fell back to kernel_map */
96 unsigned long kalloc_fallback_count;
97
98 unsigned int kalloc_large_inuse;
99 vm_size_t kalloc_large_total;
100 vm_size_t kalloc_large_max;
101 vm_size_t kalloc_largest_allocated = 0;
102 uint64_t kalloc_large_sum;
103
104 int kalloc_fake_zone_index = -1; /* index of our fake zone in statistics arrays */
105
106 vm_offset_t kalloc_map_min;
107 vm_offset_t kalloc_map_max;
108
109 #ifdef MUTEX_ZONE
110 /*
111 * Diagnostic code to track mutexes separately rather than via the 2^ zones
112 */
113 zone_t lck_mtx_zone;
114 #endif
115
116 static void
117 KALLOC_ZINFO_SALLOC(vm_size_t bytes)
118 {
119 thread_t thr = current_thread();
120 ledger_debit(thr->t_ledger, task_ledgers.tkm_shared, bytes);
121 }
122
123 static void
124 KALLOC_ZINFO_SFREE(vm_size_t bytes)
125 {
126 thread_t thr = current_thread();
127 ledger_credit(thr->t_ledger, task_ledgers.tkm_shared, bytes);
128 }
129
130 /*
131 * All allocations of size less than kalloc_max are rounded to the
132 * next nearest sized zone. This allocator is built on top of
133 * the zone allocator. A zone is created for each potential size
134 * that we are willing to get in small blocks.
135 *
136 * We assume that kalloc_max is not greater than 64K;
137 *
138 * Note that kalloc_max is somewhat confusingly named.
139 * It represents the first power of two for which no zone exists.
140 * kalloc_max_prerounded is the smallest allocation size, before
141 * rounding, for which no zone exists.
142 *
143 * Also if the allocation size is more than kalloc_kernmap_size
144 * then allocate from kernel map rather than kalloc_map.
145 */
146
147 #if KALLOC_MINSIZE == 16 && KALLOC_LOG2_MINALIGN == 4
148
149 #define K_ZONE_SIZES \
150 16, \
151 32, \
152 48, \
153 /* 3 */ 64, \
154 80, \
155 96, \
156 /* 6 */ 128, \
157 160, 192, \
158 256, \
159 /* 9 */ 288, \
160 512, 576, \
161 1024, 1152, \
162 /* C */ 1280, \
163 2048, \
164 4096
165
166 #define K_ZONE_NAMES \
167 "kalloc.16", \
168 "kalloc.32", \
169 "kalloc.48", \
170 /* 3 */ "kalloc.64", \
171 "kalloc.80", \
172 "kalloc.96", \
173 /* 6 */ "kalloc.128", \
174 "kalloc.160", \
175 "kalloc.192", \
176 "kalloc.256", \
177 /* 9 */ "kalloc.288", \
178 "kalloc.512", \
179 "kalloc.576", \
180 "kalloc.1024", \
181 "kalloc.1152", \
182 /* C */ "kalloc.1280", \
183 "kalloc.2048", \
184 "kalloc.4096"
185
186 #elif KALLOC_MINSIZE == 8 && KALLOC_LOG2_MINALIGN == 3
187
188 /*
189 * Tweaked for ARM (and x64) in 04/2011
190 */
191
192 #define K_ZONE_SIZES \
193 /* 3 */ 8, \
194 16, 24, \
195 32, 40, 48, \
196 /* 6 */ 64, 72, 88, 112, \
197 128, 192, \
198 256, 288, 384, 440, \
199 /* 9 */ 512, 576, 768, \
200 1024, 1152, 1536, \
201 2048, 2128, 3072, \
202 4096, 6144
203
204 #define K_ZONE_NAMES \
205 /* 3 */ "kalloc.8", \
206 "kalloc.16", "kalloc.24", \
207 "kalloc.32", "kalloc.40", "kalloc.48", \
208 /* 6 */ "kalloc.64", "kalloc.72", "kalloc.88", "kalloc.112", \
209 "kalloc.128", "kalloc.192", \
210 "kalloc.256", "kalloc.288", "kalloc.384", "kalloc.440", \
211 /* 9 */ "kalloc.512", "kalloc.576", "kalloc.768", \
212 "kalloc.1024", "kalloc.1152", "kalloc.1536", \
213 "kalloc.2048", "kalloc.2128", "kalloc.3072", \
214 "kalloc.4096", "kalloc.6144"
215
216 #else
217 #error missing zone size parameters for kalloc
218 #endif
219
220 #define KALLOC_MINALIGN (1 << KALLOC_LOG2_MINALIGN)
221 #define KiB(x) (1024 * (x))
222
223 static const int k_zone_size[] = {
224 K_ZONE_SIZES,
225 KiB(8),
226 KiB(16),
227 KiB(32)
228 };
229
230 #define MAX_K_ZONE (sizeof (k_zone_size) / sizeof (k_zone_size[0]))
231
232 static const char *k_zone_name[MAX_K_ZONE] = {
233 K_ZONE_NAMES,
234 "kalloc.8192",
235 "kalloc.16384",
236 "kalloc.32768"
237 };
238
239
240 /*
241 * Many kalloc() allocations are for small structures containing a few
242 * pointers and longs - the k_zone_dlut[] direct lookup table, indexed by
243 * size normalized to the minimum alignment, finds the right zone index
244 * for them in one dereference.
245 */
246
247 #define INDEX_ZDLUT(size) \
248 (((size) + KALLOC_MINALIGN - 1) / KALLOC_MINALIGN)
249 #define N_K_ZDLUT (2048 / KALLOC_MINALIGN)
250 /* covers sizes [0 .. 2048 - KALLOC_MINALIGN] */
251 #define MAX_SIZE_ZDLUT ((N_K_ZDLUT - 1) * KALLOC_MINALIGN)
252
253 static int8_t k_zone_dlut[N_K_ZDLUT]; /* table of indices into k_zone[] */
254
255 /*
256 * If there's no hit in the DLUT, then start searching from k_zindex_start.
257 */
258 static int k_zindex_start;
259
260 static zone_t k_zone[MAX_K_ZONE];
261
262 /* #define KALLOC_DEBUG 1 */
263
264 /* forward declarations */
265
266 lck_grp_t kalloc_lck_grp;
267 lck_mtx_t kalloc_lock;
268
269 #define kalloc_spin_lock() lck_mtx_lock_spin(&kalloc_lock)
270 #define kalloc_unlock() lck_mtx_unlock(&kalloc_lock)
271
272
273 /* OSMalloc local data declarations */
274 static
275 queue_head_t OSMalloc_tag_list;
276
277 lck_grp_t *OSMalloc_tag_lck_grp;
278 lck_mtx_t OSMalloc_tag_lock;
279
280 #define OSMalloc_tag_spin_lock() lck_mtx_lock_spin(&OSMalloc_tag_lock)
281 #define OSMalloc_tag_unlock() lck_mtx_unlock(&OSMalloc_tag_lock)
282
283
284 /* OSMalloc forward declarations */
285 void OSMalloc_init(void);
286 void OSMalloc_Tagref(OSMallocTag tag);
287 void OSMalloc_Tagrele(OSMallocTag tag);
288
289 /*
290 * Initialize the memory allocator. This should be called only
291 * once on a system wide basis (i.e. first processor to get here
292 * does the initialization).
293 *
294 * This initializes all of the zones.
295 */
296
297 void
298 kalloc_init(
299 void)
300 {
301 kern_return_t retval;
302 vm_offset_t min;
303 vm_size_t size, kalloc_map_size;
304 int i;
305 vm_map_kernel_flags_t vmk_flags;
306
307 /*
308 * Scale the kalloc_map_size to physical memory size: stay below
309 * 1/8th the total zone map size, or 128 MB (for a 32-bit kernel).
310 */
311 kalloc_map_size = (vm_size_t)(sane_size >> 5);
312 #if !__LP64__
313 if (kalloc_map_size > KALLOC_MAP_SIZE_MAX)
314 kalloc_map_size = KALLOC_MAP_SIZE_MAX;
315 #endif /* !__LP64__ */
316 if (kalloc_map_size < KALLOC_MAP_SIZE_MIN)
317 kalloc_map_size = KALLOC_MAP_SIZE_MIN;
318
319 vmk_flags = VM_MAP_KERNEL_FLAGS_NONE;
320 vmk_flags.vmkf_permanent = TRUE;
321
322 retval = kmem_suballoc(kernel_map, &min, kalloc_map_size,
323 FALSE,
324 (VM_FLAGS_ANYWHERE),
325 vmk_flags,
326 VM_KERN_MEMORY_KALLOC,
327 &kalloc_map);
328
329 if (retval != KERN_SUCCESS)
330 panic("kalloc_init: kmem_suballoc failed");
331
332 kalloc_map_min = min;
333 kalloc_map_max = min + kalloc_map_size - 1;
334
335 /*
336 * Create zones up to a least 2 pages because small page-multiples are common
337 * allocations. Also ensure that zones up to size 8192 bytes exist. This is
338 * desirable because messages are allocated with kalloc(), and messages up
339 * through size 8192 are common.
340 */
341 kalloc_max = PAGE_SIZE << 2;
342 if (kalloc_max < KiB(16)) {
343 kalloc_max = KiB(16);
344 }
345 assert(kalloc_max <= KiB(64)); /* assumption made in size arrays */
346
347 kalloc_max_prerounded = kalloc_max / 2 + 1;
348 /* allocations larger than 16 times kalloc_max go directly to kernel map */
349 kalloc_kernmap_size = (kalloc_max * 16) + 1;
350 kalloc_largest_allocated = kalloc_kernmap_size;
351
352 /*
353 * Allocate a zone for each size we are going to handle. Don't charge the
354 * caller for the allocation, as we aren't sure how the memory will be
355 * handled.
356 */
357 for (i = 0; i < (int)MAX_K_ZONE && (size = k_zone_size[i]) < kalloc_max; i++) {
358 k_zone[i] = zinit(size, size, size, k_zone_name[i]);
359 zone_change(k_zone[i], Z_CALLERACCT, FALSE);
360 #if VM_MAX_TAG_ZONES
361 if (zone_tagging_on) zone_change(k_zone[i], Z_TAGS_ENABLED, TRUE);
362 #endif
363 zone_change(k_zone[i], Z_KASAN_QUARANTINE, FALSE);
364 }
365
366 /*
367 * Build the Direct LookUp Table for small allocations
368 */
369 for (i = 0, size = 0; i <= N_K_ZDLUT; i++, size += KALLOC_MINALIGN) {
370 int zindex = 0;
371
372 while ((vm_size_t)k_zone_size[zindex] < size)
373 zindex++;
374
375 if (i == N_K_ZDLUT) {
376 k_zindex_start = zindex;
377 break;
378 }
379 k_zone_dlut[i] = (int8_t)zindex;
380 }
381
382 #ifdef KALLOC_DEBUG
383 printf("kalloc_init: k_zindex_start %d\n", k_zindex_start);
384
385 /*
386 * Do a quick synthesis to see how well/badly we can
387 * find-a-zone for a given size.
388 * Useful when debugging/tweaking the array of zone sizes.
389 * Cache misses probably more critical than compare-branches!
390 */
391 for (i = 0; i < (int)MAX_K_ZONE; i++) {
392 vm_size_t testsize = (vm_size_t)k_zone_size[i] - 1;
393 int compare = 0;
394 int zindex;
395
396 if (testsize < MAX_SIZE_ZDLUT) {
397 compare += 1; /* 'if' (T) */
398
399 long dindex = INDEX_ZDLUT(testsize);
400 zindex = (int)k_zone_dlut[dindex];
401
402 } else if (testsize < kalloc_max_prerounded) {
403
404 compare += 2; /* 'if' (F), 'if' (T) */
405
406 zindex = k_zindex_start;
407 while ((vm_size_t)k_zone_size[zindex] < testsize) {
408 zindex++;
409 compare++; /* 'while' (T) */
410 }
411 compare++; /* 'while' (F) */
412 } else
413 break; /* not zone-backed */
414
415 zone_t z = k_zone[zindex];
416 printf("kalloc_init: req size %4lu: %11s took %d compare%s\n",
417 (unsigned long)testsize, z->zone_name, compare,
418 compare == 1 ? "" : "s");
419 }
420 #endif
421
422 lck_grp_init(&kalloc_lck_grp, "kalloc.large", LCK_GRP_ATTR_NULL);
423 lck_mtx_init(&kalloc_lock, &kalloc_lck_grp, LCK_ATTR_NULL);
424 OSMalloc_init();
425 #ifdef MUTEX_ZONE
426 lck_mtx_zone = zinit(sizeof(struct _lck_mtx_), 1024*256, 4096, "lck_mtx");
427 #endif
428 }
429
430 /*
431 * Given an allocation size, return the kalloc zone it belongs to.
432 * Direct LookUp Table variant.
433 */
434 static __inline zone_t
435 get_zone_dlut(vm_size_t size)
436 {
437 long dindex = INDEX_ZDLUT(size);
438 int zindex = (int)k_zone_dlut[dindex];
439 return (k_zone[zindex]);
440 }
441
442 /* As above, but linear search k_zone_size[] for the next zone that fits. */
443
444 static __inline zone_t
445 get_zone_search(vm_size_t size, int zindex)
446 {
447 assert(size < kalloc_max_prerounded);
448
449 while ((vm_size_t)k_zone_size[zindex] < size)
450 zindex++;
451
452 assert((unsigned)zindex < MAX_K_ZONE &&
453 (vm_size_t)k_zone_size[zindex] < kalloc_max);
454
455 return (k_zone[zindex]);
456 }
457
458 static vm_size_t
459 vm_map_lookup_kalloc_entry_locked(
460 vm_map_t map,
461 void *addr)
462 {
463 boolean_t ret;
464 vm_map_entry_t vm_entry = NULL;
465
466 ret = vm_map_lookup_entry(map, (vm_map_offset_t)addr, &vm_entry);
467 if (!ret) {
468 panic("Attempting to lookup/free an address not allocated via kalloc! (vm_map_lookup_entry() failed map: %p, addr: %p)\n",
469 map, addr);
470 }
471 if (vm_entry->vme_start != (vm_map_offset_t)addr) {
472 panic("Attempting to lookup/free the middle of a kalloc'ed element! (map: %p, addr: %p, entry: %p)\n",
473 map, addr, vm_entry);
474 }
475 if (!vm_entry->vme_atomic) {
476 panic("Attempting to lookup/free an address not managed by kalloc! (map: %p, addr: %p, entry: %p)\n",
477 map, addr, vm_entry);
478 }
479 return (vm_entry->vme_end - vm_entry->vme_start);
480 }
481
482 #if KASAN_KALLOC
483 /*
484 * KASAN kalloc stashes the original user-requested size away in the poisoned
485 * area. Return that directly.
486 */
487 vm_size_t
488 kalloc_size(void *addr)
489 {
490 (void)vm_map_lookup_kalloc_entry_locked; /* silence warning */
491 return kasan_user_size((vm_offset_t)addr);
492 }
493 #else
494 vm_size_t
495 kalloc_size(
496 void *addr)
497 {
498 vm_map_t map;
499 vm_size_t size;
500
501 size = zone_element_size(addr, NULL);
502 if (size) {
503 return size;
504 }
505 if (((vm_offset_t)addr >= kalloc_map_min) && ((vm_offset_t)addr < kalloc_map_max)) {
506 map = kalloc_map;
507 } else {
508 map = kernel_map;
509 }
510 vm_map_lock_read(map);
511 size = vm_map_lookup_kalloc_entry_locked(map, addr);
512 vm_map_unlock_read(map);
513 return size;
514 }
515 #endif
516
517 vm_size_t
518 kalloc_bucket_size(
519 vm_size_t size)
520 {
521 zone_t z;
522 vm_map_t map;
523
524 if (size < MAX_SIZE_ZDLUT) {
525 z = get_zone_dlut(size);
526 return z->elem_size;
527 }
528
529 if (size < kalloc_max_prerounded) {
530 z = get_zone_search(size, k_zindex_start);
531 return z->elem_size;
532 }
533
534 if (size >= kalloc_kernmap_size)
535 map = kernel_map;
536 else
537 map = kalloc_map;
538
539 return vm_map_round_page(size, VM_MAP_PAGE_MASK(map));
540 }
541
542 #if KASAN_KALLOC
543 vm_size_t
544 kfree_addr(void *addr)
545 {
546 vm_size_t origsz = kalloc_size(addr);
547 kfree(addr, origsz);
548 return origsz;
549 }
550 #else
551 vm_size_t
552 kfree_addr(
553 void *addr)
554 {
555 vm_map_t map;
556 vm_size_t size = 0;
557 kern_return_t ret;
558 zone_t z;
559
560 size = zone_element_size(addr, &z);
561 if (size) {
562 zfree(z, addr);
563 return size;
564 }
565
566 if (((vm_offset_t)addr >= kalloc_map_min) && ((vm_offset_t)addr < kalloc_map_max)) {
567 map = kalloc_map;
568 } else {
569 map = kernel_map;
570 }
571 if ((vm_offset_t)addr < VM_MIN_KERNEL_AND_KEXT_ADDRESS) {
572 panic("kfree on an address not in the kernel & kext address range! addr: %p\n", addr);
573 }
574
575 vm_map_lock(map);
576 size = vm_map_lookup_kalloc_entry_locked(map, addr);
577 ret = vm_map_remove_locked(map,
578 vm_map_trunc_page((vm_map_offset_t)addr,
579 VM_MAP_PAGE_MASK(map)),
580 vm_map_round_page((vm_map_offset_t)addr + size,
581 VM_MAP_PAGE_MASK(map)),
582 VM_MAP_REMOVE_KUNWIRE);
583 if (ret != KERN_SUCCESS) {
584 panic("vm_map_remove_locked() failed for kalloc vm_entry! addr: %p, map: %p ret: %d\n",
585 addr, map, ret);
586 }
587 vm_map_unlock(map);
588
589 kalloc_spin_lock();
590 kalloc_large_total -= size;
591 kalloc_large_inuse--;
592 kalloc_unlock();
593
594 KALLOC_ZINFO_SFREE(size);
595 return size;
596 }
597 #endif
598
599 void *
600 kalloc_canblock(
601 vm_size_t * psize,
602 boolean_t canblock,
603 vm_allocation_site_t * site)
604 {
605 zone_t z;
606 vm_size_t size;
607 void *addr;
608 vm_tag_t tag;
609
610 tag = VM_KERN_MEMORY_KALLOC;
611 size = *psize;
612
613 #if KASAN_KALLOC
614 /* expand the allocation to accomodate redzones */
615 vm_size_t req_size = size;
616 size = kasan_alloc_resize(req_size);
617 #endif
618
619 if (size < MAX_SIZE_ZDLUT)
620 z = get_zone_dlut(size);
621 else if (size < kalloc_max_prerounded)
622 z = get_zone_search(size, k_zindex_start);
623 else {
624 /*
625 * If size is too large for a zone, then use kmem_alloc.
626 * (We use kmem_alloc instead of kmem_alloc_kobject so that
627 * krealloc can use kmem_realloc.)
628 */
629 vm_map_t alloc_map;
630
631 /* kmem_alloc could block so we return if noblock */
632 if (!canblock) {
633 return(NULL);
634 }
635
636 #if KASAN_KALLOC
637 /* large allocation - use guard pages instead of small redzones */
638 size = round_page(req_size + 2 * PAGE_SIZE);
639 assert(size >= MAX_SIZE_ZDLUT && size >= kalloc_max_prerounded);
640 #endif
641
642 if (size >= kalloc_kernmap_size)
643 alloc_map = kernel_map;
644 else
645 alloc_map = kalloc_map;
646
647 if (site) tag = vm_tag_alloc(site);
648
649 if (kmem_alloc_flags(alloc_map, (vm_offset_t *)&addr, size, tag, KMA_ATOMIC) != KERN_SUCCESS) {
650 if (alloc_map != kernel_map) {
651 if (kalloc_fallback_count++ == 0) {
652 printf("%s: falling back to kernel_map\n", __func__);
653 }
654 if (kmem_alloc_flags(kernel_map, (vm_offset_t *)&addr, size, tag, KMA_ATOMIC) != KERN_SUCCESS)
655 addr = NULL;
656 }
657 else
658 addr = NULL;
659 }
660
661 if (addr != NULL) {
662 kalloc_spin_lock();
663 /*
664 * Thread-safe version of the workaround for 4740071
665 * (a double FREE())
666 */
667 if (size > kalloc_largest_allocated)
668 kalloc_largest_allocated = size;
669
670 kalloc_large_inuse++;
671 kalloc_large_total += size;
672 kalloc_large_sum += size;
673
674 if (kalloc_large_total > kalloc_large_max)
675 kalloc_large_max = kalloc_large_total;
676
677 kalloc_unlock();
678
679 KALLOC_ZINFO_SALLOC(size);
680 }
681 #if KASAN_KALLOC
682 /* fixup the return address to skip the redzone */
683 addr = (void *)kasan_alloc((vm_offset_t)addr, size, req_size, PAGE_SIZE);
684 #else
685 *psize = round_page(size);
686 #endif
687 return(addr);
688 }
689 #ifdef KALLOC_DEBUG
690 if (size > z->elem_size)
691 panic("%s: z %p (%s) but requested size %lu", __func__,
692 z, z->zone_name, (unsigned long)size);
693 #endif
694
695 assert(size <= z->elem_size);
696
697 #if VM_MAX_TAG_ZONES
698 if (z->tags && site)
699 {
700 tag = vm_tag_alloc(site);
701 if (!canblock && !vm_allocation_zone_totals[tag]) tag = VM_KERN_MEMORY_KALLOC;
702 }
703 #endif
704
705 addr = zalloc_canblock_tag(z, canblock, size, tag);
706
707 #if KASAN_KALLOC
708 /* fixup the return address to skip the redzone */
709 addr = (void *)kasan_alloc((vm_offset_t)addr, z->elem_size, req_size, KASAN_GUARD_SIZE);
710
711 /* For KASan, the redzone lives in any additional space, so don't
712 * expand the allocation. */
713 #else
714 *psize = z->elem_size;
715 #endif
716
717 return addr;
718 }
719
720 void *
721 kalloc_external(
722 vm_size_t size);
723 void *
724 kalloc_external(
725 vm_size_t size)
726 {
727 return( kalloc_tag_bt(size, VM_KERN_MEMORY_KALLOC) );
728 }
729
730 volatile SInt32 kfree_nop_count = 0;
731
732 void
733 kfree(
734 void *data,
735 vm_size_t size)
736 {
737 zone_t z;
738
739 #if KASAN_KALLOC
740 /*
741 * Resize back to the real allocation size and hand off to the KASan
742 * quarantine. `data` may then point to a different allocation.
743 */
744 vm_size_t user_size = size;
745 kasan_check_free((vm_address_t)data, size, KASAN_HEAP_KALLOC);
746 data = (void *)kasan_dealloc((vm_address_t)data, &size);
747 kasan_free(&data, &size, KASAN_HEAP_KALLOC, NULL, user_size, true);
748 if (!data) {
749 return;
750 }
751 #endif
752
753 if (size < MAX_SIZE_ZDLUT)
754 z = get_zone_dlut(size);
755 else if (size < kalloc_max_prerounded)
756 z = get_zone_search(size, k_zindex_start);
757 else {
758 /* if size was too large for a zone, then use kmem_free */
759
760 vm_map_t alloc_map = kernel_map;
761
762 if ((((vm_offset_t) data) >= kalloc_map_min) && (((vm_offset_t) data) <= kalloc_map_max))
763 alloc_map = kalloc_map;
764 if (size > kalloc_largest_allocated) {
765 /*
766 * work around double FREEs of small MALLOCs
767 * this used to end up being a nop
768 * since the pointer being freed from an
769 * alloc backed by the zalloc world could
770 * never show up in the kalloc_map... however,
771 * the kernel_map is a different issue... since it
772 * was released back into the zalloc pool, a pointer
773 * would have gotten written over the 'size' that
774 * the MALLOC was retaining in the first 4 bytes of
775 * the underlying allocation... that pointer ends up
776 * looking like a really big size on the 2nd FREE and
777 * pushes the kfree into the kernel_map... we
778 * end up removing a ton of virtual space before we panic
779 * this check causes us to ignore the kfree for a size
780 * that must be 'bogus'... note that it might not be due
781 * to the above scenario, but it would still be wrong and
782 * cause serious damage.
783 */
784
785 OSAddAtomic(1, &kfree_nop_count);
786 return;
787 }
788 kmem_free(alloc_map, (vm_offset_t)data, size);
789 kalloc_spin_lock();
790
791 kalloc_large_total -= size;
792 kalloc_large_inuse--;
793
794 kalloc_unlock();
795
796 KALLOC_ZINFO_SFREE(size);
797 return;
798 }
799
800 /* free to the appropriate zone */
801 #ifdef KALLOC_DEBUG
802 if (size > z->elem_size)
803 panic("%s: z %p (%s) but requested size %lu", __func__,
804 z, z->zone_name, (unsigned long)size);
805 #endif
806 assert(size <= z->elem_size);
807 zfree(z, data);
808 }
809
810 #ifdef MACH_BSD
811 zone_t
812 kalloc_zone(
813 vm_size_t size)
814 {
815 if (size < MAX_SIZE_ZDLUT)
816 return (get_zone_dlut(size));
817 if (size <= kalloc_max)
818 return (get_zone_search(size, k_zindex_start));
819 return (ZONE_NULL);
820 }
821 #endif
822
823 void
824 OSMalloc_init(
825 void)
826 {
827 queue_init(&OSMalloc_tag_list);
828
829 OSMalloc_tag_lck_grp = lck_grp_alloc_init("OSMalloc_tag", LCK_GRP_ATTR_NULL);
830 lck_mtx_init(&OSMalloc_tag_lock, OSMalloc_tag_lck_grp, LCK_ATTR_NULL);
831 }
832
833 OSMallocTag
834 OSMalloc_Tagalloc(
835 const char *str,
836 uint32_t flags)
837 {
838 OSMallocTag OSMTag;
839
840 OSMTag = (OSMallocTag)kalloc(sizeof(*OSMTag));
841
842 bzero((void *)OSMTag, sizeof(*OSMTag));
843
844 if (flags & OSMT_PAGEABLE)
845 OSMTag->OSMT_attr = OSMT_ATTR_PAGEABLE;
846
847 OSMTag->OSMT_refcnt = 1;
848
849 strlcpy(OSMTag->OSMT_name, str, OSMT_MAX_NAME);
850
851 OSMalloc_tag_spin_lock();
852 enqueue_tail(&OSMalloc_tag_list, (queue_entry_t)OSMTag);
853 OSMalloc_tag_unlock();
854 OSMTag->OSMT_state = OSMT_VALID;
855 return(OSMTag);
856 }
857
858 void
859 OSMalloc_Tagref(
860 OSMallocTag tag)
861 {
862 if (!((tag->OSMT_state & OSMT_VALID_MASK) == OSMT_VALID))
863 panic("OSMalloc_Tagref():'%s' has bad state 0x%08X\n", tag->OSMT_name, tag->OSMT_state);
864
865 (void)hw_atomic_add(&tag->OSMT_refcnt, 1);
866 }
867
868 void
869 OSMalloc_Tagrele(
870 OSMallocTag tag)
871 {
872 if (!((tag->OSMT_state & OSMT_VALID_MASK) == OSMT_VALID))
873 panic("OSMalloc_Tagref():'%s' has bad state 0x%08X\n", tag->OSMT_name, tag->OSMT_state);
874
875 if (hw_atomic_sub(&tag->OSMT_refcnt, 1) == 0) {
876 if (hw_compare_and_store(OSMT_VALID|OSMT_RELEASED, OSMT_VALID|OSMT_RELEASED, &tag->OSMT_state)) {
877 OSMalloc_tag_spin_lock();
878 (void)remque((queue_entry_t)tag);
879 OSMalloc_tag_unlock();
880 kfree((void*)tag, sizeof(*tag));
881 } else
882 panic("OSMalloc_Tagrele():'%s' has refcnt 0\n", tag->OSMT_name);
883 }
884 }
885
886 void
887 OSMalloc_Tagfree(
888 OSMallocTag tag)
889 {
890 if (!hw_compare_and_store(OSMT_VALID, OSMT_VALID|OSMT_RELEASED, &tag->OSMT_state))
891 panic("OSMalloc_Tagfree():'%s' has bad state 0x%08X \n", tag->OSMT_name, tag->OSMT_state);
892
893 if (hw_atomic_sub(&tag->OSMT_refcnt, 1) == 0) {
894 OSMalloc_tag_spin_lock();
895 (void)remque((queue_entry_t)tag);
896 OSMalloc_tag_unlock();
897 kfree((void*)tag, sizeof(*tag));
898 }
899 }
900
901 void *
902 OSMalloc(
903 uint32_t size,
904 OSMallocTag tag)
905 {
906 void *addr=NULL;
907 kern_return_t kr;
908
909 OSMalloc_Tagref(tag);
910 if ((tag->OSMT_attr & OSMT_PAGEABLE)
911 && (size & ~PAGE_MASK)) {
912 if ((kr = kmem_alloc_pageable_external(kernel_map, (vm_offset_t *)&addr, size)) != KERN_SUCCESS)
913 addr = NULL;
914 } else
915 addr = kalloc_tag_bt((vm_size_t)size, VM_KERN_MEMORY_KALLOC);
916
917 if (!addr)
918 OSMalloc_Tagrele(tag);
919
920 return(addr);
921 }
922
923 void *
924 OSMalloc_nowait(
925 uint32_t size,
926 OSMallocTag tag)
927 {
928 void *addr=NULL;
929
930 if (tag->OSMT_attr & OSMT_PAGEABLE)
931 return(NULL);
932
933 OSMalloc_Tagref(tag);
934 /* XXX: use non-blocking kalloc for now */
935 addr = kalloc_noblock_tag_bt((vm_size_t)size, VM_KERN_MEMORY_KALLOC);
936 if (addr == NULL)
937 OSMalloc_Tagrele(tag);
938
939 return(addr);
940 }
941
942 void *
943 OSMalloc_noblock(
944 uint32_t size,
945 OSMallocTag tag)
946 {
947 void *addr=NULL;
948
949 if (tag->OSMT_attr & OSMT_PAGEABLE)
950 return(NULL);
951
952 OSMalloc_Tagref(tag);
953 addr = kalloc_noblock_tag_bt((vm_size_t)size, VM_KERN_MEMORY_KALLOC);
954 if (addr == NULL)
955 OSMalloc_Tagrele(tag);
956
957 return(addr);
958 }
959
960 void
961 OSFree(
962 void *addr,
963 uint32_t size,
964 OSMallocTag tag)
965 {
966 if ((tag->OSMT_attr & OSMT_PAGEABLE)
967 && (size & ~PAGE_MASK)) {
968 kmem_free(kernel_map, (vm_offset_t)addr, size);
969 } else
970 kfree((void *)addr, size);
971
972 OSMalloc_Tagrele(tag);
973 }
974
975 uint32_t
976 OSMalloc_size(
977 void *addr)
978 {
979 return (uint32_t)kalloc_size(addr);
980 }
981