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