Improve LOH deallocation scheme

3 files changed, 60 insertions, 159 deletions

diff --git a/include/klee/KDAlloc/allocator.h b/include/klee/KDAlloc/allocator.h
index 45d90536..1e0d305a 100644
--- a/include/klee/KDAlloc/allocator.h
+++ b/include/klee/KDAlloc/allocator.h
@@ -153,7 +153,7 @@ public:
     if (bin < static_cast<int>(sizedBins.size())) {
       return sizedBins[bin].deallocate(control->sizedBins[bin], ptr);
     } else {
-      return largeObjectBin.deallocate(control->largeObjectBin, ptr, size);
+      return largeObjectBin.deallocate(control->largeObjectBin, ptr);
     }
   }
 
diff --git a/include/klee/KDAlloc/suballocators/loh.h b/include/klee/KDAlloc/suballocators/loh.h
index d52306fc..16baf911 100644
--- a/include/klee/KDAlloc/suballocators/loh.h
+++ b/include/klee/KDAlloc/suballocators/loh.h
@@ -43,17 +43,17 @@ class LargeObjectAllocator final : public TaggedLogger<LargeObjectAllocator> {
     /// over sizes
     SizedRegions regions;
 
-    static_assert(
-        sizeof(void *) >= sizeof(std::size_t),
-        "The quarantine elements are alternating `void*` and `std::size_t`");
-    static_assert(
-        alignof(void *) >= alignof(std::size_t),
-        "The quarantine elements are alternating `void*` and `std::size_t`");
+    static_assert(sizeof(void *) >= sizeof(std::size_t),
+                  "The quarantine structure contains a `std::size_t` followed "
+                  "by many `void*`s");
+    static_assert(alignof(void *) >= alignof(std::size_t),
+                  "The quarantine structure contains a `std::size_t` followed "
+                  "by many `void*`s");
     using QuarantineElement =
         std::aligned_storage_t<sizeof(void *), alignof(void *)>;
 
     /// The quarantine position followed by the quarantine ring buffer
-    /// Structure: [pos, ptr1, size1, ptr2, size2, ...]
+    /// Structure: [pos, ptr1, ptr2, ...]
     QuarantineElement quarantine[];
 
     Data() = default;
@@ -90,7 +90,7 @@ public:
         this->quarantineSize = 0;
         this->unlimitedQuarantine = true;
       } else {
-        this->quarantineSize = quarantineSize == 0 ? 0 : quarantineSize * 2 + 1;
+        this->quarantineSize = quarantineSize == 0 ? 0 : quarantineSize + 1;
         this->unlimitedQuarantine = false;
       }
 
@@ -140,32 +140,27 @@ private:
     assert(data->referenceCount == 1);
   }
 
