Home | History | Annotate | Download | only in libgralloc 
      1 /*
      2  * Copyright (C) 2009 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include <cutils/log.h>
     18 
     19 #include "allocator.h"
     20 
     21 
     22 // align all the memory blocks on a cache-line boundary
     23 const int SimpleBestFitAllocator::kMemoryAlign = 32;
     24 
     25 SimpleBestFitAllocator::SimpleBestFitAllocator()
     26     : mHeapSize(0)
     27 {
     28 }
     29 
     30 SimpleBestFitAllocator::SimpleBestFitAllocator(size_t size)
     31     : mHeapSize(0)
     32 {
     33     setSize(size);
     34 }
     35 
     36 SimpleBestFitAllocator::~SimpleBestFitAllocator()
     37 {
     38     while(!mList.isEmpty()) {
     39         delete mList.remove(mList.head());
     40     }
     41 }
     42 
     43 ssize_t SimpleBestFitAllocator::setSize(size_t size)
     44 {
     45     Locker::Autolock _l(mLock);
     46     if (mHeapSize != 0) return -EINVAL;
     47     size_t pagesize = getpagesize();
     48     mHeapSize = ((size + pagesize-1) & ~(pagesize-1));
     49     chunk_t* node = new chunk_t(0, mHeapSize / kMemoryAlign);
     50     mList.insertHead(node);
     51     return size;
     52 }
     53 
     54 
     55 size_t SimpleBestFitAllocator::size() const
     56 {
     57     return mHeapSize;
     58 }
     59 
     60 ssize_t SimpleBestFitAllocator::allocate(size_t size, uint32_t flags)
     61 {
     62     Locker::Autolock _l(mLock);
     63     if (mHeapSize == 0) return -EINVAL;
     64     ssize_t offset = alloc(size, flags);
     65     return offset;
     66 }
     67 
     68 ssize_t SimpleBestFitAllocator::deallocate(size_t offset)
     69 {
     70     Locker::Autolock _l(mLock);
     71     if (mHeapSize == 0) return -EINVAL;
     72     chunk_t const * const freed = dealloc(offset);
     73     if (freed) {
     74         return 0;
     75     }
     76     return -ENOENT;
     77 }
     78 
     79 ssize_t SimpleBestFitAllocator::alloc(size_t size, uint32_t flags)
     80 {
     81     if (size == 0) {
     82         return 0;
     83     }
     84     size = (size + kMemoryAlign-1) / kMemoryAlign;
     85     chunk_t* free_chunk = 0;
     86     chunk_t* cur = mList.head();
     87 
     88     size_t pagesize = getpagesize();
     89     while (cur) {
     90         int extra = ( -cur->start & ((pagesize/kMemoryAlign)-1) ) ;
     91 
     92         // best fit
     93         if (cur->free && (cur->size >= (size+extra))) {
     94             if ((!free_chunk) || (cur->size < free_chunk->size)) {
     95                 free_chunk = cur;
     96             }
     97             if (cur->size == size) {
     98                 break;
     99             }
    100         }
    101         cur = cur->next;
    102     }
    103 
    104     if (free_chunk) {
    105         const size_t free_size = free_chunk->size;
    106         free_chunk->free = 0;
    107         free_chunk->size = size;
    108         if (free_size > size) {
    109             int extra = ( -free_chunk->start & ((pagesize/kMemoryAlign)-1) ) ;
    110             if (extra) {
    111                 chunk_t* split = new chunk_t(free_chunk->start, extra);
    112                 free_chunk->start += extra;
    113                 mList.insertBefore(free_chunk, split);
    114             }
    115 
    116             LOGE_IF(((free_chunk->start*kMemoryAlign)&(pagesize-1)),
    117                     "page is not aligned!!!");
    118 
    119             const ssize_t tail_free = free_size - (size+extra);
    120             if (tail_free > 0) {
    121                 chunk_t* split = new chunk_t(
    122                         free_chunk->start + free_chunk->size, tail_free);
    123                 mList.insertAfter(free_chunk, split);
    124             }
    125         }
    126         return (free_chunk->start)*kMemoryAlign;
    127     }
    128     return -ENOMEM;
    129 }
    130 
    131 SimpleBestFitAllocator::chunk_t* SimpleBestFitAllocator::dealloc(size_t start)
    132 {
    133     start = start / kMemoryAlign;
    134     chunk_t* cur = mList.head();
    135     while (cur) {
    136         if (cur->start == start) {
    137             LOG_FATAL_IF(cur->free,
    138                 "block at offset 0x%08lX of size 0x%08lX already freed",
    139                 cur->start*kMemoryAlign, cur->size*kMemoryAlign);
    140 
    141             // merge freed blocks together
    142             chunk_t* freed = cur;
    143             cur->free = 1;
    144             do {
    145                 chunk_t* const p = cur->prev;
    146                 chunk_t* const n = cur->next;
    147                 if (p && (p->free || !cur->size)) {
    148                     freed = p;
    149                     p->size += cur->size;
    150                     mList.remove(cur);
    151                     delete cur;
    152                 }
    153                 cur = n;
    154             } while (cur && cur->free);
    155 
    156             LOG_FATAL_IF(!freed->free,
    157                 "freed block at offset 0x%08lX of size 0x%08lX is not free!",
    158                 freed->start * kMemoryAlign, freed->size * kMemoryAlign);
    159 
    160             return freed;
    161         }
    162         cur = cur->next;
    163     }
    164     return 0;
    165 }
    166