% Copyright © 2008 Pippijn van Steenhoven
% You can redistribute this file under the terms of the GNU Affero General
% Public License version 3 or later. As a special exception, you may use
% this file as part of a differently licensed work provided the other
% license does not violate section 6 of the GNU AGPL. See COPYING.AGPL
% for more information.

This file implements backtraces using a GNU extension. Unlike the
[[soft_trace]] facility also provided by \rona, this backtrace causes zero
overhead and will include \emph{all} functions in the call stack.

<<*>>=
<<headers>>
<<constant definitions>>
<<static definitions>>
<<addr2line caller>>


@
We can not support an arbitrary number of calls in the backtrace. GNU libc
requires a pre-allocated pointer array to put its trace pointers in.
The [[BACKTRACE_MAX]] constant is a compile-time setting, so we can allocate
the pointer array on the stack. Note that backtraces may (and probably will)
be called on caught signals. Therefore, client code needs to make sure the
stack is not overflown here. At least $[[BACKTRACE_MAX]] * sizeof (void *)$
must be allocated for the signal handler. This can be done using
[[sigaction(2)]].

[[ADDR2LINE_MAX]] is the maximum number of calls to the [[addr2line]] utility.
We limit this, because each call takes quite a lot of time.

<<constant definitions>>=
#define BACKTRACE_MAX 1024
#define ADDR2LINE_MAX 128


@
If the environment [[RONA_ADDRONLY]] is set to anything, no calls to
[[addr2line]] are made, the backtrace is faster and possibly more reliable,
but much less useful.

<<static definitions>>=
static bool const addronly = std::getenv ("RONA_ADDRONLY");


@
This function displays function name and line with a backtrace address. It
uses the [[addr2line]] command line tool to determine symbolic function names
from an address. The [[number]] is the number to be printed in front of a line
of backtrace.

We need to be careful with stack allocations, but we can't do any heap
allocations, so we allocate a small amount of memory for these. The address
list in [[print_backtrace]] is already using a lot.

<<addr2line caller>>=
static void
backtrace_addr2line (int number, void *address, char *symbol)
{
#ifdef HAVE_BACKTRACE
  Dl_info info;
  char cmd_line[64];
  char function_name[16] = { 0 };
  int rc;

  <<Find the name and file of a function pointer>>

  void const *addr = address;
  if (info.dli_fbase >= (void const *) 0x40000000)
    addr = (void *) ((unsigned long) ((char const *) addr)
                     - (unsigned long) info.dli_fbase);

  <<Call addr2line>>

  <<Read output from addr2line>>

  if (function_name[0])
    std::fprintf (stderr, "%04d  %s\n", number, function_name);
  pclose (output);
#endif
}

/**
 * display backtrace (called when a SIGSEGV is received)
 */
static char const *
get_backtrace ()
{
  // we use a static buffer because we might be called in a stack overflow
  static char buf[BUFSIZ] = { 0 };
  char *ptr = buf;
  std::size_t i = 0;

  // Did our program build its stack trace?
  rona::adt::podvector<Trace>::const_iterator it = stack_trace.begin ();
  rona::adt::podvector<Trace>::const_iterator et = stack_trace.end ();

  while (it != et)
    {
      --et;
      ptr += snprintf (ptr, sizeof (buf) - (ptr - buf) - 1,
                       "%04lu  %s:%s [function %s]\n",
                       ++i,
                       et->file,
                       et->line,
                       et->func);
    }

  return buf;
}

void
print_backtrace ()
{
  std::fprintf (stderr, "======= Rona backtrace =======\n");
  std::fprintf (stderr, "(compiled on %s %s)\n",
                        __DATE__, __TIME__);

  if (!stack_trace.empty ())
    {
      <<Print soft backtrace>>
    }
  else
    {
      <<Print glibc backtrace>>
    }

  fputs ("======= End of backtrace =======\n", stderr);
}


<<Print soft backtrace>>=
std::string const &bt = get_backtrace ();
std::fwrite (bt.data (), 1, bt.length (), stderr);


<<Print glibc backtrace>>=
#ifdef HAVE_BACKTRACE
void *trace[BACKTRACE_MAX];

int const trace_size = backtrace (trace, BACKTRACE_MAX);
// This calls malloc (), which may fail in case the backtrace is formed
// in OOM situations. TODO: use backtrace_symbols_fd to fix this?
char **symbols = backtrace_symbols (trace, trace_size);

