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
35 #include "heap.hpp"
36
37 #if !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
38
39 #include <string.h>
40
41 #include "common/code_utils.hpp"
42 #include "common/debug.hpp"
43
44 namespace ot {
45 namespace Utils {
46
Heap(void)47 Heap::Heap(void)
48 {
49 Block &super = BlockAt(kSuperBlockOffset);
50 super.SetSize(kSuperBlockSize);
51
52 Block &first = BlockRight(super);
53 first.SetSize(kFirstBlockSize);
54
55 Block &guard = BlockRight(first);
56 guard.SetSize(Block::kGuardBlockSize);
57
58 super.SetNext(BlockOffset(first));
59 first.SetNext(BlockOffset(guard));
60
61 mMemory.mFreeSize = kFirstBlockSize;
62 }
63
CAlloc(size_t aCount,size_t aSize)64 void *Heap::CAlloc(size_t aCount, size_t aSize)
65 {
66 void * ret = nullptr;
67 Block * prev = nullptr;
68 Block * curr = nullptr;
69 uint16_t size = static_cast<uint16_t>(aCount * aSize);
70
71 VerifyOrExit(size);
72
73 size += kAlignSize - 1 - kBlockRemainderSize;
74 size &= ~(kAlignSize - 1);
75 size += kBlockRemainderSize;
76
77 prev = &BlockSuper();
78 curr = &BlockNext(*prev);
79
80 while (curr->GetSize() < size)
81 {
82 prev = curr;
83 curr = &BlockNext(*curr);
84 }
85
86 VerifyOrExit(curr->IsFree());
87
88 prev->SetNext(curr->GetNext());
89
90 if (curr->GetSize() > size + sizeof(Block))
91 {
92 const uint16_t newBlockSize = curr->GetSize() - size - sizeof(Block);
93 curr->SetSize(size);
94
95 Block &newBlock = BlockRight(*curr);
96 newBlock.SetSize(newBlockSize);
97 newBlock.SetNext(0);
98
99 if (prev->GetSize() < newBlockSize)
100 {
101 BlockInsert(*prev, newBlock);
102 }
103 else
104 {
105 BlockInsert(BlockSuper(), newBlock);
106 }
107
108 mMemory.mFreeSize -= sizeof(Block);
109 }
110
111 mMemory.mFreeSize -= curr->GetSize();
112
113 curr->SetNext(0);
114
115 memset(curr->GetPointer(), 0, size);
116 ret = curr->GetPointer();
117
118 exit:
119 return ret;
120 }
121
BlockInsert(Block & aPrev,Block & aBlock)122 void Heap::BlockInsert(Block &aPrev, Block &aBlock)
123 {
124 Block *prev = &aPrev;
125
126 for (Block *block = &BlockNext(*prev); block->GetSize() < aBlock.GetSize(); block = &BlockNext(*block))
127 {
128 prev = block;
129 }
130
131 aBlock.SetNext(prev->GetNext());
132 prev->SetNext(BlockOffset(aBlock));
133 }
134
BlockPrev(const Block & aBlock)135 Block &Heap::BlockPrev(const Block &aBlock)
136 {
137 Block *prev = &BlockSuper();
138
139 while (prev->GetNext() != BlockOffset(aBlock))
140 {
141 prev = &BlockNext(*prev);
142 }
143
144 return *prev;
145 }
146
Free(void * aPointer)147 void Heap::Free(void *aPointer)
148 {
149 if (aPointer == nullptr)
150 {
151 return;
152 }
153
154 Block &block = BlockOf(aPointer);
155 Block &right = BlockRight(block);
156
157 mMemory.mFreeSize += block.GetSize();
158
159 if (IsLeftFree(block))
160 {
161 Block *prev = &BlockSuper();
162 Block *left = &BlockNext(*prev);
163
164 mMemory.mFreeSize += sizeof(Block);
165
166 for (const uint16_t offset = block.GetLeftNext(); left->GetNext() != offset; left = &BlockNext(*left))
167 {
168 prev = left;
169 }
170
171 // Remove left from free list.
172 prev->SetNext(left->GetNext());
173 left->SetNext(0);
174
175 if (right.IsFree())
176 {
177 mMemory.mFreeSize += sizeof(Block);
178
179 if (right.GetSize() > left->GetSize())
180 {
181 for (const uint16_t offset = BlockOffset(right); prev->GetNext() != offset; prev = &BlockNext(*prev))
182 ;
183 }
184 else
185 {
186 prev = &BlockPrev(right);
187 }
188
189 // Remove right from free list.
190 prev->SetNext(right.GetNext());
191 right.SetNext(0);
192
193 // Add size of right.
194 left->SetSize(left->GetSize() + right.GetSize() + sizeof(Block));
195 }
196
197 // Add size of current block.
198 left->SetSize(left->GetSize() + block.GetSize() + sizeof(Block));
199
200 BlockInsert(*prev, *left);
201 }
202 else
203 {
204 if (right.IsFree())
205 {
206 Block &prev = BlockPrev(right);
207 prev.SetNext(right.GetNext());
208 block.SetSize(block.GetSize() + right.GetSize() + sizeof(Block));
209 BlockInsert(prev, block);
210
211 mMemory.mFreeSize += sizeof(Block);
212 }
213 else
214 {
215 BlockInsert(BlockSuper(), block);
216 }
217 }
218 }
219
220 } // namespace Utils
221 } // namespace ot
222
223 #endif // !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
224
