blob: a6124e39f5907c0b17d26a11fb73d59a14b765c2 [file] [log] [blame]
// Copyright 2020 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#include "pw_allocator/freelist_heap.h"
#include <cstring>
#include "pw_assert/assert.h"
#include "pw_log/log.h"
namespace pw::allocator {
FreeListHeap::FreeListHeap(std::span<std::byte> region, FreeList& freelist)
: freelist_(freelist), heap_stats_() {
Block* block;
Block::Init(region, &block);
freelist_.AddChunk(BlockToSpan(block));
region_ = region;
heap_stats_.total_bytes = region.size();
}
void* FreeListHeap::Allocate(size_t size) {
// Find a chunk in the freelist. Split it if needed, then return
auto chunk = freelist_.FindChunk(size);
if (chunk.data() == nullptr) {
return nullptr;
}
freelist_.RemoveChunk(chunk);
Block* chunk_block = Block::FromUsableSpace(chunk.data());
chunk_block->CrashIfInvalid();
// Split that chunk. If there's a leftover chunk, add it to the freelist
Block* leftover;
auto status = chunk_block->Split(size, &leftover);
if (status == PW_STATUS_OK) {
freelist_.AddChunk(BlockToSpan(leftover));
}
chunk_block->MarkUsed();
heap_stats_.bytes_allocated += size;
heap_stats_.cumulative_allocated += size;
heap_stats_.total_allocate_calls += 1;
return chunk_block->UsableSpace();
}
void FreeListHeap::Free(void* ptr) {
std::byte* bytes = static_cast<std::byte*>(ptr);
if (bytes < region_.data() || bytes >= region_.data() + region_.size()) {
InvalidFreeCrash();
return;
}
Block* chunk_block = Block::FromUsableSpace(bytes);
chunk_block->CrashIfInvalid();
size_t size_freed = chunk_block->InnerSize();
// Ensure that the block is in-use
if (!chunk_block->Used()) {
InvalidFreeCrash();
return;
}
chunk_block->MarkFree();
// Can we combine with the left or right blocks?
Block* prev = chunk_block->Prev();
Block* next = nullptr;
if (!chunk_block->Last()) {
next = chunk_block->Next();
}
if (prev != nullptr && !prev->Used()) {
// Remove from freelist and merge
freelist_.RemoveChunk(BlockToSpan(prev));
chunk_block->MergePrev();
// chunk_block is now invalid; prev now encompasses it.
chunk_block = prev;
}
if (next != nullptr && !next->Used()) {
freelist_.RemoveChunk(BlockToSpan(next));
chunk_block->MergeNext();
}
// Add back to the freelist
freelist_.AddChunk(BlockToSpan(chunk_block));
heap_stats_.bytes_allocated -= size_freed;
heap_stats_.cumulative_freed += size_freed;
heap_stats_.total_free_calls += 1;
}
// Follows constract of the C standard realloc() function
// If ptr is free'd, will return nullptr.
void* FreeListHeap::Realloc(void* ptr, size_t size) {
if (size == 0) {
Free(ptr);
return nullptr;
}
// If the pointer is nullptr, allocate a new memory.
if (ptr == nullptr) {
return Allocate(size);
}
std::byte* bytes = static_cast<std::byte*>(ptr);
// TODO(chenghanzh): Enhance with debug information for out-of-range and more.
if (bytes < region_.data() || bytes >= region_.data() + region_.size()) {
return nullptr;
}
Block* chunk_block = Block::FromUsableSpace(bytes);
if (!chunk_block->Used()) {
return nullptr;
}
size_t old_size = chunk_block->InnerSize();
// Do nothing and return ptr if the required memory size is smaller than
// the current size.
// TODO: Currently do not support shrink of memory chunk.
if (old_size >= size) {
return ptr;
}
void* new_ptr = Allocate(size);
// Don't invalidate ptr if Allocate(size) fails to initilize the memory.
if (new_ptr == nullptr) {
return nullptr;
}
memcpy(new_ptr, ptr, old_size);
Free(ptr);
return new_ptr;
}
void* FreeListHeap::Calloc(size_t num, size_t size) {
void* ptr = Allocate(num * size);
if (ptr != nullptr) {
memset(ptr, 0, num * size);
}
return ptr;
}
void FreeListHeap::LogHeapStats() {
PW_LOG_INFO(" ");
PW_LOG_INFO(" The current heap information: ");
PW_LOG_INFO(" The total heap size is %u bytes.",
static_cast<unsigned int>(heap_stats_.total_bytes));
PW_LOG_INFO(" The current allocated heap memory is %u bytes.",
static_cast<unsigned int>(heap_stats_.bytes_allocated));
PW_LOG_INFO(" The cumulative allocated heap memory is %u bytes.",
static_cast<unsigned int>(heap_stats_.cumulative_allocated));
PW_LOG_INFO(" The cumulative freed heap memory is %u bytes.",
static_cast<unsigned int>(heap_stats_.cumulative_freed));
PW_LOG_INFO(
" malloc() is called %u times. (realloc()/calloc() counted as "
"one time)",
static_cast<unsigned int>(heap_stats_.total_allocate_calls));
PW_LOG_INFO(
" free() is called %u times. (realloc() counted as one time)",
static_cast<unsigned int>(heap_stats_.total_free_calls));
PW_LOG_INFO(" ");
}
// TODO: Add stack tracing to locate which call to the heap operation caused
// the corruption.
void FreeListHeap::InvalidFreeCrash() {
PW_DCHECK(false, "You tried to free an invalid pointer!");
}
} // namespace pw::allocator