Index: kernel/arch/mips32/src/debug/stacktrace.c
===================================================================
--- kernel/arch/mips32/src/debug/stacktrace.c	(revision d99c1d2ba8c7b2c687d430f2e9fd237046606545)
+++ kernel/arch/mips32/src/debug/stacktrace.c	(revision e314a1289d8861cb28062b0b6a7891bb59c98472)
@@ -36,35 +36,204 @@
 #include <syscall/copy.h>
 #include <typedefs.h>
-
-bool kernel_frame_pointer_validate(uintptr_t fp)
+#include <arch/debugger.h>
+#include <print.h>
+
+#define R0	0U
+#define SP	29U
+#define RA	31U
+
+#define OP_SHIFT	26
+#define RS_SHIFT	21
+#define RT_SHIFT	16
+#define RD_SHIFT	11
+
+#define HINT_SHIFT	6
+#define BASE_SHIFT	RS_SHIFT
+#define IMM_SHIFT	0
+#define OFFSET_SHIFT	IMM_SHIFT
+
+#define RS_MASK		(0x1f << RS_SHIFT)
+#define RT_MASK		(0x1f << RT_SHIFT)
+#define RD_MASK		(0x1f << RD_SHIFT)
+#define HINT_MASK	(0x1f << HINT_SHIFT)
+#define BASE_MASK	RS_MASK
+#define IMM_MASK	(0xffff << IMM_SHIFT)
+#define OFFSET_MASK	IMM_MASK	
+
+#define RS_GET(inst)		(((inst) & RS_MASK) >> RS_SHIFT)
+#define RD_GET(inst)		(((inst) & RD_MASK) >> RD_SHIFT)
+#define IMM_GET(inst)		(int16_t)(((inst) & IMM_MASK) >> IMM_SHIFT)
+#define BASE_GET(inst)		RS_GET(inst)
+#define OFFSET_GET(inst)	IMM_GET(inst)	
+
+#define ADDU_R_SP_R0_TEMPL \
+	((0x0 << OP_SHIFT) | (SP << RS_SHIFT) | (R0 << RT_SHIFT) | 0x21)
+#define ADDU_SP_R_R0_TEMPL \
+	((0x0 << OP_SHIFT) | (SP << RD_SHIFT) | (R0 << RT_SHIFT) | 0x21)
+#define ADDI_SP_SP_IMM_TEMPL \
+	((0x8 << OP_SHIFT) | (SP << RS_SHIFT) | (SP << RT_SHIFT))
+#define ADDIU_SP_SP_IMM_TEMPL \
+	((0x9 << OP_SHIFT) | (SP << RS_SHIFT) | (SP << RT_SHIFT))
+#define JR_RA_TEMPL \
+	((0x0 << OP_SHIFT) | (RA << RS_SHIFT) | (0x0 << HINT_SHIFT) | 0x8)
+#define SW_RA_TEMPL \
+	((0x2b << OP_SHIFT) | (RA << RT_SHIFT))
+
+#define IS_ADDU_R_SP_R0(inst) \
+	(((inst) & ~RD_MASK) == ADDU_R_SP_R0_TEMPL)
+#define IS_ADDU_SP_R_R0(inst) \
+	(((inst) & ~RS_MASK) == ADDU_SP_R_R0_TEMPL)
+#define IS_ADDI_SP_SP_IMM(inst) \
+	(((inst) & ~IMM_MASK) == ADDI_SP_SP_IMM_TEMPL)
+#define IS_ADDIU_SP_SP_IMM(inst) \
+	(((inst) & ~IMM_MASK) == ADDIU_SP_SP_IMM_TEMPL)
+#define IS_JR_RA(inst) \
+	(((inst) & ~HINT_MASK) == JR_RA_TEMPL)
+#define IS_SW_RA(inst) \
+	(((inst) & ~(BASE_MASK | OFFSET_MASK)) == SW_RA_TEMPL)
+
+extern char ktext_start;
+extern char ktext_end;
+
+static bool
+scan(stack_trace_context_t *ctx, uintptr_t *prev_fp, uintptr_t *prev_ra)
+{
+	uint32_t *inst = (void *) ctx->pc;
+	bool has_fp = false;
+	size_t frame_size;
+	unsigned int fp = SP;
+
+	do {
+		inst--;
+#if 0
+		/*
+		 * This is one of the situations in which the theory (ABI) does
+		 * not meet the practice (GCC). GCC simply does not place the
+		 * JR $ra instruction as dictated by the ABI, rendering the
+		 * official stack tracing algorithm somewhat unapplicable.
+		 */
+
+		if (IS_ADDU_R_SP_R0(*inst)) {
+			uint32_t *cur;
+			fp = RD_GET(*inst);
+			/*
+			 * We have a candidate for frame pointer.
+			 */
+			
+			/* Seek to the end of this function. */
+			for (cur = inst + 1; !IS_JR_RA(*cur); cur++)
+				;
+			/* Scan the last basic block */
+			for (cur--; !is_jump(*(cur - 1)); cur--) {
+				if (IS_ADDU_SP_R_R0(*cur) &&
+				    (fp == RS_GET(*cur))) {
+					has_fp = true;
+				}
+			}
+			continue;
+		}
+		
+		if (IS_JR_RA(*inst)) {
+			if (!ctx->istate)
+				return false;
+			/*
+			 * No stack frame has been allocated yet.
+			 * Use the values stored in istate.
+			 */
+			if (prev_fp)
+				*prev_fp = ctx->istate->sp;
+			if (prev_ra)
+				*prev_ra = ctx->istate->ra - 8;
+			ctx->istate = NULL;
+			return true;
+		}
+#endif
+
+	} while ((!IS_ADDIU_SP_SP_IMM(*inst) && !IS_ADDI_SP_SP_IMM(*inst)) ||
+	    (IMM_GET(*inst) >= 0));
+	
+	/*
+	 * We are at the instruction which allocates the space for the current
+	 * stack frame.
+	 */
+	frame_size = -IMM_GET(*inst);
+	if (prev_fp)
+		*prev_fp = ctx->fp + frame_size;
+
+	/*
+	 * Scan the first basic block for the occurrence of
+	 * SW $ra, OFFSET($base).
+	 */
+	for (inst++; !is_jump(*(inst - 1)) && (uintptr_t) inst < ctx->pc;
+	    inst++) {
+		if (IS_SW_RA(*inst)) {
+			unsigned int base = BASE_GET(*inst);
+			int16_t offset = OFFSET_GET(*inst);
+
+			if (base == SP || (has_fp && base == fp)) {
+				uint32_t *addr = (void *) (ctx->fp + offset);
+				
+				if (offset % 4 != 0)
+					return false;
+				/* cannot store below current stack pointer */
+				if (offset < 0)
+					return false;
+				/* too big offsets are suspicious */
+				if (offset > 32 * 4)
+					return false;
+
+				if (prev_ra)
+					*prev_ra = *addr;
+				return true;
+			}
+		}
+	}
+
+	/*
+	 * The first basic block does not save the return address or saves it
+	 * after ctx->pc, which means that the correct value is in istate.
+	 */
+	if (prev_ra) {
+		if (!ctx->istate)
+			return false;
+		*prev_ra = ctx->istate->ra - 8;
+		ctx->istate = NULL;
+	}
+	return true;
+}
+
+
+bool kernel_stack_trace_context_validate(stack_trace_context_t *ctx)
+{
+	return !((ctx->fp == 0) || ((ctx->fp % 8) != 0) ||
+	    (ctx->pc % 4 != 0) || (ctx->pc < (uintptr_t) &ktext_start) ||
+	    (ctx->pc >= (uintptr_t) &ktext_end));
+}
+
+bool kernel_frame_pointer_prev(stack_trace_context_t *ctx, uintptr_t *prev)
+{
+	return scan(ctx, prev, NULL);
+}
+
+bool kernel_return_address_get(stack_trace_context_t *ctx, uintptr_t *ra)
+{
+	return scan(ctx, NULL, ra);
+}
+
+bool uspace_stack_trace_context_validate(stack_trace_context_t *ctx)
 {
 	return false;
 }
 
-bool kernel_frame_pointer_prev(uintptr_t fp, uintptr_t *prev)
+bool uspace_frame_pointer_prev(stack_trace_context_t *ctx, uintptr_t *prev)
 {
 	return false;
 }
 
-bool kernel_return_address_get(uintptr_t fp, uintptr_t *ra)
+bool uspace_return_address_get(stack_trace_context_t *ctx, uintptr_t *ra)
 {
 	return false;
 }
 
-bool uspace_frame_pointer_validate(uintptr_t fp)
-{
-	return false;
-}
-
-bool uspace_frame_pointer_prev(uintptr_t fp, uintptr_t *prev)
-{
-	return false;
-}
-
-bool uspace_return_address_get(uintptr_t fp, uintptr_t *ra)
-{
-	return false;
-}
-
 /** @}
  */
