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