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>
60 static size_t s_totalAllocations = 0;
61 static nsecs_t s_nextLog = 0;
62 static android::Mutex s_mutex;
63
_logUsageLocked()64 static 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
_addAllocation(int count)72 static 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
84 namespace android {
85 namespace uirenderer {
86
87 class LinearAllocator::Page {
88 public:
next()89 Page* next() { return mNextPage; }
setNext(Page * next)90 void setNext(Page* next) { mNextPage = next; }
91
Page()92 Page()
93 : mNextPage(0)
94 {}
95
operator new(size_t,void * buf)96 void* operator new(size_t /*size*/, void* buf) { return buf; }
97
start()98 void* start() {
99 return (void*) (((size_t)this) + sizeof(Page));
100 }
101
end(int pageSize)102 void* end(int pageSize) {
103 return (void*) (((size_t)start()) + pageSize);
104 }
105
106 private:
Page(const Page &)107 Page(const Page& /*other*/) {}
108 Page* mNextPage;
109 };
110
LinearAllocator()111 LinearAllocator::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
~LinearAllocator(void)122 LinearAllocator::~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
start(Page * p)138 void* LinearAllocator::start(Page* p) {
139 return ALIGN_PTR((size_t)p + sizeof(Page));
140 }
141
end(Page * p)142 void* LinearAllocator::end(Page* p) {
143 return ((char*)p) + mPageSize;
144 }
145
fitsInCurrentPage(size_t size)146 bool LinearAllocator::fitsInCurrentPage(size_t size) {
147 return mNext && ((char*)mNext + size) <= end(mCurrentPage);
148 }
149
ensureNext(size_t size)150 void 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
allocImpl(size_t size)170 void* 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
addToDestructionList(Destructor dtor,void * addr)190 void 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
runDestructorFor(void * addr)202 void 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
rewindIfLastAlloc(void * ptr,size_t allocSize)221 void 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
newPage(size_t pageSize)235 LinearAllocator::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
toSize(size_t value,float & result)244 static 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
dumpMemoryStats(const char * prefix)257 void 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