/* ----------------------------------------------------------------------------

Copyright (c) 2019-2024, Microsoft Research, Daan Leijen

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" at the root of this distribution.

-----------------------------------------------------------------------------*/

/* ----------------------------------------------------------------------------

"Arenas" are fixed area's of OS memory from which we can allocate

large blocks (>= MI_ARENA_MIN_BLOCK_SIZE, 4MiB).

In contrast to the rest of mimalloc, the arenas are shared between

threads and need to be accessed using atomic operations.

Arenas are also used to for huge OS page (1GiB) reservations or for reserving

OS memory upfront which can be improve performance or is sometimes needed

on embedded devices. We can also employ this with WASI or `sbrk` systems

to reserve large arenas upfront and be able to reuse the memory more effectively.

The arena allocation needs to be thread safe and we use an atomic bitmap to allocate.

-----------------------------------------------------------------------------*/

#include "mimalloc.h"

#include "mimalloc/internal.h"

#include "mimalloc/atomic.h"

#include "bitmap.h"

/* -----------------------------------------------------------

  Arena allocation

----------------------------------------------------------- */

// A memory arena descriptor

typedef struct mi_arena_s {

  mi_arena_id_t       id;                   // arena id; 0 for non-specific

  mi_memid_t          memid;                // memid of the memory area

  _Atomic(uint8_t*)   start;                // the start of the memory area

  size_t              block_count;          // size of the area in arena blocks (of `MI_ARENA_BLOCK_SIZE`)

  size_t              field_count;          // number of bitmap fields (where `field_count * MI_BITMAP_FIELD_BITS >= block_count`)

  size_t              meta_size;            // size of the arena structure itself (including its bitmaps)

  mi_memid_t          meta_memid;           // memid of the arena structure itself (OS or static allocation)

  int                 numa_node;            // associated NUMA node

  bool                exclusive;            // only allow allocations if specifically for this arena

  bool                is_large;             // memory area consists of large- or huge OS pages (always committed)

  mi_lock_t           abandoned_visit_lock; // lock is only used when abandoned segments are being visited

  _Atomic(size_t)     search_idx;           // optimization to start the search for free blocks

  _Atomic(mi_msecs_t) purge_expire;         // expiration time when blocks should be purged from `blocks_purge`.

  mi_bitmap_field_t*  blocks_dirty;         // are the blocks potentially non-zero?

  mi_bitmap_field_t*  blocks_committed;     // are the blocks committed? (can be NULL for memory that cannot be decommitted)

  mi_bitmap_field_t*  blocks_purge;         // blocks that can be (reset) decommitted. (can be NULL for memory that cannot be (reset) decommitted)

  mi_bitmap_field_t*  blocks_abandoned;     // blocks that start with an abandoned segment. (This crosses API's but it is convenient to have here)

  mi_bitmap_field_t   blocks_inuse[1];      // in-place bitmap of in-use blocks (of size `field_count`)

  // do not add further fields here as the dirty, committed, purged, and abandoned bitmaps follow the inuse bitmap fields.

} mi_arena_t;

#define MI_ARENA_BLOCK_SIZE   (MI_SEGMENT_SIZE)        // 64MiB  (must be at least MI_SEGMENT_ALIGN)

#define MI_ARENA_MIN_OBJ_SIZE (MI_ARENA_BLOCK_SIZE/2)  // 32MiB

#define MI_MAX_ARENAS         (132)                    // Limited as the reservation exponentially increases (and takes up .bss)

// The available arenas

static mi_decl_cache_align _Atomic(mi_arena_t*) mi_arenas[MI_MAX_ARENAS];

static mi_decl_cache_align _Atomic(size_t)      mi_arena_count; // = 0

static mi_decl_cache_align _Atomic(int64_t)     mi_arenas_purge_expire; // set if there exist purgeable arenas

#define MI_IN_ARENA_C

#include "arena-abandon.c"

#undef MI_IN_ARENA_C

/* -----------------------------------------------------------

  Arena id's

  id = arena_index + 1

----------------------------------------------------------- */

size_t mi_arena_id_index(mi_arena_id_t id) {

  return (size_t)(id <= 0 ? MI_MAX_ARENAS : id - 1);

}

static mi_arena_id_t mi_arena_id_create(size_t arena_index) {

  mi_assert_internal(arena_index < MI_MAX_ARENAS);

  return (int)arena_index + 1;

}

mi_arena_id_t _mi_arena_id_none(void) {

  return 0;

}

static bool mi_arena_id_is_suitable(mi_arena_id_t arena_id, bool arena_is_exclusive, mi_arena_id_t req_arena_id) {

  return ((!arena_is_exclusive && req_arena_id == _mi_arena_id_none()) ||

          (arena_id == req_arena_id));

}

bool _mi_arena_memid_is_suitable(mi_memid_t memid, mi_arena_id_t request_arena_id) {

  if (memid.memkind == MI_MEM_ARENA) {

    return mi_arena_id_is_suitable(memid.mem.arena.id, memid.mem.arena.is_exclusive, request_arena_id);

  }

  else {

    return mi_arena_id_is_suitable(_mi_arena_id_none(), false, request_arena_id);

  }

}

