mips: add native backtrace implementation

Should make debugging crashes on native MIPS targets far easier.
This is by no means a 100% complete or robust implementation but
it seems to handle the vast majority of functions.

Change-Id: Id5f430270e02b5092b79026b6876675c784aa649

9 files changed, 357 insertions, 3 deletions

diff --git a/firmware/export/backtrace.h b/firmware/export/backtrace.h
index 283e293b2a..fb007ab004 100644
--- a/firmware/export/backtrace.h
+++ b/firmware/export/backtrace.h
@@ -25,6 +25,9 @@
 #ifdef BACKTRACE_UNWARMINDER
 #include "backtrace-unwarminder.h"
 #endif
+#ifdef BACKTRACE_MIPSUNWINDER
+#include "backtrace-mipsunwinder.h"
+#endif
 
 /* Print a backtrace using lcd_* functions, starting at the given line and updating
  * the line number. On targets that support it (typically native targets), the
diff --git a/firmware/export/system.h b/firmware/export/system.h
index 9558be559a..def3122205 100644
--- a/firmware/export/system.h
+++ b/firmware/export/system.h
@@ -258,7 +258,8 @@ static inline void cpu_boost_unlock(void)
 #endif
 
 /* Define this if target has support for generating backtraces */
-#ifdef CPU_ARM
+#if defined(CPU_ARM) || \
+    (defined(CPU_MIPS) && (CONFIG_PLATFORM & PLATFORM_NATIVE))
     #define HAVE_RB_BACKTRACE
 #endif
 
diff --git a/firmware/panic.c b/firmware/panic.c
index fcfa8b2bb8..586ecb6e0a 100644
--- a/firmware/panic.c
+++ b/firmware/panic.c
@@ -32,9 +32,9 @@
 #include "system.h"
 #include "logf.h"
 
-#if defined(CPU_ARM)
+#ifdef HAVE_RB_BACKTRACE
 #include "gcc_extensions.h"
-#include <backtrace.h>
+#include "backtrace.h"
 #endif
 
 static char panic_buf[128];
@@ -65,6 +65,12 @@ void panicf_f( const char *fmt, ...)
                  );
 
     int pc = (int)__builtin_return_address(0);
