| // 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 |