if (!symbols)
  {
    fputs ("*** Error: allocation failed in backtrace_symbols ()", stderr);
    return;
  }

if (trace_size <= ADDR2LINE_MAX && addronly)
  {
    for (int i = 0; i < trace_size; i++)
      std::fprintf (stderr, "%04d  %p:%p\n", i + 1, trace[i], symbols[i]);
  }
else
  {
    struct
    {
      void *trace;
      char *symbol;
    } history[5] = {
      { 0, 0 },
      { 0, 0 },
      { 0, 0 },
      { 0, 0 },
      { 0, 0 }
    };
    int count = 0;
    for (int i = 0; i < trace_size; i++)
      {
        if (addronly)
          std::fprintf (stderr, "%04d  %p:%p\n", i + 1, trace[i], symbols[i]);
        else
          {
            history[0] = history[1];
            history[1] = history[2];
            history[2] = history[3];
            history[3] = history[4];
            history[4].trace  = trace[i];
            history[4].symbol = symbols[i];
            if (   history[0].trace == history[1].trace
                && history[1].trace == history[2].trace
                && history[2].trace == history[3].trace
                && history[3].trace == history[4].trace)
              {
                ++count;
                continue;
              }
            if (i == ADDR2LINE_MAX / 2)
              {
                std::fprintf (stderr, "*** Too deep call nesting, skipping %d ***\n", trace_size - ADDR2LINE_MAX);
                i = trace_size - ADDR2LINE_MAX / 2;
              }
            if (count)
              {
                std::fprintf (stderr, "*** Too deep recursion, skipping %d equal traces ***\n", count);
                backtrace_addr2line (i + 1, history[3].trace, history[3].symbol);
                count = 0;
              }
            backtrace_addr2line (i + 1, trace[i], symbols[i]);
          }
      }
  }

#else
fputs ("  No backtrace info (no debug info available or no backtrace possible on your system).\n", stderr);
#endif

@
This uses the GNU extension function [[dladdr]].

<<Find the name and file of a function pointer>>=
rc = dladdr (address, &info);
if ((rc == 0) || !info.dli_fname || !info.dli_fname[0])
  {
    std::fprintf (stderr, "%04d  %s\n", number, symbol);
    return;
  }


@
Here, we call addr2line with the filename and address of this function. Note
that this will fail if the filename has a backtick (`) in it, because we use
the backtick evaluation function of [[sh]]. In [[bash]], we could solve it
with the [[$(command)]] syntax, but we don't want to rely on [[bash]] to be
present. Also, it would then fail if a filename had a closing parenthesis in
it. If running [[addr2line]] fails, we simply print out the number and symbol
name of the function.

<<Call addr2line>>=
snprintf (cmd_line, sizeof (cmd_line),
          "addr2line --functions --demangle -e `which %s` %p",
          info.dli_fname, addr);
FILE *output = popen (cmd_line, "r");
if (!output)
  {
    std::fprintf (stderr, "%04d  %s\n", number, symbol);
    return;
  }


<<Read output from addr2line>>=
while (!feof (output))
  {
    char line[BUFSIZ];
    char *ptr_line = std::fgets (line, sizeof (line) - 1, output);
    if (ptr_line && ptr_line[0])
      {
        char *pos = std::strchr (ptr_line, '\n');
        if (pos)
          pos[0] = '\0';
        if (std::strchr (ptr_line, ':'))
          {
            std::fprintf (stderr, "%04d  %s%s%s%s\n",
                                  number,
                                  ptr_line,
                                  (function_name[0]) ? " [function " :
                                  "", function_name,
                                  (function_name[0]) ? "]" : "");
            function_name[0] = '\0';
          }
        else
          {
            if (function_name[0])
              std::fprintf (stderr, "%04d  %s", number, function_name);
            snprintf (function_name, sizeof (function_name),
                      "%s", ptr_line);
          }
      }
  }

<<headers>>=
#include <cstddef>
#include <cstdlib>
#include <cstdarg>

#include <rona/trace.h>
#include <rona/pp/initially.h>

#ifdef HAVE_EXECINFO_H
# include <execinfo.h>
#endif
#ifdef HAVE_DLFCN_H
# include <dlfcn.h>
#endif