/*	$NetBSD: mips_stacktrace.c,v 1.9 2021/04/06 13:11:22 simonb Exp $	*/

/*
 * Copyright (c) 1988 University of Utah.
 * Copyright (c) 1992, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * the Systems Programming Group of the University of Utah Computer
 * Science Department and Ralph Campbell.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * from: NetBSD: trap.c,v 1.255 2020/07/13 09:00:40 simonb Exp
 * from: Utah Hdr: trap.c 1.32 91/04/06
 *
 *	@(#)trap.c	8.5 (Berkeley) 1/11/94
 */

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: mips_stacktrace.c,v 1.9 2021/04/06 13:11:22 simonb Exp $");

#ifdef _KERNEL_OPT
#include "opt_ddb.h"
#include "opt_kgdb.h"
#endif

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/proc.h>

#include <mips/locore.h>
#include <mips/mips_opcode.h>
#include <mips/regnum.h>
#include <mips/stacktrace.h>

#if defined(_KMEMUSER) && !defined(DDB)
#define DDB 1
#endif

#ifdef DDB
#include <machine/db_machdep.h>
#include <ddb/db_sym.h>
#include <ddb/db_user.h>
#include <ddb/db_access.h>
#endif

#ifdef KGDB
#include <sys/kgdb.h>
#endif

#ifndef DDB_TRACE

#if defined(DEBUG) || defined(DDB) || defined(KGDB) || defined(geo)

extern char start[], edata[], verylocore[];
#ifdef MIPS1
extern char mips1_kern_gen_exception[];
extern char mips1_user_gen_exception[];
extern char mips1_kern_intr[];
extern char mips1_user_intr[];
extern char mips1_systemcall[];
#endif
#ifdef MIPS3
extern char mips3_kern_gen_exception[];
extern char mips3_user_gen_exception[];
extern char mips3_kern_intr[];
extern char mips3_user_intr[];
extern char mips3_systemcall[];
#endif
#ifdef MIPS32
extern char mips32_kern_gen_exception[];
extern char mips32_user_gen_exception[];
extern char mips32_kern_intr[];
extern char mips32_user_intr[];
extern char mips32_systemcall[];
#endif
#ifdef MIPS32R2
extern char mips32r2_kern_gen_exception[];
extern char mips32r2_user_gen_exception[];
extern char mips32r2_kern_intr[];
extern char mips32r2_user_intr[];
extern char mips32r2_systemcall[];
#endif
#ifdef MIPS64
extern char mips64_kern_gen_exception[];
extern char mips64_user_gen_exception[];
extern char mips64_kern_intr[];
extern char mips64_user_intr[];
extern char mips64_systemcall[];
#endif
#ifdef MIPS64R2
extern char mips64r2_kern_gen_exception[];
extern char mips64r2_user_gen_exception[];
extern char mips64r2_kern_intr[];
extern char mips64r2_user_intr[];
extern char mips64r2_systemcall[];
#endif

#define	MIPS_JR_RA	0x03e00008	/* instruction code for jr ra */
#define	MIPS_JR_K0	0x03400008	/* instruction code for jr k0 */
#define	MIPS_ERET	0x42000018	/* instruction code for eret */

int main(void *);	/* XXX */

/*
 * Functions ``special'' enough to print by name
 */
