src/fallback_malloc.cpp

//===----------------------------------------------------------------------===//
//
// 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 <__threading_support>
#ifndef _LIBCXXABI_HAS_NO_THREADS
#if defined(__ELF__) && defined(_LIBCXXABI_LINK_PTHREAD_LIB)
#pragma comment(lib, "pthread")
#endif
#endif

#include <assert.h>
#include <stdlib.h> // for malloc, calloc, free
#include <string.h> // for memset
#include <new> // for std::__libcpp_aligned_{alloc,free}

//  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
    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;
      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;
      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