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) : linearAllocator(allocator) {} LinearStdAllocator(const LinearStdAllocator & other)161 LinearStdAllocator(const LinearStdAllocator& other) : linearAllocator(other.linearAllocator) {} ~LinearStdAllocator()162 ~LinearStdAllocator() {} 163 164 // rebind marks that allocators can be rebound to different types 165 template <class U> 166 struct rebind { 167 typedef LinearStdAllocator<U> other; 168 }; 169 // enable allocators to be constructed from other templated types 170 template <class U> LinearStdAllocator(const LinearStdAllocator<U> & other)171 LinearStdAllocator(const LinearStdAllocator<U>& other) // NOLINT(google-explicit-constructor) 172 : linearAllocator(other.linearAllocator) {} 173 174 T* allocate(size_t num, const void* = 0) { 175 return (T*)(linearAllocator.alloc<void*>(num * sizeof(T))); 176 } 177 deallocate(pointer p,size_t num)178 void deallocate(pointer p, size_t num) { 179 // attempt to rewind, but no guarantees 180 linearAllocator.rewindIfLastAlloc(p, num * sizeof(T)); 181 } 182 183 // public so template copy constructor can access 184 LinearAllocator& linearAllocator; 185 }; 186 187 // return that all specializations of LinearStdAllocator are interchangeable 188 template <class T1, class T2> 189 bool operator==(const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { 190 return true; 191 } 192 template <class T1, class T2> 193 bool operator!=(const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { 194 return false; 195 } 196 197 template <class T> 198 class LsaVector : public std::vector<T, LinearStdAllocator<T>> { 199 public: LsaVector(const LinearStdAllocator<T> & allocator)200 explicit LsaVector(const LinearStdAllocator<T>& allocator) 201 : std::vector<T, LinearStdAllocator<T>>(allocator) {} 202 }; 203 204 } // namespace uirenderer 205 } // namespace android 206 207 #endif // ANDROID_LINEARALLOCATOR_H 208