#include "mimalloc.h"

#include "mimalloc/internal.h"

#include "mimalloc/atomic.h"

#include <string.h> // memset

#include <stdio.h>

#define MI_PAGE_HUGE_ALIGN (256*1024)

static void mi_segment_try_purge(mi_segment_t* segment, bool force, mi_stats_t* stats);

static bool mi_commit_mask_all_set(const mi_commit_mask_t* commit, const mi_commit_mask_t* cm) {

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

if ((commit->mask[i] & cm->mask[i]) != cm->mask[i]) return false;

}

return true;

}

static bool mi_commit_mask_any_set(const mi_commit_mask_t* commit, const mi_commit_mask_t* cm) {

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

if ((commit->mask[i] & cm->mask[i]) != 0) return true;

}

return false;

}

static void mi_commit_mask_create_intersect(const mi_commit_mask_t* commit, const mi_commit_mask_t* cm, mi_commit_mask_t* res) {

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

res->mask[i] = (commit->mask[i] & cm->mask[i]);

}

}

static void mi_commit_mask_clear(mi_commit_mask_t* res, const mi_commit_mask_t* cm) {

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

res->mask[i] &= ~(cm->mask[i]);

}

}

static void mi_commit_mask_set(mi_commit_mask_t* res, const mi_commit_mask_t* cm) {

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

res->mask[i] |= cm->mask[i];

}

}

static void mi_commit_mask_create(size_t bitidx, size_t bitcount, mi_commit_mask_t* cm) {

mi_assert_internal(bitidx < MI_COMMIT_MASK_BITS);

mi_assert_internal((bitidx + bitcount) <= MI_COMMIT_MASK_BITS);

if (bitcount == MI_COMMIT_MASK_BITS) {

mi_assert_internal(bitidx==0);

mi_commit_mask_create_full(cm);

}

else if (bitcount == 0) {

mi_commit_mask_create_empty(cm);

}

else {

mi_commit_mask_create_empty(cm);

size_t i = bitidx / MI_COMMIT_MASK_FIELD_BITS;

size_t ofs = bitidx % MI_COMMIT_MASK_FIELD_BITS;

while (bitcount > 0) {

mi_assert_internal(i < MI_COMMIT_MASK_FIELD_COUNT);

size_t avail = MI_COMMIT_MASK_FIELD_BITS - ofs;

size_t count = (bitcount > avail ? avail : bitcount);

size_t mask = (count >= MI_COMMIT_MASK_FIELD_BITS ? ~((size_t)0) : (((size_t)1 << count) - 1) << ofs);

cm->mask[i] = mask;

bitcount -= count;

ofs = 0;

i++;

}

}

}

size_t _mi_commit_mask_committed_size(const mi_commit_mask_t* cm, size_t total) {

mi_assert_internal((total%MI_COMMIT_MASK_BITS)==0);

size_t count = 0;

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

size_t mask = cm->mask[i];

if (~mask == 0) {

count += MI_COMMIT_MASK_FIELD_BITS;

}

else {

for (; mask != 0; mask >>= 1) { // todo: use popcount

if ((mask&1)!=0) count++;

}

}

}

// we use total since for huge segments each commit bit may represent a larger size

return ((total / MI_COMMIT_MASK_BITS) * count);

}

size_t _mi_commit_mask_next_run(const mi_commit_mask_t* cm, size_t* idx) {

size_t i = (*idx) / MI_COMMIT_MASK_FIELD_BITS;

size_t ofs = (*idx) % MI_COMMIT_MASK_FIELD_BITS;

size_t mask = 0;

// find first ones

while (i < MI_COMMIT_MASK_FIELD_COUNT) {

mask = cm->mask[i];

mask >>= ofs;

if (mask != 0) {

while ((mask&1) == 0) {

mask >>= 1;

ofs++;

}

break;

}

i++;

ofs = 0;

}

if (i >= MI_COMMIT_MASK_FIELD_COUNT) {

// not found

*idx = MI_COMMIT_MASK_BITS;

return 0;

}

else {

// found, count ones

size_t count = 0;

*idx = (i*MI_COMMIT_MASK_FIELD_BITS) + ofs;

do {

mi_assert_internal(ofs < MI_COMMIT_MASK_FIELD_BITS && (mask&1) == 1);

do {

count++;

mask >>= 1;

} while ((mask&1) == 1);

if ((((*idx + count) % MI_COMMIT_MASK_FIELD_BITS) == 0)) {

i++;

if (i >= MI_COMMIT_MASK_FIELD_COUNT) break;

mask = cm->mask[i];

ofs = 0;

}

} while ((mask&1) == 1);

mi_assert_internal(count > 0);

return count;

}

}

static const mi_slice_t* mi_segment_slices_end(const mi_segment_t* segment) {

return &segment->slices[segment->slice_entries];

}

