path: root/libcorkscrew/arch-mips/backtrace-mips.c

/*
 * Copyright (C) 2012 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/*
 * Backtracing functions for mips
 */

#define LOG_TAG "Corkscrew"
//#define LOG_NDEBUG 0

#include "../backtrace-arch.h"
#include "../backtrace-helper.h"
#include "../ptrace-arch.h"
#include <corkscrew/ptrace.h>
#include "dwarf.h"

#include <stdlib.h>
#include <signal.h>
#include <stdbool.h>
#include <limits.h>
#include <errno.h>
#include <string.h>
#include <sys/ptrace.h>
#include <cutils/log.h>

#include <sys/ucontext.h>

/* For PTRACE_GETREGS */
typedef struct {
    uint64_t regs[32];
    uint64_t lo;
    uint64_t hi;
    uint64_t epc;
    uint64_t badvaddr;
    uint64_t status;
    uint64_t cause;
} user_regs_struct;

enum {
    REG_ZERO = 0, REG_AT, REG_V0, REG_V1,
    REG_A0, REG_A1, REG_A2, REG_A3,
    REG_T0, REG_T1, REG_T2, REG_T3,
    REG_T4, REG_T5, REG_T6, REG_T7,
    REG_S0, REG_S1, REG_S2, REG_S3,
    REG_S4, REG_S5, REG_S6, REG_S7,
    REG_T8, REG_T9, REG_K0, REG_K1,
    REG_GP, REG_SP, REG_S8, REG_RA,
};


/* Unwind state. */
typedef struct {
    uint32_t reg[DWARF_REGISTERS];
} unwind_state_t;

uintptr_t rewind_pc_arch(const memory_t* memory __attribute__((unused)), uintptr_t pc) {
    if (pc == 0)
        return pc;
    if ((pc & 1) == 0)
        return pc-8;            /* jal/bal/jalr + branch delay slot */
    return pc;
}

/* Read byte through 4 byte cache. Usually we read byte by byte and updating cursor. */
static bool try_get_byte(const memory_t* memory, uintptr_t ptr, uint8_t* out_value, uint32_t* cursor) {
    static uintptr_t lastptr;
    static uint32_t buf;

    ptr += *cursor;

    if (ptr < lastptr || lastptr + 3 < ptr) {
        lastptr = (ptr >> 2) << 2;
        if (!try_get_word(memory, lastptr, &buf)) {
            return false;
        }
    }
    *out_value = (uint8_t)((buf >> ((ptr & 3) * 8)) & 0xff);
    ++*cursor;
    return true;
}

/* Getting X bytes. 4 is maximum for now. */
static bool try_get_xbytes(const memory_t* memory, uintptr_t ptr, uint32_t* out_value, uint8_t bytes, uint32_t* cursor) {
    uint32_t data = 0;
    if (bytes > 4) {
        ALOGE("can't read more than 4 bytes, trying to read %d", bytes);
        return false;
    }
    for (int i = 0; i < bytes; i++) {
        uint8_t buf;
        if (!try_get_byte(memory, ptr, &buf, cursor)) {
            return false;
        }
        data |= (uint32_t)buf << (i * 8);
    }
    *out_value = data;
    return true;
}

/* Reads signed/unsigned LEB128 encoded data. From 1 to 4 bytes. */
static bool try_get_leb128(const memory_t* memory, uintptr_t ptr, uint32_t* out_value, uint32_t* cursor, bool sign_extend) {
    uint8_t buf = 0;
    uint32_t val = 0;
    uint8_t c = 0;
    do {
        if (!try_get_byte(memory, ptr, &buf, cursor)) {
            return false;
        }
        val |= ((uint32_t)buf & 0x7f) << (c * 7);
        c++;
    } while (buf & 0x80 && (c * 7) <= 32);
    if (c * 7 > 32) {
        ALOGE("%s: data exceeds expected 4 bytes maximum", __FUNCTION__);
        return false;
    }
    if (sign_extend) {
        if (buf & 0x40) {
            val |= ((uint32_t)-1 << (c * 7));
        }
    }
    *out_value = val;
    return true;
}

/* Reads signed LEB128 encoded data. From 1 to 4 bytes. */
static bool try_get_sleb128(const memory_t* memory, uintptr_t ptr, uint32_t* out_value, uint32_t* cursor) {
    return try_get_leb128(memory, ptr, out_value, cursor, true);
}

/* Reads unsigned LEB128 encoded data. From 1 to 4 bytes. */
static bool try_get_uleb128(const memory_t* memory, uintptr_t ptr, uint32_t* out_value, uint32_t* cursor) {
    return try_get_leb128(memory, ptr, out_value, cursor, false);
}

