From 44f9772f87b45ca7bef7767e3962e6b61a2e5c4d Mon Sep 17 00:00:00 2001 From: Daniel Schemmel Date: Thu, 13 Oct 2022 14:24:07 +0100 Subject: Add the KDAlloc allocator using both of its suballocators --- include/klee/KDAlloc/allocator.h | 264 +++++++++++++++++++++++++++++++++++++++ include/klee/KDAlloc/kdalloc.h | 21 ++++ include/klee/KDAlloc/mapping.h | 158 +++++++++++++++++++++++ 3 files changed, 443 insertions(+) create mode 100644 include/klee/KDAlloc/allocator.h create mode 100644 include/klee/KDAlloc/kdalloc.h create mode 100644 include/klee/KDAlloc/mapping.h (limited to 'include') diff --git a/include/klee/KDAlloc/allocator.h b/include/klee/KDAlloc/allocator.h new file mode 100644 index 00000000..f59223ed --- /dev/null +++ b/include/klee/KDAlloc/allocator.h @@ -0,0 +1,264 @@ +//===-- allocator.h ---------------------------------------------*- C++ -*-===// +// +// The KLEE Symbolic Virtual Machine +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef KDALLOC_ALLOCATOR_H +#define KDALLOC_ALLOCATOR_H + +#include "define.h" +#include "location_info.h" +#include "mapping.h" +#include "suballocators/loh.h" +#include "suballocators/slot_allocator.h" +#include "tagged_logger.h" + +#include "klee/ADT/Bits.h" +#include "klee/ADT/Ref.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace klee::kdalloc { +/// Wraps a mapping that is shared with other allocators. +class Allocator final : public TaggedLogger { +public: + class Control final { + friend class Allocator; + friend class AllocatorFactory; + + static constexpr const std::uint32_t unlimitedQuarantine = + static_cast(-1); + + /// @todo This should really be a data member `static constexpr const + /// std::array meta = { ... }`. + static inline const std::array &getMeta() noexcept { + static const std::array meta = { + 1u, // bool + 4u, // int + 8u, // pointer size + 16u, // double + 32u, // compound types #1 + 64u, // compound types #2 + 256u, // compound types #3 + 2048u, // reasonable buffers + }; + return meta; + } + + [[nodiscard]] static inline int + convertSizeToBinIndex(std::size_t const size) noexcept { + for (std::size_t i = 0; i < getMeta().size(); ++i) { + if (getMeta()[i] >= size) { + return i; + } + } + return getMeta().size(); + } + + public: + mutable class klee::ReferenceCounter _refCount; + + private: + Mapping mapping; + std::array>::value> + sizedBins; + suballocators::LargeObjectAllocator::Control largeObjectBin; + + public: + Control() = delete; + Control(Control const &) = delete; + Control &operator=(Control const &) = delete; + Control(Control &&) = delete; + Control &operator=(Control &&) = delete; + + private: + Control(Mapping &&mapping) : mapping(std::move(mapping)) {} + }; + + static constexpr const auto unlimitedQuarantine = + Control::unlimitedQuarantine; + +private: + klee::ref control; + + std::array>::value> + sizedBins; + suballocators::LargeObjectAllocator largeObjectBin; + +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(std::move(control)) {} + + explicit operator bool() const noexcept { return !control.isNull(); } + + auto const &getSizedBinInfo() const noexcept { return Control::getMeta(); } + + [[nodiscard]] void *allocate(std::size_t size) { + assert(*this && "Invalid allocator"); + + auto const bin = Control::convertSizeToBinIndex(size); + traceLine("Allocating ", size, " bytes in bin ", bin); + + void *result = nullptr; + if (bin < static_cast(sizedBins.size())) { + result = sizedBins[bin].allocate(control->sizedBins[bin]); + } else { + result = largeObjectBin.allocate(control->largeObjectBin, size); + } + traceLine("Allocated ", result); + return result; + } + + void free(void *ptr, std::size_t size) { + assert(*this && "Invalid allocator"); + assert(ptr && "Freeing nullptrs is not supported"); // we are not ::free! + + auto const bin = Control::convertSizeToBinIndex(size); + traceLine("Freeing ", ptr, " of size ", size, " in bin ", bin); + + if (bin < static_cast(sizedBins.size())) { + return sizedBins[bin].deallocate(control->sizedBins[bin], ptr); + } else { + return largeObjectBin.deallocate(control->largeObjectBin, ptr, size); + } + } + + LocationInfo location_info(void const *const ptr, + std::size_t const size) const noexcept { + assert(*this && "Invalid allocator"); + + if (!ptr || reinterpret_cast(ptr) < 4096) { + return LocationInfo::LI_NullPage; + } + + // the following is technically UB if `ptr` does not actually point inside + // the mapping at all + for (std::size_t i = 0; i < Allocator::Control::getMeta().size(); ++i) { + if (control->sizedBins[i].mapping_begin() <= ptr && + ptr < control->sizedBins[i].mapping_end()) { + if (reinterpret_cast(ptr) + size <= + control->sizedBins[i].mapping_end()) { + return sizedBins[i].getLocationInfo(control->sizedBins[i], ptr, size); + } else { + return LocationInfo::LI_SpansSuballocators; + } + } + } + if (control->largeObjectBin.mapping_begin() <= ptr && + ptr < control->largeObjectBin.mapping_end()) { + if (reinterpret_cast(ptr) + size <= + control->largeObjectBin.mapping_end()) { + return largeObjectBin.getLocationInfo(control->largeObjectBin, ptr, + size); + } else { + // the loh is the suballocator using the largest addresses, therefore + // its mapping is not followed by that of another suballocator, but + // rather the end of the mapping + return LocationInfo::LI_NonNullOutsideMapping; + } + } + + return LocationInfo::LI_NonNullOutsideMapping; + } +}; + +class AllocatorFactory { +public: + static constexpr const auto unlimitedQuarantine = + Allocator::Control::unlimitedQuarantine; + +private: + klee::ref control; + +public: + AllocatorFactory() = default; + + AllocatorFactory(std::size_t const size, std::uint32_t const quarantineSize) + : AllocatorFactory(Mapping{0, size}, quarantineSize) {} + + AllocatorFactory(std::uintptr_t const address, std::size_t const size, + std::uint32_t const quarantineSize) + : AllocatorFactory(Mapping{address, size}, quarantineSize) {} + + AllocatorFactory(Mapping &&mapping, std::uint32_t const quarantineSize) { + assert(mapping && "Invalid mapping"); + assert(mapping.getSize() > + Allocator::Control::getMeta().size() * 4096 + 3 * 4096 && + "Mapping is *far* to small"); + + control = new Allocator::Control(std::move(mapping)); + auto const binSize = + static_cast(1) + << (std::numeric_limits::digits - 1 - + countLeadingZeroes(control->mapping.getSize() / + (Allocator::Control::getMeta().size() + 1))); + char *const base = static_cast(control->mapping.getBaseAddress()); + std::size_t totalSize = 0; + for (std::size_t i = 0; i < Allocator::Control::getMeta().size(); ++i) { + control->sizedBins[i].initialize( + base + totalSize, binSize, Allocator::Control::getMeta()[i], + quarantineSize == unlimitedQuarantine, + quarantineSize == unlimitedQuarantine ? 0 : quarantineSize); + + totalSize += binSize; + assert(totalSize <= control->mapping.getSize() && "Mapping too small"); + } + + auto largeObjectBinSize = control->mapping.getSize() - totalSize; + assert(largeObjectBinSize > 0); + control->largeObjectBin.initialize( + base + totalSize, largeObjectBinSize, + quarantineSize == unlimitedQuarantine, + quarantineSize == unlimitedQuarantine ? 0 : quarantineSize); + } + + explicit operator bool() const noexcept { return !control.isNull(); } + + Mapping &getMapping() noexcept { + assert(!!*this && "Cannot get mapping of uninitialized factory."); + return control->mapping; + } + + Mapping const &getMapping() const noexcept { + assert(!!*this && "Cannot get mapping of uninitialized factory."); + return control->mapping; + } + + Allocator makeAllocator() const { + assert(!!*this && + "Can only create an allocator from an initialized factory."); + + return Allocator{control}; + } + + explicit operator Allocator() && { + assert(!!*this && + "Can only create an allocator from an initialized factory."); + + return Allocator{std::move(control)}; + } +}; +} // namespace klee::kdalloc + +#endif diff --git a/include/klee/KDAlloc/kdalloc.h b/include/klee/KDAlloc/kdalloc.h new file mode 100644 index 00000000..c04a4ebf --- /dev/null +++ b/include/klee/KDAlloc/kdalloc.h @@ -0,0 +1,21 @@ +//===-- kdalloc.h -----------------------------------------------*- C++ -*-===// +// +// The KLEE Symbolic Virtual Machine +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef KDALLOC_KDALLOC_H +#define KDALLOC_KDALLOC_H + +#include "allocator.h" +#include "mapping.h" + +namespace klee::kdalloc { +using StackAllocator = Allocator; +using StackAllocatorFactory = AllocatorFactory; +} // namespace klee::kdalloc + +#endif diff --git a/include/klee/KDAlloc/mapping.h b/include/klee/KDAlloc/mapping.h new file mode 100644 index 00000000..4afc9d86 --- /dev/null +++ b/include/klee/KDAlloc/mapping.h @@ -0,0 +1,158 @@ +//===-- mapping.h -----------------------------------------------*- C++ -*-===// +// +// The KLEE Symbolic Virtual Machine +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef KDALLOC_MAPPING_H +#define KDALLOC_MAPPING_H + +#include +#include +#include +#include +#include + +#include +#include + +#if defined(__linux__) +#include +#endif + +#if defined(__APPLE__) +#include +#include +#endif + +#include "klee/Support/ErrorHandling.h" + +namespace klee::kdalloc { +class Mapping { + void *baseAddress = MAP_FAILED; + std::size_t size = 0; + + bool try_map(std::uintptr_t baseAddress) noexcept { + assert(this->baseAddress == MAP_FAILED); + + int flags = MAP_ANON | MAP_PRIVATE; +#if defined(__linux__) + flags |= MAP_NORESERVE; +#if LINUX_VERSION_CODE >= KERNEL_VERSION(4, 17, 0) + if (baseAddress != 0) { + flags |= MAP_FIXED_NOREPLACE; + } +#endif +#elif defined(__FreeBSD__) + if (baseAddress != 0) { + flags |= MAP_FIXED | MAP_EXCL; + } +#endif + + auto mappedAddress = ::mmap(reinterpret_cast(baseAddress), size, + PROT_READ | PROT_WRITE, flags, -1, 0); + if (baseAddress != 0 && + baseAddress != reinterpret_cast(mappedAddress)) { + [[maybe_unused]] int rc = ::munmap(mappedAddress, size); + assert(rc == 0 && "munmap failed"); + this->baseAddress = MAP_FAILED; + return false; + } + if (mappedAddress == MAP_FAILED) { + this->baseAddress = MAP_FAILED; + return false; + } + this->baseAddress = mappedAddress; + +#if defined(__linux__) + { + [[maybe_unused]] int rc = + ::madvise(this->baseAddress, size, + MADV_NOHUGEPAGE | MADV_DONTFORK | MADV_RANDOM); + assert(rc == 0 && "madvise failed"); + } +#elif defined(__FreeBSD__) + { + [[maybe_unused]] int rc = + ::minherit(this->baseAddress, size, INHERIT_NONE); + assert(rc == 0 && "minherit failed"); + } +#elif defined(__APPLE__) + { + [[maybe_unused]] int rc = + ::minherit(this->baseAddress, size, VM_INHERIT_NONE); + assert(rc == 0 && "minherit failed"); + } +#endif + + return true; + } + +public: + Mapping() = default; + + explicit Mapping(std::size_t size) noexcept : Mapping(0, size) {} + + Mapping(std::uintptr_t baseAddress, std::size_t size) noexcept : size(size) { + try_map(baseAddress); + assert(*this && "failed to allocate mapping"); + if (!*this) { + std::abort(); + } + } + + Mapping(Mapping const &) = delete; + Mapping &operator=(Mapping const &) = delete; + + Mapping(Mapping &&other) noexcept + : baseAddress(other.baseAddress), size(other.size) { + other.baseAddress = MAP_FAILED; + other.size = 0; + } + Mapping &operator=(Mapping &&other) noexcept { + if (&other != this) { + using std::swap; + swap(other.baseAddress, baseAddress); + swap(other.size, size); + } + return *this; + } + + [[nodiscard]] void *getBaseAddress() const noexcept { + assert(*this && "Invalid mapping"); + return baseAddress; + } + + [[nodiscard]] std::size_t getSize() const noexcept { return size; } + + void clear() { + assert(*this && "Invalid mapping"); + +#if defined(__linux__) + [[maybe_unused]] int rc = ::madvise(baseAddress, size, MADV_DONTNEED); + assert(rc == 0 && "madvise failed"); +#else + auto address = reinterpret_cast(baseAddress); + [[maybe_unused]] int rc = ::munmap(baseAddress, size); + assert(rc == 0 && "munmap failed"); + baseAddress = MAP_FAILED; + auto success = try_map(address); + assert(success && "could not recreate the mapping"); +#endif + } + + explicit operator bool() const noexcept { return baseAddress != MAP_FAILED; } + + ~Mapping() { + if (*this) { + [[maybe_unused]] int rc = ::munmap(baseAddress, size); + assert(rc == 0 && "munmap failed"); + } + } +}; +} // namespace klee::kdalloc + +#endif -- cgit 1.4.1