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; } allocatedSize()118 size_t allocatedSize() const { return mTotalAllocated; } 119 120 private: 121 LinearAllocator(const LinearAllocator& other); 122 123 class Page; 124 typedef void (*Destructor)(void* addr); 125 struct DestructorNode { 126 Destructor dtor; 127 void* addr; 128 DestructorNode* next = nullptr; 129 }; 130 131 void* allocImpl(size_t size); 132 133 void addToDestructionList(Destructor, void* addr); 134 void runDestructorFor(void* addr); 135 Page* newPage(size_t pageSize); 136 bool fitsInCurrentPage(size_t size); 137 void ensureNext(size_t size); 138 void* start(Page* p); 139 void* end(Page* p); 140 141 size_t mPageSize; 142 size_t mMaxAllocSize; 143 void* mNext; 144 Page* mCurrentPage; 145 Page* mPages; 146 DestructorNode* mDtorList = nullptr; 147 148 // Memory usage tracking 149 size_t mTotalAllocated; 150 size_t mWastedSpace; 151 size_t mPageCount; 152 size_t mDedicatedPageCount; 153 }; 154 155 template <class T> 156 class LinearStdAllocator { 157 public: 158 typedef T value_type; // needed to implement std::allocator 159 typedef T* pointer; // needed to implement std::allocator 160 LinearStdAllocator(LinearAllocator & allocator)161 explicit LinearStdAllocator(LinearAllocator& allocator) : linearAllocator(allocator) {} LinearStdAllocator(const LinearStdAllocator & other)162 LinearStdAllocator(const LinearStdAllocator& other) : linearAllocator(other.linearAllocator) {} ~LinearStdAllocator()163 ~LinearStdAllocator() {} 164 165 // rebind marks that allocators can be rebound to different types 166 template <class U> 167 struct rebind { 168 typedef LinearStdAllocator<U> other; 169 }; 170 // enable allocators to be constructed from other templated types 171 template <class U> LinearStdAllocator(const LinearStdAllocator<U> & other)172 LinearStdAllocator(const LinearStdAllocator<U>& other) // NOLINT(google-explicit-constructor) 173 : linearAllocator(other.linearAllocator) {} 174 175 T* allocate(size_t num, const void* = 0) { 176 return (T*)(linearAllocator.alloc<void*>(num * sizeof(T))); 177 } 178 deallocate(pointer p,size_t num)179 void deallocate(pointer p, size_t num) { 180 // attempt to rewind, but no guarantees 181 linearAllocator.rewindIfLastAlloc(p, num * sizeof(T)); 182 } 183 184 // public so template copy constructor can access 185 LinearAllocator& linearAllocator; 186 }; 187 188 // return that all specializations of LinearStdAllocator are interchangeable 189 template <class T1, class T2> 190 bool operator==(const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { 191 return true; 192 } 193 template <class T1, class T2> 194 bool operator!=(const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { 195 return false; 196 } 197 198 template <class T> 199 class LsaVector : public std::vector<T, LinearStdAllocator<T>> { 200 public: LsaVector(const LinearStdAllocator<T> & allocator)201 explicit LsaVector(const LinearStdAllocator<T>& allocator) 202 : std::vector<T, LinearStdAllocator<T>>(allocator) {} 203 }; 204 205 } // namespace uirenderer 206 } // namespace android 207 208 #endif // ANDROID_LINEARALLOCATOR_H 209