-  std::pair<void *, std::size_t>
-  quarantine(Control const &control, void *const ptr, std::size_t const size) {
+  void *quarantine(Control const &control, void *const ptr) {
     assert(!!data &&
            "Deallocations can only happen if allocations happened beforehand");
     assert(!control.unlimitedQuarantine);
 
     if (control.quarantineSize == 0) {
-      return {ptr, size};
+      return ptr;
     }
 
     assert(data->referenceCount == 1 &&
            "Must hold CoW ownership to quarantine a new pointer+size pair");
 
     auto const pos = reinterpret_cast<std::size_t &>(data->quarantine[0]);
-    if (pos + 2 == control.quarantineSize) {
+    if (pos + 1 == control.quarantineSize) {
       reinterpret_cast<std::size_t &>(data->quarantine[0]) = 1;
     } else {
-      reinterpret_cast<std::size_t &>(data->quarantine[0]) = pos + 2;
+      reinterpret_cast<std::size_t &>(data->quarantine[0]) = pos + 1;
     }
 
-    auto quarantinedPtr = std::exchange(
-        reinterpret_cast<void *&>(data->quarantine[pos]), std::move(ptr));
-    auto quarantinedSize = std::exchange(
-        reinterpret_cast<std::size_t &>(data->quarantine[pos + 1]),
-        std::move(size));
-    return {quarantinedPtr, quarantinedSize};
+    return std::exchange(reinterpret_cast<void *&>(data->quarantine[pos]),
+                         std::move(ptr));
   }
 
 public:
@@ -293,39 +288,30 @@ public:
     return result;
   }
 
-  void deallocate(Control const &control, void *ptr, std::size_t size) {
+  void deallocate(Control const &control, void *ptr) {
     assert(!!data &&
            "Deallocations can only happen if allocations happened beforehand");
 
     if (control.unlimitedQuarantine) {
       traceLine("Quarantining ", ptr, " for ever");
     } else {
-      auto quantizedSize = roundUpToMultipleOf4096(size);
-      traceLine("Quarantining ", ptr, " with size ", size, " (", quantizedSize,
-                ") for ", (control.quarantineSize - 1) / 2, " deallocations");
-      assert(size > 0);
-      assert(quantizedSize % 4096 == 0);
+      traceLine("Quarantining ", ptr, " for ", control.quarantineSize - 1,
+                " deallocations");
 
       acquireData(control); // we will need quarantine and/or region ownership
-      std::tie(ptr, size) = quarantine(control, ptr, size);
+      ptr = quarantine(control, ptr);
       if (!ptr) {
         return;
       }
 
-      quantizedSize = roundUpToMultipleOf4096(size);
-      traceLine("Deallocating ", ptr, " with size ", size, " (", quantizedSize,
-                ")");
+      traceLine("Deallocating ", ptr);
 
       assert(data->referenceCount == 1);
-      assert(size > 0);
-      assert(quantizedSize % 4096 == 0);
-      size = quantizedSize;
       traceContents(control);
-      traceLine("Merging region at ",
-                static_cast<void *>(static_cast<char *>(ptr) + size),
-                " with the preceding region");
+      traceLine("Merging regions around ",
+                static_cast<void *>(static_cast<char *>(ptr)));
 
-      data->regions.mergeRegionWithPrevious(static_cast<char *>(ptr) + size);
+      data->regions.mergeAroundAddress(static_cast<char *>(ptr));
     }
   }
 
diff --git a/include/klee/KDAlloc/suballocators/sized_regions.h b/include/klee/KDAlloc/suballocators/sized_regions.h
index 7236a619..2fb12bf5 100644
--- a/include/klee/KDAlloc/suballocators/sized_regions.h
+++ b/include/klee/KDAlloc/suballocators/sized_regions.h
@@ -412,136 +412,51 @@ public:
     }
   }
 