bool _mi_arena_memid_is_os_allocated(mi_memid_t memid) {

  return (memid.memkind == MI_MEM_OS);

}

size_t mi_arena_get_count(void) {

  return mi_atomic_load_relaxed(&mi_arena_count);

}

mi_arena_t* mi_arena_from_index(size_t idx) {

  mi_assert_internal(idx < mi_arena_get_count());

  return mi_atomic_load_ptr_acquire(mi_arena_t, &mi_arenas[idx]);

}

/* -----------------------------------------------------------

  Arena allocations get a (currently) 16-bit memory id where the

  lower 8 bits are the arena id, and the upper bits the block index.

----------------------------------------------------------- */

static size_t mi_block_count_of_size(size_t size) {

  return _mi_divide_up(size, MI_ARENA_BLOCK_SIZE);

}

static size_t mi_arena_block_size(size_t bcount) {

  return (bcount * MI_ARENA_BLOCK_SIZE);

}

static size_t mi_arena_size(mi_arena_t* arena) {

  return mi_arena_block_size(arena->block_count);

}

static mi_memid_t mi_memid_create_arena(mi_arena_id_t id, bool is_exclusive, mi_bitmap_index_t bitmap_index) {

  mi_memid_t memid = _mi_memid_create(MI_MEM_ARENA);

  memid.mem.arena.id = id;

  memid.mem.arena.block_index = bitmap_index;

  memid.mem.arena.is_exclusive = is_exclusive;

  return memid;

}

bool mi_arena_memid_indices(mi_memid_t memid, size_t* arena_index, mi_bitmap_index_t* bitmap_index) {

  mi_assert_internal(memid.memkind == MI_MEM_ARENA);

  *arena_index = mi_arena_id_index(memid.mem.arena.id);

  *bitmap_index = memid.mem.arena.block_index;

  return memid.mem.arena.is_exclusive;

}

/* -----------------------------------------------------------

  Special static area for mimalloc internal structures

  to avoid OS calls (for example, for the arena metadata (~= 256b))

----------------------------------------------------------- */

#define MI_ARENA_STATIC_MAX  ((MI_INTPTR_SIZE/2)*MI_KiB)  // 4 KiB on 64-bit

static mi_decl_cache_align uint8_t mi_arena_static[MI_ARENA_STATIC_MAX];  // must be cache aligned, see issue #895

static mi_decl_cache_align _Atomic(size_t) mi_arena_static_top;

static void* mi_arena_static_zalloc(size_t size, size_t alignment, mi_memid_t* memid) {

  *memid = _mi_memid_none();

  if (size == 0 || size > MI_ARENA_STATIC_MAX) return NULL;

  const size_t toplow = mi_atomic_load_relaxed(&mi_arena_static_top);

  if ((toplow + size) > MI_ARENA_STATIC_MAX) return NULL;

  // try to claim space

  if (alignment < MI_MAX_ALIGN_SIZE) { alignment = MI_MAX_ALIGN_SIZE; }

  const size_t oversize = size + alignment - 1;

  if (toplow + oversize > MI_ARENA_STATIC_MAX) return NULL;

  const size_t oldtop = mi_atomic_add_acq_rel(&mi_arena_static_top, oversize);

  size_t top = oldtop + oversize;

  if (top > MI_ARENA_STATIC_MAX) {

    // try to roll back, ok if this fails

    mi_atomic_cas_strong_acq_rel(&mi_arena_static_top, &top, oldtop);

    return NULL;

  }

  // success

  *memid = _mi_memid_create(MI_MEM_STATIC);

  memid->initially_zero = true;

  const size_t start = _mi_align_up(oldtop, alignment);

  uint8_t* const p = &mi_arena_static[start];

  _mi_memzero_aligned(p, size);

  return p;

}

void* _mi_arena_meta_zalloc(size_t size, mi_memid_t* memid) {

  *memid = _mi_memid_none();

  // try static

  void* p = mi_arena_static_zalloc(size, MI_MAX_ALIGN_SIZE, memid);

  if (p != NULL) return p;

  // or fall back to the OS

  p = _mi_os_zalloc(size, memid);

  if (p == NULL) return NULL;

  return p;

}

void _mi_arena_meta_free(void* p, mi_memid_t memid, size_t size) {

  if (mi_memkind_is_os(memid.memkind)) {

    _mi_os_free(p, size, memid);

  }

  else {

    mi_assert(memid.memkind == MI_MEM_STATIC);

  }

}

void* mi_arena_block_start(mi_arena_t* arena, mi_bitmap_index_t bindex) {

  return (arena->start + mi_arena_block_size(mi_bitmap_index_bit(bindex)));

}

/* -----------------------------------------------------------

  Thread safe allocation in an arena

----------------------------------------------------------- */

// claim the `blocks_inuse` bits

