/*

* Copyright 2018 The Emscripten Authors. All rights reserved.

* Emscripten is available under two separate licenses, the MIT license and the

* University of Illinois/NCSA Open Source License. Both these licenses can be

* found in the LICENSE file.

*

* Simple minimalistic but efficient sbrk()-based malloc/free that works in

* singlethreaded and multithreaded builds.

*

* Assumptions:

*

* - Pointers are 32-bit.

* - Maximum individual allocation size is 2GB-1 bytes (2147483647 bytes)

* - sbrk() is used to claim new memory (sbrk handles geometric/linear

* - overallocation growth)

* - sbrk() can be used by other code outside emmalloc.

* - sbrk() is very fast in most cases (internal wasm call).

*

* Invariants:

*

* - Per-allocation header overhead is 8 bytes, smallest allocated payload

* amount is 8 bytes, and a multiple of 4 bytes.

* - Acquired memory blocks are subdivided into disjoint regions that lie

* next to each other.

* - A region is either in used or free.

* Used regions may be adjacent, and a used and unused region

* may be adjacent, but not two unused ones - they would be

* merged.

* - Memory allocation takes constant time, unless the alloc needs to sbrk()

* or memory is very close to being exhausted.

*

* Debugging:

*

* - If not NDEBUG, runtime assert()s are in use.

* - If EMMALLOC_DEBUG is defined, a large amount of extra checks are done.

* - If EMMALLOC_DEBUG_LOG is defined, a lot of operations are logged

* out, in addition to EMMALLOC_DEBUG.

* - Debugging and logging directly uses console.log via uses EM_ASM, not

* printf etc., to minimize any risk of debugging or logging depending on

* malloc.

*/

#include <stdint.h>

#include <unistd.h>

#include <memory.h>

#include <assert.h>

#include <malloc.h>

#include <emscripten.h>

#include <emscripten/heap.h>

#include <emscripten/threading.h>

#ifdef __EMSCRIPTEN_TRACING__

#include <emscripten/trace.h>

#endif

// Behavior of right shifting a signed integer is compiler implementation defined.

static_assert((((int32_t)0x80000000U) >> 31) == -1, "This malloc implementation requires that right-shifting a signed integer produces a sign-extending (arithmetic) shift!");

extern "C"

