Further improve KDAlloc memory usage with infinite quarantine

2 files changed, 372 insertions, 146 deletions

diff --git a/include/klee/KDAlloc/allocator.h b/include/klee/KDAlloc/allocator.h
index 4ed76705..a0c2f162 100644
--- a/include/klee/KDAlloc/allocator.h
+++ b/include/klee/KDAlloc/allocator.h
@@ -79,7 +79,7 @@ public:
 
   private:
     Mapping mapping;
-    std::array<suballocators::SlotAllocator::Control, meta.size()> sizedBins;
+    std::array<suballocators::SlotAllocatorControl, meta.size()> sizedBins;
     suballocators::LargeObjectAllocator::Control largeObjectBin;
 
   public:
@@ -99,21 +99,161 @@ public:
 private:
   klee::ref<Control> control;
 
-  std::array<suballocators::SlotAllocator, Control::meta.size()> sizedBins;
+  std::array<std::aligned_union_t<0, suballocators::SlotAllocator<false>,
+                                  suballocators::SlotAllocator<true>>,
+             Control::meta.size()>
+      sizedBins;
   suballocators::LargeObjectAllocator largeObjectBin;
 
+  void initializeSizedBins() {
+    if (control) {
+      for (std::size_t i = 0; i < sizedBins.size(); ++i) {
+        if (control->sizedBins[i].isQuarantineUnlimited()) {
+          new (&sizedBins[i]) suballocators::SlotAllocator<true>{};
+        } else {
+          new (&sizedBins[i]) suballocators::SlotAllocator<false>{};
+        }
+      }
+    }
+  }
+
+  void destroySizedBins() {
+    if (control) {
+      for (std::size_t i = 0; i < sizedBins.size(); ++i) {
+        if (control->sizedBins[i].isQuarantineUnlimited()) {
+          reinterpret_cast<suballocators::SlotAllocator<true> &>(sizedBins[i])
+              .~SlotAllocator<true>();
+        } else {
+          reinterpret_cast<suballocators::SlotAllocator<false> &>(sizedBins[i])
+              .~SlotAllocator<false>();
+        }
+      }
+    }
+  }
+
 public:
   std::ostream &logTag(std::ostream &out) const noexcept {
     return out << "[alloc] ";
   }
 
   Allocator() = default;
-  Allocator(Allocator const &rhs) = default;
-  Allocator &operator=(Allocator const &rhs) = default;
-  Allocator(Allocator &&) = default;
-  Allocator &operator=(Allocator &&) = default;
 