static uint8_t* mi_slice_start(const mi_slice_t* slice) {

mi_segment_t* segment = _mi_ptr_segment(slice);

mi_assert_internal(slice >= segment->slices && slice < mi_segment_slices_end(segment));

return ((uint8_t*)segment + ((slice - segment->slices)*MI_SEGMENT_SLICE_SIZE));

}

static inline size_t mi_slice_bin8(size_t slice_count) {

if (slice_count<=1) return slice_count;

mi_assert_internal(slice_count <= MI_SLICES_PER_SEGMENT);

slice_count--;

size_t s = mi_bsr(slice_count); // slice_count > 1

if (s <= 2) return slice_count + 1;

size_t bin = ((s << 2) | ((slice_count >> (s - 2))&0x03)) - 4;

return bin;

}

static inline size_t mi_slice_bin(size_t slice_count) {

mi_assert_internal(slice_count*MI_SEGMENT_SLICE_SIZE <= MI_SEGMENT_SIZE);

mi_assert_internal(mi_slice_bin8(MI_SLICES_PER_SEGMENT) <= MI_SEGMENT_BIN_MAX);

size_t bin = mi_slice_bin8(slice_count);

mi_assert_internal(bin <= MI_SEGMENT_BIN_MAX);

return bin;

}

static inline size_t mi_slice_index(const mi_slice_t* slice) {

mi_segment_t* segment = _mi_ptr_segment(slice);

ptrdiff_t index = slice - segment->slices;

mi_assert_internal(index >= 0 && index < (ptrdiff_t)segment->slice_entries);

return index;

}

static void mi_span_queue_push(mi_span_queue_t* sq, mi_slice_t* slice) {

// todo: or push to the end?

mi_assert_internal(slice->prev == NULL && slice->next==NULL);

slice->prev = NULL; // paranoia

slice->next = sq->first;

sq->first = slice;

if (slice->next != NULL) slice->next->prev = slice;

else sq->last = slice;

slice->xblock_size = 0; // free

}

static mi_span_queue_t* mi_span_queue_for(size_t slice_count, mi_segments_tld_t* tld) {

size_t bin = mi_slice_bin(slice_count);

mi_span_queue_t* sq = &tld->spans[bin];

mi_assert_internal(sq->slice_count >= slice_count);

return sq;

}

static void mi_span_queue_delete(mi_span_queue_t* sq, mi_slice_t* slice) {

mi_assert_internal(slice->xblock_size==0 && slice->slice_count>0 && slice->slice_offset==0);

// should work too if the queue does not contain slice (which can happen during reclaim)

if (slice->prev != NULL) slice->prev->next = slice->next;

if (slice == sq->first) sq->first = slice->next;

if (slice->next != NULL) slice->next->prev = slice->prev;

if (slice == sq->last) sq->last = slice->prev;

slice->prev = NULL;

slice->next = NULL;

slice->xblock_size = 1; // no more free

}

static bool mi_slice_is_used(const mi_slice_t* slice) {

return (slice->xblock_size > 0);

}

#if (MI_DEBUG>=3)

static bool mi_span_queue_contains(mi_span_queue_t* sq, mi_slice_t* slice) {

for (mi_slice_t* s = sq->first; s != NULL; s = s->next) {

if (s==slice) return true;

}

return false;

}

static bool mi_segment_is_valid(mi_segment_t* segment, mi_segments_tld_t* tld) {

mi_assert_internal(segment != NULL);

mi_assert_internal(_mi_ptr_cookie(segment) == segment->cookie);

mi_assert_internal(segment->abandoned <= segment->used);

mi_assert_internal(segment->thread_id == 0 || segment->thread_id == _mi_thread_id());

mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->purge_mask)); // can only decommit committed blocks

//mi_assert_internal(segment->segment_info_size % MI_SEGMENT_SLICE_SIZE == 0);

mi_slice_t* slice = &segment->slices[0];

const mi_slice_t* end = mi_segment_slices_end(segment);

size_t used_count = 0;

mi_span_queue_t* sq;

while(slice < end) {

mi_assert_internal(slice->slice_count > 0);

mi_assert_internal(slice->slice_offset == 0);

size_t index = mi_slice_index(slice);

size_t maxindex = (index + slice->slice_count >= segment->slice_entries ? segment->slice_entries : index + slice->slice_count) - 1;

if (mi_slice_is_used(slice)) { // a page in use, we need at least MAX_SLICE_OFFSET valid back offsets

used_count++;

for (size_t i = 0; i <= MI_MAX_SLICE_OFFSET && index + i <= maxindex; i++) {

mi_assert_internal(segment->slices[index + i].slice_offset == i*sizeof(mi_slice_t));

mi_assert_internal(i==0 || segment->slices[index + i].slice_count == 0);

mi_assert_internal(i==0 || segment->slices[index + i].xblock_size == 1);

}

// and the last entry as well (for coalescing)

const mi_slice_t* last = slice + slice->slice_count - 1;

if (last > slice && last < mi_segment_slices_end(segment)) {

mi_assert_internal(last->slice_offset == (slice->slice_count-1)*sizeof(mi_slice_t));

mi_assert_internal(last->slice_count == 0);

mi_assert_internal(last->xblock_size == 1);

}

}

else { // free range of slices; only last slice needs a valid back offset

mi_slice_t* last = &segment->slices[maxindex];

if (segment->kind != MI_SEGMENT_HUGE || slice->slice_count <= (segment->slice_entries - segment->segment_info_slices)) {

mi_assert_internal((uint8_t*)slice == (uint8_t*)last - last->slice_offset);

}

mi_assert_internal(slice == last || last->slice_count == 0 );

mi_assert_internal(last->xblock_size == 0 || (segment->kind==MI_SEGMENT_HUGE && last->xblock_size==1));

if (segment->kind != MI_SEGMENT_HUGE && segment->thread_id != 0) { // segment is not huge or abandoned

sq = mi_span_queue_for(slice->slice_count,tld);

mi_assert_internal(mi_span_queue_contains(sq,slice));

}

}

slice = &segment->slices[maxindex+1];

}