static bool mi_arena_try_claim(mi_arena_t* arena, size_t blocks, mi_bitmap_index_t* bitmap_idx)

{

  size_t idx = 0; // mi_atomic_load_relaxed(&arena->search_idx);  // start from last search; ok to be relaxed as the exact start does not matter

  if (_mi_bitmap_try_find_from_claim_across(arena->blocks_inuse, arena->field_count, idx, blocks, bitmap_idx)) {

    mi_atomic_store_relaxed(&arena->search_idx, mi_bitmap_index_field(*bitmap_idx));  // start search from found location next time around

    return true;

  };

  return false;

}

/* -----------------------------------------------------------

  Arena Allocation

----------------------------------------------------------- */

static mi_decl_noinline void* mi_arena_try_alloc_at(mi_arena_t* arena, size_t arena_index, size_t needed_bcount,

                                                    bool commit, mi_memid_t* memid)

{

  MI_UNUSED(arena_index);

  mi_assert_internal(mi_arena_id_index(arena->id) == arena_index);

  mi_bitmap_index_t bitmap_index;

  if (!mi_arena_try_claim(arena, needed_bcount, &bitmap_index)) return NULL;

  // claimed it!

  void* p = mi_arena_block_start(arena, bitmap_index);

  *memid = mi_memid_create_arena(arena->id, arena->exclusive, bitmap_index);

  memid->is_pinned = arena->memid.is_pinned;

  // none of the claimed blocks should be scheduled for a decommit

  if (arena->blocks_purge != NULL) {

    // this is thread safe as a potential purge only decommits parts that are not yet claimed as used (in `blocks_inuse`).

    _mi_bitmap_unclaim_across(arena->blocks_purge, arena->field_count, needed_bcount, bitmap_index);

  }

  // set the dirty bits (todo: no need for an atomic op here?)

  if (arena->memid.initially_zero && arena->blocks_dirty != NULL) {

    memid->initially_zero = _mi_bitmap_claim_across(arena->blocks_dirty, arena->field_count, needed_bcount, bitmap_index, NULL, NULL);

  }

  // set commit state

  if (arena->blocks_committed == NULL) {

    // always committed

    memid->initially_committed = true;

  }

  else if (commit) {

    // commit requested, but the range may not be committed as a whole: ensure it is committed now

    memid->initially_committed = true;

    const size_t commit_size = mi_arena_block_size(needed_bcount);

    bool any_uncommitted;

    size_t already_committed = 0;

    _mi_bitmap_claim_across(arena->blocks_committed, arena->field_count, needed_bcount, bitmap_index, &any_uncommitted, &already_committed);

    if (any_uncommitted) {

      mi_assert_internal(already_committed < needed_bcount);

      const size_t stat_commit_size = commit_size - mi_arena_block_size(already_committed);

      bool commit_zero = false;

      if (!_mi_os_commit_ex(p, commit_size, &commit_zero, stat_commit_size)) {

        // set all as uncommitted on commit failure

        _mi_bitmap_unclaim_across(arena->blocks_committed, arena->field_count, needed_bcount, bitmap_index);

        memid->initially_committed = false;

      }

      else {

        if (commit_zero) { memid->initially_zero = true; }

      }

    }

    else {

      // all are already committed: signal that we are reusing memory in case it was purged before

      _mi_os_reuse( p, commit_size );

    }

  }

  else {

    // no need to commit, but check if already fully committed

    size_t already_committed = 0;

    memid->initially_committed = _mi_bitmap_is_claimed_across(arena->blocks_committed, arena->field_count, needed_bcount, bitmap_index, &already_committed);

    if (!memid->initially_committed && already_committed > 0) {

      // partially committed: as it will be committed at some time, adjust the stats and pretend the range is fully uncommitted.

      mi_assert_internal(already_committed < needed_bcount);

      _mi_stat_decrease(&_mi_stats_main.committed, mi_arena_block_size(already_committed));

      _mi_bitmap_unclaim_across(arena->blocks_committed, arena->field_count, needed_bcount, bitmap_index);

    }

  }

  return p;

}

// allocate in a specific arena

static void* mi_arena_try_alloc_at_id(mi_arena_id_t arena_id, bool match_numa_node, int numa_node, size_t size, size_t alignment,

                                       bool commit, bool allow_large, mi_arena_id_t req_arena_id, mi_memid_t* memid )

{

  MI_UNUSED_RELEASE(alignment);

  mi_assert(alignment <= MI_SEGMENT_ALIGN);

  const size_t bcount = mi_block_count_of_size(size);

  const size_t arena_index = mi_arena_id_index(arena_id);

  mi_assert_internal(arena_index < mi_atomic_load_relaxed(&mi_arena_count));

  mi_assert_internal(size <= mi_arena_block_size(bcount));

  // Check arena suitability

  mi_arena_t* arena = mi_arena_from_index(arena_index);

  if (arena == NULL) return NULL;

  if (!allow_large && arena->is_large) return NULL;

  if (!mi_arena_id_is_suitable(arena->id, arena->exclusive, req_arena_id)) return NULL;

  if (req_arena_id == _mi_arena_id_none()) { // in not specific, check numa affinity

    const bool numa_suitable = (numa_node < 0 || arena->numa_node < 0 || arena->numa_node == numa_node);

    if (match_numa_node) { if (!numa_suitable) return NULL; }

                    else { if (numa_suitable) return NULL; }

  }

  // try to allocate

  void* p = mi_arena_try_alloc_at(arena, arena_index, bcount, commit, memid);

  mi_assert_internal(p == NULL || _mi_is_aligned(p, alignment));

  return p;

}