-  Allocator(klee::ref<Control> control) : control(std::move(control)) {}
+  Allocator(Allocator const &rhs)
+      : control(rhs.control), largeObjectBin(rhs.largeObjectBin) {
+    if (control) {
+      for (std::size_t i = 0; i < sizedBins.size(); ++i) {
+        if (control->sizedBins[i].isQuarantineUnlimited()) {
+          new (&sizedBins[i]) suballocators::SlotAllocator<true>{
+              reinterpret_cast<suballocators::SlotAllocator<true> const &>(
+                  rhs.sizedBins[i])};
+        } else {
+          new (&sizedBins[i]) suballocators::SlotAllocator<false>{
+              reinterpret_cast<suballocators::SlotAllocator<false> const &>(
+                  rhs.sizedBins[i])};
+        }
+      }
+    }
+  }
+
+  Allocator &operator=(Allocator const &rhs) {
+    if (this != &rhs) {
+      // `control` may differ in whether it is initialized and in the properties
+      // of any one bin. However, in the expected usage, allocators that are
+      // assigned always either share the same `control' or are uninitialized
+      // (i.e. have a `nullptr` control).
+      if (control.get() != rhs.control.get()) {
+        destroySizedBins();
+        control = rhs.control;
+        initializeSizedBins();
+      } else {
+        control = rhs.control;
+      }
+
+      if (control) {
+        for (std::size_t i = 0; i < sizedBins.size(); ++i) {
+          if (control->sizedBins[i].isQuarantineUnlimited()) {
+            reinterpret_cast<suballocators::SlotAllocator<true> &>(
+                sizedBins[i]) =
+                reinterpret_cast<suballocators::SlotAllocator<true> const &>(
+                    rhs.sizedBins[i]);
+          } else {
+            reinterpret_cast<suballocators::SlotAllocator<false> &>(
+                sizedBins[i]) =
+                reinterpret_cast<suballocators::SlotAllocator<false> const &>(
+                    rhs.sizedBins[i]);
+          }
+        }
+      }
+      largeObjectBin = rhs.largeObjectBin;
+    }
+    return *this;
+  }
+
+  Allocator(Allocator &&rhs)
+      : control(std::move(rhs.control)),
+        largeObjectBin(std::move(rhs.largeObjectBin)) {
+    if (control) {
+      for (std::size_t i = 0; i < sizedBins.size(); ++i) {
+        if (control->sizedBins[i].isQuarantineUnlimited()) {
+          new (&sizedBins[i]) suballocators::SlotAllocator<true>{
+              std::move(reinterpret_cast<suballocators::SlotAllocator<true> &>(
+                  rhs.sizedBins[i]))};
+          reinterpret_cast<suballocators::SlotAllocator<true> &>(
+              rhs.sizedBins[i])
+              .~SlotAllocator<true>();
+        } else {
+          new (&sizedBins[i]) suballocators::SlotAllocator<false>{
+              std::move(reinterpret_cast<suballocators::SlotAllocator<false> &>(
+                  rhs.sizedBins[i]))};
+          reinterpret_cast<suballocators::SlotAllocator<false> &>(
+              rhs.sizedBins[i])
+              .~SlotAllocator<false>();
+        }
+      }
+    }
+  }
+
+  Allocator &operator=(Allocator &&rhs) {
+    if (this != &rhs) {
+      // `control` may differ in whether it is initialized and in the properties
+      // of any one bin. However, in the expected usage, allocators that are
+      // assigned always either share the same `control' or are uninitialized
+      // (i.e. have a `nullptr` control).
+      if (control.get() != rhs.control.get()) {
+        destroySizedBins();
+        control = std::move(rhs.control);
+        initializeSizedBins();
+      } else {
+        control = std::move(rhs.control);
+      }
+
+      if (control) {
+        for (std::size_t i = 0; i < sizedBins.size(); ++i) {
+          if (control->sizedBins[i].isQuarantineUnlimited()) {
+            reinterpret_cast<suballocators::SlotAllocator<true> &>(
+                sizedBins[i]) =
+                std::move(
+                    reinterpret_cast<suballocators::SlotAllocator<true> &>(
+                        rhs.sizedBins[i]));
+          } else {
+            reinterpret_cast<suballocators::SlotAllocator<false> &>(
+                sizedBins[i]) =
+                std::move(
+                    reinterpret_cast<suballocators::SlotAllocator<false> &>(
+                        rhs.sizedBins[i]));
+          }
+        }
+      }
+      largeObjectBin = std::move(rhs.largeObjectBin);
+    }
+    return *this;
+  }
+
+  Allocator(klee::ref<Control> control) : control(std::move(control)) {
+    initializeSizedBins();
+  }
+
+  ~Allocator() { destroySizedBins(); }
 
   explicit operator bool() const noexcept { return !control.isNull(); }
 
@@ -135,7 +275,15 @@ public:
 
     void *result = nullptr;
     if (bin < static_cast<int>(sizedBins.size())) {
-      result = sizedBins[bin].allocate(control->sizedBins[bin]);
+      if (control->sizedBins[bin].isQuarantineUnlimited()) {
+        result = reinterpret_cast<suballocators::SlotAllocator<true> &>(
+                     sizedBins[bin])
+                     .allocate(control->sizedBins[bin]);
+      } else {
+        result = reinterpret_cast<suballocators::SlotAllocator<false> &>(
+                     sizedBins[bin])
+                     .allocate(control->sizedBins[bin]);
+      }
     } else {
       result = largeObjectBin.allocate(control->largeObjectBin, size);
     }
@@ -151,7 +299,15 @@ public:
     traceLine("Freeing ", ptr, " in bin ", bin);
 
     if (bin < static_cast<int>(sizedBins.size())) {
-      return sizedBins[bin].deallocate(control->sizedBins[bin], ptr);
+      if (control->sizedBins[bin].isQuarantineUnlimited()) {
+        return reinterpret_cast<suballocators::SlotAllocator<true> &>(
+                   sizedBins[bin])
+            .deallocate(control->sizedBins[bin], ptr);
+      } else {
+        return reinterpret_cast<suballocators::SlotAllocator<false> &>(
+                   sizedBins[bin])
+            .deallocate(control->sizedBins[bin], ptr);
+      }
     } else {
       return largeObjectBin.deallocate(control->largeObjectBin, ptr);
     }
