Line data Source code
1 : /*
2 : *
3 : * Copyright (c) 2021 Project CHIP Authors
4 : * Copyright 2019 Google Inc. All Rights Reserved.
5 : *
6 : * Licensed under the Apache License, Version 2.0 (the "License");
7 : * you may not use this file except in compliance with the License.
8 : * You may obtain a copy of the License at
9 : *
10 : * http://www.apache.org/licenses/LICENSE-2.0
11 : *
12 : * Unless required by applicable law or agreed to in writing, software
13 : * distributed under the License is distributed on an "AS IS" BASIS,
14 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 : * See the License for the specific language governing permissions and
16 : * limitations under the License.
17 : */
18 :
19 : #include "PrivateHeap.h"
20 :
21 : #include <string.h>
22 :
23 : #include <lib/support/CodeUtils.h>
24 : #include <lib/support/logging/CHIPLogging.h>
25 :
26 : namespace {
27 :
28 : constexpr uint32_t kInvalidHeapBlockSize = 0xFFFFFFFF;
29 : constexpr int32_t kHeapBlockInUse = 0x01;
30 : constexpr int32_t kHeapBlockFree = 0x10;
31 : constexpr int32_t kInvalidHeaderState = 0xff;
32 :
33 : using internal::PrivateHeapBlockHeader;
34 :
35 : // this makes life easier, no need to add align offsets.
36 : static_assert(sizeof(PrivateHeapBlockHeader) % kPrivateHeapAllocationAlignment == 0, "Invalid block size.");
37 :
38 1703 : uint32_t ComputeHeapBlockChecksum(const PrivateHeapBlockHeader * header)
39 : {
40 1703 : uint32_t checksum = header->prevBytes;
41 1703 : checksum *= 31;
42 1703 : checksum += header->nextBytes;
43 1703 : checksum *= 31;
44 1703 : checksum += header->state;
45 1703 : return checksum;
46 : }
47 :
48 : // Advances the heap block to the next value
49 633 : PrivateHeapBlockHeader * NextHeader(PrivateHeapBlockHeader * start)
50 : {
51 633 : if (start->nextBytes == kInvalidHeapBlockSize)
52 : {
53 27 : return nullptr;
54 : }
55 :
56 606 : if (start->checksum != ComputeHeapBlockChecksum(start))
57 : {
58 0 : ChipLogError(Support, "Corrupted heap: checksum is invalid");
59 0 : chipDie();
60 : }
61 :
62 606 : return reinterpret_cast<PrivateHeapBlockHeader *>(reinterpret_cast<char *>(start) + sizeof(PrivateHeapBlockHeader) +
63 606 : start->nextBytes);
64 : }
65 :
66 : // Advances the heap block to the previous value
67 103 : PrivateHeapBlockHeader * PreviousHeader(PrivateHeapBlockHeader * start)
68 : {
69 103 : if (start->prevBytes == kInvalidHeapBlockSize)
70 : {
71 47 : return nullptr;
72 : }
73 :
74 56 : if (start->checksum != ComputeHeapBlockChecksum(start))
75 : {
76 0 : ChipLogError(Support, "Corrupted heap: checksum is invalid");
77 0 : chipDie();
78 : }
79 :
80 56 : return reinterpret_cast<PrivateHeapBlockHeader *>(reinterpret_cast<char *>(start) - sizeof(PrivateHeapBlockHeader) -
81 56 : start->prevBytes);
82 : }
83 :
84 649 : void ValidateHeader(const PrivateHeapBlockHeader * header)
85 : {
86 649 : if (header->state != kHeapBlockFree && header->state != kHeapBlockInUse)
87 : {
88 0 : ChipLogError(Support, "Invalid header state (neither free nor in use) at %p", header);
89 0 : chipDie();
90 : }
91 :
92 649 : if (header->checksum != ComputeHeapBlockChecksum(header))
93 : {
94 0 : ChipLogError(Support, "Corrupted heap: checksum is invalid at %p", header);
95 0 : chipDie();
96 : }
97 649 : }
98 :
99 : } // namespace
100 :
101 9 : extern "C" void PrivateHeapInit(void * heap, size_t size)
102 : {
103 9 : if (heap == nullptr)
104 : {
105 0 : ChipLogError(Support, "Cannot initialize null heap");
106 0 : chipDie();
107 : }
108 :
109 9 : if (size < 2 * sizeof(PrivateHeapBlockHeader))
110 : {
111 0 : ChipLogError(Support, "Insufficient space in private heap");
112 0 : chipDie();
113 : }
114 :
115 9 : if (reinterpret_cast<uintptr_t>(heap) % kPrivateHeapAllocationAlignment != 0)
116 : {
117 0 : ChipLogError(Support, "Invalid alignment for private heap initialization");
118 0 : chipDie();
119 : }
120 :
121 9 : PrivateHeapBlockHeader * header = reinterpret_cast<PrivateHeapBlockHeader *>(heap);
122 :
123 9 : header->prevBytes = kInvalidHeapBlockSize;
124 9 : header->nextBytes = static_cast<uint32_t>(size - 2 * sizeof(PrivateHeapBlockHeader));
125 9 : header->state = kHeapBlockFree;
126 9 : header->checksum = ComputeHeapBlockChecksum(header);
127 :
128 9 : header = NextHeader(header);
129 9 : header->nextBytes = kInvalidHeapBlockSize;
130 9 : header->prevBytes = static_cast<uint32_t>(size - 2 * sizeof(PrivateHeapBlockHeader));
131 9 : header->state = kHeapBlockFree; // does not matter really
132 9 : header->checksum = ComputeHeapBlockChecksum(header);
133 9 : }
134 :
135 130 : extern "C" void * PrivateHeapAlloc(void * heap, size_t size)
136 : {
137 130 : PrivateHeapBlockHeader * header = reinterpret_cast<PrivateHeapBlockHeader *>(heap);
138 :
139 : // we allocate aligned, no matter what
140 130 : if (size % kPrivateHeapAllocationAlignment != 0)
141 : {
142 40 : size += kPrivateHeapAllocationAlignment - (size % kPrivateHeapAllocationAlignment);
143 : }
144 :
145 567 : for (; header != nullptr; header = NextHeader(header))
146 : {
147 540 : ValidateHeader(header);
148 :
149 540 : if (header->nextBytes == kInvalidHeapBlockSize)
150 : {
151 27 : continue;
152 : }
153 :
154 513 : if (header->state != kHeapBlockFree)
155 : {
156 403 : continue; // not free
157 : }
158 :
159 110 : if (header->nextBytes < size)
160 : {
161 7 : continue; // insufficient space
162 : }
163 :
164 103 : if (header->nextBytes - size < sizeof(PrivateHeapBlockHeader) + kPrivateHeapAllocationAlignment)
165 : {
166 : // allocate the entire block
167 61 : header->state = kHeapBlockInUse;
168 61 : header->checksum = ComputeHeapBlockChecksum(header);
169 : }
170 : else
171 : {
172 : // splits the block into two
173 : //
174 : // +--------+ +--------+ +------+
175 : // | header | ---> | middle | ---> | next |
176 : // +--------+ +--------+ +------+
177 : //
178 42 : PrivateHeapBlockHeader * next = NextHeader(header);
179 42 : PrivateHeapBlockHeader * middle =
180 42 : reinterpret_cast<PrivateHeapBlockHeader *>(reinterpret_cast<char *>(header + 1) + size);
181 :
182 : // middle is a new block
183 42 : middle->nextBytes = static_cast<uint32_t>(header->nextBytes - size - sizeof(PrivateHeapBlockHeader));
184 42 : middle->prevBytes = static_cast<uint32_t>(size);
185 42 : middle->state = kHeapBlockFree;
186 42 : middle->checksum = ComputeHeapBlockChecksum(middle);
187 :
188 : // fix up the header
189 42 : header->nextBytes = static_cast<uint32_t>(size);
190 42 : header->state = kHeapBlockInUse;
191 42 : header->checksum = ComputeHeapBlockChecksum(header);
192 :
193 : // fix up the final block
194 42 : if (next != nullptr)
195 : {
196 42 : next->prevBytes = middle->nextBytes;
197 42 : next->checksum = ComputeHeapBlockChecksum(next);
198 : }
199 : }
200 :
201 : // we can now use the header
202 103 : return header + 1; // data right after the header
203 : }
204 :
205 : // no space found
206 27 : return nullptr;
207 : }
208 :
209 103 : extern "C" void PrivateHeapFree(void * ptr)
210 : {
211 103 : if (ptr == nullptr)
212 : {
213 : // freeing NULL pointers is always acceptable and a noop
214 0 : return;
215 : }
216 :
217 103 : PrivateHeapBlockHeader * header =
218 : reinterpret_cast<PrivateHeapBlockHeader *>(static_cast<char *>(ptr) - sizeof(PrivateHeapBlockHeader));
219 :
220 103 : ValidateHeader(header);
221 103 : header->state = kHeapBlockFree;
222 103 : header->checksum = ComputeHeapBlockChecksum(header);
223 :
224 : // Merge with previous
225 : //
226 : // +-------+ +--------+
227 : // | other | ----- nextBytes -----> | header |
228 : // +-------+ +--------+
229 : //
230 103 : PrivateHeapBlockHeader * other = PreviousHeader(header);
231 103 : if (other != nullptr && other->state == kHeapBlockFree && other->nextBytes != kInvalidHeapBlockSize)
232 : {
233 : // includes the free bytes in this block in the previous
234 20 : other->nextBytes += static_cast<uint32_t>(header->nextBytes + sizeof(PrivateHeapBlockHeader));
235 20 : other->checksum = ComputeHeapBlockChecksum(other);
236 20 : header->state = kInvalidHeaderState;
237 20 : header = other;
238 :
239 : // fixes up the next block
240 20 : other = NextHeader(header);
241 20 : if (other != nullptr)
242 : {
243 20 : other->prevBytes = header->nextBytes;
244 20 : other->checksum = ComputeHeapBlockChecksum(other);
245 : }
246 : }
247 :
248 : // Merge with next
249 : //
250 : // +--------+ +-------+
251 : // | header | ----- nextBytes -----> | other |
252 : // +--------+ +-------+
253 : //
254 103 : other = NextHeader(header);
255 103 : if (other != nullptr && other->state == kHeapBlockFree && other->nextBytes != kInvalidHeapBlockSize)
256 : {
257 : // includes the free bytes in the next block
258 22 : other->state = kInvalidHeaderState;
259 22 : header->nextBytes += static_cast<uint32_t>(other->nextBytes + sizeof(PrivateHeapBlockHeader));
260 22 : header->checksum = ComputeHeapBlockChecksum(header);
261 :
262 : // fixes up the next block
263 22 : other = NextHeader(header);
264 22 : if (other != nullptr)
265 : {
266 22 : other->prevBytes = header->nextBytes;
267 22 : other->checksum = ComputeHeapBlockChecksum(other);
268 : }
269 : }
270 : }
271 :
272 7 : void * PrivateHeapRealloc(void * heap, void * ptr, size_t size)
273 : {
274 7 : if (ptr == nullptr)
275 : {
276 1 : return PrivateHeapAlloc(heap, size);
277 : }
278 :
279 6 : if (size == 0)
280 : {
281 0 : PrivateHeapFree(ptr);
282 0 : return nullptr;
283 : }
284 :
285 6 : PrivateHeapBlockHeader * header =
286 : reinterpret_cast<PrivateHeapBlockHeader *>(static_cast<char *>(ptr) - sizeof(PrivateHeapBlockHeader));
287 :
288 6 : ValidateHeader(header);
289 :
290 6 : if (header->nextBytes >= size)
291 : {
292 3 : return ptr; // no reallocation needed
293 : }
294 :
295 3 : void * largerCopy = PrivateHeapAlloc(heap, size);
296 3 : if (largerCopy == nullptr)
297 : {
298 : // NOTE: original is left untouched (not freed) to match realloc() libc
299 : // functionality
300 2 : return nullptr;
301 : }
302 :
303 1 : memcpy(largerCopy, ptr, header->nextBytes);
304 1 : PrivateHeapFree(ptr);
305 :
306 1 : return largerCopy;
307 : }
308 :
309 0 : extern "C" void PrivateHeapDump(void * top)
310 : {
311 0 : PrivateHeapBlockHeader * header = reinterpret_cast<PrivateHeapBlockHeader *>(top);
312 :
313 0 : ChipLogProgress(Support, "========= HEAP ===========");
314 0 : while (header->nextBytes != kInvalidHeapBlockSize)
315 : {
316 0 : ChipLogProgress(Support, " %td: size: %d, state: %d", reinterpret_cast<char *>(header) - reinterpret_cast<char *>(top),
317 : static_cast<int>(header->nextBytes), static_cast<int>(header->state));
318 :
319 0 : header = NextHeader(header);
320 : }
321 0 : }
|
