Ting 이네 Software 이야기

Following code is part of software - written by me - that is used to analyze memory data.
Even if this just small part of software, I think this can help understand the way of unwinding stack by using DWARF information. Following sample code is to analyze DWARF information generated from C code.
For more details about unwinding stack. See this post.

const CDwf_Dbg*
CFrameS::_Get_dwf_dbg(DvAddr pc) const
{
  CDwf_Dbg*   dwf_dbg = NULL;

  for(int i=0; i<_dwfs->Size(); i++) {
    if( (*_dwfs)[i]->Is_in_fde(pc) ) { dwf_dbg = (*_dwfs)[i]; break; }
  }
  return dwf_dbg;
}

// "frm->regs" should have valid values before call this function.
int
CFrameS::_Set_frame_info(_CFrm_Info* fi) const
{
  if(REG_VAL_UNDEF==fi->regs[_tgt->Pci()].from) { return -1; }

  const CDwf_Dbg* dwf_dbg = _Get_dwf_dbg(REG_PC(fi->regs[_tgt->Pci()].val));

  if(dwf_dbg)
  {
    if( dwf_dbg->ArangeS() ) {
      ASSERT(REG_VAL_UNDEF != fi->regs[_tgt->Pci()].from);
      fi->fdie = dwf_dbg->ArangeS()->Subprogram_die(REG_PC(fi->regs[_tgt->Pci()].val), &fi->cudie);
    }
    else {
      fi->cudie = NULL;
      fi->fdie = NULL;
    }

    if( dwf_dbg->FdeS() ) {
      ASSERT(REG_VAL_UNDEF != fi->regs[_tgt->Pci()].from)
      fi->fde = dwf_dbg->FdeS()->Get_fde(REG_PC(fi->regs[_tgt->Pci()].val), NULL, NULL);
    }
    else { fi->fde = NULL; }

    if(fi->cudie)
    {
      CLine*  ln = CLine::Create(*fi->cudie);
      ln->Lineno(REG_PC(fi->regs[_tgt->Pci()].val), &fi->line, &fi->column);
      if(ln) { MDELETE(ln); }
    }
  }
  else
  {
    // There is no debugging information about this.
    // But we have address value of PC. So, it's not fail!
    fi->cudie = NULL;
    fi->fdie = NULL;
    fi->fde = NULL;
  }

  return 0;
}