@@ -165,7 +321,15 @@ public:
     traceLine("Freeing ", ptr, " of size ", size, " in bin ", bin);
 
     if (bin < static_cast<int>(sizedBins.size())) {
-      return sizedBins[bin].deallocate(control->sizedBins[bin], ptr);
+      if (control->sizedBins[bin].isQuarantineUnlimited()) {
+        return reinterpret_cast<suballocators::SlotAllocator<true> &>(
+                   sizedBins[bin])
+            .deallocate(control->sizedBins[bin], ptr);
+      } else {
+        return reinterpret_cast<suballocators::SlotAllocator<false> &>(
+                   sizedBins[bin])
+            .deallocate(control->sizedBins[bin], ptr);
+      }
     } else {
       return largeObjectBin.deallocate(control->largeObjectBin, ptr);
     }
@@ -199,7 +363,16 @@ public:
           ptr < control->sizedBins[i].mapping_end()) {
         if (reinterpret_cast<char const *>(ptr) + size <=
             control->sizedBins[i].mapping_end()) {
-          return sizedBins[i].getLocationInfo(control->sizedBins[i], ptr, size);
+          if (control->sizedBins[i].isQuarantineUnlimited()) {
+            return reinterpret_cast<suballocators::SlotAllocator<true> const &>(
+                       sizedBins[i])
+                .getLocationInfo(control->sizedBins[i], ptr, size);
+          } else {
+            return reinterpret_cast<
+                       suballocators::SlotAllocator<false> const &>(
+                       sizedBins[i])
+                .getLocationInfo(control->sizedBins[i], ptr, size);
+          }
         } else {
           return LocationInfo::LI_SpansSuballocators;
         }
diff --git a/include/klee/KDAlloc/suballocators/slot_allocator.h b/include/klee/KDAlloc/suballocators/slot_allocator.h
index be8393d7..1d0d42a8 100644
--- a/include/klee/KDAlloc/suballocators/slot_allocator.h
+++ b/include/klee/KDAlloc/suballocators/slot_allocator.h
@@ -24,144 +24,150 @@
 #include <type_traits>
 
 namespace klee::kdalloc::suballocators {
-class SlotAllocator final : public TaggedLogger<SlotAllocator> {
-  static_assert(static_cast<std::size_t>(-1) == ~static_cast<std::size_t>(0),
-                "-1 must be ~0 for size_t");
-  struct Data final {
-    /// The reference count.
-    std::size_t referenceCount; // initial value is 1 as soon as this member
-                                // is actually allocated
-
-    /// The number of allocated words. Always non-negative.
-    std::ptrdiff_t capacity; // initial value is 0 (changes as soon as this
-                             // member is actually allocated)
-
-    /// Always less than or equal to the first word that contains a one bit.
-    /// Less than or equal to _capacity. Always non-negative.
-    std::ptrdiff_t firstFreeFinger; // initial value is 0
+namespace slotallocator {
+template<bool UnlimitedQuarantine>
+class SlotAllocator;
+
+struct Data final {
+  /// The reference count.
+  std::size_t referenceCount; // initial value is 1 as soon as this member
+                              // is actually allocated
+
+  /// The number of allocated words. Always non-negative.
+  std::ptrdiff_t capacity; // initial value is 0 (changes as soon as this
+                           // member is actually allocated)
+
+  /// Always less than or equal to the first word that contains a one bit.
+  /// Less than or equal to _capacity. Always non-negative.
+  std::ptrdiff_t firstFreeFinger; // initial value is 0
+
+  /// Always greater than or equal to the last word that contains a zero bit.
+  /// Less than _capacity. May be negative (exactly -1).
+  std::ptrdiff_t lastUsedFinger; // initial value is -1
+
+  /// position in the quarantine, followed by the quarantine ring buffer,
+  /// followed by the bitmap
+  std::size_t quarantineAndBitmap[];
+};
 
-    /// Always greater than or equal to the last word that contains a zero bit.
-    /// Less than _capacity. May be negative (exactly -1).
-    std::ptrdiff_t lastUsedFinger; // initial value is -1
+class Control final : public TaggedLogger<Control> {
+  template<bool UnlimitedQuarantine>
+  friend class SlotAllocator;
 
-    /// position in the quarantine, followed by the quarantine ring buffer,
-    /// followed by the bitmap
-    std::size_t quarantineAndBitmap[];
-  };
+  /// pointer to the start of the range managed by this allocator
+  char *baseAddress = nullptr;
 
-  static_assert(std::is_pod<Data>::value, "Data must be POD");
+  /// size in bytes of the range managed by this allocator
+  std::size_t size = 0;
 
-public:
-  class Control final : public TaggedLogger<Control> {
-    friend class SlotAllocator;
+  /// size in bytes of the slots that are managed in this slot allocator
+  std::size_t slotSize = 0;
 
-    /// pointer to the start of the range managed by this allocator
-    char *baseAddress = nullptr;
+  /// number of bytes before the start of the bitmap (includes ordinary
+  /// members and quarantine)
+  std::size_t prefixSize = -1;
 
-    /// size in bytes of the range managed by this allocator
-    std::size_t size = 0;
+  /// quarantine size *including* the position (=> is never 1)
+  std::uint32_t quarantineSize = 0;
 
-    /// size in bytes of the slots that are managed in this slot allocator
-    std::size_t slotSize = 0;
+  /// true iff the quarantine is unlimited (=> quarantineSize == 0)
+  bool unlimitedQuarantine = false;
 
-    /// number of bytes before the start of the bitmap (includes ordinary
-    /// members and quarantine)
-    std::size_t prefixSize = -1;
+  [[nodiscard]] inline std::size_t
+  convertIndexToPosition(std::size_t index) const noexcept {
+    index += 1;
+    int const layer =
+        std::numeric_limits<std::size_t>::digits - countLeadingZeroes(index);
+    auto const layerSlots = static_cast<std::size_t>(1) << (layer - 1);
+    auto const currentSlotSize = (size >> layer);
+    assert(currentSlotSize > slotSize && "Zero (or below) red zone size!");
 
-    /// quarantine size *including* the position (=> is never 1)
-    std::uint32_t quarantineSize = 0;
+    auto const highBit = static_cast<std::size_t>(1) << (layer - 1);
+    assert((index & highBit) != 0 && "Failed to compute high bit");
+    assert((index ^ highBit) < highBit && "Failed to compute high bit");
 
-    /// true iff the quarantine is unlimited (=> _qurantine_size == 0)
-    bool unlimitedQuarantine = false;
+    auto layerIndex = index ^ highBit;
+    if (layerIndex % 2 == 0) {
+      layerIndex /= 2; // drop trailing 0
+    } else {
+      layerIndex /= 2; // drop trailing 1
+      layerIndex = layerSlots - 1 - layerIndex;
+    }
+    assert(layerIndex < highBit && "Invalid tempering");
+    auto const pos = layerIndex * 2 + 1;
+    return currentSlotSize * pos;
+  }
 
-    [[nodiscard]] inline std::size_t
-    convertIndexToPosition(std::size_t index) const noexcept {
-      index += 1;
-      int const layer =
-          std::numeric_limits<std::size_t>::digits - countLeadingZeroes(index);
-      auto const layerSlots = static_cast<std::size_t>(1) << (layer - 1);
-      auto const currentSlotSize = (size >> layer);
-      assert(currentSlotSize > slotSize && "Zero (or below) red zone size!");
+  [[nodiscard]] inline std::size_t
+  convertPositionToIndex(std::size_t const Position) const noexcept {
+    int const trailingZeroes = countTrailingZeroes(Position);
+    auto const layer = countTrailingZeroes(size) - trailingZeroes;
+    auto const layerSlots = static_cast<std::size_t>(1) << (layer - 1);
 
-      auto const highBit = static_cast<std::size_t>(1) << (layer - 1);
-      assert((index & highBit) != 0 && "Failed to compute high bit");
-      assert((index ^ highBit) < highBit && "Failed to compute high bit");
+    auto const highBit = static_cast<std::size_t>(1) << (layer - 1);
+    auto layerIndex = Position >> (trailingZeroes + 1);
+    assert(layerIndex < highBit && "Tempered value was not restored correctly");
 
-      auto layerIndex = index ^ highBit;
-      if (layerIndex % 2 == 0) {
-        layerIndex /= 2; // drop trailing 0
-      } else {
-        layerIndex /= 2; // drop trailing 1
-        layerIndex = layerSlots - 1 - layerIndex;
-      }
-      assert(layerIndex < highBit && "Invalid tempering");
-      auto const pos = layerIndex * 2 + 1;
-      return currentSlotSize * pos;
+    if (layerIndex < (layerSlots + 1) / 2) {
+      layerIndex *= 2; // add trailing 0
+    } else {
+      layerIndex = layerSlots - 1 - layerIndex;
+      layerIndex = layerIndex * 2 + 1; // add trailing 1
     }
+    assert(layerIndex < highBit && "Invalid reverse tempering");
 
-    [[nodiscard]] inline std::size_t
-    convertPositionToIndex(std::size_t const Position) const noexcept {
-      int const trailingZeroes = countTrailingZeroes(Position);
-      auto const layer = countTrailingZeroes(size) - trailingZeroes;
-      auto const layerSlots = static_cast<std::size_t>(1) << (layer - 1);
+    auto const index = highBit ^ layerIndex;
+    return index - 1;
+  }
 
-      auto const highBit = static_cast<std::size_t>(1) << (layer - 1);
-      auto layerIndex = Position >> (trailingZeroes + 1);
-      assert(layerIndex < highBit &&
-             "Tempered value was not restored correctly");
+public:
+  Control() = default;
+  Control(Control const &) = delete;
+  Control &operator=(Control const &) = delete;
+  Control(Control &&) = delete;
+  Control &operator=(Control &&) = delete;
+
+  void initialize(void *const baseAddress, std::size_t const size,
+                  std::size_t const slotSize, bool const unlimitedQuarantine,
+                  std::uint32_t const quarantineSize) noexcept {
+    assert(size > 0 && (size & (size - 1)) == 0 &&
+           "Sizes of sized bins must be powers of two");
+
+    this->baseAddress = static_cast<char *>(baseAddress);
+    this->size = size;
+    this->slotSize = slotSize;
+    if (unlimitedQuarantine) {
+      this->quarantineSize = 0;
+      this->unlimitedQuarantine = true;
+    } else {
+      this->quarantineSize = quarantineSize == 0 ? 0 : quarantineSize + 1;
+      this->unlimitedQuarantine = false;
+    }
+    this->prefixSize =
+        sizeof(Data) + this->quarantineSize * sizeof(std::size_t);
 
-      if (layerIndex < (layerSlots + 1) / 2) {
-        layerIndex *= 2; // add trailing 0
-      } else {
-        layerIndex = layerSlots - 1 - layerIndex;
-        layerIndex = layerIndex * 2 + 1; // add trailing 1
-      }
-      assert(layerIndex < highBit && "Invalid reverse tempering");
+    traceLine("Initialization complete");
+  }
 
-      auto const index = highBit ^ layerIndex;
-      return index - 1;
-    }
+  inline std::ostream &logTag(std::ostream &out) const noexcept {
+    return out << "[slot " << slotSize << " Control] ";
+  }
 
-  public:
-    Control() = default;
-    Control(Control const &) = delete;
-    Control &operator=(Control const &) = delete;
-    Control(Control &&) = delete;
-    Control &operator=(Control &&) = delete;
-
-    void initialize(void *const baseAddress, std::size_t const size,
-                    std::size_t const slotSize, bool const unlimitedQuarantine,
-                    std::uint32_t const quarantineSize) noexcept {
-      assert(size > 0 && (size & (size - 1)) == 0 &&
-             "Sizes of sized bins must be powers of two");
-
-      this->baseAddress = static_cast<char *>(baseAddress);
-      this->size = size;
-      this->slotSize = slotSize;
-      if (unlimitedQuarantine) {
-        this->quarantineSize = 0;
-        this->unlimitedQuarantine = true;
-      } else {
-        this->quarantineSize = quarantineSize == 0 ? 0 : quarantineSize + 1;
-        this->unlimitedQuarantine = false;
-      }
-      this->prefixSize =
-          sizeof(Data) + this->quarantineSize * sizeof(std::size_t);
+  bool isQuarantineUnlimited() const noexcept { return unlimitedQuarantine; }
 
-      traceLine("Initialization complete");
-    }
+  constexpr void *mapping_begin() const noexcept { return baseAddress; }
+  constexpr void *mapping_end() const noexcept {
+    return static_cast<void *>(static_cast<char *>(baseAddress) + size);
+  }
+};
 
-    inline std::ostream &logTag(std::ostream &out) const noexcept {
-      return out << "[slot " << slotSize << " Control] ";
-    }
+template<>
+class SlotAllocator<false> final : public TaggedLogger<SlotAllocator<false>> {
+  static_assert(static_cast<std::size_t>(-1) == ~static_cast<std::size_t>(0),
+                "-1 must be ~0 for size_t");
 
-    constexpr void *mapping_begin() const noexcept { return baseAddress; }
-    constexpr void *mapping_end() const noexcept {
-      return static_cast<void *>(static_cast<char *>(baseAddress) + size);
-    }
-  };
+  static_assert(std::is_pod<Data>::value, "Data must be POD");
 
-private:
   Data *data = nullptr;
 
   inline void releaseData() noexcept {
@@ -209,9 +215,6 @@ private:
   std::size_t quarantine(Control const &control, std::size_t const index) {
     assert(!!data &&
            "Deallocations can only happen if allocations happened beforehand");
-    assert(
-        !control.unlimitedQuarantine &&
-        "Please check for unlimited quarantine before calling this function");
 
     if (control.quarantineSize == 0) {
       return index;
@@ -487,26 +490,22 @@ public:
     assert(!!data &&
            "Deallocations can only happen if allocations happened beforehand");
 
-    if (control.unlimitedQuarantine) {
-      traceLine("Quarantining ", ptr, " for ever");
-    } else {
-      auto pos = static_cast<std::size_t>(static_cast<char *>(ptr) -
-                                          control.baseAddress);
-      acquireData(control); // we will need quarantine and/or bitmap ownership
+    auto pos = static_cast<std::size_t>(static_cast<char *>(ptr) -
+                                        control.baseAddress);
+    acquireData(control); // we will need quarantine and/or bitmap ownership
 
-      traceLine("Quarantining ", ptr, " as ", pos, " for ",
-                control.quarantineSize, " deallocations");
-      pos = quarantine(control, pos);
+    traceLine("Quarantining ", ptr, " as ", pos, " for ",
+              control.quarantineSize, " deallocations");
+    pos = quarantine(control, pos);
 
-      if (pos == static_cast<std::size_t>(-1)) {
-        traceLine("Nothing to deallocate");
-      } else {
-        traceLine("Deallocating ", pos);
-        traceContents(control);
-        assert(pos < control.size);
+    if (pos == static_cast<std::size_t>(-1)) {
+      traceLine("Nothing to deallocate");
+    } else {
+      traceLine("Deallocating ", pos);
+      traceContents(control);
+      assert(pos < control.size);
 
-        setFree(control, control.convertPositionToIndex(pos));
-      }
+      setFree(control, control.convertPositionToIndex(pos));
     }
   }
 
@@ -533,6 +532,60 @@ public:
 #endif
   }
 };
+
+
+template<>
+class SlotAllocator<true> final : public TaggedLogger<SlotAllocator<true>> {
+  std::size_t next;
+
+public:
+  inline std::ostream &logTag(std::ostream &out) const noexcept {
+    return out << "[uslot] ";
+  }
+
+  LocationInfo getLocationInfo(Control const &control, void const *const ptr,
+                               std::size_t const size) const noexcept {
+    assert(control.mapping_begin() <= ptr &&
+           reinterpret_cast<char const *>(ptr) + size < control.mapping_end() &&
+           "This property should have been ensured by the caller");
+
+    auto const begin = static_cast<std::size_t>(static_cast<char const *>(ptr) -
+                                                control.baseAddress);
+    auto const end = static_cast<std::size_t>(static_cast<char const *>(ptr) +
+                                              size - control.baseAddress);
+    assert(control.slotSize > 0 && "Uninitialized Control structure");
+    auto const pos = begin - begin % control.slotSize;
+    if (pos != (end - 1) - (end - 1) % control.slotSize) {
+      return LocationInfo::LI_Unaligned;
+    }
+
+    auto const index = control.convertPositionToIndex(pos);
+    if (index >= next) {
+      return LocationInfo::LI_Unallocated;
+    } else {
+      return {LocationInfo::LI_AllocatedOrQuarantined,
+              control.baseAddress + pos};
+    }
+  }
+
+  [[nodiscard]] void *allocate(Control const &control) noexcept {
+    traceLine("Allocating ", control.slotSize, " bytes");
+
+    return control.baseAddress + control.convertIndexToPosition(next++);
+  }
+
+  void deallocate(Control const &control, void *const ptr) {
+    traceLine("Quarantining ", ptr, " for ever");
+  }
+
+  void traceContents(Control const &) const noexcept {
+    traceLine("next: ", next);
+  }
+};
+} // namespace slotallocator
+
+using slotallocator::SlotAllocator;
+using SlotAllocatorControl = slotallocator::Control;
 } // namespace klee::kdalloc::suballocators
 
 #endif