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