#define Name(_fn)  { (void*)_fn, # _fn }
static const struct { void *addr; const char *name;} names[] = {
#ifdef _KERNEL
	Name(stacktrace),
	Name(stacktrace_subr),
	Name(main),
	Name(trap),

#ifdef MIPS1	/*  r2000 family  (mips-I CPU) */
	Name(mips1_kern_gen_exception),
	Name(mips1_user_gen_exception),
	Name(mips1_systemcall),
	Name(mips1_kern_intr),
	Name(mips1_user_intr),
#endif	/* MIPS1 */

#if defined(MIPS3)			/* r4000 family (mips-III CPU) */
	Name(mips3_kern_gen_exception),
	Name(mips3_user_gen_exception),
	Name(mips3_systemcall),
	Name(mips3_kern_intr),
	Name(mips3_user_intr),
#endif	/* MIPS3 */

#if defined(MIPS32)			/* MIPS32 family (mips-III CPU) */
	Name(mips32_kern_gen_exception),
	Name(mips32_user_gen_exception),
	Name(mips32_systemcall),
	Name(mips32_kern_intr),
	Name(mips32_user_intr),
#endif	/* MIPS32 */

#if defined(MIPS32R2)			/* MIPS32R2 family (mips-III CPU) */
	Name(mips32r2_kern_gen_exception),
	Name(mips32r2_user_gen_exception),
	Name(mips32r2_systemcall),
	Name(mips32r2_kern_intr),
	Name(mips32r2_user_intr),
#endif	/* MIPS32R2 */

#if defined(MIPS64)			/* MIPS64 family (mips-III CPU) */
	Name(mips64_kern_gen_exception),
	Name(mips64_user_gen_exception),
	Name(mips64_systemcall),
	Name(mips64_kern_intr),
	Name(mips64_user_intr),
#endif	/* MIPS64 */

#if defined(MIPS64R2)			/* MIPS64R2 family (mips-III CPU) */
	Name(mips64r2_kern_gen_exception),
	Name(mips64r2_user_gen_exception),
	Name(mips64r2_systemcall),
	Name(mips64r2_kern_intr),
	Name(mips64r2_user_intr),
#endif	/* MIPS64R2 */

	Name(cpu_idle),
	Name(cpu_switchto),
#endif /* _KERNEL */
	{0, 0}
};


bool
kdbpeek(vaddr_t addr, unsigned *valp)
{
	if (addr & 3) {
		printf("kdbpeek: unaligned address %#"PRIxVADDR"\n", addr);
		/* We might have been called from DDB, so do not go there. */
		return false;
	} else if (addr == 0) {
		printf("kdbpeek: NULL\n");
		return false;
	} else {
#if _KERNEL
		*valp = *(unsigned *)addr;
#else
		db_read_bytes((db_addr_t)addr, sizeof(unsigned), (char *)valp);
#endif
		return true;
	}
}

mips_reg_t
kdbrpeek(vaddr_t addr, size_t n)
{
	mips_reg_t rc = 0;

	if (addr & (n - 1)) {
		printf("kdbrpeek: unaligned address %#"PRIxVADDR"\n", addr);
#if _KERNEL
		/* We might have been called from DDB, so do not go there. */
		stacktrace();
#endif
		rc = -1;
	} else if (addr == 0) {
		printf("kdbrpeek: NULL\n");
		rc = 0xdeadfeed;
	} else {
		if (sizeof(mips_reg_t) == 8 && n == 8)
#if _KERNEL
			rc = *(int64_t *)addr;
 		else
			rc = *(int32_t *)addr;
#else
			db_read_bytes((db_addr_t)addr, sizeof(int64_t), (char *)&rc);
		else
			db_read_bytes((db_addr_t)addr, sizeof(int32_t), (char *)&rc);
#endif
	}
	return rc;
}

/*
 * Map a function address to a string name, if known; or a hex string.
 */
static const char *
fn_name(vaddr_t addr)
{
	static char buf[17];
	int i = 0;
#ifdef DDB
	db_expr_t diff;
	db_sym_t sym;
	const char *symname;
#endif

#ifdef DDB
	diff = 0;
	symname = NULL;
	sym = db_search_symbol(addr, DB_STGY_ANY, &diff);
	db_symbol_values(sym, &symname, 0);
	if (symname && diff == 0)
		return (symname);
#endif
	for (i = 0; names[i].name; i++)
		if (names[i].addr == (void*)addr)
			return (names[i].name);
	snprintf(buf, sizeof(buf), "%#"PRIxVADDR, addr);
	return (buf);
}

/*
 * Do a stack backtrace.
 * (*printfn)()  prints the output to either the system log,
 * the console, or both.
 */
