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>
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
84 namespace android {
85
86 class LinearAllocator::Page {
87 public:
next()88 Page* next() { return mNextPage; }
setNext(Page * next)89 void setNext(Page* next) { mNextPage = next; }
90
Page()91 Page()
92 : mNextPage(0)
93 {}
94
operator new(size_t,void * buf)95 void* operator new(size_t /*size*/, void* buf) { return buf; }
96
start()97 void* start() {
98 return (void*) (((size_t)this) + sizeof(Page));
99 }
100
end(int pageSize)101 void* end(int pageSize) {
102 return (void*) (((size_t)start()) + pageSize);
103 }
104
105 private:
Page(const Page &)106 Page(const Page& /*other*/) {}
107 Page* mNextPage;
108 };
109
LinearAllocator()110 LinearAllocator::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
~LinearAllocator(void)121 LinearAllocator::~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
start(Page * p)132 void* LinearAllocator::start(Page* p) {
133 return ALIGN_PTR(((size_t*)p) + sizeof(Page));
134 }
135
end(Page * p)136 void* LinearAllocator::end(Page* p) {
137 return ((char*)p) + mPageSize;
138 }
139
fitsInCurrentPage(size_t size)140 bool LinearAllocator::fitsInCurrentPage(size_t size) {
141 return mNext && ((char*)mNext + size) <= end(mCurrentPage);
142 }
143
ensureNext(size_t size)144 void 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
alloc(size_t size)163 void* 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
rewindIfLastAlloc(void * ptr,size_t allocSize)183 void 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
newPage(size_t pageSize)194 LinearAllocator::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
toSize(size_t value,float & result)203 static 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
dumpMemoryStats(const char * prefix)216 void 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