mi_assert_internal(slice == end);

mi_assert_internal(used_count == segment->used + 1);

return true;

}

static size_t mi_segment_info_size(mi_segment_t* segment) {

return segment->segment_info_slices * MI_SEGMENT_SLICE_SIZE;

}

static uint8_t* _mi_segment_page_start_from_slice(const mi_segment_t* segment, const mi_slice_t* slice, size_t xblock_size, size_t* page_size)

{

ptrdiff_t idx = slice - segment->slices;

size_t psize = (size_t)slice->slice_count * MI_SEGMENT_SLICE_SIZE;

// make the start not OS page aligned for smaller blocks to avoid page/cache effects

// note: the offset must always be an xblock_size multiple since we assume small allocations

// are aligned (see `mi_heap_malloc_aligned`).

size_t start_offset = 0;

if (xblock_size >= MI_INTPTR_SIZE) {

if (xblock_size <= 64) { start_offset = 3*xblock_size; }

else if (xblock_size <= 512) { start_offset = xblock_size; }

}

if (page_size != NULL) { *page_size = psize - start_offset; }

return (uint8_t*)segment + ((idx*MI_SEGMENT_SLICE_SIZE) + start_offset);

}

uint8_t* _mi_segment_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size)

{

const mi_slice_t* slice = mi_page_to_slice((mi_page_t*)page);

uint8_t* p = _mi_segment_page_start_from_slice(segment, slice, page->xblock_size, page_size);

mi_assert_internal(page->xblock_size > 0 || _mi_ptr_page(p) == page);

mi_assert_internal(_mi_ptr_segment(p) == segment);

return p;

}

static size_t mi_segment_calculate_slices(size_t required, size_t* pre_size, size_t* info_slices) {

size_t page_size = _mi_os_page_size();

size_t isize = _mi_align_up(sizeof(mi_segment_t), page_size);

size_t guardsize = 0;

if (MI_SECURE>0) {

// in secure mode, we set up a protected page in between the segment info

// and the page data (and one at the end of the segment)

guardsize = page_size;

if (required > 0) {

required = _mi_align_up(required, MI_SEGMENT_SLICE_SIZE) + page_size;

}

}

if (pre_size != NULL) *pre_size = isize;

isize = _mi_align_up(isize + guardsize, MI_SEGMENT_SLICE_SIZE);

if (info_slices != NULL) *info_slices = isize / MI_SEGMENT_SLICE_SIZE;

size_t segment_size = (required==0 ? MI_SEGMENT_SIZE : _mi_align_up( required + isize + guardsize, MI_SEGMENT_SLICE_SIZE) );

mi_assert_internal(segment_size % MI_SEGMENT_SLICE_SIZE == 0);

return (segment_size / MI_SEGMENT_SLICE_SIZE);

}

static void mi_segments_track_size(long segment_size, mi_segments_tld_t* tld) {

if (segment_size>=0) _mi_stat_increase(&tld->stats->segments,1);

else _mi_stat_decrease(&tld->stats->segments,1);

tld->count += (segment_size >= 0 ? 1 : -1);

if (tld->count > tld->peak_count) tld->peak_count = tld->count;

tld->current_size += segment_size;

if (tld->current_size > tld->peak_size) tld->peak_size = tld->current_size;

}

static void mi_segment_os_free(mi_segment_t* segment, mi_segments_tld_t* tld) {

segment->thread_id = 0;

_mi_segment_map_freed_at(segment);

mi_segments_track_size(-((long)mi_segment_size(segment)),tld);

if (MI_SECURE>0) {

// _mi_os_unprotect(segment, mi_segment_size(segment)); // ensure no more guard pages are set

// unprotect the guard pages; we cannot just unprotect the whole segment size as part may be decommitted

size_t os_pagesize = _mi_os_page_size();

_mi_os_unprotect((uint8_t*)segment + mi_segment_info_size(segment) - os_pagesize, os_pagesize);

uint8_t* end = (uint8_t*)segment + mi_segment_size(segment) - os_pagesize;

_mi_os_unprotect(end, os_pagesize);

}

// purge delayed decommits now? (no, leave it to the arena)

// mi_segment_try_purge(segment,true,tld->stats);

const size_t size = mi_segment_size(segment);

const size_t csize = _mi_commit_mask_committed_size(&segment->commit_mask, size);

_mi_abandoned_await_readers(tld->abandoned); // wait until safe to free

_mi_arena_free(segment, mi_segment_size(segment), csize, segment->memid, tld->stats);

}

