third_party/pigweed/repo/pw_allocator/freelist_test.cc

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14
  15 #include "pw_allocator/freelist.h"
  16
  17 #include <span>
  18
  19 #include "gtest/gtest.h"
  20 #include "pw_status/status.h"
  21
  22 using std::byte;
  23
  24 namespace pw::allocator {
  25
  26 static const size_t SIZE = 8;
  27 static const std::array<size_t, SIZE> example_sizes = {
  28     64, 128, 256, 512, 1024, 2048, 4096, 8192};
  29
  30 TEST(FreeList, EmptyListHasNoMembers) {
  31   FreeListBuffer<SIZE> list(example_sizes);
  32
  33   auto item = list.FindChunk(4);
  34   EXPECT_EQ(item.size(), static_cast<size_t>(0));
  35   item = list.FindChunk(128);
  36   EXPECT_EQ(item.size(), static_cast<size_t>(0));
  37 }
  38
  39 TEST(FreeList, CanRetrieveAddedMember) {
  40   FreeListBuffer<SIZE> list(example_sizes);
  41   constexpr size_t kN = 512;
  42
  43   byte data[kN] = {std::byte(0)};
  44
  45   auto status = list.AddChunk(std::span(data, kN));
  46   EXPECT_EQ(status, OkStatus());
  47
  48   auto item = list.FindChunk(kN);
  49   EXPECT_EQ(item.size(), kN);
  50   EXPECT_EQ(item.data(), data);
  51 }
  52
  53 TEST(FreeList, CanRetrieveAddedMemberForSmallerSize) {
  54   FreeListBuffer<SIZE> list(example_sizes);
  55   constexpr size_t kN = 512;
  56
  57   byte data[kN] = {std::byte(0)};
  58
  59   list.AddChunk(std::span(data, kN));
  60   auto item = list.FindChunk(kN / 2);
  61   EXPECT_EQ(item.size(), kN);
  62   EXPECT_EQ(item.data(), data);
  63 }
  64
  65 TEST(FreeList, CanRemoveItem) {
  66   FreeListBuffer<SIZE> list(example_sizes);
  67   constexpr size_t kN = 512;
  68
  69   byte data[kN] = {std::byte(0)};
  70
  71   list.AddChunk(std::span(data, kN));
  72   auto status = list.RemoveChunk(std::span(data, kN));
  73   EXPECT_EQ(status, OkStatus());
  74
  75   auto item = list.FindChunk(kN);
  76   EXPECT_EQ(item.size(), static_cast<size_t>(0));
  77 }
  78
  79 TEST(FreeList, FindReturnsSmallestChunk) {
  80   FreeListBuffer<SIZE> list(example_sizes);
  81   constexpr size_t kN1 = 512;
  82   constexpr size_t kN2 = 1024;
  83
  84   byte data1[kN1] = {std::byte(0)};
  85   byte data2[kN2] = {std::byte(0)};
  86
  87   list.AddChunk(std::span(data1, kN1));
  88   list.AddChunk(std::span(data2, kN2));
  89
  90   auto chunk = list.FindChunk(kN1 / 2);
  91   EXPECT_EQ(chunk.size(), kN1);
  92   EXPECT_EQ(chunk.data(), data1);
  93
  94   chunk = list.FindChunk(kN1);
  95   EXPECT_EQ(chunk.size(), kN1);
  96   EXPECT_EQ(chunk.data(), data1);
  97
  98   chunk = list.FindChunk(kN1 + 1);
  99   EXPECT_EQ(chunk.size(), kN2);
 100   EXPECT_EQ(chunk.data(), data2);
 101 }
 102
 103 TEST(FreeList, FindReturnsCorrectChunkInSameBucket) {
 104   // If we have two values in the same bucket, ensure that the allocation will
 105   // pick an appropriately sized one.
 106   FreeListBuffer<SIZE> list(example_sizes);
 107   constexpr size_t kN1 = 512;
 108   constexpr size_t kN2 = 257;
 109
 110   byte data1[kN1] = {std::byte(0)};
 111   byte data2[kN2] = {std::byte(0)};
 112
 113   // List should now be 257 -> 512 -> NULL
 114   list.AddChunk(std::span(data1, kN1));
 115   list.AddChunk(std::span(data2, kN2));
 116
 117   auto chunk = list.FindChunk(kN2 + 1);
 118   EXPECT_EQ(chunk.size(), kN1);
 119 }
 120
 121 TEST(FreeList, FindCanMoveUpThroughBuckets) {
 122   // Ensure that finding a chunk will move up through buckets if no appropriate
 123   // chunks were found in a given bucket
 124   FreeListBuffer<SIZE> list(example_sizes);
 125   constexpr size_t kN1 = 257;
 126   constexpr size_t kN2 = 513;
 127
 128   byte data1[kN1] = {std::byte(0)};
 129   byte data2[kN2] = {std::byte(0)};
 130
 131   // List should now be:
 132   // bkt[3] (257 bytes up to 512 bytes) -> 257 -> NULL
 133   // bkt[4] (513 bytes up to 1024 bytes) -> 513 -> NULL
 134   list.AddChunk(std::span(data1, kN1));
 135   list.AddChunk(std::span(data2, kN2));
 136
 137   // Request a 300 byte chunk. This should return the 513 byte one
 138   auto chunk = list.FindChunk(kN1 + 1);
 139   EXPECT_EQ(chunk.size(), kN2);
 140 }
 141
 142 TEST(FreeList, RemoveUnknownChunkReturnsNotFound) {
 143   FreeListBuffer<SIZE> list(example_sizes);
 144   constexpr size_t kN = 512;
 145
 146   byte data[kN] = {std::byte(0)};
 147   byte data2[kN] = {std::byte(0)};
 148
 149   list.AddChunk(std::span(data, kN));
 150   auto status = list.RemoveChunk(std::span(data2, kN));
 151   EXPECT_EQ(status, Status::NotFound());
 152 }
 153
 154 TEST(FreeList, CanStoreMultipleChunksPerBucket) {
 155   FreeListBuffer<SIZE> list(example_sizes);
 156   constexpr size_t kN = 512;
 157
 158   byte data1[kN] = {std::byte(0)};
 159   byte data2[kN] = {std::byte(0)};
 160
 161   list.AddChunk(std::span(data1, kN));
 162   list.AddChunk(std::span(data2, kN));
 163
 164   auto chunk1 = list.FindChunk(kN);
 165   list.RemoveChunk(chunk1);
 166   auto chunk2 = list.FindChunk(kN);
 167   list.RemoveChunk(chunk2);
 168
 169   // Ordering of the chunks doesn't matter
 170   EXPECT_TRUE(chunk1.data() != chunk2.data());
 171   EXPECT_TRUE(chunk1.data() == data1 || chunk1.data() == data2);
 172   EXPECT_TRUE(chunk2.data() == data1 || chunk2.data() == data2);
 173 }
 174
 175 }  // namespace pw::allocator