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>
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 memory usage: %zu kb", s_totalAllocations / 1024);
69 }
70 }
71
_addAllocation(size_t size)72 static 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
operator new(std::size_t size,android::uirenderer::LinearAllocator & la)84 void* operator new(std::size_t size, android::uirenderer::LinearAllocator& la) {
85 return la.alloc(size);
86 }
87
88 namespace android {
89 namespace uirenderer {
90
91 class LinearAllocator::Page {
92 public:
next()93 Page* next() { return mNextPage; }
setNext(Page * next)94 void setNext(Page* next) { mNextPage = next; }
95
Page()96 Page()
97 : mNextPage(0)
98 {}
99
operator new(size_t,void * buf)100 void* operator new(size_t /*size*/, void* buf) { return buf; }
101
start()102 void* start() {
103 return (void*) (((size_t)this) + sizeof(Page));
104 }
105
end(int pageSize)106 void* end(int pageSize) {
107 return (void*) (((size_t)start()) + pageSize);
108 }
109
110 private:
Page(const Page &)111 Page(const Page& /*other*/) {}
112 Page* mNextPage;
113 };
114
LinearAllocator()115 LinearAllocator::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
~LinearAllocator(void)126 LinearAllocator::~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
start(Page * p)142 void* LinearAllocator::start(Page* p) {
143 return ALIGN_PTR(((size_t*)p) + sizeof(Page));
144 }
145
end(Page * p)146 void* LinearAllocator::end(Page* p) {
147 return ((char*)p) + mPageSize;
148 }
149
fitsInCurrentPage(size_t size)150 bool LinearAllocator::fitsInCurrentPage(size_t size) {
151 return mNext && ((char*)mNext + size) <= end(mCurrentPage);
152 }
153
ensureNext(size_t size)154 void 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
alloc(size_t size)173 void* 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
addToDestructionList(Destructor dtor,void * addr)193 void 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
runDestructorFor(void * addr)205 void 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
rewindIfLastAlloc(void * ptr,size_t allocSize)224 void 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
newPage(size_t pageSize)238 LinearAllocator::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
toSize(size_t value,float & result)247 static 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
dumpMemoryStats(const char * prefix)260 void 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