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 // 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>
     59 static size_t s_totalAllocations = 0;
     60 static nsecs_t s_nextLog = 0;
     61 static android::Mutex s_mutex;
     62 
     63 static 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 
     71 static 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 
     83 namespace android {
     84 namespace uirenderer {
     85 
     86 class LinearAllocator::Page {
     87 public:
     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 
     99 private:
    100     Page(const Page& /*other*/) {}
    101     Page* mNextPage;
    102 };
    103 
    104 LinearAllocator::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 
    115 LinearAllocator::~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 
    131 void* LinearAllocator::start(Page* p) {
    132     return ALIGN_PTR((size_t)p + sizeof(Page));
    133 }
    134 
    135 void* LinearAllocator::end(Page* p) {
    136     return ((char*)p) + mPageSize;
    137 }
    138 
    139 bool LinearAllocator::fitsInCurrentPage(size_t size) {
    140     return mNext && ((char*)mNext + size) <= end(mCurrentPage);
    141 }
    142 
    143 void 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 
    163 void* 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 
    182 void 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 
    194 void 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 
    213 void 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 
    227 LinearAllocator::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 
    236 static 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 
    249 void 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