/*
 * Copyright (c) 2017 Cisco and/or its affiliates.
 * 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.
 */

/**
 * This is a substitute for posix_memalign(3) that
 * establishes detectable boundaries around an allocated memory segment,
 * records a stack backtrace for each allocation,
 * detects buffer overruns and underruns by checking the boundaries when the memory is deallocated,
 * and tries to prevent a stray pointer to reference the memory again once it's been deallocated.
 *
 * The allocated memory consists of three contiguous segments: the prefix, the memory usable by the caller, and the suffix.
 * The memory usable by the caller is aligned as specified by the caller.
 * The alignment must be a power of 2 greater than or equal to the size of a {@code void *}.
 * <pre>
 * +--base  +-prefix     +-- memory           +-- suffix aligned on (void *)
 * v        v            v                    v
 * |________|PPPPPPPPPPPP|mmmmmmmmm...mmmm|___|SSSSSSSSS
 *                                         ^
 *                                         +-- variable padding
 * </pre>
 * Where '-' indicates padding, 'P' indicates the prefix data structure, 'm'
 * indicates contiguous memory for use by the caller, and 'S" indicates the suffix data structure.
 *
 */
#include <config.h>

#include <LongBow/runtime.h>

#if defined(_WIN64)
#  define backtrace(...) (0)
#  define backtrace_symbols(...) 0
#  define backtrace_symbols_fd(...) ((void) 0)
#elif defined(_WIN32)
#  define backtrace(...) (0)
#  define backtrace_symbols(...) 0
#  define backtrace_symbols_fd(...) ((void) 0)
#elif defined(__ANDROID__)
#  define backtrace(...) (0)
#  define backtrace_symbols(...) 0
#  define backtrace_symbols_fd(...) ((void) 0)
#elif defined(__APPLE__)
#  include <execinfo.h>
#elif defined(__linux)
#  include <execinfo.h>
#elif defined(__unix) // all unices not caught above
#  define backtrace(...) (0)
#  define backtrace_symbols(...) 0
#  define backtrace_symbols_fd(...) ((void) 0)
#elif defined(__posix)
#  include <execinfo.h>
#endif

#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <sys/errno.h>
#include <sys/queue.h>
#include <pthread.h>

#include <stdint.h>
#include <inttypes.h>
#include <stdbool.h>

#include <parc/algol/parc_StdlibMemory.h>
#include <parc/algol/parc_SafeMemory.h>
#include <parc/algol/parc_DisplayIndented.h>

typedef struct memory_backtrace {
    void **callstack;
    int maximumFrameCount;
    int actualFrameCount;
} _MemoryBacktrace;

static const uint32_t _parcSafeMemory_SuffixGuard = 0xcafecafe;
typedef struct memory_suffix {
    uint32_t guard;
} _MemorySuffix;

static const uint64_t _parcSafeMemory_PrefixMagic = 0xfacefacefaceface;
static const uint64_t _parcSafeMemory_Guard = 0xdeaddeaddeaddead;
static const uint64_t _parcSafeMemory_GuardAlreadyFreed = 0xBADDCAFEBADDCAFE;
typedef struct memory_prefix {
    uint64_t magic;               // A magic number indicating the start of this data structure.
    size_t requestedLength;       // The number of bytes the caller requested.
    size_t actualLength;          // The number of bytes >= requestedLength to ensure the right alignment for the suffix.
    size_t alignment;             // The aligment required by the caller.  Must be a power of 2 and >= sizeof(void *).
    _MemoryBacktrace *backtrace;  // A record of the caller's stack trace at the time of allocation.
    uint64_t guard;               // Try to detect underrun of the allocated memory.
} _MemoryPrefix;

typedef void *PARCSafeMemoryOrigin;

typedef void *PARCSafeMemoryUsable;

static PARCMemoryInterface *_parcMemory = &PARCStdlibMemoryAsPARCMemory;

static pthread_mutex_t _parcSafeMemory_Mutex = PTHREAD_MUTEX_INITIALIZER;


/**
 * Return true if the given alignment value is greater than or equal to {@code sizeof(void *)} and
 * is a power of 2.
 *
 * @param alignment
 * @return
 */
static bool
_alignmentIsValid(size_t alignment)
{
    return alignment >= sizeof(void *) && (alignment & (~alignment + 1)) == alignment;
}

/**
 * Add two pointers arithmetically.
 */
// Should increment be a ssize_t, instead of size_t?
static void *
_pointerAdd(const void *base, const size_t increment)
{
    void *result = (void *) &((char *) base)[increment];
    return result;
}