int
CFrameS::_Create_previous_frame_info(_CFrm_Info* outfi, const _CFrm_Info* fi) const
{
  ASSERT(outfi && fi);

  bool          b_exact = true;
#ifdef __RT_DEBUG__
  DvAddr        fde_lopc, fdie_lopc;
#endif // __RT_DEBUG__

  if( (REG_VAL_UNDEF == fi->regs[_tgt->Pci()].from)
      || (REG_VAL_UNDEF == fi->regs[_tgt->Spi()].from) ) { goto no_info; }

  const CDwf_Dbg* dwf_dbg = _Get_dwf_dbg(REG_PC(fi->regs[_tgt->Pci()].val));

  if(dwf_dbg && dwf_dbg->FdeS() && fi->fde)
  {
    DvHalf      lri = dwf_dbg->FdeS()->Get_return_addr_register(fi->fde);

    // initial reg values of this frame
    if(0 > dwf_dbg->FdeS()->Get_all_regs(outfi->regs, fi->regs,
                                          fi->fde, REG_PC(fi->regs[_tgt->Pci()].val)))
    { goto fail; }

    if(REG_VAL_UNDEF == outfi->regs[lri].from) { goto fail; }

    outfi->regs[_tgt->Pci()] = outfi->regs[lri];
    COMPENSATE_PC_AHEAD_OF_LR(outfi->regs[_tgt->Pci()].val);

    if(fi->fdie && fi->cudie)
    {
#ifdef __RT_DEBUG__
      fde_lopc = dwf_dbg->FdeS()->Fde_lopc(fi->fde);
      if(0 > fi->fdie->LoPC(&fdie_lopc)) { goto fail; }

      if(fde_lopc != fdie_lopc) { ASSERT(FALSE); goto fail; }
#endif // __RT_DEBUG__

      if(fi->fdie->Has(DW_AT_frame_base))
      {
        DvUSign             val;
        int                 val_type;
        DvAddr              culo;
        bool                b_exact = false;
        CArr<CLoc_Desc*> locarr;
        if(0 > fi->fdie->Frame_base(&locarr) ) {goto fail; }
        ASSERT(REG_VAL_UNDEF != fi->regs[_tgt->Pci()].from);
        if(0 > fi->cudie->LoPC(&culo)) { goto fail; }

        if(0 > CLocS::Interpret(&val_type, &val, &b_exact,_tgt,
                                REG_PC(fi->regs[_tgt->Pci()].val) - culo,
                                INVALID_FRAME_BASE, fi->regs, locarr) ) { goto fail; }
        if(!b_exact){ goto fail; } // this should be exact value.!

        //ASSERT( (LOC_VAL_REG == val_type) || (LOC_VAL_UCONST == val_type) );
        outfi->regs[_tgt->Spi()].val = val;
        outfi->regs[_tgt->Spi()].from = REG_VAL_FROM_REG;
      } // if(fi->fdie->Has(DW_AT_frame_base))
      else if(fi->fdie->Has(DW_AT_abstract_origin) )
      { // this may be inlined function
        CDieI* ofdie = fi->fdie->Original_die(ORI_PURE);

#ifdef  __RT_DEBUG__
        ODPRINTF(("========*********=========\n"));
        ODPRINTF(("Tag: %s\n", dwarf_get_tagCN(fi->fdie->Tag()) ));
        fi->fdie->ODPrint_attributes();
        ODPRINTF(("=========*********============\n"));
        ODPRINTF(("Tag:%s\n", dwarf_get_tagCN(ofdie->Tag()) ));
        ofdie->ODPrint_attributes();
        //ASSERT(FALSE);
#endif // __RT_DEBUG__
        if(ofdie->Has(DW_AT_inline)) {
          outfi->regs[_tgt->Spi()] = fi->regs[_tgt->Spi()];
        }
        else { ASSERT(FALSE); }
        MDELETE(ofdie);
      }
      else { ASSERT(FALSE); }
    }
    else
    {
#ifdef COMPILER_ADS12
      DvSign off;
      if( 0 <= dwf_dbg->FdeS()->Get_cfa_offset_via_sp(&off, fi->fde, fi->regs[_tgt->Pci()].val) )
      {
        if(0 == off) { goto fail; } // If value of stack pointer is not changed, than we can assume that virtual unwinding fails.
        else {
          outfi->regs[_tgt->Spi()].val = fi->regs[_tgt->Spi()].val+off;
          outfi->regs[_tgt->Spi()].from = fi->regs[_tgt->Spi()].from;
        }
      }
      else
#endif // COMPILER_ADS12
      { goto no_info; }
    }
  }
  else  // if(dwf_dbg && dwf_dbg->FdeS() && fi->fde)
  {
    static const int  __UNW_INST_CNT  = 1000;

    bool b_success = false;
    // try to unwind stack with raw machine instruction!!
    if(_unw)
    {
      UnwRT*    unwr;
      MMNEW(unwr, , UnwRT, _tgt->Num_regs());
      for(int i=0; i<_tgt->Num_regs(); i++) {
        unwr[i].v = fi->regs[i].val;
        unwr[i].o = (REG_VAL_UNDEF==fi->regs[i].from)? UNWR_INVALID: UNWR_VALID;
      }

      if( UNW_OK == _unw->Unw(unwr, __UNW_INST_CNT, _stk_base))
      {
        for(int i=0; i<_tgt->Num_regs(); i++) {
          ASSERT( (UNWR_VALID==unwr[_tgt->Pci()].o)&&(UNWR_VALID==unwr[_tgt->Spi()].o) );
          outfi->regs[i].val = unwr[i].v;
          // We can assume that valid register value comes from stack.
          outfi->regs[i].from = (UNWR_VALID==unwr[i].o)? REG_VAL_FROM_ADDR: REG_VAL_UNDEF;
        }
        b_success = true;;
      }
      MMDELETE(unwr);
      COMPENSATE_PC_AHEAD_OF_LR(outfi->regs[_tgt->Pci()].val);
    } // if(_unw)
    if(!b_success) { goto fail; }
  } // else  // if(dwf_dbg && dwf_dbg->FdeS() && fi->fde)

  // Unexpected case. - infinite loop!! if this happened
  // If PC is on 'very strange position' this can be happened
  // previous frame is exactly same with current frame! This cannot happened in normal situation!
  if( (REG_VAL_UNDEF != outfi->regs[_tgt->Pci()].from)
      && (outfi->regs[_tgt->Spi()].val == fi->regs[_tgt->Spi()].val)
      && (outfi->regs[_tgt->Pci()].val == fi->regs[_tgt->Pci()].val)
      && (outfi->regs[_tgt->Lri()].val == fi->regs[_tgt->Lri()].val) )
  { goto fail; }

  if(0 > _Set_frame_info(outfi) ) { goto fail; }

  return (b_exact)? FRAME_OK: FRAME_NOT_EXACT;

fail:
  return FRAME_FAIL;

no_info:
  return FRAME_NO_DBG_INFO;

}