void _mi_segment_thread_collect(mi_segments_tld_t* tld) {

MI_UNUSED(tld);

// nothing to do

}

static void mi_segment_commit_mask(mi_segment_t* segment, bool conservative, uint8_t* p, size_t size, uint8_t** start_p, size_t* full_size, mi_commit_mask_t* cm) {

mi_assert_internal(_mi_ptr_segment(p + 1) == segment);

mi_assert_internal(segment->kind != MI_SEGMENT_HUGE);

mi_commit_mask_create_empty(cm);

if (size == 0 || size > MI_SEGMENT_SIZE || segment->kind == MI_SEGMENT_HUGE) return;

const size_t segstart = mi_segment_info_size(segment);

const size_t segsize = mi_segment_size(segment);

if (p >= (uint8_t*)segment + segsize) return;

size_t pstart = (p - (uint8_t*)segment);

mi_assert_internal(pstart + size <= segsize);

size_t start;

size_t end;

if (conservative) {

// decommit conservative

start = _mi_align_up(pstart, MI_COMMIT_SIZE);

end = _mi_align_down(pstart + size, MI_COMMIT_SIZE);

mi_assert_internal(start >= segstart);

mi_assert_internal(end <= segsize);

}

else {

// commit liberal

start = _mi_align_down(pstart, MI_MINIMAL_COMMIT_SIZE);

end = _mi_align_up(pstart + size, MI_MINIMAL_COMMIT_SIZE);

}

if (pstart >= segstart && start < segstart) { // note: the mask is also calculated for an initial commit of the info area

start = segstart;

}

if (end > segsize) {

end = segsize;

}

mi_assert_internal(start <= pstart && (pstart + size) <= end);

mi_assert_internal(start % MI_COMMIT_SIZE==0 && end % MI_COMMIT_SIZE == 0);

*start_p = (uint8_t*)segment + start;

*full_size = (end > start ? end - start : 0);

if (*full_size == 0) return;

size_t bitidx = start / MI_COMMIT_SIZE;

mi_assert_internal(bitidx < MI_COMMIT_MASK_BITS);

size_t bitcount = *full_size / MI_COMMIT_SIZE; // can be 0

if (bitidx + bitcount > MI_COMMIT_MASK_BITS) {

_mi_warning_message("commit mask overflow: idx=%zu count=%zu start=%zx end=%zx p=0x%p size=%zu fullsize=%zu\n", bitidx, bitcount, start, end, p, size, *full_size);

}

mi_assert_internal((bitidx + bitcount) <= MI_COMMIT_MASK_BITS);

mi_commit_mask_create(bitidx, bitcount, cm);

}

static bool mi_segment_commit(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) {

mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->purge_mask));

// commit liberal

uint8_t* start = NULL;

size_t full_size = 0;

mi_commit_mask_t mask;

mi_segment_commit_mask(segment, false /* conservative? */, p, size, &start, &full_size, &mask);

if (mi_commit_mask_is_empty(&mask) || full_size == 0) return true;

if (!mi_commit_mask_all_set(&segment->commit_mask, &mask)) {

// committing

bool is_zero = false;

mi_commit_mask_t cmask;

mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask);

_mi_stat_decrease(&_mi_stats_main.committed, _mi_commit_mask_committed_size(&cmask, MI_SEGMENT_SIZE)); // adjust for overlap

if (!_mi_os_commit(start, full_size, &is_zero, stats)) return false;

mi_commit_mask_set(&segment->commit_mask, &mask);

}

// increase purge expiration when using part of delayed purges -- we assume more allocations are coming soon.

if (mi_commit_mask_any_set(&segment->purge_mask, &mask)) {

segment->purge_expire = _mi_clock_now() + mi_option_get(mi_option_purge_delay);

}

// always clear any delayed purges in our range (as they are either committed now)

mi_commit_mask_clear(&segment->purge_mask, &mask);

return true;

}

static bool mi_segment_ensure_committed(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) {

mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->purge_mask));

// note: assumes commit_mask is always full for huge segments as otherwise the commit mask bits can overflow

if (mi_commit_mask_is_full(&segment->commit_mask) && mi_commit_mask_is_empty(&segment->purge_mask)) return true; // fully committed

mi_assert_internal(segment->kind != MI_SEGMENT_HUGE);

return mi_segment_commit(segment, p, size, stats);

}

static bool mi_segment_purge(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) {

mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->purge_mask));

