diff options
| -rw-r--r-- | include/klee/KDAlloc/allocator.h | 2 | ||||
| -rw-r--r-- | include/klee/KDAlloc/suballocators/loh.h | 58 | ||||
| -rw-r--r-- | include/klee/KDAlloc/suballocators/sized_regions.h | 159 |
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 = ¤tNode->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 = ¤tNode->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: |