/*
 * Copyright 2016 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "src/base/SkArenaAlloc.h"

#include "include/private/base/SkMalloc.h"

#include <algorithm>
#include <cassert>
#include <cstddef>

static char* end_chain(char*) { return nullptr; }

SkArenaAlloc::SkArenaAlloc(char* block, size_t size, size_t firstHeapAllocation)
    : fDtorCursor {block}
    , fCursor     {block}
    , fEnd        {block + SkToU32(size)}
    , fFibonacciProgression{SkToU32(size), SkToU32(firstHeapAllocation)}
{
    if (size < sizeof(Footer)) {
        fEnd = fCursor = fDtorCursor = nullptr;
    }

    if (fCursor != nullptr) {
        this->installFooter(end_chain, 0);
        sk_asan_poison_memory_region(fCursor, fEnd - fCursor);
    }
}

SkArenaAlloc::~SkArenaAlloc() {
    RunDtorsOnBlock(fDtorCursor);
}

void SkArenaAlloc::installFooter(FooterAction* action, uint32_t padding) {
    assert(SkTFitsIn<uint8_t>(padding));
    this->installRaw(action);
    this->installRaw((uint8_t)padding);
    fDtorCursor = fCursor;
}

char* SkArenaAlloc::SkipPod(char* footerEnd) {
    char* objEnd = footerEnd - (sizeof(Footer) + sizeof(uint32_t));
    uint32_t skip;
    memmove(&skip, objEnd, sizeof(uint32_t));
    return objEnd - (ptrdiff_t) skip;
}

void SkArenaAlloc::RunDtorsOnBlock(char* footerEnd) {
    while (footerEnd != nullptr) {
        FooterAction* action;
        uint8_t       padding;

        memcpy(&action,  footerEnd - sizeof( Footer), sizeof( action));
        memcpy(&padding, footerEnd - sizeof(padding), sizeof(padding));

        footerEnd = action(footerEnd) - (ptrdiff_t)padding;
    }
}

char* SkArenaAlloc::NextBlock(char* footerEnd) {
    char* objEnd = footerEnd - (sizeof(char*) + sizeof(Footer));
    char* next;
    memmove(&next, objEnd, sizeof(char*));
    RunDtorsOnBlock(next);
    sk_free(objEnd);
    return nullptr;
}

void SkArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) {
    constexpr uint32_t headerSize = sizeof(Footer) + sizeof(ptrdiff_t);
    constexpr uint32_t maxSize = std::numeric_limits<uint32_t>::max();
    constexpr uint32_t overhead = headerSize + sizeof(Footer);
    AssertRelease(size <= maxSize - overhead);
    uint32_t objSizeAndOverhead = size + overhead;

    const uint32_t alignmentOverhead = alignment - 1;
    AssertRelease(objSizeAndOverhead <= maxSize - alignmentOverhead);
    objSizeAndOverhead += alignmentOverhead;

    uint32_t minAllocationSize = fFibonacciProgression.nextBlockSize();
    uint32_t allocationSize = std::max(objSizeAndOverhead, minAllocationSize);

    // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K
    // heuristic is from the JEMalloc behavior.
    {
        uint32_t mask = allocationSize > (1 << 15) ? (1 << 12) - 1 : 16 - 1;
        AssertRelease(allocationSize <= maxSize - mask);
        allocationSize = (allocationSize + mask) & ~mask;
    }

    char* newBlock = static_cast<char*>(sk_malloc_throw(allocationSize));

    auto previousDtor = fDtorCursor;
    fCursor = newBlock;
    fDtorCursor = newBlock;
    fEnd = fCursor + allocationSize;

    // poison the unused bytes in the block.
    sk_asan_poison_memory_region(fCursor, fEnd - fCursor);

    this->installRaw(previousDtor);
    this->installFooter(NextBlock, 0);
}

char* SkArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) {
    uintptr_t mask = alignment - 1;

restart:
    uint32_t skipOverhead = 0;
    const bool needsSkipFooter = fCursor != fDtorCursor;
    if (needsSkipFooter) {
        skipOverhead = sizeof(Footer) + sizeof(uint32_t);
    }
    const uint32_t totalSize = sizeIncludingFooter + skipOverhead;

    // Math on null fCursor/fEnd is undefined behavior, so explicitly check for first alloc.
    if (!fCursor) {
        this->ensureSpace(totalSize, alignment);
        goto restart;
    }

    assert(fEnd);
    // This test alone would be enough nullptr were defined to be 0, but it's not.
    char* objStart = (char*)((uintptr_t)(fCursor + skipOverhead + mask) & ~mask);
    if ((ptrdiff_t)totalSize > fEnd - objStart) {
        this->ensureSpace(totalSize, alignment);
        goto restart;
    }

    AssertRelease((ptrdiff_t)totalSize <= fEnd - objStart);

    // Install a skip footer if needed, thus terminating a run of POD data. The calling code is
    // responsible for installing the footer after the object.
    if (needsSkipFooter) {
        this->installRaw(SkToU32(fCursor - fDtorCursor));
        this->installFooter(SkipPod, 0);
    }

    return objStart;
}

SkArenaAllocWithReset::SkArenaAllocWithReset(char* block,
                                             size_t size,
                                             size_t firstHeapAllocation)
        : SkArenaAlloc(block, size, firstHeapAllocation)
        , fFirstBlock{block}
        , fFirstSize{SkToU32(size)}
        , fFirstHeapAllocationSize{SkToU32(firstHeapAllocation)} {}

void SkArenaAllocWithReset::reset() {
    char* const    firstBlock              = fFirstBlock;
    const uint32_t firstSize               = fFirstSize;
    const uint32_t firstHeapAllocationSize = fFirstHeapAllocationSize;
    this->~SkArenaAllocWithReset();
    new (this) SkArenaAllocWithReset{firstBlock, firstSize, firstHeapAllocationSize};
}

bool SkArenaAllocWithReset::isEmpty() {
    return this->cursor() == nullptr ||
           this->cursor() == fFirstBlock + sizeof(Footer);
}

// SkFibonacci47 is the first 47 Fibonacci numbers. Fib(47) is the largest value less than 2 ^ 32.
// Used by SkFibBlockSizes.
std::array<const uint32_t, 47> SkFibonacci47 {
                1,         1,          2,          3,          5,          8,
               13,        21,         34,         55,         89,        144,
              233,       377,        610,        987,       1597,       2584,
             4181,      6765,      10946,      17711,      28657,      46368,
            75025,    121393,     196418,     317811,     514229,     832040,
          1346269,   2178309,    3524578,    5702887,    9227465,   14930352,
         24157817,  39088169,   63245986,  102334155,  165580141,  267914296,
        433494437, 701408733, 1134903170, 1836311903, 2971215073,
};