Differential D19566 Diff 55036 contrib/libcxxabi/src/fallback_malloc.cpp

Changeset View

Standalone View

contrib/libcxxabi/src/fallback_malloc.cpp

This file was added.

Property	Old Value	New Value
svn:eol-style	null	native \ No newline at end of property
svn:keywords	null	FreeBSD=%H \ No newline at end of property
svn:mime-type	null	text/plain \ No newline at end of property

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

				// Define _LIBCPP_BUILDING_LIBRARY to ensure _LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION
				// is only defined when libc aligned allocation is not available.
				#define _LIBCPP_BUILDING_LIBRARY
				#include "fallback_malloc.h"

				#include <__threading_support>

				#include <cstdlib> // for malloc, calloc, free
				#include <cstring> // 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
				_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::cout << "Freeing item at " << offset_from_node(cp) << " of size "
				<< cp->len << std::endl;
				#endif

				for (p = freelist, prev = 0; p && p != list_end;
				prev = p, p = node_from_offset(p->next_node)) {
				#ifdef DEBUG_FALLBACK_MALLOC
				std::cout << " p, cp, after (p), after(cp) " << offset_from_node(p) << ' '
				<< offset_from_node(cp) << ' ' << offset_from_node(after(p))
				<< ' ' << offset_from_node(after(cp)) << std::endl;
				#endif
				if (after(p) == cp) {
				#ifdef DEBUG_FALLBACK_MALLOC
				std::cout << " Appending onto chunk at " << offset_from_node(p)
				<< std::endl;
				#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::cout << " Appending free chunk at " << offset_from_node(p)
				<< std::endl;
				#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::cout << " Making new free list entry " << offset_from_node(cp)
				<< std::endl;
				#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::cout << (prev == 0 ? "" : " ") << "Offset: " << offset_from_node(p)
				<< "\tsize: " << p->len << " Next: " << p->next_node << std::endl;
				total_free += p->len;
				}
				std::cout << "Total Free space: " << total_free << std::endl;
				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 = _aligned_malloc(size, alignof(__aligned_type)))
				return dest;
				#elif defined(_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION)
				if (void* dest = std::malloc(size))
				return dest;
				#else
				if (size == 0)
				size = 1;
				void* dest;
				if (::posix_memalign(&dest, __alignof(__aligned_type), size) == 0)
				return dest;
				#endif
				return fallback_malloc(size);
				}

				void* __calloc_with_fallback(size_t count, size_t size) {
				void* ptr = std::calloc(count, size);
				if (NULL != ptr)
				return ptr;
				// if calloc fails, fall back to emergency stash
				ptr = fallback_malloc(size * count);
				if (NULL != ptr)
				std::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(_WIN32)
				::_aligned_free(ptr);
				#else
				std::free(ptr);
				#endif
				}
				}

				void __free_with_fallback(void* ptr) {
				if (is_fallback_ptr(ptr))
				fallback_free(ptr);
				else
				std::free(ptr);
				}

				} // namespace __cxxabiv1