Home | History | Annotate | Download | only in utils 
      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>
     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     template<class T>
     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>
    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      */
    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 
    160     LinearStdAllocator(LinearAllocator& allocator)
    161             : linearAllocator(allocator) {}
    162     LinearStdAllocator(const LinearStdAllocator& other)
    163             : linearAllocator(other.linearAllocator) {}
    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>
    173     LinearStdAllocator(const LinearStdAllocator<U>& other)
    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 
    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:
    198     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