/*

  Copyright (C) 2000,2002,2004,2005,2006 Silicon Graphics, Inc.  All Rights Reserved.

  Portions Copyright (C) 2007 David Anderson. All Rights Reserved.

  This program is free software; you can redistribute it and/or modify it

  under the terms of version 2.1 of the GNU Lesser General Public License 

  as published by the Free Software Foundation.

  This program is distributed in the hope that it would be useful, but

  WITHOUT ANY WARRANTY; without even the implied warranty of

  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

  Further, this software is distributed without any warranty that it is

  free of the rightful claim of any third person regarding infringement 

  or the like.  Any license provided herein, whether implied or 

  otherwise, applies only to this software file.  Patent licenses, if

  any, provided herein do not apply to combinations of this program with 

  other software, or any other product whatsoever.  

  You should have received a copy of the GNU Lesser General Public 

  License along with this program; if not, write the Free Software 

  Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston MA 02110-1301,

  USA.

  Contact information:  Silicon Graphics, Inc., 1500 Crittenden Lane,

  Mountain View, CA 94043, or:

  http://www.sgi.com

  For further information regarding this notice, see:

  http://oss.sgi.com/projects/GenInfo/NoticeExplan

*/

/* The address of the Free Software Foundation is

   Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, 

   Boston, MA 02110-1301, USA.

   SGI has moved from the Crittenden Lane address.

*/

#include "config.h"

#include "dwarf_incl.h"

#include <stdio.h>

#include <stdlib.h>

#include "dwarf_frame.h"

#include "dwarf_arange.h"	/* Using Arange as a way to build a

				   list */

#define FDE_NULL_CHECKS_AND_SET_DBG(fde,dbg )          \

    do {                                               \

     if ((fde) == NULL) {                              \

        _dwarf_error(NULL, error, DW_DLE_FDE_NULL);    \

        return (DW_DLV_ERROR);                         \

    }                                                  \

    (dbg)= (fde)->fd_dbg;                              \

    if ((dbg) == NULL) {                               \

        _dwarf_error(NULL, error, DW_DLE_FDE_DBG_NULL);\

        return (DW_DLV_ERROR);                         \

    } } while (0)

#define MIN(a,b)  (((a) < (b))? a:b)

static void _dwarf_init_regrule_table(struct Dwarf_Reg_Rule_s *t1reg,

				      int last_reg_num,

				      int initial_value);

static int dwarf_initialize_fde_table(Dwarf_Debug dbg,

				      struct Dwarf_Frame_s *fde_table,

				      unsigned table_real_data_size,

				      Dwarf_Error * error);

static void dwarf_free_fde_table(struct Dwarf_Frame_s *fde_table);

#if 0

/* Only used for debugging libdwarf. */

static void dump_frame_rule(char *msg,

			    struct Dwarf_Reg_Rule_s *reg_rule);

#endif

