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