if (!segment->allow_purge) return true;

// purge conservative

uint8_t* start = NULL;

size_t full_size = 0;

mi_commit_mask_t mask;

mi_segment_commit_mask(segment, true /* conservative? */, p, size, &start, &full_size, &mask);

if (mi_commit_mask_is_empty(&mask) || full_size==0) return true;

if (mi_commit_mask_any_set(&segment->commit_mask, &mask)) {

// purging

mi_assert_internal((void*)start != (void*)segment);

mi_assert_internal(segment->allow_decommit);

const bool decommitted = _mi_os_purge(start, full_size, stats); // reset or decommit

if (decommitted) {

mi_commit_mask_t cmask;

mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask);

_mi_stat_increase(&_mi_stats_main.committed, full_size - _mi_commit_mask_committed_size(&cmask, MI_SEGMENT_SIZE)); // adjust for double counting

mi_commit_mask_clear(&segment->commit_mask, &mask);

}

}

// always clear any scheduled purges in our range

mi_commit_mask_clear(&segment->purge_mask, &mask);

return true;

}

static void mi_segment_schedule_purge(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) {

if (!segment->allow_purge) return;

if (mi_option_get(mi_option_purge_delay) == 0) {

mi_segment_purge(segment, p, size, stats);

}

else {

// register for future purge in the purge mask

uint8_t* start = NULL;

size_t full_size = 0;

mi_commit_mask_t mask;

mi_segment_commit_mask(segment, true /*conservative*/, p, size, &start, &full_size, &mask);

if (mi_commit_mask_is_empty(&mask) || full_size==0) return;

// update delayed commit

mi_assert_internal(segment->purge_expire > 0 || mi_commit_mask_is_empty(&segment->purge_mask));

mi_commit_mask_t cmask;

mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask); // only purge what is committed; span_free may try to decommit more

mi_commit_mask_set(&segment->purge_mask, &cmask);

mi_msecs_t now = _mi_clock_now();

if (segment->purge_expire == 0) {

// no previous purgess, initialize now

segment->purge_expire = now + mi_option_get(mi_option_purge_delay);

}

else if (segment->purge_expire <= now) {

// previous purge mask already expired

if (segment->purge_expire + mi_option_get(mi_option_purge_extend_delay) <= now) {

mi_segment_try_purge(segment, true, stats);

}

else {

segment->purge_expire = now + mi_option_get(mi_option_purge_extend_delay); // (mi_option_get(mi_option_purge_delay) / 8); // wait a tiny bit longer in case there is a series of free's

}

}

else {

// previous purge mask is not yet expired, increase the expiration by a bit.

segment->purge_expire += mi_option_get(mi_option_purge_extend_delay);

}

}

}

static void mi_segment_try_purge(mi_segment_t* segment, bool force, mi_stats_t* stats) {

if (!segment->allow_purge || mi_commit_mask_is_empty(&segment->purge_mask)) return;

mi_msecs_t now = _mi_clock_now();

if (!force && now < segment->purge_expire) return;

mi_commit_mask_t mask = segment->purge_mask;

segment->purge_expire = 0;

mi_commit_mask_create_empty(&segment->purge_mask);

size_t idx;

size_t count;

mi_commit_mask_foreach(&mask, idx, count) {

// if found, decommit that sequence

if (count > 0) {

uint8_t* p = (uint8_t*)segment + (idx*MI_COMMIT_SIZE);

size_t size = count * MI_COMMIT_SIZE;

mi_segment_purge(segment, p, size, stats);

}

}

mi_commit_mask_foreach_end()

mi_assert_internal(mi_commit_mask_is_empty(&segment->purge_mask));

}

static bool mi_segment_is_abandoned(mi_segment_t* segment) {

return (segment->thread_id == 0);

}

static void mi_segment_span_free(mi_segment_t* segment, size_t slice_index, size_t slice_count, bool allow_purge, mi_segments_tld_t* tld) {

mi_assert_internal(slice_index < segment->slice_entries);

mi_span_queue_t* sq = (segment->kind == MI_SEGMENT_HUGE || mi_segment_is_abandoned(segment)

? NULL : mi_span_queue_for(slice_count,tld));

if (slice_count==0) slice_count = 1;

mi_assert_internal(slice_index + slice_count - 1 < segment->slice_entries);

// set first and last slice (the intermediates can be undetermined)

mi_slice_t* slice = &segment->slices[slice_index];

slice->slice_count = (uint32_t)slice_count;

mi_assert_internal(slice->slice_count == slice_count); // no overflow?

slice->slice_offset = 0;

if (slice_count > 1) {

mi_slice_t* last = &segment->slices[slice_index + slice_count - 1];

last->slice_count = 0;

last->slice_offset = (uint32_t)(sizeof(mi_page_t)*(slice_count - 1));

last->xblock_size = 0;

}

// perhaps decommit

if (allow_purge) {

mi_segment_schedule_purge(segment, mi_slice_start(slice), slice_count * MI_SEGMENT_SLICE_SIZE, tld->stats);

}

// and push it on the free page queue (if it was not a huge page)

if (sq != NULL) mi_span_queue_push( sq, slice );

else slice->xblock_size = 0; // mark huge page as free anyways

}

