LinearAllocator.h revision 81a1d2a15927b06b84359f839ab03ac8a20970bd 
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
32namespace android {
33namespace uirenderer {
34
35/**
36 * A memory manager that internally allocates multi-kbyte buffers for placing objects in. It avoids
37 * the overhead of malloc when many objects are allocated. It is most useful when creating many
38 * small objects with a similar lifetime, and doesn't add significant overhead for large
39 * allocations.
40 */
41class LinearAllocator {
42public:
43    LinearAllocator();
44    ~LinearAllocator();
45
46    /**
47     * Reserves and returns a region of memory of at least size 'size', aligning as needed.
48     * Typically this is used in an object's overridden new() method or as a replacement for malloc.
49     *
50     * The lifetime of the returned buffers is tied to that of the LinearAllocator. If calling
51     * delete() on an object stored in a buffer is needed, it should be overridden to use
52     * rewindIfLastAlloc()
53     */
54    void* alloc(size_t size);
55
56    /**
57     * Allocates an instance of the template type with the default constructor
58     * and adds it to the automatic destruction list.
59     */
60    template<class T>
61    T* alloc() {
62        T* ret = new (*this) T;
63        autoDestroy(ret);
64        return ret;
65    }
66
67    /**
68     * Adds the pointer to the tracking list to have its destructor called
69     * when the LinearAllocator is destroyed.
70     */
71    template<class T>
72    void autoDestroy(T* addr) {
73        if (!std::is_trivially_destructible<T>::value) {
74            auto dtor = [](void* addr) { ((T*)addr)->~T(); };
75            addToDestructionList(dtor, addr);
76        }
77    }
78
79    /**
80     * Attempt to deallocate the given buffer, with the LinearAllocator attempting to rewind its
81     * state if possible.
82     */
83    void rewindIfLastAlloc(void* ptr, size_t allocSize);
84
85    /**
86     * Same as rewindIfLastAlloc(void*, size_t)
87     */
88    template<class T>
89    void rewindIfLastAlloc(T* ptr) {
90        rewindIfLastAlloc((void*)ptr, sizeof(T));
91    }
92
93    /**
94     * Dump memory usage statistics to the log (allocated and wasted space)
95     */
96    void dumpMemoryStats(const char* prefix = "");
97
98    /**
99     * The number of bytes used for buffers allocated in the LinearAllocator (does not count space
100     * wasted)
101     */
102    size_t usedSize() const { return mTotalAllocated - mWastedSpace; }
103
104private:
105    LinearAllocator(const LinearAllocator& other);
106
107    class Page;
108    typedef void (*Destructor)(void* addr);
109    struct DestructorNode {
110        Destructor dtor;
111        void* addr;
112        DestructorNode* next = nullptr;
113    };
114
115    void addToDestructionList(Destructor, void* addr);
116    void runDestructorFor(void* addr);
117    Page* newPage(size_t pageSize);
118    bool fitsInCurrentPage(size_t size);
119    void ensureNext(size_t size);
120    void* start(Page *p);
121    void* end(Page* p);
122
123    size_t mPageSize;
124    size_t mMaxAllocSize;
125    void* mNext;
126    Page* mCurrentPage;
127    Page* mPages;
128    DestructorNode* mDtorList = nullptr;
129
130    // Memory usage tracking
131    size_t mTotalAllocated;
132    size_t mWastedSpace;
133    size_t mPageCount;
134    size_t mDedicatedPageCount;
135};
136
137template <class T>
138class LinearStdAllocator {
139public:
140    typedef T value_type; // needed to implement std::allocator
141    typedef T* pointer; // needed to implement std::allocator
142
143    LinearStdAllocator(LinearAllocator& allocator)
144            : linearAllocator(allocator) {}
145    LinearStdAllocator(const LinearStdAllocator& other)
146            : linearAllocator(other.linearAllocator) {}
147    ~LinearStdAllocator() {}
148
149    // rebind marks that allocators can be rebound to different types
150    template <class U>
151    struct rebind {
152        typedef LinearStdAllocator<U> other;
153    };
154    // enable allocators to be constructed from other templated types
155    template <class U>
156    LinearStdAllocator(const LinearStdAllocator<U>& other)
157            : linearAllocator(other.linearAllocator) {}
158
159    T* allocate(size_t num, const void* = 0) {
160        return (T*)(linearAllocator.alloc(num * sizeof(T)));
161    }
162
163    void deallocate(pointer p, size_t num) {
164        // attempt to rewind, but no guarantees
165        linearAllocator.rewindIfLastAlloc(p, num * sizeof(T));
166    }
167
168    // public so template copy constructor can access
169    LinearAllocator& linearAllocator;
170};
171
172// return that all specializations of LinearStdAllocator are interchangeable
173template <class T1, class T2>
174bool operator== (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return true; }
175template <class T1, class T2>
176bool operator!= (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return false; }
177
178}; // namespace uirenderer
179}; // namespace android
180
181void* operator new(std::size_t size, android::uirenderer::LinearAllocator& la);
182
183#endif // ANDROID_LINEARALLOCATOR_H
184