static size_t
_computePrefixLength(const size_t alignment)
{
    return (sizeof(_MemoryPrefix) + alignment - 1) & ~(alignment - 1);
}

static size_t
_computeUsableMemoryLength(const size_t requestedLength, const size_t alignment)
{
    return (requestedLength + alignment - 1) & ~(alignment - 1);
}

/**
 * Compute the size of the suffix on an allocated chunk of managed memory that causes the
 * first byte after this size to be aligned according to the given alignment value.
 */
static size_t
_computeSuffixLength(size_t alignment __attribute__((unused)))
{
    return sizeof(_MemorySuffix);
}

/**
 * Compute the total number of bytes necessary to store the entire Safe Memory structure.
 * Given a size number of bytes for use by a client function,
 * produce the total number of bytes necessary to store @p size
 * number of bytes for use by a client function and the `_MemoryPrefix`
 * and `_MemorySuffix` structures.
 */
static size_t
_computeMemoryTotalLength(size_t requestedLength, size_t alignment)
{
    size_t result =
        _computePrefixLength(alignment)
        + _computeUsableMemoryLength(requestedLength, sizeof(void*))
        + _computeSuffixLength(alignment);

    return result;
}

/**
 * Given the safe memory address, return a pointer to the _MemoryPrefix structure.
 */
static _MemoryPrefix *
_parcSafeMemory_GetPrefix(const PARCSafeMemoryUsable *usable)
{
    _MemoryPrefix *prefix = _pointerAdd(usable, -sizeof(_MemoryPrefix));
    return prefix;
}

/**
 * Given a base address for memory Return a pointer to the {@link _MemorySuffix}
 * structure for the given base pointer to allocated memory.
 *
 * @param base
 * @return
 */
static _MemorySuffix *
_parcSafeMemory_GetSuffix(const PARCSafeMemoryUsable *memory)
{
    _MemoryPrefix *prefix = _parcSafeMemory_GetPrefix(memory);

    _MemorySuffix *suffix = _pointerAdd(memory, prefix->actualLength);
    return suffix;
}

static PARCSafeMemoryState
_parcSafeMemory_GetPrefixState(const PARCSafeMemoryUsable *usable)
{
    _MemoryPrefix *prefix = _parcSafeMemory_GetPrefix(usable);

    if (prefix->guard == _parcSafeMemory_GuardAlreadyFreed) {
        return PARCSafeMemoryState_ALREADYFREE;
    }
    if (prefix->guard != _parcSafeMemory_Guard) {
        return PARCSafeMemoryState_UNDERRUN;
    }
    if (prefix->magic != _parcSafeMemory_PrefixMagic) {
        return PARCSafeMemoryState_UNDERRUN;
    }
    if (!_alignmentIsValid(prefix->alignment)) {
        return PARCSafeMemoryState_UNDERRUN;
    }

    return PARCSafeMemoryState_OK;
}

static PARCSafeMemoryOrigin *
_parcSafeMemory_GetOrigin(const PARCSafeMemoryUsable *memory)
{
    _MemoryPrefix *prefix = _parcSafeMemory_GetPrefix(memory);

    return _pointerAdd(memory, -_computePrefixLength(prefix->alignment));
}

static PARCSafeMemoryState
_parcSafeMemory_GetSuffixState(const PARCSafeMemoryUsable *memory)
{
    PARCSafeMemoryState result = PARCSafeMemoryState_OK;;
    _MemorySuffix *suffix = _parcSafeMemory_GetSuffix(memory);
    if (suffix->guard != _parcSafeMemory_SuffixGuard) {
        result = PARCSafeMemoryState_OVERRUN;
    }
    return result;
}

/**
 * Given a pointer to the base address of an allocated memory segment,
 * compute and return a pointer to the corresponding {@link _MemorySuffix} for that same memory.
 */
static _MemorySuffix *
_parcSafeMemory_FormatSuffix(const PARCSafeMemoryUsable *memory)
{
    _MemorySuffix *suffix = _parcSafeMemory_GetSuffix(memory);

    suffix->guard = _parcSafeMemory_SuffixGuard;
    return suffix;
}

static void
_backtraceReport(const _MemoryBacktrace *backtrace, int outputFd)
{
    if (outputFd != -1) {
        // Ignore the first entry as it points to this function and we just need to start at the calling function.
        backtrace_symbols_fd(&backtrace->callstack[1], backtrace->actualFrameCount - 1, outputFd);
    }
}

// This is a list of all memory allocations that were created by calls to Safe Memory.
// Each element of the list is the pointer to the result returned to the caller of the memory allocation,
// not a pointer to the base.
struct safememory_entry {
    LIST_ENTRY(safememory_entry) entries;      // List
    void *memory;
};
LIST_HEAD(, safememory_entry) head = LIST_HEAD_INITIALIZER(head);
static pthread_mutex_t head_mutex = PTHREAD_MUTEX_INITIALIZER;