static void mi_segment_span_remove_from_queue(mi_slice_t* slice, mi_segments_tld_t* tld) {

mi_assert_internal(slice->slice_count > 0 && slice->slice_offset==0 && slice->xblock_size==0);

mi_assert_internal(_mi_ptr_segment(slice)->kind != MI_SEGMENT_HUGE);

mi_span_queue_t* sq = mi_span_queue_for(slice->slice_count, tld);

mi_span_queue_delete(sq, slice);

}

static mi_slice_t* mi_segment_span_free_coalesce(mi_slice_t* slice, mi_segments_tld_t* tld) {

mi_assert_internal(slice != NULL && slice->slice_count > 0 && slice->slice_offset == 0);

mi_segment_t* segment = _mi_ptr_segment(slice);

bool is_abandoned = mi_segment_is_abandoned(segment);

// for huge pages, just mark as free but don't add to the queues

if (segment->kind == MI_SEGMENT_HUGE) {

// issue #691: segment->used can be 0 if the huge page block was freed while abandoned (reclaim will get here in that case)

mi_assert_internal((segment->used==0 && slice->xblock_size==0) || segment->used == 1); // decreased right after this call in `mi_segment_page_clear`

slice->xblock_size = 0; // mark as free anyways

// we should mark the last slice `xblock_size=0` now to maintain invariants but we skip it to

// avoid a possible cache miss (and the segment is about to be freed)

return slice;

}

// otherwise coalesce the span and add to the free span queues

size_t slice_count = slice->slice_count;

mi_slice_t* next = slice + slice->slice_count;

mi_assert_internal(next <= mi_segment_slices_end(segment));

if (next < mi_segment_slices_end(segment) && next->xblock_size==0) {

// free next block -- remove it from free and merge

mi_assert_internal(next->slice_count > 0 && next->slice_offset==0);

slice_count += next->slice_count; // extend

if (!is_abandoned) { mi_segment_span_remove_from_queue(next, tld); }

}

if (slice > segment->slices) {

mi_slice_t* prev = mi_slice_first(slice - 1);

mi_assert_internal(prev >= segment->slices);

if (prev->xblock_size==0) {

// free previous slice -- remove it from free and merge

mi_assert_internal(prev->slice_count > 0 && prev->slice_offset==0);

slice_count += prev->slice_count;

if (!is_abandoned) { mi_segment_span_remove_from_queue(prev, tld); }

slice = prev;

}

}

// and add the new free page

mi_segment_span_free(segment, mi_slice_index(slice), slice_count, true, tld);

return slice;

}

static mi_page_t* mi_segment_span_allocate(mi_segment_t* segment, size_t slice_index, size_t slice_count, mi_segments_tld_t* tld) {

mi_assert_internal(slice_index < segment->slice_entries);

mi_slice_t* const slice = &segment->slices[slice_index];

mi_assert_internal(slice->xblock_size==0 || slice->xblock_size==1);

// commit before changing the slice data

if (!mi_segment_ensure_committed(segment, _mi_segment_page_start_from_slice(segment, slice, 0, NULL), slice_count * MI_SEGMENT_SLICE_SIZE, tld->stats)) {

return NULL; // commit failed!

}

// convert the slices to a page

slice->slice_offset = 0;

slice->slice_count = (uint32_t)slice_count;

mi_assert_internal(slice->slice_count == slice_count);

const size_t bsize = slice_count * MI_SEGMENT_SLICE_SIZE;

slice->xblock_size = (uint32_t)(bsize >= MI_HUGE_BLOCK_SIZE ? MI_HUGE_BLOCK_SIZE : bsize);

mi_page_t* page = mi_slice_to_page(slice);

mi_assert_internal(mi_page_block_size(page) == bsize);

// set slice back pointers for the first MI_MAX_SLICE_OFFSET entries

size_t extra = slice_count-1;

if (extra > MI_MAX_SLICE_OFFSET) extra = MI_MAX_SLICE_OFFSET;

if (slice_index + extra >= segment->slice_entries) extra = segment->slice_entries - slice_index - 1; // huge objects may have more slices than available entries in the segment->slices

mi_slice_t* slice_next = slice + 1;

for (size_t i = 1; i <= extra; i++, slice_next++) {

slice_next->slice_offset = (uint32_t)(sizeof(mi_slice_t)*i);

slice_next->slice_count = 0;

slice_next->xblock_size = 1;

}

// and also for the last one (if not set already) (the last one is needed for coalescing and for large alignments)

// note: the cast is needed for ubsan since the index can be larger than MI_SLICES_PER_SEGMENT for huge allocations (see #543)

mi_slice_t* last = slice + slice_count - 1;

mi_slice_t* end = (mi_slice_t*)mi_segment_slices_end(segment);

if (last > end) last = end;

if (last > slice) {

last->slice_offset = (uint32_t)(sizeof(mi_slice_t) * (last - slice));

last->slice_count = 0;

last->xblock_size = 1;

}

// and initialize the page

page->is_committed = true;

segment->used++;

return page;

}

