| 1 | /*
|
|---|
| 2 | * Copyright (c) 2010 Jakub Jermar
|
|---|
| 3 | * All rights reserved.
|
|---|
| 4 | *
|
|---|
| 5 | * Redistribution and use in source and binary forms, with or without
|
|---|
| 6 | * modification, are permitted provided that the following conditions
|
|---|
| 7 | * are met:
|
|---|
| 8 | *
|
|---|
| 9 | * - Redistributions of source code must retain the above copyright
|
|---|
| 10 | * notice, this list of conditions and the following disclaimer.
|
|---|
| 11 | * - Redistributions in binary form must reproduce the above copyright
|
|---|
| 12 | * notice, this list of conditions and the following disclaimer in the
|
|---|
| 13 | * documentation and/or other materials provided with the distribution.
|
|---|
| 14 | * - The name of the author may not be used to endorse or promote products
|
|---|
| 15 | * derived from this software without specific prior written permission.
|
|---|
| 16 | *
|
|---|
| 17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
|
|---|
| 18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
|
|---|
| 19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
|
|---|
| 20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
|
|---|
| 21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
|
|---|
| 22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
|---|
| 23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
|---|
| 24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|---|
| 25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
|
|---|
| 26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|---|
| 27 | */
|
|---|
| 28 |
|
|---|
| 29 | /** @addtogroup mips32
|
|---|
| 30 | * @{
|
|---|
| 31 | */
|
|---|
| 32 | /** @file
|
|---|
| 33 | */
|
|---|
| 34 |
|
|---|
| 35 | /*
|
|---|
| 36 | * This stack tracing code is based on the suggested algorithm described on page
|
|---|
| 37 | * 3-27 and 3-28 of:
|
|---|
| 38 | *
|
|---|
| 39 | * SYSTEM V
|
|---|
| 40 | * APPLICATION BINARY INTERFACE
|
|---|
| 41 | *
|
|---|
| 42 | * MIPS RISC Processor
|
|---|
| 43 | * Supplement
|
|---|
| 44 | * 3rd Edition
|
|---|
| 45 | *
|
|---|
| 46 | * Unfortunately, GCC generates code which is not entirely compliant with this
|
|---|
| 47 | * method. For example, it places the "jr ra" instruction quite arbitrarily in
|
|---|
| 48 | * the middle of the function which makes the original algorithm unapplicable.
|
|---|
| 49 | *
|
|---|
| 50 | * We deal with this problem by simply not using those parts of the algorithm
|
|---|
| 51 | * that rely on the "jr ra" instruction occurring in the last basic block of a
|
|---|
| 52 | * function, which gives us still usable, but less reliable stack tracer. The
|
|---|
| 53 | * unreliability stems from the fact that under some circumstances it can become
|
|---|
| 54 | * confused and produce incorrect or incomplete stack trace. We apply extra
|
|---|
| 55 | * sanity checks so that the algorithm is still safe and should not crash the
|
|---|
| 56 | * system.
|
|---|
| 57 | *
|
|---|
| 58 | * Even though not perfect, our solution is pretty lightweight, especially when
|
|---|
| 59 | * compared with a prospective alternative solution based on additional
|
|---|
| 60 | * debugging information stored directly in the kernel image.
|
|---|
| 61 | */
|
|---|
| 62 |
|
|---|
| 63 | #include <stacktrace.h>
|
|---|
| 64 | #include <stddef.h>
|
|---|
| 65 | #include <syscall/copy.h>
|
|---|
| 66 | #include <typedefs.h>
|
|---|
| 67 | #include <arch/debugger.h>
|
|---|
| 68 | #include <print.h>
|
|---|
| 69 |
|
|---|
| 70 | #define R0 0U
|
|---|
| 71 | #define SP 29U
|
|---|
| 72 | #define RA 31U
|
|---|
| 73 |
|
|---|
| 74 | #define OP_SHIFT 26
|
|---|
| 75 | #define RS_SHIFT 21
|
|---|
| 76 | #define RT_SHIFT 16
|
|---|
| 77 | #define RD_SHIFT 11
|
|---|
| 78 |
|
|---|
| 79 | #define HINT_SHIFT 6
|
|---|
| 80 | #define BASE_SHIFT RS_SHIFT
|
|---|
| 81 | #define IMM_SHIFT 0
|
|---|
| 82 | #define OFFSET_SHIFT IMM_SHIFT
|
|---|
| 83 |
|
|---|
| 84 | #define RS_MASK (0x1f << RS_SHIFT)
|
|---|
| 85 | #define RT_MASK (0x1f << RT_SHIFT)
|
|---|
| 86 | #define RD_MASK (0x1f << RD_SHIFT)
|
|---|
| 87 | #define HINT_MASK (0x1f << HINT_SHIFT)
|
|---|
| 88 | #define BASE_MASK RS_MASK
|
|---|
| 89 | #define IMM_MASK (0xffff << IMM_SHIFT)
|
|---|
| 90 | #define OFFSET_MASK IMM_MASK
|
|---|
| 91 |
|
|---|
| 92 | #define RS_GET(inst) (((inst) & RS_MASK) >> RS_SHIFT)
|
|---|
| 93 | #define RD_GET(inst) (((inst) & RD_MASK) >> RD_SHIFT)
|
|---|
| 94 | #define IMM_GET(inst) (int16_t)(((inst) & IMM_MASK) >> IMM_SHIFT)
|
|---|
| 95 | #define BASE_GET(inst) RS_GET(inst)
|
|---|
| 96 | #define OFFSET_GET(inst) IMM_GET(inst)
|
|---|
| 97 |
|
|---|
| 98 | #define ADDU_R_SP_R0_TEMPL \
|
|---|
| 99 | ((0x0 << OP_SHIFT) | (SP << RS_SHIFT) | (R0 << RT_SHIFT) | 0x21)
|
|---|
| 100 | #define ADDU_SP_R_R0_TEMPL \
|
|---|
| 101 | ((0x0 << OP_SHIFT) | (SP << RD_SHIFT) | (R0 << RT_SHIFT) | 0x21)
|
|---|
| 102 | #define ADDI_SP_SP_IMM_TEMPL \
|
|---|
| 103 | ((0x8 << OP_SHIFT) | (SP << RS_SHIFT) | (SP << RT_SHIFT))
|
|---|
| 104 | #define ADDIU_SP_SP_IMM_TEMPL \
|
|---|
| 105 | ((0x9 << OP_SHIFT) | (SP << RS_SHIFT) | (SP << RT_SHIFT))
|
|---|
| 106 | #define JR_RA_TEMPL \
|
|---|
| 107 | ((0x0 << OP_SHIFT) | (RA << RS_SHIFT) | (0x0 << HINT_SHIFT) | 0x8)
|
|---|
| 108 | #define SW_RA_TEMPL \
|
|---|
| 109 | ((0x2b << OP_SHIFT) | (RA << RT_SHIFT))
|
|---|
| 110 |
|
|---|
| 111 | #define IS_ADDU_R_SP_R0(inst) \
|
|---|
| 112 | (((inst) & ~RD_MASK) == ADDU_R_SP_R0_TEMPL)
|
|---|
| 113 | #define IS_ADDU_SP_R_R0(inst) \
|
|---|
| 114 | (((inst) & ~RS_MASK) == ADDU_SP_R_R0_TEMPL)
|
|---|
| 115 | #define IS_ADDI_SP_SP_IMM(inst) \
|
|---|
| 116 | (((inst) & ~IMM_MASK) == ADDI_SP_SP_IMM_TEMPL)
|
|---|
| 117 | #define IS_ADDIU_SP_SP_IMM(inst) \
|
|---|
| 118 | (((inst) & ~IMM_MASK) == ADDIU_SP_SP_IMM_TEMPL)
|
|---|
| 119 | #define IS_JR_RA(inst) \
|
|---|
| 120 | (((inst) & ~HINT_MASK) == JR_RA_TEMPL)
|
|---|
| 121 | #define IS_SW_RA(inst) \
|
|---|
| 122 | (((inst) & ~(BASE_MASK | OFFSET_MASK)) == SW_RA_TEMPL)
|
|---|
| 123 |
|
|---|
| 124 | extern char ktext_start;
|
|---|
| 125 | extern char ktext_end;
|
|---|
| 126 |
|
|---|
| 127 | static bool bounds_check(uintptr_t pc)
|
|---|
| 128 | {
|
|---|
| 129 | return (pc >= (uintptr_t) &ktext_start) &&
|
|---|
| 130 | (pc < (uintptr_t) &ktext_end);
|
|---|
| 131 | }
|
|---|
| 132 |
|
|---|
| 133 | static bool
|
|---|
| 134 | scan(stack_trace_context_t *ctx, uintptr_t *prev_fp, uintptr_t *prev_ra)
|
|---|
| 135 | {
|
|---|
| 136 | uint32_t *inst = (void *) ctx->pc;
|
|---|
| 137 | bool has_fp = false;
|
|---|
| 138 | size_t frame_size;
|
|---|
| 139 | unsigned int fp = SP;
|
|---|
| 140 |
|
|---|
| 141 | do {
|
|---|
| 142 | inst--;
|
|---|
| 143 | if (!bounds_check((uintptr_t) inst))
|
|---|
| 144 | return false;
|
|---|
| 145 | #if 0
|
|---|
| 146 | /*
|
|---|
| 147 | * This is one of the situations in which the theory (ABI) does
|
|---|
| 148 | * not meet the practice (GCC). GCC simply does not place the
|
|---|
| 149 | * JR $ra instruction as dictated by the ABI, rendering the
|
|---|
| 150 | * official stack tracing algorithm somewhat unapplicable.
|
|---|
| 151 | */
|
|---|
| 152 |
|
|---|
| 153 | if (IS_ADDU_R_SP_R0(*inst)) {
|
|---|
| 154 | uint32_t *cur;
|
|---|
| 155 | fp = RD_GET(*inst);
|
|---|
| 156 | /*
|
|---|
| 157 | * We have a candidate for frame pointer.
|
|---|
| 158 | */
|
|---|
| 159 |
|
|---|
| 160 | /* Seek to the end of this function. */
|
|---|
| 161 | cur = inst + 1;
|
|---|
| 162 | while (!IS_JR_RA(*cur))
|
|---|
| 163 | cur++;
|
|---|
| 164 |
|
|---|
| 165 | /* Scan the last basic block */
|
|---|
| 166 | for (cur--; !is_jump(*(cur - 1)); cur--) {
|
|---|
| 167 | if (IS_ADDU_SP_R_R0(*cur) &&
|
|---|
| 168 | (fp == RS_GET(*cur))) {
|
|---|
| 169 | has_fp = true;
|
|---|
| 170 | }
|
|---|
| 171 | }
|
|---|
| 172 | continue;
|
|---|
| 173 | }
|
|---|
| 174 |
|
|---|
| 175 | if (IS_JR_RA(*inst)) {
|
|---|
| 176 | if (!ctx->istate)
|
|---|
| 177 | return false;
|
|---|
| 178 | /*
|
|---|
| 179 | * No stack frame has been allocated yet.
|
|---|
| 180 | * Use the values stored in istate.
|
|---|
| 181 | */
|
|---|
| 182 | if (prev_fp)
|
|---|
| 183 | *prev_fp = ctx->istate->sp;
|
|---|
| 184 | if (prev_ra)
|
|---|
| 185 | *prev_ra = ctx->istate->ra - 8;
|
|---|
| 186 | ctx->istate = NULL;
|
|---|
| 187 | return true;
|
|---|
| 188 | }
|
|---|
| 189 | #endif
|
|---|
| 190 |
|
|---|
| 191 | } while ((!IS_ADDIU_SP_SP_IMM(*inst) && !IS_ADDI_SP_SP_IMM(*inst)) ||
|
|---|
| 192 | (IMM_GET(*inst) >= 0));
|
|---|
| 193 |
|
|---|
| 194 | /*
|
|---|
| 195 | * We are at the instruction which allocates the space for the current
|
|---|
| 196 | * stack frame.
|
|---|
| 197 | */
|
|---|
| 198 | frame_size = -IMM_GET(*inst);
|
|---|
| 199 | if (prev_fp)
|
|---|
| 200 | *prev_fp = ctx->fp + frame_size;
|
|---|
| 201 |
|
|---|
| 202 | /*
|
|---|
| 203 | * Scan the first basic block for the occurrence of
|
|---|
| 204 | * SW $ra, OFFSET($base).
|
|---|
| 205 | */
|
|---|
| 206 | for (inst++; !is_jump(*(inst - 1)) && (uintptr_t) inst < ctx->pc;
|
|---|
| 207 | inst++) {
|
|---|
| 208 | if (IS_SW_RA(*inst)) {
|
|---|
| 209 | unsigned int base = BASE_GET(*inst);
|
|---|
| 210 | int16_t offset = OFFSET_GET(*inst);
|
|---|
| 211 |
|
|---|
| 212 | if (base == SP || (has_fp && base == fp)) {
|
|---|
| 213 | uint32_t *addr = (void *) (ctx->fp + offset);
|
|---|
| 214 |
|
|---|
| 215 | if (offset % 4 != 0)
|
|---|
| 216 | return false;
|
|---|
| 217 | /* cannot store below current stack pointer */
|
|---|
| 218 | if (offset < 0)
|
|---|
| 219 | return false;
|
|---|
| 220 | /* too big offsets are suspicious */
|
|---|
| 221 | if ((size_t) offset > sizeof(istate_t))
|
|---|
| 222 | return false;
|
|---|
| 223 |
|
|---|
| 224 | if (prev_ra)
|
|---|
| 225 | *prev_ra = *addr;
|
|---|
| 226 | return true;
|
|---|
| 227 | }
|
|---|
| 228 | }
|
|---|
| 229 | }
|
|---|
| 230 |
|
|---|
| 231 | /*
|
|---|
| 232 | * The first basic block does not save the return address or saves it
|
|---|
| 233 | * after ctx->pc, which means that the correct value is in istate.
|
|---|
| 234 | */
|
|---|
| 235 | if (prev_ra) {
|
|---|
| 236 | if (!ctx->istate)
|
|---|
| 237 | return false;
|
|---|
| 238 | *prev_ra = ctx->istate->ra - 8;
|
|---|
| 239 | ctx->istate = NULL;
|
|---|
| 240 | }
|
|---|
| 241 | return true;
|
|---|
| 242 | }
|
|---|
| 243 |
|
|---|
| 244 |
|
|---|
| 245 | bool kernel_stack_trace_context_validate(stack_trace_context_t *ctx)
|
|---|
| 246 | {
|
|---|
| 247 | return !((ctx->fp == 0) || ((ctx->fp % 8) != 0) ||
|
|---|
| 248 | (ctx->pc % 4 != 0) || !bounds_check(ctx->pc));
|
|---|
| 249 | }
|
|---|
| 250 |
|
|---|
| 251 | bool kernel_frame_pointer_prev(stack_trace_context_t *ctx, uintptr_t *prev)
|
|---|
| 252 | {
|
|---|
| 253 | return scan(ctx, prev, NULL);
|
|---|
| 254 | }
|
|---|
| 255 |
|
|---|
| 256 | bool kernel_return_address_get(stack_trace_context_t *ctx, uintptr_t *ra)
|
|---|
| 257 | {
|
|---|
| 258 | return scan(ctx, NULL, ra);
|
|---|
| 259 | }
|
|---|
| 260 |
|
|---|
| 261 | bool uspace_stack_trace_context_validate(stack_trace_context_t *ctx)
|
|---|
| 262 | {
|
|---|
| 263 | return false;
|
|---|
| 264 | }
|
|---|
| 265 |
|
|---|
| 266 | bool uspace_frame_pointer_prev(stack_trace_context_t *ctx, uintptr_t *prev)
|
|---|
| 267 | {
|
|---|
| 268 | return false;
|
|---|
| 269 | }
|
|---|
| 270 |
|
|---|
| 271 | bool uspace_return_address_get(stack_trace_context_t *ctx, uintptr_t *ra)
|
|---|
| 272 | {
|
|---|
| 273 | return false;
|
|---|
| 274 | }
|
|---|
| 275 |
|
|---|
| 276 | /** @}
|
|---|
| 277 | */
|
|---|