int
CFrameS::Construct_frame_stack(const RegT* regs)
{
  for(int i=0; i<_frame.Size(); i++) { MDELETE(_frame[i]); }
  _frame.Reset();

  int         frm_ret;
  bool        b_end = false;

  // flag to retry frame unwind
  bool        b_retry = true;
  _CFrm_Info* prev_fi = NULL;
  _CFrm_Info* next_fi = NULL;

  MNEW(prev_fi, , _CFrm_Info, (_num_regs));
  for(int i=0; i<_num_regs; i++) {
    prev_fi->regs[i].from = regs[i].from;
    prev_fi->regs[i].val = regs[i].val;
  }

  if(0 > _Set_frame_info(prev_fi) ) { goto fail; }
  _frame.Append(prev_fi);
  _ODPrint_frame_name(prev_fi);
  prev_fi = prev_fi->Clone();

  for(;;)
  {
    ASSERT(REG_VAL_UNDEF != prev_fi->regs[_tgt->Pci()].from);

    MNEW(next_fi, , _CFrm_Info, (_num_regs));
    frm_ret = _Create_previous_frame_info(next_fi, prev_fi);

    switch(frm_ret)
    {
      case FRAME_NOT_EXACT:
      case FRAME_OK:
        ASSERT(prev_fi && next_fi);
        _frame.Append(next_fi);
        MDELETE(prev_fi);
        prev_fi = next_fi->Clone();
        next_fi = NULL;
#ifdef __RT_DEBUG__
        if(prev_fi->fdie) {
          _ODPrint_frame_name(prev_fi);
        }
        else if(REG_VAL_UNDEF != prev_fi->regs[_tgt->Pci()].from) {
          ODPRINTF(("-- [0x%8x]\n", prev_fi->regs[_tgt->Pci()].val));
        }
#endif // __RT_DEBUG__

#ifdef ARCHITECTURE_ARM
        // In ARM, stack grows in negative direction.
        if( (REG_VAL_UNDEF != prev_fi->regs[_tgt->Spi()].from)
          && (prev_fi->regs[_tgt->Spi()].val >= _stk_base ) ) {
          frm_ret = FRAME_END;
          goto end_of_loop;
        }
#endif // ARCHITECTURE_ARM
      break;

      case FRAME_FAIL:
      case FRAME_NO_DBG_INFO:
        ASSERT(prev_fi);
        MDELETE(next_fi); 

        // Check whether previous frame is top of frame or not.
        if( (1 == _frame.Size()) && b_retry )
        {
          b_retry = false;
          ///////////////////////////////////
          // Let's try again with LR!! if previous frame is top of stack!!
          // (There are lots of cases that pc is corrupted in the top of stack!! (ex. prefetch abort))

          /////////////////////////////////////////////////////////////
          // CHECK IT! : "Try with LR" is good for approximation?!
          //  - Careful investigation is needed!
          /////////////////////////////////////////////////////////////
          DvAddr  lrpc = prev_fi->regs[_tgt->Lri()].val;
          COMPENSATE_PC_AHEAD_OF_LR(lrpc);

          if( (REG_VAL_UNDEF != prev_fi->regs[_tgt->Lri()].from)
              && (lrpc != prev_fi->regs[_tgt->Pci()].val) )
          {
            prev_fi->regs[_tgt->Pci()].val = lrpc;
            if(0 > _Set_frame_info(prev_fi) ) { goto fail; }  // set new frame info for retrying with LR.
          }
          else { goto end_of_loop; }
        }
        else { goto end_of_loop; }
      break;

      default:
        ASSERT(FALSE);
    } // switch
    continue;

end_of_loop:
    break;
  } // for(;;)

  if(prev_fi) { MDELETE(prev_fi); }
  if(next_fi) { MDELETE(next_fi); }

  _frame_status = frm_ret;
  return 0;

fail:
  if(prev_fi) { MDELETE(prev_fi); }
  if(next_fi) { MDELETE(next_fi); }
  return -1;
}