// allocate from an arena with fallback to the OS

static mi_decl_noinline void* mi_arena_try_alloc(int numa_node, size_t size, size_t alignment,

                                                  bool commit, bool allow_large,

                                                  mi_arena_id_t req_arena_id, mi_memid_t* memid )

{

  MI_UNUSED(alignment);

  mi_assert_internal(alignment <= MI_SEGMENT_ALIGN);

  const size_t max_arena = mi_atomic_load_relaxed(&mi_arena_count);

  if mi_likely(max_arena == 0) return NULL;

  if (req_arena_id != _mi_arena_id_none()) {

    // try a specific arena if requested

    if (mi_arena_id_index(req_arena_id) < max_arena) {

      void* p = mi_arena_try_alloc_at_id(req_arena_id, true, numa_node, size, alignment, commit, allow_large, req_arena_id, memid);

      if (p != NULL) return p;

    }

  }

  else {

    // try numa affine allocation

    for (size_t i = 0; i < max_arena; i++) {

      void* p = mi_arena_try_alloc_at_id(mi_arena_id_create(i), true, numa_node, size, alignment, commit, allow_large, req_arena_id, memid);

      if (p != NULL) return p;

    }

    // try from another numa node instead..

    if (numa_node >= 0) {  // if numa_node was < 0 (no specific affinity requested), all arena's have been tried already

      for (size_t i = 0; i < max_arena; i++) {

        void* p = mi_arena_try_alloc_at_id(mi_arena_id_create(i), false /* only proceed if not numa local */, numa_node, size, alignment, commit, allow_large, req_arena_id, memid);

        if (p != NULL) return p;

      }

    }

  }

  return NULL;

}

// try to reserve a fresh arena space

static bool mi_arena_reserve(size_t req_size, bool allow_large, mi_arena_id_t *arena_id)

{

  if (_mi_preloading()) return false;  // use OS only while pre loading

  const size_t arena_count = mi_atomic_load_acquire(&mi_arena_count);

  if (arena_count > (MI_MAX_ARENAS - 4)) return false;

  size_t arena_reserve = mi_option_get_size(mi_option_arena_reserve);

  if (arena_reserve == 0) return false;

  if (!_mi_os_has_virtual_reserve()) {

    arena_reserve = arena_reserve/4;  // be conservative if virtual reserve is not supported (for WASM for example)

  }

  arena_reserve = _mi_align_up(arena_reserve, MI_ARENA_BLOCK_SIZE);

  arena_reserve = _mi_align_up(arena_reserve, MI_SEGMENT_SIZE);

  if (arena_count >= 8 && arena_count <= 128) {

    // scale up the arena sizes exponentially every 8 entries (128 entries get to 589TiB)

    const size_t multiplier = (size_t)1 << _mi_clamp(arena_count/8, 0, 16 );

    size_t reserve = 0;

    if (!mi_mul_overflow(multiplier, arena_reserve, &reserve)) {

      arena_reserve = reserve;

    }

  }

  if (arena_reserve < req_size) return false;  // should be able to at least handle the current allocation size

  // commit eagerly?

  bool arena_commit = false;

  if (mi_option_get(mi_option_arena_eager_commit) == 2)      { arena_commit = _mi_os_has_overcommit() || mi_option_is_enabled(mi_option_allow_large_os_pages); }

  else if (mi_option_get(mi_option_arena_eager_commit) == 1) { arena_commit = true; }

  return (mi_reserve_os_memory_ex(arena_reserve, arena_commit, allow_large, false /* exclusive? */, arena_id) == 0);

}

void* _mi_arena_alloc_aligned(size_t size, size_t alignment, size_t align_offset, bool commit, bool allow_large,

                              mi_arena_id_t req_arena_id, mi_memid_t* memid)

