path: root/contrib/libs/cxxsupp/libcxxabi/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 <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 
_LIBCPP_SAFE_STATIC 
static std::__libcpp_mutex_t heap_mutex = _LIBCPP_MUTEX_INITIALIZER; 
#else 
static 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; 
 
struct heap_node { 
  heap_offset next_node; // offset into heap 
  heap_size len;         // size in units of "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)); 
} 
 
void init_heap() { 
  freelist = (heap_node*)heap; 
  freelist->next_node = offset_from_node(list_end); 
  freelist->len = HEAP_SIZE / sizeof(heap_node); 
} 
 
//  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)) { 
 
    if (p->len > nelems) { //  chunk is larger, shorten, and return the tail 
      heap_node* q; 
 
      p->len = static_cast<heap_size>(p->len - nelems); 
      q = p + p->len; 
      q->next_node = 0; 
      q->len = static_cast<heap_size>(nelems); 
      return (void*)(q + 1); 
    } 
 
    if (p->len == nelems) { // exact size match 
      if (prev == 0) 
        freelist = node_from_offset(p->next_node); 
      else 
        prev->next_node = p->next_node; 
      p->next_node = 0; 
      return (void*)(p + 1); 
    } 
  } 
  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