Following code is part of software - written by me - that is used to analyze memory data.
I think this can be good sample to help understand the way of "unwinding stack by pseudo execution". For more details see this post.

static void
_invalidate_variable_registers(UnwRT* r)
{
  for(int i=0; i<13; i++) { r[i].o = UNWR_INVALID; }
}

int
CRawunw::_Unw_thumb(UnwRT* r, unsigned int inst_cnt, unsigned int stack_base) const
{
#define __IS_IN_DUMPED_STACK(aDDR) ( (stack_base>=(aDDR)) && ((aDDR)<=osp) )

#ifdef UNW_ESCAPE_INFINITE_LOOP
  CArr<_CBInfo>   cbi;
#endif // UNW_ESCAPE_INFINITE_LOOP
  unsigned short instr;
  unsigned int   osp = r[13].v; // original sp.
  for(;;)
  {
    if(inst_cnt==0) {
      return UNW_INST_CNT_EXPIRED;
    }
    // PC is still on thumb.
    if(!(r[15].v&0x1)) { return UNW_FAIL; }
    //ASSERT(r[15].v&0x1);

    // Check PC & SP is OK.
    if((UNWR_INVALID==r[15].o)||(UNWR_INVALID==r[13].o)) {
		//ASSERT(FALSE);
		return UNW_FAIL;
    }

    if(stack_base <= r[13].v) {
      return UNW_END_OF_FRAME;
    }

    if(0 > _read2(_user, r[15].v&(~0x1), &instr)) {
      /*ASSERT(FALSE);*/ return UNW_FAIL;
    }

    // Undefined instruction
    if( ((instr & 0xf801) == 0xe801)
#if 0 // followings can be 'defined instrucion' in future!
        || ((instr & 0xff00) == 0xbf00)
        || ((instr & 0xff00) == 0xb100)
        || ((instr & 0xfa00) == 0xb200)
        || ((instr & 0xfc00) == 0xb800)
#endif
        ) {
      // undefined instruction. Unwinding SHOULD BE Stopped!
      return UNW_FAIL;
    }

    //Hi register operations/branch exchange
    else if((instr & 0xfc00) == 0x4400)
    {
      unsigned char    op  = (instr & 0x0300) >> 8;
      char h1  = (instr & 0x0080) ? TRUE: FALSE;
      char h2  = (instr & 0x0040) ? TRUE: FALSE;
      unsigned char    rs = (instr & 0x0038) >> 3;
      unsigned char    rd = (instr & 0x0007);

      // Adjust the register numbers
      if(h2) { rs += 8; }
      if(h1) { rd += 8; }

      if(op != 3 && !h1 && !h2) {
        ODPRINTF(("Invalid Instruction:0x%x", instr));
        return UNW_FAIL;
      }

      switch(op)
      {
        case 0: // ADD
          if((15==rd)&&(13==rd)) { ASSERT(FALSE); return UNW_FAIL; }
          else {
            r[rd].v += r[rs].v;
            r[rd].o = ((UNWR_VALID == r[rd].o) && (UNWR_VALID == r[rs].o) )? UNWR_VALID: UNWR_INVALID;
            ASSERT(UNWR_VALID == r[13].o);
          }
        break;

        case 1: // CMP
          ; // nothing to do!
        break;

        case 2: // MOV
          if((15==rd)&&(14==rs)&&(UNWR_VALID==r[rs].o)) {
            r[15]=r[14];
            return UNW_OK;
          }
          else {
            r[rd] = r[rs];
            ASSERT(UNWR_VALID == r[13].o);
          }
        break;

        case 3: // BX
          // if "14==rs" and it is valid than this is return!
          if(14==rs)
          {
            if(UNWR_VALID==r[rs].o) {
              ODPRINTF(("!!!Return PC=0x%x\n", r[rs].v));
              r[15]=r[rs];
              return UNW_OK;
            }
            else {
              ASSERT(FALSE);
              ODPRINTF(("!!!BX Fail\n"));
              return UNW_FAIL;
            }
          }
          // BX to somewhere. Just ignore it! - do nothing!!
          ODPRINTF(("!!!BX is ignored! [%s] 0x%x\n", (UNWR_VALID==r[rs].o)? "Valid": "Invalid", r[rs].v));
        break;
      }
    }
    //  ADD sp,#+imm
    //  ADD sp,#-imm
    else if((instr & 0xff00) == 0xb000)
    {
      unsigned short value = (instr & 0x7f) * 4;
      /* Check the negative bit */
      if(instr & 0x80) {
        r[13].v -= value;
        ODPRINTF(("*** SP(-) : 0x%x\n", r[13].v));
      }
      else {
        r[13].v += value;
        ODPRINTF(("*** SP(+) : 0x%x\n", r[13].v));
      }
    }
    //  PUSH {Rlist}
    //  PUSH {Rlist, LR}
    //  POP {Rlist}
    //  POP {Rlist, PC}
    else if((instr & 0xf600) == 0xb400)
    {
      char  L     = (instr & 0x0800) ? TRUE : FALSE;
      char  R     = (instr & 0x0100) ? TRUE : FALSE;
      unsigned char     r_list = (instr & 0x00ff);

      if(L) // stack grows in negative direction in ARM.
      {
        for(int i=0; i<8; i++)
        {
          if(r_list & (0x1 << i))
          {
            // value only in dumped stack is valid!
            if( __IS_IN_DUMPED_STACK(r[13].v) ) {
              // Read the word
              if(0 > _read4(_user, r[13].v, &(r[i].v)) ) { ASSERT(FALSE); return UNW_FAIL; }
              r[i].o = UNWR_VALID;
              ODPRINTF(("  r%d = 0x%08x\n", i, r[i].v));
            }
            else { r[i].o = UNWR_INVALID; }
            r[13].v += 4;
          }
        }

        // Check if the PC is to be popped
        if(R)
        {
          // Get the return address
          if(0 > _read4(_user, r[13].v, &(r[15].v)) ) { ASSERT(FALSE); return UNW_FAIL; }
          r[15].o = UNWR_VALID;
          ODPRINTF((" Return PC=%x\n", r[15].v));
          r[13].v += 4;
          return UNW_OK; // success.
        } // if(R)
        ODPRINTF(("*** SP(L) : 0x%x\n", r[13].v));
      } // if(L)
      else
      {
        // Stack grows. But we can't believe the values. So, just increase stack pointer!!
        // Check if the LR is to be pushed
        if(R) { r[13].v -= 4; }
        for(int i=7; i>=0; i--) {
          if(r_list & (0x1 << i)) { r[13].v -= 4; }
        }
        ODPRINTF(("*** SP(!L) : 0x%x\n", r[13].v));
      }
    }
    //  B label
    else if((instr&0xf800) == 0xe000)
    {
      short brv = (instr&0x07ff);
      if(brv & 0x400) { brv |= 0xf800; }

      // Branch distance is twice that specified in the instruction.
      brv *= 2;

#ifdef UNW_ESCAPE_INFINITE_LOOP
      int  idx = -1;
      for(int i=0; i<cbi.Size(); i++) {
        if(cbi[i].pc==r[15].v) { idx=i; break; }
      }
      if(idx>=0)
      { // found
        if(cbi[idx].b_jump) { cbi[idx].b_jump = false; }
        else {
          cbi[idx].b_jump = true;
          // branch
          r[15].v += brv; r[15].v += 2; // prefetch advance.
        }
      }
      else
      {
        // default is "Jump"
        _CBInfo  info(r[15].v, true);
        cbi.Append(info);
        // branch
        r[15].v += brv; r[15].v += 2; // prefetch advance.
      }
#else // UNW_ESCAPE_INFINITE_LOOP
      r[15].v += brv;
      // Need to advance by a word to account for pre-fetch.
      //  Advance by a half word here, allowing the normal address
      //  advance to account for the other half word.
      r[15].v += 2;
#endif // UNW_ESCAPE_INFINITE_LOOP
    }
#ifdef UNW_ESCAPE_INFINITE_LOOP
    // B<cond> label
    else if((instr&0xf000) == 0xd000)
    {
      short immed8  = instr&0x00ff;
      int  idx = -1;
      for(int i=0; i<cbi.Size(); i++) {
        if(cbi[i].pc==r[15].v) { idx=i; break; }
      }
      if(idx>=0)
      { // found
        if(cbi[idx].b_jump) { cbi[idx].b_jump = false; }
        else {
          cbi[idx].b_jump = true;
          // try to jump
          r[15].v += immed8*2;
          r[15].v += 2; // prefetch advance.
        }
      }
      else {
        // default is "Pass"
        _CBInfo  info(r[15].v, false);
        cbi.Append(info);
      }
    }
#endif // UNW_ESCAPE_INFINITE_LOOP
    // ADD <Rd>, PC/SP, #<immed_8>*4
    // It is not essential But, because sp and pc are always 'valid', result is valid.
    // So, I put this. BUT IT'S NOT ESSENTIAL!
    else if((instr&0xf000) == 0xa000)
    {
      unsigned char rd = (instr&0x0700)>>8;
      unsigned short imm8 = (instr&0x00ff)<<2;
      if(instr&0x0800) { r[rd].v = r[13].v + imm8; }    // SP
      else { r[rd].v = (r[15].v & 0xfffffffc) + imm8; } // PC
    }
    // LDR <Rd> [SP, #<immd_8>*4]
    // It is not essential. But, because original stack is 'valid', in most case, result is valid.
    // So, I put this. BUT IT'S NOT ESSENTIAL!
    else if((instr&0xf800) == 0x9800)
    {
      char  rd = instr&0x0700 >> 8;
      short imm8d = instr&0x00ff;
      unsigned int addr = r[13].v+imm8d*4;
      if(addr%4) { ASSERT(FALSE); return UNW_FAIL; }
      if(osp<=addr) { // valid stack.
        if(0 > _read4(_user, addr, &(r[rd].v))) { ODPRINTF(("Cannot read from stack\n")); ASSERT(FALSE); return UNW_FAIL; }
        r[rd].o = UNWR_VALID;  // assume that value from stack or constant!.
      }
      else {
        r[rd].o = UNWR_INVALID;
      }
    }
    else  // invalidate registers
    {
      _invalidate_variable_registers(r);
    }

    r[15].v += 2;
    inst_cnt--;
  }

#undef __IS_IN_DUMPED_STACK
}