void
stacktrace_subr(mips_reg_t a0, mips_reg_t a1, mips_reg_t a2, mips_reg_t a3,
    vaddr_t pc, vaddr_t sp, vaddr_t fp, vaddr_t ra,
    void (*printfn)(const char*, ...))
{
	vaddr_t va, subr;
	unsigned instr, mask;
	InstFmt i;
	int more, stksize;
	unsigned int frames =  0;
	int foundframesize = 0;
	mips_reg_t regs[32] = {
		[_R_ZERO] = 0,
		[_R_A0] = a0, [_R_A1] = a1, [_R_A2] = a2, [_R_A3] = a3,
		[_R_RA] = ra,
	};

/* Jump here when done with a frame, to start a new one */
loop:
	stksize = 0;
	subr = 0;
	mask = 1;
	if (frames++ > 100) {
		(*printfn)("\nstackframe count exceeded\n");
		/* return breaks stackframe-size heuristics with gcc -O2 */
		goto finish;	/*XXX*/
	}

	/* check for bad SP: could foul up next frame */
	if ((sp & (sizeof(sp)-1)) || (intptr_t)sp >= 0) {
		(*printfn)("SP 0x%x: not in kernel\n", sp);
		ra = 0;
		subr = 0;
		goto done;
	}

	/* Check for bad PC */
	if (pc & 3 || (intptr_t)pc >= 0 || (intptr_t)pc >= (intptr_t)edata) {
		(*printfn)("PC 0x%x: not in kernel space\n", pc);
		ra = 0;
		goto done;
	}

#if defined(DDB) && defined(_KERNEL)
	if (ksyms_available()) {
		db_expr_t diff;
		db_sym_t sym;

		/*
		 * Check the kernel symbol table to see the beginning of
		 * the current subroutine.
		 */
		diff = 0;
		sym = db_search_symbol(pc, DB_STGY_ANY, &diff);
		if (sym != DB_SYM_NULL && diff == 0) {
			/* check func(foo) __attribute__((__noreturn__)) case */
			if (!kdbpeek(pc - 2 * sizeof(unsigned), &instr))
				return;
			i.word = instr;
			if (i.JType.op == OP_JAL) {
				sym = db_search_symbol(pc - sizeof(int),
				    DB_STGY_ANY, &diff);
				if (sym != DB_SYM_NULL && diff != 0)
					diff += sizeof(int);
			}
		}
		if (sym == DB_SYM_NULL) {
			ra = 0;
			goto done;
		}
		va = pc - diff;
	} else {
#endif /* DDB && _KERNEL */
		/*
		 * Find the beginning of the current subroutine by
		 * scanning backwards from the current PC for the end
		 * of the previous subroutine.
		 *
		 * XXX This won't work well because nowadays gcc is so
		 *     aggressive as to reorder instruction blocks for
		 *     branch-predict. (i.e. 'jr ra' wouldn't indicate
		 *     the end of subroutine)
		 */
		va = pc;
		do {
			va -= sizeof(int);
#ifdef _KERNEL /* XXX crash */
			if (va <= (vaddr_t)verylocore)
				goto finish;
#endif
			if (!kdbpeek(va, &instr))
				return;
			if (instr == MIPS_ERET)
				goto mips3_eret;
		} while (instr != MIPS_JR_RA && instr != MIPS_JR_K0);
		/* skip back over branch & delay slot */
		va += sizeof(int);
mips3_eret:
		va += sizeof(int);
		/* skip over nulls which might separate .o files */
		instr = 0;
		while (instr == 0) {
			if (!kdbpeek(va, &instr))
				return;
			va += sizeof(int);
		}
#if defined(DDB) && defined(_KERNEL)
	}
#endif /* DDB && _KERNEL */
	subr = va;

	/* scan forwards to find stack size and any saved registers */
	stksize = 0;
	more = 3;
	mask &= 0x40ff0001;	/* if s0-s8 are valid, leave then as valid */
	foundframesize = 0;
	for (va = subr; more; va += sizeof(int),
			      more = (more == 3) ? 3 : more - 1) {
		/* stop if hit our current position */
		if (va >= pc)
			break;
		if (!kdbpeek(va, &instr))
			return;
		i.word = instr;
		switch (i.JType.op) {
		case OP_SPECIAL:
			switch (i.RType.func) {
			case OP_JR:
			case OP_JALR:
				more = 2; /* stop after next instruction */
				break;

			case OP_ADD:
			case OP_ADDU:
			case OP_DADD:
			case OP_DADDU:
				if (!(mask & (1 << i.RType.rd))
				    || !(mask & (1 << i.RType.rt)))
					break;
				if (i.RType.rd != _R_ZERO)
					break;
				mask |= (1 << i.RType.rs);
				regs[i.RType.rs] = regs[i.RType.rt];
				if (i.RType.func >= OP_DADD)
					break;
				regs[i.RType.rs] = (int32_t)regs[i.RType.rs];
				break;

			case OP_SYSCALL:
			case OP_BREAK:
				more = 1; /* stop now */
				break;
			}
			break;

		case OP_REGIMM:
		case OP_J:
		case OP_JAL:
		case OP_BEQ:
		case OP_BNE:
		case OP_BLEZ:
		case OP_BGTZ:
			more = 2; /* stop after next instruction */
			break;

		case OP_COP0:
		case OP_COP1:
		case OP_COP2:
		case OP_COP3:
			switch (i.RType.rs) {
			case OP_BCx:
			case OP_BCy:
				more = 2; /* stop after next instruction */
			};
			break;

		case OP_SW:
#if !defined(__mips_o32)
		case OP_SD:
#endif
		{
			size_t size = (i.JType.op == OP_SW) ? 4 : 8;

			/* look for saved registers on the stack */
			if (i.IType.rs != _R_SP)
				break;
			switch (i.IType.rt) {
			case _R_A0: /* a0 */
			case _R_A1: /* a1 */
			case _R_A2: /* a2 */
			case _R_A3: /* a3 */
			case _R_S0: /* s0 */
			case _R_S1: /* s1 */
			case _R_S2: /* s2 */
			case _R_S3: /* s3 */
			case _R_S4: /* s4 */
			case _R_S5: /* s5 */
			case _R_S6: /* s6 */
			case _R_S7: /* s7 */
			case _R_S8: /* s8 */
			case _R_RA: /* ra */
				regs[i.IType.rt] =
				    kdbrpeek(sp + (int16_t)i.IType.imm, size);
				mask |= (1 << i.IType.rt);
				break;
			}
			break;
		}

		case OP_ADDI:
		case OP_ADDIU:
#if !defined(__mips_o32)
		case OP_DADDI:
		case OP_DADDIU:
#endif
			/* look for stack pointer adjustment */
			if (i.IType.rs != _R_SP || i.IType.rt != _R_SP)
				break;
			/* don't count pops for mcount */
			if (!foundframesize) {
				stksize = - ((short)i.IType.imm);
				foundframesize = 1;
			}
			break;
		}
	}
done:
	if (mask & (1 << _R_RA))
		ra = regs[_R_RA];
	(*printfn)("%#"PRIxVADDR": %s+%#"PRIxVADDR" (%#"PRIxREGISTER","
	    "%#"PRIxREGISTER",%#"PRIxREGISTER",%#"PRIxREGISTER") "
	    "ra %#"PRIxVADDR" sz %d\n",
	    sp, fn_name(subr), pc - subr,
	    regs[_R_A0], regs[_R_A1], regs[_R_A2], regs[_R_A3],
	    ra, stksize);

	if (ra) {
		if (pc == ra && stksize == 0)
			(*printfn)("stacktrace: loop!\n");
		else {
			pc = ra;
			sp += stksize;
			ra = 0;
			goto loop;
		}
	} else {
finish:
#ifdef _KERNEL
		(*printfn)("User-level: pid %d.%d\n",
		    curlwp->l_proc->p_pid, curlwp->l_lid);
#else
		(*printfn)("User-level: FIXME\n");
#endif
	}
}

#endif /* DEBUG || DDB || KGDB || geo */
#endif /* DDB_TRACE */