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