Home | History | Annotate | Download | only in utils 
      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 
     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 
     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:
     89     Page* next() { return mNextPage; }
     90     void setNext(Page* next) { mNextPage = next; }
     91 
     92     Page()
     93         : mNextPage(0)
     94     {}
     95 
     96     void* operator new(size_t /*size*/, void* buf) { return buf; }
     97 
     98     void* start() {
     99         return (void*) (((size_t)this) + sizeof(Page));
    100     }
    101 
    102     void* end(int pageSize) {
    103         return (void*) (((size_t)start()) + pageSize);
    104     }
    105 
    106 private:
    107     Page(const Page& /*other*/) {}
    108     Page* mNextPage;
    109 };
    110 
    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 
    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 
    138 void* LinearAllocator::start(Page* p) {
    139     return ALIGN_PTR((size_t)p + sizeof(Page));
    140 }
    141 
    142 void* LinearAllocator::end(Page* p) {
    143     return ((char*)p) + mPageSize;
    144 }
    145 
    146 bool LinearAllocator::fitsInCurrentPage(size_t size) {
    147     return mNext && ((char*)mNext + size) <= end(mCurrentPage);
    148 }
    149 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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