1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
// 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/check.h"
#include "pw_log/log.h"
namespace pw::allocator {
FreeListHeap::FreeListHeap(span<std::byte> region, FreeList& freelist)
: freelist_(freelist), heap_stats_() {
Block* block;
PW_CHECK_OK(
Block::Init(region, &block),
"Failed to initialize FreeListHeap region; misaligned or too small");
freelist_.AddChunk(BlockToSpan(block))
.IgnoreError(); // TODO(b/242598609): Handle Status properly
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)
.IgnoreError(); // TODO(b/242598609): Handle Status properly
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))
.IgnoreError(); // TODO(b/242598609): Handle Status properly
}
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))
.IgnoreError(); // TODO(b/242598609): Handle Status properly
chunk_block->MergePrev()
.IgnoreError(); // TODO(b/242598609): Handle Status properly
// chunk_block is now invalid; prev now encompasses it.
chunk_block = prev;
}
if (next != nullptr && !next->Used()) {
freelist_.RemoveChunk(BlockToSpan(next))
.IgnoreError(); // TODO(b/242598609): Handle Status properly
chunk_block->MergeNext()
.IgnoreError(); // TODO(b/242598609): Handle Status properly
}
// Add back to the freelist
freelist_.AddChunk(BlockToSpan(chunk_block))
.IgnoreError(); // TODO(b/242598609): Handle Status properly
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(keir): 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(keir): 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
|
