1 /*
2 * Copyright (c) 2017, The OpenThread Authors.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. Neither the name of the copyright holder nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /**
30 * @file
31 * This file implements heap.
32 */
33
34 #include "heap.hpp"
35
36 #if !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
37
38 #include <string.h>
39
40 #include "common/code_utils.hpp"
41 #include "common/debug.hpp"
42
43 namespace ot {
44 namespace Utils {
45
Heap(void)46 Heap::Heap(void)
47 {
48 Block &super = BlockAt(kSuperBlockOffset);
49 super.SetSize(kSuperBlockSize);
50
51 Block &first = BlockRight(super);
52 first.SetSize(kFirstBlockSize);
53
54 Block &guard = BlockRight(first);
55 guard.SetSize(Block::kGuardBlockSize);
56
57 super.SetNext(BlockOffset(first));
58 first.SetNext(BlockOffset(guard));
59
60 mMemory.mFreeSize = kFirstBlockSize;
61 }
62
CAlloc(size_t aCount,size_t aSize)63 void *Heap::CAlloc(size_t aCount, size_t aSize)
64 {
65 void *ret = nullptr;
66 Block *prev = nullptr;
67 Block *curr = nullptr;
68 uint16_t size = static_cast<uint16_t>(aCount * aSize);
69
70 VerifyOrExit(size);
71
72 size += kAlignSize - 1 - kBlockRemainderSize;
73 size &= ~(kAlignSize - 1);
74 size += kBlockRemainderSize;
75
76 prev = &BlockSuper();
77 curr = &BlockNext(*prev);
78
79 while (curr->GetSize() < size)
80 {
81 prev = curr;
82 curr = &BlockNext(*curr);
83 }
84
85 VerifyOrExit(curr->IsFree());
86
87 prev->SetNext(curr->GetNext());
88
89 if (curr->GetSize() > size + sizeof(Block))
90 {
91 const uint16_t newBlockSize = curr->GetSize() - size - sizeof(Block);
92 curr->SetSize(size);
93
94 Block &newBlock = BlockRight(*curr);
95 newBlock.SetSize(newBlockSize);
96 newBlock.SetNext(0);
97
98 if (prev->GetSize() < newBlockSize)
99 {
100 BlockInsert(*prev, newBlock);
101 }
102 else
103 {
104 BlockInsert(BlockSuper(), newBlock);
105 }
106
107 mMemory.mFreeSize -= sizeof(Block);
108 }
109
110 mMemory.mFreeSize -= curr->GetSize();
111
112 curr->SetNext(0);
113
114 memset(curr->GetPointer(), 0, size);
115 ret = curr->GetPointer();
116
117 exit:
118 return ret;
119 }
120
BlockInsert(Block & aPrev,Block & aBlock)121 void Heap::BlockInsert(Block &aPrev, Block &aBlock)
122 {
123 Block *prev = &aPrev;
124
125 for (Block *block = &BlockNext(*prev); block->GetSize() < aBlock.GetSize(); block = &BlockNext(*block))
126 {
127 prev = block;
128 }
129
130 aBlock.SetNext(prev->GetNext());
131 prev->SetNext(BlockOffset(aBlock));
132 }
133
BlockPrev(const Block & aBlock)134 Block &Heap::BlockPrev(const Block &aBlock)
135 {
136 Block *prev = &BlockSuper();
137
138 while (prev->GetNext() != BlockOffset(aBlock))
139 {
140 prev = &BlockNext(*prev);
141 }
142
143 return *prev;
144 }
145
Free(void * aPointer)146 void Heap::Free(void *aPointer)
147 {
148 if (aPointer == nullptr)
149 {
150 return;
151 }
152
153 Block &block = BlockOf(aPointer);
154 Block &right = BlockRight(block);
155
156 mMemory.mFreeSize += block.GetSize();
157
158 if (IsLeftFree(block))
159 {
160 Block *prev = &BlockSuper();
161 Block *left = &BlockNext(*prev);
162
163 mMemory.mFreeSize += sizeof(Block);
164
165 for (const uint16_t offset = block.GetLeftNext(); left->GetNext() != offset; left = &BlockNext(*left))
166 {
167 prev = left;
168 }
169
170 // Remove left from free list.
171 prev->SetNext(left->GetNext());
172 left->SetNext(0);
173
174 if (right.IsFree())
175 {
176 mMemory.mFreeSize += sizeof(Block);
177
178 if (right.GetSize() > left->GetSize())
179 {
180 for (const uint16_t offset = BlockOffset(right); prev->GetNext() != offset; prev = &BlockNext(*prev))
181 ;
182 }
183 else
184 {
185 prev = &BlockPrev(right);
186 }
187
188 // Remove right from free list.
189 prev->SetNext(right.GetNext());
190 right.SetNext(0);
191
192 // Add size of right.
193 left->SetSize(left->GetSize() + right.GetSize() + sizeof(Block));
194 }
195
196 // Add size of current block.
197 left->SetSize(left->GetSize() + block.GetSize() + sizeof(Block));
198
199 BlockInsert(*prev, *left);
200 }
201 else
202 {
203 if (right.IsFree())
204 {
205 Block &prev = BlockPrev(right);
206 prev.SetNext(right.GetNext());
207 block.SetSize(block.GetSize() + right.GetSize() + sizeof(Block));
208 BlockInsert(prev, block);
209
210 mMemory.mFreeSize += sizeof(Block);
211 }
212 else
213 {
214 BlockInsert(BlockSuper(), block);
215 }
216 }
217 }
218
219 } // namespace Utils
220 } // namespace ot
221
222 #endif // !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
223