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_TAG "LinearAllocator"
27#define LOG_NDEBUG 1
28
29#include <stdlib.h>
30#include <utils/LinearAllocator.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
84namespace android {
85
86class LinearAllocator::Page {
87public:
88    Page* next() { return mNextPage; }
89    void setNext(Page* next) { mNextPage = next; }
90
91    Page()
92        : mNextPage(0)
93    {}
94
95    void* operator new(size_t /*size*/, void* buf) { return buf; }
96
97    void* start() {
98        return (void*) (((size_t)this) + sizeof(Page));
99    }
100
101    void* end(int pageSize) {
102        return (void*) (((size_t)start()) + pageSize);
103    }
104
105private:
106    Page(const Page& /*other*/) {}
107    Page* mNextPage;
108};
109
110LinearAllocator::LinearAllocator()
111    : mPageSize(INITIAL_PAGE_SIZE)
112    , mMaxAllocSize(MAX_WASTE_SIZE)
113    , mNext(0)
114    , mCurrentPage(0)
115    , mPages(0)
116    , mTotalAllocated(0)
117    , mWastedSpace(0)
118    , mPageCount(0)
119    , mDedicatedPageCount(0) {}
120
121LinearAllocator::~LinearAllocator(void) {
122    Page* p = mPages;
123    while (p) {
124        Page* next = p->next();
125        p->~Page();
126        free(p);
127        RM_ALLOCATION(mPageSize);
128        p = next;
129    }
130}
131
132void* LinearAllocator::start(Page* p) {
133    return ALIGN_PTR(((size_t*)p) + sizeof(Page));
134}
135
136void* LinearAllocator::end(Page* p) {
137    return ((char*)p) + mPageSize;
138}
139
140bool LinearAllocator::fitsInCurrentPage(size_t size) {
141    return mNext && ((char*)mNext + size) <= end(mCurrentPage);
142}
143
144void LinearAllocator::ensureNext(size_t size) {
145    if (fitsInCurrentPage(size)) return;
146
147    if (mCurrentPage && mPageSize < MAX_PAGE_SIZE) {
148        mPageSize = min(MAX_PAGE_SIZE, mPageSize * 2);
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::alloc(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)
173            mCurrentPage = mPages;
174        return start(page);
175    }
176    ensureNext(size);
177    void* ptr = mNext;
178    mNext = ((char*)mNext) + size;
179    mWastedSpace -= size;
180    return ptr;
181}
182
183void LinearAllocator::rewindIfLastAlloc(void* ptr, size_t allocSize) {
184    // Don't bother rewinding across pages
185    allocSize = ALIGN(allocSize);
186    if (ptr >= start(mCurrentPage) && ptr < end(mCurrentPage)
187            && ptr == ((char*)mNext - allocSize)) {
188        mTotalAllocated -= allocSize;
189        mWastedSpace += allocSize;
190        mNext = ptr;
191    }
192}
193
194LinearAllocator::Page* LinearAllocator::newPage(size_t pageSize) {
195    pageSize = ALIGN(pageSize + sizeof(LinearAllocator::Page));
196    ADD_ALLOCATION(pageSize);
197    mTotalAllocated += pageSize;
198    mPageCount++;
199    void* buf = malloc(pageSize);
200    return new (buf) Page();
201}
202
203static const char* toSize(size_t value, float& result) {
204    if (value < 2000) {
205        result = value;
206        return "B";
207    }
208    if (value < 2000000) {
209        result = value / 1024.0f;
210        return "KB";
211    }
212    result = value / 1048576.0f;
213    return "MB";
214}
215
216void LinearAllocator::dumpMemoryStats(const char* prefix) {
217    float prettySize;
218    const char* prettySuffix;
219    prettySuffix = toSize(mTotalAllocated, prettySize);
220    ALOGD("%sTotal allocated: %.2f%s", prefix, prettySize, prettySuffix);
221    prettySuffix = toSize(mWastedSpace, prettySize);
222    ALOGD("%sWasted space: %.2f%s (%.1f%%)", prefix, prettySize, prettySuffix,
223          (float) mWastedSpace / (float) mTotalAllocated * 100.0f);
224    ALOGD("%sPages %zu (dedicated %zu)", prefix, mPageCount, mDedicatedPageCount);
225}
226
227}; // namespace android
228