{

  mi_assert_internal(memid != NULL);

  mi_assert_internal(size > 0);

  *memid = _mi_memid_none();

  const int numa_node = _mi_os_numa_node(); // current numa node

  // try to allocate in an arena if the alignment is small enough and the object is not too small (as for heap meta data)

  if (!mi_option_is_enabled(mi_option_disallow_arena_alloc)) {  // is arena allocation allowed?

    if (size >= MI_ARENA_MIN_OBJ_SIZE && alignment <= MI_SEGMENT_ALIGN && align_offset == 0)

    {

      void* p = mi_arena_try_alloc(numa_node, size, alignment, commit, allow_large, req_arena_id, memid);

      if (p != NULL) return p;

      // otherwise, try to first eagerly reserve a new arena

      if (req_arena_id == _mi_arena_id_none()) {

        mi_arena_id_t arena_id = 0;

        if (mi_arena_reserve(size, allow_large, &arena_id)) {

          // and try allocate in there

          mi_assert_internal(req_arena_id == _mi_arena_id_none());

          p = mi_arena_try_alloc_at_id(arena_id, true, numa_node, size, alignment, commit, allow_large, req_arena_id, memid);

          if (p != NULL) return p;

        }

      }

    }

  }

  // if we cannot use OS allocation, return NULL

  if (mi_option_is_enabled(mi_option_disallow_os_alloc) || req_arena_id != _mi_arena_id_none()) {

    errno = ENOMEM;

    return NULL;

  }

  // finally, fall back to the OS

  if (align_offset > 0) {

    return _mi_os_alloc_aligned_at_offset(size, alignment, align_offset, commit, allow_large, memid);

  }

  else {

    return _mi_os_alloc_aligned(size, alignment, commit, allow_large, memid);

  }

}

void* _mi_arena_alloc(size_t size, bool commit, bool allow_large, mi_arena_id_t req_arena_id, mi_memid_t* memid)

{

  return _mi_arena_alloc_aligned(size, MI_ARENA_BLOCK_SIZE, 0, commit, allow_large, req_arena_id, memid);

}

void* mi_arena_area(mi_arena_id_t arena_id, size_t* size) {

  if (size != NULL) *size = 0;

  size_t arena_index = mi_arena_id_index(arena_id);

  if (arena_index >= MI_MAX_ARENAS) return NULL;

  mi_arena_t* arena = mi_atomic_load_ptr_acquire(mi_arena_t, &mi_arenas[arena_index]);

  if (arena == NULL) return NULL;

  if (size != NULL) { *size = mi_arena_block_size(arena->block_count); }

  return arena->start;

}

/* -----------------------------------------------------------

  Arena purge

----------------------------------------------------------- */

static long mi_arena_purge_delay(void) {

  // <0 = no purging allowed, 0=immediate purging, >0=milli-second delay

  return (mi_option_get(mi_option_purge_delay) * mi_option_get(mi_option_arena_purge_mult));

}

// reset or decommit in an arena and update the committed/decommit bitmaps

// assumes we own the area (i.e. blocks_in_use is claimed by us)

static void mi_arena_purge(mi_arena_t* arena, size_t bitmap_idx, size_t blocks) {

  mi_assert_internal(arena->blocks_committed != NULL);

  mi_assert_internal(arena->blocks_purge != NULL);

  mi_assert_internal(!arena->memid.is_pinned);

  const size_t size = mi_arena_block_size(blocks);

  void* const p = mi_arena_block_start(arena, bitmap_idx);

  bool needs_recommit;

  size_t already_committed = 0;

  if (_mi_bitmap_is_claimed_across(arena->blocks_committed, arena->field_count, blocks, bitmap_idx, &already_committed)) {

    // all blocks are committed, we can purge freely

    mi_assert_internal(already_committed == blocks);

    needs_recommit = _mi_os_purge(p, size);

  }

  else {

    // some blocks are not committed -- this can happen when a partially committed block is freed

    // in `_mi_arena_free` and it is conservatively marked as uncommitted but still scheduled for a purge

    // we need to ensure we do not try to reset (as that may be invalid for uncommitted memory).

    mi_assert_internal(already_committed < blocks);

    mi_assert_internal(mi_option_is_enabled(mi_option_purge_decommits));

    needs_recommit = _mi_os_purge_ex(p, size, false /* allow reset? */, mi_arena_block_size(already_committed));

  }

  // clear the purged blocks

  _mi_bitmap_unclaim_across(arena->blocks_purge, arena->field_count, blocks, bitmap_idx);

  // update committed bitmap

  if (needs_recommit) {

    _mi_bitmap_unclaim_across(arena->blocks_committed, arena->field_count, blocks, bitmap_idx);

  }

}

// Schedule a purge. This is usually delayed to avoid repeated decommit/commit calls.

// Note: assumes we (still) own the area as we may purge immediately

static void mi_arena_schedule_purge(mi_arena_t* arena, size_t bitmap_idx, size_t blocks) {

  mi_assert_internal(arena->blocks_purge != NULL);

  const long delay = mi_arena_purge_delay();

  if (delay < 0) return;  // is purging allowed at all?

  if (_mi_preloading() || delay == 0) {

    // decommit directly

    mi_arena_purge(arena, bitmap_idx, blocks);

  }

  else {

    // schedule purge

    const mi_msecs_t expire = _mi_clock_now() + delay;

    mi_msecs_t expire0 = 0;

    if (mi_atomic_casi64_strong_acq_rel(&arena->purge_expire, &expire0, expire)) {

      // expiration was not yet set

      // maybe set the global arenas expire as well (if it wasn't set already)

      mi_atomic_casi64_strong_acq_rel(&mi_arenas_purge_expire, &expire0, expire);

    }

    else {

      // already an expiration was set

    }

    _mi_bitmap_claim_across(arena->blocks_purge, arena->field_count, blocks, bitmap_idx, NULL, NULL);

  }

}

