11ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck/* 21ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * Copyright 2012, The Android Open Source Project 31ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * 41ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * Redistribution and use in source and binary forms, with or without 51ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * modification, are permitted provided that the following conditions 61ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * are met: 71ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * * Redistributions of source code must retain the above copyright 81ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * notice, this list of conditions and the following disclaimer. 91ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * * Redistributions in binary form must reproduce the above copyright 101ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * notice, this list of conditions and the following disclaimer in the 111ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * documentation and/or other materials provided with the distribution. 121ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * 131ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY 141ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 151ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 161ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 171ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 181ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 191ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 201ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 211ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 221ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 231ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 241ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck */ 251ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 261ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck#ifndef ANDROID_LINEARALLOCATOR_H 271ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck#define ANDROID_LINEARALLOCATOR_H 281ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 291ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck#include <stddef.h> 30b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck#include <type_traits> 311ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 32b36af87f8275f4b982906f88193ec27600f2746aChris Craik#include <vector> 33b36af87f8275f4b982906f88193ec27600f2746aChris Craik 341ed723723d9e42a064d54799cc24bdc24891e44dJohn Recknamespace android { 351ed723723d9e42a064d54799cc24bdc24891e44dJohn Recknamespace uirenderer { 361ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 371ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck/** 381ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * A memory manager that internally allocates multi-kbyte buffers for placing objects in. It avoids 391ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * the overhead of malloc when many objects are allocated. It is most useful when creating many 401ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * small objects with a similar lifetime, and doesn't add significant overhead for large 411ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * allocations. 421ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck */ 431ed723723d9e42a064d54799cc24bdc24891e44dJohn Reckclass LinearAllocator { 441ed723723d9e42a064d54799cc24bdc24891e44dJohn Reckpublic: 451ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck LinearAllocator(); 461ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck ~LinearAllocator(); 471ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 481ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck /** 491ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * Reserves and returns a region of memory of at least size 'size', aligning as needed. 501ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * Typically this is used in an object's overridden new() method or as a replacement for malloc. 511ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * 521ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * The lifetime of the returned buffers is tied to that of the LinearAllocator. If calling 531ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * delete() on an object stored in a buffer is needed, it should be overridden to use 541ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * rewindIfLastAlloc() 557df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck * 567df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck * Note that unlike create, for alloc the type is purely for compile-time error 577df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck * checking and does not affect size. 581ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck */ 597df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck template<class T> 607df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck void* alloc(size_t size) { 617df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck static_assert(std::is_trivially_destructible<T>::value, 627df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck "Error, type is non-trivial! did you mean to use create()?"); 637df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck return allocImpl(size); 647df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck } 651ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 661ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck /** 67e4db79de127cfe961195f52907af8451026eaa20Chris Craik * Allocates an instance of the template type with the given construction parameters 68b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck * and adds it to the automatic destruction list. 69b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck */ 70e4db79de127cfe961195f52907af8451026eaa20Chris Craik template<class T, typename... Params> 717df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck T* create(Params&&... params) { 727df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck T* ret = new (allocImpl(sizeof(T))) T(std::forward<Params>(params)...); 737df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck if (!std::is_trivially_destructible<T>::value) { 747df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck auto dtor = [](void* ret) { ((T*)ret)->~T(); }; 757df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck addToDestructionList(dtor, ret); 767df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck } 77b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck return ret; 78b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck } 79b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck 807df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck template<class T, typename... Params> 817df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck T* create_trivial(Params&&... params) { 827df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck static_assert(std::is_trivially_destructible<T>::value, 837df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck "Error, called create_trivial on a non-trivial type"); 847df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck return new (allocImpl(sizeof(T))) T(std::forward<Params>(params)...); 85b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck } 86b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck 877a89600bac7ab889a5ba8a994c57d677de0e45d5Chris Craik template<class T> 887a89600bac7ab889a5ba8a994c57d677de0e45d5Chris Craik T* create_trivial_array(int count) { 897a89600bac7ab889a5ba8a994c57d677de0e45d5Chris Craik static_assert(std::is_trivially_destructible<T>::value, 907a89600bac7ab889a5ba8a994c57d677de0e45d5Chris Craik "Error, called create_trivial_array on a non-trivial type"); 917a89600bac7ab889a5ba8a994c57d677de0e45d5Chris Craik return reinterpret_cast<T*>(allocImpl(sizeof(T) * count)); 927a89600bac7ab889a5ba8a994c57d677de0e45d5Chris Craik } 937a89600bac7ab889a5ba8a994c57d677de0e45d5Chris Craik 94b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck /** 951ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * Attempt to deallocate the given buffer, with the LinearAllocator attempting to rewind its 96b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck * state if possible. 971ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck */ 981ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck void rewindIfLastAlloc(void* ptr, size_t allocSize); 991ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 1001ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck /** 101b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck * Same as rewindIfLastAlloc(void*, size_t) 102b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck */ 103b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck template<class T> 104b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck void rewindIfLastAlloc(T* ptr) { 105b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck rewindIfLastAlloc((void*)ptr, sizeof(T)); 106b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck } 107b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck 108b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck /** 1091ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * Dump memory usage statistics to the log (allocated and wasted space) 1101ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck */ 1111ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck void dumpMemoryStats(const char* prefix = ""); 1121ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 1131ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck /** 1141ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * The number of bytes used for buffers allocated in the LinearAllocator (does not count space 1151ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck * wasted) 1161ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck */ 1171ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck size_t usedSize() const { return mTotalAllocated - mWastedSpace; } 1181ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 1191ed723723d9e42a064d54799cc24bdc24891e44dJohn Reckprivate: 1201ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck LinearAllocator(const LinearAllocator& other); 1211ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 1221ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck class Page; 123b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck typedef void (*Destructor)(void* addr); 124b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck struct DestructorNode { 125b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck Destructor dtor; 126b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck void* addr; 127b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck DestructorNode* next = nullptr; 128b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck }; 1291ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 1307df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck void* allocImpl(size_t size); 1317df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck 132b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck void addToDestructionList(Destructor, void* addr); 133b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck void runDestructorFor(void* addr); 1341ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck Page* newPage(size_t pageSize); 1351ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck bool fitsInCurrentPage(size_t size); 1361ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck void ensureNext(size_t size); 1371ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck void* start(Page *p); 1381ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck void* end(Page* p); 1391ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 1401ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck size_t mPageSize; 1411ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck size_t mMaxAllocSize; 1421ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck void* mNext; 1431ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck Page* mCurrentPage; 1441ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck Page* mPages; 145b5bc454870c8b7df88a633b18c4c6499361c3a08John Reck DestructorNode* mDtorList = nullptr; 1461ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 1471ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck // Memory usage tracking 1481ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck size_t mTotalAllocated; 1491ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck size_t mWastedSpace; 1501ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck size_t mPageCount; 1511ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck size_t mDedicatedPageCount; 1521ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck}; 1531ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 15481a1d2a15927b06b84359f839ab03ac8a20970bdChris Craiktemplate <class T> 15581a1d2a15927b06b84359f839ab03ac8a20970bdChris Craikclass LinearStdAllocator { 15681a1d2a15927b06b84359f839ab03ac8a20970bdChris Craikpublic: 15781a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik typedef T value_type; // needed to implement std::allocator 15881a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik typedef T* pointer; // needed to implement std::allocator 15981a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik 16081a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik LinearStdAllocator(LinearAllocator& allocator) 16181a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik : linearAllocator(allocator) {} 16281a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik LinearStdAllocator(const LinearStdAllocator& other) 16381a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik : linearAllocator(other.linearAllocator) {} 16481a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik ~LinearStdAllocator() {} 16581a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik 16681a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik // rebind marks that allocators can be rebound to different types 16781a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik template <class U> 16881a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik struct rebind { 16981a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik typedef LinearStdAllocator<U> other; 17081a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik }; 17181a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik // enable allocators to be constructed from other templated types 17281a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik template <class U> 17381a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik LinearStdAllocator(const LinearStdAllocator<U>& other) 17481a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik : linearAllocator(other.linearAllocator) {} 17581a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik 17681a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik T* allocate(size_t num, const void* = 0) { 1777df9ff2a08fd4bbd9b2e734a357cffcf64675df9John Reck return (T*)(linearAllocator.alloc<void*>(num * sizeof(T))); 17881a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik } 17981a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik 18081a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik void deallocate(pointer p, size_t num) { 18181a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik // attempt to rewind, but no guarantees 18281a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik linearAllocator.rewindIfLastAlloc(p, num * sizeof(T)); 18381a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik } 18481a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik 18581a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik // public so template copy constructor can access 18681a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik LinearAllocator& linearAllocator; 18781a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik}; 18881a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik 18981a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik// return that all specializations of LinearStdAllocator are interchangeable 19081a1d2a15927b06b84359f839ab03ac8a20970bdChris Craiktemplate <class T1, class T2> 19181a1d2a15927b06b84359f839ab03ac8a20970bdChris Craikbool operator== (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return true; } 19281a1d2a15927b06b84359f839ab03ac8a20970bdChris Craiktemplate <class T1, class T2> 19381a1d2a15927b06b84359f839ab03ac8a20970bdChris Craikbool operator!= (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return false; } 19481a1d2a15927b06b84359f839ab03ac8a20970bdChris Craik 195b36af87f8275f4b982906f88193ec27600f2746aChris Craiktemplate <class T> 196b36af87f8275f4b982906f88193ec27600f2746aChris Craikclass LsaVector : public std::vector<T, LinearStdAllocator<T>> { 197b36af87f8275f4b982906f88193ec27600f2746aChris Craikpublic: 198b36af87f8275f4b982906f88193ec27600f2746aChris Craik LsaVector(const LinearStdAllocator<T>& allocator) 199b36af87f8275f4b982906f88193ec27600f2746aChris Craik : std::vector<T, LinearStdAllocator<T>>(allocator) {} 200b36af87f8275f4b982906f88193ec27600f2746aChris Craik}; 201b36af87f8275f4b982906f88193ec27600f2746aChris Craik 2021ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck}; // namespace uirenderer 2031ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck}; // namespace android 2041ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck 2051ed723723d9e42a064d54799cc24bdc24891e44dJohn Reck#endif // ANDROID_LINEARALLOCATOR_H 206