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 includes definitions for heap.
32  *
33  */
34 
35 #ifndef OT_UTILS_HEAP_HPP_
36 #define OT_UTILS_HEAP_HPP_
37 
38 #include "openthread-core-config.h"
39 
40 #if !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
41 
42 #include <stddef.h>
43 #include <stdint.h>
44 
45 #include "common/const_cast.hpp"
46 #include "common/non_copyable.hpp"
47 
48 namespace ot {
49 namespace Utils {
50 
51 /**
52  * Represents a memory block.
53  *
54  * A block is of the structure as below.
55  *
56  *     +------------------------------+
57  *     | mSize   |  mMemory |  mNext  |
58  *     |---------|----------| --------|
59  *     | 2 bytes |  n bytes | 2 bytes |
60  *     +------------------------------+
61  *
62  * Since block metadata is of 4-byte size, mSize and mNext are separated at the beginning
63  * and end of the block to make sure the mMemory is aligned with long.
64  *
65  */
66 class Block
67 {
68     friend class Heap;
69 
70 public:
71     /**
72      * Returns the size of this block.
73      *
74      * @returns Size of this block.
75      *
76      */
GetSize(void) const77     uint16_t GetSize(void) const { return mSize; }
78 
79     /**
80      * Updates the size of this block.
81      *
82      * @param[in]   aSize   Size of this block in bytes.
83      *
84      */
SetSize(uint16_t aSize)85     void SetSize(uint16_t aSize) { mSize = aSize; }
86 
87     /**
88      * Returns the offset of the free block after this block.
89      *
90      * @note This offset is relative to the start of the heap.
91      *
92      * @returns Offset of the next free block in bytes.
93      *
94      * @retval  0   This block is not free.
95      *
96      */
GetNext(void) const97     uint16_t GetNext(void) const
98     {
99         return *reinterpret_cast<const uint16_t *>(
100             reinterpret_cast<const void *>(reinterpret_cast<const uint8_t *>(this) + sizeof(mSize) + mSize));
101     }
102 
103     /**
104      * Updates the offset of the free block after this block.
105      *
106      * @note This offset @p aNext must be relative to the start of the heap.
107      *
108      * @param[in]   aNext   Offset of the next free block in bytes.
109      *
110      */
SetNext(uint16_t aNext)111     void SetNext(uint16_t aNext)
112     {
113         *reinterpret_cast<uint16_t *>(
114             reinterpret_cast<void *>(reinterpret_cast<uint8_t *>(this) + sizeof(mSize) + mSize)) = aNext;
115     }
116 
117     /**
118      * Returns the pointer to the start of the memory for user.
119      *
120      * @retval  Pointer to the user memory. The pointer address is aligned to sizeof(long).
121      *
122      */
GetPointer(void)123     void *GetPointer(void) { return &mMemory; }
124 
125     /**
126      * Returns the offset of the free block after the left neighbor block.
127      *
128      * @returns Offset in bytes.
129      *
130      */
GetLeftNext(void) const131     uint16_t GetLeftNext(void) const { return *(&mSize - 1); }
132 
133     /**
134      * Returns whether the left neighbor block is a free block.
135      *
136      * @retval  true    The left neighbor block is free.
137      * @retval  false   The left neighbor block is not free.
138      *
139      */
IsLeftFree(void) const140     bool IsLeftFree(void) const { return GetLeftNext() != 0; }
141 
142     /**
143      * Returns whether the current block is a free block.
144      *
145      * @retval  true    The block is free.
146      * @retval  false   The block is not free.
147      *
148      */
IsFree(void) const149     bool IsFree(void) const { return mSize != kGuardBlockSize && GetNext() != 0; }
150 
151 private:
152     static constexpr uint16_t kGuardBlockSize = 0xffff; // Size value of the guard block.
153 
154     uint16_t mSize; // Number of bytes in mMemory.
155 
156     // Memory for user, with size of `mNext` to ensure size of this
157     // structure is equal to size of block metadata, i.e.,
158     // sizeof(mSize) + sizeof(mNext).
159     uint8_t mMemory[sizeof(uint16_t)];
160 };
161 
162 /**
163  * Defines functionality to manipulate heap.
164  *
165  * This implementation is currently for mbedTLS.
166  *
167  * The memory is divided into blocks. The whole picture is as follows:
168  *
169  *     +--------------------------------------------------------------------------+
170  *     |    unused      |    super   | block 1 | block 2 | ... | block n | guard  |
171  *     +----------------+------------+---------+---------+-----+---------+--------+
172  *     | kAlignSize - 2 | kAlignSize | 4 + s1  | 4 + s2  | ... | 4 + s4  |   2    |
173  *     +--------------------------------------------------------------------------+
174  *
175  */
176 class Heap : private NonCopyable
177 {
178 public:
179     /**
180      * Initializes a memory heap.
181      *
182      */
183     Heap(void);
184 
185     /**
186      * Allocates at least @p aCount * @aSize bytes memory and initialize to zero.
187      *
188      * @param[in]   aCount  Number of allocate units.
189      * @param[in]   aSize   Unit size in bytes.
190      *
191      * @returns A pointer to the allocated memory.
192      *
193      * @retval  nullptr    Indicates not enough memory.
194      *
195      */
196     void *CAlloc(size_t aCount, size_t aSize);
197 
198     /**
199      * Free memory pointed by @p aPointer.
200      *
201      * @param[in]   aPointer    A pointer to the memory to free.
202      *
203      */
204     void Free(void *aPointer);
205 
206     /**
207      * Returns whether the heap is clean.
208      *
209      */
IsClean(void) const210     bool IsClean(void) const
211     {
212         Heap        &self  = *AsNonConst(this);
213         const Block &super = self.BlockSuper();
214         const Block &first = self.BlockRight(super);
215         return super.GetNext() == self.BlockOffset(first) && first.GetSize() == kFirstBlockSize;
216     }
217 
218     /**
219      * Returns the capacity of this heap.
220      *
221      */
GetCapacity(void) const222     size_t GetCapacity(void) const { return kFirstBlockSize; }
223 
224     /**
225      * Returns free space of this heap.
226      */
GetFreeSize(void) const227     size_t GetFreeSize(void) const { return mMemory.mFreeSize; }
228 
229 private:
230 #if OPENTHREAD_CONFIG_TLS_ENABLE || OPENTHREAD_CONFIG_SECURE_TRANSPORT_ENABLE
231     static constexpr uint16_t kMemorySize = OPENTHREAD_CONFIG_HEAP_INTERNAL_SIZE;
232 #else
233     static constexpr uint16_t kMemorySize = OPENTHREAD_CONFIG_HEAP_INTERNAL_SIZE_NO_DTLS;
234 #endif
235     static constexpr uint16_t kAlignSize          = sizeof(void *);
236     static constexpr uint16_t kBlockRemainderSize = kAlignSize - sizeof(uint16_t) * 2;
237     static constexpr uint16_t kSuperBlockSize     = kAlignSize - sizeof(Block);
238     static constexpr uint16_t kFirstBlockSize     = kMemorySize - kAlignSize * 3 + kBlockRemainderSize;
239     static constexpr uint16_t kSuperBlockOffset   = kAlignSize - sizeof(uint16_t);
240     static constexpr uint16_t kFirstBlockOffset   = kAlignSize * 2 - sizeof(uint16_t);
241     static constexpr uint16_t kGuardBlockOffset   = kMemorySize - sizeof(uint16_t);
242 
243     static_assert(kMemorySize % kAlignSize == 0, "The heap memory size is not aligned to kAlignSize!");
244 
245     /**
246      * Returns the block at offset @p aOffset.
247      *
248      * @param[in]   aOffset     Offset in bytes.
249      *
250      * @returns A reference to the block.
251      *
252      */
BlockAt(uint16_t aOffset)253     Block &BlockAt(uint16_t aOffset) { return *reinterpret_cast<Block *>(&mMemory.m16[aOffset / 2]); }
254 
255     /**
256      * Returns the block of @p aPointer.
257      *
258      * @param[in]   aPointer     The pointer returned by CAlloc().
259      *
260      * @returns A reference to the block.
261      *
262      */
BlockOf(void * aPointer)263     Block &BlockOf(void *aPointer)
264     {
265         uint16_t offset = static_cast<uint16_t>(reinterpret_cast<uint8_t *>(aPointer) - mMemory.m8);
266         offset -= sizeof(uint16_t);
267         return BlockAt(offset);
268     }
269 
270     /**
271      * Returns the super block.
272      *
273      * @returns Reference to the super block.
274      *
275      */
BlockSuper(void)276     Block &BlockSuper(void) { return BlockAt(kSuperBlockOffset); }
277 
278     /**
279      * Returns the free block after @p aBlock in the free block list.
280      *
281      * @param[in]   aBlock  A reference to the block.
282      *
283      * @returns Reference to the free block after this block.
284      *
285      */
BlockNext(const Block & aBlock)286     Block &BlockNext(const Block &aBlock) { return BlockAt(aBlock.GetNext()); }
287 
288     /**
289      * Returns the block on the right side of @p aBlock.
290      *
291      * @param[in]   aBlock  A reference to the block.
292      *
293      * @returns Reference to the block on the right side.
294      *
295      */
BlockRight(const Block & aBlock)296     Block &BlockRight(const Block &aBlock) { return BlockAt(BlockOffset(aBlock) + sizeof(Block) + aBlock.GetSize()); }
297 
298     /**
299      * Returns the free block before @p aBlock in the free block list.
300      *
301      * @returns Reference to the free block before this block.
302      *
303      */
304     Block &BlockPrev(const Block &aBlock);
305 
306     /**
307      * Returns whether the block on the left side of @p aBlock is free.
308      *
309      * @param[in]   aBlock  A reference to the block.
310      *
311      */
IsLeftFree(const Block & aBlock)312     bool IsLeftFree(const Block &aBlock) { return (BlockOffset(aBlock) != kFirstBlockOffset && aBlock.IsLeftFree()); }
313 
314     /**
315      * Returns the offset of @p aBlock.
316      *
317      * @param[in]   aBlock  A reference to the block.
318      *
319      * @returns Offset in bytes of @p aBlock.
320      *
321      */
BlockOffset(const Block & aBlock)322     uint16_t BlockOffset(const Block &aBlock)
323     {
324         return static_cast<uint16_t>(reinterpret_cast<const uint8_t *>(&aBlock) - mMemory.m8);
325     }
326 
327     /**
328      * Inserts @p aBlock into the free block list.
329      *
330      * The free block list is single linked and is sorted by size from minimal to maximum.
331      *
332      * @param[in]   aPrev   A reference to the block after which to place @p aBlock.
333      * @param[in]   aBlock  A reference to the block.
334      *
335      */
336     void BlockInsert(Block &aPrev, Block &aBlock);
337 
338     union
339     {
340         uint16_t mFreeSize;
341         // Make sure memory is long aligned.
342         long     mLong[kMemorySize / sizeof(long)];
343         uint8_t  m8[kMemorySize];
344         uint16_t m16[kMemorySize / sizeof(uint16_t)];
345     } mMemory;
346 };
347 
348 } // namespace Utils
349 } // namespace ot
350 
351 #endif // !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE
352 
353 #endif // OT_UTILS_HEAP_HPP_
354