| // Copyright 2019 The Marl Authors. | |
| // | |
| // Licensed under the Apache License, Version 2.0 (the "License"); | |
| // you may not use this file except in compliance with the License. | |
| // You may obtain a copy of the License at | |
| // | |
| // https://www.apache.org/licenses/LICENSE-2.0 | |
| // | |
| // Unless required by applicable law or agreed to in writing, software | |
| // distributed under the License is distributed on an "AS IS" BASIS, | |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| // See the License for the specific language governing permissions and | |
| // limitations under the License. | |
| #ifndef marl_memory_h | |
| #define marl_memory_h | |
| #include "debug.h" | |
| #include "export.h" | |
| #include <stdint.h> | |
| #include <array> | |
| #include <cstdlib> | |
| #include <memory> | |
| #include <mutex> | |
| #include <utility> // std::forward | |
| namespace marl { | |
| template <typename T> | |
| struct StlAllocator; | |
| // pageSize() returns the size in bytes of a virtual memory page for the host | |
| // system. | |
| MARL_EXPORT | |
| size_t pageSize(); | |
| template <typename T> | |
| MARL_NO_EXPORT inline T alignUp(T val, T alignment) { | |
| return alignment * ((val + alignment - 1) / alignment); | |
| } | |
| // aligned_storage() is a replacement for std::aligned_storage that isn't busted | |
| // on older versions of MSVC. | |
| template <size_t SIZE, size_t ALIGNMENT> | |
| struct aligned_storage { | |
| struct alignas(ALIGNMENT) type { | |
| unsigned char data[SIZE]; | |
| }; | |
| }; | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // Allocation | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // Allocation holds the result of a memory allocation from an Allocator. | |
| struct Allocation { | |
| // Intended usage of the allocation. Used for allocation trackers. | |
| enum class Usage : uint8_t { | |
| Undefined = 0, | |
| Stack, // Fiber stack | |
| Create, // Allocator::create(), make_unique(), make_shared() | |
| Vector, // marl::containers::vector<T> | |
| List, // marl::containers::list<T> | |
| Stl, // marl::StlAllocator | |
| Count, // Not intended to be used as a usage type - used for upper bound. | |
| }; | |
| // Request holds all the information required to make an allocation. | |
| struct Request { | |
| size_t size = 0; // The size of the allocation in bytes. | |
| size_t alignment = 0; // The minimum alignment of the allocation. | |
| bool useGuards = false; // Whether the allocation is guarded. | |
| Usage usage = Usage::Undefined; // Intended usage of the allocation. | |
| }; | |
| void* ptr = nullptr; // The pointer to the allocated memory. | |
| Request request; // Request used for the allocation. | |
| }; | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // Allocator | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // Allocator is an interface to a memory allocator. | |
| // Marl provides a default implementation with Allocator::Default. | |
| class Allocator { | |
| public: | |
| // The default allocator. Initialized with an implementation that allocates | |
| // from the OS. Can be assigned a custom implementation. | |
| MARL_EXPORT static Allocator* Default; | |
| // Deleter is a smart-pointer compatible deleter that can be used to delete | |
| // objects created by Allocator::create(). Deleter is used by the smart | |
| // pointers returned by make_shared() and make_unique(). | |
| struct MARL_EXPORT Deleter { | |
| MARL_NO_EXPORT inline Deleter(); | |
| MARL_NO_EXPORT inline Deleter(Allocator* allocator, size_t count); | |
| template <typename T> | |
| MARL_NO_EXPORT inline void operator()(T* object); | |
| Allocator* allocator = nullptr; | |
| size_t count = 0; | |
| }; | |
| // unique_ptr<T> is an alias to std::unique_ptr<T, Deleter>. | |
| template <typename T> | |
| using unique_ptr = std::unique_ptr<T, Deleter>; | |
| virtual ~Allocator() = default; | |
| // allocate() allocates memory from the allocator. | |
| // The returned Allocation::request field must be equal to the Request | |
| // parameter. | |
| virtual Allocation allocate(const Allocation::Request&) = 0; | |
| // free() frees the memory returned by allocate(). | |
| // The Allocation must have all fields equal to those returned by allocate(). | |
| virtual void free(const Allocation&) = 0; | |
| // create() allocates and constructs an object of type T, respecting the | |
| // alignment of the type. | |
| // The pointer returned by create() must be deleted with destroy(). | |
| template <typename T, typename... ARGS> | |
| inline T* create(ARGS&&... args); | |
| // destroy() destructs and frees the object allocated with create(). | |
| template <typename T> | |
| inline void destroy(T* object); | |
| // make_unique() returns a new object allocated from the allocator wrapped | |
| // in a unique_ptr that respects the alignment of the type. | |
| template <typename T, typename... ARGS> | |
| inline unique_ptr<T> make_unique(ARGS&&... args); | |
| // make_unique_n() returns an array of n new objects allocated from the | |
| // allocator wrapped in a unique_ptr that respects the alignment of the | |
| // type. | |
| template <typename T, typename... ARGS> | |
| inline unique_ptr<T> make_unique_n(size_t n, ARGS&&... args); | |
| // make_shared() returns a new object allocated from the allocator | |
| // wrapped in a std::shared_ptr that respects the alignment of the type. | |
| template <typename T, typename... ARGS> | |
| inline std::shared_ptr<T> make_shared(ARGS&&... args); | |
| protected: | |
| Allocator() = default; | |
| }; | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // Allocator::Deleter | |
| /////////////////////////////////////////////////////////////////////////////// | |
| Allocator::Deleter::Deleter() : allocator(nullptr) {} | |
| Allocator::Deleter::Deleter(Allocator* allocator_, size_t count_) | |
| : allocator(allocator_), count(count_) {} | |
| template <typename T> | |
| void Allocator::Deleter::operator()(T* object) { | |
| object->~T(); | |
| Allocation allocation; | |
| allocation.ptr = object; | |
| allocation.request.size = sizeof(T) * count; | |
| allocation.request.alignment = alignof(T); | |
| allocation.request.usage = Allocation::Usage::Create; | |
| allocator->free(allocation); | |
| } | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // Allocator | |
| /////////////////////////////////////////////////////////////////////////////// | |
| template <typename T, typename... ARGS> | |
| T* Allocator::create(ARGS&&... args) { | |
| Allocation::Request request; | |
| request.size = sizeof(T); | |
| request.alignment = alignof(T); | |
| request.usage = Allocation::Usage::Create; | |
| auto alloc = allocate(request); | |
| new (alloc.ptr) T(std::forward<ARGS>(args)...); | |
| return reinterpret_cast<T*>(alloc.ptr); | |
| } | |
| template <typename T> | |
| void Allocator::destroy(T* object) { | |
| object->~T(); | |
| Allocation alloc; | |
| alloc.ptr = object; | |
| alloc.request.size = sizeof(T); | |
| alloc.request.alignment = alignof(T); | |
| alloc.request.usage = Allocation::Usage::Create; | |
| free(alloc); | |
| } | |
| template <typename T, typename... ARGS> | |
| Allocator::unique_ptr<T> Allocator::make_unique(ARGS&&... args) { | |
| return make_unique_n<T>(1, std::forward<ARGS>(args)...); | |
| } | |
| template <typename T, typename... ARGS> | |
| Allocator::unique_ptr<T> Allocator::make_unique_n(size_t n, ARGS&&... args) { | |
| if (n == 0) { | |
| return nullptr; | |
| } | |
| Allocation::Request request; | |
| request.size = sizeof(T) * n; | |
| request.alignment = alignof(T); | |
| request.usage = Allocation::Usage::Create; | |
| auto alloc = allocate(request); | |
| new (alloc.ptr) T(std::forward<ARGS>(args)...); | |
| return unique_ptr<T>(reinterpret_cast<T*>(alloc.ptr), Deleter{this, n}); | |
| } | |
| template <typename T, typename... ARGS> | |
| std::shared_ptr<T> Allocator::make_shared(ARGS&&... args) { | |
| Allocation::Request request; | |
| request.size = sizeof(T); | |
| request.alignment = alignof(T); | |
| request.usage = Allocation::Usage::Create; | |
| auto alloc = allocate(request); | |
| new (alloc.ptr) T(std::forward<ARGS>(args)...); | |
| return std::shared_ptr<T>(reinterpret_cast<T*>(alloc.ptr), Deleter{this, 1}); | |
| } | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // TrackedAllocator | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // TrackedAllocator wraps an Allocator to track the allocations made. | |
| class TrackedAllocator : public Allocator { | |
| public: | |
| struct UsageStats { | |
| // Total number of allocations. | |
| size_t count = 0; | |
| // total allocation size in bytes (as requested, may be higher due to | |
| // alignment or guards). | |
| size_t bytes = 0; | |
| }; | |
| struct Stats { | |
| // numAllocations() returns the total number of allocations across all | |
| // usages for the allocator. | |
| inline size_t numAllocations() const; | |
| // bytesAllocated() returns the total number of bytes allocated across all | |
| // usages for the allocator. | |
| inline size_t bytesAllocated() const; | |
| // Statistics per usage. | |
| std::array<UsageStats, size_t(Allocation::Usage::Count)> byUsage; | |
| }; | |
| // Constructor that wraps an existing allocator. | |
| inline TrackedAllocator(Allocator* allocator); | |
| // stats() returns the current allocator statistics. | |
| inline Stats stats(); | |
| // Allocator compliance | |
| inline Allocation allocate(const Allocation::Request&) override; | |
| inline void free(const Allocation&) override; | |
| private: | |
| Allocator* const allocator; | |
| std::mutex mutex; | |
| Stats stats_; | |
| }; | |
| size_t TrackedAllocator::Stats::numAllocations() const { | |
| size_t out = 0; | |
| for (auto& stats : byUsage) { | |
| out += stats.count; | |
| } | |
| return out; | |
| } | |
| size_t TrackedAllocator::Stats::bytesAllocated() const { | |
| size_t out = 0; | |
| for (auto& stats : byUsage) { | |
| out += stats.bytes; | |
| } | |
| return out; | |
| } | |
| TrackedAllocator::TrackedAllocator(Allocator* allocator_) | |
| : allocator(allocator_) {} | |
| TrackedAllocator::Stats TrackedAllocator::stats() { | |
| std::unique_lock<std::mutex> lock(mutex); | |
| return stats_; | |
| } | |
| Allocation TrackedAllocator::allocate(const Allocation::Request& request) { | |
| { | |
| std::unique_lock<std::mutex> lock(mutex); | |
| auto& usageStats = stats_.byUsage[int(request.usage)]; | |
| ++usageStats.count; | |
| usageStats.bytes += request.size; | |
| } | |
| return allocator->allocate(request); | |
| } | |
| void TrackedAllocator::free(const Allocation& allocation) { | |
| { | |
| std::unique_lock<std::mutex> lock(mutex); | |
| auto& usageStats = stats_.byUsage[int(allocation.request.usage)]; | |
| MARL_ASSERT(usageStats.count > 0, | |
| "TrackedAllocator detected abnormal free()"); | |
| MARL_ASSERT(usageStats.bytes >= allocation.request.size, | |
| "TrackedAllocator detected abnormal free()"); | |
| --usageStats.count; | |
| usageStats.bytes -= allocation.request.size; | |
| } | |
| return allocator->free(allocation); | |
| } | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // StlAllocator | |
| /////////////////////////////////////////////////////////////////////////////// | |
| // StlAllocator exposes an STL-compatible allocator wrapping a marl::Allocator. | |
| template <typename T> | |
| struct StlAllocator { | |
| using value_type = T; | |
| using pointer = T*; | |
| using const_pointer = const T*; | |
| using reference = T&; | |
| using const_reference = const T&; | |
| using size_type = size_t; | |
| using difference_type = size_t; | |
| // An equivalent STL allocator for a different type. | |
| template <class U> | |
| struct rebind { | |
| typedef StlAllocator<U> other; | |
| }; | |
| // Constructs an StlAllocator that will allocate using allocator. | |
| // allocator must remain valid until this StlAllocator has been destroyed. | |
| inline StlAllocator(Allocator* allocator); | |
| template <typename U> | |
| inline StlAllocator(const StlAllocator<U>& other); | |
| // Returns the actual address of x even in presence of overloaded operator&. | |
| inline pointer address(reference x) const; | |
| inline const_pointer address(const_reference x) const; | |
| // Allocates the memory for n objects of type T. | |
| // Does not actually construct the objects. | |
| inline T* allocate(std::size_t n); | |
| // Deallocates the memory for n objects of type T. | |
| inline void deallocate(T* p, std::size_t n); | |
| // Returns the maximum theoretically possible number of T stored in this | |
| // allocator. | |
| inline size_type max_size() const; | |
| // Copy constructs an object of type T at the address p. | |
| inline void construct(pointer p, const_reference val); | |
| // Constructs an object of type U at the address P forwarning all other | |
| // arguments to the constructor. | |
| template <typename U, typename... Args> | |
| inline void construct(U* p, Args&&... args); | |
| // Deconstructs the object at p. It does not free the memory. | |
| inline void destroy(pointer p); | |
| // Deconstructs the object at p. It does not free the memory. | |
| template <typename U> | |
| inline void destroy(U* p); | |
| private: | |
| inline Allocation::Request request(size_t n) const; | |
| template <typename U> | |
| friend struct StlAllocator; | |
| Allocator* allocator; | |
| }; | |
| template <typename T> | |
| StlAllocator<T>::StlAllocator(Allocator* allocator_) : allocator(allocator_) {} | |
| template <typename T> | |
| template <typename U> | |
| StlAllocator<T>::StlAllocator(const StlAllocator<U>& other) { | |
| allocator = other.allocator; | |
| } | |
| template <typename T> | |
| typename StlAllocator<T>::pointer StlAllocator<T>::address(reference x) const { | |
| return &x; | |
| } | |
| template <typename T> | |
| typename StlAllocator<T>::const_pointer StlAllocator<T>::address( | |
| const_reference x) const { | |
| return &x; | |
| } | |
| template <typename T> | |
| T* StlAllocator<T>::allocate(std::size_t n) { | |
| auto alloc = allocator->allocate(request(n)); | |
| return reinterpret_cast<T*>(alloc.ptr); | |
| } | |
| template <typename T> | |
| void StlAllocator<T>::deallocate(T* p, std::size_t n) { | |
| Allocation alloc; | |
| alloc.ptr = p; | |
| alloc.request = request(n); | |
| allocator->free(alloc); | |
| } | |
| template <typename T> | |
| typename StlAllocator<T>::size_type StlAllocator<T>::max_size() const { | |
| return std::numeric_limits<size_type>::max() / sizeof(value_type); | |
| } | |
| template <typename T> | |
| void StlAllocator<T>::construct(pointer p, const_reference val) { | |
| new (p) T(val); | |
| } | |
| template <typename T> | |
| template <typename U, typename... Args> | |
| void StlAllocator<T>::construct(U* p, Args&&... args) { | |
| ::new ((void*)p) U(std::forward<Args>(args)...); | |
| } | |
| template <typename T> | |
| void StlAllocator<T>::destroy(pointer p) { | |
| ((T*)p)->~T(); | |
| } | |
| template <typename T> | |
| template <typename U> | |
| void StlAllocator<T>::destroy(U* p) { | |
| p->~U(); | |
| } | |
| template <typename T> | |
| Allocation::Request StlAllocator<T>::request(size_t n) const { | |
| Allocation::Request req = {}; | |
| req.size = sizeof(T) * n; | |
| req.alignment = alignof(T); | |
| req.usage = Allocation::Usage::Stl; | |
| return req; | |
| } | |
| } // namespace marl | |
| #endif // marl_memory_h |