+#elif defined(BACKTRACE_MIPSUNWINDER)
+void panicf( const char *fmt, ... )
+{
+    /* NOTE: these are obtained by the backtrace lib */
+    const int pc = 0;
+    const int sp = 0;
 #else
 void panicf( const char *fmt, ...)
 {
diff --git a/lib/mipsunwinder/SOURCES b/lib/mipsunwinder/SOURCES
new file mode 100644
index 0000000000..32fa57d157
--- /dev/null
+++ b/lib/mipsunwinder/SOURCES
@@ -0,0 +1,2 @@
+backtrace-mips32.c
+init_context_32.S
diff --git a/lib/mipsunwinder/backtrace-mips32.c b/lib/mipsunwinder/backtrace-mips32.c
new file mode 100644
index 0000000000..c5ab41e628
--- /dev/null
+++ b/lib/mipsunwinder/backtrace-mips32.c
@@ -0,0 +1,236 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * MIPS32 backtrace implementation
+ * Copyright (C) 2022 Aidan MacDonald
+ *
+ * References:
+ * https://yosefk.com/blog/getting-the-call-stack-without-a-frame-pointer.html
+ * https://elinux.org/images/6/68/ELC2008_-_Back-tracing_in_MIPS-based_Linux_Systems.pdf
+ * System V ABI MIPS Supplement, 3rd edition
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+#include "backtrace.h"
+#include "lcd.h"
+#include <stdint.h>
+#include <stdbool.h>
+#include <stdalign.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+#define MIN_ADDR    0x80000000ul
+#define MAX_ADDR    (MIN_ADDR + (MEMORYSIZE * 1024 * 1024) - 1)
+
+static bool read_check(const void* addr, size_t alignment)
+{
+    if(addr < (const void*)MIN_ADDR ||
+       addr > (const void*)MAX_ADDR)
+        return false;
+
+    if((uintptr_t)addr & (alignment - 1))
+        return false;
+
+    return true;
+}
+
+static bool read32(const void* addr, uint32_t* val)
+{
+    if(!read_check(addr, alignof(uint32_t)))
+        return false;
+
+    *val = *(const uint32_t*)addr;
+    return true;
+}
+
+#if 0
+static bool read16(const void* addr, uint16_t* val)
+{
+    if(!read_check(addr, alignof(uint16_t)))
+        return false;
+
+    *val = *(const uint16_t*)addr;
+    return true;
+}
+
+static bool read8(const void* addr, uint8_t* val)
+{
+    if(!read_check(addr, alignof(uint8_t)))
+        return false;
+
+    *val = *(const uint8_t*)addr;
+    return true;
+}
+#endif
+
+static long extract_s16(uint32_t val)
+{
+#if 1
+    /* not ISO C, but gets GCC to emit 'seh' which is more compact */
+    return (int32_t)(val << 16) >> 16;
+#else
+    val &= 0xffff;
+
+    if(val > 0x7fff)
+        return (long)val - 0x10000l;
+    else
+        return val;
+#endif
+}
+
+/* TODO - cases not handled by the backtrace algorithm
+ *
+ * 1. functions that save the frame pointer will not be handled correctly
+ *    (need to implement the algorithm specified by the System V ABI).
+ *
+ * 2. GCC can generate functions with a "false" stack pointer decrement,
+ *    for some examples see read_bmp_fd and walk_path. those functions
+ *    seem to be more difficult to deal with and the SysV algorithm will
+ *    also get confused by them, but they are not common.
+ */
+int mips_bt_step(struct mips_bt_context* ctx)
+{
+    /* go backward and look for the stack pointer decrement */
+    uint32_t* pc = ctx->pc;
+    uint32_t insn;
+    long sp_off;
+
+    while(true) {
+        if(!read32(pc, &insn))
+            return 0;
+
+        /* addiu sp, sp, sp_off */
+        if((insn >> 16) == 0x27bd) {
+            sp_off = extract_s16(insn);
+            if(sp_off < 0)
+                break;
+        }
+
+        /* jr ra */
+        if(insn == 0x03e00008) {
+            /* end if this is not a leaf or we lack register info */
+            if(ctx->depth > 0 || !(ctx->valid & (1 << MIPSBT_RA))) {
+                mips_bt_debug(ctx, "unexpected leaf function");
+                return 0;
+            }
+
+            /* this is a leaf function - ra contains the return address
+             * and sp is unchanged */
+            ctx->pc = (void*)ctx->reg[MIPSBT_RA] - 8;
+            ctx->depth++;
+            return 1;
+        }
+
+        --pc;
+    }
+
+    mips_bt_debug(ctx, "found sp_off=%ld at %p", sp_off, pc);
+
+    /* now go forward and find the saved return address */
+    while((void*)pc < ctx->pc) {
+        if(!read32(pc, &insn))
+            return 0;
+
+        /* sw ra, ra_off(sp) */
+        if((insn >> 16) == 0xafbf) {
+            long ra_off = extract_s16(insn);
+            uint32_t save_ra;
+
+            /* load the saved return address */
+            mips_bt_debug(ctx, "load ra from %p+%ld", ctx->sp, ra_off);
+            if(!read32(ctx->sp + ra_off, &save_ra))
+                return 0;
+
+            if(save_ra == 0) {
+                mips_bt_debug("hit root");
+                return 0;
+            }
+
+            /* update bt context */
+            ctx->pc = (void*)save_ra - 8;
+            ctx->sp -= sp_off;
+
+            /* update saved register info */
+            ctx->reg[MIPSBT_RA] = save_ra;
+            ctx->valid |= (1 << MIPSBT_RA);
+
+            ctx->depth++;
+            return 1;
+        }
+
+        ++pc;
+    }
+
+    /* sometimes an exception occurs before ra is saved - in this case
+     * the ra register should contain the caller PC, but we still need
+     * to adjust the stack frame. */
+    if(ctx->depth == 0 && (ctx->valid & (1 << MIPSBT_RA))) {
+        ctx->pc = (void*)ctx->reg[MIPSBT_RA] - 8;
+        ctx->sp -= sp_off;
+
+        ctx->depth++;
+        return 1;
+    }
+
+    mips_bt_debug(ctx, "ra not found");
+    return 0;
+}
+
+#ifdef MIPSUNWINDER_DEBUG
+static void rb_backtrace_debugf(void* arg, const char* fmt, ...)
+{
+    static char buf[64];
+    va_list ap;
+    va_start(ap, fmt);
+    vsnprintf(buf, sizeof(buf), fmt, ap);
+    va_end(ap);
+
+    unsigned int* line = arg;
+    lcd_putsf(4, (*line)++, "%s", buf);
+    lcd_update();
+}
+#endif
+
+void rb_backtrace_ctx(void* arg, unsigned* line)
+{
+    struct mips_bt_context* ctx = arg;
+#ifdef MIPSUNWINDER_DEBUG
+    ctx->debugf = rb_backtrace_debugf;
+    ctx->debug_arg = line;
+#endif
+
+    do {
+        lcd_putsf(0, (*line)++, "%02d pc:%08lx sp:%08lx",
+                  ctx->depth, (unsigned long)ctx->pc, (unsigned long)ctx->sp);
+        lcd_update();
+    } while(mips_bt_step(ctx));
+
+    lcd_puts(0, (*line)++, "bt end");
+    lcd_update();
+}
+
+void rb_backtrace(int pcAddr, int spAddr, unsigned* line)
+{
+    (void)pcAddr;
+    (void)spAddr;
+
+    struct mips_bt_context ctx;
+    mips_bt_start(&ctx);
+    mips_bt_step(&ctx); /* step over this function */
+
+    rb_backtrace_ctx(&ctx, line);
+}
diff --git a/lib/mipsunwinder/backtrace-mipsunwinder.h b/lib/mipsunwinder/backtrace-mipsunwinder.h
new file mode 100644
index 0000000000..4d6288b5fe
--- /dev/null
+++ b/lib/mipsunwinder/backtrace-mipsunwinder.h
@@ -0,0 +1,65 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * Copyright (C) 2022 Aidan MacDonald
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+#ifndef BACKTRACE_MIPSUNWINDER_H
+#define BACKTRACE_MIPSUNWINDER_H
+
+/*#define MIPSUNWINDER_DEBUG*/
+
+#include <stdint.h>
+
+enum {
+    MIPSBT_RA,
+    MIPSBT_NREG,
+};
+
+struct mips_bt_context {
+    void* pc;
+    void* sp;
+    int depth;
+    uint32_t valid;
+    uint32_t reg[MIPSBT_NREG];
+#ifdef MIPSUNWINDER_DEBUG
+    void(*debugf)(void*, const char*, ...);
+    void* debug_arg;
+#endif
+};
+
+int mips_bt_step(struct mips_bt_context* ctx);
+void mips_bt_start(struct mips_bt_context* ctx);
+
+#ifdef MIPSUNWINDER_DEBUG
+# define mips_bt_debug(ctx, ...) \
+    do { struct mips_bt_context* __ctx = ctx; \
+         if(__ctx->debugf) \
+             __ctx->debugf(__ctx->debug_arg, __VA_ARGS__);\
+    } while(0)
+#else
+# define mips_bt_debug(...) do { } while(0)
+#endif
+
+/* NOTE: ignores pcAddr and spAddr, backtrace starts from caller */
+void rb_backtrace(int pcAddr, int spAddr, unsigned* line);
+
+/* given struct mips_bt_context argument, print stack traceback */
+void rb_backtrace_ctx(void* arg, unsigned* line);
+
+#endif /* BACKTRACE_MIPSUNWINDER_H */
diff --git a/lib/mipsunwinder/init_context_32.S b/lib/mipsunwinder/init_context_32.S
new file mode 100644
index 0000000000..a943d13dc3
--- /dev/null
+++ b/lib/mipsunwinder/init_context_32.S
@@ -0,0 +1,12 @@
+#include "mips.h"
+
+    .text
+    .global mips_bt_start
+
+mips_bt_start:
+    addiu   v0, ra, -8
+    sw      v0, 0(a0)       /* ctx->pc = ra - 8 */
+    sw      sp, 4(a0)       /* ctx->sp = sp */
+    sw      zero, 8(a0)     /* ctx->depth = 0 */
+    sw      zero, 12(a0)    /* ctx->valid = 0 */
+    jr      ra
diff --git a/lib/mipsunwinder/mipsunwinder.make b/lib/mipsunwinder/mipsunwinder.make
new file mode 100644
index 0000000000..ddd1ce078f
--- /dev/null
+++ b/lib/mipsunwinder/mipsunwinder.make
@@ -0,0 +1,23 @@
+#             __________               __   ___.
+#   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+#   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+#   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+#   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+#                     \/            \/     \/    \/            \/
+#
+
+MIPSUNWINDERLIB_DIR = $(ROOTDIR)/lib/mipsunwinder
+MIPSUNWINDERLIB_SRC = $(call preprocess, $(MIPSUNWINDERLIB_DIR)/SOURCES)
+MIPSUNWINDERLIB_OBJ := $(call c2obj, $(MIPSUNWINDERLIB_SRC))
+
+OTHER_SRC += $(MIPSUNWINDERLIB_SRC)
+
+MIPSUNWINDERLIB = $(BUILDDIR)/lib/libmipsunwinder.a
+CORE_LIBS += $(MIPSUNWINDERLIB)
+
+INCLUDES += -I$(MIPSUNWINDERLIB_DIR)
+DEFINES += -DBACKTRACE_MIPSUNWINDER
+
+$(MIPSUNWINDERLIB): $(MIPSUNWINDERLIB_OBJ)
+	$(SILENT)$(shell rm -f $@)
+	$(call PRINTS,AR $(@F))$(AR) rcs $@ $^ >/dev/null
diff --git a/tools/root.make b/tools/root.make
index 2a83a32292..03c4d48986 100644
--- a/tools/root.make
+++ b/tools/root.make
@@ -75,6 +75,12 @@ ifeq (,$(findstring checkwps,$(APP_TYPE)))
             include $(ROOTDIR)/lib/unwarminder/unwarminder.make
           endif
       endif
+      ifeq (arch_mips,$(ARCH))
+          # mips unwinder is only usable on native ports
+          ifeq (,$(APP_TYPE))
+            include $(ROOTDIR)/lib/mipsunwinder/mipsunwinder.make
+          endif
+      endif
       ifeq (,$(findstring bootloader,$(APPSDIR)))
         include $(ROOTDIR)/lib/skin_parser/skin_parser.make
         include $(ROOTDIR)/lib/tlsf/libtlsf.make