static void
_parcSafeMemory_AddAllocation(void *memory)
{
    if (parcSafeMemory_Outstanding() == 0) {
        LIST_INIT(&head); // Initialize the list.
    }

    struct safememory_entry *e = malloc(sizeof(struct safememory_entry)); // Insert this at the head.
    e->memory = memory;

    pthread_mutex_lock(&head_mutex);
    LIST_INSERT_HEAD(&head, e, entries);
    pthread_mutex_unlock(&head_mutex);
}

static void
_parcSafeMemory_RemoveAllocation(void *memory)
{
    struct safememory_entry *e;
    pthread_mutex_lock(&head_mutex);
    LIST_FOREACH(e, &head, entries)
    {
        if (e->memory == memory) {
            LIST_REMOVE(e, entries);
            free(e);
            pthread_mutex_unlock(&head_mutex);
            return;
        }
    }

    pthread_mutex_unlock(&head_mutex);
    fprintf(stderr, "parcSafeMemory_RemoveAllocation: Destroying memory (%p) which is NOT in the allocated memory record. Double free?\n", memory);
}

static PARCSafeMemoryState
_parcSafeMemory_GetState(const PARCSafeMemoryUsable *memory)
{
    PARCSafeMemoryState prefixState = _parcSafeMemory_GetPrefixState(memory);
    if (prefixState != PARCSafeMemoryState_OK) {
        return prefixState;
    }
    return _parcSafeMemory_GetSuffixState(memory);
}

static const char *
_parcSafeMemory_StateToString(PARCSafeMemoryState status)
{
    switch (status) {
        case PARCSafeMemoryState_OK:                return "OK";
        case PARCSafeMemoryState_MISMATCHED:        return "MISMATCHED";
        case PARCSafeMemoryState_UNDERRUN:          return "UNDERRUN";
        case PARCSafeMemoryState_OVERRUN:           return "OVERRUN";
        case PARCSafeMemoryState_NOTHINGALLOCATED:  return "NOTHINGALLOCATED";
        case PARCSafeMemoryState_ALREADYFREE:       return "ALREADYFREE";
    }
    return "?";
}

static void
_parcSafeMemory_Report(const PARCSafeMemoryUsable *safeMemory, int outputFd)
{
    _MemoryPrefix *prefix = _parcSafeMemory_GetPrefix(safeMemory);

    if (outputFd != -1) {
        int charactersPrinted = dprintf(outputFd, "Memory %p (base %p) %s\n",
                                        (void *) safeMemory,
                                        (void *) prefix,
                                        _parcSafeMemory_StateToString(_parcSafeMemory_GetState(safeMemory)));
        trapUnexpectedStateIf(charactersPrinted < 0, "Cannot write to file descriptor %d", outputFd);
    }
    _backtraceReport(prefix->backtrace, outputFd);
}

uint32_t
parcSafeMemory_ReportAllocation(int outputFd)
{
    uint32_t index = 0;
    struct safememory_entry *e;

    pthread_mutex_lock(&head_mutex);
    LIST_FOREACH(e, &head, entries)
    {
        _MemoryPrefix *prefix = _parcSafeMemory_GetPrefix(e->memory);
        if (outputFd != -1) {
            int charactersPrinted = dprintf(outputFd,
                                            "\n%u SafeMemory@%p: %p={ .requestedLength=%zd, .actualLength=%zd, .alignment=%zd }\n",
                                            index, e->memory, (void *) prefix, prefix->requestedLength, prefix->actualLength, prefix->alignment);
            trapUnexpectedStateIf(charactersPrinted < 0, "Cannot write to file descriptor %d", outputFd)
            {
                pthread_mutex_unlock(&head_mutex);
            }
        }
        _parcSafeMemory_Report(e->memory, outputFd);
        index++;
    }
    pthread_mutex_unlock(&head_mutex);
    return parcSafeMemory_Outstanding();
}

static void
_backtraceDestroy(_MemoryBacktrace **backtrace)
{
    free((*backtrace)->callstack);
    free(*backtrace);
    *backtrace = 0;
}

