210 lines · c
1//===-- Interface for freelist_heap ---------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_FREELIST_HEAP_H10#define LLVM_LIBC_SRC___SUPPORT_FREELIST_HEAP_H11 12#include <stddef.h>13 14#include "block.h"15#include "freestore.h"16#include "src/__support/CPP/optional.h"17#include "src/__support/CPP/span.h"18#include "src/__support/libc_assert.h"19#include "src/__support/macros/config.h"20#include "src/__support/math_extras.h"21#include "src/string/memory_utils/inline_memcpy.h"22#include "src/string/memory_utils/inline_memset.h"23 24namespace LIBC_NAMESPACE_DECL {25 26extern "C" cpp::byte _end;27extern "C" cpp::byte __llvm_libc_heap_limit;28 29using cpp::optional;30using cpp::span;31 32LIBC_INLINE constexpr bool IsPow2(size_t x) { return x && (x & (x - 1)) == 0; }33 34class FreeListHeap {35public:36 constexpr FreeListHeap() : begin(&_end), end(&__llvm_libc_heap_limit) {}37 38 constexpr FreeListHeap(span<cpp::byte> region)39 : begin(region.begin()), end(region.end()) {}40 41 void *allocate(size_t size);42 void *aligned_allocate(size_t alignment, size_t size);43 // NOTE: All pointers passed to free must come from one of the other44 // allocation functions: `allocate`, `aligned_allocate`, `realloc`, `calloc`.45 void free(void *ptr);46 void *realloc(void *ptr, size_t size);47 void *calloc(size_t num, size_t size);48 49 cpp::span<cpp::byte> region() const { return {begin, end}; }50 51private:52 void init();53 54 void *allocate_impl(size_t alignment, size_t size);55 56 span<cpp::byte> block_to_span(Block *block) {57 return span<cpp::byte>(block->usable_space(), block->inner_size());58 }59 60 bool is_valid_ptr(void *ptr) { return ptr >= begin && ptr < end; }61 62 cpp::byte *begin;63 cpp::byte *end;64 bool is_initialized = false;65 FreeStore free_store;66};67 68template <size_t BUFF_SIZE> class FreeListHeapBuffer : public FreeListHeap {69public:70 constexpr FreeListHeapBuffer() : FreeListHeap{buffer}, buffer{} {}71 72private:73 cpp::byte buffer[BUFF_SIZE];74};75 76LIBC_INLINE void FreeListHeap::init() {77 LIBC_ASSERT(!is_initialized && "duplicate initialization");78 auto result = Block::init(region());79 Block *block = *result;80 free_store.set_range({0, cpp::bit_ceil(block->inner_size())});81 free_store.insert(block);82 is_initialized = true;83}84 85LIBC_INLINE void *FreeListHeap::allocate_impl(size_t alignment, size_t size) {86 if (size == 0)87 return nullptr;88 89 if (!is_initialized)90 init();91 92 size_t request_size = Block::min_size_for_allocation(alignment, size);93 if (!request_size)94 return nullptr;95 96 Block *block = free_store.remove_best_fit(request_size);97 if (!block)98 return nullptr;99 100 auto block_info = Block::allocate(block, alignment, size);101 if (block_info.next)102 free_store.insert(block_info.next);103 if (block_info.prev)104 free_store.insert(block_info.prev);105 106 block_info.block->mark_used();107 return block_info.block->usable_space();108}109 110LIBC_INLINE void *FreeListHeap::allocate(size_t size) {111 return allocate_impl(alignof(max_align_t), size);112}113 114LIBC_INLINE void *FreeListHeap::aligned_allocate(size_t alignment,115 size_t size) {116 // The alignment must be an integral power of two.117 if (!IsPow2(alignment))118 return nullptr;119 120 // The size parameter must be an integral multiple of alignment.121 if (size % alignment != 0)122 return nullptr;123 124 // The minimum alignment supported by Block is max_align_t.125 alignment = cpp::max(alignment, alignof(max_align_t));126 127 return allocate_impl(alignment, size);128}129 130LIBC_INLINE void FreeListHeap::free(void *ptr) {131 cpp::byte *bytes = static_cast<cpp::byte *>(ptr);132 133 LIBC_ASSERT(is_valid_ptr(bytes) && "Invalid pointer");134 135 Block *block = Block::from_usable_space(bytes);136 LIBC_ASSERT(block->next() && "sentinel last block cannot be freed");137 LIBC_ASSERT(block->used() && "double free");138 block->mark_free();139 140 // Can we combine with the left or right blocks?141 Block *prev_free = block->prev_free();142 Block *next = block->next();143 144 if (prev_free != nullptr) {145 // Remove from free store and merge.146 free_store.remove(prev_free);147 block = prev_free;148 block->merge_next();149 }150 if (!next->used()) {151 free_store.remove(next);152 block->merge_next();153 }154 // Add back to the freelist155 free_store.insert(block);156}157 158// Follows constract of the C standard realloc() function159// If ptr is free'd, will return nullptr.160LIBC_INLINE void *FreeListHeap::realloc(void *ptr, size_t size) {161 if (size == 0) {162 free(ptr);163 return nullptr;164 }165 166 // If the pointer is nullptr, allocate a new memory.167 if (ptr == nullptr)168 return allocate(size);169 170 cpp::byte *bytes = static_cast<cpp::byte *>(ptr);171 172 if (!is_valid_ptr(bytes))173 return nullptr;174 175 Block *block = Block::from_usable_space(bytes);176 if (!block->used())177 return nullptr;178 size_t old_size = block->inner_size();179 180 // Do nothing and return ptr if the required memory size is smaller than181 // the current size.182 if (old_size >= size)183 return ptr;184 185 void *new_ptr = allocate(size);186 // Don't invalidate ptr if allocate(size) fails to initilize the memory.187 if (new_ptr == nullptr)188 return nullptr;189 LIBC_NAMESPACE::inline_memcpy(new_ptr, ptr, old_size);190 191 free(ptr);192 return new_ptr;193}194 195LIBC_INLINE void *FreeListHeap::calloc(size_t num, size_t size) {196 size_t bytes;197 if (__builtin_mul_overflow(num, size, &bytes))198 return nullptr;199 void *ptr = allocate(bytes);200 if (ptr != nullptr)201 LIBC_NAMESPACE::inline_memset(ptr, 0, bytes);202 return ptr;203}204 205extern FreeListHeap *freelist_heap;206 207} // namespace LIBC_NAMESPACE_DECL208 209#endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_HEAP_H210