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     * 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
119private:
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
154template <class T>
155class LinearStdAllocator {
156public:
157    typedef T value_type; // needed to implement std::allocator
158    typedef T* pointer; // needed to implement std::allocator
159
160    explicit 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)  // NOLINT(implicit)
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
190template <class T1, class T2>
191bool operator== (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return true; }
192template <class T1, class T2>
193bool operator!= (const LinearStdAllocator<T1>&, const LinearStdAllocator<T2>&) { return false; }
194
195template <class T>
196class LsaVector : public std::vector<T, LinearStdAllocator<T>> {
197public:
198    explicit 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