/*
* 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