static void mi_segment_slice_split(mi_segment_t* segment, mi_slice_t* slice, size_t slice_count, mi_segments_tld_t* tld) {

mi_assert_internal(_mi_ptr_segment(slice) == segment);

mi_assert_internal(slice->slice_count >= slice_count);

mi_assert_internal(slice->xblock_size > 0); // no more in free queue

if (slice->slice_count <= slice_count) return;

mi_assert_internal(segment->kind != MI_SEGMENT_HUGE);

size_t next_index = mi_slice_index(slice) + slice_count;

size_t next_count = slice->slice_count - slice_count;

mi_segment_span_free(segment, next_index, next_count, false /* don't purge left-over part */, tld);

slice->slice_count = (uint32_t)slice_count;

}

static mi_page_t* mi_segments_page_find_and_allocate(size_t slice_count, mi_arena_id_t req_arena_id, mi_segments_tld_t* tld) {

mi_assert_internal(slice_count*MI_SEGMENT_SLICE_SIZE <= MI_LARGE_OBJ_SIZE_MAX);

// search from best fit up

mi_span_queue_t* sq = mi_span_queue_for(slice_count, tld);

if (slice_count == 0) slice_count = 1;

while (sq <= &tld->spans[MI_SEGMENT_BIN_MAX]) {

for (mi_slice_t* slice = sq->first; slice != NULL; slice = slice->next) {

if (slice->slice_count >= slice_count) {

// found one

mi_segment_t* segment = _mi_ptr_segment(slice);

if (_mi_arena_memid_is_suitable(segment->memid, req_arena_id)) {

// found a suitable page span

mi_span_queue_delete(sq, slice);

if (slice->slice_count > slice_count) {

mi_segment_slice_split(segment, slice, slice_count, tld);

}

mi_assert_internal(slice != NULL && slice->slice_count == slice_count && slice->xblock_size > 0);

mi_page_t* page = mi_segment_span_allocate(segment, mi_slice_index(slice), slice->slice_count, tld);

if (page == NULL) {

// commit failed; return NULL but first restore the slice

mi_segment_span_free_coalesce(slice, tld);

return NULL;

}

return page;

}

}

}

sq++;

}

// could not find a page..

return NULL;

}

static mi_segment_t* mi_segment_os_alloc( size_t required, size_t page_alignment, bool eager_delayed, mi_arena_id_t req_arena_id,

size_t* psegment_slices, size_t* ppre_size, size_t* pinfo_slices,

bool commit, mi_segments_tld_t* tld, mi_os_tld_t* os_tld)

{

mi_memid_t memid;

bool allow_large = (!eager_delayed && (MI_SECURE == 0)); // only allow large OS pages once we are no longer lazy

size_t align_offset = 0;

size_t alignment = MI_SEGMENT_ALIGN;

if (page_alignment > 0) {

// mi_assert_internal(huge_page != NULL);

mi_assert_internal(page_alignment >= MI_SEGMENT_ALIGN);

alignment = page_alignment;

const size_t info_size = (*pinfo_slices) * MI_SEGMENT_SLICE_SIZE;

align_offset = _mi_align_up( info_size, MI_SEGMENT_ALIGN );

const size_t extra = align_offset - info_size;

// recalculate due to potential guard pages

*psegment_slices = mi_segment_calculate_slices(required + extra, ppre_size, pinfo_slices);

// mi_page_t.slice_count type is uint32_t

if (*psegment_slices > (size_t)UINT32_MAX) return NULL;

}

const size_t segment_size = (*psegment_slices) * MI_SEGMENT_SLICE_SIZE;

mi_segment_t* segment = (mi_segment_t*)_mi_arena_alloc_aligned(segment_size, alignment, align_offset, commit, allow_large, req_arena_id, &memid, os_tld);

if (segment == NULL) {

return NULL; // failed to allocate

}

// ensure metadata part of the segment is committed

mi_commit_mask_t commit_mask;

if (memid.initially_committed) {

mi_commit_mask_create_full(&commit_mask);

}

else {

// at least commit the info slices

const size_t commit_needed = _mi_divide_up((*pinfo_slices)*MI_SEGMENT_SLICE_SIZE, MI_COMMIT_SIZE);

mi_assert_internal(commit_needed>0);

mi_commit_mask_create(0, commit_needed, &commit_mask);

mi_assert_internal(commit_needed*MI_COMMIT_SIZE >= (*pinfo_slices)*MI_SEGMENT_SLICE_SIZE);

if (!_mi_os_commit(segment, commit_needed*MI_COMMIT_SIZE, NULL, tld->stats)) {

_mi_arena_free(segment,segment_size,0,memid,tld->stats);

return NULL;

}

}

mi_assert_internal(segment != NULL && (uintptr_t)segment % MI_SEGMENT_SIZE == 0);

segment->memid = memid;

segment->allow_decommit = !memid.is_pinned;

segment->allow_purge = segment->allow_decommit && (mi_option_get(mi_option_purge_delay) >= 0);

segment->segment_size = segment_size;

segment->commit_mask = commit_mask;

segment->purge_expire = 0;

mi_commit_mask_create_empty(&segment->purge_mask);

mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, NULL); // tsan