/* Getting data encoded by dwarf encodings. */
static bool read_dwarf(const memory_t* memory, uintptr_t ptr, uint32_t* out_value, uint8_t encoding, uint32_t* cursor) {
    uint32_t data = 0;
    bool issigned = true;
    uintptr_t addr = ptr + *cursor;
    /* Lower 4 bits is data type/size */
    /* TODO: add more encodings if it becomes necessary */
    switch (encoding & 0xf) {
    case DW_EH_PE_absptr:
        if (!try_get_xbytes(memory, ptr, &data, 4, cursor)) {
            return false;
        }
        *out_value = data;
        return true;
    case DW_EH_PE_udata4:
        issigned = false;
    case DW_EH_PE_sdata4:
        if (!try_get_xbytes(memory, ptr, &data, 4, cursor)) {
            return false;
        }
        break;
    default:
        ALOGE("unrecognized dwarf lower part encoding: 0x%x", encoding);
        return false;
    }
    /* Higher 4 bits is modifier */
    /* TODO: add more encodings if it becomes necessary */
    switch (encoding & 0xf0) {
    case 0:
        *out_value = data;
        break;
    case DW_EH_PE_pcrel:
        if (issigned) {
            *out_value = addr + (int32_t)data;
        } else {
            *out_value = addr + data;
        }
        break;
        /* Assuming ptr is correct base to calculate datarel */
    case DW_EH_PE_datarel:
        if (issigned) {
            *out_value = ptr + (int32_t)data;
        } else {
            *out_value = ptr + data;
        }
        break;
    default:
        ALOGE("unrecognized dwarf higher part encoding: 0x%x", encoding);
        return false;
    }
    return true;
}

