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
FreeListHeap(std::span<std::byte> region,FreeList & freelist)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
Allocate(size_t size)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
Free(void * ptr)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.
Realloc(void * ptr,size_t size)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
Calloc(size_t num,size_t size)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
LogHeapStats()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.
InvalidFreeCrash()189 void FreeListHeap::InvalidFreeCrash() {
190 PW_DCHECK(false, "You tried to free an invalid pointer!");
191 }
192
193 } // namespace pw::allocator
194