LinearAllocator.cpp revision b5bc454870c8b7df88a633b18c4c6499361c3a08 
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)4096) // 4kb
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_SIZE ((size_t)1024)
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(size)
56#define RM_ALLOCATION(size)
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 memory usage: %zu kb", s_totalAllocations / 1024);
69    }
70}
71
72static void _addAllocation(size_t size) {
73    android::AutoMutex lock(s_mutex);
74    s_totalAllocations += size;
75    _logUsageLocked();
76}
77
78#define ADD_ALLOCATION(size) _addAllocation(size);
79#define RM_ALLOCATION(size) _addAllocation(-size);
80#endif
81
82#define min(x,y) (((x) < (y)) ? (x) : (y))
83
84void* operator new(std::size_t size, android::uirenderer::LinearAllocator& la) {
85    return la.alloc(size);
86}
87
88namespace android {
89namespace uirenderer {
90
91class LinearAllocator::Page {
92public:
93    Page* next() { return mNextPage; }
94    void setNext(Page* next) { mNextPage = next; }
95
96    Page()
97        : mNextPage(0)
98    {}
99
100    void* operator new(size_t /*size*/, void* buf) { return buf; }
101
102    void* start() {
103        return (void*) (((size_t)this) + sizeof(Page));
104    }
105
106    void* end(int pageSize) {
107        return (void*) (((size_t)start()) + pageSize);
108    }
109
110private:
111    Page(const Page& /*other*/) {}
112    Page* mNextPage;
113};
114
115LinearAllocator::LinearAllocator()
116    : mPageSize(INITIAL_PAGE_SIZE)
117    , mMaxAllocSize(MAX_WASTE_SIZE)
118    , mNext(0)
119    , mCurrentPage(0)
120    , mPages(0)
121    , mTotalAllocated(0)
122    , mWastedSpace(0)
123    , mPageCount(0)
124    , mDedicatedPageCount(0) {}
125
126LinearAllocator::~LinearAllocator(void) {
127    while (mDtorList) {
128        auto node = mDtorList;
129        mDtorList = node->next;
130        node->dtor(node->addr);
131    }
132    Page* p = mPages;
133    while (p) {
134        Page* next = p->next();
135        p->~Page();
136        free(p);
137        RM_ALLOCATION(mPageSize);
138        p = next;
139    }
140}
141
142void* LinearAllocator::start(Page* p) {
143    return ALIGN_PTR(((size_t*)p) + sizeof(Page));
144}
145
146void* LinearAllocator::end(Page* p) {
147    return ((char*)p) + mPageSize;
148}
149
150bool LinearAllocator::fitsInCurrentPage(size_t size) {
151    return mNext && ((char*)mNext + size) <= end(mCurrentPage);
152}
153
154void LinearAllocator::ensureNext(size_t size) {
155    if (fitsInCurrentPage(size)) return;
156
157    if (mCurrentPage && mPageSize < MAX_PAGE_SIZE) {
158        mPageSize = min(MAX_PAGE_SIZE, mPageSize * 2);
159        mPageSize = ALIGN(mPageSize);
160    }
161    mWastedSpace += mPageSize;
162    Page* p = newPage(mPageSize);
163    if (mCurrentPage) {
164        mCurrentPage->setNext(p);
165    }
166    mCurrentPage = p;
167    if (!mPages) {
168        mPages = mCurrentPage;
169    }
170    mNext = start(mCurrentPage);
171}
172
173void* LinearAllocator::alloc(size_t size) {
174    size = ALIGN(size);
175    if (size > mMaxAllocSize && !fitsInCurrentPage(size)) {
176        ALOGV("Exceeded max size %zu > %zu", size, mMaxAllocSize);
177        // Allocation is too large, create a dedicated page for the allocation
178        Page* page = newPage(size);
179        mDedicatedPageCount++;
180        page->setNext(mPages);
181        mPages = page;
182        if (!mCurrentPage)
183            mCurrentPage = mPages;
184        return start(page);
185    }
186    ensureNext(size);
187    void* ptr = mNext;
188    mNext = ((char*)mNext) + size;
189    mWastedSpace -= size;
190    return ptr;
191}
192
193void LinearAllocator::addToDestructionList(Destructor dtor, void* addr) {
194    static_assert(std::is_standard_layout<DestructorNode>::value,
195                  "DestructorNode must have standard layout");
196    static_assert(std::is_trivially_destructible<DestructorNode>::value,
197                  "DestructorNode must be trivially destructable");
198    auto node = new (*this) DestructorNode();
199    node->dtor = dtor;
200    node->addr = addr;
201    node->next = mDtorList;
202    mDtorList = node;
203}
204
205void LinearAllocator::runDestructorFor(void* addr) {
206    auto node = mDtorList;
207    DestructorNode* previous = nullptr;
208    while (node) {
209        if (node->addr == addr) {
210            if (previous) {
211                previous->next = node->next;
212            } else {
213                mDtorList = node->next;
214            }
215            node->dtor(node->addr);
216            rewindIfLastAlloc(node, sizeof(DestructorNode));
217            break;
218        }
219        previous = node;
220        node = node->next;
221    }
222}
223
224void LinearAllocator::rewindIfLastAlloc(void* ptr, size_t allocSize) {
225    // First run the destructor as running the destructor will
226    // also rewind for the DestructorNode allocation which will
227    // have been allocated after this void* if it has a destructor
228    runDestructorFor(ptr);
229    // Don't bother rewinding across pages
230    allocSize = ALIGN(allocSize);
231    if (ptr >= start(mCurrentPage) && ptr < end(mCurrentPage)
232            && ptr == ((char*)mNext - allocSize)) {
233        mWastedSpace += allocSize;
234        mNext = ptr;
235    }
236}
237
238LinearAllocator::Page* LinearAllocator::newPage(size_t pageSize) {
239    pageSize = ALIGN(pageSize + sizeof(LinearAllocator::Page));
240    ADD_ALLOCATION(pageSize);
241    mTotalAllocated += pageSize;
242    mPageCount++;
243    void* buf = malloc(pageSize);
244    return new (buf) Page();
245}
246
247static const char* toSize(size_t value, float& result) {
248    if (value < 2000) {
249        result = value;
250        return "B";
251    }
252    if (value < 2000000) {
253        result = value / 1024.0f;
254        return "KB";
255    }
256    result = value / 1048576.0f;
257    return "MB";
258}
259
260void LinearAllocator::dumpMemoryStats(const char* prefix) {
261    float prettySize;
262    const char* prettySuffix;
263    prettySuffix = toSize(mTotalAllocated, prettySize);
264    ALOGD("%sTotal allocated: %.2f%s", prefix, prettySize, prettySuffix);
265    prettySuffix = toSize(mWastedSpace, prettySize);
266    ALOGD("%sWasted space: %.2f%s (%.1f%%)", prefix, prettySize, prettySuffix,
267          (float) mWastedSpace / (float) mTotalAllocated * 100.0f);
268    ALOGD("%sPages %zu (dedicated %zu)", prefix, mPageCount, mDedicatedPageCount);
269}
270
271}; // namespace uirenderer
272}; // namespace android
273