{

// Configuration: specifies the minimum alignment that malloc()ed memory outputs. Allocation requests with smaller alignment

// than this will yield an allocation with this much alignment.

#define MALLOC_ALIGNMENT 8

// Configuration: If EMMALLOC_USE_64BIT_OPS is specified, emmalloc uses 64 buckets for free memory regions instead of just 32.

// When building to target asm.js/wasm2js, 64-bit ops are disabled, but in Wasm builds, 64-bit ops are enabled. (this is

// configured from command line in system_libs.py build)

// #define EMMALLOC_USE_64BIT_OPS

#define EMMALLOC_EXPORT __attribute__((weak, __visibility__("default")))

#define MIN(x, y) ((x) < (y) ? (x) : (y))

#define MAX(x, y) ((x) > (y) ? (x) : (y))

#ifdef EMMALLOC_USE_64BIT_OPS

#define NUM_FREE_BUCKETS 64

#define BUCKET_BITMASK_T uint64_t

#define CountLeadingZeroesInBitmask __builtin_clzll

#define CountTrailingZeroesInBitmask __builtin_ctzll

#else

#define NUM_FREE_BUCKETS 32

#define BUCKET_BITMASK_T uint32_t

#define CountLeadingZeroesInBitmask __builtin_clz

#define CountTrailingZeroesInBitmask __builtin_ctz

#endif

// Dynamic memory is subdivided into regions, in the format

// <size:uint32_t> ..... <size:uint32_t> | <size:uint32_t> ..... <size:uint32_t> | <size:uint32_t> ..... <size:uint32_t> | .....

// That is, at the bottom and top end of each memory region, the size of that region is stored. That allows traversing the

// memory regions backwards and forwards. Free regions are distinguished by used regions by having all bits inverted in the size

// field at the end of the region. Hence if the size values at the beginning and at the end of the region are the same, then the

// region is in use, otherwise it is a free region.

// A free region has the following structure:

// <size:uint32_t> <prevptr> <nextptr> ... <size:uint32_t>

struct Region

{

uint32_t size;

// Use a circular doubly linked list to represent free region data.

Region *prev, *next;

// ... N bytes of free data

uint32_t _at_the_end_of_this_struct_size; // do not dereference, this is present for convenient struct sizeof() computation only

};

#if defined(__EMSCRIPTEN_PTHREADS__)

// In multithreaded builds, use a simple global spinlock strategy to acquire/release access to the memory allocator.

static volatile uint8_t multithreadingLock = 0;

#define MALLOC_ACQUIRE() while(__sync_lock_test_and_set(&multithreadingLock, 1)) { while(multithreadingLock) { /*nop*/ } }

#define MALLOC_RELEASE() __sync_lock_release(&multithreadingLock)

// Test code to ensure we have tight malloc acquire/release guards in place.

#define ASSERT_MALLOC_IS_ACQUIRED() assert(multithreadingLock == 1)

#else

// In singlethreaded builds, no need for locking.

#define MALLOC_ACQUIRE() ((void)0)

#define MALLOC_RELEASE() ((void)0)

#define ASSERT_MALLOC_IS_ACQUIRED() ((void)0)

#endif

#define IS_POWER_OF_2(val) (((val) & ((val)-1)) == 0)

#define ALIGN_UP(ptr, alignment) ((uint8_t*)((((uintptr_t)(ptr)) + ((alignment)-1)) & ~((alignment)-1)))

#define HAS_ALIGNMENT(ptr, alignment) ((((uintptr_t)(ptr)) & ((alignment)-1)) == 0)

static_assert(IS_POWER_OF_2(MALLOC_ALIGNMENT), "MALLOC_ALIGNMENT must be a power of two value!");

static_assert(MALLOC_ALIGNMENT >= 4, "Smallest possible MALLOC_ALIGNMENT if 4!");

// A region that contains as payload a single forward linked list of pointers to head regions of each disjoint region blocks.

static Region *listOfAllRegions = 0;

// For each of the buckets, maintain a linked list head node. The head node for each

// free region is a sentinel node that does not actually represent any free space, but

// the sentinel is used to avoid awkward testing against (if node == freeRegionHeadNode)

// when adding and removing elements from the linked list, i.e. we are guaranteed that

// the sentinel node is always fixed and there, and the actual free region list elements

// start at freeRegionBuckets[i].next each.

static Region freeRegionBuckets[NUM_FREE_BUCKETS];

// A bitmask that tracks the population status for each of the 32 distinct memory regions:

// a zero at bit position i means that the free list bucket i is empty. This bitmask is

// used to avoid redundant scanning of the 32 different free region buckets: instead by

// looking at the bitmask we can find in constant time an index to a free region bucket

// that contains free memory of desired size.

static BUCKET_BITMASK_T freeRegionBucketsUsed = 0;

// Amount of bytes taken up by allocation header data

#define REGION_HEADER_SIZE (2*sizeof(uint32_t))

// Smallest allocation size that is possible is 2*pointer size, since payload of each region must at least contain space

// to store the free region linked list prev and next pointers. An allocation size smaller than this will be rounded up

// to this size.

#define SMALLEST_ALLOCATION_SIZE (2*sizeof(void*))

/* Subdivide regions of free space into distinct circular doubly linked lists, where each linked list

represents a range of free space blocks. The following function compute_free_list_bucket() converts

an allocation size to the bucket index that should be looked at.

When using 32 buckets, this function produces a subdivision/grouping as follows:

Bucket 0: [8-15], range size=8

Bucket 1: [16-23], range size=8

Bucket 2: [24-31], range size=8

Bucket 3: [32-39], range size=8

Bucket 4: [40-47], range size=8

Bucket 5: [48-63], range size=16

Bucket 6: [64-127], range size=64

Bucket 7: [128-255], range size=128

Bucket 8: [256-511], range size=256

Bucket 9: [512-1023], range size=512

Bucket 10: [1024-2047], range size=1024

Bucket 11: [2048-3071], range size=1024

Bucket 12: [3072-4095], range size=1024

Bucket 13: [4096-6143], range size=2048

Bucket 14: [6144-8191], range size=2048

Bucket 15: [8192-12287], range size=4096

Bucket 16: [12288-16383], range size=4096

Bucket 17: [16384-24575], range size=8192

Bucket 18: [24576-32767], range size=8192

Bucket 19: [32768-49151], range size=16384

Bucket 20: [49152-65535], range size=16384

Bucket 21: [65536-98303], range size=32768

Bucket 22: [98304-131071], range size=32768

Bucket 23: [131072-196607], range size=65536

Bucket 24: [196608-262143], range size=65536

Bucket 25: [262144-393215], range size=131072

Bucket 26: [393216-524287], range size=131072

Bucket 27: [524288-786431], range size=262144

Bucket 28: [786432-1048575], range size=262144

Bucket 29: [1048576-1572863], range size=524288

Bucket 30: [1572864-2097151], range size=524288

Bucket 31: 2097152 bytes and larger.

When using 64 buckets, this function produces a grouping as follows:

Bucket 0: [8, 15], range size=8

Bucket 1: [16, 23], range size=8

Bucket 2: [24, 31], range size=8

Bucket 3: [32, 39], range size=8

Bucket 4: [40, 47], range size=8

Bucket 5: [48, 55], range size=8

Bucket 6: [56, 63], range size=8

Bucket 7: [64, 71], range size=8

Bucket 8: [72, 79], range size=8

Bucket 9: [80, 87], range size=8

Bucket 10: [88, 95], range size=8

Bucket 11: [96, 103], range size=8

Bucket 12: [104, 111], range size=8

Bucket 13: [112, 119], range size=8

Bucket 14: [120, 159], range size=40

Bucket 15: [160, 191], range size=32

Bucket 16: [192, 223], range size=32

Bucket 17: [224, 255], range size=32

Bucket 18: [256, 319], range size=64

Bucket 19: [320, 383], range size=64

Bucket 20: [384, 447], range size=64

Bucket 21: [448, 511], range size=64

Bucket 22: [512, 639], range size=128

Bucket 23: [640, 767], range size=128

Bucket 24: [768, 895], range size=128

Bucket 25: [896, 1023], range size=128

Bucket 26: [1024, 1279], range size=256

Bucket 27: [1280, 1535], range size=256

Bucket 28: [1536, 1791], range size=256

Bucket 29: [1792, 2047], range size=256

Bucket 30: [2048, 2559], range size=512

Bucket 31: [2560, 3071], range size=512

Bucket 32: [3072, 3583], range size=512

Bucket 33: [3584, 6143], range size=2560

Bucket 34: [6144, 8191], range size=2048

Bucket 35: [8192, 12287], range size=4096

Bucket 36: [12288, 16383], range size=4096

Bucket 37: [16384, 24575], range size=8192

Bucket 38: [24576, 32767], range size=8192

Bucket 39: [32768, 49151], range size=16384

Bucket 40: [49152, 65535], range size=16384

Bucket 41: [65536, 98303], range size=32768

Bucket 42: [98304, 131071], range size=32768

Bucket 43: [131072, 196607], range size=65536

Bucket 44: [196608, 262143], range size=65536

Bucket 45: [262144, 393215], range size=131072

Bucket 46: [393216, 524287], range size=131072

Bucket 47: [524288, 786431], range size=262144

Bucket 48: [786432, 1048575], range size=262144

Bucket 49: [1048576, 1572863], range size=524288

Bucket 50: [1572864, 2097151], range size=524288

Bucket 51: [2097152, 3145727], range size=1048576

Bucket 52: [3145728, 4194303], range size=1048576

Bucket 53: [4194304, 6291455], range size=2097152

Bucket 54: [6291456, 8388607], range size=2097152

Bucket 55: [8388608, 12582911], range size=4194304

Bucket 56: [12582912, 16777215], range size=4194304

Bucket 57: [16777216, 25165823], range size=8388608

Bucket 58: [25165824, 33554431], range size=8388608

Bucket 59: [33554432, 50331647], range size=16777216

Bucket 60: [50331648, 67108863], range size=16777216

Bucket 61: [67108864, 100663295], range size=33554432

Bucket 62: [100663296, 134217727], range size=33554432

Bucket 63: 134217728 bytes and larger. */

static int compute_free_list_bucket(uint32_t allocSize)

{

#if NUM_FREE_BUCKETS == 32

if (allocSize < 48) return (allocSize >> 3) - 1;

int clz = __builtin_clz(allocSize);

int bucketIndex = (clz > 20) ? 31 - clz : MIN(51 - (clz<<1) + ((allocSize >> (30-clz)) ^ 2), NUM_FREE_BUCKETS-1);

#elif NUM_FREE_BUCKETS == 64

if (allocSize < 128) return (allocSize >> 3) - 1;

int clz = __builtin_clz(allocSize);

int bucketIndex = (clz > 19) ? 110 - (clz<<2) + ((allocSize >> (29-clz)) ^ 4) : MIN(71 - (clz<<1) + ((allocSize >> (30-clz)) ^ 2), NUM_FREE_BUCKETS-1);

#else

#error Invalid size chosen for NUM_FREE_BUCKETS

#endif

assert(bucketIndex >= 0);

assert(bucketIndex < NUM_FREE_BUCKETS);

return bucketIndex;

}

#define DECODE_CEILING_SIZE(size) (uint32_t)(((size) ^ (((int32_t)(size)) >> 31)))

static Region *prev_region(Region *region)

{

uint32_t prevRegionSize = ((uint32_t*)region)[-1];

prevRegionSize = DECODE_CEILING_SIZE(prevRegionSize);

return (Region*)((uint8_t*)region - prevRegionSize);

}

static Region *next_region(Region *region)

{

return (Region*)((uint8_t*)region + region->size);

}

static uint32_t region_ceiling_size(Region *region)

{

return ((uint32_t*)((uint8_t*)region + region->size))[-1];

}

static bool region_is_free(Region *r)

{

return region_ceiling_size(r) >> 31;

}

static bool region_is_in_use(Region *r)

{

return r->size == region_ceiling_size(r);

}

static uint32_t size_of_region_from_ceiling(Region *r)

{

uint32_t size = region_ceiling_size(r);

return DECODE_CEILING_SIZE(size);

}

static bool debug_region_is_consistent(Region *r)

{

assert(r);

uint32_t sizeAtBottom = r->size;

uint32_t sizeAtCeiling = size_of_region_from_ceiling(r);

return sizeAtBottom == sizeAtCeiling;

}

static uint8_t *region_payload_start_ptr(Region *region)

{

return (uint8_t*)region + sizeof(uint32_t);

}

static uint8_t *region_payload_end_ptr(Region *region)

{

return (uint8_t*)region + region->size - sizeof(uint32_t);

}

static void create_used_region(void *ptr, uint32_t size)

{

assert(ptr);

assert(HAS_ALIGNMENT(ptr, sizeof(uint32_t)));

assert(HAS_ALIGNMENT(size, sizeof(uint32_t)));

assert(size >= sizeof(Region));

*(uint32_t*)ptr = size;

((uint32_t*)ptr)[(size>>2)-1] = size;

}

static void create_free_region(void *ptr, uint32_t size)

{

assert(ptr);

assert(HAS_ALIGNMENT(ptr, sizeof(uint32_t)));

assert(HAS_ALIGNMENT(size, sizeof(uint32_t)));

assert(size >= sizeof(Region));

Region *freeRegion = (Region*)ptr;

freeRegion->size = size;

((uint32_t*)ptr)[(size>>2)-1] = ~size;

}

static void prepend_to_free_list(Region *region, Region *prependTo)

{

assert(region);

assert(prependTo);

// N.b. the region we are prepending to is always the sentinel node,

// which represents a dummy node that is technically not a free node, so

// region_is_free(prependTo) does not hold.

assert(region_is_free((Region*)region));

region->next = prependTo;

region->prev = prependTo->prev;

assert(region->prev);

prependTo->prev = region;

region->prev->next = region;

}

static void unlink_from_free_list(Region *region)

{

assert(region);

assert(region_is_free((Region*)region));

assert(region->prev);

assert(region->next);

region->prev->next = region->next;

region->next->prev = region->prev;

}

static void link_to_free_list(Region *freeRegion)

{

assert(freeRegion);

assert(freeRegion->size >= sizeof(Region));

int bucketIndex = compute_free_list_bucket(freeRegion->size-REGION_HEADER_SIZE);

Region *freeListHead = freeRegionBuckets + bucketIndex;

freeRegion->prev = freeListHead;

freeRegion->next = freeListHead->next;

assert(freeRegion->next);

freeListHead->next = freeRegion;

freeRegion->next->prev = freeRegion;

freeRegionBucketsUsed |= ((BUCKET_BITMASK_T)1) << bucketIndex;

}

static void dump_memory_regions()

{

ASSERT_MALLOC_IS_ACQUIRED();

Region *root = listOfAllRegions;

MAIN_THREAD_ASYNC_EM_ASM(console.log('All memory regions:'));

while(root)

{

Region *r = root;

assert(debug_region_is_consistent(r));

uint8_t *lastRegionEnd = (uint8_t*)(((uint32_t*)root)[2]);

MAIN_THREAD_ASYNC_EM_ASM(console.log('Region block '+$0.toString(16)+'-'+$1.toString(16)+ ' ('+$2+' bytes):'),

r, lastRegionEnd, lastRegionEnd-(uint8_t*)r);

while((uint8_t*)r < lastRegionEnd)

{

MAIN_THREAD_ASYNC_EM_ASM(console.log('Region '+$0.toString(16)+', size: '+$1+' ('+($2?"used":"--FREE--")+')'),

r, r->size, region_ceiling_size(r) == r->size);

assert(debug_region_is_consistent(r));

uint32_t sizeFromCeiling = size_of_region_from_ceiling(r);

if (sizeFromCeiling != r->size)

MAIN_THREAD_ASYNC_EM_ASM(console.log('Corrupt region! Size marker at the end of the region does not match: '+$0), sizeFromCeiling);

if (r->size == 0)

break;

r = next_region(r);

}

root = ((Region*)((uint32_t*)root)[1]);

MAIN_THREAD_ASYNC_EM_ASM(console.log(""));

}

MAIN_THREAD_ASYNC_EM_ASM(console.log('Free regions:'));

for(int i = 0; i < NUM_FREE_BUCKETS; ++i)

{

Region *prev = &freeRegionBuckets[i];

Region *fr = freeRegionBuckets[i].next;

while(fr != &freeRegionBuckets[i])

{

MAIN_THREAD_ASYNC_EM_ASM(console.log('In bucket '+$0+', free region '+$1.toString(16)+', size: ' + $2 + ' (size at ceiling: '+$3+'), prev: ' + $4.toString(16) + ', next: ' + $5.toString(16)),

i, fr, fr->size, size_of_region_from_ceiling(fr), fr->prev, fr->next);

assert(debug_region_is_consistent(fr));

assert(region_is_free(fr));

assert(fr->prev == prev);

prev = fr;

assert(fr->next != fr);

assert(fr->prev != fr);

fr = fr->next;

}

}

#if NUM_FREE_BUCKETS == 64

MAIN_THREAD_ASYNC_EM_ASM(console.log('Free bucket index map: ' + ($0>>>0).toString(2) + ' ' + ($1>>>0).toString(2)), (uint32_t)(freeRegionBucketsUsed >> 32), (uint32_t)freeRegionBucketsUsed);

#else

MAIN_THREAD_ASYNC_EM_ASM(console.log('Free bucket index map: ' + ($0>>>0).toString(2)), freeRegionBucketsUsed);

#endif

MAIN_THREAD_ASYNC_EM_ASM(console.log(""));

}

void emmalloc_dump_memory_regions()

{

MALLOC_ACQUIRE();

dump_memory_regions();

MALLOC_RELEASE();

}

static int validate_memory_regions()

{

ASSERT_MALLOC_IS_ACQUIRED();

Region *root = listOfAllRegions;

while(root)

{

Region *r = root;

if (!debug_region_is_consistent(r))

{

MAIN_THREAD_ASYNC_EM_ASM(console.error('Used region '+$0.toString(16)+', size: '+$1+' ('+($2?"used":"--FREE--")+') is corrupt (size markers in the beginning and at the end of the region do not match!)'),

r, r->size, region_ceiling_size(r) == r->size);

return 1;

}

uint8_t *lastRegionEnd = (uint8_t*)(((uint32_t*)root)[2]);

while((uint8_t*)r < lastRegionEnd)

{

if (!debug_region_is_consistent(r))

{

MAIN_THREAD_ASYNC_EM_ASM(console.error('Used region '+$0.toString(16)+', size: '+$1+' ('+($2?"used":"--FREE--")+') is corrupt (size markers in the beginning and at the end of the region do not match!)'),

r, r->size, region_ceiling_size(r) == r->size);

return 1;

}

if (r->size == 0)

break;

r = next_region(r);

}

root = ((Region*)((uint32_t*)root)[1]);

}

for(int i = 0; i < NUM_FREE_BUCKETS; ++i)

{

Region *prev = &freeRegionBuckets[i];

Region *fr = freeRegionBuckets[i].next;

while(fr != &freeRegionBuckets[i])

{

if (!debug_region_is_consistent(fr) || !region_is_free(fr) || fr->prev != prev || fr->next == fr || fr->prev == fr)

{

MAIN_THREAD_ASYNC_EM_ASM(console.log('In bucket '+$0+', free region '+$1.toString(16)+', size: ' + $2 + ' (size at ceiling: '+$3+'), prev: ' + $4.toString(16) + ', next: ' + $5.toString(16) + ' is corrupt!'),

i, fr, fr->size, size_of_region_from_ceiling((Region*)fr), fr->prev, fr->next);

return 1;

}

prev = fr;

fr = fr->next;

}

}

return 0;

}

int emmalloc_validate_memory_regions()

{

MALLOC_ACQUIRE();

int memoryError = validate_memory_regions();

MALLOC_RELEASE();

return memoryError;

}

static bool claim_more_memory(size_t numBytes)

{

#ifdef EMMALLOC_DEBUG_LOG

MAIN_THREAD_ASYNC_EM_ASM(console.log('claim_more_memory(numBytes='+$0+ ')'), numBytes);

#endif

#ifdef EMMALLOC_DEBUG

validate_memory_regions();

#endif

// Claim memory via sbrk

uint8_t *startPtr = (uint8_t*)sbrk(numBytes);

if ((intptr_t)startPtr <= 0)

{

#ifdef EMMALLOC_DEBUG_LOG

MAIN_THREAD_ASYNC_EM_ASM(console.error('claim_more_memory - sbrk failed!'));

#endif

return false;

}

#ifdef EMMALLOC_DEBUG_LOG

MAIN_THREAD_ASYNC_EM_ASM(console.log('claim_more_memory - claimed ' + $0.toString(16) + '-' + $1.toString(16) + ' (' + $2 + ' bytes) via sbrk()'), startPtr, startPtr + numBytes, numBytes);

#endif

assert(HAS_ALIGNMENT(startPtr, 4));

uint8_t *endPtr = startPtr + numBytes;

// Create a sentinel region at the end of the new heap block

Region *endSentinelRegion = (Region*)(endPtr - sizeof(Region));

create_used_region(endSentinelRegion, sizeof(Region));

// If we are the sole user of sbrk(), it will feed us continuous/consecutive memory addresses - take advantage

// of that if so: instead of creating two disjoint memory regions blocks, expand the previous one to a larger size.

uint8_t *previousSbrkEndAddress = listOfAllRegions ? (uint8_t*)((uint32_t*)listOfAllRegions)[2] : 0;

if (startPtr == previousSbrkEndAddress)

{

Region *prevEndSentinel = prev_region((Region*)startPtr);

assert(debug_region_is_consistent(prevEndSentinel));

assert(region_is_in_use(prevEndSentinel));

Region *prevRegion = prev_region(prevEndSentinel);

assert(debug_region_is_consistent(prevRegion));

((uint32_t*)listOfAllRegions)[2] = (uint32_t)endPtr;

// Two scenarios, either the last region of the previous block was in use, in which case we need to create

// a new free region in the newly allocated space; or it was free, in which case we can extend that region

// to cover a larger size.

if (region_is_free(prevRegion))

{

size_t newFreeRegionSize = (uint8_t*)endSentinelRegion - (uint8_t*)prevRegion;

unlink_from_free_list(prevRegion);

create_free_region(prevRegion, newFreeRegionSize);

link_to_free_list(prevRegion);

return true;

}

// else: last region of the previous block was in use. Since we are joining two consecutive sbrk() blocks,

// we can swallow the end sentinel of the previous block away.

startPtr -= sizeof(Region);

}

else

{

// Create a sentinel region at the start of the heap block

create_used_region(startPtr, sizeof(Region));

// Dynamic heap start region:

Region *newRegionBlock = (Region*)startPtr;

((uint32_t*)newRegionBlock)[1] = (uint32_t)listOfAllRegions; // Pointer to next region block head

((uint32_t*)newRegionBlock)[2] = (uint32_t)endPtr; // Pointer to the end address of this region block

listOfAllRegions = newRegionBlock;

startPtr += sizeof(Region);

}

// Create a new memory region for the new claimed free space.

create_free_region(startPtr, (uint8_t*)endSentinelRegion - startPtr);

link_to_free_list((Region*)startPtr);

return true;

}

// Initialize malloc during static initialization with highest constructor priority,

// so that it initializes before any other static initializers in compilation units.

static void EMSCRIPTEN_KEEPALIVE __attribute__((constructor(0))) initialize_malloc_heap()

{

#if __EMSCRIPTEN_PTHREADS__

// This function should be called on the main thread before any pthreads have been

// established to initialize the malloc subsystem. (so no lock acquire needed)

assert(emscripten_is_main_runtime_thread());

#endif

// Initialize circular doubly linked lists representing free space

#pragma clang loop unroll(disable) // Never useful to unroll this for loop, just takes up code size.

for(int i = 0; i < NUM_FREE_BUCKETS; ++i)

freeRegionBuckets[i].prev = freeRegionBuckets[i].next = &freeRegionBuckets[i];

#ifdef EMMALLOC_DEBUG_LOG

MAIN_THREAD_ASYNC_EM_ASM(console.log('initialize_malloc_heap()'));

#endif

// Start with a tiny dynamic region.

claim_more_memory(3*sizeof(Region));

}

void emmalloc_blank_slate_from_orbit()

{

listOfAllRegions = 0;

freeRegionBucketsUsed = 0;

initialize_malloc_heap();

}

static void *attempt_allocate(Region *freeRegion, size_t alignment, size_t size)

{

ASSERT_MALLOC_IS_ACQUIRED();

assert(freeRegion);

// Look at the next potential free region to allocate into.

// First, we should check if the free region has enough of payload bytes contained

// in it to accommodate the new allocation. This check needs to take account the

// requested allocation alignment, so the payload memory area needs to be rounded

// upwards to the desired alignment.

uint8_t *payloadStartPtr = region_payload_start_ptr(freeRegion);

uint8_t *payloadStartPtrAligned = ALIGN_UP(payloadStartPtr, alignment);

uint8_t *payloadEndPtr = region_payload_end_ptr(freeRegion);

// Do we have enough free space, taking into account alignment?

if (payloadStartPtrAligned + size > payloadEndPtr)

return 0;

// We have enough free space, so the memory allocation will be made into this region. Remove this free region

// from the list of free regions: whatever slop remains will be later added back to the free region pool.

unlink_from_free_list(freeRegion);

// Before we proceed further, fix up the boundary of this region and the region that precedes this one,

// so that the boundary between the two regions happens at a right spot for the payload to be aligned.

if (payloadStartPtr != payloadStartPtrAligned)

{

Region *prevRegion = prev_region((Region*)freeRegion);

// We never have two free regions adjacent to each other, so the region before this free

// region should be in use.

assert(region_is_in_use(prevRegion));

size_t regionBoundaryBumpAmount = payloadStartPtrAligned - payloadStartPtr;

size_t newThisRegionSize = freeRegion->size - regionBoundaryBumpAmount;

create_used_region(prevRegion, prevRegion->size + regionBoundaryBumpAmount);

freeRegion = (Region *)((uint8_t*)freeRegion + regionBoundaryBumpAmount);

freeRegion->size = newThisRegionSize;

}

// Next, we need to decide whether this region is so large that it should be split into two regions,

// one representing the newly used memory area, and at the high end a remaining leftover free area.

// This splitting to two is done always if there is enough space for the high end to fit a region.

// Carve 'size' bytes of payload off this region. So,

// [sz prev next sz]

// becomes

// [sz payload sz] [sz prev next sz]

if (sizeof(Region) + REGION_HEADER_SIZE + size <= freeRegion->size)

{

// There is enough space to keep a free region at the end of the carved out block

// -> construct the new block

Region *newFreeRegion = (Region *)((uint8_t*)freeRegion + REGION_HEADER_SIZE + size);

create_free_region(newFreeRegion, freeRegion->size - size - REGION_HEADER_SIZE);

link_to_free_list(newFreeRegion);

// Recreate the resized Region under its new size.

create_used_region(freeRegion, size + REGION_HEADER_SIZE);

}

else

{

// There is not enough space to split the free memory region into used+free parts, so consume the whole

// region as used memory, not leaving a free memory region behind.

// Initialize the free region as used by resetting the ceiling size to the same value as the size at bottom.

((uint32_t*)((uint8_t*)freeRegion + freeRegion->size))[-1] = freeRegion->size;

}

#ifdef __EMSCRIPTEN_TRACING__

emscripten_trace_record_allocation(freeRegion, freeRegion->size);

#endif

#ifdef EMMALLOC_DEBUG_LOG

MAIN_THREAD_ASYNC_EM_ASM(console.log('attempt_allocate - succeeded allocating memory, region ptr=' + $0.toString(16) + ', align=' + $1 + ', payload size=' + $2 + ' bytes)'), freeRegion, alignment, size);

#endif

return (uint8_t*)freeRegion + sizeof(uint32_t);

}

static size_t validate_alloc_alignment(size_t alignment)

{

// Cannot perform allocations that are less than 4 byte aligned, because the Region

// control structures need to be aligned. Also round up to minimum outputted alignment.

alignment = MAX(alignment, MALLOC_ALIGNMENT);

// Arbitrary upper limit on alignment - very likely a programming bug if alignment is higher than this.

assert(alignment <= 1024*1024);

return alignment;

}

static size_t validate_alloc_size(size_t size)

{

// Allocation sizes must be a multiple of pointer sizes, and at least 2*sizeof(pointer).

return size > 2*sizeof(Region*) ? (size_t)ALIGN_UP(size, sizeof(Region*)) : 2*sizeof(Region*);

}

static void *allocate_memory(size_t alignment, size_t size)

{

ASSERT_MALLOC_IS_ACQUIRED();

#ifdef EMMALLOC_DEBUG_LOG

MAIN_THREAD_ASYNC_EM_ASM(console.log('allocate_memory(align=' + $0 + ', size=' + $1 + ' bytes)'), alignment, size);

#endif

#ifdef EMMALLOC_DEBUG

validate_memory_regions();

#endif

if (!IS_POWER_OF_2(alignment))

return 0;

alignment = validate_alloc_alignment(alignment);

size = validate_alloc_size(size);

// Attempt to allocate memory starting from smallest bucket that can contain the required amount of memory.

// Under normal alignment conditions this should always be the first or second bucket we look at, but if

// performing an allocation with complex alignment, we may need to look at multiple buckets.

int bucketIndex = compute_free_list_bucket(size);

BUCKET_BITMASK_T bucketMask = freeRegionBucketsUsed >> bucketIndex;

// Loop through each bucket that has free regions in it, based on bits set in freeRegionBucketsUsed bitmap.

while(bucketMask)

{

BUCKET_BITMASK_T indexAdd = CountTrailingZeroesInBitmask(bucketMask);

bucketIndex += indexAdd;

bucketMask >>= indexAdd;

assert(bucketIndex >= 0);

assert(bucketIndex <= NUM_FREE_BUCKETS-1);

assert(freeRegionBucketsUsed & (((BUCKET_BITMASK_T)1) << bucketIndex));

Region *freeRegion = freeRegionBuckets[bucketIndex].next;

assert(freeRegion);

if (freeRegion != &freeRegionBuckets[bucketIndex])

{

void *ptr = attempt_allocate(freeRegion, alignment, size);

if (ptr)

return ptr;

// We were not able to allocate from the first region found in this bucket, so penalize

// the region by cycling it to the end of the doubly circular linked list. (constant time)

// This provides a randomized guarantee that when performing allocations of size k to a

// bucket of [k-something, k+something] range, we will not always attempt to satisfy the

// allocation from the same available region at the front of the list, but we try each

// region in turn.

unlink_from_free_list(freeRegion);

prepend_to_free_list(freeRegion, &freeRegionBuckets[bucketIndex]);

// But do not stick around to attempt to look at other regions in this bucket - move

// to search the next populated bucket index if this did not fit. This gives a practical

// "allocation in constant time" guarantee, since the next higher bucket will only have

// regions that are all of strictly larger size than the requested allocation. Only if

// there is a difficult alignment requirement we may fail to perform the allocation from

// a region in the next bucket, and if so, we keep trying higher buckets until one of them

// works.

++bucketIndex;

bucketMask >>= 1;

}

else

{

// This bucket was not populated after all with any regions,

// but we just had a stale bit set to mark a populated bucket.

// Reset the bit to update latest status so that we do not

// redundantly look at this bucket again.

freeRegionBucketsUsed &= ~(((BUCKET_BITMASK_T)1) << bucketIndex);

bucketMask ^= 1;

}

// Instead of recomputing bucketMask from scratch at the end of each loop, it is updated as we go,

// to avoid undefined behavior with (x >> 32)/(x >> 64) when bucketIndex reaches 32/64, (the shift would comes out as a no-op instead of 0).

// Work around bug https://github.com/emscripten-core/emscripten/issues/10173

// assert((bucketIndex == NUM_FREE_BUCKETS && bucketMask == 0) || (bucketMask == freeRegionBucketsUsed >> bucketIndex));

assert((bucketIndex == NUM_FREE_BUCKETS && bucketMask == 0) || (bucketMask + EM_ASM_INT(return 0) == (freeRegionBucketsUsed >> bucketIndex) + EM_ASM_INT(return 0)));

}

// None of the buckets were able to accommodate an allocation. If this happens we are almost out of memory.

// The largest bucket might contain some suitable regions, but we only looked at one region in that bucket, so

// as a last resort, loop through more free regions in the bucket that represents the largest allocations available.

// But only if the bucket representing largest allocations available is not any of the first ten buckets (thirty buckets

// in 64-bit buckets build), these represent allocatable areas less than <1024 bytes - which could be a lot of scrap.

// In such case, prefer to sbrk() in more memory right away.

int largestBucketIndex = NUM_FREE_BUCKETS - 1 - CountLeadingZeroesInBitmask(freeRegionBucketsUsed);

Region *freeRegion = freeRegionBuckets[largestBucketIndex].next;

#ifdef EMMALLOC_USE_64BIT_OPS

if (freeRegionBucketsUsed >> 30)

#else

if (freeRegionBucketsUsed >> 10)

#endif

{

// Look only at a constant number of regions in this bucket max, to avoid bad worst case behavior.

// If this many regions cannot find free space, we give up and prefer to sbrk() more instead.

const int maxRegionsToTryBeforeGivingUp = 99;

int numTriesLeft = maxRegionsToTryBeforeGivingUp;

while(freeRegion != &freeRegionBuckets[largestBucketIndex] && numTriesLeft-- > 0)

{

void *ptr = attempt_allocate(freeRegion, alignment, size);

if (ptr)

return ptr;

freeRegion = freeRegion->next;

}

}

// We were unable to find a free memory region. Must sbrk() in more memory!

size_t numBytesToClaim = size+sizeof(Region)*3;

bool success = claim_more_memory(numBytesToClaim);

if (success)

return allocate_memory(alignment, size); // Recurse back to itself to try again

// also sbrk() failed, we are really really constrained :( As a last resort, go back to looking at the

// bucket we already looked at above, continuing where the above search left off - perhaps there are

// regions we overlooked the first time that might be able to satisfy the allocation.

while(freeRegion != &freeRegionBuckets[largestBucketIndex])

{

void *ptr = attempt_allocate(freeRegion, alignment, size);

if (ptr)

return ptr;

freeRegion = freeRegion->next;

}

return 0;

}

void *emmalloc_memalign(size_t alignment, size_t size)

{

MALLOC_ACQUIRE();

void *ptr = allocate_memory(alignment, size);

MALLOC_RELEASE();

return ptr;

}

extern __typeof(emmalloc_memalign) emscripten_builtin_memalign __attribute__((alias("emmalloc_memalign")));

void * EMMALLOC_EXPORT memalign(size_t alignment, size_t size)

{

return emmalloc_memalign(alignment, size);

}

void * EMMALLOC_EXPORT aligned_alloc(size_t alignment, size_t size)

{

if ((alignment % sizeof(void *) != 0) || (size % alignment) != 0)

return 0;

return emmalloc_memalign(alignment, size);

}

void *emmalloc_malloc(size_t size)

{

return emmalloc_memalign(MALLOC_ALIGNMENT, size);

}

extern __typeof(emmalloc_malloc) emscripten_builtin_malloc __attribute__((alias("emmalloc_malloc")));

void * EMMALLOC_EXPORT malloc(size_t size)

{

return emmalloc_malloc(size);

}

size_t emmalloc_usable_size(void *ptr)

{

if (!ptr)

return 0;

uint8_t *regionStartPtr = (uint8_t*)ptr - sizeof(uint32_t);

Region *region = (Region*)(regionStartPtr);

assert(HAS_ALIGNMENT(region, sizeof(uint32_t)));

MALLOC_ACQUIRE();

uint32_t size = region->size;

assert(size >= sizeof(Region));

assert(region_is_in_use(region));

MALLOC_RELEASE();

return size - REGION_HEADER_SIZE;

}

size_t EMMALLOC_EXPORT malloc_usable_size(void *ptr)

{

return emmalloc_usable_size(ptr);

}

void emmalloc_free(void *ptr)

{

#ifdef EMMALLOC_DEBUG

emmalloc_validate_memory_regions();

#endif

if (!ptr)

return;

#ifdef EMMALLOC_DEBUG_LOG

MAIN_THREAD_ASYNC_EM_ASM(console.log('free(ptr='+$0.toString(16)+')'), ptr);

#endif

uint8_t *regionStartPtr = (uint8_t*)ptr - sizeof(uint32_t);

Region *region = (Region*)(regionStartPtr);

assert(HAS_ALIGNMENT(region, sizeof(uint32_t)));

MALLOC_ACQUIRE();

uint32_t size = region->size;

#ifdef EMMALLOC_DEBUG_LOG

if (size < sizeof(Region) || !region_is_in_use(region))

{

if (debug_region_is_consistent(region))

// LLVM wasm backend bug: cannot use MAIN_THREAD_ASYNC_EM_ASM() here, that generates internal compiler error

EM_ASM(console.error('Double free at region ptr ' + $0.toString(16) + ', region->size: ' + $1.toString(16) + ', region->sizeAtCeiling: ' + $2.toString(16) + ')'), region, size, region_ceiling_size(region));

else

MAIN_THREAD_ASYNC_EM_ASM(console.error('Corrupt region at region ptr ' + $0.toString(16) + ' region->size:' + $1.toString(16) + ', region->sizeAtCeiling:' + $2.toString(16) + ')'), region, size, region_ceiling_size(region));

}

#endif

assert(size >= sizeof(Region));

assert(region_is_in_use(region));

#ifdef __EMSCRIPTEN_TRACING__

emscripten_trace_record_free(region);

#endif

// Check merging with left side

uint32_t prevRegionSize = ((uint32_t*)region)[-1];

uint32_t prevRegionSizeMask = (uint32_t)((int32_t)prevRegionSize >> 31);

if (prevRegionSizeMask)

{

prevRegionSize ^= prevRegionSizeMask;

Region *prevRegion = (Region*)((uint8_t*)region - prevRegionSize);

assert(debug_region_is_consistent(prevRegion));

unlink_from_free_list(prevRegion);

regionStartPtr = (uint8_t*)prevRegion;

size += prevRegionSize;

}

// Check merging with right side

Region *nextRegion = next_region(region);

assert(debug_region_is_consistent(nextRegion));

uint32_t sizeAtEnd = *(uint32_t*)region_payload_end_ptr(nextRegion);

if (nextRegion->size != sizeAtEnd)

{

unlink_from_free_list(nextRegion);

size += nextRegion->size;

}

create_free_region(regionStartPtr, size);

link_to_free_list((Region*)regionStartPtr);

MALLOC_RELEASE();

#ifdef EMMALLOC_DEBUG

emmalloc_validate_memory_regions();

#endif

}

extern __typeof(emmalloc_free) emscripten_builtin_free __attribute__((alias("emmalloc_free")));

void EMMALLOC_EXPORT free(void *ptr)

{

return emmalloc_free(ptr);

}

// Can be called to attempt to increase or decrease the size of the given region

// to a new size (in-place). Returns 1 if resize succeeds, and 0 on failure.

static int attempt_region_resize(Region *region, size_t size)

{

ASSERT_MALLOC_IS_ACQUIRED();

assert(size > 0);

assert(HAS_ALIGNMENT(size, sizeof(uint32_t)));

#ifdef EMMALLOC_DEBUG_LOG

MAIN_THREAD_ASYNC_EM_ASM(console.log('attempt_region_resize(region=' + $0.toString(16) + ', size=' + $1 + ' bytes)'), region, size);

#endif

// First attempt to resize this region, if the next region that follows this one

// is a free region.

Region *nextRegion = next_region(region);

uint8_t *nextRegionEndPtr = (uint8_t*)nextRegion + nextRegion->size;

size_t sizeAtCeiling = ((uint32_t*)nextRegionEndPtr)[-1];

if (nextRegion->size != sizeAtCeiling) // Next region is free?

{

assert(region_is_free(nextRegion));

uint8_t *newNextRegionStartPtr = (uint8_t*)region + size;

assert(HAS_ALIGNMENT(newNextRegionStartPtr, sizeof(uint32_t)));

// Next region does not shrink to too small size?

if (newNextRegionStartPtr + sizeof(Region) <= nextRegionEndPtr)

{

unlink_from_free_list(nextRegion);

create_free_region(newNextRegionStartPtr, nextRegionEndPtr - newNextRegionStartPtr);

link_to_free_list((Region*)newNextRegionStartPtr);

create_used_region(region, newNextRegionStartPtr - (uint8_t*)region);

return 1;

}

// If we remove the next region altogether, allocation is satisfied?

if (newNextRegionStartPtr <= nextRegionEndPtr)

{

unlink_from_free_list(nextRegion);

create_used_region(region, region->size + nextRegion->size);

return 1;

}

}

else

{

// Next region is an used region - we cannot change its starting address. However if we are shrinking the

// size of this region, we can create a new free region between this and the next used region.

if (size + sizeof(Region) <= region->size)