src/lib/support/tests/TestPrivateHeap.cpp

   1 /*
   2  *
   3  *    Copyright (c) 2021 Project CHIP Authors
   4  *    Copyright 2019 Google Inc. All Rights Reserved.
   5  *
   6  *    Licensed under the Apache License, Version 2.0 (the "License");
   7  *    you may not use this file except in compliance with the License.
   8  *    You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  *    Unless required by applicable law or agreed to in writing, software
  13  *    distributed under the License is distributed on an "AS IS" BASIS,
  14  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  *    See the License for the specific language governing permissions and
  16  *    limitations under the License.
  17  */
  18
  19 #include <support/PrivateHeap.h>
  20 #include <support/UnitTestRegistration.h>
  21
  22 #include <string.h>
  23
  24 #include <nlunit-test.h>
  25
  26 namespace {
  27
  28 constexpr size_t kBlockHeaderSize = sizeof(internal::PrivateHeapBlockHeader);
  29
  30 // Splitting block tests assume we know the size
  31 static_assert(kBlockHeaderSize == 16, "Test assumes block size of 16");
  32
  33 // helper class for allocating things
  34 template <size_t kSize>
  35 class PrivateHeapAllocator
  36 {
  37 public:
  38     PrivateHeapAllocator() { PrivateHeapInit(mHeap.buffer, kSize); }
  39     void * HeapAlloc(size_t size) { return PrivateHeapAlloc(mHeap.buffer, size); }
  40     void HeapFree(void * buffer) { PrivateHeapFree(buffer); }
  41     void * HeapRealloc(void * buffer, size_t size) { return PrivateHeapRealloc(mHeap.buffer, buffer, size); }
  42
  43 private:
  44     struct alignas(kPrivateHeapAllocationAlignment)
  45     {
  46         uint8_t buffer[kSize];
  47     } mHeap;
  48 };
  49
  50 void SingleHeapAllocAndFree(nlTestSuite * inSuite, void * inContext)
  51 {
  52     PrivateHeapAllocator<16 + 2 * kBlockHeaderSize> allocator;
  53
  54     NL_TEST_ASSERT(inSuite, nullptr == allocator.HeapAlloc(17)); // insufficient size
  55     void * ptr = allocator.HeapAlloc(16);
  56     NL_TEST_ASSERT(inSuite, nullptr != ptr);
  57     NL_TEST_ASSERT(inSuite, nullptr == allocator.HeapAlloc(1)); // insufficient size
  58     memset(ptr, 0xab, 16);
  59     allocator.HeapFree(ptr);
  60
  61     // allocate different sizes on this heap, see how that goes
  62     for (size_t i = 1; i < 17; ++i)
  63     {
  64         ptr = allocator.HeapAlloc(i);
  65         NL_TEST_ASSERT(inSuite, nullptr != ptr);
  66         NL_TEST_ASSERT(inSuite, nullptr == allocator.HeapAlloc(17 - i)); // insufficient size
  67         allocator.HeapFree(ptr);
  68     }
  69 }
  70
  71 void SplitHeapAllocAndFree(nlTestSuite * inSuite, void * inContext)
  72 {
  73     PrivateHeapAllocator<128> allocator;
  74     // allocator state:
  75     // <HDR-FREE> 96 <HDR-END>
  76
  77     void * p1 = allocator.HeapAlloc(30);
  78     NL_TEST_ASSERT(inSuite, nullptr != p1);
  79     // allocator state:
  80     // <HDR-IN_USE> 32 <HRD-FREE> 48 <HDR-END>
  81
  82     void * p2 = allocator.HeapAlloc(4);
  83     NL_TEST_ASSERT(inSuite, nullptr != p2);
  84     // allocator state:
  85     // <HDR-IN_USE> 32 <HRD-IN_USE> 8 <HDR-FREE> 24 <HDR-END>
  86
  87     allocator.HeapFree(p1);
  88     // allocator state:
  89     // <HDR-FREE> 32 <HRD-IN_USE> 8 <HDR-FREE> 24 <HDR-END>
  90
  91     allocator.HeapFree(p2);
  92     // allocator state:
  93     // <HDR-FREE> 96 <HDR-END>
  94
  95     p1 = allocator.HeapAlloc(90);
  96     NL_TEST_ASSERT(inSuite, nullptr != p1);
  97     allocator.HeapFree(p1);
  98 }
  99
 100 void FreeMergeNext(nlTestSuite * inSuite, void * inContext)
 101 {
 102     PrivateHeapAllocator<5 * 16> allocator;
 103
 104     void * p1 = allocator.HeapAlloc(16);
 105     void * p2 = allocator.HeapAlloc(16);
 106
 107     NL_TEST_ASSERT(inSuite, nullptr != p1);
 108     NL_TEST_ASSERT(inSuite, nullptr != p2);
 109     NL_TEST_ASSERT(inSuite, nullptr == allocator.HeapAlloc(1));
 110
 111     memset(p1, 0xab, 16);
 112     memset(p2, 0xcd, 16);
 113
 114     // freeing 1,2 should clear space
 115     allocator.HeapFree(p1);
 116     allocator.HeapFree(p2);
 117
 118     p1 = allocator.HeapAlloc(3 * 16);
 119     NL_TEST_ASSERT(inSuite, nullptr != p1);
 120     allocator.HeapFree(p1);
 121 }
 122
 123 void FreeMergePrevious(nlTestSuite * inSuite, void * inContext)
 124 {
 125     PrivateHeapAllocator<5 * 16> allocator;
 126
 127     void * p1 = allocator.HeapAlloc(16);
 128     void * p2 = allocator.HeapAlloc(16);
 129
 130     NL_TEST_ASSERT(inSuite, nullptr != p1);
 131     NL_TEST_ASSERT(inSuite, nullptr != p2);
 132     NL_TEST_ASSERT(inSuite, nullptr == allocator.HeapAlloc(1));
 133
 134     memset(p1, 0xab, 16);
 135     memset(p2, 0xcd, 16);
 136
 137     // freeing 2,1 should clear space
 138     allocator.HeapFree(p2);
 139     allocator.HeapFree(p1);
 140     p1 = allocator.HeapAlloc(3 * 16);
 141     NL_TEST_ASSERT(inSuite, nullptr != p1);
 142     allocator.HeapFree(p1);
 143 }
 144
 145 void FreeMergePreviousAndNext(nlTestSuite * inSuite, void * inContext)
 146 {
 147
 148     PrivateHeapAllocator<7 * 16> allocator;
 149
 150     void * p1 = allocator.HeapAlloc(16);
 151     void * p2 = allocator.HeapAlloc(16);
 152     void * p3 = allocator.HeapAlloc(16);
 153
 154     NL_TEST_ASSERT(inSuite, nullptr != p1);
 155     NL_TEST_ASSERT(inSuite, nullptr != p2);
 156     NL_TEST_ASSERT(inSuite, nullptr != p3);
 157     NL_TEST_ASSERT(inSuite, nullptr == allocator.HeapAlloc(1));
 158
 159     memset(p1, 0xab, 16);
 160     memset(p2, 0xcd, 16);
 161     memset(p3, 0xef, 16);
 162
 163     allocator.HeapFree(p1);
 164     allocator.HeapFree(p3);
 165     // we have 2 slots of size 16 available now
 166     NL_TEST_ASSERT(inSuite, nullptr == allocator.HeapAlloc(17));
 167
 168     // Freeing p2 makes enoug space
 169     allocator.HeapFree(p2);
 170     p1 = allocator.HeapAlloc(5 * 16);
 171     NL_TEST_ASSERT(inSuite, nullptr != p1);
 172     allocator.HeapFree(p1);
 173 }
 174
 175 void MultipleMerge(nlTestSuite * inSuite, void * inContext)
 176 {
 177     PrivateHeapAllocator<32 * kBlockHeaderSize> allocator;
 178
 179     // 31 blocks available for alloc
 180     void * p1 = allocator.HeapAlloc(2 * kBlockHeaderSize); // uses up 3 blocks
 181     void * p2 = allocator.HeapAlloc(5 * kBlockHeaderSize); // uses up 6 blocks
 182     void * p3 = allocator.HeapAlloc(8 * kBlockHeaderSize); // uses up 9 blocks
 183     void * p4 = allocator.HeapAlloc(1 * kBlockHeaderSize); // uses up 2 blocks
 184     void * p5 = allocator.HeapAlloc(7 * kBlockHeaderSize); // uses up 8 blocks
 185     void * p6 = allocator.HeapAlloc(2 * kBlockHeaderSize); // uses up 2 (last given)
 186
 187     NL_TEST_ASSERT(inSuite, nullptr != p1);
 188     NL_TEST_ASSERT(inSuite, nullptr != p2);
 189     NL_TEST_ASSERT(inSuite, nullptr != p3);
 190     NL_TEST_ASSERT(inSuite, nullptr != p4);
 191     NL_TEST_ASSERT(inSuite, nullptr != p5);
 192     NL_TEST_ASSERT(inSuite, nullptr != p6);
 193
 194     allocator.HeapFree(p3);
 195     allocator.HeapFree(p4);
 196     // 10 blocks available (9 from p3 without HDR and 2 from p4 + HDR)
 197     p3 = allocator.HeapAlloc(10 * kBlockHeaderSize);
 198     NL_TEST_ASSERT(inSuite, nullptr != p3);
 199     NL_TEST_ASSERT(inSuite, nullptr == allocator.HeapAlloc(1)); // full
 200
 201     allocator.HeapFree(p6);
 202     allocator.HeapFree(p5);
 203     allocator.HeapFree(p3);
 204     allocator.HeapFree(p2);
 205     allocator.HeapFree(p1);
 206
 207     p1 = allocator.HeapAlloc(30 * kBlockHeaderSize);
 208     NL_TEST_ASSERT(inSuite, nullptr != p1);
 209     allocator.HeapFree(p1);
 210 }
 211
 212 void ForwardFreeAndRealloc(nlTestSuite * inSuite, void * inContext)
 213 {
 214     constexpr int kNumBlocks = 16;
 215     PrivateHeapAllocator<(2 * kNumBlocks + 1) * kBlockHeaderSize> allocator;
 216     void * ptrs[kNumBlocks];
 217
 218     for (int i = 0; i < kNumBlocks; ++i)
 219     {
 220         ptrs[i] = allocator.HeapAlloc(kBlockHeaderSize);
 221         NL_TEST_ASSERT(inSuite, nullptr != ptrs[i]);
 222         memset(ptrs[i], 0xab, kBlockHeaderSize);
 223     }
 224
 225     // heap looks like:
 226     ///  |HDR| 16 |HDR| 16 |HDR| ..... |HDR| 16 |HDR|
 227
 228     // free each block from the start and re-allocate into a bigger block
 229     for (size_t i = 1; i < kNumBlocks; ++i)
 230     {
 231         allocator.HeapFree(ptrs[0]);
 232         allocator.HeapFree(ptrs[i]);
 233
 234         ptrs[0] = allocator.HeapAlloc((1 + 2 * i) * kBlockHeaderSize);
 235         NL_TEST_ASSERT(inSuite, nullptr != ptrs[0]);
 236     }
 237     allocator.HeapFree(ptrs[0]);
 238 }
 239
 240 void BackwardFreeAndRealloc(nlTestSuite * inSuite, void * inContext)
 241 {
 242     constexpr int kNumBlocks = 16;
 243     PrivateHeapAllocator<(2 * kNumBlocks + 1) * kBlockHeaderSize> allocator;
 244     void * ptrs[kNumBlocks];
 245
 246     for (int i = 0; i < kNumBlocks; ++i)
 247     {
 248         ptrs[i] = allocator.HeapAlloc(kBlockHeaderSize);
 249         NL_TEST_ASSERT(inSuite, nullptr != ptrs[i]);
 250         memset(ptrs[i], 0xab, kBlockHeaderSize);
 251     }
 252
 253     // heap looks like:
 254     ///  |HDR| 16 |HDR| 16 |HDR| ..... |HDR| 16 |HDR|
 255
 256     // free each block from the send and re-allocate into a bigger block
 257     for (size_t i = 1; i < kNumBlocks; ++i)
 258     {
 259         allocator.HeapFree(ptrs[kNumBlocks - 1]);
 260         allocator.HeapFree(ptrs[kNumBlocks - i - 1]);
 261
 262         ptrs[kNumBlocks - 1] = allocator.HeapAlloc((1 + 2 * i) * kBlockHeaderSize);
 263         NL_TEST_ASSERT(inSuite, nullptr != ptrs[kNumBlocks - 1]);
 264     }
 265     allocator.HeapFree(ptrs[kNumBlocks - 1]);
 266 }
 267
 268 // Fills the data with a known pattern
 269 void FillKnownPattern(void * buffer, size_t size, uint8_t start)
 270 {
 271     uint8_t * p = static_cast<uint8_t *>(buffer);
 272     size_t cnt  = start;
 273     while (cnt++ < size)
 274     {
 275         uint8_t value = static_cast<uint8_t>(cnt * 31 + 7);
 276         *p            = value;
 277     }
 278 }
 279
 280 // checks if the specified buffer has the given pattern in it
 281 bool IsKnownPattern(void * buffer, size_t size, uint8_t start)
 282 {
 283     uint8_t * p = static_cast<uint8_t *>(buffer);
 284     size_t cnt  = start;
 285     while (cnt++ < size)
 286     {
 287         uint8_t value = static_cast<uint8_t>(cnt * 31 + 7);
 288         if (*p != value)
 289         {
 290             return false;
 291         }
 292     }
 293     return true;
 294 }
 295
 296 void Realloc(nlTestSuite * inSuite, void * inContext)
 297 {
 298     PrivateHeapAllocator<6 * 16> allocator;
 299
 300     void * p1 = allocator.HeapRealloc(nullptr, 16); // malloc basically
 301     NL_TEST_ASSERT(inSuite, p1 != nullptr);
 302
 303     FillKnownPattern(p1, 16, 11);
 304
 305     void * p2 = allocator.HeapRealloc(p1, 8); // resize, should fit
 306     NL_TEST_ASSERT(inSuite, p1 == p2);
 307     NL_TEST_ASSERT(inSuite, IsKnownPattern(p1, 8, 11));
 308
 309     p2 = allocator.HeapRealloc(p1, 16); // resize, should fit
 310     NL_TEST_ASSERT(inSuite, p1 == p2);
 311     NL_TEST_ASSERT(inSuite, IsKnownPattern(p2, 8, 11)); // only 8 bytes are guaranteed
 312
 313     FillKnownPattern(p1, 16, 33);
 314     p2 = allocator.HeapRealloc(p1, 32); // resize, does not fit. This frees p1
 315     NL_TEST_ASSERT(inSuite, p2 != nullptr);
 316     NL_TEST_ASSERT(inSuite, p2 != p1); // new reallocation occured
 317     NL_TEST_ASSERT(inSuite, IsKnownPattern(p2, 16, 33));
 318
 319     void * p3 = allocator.HeapAlloc(48); // insufficient heap for this
 320     NL_TEST_ASSERT(inSuite, p3 == nullptr);
 321
 322     p1 = allocator.HeapRealloc(p2, 16); // reallocation does not change block size
 323     NL_TEST_ASSERT(inSuite, p1 == p2);
 324
 325     p3 = allocator.HeapAlloc(48); // still insufficient heap for this
 326     NL_TEST_ASSERT(inSuite, p3 == nullptr);
 327
 328     p2 = allocator.HeapRealloc(p1, 48); // insufficient heap, p1 is NOT freed
 329     NL_TEST_ASSERT(inSuite, p2 == nullptr);
 330
 331     p2 = allocator.HeapRealloc(p1, 48); // Repeat the test to ensure p1 is not freed
 332     NL_TEST_ASSERT(inSuite, p2 == nullptr);
 333
 334     allocator.HeapFree(p1);
 335
 336     p3 = allocator.HeapAlloc(48); // above free should have made sufficient space
 337     NL_TEST_ASSERT(inSuite, p3 != nullptr);
 338     allocator.HeapFree(p3);
 339 }
 340
 341 const nlTest sTests[] = {
 342     NL_TEST_DEF("SingleHeapAllocAndFree", SingleHeapAllocAndFree),     //
 343     NL_TEST_DEF("SplitHeapAllocAndFree", SplitHeapAllocAndFree),       //
 344     NL_TEST_DEF("FreeMergeNext", FreeMergeNext),                       //
 345     NL_TEST_DEF("FreeMergePrevious", FreeMergePrevious),               //
 346     NL_TEST_DEF("FreeMergePreviousAndNext", FreeMergePreviousAndNext), //
 347     NL_TEST_DEF("MultipleMerge", MultipleMerge),                       //
 348     NL_TEST_DEF("ForwardFreeAndRealloc", ForwardFreeAndRealloc),       //
 349     NL_TEST_DEF("BackwardFreeAndRealloc", BackwardFreeAndRealloc),     //
 350     NL_TEST_DEF("Realloc", Realloc),                                   //
 351     NL_TEST_SENTINEL()                                                 //
 352 };
 353
 354 } // namespace
 355
 356 int TestPrivateHeap(void)
 357 {
 358     nlTestSuite theSuite = { "PrivateHeap", sTests, nullptr, nullptr };
 359     nlTestRunner(&theSuite, nullptr);
 360     return nlTestRunnerStats(&theSuite);
 361 }
 362
 363 CHIP_REGISTER_TEST_SUITE(TestPrivateHeap)