LinearAllocator.h revision e537330ead4111cae74668bbc25a332e186d6c91 
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
34namespace android {
35namespace 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 */
43class LinearAllocator {
44public:
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    void* alloc(size_t size);
57
58    /**
59     * Allocates an instance of the template type with the given construction parameters
60     * and adds it to the automatic destruction list.
61     */
62    template<class T, typename... Params>
63    T* create(Params... params) {
64        T* ret = new (*this) T(params...);
65        autoDestroy(ret);
66        return ret;
67    }
68
69    /**
70     * Adds the pointer to the tracking list to have its destructor called
71     * when the LinearAllocator is destroyed.
72     */
73    template<class T>
74    void autoDestroy(T* addr) {
75        if (!std::is_trivially_destructible<T>::value) {
76            auto dtor = [](void* addr) { ((T*)addr)->~T(); };
77            addToDestructionList(dtor, addr);
78        }
79    }
80
81    /**
82     * Attempt to deallocate the given buffer, with the LinearAllocator attempting to rewind its
83     * state if possible.
84     */
85    void rewindIfLastAlloc(void* ptr, size_t allocSize);
86
87    /**
88     * Same as rewindIfLastAlloc(void*, size_t)
89     */
90    template<class T>
91    void rewindIfLastAlloc(T* ptr) {
92        rewindIfLastAlloc((void*)ptr, sizeof(T));
93    }
94
95    /**
96     * Dump memory usage statistics to the log (allocated and wasted space)
97     */
98    void dumpMemoryStats(const char* prefix = "");
99
100    /**
101     * The number of bytes used for buffers allocated in the LinearAllocator (does not count space
102     * wasted)
103     */
104    size_t usedSize() const { return mTotalAllocated - mWastedSpace; }
105
106private:
107    LinearAllocator(const LinearAllocator& other);
108
109    class Page;
110    typedef void (*Destructor)(void* addr);
111    struct DestructorNode {
112        Destructor dtor;
113        void* addr;
114        DestructorNode* next = nullptr;
115    };
116
117    void addToDestructionList(Destructor, void* addr);
118    void runDestructorFor(void* addr);
119    Page* newPage(size_t pageSize);
120    bool fitsInCurrentPage(size_t size);
121    void ensureNext(size_t size);
122    void* start(Page *p);
123    void* end(Page* p);
124
125    size_t mPageSize;
126    size_t mMaxAllocSize;
127    void* mNext;
128    Page* mCurrentPage;
129    Page* mPages;
130    DestructorNode* mDtorList = nullptr;
131
132    // Memory usage tracking
133    size_t mTotalAllocated;
134    size_t mWastedSpace;
135    size_t mPageCount;
136    size_t mDedicatedPageCount;
137};
138
139template <class T>
140class LinearStdAllocator {
141public:
142    typedef T value_type; // needed to implement std::allocator
143    typedef T* pointer; // needed to implement std::allocator
144
145    LinearStdAllocator(LinearAllocator& allocator)
146            : linearAllocator(allocator) {}
147    LinearStdAllocator(const LinearStdAllocator& other)
148            : linearAllocator(other.linearAllocator) {}
149    ~LinearStdAllocator() {}
150
151    // rebind marks that allocators can be rebound to different types
152    template <class U>
153    struct rebind {
154        typedef LinearStdAllocator<U> other;
155    };
156    // enable allocators to be constructed from other templated types
157    template <class U>
158    LinearStdAllocator(const LinearStdAllocator<U>& other)
159            : linearAllocator(other.linearAllocator) {}
160
161    T* allocate(size_t num, const void* = 0) {
162        return (T*)(linearAllocator.alloc(num * sizeof(T)));
163    }
164
165    void deallocate(pointer p, size_t num) {
166        // attempt to rewind, but no guarantees
167        linearAllocator.rewindIfLastAlloc(p, num * sizeof(T));
168    }
169
170    // public so template copy constructor can access
171    LinearAllocator& linearAllocator;
172};
173
174// return that all specializations of LinearStdAllocator are interchangeable
175template <class T1, class T2>
176bool operator== (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return true; }
177template <class T1, class T2>
178bool operator!= (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return false; }
179
180template <class T>
181class LsaVector : public std::vector<T, LinearStdAllocator<T>> {
182public:
183    LsaVector(const LinearStdAllocator<T>& allocator)
184            : std::vector<T, LinearStdAllocator<T>>(allocator) {}
185};
186
187}; // namespace uirenderer
188}; // namespace android
189
190void* operator new(std::size_t size, android::uirenderer::LinearAllocator& la);
191
192#endif // ANDROID_LINEARALLOCATOR_H
193