// Copyright 2016 The Fuchsia Authors
// Copyright (c) 2008-2015 Travis Geiselbrecht
//
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file or at
// https://opensource.org/licenses/MIT

#include <lib/heap.h>

#include <arch/ops.h>
#include <assert.h>
#include <debug.h>
#include <err.h>
#include <kernel/auto_lock.h>
#include <kernel/spinlock.h>
#include <lib/cmpctmalloc.h>
#include <lib/console.h>
#include <list.h>
#include <stdlib.h>
#include <string.h>
#include <trace.h>
#include <vm/physmap.h>
#include <vm/pmm.h>
#include <vm/vm.h>

#define LOCAL_TRACE 0

#ifndef HEAP_PANIC_ON_ALLOC_FAIL
#if LK_DEBUGLEVEL > 2
#define HEAP_PANIC_ON_ALLOC_FAIL 1
#else
#define HEAP_PANIC_ON_ALLOC_FAIL 0
#endif
#endif

/* heap tracing */
#if LK_DEBUGLEVEL > 1
static bool heap_trace = false;
#else
#define heap_trace (false)
#endif

// keep a list of unique caller:size sites in a list
namespace {

struct alloc_stat {
    list_node node;

    void* caller;
    size_t size;

    uint64_t count;
};

const size_t num_stats = 1024;
size_t next_unused_stat = 0;
alloc_stat stats[num_stats];

list_node stat_list = LIST_INITIAL_VALUE(stat_list);
SpinLock stat_lock;

void add_stat(void* caller, size_t size) {
    if (!HEAP_COLLECT_STATS) {
        return;
    }

    AutoSpinLock guard(&stat_lock);

    // look for an existing stat, bump the count and move to head if found
    alloc_stat* s;
    list_for_every_entry (&stat_list, s, alloc_stat, node) {
        if (s->caller == caller && s->size == size) {
            s->count++;
            list_delete(&s->node);
            list_add_head(&stat_list, &s->node);
            return;
        }
    }

    // allocate a new one and add it to the list
    if (unlikely(next_unused_stat >= num_stats))
        return;

    s = &stats[next_unused_stat++];
    s->caller = caller;
    s->size = size;
    s->count = 1;
    list_add_head(&stat_list, &s->node);
}

void dump_stats() {
    if (!HEAP_COLLECT_STATS) {
        return;
    }

    AutoSpinLock guard(&stat_lock);

    // remove all of them from the list
    alloc_stat* s;
    while ((s = list_remove_head_type(&stat_list, alloc_stat, node)))
        ;

    // reinsert all of the entries, sorted by size
    for (size_t i = 0; i < next_unused_stat; i++) {
        bool added = false;
        list_for_every_entry (&stat_list, s, alloc_stat, node) {
            if (stats[i].size >= s->size) {
                list_add_before(&s->node, &stats[i].node);
                added = true;
                break;
            }
        }
        // fell off the end
        if (!added) {
            list_add_tail(&stat_list, &stats[i].node);
        }
    }

    // dump the list of stats
    list_for_every_entry (&stat_list, s, alloc_stat, node) {
        printf("size %8zu count %8" PRIu64 " caller %p\n", s->size, s->count, s->caller);
    }

    if (next_unused_stat >= num_stats) {
        printf("WARNING: max number of unique records hit, some statistics were likely lost\n");
    }
}

} // namespace

void heap_init() {
    cmpct_init();
}

void heap_trim() {
    cmpct_trim();
}

void* malloc(size_t size) {
    DEBUG_ASSERT(!arch_blocking_disallowed());

    LTRACEF("size %zu\n", size);

    add_stat(__GET_CALLER(), size);

    void* ptr = cmpct_alloc(size);
    if (unlikely(heap_trace)) {
        printf("caller %p malloc %zu -> %p\n", __GET_CALLER(), size, ptr);
    }

    if (HEAP_PANIC_ON_ALLOC_FAIL && unlikely(!ptr)) {
        panic("malloc of size %zu failed\n", size);
    }

    return ptr;
}

void* malloc_debug_caller_(size_t size, void* caller) {
    DEBUG_ASSERT(!arch_blocking_disallowed());

    LTRACEF("size %zu\n", size);

    add_stat(caller, size);

    void* ptr = cmpct_alloc(size);
    if (unlikely(heap_trace)) {
        printf("caller %p malloc %zu -> %p\n", caller, size, ptr);
    }

    if (HEAP_PANIC_ON_ALLOC_FAIL && unlikely(!ptr)) {
        panic("malloc of size %zu failed\n", size);
    }

    return ptr;
}

void* memalign(size_t boundary, size_t size) {
    DEBUG_ASSERT(!arch_blocking_disallowed());

    LTRACEF("boundary %zu, size %zu\n", boundary, size);

    add_stat(__GET_CALLER(), size);

    void* ptr = cmpct_memalign(size, boundary);
    if (unlikely(heap_trace)) {
        printf("caller %p memalign %zu, %zu -> %p\n", __GET_CALLER(), boundary, size, ptr);
    }

    if (HEAP_PANIC_ON_ALLOC_FAIL && unlikely(!ptr)) {
        panic("memalign of size %zu align %zu failed\n", size, boundary);
    }

    return ptr;
}

