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