libc/test/src/__support/freestore_test.cpp

   1 //===-- Unittests for a freestore -------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include <stddef.h>
  10
  11 #include "src/__support/freestore.h"
  12 #include "test/UnitTest/Test.h"
  13
  14 using LIBC_NAMESPACE::Block;
  15 using LIBC_NAMESPACE::FreeList;
  16 using LIBC_NAMESPACE::FreeStore;
  17 using LIBC_NAMESPACE::FreeTrie;
  18 using LIBC_NAMESPACE::cpp::byte;
  19 using LIBC_NAMESPACE::cpp::optional;
  20
  21 // Inserting or removing blocks too small to be tracked does nothing.
  22 TEST(LlvmLibcFreeStore, TooSmall) {
  23   byte mem[1024];
  24   optional<Block<> *> maybeBlock = Block<>::init(mem);
  25   ASSERT_TRUE(maybeBlock.has_value());
  26   Block<> *too_small = *maybeBlock;
  27   maybeBlock = too_small->split(sizeof(Block<>::offset_type));
  28   ASSERT_TRUE(maybeBlock.has_value());
  29   Block<> *remainder = *maybeBlock;
  30
  31   FreeStore store;
  32   store.set_range({0, 4096});
  33   store.insert(too_small);
  34   store.insert(remainder);
  35
  36   EXPECT_EQ(store.remove_best_fit(too_small->inner_size()), remainder);
  37   store.remove(too_small);
  38 }
  39
  40 TEST(LlvmLibcFreeStore, RemoveBestFit) {
  41   byte mem[1024];
  42   optional<Block<> *> maybeBlock = Block<>::init(mem);
  43   ASSERT_TRUE(maybeBlock.has_value());
  44
  45   Block<> *smallest = *maybeBlock;
  46   maybeBlock = smallest->split(sizeof(FreeList) + sizeof(Block<>::offset_type));
  47   ASSERT_TRUE(maybeBlock.has_value());
  48   Block<> *largest_small = *maybeBlock;
  49   maybeBlock =
  50       largest_small->split(sizeof(FreeTrie::Node) +
  51                            sizeof(Block<>::offset_type) - alignof(max_align_t));
  52   ASSERT_TRUE(maybeBlock.has_value());
  53   ASSERT_GT(largest_small->inner_size(), smallest->inner_size());
  54
  55   Block<> *remainder = *maybeBlock;
  56
  57   FreeStore store;
  58   store.set_range({0, 4096});
  59   store.insert(smallest);
  60   store.insert(largest_small);
  61   store.insert(remainder);
  62
  63   // Find exact match for smallest.
  64   ASSERT_EQ(store.remove_best_fit(smallest->inner_size()), smallest);
  65   store.insert(smallest);
  66
  67   // Find exact match for largest.
  68   ASSERT_EQ(store.remove_best_fit(largest_small->inner_size()), largest_small);
  69   store.insert(largest_small);
  70
  71   // Search smallest for best fit.
  72   ASSERT_EQ(store.remove_best_fit(smallest->inner_size() + 1), largest_small);
  73   store.insert(largest_small);
  74
  75   // Continue search for best fit to large blocks.
  76   EXPECT_EQ(store.remove_best_fit(largest_small->inner_size() + 1), remainder);
  77 }
  78
  79 TEST(LlvmLibcFreeStore, Remove) {
  80   byte mem[1024];
  81   optional<Block<> *> maybeBlock = Block<>::init(mem);
  82   ASSERT_TRUE(maybeBlock.has_value());
  83
  84   Block<> *small = *maybeBlock;
  85   maybeBlock = small->split(sizeof(FreeList) + sizeof(Block<>::offset_type));
  86   ASSERT_TRUE(maybeBlock.has_value());
  87
  88   Block<> *remainder = *maybeBlock;
  89
  90   FreeStore store;
  91   store.set_range({0, 4096});
  92   store.insert(small);
  93   store.insert(remainder);
  94
  95   store.remove(remainder);
  96   ASSERT_EQ(store.remove_best_fit(remainder->inner_size()),
  97             static_cast<Block<> *>(nullptr));
  98   store.remove(small);
  99   ASSERT_EQ(store.remove_best_fit(small->inner_size()),
 100             static_cast<Block<> *>(nullptr));
 101 }