LinearAllocator.h revision 7df9ff2a08fd4bbd9b2e734a357cffcf64675df9
1/* 2 * Copyright 2012, The Android Open Source Project 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * * Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * * Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#ifndef ANDROID_LINEARALLOCATOR_H 27#define ANDROID_LINEARALLOCATOR_H 28 29#include <stddef.h> 30#include <type_traits> 31 32#include <vector> 33 34namespace android { 35namespace uirenderer { 36 37/** 38 * A memory manager that internally allocates multi-kbyte buffers for placing objects in. It avoids 39 * the overhead of malloc when many objects are allocated. It is most useful when creating many 40 * small objects with a similar lifetime, and doesn't add significant overhead for large 41 * allocations. 42 */ 43class LinearAllocator { 44public: 45 LinearAllocator(); 46 ~LinearAllocator(); 47 48 /** 49 * Reserves and returns a region of memory of at least size 'size', aligning as needed. 50 * Typically this is used in an object's overridden new() method or as a replacement for malloc. 51 * 52 * The lifetime of the returned buffers is tied to that of the LinearAllocator. If calling 53 * delete() on an object stored in a buffer is needed, it should be overridden to use 54 * rewindIfLastAlloc() 55 * 56 * Note that unlike create, for alloc the type is purely for compile-time error 57 * checking and does not affect size. 58 */ 59 template<class T> 60 void* alloc(size_t size) { 61 static_assert(std::is_trivially_destructible<T>::value, 62 "Error, type is non-trivial! did you mean to use create()?"); 63 return allocImpl(size); 64 } 65 66 /** 67 * Allocates an instance of the template type with the given construction parameters 68 * and adds it to the automatic destruction list. 69 */ 70 template<class T, typename... Params> 71 T* create(Params&&... params) { 72 T* ret = new (allocImpl(sizeof(T))) T(std::forward<Params>(params)...); 73 if (!std::is_trivially_destructible<T>::value) { 74 auto dtor = [](void* ret) { ((T*)ret)->~T(); }; 75 addToDestructionList(dtor, ret); 76 } 77 return ret; 78 } 79 80 template<class T, typename... Params> 81 T* create_trivial(Params&&... params) { 82 static_assert(std::is_trivially_destructible<T>::value, 83 "Error, called create_trivial on a non-trivial type"); 84 return new (allocImpl(sizeof(T))) T(std::forward<Params>(params)...); 85 } 86 87 /** 88 * Attempt to deallocate the given buffer, with the LinearAllocator attempting to rewind its 89 * state if possible. 90 */ 91 void rewindIfLastAlloc(void* ptr, size_t allocSize); 92 93 /** 94 * Same as rewindIfLastAlloc(void*, size_t) 95 */ 96 template<class T> 97 void rewindIfLastAlloc(T* ptr) { 98 rewindIfLastAlloc((void*)ptr, sizeof(T)); 99 } 100 101 /** 102 * Dump memory usage statistics to the log (allocated and wasted space) 103 */ 104 void dumpMemoryStats(const char* prefix = ""); 105 106 /** 107 * The number of bytes used for buffers allocated in the LinearAllocator (does not count space 108 * wasted) 109 */ 110 size_t usedSize() const { return mTotalAllocated - mWastedSpace; } 111 112private: 113 LinearAllocator(const LinearAllocator& other); 114 115 class Page; 116 typedef void (*Destructor)(void* addr); 117 struct DestructorNode { 118 Destructor dtor; 119 void* addr; 120 DestructorNode* next = nullptr; 121 }; 122 123 void* allocImpl(size_t size); 124 125 void addToDestructionList(Destructor, void* addr); 126 void runDestructorFor(void* addr); 127 Page* newPage(size_t pageSize); 128 bool fitsInCurrentPage(size_t size); 129 void ensureNext(size_t size); 130 void* start(Page *p); 131 void* end(Page* p); 132 133 size_t mPageSize; 134 size_t mMaxAllocSize; 135 void* mNext; 136 Page* mCurrentPage; 137 Page* mPages; 138 DestructorNode* mDtorList = nullptr; 139 140 // Memory usage tracking 141 size_t mTotalAllocated; 142 size_t mWastedSpace; 143 size_t mPageCount; 144 size_t mDedicatedPageCount; 145}; 146 147template <class T> 148class LinearStdAllocator { 149public: 150 typedef T value_type; // needed to implement std::allocator 151 typedef T* pointer; // needed to implement std::allocator 152 153 LinearStdAllocator(LinearAllocator& allocator) 154 : linearAllocator(allocator) {} 155 LinearStdAllocator(const LinearStdAllocator& other) 156 : linearAllocator(other.linearAllocator) {} 157 ~LinearStdAllocator() {} 158 159 // rebind marks that allocators can be rebound to different types 160 template <class U> 161 struct rebind { 162 typedef LinearStdAllocator<U> other; 163 }; 164 // enable allocators to be constructed from other templated types 165 template <class U> 166 LinearStdAllocator(const LinearStdAllocator<U>& other) 167 : linearAllocator(other.linearAllocator) {} 168 169 T* allocate(size_t num, const void* = 0) { 170 return (T*)(linearAllocator.alloc<void*>(num * sizeof(T))); 171 } 172 173 void deallocate(pointer p, size_t num) { 174 // attempt to rewind, but no guarantees 175 linearAllocator.rewindIfLastAlloc(p, num * sizeof(T)); 176 } 177 178 // public so template copy constructor can access 179 LinearAllocator& linearAllocator; 180}; 181 182// return that all specializations of LinearStdAllocator are interchangeable 183template <class T1, class T2> 184bool operator== (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return true; } 185template <class T1, class T2> 186bool operator!= (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return false; } 187 188template <class T> 189class LsaVector : public std::vector<T, LinearStdAllocator<T>> { 190public: 191 LsaVector(const LinearStdAllocator<T>& allocator) 192 : std::vector<T, LinearStdAllocator<T>>(allocator) {} 193}; 194 195}; // namespace uirenderer 196}; // namespace android 197 198#endif // ANDROID_LINEARALLOCATOR_H 199