/* 

    This function is the heart of the debug_frame stuff.  Don't even

    think of reading this without reading both the Libdwarf and 

    consumer API carefully first.  This function basically executes     

    frame instructions contained in a Cie or an Fde, but does in a      

    number of different ways depending on the information sought.       

    Start_instr_ptr points to the first byte of the frame instruction    

    stream, and final_instr_ptr to the to the first byte after the       

    last.                                                                

    The offsets returned in the frame instructions are factored.  That   

    is they need to be multiplied by either the code_alignment_factor    

    or the data_alignment_factor, as appropriate to obtain the actual      

    offset.  This makes it possible to expand an instruction stream      

    without the corresponding Cie.  However, when an Fde frame instr     

    sequence is being expanded there must be a valid Cie with a pointer  

    to an initial table row.                                             

    If successful, returns DW_DLV_OK

		And sets returned_count thru the pointer

		 if make_instr is true.

		If make_instr is false returned_count 

		 should NOT be used by the caller (returned_count

		 is set to 0 thru the pointer by this routine...)

    If unsuccessful, returns DW_DLV_ERROR

		and sets returned_error to the error code

    It does not do a whole lot of input validation being a private 

    function.  Please make sure inputs are valid.

    (1) If make_instr is true, it makes a list of pointers to              

    Dwarf_Frame_Op structures containing the frame instructions          

    executed.  A pointer to this list is returned in ret_frame_instr.    

    Make_instr is true only when a list of frame instructions is to be   

    returned.  In this case since we are not interested in the contents  

    of the table, the input Cie can be NULL.  This is the only case

    where the inpute Cie can be NULL.

    (2) If search_pc is true, frame instructions are executed till       

    either a location is reached that is greater than the search_pc_val

    provided, or all instructions are executed.  At this point the       

    last row of the table generated is returned in a structure.          

    A pointer to this structure is supplied in table.                    

    (3) This function is also used to create the initial table row       

    defined by a Cie.  In this case, the Dwarf_Cie pointer cie, is       

    NULL.  For an FDE, however, cie points to the associated Cie.        

    make_instr - make list of frame instr? 0/1

    ret_frame_instr -  Ptr to list of ptrs to frame instrs

    search_pc  - Search for a pc value?  0/1

     search_pc_val -  Search for this pc value

    initial_loc - Initial code location value.

    start_instr_ptr -   Ptr to start of frame instrs.

    final_instr_ptr -   Ptr just past frame instrs. 

    table       -     Ptr to struct with last row. 

    cie     -   Ptr to Cie used by the Fde.

*/

int

_dwarf_exec_frame_instr(Dwarf_Bool make_instr,

			Dwarf_Frame_Op ** ret_frame_instr,

			Dwarf_Bool search_pc,

			Dwarf_Addr search_pc_val,

			Dwarf_Addr initial_loc,

			Dwarf_Small * start_instr_ptr,

			Dwarf_Small * final_instr_ptr,

			Dwarf_Frame table,

			Dwarf_Cie cie,

			Dwarf_Debug dbg,

			Dwarf_Half reg_num_of_cfa,

			Dwarf_Sword * returned_count,

			int *returned_error)

