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