#include "mimalloc.h"
#include "mimalloc/types.h"
#include "mimalloc/prim/prim-tls.h"
#include "mimalloc/util/stats.h"
#include "mimalloc/alloc/alloc.h"
#include "mimalloc/alloc/page.h"
#include "mimalloc/profile/sample-profile.h"
#include "mimalloc/heap/subproc.h"
#include "mimalloc/heap/process.h"
#include "page-queue.h"
#include "page.h"
static inline bool mi_page_free_quick_collect(mi_page_t* page) {
if mi_likely(page->free != NULL) return true;
if (page->local_free == NULL) return false;
#if (MI_SECURE_REUSE_DELAY > 0) || (MI_SECURE_HOLD_BACK > 0)
if (!_mi_page_local_free_to_free(page)) return false;
#else
page->free = page->local_free;
page->local_free = NULL;
page->free_is_zero = mi_page_is_zero_on_free(page);
#endif
_mi_page_update_sample_countdown(page);
return true;
}
#define MI_XCOLLECT_SCORE_MAX (256)
#define MI_XCOLLECT_SCORE_SHIFT (5)
#define MI_XCOLLECT_SCORE_INC (8)
static mi_decl_noinline mi_page_t* mi_page_queue_find_free_ex(mi_theap_t* theap, mi_page_queue_t* pq, bool first_try)
{
size_t count = 0;
long candidate_limit = 0; long page_full_retain = (pq->block_size > MI_SMALL_MAX_OBJ_SIZE ? 0 : theap->page_full_retain); if (page_full_retain >= 0) {
page_full_retain += (long)(pq->xcollect_score >> MI_XCOLLECT_SCORE_SHIFT);
}
mi_page_t* page_candidate = NULL; #if (MI_SECURE_REUSE_DELAY > 0)
mi_page_t* page_delayed = NULL; size_t delayed_count = 0;
#endif
mi_page_t* page = pq->first;
mi_page_t* const last = pq->last;
while (page!=NULL)
{
mi_page_t* next = page->next; count++;
candidate_limit--;
bool immediate_available = mi_page_immediate_available(page);
if (!immediate_available) {
const bool collected_xfree = _mi_page_free_collect(page, false);
immediate_available = mi_page_immediate_available(page);
if (collected_xfree && immediate_available) {
pq->xcollect_score = mi_min(pq->xcollect_score + MI_XCOLLECT_SCORE_INC, MI_XCOLLECT_SCORE_MAX);
}
else if (pq->xcollect_score > 0) {
pq->xcollect_score--;
}
}
#if (MI_SECURE_REUSE_DELAY > 0)
if (!immediate_available && page->local_free != NULL && !mi_page_is_expandable(page)) {
if (page_delayed == NULL) { page_delayed = page; }
if (page_candidate == NULL && ++delayed_count >= MI_SECURE_REUSE_DELAY_PAGES) break;
if (page!=last && pq->last!=page) { mi_page_queue_move_to_back(theap, pq, page); }
}
else
#endif
if (!immediate_available && !mi_page_is_expandable(page)) {
page_full_retain--;
if (page_full_retain < 0) {
mi_assert_internal(!mi_page_is_in_full(page) && !mi_page_immediate_available(page));
_mi_page_to_full(page, pq);
}
else if (page!=last && pq->last!=page) {
mi_page_queue_move_to_back(theap, pq, page);
}
}
else {
if (page_candidate == NULL) {
page_candidate = page;
candidate_limit = _mi_option_get_fast(mi_option_page_max_candidates);
}
else if (mi_page_all_free(page_candidate)) {
_mi_page_free(page_candidate, pq);
page_candidate = page;
}
else if (mi_page_used(page) >= mi_page_used(page_candidate) && !mi_page_is_mostly_used(page)) { page_candidate = page;
}
if (immediate_available || candidate_limit <= 0) {
mi_assert_internal(page_candidate!=NULL);
break;
}
}
#if 0 #endif
if (page==last) { page=NULL; } else { page = next; }
}
mi_theap_stat_counter_increase(theap, page_searches, count);
mi_theap_stat_counter_increase(theap, page_searches_count, 1);
if (page_candidate != NULL) {
page = page_candidate;
}
#if (MI_SECURE_REUSE_DELAY > 0)
else if (page_delayed != NULL && delayed_count >= MI_SECURE_REUSE_DELAY_PAGES) {
_mi_page_local_free_to_free_now(page_delayed);
_mi_page_update_sample_countdown(page_delayed);
page = page_delayed;
}
#endif
if (page != NULL) {
if (!mi_page_immediate_available(page)) {
mi_assert_internal(mi_page_is_expandable(page));
if (!_mi_page_extend_free(theap, page)) {
page = NULL; }
}
mi_assert_internal(page == NULL || mi_page_immediate_available(page));
}
if (page == NULL) {
_mi_theap_collect_retired(theap, false); page = _mi_page_fresh(theap, pq);
mi_assert_internal(page == NULL || mi_page_immediate_available(page));
if (page == NULL && first_try) {
page = mi_page_queue_find_free_ex(theap, pq, false);
mi_assert_internal(page == NULL || mi_page_immediate_available(page));
}
}
else {
mi_assert_internal(page == NULL || mi_page_immediate_available(page));
mi_page_queue_move_to_front(theap, pq, page);
page->retire_expire = 0;
_mi_page_qsbr_clear(page);
}
mi_assert_internal(page == NULL || mi_page_immediate_available(page));
return page;
}
static inline mi_page_t* mi_page_queue_lookup_free_first(mi_theap_t* theap, mi_page_queue_t* pq) {
mi_assert_internal(!mi_page_queue_is_huge(pq));
mi_page_t* page = pq->first;
if mi_likely(page!=NULL && mi_page_free_quick_collect(page)) {
#if MI_SECURE_RANDOM_EXTEND
if (page->capacity < page->reserved && ((_mi_theap_random_next(theap) & 1) == 1)) {
(void)_mi_page_extend_free(theap, page); mi_assert_internal(mi_page_immediate_available(page));
}
#else
MI_UNUSED(theap);
#endif
page->retire_expire = 0;
_mi_page_qsbr_clear(page);
mi_assert_internal(mi_page_immediate_available(page));
mi_assert_internal(mi_is_aligned(mi_page_slice_start(page), MI_PAGE_ALIGN));
mi_assert_internal(mi_ptr_page(mi_page_start(page))==page);
return page;
}
else {
return NULL;
}
}
static inline mi_page_t* mi_page_queue_find_free(mi_theap_t* theap, mi_page_queue_t* pq) {
mi_assert_internal(!mi_page_queue_is_huge(pq));
mi_page_t* page = mi_page_queue_lookup_free_first(theap,pq);
if (page==NULL) {
page = mi_page_queue_find_free_ex(theap, pq, true);
if (page==NULL) return NULL;
}
mi_assert_internal(mi_page_immediate_available(page));
mi_assert_internal(mi_is_aligned(mi_page_slice_start(page), MI_PAGE_ALIGN));
mi_assert_internal(mi_ptr_page(mi_page_start(page))==page);
return page;
}
static mi_page_t* mi_huge_page_alloc(mi_theap_t* theap, size_t size, size_t page_alignment, mi_page_queue_t* pq) {
_mi_theap_qsbr_collect_delayed(theap);
_mi_theap_collect_huge_pages(theap);
const size_t block_size = mi_bounds_size(_mi_os_good_alloc_size(size));
const size_t bounds_align = mi_bounds_align(block_size);
if mi_unlikely(bounds_align >= MI_PAGE_MAX_OVERALLOC_ALIGN) {
page_alignment = mi_max(page_alignment, mi_max(bounds_align, 2*MI_PAGE_MAX_OVERALLOC_ALIGN));
}
#if MI_HUGE_PAGE_ABANDON
#error todo.
#else
mi_assert_internal(mi_page_queue_is_huge(pq));
#endif
mi_page_t* page = _mi_page_fresh_alloc(theap, pq, block_size, page_alignment);
if (page != NULL) {
mi_assert_internal(mi_page_block_size(page) >= size);
mi_assert_internal(mi_page_immediate_available(page));
mi_assert_internal(mi_page_is_huge(page));
mi_assert_internal(mi_page_is_singleton(page));
#if MI_HUGE_PAGE_ABANDON
mi_assert_internal(mi_page_is_abandoned(page));
mi_page_set_theap(page, NULL);
#endif
}
return page;
}
static mi_page_t* mi_find_page(mi_theap_t* theap, size_t size, size_t huge_alignment) mi_attr_noexcept {
const size_t req_size = size - MI_PADDING_SIZE; if mi_unlikely(req_size > MI_MAX_ALLOC_SIZE) { _mi_error_message(EOVERFLOW, "allocation request is too large (%zu bytes)\n", req_size);
return NULL;
}
mi_page_queue_t* pq = mi_page_queue(theap, (huge_alignment > 0 ? MI_LARGE_MAX_OBJ_SIZE+1 : size));
mi_page_t* page;
if mi_unlikely(mi_page_queue_is_huge(pq)) { page = mi_huge_page_alloc(theap,size,huge_alignment,pq);
}
else {
#if MI_PADDING
mi_assert_internal(size >= MI_PADDING_SIZE);
#endif
page = mi_page_queue_find_free(theap,pq);
}
if (page==NULL) return NULL;
mi_assert_internal(mi_page_block_size(page) >= size);
mi_assert_internal(mi_page_immediate_available(page));
mi_assert_internal(mi_is_aligned(mi_page_slice_start(page), MI_PAGE_ALIGN));
mi_assert_internal(mi_ptr_page(mi_page_start(page))==page);
return page;
}
void _mi_deferred_free(mi_theap_t* theap, bool force) {
theap->heartbeat++;
const mi_process_sealed_t* const sealed = mi_process_get_sealed();
if (mi_atomic_load_ptr_relaxed(void,&sealed->deferred_free) != NULL && !theap->tld->recurse) {
theap->tld->recurse = true;
void* arg;
mi_deferred_free_fun* const fun = (mi_deferred_free_fun*)_mi_process_get_callback(&sealed->deferred_free, &sealed->deferred_arg, &arg);
if (fun != NULL) { fun(force, theap->heartbeat, arg); }
theap->tld->recurse = false;
}
}
void mi_register_deferred_free(mi_deferred_free_fun* fn, void* arg) mi_attr_noexcept {
const mi_process_sealed_t* const sealed = mi_process_get_sealed();
_mi_process_set_callback(&sealed->deferred_free, &sealed->deferred_arg, (void*)fn, arg);
}
static mi_theap_t* mi_theap_init(mi_theap_t* theap) {
if mi_likely(mi_theap_is_initialized(theap)) {
return (mi_theap_handle_is_valid(theap) ? theap : NULL); }
if (theap != _mi_theap_default()) return NULL;
mi_assert_internal(!_mi_thread_is_done());
theap = _mi_thread_init();
return (mi_theap_is_initialized(theap) ? theap : NULL);
}
static mi_theap_t* mi_malloc_generic_admin(mi_theap_t* theap)
{
theap = mi_theap_init(theap);
if (theap==NULL) return NULL;
mi_assert_internal(mi_theap_is_initialized(theap));
if mi_unlikely(theap->generic_count >= 1000) {
theap->generic_collect_count += theap->generic_count;
theap->generic_count = 0;
_mi_fork_child_try_collect();
if (!theap->profile_never) {
mi_heap_t* const heap = mi_theap_heap(theap);
mi_profiler_t* prof = mi_atomic_load_ptr_acquire(mi_profiler_t, &heap->profiler);
const bool prof_enabled = (prof!=NULL && mi_profiler_is_enabled(prof));
if (prof_enabled && theap->profile_sample_rate==0) {
_mi_theap_set_profile_sample_rate(theap,mi_max(1,prof->initial_sample_rate)); }
else if (!prof_enabled && theap->profile_sample_rate!=0) {
_mi_theap_set_profile_sample_rate(theap,0); }
}
const long generic_collect = mi_option_get_clamp(mi_option_generic_collect, 1, 1000000L);
if (theap->generic_collect_count >= generic_collect) {
theap->generic_collect_count = 0;
mi_theap_collect(theap, false );
}
else {
_mi_deferred_free(theap, false); _mi_theap_collect_retired(theap, false); }
}
return theap;
}
static bool mi_malloc_generic_check_size(size_t size) {
const size_t req_size = size - MI_PADDING_SIZE;
if mi_unlikely(req_size > MI_MAX_ALLOC_SIZE - MI_PADDING_SIZE) {
_mi_error_message(EOVERFLOW, "allocation request is too large (%zu bytes)\n", req_size);
return false;
}
return true;
}
static void* mi_malloc_generic_from_page(mi_theap_t* theap, size_t size, bool zero, size_t huge_alignment, mi_page_t** ppage, size_t sample_countdown_adjust)
{
mi_page_t* page = mi_find_page(theap, size, huge_alignment);
if mi_unlikely(page == NULL) { mi_theap_collect(theap, true );
page = mi_find_page(theap, size, huge_alignment);
}
if mi_unlikely(page == NULL) { theap->sample_countdown -= sample_countdown_adjust; _mi_error_message(ENOMEM, "unable to allocate memory (%zu bytes)\n", size - MI_PADDING_SIZE);
return NULL;
}
mi_assert_internal(mi_page_immediate_available(page));
mi_assert_internal(mi_page_block_size(page) >= size);
mi_assert_internal(mi_is_aligned(mi_page_slice_start(page), MI_PAGE_ALIGN));
mi_assert_internal(mi_ptr_page(mi_page_start(page))==page);
if (ppage!=NULL) { *ppage = page; }
void* const p = _mi_page_malloc_zero(theap,page,size,zero);
mi_assert_internal(p != NULL);
_mi_page_update_sample_countdown(page);
if (mi_page_block_size(page) > MI_SMALL_MAX_OBJ_SIZE) {
if (mi_page_is_full(page)) {
_mi_page_to_full(page, mi_page_queue_of(page));
}
}
return p;
}
static mi_decl_noinline void* mi_malloc_generic_sample(mi_theap_t* theap, size_t size, bool zero, size_t huge_alignment, mi_page_t** ppage)
{
const size_t req_size = size - MI_PADDING_SIZE;
if (huge_alignment==0 && theap->sample_rate!=0) {
return _mi_theap_malloc_sampled(theap,req_size,zero,ppage);
}
mi_assert_internal(!_mi_is_empty_theap(theap)); mi_assert_internal(req_size <= MI_SAMPLE_COUNTDOWN_MAX);
size_t sample_countdown_adjust = 0;
if (theap->sample_rate==0) {
theap->sample_countdown = MI_SAMPLE_COUNTDOWN_MAX; }
#if MI_SAMPLE==2
else {
mi_assert_internal(huge_alignment!=0);
mi_assert_internal(theap->sample_countdown <= SIZE_MAX - req_size);
sample_countdown_adjust = req_size;
theap->sample_countdown += req_size; }
#endif
return mi_malloc_generic_from_page(theap, size, zero, huge_alignment, ppage, sample_countdown_adjust);
}
static mi_decl_noinline void* mi_malloc_generic_thread_done(size_t size, size_t huge_alignment, mi_page_t** ppage)
{
mi_subproc_t* const subproc = _mi_subproc();
const size_t req_size = size - MI_PADDING_SIZE;
void* const p = (huge_alignment==0 ? _mi_meta_zalloc(subproc, req_size, NULL) : _mi_meta_zalloc_aligned(subproc, req_size, huge_alignment, NULL));
if (p!=NULL && ppage!=NULL) { *ppage = mi_ptr_page(p); }
return p;
}
static bool mi_theap_is_thread_done(const mi_theap_t* theap) {
return (_mi_theap_is_unavailable(theap) && _mi_thread_is_done());
}
static inline void* mi_malloc_generic_fallback_ex(mi_theap_t* theap, size_t size, bool zero, size_t huge_alignment, mi_page_t** ppage)
{
if mi_unlikely(mi_theap_is_thread_done(theap)) {
return mi_malloc_generic_thread_done(size, huge_alignment, ppage);
}
theap = mi_malloc_generic_admin(theap);
if (theap==NULL) return NULL;
if (!mi_malloc_generic_check_size(size)) return NULL;
if mi_unlikely(mi_theap_should_sample(theap, size - MI_PADDING_SIZE)) {
return mi_malloc_generic_sample(theap, size, zero, huge_alignment, ppage);
}
else {
return mi_malloc_generic_from_page(theap, size, zero, huge_alignment, ppage, 0);
}
}
static mi_decl_noinline void* mi_malloc_generic_fallback(mi_theap_t* theap, size_t size, bool zero, size_t huge_alignment, mi_page_t** ppage)
{
void* const p = mi_malloc_generic_fallback_ex(theap, size, zero, huge_alignment, ppage);
if mi_unlikely(p==NULL) { errno = ENOMEM; }
return p;
}
mi_decl_restrict void* _mi_malloc_generic(mi_theap_t* theap, size_t size, size_t zero_huge_alignment, mi_page_t** ppage) mi_attr_noexcept
{
#if !MI_THEAP_INITASNULL
mi_assert_internal(theap != NULL);
#endif
const bool zero = ((zero_huge_alignment & 1) != 0);
const size_t huge_alignment = (zero_huge_alignment & ~1);
mi_assert_internal(huge_alignment==0 || huge_alignment > MI_PAGE_MAX_OVERALLOC_ALIGN);
mi_page_t* page = NULL;
if mi_likely(mi_theap_is_initialized(theap) && mi_theap_has_valid_cookie(theap) && ++theap->generic_count < 1000 && huge_alignment==0) { const size_t req_size = size - MI_PADDING_SIZE; if (req_size < MI_SMALL_MAX_OBJ_SIZE)
{
#if MI_SAMPLE
if mi_likely(!mi_theap_should_sample(theap,req_size)) #endif
{
mi_page_queue_t* pq = mi_page_queue(theap, size);
mi_assert_internal(pq!=NULL && !mi_page_queue_is_huge(pq));
page = mi_page_queue_find_free(theap,pq);
if (page!=NULL) {
if (ppage!=NULL) { *ppage = page; }
mi_assert_internal(mi_page_immediate_available(page)); void* p = _mi_page_malloc_zero(theap,page,size,zero); mi_assert_internal(p != NULL);
return p;
}
}
}
}
return mi_malloc_generic_fallback(theap,size,zero,huge_alignment,ppage);
}
mi_decl_restrict void* _mi_malloc_generic_no_sample(mi_theap_t* theap, size_t size, bool zero, mi_page_t** ppage) mi_attr_noexcept
{
if mi_unlikely(mi_theap_is_thread_done(theap)) {
return mi_malloc_generic_thread_done(size, 0, ppage);
}
theap = mi_malloc_generic_admin(theap);
if (theap==NULL) return NULL;
if (!mi_malloc_generic_check_size(size)) return NULL;
const size_t sample_countdown = theap->sample_countdown;
theap->sample_countdown = MI_SAMPLE_COUNTDOWN_MAX; mi_page_t* page = NULL;
void* p = mi_malloc_generic_from_page(theap, size, zero, 0, &page, 0);
if (ppage!=NULL) { *ppage = page; }
const size_t counted = MI_SAMPLE_COUNTDOWN_MAX - theap->sample_countdown;
#if MI_SAMPLE==1
const size_t self = (p==NULL ? 0 : mi_page_usable_block_size(page)); #else
const size_t self = (p==NULL ? 0 : size - MI_PADDING_SIZE);
#endif
theap->sample_countdown = (theap->sample_rate!=0 && sample_countdown > theap->sample_rate ? theap->sample_rate : sample_countdown);
if (counted > self) { mi_theap_sample_countdown_sub(theap, counted - self); }
return p;
}