//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "fallback_malloc.h"
#include "abort_message.h"
#include <__thread/support.h>
#ifndef _LIBCXXABI_HAS_NO_THREADS
#if defined(__ELF__) && defined(_LIBCXXABI_LINK_PTHREAD_LIB)
#pragma comment(lib, "pthread")
#endif
#endif
#include <__memory/aligned_alloc.h>
#include <__assert>
#include <stdlib.h> // for malloc, calloc, free
#include <string.h> // for memset
// A small, simple heap manager based (loosely) on
// the startup heap manager from FreeBSD, optimized for space.
//
// Manages a fixed-size memory pool, supports malloc and free only.
// No support for realloc.
//
// Allocates chunks in multiples of four bytes, with a four byte header
// for each chunk. The overhead of each chunk is kept low by keeping pointers
// as two byte offsets within the heap, rather than (4 or 8 byte) pointers.
namespace {
// When POSIX threads are not available, make the mutex operations a nop
#ifndef _LIBCXXABI_HAS_NO_THREADS
static _LIBCPP_CONSTINIT std::__libcpp_mutex_t heap_mutex = _LIBCPP_MUTEX_INITIALIZER;
#else
static _LIBCPP_CONSTINIT void* heap_mutex = 0;
#endif
class mutexor {
public:
#ifndef _LIBCXXABI_HAS_NO_THREADS
mutexor(std::__libcpp_mutex_t* m) : mtx_(m) {
std::__libcpp_mutex_lock(mtx_);
}
~mutexor() { std::__libcpp_mutex_unlock(mtx_); }
#else
mutexor(void*) {}
~mutexor() {}
#endif
private:
mutexor(const mutexor& rhs);
mutexor& operator=(const mutexor& rhs);
#ifndef _LIBCXXABI_HAS_NO_THREADS
std::__libcpp_mutex_t* mtx_;
#endif
};
static const size_t HEAP_SIZE = 512;
char heap[HEAP_SIZE] __attribute__((aligned));
typedef unsigned short heap_offset;
typedef unsigned short heap_size;
// On both 64 and 32 bit targets heap_node should have the following properties
// Size: 4
// Alignment: 2
struct heap_node {
heap_offset next_node; // offset into heap
heap_size len; // size in units of "sizeof(heap_node)"
};
// All pointers returned by fallback_malloc must be at least aligned
// as RequiredAligned. Note that RequiredAlignment can be greater than
// alignof(std::max_align_t) on 64 bit systems compiling 32 bit code.
struct FallbackMaxAlignType {
} __attribute__((aligned));
const size_t RequiredAlignment = alignof(FallbackMaxAlignType);
static_assert(alignof(FallbackMaxAlignType) % sizeof(heap_node) == 0,
"The required alignment must be evenly divisible by the sizeof(heap_node)");
// The number of heap_node's that can fit in a chunk of memory with the size
// of the RequiredAlignment. On 64 bit targets NodesPerAlignment should be 4.
const size_t NodesPerAlignment = alignof(FallbackMaxAlignType) / sizeof(heap_node);
static const heap_node* list_end =
(heap_node*)(&heap[HEAP_SIZE]); // one past the end of the heap
static heap_node* freelist = NULL;
heap_node* node_from_offset(const heap_offset offset) {
return (heap_node*)(heap + (offset * sizeof(heap_node)));
}
heap_offset offset_from_node(const heap_node* ptr) {
return static_cast<heap_offset>(
static_cast<size_t>(reinterpret_cast<const char*>(ptr) - heap) /
sizeof(heap_node));
}
// Return a pointer to the first address, 'A', in `heap` that can actually be
// used to represent a heap_node. 'A' must be aligned so that
// '(A + sizeof(heap_node)) % RequiredAlignment == 0'. On 64 bit systems this
// address should be 12 bytes after the first 16 byte boundary.
heap_node* getFirstAlignedNodeInHeap() {
heap_node* node = (heap_node*)heap;
const size_t alignNBytesAfterBoundary = RequiredAlignment - sizeof(heap_node);
size_t boundaryOffset = reinterpret_cast<size_t>(node) % RequiredAlignment;
size_t requiredOffset = alignNBytesAfterBoundary - boundaryOffset;
size_t NElemOffset = requiredOffset / sizeof(heap_node);
return node + NElemOffset;
}
void init_heap() {
freelist = getFirstAlignedNodeInHeap();
freelist->next_node = offset_from_node(list_end);
freelist->len = static_cast<heap_size>(list_end - freelist);
}
// How big a chunk we allocate
size_t alloc_size(size_t len) {
return (len + sizeof(heap_node) - 1) / sizeof(heap_node) + 1;
}
bool is_fallback_ptr(void* ptr) {
return ptr >= heap && ptr < (heap + HEAP_SIZE);
}
void* fallback_malloc(size_t len) {
heap_node *p, *prev;
const size_t nelems = alloc_size(len);
mutexor mtx(&heap_mutex);
if (NULL == freelist)
init_heap();
// Walk the free list, looking for a "big enough" chunk
for (p = freelist, prev = 0; p && p != list_end;
prev = p, p = node_from_offset(p->next_node)) {
// Check the invariant that all heap_nodes pointers 'p' are aligned
// so that 'p + 1' has an alignment of at least RequiredAlignment
_LIBCXXABI_ASSERT(reinterpret_cast<size_t>(p + 1) % RequiredAlignment == 0, "");
// Calculate the number of extra padding elements needed in order
// to split 'p' and create a properly aligned heap_node from the tail
// of 'p'. We calculate aligned_nelems such that 'p->len - aligned_nelems'
// will be a multiple of NodesPerAlignment.
size_t aligned_nelems = nelems;
if (p->len > nelems) {
heap_size remaining_len = static_cast<heap_size>(p->len - nelems);
aligned_nelems += remaining_len % NodesPerAlignment;
}
// chunk is larger and we can create a properly aligned heap_node
// from the tail. In this case we shorten 'p' and return the tail.
if (p->len > aligned_nelems) {
heap_node* q;
p->len = static_cast<heap_size>(p->len - aligned_nelems);
q = p + p->len;
q->next_node = 0;
q->len = static_cast<heap_size>(aligned_nelems);
void* ptr = q + 1;
_LIBCXXABI_ASSERT(reinterpret_cast<size_t>(ptr) % RequiredAlignment == 0, "");
return ptr;
}
// The chunk is the exact size or the chunk is larger but not large
// enough to split due to alignment constraints.
if (p->len >= nelems) {
if (prev == 0)
freelist = node_from_offset(p->next_node);
else
prev->next_node = p->next_node;
p->next_node = 0;
void* ptr = p + 1;
_LIBCXXABI_ASSERT(reinterpret_cast<size_t>(ptr) % RequiredAlignment == 0, "");
return ptr;
}
}
return NULL; // couldn't find a spot big enough
}
// Return the start of the next block
heap_node* after(struct heap_node* p) { return p + p->len; }
void fallback_free(void* ptr) {
struct heap_node* cp = ((struct heap_node*)ptr) - 1; // retrieve the chunk
struct heap_node *p, *prev;
mutexor mtx(&heap_mutex);
#ifdef DEBUG_FALLBACK_MALLOC
std::printf("Freeing item at %d of size %d\n", offset_from_node(cp), cp->len);
#endif
for (p = freelist, prev = 0; p && p != list_end;
prev = p, p = node_from_offset(p->next_node)) {
#ifdef DEBUG_FALLBACK_MALLOC
std::printf(" p=%d, cp=%d, after(p)=%d, after(cp)=%d\n",
offset_from_node(p), offset_from_node(cp),
offset_from_node(after(p)), offset_from_node(after(cp)));
#endif
if (after(p) == cp) {
#ifdef DEBUG_FALLBACK_MALLOC
std::printf(" Appending onto chunk at %d\n", offset_from_node(p));
#endif
p->len = static_cast<heap_size>(
p->len + cp->len); // make the free heap_node larger
return;
} else if (after(cp) == p) { // there's a free heap_node right after
#ifdef DEBUG_FALLBACK_MALLOC
std::printf(" Appending free chunk at %d\n", offset_from_node(p));
#endif
cp->len = static_cast<heap_size>(cp->len + p->len);
if (prev == 0) {
freelist = cp;
cp->next_node = p->next_node;
} else
prev->next_node = offset_from_node(cp);
return;
}
}
// Nothing to merge with, add it to the start of the free list
#ifdef DEBUG_FALLBACK_MALLOC
std::printf(" Making new free list entry %d\n", offset_from_node(cp));
#endif
cp->next_node = offset_from_node(freelist);
freelist = cp;
}
#ifdef INSTRUMENT_FALLBACK_MALLOC
size_t print_free_list() {
struct heap_node *p, *prev;
heap_size total_free = 0;
if (NULL == freelist)
init_heap();
for (p = freelist, prev = 0; p && p != list_end;
prev = p, p = node_from_offset(p->next_node)) {
std::printf("%sOffset: %d\tsize: %d Next: %d\n",
(prev == 0 ? "" : " "), offset_from_node(p), p->len, p->next_node);
total_free += p->len;
}
std::printf("Total Free space: %d\n", total_free);
return total_free;
}
#endif
} // end unnamed namespace
namespace __cxxabiv1 {
struct __attribute__((aligned)) __aligned_type {};
void* __aligned_malloc_with_fallback(size_t size) {
#if defined(_WIN32)
if (void* dest = std::__libcpp_aligned_alloc(alignof(__aligned_type), size))
return dest;
#elif defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION)
if (void* dest = ::malloc(size))
return dest;
#else
if (size == 0)
size = 1;
if (void* dest = std::__libcpp_aligned_alloc(__alignof(__aligned_type), size))
return dest;
#endif
return fallback_malloc(size);
}
void* __calloc_with_fallback(size_t count, size_t size) {
void* ptr = ::calloc(count, size);
if (NULL != ptr)
return ptr;
// if calloc fails, fall back to emergency stash
ptr = fallback_malloc(size * count);
if (NULL != ptr)
::memset(ptr, 0, size * count);
return ptr;
}
void __aligned_free_with_fallback(void* ptr) {
if (is_fallback_ptr(ptr))
fallback_free(ptr);
else {
#if defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION)
::free(ptr);
#else
std::__libcpp_aligned_free(ptr);
#endif
}
}
void __free_with_fallback(void* ptr) {
if (is_fallback_ptr(ptr))
fallback_free(ptr);
else
::free(ptr);
}
} // namespace __cxxabiv1
Codebase Browser
llvm