// purge a range of blocks

// return true if the full range was purged.

// assumes we own the area (i.e. blocks_in_use is claimed by us)

static bool mi_arena_purge_range(mi_arena_t* arena, size_t idx, size_t startidx, size_t bitlen, size_t purge) {

  const size_t endidx = startidx + bitlen;

  size_t bitidx = startidx;

  bool all_purged = false;

  while (bitidx < endidx) {

    // count consecutive ones in the purge mask

    size_t count = 0;

    while (bitidx + count < endidx && (purge & ((size_t)1 << (bitidx + count))) != 0) {

      count++;

    }

    if (count > 0) {

      // found range to be purged

      const mi_bitmap_index_t range_idx = mi_bitmap_index_create(idx, bitidx);

      mi_arena_purge(arena, range_idx, count);

      if (count == bitlen) {

        all_purged = true;

      }

    }

    bitidx += (count+1); // +1 to skip the zero bit (or end)

  }

  return all_purged;

}

// returns

// -1 = nothing was purged

// 0  = nothing was purged yet because have not yet reached the expire time

// 1  = some pages in the arena were purged

static int mi_arena_try_purge(mi_arena_t* arena, mi_msecs_t now, bool force)

{

  // check pre-conditions

  if (arena->memid.is_pinned) return -1;

  // expired yet?

  mi_msecs_t expire = mi_atomic_loadi64_relaxed(&arena->purge_expire);

  if (!force) {

    if (expire == 0)  return -1;

    if (expire > now) return 0;

  }

  // reset expire (if not already set concurrently)

  mi_atomic_casi64_strong_acq_rel(&arena->purge_expire, &expire, (mi_msecs_t)0);

  _mi_stat_counter_increase(&_mi_stats_main.arena_purges, 1);

  // potential purges scheduled, walk through the bitmap

  bool any_purged = false;

  bool full_purge = true;

  for (size_t i = 0; i < arena->field_count; i++) {

    size_t purge = mi_atomic_load_relaxed(&arena->blocks_purge[i]);

    if (purge != 0) {

      size_t bitidx = 0;

      while (bitidx < MI_BITMAP_FIELD_BITS) {

        // find consecutive range of ones in the purge mask

        size_t bitlen = 0;

        while (bitidx + bitlen < MI_BITMAP_FIELD_BITS && (purge & ((size_t)1 << (bitidx + bitlen))) != 0) {

          bitlen++;

        }

        // temporarily claim the purge range as "in-use" to be thread-safe with allocation

        // try to claim the longest range of corresponding in_use bits

        const mi_bitmap_index_t bitmap_index = mi_bitmap_index_create(i, bitidx);

        while( bitlen > 0 ) {

          if (_mi_bitmap_try_claim(arena->blocks_inuse, arena->field_count, bitlen, bitmap_index)) {

            break;

          }

          bitlen--;

        }

        // actual claimed bits at `in_use`

        if (bitlen > 0) {

          // read purge again now that we have the in_use bits

          purge = mi_atomic_load_acquire(&arena->blocks_purge[i]);

          if (!mi_arena_purge_range(arena, i, bitidx, bitlen, purge)) {

            full_purge = false;

          }

          any_purged = true;

          // release the claimed `in_use` bits again

          _mi_bitmap_unclaim(arena->blocks_inuse, arena->field_count, bitlen, bitmap_index);

        }

        bitidx += (bitlen+1);  // +1 to skip the zero (or end)

      } // while bitidx

    } // purge != 0

  }

  // if not fully purged, make sure to purge again in the future

  if (!full_purge) {

    const long delay = mi_arena_purge_delay();

    mi_msecs_t expected = 0;

    mi_atomic_casi64_strong_acq_rel(&arena->purge_expire,&expected,_mi_clock_now() + delay);

  }

  return (any_purged ? 1 : -1);

}

static void mi_arenas_try_purge( bool force, bool visit_all )

{

  if (_mi_preloading() || mi_arena_purge_delay() <= 0) return;  // nothing will be scheduled

  // check if any arena needs purging?

  const mi_msecs_t now = _mi_clock_now();

  mi_msecs_t arenas_expire = mi_atomic_loadi64_acquire(&mi_arenas_purge_expire);

  if (!force && (arenas_expire == 0 || arenas_expire > now)) return;

  const size_t max_arena = mi_atomic_load_acquire(&mi_arena_count);

  if (max_arena == 0) return;

  // allow only one thread to purge at a time

  static mi_atomic_guard_t purge_guard;

  mi_atomic_guard(&purge_guard)

  {

    // increase global expire: at most one purge per delay cycle

    mi_atomic_storei64_release(&mi_arenas_purge_expire, now + mi_arena_purge_delay());

    size_t max_purge_count = (visit_all ? max_arena : 2);

    bool all_visited = true;

    bool any_purged = false;

    for (size_t i = 0; i < max_arena; i++) {

      mi_arena_t* arena = mi_atomic_load_ptr_acquire(mi_arena_t, &mi_arenas[i]);

      if (arena != NULL) {

        int purged = mi_arena_try_purge(arena, now, force);

        if (purged >= 0) {    // purged, or not yet the expire-time reached

          any_purged = true;

          if (purged >= 1) {  // purged at least one page

            if (max_purge_count <= 1) {

              all_visited = false;

              break;

            }

            max_purge_count--;

          }

        }

      }

    }

    if (all_visited && !any_purged) {

      // all arena's were visited and nothing needed to be purged: reset global expire

      mi_atomic_storei64_release(&mi_arenas_purge_expire, (mi_msecs_t)0);

    }

  }

}

