1/* 2 * Copyright (C) 2007 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#define LOG_TAG "MemoryDealer" 18 19#include <binder/MemoryDealer.h> 20#include <binder/IPCThreadState.h> 21#include <binder/MemoryBase.h> 22 23#include <utils/Log.h> 24#include <utils/SortedVector.h> 25#include <utils/String8.h> 26#include <utils/threads.h> 27 28#include <stdint.h> 29#include <stdio.h> 30#include <stdlib.h> 31#include <fcntl.h> 32#include <unistd.h> 33#include <errno.h> 34#include <string.h> 35 36#include <sys/stat.h> 37#include <sys/types.h> 38#include <sys/mman.h> 39#include <sys/file.h> 40 41namespace android { 42// ---------------------------------------------------------------------------- 43 44/* 45 * A simple templatized doubly linked-list implementation 46 */ 47 48template <typename NODE> 49class LinkedList 50{ 51 NODE* mFirst; 52 NODE* mLast; 53 54public: 55 LinkedList() : mFirst(0), mLast(0) { } 56 bool isEmpty() const { return mFirst == 0; } 57 NODE const* head() const { return mFirst; } 58 NODE* head() { return mFirst; } 59 NODE const* tail() const { return mLast; } 60 NODE* tail() { return mLast; } 61 62 void insertAfter(NODE* node, NODE* newNode) { 63 newNode->prev = node; 64 newNode->next = node->next; 65 if (node->next == 0) mLast = newNode; 66 else node->next->prev = newNode; 67 node->next = newNode; 68 } 69 70 void insertBefore(NODE* node, NODE* newNode) { 71 newNode->prev = node->prev; 72 newNode->next = node; 73 if (node->prev == 0) mFirst = newNode; 74 else node->prev->next = newNode; 75 node->prev = newNode; 76 } 77 78 void insertHead(NODE* newNode) { 79 if (mFirst == 0) { 80 mFirst = mLast = newNode; 81 newNode->prev = newNode->next = 0; 82 } else { 83 newNode->prev = 0; 84 newNode->next = mFirst; 85 mFirst->prev = newNode; 86 mFirst = newNode; 87 } 88 } 89 90 void insertTail(NODE* newNode) { 91 if (mLast == 0) { 92 insertHead(newNode); 93 } else { 94 newNode->prev = mLast; 95 newNode->next = 0; 96 mLast->next = newNode; 97 mLast = newNode; 98 } 99 } 100 101 NODE* remove(NODE* node) { 102 if (node->prev == 0) mFirst = node->next; 103 else node->prev->next = node->next; 104 if (node->next == 0) mLast = node->prev; 105 else node->next->prev = node->prev; 106 return node; 107 } 108}; 109 110// ---------------------------------------------------------------------------- 111 112class Allocation : public MemoryBase { 113public: 114 Allocation(const sp<MemoryDealer>& dealer, 115 const sp<IMemoryHeap>& heap, ssize_t offset, size_t size); 116 virtual ~Allocation(); 117private: 118 sp<MemoryDealer> mDealer; 119}; 120 121// ---------------------------------------------------------------------------- 122 123class SimpleBestFitAllocator 124{ 125 enum { 126 PAGE_ALIGNED = 0x00000001 127 }; 128public: 129 SimpleBestFitAllocator(size_t size); 130 ~SimpleBestFitAllocator(); 131 132 size_t allocate(size_t size, uint32_t flags = 0); 133 status_t deallocate(size_t offset); 134 size_t size() const; 135 void dump(const char* what) const; 136 void dump(String8& res, const char* what) const; 137 138private: 139 140 struct chunk_t { 141 chunk_t(size_t start, size_t size) 142 : start(start), size(size), free(1), prev(0), next(0) { 143 } 144 size_t start; 145 size_t size : 28; 146 int free : 4; 147 mutable chunk_t* prev; 148 mutable chunk_t* next; 149 }; 150 151 ssize_t alloc(size_t size, uint32_t flags); 152 chunk_t* dealloc(size_t start); 153 void dump_l(const char* what) const; 154 void dump_l(String8& res, const char* what) const; 155 156 static const int kMemoryAlign; 157 mutable Mutex mLock; 158 LinkedList<chunk_t> mList; 159 size_t mHeapSize; 160}; 161 162// ---------------------------------------------------------------------------- 163 164Allocation::Allocation( 165 const sp<MemoryDealer>& dealer, 166 const sp<IMemoryHeap>& heap, ssize_t offset, size_t size) 167 : MemoryBase(heap, offset, size), mDealer(dealer) 168{ 169#ifndef NDEBUG 170 void* const start_ptr = (void*)(intptr_t(heap->base()) + offset); 171 memset(start_ptr, 0xda, size); 172#endif 173} 174 175Allocation::~Allocation() 176{ 177 size_t freedOffset = getOffset(); 178 size_t freedSize = getSize(); 179 if (freedSize) { 180 /* NOTE: it's VERY important to not free allocations of size 0 because 181 * they're special as they don't have any record in the allocator 182 * and could alias some real allocation (their offset is zero). */ 183 184 // keep the size to unmap in excess 185 size_t pagesize = getpagesize(); 186 size_t start = freedOffset; 187 size_t end = start + freedSize; 188 start &= ~(pagesize-1); 189 end = (end + pagesize-1) & ~(pagesize-1); 190 191 // give back to the kernel the pages we don't need 192 size_t free_start = freedOffset; 193 size_t free_end = free_start + freedSize; 194 if (start < free_start) 195 start = free_start; 196 if (end > free_end) 197 end = free_end; 198 start = (start + pagesize-1) & ~(pagesize-1); 199 end &= ~(pagesize-1); 200 201 if (start < end) { 202 void* const start_ptr = (void*)(intptr_t(getHeap()->base()) + start); 203 size_t size = end-start; 204 205#ifndef NDEBUG 206 memset(start_ptr, 0xdf, size); 207#endif 208 209 // MADV_REMOVE is not defined on Dapper based Goobuntu 210#ifdef MADV_REMOVE 211 if (size) { 212 int err = madvise(start_ptr, size, MADV_REMOVE); 213 ALOGW_IF(err, "madvise(%p, %zu, MADV_REMOVE) returned %s", 214 start_ptr, size, err<0 ? strerror(errno) : "Ok"); 215 } 216#endif 217 } 218 219 // This should be done after madvise(MADV_REMOVE), otherwise madvise() 220 // might kick out the memory region that's allocated and/or written 221 // right after the deallocation. 222 mDealer->deallocate(freedOffset); 223 } 224} 225 226// ---------------------------------------------------------------------------- 227 228MemoryDealer::MemoryDealer(size_t size, const char* name, uint32_t flags) 229 : mHeap(new MemoryHeapBase(size, flags, name)), 230 mAllocator(new SimpleBestFitAllocator(size)) 231{ 232} 233 234MemoryDealer::~MemoryDealer() 235{ 236 delete mAllocator; 237} 238 239sp<IMemory> MemoryDealer::allocate(size_t size) 240{ 241 sp<IMemory> memory; 242 const ssize_t offset = allocator()->allocate(size); 243 if (offset >= 0) { 244 memory = new Allocation(this, heap(), offset, size); 245 } 246 return memory; 247} 248 249void MemoryDealer::deallocate(size_t offset) 250{ 251 allocator()->deallocate(offset); 252} 253 254void MemoryDealer::dump(const char* what) const 255{ 256 allocator()->dump(what); 257} 258 259const sp<IMemoryHeap>& MemoryDealer::heap() const { 260 return mHeap; 261} 262 263SimpleBestFitAllocator* MemoryDealer::allocator() const { 264 return mAllocator; 265} 266 267// ---------------------------------------------------------------------------- 268 269// align all the memory blocks on a cache-line boundary 270const int SimpleBestFitAllocator::kMemoryAlign = 32; 271 272SimpleBestFitAllocator::SimpleBestFitAllocator(size_t size) 273{ 274 size_t pagesize = getpagesize(); 275 mHeapSize = ((size + pagesize-1) & ~(pagesize-1)); 276 277 chunk_t* node = new chunk_t(0, mHeapSize / kMemoryAlign); 278 mList.insertHead(node); 279} 280 281SimpleBestFitAllocator::~SimpleBestFitAllocator() 282{ 283 while(!mList.isEmpty()) { 284 delete mList.remove(mList.head()); 285 } 286} 287 288size_t SimpleBestFitAllocator::size() const 289{ 290 return mHeapSize; 291} 292 293size_t SimpleBestFitAllocator::allocate(size_t size, uint32_t flags) 294{ 295 Mutex::Autolock _l(mLock); 296 ssize_t offset = alloc(size, flags); 297 return offset; 298} 299 300status_t SimpleBestFitAllocator::deallocate(size_t offset) 301{ 302 Mutex::Autolock _l(mLock); 303 chunk_t const * const freed = dealloc(offset); 304 if (freed) { 305 return NO_ERROR; 306 } 307 return NAME_NOT_FOUND; 308} 309 310ssize_t SimpleBestFitAllocator::alloc(size_t size, uint32_t flags) 311{ 312 if (size == 0) { 313 return 0; 314 } 315 size = (size + kMemoryAlign-1) / kMemoryAlign; 316 chunk_t* free_chunk = 0; 317 chunk_t* cur = mList.head(); 318 319 size_t pagesize = getpagesize(); 320 while (cur) { 321 int extra = 0; 322 if (flags & PAGE_ALIGNED) 323 extra = ( -cur->start & ((pagesize/kMemoryAlign)-1) ) ; 324 325 // best fit 326 if (cur->free && (cur->size >= (size+extra))) { 327 if ((!free_chunk) || (cur->size < free_chunk->size)) { 328 free_chunk = cur; 329 } 330 if (cur->size == size) { 331 break; 332 } 333 } 334 cur = cur->next; 335 } 336 337 if (free_chunk) { 338 const size_t free_size = free_chunk->size; 339 free_chunk->free = 0; 340 free_chunk->size = size; 341 if (free_size > size) { 342 int extra = 0; 343 if (flags & PAGE_ALIGNED) 344 extra = ( -free_chunk->start & ((pagesize/kMemoryAlign)-1) ) ; 345 if (extra) { 346 chunk_t* split = new chunk_t(free_chunk->start, extra); 347 free_chunk->start += extra; 348 mList.insertBefore(free_chunk, split); 349 } 350 351 ALOGE_IF((flags&PAGE_ALIGNED) && 352 ((free_chunk->start*kMemoryAlign)&(pagesize-1)), 353 "PAGE_ALIGNED requested, but page is not aligned!!!"); 354 355 const ssize_t tail_free = free_size - (size+extra); 356 if (tail_free > 0) { 357 chunk_t* split = new chunk_t( 358 free_chunk->start + free_chunk->size, tail_free); 359 mList.insertAfter(free_chunk, split); 360 } 361 } 362 return (free_chunk->start)*kMemoryAlign; 363 } 364 return NO_MEMORY; 365} 366 367SimpleBestFitAllocator::chunk_t* SimpleBestFitAllocator::dealloc(size_t start) 368{ 369 start = start / kMemoryAlign; 370 chunk_t* cur = mList.head(); 371 while (cur) { 372 if (cur->start == start) { 373 LOG_FATAL_IF(cur->free, 374 "block at offset 0x%08lX of size 0x%08lX already freed", 375 cur->start*kMemoryAlign, cur->size*kMemoryAlign); 376 377 // merge freed blocks together 378 chunk_t* freed = cur; 379 cur->free = 1; 380 do { 381 chunk_t* const p = cur->prev; 382 chunk_t* const n = cur->next; 383 if (p && (p->free || !cur->size)) { 384 freed = p; 385 p->size += cur->size; 386 mList.remove(cur); 387 delete cur; 388 } 389 cur = n; 390 } while (cur && cur->free); 391 392 #ifndef NDEBUG 393 if (!freed->free) { 394 dump_l("dealloc (!freed->free)"); 395 } 396 #endif 397 LOG_FATAL_IF(!freed->free, 398 "freed block at offset 0x%08lX of size 0x%08lX is not free!", 399 freed->start * kMemoryAlign, freed->size * kMemoryAlign); 400 401 return freed; 402 } 403 cur = cur->next; 404 } 405 return 0; 406} 407 408void SimpleBestFitAllocator::dump(const char* what) const 409{ 410 Mutex::Autolock _l(mLock); 411 dump_l(what); 412} 413 414void SimpleBestFitAllocator::dump_l(const char* what) const 415{ 416 String8 result; 417 dump_l(result, what); 418 ALOGD("%s", result.string()); 419} 420 421void SimpleBestFitAllocator::dump(String8& result, 422 const char* what) const 423{ 424 Mutex::Autolock _l(mLock); 425 dump_l(result, what); 426} 427 428void SimpleBestFitAllocator::dump_l(String8& result, 429 const char* what) const 430{ 431 size_t size = 0; 432 int32_t i = 0; 433 chunk_t const* cur = mList.head(); 434 435 const size_t SIZE = 256; 436 char buffer[SIZE]; 437 snprintf(buffer, SIZE, " %s (%p, size=%u)\n", 438 what, this, (unsigned int)mHeapSize); 439 440 result.append(buffer); 441 442 while (cur) { 443 const char* errs[] = {"", "| link bogus NP", 444 "| link bogus PN", "| link bogus NP+PN" }; 445 int np = ((cur->next) && cur->next->prev != cur) ? 1 : 0; 446 int pn = ((cur->prev) && cur->prev->next != cur) ? 2 : 0; 447 448 snprintf(buffer, SIZE, " %3u: %p | 0x%08X | 0x%08X | %s %s\n", 449 i, cur, int(cur->start*kMemoryAlign), 450 int(cur->size*kMemoryAlign), 451 int(cur->free) ? "F" : "A", 452 errs[np|pn]); 453 454 result.append(buffer); 455 456 if (!cur->free) 457 size += cur->size*kMemoryAlign; 458 459 i++; 460 cur = cur->next; 461 } 462 snprintf(buffer, SIZE, 463 " size allocated: %u (%u KB)\n", int(size), int(size/1024)); 464 result.append(buffer); 465} 466 467 468}; // namespace android 469