void* calloc(size_t count, size_t size) {
    DEBUG_ASSERT(!arch_blocking_disallowed());

    LTRACEF("count %zu, size %zu\n", count, size);

    add_stat(__GET_CALLER(), size);

    size_t realsize = count * size;

    void* ptr = cmpct_alloc(realsize);
    if (likely(ptr)) {
        memset(ptr, 0, realsize);
    }
    if (unlikely(heap_trace)) {
        printf("caller %p calloc %zu, %zu -> %p\n", __GET_CALLER(), count, size, ptr);
    }
    return ptr;
}

void* realloc(void* ptr, size_t size) {
    DEBUG_ASSERT(!arch_blocking_disallowed());

    LTRACEF("ptr %p, size %zu\n", ptr, size);

    add_stat(__GET_CALLER(), size);

    void* ptr2 = cmpct_realloc(ptr, size);
    if (unlikely(heap_trace)) {
        printf("caller %p realloc %p, %zu -> %p\n", __GET_CALLER(), ptr, size, ptr2);
    }

    if (HEAP_PANIC_ON_ALLOC_FAIL && unlikely(!ptr2)) {
        panic("realloc of size %zu old ptr %p failed\n", size, ptr);
    }

    return ptr2;
}

void free(void* ptr) {
    DEBUG_ASSERT(!arch_blocking_disallowed());

    LTRACEF("ptr %p\n", ptr);
    if (unlikely(heap_trace)) {
        printf("caller %p free %p\n", __GET_CALLER(), ptr);
    }

    cmpct_free(ptr);
}

static void heap_dump(bool panic_time) {
    cmpct_dump(panic_time);
}

void heap_get_info(size_t* size_bytes, size_t* free_bytes) {
    cmpct_get_info(size_bytes, free_bytes);
}

static void heap_test() {
    cmpct_test();
}

void* heap_page_alloc(size_t pages) {
    DEBUG_ASSERT(pages > 0);

    list_node list = LIST_INITIAL_VALUE(list);

    paddr_t pa;
    zx_status_t status = pmm_alloc_contiguous(pages, 0, PAGE_SIZE_SHIFT, &pa, &list);
    if (status != ZX_OK) {
        return nullptr;
    }

    // mark all of the allocated page as HEAP
    vm_page_t *p, *temp;
    list_for_every_entry_safe (&list, p, temp, vm_page_t, queue_node) {
        list_delete(&p->queue_node);
        p->state = VM_PAGE_STATE_HEAP;
    }

    LTRACEF("pages %zu: pa %#lx, va %p\n", pages, pa, paddr_to_physmap(pa));

    return paddr_to_physmap(pa);
}

void heap_page_free(void* _ptr, size_t pages) {
    DEBUG_ASSERT(IS_PAGE_ALIGNED((uintptr_t)_ptr));
    DEBUG_ASSERT(pages > 0);

    LTRACEF("ptr %p, pages %zu\n", _ptr, pages);

    uint8_t* ptr = (uint8_t*)_ptr;

    list_node list;
    list_initialize(&list);

    while (pages > 0) {
        vm_page_t* p = paddr_to_vm_page(vaddr_to_paddr(ptr));
        if (p) {
            DEBUG_ASSERT(p->state == VM_PAGE_STATE_HEAP);
            DEBUG_ASSERT(!list_in_list(&p->queue_node));

            list_add_tail(&list, &p->queue_node);
        }

        ptr += PAGE_SIZE;
        pages--;
    }

    pmm_free(&list);
}

#if LK_DEBUGLEVEL > 1

#include <lib/console.h>

static int cmd_heap(int argc, const cmd_args* argv, uint32_t flags);

STATIC_COMMAND_START
STATIC_COMMAND_MASKED("heap", "heap debug commands", &cmd_heap, CMD_AVAIL_ALWAYS)
STATIC_COMMAND_END(heap);

static int cmd_heap(int argc, const cmd_args* argv, uint32_t flags) {
    if (argc < 2) {
    usage:
        printf("usage:\n");
        printf("\t%s info\n", argv[0].str);
        if (HEAP_COLLECT_STATS) {
            printf("\t%s stats\n", argv[0].str);
        }
        if (!(flags & CMD_FLAG_PANIC)) {
            printf("\t%s trace\n", argv[0].str);
            printf("\t%s trim\n", argv[0].str);
            printf("\t%s test\n", argv[0].str);
        }
        return -1;
    }

    if (strcmp(argv[1].str, "info") == 0) {
        heap_dump(flags & CMD_FLAG_PANIC);
    } else if (HEAP_COLLECT_STATS && strcmp(argv[1].str, "stats") == 0) {
        dump_stats();
    } else if (!(flags & CMD_FLAG_PANIC) && strcmp(argv[1].str, "test") == 0) {
        heap_test();
    } else if (!(flags & CMD_FLAG_PANIC) && strcmp(argv[1].str, "trace") == 0) {
        heap_trace = !heap_trace;
        printf("heap trace is now %s\n", heap_trace ? "on" : "off");
    } else if (!(flags & CMD_FLAG_PANIC) && strcmp(argv[1].str, "trim") == 0) {
        heap_trim();
    } else {
        printf("unrecognized command\n");
        goto usage;
    }

    return 0;
}

#endif