/* Having PC find corresponding FDE by reading .eh_frame_hdr section data. */
static uintptr_t find_fde(const memory_t* memory,
                          const map_info_t* map_info_list, uintptr_t pc) {
    if (!pc) {
        ALOGV("find_fde: pc is zero, no eh_frame");
        return 0;
    }
    const map_info_t* mi = find_map_info(map_info_list, pc);
    if (!mi) {
        ALOGV("find_fde: no map info for pc:0x%x", pc);
        return 0;
    }
    const map_info_data_t* midata = mi->data;
    if (!midata) {
        ALOGV("find_fde: no eh_frame_hdr for map: start=0x%x, end=0x%x", mi->start, mi->end);
        return 0;
    }

    eh_frame_hdr_info_t eh_hdr_info;
    memset(&eh_hdr_info, 0, sizeof(eh_frame_hdr_info_t));

    /* Getting the first word of eh_frame_hdr:
       1st byte is version;
       2nd byte is encoding of pointer to eh_frames;
       3rd byte is encoding of count of FDEs in lookup table;
       4th byte is encoding of lookup table entries.
    */
    uintptr_t eh_frame_hdr = midata->eh_frame_hdr;
    uint32_t c = 0;
    if (!try_get_byte(memory, eh_frame_hdr, &eh_hdr_info.version, &c)) return 0;
    if (!try_get_byte(memory, eh_frame_hdr, &eh_hdr_info.eh_frame_ptr_enc, &c)) return 0;
    if (!try_get_byte(memory, eh_frame_hdr, &eh_hdr_info.fde_count_enc, &c)) return 0;
    if (!try_get_byte(memory, eh_frame_hdr, &eh_hdr_info.fde_table_enc, &c)) return 0;

    /* TODO: 3rd byte can be DW_EH_PE_omit, that means no lookup table available and we should
       try to parse eh_frame instead. Not sure how often it may occur, skipping now.
    */
    if (eh_hdr_info.version != 1) {
        ALOGV("find_fde: eh_frame_hdr version %d is not supported", eh_hdr_info.version);
        return 0;
    }
    /* Getting the data:
       2nd word is eh_frame pointer (normally not used, because lookup table has all we need);
       3rd word is count of FDEs in the lookup table;
       starting from 4 word there is FDE lookup table (pairs of PC and FDE pointer) sorted by PC;
    */
    if (!read_dwarf(memory, eh_frame_hdr, &eh_hdr_info.eh_frame_ptr, eh_hdr_info.eh_frame_ptr_enc, &c)) return 0;
    if (!read_dwarf(memory, eh_frame_hdr, &eh_hdr_info.fde_count, eh_hdr_info.fde_count_enc, &c)) return 0;
    ALOGV("find_fde: found %d FDEs", eh_hdr_info.fde_count);

    int32_t low = 0;
    int32_t high = eh_hdr_info.fde_count;
    uintptr_t start = 0;
    uintptr_t fde = 0;
    /* eh_frame_hdr + c points to lookup table at this point. */
    while (low <= high) {
        uint32_t mid = (high + low)/2;
        uint32_t entry = c + mid * 8;
        if (!read_dwarf(memory, eh_frame_hdr, &start, eh_hdr_info.fde_table_enc, &entry)) return 0;
        if (pc <= start) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    /* Value found is at high. */
    if (high < 0) {
        ALOGV("find_fde: pc %x is out of FDE bounds: %x", pc, start);
        return 0;
    }
    c += high * 8;
    if (!read_dwarf(memory, eh_frame_hdr, &start, eh_hdr_info.fde_table_enc, &c)) return 0;
    if (!read_dwarf(memory, eh_frame_hdr, &fde, eh_hdr_info.fde_table_enc, &c)) return 0;
    ALOGV("pc 0x%x, ENTRY %d: start=0x%x, fde=0x%x", pc, high, start, fde);
    return fde;
}

/* Execute single dwarf instruction and update dwarf state accordingly. */
static bool execute_dwarf(const memory_t* memory, uintptr_t ptr, cie_info_t* cie_info,
                          dwarf_state_t* dstate, uint32_t* cursor,
                          dwarf_state_t* stack, uint8_t* stack_ptr) {
    uint8_t inst;
    uint8_t op = 0;

    if (!try_get_byte(memory, ptr, &inst, cursor)) {
        return false;
    }
    ALOGV("DW_CFA inst: 0x%x", inst);

    /* For some instructions upper 2 bits is opcode and lower 6 bits is operand. See dwarf-2.0 7.23. */
    if (inst & 0xc0) {
        op = inst & 0x3f;
        inst &= 0xc0;
    }

    switch ((dwarf_CFA)inst) {
        uint32_t reg = 0;
        uint32_t offset = 0;
    case DW_CFA_advance_loc:
        dstate->loc += op * cie_info->code_align;
        ALOGV("DW_CFA_advance_loc: %d to 0x%x", op, dstate->loc);
        break;
    case DW_CFA_offset:
        if (!try_get_uleb128(memory, ptr, &offset, cursor)) return false;
        dstate->regs[op].rule = 'o';
        dstate->regs[op].value = offset * cie_info->data_align;
        ALOGV("DW_CFA_offset: r%d = o(%d)", op, dstate->regs[op].value);
        break;
    case DW_CFA_restore:
        dstate->regs[op].rule = stack->regs[op].rule;
        dstate->regs[op].value = stack->regs[op].value;
        ALOGV("DW_CFA_restore: r%d = %c(%d)", op, dstate->regs[op].rule, dstate->regs[op].value);
        break;
    case DW_CFA_nop:
        break;
    case DW_CFA_set_loc: // probably we don't have it on mips.
        if (!try_get_xbytes(memory, ptr, &offset, 4, cursor)) return false;
        if (offset < dstate->loc) {
            ALOGE("DW_CFA_set_loc: attempt to move location backward");
            return false;
        }
        dstate->loc = offset * cie_info->code_align;
        ALOGV("DW_CFA_set_loc: %d to 0x%x", offset * cie_info->code_align, dstate->loc);
        break;
    case DW_CFA_advance_loc1:
        if (!try_get_byte(memory, ptr, (uint8_t*)&offset, cursor)) return false;
        dstate->loc += (uint8_t)offset * cie_info->code_align;
        ALOGV("DW_CFA_advance_loc1: %d to 0x%x", (uint8_t)offset * cie_info->code_align, dstate->loc);
        break;
    case DW_CFA_advance_loc2:
        if (!try_get_xbytes(memory, ptr, &offset, 2, cursor)) return false;
        dstate->loc += (uint16_t)offset * cie_info->code_align;
        ALOGV("DW_CFA_advance_loc2: %d to 0x%x", (uint16_t)offset * cie_info->code_align, dstate->loc);
        break;
    case DW_CFA_advance_loc4:
        if (!try_get_xbytes(memory, ptr, &offset, 4, cursor)) return false;
        dstate->loc += offset * cie_info->code_align;
        ALOGV("DW_CFA_advance_loc4: %d to 0x%x", offset * cie_info->code_align, dstate->loc);
        break;
    case DW_CFA_offset_extended: // probably we don't have it on mips.
        if (!try_get_uleb128(memory, ptr, &reg, cursor)) return false;
        if (!try_get_uleb128(memory, ptr, &offset, cursor)) return false;
        if (reg >= DWARF_REGISTERS) {
            ALOGE("DW_CFA_offset_extended: r%d exceeds supported number of registers (%d)", reg, DWARF_REGISTERS);
            return false;
        }
        dstate->regs[reg].rule = 'o';
        dstate->regs[reg].value = offset * cie_info->data_align;
        ALOGV("DW_CFA_offset_extended: r%d = o(%d)", reg, dstate->regs[reg].value);
        break;
    case DW_CFA_restore_extended: // probably we don't have it on mips.
        if (!try_get_uleb128(memory, ptr, &reg, cursor)) return false;
        if (reg >= DWARF_REGISTERS) {
            ALOGE("DW_CFA_restore_extended: r%d exceeds supported number of registers (%d)", reg, DWARF_REGISTERS);
            return false;
        }
        dstate->regs[reg].rule = stack->regs[reg].rule;
        dstate->regs[reg].value = stack->regs[reg].value;
        ALOGV("DW_CFA_restore: r%d = %c(%d)", reg, dstate->regs[reg].rule, dstate->regs[reg].value);
        break;
    case DW_CFA_undefined: // probably we don't have it on mips.
        if (!try_get_uleb128(memory, ptr, &reg, cursor)) return false;
        if (reg >= DWARF_REGISTERS) {
            ALOGE("DW_CFA_undefined: r%d exceeds supported number of registers (%d)", reg, DWARF_REGISTERS);
            return false;
        }
        dstate->regs[reg].rule = 'u';
        dstate->regs[reg].value = 0;
        ALOGV("DW_CFA_undefined: r%d", reg);
        break;
    case DW_CFA_same_value: // probably we don't have it on mips.
        if (!try_get_uleb128(memory, ptr, &reg, cursor)) return false;
        if (reg >= DWARF_REGISTERS) {
            ALOGE("DW_CFA_undefined: r%d exceeds supported number of registers (%d)", reg, DWARF_REGISTERS);
            return false;
        }
        dstate->regs[reg].rule = 's';
        dstate->regs[reg].value = 0;
        ALOGV("DW_CFA_same_value: r%d", reg);
        break;
    case DW_CFA_register: // probably we don't have it on mips.
        if (!try_get_uleb128(memory, ptr, &reg, cursor)) return false;
        /* that's new register actually, not offset */
        if (!try_get_uleb128(memory, ptr, &offset, cursor)) return false;
        if (reg >= DWARF_REGISTERS || offset >= DWARF_REGISTERS) {
            ALOGE("DW_CFA_register: r%d or r%d exceeds supported number of registers (%d)", reg, offset, DWARF_REGISTERS);
            return false;
        }
        dstate->regs[reg].rule = 'r';
        dstate->regs[reg].value = offset;
        ALOGV("DW_CFA_register: r%d = r(%d)", reg, dstate->regs[reg].value);
        break;
    case DW_CFA_remember_state:
        if (*stack_ptr == DWARF_STATES_STACK) {
            ALOGE("DW_CFA_remember_state: states stack overflow %d", *stack_ptr);
            return false;
        }
        stack[(*stack_ptr)++] = *dstate;
        ALOGV("DW_CFA_remember_state: stacktop moves to %d", *stack_ptr);
        break;
    case DW_CFA_restore_state:
        /* We have CIE state saved at 0 position. It's not supposed to be taken
           by DW_CFA_restore_state. */
        if (*stack_ptr == 1) {
            ALOGE("DW_CFA_restore_state: states stack is empty");
            return false;
        }
        /* Don't touch location on restore. */
        uintptr_t saveloc = dstate->loc;
        *dstate = stack[--*stack_ptr];
        dstate->loc = saveloc;
        ALOGV("DW_CFA_restore_state: stacktop moves to %d", *stack_ptr);
        break;
    case DW_CFA_def_cfa:
        if (!try_get_uleb128(memory, ptr, &reg, cursor)) return false;
        if (!try_get_uleb128(memory, ptr, &offset, cursor)) return false;
        dstate->cfa_reg = reg;
        dstate->cfa_off = offset;
        ALOGV("DW_CFA_def_cfa: %x(r%d)", offset, reg);
        break;
    case DW_CFA_def_cfa_register:
        if (!try_get_uleb128(memory, ptr, &reg, cursor)) {
            return false;
        }
        dstate->cfa_reg = reg;
        ALOGV("DW_CFA_def_cfa_register: r%d", reg);
        break;
    case DW_CFA_def_cfa_offset:
        if (!try_get_uleb128(memory, ptr, &offset, cursor)) {
            return false;
        }
        dstate->cfa_off = offset;
        ALOGV("DW_CFA_def_cfa_offset: %x", offset);
        break;
    default:
        ALOGE("unrecognized DW_CFA_* instruction: 0x%x", inst);
        return false;
    }
    return true;
}

/* Restoring particular register value based on dwarf state. */
static bool get_old_register_value(const memory_t* memory, uint32_t cfa,
                                   dwarf_state_t* dstate, uint8_t reg,
                                   unwind_state_t* state, unwind_state_t* newstate) {
    uint32_t addr;
    switch (dstate->regs[reg].rule) {
    case 0:
        /* We don't have dstate updated for this register, so assuming value kept the same.
           Normally we should look into state and return current value as the old one
           but we don't have all registers in state to handle this properly */
        ALOGV("get_old_register_value: value of r%d is the same", reg);
        // for SP if it's not updated by dwarf rule we assume it's equal to CFA
        // for PC if it's not updated by dwarf rule we assume it's equal to RA
        if (reg == DWARF_SP) {
            ALOGV("get_old_register_value: adjusting sp to CFA: 0x%x", cfa);
            newstate->reg[reg] = cfa;
        } else if (reg == DWARF_PC) {
            ALOGV("get_old_register_value: adjusting PC to RA: 0x%x", newstate->reg[DWARF_RA]);
            newstate->reg[reg] = newstate->reg[DWARF_RA];
        } else {
            newstate->reg[reg] = state->reg[reg];
        }
        break;
    case 'o':
        addr = cfa + (int32_t)dstate->regs[reg].value;
        if (!try_get_word(memory, addr, &newstate->reg[reg])) {
            ALOGE("get_old_register_value: can't read from 0x%x", addr);
            return false;
        }
        ALOGV("get_old_register_value: r%d at 0x%x is 0x%x", reg, addr, newstate->reg[reg]);
        break;
    case 'r':
        /* We don't have all registers in state so don't even try to look at 'r' */
        ALOGE("get_old_register_value: register lookup not implemented yet");
        break;
    default:
        ALOGE("get_old_register_value: unexpected rule:%c value:%d for register %d",
              dstate->regs[reg].rule, (int32_t)dstate->regs[reg].value, reg);
        return false;
    }
    return true;
}

/* Updaing state based on dwarf state. */
static bool update_state(const memory_t* memory, unwind_state_t* state,
                         dwarf_state_t* dstate) {
    unwind_state_t newstate;
    /* We can restore more registers here if we need them. Meanwile doing minimal work here. */
    /* Getting CFA. */
    uintptr_t cfa = 0;
    if (dstate->cfa_reg == DWARF_SP) {
        cfa = state->reg[DWARF_SP] + dstate->cfa_off;
    } else if (dstate->cfa_reg == DWARF_FP) {
        cfa = state->reg[DWARF_FP] + dstate->cfa_off;
    } else {
        ALOGE("update_state: unexpected CFA register: %d", dstate->cfa_reg);
        return false;
    }
    ALOGV("update_state: new CFA: 0x%x", cfa);

    /* Update registers. Order is important to allow RA to propagate to PC */
    /* Getting FP. */
    if (!get_old_register_value(memory, cfa, dstate, DWARF_FP, state, &newstate)) return false;
    /* Getting SP. */
    if (!get_old_register_value(memory, cfa, dstate, DWARF_SP, state, &newstate)) return false;
    /* Getting RA. */
    if (!get_old_register_value(memory, cfa, dstate, DWARF_RA, state, &newstate)) return false;
    /* Getting PC. */
    if (!get_old_register_value(memory, cfa, dstate, DWARF_PC, state, &newstate)) return false;

    ALOGV("update_state: PC: 0x%x; restore PC: 0x%x", state->reg[DWARF_PC], newstate.reg[DWARF_PC]);
    ALOGV("update_state: RA: 0x%x; restore RA: 0x%x", state->reg[DWARF_RA], newstate.reg[DWARF_RA]);
    ALOGV("update_state: FP: 0x%x; restore FP: 0x%x", state->reg[DWARF_FP], newstate.reg[DWARF_FP]);
    ALOGV("update_state: SP: 0x%x; restore SP: 0x%x", state->reg[DWARF_SP], newstate.reg[DWARF_SP]);

    if (newstate.reg[DWARF_PC] == 0)
        return false;

    /* End backtrace if registers do not change */
    if ((state->reg[DWARF_PC] == newstate.reg[DWARF_PC]) &&
        (state->reg[DWARF_RA] == newstate.reg[DWARF_RA]) &&
        (state->reg[DWARF_FP] == newstate.reg[DWARF_FP]) &&
        (state->reg[DWARF_SP] == newstate.reg[DWARF_SP]))
        return false;

    *state = newstate;
    return true;
}

/* Execute CIE and FDE instructions for FDE found with find_fde. */
static bool execute_fde(const memory_t* memory,
                        uintptr_t fde,
                        unwind_state_t* state) {
    uint32_t fde_length = 0;
    uint32_t cie_length = 0;
    uintptr_t cie = 0;
    uintptr_t cie_offset = 0;
    cie_info_t cie_i;
    cie_info_t* cie_info = &cie_i;
    fde_info_t fde_i;
    fde_info_t* fde_info = &fde_i;
    dwarf_state_t dwarf_state;
    dwarf_state_t* dstate = &dwarf_state;
    dwarf_state_t stack[DWARF_STATES_STACK];
    uint8_t stack_ptr = 0;

    memset(dstate, 0, sizeof(dwarf_state_t));
    memset(cie_info, 0, sizeof(cie_info_t));
    memset(fde_info, 0, sizeof(fde_info_t));

    /* Read common CIE or FDE area:
       1st word is length;
       2nd word is ID: 0 for CIE, CIE pointer for FDE.
    */
    if (!try_get_word(memory, fde, &fde_length)) {
        return false;
    }
    if ((int32_t)fde_length == -1) {
        ALOGV("execute_fde: 64-bit dwarf detected, not implemented yet");
        return false;
    }
    if (!try_get_word(memory, fde + 4, &cie_offset)) {
        return false;
    }
    if (cie_offset == 0) {
        /* This is CIE. We shouldn't be here normally. */
        cie = fde;
        cie_length = fde_length;
    } else {
        /* Find CIE. */
        /* Positive cie_offset goes backward from current field. */
        cie = fde + 4 - cie_offset;
        if (!try_get_word(memory, cie, &cie_length)) {
            return false;
        }
        if ((int32_t)cie_length == -1) {
            ALOGV("execute_fde: 64-bit dwarf detected, not implemented yet");
            return false;
        }
        if (!try_get_word(memory, cie + 4, &cie_offset)) {
            return false;
        }
        if (cie_offset != 0) {
            ALOGV("execute_fde: can't find CIE");
            return false;
        }
    }
    ALOGV("execute_fde: FDE length: %d", fde_length);
    ALOGV("execute_fde: CIE pointer: %x", cie);
    ALOGV("execute_fde: CIE length: %d", cie_length);

    /* Read CIE:
       Augmentation independent:
       1st byte is version;
       next x bytes is /0 terminated augmentation string;
       next x bytes is unsigned LEB128 encoded code alignment factor;
       next x bytes is signed LEB128 encoded data alignment factor;
       next 1 (CIE version 1) or x (CIE version 3 unsigned LEB128) bytes is return register column;
       Augmentation dependent:
       if 'z' next x bytes is unsigned LEB128 encoded augmentation data size;
       if 'L' next 1 byte is LSDA encoding;
       if 'R' next 1 byte is FDE encoding;
       if 'S' CIE represents signal handler stack frame;
       if 'P' next 1 byte is personality encoding folowed by personality function pointer;
       Next x bytes is CIE program.
    */

    uint32_t c = 8;
    if (!try_get_byte(memory, cie, &cie_info->version, &c)) {
        return false;
    }
    ALOGV("execute_fde: CIE version: %d", cie_info->version);
    uint8_t ch;
    do {
        if (!try_get_byte(memory, cie, &ch, &c)) {
            return false;
        }
        switch (ch) {
        case '\0': break;
        case 'z': cie_info->aug_z = 1; break;
        case 'L': cie_info->aug_L = 1; break;
        case 'R': cie_info->aug_R = 1; break;
        case 'S': cie_info->aug_S = 1; break;
        case 'P': cie_info->aug_P = 1; break;
        default:
            ALOGV("execute_fde: Unrecognized CIE augmentation char: '%c'", ch);
            return false;
            break;
        }
    } while (ch);
    if (!try_get_uleb128(memory, cie, &cie_info->code_align, &c)) {
        return false;
    }
    if (!try_get_sleb128(memory, cie, &cie_info->data_align, &c)) {
        return false;
    }
    if (cie_info->version >= 3) {
        if (!try_get_uleb128(memory, cie, &cie_info->reg, &c)) {
            return false;
        }
    } else {
        if (!try_get_byte(memory, cie, (uint8_t*)&cie_info->reg, &c)) {
            return false;
        }
    }
    ALOGV("execute_fde: CIE code alignment factor: %d", cie_info->code_align);
    ALOGV("execute_fde: CIE data alignment factor: %d", cie_info->data_align);
    if (cie_info->aug_z) {
        if (!try_get_uleb128(memory, cie, &cie_info->aug_z, &c)) {
            return false;
        }
    }
    if (cie_info->aug_L) {
        if (!try_get_byte(memory, cie, &cie_info->aug_L, &c)) {
            return false;
        }
    } else {
        /* Default encoding. */
        cie_info->aug_L = DW_EH_PE_absptr;
    }
    if (cie_info->aug_R) {
        if (!try_get_byte(memory, cie, &cie_info->aug_R, &c)) {
            return false;
        }
    } else {
        /* Default encoding. */
        cie_info->aug_R = DW_EH_PE_absptr;
    }
    if (cie_info->aug_P) {
        /* Get encoding of personality routine pointer. We don't use it now. */
        if (!try_get_byte(memory, cie, (uint8_t*)&cie_info->aug_P, &c)) {
            return false;
        }
        /* Get routine pointer. */
        if (!read_dwarf(memory, cie, &cie_info->aug_P, (uint8_t)cie_info->aug_P, &c)) {
            return false;
        }
    }
    /* CIE program. */
    /* Length field itself (4 bytes) is not included into length. */
    stack[0] = *dstate;
    stack_ptr = 1;
    while (c < cie_length + 4) {
        if (!execute_dwarf(memory, cie, cie_info, dstate, &c, stack, &stack_ptr)) {
            return false;
        }
    }

    /* We went directly to CIE. Normally it shouldn't occur. */
    if (cie == fde) return true;

    /* Go back to FDE. */
    c = 8;
    /* Read FDE:
       Augmentation independent:
       next x bytes (encoded as specified in CIE) is FDE starting address;
       next x bytes (encoded as specified in CIE) is FDE number of instructions covered;
       Augmentation dependent:
       if 'z' next x bytes is unsigned LEB128 encoded augmentation data size;
       if 'L' next x bytes is LSDA pointer (encoded as specified in CIE);
       Next x bytes is FDE program.
    */
    if (!read_dwarf(memory, fde, &fde_info->start, (uint8_t)cie_info->aug_R, &c)) {
        return false;
    }
    dstate->loc = fde_info->start;
    ALOGV("execute_fde: FDE start: %x", dstate->loc);
    if (!read_dwarf(memory, fde, &fde_info->length, 0, &c)) {
        return false;
    }
    ALOGV("execute_fde: FDE length: %x", fde_info->length);
    if (cie_info->aug_z) {
        if (!try_get_uleb128(memory, fde, &fde_info->aug_z, &c)) {
            return false;
        }
    }
    if (cie_info->aug_L && cie_info->aug_L != DW_EH_PE_omit) {
        if (!read_dwarf(memory, fde, &fde_info->aug_L, cie_info->aug_L, &c)) {
            return false;
        }
    }
    /* FDE program. */
    /* Length field itself (4 bytes) is not included into length. */
    /* Save CIE state as 0 element of stack. Used by DW_CFA_restore. */
    stack[0] = *dstate;
    stack_ptr = 1;
    while (c < fde_length + 4 && state->reg[DWARF_PC] >= dstate->loc) {
        if (!execute_dwarf(memory, fde, cie_info, dstate, &c, stack, &stack_ptr)) {
            return false;
        }
        ALOGV("PC: %x, LOC: %x", state->reg[DWARF_PC], dstate->loc);
    }

    return update_state(memory, state, dstate);
}

static bool heuristic_state_update(const memory_t* memory, unwind_state_t* state)
{
    bool found_start = false;
    int maxcheck = 1024;
    int32_t stack_size = 0;
    int32_t ra_offset = 0;
    dwarf_state_t dwarf_state;
    dwarf_state_t* dstate = &dwarf_state;

    static struct {
        uint32_t insn;
        uint32_t mask;
    } frame0sig[] = {
        {0x3c1c0000, 0xffff0000}, /* lui     gp,xxxx */
        {0x279c0000, 0xffff0000}, /* addiu   gp,gp,xxxx */
        {0x039fe021, 0xffffffff}, /* addu    gp,gp,ra */
    };
    const int nframe0sig = sizeof(frame0sig)/sizeof(frame0sig[0]);
    int f0 = nframe0sig;
    memset(dstate, 0, sizeof(dwarf_state_t));

    /* Search code backwards looking for function prologue */
    for (uint32_t pc = state->reg[DWARF_PC]-4; maxcheck-- > 0 && !found_start; pc -= 4) {
        uint32_t op;
        int32_t immediate;

        if (!try_get_word(memory, pc, &op))
            return false;

        // ALOGV("@0x%08x: 0x%08x\n", pc, op);

        // Check for frame 0 signature
        if ((op & frame0sig[f0].mask) == frame0sig[f0].insn) {
            if (f0 == 0)
                return false;
            f0--;
        }
        else {
            f0 = nframe0sig;
        }

        switch (op & 0xffff0000) {
        case 0x27bd0000: // addiu sp, imm
            // looking for stack being decremented
            immediate = (((int32_t)op) << 16) >> 16;
            if (immediate < 0) {
                stack_size = -immediate;
                ALOGV("@0x%08x: found stack adjustment=%d\n", pc, stack_size);
            }
            break;
        case 0x039f0000: // e021

        case 0xafbf0000: // sw ra, imm(sp)
            ra_offset = (((int32_t)op) << 16) >> 16;
            ALOGV("@0x%08x: found ra offset=%d\n", pc, ra_offset);
            break;
        case 0x3c1c0000: // lui gp
            ALOGV("@0x%08x: found function boundary", pc);
            found_start = true;
            break;
        default:
            break;
        }
    }

    dstate->cfa_reg = DWARF_SP;
    dstate->cfa_off = stack_size;

    if (ra_offset) {
        dstate->regs[DWARF_RA].rule = 'o';
        dstate->regs[DWARF_RA].value = -stack_size + ra_offset;
    }

    return update_state(memory, state, dstate);
}

static ssize_t unwind_backtrace_common(const memory_t* memory,
        const map_info_t* map_info_list,
        unwind_state_t* state, backtrace_frame_t* backtrace,
        size_t ignore_depth, size_t max_depth) {

    size_t ignored_frames = 0;
    size_t returned_frames = 0;

    ALOGV("Unwinding tid: %d", memory->tid);
    ALOGV("PC: %x", state->reg[DWARF_PC]);
    ALOGV("RA: %x", state->reg[DWARF_RA]);
    ALOGV("FP: %x", state->reg[DWARF_FP]);
    ALOGV("SP: %x", state->reg[DWARF_SP]);

    for (size_t index = 0; returned_frames < max_depth; index++) {
        uintptr_t fde = find_fde(memory, map_info_list, state->reg[DWARF_PC]);
        backtrace_frame_t* frame = add_backtrace_entry(
            index ? rewind_pc_arch(memory, state->reg[DWARF_PC]) : state->reg[DWARF_PC],
            backtrace, ignore_depth, max_depth,
            &ignored_frames, &returned_frames);
        uint32_t stack_top = state->reg[DWARF_SP];

        if (fde) {
            /* Use FDE to update state */
            if (!execute_fde(memory, fde, state))
                break;
        }
        else {
            /* FDE is not found, update state heuristically */
            if (!heuristic_state_update(memory, state))
                break;
        }

        if (frame) {
            frame->stack_top = stack_top;
            if (stack_top < state->reg[DWARF_SP]) {
                frame->stack_size = state->reg[DWARF_SP] - stack_top;
            }
        }
        ALOGV("Stack: 0x%x ... 0x%x - %d bytes", frame->stack_top, state->reg[DWARF_SP], frame->stack_size);
    }
    return returned_frames;
}

ssize_t unwind_backtrace_signal_arch(siginfo_t* siginfo __attribute__((unused)), void* sigcontext,
        const map_info_t* map_info_list,
        backtrace_frame_t* backtrace, size_t ignore_depth, size_t max_depth) {
    const ucontext_t* uc = (const ucontext_t*)sigcontext;

    unwind_state_t state;
    state.reg[DWARF_PC] = uc->uc_mcontext.pc;
    state.reg[DWARF_RA] = uc->uc_mcontext.gregs[REG_RA];
    state.reg[DWARF_FP] = uc->uc_mcontext.gregs[REG_S8];
    state.reg[DWARF_SP] = uc->uc_mcontext.gregs[REG_SP];

    ALOGV("unwind_backtrace_signal_arch: "
          "ignore_depth=%d max_depth=%d pc=0x%08x sp=0x%08x ra=0x%08x\n",
          ignore_depth, max_depth, state.reg[DWARF_PC], state.reg[DWARF_SP], state.reg[DWARF_RA]);

    memory_t memory;
    init_memory(&memory, map_info_list);
    return unwind_backtrace_common(&memory, map_info_list,
                                   &state, backtrace, ignore_depth, max_depth);
}

ssize_t unwind_backtrace_ptrace_arch(pid_t tid, const ptrace_context_t* context,
        backtrace_frame_t* backtrace, size_t ignore_depth, size_t max_depth) {

    user_regs_struct regs;
    if (ptrace(PTRACE_GETREGS, tid, 0, &regs)) {
        return -1;
    }

    unwind_state_t state;
    state.reg[DWARF_PC] = regs.epc;
    state.reg[DWARF_RA] = regs.regs[REG_RA];
    state.reg[DWARF_FP] = regs.regs[REG_S8];
    state.reg[DWARF_SP] = regs.regs[REG_SP];

    ALOGV("unwind_backtrace_ptrace_arch: "
          "ignore_depth=%d max_depth=%d pc=0x%08x sp=0x%08x ra=0x%08x\n",
          ignore_depth, max_depth, state.reg[DWARF_PC], state.reg[DWARF_SP], state.reg[DWARF_RA]);

    memory_t memory;
    init_memory_ptrace(&memory, tid);
    return unwind_backtrace_common(&memory, context->map_info_list,
                                   &state, backtrace, ignore_depth, max_depth);
}