diff options
| -rw-r--r-- | include/klee/KDAlloc/allocator.h | 195 | ||||
| -rw-r--r-- | include/klee/KDAlloc/suballocators/slot_allocator.h | 323 |
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 |