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