• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 maximum amount of wasted space we can have per page
35 // Allocations exceeding this will have their own dedicated page
36 // If this is too low, we will malloc too much
37 // Too high, and we may waste too much space
38 // Must be smaller than kInitialPageSize
39 #define MAX_WASTE_RATIO (0.5f)
40 
41 #if LOG_NDEBUG
42 #define ADD_ALLOCATION()
43 #define RM_ALLOCATION()
44 #else
45 #include <utils/Thread.h>
46 #include <utils/Timers.h>
47 static size_t s_totalAllocations = 0;
48 static nsecs_t s_nextLog = 0;
49 static android::Mutex s_mutex;
50 
_logUsageLocked()51 static void _logUsageLocked() {
52     nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC);
53     if (now > s_nextLog) {
54         s_nextLog = now + milliseconds_to_nanoseconds(10);
55         ALOGV("Total pages allocated: %zu", s_totalAllocations);
56     }
57 }
58 
_addAllocation(int count)59 static void _addAllocation(int count) {
60     android::AutoMutex lock(s_mutex);
61     s_totalAllocations += count;
62     _logUsageLocked();
63 }
64 
65 #define ADD_ALLOCATION(size) _addAllocation(1);
66 #define RM_ALLOCATION(size) _addAllocation(-1);
67 #endif
68 
69 #define min(x, y) (((x) < (y)) ? (x) : (y))
70 
71 namespace android {
72 namespace uirenderer {
73 
74 // The ideal size of a page allocation (these need to be multiples of 8)
75 static constexpr size_t kInitialPageSize = 512;  // 512b
76 static constexpr size_t kMaxPageSize = 131072;   // 128kb
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(kInitialPageSize)
98         , mMaxAllocSize(kInitialPageSize * 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 < kMaxPageSize) {
139         mPageSize = min(kMaxPageSize, 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