{

#define ERROR_IF_REG_NUM_TOO_HIGH(macreg,machigh_reg)               \

     do {                                             \

       if ((macreg) >= (machigh_reg) || (macreg) < 0) {            \

	SIMPLE_ERROR_RETURN(DW_DLE_DF_REG_NUM_TOO_HIGH); \

       }                                              \

     } /*CONSTCOND */ while(0)

#define SIMPLE_ERROR_RETURN(code) \

        free(localregtab); \

        *returned_error = code; \

        return DW_DLV_ERROR

    /* Sweeps the frame instructions. */

    Dwarf_Small *instr_ptr;

    /* Register numbers not limited to just 255, thus not using

       Dwarf_Small. */

    typedef int reg_num_type;

    Dwarf_Unsigned factored_N_value;

    Dwarf_Signed signed_factored_N_value;

    Dwarf_Addr current_loc = initial_loc;	/* code location/

						   pc-value

						   corresponding to the 

						   frame instructions.

						   Starts at zero when

						   the caller has no

						   value to pass in. */

    /* Must be min de_pointer_size bytes and must be at least sizeof

       Dwarf_ufixed */

    Dwarf_Unsigned adv_loc;

    int reg_count = dbg->de_frame_reg_rules_entry_count;

    struct Dwarf_Reg_Rule_s *localregtab = calloc(reg_count,

					  sizeof(struct

						 Dwarf_Reg_Rule_s));

    struct Dwarf_Reg_Rule_s cfa_reg;

    /* This is used to end executing frame instructions.  */

    /* Becomes true when search_pc is true and current_loc */

    /* is greater than search_pc_val.  */

    Dwarf_Bool search_over = false;

    /* Used by the DW_FRAME_advance_loc instr */

    /* to hold the increment in pc value.  */

    Dwarf_Addr adv_pc;

    /* Contains the length in bytes of */

    /* an leb128 encoded number.  */

    Dwarf_Word leb128_length;

    /* Counts the number of frame instructions executed.  */

    Dwarf_Word instr_count = 0;

    /* 

       These contain the current fields of the current frame

       instruction. */

    Dwarf_Small fp_base_op = 0;

    Dwarf_Small fp_extended_op;

    reg_num_type fp_register;

    /* The value in fp_offset may be signed, though we call it

       unsigned. This works ok for 2-s complement arithmetic. */

    Dwarf_Unsigned fp_offset;

    Dwarf_Off fp_instr_offset;

    /* 

       Stack_table points to the row (Dwarf_Frame ie) being pushed or

       popped by a remember or restore instruction. Top_stack points to 

       the top of the stack of rows. */

    Dwarf_Frame stack_table;

    Dwarf_Frame top_stack = NULL;

    /* 

       These are used only when make_instr is true. Curr_instr is a

       pointer to the current frame instruction executed.

       Curr_instr_ptr, head_instr_list, and curr_instr_list are used to 

       form a chain of Dwarf_Frame_Op structs. Dealloc_instr_ptr is

       used to deallocate the structs used to form the chain.

       Head_instr_block points to a contiguous list of pointers to the

       Dwarf_Frame_Op structs executed. */

    Dwarf_Frame_Op *curr_instr;

    Dwarf_Chain curr_instr_item, dealloc_instr_item;

    Dwarf_Chain head_instr_chain = NULL;

    Dwarf_Chain tail_instr_chain = NULL;

    Dwarf_Frame_Op *head_instr_block;

    /* 

       These are the alignment_factors taken from the Cie provided.

       When no input Cie is provided they are set to 1, because only

       factored offsets are required. */

    Dwarf_Sword code_alignment_factor = 1;

    Dwarf_Sword data_alignment_factor = 1;

    /* 

       This flag indicates when an actual alignment factor is needed.

       So if a frame instruction that computes an offset using an

       alignment factor is encountered when this flag is set, an error

       is returned because the Cie did not have a valid augmentation. */

    Dwarf_Bool need_augmentation = false;

    Dwarf_Word i;

    /* Initialize first row from associated Cie. Using temp regs

       explicity */

    if (localregtab == 0) {

	SIMPLE_ERROR_RETURN(DW_DLE_ALLOC_FAIL);

    }

    {

	struct Dwarf_Reg_Rule_s *t1reg = localregtab;

	struct Dwarf_Reg_Rule_s *t1end = t1reg + reg_count;

	if (cie != NULL && cie->ci_initial_table != NULL) {

	    struct Dwarf_Reg_Rule_s *t2reg =

		cie->ci_initial_table->fr_reg;

	    if (reg_count != cie->ci_initial_table->fr_reg_count) {

		/* Should never happen, it makes no sense to have the

		   table sizes change. There is no real allowance for

		   the set of registers to change dynamically in a

		   single Dwarf_Debug (except the size can be set near

		   initial Dwarf_Debug creation time). */

		SIMPLE_ERROR_RETURN

		    (DW_DLE_FRAME_REGISTER_COUNT_MISMATCH);

	    }

	    for (; t1reg < t1end; t1reg++, t2reg++) {

		*t1reg = *t2reg;

	    }

	    cfa_reg = cie->ci_initial_table->fr_cfa_rule;

	} else {

	    _dwarf_init_regrule_table(t1reg,

				      reg_count,

				      dbg->de_frame_rule_initial_value);

	    _dwarf_init_regrule_table(&cfa_reg, 1,

				      dbg->de_frame_rule_initial_value);

	}

    }

    /* 

       The idea here is that the code_alignment_factor and

       data_alignment_factor which are needed for certain instructions

       are valid only when the Cie has a proper augmentation string. So 

       if the augmentation is not right, only Frame instruction can be

       read. */

    if (cie != NULL && cie->ci_augmentation != NULL) {

	code_alignment_factor = cie->ci_code_alignment_factor;

	data_alignment_factor = cie->ci_data_alignment_factor;

    } else {

	need_augmentation = !make_instr;

    }

    instr_ptr = start_instr_ptr;

    while ((instr_ptr < final_instr_ptr) && (!search_over)) {

        Dwarf_Small instr = 0;

        Dwarf_Small opcode = 0;

        reg_num_type reg_no = 0;

	fp_instr_offset = instr_ptr - start_instr_ptr;

	instr = *(Dwarf_Small *) instr_ptr;

	instr_ptr += sizeof(Dwarf_Small);

	fp_base_op = (instr & 0xc0) >> 6;

	if ((instr & 0xc0) == 0x00) {

	    opcode = instr;	/* is really extended op */

	    fp_extended_op = (instr & (~(0xc0))) & 0xff;

	} else {

	    opcode = instr & 0xc0;	/* is base op */

	    fp_extended_op = 0;

	}

	fp_register = 0;

	fp_offset = 0;

	switch (opcode) {

	case DW_CFA_advance_loc:

	    {

		/* base op */

		fp_offset = adv_pc = instr & DW_FRAME_INSTR_OFFSET_MASK;

		if (need_augmentation) {

		    SIMPLE_ERROR_RETURN(DW_DLE_DF_NO_CIE_AUGMENTATION);

		}

		adv_pc = adv_pc * code_alignment_factor;

		search_over = search_pc &&

		    (current_loc + adv_pc > search_pc_val);

		/* If gone past pc needed, retain old pc.  */

		if (!search_over)

		    current_loc = current_loc + adv_pc;

		break;

	    }

	case DW_CFA_offset:

	    {			/* base op */

		reg_no =

		    (reg_num_type) (instr & DW_FRAME_INSTR_OFFSET_MASK);

		ERROR_IF_REG_NUM_TOO_HIGH(reg_no, reg_count);

		factored_N_value =

		    _dwarf_decode_u_leb128(instr_ptr, &leb128_length);

		instr_ptr = instr_ptr + leb128_length;

		fp_register = reg_no;

		fp_offset = factored_N_value;

		if (need_augmentation) {

		    SIMPLE_ERROR_RETURN(DW_DLE_DF_NO_CIE_AUGMENTATION);

		}

		localregtab[reg_no].ru_is_off = 1;

		localregtab[reg_no].ru_value_type = DW_EXPR_OFFSET;

		localregtab[reg_no].ru_register = reg_num_of_cfa;

		localregtab[reg_no].ru_offset_or_block_len =

		    factored_N_value * data_alignment_factor;

		break;

	    }

	case DW_CFA_restore:

	    {			/* base op */

		reg_no = (instr & DW_FRAME_INSTR_OFFSET_MASK);

		ERROR_IF_REG_NUM_TOO_HIGH(reg_no, reg_count);

		fp_register = reg_no;

		if (cie != NULL && cie->ci_initial_table != NULL)

		    localregtab[reg_no] = 

                       cie->ci_initial_table->fr_reg[reg_no];

		else if (!make_instr) {

		    SIMPLE_ERROR_RETURN(DW_DLE_DF_MAKE_INSTR_NO_INIT);

		}

		break;

	    }

	case DW_CFA_set_loc:

	    {

		Dwarf_Addr new_loc = 0;

		READ_UNALIGNED(dbg, new_loc, Dwarf_Addr,

			       instr_ptr, dbg->de_pointer_size);

		instr_ptr += dbg->de_pointer_size;

		if (new_loc != 0 && current_loc != 0) {

		    /* Pre-relocation or before current_loc is set the

		       test comparing new_loc and current_loc makes no

		       sense. Testing for non-zero (above) is a way

		       (fallible) to check that current_loc, new_loc

		       are already relocated.  */

		    if (new_loc <= current_loc) {

			/* Within a frame, address must increase.

			   Seemingly it has not. Seems to be an error. */

			SIMPLE_ERROR_RETURN

			    (DW_DLE_DF_NEW_LOC_LESS_OLD_LOC);

		    }

		}

		search_over = search_pc && (new_loc > search_pc_val);

		/* If gone past pc needed, retain old pc.  */

		if (!search_over)

		    current_loc = new_loc;

		fp_offset = new_loc;

		break;

	    }

	case DW_CFA_advance_loc1:

	    {

		fp_offset = adv_loc = *(Dwarf_Small *) instr_ptr;

		instr_ptr += sizeof(Dwarf_Small);

		if (need_augmentation) {

		    SIMPLE_ERROR_RETURN(DW_DLE_DF_NO_CIE_AUGMENTATION);

		}

		adv_loc *= code_alignment_factor;

		search_over = search_pc &&

		    (current_loc + adv_loc > search_pc_val);

		/* If gone past pc needed, retain old pc.  */

		if (!search_over)

		    current_loc = current_loc + adv_loc;

		break;

	    }

	case DW_CFA_advance_loc2:

	    {

		READ_UNALIGNED(dbg, adv_loc, Dwarf_Unsigned,

			       instr_ptr, sizeof(Dwarf_Half));

		instr_ptr += sizeof(Dwarf_Half);

		fp_offset = adv_loc;

		if (need_augmentation) {

		    SIMPLE_ERROR_RETURN(DW_DLE_DF_NO_CIE_AUGMENTATION);

		}

		adv_loc *= code_alignment_factor;

		search_over = search_pc &&

		    (current_loc + adv_loc > search_pc_val);

		/* If gone past pc needed, retain old pc.  */

		if (!search_over)

		    current_loc = current_loc + adv_loc;

		break;

	    }

	case DW_CFA_advance_loc4:

	    {

		READ_UNALIGNED(dbg, adv_loc, Dwarf_Unsigned,

			       instr_ptr, sizeof(Dwarf_ufixed));

		instr_ptr += sizeof(Dwarf_ufixed);

		fp_offset = adv_loc;

		if (need_augmentation) {

		    SIMPLE_ERROR_RETURN(DW_DLE_DF_NO_CIE_AUGMENTATION);

		}

		adv_loc *= code_alignment_factor;

		search_over = search_pc &&

		    (current_loc + adv_loc > search_pc_val);

		/* If gone past pc needed, retain old pc.  */

		if (!search_over)

		    current_loc = current_loc + adv_loc;

		break;

	    }

	case DW_CFA_offset_extended:

	    {

		Dwarf_Unsigned lreg;

		DECODE_LEB128_UWORD(instr_ptr, lreg);

		reg_no = (reg_num_type) lreg;

		ERROR_IF_REG_NUM_TOO_HIGH(reg_no, reg_count);;

		factored_N_value =

		    _dwarf_decode_u_leb128(instr_ptr, &leb128_length);

		instr_ptr += leb128_length;

		if (need_augmentation) {

		    SIMPLE_ERROR_RETURN(DW_DLE_DF_NO_CIE_AUGMENTATION);

		}

		localregtab[reg_no].ru_is_off = 1;

		localregtab[reg_no].ru_value_type = DW_EXPR_OFFSET;

		localregtab[reg_no].ru_register = reg_num_of_cfa;

		localregtab[reg_no].ru_offset_or_block_len = factored_N_value *

		    data_alignment_factor;

		fp_register = reg_no;

		fp_offset = factored_N_value;

		break;

	    }

	case DW_CFA_restore_extended:

	    {

		Dwarf_Unsigned lreg;

		DECODE_LEB128_UWORD(instr_ptr, lreg);

		reg_no = (reg_num_type) lreg;

		ERROR_IF_REG_NUM_TOO_HIGH(reg_no, reg_count);

		if (cie != NULL && cie->ci_initial_table != NULL) {

		    localregtab[reg_no] = cie->ci_initial_table->fr_reg[reg_no];

		} else {