static PARCSafeMemoryState
_parcSafeMemory_Destroy(void **memoryPointer)
{
    pthread_mutex_lock(&_parcSafeMemory_Mutex);

    if (parcSafeMemory_Outstanding() == 0) {
        pthread_mutex_unlock(&_parcSafeMemory_Mutex);
        return PARCSafeMemoryState_NOTHINGALLOCATED;
    }

    _parcSafeMemory_RemoveAllocation(*memoryPointer);

    PARCSafeMemoryUsable *memory = *memoryPointer;

    PARCSafeMemoryState state = _parcSafeMemory_GetState(memory);
    trapUnexpectedStateIf(state != PARCSafeMemoryState_OK,
                          "Expected PARCSafeMemoryState_OK, actual %s (see parc_SafeMemory.h)",
                          _parcSafeMemory_StateToString(state))
    {
        pthread_mutex_unlock(&_parcSafeMemory_Mutex);
    }

    _MemoryPrefix *prefix = _parcSafeMemory_GetPrefix(memory);
    _backtraceDestroy(&prefix->backtrace);

    PARCSafeMemoryOrigin *base = _parcSafeMemory_GetOrigin(memory);

    memset(base, 0, _computeMemoryTotalLength(prefix->requestedLength, prefix->alignment));
    prefix->guard = _parcSafeMemory_GuardAlreadyFreed;

    ((PARCMemoryDeallocate *) _parcMemory->Deallocate)((void **) &base);

    *memoryPointer = 0;

    pthread_mutex_unlock(&_parcSafeMemory_Mutex);
    return PARCSafeMemoryState_OK;
}

__attribute__((unused))
static void
_parcSafeMemory_DeallocateAll(void)
{
    struct safememory_entry *e;

    pthread_mutex_lock(&head_mutex);
    LIST_FOREACH(e, &head, entries)
    {
        _parcSafeMemory_Destroy(&e->memory);
    }
    pthread_mutex_unlock(&head_mutex);
}

static _MemoryBacktrace *
_backtraceCreate(int maximumFrameCount)
{
    _MemoryBacktrace *result = malloc(sizeof(_MemoryBacktrace));
    result->maximumFrameCount = maximumFrameCount;
    result->callstack = calloc(result->maximumFrameCount, sizeof(void *));

    result->actualFrameCount = backtrace(result->callstack, result->maximumFrameCount);

    return result;
}

/**
 * Format memory with a MemoryPrefix structure.
 *
 * @param origin The origin of the allocated memory (which is not the same as the start of usable memory).
 * @param requestedLength The length of the extent of memory for general purpose use by the caller.
 * @param alignment A power of 2 greater than or equal to {@code sizeof(void *)}.
 * @return The pointer to the first address suitable for general purpose use by the caller.
 */
static PARCSafeMemoryUsable *
_parcSafeMemory_FormatPrefix(PARCSafeMemoryOrigin *origin, size_t requestedLength, size_t alignment)
{
    int backTraceDepth = 20;

    if (!_alignmentIsValid(alignment)) {
        return NULL;
    }
    size_t prefixSize = _computePrefixLength(alignment);

    // This abuts the prefix to the user memory, it does not start at the beginning
    // of the aligned prefix region.
    _MemoryPrefix *prefix = (_MemoryPrefix *) (origin + (prefixSize - sizeof(_MemoryPrefix)));

    prefix->magic = _parcSafeMemory_PrefixMagic;
    prefix->requestedLength = requestedLength;
    prefix->actualLength = _computeUsableMemoryLength(requestedLength, sizeof(void*));
    prefix->alignment = alignment;
    prefix->backtrace = _backtraceCreate(backTraceDepth);
    prefix->guard = _parcSafeMemory_Guard;

    PARCSafeMemoryUsable *result = _pointerAdd(origin, prefixSize);

    assertAligned(result, alignment, "Return value is not properly aligned to %zu", alignment);
    return result;
}

/**
 * Given a pointer to allocated memory and the length of bytes that will be used by the caller,
 * format the prefix and suffix structures returning a pointer to the first properly aligned
 * byte available to the client function.
 */
static void *
_parcSafeMemory_FormatMemory(PARCSafeMemoryOrigin *origin, size_t length, size_t alignment)
{
    PARCSafeMemoryUsable *memory = _parcSafeMemory_FormatPrefix(origin, length, alignment);
    if (memory != NULL) {
        _parcSafeMemory_FormatSuffix(memory);
    }

    return memory;
}

