//===----------------------------------------------------------------------===//

//

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

#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