/* -----------------------------------------------------------

  Arena free

----------------------------------------------------------- */

void _mi_arena_free(void* p, size_t size, size_t committed_size, mi_memid_t memid) {

  mi_assert_internal(size > 0);

  mi_assert_internal(committed_size <= size);

  if (p==NULL) return;

  if (size==0) return;

  const bool all_committed = (committed_size == size);

  const size_t decommitted_size = (committed_size <= size ? size - committed_size : 0);

  // need to set all memory to undefined as some parts may still be marked as no_access (like padding etc.)

  mi_track_mem_undefined(p,size);

  if (mi_memkind_is_os(memid.memkind)) {

    // was a direct OS allocation, pass through

    if (!all_committed && decommitted_size > 0) {

      // if partially committed, adjust the committed stats (as `_mi_os_free` will decrease commit by the full size)

      _mi_stat_increase(&_mi_stats_main.committed, decommitted_size);

    }

    _mi_os_free(p, size, memid);

  }

  else if (memid.memkind == MI_MEM_ARENA) {

    // allocated in an arena

    size_t arena_idx;

    size_t bitmap_idx;

    mi_arena_memid_indices(memid, &arena_idx, &bitmap_idx);

    mi_assert_internal(arena_idx < MI_MAX_ARENAS);

    mi_arena_t* arena = mi_atomic_load_ptr_acquire(mi_arena_t,&mi_arenas[arena_idx]);

    mi_assert_internal(arena != NULL);

    const size_t blocks = mi_block_count_of_size(size);

    // checks

    if (arena == NULL) {

      _mi_error_message(EINVAL, "trying to free from an invalid arena: %p, size %zu, memkind: 0x%x\n", p, size, memid.memkind);

      return;

    }

    mi_assert_internal(arena->field_count > mi_bitmap_index_field(bitmap_idx));

    if (arena->field_count <= mi_bitmap_index_field(bitmap_idx)) {

      _mi_error_message(EINVAL, "trying to free from an invalid arena block: %p, size %zu, memid: 0x%x\n", p, size, memid.memkind);

      return;

    }

    // potentially decommit

    if (arena->memid.is_pinned || arena->blocks_committed == NULL) {

      mi_assert_internal(all_committed);

    }

    else {

      mi_assert_internal(arena->blocks_committed != NULL);

      mi_assert_internal(arena->blocks_purge != NULL);

      if (!all_committed) {

        // mark the entire range as no longer committed (so we will recommit the full range when re-using)

        _mi_bitmap_unclaim_across(arena->blocks_committed, arena->field_count, blocks, bitmap_idx);

        mi_track_mem_noaccess(p,size);

        //if (committed_size > 0) {

          // if partially committed, adjust the committed stats (is it will be recommitted when re-using)

          // in the delayed purge, we do no longer decrease the commit if the range is not marked entirely as committed.

          _mi_stat_decrease(&_mi_stats_main.committed, committed_size);

        //}

        // note: if not all committed, it may be that the purge will reset/decommit the entire range

        // that contains already decommitted parts. Since purge consistently uses reset or decommit that

        // works (as we should never reset decommitted parts).

      }

      // (delay) purge the entire range

      mi_arena_schedule_purge(arena, bitmap_idx, blocks);

    }

    // and make it available to others again

    bool all_inuse = _mi_bitmap_unclaim_across(arena->blocks_inuse, arena->field_count, blocks, bitmap_idx);

    if (!all_inuse) {

      _mi_error_message(EAGAIN, "trying to free an already freed arena block: %p, size %zu\n", p, size);

      return;

    };

  }

  else {

    // arena was none, external, or static; nothing to do

    mi_assert_internal(memid.memkind < MI_MEM_OS);

  }

  // purge expired decommits

  mi_arenas_try_purge(false, false);

}

// destroy owned arenas; this is unsafe and should only be done using `mi_option_destroy_on_exit`

// for dynamic libraries that are unloaded and need to release all their allocated memory.

