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/check.h"
20 #include "pw_log/log.h"
21
22 namespace pw::allocator {
23
FreeListHeap(span<std::byte> region,FreeList & freelist)24 FreeListHeap::FreeListHeap(span<std::byte> region, FreeList& freelist)
25 : freelist_(freelist), heap_stats_() {
26 auto result = BlockType::Init(region);
27 PW_CHECK_OK(
28 result.status(),
29 "Failed to initialize FreeListHeap region; misaligned or too small");
30 BlockType* block = *result;
31 block->CrashIfInvalid();
32
33 freelist_.AddChunk(BlockToSpan(block))
34 .IgnoreError(); // TODO: b/242598609 - Handle Status properly
35
36 region_ = region;
37 heap_stats_.total_bytes = region.size();
38 }
39
Allocate(size_t size)40 void* FreeListHeap::Allocate(size_t size) {
41 // Find a chunk in the freelist. Split it if needed, then return
42
43 auto chunk = freelist_.FindChunk(size);
44
45 if (chunk.data() == nullptr) {
46 return nullptr;
47 }
48 freelist_.RemoveChunk(chunk)
49 .IgnoreError(); // TODO: b/242598609 - Handle Status properly
50
51 BlockType* chunk_block = BlockType::FromUsableSpace(chunk.data());
52
53 chunk_block->CrashIfInvalid();
54
55 // Split that chunk. If there's a leftover chunk, add it to the freelist
56 Result<BlockType*> result = BlockType::Split(chunk_block, size);
57 if (result.ok()) {
58 freelist_.AddChunk(BlockToSpan(*result))
59 .IgnoreError(); // TODO: b/242598609 - Handle Status properly
60 }
61
62 chunk_block->MarkUsed();
63
64 heap_stats_.bytes_allocated += size;
65 heap_stats_.cumulative_allocated += size;
66 heap_stats_.total_allocate_calls += 1;
67
68 return chunk_block->UsableSpace();
69 }
70
Free(void * ptr)71 void FreeListHeap::Free(void* ptr) {
72 std::byte* bytes = static_cast<std::byte*>(ptr);
73
74 if (bytes < region_.data() || bytes >= region_.data() + region_.size()) {
75 InvalidFreeCrash();
76 return;
77 }
78
79 BlockType* chunk_block = BlockType::FromUsableSpace(bytes);
80 chunk_block->CrashIfInvalid();
81
82 size_t size_freed = chunk_block->InnerSize();
83 // Ensure that the block is in-use
84 if (!chunk_block->Used()) {
85 InvalidFreeCrash();
86 return;
87 }
88 chunk_block->MarkFree();
89 // Can we combine with the left or right blocks?
90 BlockType* prev = chunk_block->Prev();
91 BlockType* next = nullptr;
92
93 if (!chunk_block->Last()) {
94 next = chunk_block->Next();
95 }
96
97 if (prev != nullptr && !prev->Used()) {
98 // Remove from freelist and merge
99 freelist_.RemoveChunk(BlockToSpan(prev))
100 .IgnoreError(); // TODO: b/242598609 - Handle Status properly
101 chunk_block = chunk_block->Prev();
102 BlockType::MergeNext(chunk_block)
103 .IgnoreError(); // TODO: b/242598609 - Handle Status properly
104 }
105
106 if (next != nullptr && !next->Used()) {
107 freelist_.RemoveChunk(BlockToSpan(next))
108 .IgnoreError(); // TODO: b/242598609 - Handle Status properly
109 BlockType::MergeNext(chunk_block)
110 .IgnoreError(); // TODO: b/242598609 - Handle Status properly
111 }
112 // Add back to the freelist
113 freelist_.AddChunk(BlockToSpan(chunk_block))
114 .IgnoreError(); // TODO: b/242598609 - Handle Status properly
115
116 heap_stats_.bytes_allocated -= size_freed;
117 heap_stats_.cumulative_freed += size_freed;
118 heap_stats_.total_free_calls += 1;
119 }
120
121 // Follows constract of the C standard realloc() function
122 // If ptr is free'd, will return nullptr.
Realloc(void * ptr,size_t size)123 void* FreeListHeap::Realloc(void* ptr, size_t size) {
124 if (size == 0) {
125 Free(ptr);
126 return nullptr;
127 }
128
129 // If the pointer is nullptr, allocate a new memory.
130 if (ptr == nullptr) {
131 return Allocate(size);
132 }
133
134 std::byte* bytes = static_cast<std::byte*>(ptr);
135
136 // TODO(chenghanzh): Enhance with debug information for out-of-range and more.
137 if (bytes < region_.data() || bytes >= region_.data() + region_.size()) {
138 return nullptr;
139 }
140
141 BlockType* chunk_block = BlockType::FromUsableSpace(bytes);
142 if (!chunk_block->Used()) {
143 return nullptr;
144 }
145 size_t old_size = chunk_block->InnerSize();
146
147 // Do nothing and return ptr if the required memory size is smaller than
148 // the current size.
149 // TODO(keir): Currently do not support shrink of memory chunk.
150 if (old_size >= size) {
151 return ptr;
152 }
153
154 void* new_ptr = Allocate(size);
155 // Don't invalidate ptr if Allocate(size) fails to initilize the memory.
156 if (new_ptr == nullptr) {
157 return nullptr;
158 }
159 memcpy(new_ptr, ptr, old_size);
160
161 Free(ptr);
162 return new_ptr;
163 }
164
Calloc(size_t num,size_t size)165 void* FreeListHeap::Calloc(size_t num, size_t size) {
166 void* ptr = Allocate(num * size);
167 if (ptr != nullptr) {
168 memset(ptr, 0, num * size);
169 }
170 return ptr;
171 }
172
LogHeapStats()173 void FreeListHeap::LogHeapStats() {
174 PW_LOG_INFO(" ");
175 PW_LOG_INFO(" The current heap information: ");
176 PW_LOG_INFO(" The total heap size is %u bytes.",
177 static_cast<unsigned int>(heap_stats_.total_bytes));
178 PW_LOG_INFO(" The current allocated heap memory is %u bytes.",
179 static_cast<unsigned int>(heap_stats_.bytes_allocated));
180 PW_LOG_INFO(" The cumulative allocated heap memory is %u bytes.",
181 static_cast<unsigned int>(heap_stats_.cumulative_allocated));
182 PW_LOG_INFO(" The cumulative freed heap memory is %u bytes.",
183 static_cast<unsigned int>(heap_stats_.cumulative_freed));
184 PW_LOG_INFO(
185 " malloc() is called %u times. (realloc()/calloc() counted as "
186 "one time)",
187 static_cast<unsigned int>(heap_stats_.total_allocate_calls));
188 PW_LOG_INFO(
189 " free() is called %u times. (realloc() counted as one time)",
190 static_cast<unsigned int>(heap_stats_.total_free_calls));
191 PW_LOG_INFO(" ");
192 }
193
194 // TODO(keir): Add stack tracing to locate which call to the heap operation
195 // caused the corruption.
InvalidFreeCrash()196 void FreeListHeap::InvalidFreeCrash() {
197 PW_DCHECK(false, "You tried to free an invalid pointer!");
198 }
199
200 } // namespace pw::allocator
201