Loading...
--- libmalloc/libmalloc-792.80.2/src/xzone_malloc/xzone_segment.c
+++ /dev/null
@@ -1,3270 +0,0 @@
-/* ----------------------------------------------------------------------------
-Copyright (c) 2018-2022, Microsoft Research, Daan Leijen
-Copyright © 2025 Apple Inc.
-This is free software; you can redistribute it and/or modify it under the
-terms of the MIT license. A copy of the license can be found in the file
-"LICENSE" in the same directory as this file.
------------------------------------------------------------------------------*/
-
-#include "../internal.h"
-
-#if CONFIG_XZONE_MALLOC
-
-static void
-xzm_madvise(xzm_malloc_zone_t zone, uint8_t *start, size_t size);
-
-static void
-_xzm_segment_group_segment_deallocate(xzm_segment_group_t sg,
- xzm_segment_t segment, bool free_from_table);
-
-#pragma mark segment map
-
-// mimalloc: _mi_segment_map_allocated_at
-static void
-_xzm_segment_table_allocated_at(xzm_main_malloc_zone_t main, void *data,
- xzm_segment_t metadata, bool normal)
-{
- xzm_debug_assert((uintptr_t)data % XZM_SEGMENT_SIZE == 0);
-
- void *segment_end = _xzm_segment_end(metadata);
- xzm_debug_assert((uintptr_t)data < (uintptr_t)segment_end);
-
- xzm_segment_table_entry_s entry_val =
- _xzm_segment_to_segment_table_entry(metadata, normal);
-
- while (data < segment_end) {
-#if CONFIG_EXTERNAL_METADATA_LARGE
- // If this allocation is in a new 64GB granule, allocate a new leaf
- // table to store the metadata pointers in
- size_t ext_idx = 0;
- __assert_only size_t index = _xzm_segment_table_index_of(data, &ext_idx);
- xzm_debug_assert(index < XZM_SEGMENT_TABLE_ENTRIES);
- xzm_debug_assert(ext_idx < XZM_EXTENDED_SEGMENT_TABLE_ENTRIES);
-
- if (ext_idx != 0) {
- xzm_extended_segment_table_entry_s *ext_addr =
- &main->xzmz_extended_segment_table[ext_idx];
- xzm_extended_segment_table_entry_s ext_entry = { 0 };
- ext_entry = os_atomic_load(ext_addr, relaxed);
- if (ext_entry.xeste_val == 0) {
- // Need to allocate a new segment table since this pointer is in
- // a new segment table (64GB span)
- _malloc_lock_lock(&main->xzmz_extended_segment_table_lock);
- // Load the table entry again to see if another thread populated
- // it while we were acquiring the lock
- ext_entry = os_atomic_load(ext_addr, relaxed);
- if (ext_entry.xeste_val == 0) {
- xzm_metapool_t mp;
- mp = &main->xzmz_metapools[XZM_METAPOOL_SEGMENT_TABLE];
- void *leaf_table = xzm_metapool_alloc(mp);
- xzm_assert(leaf_table);
- xzm_debug_assert(((uintptr_t)leaf_table /
- XZM_SEGMENT_TABLE_ALIGN) <= UINT32_MAX);
- ext_entry.xeste_val = (uint32_t)((uintptr_t)leaf_table /
- XZM_SEGMENT_TABLE_ALIGN);
- os_atomic_store(ext_addr, ext_entry, relaxed);
- }
- _malloc_lock_unlock(&main->xzmz_extended_segment_table_lock);
- }
- }
-#endif // CONFIG_EXTERNAL_METADATA_LARGE
-
- xzm_segment_table_entry_s *entry;
- entry = _xzm_ptr_to_table_entry(data, main);
- xzm_debug_assert(entry != NULL);
-
- xzm_debug_assert(entry->xste_val == 0);
-
- // Store-release to publish the segment and chunk initializations
- // TODO: document all paired dependency/acquire loads
- os_atomic_store(entry, entry_val, release);
-
- data = (void *)((uintptr_t)data + XZM_SEGMENT_SIZE);
- }
-}
-
-// mimalloc: _mi_segment_map_freed_at
-static void
-_xzm_segment_table_freed_at(xzm_main_malloc_zone_t main, void *data,
- xzm_segment_t metadata, __assert_only bool full_segment)
-{
- void *end = _xzm_segment_end(metadata);
- xzm_debug_assert(!full_segment ||
- _xzm_segment_start(metadata) == data);
- while (data < end) {
- xzm_segment_table_entry_s *entry;
- entry = _xzm_ptr_to_table_entry(data, main);
- xzm_debug_assert(entry != NULL);
- xzm_debug_assert(_xzm_segment_to_segment_table_entry(metadata, false).xste_val ==
- entry->xste_val);
- xzm_segment_table_entry_s null_entry;
- null_entry = _xzm_segment_to_segment_table_entry(NULL, false);
- os_atomic_store(entry, null_entry, relaxed);
-
- data = (void *)((uintptr_t)data + XZM_SEGMENT_SIZE);
- }
-}
-
-#pragma mark vm reclaim
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
-
-static struct xzm_reclaim_buffer_s xzm_reclaim_buffer;
-
-static bool
-_xzm_reclaim_id_cache_is_empty(xzm_reclaim_id_cache_t cache)
-{
- return cache->ric_head == 0;
-}
-
-static uint64_t
-_xzm_reclaim_id_cache_pop(xzm_reclaim_id_cache_t cache)
-{
- xzm_debug_assert(!_xzm_reclaim_id_cache_is_empty(cache));
- uint64_t id = cache->ric_ids[--cache->ric_head];
- xzm_debug_assert(id != VM_RECLAIM_ID_NULL);
- return id;
-}
-
-static void
-_xzm_reclaim_id_cache_push(xzm_reclaim_id_cache_t cache, mach_vm_reclaim_id_t id)
-{
- xzm_assert(cache->ric_head < cache->ric_len);
- xzm_debug_assert(id != VM_RECLAIM_ID_NULL);
- cache->ric_ids[cache->ric_head++] = id;
-}
-
-static void
-_xzm_reclaim_id_cache_init(xzm_reclaim_buffer_t buffer)
-{
- xzm_reclaim_id_cache_t id_cache = &buffer->xrb_id_cache;
- mach_vm_reclaim_count_t max_buffer_count;
- mach_vm_reclaim_error_t kr = mach_vm_reclaim_ring_capacity(
- buffer->xrb_ringbuffer, &max_buffer_count);
- xzm_assert(kr == VM_RECLAIM_SUCCESS);
- size_t min_id_cache_size =
- max_buffer_count * sizeof(mach_vm_reclaim_id_t);
- size_t id_cache_size = round_page(min_id_cache_size);
- if (id_cache->ric_ids == NULL ||
- id_cache->ric_len < max_buffer_count) {
- mach_vm_reclaim_id_t *ids = (mach_vm_reclaim_id_t *)
- mvm_allocate_pages(id_cache_size, 0, MALLOC_ABORT_ON_ERROR,
- VM_MEMORY_MALLOC);
- if (id_cache->ric_ids != NULL) {
- // Deallocate the old cache
- mvm_deallocate_pages((void *)(id_cache->ric_ids),
- id_cache->ric_len * sizeof(mach_vm_reclaim_id_t),
- MALLOC_ABORT_ON_ERROR);
- }
- id_cache->ric_ids = ids;
- id_cache->ric_len = id_cache_size / sizeof(mach_vm_reclaim_id_t);
- }
- id_cache->ric_head = 0;
- xzm_debug_assert(id_cache->ric_len >= max_buffer_count);
-}
-
-bool
-xzm_reclaim_init(xzm_main_malloc_zone_t main,
- mach_vm_reclaim_count_t initial_count, mach_vm_reclaim_count_t max_count)
-{
- // Pick a sane minimum number of entries and let vm_reclaim round up
- // to a page boundary. The intention is for the initial size to be
- // one page.
- mach_vm_reclaim_count_t buffer_capacity =
- mach_vm_reclaim_round_capacity(initial_count);
- mach_vm_reclaim_count_t max_buffer_capacity =
- mach_vm_reclaim_round_capacity(max_count);
- xzm_reclaim_buffer.xrb_id_cache.ric_len = 0;
- xzm_reclaim_buffer.xrb_id_cache.ric_ids = NULL;
- _malloc_lock_init(&xzm_reclaim_buffer.xrb_lock);
- mach_vm_reclaim_error_t err = mach_vm_reclaim_ring_allocate(
- &xzm_reclaim_buffer.xrb_ringbuffer, buffer_capacity,
- max_buffer_capacity);
- if (err == VM_RECLAIM_SUCCESS) {
- xzm_reclaim_buffer.xrb_len = buffer_capacity;
- main->xzmz_reclaim_buffer = &xzm_reclaim_buffer;
- _xzm_reclaim_id_cache_init(&xzm_reclaim_buffer);
- } else {
- malloc_report(ASL_LEVEL_ERR,
- "xzm: failed to initialize deferred "
- "reclamation buffer [%d] %s\n",
- err_get_code(err), mach_error_string(err));
- }
- return (err == VM_RECLAIM_SUCCESS);
-}
-
-static mach_vm_reclaim_state_t
-_xzm_reclaim_mark_used_locked(xzm_reclaim_buffer_t buffer,
- mach_vm_reclaim_id_t id, uint8_t *addr, size_t size, bool reusable,
- bool *update_accounting_out)
-{
- mach_vm_reclaim_error_t err;
- mach_vm_reclaim_state_t state;
-
- xzm_debug_assert(size <= UINT32_MAX);
- mach_vm_reclaim_action_t behavior = reusable ?
- VM_RECLAIM_FREE : VM_RECLAIM_DEALLOCATE;
-
- err = mach_vm_reclaim_try_cancel(buffer->xrb_ringbuffer, id,
- (mach_vm_address_t)addr, (mach_vm_size_t)size,
- behavior, &state, update_accounting_out);
- xzm_assert(err == VM_RECLAIM_SUCCESS);
-
- if (state == VM_RECLAIM_UNRECLAIMED) {
- _xzm_reclaim_id_cache_push(&buffer->xrb_id_cache, id);
- }
-
- return state;
-}
-
-static mach_vm_reclaim_state_t
-_xzm_reclaim_mark_used(xzm_reclaim_buffer_t buffer, mach_vm_reclaim_id_t id,
- uint8_t *addr, size_t size, bool reusable)
-{
- bool update_accounting = false;
-
- _malloc_lock_lock(&buffer->xrb_lock);
-
- mach_vm_reclaim_state_t state = _xzm_reclaim_mark_used_locked(buffer, id,
- addr, size, reusable, &update_accounting);
-
- _malloc_lock_unlock(&buffer->xrb_lock);
-
- if (update_accounting) {
- __assert_only mach_vm_reclaim_error_t err =
- mach_vm_reclaim_update_kernel_accounting(buffer->xrb_ringbuffer);
- xzm_debug_assert(err == VM_RECLAIM_SUCCESS);
- }
-
- return state;
-}
-
-static bool
-_xzm_reclaim_is_reusable(xzm_reclaim_buffer_t buffer, mach_vm_reclaim_id_t reclaim_id, bool deallocate)
-{
- mach_vm_reclaim_error_t err;
- mach_vm_reclaim_state_t state;
- err = mach_vm_reclaim_query_state(buffer->xrb_ringbuffer, reclaim_id,
- deallocate ? VM_RECLAIM_DEALLOCATE : VM_RECLAIM_FREE, &state);
- xzm_assert(err == VM_RECLAIM_SUCCESS);
- return mach_vm_reclaim_is_reusable(state);
-}
-
-uint64_t
-xzm_reclaim_mark_free_locked(xzm_reclaim_buffer_t buffer, uint8_t *addr,
- size_t size, bool reusable, bool *update_accounting_out)
-{
- mach_vm_reclaim_error_t kr;
- mach_vm_reclaim_id_t id;
- mach_vm_address_t vm_addr = (mach_vm_address_t)addr;
- uint32_t vm_size = (uint32_t)size;
- xzm_debug_assert(size <= UINT32_MAX);
- xzm_debug_assert(vm_addr % XZM_SEGMENT_SLICE_SIZE == 0);
- xzm_debug_assert(vm_size % XZM_SEGMENT_SLICE_SIZE == 0);
-#ifdef DEBUG
- _malloc_lock_assert_owner(&buffer->xrb_lock);
-#endif // DEBUG
-
- mach_vm_reclaim_action_t behavior = reusable ?
- VM_RECLAIM_FREE : VM_RECLAIM_DEALLOCATE;
-
- while (!_xzm_reclaim_id_cache_is_empty(&buffer->xrb_id_cache)) {
- id = _xzm_reclaim_id_cache_pop(&buffer->xrb_id_cache);
- kr = mach_vm_reclaim_try_enter(
- buffer->xrb_ringbuffer,
- vm_addr, vm_size, behavior, &id,
- update_accounting_out);
- xzm_assert(kr == VM_RECLAIM_SUCCESS);
- if (id != VM_RECLAIM_ID_NULL) {
- goto done;
- }
- }
- do {
- id = VM_RECLAIM_ID_NULL;
- kr = mach_vm_reclaim_try_enter(buffer->xrb_ringbuffer, vm_addr, vm_size,
- behavior, &id, update_accounting_out);
- xzm_assert(kr == VM_RECLAIM_SUCCESS);
- if (id == VM_RECLAIM_ID_NULL) {
- // If the ringbuffer is full, reap all of its contents and resize
- xzm_reclaim_sync_and_resize(buffer);
- }
- } while (id == VM_RECLAIM_ID_NULL);
-
-done:
- return id;
-}
-
-static uint64_t
-_xzm_reclaim_mark_free(xzm_reclaim_buffer_t buffer, uint8_t *addr, size_t size,
- bool reusable)
-{
- uint64_t id;
- bool should_update_kernel_accounting = false;
-
- _malloc_lock_lock(&buffer->xrb_lock);
-
- id = xzm_reclaim_mark_free_locked(buffer, addr, size, reusable,
- &should_update_kernel_accounting);
-
- _malloc_lock_unlock(&buffer->xrb_lock);
-
- if (should_update_kernel_accounting) {
- __assert_only mach_vm_reclaim_error_t kr =
- mach_vm_reclaim_update_kernel_accounting(buffer->xrb_ringbuffer);
- xzm_debug_assert(kr == VM_RECLAIM_SUCCESS);
- }
- return id;
-}
-
-static bool
-xzm_reclaim_mark_smaller(xzm_reclaim_buffer_t buffer, uint64_t *front_id,
- uint64_t *back_id, uint8_t *front_start, size_t front_free_size,
- size_t used_size, size_t back_free_size, bool deferred, bool pristine,
- bool reusable)
-{
- const size_t span_size = front_free_size + used_size + back_free_size;
- xzm_debug_assert(span_size <= UINT32_MAX);
-
- bool should_update_used = false;
- bool should_update_free_front = false, should_update_free_back = false;
-
- _malloc_lock_lock(&buffer->xrb_lock);
-
- bool usable = true;
- mach_vm_reclaim_state_t state;
- if (deferred) {
- xzm_debug_assert(*front_id != VM_RECLAIM_ID_NULL);
- // Mark the entire span as used
- state = _xzm_reclaim_mark_used_locked(buffer, *front_id, front_start,
- span_size, reusable, &should_update_used);
- usable = mach_vm_reclaim_is_reusable(state);
- if (usable) {
- *front_id = VM_RECLAIM_ID_NULL;
- }
- }
- if (usable) {
- if (front_free_size && !pristine) {
- // Mark the front as free. Note that it already has a reclaim id
- xzm_debug_assert(*front_id == VM_RECLAIM_ID_NULL);
- *front_id = xzm_reclaim_mark_free_locked(buffer, front_start,
- front_free_size, reusable, &should_update_free_front);
- }
-
- if (back_free_size) {
- xzm_debug_assert(back_id);
- if (!pristine) {
- // Mark the back as free
- uint8_t *back_start = front_start + front_free_size + used_size;
- *back_id = xzm_reclaim_mark_free_locked(buffer, back_start,
- back_free_size, reusable, &should_update_free_back);
- } else {
- // Initialize the reclaim id now, because when the span metadata
- // is updated, it cannot overwrite any reclaim id we set
- *back_id = VM_RECLAIM_ID_NULL;
- }
- }
- }
-
- _malloc_lock_unlock(&buffer->xrb_lock);
-
- if (should_update_used || should_update_free_front ||
- should_update_free_back) {
- mach_vm_reclaim_update_kernel_accounting(buffer->xrb_ringbuffer);
- }
-
- return usable;
-}
-
-void
-xzm_reclaim_force_sync(xzm_reclaim_buffer_t buffer)
-{
- // This function is called in a loop when reclaim_mark_used fails while
- // trying to free a span in the reclaim buffer.
- mach_vm_reclaim_count_t capacity;
- __assert_only mach_vm_reclaim_error_t err;
- err = mach_vm_reclaim_ring_capacity(buffer->xrb_ringbuffer, &capacity);
- xzm_assert(err == VM_RECLAIM_SUCCESS);
- err = mach_vm_reclaim_ring_flush(buffer->xrb_ringbuffer, capacity);
- xzm_assert(err == VM_RECLAIM_SUCCESS);
-}
-
-void
-xzm_reclaim_sync_and_resize(xzm_reclaim_buffer_t buffer)
-{
- mach_vm_reclaim_error_t kr;
- mach_vm_reclaim_count_t count;
- kr = mach_vm_reclaim_ring_capacity(buffer->xrb_ringbuffer, &count);
- xzm_assert(kr == VM_RECLAIM_SUCCESS);
- mach_vm_reclaim_count_t new_count =
- mach_vm_reclaim_round_capacity(2 * count);
-
- kr = mach_vm_reclaim_ring_resize(buffer->xrb_ringbuffer, new_count);
- if (kr == VM_RECLAIM_SUCCESS) {
- _xzm_reclaim_id_cache_init(buffer);
- } else {
- // Must explicitly flush if the resize operation failed
- xzm_reclaim_force_sync(buffer);
- }
-}
-
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
-#pragma mark range group
-
-OS_OPTIONS(xzm_range_group_alloc_flags, uint32_t,
- XZM_RANGE_GROUP_ALLOC_FLAGS_HUGE = 1 << 0,
- XZM_RANGE_GROUP_ALLOC_FLAGS_PURGEABLE = 1 << 1,
-#if CONFIG_MTE
- XZM_RANGE_GROUP_ALLOC_FLAGS_MTE = 1 << 2,
-#endif
-);
-
-static int
-_xzm_range_group_vm_tag_for_segment(size_t size, bool huge)
-{
- // Note: although there is already a VM_MEMORY_MALLOC_HUGE tag, which has
- // been there since prehistory, we'll use LARGE for huge segments to ensure
- // that any special handling from the kernel or other tools works exactly as
- // before (e.g. VM_MEMORY_MALLOC_HUGE is not included in
- // vm_memory_malloc_no_cow_mask)
- //
- // We use VM_MEMORY_MALLOC_SMALL for normal segment allocations so that they
- // are easily distinguisable from metadata allocations purely by tag.
- return huge ? VM_MEMORY_MALLOC_LARGE : VM_MEMORY_MALLOC_SMALL;
-}
-
-static void * __alloc_size(2)
-_xzm_range_group_alloc_mvm_segment(xzm_main_malloc_zone_t main, size_t size,
- size_t align, plat_map_t *map, xzm_range_group_alloc_flags_t rga_flags)
-{
- bool huge = (rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_HUGE);
- bool purgeable = (rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_PURGEABLE);
-
- uint32_t flags = 0;
- if (os_unlikely(purgeable)) {
- flags |= MALLOC_PURGEABLE;
- }
-
-#if XZM_NARROW_BUCKETING
- // If we're doing narrow bucketing, and we ourselves aren't enabling
- // VM user ranges, but we've detected that VM user ranges are active in the
- // address space (<-> entropic_base is set), we want to pass DISABLE_ASLR to
- // skip the mvm-layer ASLR, which would cause our allocations to be placed
- // at the opposite end of the heap range from other pure data allocations
- // and use an additional PTE
- if (main->xzmz_narrow_bucketing && !main->xzmz_use_ranges && entropic_base) {
- flags |= DISABLE_ASLR;
- }
-#endif
-
-#if CONFIG_MTE
- if (rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_MTE) {
- flags |= MALLOC_MTE_TAGGABLE;
- }
-#endif
-
- int tag = _xzm_range_group_vm_tag_for_segment(size, huge);
- if (os_likely(align == 0)) {
- return mvm_allocate_pages_plat(size, XZM_SEGMENT_SHIFT, flags, tag, map);
- } else {
- // mvm_allocate_pages_plat takes the log2 of the alignment
- size_t align_pow = __builtin_ctzl(align);
- xzm_debug_assert(align_pow < UINT8_MAX);
- align_pow = MAX(align_pow, XZM_SEGMENT_SHIFT);
- return mvm_allocate_pages_plat(size, align_pow, flags, tag, map);
- }
-}
-
-MALLOC_USED
-static void * __alloc_size(1)
-_xzm_range_group_alloc_anywhere_segment(mach_vm_address_t hint, size_t size,
- size_t align, plat_map_t *map, xzm_range_group_alloc_flags_t rga_flags)
-{
- bool huge = (rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_HUGE);
- bool purgeable = (rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_PURGEABLE);
-
- (void)map;
- int tag = _xzm_range_group_vm_tag_for_segment(size, huge);
-
- mach_vm_address_t vm_addr = hint;
- mach_vm_size_t allocation_size = (mach_vm_size_t)size;
- int flags = VM_FLAGS_ANYWHERE | VM_MAKE_TAG(tag);
- if (os_unlikely(purgeable)) {
- flags |= VM_FLAGS_PURGABLE;
- }
-
-#if CONFIG_MTE
- if (rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_MTE) {
- flags |= VM_FLAGS_MTE;
- }
-#endif
-
- align = MAX(align, XZM_SEGMENT_SIZE);
- // alignment must be a power of 2 for the allocation mask to work
- xzm_debug_assert(powerof2(align));
- mach_vm_offset_t allocation_mask = (mach_vm_offset_t)align - 1;
- kern_return_t kr = mach_vm_map(mach_task_self(), &vm_addr, allocation_size,
- allocation_mask, flags, MEMORY_OBJECT_NULL, 0, FALSE,
- VM_PROT_DEFAULT, VM_PROT_ALL, VM_INHERIT_DEFAULT);
- if (kr) {
- if (kr != KERN_NO_SPACE) {
- xzm_debug_abort_with_reason("Failed to allocate data segment", kr);
- malloc_zone_error(0, false,
- "Failed to allocate segment (size=%lu, flags=%x, kr=%d)\n",
- (unsigned long)size, flags, kr);
- }
-
- return NULL;
- }
-
- xzm_debug_assert(vm_addr);
- xzm_debug_assert(vm_addr % align == 0);
- return (void *)vm_addr;
-}
-
-static uintptr_t
-_xzm_range_group_bump_alloc_segment(xzm_range_group_t rg, size_t size,
- bool warn_on_exhaustion)
-{
- uintptr_t segment_addr = 0;
-
- if (rg->xzrg_warned_full) {
- return segment_addr;
- }
-
- // Reserve space for a new segment
- _malloc_lock_lock(&rg->xzrg_lock);
- if (rg->xzrg_remaining >= size) {
- if (rg->xzrg_next == rg->xzrg_skip_addr) {
- if (rg->xzrg_direction == XZM_FRONT_INCREASING) {
- rg->xzrg_next += rg->xzrg_skip_size;
- } else {
- xzm_debug_assert(rg->xzrg_direction == XZM_FRONT_DECREASING);
- rg->xzrg_next -= rg->xzrg_skip_size;
- }
- }
-
- // In the decreasing direction, xzrg_next points to the _end_ of what
- // will be the next segment we serve, and we subtract the size to be
- // allocated from its initial value. In the increasing direction, the
- // initial value is the start of the segment we're going to serve, and
- // we increase afterward.
- if (rg->xzrg_direction == XZM_FRONT_DECREASING) {
- rg->xzrg_next -= size;
- }
-
- segment_addr = rg->xzrg_next;
- xzm_debug_assert(segment_addr % size == 0);
-
- if (rg->xzrg_direction == XZM_FRONT_INCREASING) {
- rg->xzrg_next += size;
- }
-
- rg->xzrg_remaining -= size;
- }
-
- if (!segment_addr && warn_on_exhaustion) {
- if (!rg->xzrg_warned_full) {
- rg->xzrg_warned_full = true;
- malloc_report(ASL_LEVEL_WARNING, "Failed to allocate segment from range group - out of space\n");
- }
- }
-
- _malloc_lock_unlock(&rg->xzrg_lock);
-
- return segment_addr;
-}
-
-static void * __alloc_size(2)
-_xzm_range_group_alloc_data_segment(xzm_range_group_t rg, size_t size,
- size_t alignment, plat_map_t *map, xzm_range_group_alloc_flags_t rga_flags)
-{
- xzm_debug_assert(rg->xzrg_id == XZM_RANGE_GROUP_DATA);
-
-#if CONFIG_VM_USER_RANGES || CONFIG_MACOS_RANGES
- if (rg->xzrg_main_ref->xzmz_use_ranges) {
- // On systems with VM user ranges, an ANYWHERE allocation with one of the
- // VM_MEMORY_MALLOC tags will be placed in the data range automatically.
- mach_vm_address_t hint = 0;
-
-#if CONFIG_MACOS_RANGES
- // On macOS, the data range isn't strongly isolated. We just choose an
- // otherwise empty normal range of the address space to allocate into
- // using a hint.
- hint = rg->xzrg_base;
-#endif // CONFIG_MACOS_RANGES
-
- return _xzm_range_group_alloc_anywhere_segment(hint, size, alignment,
- map, rga_flags);
- }
-#endif // CONFIG_VM_USER_RANGES || CONFIG_MACOS_RANGES
-
- return _xzm_range_group_alloc_mvm_segment(rg->xzrg_main_ref, size,
- alignment, map, rga_flags);
-}
-
-static void * __alloc_size(2)
-_xzm_range_group_alloc_ptr_segment(xzm_range_group_t rg, size_t size,
- plat_map_t *map, xzm_range_group_alloc_flags_t rga_flags)
-{
- xzm_debug_assert(rg->xzrg_id == XZM_RANGE_GROUP_PTR);
- xzm_debug_assert(!(rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_HUGE));
- xzm_debug_assert(size == XZM_SEGMENT_SIZE);
- xzm_debug_assert(rg->xzrg_main_ref->xzmz_segment_group_count !=
- XZM_SEGMENT_GROUP_IDS_COUNT_DATA_ONLY);
-
-#if CONFIG_VM_USER_RANGES || CONFIG_MACOS_RANGES
- if (rg->xzrg_main_ref->xzmz_use_ranges)
-#else
- if ((0))
-#endif // MALLOC_TARGET_EXCLAVES
- {
- bool allow_fallback = false;
-#if CONFIG_MALLOC_PROCESS_IDENTITY && CONFIG_MACOS_RANGES
- if (!malloc_process_is_security_critical(malloc_process_identity)) {
- allow_fallback = true;
- }
-#endif // CONFIG_MALLOC_PROCESS_IDENTITY && CONFIG_MACOS_RANGES
-
- mach_vm_address_t segment_addr = _xzm_range_group_bump_alloc_segment(rg,
- size, !allow_fallback);
- if (!segment_addr) {
-#if CONFIG_MALLOC_PROCESS_IDENTITY && CONFIG_MACOS_RANGES
- if (allow_fallback) {
- goto fallback;
- }
-#endif // CONFIG_MALLOC_PROCESS_IDENTITY && CONFIG_MACOS_RANGES
-
- xzm_debug_abort("Pointer range exhausted");
- return NULL;
- }
-
-#if CONFIG_VM_USER_RANGES || CONFIG_MACOS_RANGES
- mach_vm_address_t vm_addr = segment_addr;
- mach_vm_size_t vm_size = (mach_vm_size_t)size;
- int alloc_flags = VM_FLAGS_OVERWRITE |
- VM_MAKE_TAG(VM_MEMORY_MALLOC_SMALL);
-
-#if CONFIG_MTE
- if (rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_MTE) {
- alloc_flags |= VM_FLAGS_MTE;
- }
-#endif
-
- kern_return_t kr = mach_vm_map(mach_task_self(), &vm_addr, vm_size,
- /* mask */ 0, alloc_flags, MEMORY_OBJECT_NULL,
- /* offset */ 0, /* copy */ FALSE, VM_PROT_DEFAULT,
- VM_PROT_ALL, VM_INHERIT_DEFAULT);
- if (kr != KERN_SUCCESS) {
- xzm_abort_with_reason(
- "pointer range mach_vm_map() overwrite failed", kr);
- }
-#endif // CONFIG_VM_USER_RANGES || CONFIG_MACOS_RANGES
-
- return (void *)segment_addr;
- }
-
-#if CONFIG_MALLOC_PROCESS_IDENTITY && CONFIG_MACOS_RANGES
-fallback:
-#endif // CONFIG_MALLOC_PROCESS_IDENTITY && CONFIG_MACOS_RANGES
- return _xzm_range_group_alloc_mvm_segment(rg->xzrg_main_ref, size, 0, map,
- rga_flags);
-}
-
-static void * __alloc_size(2)
-xzm_range_group_alloc_segment(xzm_range_group_t rg, size_t size,
- size_t alignment, plat_map_t *map,
- xzm_range_group_alloc_flags_t rga_flags)
-{
- if (rg->xzrg_id == XZM_RANGE_GROUP_DATA) {
- return _xzm_range_group_alloc_data_segment(rg, size, alignment, map,
- rga_flags);
- } else {
- xzm_debug_assert(alignment == 0);
- // Only huge segment bodies (which must be in the data range) can be
- // purgable
- xzm_debug_assert(!(rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_PURGEABLE));
- return _xzm_range_group_alloc_ptr_segment(rg, size, map, rga_flags);
- }
-}
-
-static void
-xzm_range_group_free_segment_body(xzm_range_group_t rg, void *body,
- size_t size, plat_map_t *map)
-{
- xzm_debug_assert(rg->xzrg_id == XZM_RANGE_GROUP_DATA);
-
- int debug_flags = 0;
-#ifdef DEBUG
- debug_flags = MALLOC_ABORT_ON_ERROR;
-#endif // DEBUG
- mvm_deallocate_plat(body, size, debug_flags, map);
-}
-
-#if CONFIG_VM_USER_RANGES
-static bool
-parse_void_ranges(struct mach_vm_range *left_void,
- struct mach_vm_range *right_void)
-{
- char buf[256];
- size_t bsz = sizeof(buf) - 1;
- char *s;
-
- int rc = sysctlbyname("vm.malloc_ranges", buf, &bsz, NULL, 0);
- if (rc == -1) {
- switch (errno) {
- case ENOENT:
-#ifdef DEBUG
- malloc_report(ASL_LEVEL_INFO, "VM user ranges not supported\n");
-#endif
- break;
- case EPERM:
- // TODO: make this fatal in processes that strictly need VM user
- // ranges
- malloc_report(ASL_LEVEL_ERR,
- "sysctlbyname(\"vm.malloc_ranges\") denied\n");
- break;
- default:
- xzm_abort_with_reason("sysctlbyname(\"vm.malloc_ranges\") failed",
- errno);
- break;
- }
- return false;
- }
- buf[bsz] = '\0';
-
- s = buf;
-
- left_void->min_address = strtoull(s, &s, 16);
- s++;
-
- left_void->max_address = strtoull(s, &s, 16);
- s++;
-
- right_void->min_address = strtoull(s, &s, 16);
- s++;
-
- right_void->max_address = strtoull(s, &s, 16);
-
- return true;
-}
-#endif // CONFIG_VM_USER_RANGES
-
-#if MALLOC_TARGET_EXCLAVES || CONFIG_VM_USER_RANGES || CONFIG_MACOS_RANGES
-
-#define XZM_RANGE_SEPARATION GiB(4)
-
-#define XZM_DATA_RANGE_SIZE GiB(10)
-#define XZM_POINTER_RANGE_SIZE GiB(16)
-
-#define XZM_PAGE_TABLE_GRANULE MiB(32)
-#define XZM_PAGE_TABLE_BITS 25
-
-// Exclaves don't have struct mach_vm_range, so we'll just define our own little
-// identical type
-struct xzm_vm_range {
- uint64_t min_address;
- uint64_t max_address;
-};
-
-
-static_assert(sizeof(struct mach_vm_range) == sizeof(struct xzm_vm_range),
- "compatible vm range size");
-static_assert(offsetof(struct mach_vm_range, min_address) ==
- offsetof(struct xzm_vm_range, min_address),
- "compatible vm range min_address offset");
-static_assert(offsetof(struct mach_vm_range, max_address) ==
- offsetof(struct xzm_vm_range, max_address),
- "compatible vm range max_address offset");
-
-
-static void
-_xzm_main_malloc_zone_init_ptr_fronts(xzm_range_group_t range_groups,
- size_t allocation_front_count, struct xzm_vm_range *ranges,
- size_t range_count, plat_map_t *map)
-{
- xzm_assert(allocation_front_count == 2);
- xzm_assert(range_count > 0);
- xzm_assert(ranges[0].min_address < ranges[0].max_address);
- if (range_count > 1) {
-#if CONFIG_VM_USER_RANGES
- xzm_assert(range_count == 2);
- xzm_assert(ranges[1].min_address > ranges[0].max_address);
- xzm_assert(ranges[1].min_address < ranges[1].max_address);
-#else
- xzm_abort_with_reason("unsupported range_count", range_count);
-#endif
- }
-
- uint64_t total_span = 0;
- for (size_t i = 0; i < range_count; i++) {
- total_span += ranges[i].max_address - ranges[i].min_address;
- }
- uint64_t middle_pte_offset = roundup(total_span / 2,
- XZM_PAGE_TABLE_GRANULE);
-
- if (ranges[0].min_address + middle_pte_offset >= ranges[0].max_address) {
- xzm_assert(range_count == 2);
- middle_pte_offset += ranges[1].min_address - ranges[0].max_address;
- }
-
- uint64_t middle_pte = ranges[0].min_address + middle_pte_offset;
- xzm_assert(middle_pte % XZM_PAGE_TABLE_GRANULE == 0);
-
- uint64_t middle_pte_middle = middle_pte + (XZM_PAGE_TABLE_GRANULE / 2);
-
- uint64_t rg_up_size = 0;
- uint64_t rg_up_skip_addr = 0;
- uint64_t rg_up_skip_size = 0;
-
- uint64_t rg_down_size = 0;
- uint64_t rg_down_skip_addr = 0;
- uint64_t rg_down_skip_size = 0;
-
- if (range_count == 2) {
- if (middle_pte_middle > ranges[0].max_address) {
- xzm_assert(middle_pte_middle > ranges[1].min_address);
- xzm_assert(middle_pte_middle < ranges[1].max_address);
-
- // The right side (up) is not split
- rg_up_size = ranges[1].max_address - middle_pte_middle;
-
- // The left side (down) is split
- rg_down_size = (middle_pte_middle - ranges[1].min_address) +
- (ranges[0].max_address - ranges[0].min_address);
- rg_down_skip_addr = ranges[1].min_address;
- rg_down_skip_size = ranges[1].min_address - ranges[0].max_address;
- } else {
- xzm_assert(middle_pte_middle < ranges[0].max_address);
- xzm_assert(middle_pte_middle > ranges[0].min_address);
-
- // The right side (up) is split
- rg_up_size = (ranges[1].max_address - ranges[1].min_address) +
- (ranges[0].max_address - middle_pte_middle);
- rg_up_skip_addr = ranges[0].max_address;
- rg_up_skip_size = ranges[1].min_address - ranges[0].max_address;
-
- // The left side (down) is not split
- rg_down_size = middle_pte_middle - ranges[0].min_address;
- }
- } else {
- xzm_assert(ranges[0].min_address < middle_pte_middle);
- xzm_assert(middle_pte_middle < ranges[0].max_address);
-
- rg_up_size = ranges[0].max_address - middle_pte_middle;
- rg_down_size = middle_pte_middle - ranges[0].min_address;
- }
-
- xzm_range_group_t ptr_rg_up = &range_groups[XZM_RANGE_GROUP_PTR + 0];
- xzm_debug_assert(ptr_rg_up->xzrg_id == XZM_RANGE_GROUP_PTR);
-
- ptr_rg_up->xzrg_base = middle_pte_middle;
- ptr_rg_up->xzrg_next = ptr_rg_up->xzrg_base;
- ptr_rg_up->xzrg_size = rg_up_size;
- ptr_rg_up->xzrg_remaining = ptr_rg_up->xzrg_size;
- ptr_rg_up->xzrg_skip_addr = rg_up_skip_addr;
- ptr_rg_up->xzrg_skip_size = rg_up_skip_size;
- ptr_rg_up->xzrg_direction = XZM_FRONT_INCREASING;
-
- xzm_range_group_t ptr_rg_down = &range_groups[XZM_RANGE_GROUP_PTR + 1];
- xzm_debug_assert(ptr_rg_down->xzrg_id == XZM_RANGE_GROUP_PTR);
-
- ptr_rg_down->xzrg_base = middle_pte_middle;
- ptr_rg_down->xzrg_next = ptr_rg_down->xzrg_base;
- ptr_rg_down->xzrg_size = rg_down_size;
- ptr_rg_down->xzrg_remaining = ptr_rg_down->xzrg_size;
- ptr_rg_down->xzrg_skip_addr = rg_down_skip_addr;
- ptr_rg_down->xzrg_skip_size = rg_down_skip_size;
- ptr_rg_down->xzrg_direction = XZM_FRONT_DECREASING;
-
-}
-
-#if CONFIG_VM_USER_RANGES
-
-static void
-_xzm_main_malloc_zone_choose_ptr_ranges(struct mach_vm_range left_void,
- struct mach_vm_range right_void, size_t ptr_rg_size, uint64_t entropy,
- struct mach_vm_range *ranges_out, size_t *ranges_count_inout)
-{
- // For now, the caller needs to be able to handle 2 result ranges
- xzm_assert(*ranges_count_inout == 2);
-
- xzm_assert(left_void.min_address);
- xzm_assert(left_void.max_address >= left_void.min_address);
- xzm_assert(right_void.min_address >= left_void.max_address);
- xzm_assert(right_void.max_address >= right_void.min_address);
-
-#define xzm_trunc_page_table_granule(addr) \
- ((addr) & ~(XZM_PAGE_TABLE_GRANULE - 1))
-
- // Note: the void boundaries should already be aligned to the page table
- // granule anyway
-
- // |<----------------total span--------------->|
- // |<-left void->|<-data body->|<-right void->|
- // |<usable>|<pad>|<-data body->|<pad>|<usable>|
- // |<usable>|<-------data span------->|<usable>|
-
- uint64_t left_void_min = roundup(left_void.min_address,
- XZM_PAGE_TABLE_GRANULE);
- uint64_t left_void_limit =
- xzm_trunc_page_table_granule(left_void.max_address);
- if (left_void_limit < left_void_min) {
- // Shouldn't ever happen - the kernel would have to give us a
- // sub-granule left void that isn't granule-aligned. If it does, we can
- // pretend it gave us an empty left void that's actually "in" the data
- // range, technically.
- left_void_min = left_void_limit;
- }
- xzm_assert(left_void_min <= left_void_limit);
-
- uint64_t right_void_min = roundup(right_void.min_address,
- XZM_PAGE_TABLE_GRANULE);
- uint64_t right_void_limit =
- xzm_trunc_page_table_granule(right_void.max_address);
- if (right_void_limit < right_void_min) {
- // Same thing, shouldn't happen
- right_void_limit = right_void_min;
- }
- xzm_assert(right_void_min <= right_void_limit);
-
- xzm_assert(left_void_limit <= right_void_min);
-
- uint64_t total_span = right_void_limit - left_void_min;
-
- uint64_t data_body_span = right_void_min - left_void_limit;
-
- uint64_t data_left_pad = MIN(XZM_RANGE_SEPARATION,
- left_void_limit - left_void_min);
- uint64_t data_left_pad_start = left_void_limit - data_left_pad;
-
- uint64_t data_right_pad = MIN(XZM_RANGE_SEPARATION,
- right_void_limit - right_void_min);
- uint64_t data_right_pad_limit = right_void_min + data_right_pad;
-
- uint64_t data_span = data_left_pad + data_body_span + data_right_pad;
-
- xzm_assert(data_span < total_span);
- uint64_t usable_space = total_span - data_span;
-
- xzm_assert(usable_space >= ptr_rg_size);
- uint64_t starting_space = usable_space - ptr_rg_size;
-
- xzm_assert(starting_space % XZM_PAGE_TABLE_GRANULE == 0);
-
- // Note: + 1 because the final granule address is also usable
- uint64_t starting_candidate_granules =
- (starting_space / XZM_PAGE_TABLE_GRANULE) + 1;
-
- // Note: start_granules is small relative to entropy, so the modulo bias is
- // not significant
- uint64_t start_granule = entropy % starting_candidate_granules;
-
- uint64_t start_address = left_void_min +
- (start_granule * XZM_PAGE_TABLE_GRANULE);
-
- if (start_address >= data_left_pad_start) {
- start_address += data_span;
- }
-
- uint64_t limit_address = start_address + ptr_rg_size;
-
- if (start_address < data_left_pad_start &&
- limit_address > data_left_pad_start) {
- // The pointer range is split across the data range
- ranges_out[0] = (struct mach_vm_range){
- .min_address = start_address,
- .max_address = data_left_pad_start,
- };
-
- uint64_t left_range_span = data_left_pad_start - start_address;
- uint64_t right_range_span = ptr_rg_size - left_range_span;
- ranges_out[1] = (struct mach_vm_range){
- .min_address = data_right_pad_limit,
- .max_address = data_right_pad_limit + right_range_span,
- };
-
- *ranges_count_inout = 2;
- } else {
- // The pointer range is fully on one side of the data range
- ranges_out[0] = (struct mach_vm_range){
- .min_address = start_address,
- .max_address = limit_address,
- };
-
- *ranges_count_inout = 1;
- }
-}
-
-static kern_return_t
-_xzm_main_malloc_zone_create_ptr_range(struct mach_vm_range range)
-{
- // It's important that we use a malloc tag in the recipe so that the kernel
- // gives us a single object rather than chunking into many.
- mach_vm_range_recipe_v1_t recipe = {
- .range = range,
- .range_tag = MACH_VM_RANGE_FIXED,
- .vm_tag = VM_MEMORY_MALLOC_SMALL,
- };
-
- kern_return_t kr = mach_vm_range_create(mach_task_self(),
- MACH_VM_RANGE_FLAVOR_V1, (mach_vm_range_recipes_raw_t)&recipe,
- sizeof(recipe));
- switch (kr) {
- case KERN_SUCCESS:
- break;
- case KERN_DENIED:
- // TODO: make this fatal in processes that strictly need VM user ranges
- malloc_report(ASL_LEVEL_ERR, "mach_vm_range_create() denied\n");
- return kr;
- case KERN_NOT_SUPPORTED:
- // Strange - in a process that doesn't have VM user ranges we would have
- // expected the sysctl to fail
- xzm_debug_abort("mach_vm_range_create() not supported?");
- return kr;
- default:
- xzm_abort_with_reason("unexpected error from mach_vm_range_create()",
- kr);
- return kr;
- }
-
- // Avoid malloc-no-CoW semantics on the pointer range reservation by
- // replacing the VM object for it with one that has a non-malloc tag.
- // Giving it VM_PROT_NONE causes the kernel to give us a single object
- // rather than chunking (which is important to avoid creating tons of
- // pointless VM objects), and hides it in vmmap by default.
- mach_vm_address_t overwrite_addr = (mach_vm_address_t)range.min_address;
- mach_vm_size_t overwrite_size =
- (mach_vm_size_t)(range.max_address - range.min_address);
- int alloc_flags = VM_FLAGS_OVERWRITE;
- kr = mach_vm_map(mach_task_self(), &overwrite_addr, overwrite_size,
- /* mask */ 0, alloc_flags, MEMORY_OBJECT_NULL, /* offset */ 0,
- /* copy */ FALSE, VM_PROT_NONE, VM_PROT_NONE, VM_INHERIT_DEFAULT);
- if (kr != KERN_SUCCESS) {
- xzm_abort_with_reason(
- "pointer range initial overwrite failed", kr);
- }
-
- return KERN_SUCCESS;
-}
-
-#endif // CONFIG_VM_USER_RANGES
-
-#endif // MALLOC_TARGET_EXCLAVES || CONFIG_VM_USER_RANGES || CONFIG_MACOS_RANGES
-
-void
-xzm_main_malloc_zone_init_range_groups(xzm_main_malloc_zone_t main)
-{
- // Basic initialization is done in xzm_main_malloc_zone_create() - here we
- // mainly deal with VM user ranges.
- MALLOC_STATIC_ASSERT(XZM_RANGE_GROUP_COUNT == 3,
- "all range groups need to be initialized");
-
-#if CONFIG_VM_USER_RANGES
- struct mach_vm_range left_void, right_void;
- bool user_ranges_supported = parse_void_ranges(&left_void, &right_void);
- if (!user_ranges_supported) {
- return;
- }
-
- // VM user range support:
- //
- // We'll use the kernel default heap range for the DATA range.
- //
- // The ranges in the PTR range group:
- // - Should be separated from the data range (as defined by
- // [void1.max_address, void2.min_address)) by at least 4G
- // - Should allow each allocation front to span 8G, possibly crossing the
- // DATA range if necessary
-
- // The configurations we support are:
- // - No user ranges at all, in which case we shouldn't get here
- // - User ranges support with 2 allocation fronts
- if (main->xzmz_allocation_front_count != 2) {
- xzm_abort_with_reason("unsupported allocation front count",
- main->xzmz_allocation_front_count);
- }
-
- size_t ptr_rg_size = XZM_POINTER_RANGE_SIZE;
-
- struct mach_vm_range ptr_ranges[2];
- size_t ptr_range_count = 2;
- _xzm_main_malloc_zone_choose_ptr_ranges(left_void, right_void, ptr_rg_size,
- malloc_entropy[1], ptr_ranges, &ptr_range_count);
-
- for (size_t i = 0; i < ptr_range_count; i++) {
- kern_return_t kr =
- _xzm_main_malloc_zone_create_ptr_range(ptr_ranges[i]);
- if (kr != KERN_SUCCESS) {
- return;
- }
- }
-
- main->xzmz_use_ranges = true;
-
- _xzm_main_malloc_zone_init_ptr_fronts(main->xzmz_range_groups,
- main->xzmz_allocation_front_count,
- (struct xzm_vm_range *)ptr_ranges, ptr_range_count, NULL);
-
- xzm_range_group_t data_rg = &main->xzmz_range_groups[XZM_RANGE_GROUP_DATA];
- xzm_debug_assert(data_rg->xzrg_id == XZM_RANGE_GROUP_DATA);
-
- // Note: these are recorded purely for introspection purposes
- data_rg->xzrg_base = (mach_vm_address_t)left_void.max_address;
- data_rg->xzrg_size = right_void.min_address - left_void.max_address;
-
- // end of CONFIG_VM_USER_RANGES
-#elif CONFIG_MACOS_RANGES
- // We want a similar layout to embedded, with:
- // - A data range and a pointer range located in the first 64GB (L2) of the
- // address space to economize PTE usage
- // - Guaranteed minimum separation between the pointer range and everything
- // else
- // - Both ranges separated from the traditional "low space" by a few GB of
- // buffer distance
- //
- // However, on macOS there are no "voids" for us to need the
- // mach_vm_range_create() interface to access, nor is there a special data
- // range that the kernel knows about. Instead, we create our own strongly
- // isolated pointer range reservation, and have a more relaxed model for the
- // data range that permits reuse with general VA, allowing us to model it as
- // a simple starting address hint. An implication of the data range not
- // being strongly isolated is that it doesn't need to be contiguous.
- //
- // Either range should be able to grow to their standard size without
- // overflowing the first L2.
- //
- // So, our placement strategy will be:
- // - Place the pointer range, with its guards, in the space
- // - Then choose the data range hint somewhere in the remaining space
-
- // Start at 16GB to leave room in the low space for other VM allocations
-#define XZM_MACOS_RANGES_START GiB(16)
- // End at 63GB to avoid crossing the commpage
-#define XZM_MACOS_RANGES_END GiB(63)
-
- uint64_t range_first_candidate = XZM_MACOS_RANGES_START;
- uint64_t ptr_reservation_size = XZM_RANGE_SEPARATION +
- XZM_POINTER_RANGE_SIZE + XZM_RANGE_SEPARATION;
- uint64_t range_last_candidate = XZM_MACOS_RANGES_END - ptr_reservation_size;
-
- uint64_t ptr_candidate_span = range_last_candidate - range_first_candidate;
- uint64_t ptr_candidate_granules =
- ptr_candidate_span / XZM_PAGE_TABLE_GRANULE;
-
- uint64_t ptr_entropy = (uint32_t)(malloc_entropy[1]);
- uint64_t ptr_granule = ptr_entropy % ptr_candidate_granules;
-
- uint64_t ptr_start =
- range_first_candidate + (ptr_granule * XZM_PAGE_TABLE_GRANULE);
-
- xzm_assert(ptr_start + ptr_reservation_size <= XZM_MACOS_RANGES_END);
-
- // Reserve the pointer range with a big max-protection == PROT_NONE region.
- // It is important that we not give it a malloc tag or protection above
- // PROT_NONE to avoid chunking or special CoW treatment from the VM - we
- // need for this to be just one entry.
- mach_vm_address_t ptr_addr = (mach_vm_address_t)ptr_start;
- mach_vm_size_t reservation_size = (mach_vm_size_t)ptr_reservation_size;
- int alloc_flags = 0; // fixed, no tag
- kern_return_t kr = mach_vm_map(mach_task_self(), &ptr_addr,
- reservation_size, /* mask */ 0, alloc_flags, MEMORY_OBJECT_NULL,
- /* offset */ 0, /* copy */ FALSE, VM_PROT_NONE, VM_PROT_NONE,
- VM_INHERIT_DEFAULT);
- if (kr != KERN_SUCCESS) {
- // We could fall back to mvm allocation, but we want this to fail loudly
- // if something starts preventing us from being able to make the
- // reservation we need
- xzm_abort_with_reason(
- "pointer range initial reservation failed", kr);
- }
-
- main->xzmz_use_ranges = true;
-
- mach_vm_address_t ptr_base = ptr_addr + XZM_RANGE_SEPARATION;
-
- struct xzm_vm_range range = {
- .min_address = ptr_base,
- .max_address = ptr_base + XZM_POINTER_RANGE_SIZE,
- };
- _xzm_main_malloc_zone_init_ptr_fronts(main->xzmz_range_groups,
- main->xzmz_allocation_front_count, &range, 1, NULL);
-
- // Choose a starting hint for the data range
-
- uint64_t data_candidate_span = ptr_candidate_span - XZM_DATA_RANGE_SIZE;
- uint64_t data_candidate_granules =
- data_candidate_span / XZM_PAGE_TABLE_GRANULE;
-
- uint64_t data_entropy = malloc_entropy[1] >> 32;
- uint64_t data_granule = data_entropy % data_candidate_granules;
-
- uint64_t data_start;
- if (data_granule < ptr_granule) {
- data_start = XZM_MACOS_RANGES_START +
- (data_granule * XZM_PAGE_TABLE_GRANULE);
- } else {
- uint64_t ptr_reservation_granules =
- ptr_reservation_size / XZM_PAGE_TABLE_GRANULE;
- uint64_t data_adjusted_granule =
- data_granule + ptr_reservation_granules;
- data_start = XZM_MACOS_RANGES_START +
- (data_adjusted_granule * XZM_PAGE_TABLE_GRANULE);
- }
-
- xzm_assert(data_start < ptr_start ||
- data_start >= ptr_start + ptr_reservation_size);
- xzm_assert(data_start + XZM_DATA_RANGE_SIZE <= XZM_MACOS_RANGES_END);
-
- xzm_range_group_t data_rg = &main->xzmz_range_groups[XZM_RANGE_GROUP_DATA];
- xzm_debug_assert(data_rg->xzrg_id == XZM_RANGE_GROUP_DATA);
-
- data_rg->xzrg_base = (mach_vm_address_t)data_start;
-#endif // CONFIG_MACOS_RANGES
-}
-
-#pragma mark segment group
-
-static void _xzm_segment_group_clear_chunk(xzm_segment_group_t sg,
- uint8_t *start, size_t size);
-
-static void _xzm_segment_group_split_huge_segment(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_slice_count_t required_slices);
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
-
-static void
-__xzm_segment_cache_remove(xzm_segment_cache_t cache,
- xzm_segment_t segment)
-{
- xzm_debug_assert(cache->xzsc_count > 0);
- cache->xzsc_count--;
- TAILQ_REMOVE(&cache->xzsc_head, segment, xzs_cache_entry);
-}
-
-static void
-__xzm_segment_cache_insert(xzm_segment_cache_t cache, xzm_segment_t segment)
-{
- xzm_debug_assert(cache->xzsc_count < cache->xzsc_max_count);
- TAILQ_INSERT_HEAD(&cache->xzsc_head, segment, xzs_cache_entry);
- cache->xzsc_count++;
-}
-
-static void
-_xzm_segment_group_cache_invalidate(xzm_segment_group_t sg,
- xzm_segment_t segment)
-{
-#ifdef DEBUG
- _malloc_lock_assert_owner(&sg->xzsg_cache.xzsc_lock);
-#endif
- __xzm_segment_cache_remove(&sg->xzsg_cache, segment);
- // Free memory backing segment header
- xzm_metapool_free(&sg->xzsg_main_ref->xzmz_metapools[XZM_METAPOOL_SEGMENT],
- segment);
-}
-
-static void
-_xzm_segment_group_cache_mark_free(xzm_segment_group_t sg,
- xzm_segment_t segment)
-{
-#ifdef DEBUG
- _malloc_lock_assert_owner(&sg->xzsg_cache.xzsc_lock);
- // Make sure that this segment isn't in the segment table before we put it
- // into the cache
- xzm_segment_table_entry_s *entry;
- entry = _xzm_ptr_to_table_entry(_xzm_segment_start(segment),
- sg->xzsg_main_ref);
- xzm_debug_assert(entry->xste_val == 0);
-#endif
- xzm_debug_assert(segment->xzs_reclaim_id == VM_RECLAIM_ID_NULL);
-
- xzm_main_malloc_zone_t main = sg->xzsg_main_ref;
- xzm_reclaim_buffer_t buffer = main->xzmz_reclaim_buffer;
-
- uint8_t *addr = _xzm_segment_start(segment);
- size_t size = _xzm_segment_size(segment);
- segment->xzs_reclaim_id = _xzm_reclaim_mark_free(buffer, addr, size, false);
- __xzm_segment_cache_insert(&sg->xzsg_cache, segment);
-}
-
-// Attempt to re-use a segment from the cache. Returns true if successful.
-// If unsuccessful, the caller should invalidate the segment's cache entry.
-static bool
-_xzm_segment_group_cache_mark_used(xzm_segment_group_t sg,
- xzm_segment_t segment)
-{
-#ifdef DEBUG
- _malloc_lock_assert_owner(&sg->xzsg_cache.xzsc_lock);
-#endif
- xzm_debug_assert(segment->xzs_reclaim_id != VM_RECLAIM_ID_NULL);
- xzm_main_malloc_zone_t main = sg->xzsg_main_ref;
- xzm_reclaim_buffer_t buffer = main->xzmz_reclaim_buffer;
- mach_vm_reclaim_state_t state;
-
- state = _xzm_reclaim_mark_used(buffer, segment->xzs_reclaim_id,
- _xzm_segment_start(segment), _xzm_segment_size(segment), false);
- if (!mach_vm_reclaim_is_reusable(state)) {
- // Entry has been reclaimed by the kernel since being placed in cache
- _xzm_segment_group_cache_invalidate(sg, segment);
- return false;
- }
- segment->xzs_reclaim_id = VM_RECLAIM_ID_NULL;
- __xzm_segment_cache_remove(&sg->xzsg_cache, segment);
- return true;
-}
-
-// Evict a segment from the cache
-static void
-_xzm_segment_group_cache_evict(xzm_segment_group_t sg)
-{
-#ifdef DEBUG
- _malloc_lock_assert_owner(&sg->xzsg_cache.xzsc_lock);
-#endif
- // approximate the oldest segment by evicting the tail
- xzm_segment_t segment = TAILQ_LAST(&sg->xzsg_cache.xzsc_head,
- xzm_segment_cache_head_s);
- xzm_debug_assert(segment->xzs_reclaim_id != VM_RECLAIM_ID_NULL);
- if (_xzm_segment_group_cache_mark_used(sg, segment)) {
- _malloc_lock_unlock(&sg->xzsg_cache.xzsc_lock);
- // Segment isn't in segment table while in the cache, so pass false for
- // free_from_table while deallocating
- _xzm_segment_group_segment_deallocate(sg, segment, false);
- _malloc_lock_lock(&sg->xzsg_cache.xzsc_lock);
- }
-}
-
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
-// mimalloc: mi_slice_bin8
-MALLOC_ALWAYS_INLINE MALLOC_INLINE
-static size_t
-xzm_slice_bin8(xzm_slice_count_t slice_count)
-{
- xzm_debug_assert(slice_count != 0);
- if (slice_count <= 8) {
- return slice_count - 1;
- }
-
- xzm_debug_assert(slice_count <= XZM_SLICES_PER_SEGMENT);
- slice_count--;
-
- int msb = 63 - __builtin_clzl(slice_count);
- return ((msb << 2) + ((slice_count >> (msb - 2)) & 0x3)) - 5;
-}
-
-// mimalloc: mi_slice_bin
-MALLOC_ALWAYS_INLINE MALLOC_INLINE
-static size_t
-xzm_slice_bin(xzm_slice_count_t slice_count)
-{
- xzm_debug_assert(slice_count * XZM_SEGMENT_SLICE_SIZE <= XZM_SEGMENT_SIZE);
- xzm_debug_assert(xzm_slice_bin8(XZM_SLICES_PER_SEGMENT) <
- XZM_SPAN_QUEUE_COUNT);
- size_t bin = xzm_slice_bin8(slice_count);
- xzm_debug_assert(bin < XZM_SPAN_QUEUE_COUNT);
- return bin;
-}
-
-// mimalloc: mi_span_queue_for
-static xzm_span_queue_t
-xzm_span_queue_for(xzm_segment_group_t sg, xzm_slice_count_t slice_count)
-{
- size_t bin = xzm_slice_bin(slice_count);
- xzm_span_queue_t sq = &sg->xzsg_spans[bin];
- xzm_debug_assert(sq->xzsq_slice_count >= slice_count);
- return sq;
-}
-
-#ifdef DEBUG
-static void
-_xzm_segment_group_assert_correct_span_queue(xzm_segment_group_t sg,
- xzm_slice_t slice)
-{
- xzm_slice_kind_t kind = slice->xzc_bits.xzcb_kind;
- xzm_assert(_xzm_slice_kind_is_free_span(kind));
-
- xzm_slice_count_t slice_count;
- if (kind == XZM_SLICE_KIND_SINGLE_FREE) {
- slice_count = 1;
- } else {
- slice_count = slice->xzcs_slice_count;
- }
-
- xzm_span_queue_t sq = xzm_span_queue_for(sg, slice_count);
- xzm_free_span_t span;
- LIST_FOREACH(span, &sq->xzsq_queue, xzc_entry) {
- if (span == slice) {
- return;
- }
- }
- xzm_abort("Didn't find free span in expected span queue");
-}
-
-// mimalloc: mi_segment_is_valid
-static bool
-_xzm_segment_group_segment_is_valid(xzm_segment_group_t sg,
- xzm_segment_t segment)
-{
- xzm_assert(segment->xzs_segment_group == sg);
-
- xzm_slice_t end = _xzm_segment_slices_end(segment);
- xzm_slice_t slice = _xzm_segment_slices_begin(segment);
-
- if (segment->xzs_kind == XZM_SEGMENT_KIND_HUGE) {
- xzm_assert(segment->xzs_used == 1);
- xzm_chunk_t chunk = slice;
- xzm_assert(chunk->xzc_bits.xzcb_kind == XZM_SLICE_KIND_HUGE_CHUNK);
- xzm_assert(chunk->xzcs_slice_count == segment->xzs_slice_count);
- return true;
- }
-
- _malloc_lock_assert_owner(&sg->xzsg_lock);
-
- while (slice < end) {
- xzm_slice_kind_t kind = slice->xzc_bits.xzcb_kind;
- switch (kind) {
- case XZM_SLICE_KIND_TINY_CHUNK:
- slice++;
- break;
- case XZM_SLICE_KIND_SMALL_CHUNK:
- case XZM_SLICE_KIND_SMALL_FREELIST_CHUNK:
- case XZM_SLICE_KIND_LARGE_CHUNK: {
- size_t slice_index = _xzm_slice_index(segment, slice);
- size_t slice_count = slice->xzcs_slice_count;
- xzm_assert(slice_count > 1);
-
- slice++;
- size_t extra = MIN(slice_count - 1, XZM_MAX_SLICE_OFFSET);
- for (size_t i = 1; i <= extra; i++, slice++) {
- xzm_assert(slice->xzc_bits.xzcb_kind ==
- XZM_SLICE_KIND_MULTI_BODY);
- xzm_assert(slice->xzsl_slice_offset_bytes ==
- (uint32_t)(sizeof(struct xzm_slice_s) * i));
- }
-
- size_t last_slice_index = slice_index + slice_count - 1;
- xzm_assert(last_slice_index < segment->xzs_slice_entry_count);
- xzm_slice_t last = &segment->xzs_slices[last_slice_index];
- if (last >= slice) {
- xzm_assert(last->xzc_bits.xzcb_kind ==
- XZM_SLICE_KIND_MULTI_BODY);
- xzm_assert(last->xzsl_slice_offset_bytes ==
- (uint32_t)(sizeof(struct xzm_slice_s) *
- (slice_count - 1)));
- }
- slice = last + 1;
- break;
- }
- case XZM_SLICE_KIND_GUARD: {
- size_t slice_count = slice->xzcs_slice_count;
- slice++;
-
- for (size_t i = 1; i < slice_count; i++, slice++) {
- xzm_assert(slice->xzc_bits.xzcb_kind ==
- XZM_SLICE_KIND_MULTI_BODY);
- xzm_assert(slice->xzsl_slice_offset_bytes ==
- (uint32_t)(sizeof(struct xzm_slice_s) * i));
- }
-
- // Adjacent guards should always be coalesced
- if (slice < end) {
- xzm_assert(slice->xzc_bits.xzcb_kind != XZM_SLICE_KIND_GUARD);
- }
-
- break;
- }
- case XZM_SLICE_KIND_HUGE_CHUNK:
- xzm_abort("huge chunk in normal segment");
- break;
- case XZM_SLICE_KIND_SINGLE_FREE: {
- xzm_assert(slice->xzc_mzone_idx == XZM_MZONE_INDEX_INVALID);
- _xzm_segment_group_assert_correct_span_queue(sg, slice);
-#if CONFIG_XZM_DEFERRED_RECLAIM
- mach_vm_reclaim_id_t *reclaim_id =
- _xzm_segment_slice_meta_reclaim_id(segment, slice);
- xzm_assert(*reclaim_id == VM_RECLAIM_ID_NULL ||
- !slice->xzc_bits.xzcb_is_pristine);
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- slice++;
- break;
- }
- case XZM_SLICE_KIND_MULTI_FREE: {
- xzm_assert(slice->xzc_mzone_idx == XZM_MZONE_INDEX_INVALID);
- _xzm_segment_group_assert_correct_span_queue(sg, slice);
-
- size_t slice_index = _xzm_slice_index(segment, slice);
- size_t slice_count = slice->xzcs_slice_count;
- xzm_assert(slice_count > 1);
-
- size_t last_slice_index = slice_index + slice_count - 1;
- xzm_assert(last_slice_index < segment->xzs_slice_entry_count);
-
- xzm_slice_t last = &segment->xzs_slices[last_slice_index];
- xzm_assert(last->xzc_bits.xzcb_kind ==
- XZM_SLICE_KIND_MULTI_BODY);
- xzm_assert(last->xzsl_slice_offset_bytes ==
- (uint32_t)(sizeof(struct xzm_slice_s) * (slice_count - 1)));
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
- mach_vm_reclaim_id_t *reclaim_id =
- _xzm_segment_slice_meta_reclaim_id(segment, slice);
- xzm_assert(*reclaim_id == VM_RECLAIM_ID_NULL ||
- !slice->xzc_bits.xzcb_is_pristine);
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
- slice = last + 1;
- break;
- }
- default:
- xzm_abort_with_reason("Unexpected slice kind", (unsigned)kind);
- break;
- }
- }
-
- return true;
-}
-#endif // DEBUG
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
-
-static void
-_xzm_segment_group_span_mark_free(xzm_segment_group_t sg, xzm_free_span_t span)
-{
- xzm_debug_assert(_xzm_segment_group_uses_deferred_reclamation(sg));
- xzm_debug_assert(_xzm_slice_kind_is_free_span(span->xzc_bits.xzcb_kind));
-
- xzm_main_malloc_zone_t main = sg->xzsg_main_ref;
- xzm_malloc_zone_t zone = &main->xzmz_base;
- xzm_reclaim_buffer_t buffer = main->xzmz_reclaim_buffer;
-
- mach_vm_reclaim_id_t *reclaim_id = _xzm_slice_meta_reclaim_id(zone, span);
- xzm_debug_assert(*reclaim_id == VM_RECLAIM_ID_NULL);
- size_t span_size = _xzm_free_span_size(span);
- uint8_t *span_start = _xzm_slice_start(zone, span);
-
- *reclaim_id = _xzm_reclaim_mark_free(buffer, span_start, span_size, true);
-}
-
-static bool
-_xzm_segment_group_span_mark_used(xzm_segment_group_t sg, xzm_free_span_t span)
-{
- xzm_debug_assert(_xzm_segment_group_uses_deferred_reclamation(sg));
- xzm_debug_assert(_xzm_slice_kind_is_free_span(span->xzc_bits.xzcb_kind));
- xzm_main_malloc_zone_t main = sg->xzsg_main_ref;
- xzm_malloc_zone_t zone = &main->xzmz_base;
-
- if (!_xzm_slice_is_deferred(zone, span)) {
- // span has not been marked free
- return true;
- }
-
- xzm_reclaim_buffer_t buffer = main->xzmz_reclaim_buffer;
-
- mach_vm_reclaim_id_t *reclaim_id = _xzm_slice_meta_reclaim_id(zone, span);
- xzm_debug_assert(*reclaim_id != VM_RECLAIM_ID_NULL);
- size_t span_size = _xzm_free_span_size(span);
- uint8_t *span_start = _xzm_slice_start(zone, span);
- mach_vm_reclaim_state_t state;
-
- state = _xzm_reclaim_mark_used(buffer, *reclaim_id, span_start,
- span_size, true);
- if (mach_vm_reclaim_is_reusable(state)) {
- *reclaim_id = VM_RECLAIM_ID_NULL;
- return true;
- }
- return false;
-}
-
-static bool
-_xzm_segment_group_span_mark_smaller(xzm_segment_group_t sg,
- xzm_free_span_t span, xzm_slice_count_t front_free_count,
- xzm_slice_count_t used_count, xzm_slice_count_t back_free_count)
-{
- xzm_debug_assert(_xzm_segment_group_uses_deferred_reclamation(sg));
- xzm_debug_assert(_xzm_slice_kind_is_free_span(span->xzc_bits.xzcb_kind));
- xzm_debug_assert(front_free_count + used_count + back_free_count ==
- _xzm_free_span_slice_count(span));
-
- xzm_main_malloc_zone_t main = sg->xzsg_main_ref;
- xzm_malloc_zone_t zone = &main->xzmz_base;
- xzm_reclaim_buffer_t buffer = main->xzmz_reclaim_buffer;
-
- const bool deferred = _xzm_slice_is_deferred(zone, span);
- uint64_t *span_id = _xzm_slice_meta_reclaim_id(zone, span);
- uint8_t *span_start = _xzm_slice_start(zone, span);
- bool pristine = span->xzc_bits.xzcb_is_pristine;
-
- // Actual span metadata for the front/middle/back spans has not yet been
- // updated, we only set the deferred reclaim metadata for these spans
- xzm_free_span_t back_span = span + front_free_count + used_count;
- const size_t front_size = front_free_count << XZM_SEGMENT_SLICE_SHIFT;
- const size_t used_size = used_count << XZM_SEGMENT_SLICE_SHIFT;
- const size_t back_size = back_free_count << XZM_SEGMENT_SLICE_SHIFT;
- xzm_debug_assert(!back_size || span_start + front_size + used_size ==
- _xzm_slice_start(zone, back_span));
- uint64_t *back_id = back_size ?
- _xzm_slice_meta_reclaim_id(zone, back_span) : NULL;
- return xzm_reclaim_mark_smaller(buffer, span_id, back_id, span_start,
- front_size, used_size, back_size, deferred, pristine, true);
-}
-
-void
-xzm_chunk_mark_free(xzm_malloc_zone_t zone, xzm_chunk_t chunk)
-{
- xzm_main_malloc_zone_t main = _xzm_malloc_zone_main(zone);
- xzm_debug_assert(_xzm_chunk_should_defer_reclamation(main, chunk));
-
- xzm_reclaim_buffer_t buffer = main->xzmz_reclaim_buffer;
-
- mach_vm_reclaim_id_t *reclaim_id = _xzm_slice_meta_reclaim_id(zone, chunk);
- xzm_debug_assert(*reclaim_id == VM_RECLAIM_ID_NULL);
- size_t chunk_size;
- uint8_t *chunk_start = _xzm_chunk_start_ptr(zone, chunk, &chunk_size);
-
- *reclaim_id = _xzm_reclaim_mark_free(buffer, chunk_start, chunk_size,
- true);
-}
-
-bool
-xzm_chunk_mark_used(xzm_malloc_zone_t zone, xzm_chunk_t chunk,
- bool *was_reclaimed)
-{
- xzm_main_malloc_zone_t main = _xzm_malloc_zone_main(zone);
- xzm_debug_assert(_xzm_slice_kind_is_chunk(chunk->xzc_bits.xzcb_kind));
- xzm_debug_assert(_xzm_chunk_should_defer_reclamation(main, chunk));
-
- xzm_reclaim_buffer_t buffer = main->xzmz_reclaim_buffer;
-
- mach_vm_reclaim_id_t *reclaim_id = _xzm_slice_meta_reclaim_id(zone, chunk);
- xzm_debug_assert(*reclaim_id != VM_RECLAIM_ID_NULL);
- size_t chunk_size;
- uint8_t *chunk_start = _xzm_chunk_start_ptr(zone, chunk, &chunk_size);
- mach_vm_reclaim_state_t state;
-
- state = _xzm_reclaim_mark_used(buffer, *reclaim_id, chunk_start,
- chunk_size, true);
-
- if (was_reclaimed) {
- *was_reclaimed = (state != VM_RECLAIM_UNRECLAIMED);
- }
- if (mach_vm_reclaim_is_reusable(state)) {
- *reclaim_id = VM_RECLAIM_ID_NULL;
- return true;
- }
- return false;
-}
-
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
-// mimalloc: mi_segment_span_free
-//
-// Precondition: sg is locked (except for huge segments)
-static void
-_xzm_segment_group_segment_span_free(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_slice_count_t slice_index,
- xzm_slice_count_t slice_count, bool set_id, bool is_pristine)
-{
- xzm_debug_assert(slice_count != 0);
- xzm_debug_assert(slice_index < segment->xzs_slice_entry_count);
-
- // set first and last slice (the intermediates can be undetermined)
- //
- // TODO: leaving the intermediates undetermined means that you can't
- // reliably check whether an arbitrary slice in a segment belongs to a
- // chunk. That would be useful for:
- // - the checked memcpy trick
- // - malloc_claimed_address()
- // - possibly other things?
- //
- // However, for large allocations it would require updating large numbers of
- // slices, which is probably not worth the cost
- xzm_free_span_t span = &segment->xzs_slices[slice_index];
- span->xzc_bits.xzcb_is_pristine = is_pristine;
- if (slice_count == 1) {
- xzm_debug_assert(segment->xzs_kind != XZM_SEGMENT_KIND_HUGE);
- span->xzc_bits.xzcb_kind = XZM_SLICE_KIND_SINGLE_FREE;
- } else {
- span->xzc_bits.xzcb_kind = XZM_SLICE_KIND_MULTI_FREE;
- span->xzcs_slice_count = slice_count;
-
- xzm_debug_assert(slice_index + slice_count - 1 < segment->xzs_slice_entry_count);
- xzm_slice_t last = &segment->xzs_slices[slice_index + slice_count - 1];
- last->xzc_bits.xzcb_kind = XZM_SLICE_KIND_MULTI_BODY;
- last->xzsl_slice_offset_bytes =
- (uint32_t)(sizeof(struct xzm_slice_s) * (slice_count - 1));
- }
-
- if (segment->xzs_kind == XZM_SEGMENT_KIND_NORMAL) {
-#ifdef DEBUG
- _malloc_lock_assert_owner(&sg->xzsg_lock);
-#endif
- xzm_span_queue_t sq = xzm_span_queue_for(sg, slice_count);
- LIST_INSERT_HEAD(&sq->xzsq_queue, span, xzc_entry);
- }
-#if CONFIG_XZM_DEFERRED_RECLAIM
- if (set_id) {
- mach_vm_reclaim_id_t *reclaim_id = _xzm_segment_slice_meta_reclaim_id(
- segment, span);
- *reclaim_id = VM_RECLAIM_ID_NULL;
- } else if (!is_pristine) {
- xzm_debug_assert(*_xzm_segment_slice_meta_reclaim_id(segment, span) !=
- VM_RECLAIM_ID_NULL);
- }
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-}
-
-// mimalloc: mi_segment_slice_split
-static xzm_free_span_t
-_xzm_segment_group_segment_slice_split(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_free_span_t span,
- xzm_slice_count_t slice_count, bool uses_dr, bool front)
-{
- xzm_debug_assert(_xzm_segment_for_slice(&sg->xzsg_main_ref->xzmz_base, span) == segment);
- xzm_debug_assert(span->xzc_bits.xzcb_kind == XZM_SLICE_KIND_MULTI_FREE);
- xzm_debug_assert(span->xzcs_slice_count > slice_count);
- xzm_debug_assert(segment->xzs_kind != XZM_SEGMENT_KIND_HUGE);
-
- // Find the start and length of the piece being split off and update its
- // slices
- xzm_free_span_t retval;
- xzm_slice_count_t index_to_free;
- xzm_slice_count_t count_to_free = span->xzcs_slice_count - slice_count;
- if (front) {
- retval = span + count_to_free;
- // We don't update the backpointers here because this span is about to
- // be used as a large chunk, but we do need to update the slice count
- // and kind since this span could be given back to _segment_slice_split
- // to split off the back end
- retval->xzcs_slice_count = span->xzcs_slice_count - count_to_free;
- // We could probably copy the bits wholesale, but for now only
- // explicitly copy the ones we know we need
- retval->xzc_bits.xzcb_kind = XZM_SLICE_KIND_MULTI_FREE;
- // Preserve whether the span is pristine, since it was undefined
- retval->xzc_bits.xzcb_is_pristine = span->xzc_bits.xzcb_is_pristine;
- index_to_free = _xzm_slice_index(segment, span);
- } else {
- retval = span;
- index_to_free = _xzm_slice_index(segment, span) + slice_count;
- }
- // If the segment group uses deferred reclaim, then the reclaim id for the
- // split span has already been initialized, so don't overwrite it
- _xzm_segment_group_segment_span_free(sg, segment, index_to_free,
- count_to_free, !uses_dr, span->xzc_bits.xzcb_is_pristine);
- return retval;
-}
-
-static void
-_xzm_segment_group_segment_create_guard(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_slice_count_t index)
-{
- xzm_slice_t slice = &segment->xzs_slices[index];
- xzm_slice_count_t slice_count = 1;
-
- // Coalesce with next guard page
- if (&slice[1] < _xzm_segment_slices_end(segment) &&
- slice[1].xzc_bits.xzcb_kind == XZM_SLICE_KIND_GUARD) {
- slice_count += slice[1].xzcs_slice_count;
- }
-
- // Coalesce with previous guard page
- if (slice > _xzm_segment_slices_begin(segment)) {
- xzm_slice_t prev = _xzm_span_slice_first(slice - 1);
- if (prev->xzc_bits.xzcb_kind == XZM_SLICE_KIND_GUARD) {
- index -= prev->xzcs_slice_count;
- slice_count += prev->xzcs_slice_count;
- slice = prev;
- }
- }
-
- if (slice_count > 1) {
- // Setup backpointers
- for (int i = 1; i < slice_count; i++) {
- slice[i].xzsl_slice_offset_bytes = i * sizeof(struct xzm_slice_s);
- slice[i].xzc_bits.xzcb_kind = XZM_SLICE_KIND_MULTI_BODY;
- }
- } else {
- // This is a new guard page entry, increment segment count to avoid
- // trying to free this segment while it has guards
- segment->xzs_used++;
- }
-
- xzm_debug_assert(slice == &segment->xzs_slices[index]);
-
- slice->xzcs_slice_count = slice_count;
- // mprotect
- size_t size = XZM_SEGMENT_SLICE_SIZE * slice_count;
- void *start = _xzm_segment_slice_index_start(segment, index);
- int rc = mprotect(start, size, PROT_NONE);
- if (rc) {
- xzm_abort_with_reason("Failed to mprotect guard page", errno);
- }
-
- // Atomic store maybe?
- slice->xzc_bits.xzcb_kind = XZM_SLICE_KIND_GUARD;
-}
-
-// mimalloc: mi_segment_span_allocate
-static xzm_chunk_t
-_xzm_segment_group_segment_span_mark_allocated(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_slice_kind_t kind, size_t slice_index,
- xzm_slice_count_t slice_count)
-{
- xzm_debug_assert(_xzm_slice_kind_is_chunk(kind));
- xzm_debug_assert(slice_index < segment->xzs_slice_entry_count);
-
- xzm_slice_t slice = &segment->xzs_slices[slice_index];
- xzm_chunk_t chunk = slice;
-
- // set slice back pointers for the first XZM_MAX_SLICE_OFFSET entries
- size_t extra = MIN(slice_count - 1, XZM_MAX_SLICE_OFFSET);
- if (slice_index + extra >= segment->xzs_slice_entry_count) {
- // huge objects may have more slices than available entries in the
- // segment->xzs_slices table
- extra = segment->xzs_slice_entry_count - slice_index - 1;
- }
- slice++;
- for (size_t i = 1; i <= extra; i++, slice++) {
- slice->xzc_bits.xzcb_kind = XZM_SLICE_KIND_MULTI_BODY;
- slice->xzsl_slice_offset_bytes =
- (uint32_t)(sizeof(struct xzm_slice_s) * i);
- }
-
- // And also for the last one, if not set already (the last one is needed for
- // coalescing)
- size_t last_slice_index = slice_index + slice_count - 1;
- if (kind != XZM_SLICE_KIND_HUGE_CHUNK) {
- xzm_debug_assert(last_slice_index < segment->xzs_slice_entry_count);
-
- xzm_slice_t last = &segment->xzs_slices[last_slice_index];
- if (last >= slice) {
- last->xzc_bits.xzcb_kind = XZM_SLICE_KIND_MULTI_BODY;
- last->xzsl_slice_offset_bytes =
- (uint32_t)(sizeof(struct xzm_slice_s) * (slice_count - 1));
- }
- }
-
- // Update the chunk slice last, setting the kind at the very end to
- // "publish" the chunk for the enumerator protocol
- if (kind != XZM_SLICE_KIND_TINY_CHUNK) {
- chunk->xzcs_slice_count = slice_count;
- } else {
- xzm_debug_assert(slice_count == 1);
- }
- // TODO: atomic store, compiler barrier
- chunk->xzc_bits.xzcb_kind = kind;
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
- mach_vm_reclaim_id_t *reclaim_id = _xzm_segment_slice_meta_reclaim_id(
- segment, chunk);
- *reclaim_id = VM_RECLAIM_ID_NULL;
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- segment->xzs_used++;
- return chunk;
-}
-
-// Taken from xnu/osfmk/kern/zalloc.c
-static inline uint32_t
-dist_u32(uint32_t a, uint32_t b)
-{
- return a < b ? b - a : a - b;
-}
-
-static uint32_t
-_xzm_random_clear_n_bits(uint32_t mask, uint32_t pop, uint32_t n)
-{
- for(; n--; pop--) {
- uint32_t bit = arc4random_uniform(pop);
- uint32_t m = mask;
- // Clear the bottom `bit` bits from m...
- for (; bit; bit--) {
- m &= (m - 1);
- }
- // ... in order to clear the `bit`th least significant set bit in mask
- mask ^= 1 << __builtin_ctz(m);
- }
- return mask;
-}
-
-// Create a bitmap `width` bits wide with `pop` set bits
-static uint32_t
-_xzm_random_bits(uint32_t pop, uint32_t width)
-{
- uint32_t mask = (uint32_t)((1ull << width) - 1);
- uint32_t retval;
- uint32_t cur;
-
- if (3 * width / 4 <= pop) {
- // Caller wants >75% of the bits set, so set them all and clear <25%
- retval = mask;
- cur = width;
- } else if (pop <= width / 4) {
- retval = 0;
- cur = 0;
- } else {
- // A masked value from arc4random should contain ~`width/2` set bits
- retval = arc4random() & mask;
- cur = __builtin_popcount(retval);
-
- if (dist_u32(cur, pop) > dist_u32(width - cur, pop)) {
- // If the opposite mask has a closer popcount, then start with that
- cur = width - cur;
- retval ^= mask;
- }
- }
-
- if (cur < pop) {
- // Setting `pop - cur` bits is really clearing that many from the
- // opposite mask.
- retval ^= mask;
- retval = _xzm_random_clear_n_bits(retval, width - cur, pop - cur);
- retval ^= mask;
- } else if (pop < cur) {
- retval = _xzm_random_clear_n_bits(retval, cur, cur - pop);
- }
- xzm_debug_assert(__builtin_popcount(retval) == pop);
- xzm_debug_assert((retval & ~mask) == 0);
- return retval;
-}
-
-static xzm_chunk_t
-_xzm_segment_group_segment_span_init_run(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_slice_kind_t kind,
- xzm_preallocate_list_s *preallocate_list, xzm_slice_count_t start_index,
- xzm_slice_count_t total_slices, xzm_slice_count_t guard_count,
- xzm_slice_count_t num_chunks)
-{
- xzm_chunk_t retval = NULL;
- uint32_t guard_mask;
- if (guard_count) {
- guard_mask = _xzm_random_bits(guard_count, num_chunks + 1);
- } else {
- guard_mask = 0;
- }
-
- xzm_slice_count_t slices_per_chunk = 0;
- if (kind == XZM_SLICE_KIND_TINY_CHUNK) {
- slices_per_chunk = 1;
- } else if (kind == XZM_SLICE_KIND_SMALL_CHUNK) {
- slices_per_chunk = XZM_SMALL_CHUNK_SIZE / XZM_SEGMENT_SLICE_SIZE;
- } else if (kind == XZM_SLICE_KIND_SMALL_FREELIST_CHUNK) {
- slices_per_chunk =
- XZM_SMALL_FREELIST_CHUNK_SIZE / XZM_SEGMENT_SLICE_SIZE;
- } else {
- xzm_debug_assert(!preallocate_list);
- xzm_debug_assert(guard_count == 0);
- xzm_debug_assert(kind == XZM_SLICE_KIND_LARGE_CHUNK);
- xzm_debug_assert(num_chunks == 1);
- slices_per_chunk = total_slices;
- }
- xzm_debug_assert((num_chunks * slices_per_chunk + guard_count) ==
- total_slices);
- xzm_debug_assert((start_index + total_slices) <=
- segment->xzs_slice_entry_count);
-
- xzm_slice_count_t index = start_index;
- bool is_pristine = segment->xzs_slices[index].xzc_bits.xzcb_is_pristine;
-
- for (int i = 0; i < num_chunks; i++) {
- if (guard_mask & 1) {
- _xzm_segment_group_segment_create_guard(sg, segment, index);
- index++;
- }
- guard_mask >>= 1;
-
- xzm_chunk_t chunk = _xzm_segment_group_segment_span_mark_allocated(sg,
- segment, kind, index, slices_per_chunk);
- chunk->xzc_bits.xzcb_is_pristine = is_pristine;
- index += slices_per_chunk;
-
- if (i == 0) {
- retval = chunk;
- } else {
- SLIST_INSERT_HEAD(preallocate_list, chunk, xzc_slist_entry);
- }
- }
-
- xzm_debug_assert(guard_mask <= 1);
- if (guard_mask) {
- _xzm_segment_group_segment_create_guard(sg, segment, index);
- index++;
- }
-
- xzm_debug_assert(index - start_index == total_slices);
- return retval;
-}
-
-// mimalloc: mi_segments_page_find_and_allocate
-// Precondition: sg is locked
-static xzm_chunk_t
-_xzm_segment_group_find_and_allocate_chunk(xzm_segment_group_t sg,
- xzm_slice_kind_t kind, xzm_xzone_guard_config_t guard_config,
- xzm_preallocate_list_s *preallocate_list, xzm_slice_count_t slice_count,
- size_t alignment)
-{
- xzm_debug_assert(_xzm_slice_kind_is_chunk(kind));
- xzm_debug_assert(kind != XZM_SLICE_KIND_TINY_CHUNK || slice_count == 1);
- xzm_debug_assert(slice_count != 0);
- xzm_debug_assert(slice_count * XZM_SEGMENT_SLICE_SIZE <=
- XZM_LARGE_BLOCK_SIZE_MAX);
- xzm_debug_assert(alignment == 0 || kind == XZM_SLICE_KIND_LARGE_CHUNK);
-
- xzm_debug_assert(kind != XZM_SLICE_KIND_TINY_CHUNK || guard_config != NULL);
- xzm_debug_assert(kind != XZM_SLICE_KIND_SMALL_CHUNK || guard_config != NULL);
- xzm_debug_assert(kind != XZM_SLICE_KIND_SMALL_FREELIST_CHUNK ||
- guard_config != NULL);
- xzm_debug_assert(kind != XZM_SLICE_KIND_LARGE_CHUNK || guard_config == NULL);
-
- if (alignment <= XZM_SEGMENT_SLICE_SIZE) {
- // Large chunks guarantee page alignment
- alignment = 0;
- }
- xzm_slice_count_t alignment_slices;
- if (os_convert_overflow(alignment / XZM_SEGMENT_SLICE_SIZE, &alignment_slices)) {
- xzm_debug_abort_with_reason("Unexpected align value", alignment);
- return NULL;
- }
-
- xzm_slice_count_t total_slice_count;
- uint8_t chunks_in_run;
- uint8_t guards;
- if (guard_config && guard_config->xxgc_max_run_length) {
- chunks_in_run = arc4random_uniform(guard_config->xxgc_max_run_length) + 1;
- total_slice_count = chunks_in_run * slice_count;
- guards = (guard_config->xxgc_density * total_slice_count) / 256;
- uint32_t remainder = (guard_config->xxgc_density * total_slice_count) %
- 256;
- // short circuit to avoid a call to corecrypto in common case that the
- // density of guard pages goes perfectly into the allocated pages
- if (remainder && remainder > arc4random_uniform(256)) {
- guards++;
- }
- total_slice_count += guards;
- } else {
- total_slice_count = slice_count;
- chunks_in_run = 1;
- guards = 0;
- }
- xzm_debug_assert(total_slice_count <=
- (XZM_LARGE_BLOCK_SIZE_MAX / XZM_SEGMENT_SLICE_SIZE) ||
- // Aligned allocations can request more than LARGE_BLOCK_SIZE slices
- // from the span queue
- alignment != 0);
- // At present, we only allow 1 guard page between chunks in a run, so it
- // shouldn't be possible to have more guards than chunks
- xzm_debug_assert(chunks_in_run >= guards);
-
- if (alignment_slices) {
- // We only need to allocate (slice_count + alignment_slices - 1) slices
- // to guarantee that there will be a slice_count long span at the
- // correct alignment
- xzm_slice_count_t max_align_slices =
- alignment_slices ? alignment_slices - 1 : 0;
-
- if (os_add_overflow(total_slice_count, max_align_slices,
- &total_slice_count)) {
- xzm_debug_abort_with_reason("Unexpected total slice count",
- slice_count + max_align_slices);
- return NULL;
- }
-
- xzm_debug_assert(total_slice_count < XZM_SLICES_PER_SEGMENT);
- }
-
- for (xzm_span_queue_t sq = xzm_span_queue_for(sg, total_slice_count);
- sq < &sg->xzsg_spans[XZM_SPAN_QUEUE_COUNT];
- sq++) {
- // TODO: rather than allowing a range of span sizes in a span queue,
- // should all the spans be exactly the span queue size? Then this would
- // be a pop rather than a list scan.
- xzm_free_span_t span, tmp;
- LIST_FOREACH_SAFE(span, &sq->xzsq_queue, xzc_entry, tmp) {
- xzm_slice_count_t span_slice_count =
- _xzm_free_span_slice_count(span);
- if (span_slice_count >= total_slice_count) {
- xzm_malloc_zone_t zone = &sg->xzsg_main_ref->xzmz_base;
- xzm_segment_t segment = _xzm_segment_for_slice(zone, span);
-#if CONFIG_XZM_DEFERRED_RECLAIM
- xzm_slice_count_t old_total_slice_count = total_slice_count;
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- xzm_slice_count_t front_free_count = 0;
-
- if (alignment_slices) {
- // Split off the front to round the address up to alignment
- xzm_slice_count_t actual_index = _xzm_slice_index(segment,
- span);
- xzm_slice_count_t desired_index = roundup(actual_index,
- alignment_slices);
-
- front_free_count = desired_index - actual_index;
- xzm_debug_assert(slice_count <= (total_slice_count - front_free_count));
-
- // Take the alignment slices back out of our request
- total_slice_count = slice_count;
-
- if (front_free_count) {
- span_slice_count -= front_free_count;
- }
- }
-
- xzm_slice_count_t back_free_count =
- span_slice_count - total_slice_count;
-
- bool uses_dr = false;
-#if CONFIG_XZM_DEFERRED_RECLAIM
- uses_dr = _xzm_segment_group_uses_deferred_reclamation(sg);
- if (uses_dr) {
- if (!_xzm_segment_group_span_mark_smaller(sg, span,
- front_free_count, total_slice_count,
- back_free_count)) {
- total_slice_count = old_total_slice_count;
- // span is busy being reclaimed by the kernel
- continue;
- }
- }
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
- LIST_REMOVE(span, xzc_entry);
-
- if (front_free_count) {
- span = _xzm_segment_group_segment_slice_split(sg, segment,
- span, span_slice_count, uses_dr, true);
- }
-
- if (back_free_count) {
- _xzm_segment_group_segment_slice_split(sg, segment, span,
- total_slice_count, uses_dr, false);
- }
-
- xzm_slice_count_t index = _xzm_slice_index(segment, span);
-
- xzm_chunk_t chunk;
- chunk = _xzm_segment_group_segment_span_init_run(sg, segment,
- kind, preallocate_list, index, total_slice_count,
- guards, chunks_in_run);
-
- xzm_debug_assert(chunk);
- xzm_debug_assert(_xzm_segment_group_segment_is_valid(sg,
- segment));
-
- return chunk;
- }
- }
- }
-
- return NULL;
-}
-
-// mi_segment_init
-static xzm_chunk_t
-_xzm_segment_group_init_segment(xzm_segment_group_t sg, xzm_segment_t segment,
- void *body, size_t body_size, bool huge, bool is_pristine)
-{
- xzm_chunk_t chunk = NULL;
- xzm_assert((uintptr_t)segment < XZM_LIMIT_ADDRESS);
- xzm_assert((uintptr_t)body < XZM_LIMIT_ADDRESS);
- xzm_debug_assert((uintptr_t)segment % XZM_METAPOOL_SEGMENT_ALIGN == 0);
- xzm_debug_assert((uintptr_t)body % XZM_SEGMENT_SIZE == 0);
- xzm_debug_assert(body_size % XZM_SEGMENT_SLICE_SIZE == 0);
-
- xzm_slice_count_t total_slices = 0;
- if (os_convert_overflow(body_size / XZM_SEGMENT_SLICE_SIZE, &total_slices)) {
- xzm_abort("Slice count too large in init_segment");
- }
- segment->xzs_segment_group = sg;
- segment->xzs_slice_count = total_slices;
- segment->xzs_slice_entry_count = MIN(total_slices, XZM_SLICES_PER_SEGMENT);
- segment->xzs_used = 0;
- segment->xzs_segment_body = body;
-#if CONFIG_XZM_DEFERRED_RECLAIM
- segment->xzs_reclaim_id = VM_RECLAIM_ID_NULL;
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
- segment->xzs_kind = huge ? XZM_SEGMENT_KIND_HUGE : XZM_SEGMENT_KIND_NORMAL;
- if (huge) {
- chunk = _xzm_segment_group_segment_span_mark_allocated(sg, segment,
- XZM_SLICE_KIND_HUGE_CHUNK, 0, segment->xzs_slice_count);
- chunk->xzc_bits.xzcb_is_pristine = is_pristine;
- } else {
- // Lock the segment group to add this span - we'll return to the caller
- // with the segment group locked so they can then directly allocate what
- // they need
- _malloc_lock_lock(&sg->xzsg_lock);
-
- _xzm_segment_group_segment_span_free(sg, segment, 0, total_slices,
- true, is_pristine);
- }
- xzm_debug_assert(_xzm_segment_group_segment_is_valid(sg, segment));
- return chunk;
-}
-
-// mimalloc: mi_segment_alloc
-//
-// Used to allocate both normal and huge segments.
-//
-// Postcondition: for normal segments, the segment group lock is held on
-// successful return
-static bool
-_xzm_segment_group_alloc_segment(xzm_segment_group_t sg, size_t required_bytes,
- size_t alignment, xzm_chunk_t *huge_chunk, bool purgeable)
-{
- xzm_chunk_t chunk;
- xzm_debug_assert((required_bytes == 0 && huge_chunk == NULL) ||
- (required_bytes > 0 && huge_chunk != NULL));
-
- bool huge = (required_bytes != 0);
-
- // non-default segment alignment is only supported for huge chunks
- xzm_debug_assert(huge || alignment == 0);
-
- // The total number of bytes we need to allocate is then:
- // - For normal segments, exactly the standard segment size
- // - For huge segments, the required body size, rounded up to the next slice
- size_t total_required_bytes;
- if (huge) {
- total_required_bytes = roundup(required_bytes, XZM_SEGMENT_SLICE_SIZE);
- } else {
- total_required_bytes = XZM_SEGMENT_SIZE;
- }
-
- xzm_range_group_t rg = sg->xzsg_range_group;
-
- xzm_range_group_alloc_flags_t rga_flags = 0;
- if (huge) {
- rga_flags |= XZM_RANGE_GROUP_ALLOC_FLAGS_HUGE;
- }
-
- if (purgeable) {
- rga_flags |= XZM_RANGE_GROUP_ALLOC_FLAGS_PURGEABLE;
- }
-
-#if CONFIG_MTE
- // XXX Note: we need to allocate all data segments as taggable in order for
- // tag_data to work, but the vast majority of the space will be for
- // large/huge, which is a significant waste. We're okay with that because
- // tag_data is not the default/production configuration, but we may need to
- // be more efficient about this in the future.
- if (_xzm_segment_group_memtag_enabled(sg)) {
- rga_flags |= XZM_RANGE_GROUP_ALLOC_FLAGS_MTE;
- }
-#endif
-
- void *segment_body = xzm_range_group_alloc_segment(rg, total_required_bytes,
- alignment, mvm_plat_map(*map_ptr), rga_flags);
- if (!segment_body) {
- return false;
- }
-
- xzm_assert((uintptr_t)segment_body < XZM_LIMIT_ADDRESS);
-
- xzm_segment_t segment_meta = xzm_metapool_alloc(
- &sg->xzsg_main_ref->xzmz_metapools[XZM_METAPOOL_SEGMENT]);
-
-
- chunk = _xzm_segment_group_init_segment(sg, segment_meta, segment_body,
- total_required_bytes, huge, true);
-
- // Publish the segment in the segment table now that it has been properly
- // initialized
- _xzm_segment_table_allocated_at(sg->xzsg_main_ref, segment_body,
- segment_meta, !huge);
-
- if (huge) {
- *huge_chunk = chunk;
- }
- return true;
-}
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
-
-static xzm_chunk_t
-_xzm_segment_group_alloc_huge_chunk_from_cache(xzm_segment_group_t sg,
- xzm_slice_count_t slice_count)
-{
- xzm_debug_assert(sg->xzsg_id == XZM_SEGMENT_GROUP_DATA_LARGE);
-
- xzm_segment_t best_seg, cur_seg, seg_tmp;
- xzm_segment_cache_t cache = &sg->xzsg_cache;
- xzm_chunk_t chunk = NULL;
-
- _malloc_lock_lock(&cache->xzsc_lock);
-
- if (cache->xzsc_count == 0) {
- _malloc_lock_unlock(&cache->xzsc_lock);
- return NULL;
- }
-
- xzm_reclaim_buffer_t buffer = sg->xzsg_main_ref->xzmz_reclaim_buffer;
- while (1) {
- best_seg = NULL;
- TAILQ_FOREACH_SAFE(cur_seg, &cache->xzsc_head, xzs_cache_entry, seg_tmp) {
- if (cur_seg->xzs_slice_count >= slice_count &&
- // allow up to 50% fragmentation
- (cur_seg->xzs_slice_count < (2 * slice_count)) &&
- (best_seg == NULL ||
- cur_seg->xzs_slice_count < best_seg->xzs_slice_count)) {
- if (_xzm_reclaim_is_reusable(buffer,
- cur_seg->xzs_reclaim_id, true)) {
- best_seg = cur_seg;
- } else {
- // Kernel has already reclaimed this entry or
- // is in the process of trying to reclaim it.
- _xzm_segment_group_cache_invalidate(sg, cur_seg);
- }
- }
- }
-
- if (best_seg == NULL) {
- // Unable to find a suitable entry
- _malloc_lock_unlock(&cache->xzsc_lock);
- return NULL;
- }
-
- if (_xzm_segment_group_cache_mark_used(sg, best_seg)) {
- // entry has been reclaimed
- break;
- }
- }
-
- _malloc_lock_unlock(&cache->xzsc_lock);
-
- // Mark segment as allocated since it has been removed from the cache
- _xzm_segment_table_allocated_at(sg->xzsg_main_ref,
- _xzm_segment_start(best_seg), best_seg, false);
-
- chunk = (xzm_chunk_t)_xzm_segment_slices_begin(best_seg);
-
- return chunk;
-}
-
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
-// mimalloc: mi_segment_huge_page_alloc
-static xzm_chunk_t
-_xzm_segment_group_alloc_huge_chunk(xzm_segment_group_t sg,
- xzm_slice_count_t slice_count, bool clear, size_t alignment,
- bool purgeable)
-{
- if (alignment < XZM_SEGMENT_SIZE) {
- // Huge chunks guarantee segment alignment
- alignment = 0;
- }
-
- xzm_debug_assert(alignment % XZM_SEGMENT_SIZE == 0);
- __assert_only bool defer_large = sg->xzsg_main_ref->xzmz_defer_large;
- xzm_debug_assert(sg->xzsg_id == XZM_SEGMENT_GROUP_DATA_LARGE ||
- !defer_large);
- xzm_debug_assert(sg->xzsg_id == XZM_SEGMENT_GROUP_DATA || defer_large);
-
- size_t required_bytes = (size_t)slice_count * XZM_SEGMENT_SLICE_SIZE;
- xzm_chunk_t chunk = NULL;
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
- if (sg->xzsg_id == XZM_SEGMENT_GROUP_DATA_LARGE &&
- sg->xzsg_cache.xzsc_max_count > 0 &&
- slice_count <= sg->xzsg_cache.xzsc_max_entry_slices &&
- alignment <= XZM_SEGMENT_SIZE) {
- chunk = _xzm_segment_group_alloc_huge_chunk_from_cache(sg, slice_count);
- if (chunk) {
- if (clear) {
- size_t chunk_size = 0;
- uint8_t *start = _xzm_chunk_start_ptr(
- &sg->xzsg_main_ref->xzmz_base,
- chunk, &chunk_size);
-#if CONFIG_REALLOC_CAN_USE_VMCOPY
- // rdar://140793773
- bzero(start, chunk_size);
-#else
- _xzm_segment_group_clear_chunk(sg, start, chunk_size);
-#endif
- chunk->xzc_bits.xzcb_is_pristine = true;
- } else {
- chunk->xzc_bits.xzcb_is_pristine = false;
- }
-#ifdef DEBUG
- size_t chunk_size = 0;
- uintptr_t start = (uintptr_t)_xzm_chunk_start_ptr(
- &sg->xzsg_main_ref->xzmz_base, chunk, &chunk_size);
- xzm_debug_assert(alignment == 0 || (start % alignment) == 0);
-#endif // DEBUG
- return chunk;
- }
- }
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- // huge chunks allocated from the VM are inherently clear
- bool allocated = _xzm_segment_group_alloc_segment(sg, required_bytes,
- alignment, &chunk, purgeable);
- return allocated ? chunk : NULL;
-}
-
-static xzm_chunk_t
-_xzm_segment_group_alloc_segment_and_chunk(xzm_segment_group_t sg,
- xzm_slice_kind_t kind, xzm_xzone_guard_config_t guard_config,
- xzm_preallocate_list_s *preallocate_list, xzm_slice_count_t slice_count,
- size_t alignment)
-{
- xzm_chunk_t chunk = NULL;
-
- bool allocated = _xzm_segment_group_alloc_segment(sg, 0, 0, NULL, false);
- if (!allocated) {
- goto alloc_done;
- }
-
- // We hold the main lock again (alloc took it for us). Since we were
- // able to allocate, we should be sure to get the chunk.
- chunk = _xzm_segment_group_find_and_allocate_chunk(sg, kind, guard_config,
- preallocate_list, slice_count, alignment);
- xzm_debug_assert(chunk);
- _malloc_lock_unlock(&sg->xzsg_lock);
-
-alloc_done:
- _malloc_lock_unlock(&sg->xzsg_alloc_lock);
- return chunk;
-}
-
-static void
-_xzm_segment_group_bzero_chunk(xzm_segment_group_t sg, uint8_t *start, size_t size)
-{
- // Put a ceiling on the amount of memory we dirty at a time
- size_t max_clear_size = KiB(512);
-
- while (size) {
- size_t next_clear_size = MIN(size, max_clear_size);
- bzero(start, next_clear_size);
- xzm_madvise(&sg->xzsg_main_ref->xzmz_base, start, next_clear_size);
-
- start += next_clear_size;
- size -= next_clear_size;
- }
-}
-
-static void
-_xzm_segment_group_clear_chunk(xzm_segment_group_t sg, uint8_t *start, size_t size)
-{
-#if CONFIG_MADV_ZERO
- if (madvise(start, size, MADV_ZERO)) {
-#ifdef DEBUG
- malloc_zone_error(0, false,
- "Failed to madvise(MADV_ZERO) chunk at %p, error: %d\n",
- start, errno);
-#endif
- return _xzm_segment_group_bzero_chunk(sg, start, size);
- }
-#else
- return _xzm_segment_group_bzero_chunk(sg, start, size);
-#endif // CONFIG_MADV_ZERO
-}
-
-static void
-_xzm_segment_group_overwrite_chunk(uint8_t *start, size_t size,
- xzm_range_group_alloc_flags_t rga_flags)
-{
- mach_vm_address_t vm_addr = (mach_vm_address_t)start;
- mach_vm_size_t vm_size = (mach_vm_size_t)size;
- int alloc_flags = VM_FLAGS_OVERWRITE | VM_MAKE_TAG(VM_MEMORY_MALLOC_SMALL);
-#if CONFIG_MTE
- if (rga_flags & XZM_RANGE_GROUP_ALLOC_FLAGS_MTE) {
- alloc_flags |= VM_FLAGS_MTE;
- }
-#endif
- kern_return_t kr = mach_vm_map(mach_task_self(), &vm_addr, vm_size,
- /* mask */ 0, alloc_flags, MEMORY_OBJECT_NULL,
- /* offset */ 0, /* copy */ FALSE, VM_PROT_DEFAULT,
- VM_PROT_ALL, VM_INHERIT_DEFAULT);
- if (kr != KERN_SUCCESS) {
- xzm_abort_with_reason("mach_vm_map() overwrite failed", kr);
- }
-}
-
-// mimalloc: mi_segments_page_alloc
-xzm_chunk_t
-xzm_segment_group_alloc_chunk(xzm_segment_group_t sg, xzm_slice_kind_t kind,
- xzm_xzone_guard_config_t guard_config, xzm_slice_count_t slice_count,
- xzm_preallocate_list_s *preallocate_list, size_t alignment, bool clear,
- bool purgeable) {
- if (kind == XZM_SLICE_KIND_HUGE_CHUNK) {
- xzm_debug_assert(guard_config == NULL);
- xzm_debug_assert(preallocate_list == NULL);
- xzm_debug_assert((slice_count >
- XZM_LARGE_BLOCK_SIZE_MAX / XZM_SEGMENT_SLICE_SIZE) ||
- (alignment > XZM_ALIGNMENT_MAX));
- return _xzm_segment_group_alloc_huge_chunk(sg, slice_count, clear,
- alignment, purgeable);
- }
- xzm_debug_assert(kind == XZM_SLICE_KIND_LARGE_CHUNK || alignment == 0);
-
- // Due to alignment, it's possible for the xzone layer to request a single
- // page large chunk. The segment layer assumes that such chunks can't exist,
- // so we round up the slice count here
- if (kind == XZM_SLICE_KIND_LARGE_CHUNK && slice_count == 1) {
- slice_count = 2;
- }
-
- // Consider: round up slice_count like mimalloc does?
-
- // We don't want to hold the main segment group lock while interacting with
- // the VM so that other allocations and deallocations that don't need to can
- // be served concurrently, but we do want to limit ourselves to allocating
- // only one new segment at a time so that we don't overshoot what we need if
- // many threads arrive during a period where a new segment is needed.
- //
- // So, we also have an "allocations lock", and the protocol is that a thread
- // wanting to allocate new VM must acquire it before going off to the VM.
-
- xzm_chunk_t chunk = NULL;
-
- _malloc_lock_lock(&sg->xzsg_lock);
- chunk = _xzm_segment_group_find_and_allocate_chunk(sg, kind, guard_config,
- preallocate_list, slice_count, alignment);
- if (chunk) {
- // Happy path: we got the chunk and are done.
- _malloc_lock_unlock(&sg->xzsg_lock);
- goto done;
- }
-
- // First try didn't succeed, so we need a new segment. See if we can get
- // the alloc lock to allocate a new segment.
- bool gotlock = _malloc_lock_trylock(&sg->xzsg_alloc_lock);
- if (os_likely(gotlock)) {
- // We got it, so we can try to directly allocate a new segment.
- _malloc_lock_unlock(&sg->xzsg_lock);
- chunk = _xzm_segment_group_alloc_segment_and_chunk(sg, kind,
- guard_config, preallocate_list, slice_count, alignment);
- } else {
- // We didn't get it, so somebody else is allocating. We need to drop
- // the main lock...
- _malloc_lock_unlock(&sg->xzsg_lock);
-
- // ... and wait for them on the alloc lock.
- _malloc_lock_lock(&sg->xzsg_alloc_lock);
-
- // Now that we've got the alloc lock, reacquire the main lock and try to
- // allocate from the new segment that the thread we were waiting for
- // would have installed.
- _malloc_lock_lock(&sg->xzsg_lock);
- chunk = _xzm_segment_group_find_and_allocate_chunk(sg, kind,
- guard_config, preallocate_list, slice_count, alignment);
- _malloc_lock_unlock(&sg->xzsg_lock);
-
- if (chunk) {
- // We were able to allocate from the new segment.
- _malloc_lock_unlock(&sg->xzsg_alloc_lock);
- } else {
- // The entire new segment has already been exhausted while we were
- // waiting for the alloc lock. We have it now, so it's our turn to
- // allocate a new segment.
- chunk = _xzm_segment_group_alloc_segment_and_chunk(sg, kind,
- guard_config, preallocate_list, slice_count, alignment);
- }
- }
-
-done:
-
- if (chunk) {
- size_t chunk_size;
- uint8_t *start = _xzm_chunk_start_ptr(&sg->xzsg_main_ref->xzmz_base,
- chunk, &chunk_size);
-#if CONFIG_MTE
- const bool memtag_enabled =
- _xzm_segment_group_memtag_block(sg, chunk_size);
-#endif
- if (!chunk->xzc_bits.xzcb_is_pristine) {
- if (_xzm_segment_group_has_madvise_workaround(sg) &&
- kind == XZM_SLICE_KIND_LARGE_CHUNK) {
- xzm_range_group_alloc_flags_t rga_flags = 0;
-#if CONFIG_MTE
- if (memtag_enabled) {
- rga_flags |= XZM_RANGE_GROUP_ALLOC_FLAGS_MTE;
- }
-#endif
- _xzm_segment_group_overwrite_chunk(start, chunk_size, rga_flags);
- chunk->xzc_bits.xzcb_is_pristine = true;
- } else if (clear) {
- // TODO: is this the right cutoff?
- if (kind == XZM_SLICE_KIND_TINY_CHUNK) {
- // It's just one page that we're going to fault anyway
- bzero(start, chunk_size);
- } else {
- _xzm_segment_group_clear_chunk(sg, start, chunk_size);
- }
-
- chunk->xzc_bits.xzcb_is_pristine = true;
- }
- }
-
- if (os_unlikely(purgeable)) {
- xzm_debug_assert(guard_config == NULL);
- xzm_debug_assert(kind == XZM_SLICE_KIND_LARGE_CHUNK);
- mach_vm_address_t vm_addr = (mach_vm_address_t)start;
- mach_vm_size_t vm_size = (mach_vm_size_t)chunk_size;
- int alloc_flags = VM_FLAGS_OVERWRITE |
- VM_MAKE_TAG(VM_MEMORY_MALLOC_SMALL) | VM_FLAGS_PURGABLE;
-#if CONFIG_MTE
- if (memtag_enabled) {
- alloc_flags |= VM_FLAGS_MTE;
- }
-#endif
- kern_return_t kr = mach_vm_map(mach_task_self(), &vm_addr, vm_size,
- /* mask */ 0, alloc_flags, MEMORY_OBJECT_NULL,
- /* offset */ 0, /* copy */ FALSE, VM_PROT_DEFAULT,
- VM_PROT_ALL, VM_INHERIT_DEFAULT);
- if (kr != KERN_SUCCESS) {
- xzm_abort_with_reason("mach_vm_map() overwrite failed", kr);
- }
- }
- }
-
- return chunk;
-}
-
-// mimalloc: mi_segment_span_remove_from_queue
-static void
-_xzm_segment_group_segment_span_remove_from_queue(xzm_segment_group_t sg,
- xzm_free_span_t span, xzm_slice_count_t slice_count)
-{
- (void)sg; (void)slice_count;
- LIST_REMOVE(span, xzc_entry);
-}
-
-// mimalloc: mi_segment_span_free_coalesce
-//
-// TODO: more nuanced policy for zero-tracking
-// - Right now we do the easy thing, which is to mark the entire coalesced free
-// span as dirty because the chunk being deallocated is
-// - However, that's probably not optimal if we're coalescing something small
-// with a very large free span - e.g. the initial pristine span
-// - One possibility would be to compare the sizes of the chunk being freed and
-// the spans being coalesced with - if the spans we're coalescing with are
-// relatively large and already zero-initialized, it may be better to just
-// zero the chunk being freed and maintain the zero initialization of the new
-// span as a whole
-// - The risk of that, though, is that we may waste time zeroing chunks that
-// aren't going to wind up being used to serve cleared allocations anyway
-static xzm_free_span_t
-_xzm_segment_group_segment_span_free_coalesce(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_chunk_t chunk, bool *success_out)
-{
- xzm_slice_count_t slice_count;
- if (_xzm_slice_kind_is_chunk(chunk->xzc_bits.xzcb_kind)) {
- slice_count = _xzm_chunk_slice_count(chunk);
- } else if (_xzm_slice_kind_is_free_span(chunk->xzc_bits.xzcb_kind)) {
- slice_count = _xzm_free_span_slice_count(chunk);
- } else {
- xzm_abort("attempting to coalesce slice of unexpected type");
- }
-
- xzm_free_span_t span = chunk;
-
- if (success_out) {
- *success_out = true;
- }
-
- // "unpublish" the chunk for enumeration as early as possible by resetting
- // its kind
- span->xzc_bits.xzcb_kind = XZM_SLICE_KIND_INVALID;
-
- xzm_slice_t next = chunk + slice_count;
- if (next < _xzm_segment_slices_end(segment) &&
- _xzm_slice_kind_is_free_span(next->xzc_bits.xzcb_kind)) {
-#if CONFIG_XZM_DEFERRED_RECLAIM
- if (_xzm_segment_group_uses_deferred_reclamation(sg)) {
- if (!_xzm_segment_group_span_mark_used(sg, next)) {
- if (success_out) {
- *success_out = false;
- }
- goto previous;
- }
- }
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- xzm_slice_count_t next_slice_count = _xzm_free_span_slice_count(next);
- slice_count += next_slice_count; // extend
- _xzm_segment_group_segment_span_remove_from_queue(sg, next,
- next_slice_count);
- }
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
-previous:
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- if (span > _xzm_segment_slices_begin(segment)) {
- xzm_slice_t prev = _xzm_span_slice_first(span - 1);
- if (_xzm_slice_kind_is_free_span(prev->xzc_bits.xzcb_kind)) {
-#if CONFIG_XZM_DEFERRED_RECLAIM
- if (_xzm_segment_group_uses_deferred_reclamation(sg)) {
- if (!_xzm_segment_group_span_mark_used(sg, prev)) {
- if (success_out) {
- *success_out = false;
- }
- goto done;
- }
- }
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- xzm_slice_count_t prev_slice_count =
- _xzm_free_span_slice_count(prev);
- slice_count += prev_slice_count;
- _xzm_segment_group_segment_span_remove_from_queue(sg, prev,
- prev_slice_count);
- span = prev;
- }
- }
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
-done:
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- // and add the new free span
- _xzm_segment_group_segment_span_free(sg, segment,
- _xzm_slice_index(segment, span), slice_count, true, false);
- return span;
-}
-
-static void
-_xzm_segment_group_segment_deallocate(xzm_segment_group_t sg,
- xzm_segment_t segment, bool free_from_table)
-{
- // Remove the segment from the segment map
- if (free_from_table) {
- _xzm_segment_table_freed_at(sg->xzsg_main_ref,
- _xzm_segment_start(segment), segment, true);
- }
-
- size_t size = segment->xzs_slice_count * XZM_SEGMENT_SLICE_SIZE;
- xzm_range_group_free_segment_body(sg->xzsg_range_group,
- _xzm_segment_start(segment), size, mvm_plat_map(segment->xzs_map));
- xzm_metapool_free(&sg->xzsg_main_ref->xzmz_metapools[XZM_METAPOOL_SEGMENT],
- segment);
-}
-
-// mimalloc: mi_segment_free
-static void
-_xzm_segment_group_segment_free(xzm_segment_group_t sg, xzm_segment_t segment)
-{
- xzm_debug_assert(segment->xzs_used == 0);
- xzm_free_span_t span = _xzm_segment_slices_begin(segment);
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
- xzm_free_span_t next;
- if (_xzm_segment_group_uses_deferred_reclamation(sg)) {
- if (!_xzm_segment_group_span_mark_used(sg, span)) {
- // kernel is holding this span busy
- goto fail;
- }
- while (_xzm_free_span_slice_count(span) < _xzm_segment_slice_count(segment)) {
- bool success;
- _xzm_segment_group_segment_span_remove_from_queue(sg, span,
- span->xzcs_slice_count);
- span = _xzm_segment_group_segment_span_free_coalesce(sg, segment,
- span, &success);
- if (!success) {
- // kernel is holding an adjacent span busy
- goto fail;
- }
- }
- }
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
- // The segment should have exactly one free span, which we need to now
- // remove from its span queue
- xzm_debug_assert(span->xzc_bits.xzcb_kind == XZM_SLICE_KIND_MULTI_FREE);
- xzm_debug_assert(span->xzcs_slice_count == segment->xzs_slice_count);
-
- _xzm_segment_group_segment_span_remove_from_queue(sg, span,
- span->xzcs_slice_count);
-
- // Drop the segment group lock before going off to the VM
- _malloc_lock_unlock(&sg->xzsg_lock);
-
- _xzm_segment_group_segment_deallocate(sg, segment, true);
- return;
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
-fail:;
- // Kernel is holding a span busy, place any re-used spans back in the
- // buffer.
- next = _xzm_segment_slices_begin(segment);
- do {
- span = next;
- if (!_xzm_segment_slice_is_deferred(segment, span)) {
- _xzm_segment_group_span_mark_free(sg, span);
- }
- next = span + _xzm_free_span_slice_count(span);
- } while (next < _xzm_segment_slices_end(segment));
- _malloc_lock_unlock(&sg->xzsg_lock);
- return;
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-}
-
-// trim unneeded space off the end of a huge segment
-static void
-_xzm_segment_group_split_huge_segment(xzm_segment_group_t sg, xzm_segment_t segment,
- xzm_slice_count_t required_slices)
-{
- xzm_debug_assert(segment->xzs_kind == XZM_SEGMENT_KIND_HUGE);
- xzm_debug_assert(segment->xzs_slice_count >= required_slices);
- if (segment->xzs_slice_count == required_slices) {
- return;
- }
-
- uint8_t *start = _xzm_segment_start(segment);
- uint8_t *end = _xzm_segment_end(segment);
-
- uint8_t *remainder = (uint8_t *)(start +
- required_slices * XZM_SEGMENT_SLICE_SIZE);
- if (remainder < end) {
- size_t total_remainder_size = (size_t)(end - remainder);
-#if CONFIG_XZM_DEFERRED_RECLAIM
- // new segments must be created on a SEGMENT_SIZE boundary to be annotated
- // in the segment table
- uint8_t *remainder_seg = (uint8_t *)roundup((uintptr_t)remainder,
- XZM_SEGMENT_SIZE);
- xzm_metapool_t metapool =
- &sg->xzsg_main_ref->xzmz_metapools[XZM_METAPOOL_SEGMENT];
- xzm_segment_t remainder_metadata = xzm_metapool_alloc(metapool);
- size_t remainder_seg_size = (end - remainder_seg);
-
- // If the remainder that we're freeing spans a segment granule, we need
- // to clear the entries from the segment map
- if (remainder_seg < end) {
- _xzm_segment_table_freed_at(sg->xzsg_main_ref, remainder_seg,
- segment, false);
- }
-
- _malloc_lock_lock(&sg->xzsg_cache.xzsc_lock);
- if (remainder_seg < end &&
- remainder_seg_size > XZM_LARGE_BLOCK_SIZE_MAX &&
- sg->xzsg_cache.xzsc_count < sg->xzsg_cache.xzsc_max_count) {
- // create a new segment from the end of this one and add it back to
- // the cache
-
- _xzm_segment_group_init_segment(sg, remainder_metadata,
- remainder_seg, remainder_seg_size, true, false);
- _xzm_segment_group_cache_mark_free(sg, remainder_metadata);
-
- _malloc_lock_unlock(&sg->xzsg_cache.xzsc_lock);
-
- if (remainder_seg > remainder) {
- // free the unused portion of the current segment
- size_t remainder_size = total_remainder_size -
- remainder_seg_size;
- xzm_range_group_free_segment_body(sg->xzsg_range_group,
- (void *)remainder, remainder_size, NULL);
- }
- } else {
- _malloc_lock_unlock(&sg->xzsg_cache.xzsc_lock);
- // cannot create a cached segment out of the remainder,
- // free it instead.
- xzm_metapool_free(metapool, remainder_metadata);
- xzm_range_group_free_segment_body(sg->xzsg_range_group,
- (void *)remainder, total_remainder_size, NULL);
- }
-#else // CONFIG_XZM_DEFERRED_RECLAIM
- uint8_t *remainder_seg = (uint8_t *)roundup((uintptr_t)remainder,
- XZM_SEGMENT_SIZE);
- // If the body that we're freeing spans a segment granule, we need to
- // clear the entries from the segment map
- if (remainder_seg < end) {
- _xzm_segment_table_freed_at(sg->xzsg_main_ref, remainder_seg,
- segment, false);
- }
- xzm_range_group_free_segment_body(sg->xzsg_range_group, (void *)remainder,
- total_remainder_size, NULL);
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- // re-initialize original segment with reduced slice count
- _xzm_segment_group_init_segment(sg, segment,
- _xzm_segment_start(segment),
- required_slices * XZM_SEGMENT_SLICE_SIZE, true, false);
- }
- xzm_debug_assert(_xzm_segment_end(segment) == remainder);
-}
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
-
-static bool
-_xzm_segment_group_free_huge_chunk_to_cache(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_chunk_t chunk) {
- xzm_segment_cache_t cache = &sg->xzsg_cache;
- xzm_segment_t entry = NULL, tmp_entry = NULL;
- xzm_debug_assert(cache->xzsc_max_count > 0);
-
- if (segment->xzs_slice_count > cache->xzsc_max_entry_slices) {
- // Do this check (and all others that can cause us to return false)
- // before modifying the segment table
- return false;
- }
-
- // The data for this segment could be asynchronously reclaimed and reused
- // before the metadata is invalidated/removed from the segment table, so we
- // need to remove this segment from the segment table before putting it into
- // the cache. If reused, the segment will be marked allocated in
- // _xzm_segment_group_alloc_huge_chunk_from_cache
- _xzm_segment_table_freed_at(sg->xzsg_main_ref,
- _xzm_segment_start(segment), segment, true);
-
-#if CONFIG_MTE
- // We are committed to returning the chunk to the cache and have removed
- // access to it from the segment table. We can safely retag now before taking
- // the cache lock.
- if (_xzm_segment_group_memtag_enabled(sg)) {
- size_t chunk_size = 0;
- void *ptr = _xzm_chunk_start_ptr(
- &sg->xzsg_main_ref->xzmz_base, chunk, &chunk_size);
- memtag_tag_canonical(ptr, chunk_size);
- // Note: for better protection from canonical pointers into huge chunks we
- // could retag with a random tag here (which will require code changes on
- // the alloc path also).
- }
-#endif
-
- _malloc_lock_lock(&cache->xzsc_lock);
-
- xzm_reclaim_buffer_t buffer = sg->xzsg_main_ref->xzmz_reclaim_buffer;
-
- if (sg->xzsg_cache.xzsc_count == sg->xzsg_cache.xzsc_max_count) {
- // cache is full, sweep through the cache to find invalid entries
- TAILQ_FOREACH_SAFE(entry, &sg->xzsg_cache.xzsc_head,
- xzs_cache_entry, tmp_entry) {
- if (!_xzm_reclaim_is_reusable(buffer,
- entry->xzs_reclaim_id, true)) {
- _xzm_segment_group_cache_invalidate(sg, entry);
- continue;
- } else {
- // cache entries are kept in LRU order - encountering an
- // available one implies all other cache entries are also
- // available
- break;
- }
- }
- }
-
- while (cache->xzsc_count == cache->xzsc_max_count) {
- // Cache is full, evict the oldest entry
- _xzm_segment_group_cache_evict(sg);
- }
-
- // insert segment into cache
- _xzm_segment_group_cache_mark_free(sg, segment);
- _malloc_lock_unlock(&cache->xzsc_lock);
- return true;
-}
-
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
-// mimalloc: _mi_segment_huge_page_free
-static void
-_xzm_segment_group_free_huge_chunk(xzm_segment_group_t sg, xzm_chunk_t chunk,
- bool purgeable)
-{
- xzm_segment_t segment = _xzm_segment_for_slice(
- &sg->xzsg_main_ref->xzmz_base, chunk);
- xzm_debug_assert(segment->xzs_kind == XZM_SEGMENT_KIND_HUGE);
- xzm_debug_assert(segment->xzs_used == 1);
-
-#if CONFIG_XZM_DEFERRED_RECLAIM
- if (sg->xzsg_cache.xzsc_max_count > 0 &&
- !purgeable &&
- segment->xzs_slice_count <= sg->xzsg_cache.xzsc_max_entry_slices &&
- segment->xzs_slice_count >
- (XZM_LARGE_BLOCK_SIZE_MAX / XZM_SEGMENT_SLICE_SIZE)) {
- if (_xzm_segment_group_free_huge_chunk_to_cache(sg, segment, chunk)) {
- return;
- }
- }
-#else
- // No special handling of purgeable huge segments without the huge cache
- (void)purgeable;
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
- _xzm_segment_group_segment_deallocate(sg, segment, true);
-}
-
-static void
-xzm_madvise(xzm_malloc_zone_t zone, uint8_t *start, size_t size)
-{
- __assert_only int rc = mvm_madvise_plat(start, size, MADV_FREE_REUSABLE, 0,
- mvm_plat_map(xzm_segment_table_query(_xzm_malloc_zone_main(zone),
- start)->xzs_map));
-
-#ifdef DEBUG
- if (rc) {
- // TODO: time for a compatibility break? Make this fatal?
- malloc_zone_error(0, false,
- "Failed to madvise chunk at %p, error: %d\n", start, errno);
- }
-#endif // DEBUG
-}
-
-void
-xzm_segment_group_segment_madvise_span(xzm_segment_group_t sg,
- uint8_t *slice_start, xzm_slice_count_t count)
-{
- xzm_debug_assert((uintptr_t)slice_start % XZM_SEGMENT_SLICE_SIZE == 0);
- size_t span_size = count * XZM_SEGMENT_SLICE_SIZE;
- xzm_madvise(&sg->xzsg_main_ref->xzmz_base, slice_start, span_size);
-}
-
-void
-xzm_segment_group_segment_madvise_chunk(xzm_segment_group_t sg,
- xzm_chunk_t chunk)
-{
- xzm_debug_assert(_xzm_slice_kind_is_chunk(chunk->xzc_bits.xzcb_kind));
-
- size_t chunk_size = 0;
- uint8_t *start = _xzm_chunk_start_ptr(&sg->xzsg_main_ref->xzmz_base, chunk,
- &chunk_size);
- xzm_madvise(&sg->xzsg_main_ref->xzmz_base, start, chunk_size);
-}
-
-// mimalloc: _mi_segment_page_free
-void
-xzm_segment_group_free_chunk(xzm_segment_group_t sg, xzm_chunk_t chunk,
- bool purgeable, bool small_madvise_needed)
-{
- xzm_slice_kind_t kind = chunk->xzc_bits.xzcb_kind;
- xzm_debug_assert(_xzm_slice_kind_is_chunk(kind));
-
- if (kind == XZM_SLICE_KIND_HUGE_CHUNK) {
- _xzm_segment_group_free_huge_chunk(sg, chunk, purgeable);
- return;
- }
-
- size_t chunk_size = 0;
- uint8_t *start = _xzm_chunk_start_ptr(
- &sg->xzsg_main_ref->xzmz_base, chunk, &chunk_size);
- xzm_range_group_alloc_flags_t rga_flags = 0;
-#if CONFIG_MTE
- if (_xzm_segment_group_memtag_enabled(sg)) {
- rga_flags |= XZM_RANGE_GROUP_ALLOC_FLAGS_MTE;
- // Clear tags for chunk before handing it back to segment group
- memtag_tag_canonical(start, chunk_size);
- }
-#endif
-
- if (os_unlikely(purgeable)) {
- xzm_debug_assert(kind == XZM_SLICE_KIND_LARGE_CHUNK);
- // Remove the purgeability from this allocation before freeing back to
- // the segment
- _xzm_segment_group_overwrite_chunk(start, chunk_size, rga_flags);
- }
-
- xzm_segment_t segment = _xzm_segment_for_slice(
- &sg->xzsg_main_ref->xzmz_base, chunk);
-
- if (_xzm_segment_group_has_madvise_workaround(sg) &&
- kind == XZM_SLICE_KIND_LARGE_CHUNK) {
- _xzm_segment_group_overwrite_chunk(start, chunk_size, rga_flags);
- } else if (!_xzm_segment_group_uses_deferred_reclamation(sg) &&
- // Small chunks will have already been aggressively madvised
- // by the time they are free
- (kind != XZM_SLICE_KIND_SMALL_CHUNK || small_madvise_needed)) {
- xzm_segment_group_segment_madvise_chunk(sg, chunk);
- }
-
- _malloc_lock_lock(&sg->xzsg_lock);
-
- xzm_debug_assert(_xzm_segment_group_segment_is_valid(sg, segment));
-#if CONFIG_XZM_DEFERRED_RECLAIM
- xzm_debug_assert(!(_xzm_segment_group_uses_deferred_reclamation(sg) &&
- _xzm_segment_slice_is_deferred(segment, chunk)));
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
- xzm_free_span_t span = _xzm_segment_group_segment_span_free_coalesce(sg, segment, chunk, NULL);
- segment->xzs_used--;
-#if !CONFIG_XZM_DEFERRED_RECLAIM
- (void)span;
-#endif // !CONFIG_XZM_DEFERRED_RECLAIM
-
- xzm_debug_assert(kind != XZM_SLICE_KIND_HUGE_CHUNK);
- const bool can_deallocate = sg->xzsg_main_ref->xzmz_deallocate_segment &&
- _xzm_segment_group_id_is_data(segment->xzs_segment_group->xzsg_id);
- if (segment->xzs_used == 0 && can_deallocate) {
- // Drops the segment group lock
- _xzm_segment_group_segment_free(sg, segment);
- } else {
-#if CONFIG_XZM_DEFERRED_RECLAIM
- if (_xzm_segment_group_uses_deferred_reclamation(sg)) {
- _xzm_segment_group_span_mark_free(sg, span);
- }
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
- // TODO: sequester segments more efficiently - just leaving the final
- // whole-segment span in its span queue means its metadata page stays
- // dirty
- xzm_debug_assert(_xzm_segment_group_segment_is_valid(sg, segment));
- _malloc_lock_unlock(&sg->xzsg_lock);
- }
-}
-
-bool
-xzm_segment_group_try_realloc_large_chunk(xzm_segment_group_t sg,
- xzm_segment_t segment, xzm_chunk_t chunk,
- xzm_slice_count_t new_slice_count)
-{
- xzm_debug_assert(_xzm_segment_for_slice(&sg->xzsg_main_ref->xzmz_base,
- chunk) == segment);
- xzm_debug_assert(new_slice_count >
- (XZM_SMALL_BLOCK_SIZE_MAX / XZM_SEGMENT_SLICE_SIZE));
- xzm_debug_assert(new_slice_count <=
- (XZM_LARGE_BLOCK_SIZE_MAX / XZM_SEGMENT_SLICE_SIZE));
- xzm_debug_assert(chunk->xzc_bits.xzcb_kind == XZM_SLICE_KIND_LARGE_CHUNK);
-
- if (chunk->xzcs_slice_count < new_slice_count) {
- _malloc_lock_lock(&sg->xzsg_lock);
- xzm_slice_count_t slices_to_add = (new_slice_count -
- chunk->xzcs_slice_count);
- xzm_slice_t next_slice = chunk + chunk->xzcs_slice_count;
- xzm_slice_count_t next_free_slices = _xzm_free_span_slice_count(next_slice);
- // Check if adjacent chunk is in the right segment, free, and
- // large enough to realloc into
- if (next_slice >= _xzm_segment_slices_end(segment) ||
- !_xzm_slice_kind_is_free_span(next_slice->xzc_bits.xzcb_kind) ||
- next_free_slices < slices_to_add) {
- _malloc_lock_unlock(&sg->xzsg_lock);
- return false;
- }
-
- const xzm_slice_count_t next_slices_to_free =
- next_free_slices - slices_to_add;
- bool uses_dr = false;
-#if CONFIG_XZM_DEFERRED_RECLAIM
- uses_dr = _xzm_segment_group_uses_deferred_reclamation(sg);
- if (uses_dr) {
- if (!_xzm_segment_group_span_mark_smaller(sg, next_slice, 0,
- slices_to_add, next_slices_to_free)) {
- // kernel is holding next span busy
- _malloc_lock_unlock(&sg->xzsg_lock);
- return false;
- }
- }
-#endif // CONFIG_XZM_DEFERRED_RECLAIM
-
- _xzm_segment_group_segment_span_remove_from_queue(sg, next_slice,
- next_free_slices);
-
- // We can only split if there will be 1 or more free slices left over
- if (next_slices_to_free) {
- _xzm_segment_group_segment_slice_split(sg, segment, next_slice,
- slices_to_add, uses_dr, false);
- }
-
- for (int i = 0; i < slices_to_add; i++) {
- next_slice[i].xzc_bits.xzcb_kind = XZM_SLICE_KIND_MULTI_BODY;
- next_slice[i].xzsl_slice_offset_bytes = (uint32_t)
- (((uintptr_t)&next_slice[i]) - ((uintptr_t)chunk));
- }
- chunk->xzcs_slice_count = new_slice_count;
- xzm_debug_assert(_xzm_segment_group_segment_is_valid(sg, segment));
- _malloc_lock_unlock(&sg->xzsg_lock);
-
-#if CONFIG_MTE
- // If block grows on realloc(), tag additional size with same tag as
- // allocation.
- if (_xzm_segment_group_memtag_enabled(sg)) {
- size_t additional_size = (slices_to_add * XZM_SEGMENT_SLICE_SIZE);
- size_t chunk_size;
- void *start = (void *)_xzm_chunk_start(
- &sg->xzsg_main_ref->xzmz_base, chunk, &chunk_size);
- size_t offset = chunk_size - additional_size;
- void *additional_start = _memtag_load_tag(start) + offset;
- memtag_set_tag(additional_start, additional_size);
- }
-#endif
-
- return true;
- } else if (chunk->xzcs_slice_count > new_slice_count) {
- _malloc_lock_lock(&sg->xzsg_lock);
-
- xzm_slice_count_t slices_to_free = (chunk->xzcs_slice_count -
- new_slice_count);
- xzm_free_span_t span_to_free = chunk + new_slice_count;
-
- chunk->xzcs_slice_count = new_slice_count;
-
- xzm_slice_t last_slice = chunk + (chunk->xzcs_slice_count - 1);
- last_slice->xzc_bits.xzcb_kind = XZM_SLICE_KIND_MULTI_BODY;
- last_slice->xzsl_slice_offset_bytes = (uint32_t)
- (((uintptr_t)last_slice) - ((uintptr_t)chunk));
-
- // create a fake chunk out of the remainder before freeing it
- xzm_segment_t segment = _xzm_segment_for_slice(
- &sg->xzsg_main_ref->xzmz_base, chunk);
- xzm_slice_kind_t tail_kind = slices_to_free > 1 ?
- XZM_SLICE_KIND_LARGE_CHUNK : XZM_SLICE_KIND_TINY_CHUNK;
- _xzm_segment_group_segment_span_mark_allocated(sg, segment, tail_kind,
- _xzm_slice_index(segment, span_to_free), slices_to_free);
- _malloc_lock_unlock(&sg->xzsg_lock);
- // Realloc in place is disabled for the purgeable zone, so we can always
- // pass purgeable=false here
- xzm_segment_group_free_chunk(sg, span_to_free, false, false);
- return true;
- }
- return true; // old size == new size, so no-op
-}
-
-bool
-xzm_segment_group_try_realloc_huge_chunk(xzm_segment_group_t sg,
- xzm_malloc_zone_t zone, xzm_segment_t segment,
- xzm_chunk_t chunk, xzm_slice_count_t new_slice_count)
-{
- xzm_debug_assert(_xzm_segment_for_slice(&sg->xzsg_main_ref->xzmz_base,
- chunk) == segment);
- xzm_debug_assert(new_slice_count >
- (XZM_LARGE_BLOCK_SIZE_MAX / XZM_SEGMENT_SLICE_SIZE));
- xzm_debug_assert(chunk->xzc_bits.xzcb_kind == XZM_SLICE_KIND_HUGE_CHUNK);
-
-
- if (chunk->xzcs_slice_count < new_slice_count) {
- size_t current_size = 0;
- vm_address_t current_ptr = (vm_address_t)_xzm_chunk_start(zone, chunk,
- ¤t_size);
- vm_address_t addr_to_request = current_ptr + current_size;
- size_t slices_to_request = new_slice_count - chunk->xzcs_slice_count;
- size_t size_to_request = slices_to_request * XZM_SEGMENT_SLICE_SIZE;
-
- uintptr_t segment_to_check = roundup(addr_to_request, XZM_SEGMENT_SIZE);
- while (segment_to_check < (addr_to_request+size_to_request)) {
- // TODO: Once we have deferred reclaim for huge chunks, we have the
- // option to do something more clever here (e.g. if all segments
- // are unallocated or are still waiting to be reclaimed, then we
- // can acquire those and realloc)
- if (xzm_segment_table_query(sg->xzsg_main_ref,
- (void *)segment_to_check)) {
- return false;
- }
- segment_to_check += XZM_SEGMENT_SIZE;
- }
-
- int label = VM_MEMORY_REALLOC;
- void *addr = mvm_allocate_plat(addr_to_request, size_to_request,
- 0, VM_FLAGS_FIXED, 0, label, mvm_plat_map(segment->xzs_map));
- if (addr) {
- size_t new_body_size = new_slice_count * XZM_SEGMENT_SLICE_SIZE;
- _xzm_segment_group_init_segment(sg, segment,
- _xzm_segment_start(segment), new_body_size, true, false);
-
- // If we expanded into new segment granules, mark them as allocated
- uintptr_t first_new_segment = roundup(addr_to_request,
- XZM_SEGMENT_SIZE);
- if ((uintptr_t)current_ptr + new_body_size > first_new_segment) {
- _xzm_segment_table_allocated_at(_xzm_malloc_zone_main(zone),
- (void *)first_new_segment, segment, false);
-#if CONFIG_MTE
- // If block grows on realloc(), tag additional size with same tag as
- // allocation.
- if (_xzm_segment_group_memtag_enabled(sg)) {
- void *tagged_addr_to_request =
- _memtag_load_tag((void *)current_ptr) +
- current_size;
- memtag_set_tag(tagged_addr_to_request, size_to_request);
- }
-#endif
- }
-
- xzm_debug_assert(_xzm_segment_group_segment_is_valid(sg, segment));
- return true;
- }
- return false;
- } else if (chunk->xzcs_slice_count > new_slice_count) {
- _xzm_segment_group_split_huge_segment(sg, segment, new_slice_count);
- xzm_debug_assert(_xzm_segment_group_segment_is_valid(sg, segment));
- return true;
- }
- return true; // old size == new size, so no-op
-}
-
-#endif // CONFIG_XZONE_MALLOC