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#define LOG_NDEBUG 1
27
28#include "utils/LinearAllocator.h"
29
30#include <stdlib.h>
31#include <utils/Log.h>
32
33// The ideal size of a page allocation (these need to be multiples of 8)
34#define INITIAL_PAGE_SIZE ((size_t)512)  // 512b
35#define MAX_PAGE_SIZE ((size_t)131072)   // 128kb
36
37// The maximum amount of wasted space we can have per page
38// Allocations exceeding this will have their own dedicated page
39// If this is too low, we will malloc too much
40// Too high, and we may waste too much space
41// Must be smaller than INITIAL_PAGE_SIZE
42#define MAX_WASTE_RATIO (0.5f)
43
44#if ALIGN_DOUBLE
45#define ALIGN_SZ (sizeof(double))
46#else
47#define ALIGN_SZ (sizeof(int))
48#endif
49
50#define ALIGN(x) (((x) + ALIGN_SZ - 1) & ~(ALIGN_SZ - 1))
51#define ALIGN_PTR(p) ((void*)(ALIGN((size_t)(p))))
52
53#if LOG_NDEBUG
54#define ADD_ALLOCATION()
55#define RM_ALLOCATION()
56#else
57#include <utils/Thread.h>
58#include <utils/Timers.h>
59static size_t s_totalAllocations = 0;
60static nsecs_t s_nextLog = 0;
61static android::Mutex s_mutex;
62
63static void _logUsageLocked() {
64    nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC);
65    if (now > s_nextLog) {
66        s_nextLog = now + milliseconds_to_nanoseconds(10);
67        ALOGV("Total pages allocated: %zu", s_totalAllocations);
68    }
69}
70
71static void _addAllocation(int count) {
72    android::AutoMutex lock(s_mutex);
73    s_totalAllocations += count;
74    _logUsageLocked();
75}
76
77#define ADD_ALLOCATION(size) _addAllocation(1);
78#define RM_ALLOCATION(size) _addAllocation(-1);
79#endif
80
81#define min(x, y) (((x) < (y)) ? (x) : (y))
82
83namespace android {
84namespace uirenderer {
85
86class LinearAllocator::Page {
87public:
88    Page* next() { return mNextPage; }
89    void setNext(Page* next) { mNextPage = next; }
90
91    Page() : mNextPage(0) {}
92
93    void* operator new(size_t /*size*/, void* buf) { return buf; }
94
95    void* start() { return (void*)(((size_t)this) + sizeof(Page)); }
96
97    void* end(int pageSize) { return (void*)(((size_t)start()) + pageSize); }
98
99private:
100    Page(const Page& /*other*/) {}
101    Page* mNextPage;
102};
103
104LinearAllocator::LinearAllocator()
105        : mPageSize(INITIAL_PAGE_SIZE)
106        , mMaxAllocSize(INITIAL_PAGE_SIZE * MAX_WASTE_RATIO)
107        , mNext(0)
108        , mCurrentPage(0)
109        , mPages(0)
110        , mTotalAllocated(0)
111        , mWastedSpace(0)
112        , mPageCount(0)
113        , mDedicatedPageCount(0) {}
114
115LinearAllocator::~LinearAllocator(void) {
116    while (mDtorList) {
117        auto node = mDtorList;
118        mDtorList = node->next;
119        node->dtor(node->addr);
120    }
121    Page* p = mPages;
122    while (p) {
123        Page* next = p->next();
124        p->~Page();
125        free(p);
126        RM_ALLOCATION();
127        p = next;
128    }
129}
130
131void* LinearAllocator::start(Page* p) {
132    return ALIGN_PTR((size_t)p + sizeof(Page));
133}
134
135void* LinearAllocator::end(Page* p) {
136    return ((char*)p) + mPageSize;
137}
138
139bool LinearAllocator::fitsInCurrentPage(size_t size) {
140    return mNext && ((char*)mNext + size) <= end(mCurrentPage);
141}
142
143void LinearAllocator::ensureNext(size_t size) {
144    if (fitsInCurrentPage(size)) return;
145
146    if (mCurrentPage && mPageSize < MAX_PAGE_SIZE) {
147        mPageSize = min(MAX_PAGE_SIZE, mPageSize * 2);
148        mMaxAllocSize = mPageSize * MAX_WASTE_RATIO;
149        mPageSize = ALIGN(mPageSize);
150    }
151    mWastedSpace += mPageSize;
152    Page* p = newPage(mPageSize);
153    if (mCurrentPage) {
154        mCurrentPage->setNext(p);
155    }
156    mCurrentPage = p;
157    if (!mPages) {
158        mPages = mCurrentPage;
159    }
160    mNext = start(mCurrentPage);
161}
162
163void* LinearAllocator::allocImpl(size_t size) {
164    size = ALIGN(size);
165    if (size > mMaxAllocSize && !fitsInCurrentPage(size)) {
166        ALOGV("Exceeded max size %zu > %zu", size, mMaxAllocSize);
167        // Allocation is too large, create a dedicated page for the allocation
168        Page* page = newPage(size);
169        mDedicatedPageCount++;
170        page->setNext(mPages);
171        mPages = page;
172        if (!mCurrentPage) mCurrentPage = mPages;
173        return start(page);
174    }
175    ensureNext(size);
176    void* ptr = mNext;
177    mNext = ((char*)mNext) + size;
178    mWastedSpace -= size;
179    return ptr;
180}
181
182void LinearAllocator::addToDestructionList(Destructor dtor, void* addr) {
183    static_assert(std::is_standard_layout<DestructorNode>::value,
184                  "DestructorNode must have standard layout");
185    static_assert(std::is_trivially_destructible<DestructorNode>::value,
186                  "DestructorNode must be trivially destructable");
187    auto node = new (allocImpl(sizeof(DestructorNode))) DestructorNode();
188    node->dtor = dtor;
189    node->addr = addr;
190    node->next = mDtorList;
191    mDtorList = node;
192}
193
194void LinearAllocator::runDestructorFor(void* addr) {
195    auto node = mDtorList;
196    DestructorNode* previous = nullptr;
197    while (node) {
198        if (node->addr == addr) {
199            if (previous) {
200                previous->next = node->next;
201            } else {
202                mDtorList = node->next;
203            }
204            node->dtor(node->addr);
205            rewindIfLastAlloc(node, sizeof(DestructorNode));
206            break;
207        }
208        previous = node;
209        node = node->next;
210    }
211}
212
213void LinearAllocator::rewindIfLastAlloc(void* ptr, size_t allocSize) {
214    // First run the destructor as running the destructor will
215    // also rewind for the DestructorNode allocation which will
216    // have been allocated after this void* if it has a destructor
217    runDestructorFor(ptr);
218    // Don't bother rewinding across pages
219    allocSize = ALIGN(allocSize);
220    if (ptr >= start(mCurrentPage) && ptr < end(mCurrentPage) &&
221        ptr == ((char*)mNext - allocSize)) {
222        mWastedSpace += allocSize;
223        mNext = ptr;
224    }
225}
226
227LinearAllocator::Page* LinearAllocator::newPage(size_t pageSize) {
228    pageSize = ALIGN(pageSize + sizeof(LinearAllocator::Page));
229    ADD_ALLOCATION();
230    mTotalAllocated += pageSize;
231    mPageCount++;
232    void* buf = malloc(pageSize);
233    return new (buf) Page();
234}
235
236static const char* toSize(size_t value, float& result) {
237    if (value < 2000) {
238        result = value;
239        return "B";
240    }
241    if (value < 2000000) {
242        result = value / 1024.0f;
243        return "KB";
244    }
245    result = value / 1048576.0f;
246    return "MB";
247}
248
249void LinearAllocator::dumpMemoryStats(const char* prefix) {
250    float prettySize;
251    const char* prettySuffix;
252    prettySuffix = toSize(mTotalAllocated, prettySize);
253    ALOGD("%sTotal allocated: %.2f%s", prefix, prettySize, prettySuffix);
254    prettySuffix = toSize(mWastedSpace, prettySize);
255    ALOGD("%sWasted space: %.2f%s (%.1f%%)", prefix, prettySize, prettySuffix,
256          (float)mWastedSpace / (float)mTotalAllocated * 100.0f);
257    ALOGD("%sPages %zu (dedicated %zu)", prefix, mPageCount, mDedicatedPageCount);
258}
259
260};  // namespace uirenderer
261};  // namespace android
262