-private:
-  static CoWPtr<Node> mergeRegionWithPreviousRec(CoWPtr<Node> &treap,
-                                                 char *const baseAddress) {
-    assert(treap && "cannot extract region that is not part of the treap");
-    if (baseAddress < treap->getBaseAddress()) {
-      auto &node = treap.acquire();
-      if (auto greater = mergeRegionWithPreviousRec(node.lhs, baseAddress)) {
-        if (node.getBaseAddress() < greater->getBaseAddress()) {
-          auto newSize = static_cast<std::size_t>(greater->getBaseAddress() -
-                                                  node.getBaseAddress() +
-                                                  greater->getSize());
-          assert(
-              newSize > node.getSize() &&
-              "Sizes only get greater by adding `greater - smaller` to them");
-          node.setSize(newSize);
-          return {};
+  /// This function merges the region after the given address, with the region
+  /// immediately preceding it. There must be a region before and a region after
+  /// `address`.
+  void mergeAroundAddress(char const *const address) noexcept {
+    assert(root && "An empty treap holds no regions to merge");
+
+    CoWPtr<Node> *currentNode = &root;
+    CoWPtr<Node> *closestPredecessor = nullptr;
+    CoWPtr<Node> *closestSuccessor = nullptr;
+    for (;;) {
+      if (address < (*currentNode)->getBaseAddress()) {
+        assert(!closestSuccessor ||
+               (*currentNode)->getBaseAddress() <
+                   (*closestSuccessor)->getBaseAddress());
+        closestSuccessor = currentNode;
+        if ((*currentNode)->lhs) {
+          currentNode = &currentNode->acquire().lhs;
         } else {
-          return greater;
+          break;
         }
       } else {
-        if (node.lhs->getSize() > node.getSize() ||
-            (node.lhs->getSize() == node.getSize() &&
-             node.lhs->hash() > node.hash())) {
-          auto temp = std::move(node.lhs);
-          auto &nodeTemp = temp.getOwned();
-          node.lhs = std::move(nodeTemp.rhs);
-          nodeTemp.rhs = std::move(treap);
-          treap = std::move(temp);
-        }
-        return {};
-      }
-    } else if (treap->getBaseAddress() < baseAddress) {
-      auto &node = treap.acquire();
-      if (auto greater = mergeRegionWithPreviousRec(node.rhs, baseAddress)) {
-        if (node.getBaseAddress() < greater->getBaseAddress()) {
-          auto newSize = static_cast<std::size_t>(greater->getBaseAddress() -
-                                                  node.getBaseAddress() +
-                                                  greater->getSize());
-          assert(
-              newSize > node.getSize() &&
-              "Sizes only get greater by adding `greater - smaller` to them");
-          node.setSize(newSize);
-          return {};
+        assert(!closestPredecessor ||
+               (*currentNode)->getBaseAddress() >
+                   (*closestPredecessor)->getBaseAddress());
+        closestPredecessor = currentNode;
+        if ((*currentNode)->rhs) {
+          currentNode = &currentNode->acquire().rhs;
         } else {
-          return greater;
-        }
-      } else {
-        if (node.rhs->getSize() > node.getSize() ||
-            (node.rhs->getSize() == node.getSize() &&
-             node.rhs->hash() > node.hash())) {
-          auto temp = std::move(node.rhs);
-          auto &nodeTemp = temp.getOwned();
-          node.rhs = std::move(nodeTemp.lhs);
-          nodeTemp.lhs = std::move(treap);
-          treap = std::move(temp);
+          break;
         }
-        return greater;
-      }
-    } else {
-      assert(treap->getBaseAddress() == baseAddress);
-      // target is now the greater (w.r.t. the tree key) of the two regions we
-      // are looking for
-      if (treap->lhs) {
-        CoWPtr<Node> lhs, rhs;
-        if (treap.isOwned()) {
-          auto &node = treap.acquire();
-          lhs = std::move(node.lhs);
-          rhs = std::move(node.rhs);
-        } else {
-          lhs = treap->lhs;
-          rhs = treap->rhs;
-        }
-        auto const greaterBaseAddress = treap->getBaseAddress();
-        auto const greaterSize = treap->getSize();
-
-        auto *target = &lhs;
-        while ((*target)->rhs) {
-          target = &target->acquire().rhs;
-        }
-        treap = std::move(*target);
-        auto &node = treap.acquire();
-        *target = std::move(node.lhs);
-
-        assert(greaterBaseAddress > node.getBaseAddress());
-        auto newSize = static_cast<std::size_t>(
-            greaterBaseAddress - node.getBaseAddress() + greaterSize);
-        assert(newSize > node.getSize() &&
-               "Sizes only get greater by adding `greater - smaller` to them");
-        node.setSize(newSize);
-
-        assert(!node.rhs && "We looked for a node that has no rhs");
-        assert((!rhs || node.getBaseAddress() < rhs->getBaseAddress()) &&
-               "`lesser` comes from the left subtree of `greater`, while "
-               "rhs is the right subtree of `greater`");
-        assert((!rhs || node.getSize() > rhs->getSize()) &&
-               "The old size of `greater` was >= that of its right subtree, "
-               "so the new size (of `lesser`) is strictly greater");
-        node.rhs = std::move(rhs);
-
-        assert(!node.lhs && "The lhs of this node has already been removed");
-        assert((!lhs || lhs->getBaseAddress() < node.getBaseAddress()) &&
-               "`lesser` is the greatest child of the `lhs` subtree");
-        assert((!lhs || node.getSize() > lhs->getSize()) &&
-               "The old size of `greater` was >= that of its left subtree, "
-               "so the new size (of `lesser`) is strictly greater");
-        node.lhs = std::move(lhs);
-        return {};
-      } else {
-        auto greater = std::move(treap);
-        if (greater->rhs) {
-          if (greater.isOwned()) {
-            treap = std::move(greater.acquire().rhs);
-          } else {
-            treap = greater->rhs;
-          }
-        }
-        return greater; // no move to enable copy elision
       }
     }
-  }
 
-public:
-  /// This function merges the region starting at the given address, with the
-  /// region immediately preceding it. Both regions must exist. The resulting
-  /// region has the same base address as the lesser region with its size large
-  /// enough to cover the space to the end of the greater region (filling any
-  /// holes in the process).
-  inline void mergeRegionWithPrevious(char *const baseAddress) {
-    assert(root && "An empty treap holds no regions to merge");
-    mergeRegionWithPreviousRec(root, baseAddress);
+    assert(closestPredecessor && closestSuccessor &&
+           "address must be in between two regions");
+
+    closestPredecessor->acquire().setSize(
+        (*closestSuccessor)->getBaseAddress() + (*closestSuccessor)->getSize() -
+        (*closestPredecessor)->getBaseAddress());
+    CoWPtr<Node> lhs = (*closestSuccessor)->lhs;
+    CoWPtr<Node> rhs = (*closestSuccessor)->rhs;
+    closestSuccessor->release();
+    if (lhs || rhs) {
+      mergeTreaps(closestSuccessor, lhs, rhs);
+    }
   }
 
 private: