#define _GNU_SOURCE
#include "backtrace.h"
#include <execinfo.h>              // for backtrace, backtrace_symbols
#include <fcntl.h>                 // for open, O_CLOEXEC, O_RDONLY
#include <pthread.h>               // for pthread_mutex_lock, pthread_mute...
#include <spawn.h>                 // for posix_spawn_file_actions_t, posi...
#include <stddef.h>                // for ptrdiff_t
#include <stdio.h>                 // for snprintf, sscanf
#include <stdlib.h>                // for size_t, NULL, abort, free, strtoull
#include <string.h>                // for memset, strrchr
#include <sys/wait.h>              // for waitpid
#include <unistd.h>                // for close, read, pipe2, ssize_t, rea...
#include "simplest-defs.h"  // for NELEM, UNUSED
#include "sparse.h"         // for __force
#include "spew.h"           // for spew, SPEW_DEBUG, SPEW_INFO, SPE...

/* DO NOT USE ASSERT() IN THIS FILE, TO AVOID INFINITE RECURSION */
#ifdef ASSERT
#error CANNOT_USE_ASSERT_IN_THIS_FILE
#endif

// I'm using pthread_mutex_t rather than xthread_mutex_t because I cannot
// think of a better way to do this than with a static variable.  And with a
// static variable, I want to use PTHREAD_MUTEX_INITIALIZER, which there
// doesn't seem to have a xthread_mutex analogue.

static pthread_mutex_t backtrace_mutex = PTHREAD_MUTEX_INITIALIZER;

// Backtracer wants to fork an "addr2line" process to be able to translate
// code offsets into human-readable strings.  Back in the dark ages, we would
// do the fork whenever we wanted a backtrace.  That turned out to be too
// expensive, since fork() would copy huge page table (covering many gigabytes
// of memory), and it was silly because the exec() would just throw it away.
//
// Our next solution used a constructor/destructor.  At the beginning of the
// program we would start up the backtracer.  At that point in time the page
// table was small, and we didn't really care if it was expensive since
// nothing was really happening yet.  However we don't really like the
// constructor/destructor stuff, since it's fragile.  (And Matteo doesn't like
// it because it's a desugared version of C++ :-)
//
// This solution uses posix_spawnp() to do a fork/exec operation.
// posix_spawnp() lets you do some housekeeping (with dup2 and close
// operations) between the fork and the spawn.  Because the kernel gets all
// the information about the fork/dup/close/spawn sequence at once, it can
// avoid copying the page tables.  The performance of this sequence is about
// 200us to 500us.

struct backtracer {
    int    broken;          // true if something went wrong and the backtracer
                            // is failing.  Fall back to not printing
                            // backtraces, and try to keep running.
    pid_t  child;           // The addr2line process
    int    pipe_to_child;   // The write end of a pipe that goes the
                            // addr2line's stdin.
    int    pipe_from_child; // The read end of a pipe that comes from
                            // addr2line's stdout.
    size_t va_base;         // The offset to be subtracted from addresses to
                            // to ASLR.
};

static int __attribute__((warn_unused_result)) // NEGATIVE_ON_ERROR
sinit(posix_spawn_file_actions_t *file_actions)
// Effect: Initialize the file_actions.  If anything goes wrong return -1.
{
    int r = posix_spawn_file_actions_init(file_actions);
    if (r != 0) {
        spew(SPEW_DEBUG, "Cannot spawn_file_actions_init: r=%d", r);
        return -1;
    } else {
        return 0;
    }
 }

static int __attribute__((warn_unused_result)) // NEGATIVE_ON_ERROR
sdup2(posix_spawn_file_actions_t *file_actions, int from, int to)
// Effect: Record a dup2() operation to be done when posix_spawn runs.  If
// anything goes wrong, spew a diagnostic and return -1;
{
    int r = posix_spawn_file_actions_adddup2(file_actions, from, to);
    if (r != 0) {
        spew(SPEW_DEBUG, "Cannot spawn_fileactions_adddup2: r=%d", r);
        return -1;
    } else {
        return 0;
    }
}

static int __attribute__((warn_unused_result)) // NEGATIVE_ON_ERROR
sclose(posix_spawn_file_actions_t *file_actions, int fd)
// Effect: Record a close() operation to be cone when posix_spawn runs.  If
// anything goes wrong, spew a diagnostic and return -1;
{
    int r = posix_spawn_file_actions_addclose(file_actions, fd);
    if (r != 0) {
        spew(SPEW_DEBUG, "Cannot spawn_fileactions_addclose: r=%d", r);
        return -1;
    } else {
        return 0;
    }
}

static const struct backtracer errresult = {
    .pipe_to_child=-1, .pipe_from_child=-1, .child=0, .broken=1, .va_base = 0};

static struct backtracer
mk_backtracer(void) {
    // Only one backtracer may exist at a time (to prevent forkbombing if all
    // threads start backtracing.)  This mutex is unlocked when you destroy
    // the backtracer.
    pthread_mutex_lock(&backtrace_mutex);

    // Plumbing
    int tochildpipe[2];
    int fromchildpipe[2];
    {
        int r = pipe2(tochildpipe, O_CLOEXEC);
        if (r) {
            spew(SPEW_ERROR, "pipe2 failed");
        }
    }
    {
        int r = pipe2(fromchildpipe, O_CLOEXEC);
        if (r) {
            spew(SPEW_ERROR, "pipe2 failed");
        }
    }

    // Find the path to the current executable.  It's a symlink in
    // /proc/self/exe.

    char      exec_path[204];
    // readlink doesn't null terminate.  Fill it with zeros and tell it to
    // only use sizeof(exec_path)-1 to make sure there is a null at the
    // end.
    memset(exec_path, 0, sizeof(exec_path));
    ssize_t rc = readlink("/proc/self/exe", exec_path,
                          sizeof(exec_path)-1);
    UNUSED(rc);
    spew(SPEW_INFO, "exec path is %s", exec_path);

    // Set up to do the plumbing after the spawn.
    posix_spawn_file_actions_t file_actions;
    if (0
        || sinit(&file_actions)
        || sdup2(&file_actions, tochildpipe[0], 0)
        || sdup2(&file_actions, fromchildpipe[1], 1)
        || sclose(&file_actions, tochildpipe[0])
        || sclose(&file_actions, tochildpipe[1])
        || sclose(&file_actions, fromchildpipe[0])
        || sclose(&file_actions, fromchildpipe[1]))
    {
        return errresult;
    }
    pid_t child;
    {
        // Hack around because posix_spawnp doesn't have const's in quite the right place.
        char addr2line_s[] = "addr2line";
        char _e_s[]        = "-e";
        char _f_s[]        = "-f";
        char * const argv[] = {addr2line_s, _e_s, exec_path, _f_s, NULL};
        int r = posix_spawnp(&child, "addr2line",
                             &file_actions, NULL,
                             argv, environ);
        if (r != 0) {
            spew(SPEW_DEBUG, "Could not posix_spawnp r=%d", r);
            return errresult;
        }
    }
    {
        int r = posix_spawn_file_actions_destroy(&file_actions);
        if (r) spew(SPEW_FATAL, "Cannot destroy fail_actions r=%d", r);
    }

    // Plumbing back here the main program.
    struct backtracer result = {.broken = 0,
                                .child = child,
                                .pipe_to_child = tochildpipe[1],
                                .pipe_from_child = fromchildpipe[0],
                                .va_base         = 0};
    close(tochildpipe[0]);
    close(fromchildpipe[1]);

    // Find the va_base
    {
        int fd = open("/proc/self/maps", O_RDONLY);
        if (fd >= 0) {
            char addr_buffer[256];
            // HACK: we're going to assume that the first line in the
            // file contains the mapping for our executable.  Dynamic
            // libraries will be mapped in different locations, but we
            // don't really use any of them so our traceback should be
            // mostly correct.
            ssize_t bytes_read = read(fd, &addr_buffer, NELEM(addr_buffer)-1);
            if (bytes_read > 0) {
                addr_buffer[bytes_read] = 0;
                int rval = sscanf(addr_buffer, "%zx-", &result.va_base);
                if (rval != 1) {
                    result.va_base = 0;
                }
            }
        }
        close(fd);
    }
    spew(SPEW_INFO, "va_base is %zx", result.va_base);
    if (result.va_base < 0x800000) {
        // If ASLR is off, subtracting va_base makes offsets that addr2line
        // doesn't understand.  The best heuristic I've (jmp) found is that if
        // va_base is "low", then ASLR is off.  I haven't been able to figure
        // out if there's a "low" address under which ASLR is disabled, but
        // I've seen 4 MiB in many systems, so I'm going to claim any va_base
        // under 8 MiB is in a non-ASLR system.
        result.va_base = 0;
    }

    return result;
}

static void
backtracer_destroy(struct backtracer *bt) {
    close(bt->pipe_to_child);
    close(bt->pipe_from_child);
    spew(SPEW_INFO, "waitpid(%d)", bt->child);
    int wstatus;
    waitpid(bt->child, &wstatus, 0);
    spew(SPEW_INFO, "waitpid(%d) done wstatus=%d", bt->child, wstatus);
    *bt = errresult;
    pthread_mutex_unlock(&backtrace_mutex);
}

static void read_tail_of_line(int fd, char *line, size_t linelen)
// Effect: Read a line of data from fd into line.  If the line is too long to
//  fit, then put the last characters in so that if we read
//  "longfilename/fun.c:25" and linelen is 11 we end up with "e/fun.c:25"
//  rather than "longfilena".
//  line will always end NUL-terminated.
// Requires: linelen>0.  This function will fail unpredictably if linelen==0.
{
    for (size_t i = 0; i+1 < linelen; i++) {
        char c;
        ssize_t rr = read(fd, &c, 1);
        if (0 == rr || '\n' == c) {
            line[i] = 0;
            return;
        } else {
            line[i] = c;
        }
    }
    while (1) {
        char c;
        ssize_t rr = read(fd, &c, 1);
        if (0 == rr || '\n' == c) {
            line[linelen-1] = 0;
            return;
        } else {
            line[linelen-1] = c;
            // Shift the string left by 1.o
            for (size_t j = 0; j+1 < linelen; j++) {
                line[j] = line[j+1];
            }
        }
    }
}

static void spew_backtrace_symbol(struct backtracer *bt,
                                  const void *addr,
                                  const char *from_backtrace_symbol,
                                  size_t      spew_level)
{
    void *addr_from_base =  (void*)((__force size_t)addr
                                    - bt->va_base);
    char str_of_ptr[20];
    char fun_line[300] = "";
    char file_line[300] = "";
    if (!bt->broken) {
        int len = snprintf(str_of_ptr, sizeof(str_of_ptr),
                           "%p\n", addr_from_base);
        ssize_t wr = write(bt->pipe_to_child, str_of_ptr,
                           (__force size_t)(ptrdiff_t)len);
        int did_write = wr == len;
        if (!did_write) {
            bt->broken = 1;
        } else {
            read_tail_of_line(bt->pipe_from_child, fun_line, sizeof(fun_line));
            read_tail_of_line(bt->pipe_from_child, file_line, sizeof(file_line));
        }
    }
    if (!from_backtrace_symbol) {
        from_backtrace_symbol = "(unknown offset)";
    }
    const char* function = &fun_line[0];
    if (!fun_line[0]) {
        function = "(unknown function)";
    }
    size_t line_number = 0;
    const char* filename = &file_line[0];
    if (*filename) {
        // Find line number by looking for last : in file_line.
        char* line_number_start = strrchr(file_line, ':');
        if (line_number_start != NULL) {
            // Parse the line number
            line_number = strtoull(line_number_start + 1, NULL, 10);
            if (line_number > 0) {
                // Parsed, remove the line number and : from file_line.
                *line_number_start = 0;
            }
        }
    } else {
        // No filename, substitute backtrace symbol for filename.
        filename = from_backtrace_symbol;
        from_backtrace_symbol = "";
    }
    spew_for_backtrace(
        spew_level, filename, line_number, function, from_backtrace_symbol);
}

void spew_stored_backtrace(void *const*ptrs, int nptrs, size_t spew_level)
{
    char **strings = backtrace_symbols(ptrs, nptrs);

    struct backtracer bt = mk_backtracer();

    for (int j = 0; j < nptrs; j++) {
        spew_backtrace_symbol(&bt,
                              ptrs[(__force ptrdiff_t)j],
                              strings ? strings[(__force ptrdiff_t)j] : NULL,
                              spew_level);
    }

    backtracer_destroy(&bt);

    free(strings);
}

void spew_backtrace(size_t spew_level)
{
    if (spew_level < spew_get_level()) return;
    void *buffer[100];
    int nptrs = backtrace(buffer, (__force int)NELEM(buffer));

    /* cannot assert in this file */
    if (nptrs >= 0 && nptrs <= (__force int)NELEM(buffer)) {
        spew_stored_backtrace(buffer, nptrs, spew_level);
    } else {
        abort(); // can't happen
    }
}