| /* |
| * Copyright (C) 2007 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #define LOG_TAG "MemoryDealer" |
| |
| #include <binder/MemoryDealer.h> |
| #include <binder/IPCThreadState.h> |
| #include <binder/MemoryBase.h> |
| |
| #include <utils/Log.h> |
| #include <utils/SortedVector.h> |
| #include <utils/String8.h> |
| #include <utils/threads.h> |
| |
| #include <stdint.h> |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <fcntl.h> |
| #include <unistd.h> |
| #include <errno.h> |
| #include <string.h> |
| |
| #include <sys/stat.h> |
| #include <sys/types.h> |
| #include <sys/mman.h> |
| #include <sys/file.h> |
| |
| namespace android { |
| // ---------------------------------------------------------------------------- |
| |
| /* |
| * A simple templatized doubly linked-list implementation |
| */ |
| |
| template <typename NODE> |
| class LinkedList |
| { |
| NODE* mFirst; |
| NODE* mLast; |
| |
| public: |
| LinkedList() : mFirst(nullptr), mLast(nullptr) { } |
| bool isEmpty() const { return mFirst == nullptr; } |
| NODE const* head() const { return mFirst; } |
| NODE* head() { return mFirst; } |
| NODE const* tail() const { return mLast; } |
| NODE* tail() { return mLast; } |
| |
| void insertAfter(NODE* node, NODE* newNode) { |
| newNode->prev = node; |
| newNode->next = node->next; |
| if (node->next == nullptr) mLast = newNode; |
| else node->next->prev = newNode; |
| node->next = newNode; |
| } |
| |
| void insertBefore(NODE* node, NODE* newNode) { |
| newNode->prev = node->prev; |
| newNode->next = node; |
| if (node->prev == nullptr) mFirst = newNode; |
| else node->prev->next = newNode; |
| node->prev = newNode; |
| } |
| |
| void insertHead(NODE* newNode) { |
| if (mFirst == nullptr) { |
| mFirst = mLast = newNode; |
| newNode->prev = newNode->next = nullptr; |
| } else { |
| newNode->prev = nullptr; |
| newNode->next = mFirst; |
| mFirst->prev = newNode; |
| mFirst = newNode; |
| } |
| } |
| |
| void insertTail(NODE* newNode) { |
| if (mLast == 0) { |
| insertHead(newNode); |
| } else { |
| newNode->prev = mLast; |
| newNode->next = 0; |
| mLast->next = newNode; |
| mLast = newNode; |
| } |
| } |
| |
| NODE* remove(NODE* node) { |
| if (node->prev == nullptr) mFirst = node->next; |
| else node->prev->next = node->next; |
| if (node->next == nullptr) mLast = node->prev; |
| else node->next->prev = node->prev; |
| return node; |
| } |
| }; |
| |
| // ---------------------------------------------------------------------------- |
| |
| class Allocation : public MemoryBase { |
| public: |
| Allocation(const sp<MemoryDealer>& dealer, |
| const sp<IMemoryHeap>& heap, ssize_t offset, size_t size); |
| virtual ~Allocation(); |
| private: |
| sp<MemoryDealer> mDealer; |
| }; |
| |
| // ---------------------------------------------------------------------------- |
| |
| class SimpleBestFitAllocator |
| { |
| enum { |
| PAGE_ALIGNED = 0x00000001 |
| }; |
| public: |
| explicit SimpleBestFitAllocator(size_t size); |
| ~SimpleBestFitAllocator(); |
| |
| size_t allocate(size_t size, uint32_t flags = 0); |
| status_t deallocate(size_t offset); |
| size_t size() const; |
| void dump(const char* what) const; |
| void dump(String8& res, const char* what) const; |
| |
| static size_t getAllocationAlignment() { return kMemoryAlign; } |
| |
| private: |
| |
| struct chunk_t { |
| chunk_t(size_t start, size_t size) |
| : start(start), size(size), free(1), prev(nullptr), next(nullptr) { |
| } |
| size_t start; |
| size_t size : 28; |
| int free : 4; |
| mutable chunk_t* prev; |
| mutable chunk_t* next; |
| }; |
| |
| ssize_t alloc(size_t size, uint32_t flags); |
| chunk_t* dealloc(size_t start); |
| void dump_l(const char* what) const; |
| void dump_l(String8& res, const char* what) const; |
| |
| static const int kMemoryAlign; |
| mutable Mutex mLock; |
| LinkedList<chunk_t> mList; |
| size_t mHeapSize; |
| }; |
| |
| // ---------------------------------------------------------------------------- |
| |
| Allocation::Allocation( |
| const sp<MemoryDealer>& dealer, |
| const sp<IMemoryHeap>& heap, ssize_t offset, size_t size) |
| : MemoryBase(heap, offset, size), mDealer(dealer) |
| { |
| #ifndef NDEBUG |
| void* const start_ptr = (void*)(intptr_t(heap->base()) + offset); |
| memset(start_ptr, 0xda, size); |
| #endif |
| } |
| |
| Allocation::~Allocation() |
| { |
| size_t freedOffset = getOffset(); |
| size_t freedSize = getSize(); |
| if (freedSize) { |
| /* NOTE: it's VERY important to not free allocations of size 0 because |
| * they're special as they don't have any record in the allocator |
| * and could alias some real allocation (their offset is zero). */ |
| |
| // keep the size to unmap in excess |
| size_t pagesize = getpagesize(); |
| size_t start = freedOffset; |
| size_t end = start + freedSize; |
| start &= ~(pagesize-1); |
| end = (end + pagesize-1) & ~(pagesize-1); |
| |
| // give back to the kernel the pages we don't need |
| size_t free_start = freedOffset; |
| size_t free_end = free_start + freedSize; |
| if (start < free_start) |
| start = free_start; |
| if (end > free_end) |
| end = free_end; |
| start = (start + pagesize-1) & ~(pagesize-1); |
| end &= ~(pagesize-1); |
| |
| if (start < end) { |
| void* const start_ptr = (void*)(intptr_t(getHeap()->base()) + start); |
| size_t size = end-start; |
| |
| #ifndef NDEBUG |
| memset(start_ptr, 0xdf, size); |
| #endif |
| |
| // MADV_REMOVE is not defined on Dapper based Goobuntu |
| #ifdef MADV_REMOVE |
| if (size) { |
| int err = madvise(start_ptr, size, MADV_REMOVE); |
| ALOGW_IF(err, "madvise(%p, %zu, MADV_REMOVE) returned %s", |
| start_ptr, size, err<0 ? strerror(errno) : "Ok"); |
| } |
| #endif |
| } |
| |
| // This should be done after madvise(MADV_REMOVE), otherwise madvise() |
| // might kick out the memory region that's allocated and/or written |
| // right after the deallocation. |
| mDealer->deallocate(freedOffset); |
| } |
| } |
| |
| // ---------------------------------------------------------------------------- |
| |
| MemoryDealer::MemoryDealer(size_t size, const char* name, uint32_t flags) |
| : mHeap(new MemoryHeapBase(size, flags, name)), |
| mAllocator(new SimpleBestFitAllocator(size)) |
| { |
| } |
| |
| MemoryDealer::~MemoryDealer() |
| { |
| delete mAllocator; |
| } |
| |
| sp<IMemory> MemoryDealer::allocate(size_t size) |
| { |
| sp<IMemory> memory; |
| const ssize_t offset = allocator()->allocate(size); |
| if (offset >= 0) { |
| memory = new Allocation(this, heap(), offset, size); |
| } |
| return memory; |
| } |
| |
| void MemoryDealer::deallocate(size_t offset) |
| { |
| allocator()->deallocate(offset); |
| } |
| |
| void MemoryDealer::dump(const char* what) const |
| { |
| allocator()->dump(what); |
| } |
| |
| const sp<IMemoryHeap>& MemoryDealer::heap() const { |
| return mHeap; |
| } |
| |
| SimpleBestFitAllocator* MemoryDealer::allocator() const { |
| return mAllocator; |
| } |
| |
| // static |
| size_t MemoryDealer::getAllocationAlignment() |
| { |
| return SimpleBestFitAllocator::getAllocationAlignment(); |
| } |
| |
| // ---------------------------------------------------------------------------- |
| |
| // align all the memory blocks on a cache-line boundary |
| const int SimpleBestFitAllocator::kMemoryAlign = 32; |
| |
| SimpleBestFitAllocator::SimpleBestFitAllocator(size_t size) |
| { |
| size_t pagesize = getpagesize(); |
| mHeapSize = ((size + pagesize-1) & ~(pagesize-1)); |
| |
| chunk_t* node = new chunk_t(0, mHeapSize / kMemoryAlign); |
| mList.insertHead(node); |
| } |
| |
| SimpleBestFitAllocator::~SimpleBestFitAllocator() |
| { |
| while(!mList.isEmpty()) { |
| chunk_t* removed = mList.remove(mList.head()); |
| #ifdef __clang_analyzer__ |
| // Clang static analyzer gets confused in this loop |
| // and generates a false positive warning about accessing |
| // memory that is already freed. |
| // Add an "assert" to avoid the confusion. |
| LOG_ALWAYS_FATAL_IF(mList.head() == removed); |
| #endif |
| delete removed; |
| } |
| } |
| |
| size_t SimpleBestFitAllocator::size() const |
| { |
| return mHeapSize; |
| } |
| |
| size_t SimpleBestFitAllocator::allocate(size_t size, uint32_t flags) |
| { |
| Mutex::Autolock _l(mLock); |
| ssize_t offset = alloc(size, flags); |
| return offset; |
| } |
| |
| status_t SimpleBestFitAllocator::deallocate(size_t offset) |
| { |
| Mutex::Autolock _l(mLock); |
| chunk_t const * const freed = dealloc(offset); |
| if (freed) { |
| return NO_ERROR; |
| } |
| return NAME_NOT_FOUND; |
| } |
| |
| ssize_t SimpleBestFitAllocator::alloc(size_t size, uint32_t flags) |
| { |
| if (size == 0) { |
| return 0; |
| } |
| size = (size + kMemoryAlign-1) / kMemoryAlign; |
| chunk_t* free_chunk = nullptr; |
| chunk_t* cur = mList.head(); |
| |
| size_t pagesize = getpagesize(); |
| while (cur) { |
| int extra = 0; |
| if (flags & PAGE_ALIGNED) |
| extra = ( -cur->start & ((pagesize/kMemoryAlign)-1) ) ; |
| |
| // best fit |
| if (cur->free && (cur->size >= (size+extra))) { |
| if ((!free_chunk) || (cur->size < free_chunk->size)) { |
| free_chunk = cur; |
| } |
| if (cur->size == size) { |
| break; |
| } |
| } |
| cur = cur->next; |
| } |
| |
| if (free_chunk) { |
| const size_t free_size = free_chunk->size; |
| free_chunk->free = 0; |
| free_chunk->size = size; |
| if (free_size > size) { |
| int extra = 0; |
| if (flags & PAGE_ALIGNED) |
| extra = ( -free_chunk->start & ((pagesize/kMemoryAlign)-1) ) ; |
| if (extra) { |
| chunk_t* split = new chunk_t(free_chunk->start, extra); |
| free_chunk->start += extra; |
| mList.insertBefore(free_chunk, split); |
| } |
| |
| ALOGE_IF((flags&PAGE_ALIGNED) && |
| ((free_chunk->start*kMemoryAlign)&(pagesize-1)), |
| "PAGE_ALIGNED requested, but page is not aligned!!!"); |
| |
| const ssize_t tail_free = free_size - (size+extra); |
| if (tail_free > 0) { |
| chunk_t* split = new chunk_t( |
| free_chunk->start + free_chunk->size, tail_free); |
| mList.insertAfter(free_chunk, split); |
| } |
| } |
| return (free_chunk->start)*kMemoryAlign; |
| } |
| return NO_MEMORY; |
| } |
| |
| SimpleBestFitAllocator::chunk_t* SimpleBestFitAllocator::dealloc(size_t start) |
| { |
| start = start / kMemoryAlign; |
| chunk_t* cur = mList.head(); |
| while (cur) { |
| if (cur->start == start) { |
| LOG_FATAL_IF(cur->free, |
| "block at offset 0x%08lX of size 0x%08lX already freed", |
| cur->start*kMemoryAlign, cur->size*kMemoryAlign); |
| |
| // merge freed blocks together |
| chunk_t* freed = cur; |
| cur->free = 1; |
| do { |
| chunk_t* const p = cur->prev; |
| chunk_t* const n = cur->next; |
| if (p && (p->free || !cur->size)) { |
| freed = p; |
| p->size += cur->size; |
| mList.remove(cur); |
| delete cur; |
| } |
| cur = n; |
| } while (cur && cur->free); |
| |
| #ifndef NDEBUG |
| if (!freed->free) { |
| dump_l("dealloc (!freed->free)"); |
| } |
| #endif |
| LOG_FATAL_IF(!freed->free, |
| "freed block at offset 0x%08lX of size 0x%08lX is not free!", |
| freed->start * kMemoryAlign, freed->size * kMemoryAlign); |
| |
| return freed; |
| } |
| cur = cur->next; |
| } |
| return nullptr; |
| } |
| |
| void SimpleBestFitAllocator::dump(const char* what) const |
| { |
| Mutex::Autolock _l(mLock); |
| dump_l(what); |
| } |
| |
| void SimpleBestFitAllocator::dump_l(const char* what) const |
| { |
| String8 result; |
| dump_l(result, what); |
| ALOGD("%s", result.string()); |
| } |
| |
| void SimpleBestFitAllocator::dump(String8& result, |
| const char* what) const |
| { |
| Mutex::Autolock _l(mLock); |
| dump_l(result, what); |
| } |
| |
| void SimpleBestFitAllocator::dump_l(String8& result, |
| const char* what) const |
| { |
| size_t size = 0; |
| int32_t i = 0; |
| chunk_t const* cur = mList.head(); |
| |
| const size_t SIZE = 256; |
| char buffer[SIZE]; |
| snprintf(buffer, SIZE, " %s (%p, size=%u)\n", |
| what, this, (unsigned int)mHeapSize); |
| |
| result.append(buffer); |
| |
| while (cur) { |
| const char* errs[] = {"", "| link bogus NP", |
| "| link bogus PN", "| link bogus NP+PN" }; |
| int np = ((cur->next) && cur->next->prev != cur) ? 1 : 0; |
| int pn = ((cur->prev) && cur->prev->next != cur) ? 2 : 0; |
| |
| snprintf(buffer, SIZE, " %3u: %p | 0x%08X | 0x%08X | %s %s\n", |
| i, cur, int(cur->start*kMemoryAlign), |
| int(cur->size*kMemoryAlign), |
| int(cur->free) ? "F" : "A", |
| errs[np|pn]); |
| |
| result.append(buffer); |
| |
| if (!cur->free) |
| size += cur->size*kMemoryAlign; |
| |
| i++; |
| cur = cur->next; |
| } |
| snprintf(buffer, SIZE, |
| " size allocated: %u (%u KB)\n", int(size), int(size/1024)); |
| result.append(buffer); |
| } |
| |
| |
| } // namespace android |