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 ALOGE_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