mi_segments_track_size((long)(segment_size), tld);

_mi_segment_map_allocated_at(segment);

return segment;

}

static mi_segment_t* mi_segment_alloc(size_t required, size_t page_alignment, mi_arena_id_t req_arena_id, mi_segments_tld_t* tld, mi_os_tld_t* os_tld, mi_page_t** huge_page)

{

mi_assert_internal((required==0 && huge_page==NULL) || (required>0 && huge_page != NULL));

// calculate needed sizes first

size_t info_slices;

size_t pre_size;

size_t segment_slices = mi_segment_calculate_slices(required, &pre_size, &info_slices);

// mi_page_t.slice_count type is uint32_t

if (segment_slices > (size_t)UINT32_MAX) return NULL;

// Commit eagerly only if not the first N lazy segments (to reduce impact of many threads that allocate just a little)

const bool eager_delay = (// !_mi_os_has_overcommit() && // never delay on overcommit systems

_mi_current_thread_count() > 1 && // do not delay for the first N threads

tld->count < (size_t)mi_option_get(mi_option_eager_commit_delay));

const bool eager = !eager_delay && mi_option_is_enabled(mi_option_eager_commit);

bool commit = eager || (required > 0);

// Allocate the segment from the OS

mi_segment_t* segment = mi_segment_os_alloc(required, page_alignment, eager_delay, req_arena_id,

&segment_slices, &pre_size, &info_slices, commit, tld, os_tld);

if (segment == NULL) return NULL;

// zero the segment info? -- not always needed as it may be zero initialized from the OS

if (!segment->memid.initially_zero) {

ptrdiff_t ofs = offsetof(mi_segment_t, next);

size_t prefix = offsetof(mi_segment_t, slices) - ofs;

size_t zsize = prefix + (sizeof(mi_slice_t) * (segment_slices + 1)); // one more

_mi_memzero((uint8_t*)segment + ofs, zsize);

}

// initialize the rest of the segment info

const size_t slice_entries = (segment_slices > MI_SLICES_PER_SEGMENT ? MI_SLICES_PER_SEGMENT : segment_slices);

segment->segment_slices = segment_slices;

segment->segment_info_slices = info_slices;

segment->thread_id = _mi_thread_id();

segment->cookie = _mi_ptr_cookie(segment);

segment->slice_entries = slice_entries;

segment->kind = (required == 0 ? MI_SEGMENT_NORMAL : MI_SEGMENT_HUGE);

// _mi_memzero(segment->slices, sizeof(mi_slice_t)*(info_slices+1));

_mi_stat_increase(&tld->stats->page_committed, mi_segment_info_size(segment));

// set up guard pages

size_t guard_slices = 0;

if (MI_SECURE>0) {

// in secure mode, we set up a protected page in between the segment info

// and the page data, and at the end of the segment.

size_t os_pagesize = _mi_os_page_size();

mi_assert_internal(mi_segment_info_size(segment) - os_pagesize >= pre_size);

_mi_os_protect((uint8_t*)segment + mi_segment_info_size(segment) - os_pagesize, os_pagesize);

uint8_t* end = (uint8_t*)segment + mi_segment_size(segment) - os_pagesize;

mi_segment_ensure_committed(segment, end, os_pagesize, tld->stats);

_mi_os_protect(end, os_pagesize);

if (slice_entries == segment_slices) segment->slice_entries--; // don't use the last slice :-(

guard_slices = 1;

}

// reserve first slices for segment info

mi_page_t* page0 = mi_segment_span_allocate(segment, 0, info_slices, tld);

mi_assert_internal(page0!=NULL); if (page0==NULL) return NULL; // cannot fail as we always commit in advance

mi_assert_internal(segment->used == 1);

segment->used = 0; // don't count our internal slices towards usage

// initialize initial free pages

if (segment->kind == MI_SEGMENT_NORMAL) { // not a huge page

mi_assert_internal(huge_page==NULL);

mi_segment_span_free(segment, info_slices, segment->slice_entries - info_slices, false /* don't purge */, tld);

}

else {

mi_assert_internal(huge_page!=NULL);

mi_assert_internal(mi_commit_mask_is_empty(&segment->purge_mask));

mi_assert_internal(mi_commit_mask_is_full(&segment->commit_mask));

*huge_page = mi_segment_span_allocate(segment, info_slices, segment_slices - info_slices - guard_slices, tld);