static void mi_arenas_unsafe_destroy(void) {

  const size_t max_arena = mi_atomic_load_relaxed(&mi_arena_count);

  size_t new_max_arena = 0;

  for (size_t i = 0; i < max_arena; i++) {

    mi_arena_t* arena = mi_atomic_load_ptr_acquire(mi_arena_t, &mi_arenas[i]);

    if (arena != NULL) {

      mi_lock_done(&arena->abandoned_visit_lock);

      if (arena->start != NULL && mi_memkind_is_os(arena->memid.memkind)) {

        mi_atomic_store_ptr_release(mi_arena_t, &mi_arenas[i], NULL);

        _mi_os_free(arena->start, mi_arena_size(arena), arena->memid);

      }

      else {

        new_max_arena = i;

      }

      _mi_arena_meta_free(arena, arena->meta_memid, arena->meta_size);

    }

  }

  // try to lower the max arena.

  size_t expected = max_arena;

  mi_atomic_cas_strong_acq_rel(&mi_arena_count, &expected, new_max_arena);

}

// Purge the arenas; if `force_purge` is true, amenable parts are purged even if not yet expired

void _mi_arenas_collect(bool force_purge) {

  mi_arenas_try_purge(force_purge, force_purge /* visit all? */);

}

// destroy owned arenas; this is unsafe and should only be done using `mi_option_destroy_on_exit`

// for dynamic libraries that are unloaded and need to release all their allocated memory.

void _mi_arena_unsafe_destroy_all(void) {

  mi_arenas_unsafe_destroy();

  _mi_arenas_collect(true /* force purge */);  // purge non-owned arenas

}

// Is a pointer inside any of our arenas?

bool _mi_arena_contains(const void* p) {

  const size_t max_arena = mi_atomic_load_relaxed(&mi_arena_count);

  for (size_t i = 0; i < max_arena; i++) {

    mi_arena_t* arena = mi_atomic_load_ptr_relaxed(mi_arena_t, &mi_arenas[i]);

    if (arena != NULL && arena->start <= (const uint8_t*)p && arena->start + mi_arena_block_size(arena->block_count) > (const uint8_t*)p) {

      return true;

    }

  }

  return false;

}

/* -----------------------------------------------------------

  Add an arena.

----------------------------------------------------------- */

static bool mi_arena_add(mi_arena_t* arena, mi_arena_id_t* arena_id, mi_stats_t* stats) {

  mi_assert_internal(arena != NULL);

  mi_assert_internal((uintptr_t)mi_atomic_load_ptr_relaxed(uint8_t,&arena->start) % MI_SEGMENT_ALIGN == 0);

  mi_assert_internal(arena->block_count > 0);

  if (arena_id != NULL) { *arena_id = -1; }

  size_t i = mi_atomic_load_relaxed(&mi_arena_count);

  while (i < MI_MAX_ARENAS) {

    if (mi_atomic_cas_strong_acq_rel(&mi_arena_count, &i, i+1)) {

      _mi_stat_counter_increase(&stats->arena_count, 1);

      arena->id = mi_arena_id_create(i);

      mi_atomic_store_ptr_release(mi_arena_t, &mi_arenas[i], arena);

      if (arena_id != NULL) { *arena_id = arena->id; }

      return true;

    }

  }

  return false;

}

static bool mi_manage_os_memory_ex2(void* start, size_t size, bool is_large, int numa_node, bool exclusive, mi_memid_t memid, mi_arena_id_t* arena_id) mi_attr_noexcept

{

  if (arena_id != NULL) *arena_id = _mi_arena_id_none();

  if (size < MI_ARENA_BLOCK_SIZE) {

    _mi_warning_message("the arena size is too small (memory at %p with size %zu)\n", start, size);

    return false;

  }

  if (size > MI_MAX_ALLOC_SIZE) {

    _mi_error_message(EOVERFLOW, "the arena size is too large (memory at %p with size %zu)\n", start, size);

    return false;

  }

  if (is_large) {

    mi_assert_internal(memid.initially_committed && memid.is_pinned);

  }

  if (!_mi_is_aligned(start, MI_SEGMENT_ALIGN)) {

    void* const aligned_start = _mi_align_up_ptr(start, MI_SEGMENT_ALIGN);

    const size_t diff = (uint8_t*)aligned_start - (uint8_t*)start;

    if (diff >= size || (size - diff) < MI_ARENA_BLOCK_SIZE) {

      _mi_warning_message("after alignment, the size of the arena becomes too small (memory at %p with size %zu)\n", start, size);

      return false;

    }

    start = aligned_start;

    size = size - diff;

  }

  const size_t bcount = size / MI_ARENA_BLOCK_SIZE;

  const size_t fields = _mi_divide_up(bcount, MI_BITMAP_FIELD_BITS);

  const size_t bitmaps = (memid.is_pinned ? 3 : 5);

  const size_t asize  = sizeof(mi_arena_t) + (bitmaps*fields*sizeof(mi_bitmap_field_t));

  mi_memid_t meta_memid;

  mi_arena_t* arena   = (mi_arena_t*)_mi_arena_meta_zalloc(asize, &meta_memid);

  if (arena == NULL) return false;

  // already zero'd due to zalloc

  // _mi_memzero(arena, asize);

  arena->id = _mi_arena_id_none();

  arena->memid = memid;