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 34 namespace android { 35 namespace 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 */ 43 class LinearAllocator { 44 public: 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> alloc(size_t size)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> create(Params &&...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> create_trivial(Params &&...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 template<class T> create_trivial_array(int count)88 T* create_trivial_array(int count) { 89 static_assert(std::is_trivially_destructible<T>::value, 90 "Error, called create_trivial_array on a non-trivial type"); 91 return reinterpret_cast<T*>(allocImpl(sizeof(T) * count)); 92 } 93 94 /** 95 * Attempt to deallocate the given buffer, with the LinearAllocator attempting to rewind its 96 * state if possible. 97 */ 98 void rewindIfLastAlloc(void* ptr, size_t allocSize); 99 100 /** 101 * Same as rewindIfLastAlloc(void*, size_t) 102 */ 103 template<class T> rewindIfLastAlloc(T * ptr)104 void rewindIfLastAlloc(T* ptr) { 105 rewindIfLastAlloc((void*)ptr, sizeof(T)); 106 } 107 108 /** 109 * Dump memory usage statistics to the log (allocated and wasted space) 110 */ 111 void dumpMemoryStats(const char* prefix = ""); 112 113 /** 114 * The number of bytes used for buffers allocated in the LinearAllocator (does not count space 115 * wasted) 116 */ usedSize()117 size_t usedSize() const { return mTotalAllocated - mWastedSpace; } 118 119 private: 120 LinearAllocator(const LinearAllocator& other); 121 122 class Page; 123 typedef void (*Destructor)(void* addr); 124 struct DestructorNode { 125 Destructor dtor; 126 void* addr; 127 DestructorNode* next = nullptr; 128 }; 129 130 void* allocImpl(size_t size); 131 132 void addToDestructionList(Destructor, void* addr); 133 void runDestructorFor(void* addr); 134 Page* newPage(size_t pageSize); 135 bool fitsInCurrentPage(size_t size); 136 void ensureNext(size_t size); 137 void* start(Page *p); 138 void* end(Page* p); 139 140 size_t mPageSize; 141 size_t mMaxAllocSize; 142 void* mNext; 143 Page* mCurrentPage; 144 Page* mPages; 145 DestructorNode* mDtorList = nullptr; 146 147 // Memory usage tracking 148 size_t mTotalAllocated; 149 size_t mWastedSpace; 150 size_t mPageCount; 151 size_t mDedicatedPageCount; 152 }; 153 154 template <class T> 155 class LinearStdAllocator { 156 public: 157 typedef T value_type; // needed to implement std::allocator 158 typedef T* pointer; // needed to implement std::allocator 159 LinearStdAllocator(LinearAllocator & allocator)160 explicit LinearStdAllocator(LinearAllocator& allocator) 161 : linearAllocator(allocator) {} LinearStdAllocator(const LinearStdAllocator & other)162 LinearStdAllocator(const LinearStdAllocator& other) 163 : linearAllocator(other.linearAllocator) {} ~LinearStdAllocator()164 ~LinearStdAllocator() {} 165 166 // rebind marks that allocators can be rebound to different types 167 template <class U> 168 struct rebind { 169 typedef LinearStdAllocator<U> other; 170 }; 171 // enable allocators to be constructed from other templated types 172 template <class U> LinearStdAllocator(const LinearStdAllocator<U> & other)173 LinearStdAllocator(const LinearStdAllocator<U>& other) // NOLINT(implicit) 174 : linearAllocator(other.linearAllocator) {} 175 176 T* allocate(size_t num, const void* = 0) { 177 return (T*)(linearAllocator.alloc<void*>(num * sizeof(T))); 178 } 179 deallocate(pointer p,size_t num)180 void deallocate(pointer p, size_t num) { 181 // attempt to rewind, but no guarantees 182 linearAllocator.rewindIfLastAlloc(p, num * sizeof(T)); 183 } 184 185 // public so template copy constructor can access 186 LinearAllocator& linearAllocator; 187 }; 188 189 // return that all specializations of LinearStdAllocator are interchangeable 190 template <class T1, class T2> 191 bool operator== (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return true; } 192 template <class T1, class T2> 193 bool operator!= (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return false; } 194 195 template <class T> 196 class LsaVector : public std::vector<T, LinearStdAllocator<T>> { 197 public: LsaVector(const LinearStdAllocator<T> & allocator)198 explicit LsaVector(const LinearStdAllocator<T>& allocator) 199 : std::vector<T, LinearStdAllocator<T>>(allocator) {} 200 }; 201 202 }; // namespace uirenderer 203 }; // namespace android 204 205 #endif // ANDROID_LINEARALLOCATOR_H 206