third_party/pigweed/repo/pw_allocator/freelist_heap.cc

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14
  15 #include "pw_allocator/freelist_heap.h"
  16
  17 #include <cstring>
  18
  19 #include "pw_assert/assert.h"
  20 #include "pw_log/log.h"
  21
  22 namespace pw::allocator {
  23
  24 FreeListHeap::FreeListHeap(std::span<std::byte> region, FreeList& freelist)
  25     : freelist_(freelist), heap_stats_() {
  26   Block* block;
  27   PW_CHECK_OK(
  28       Block::Init(region, &block),
  29       "Failed to initialize FreeListHeap region; misaligned or too small");
  30
  31   freelist_.AddChunk(BlockToSpan(block));
  32
  33   region_ = region;
  34   heap_stats_.total_bytes = region.size();
  35 }
  36
  37 void* FreeListHeap::Allocate(size_t size) {
  38   // Find a chunk in the freelist. Split it if needed, then return
  39
  40   auto chunk = freelist_.FindChunk(size);
  41
  42   if (chunk.data() == nullptr) {
  43     return nullptr;
  44   }
  45   freelist_.RemoveChunk(chunk);
  46
  47   Block* chunk_block = Block::FromUsableSpace(chunk.data());
  48
  49   chunk_block->CrashIfInvalid();
  50
  51   // Split that chunk. If there's a leftover chunk, add it to the freelist
  52   Block* leftover;
  53   auto status = chunk_block->Split(size, &leftover);
  54   if (status == PW_STATUS_OK) {
  55     freelist_.AddChunk(BlockToSpan(leftover));
  56   }
  57
  58   chunk_block->MarkUsed();
  59
  60   heap_stats_.bytes_allocated += size;
  61   heap_stats_.cumulative_allocated += size;
  62   heap_stats_.total_allocate_calls += 1;
  63
  64   return chunk_block->UsableSpace();
  65 }
  66
  67 void FreeListHeap::Free(void* ptr) {
  68   std::byte* bytes = static_cast<std::byte*>(ptr);
  69
  70   if (bytes < region_.data() || bytes >= region_.data() + region_.size()) {
  71     InvalidFreeCrash();
  72     return;
  73   }
  74
  75   Block* chunk_block = Block::FromUsableSpace(bytes);
  76   chunk_block->CrashIfInvalid();
  77
  78   size_t size_freed = chunk_block->InnerSize();
  79   // Ensure that the block is in-use
  80   if (!chunk_block->Used()) {
  81     InvalidFreeCrash();
  82     return;
  83   }
  84   chunk_block->MarkFree();
  85   // Can we combine with the left or right blocks?
  86   Block* prev = chunk_block->Prev();
  87   Block* next = nullptr;
  88
  89   if (!chunk_block->Last()) {
  90     next = chunk_block->Next();
  91   }
  92
  93   if (prev != nullptr && !prev->Used()) {
  94     // Remove from freelist and merge
  95     freelist_.RemoveChunk(BlockToSpan(prev));
  96     chunk_block->MergePrev();
  97
  98     // chunk_block is now invalid; prev now encompasses it.
  99     chunk_block = prev;
 100   }
 101
 102   if (next != nullptr && !next->Used()) {
 103     freelist_.RemoveChunk(BlockToSpan(next));
 104     chunk_block->MergeNext();
 105   }
 106   // Add back to the freelist
 107   freelist_.AddChunk(BlockToSpan(chunk_block));
 108
 109   heap_stats_.bytes_allocated -= size_freed;
 110   heap_stats_.cumulative_freed += size_freed;
 111   heap_stats_.total_free_calls += 1;
 112 }
 113
 114 // Follows constract of the C standard realloc() function
 115 // If ptr is free'd, will return nullptr.
 116 void* FreeListHeap::Realloc(void* ptr, size_t size) {
 117   if (size == 0) {
 118     Free(ptr);
 119     return nullptr;
 120   }
 121
 122   // If the pointer is nullptr, allocate a new memory.
 123   if (ptr == nullptr) {
 124     return Allocate(size);
 125   }
 126
 127   std::byte* bytes = static_cast<std::byte*>(ptr);
 128
 129   // TODO(chenghanzh): Enhance with debug information for out-of-range and more.
 130   if (bytes < region_.data() || bytes >= region_.data() + region_.size()) {
 131     return nullptr;
 132   }
 133
 134   Block* chunk_block = Block::FromUsableSpace(bytes);
 135   if (!chunk_block->Used()) {
 136     return nullptr;
 137   }
 138   size_t old_size = chunk_block->InnerSize();
 139
 140   // Do nothing and return ptr if the required memory size is smaller than
 141   // the current size.
 142   // TODO: Currently do not support shrink of memory chunk.
 143   if (old_size >= size) {
 144     return ptr;
 145   }
 146
 147   void* new_ptr = Allocate(size);
 148   // Don't invalidate ptr if Allocate(size) fails to initilize the memory.
 149   if (new_ptr == nullptr) {
 150     return nullptr;
 151   }
 152   memcpy(new_ptr, ptr, old_size);
 153
 154   Free(ptr);
 155   return new_ptr;
 156 }
 157
 158 void* FreeListHeap::Calloc(size_t num, size_t size) {
 159   void* ptr = Allocate(num * size);
 160   if (ptr != nullptr) {
 161     memset(ptr, 0, num * size);
 162   }
 163   return ptr;
 164 }
 165
 166 void FreeListHeap::LogHeapStats() {
 167   PW_LOG_INFO(" ");
 168   PW_LOG_INFO("    The current heap information: ");
 169   PW_LOG_INFO("          The total heap size is %u bytes.",
 170               static_cast<unsigned int>(heap_stats_.total_bytes));
 171   PW_LOG_INFO("          The current allocated heap memory is %u bytes.",
 172               static_cast<unsigned int>(heap_stats_.bytes_allocated));
 173   PW_LOG_INFO("          The cumulative allocated heap memory is %u bytes.",
 174               static_cast<unsigned int>(heap_stats_.cumulative_allocated));
 175   PW_LOG_INFO("          The cumulative freed heap memory is %u bytes.",
 176               static_cast<unsigned int>(heap_stats_.cumulative_freed));
 177   PW_LOG_INFO(
 178       "          malloc() is called %u times. (realloc()/calloc() counted as "
 179       "one time)",
 180       static_cast<unsigned int>(heap_stats_.total_allocate_calls));
 181   PW_LOG_INFO(
 182       "          free() is called %u times. (realloc() counted as one time)",
 183       static_cast<unsigned int>(heap_stats_.total_free_calls));
 184   PW_LOG_INFO(" ");
 185 }
 186
 187 // TODO: Add stack tracing to locate which call to the heap operation caused
 188 // the corruption.
 189 void FreeListHeap::InvalidFreeCrash() {
 190   PW_DCHECK(false, "You tried to free an invalid pointer!");
 191 }
 192
 193 }  // namespace pw::allocator