libs/binder/MemoryDealer.cpp

   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
  41 namespace android {
  42 // ----------------------------------------------------------------------------
  43
  44 /*
  45  * A simple templatized doubly linked-list implementation
  46  */
  47
  48 template <typename NODE>
  49 class LinkedList
  50 {
  51     NODE*  mFirst;
  52     NODE*  mLast;
  53
  54 public:
  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
 112 class Allocation : public MemoryBase {
 113 public:
 114     Allocation(const sp<MemoryDealer>& dealer,
 115             const sp<IMemoryHeap>& heap, ssize_t offset, size_t size);
 116     virtual ~Allocation();
 117 private:
 118     sp<MemoryDealer> mDealer;
 119 };
 120
 121 // ----------------------------------------------------------------------------
 122
 123 class SimpleBestFitAllocator
 124 {
 125     enum {
 126         PAGE_ALIGNED = 0x00000001
 127     };
 128 public:
 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
 138 private:
 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
 164 Allocation::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
 175 Allocation::~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, %u, 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
 228 MemoryDealer::MemoryDealer(size_t size, const char* name)
 229     : mHeap(new MemoryHeapBase(size, 0, name)),
 230     mAllocator(new SimpleBestFitAllocator(size))
 231 {
 232 }
 233
 234 MemoryDealer::~MemoryDealer()
 235 {
 236     delete mAllocator;
 237 }
 238
 239 sp<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
 249 void MemoryDealer::deallocate(size_t offset)
 250 {
 251     allocator()->deallocate(offset);
 252 }
 253
 254 void MemoryDealer::dump(const char* what) const
 255 {
 256     allocator()->dump(what);
 257 }
 258
 259 const sp<IMemoryHeap>& MemoryDealer::heap() const {
 260     return mHeap;
 261 }
 262
 263 SimpleBestFitAllocator* MemoryDealer::allocator() const {
 264     return mAllocator;
 265 }
 266
 267 // ----------------------------------------------------------------------------
 268
 269 // align all the memory blocks on a cache-line boundary
 270 const int SimpleBestFitAllocator::kMemoryAlign = 32;
 271
 272 SimpleBestFitAllocator::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
 281 SimpleBestFitAllocator::~SimpleBestFitAllocator()
 282 {
 283     while(!mList.isEmpty()) {
 284         delete mList.remove(mList.head());
 285     }
 286 }
 287
 288 size_t SimpleBestFitAllocator::size() const
 289 {
 290     return mHeapSize;
 291 }
 292
 293 size_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
 300 status_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
 310 ssize_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
 367 SimpleBestFitAllocator::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
 408 void SimpleBestFitAllocator::dump(const char* what) const
 409 {
 410     Mutex::Autolock _l(mLock);
 411     dump_l(what);
 412 }
 413
 414 void SimpleBestFitAllocator::dump_l(const char* what) const
 415 {
 416     String8 result;
 417     dump_l(result, what);
 418     ALOGD("%s", result.string());
 419 }
 420
 421 void SimpleBestFitAllocator::dump(String8& result,
 422         const char* what) const
 423 {
 424     Mutex::Autolock _l(mLock);
 425     dump_l(result, what);
 426 }
 427
 428 void 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: %08x | 0x%08X | 0x%08X | %s %s\n",
 449             i, int(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