int
parcSafeMemory_MemAlign(void **memptr, size_t alignment, size_t requestedSize)
{
    if (!_alignmentIsValid(alignment)) {
        return EINVAL;
    }
    if (requestedSize == 0) {
        return EINVAL;
    }

    size_t totalSize = _computeMemoryTotalLength(requestedSize, alignment);
    if (totalSize < requestedSize) {
        return ERANGE;
    }

    pthread_mutex_lock(&_parcSafeMemory_Mutex);

    void *base;
    int failure = ((PARCMemoryMemAlign *) _parcMemory->MemAlign)(&base, alignment, totalSize);

    if (failure != 0 || base == NULL) {
        pthread_mutex_unlock(&_parcSafeMemory_Mutex);
        return ENOMEM;
    }

    *memptr = _parcSafeMemory_FormatMemory(base, requestedSize, alignment);

    _parcSafeMemory_AddAllocation(*memptr);
    pthread_mutex_unlock(&_parcSafeMemory_Mutex);

    return 0;
}

void *
parcSafeMemory_Allocate(size_t requestedSize)
{
    void *result = NULL;

    if (requestedSize != 0) {
        size_t totalSize = _computeMemoryTotalLength(requestedSize, sizeof(void *));

        if (totalSize >= requestedSize) {
            pthread_mutex_lock(&_parcSafeMemory_Mutex);

            void *base = ((PARCMemoryAllocate *) _parcMemory->Allocate)(totalSize);
            if (base != NULL) {
                result = _parcSafeMemory_FormatMemory(base, requestedSize, sizeof(void *));

                _parcSafeMemory_AddAllocation(result);
            }
            pthread_mutex_unlock(&_parcSafeMemory_Mutex);
        }
    }
    return result;
}

void *
parcSafeMemory_AllocateAndClear(size_t requestedSize)
{
    void *memptr = parcSafeMemory_Allocate(requestedSize);
    if (memptr != NULL) {
        memset(memptr, 0, requestedSize);
    }
    return memptr;
}

bool
parcSafeMemory_IsValid(const void *memory)
{
    bool result = true;

    PARCSafeMemoryState state = _parcSafeMemory_GetState(memory);
    if (state != PARCSafeMemoryState_OK) {
        return false;
    }

    return result;
}


uint32_t
parcSafeMemory_Outstanding(void)
{
    return ((PARCMemoryOutstanding *) _parcMemory->Outstanding)();
}

void *
parcSafeMemory_Reallocate(void *original, size_t newSize)
{
    void *result;

    result = parcSafeMemory_Allocate(newSize);

    if (original == NULL) {
        return result;
    }

    if (result != NULL) {
        _MemoryPrefix *prefix = _parcSafeMemory_GetPrefix(original);
        size_t originalSize = prefix->requestedLength;

        memcpy(result, original, originalSize);
        parcSafeMemory_Deallocate(&original);
    }
    return result;
}

char *
parcSafeMemory_StringDuplicate(const char *string, size_t length)
{
    size_t actualLength = strlen(string);
    if (length < actualLength) {
        actualLength = length;
    }

    char *result = parcSafeMemory_Allocate(actualLength + 1);
    if (result != NULL) {
        memcpy(result, string, actualLength);
        result[actualLength] = 0;
    }
    return result;
}

void
parcSafeMemory_Deallocate(void **pointer)
{
    _parcSafeMemory_Destroy(pointer);
}

void
parcSafeMemory_Display(const void *memory, int indentation)
{
    if (memory == NULL) {
        parcDisplayIndented_PrintLine(indentation, "PARCSafeMemory@NULL");
    } else {
        _MemoryPrefix *prefix = _parcSafeMemory_GetPrefix(memory);

        parcDisplayIndented_PrintLine(indentation, "PARCSafeMemory@%p {", (void *) memory);
        parcDisplayIndented_PrintLine(indentation + 1,
                                      "%p=[ magic=0x%" PRIx64 " requestedLength=%zd, actualLength=%zd, alignment=%zd, guard=0x%" PRIx64 "]",
                                      _parcSafeMemory_GetOrigin(memory),
                                      prefix->magic,
                                      prefix->requestedLength,
                                      prefix->actualLength,
                                      prefix->alignment,
                                      prefix->guard);

        parcDisplayIndented_PrintMemory(indentation + 1, prefix->requestedLength, memory);

        parcDisplayIndented_PrintLine(indentation, "}");
    }
}

PARCMemoryInterface PARCSafeMemoryAsPARCMemory = {
    .Allocate         = (uintptr_t) parcSafeMemory_Allocate,
    .AllocateAndClear = (uintptr_t) parcSafeMemory_AllocateAndClear,
    .MemAlign         = (uintptr_t) parcSafeMemory_MemAlign,
    .Deallocate       = (uintptr_t) parcSafeMemory_Deallocate,
    .Reallocate       = (uintptr_t) parcSafeMemory_Reallocate,
    .Outstanding      = (uintptr_t) parcSafeMemory_Outstanding,
    .StringDuplicate  = (uintptr_t) parcSafeMemory_StringDuplicate
};