/*

  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.

*/

/*

	This  implements _dwarf_get_fde_list_internal()

        and related helper functions for reading cie/fde data.

*/

#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 */

static int dwarf_find_existing_cie_ptr(Dwarf_Small * cie_ptr,

				       Dwarf_Cie cur_cie_ptr,

				       Dwarf_Cie * cie_ptr_to_use_out,

				       Dwarf_Cie head_cie_ptr);

static void dealloc_fde_cie_list_internal(Dwarf_Fde head_fde_ptr,

					  Dwarf_Cie head_cie_ptr);

static int dwarf_create_cie_from_start(Dwarf_Debug dbg,

				       Dwarf_Small * cie_ptr_val,

				       Dwarf_Small * section_ptr,

				       Dwarf_Unsigned section_index,

				       Dwarf_Unsigned section_length,

				       Dwarf_Small * frame_ptr_end,

				       Dwarf_Unsigned cie_id_value,

				       Dwarf_Unsigned cie_count,

				       int use_gnu_cie_calc,

				       Dwarf_Cie * cie_ptr_to_use_out,

				       Dwarf_Error * error);

static Dwarf_Small *get_cieptr_given_offset(Dwarf_Unsigned cie_id_value,

					    int use_gnu_cie_calc,

					    Dwarf_Small * section_ptr,

					    Dwarf_Small * cie_id_addr);

static int get_gcc_eh_augmentation(Dwarf_Debug dbg,

				   Dwarf_Small * frame_ptr,

				   unsigned long

				   *size_of_augmentation_data,

				   enum Dwarf_augmentation_type augtype,

				   Dwarf_Small * section_pointer,

				   Dwarf_Small * fde_eh_encoding_out,

				   char *augmentation);

static int

  gnu_aug_encodings(Dwarf_Debug dbg, char *augmentation,

		    Dwarf_Small * aug_data, Dwarf_Unsigned aug_data_len,

		    unsigned char *pers_hand_enc_out,

		    unsigned char *lsda_enc_out,

		    unsigned char *fde_begin_enc_out,

		    Dwarf_Addr * gnu_pers_addr_out);

static int read_encoded_ptr(Dwarf_Debug dbg,

			    Dwarf_Small * section_pointer,

			    Dwarf_Small * input_field,

			    int gnu_encoding,

			    Dwarf_Unsigned * addr,

			    Dwarf_Small ** input_field_out);

static int qsort_compare(const void *elem1, const void *elem2);

/* Adds 'newone' to the end of the list starting at 'head'

   and makes the new one 'cur'rent. */

static void

chain_up_fde(Dwarf_Fde newone, Dwarf_Fde * head, Dwarf_Fde * cur)

{

    if (*head == NULL)

	*head = newone;

    else {

	(*cur)->fd_next = newone;

    }

    *cur = newone;

}

/* Adds 'newone' to the end of the list starting at 'head'

   and makes the new one 'cur'rent. */

static void

chain_up_cie(Dwarf_Cie newone, Dwarf_Cie * head, Dwarf_Cie * cur)

{

    if (*head == NULL) {

	*head = newone;

    } else {

	(*cur)->ci_next = newone;

    }

    *cur = newone;

}

#if 0

/* For debugging only. */

static void

print_prefix(struct cie_fde_prefix_s *prefix, int line)

{

    printf("prefix-print, prefix at 0x%lx, line %d\n",

	   (long) prefix, line);

    printf("  start addr 0x%lx after prefix 0x%lx\n",

	   (long) prefix->cf_start_addr,

	   (long) prefix->cf_addr_after_prefix);

    printf("  length 0x%llx, len size %d ext size %d\n", (long long)

	   (unsigned long long) prefix->cf_length,

	   prefix->cf_local_length_size,

	   prefix->cf_local_extension_size);

    printf("  cie_id 0x%llx cie_id  cie_id_addr 0x%lx\n",

	   (unsigned long long) prefix->cf_cie_id,

	   (long) prefix->cf_cie_id_addr);

    printf

	("  sec ptr 0x%lx sec index %lld sec len 0x%llx sec past end 0x%lx\n",

	 (long) prefix->cf_section_ptr,

	 (long long) prefix->cf_section_index,

	 (unsigned long long) prefix->cf_section_length,

	 (long) prefix->cf_section_ptr + prefix->cf_section_length);

}

#endif

/* Internal function called from various places to create

   lists of CIEs and FDEs.  Not directly called

   by consumer code */

int

_dwarf_get_fde_list_internal(Dwarf_Debug dbg, Dwarf_Cie ** cie_data,

			     Dwarf_Signed * cie_element_count,

			     Dwarf_Fde ** fde_data,

			     Dwarf_Signed * fde_element_count,

			     Dwarf_Small * section_ptr,

			     Dwarf_Unsigned section_index,

			     Dwarf_Unsigned section_length,

			     Dwarf_Unsigned cie_id_value,

			     int use_gnu_cie_calc, Dwarf_Error * error)

{

    /* Scans the debug_frame section. */

    Dwarf_Small *frame_ptr = section_ptr;

    Dwarf_Small *frame_ptr_end = section_ptr + section_length;

    /* 

       New_cie points to the Cie being read, and head_cie_ptr and

       cur_cie_ptr are used for chaining them up in sequence. 

       In case cie's are reused aggressively we need tail_cie_ptr

       to add to the chain.  If we re-use an early cie

       later on, that does not mean we chain a new cie to the early one,

       we always chain it to the tail.  */

    Dwarf_Cie head_cie_ptr = NULL;

    Dwarf_Cie cur_cie_ptr = NULL;

    Dwarf_Cie tail_cie_ptr = NULL;

    Dwarf_Word cie_count = 0;

    /* 

       Points to a list of contiguous pointers to Dwarf_Cie structures. 

     */

    Dwarf_Cie *cie_list_ptr = 0;

    /* 

       New_fde points to the Fde being created, and head_fde_ptr and

       cur_fde_ptr are used to chain them up. */

    Dwarf_Fde head_fde_ptr = NULL;

    Dwarf_Fde cur_fde_ptr = NULL;

    Dwarf_Word fde_count = 0;

    /* 

       Points to a list of contiguous pointers to Dwarf_Fde structures. 

     */

    Dwarf_Fde *fde_list_ptr = NULL;

    Dwarf_Word i = 0;

    int res = 0;

    if (frame_ptr == 0) {

	return DW_DLV_NO_ENTRY;

    }

    /* We create the fde and cie arrays. Processing each CIE as we come 

       to it or as an FDE refers to it.  We cannot process 'late' CIEs

       late as GNU .eh_frame complexities mean we need the whole CIE

       before we can process the FDE correctly. */

    while (frame_ptr < frame_ptr_end) {

	struct cie_fde_prefix_s prefix;

	/* First read in the 'common prefix' to figure out what we are

	   to do with this entry. */

	memset(&prefix, 0, sizeof(prefix));

	res = dwarf_read_cie_fde_prefix(dbg,

					frame_ptr, section_ptr,

					section_index,

					section_length, &prefix, error);

	if (res == DW_DLV_ERROR) {

	    dealloc_fde_cie_list_internal(head_fde_ptr, head_cie_ptr);

	    return res;

	}

	if (res == DW_DLV_NO_ENTRY)

	    break;

	frame_ptr = prefix.cf_addr_after_prefix;

	if (frame_ptr >= frame_ptr_end) {

	    dealloc_fde_cie_list_internal(head_fde_ptr, head_cie_ptr);

	    _dwarf_error(dbg, error, DW_DLE_DEBUG_FRAME_LENGTH_BAD);

	    return DW_DLV_ERROR;

	}

	if (prefix.cf_cie_id == cie_id_value) {

	    /* This is a CIE.  */

	    Dwarf_Cie cie_ptr_to_use = 0;

	    int res = dwarf_find_existing_cie_ptr(prefix.cf_start_addr,

						  cur_cie_ptr,

						  &cie_ptr_to_use,

						  head_cie_ptr);

	    if (res == DW_DLV_OK) {

		cur_cie_ptr = cie_ptr_to_use;

		/* Ok. Seen already. */

	    } else if (res == DW_DLV_NO_ENTRY) {

		/* CIE before its FDE in this case. */

		res = dwarf_create_cie_from_after_start(dbg,

							&prefix,

							section_ptr,

							frame_ptr,

							cie_count,

							use_gnu_cie_calc,

							&cie_ptr_to_use,

							error);

		/* ASSERT: res==DW_DLV_NO_ENTRY impossible. */

		if (res == DW_DLV_ERROR) {

		    dealloc_fde_cie_list_internal(head_fde_ptr,

						  head_cie_ptr);

		    return res;

		}

		/* ASSERT res != DW_DLV_NO_ENTRY */

		cie_count++;

		chain_up_cie(cie_ptr_to_use, &head_cie_ptr,

			     &tail_cie_ptr);

                cur_cie_ptr = tail_cie_ptr;

	    } else {		/* res == DW_DLV_ERROR */

		dealloc_fde_cie_list_internal(head_fde_ptr,

					      head_cie_ptr);

		return res;

	    }

	    frame_ptr = cie_ptr_to_use->ci_cie_start +

		cie_ptr_to_use->ci_length +

		cie_ptr_to_use->ci_length_size +

		cie_ptr_to_use->ci_extension_size;

	    continue;

	} else {

	    /* this is an FDE, Frame Description Entry, see the Dwarf

	       Spec, section 6.4.1 */

	    int res = 0;

	    Dwarf_Cie cie_ptr_to_use = 0;

	    Dwarf_Fde fde_ptr_to_use = 0;

	    /* Do not call this twice on one prefix, as

	       prefix.cf_cie_id_addr is altered as a side effect. */

	    Dwarf_Small *cieptr_val =

		get_cieptr_given_offset(prefix.cf_cie_id,

					use_gnu_cie_calc,

					section_ptr,

					prefix.cf_cie_id_addr);

	    res = dwarf_find_existing_cie_ptr(cieptr_val,

					      cur_cie_ptr,

					      &cie_ptr_to_use,

					      head_cie_ptr);

	    if (res == DW_DLV_OK) {

		cur_cie_ptr = cie_ptr_to_use;

		/* Ok. Seen CIE already. */

	    } else if (res == DW_DLV_NO_ENTRY) {

		res = dwarf_create_cie_from_start(dbg,

						  cieptr_val,

						  section_ptr,

						  section_index,

						  section_length,

						  frame_ptr_end,

						  cie_id_value,

						  cie_count,

						  use_gnu_cie_calc,

						  &cie_ptr_to_use,

						  error);

		if (res == DW_DLV_ERROR) {

		    dealloc_fde_cie_list_internal(head_fde_ptr,

						  head_cie_ptr);

		    return res;

		} else if (res == DW_DLV_NO_ENTRY) {

		    return res;

		}

		++cie_count;

		chain_up_cie(cie_ptr_to_use, &head_cie_ptr,

			     &tail_cie_ptr);

                cur_cie_ptr = tail_cie_ptr;

	    } else {

		/* DW_DLV_ERROR */

		return res;

	    }

	    res = dwarf_create_fde_from_after_start(dbg,

						    &prefix,

						    section_ptr,

						    frame_ptr,

						    use_gnu_cie_calc,

						    cie_ptr_to_use,

						    &fde_ptr_to_use,

						    error);

	    if (res == DW_DLV_ERROR) {

		return res;

	    }

	    chain_up_fde(fde_ptr_to_use, &head_fde_ptr, &cur_fde_ptr);

	    fde_count++;

	    /* ASSERT: DW_DLV_OK. */

	    frame_ptr = fde_ptr_to_use->fd_fde_start +

		fde_ptr_to_use->fd_length +

		fde_ptr_to_use->fd_length_size +

		fde_ptr_to_use->fd_extension_size;

	    continue;

	}

    }

    /* Now build list of CIEs from the list. */

    if (cie_count > 0) {

	cie_list_ptr = (Dwarf_Cie *)

	    _dwarf_get_alloc(dbg, DW_DLA_LIST, cie_count);

    } else {

	dealloc_fde_cie_list_internal(head_fde_ptr, head_cie_ptr);

	return (DW_DLV_NO_ENTRY);

    }

    if (cie_list_ptr == NULL) {

	dealloc_fde_cie_list_internal(head_fde_ptr, head_cie_ptr);

	_dwarf_error(dbg, error, DW_DLE_ALLOC_FAIL);

	return (DW_DLV_ERROR);

    }

    cur_cie_ptr = head_cie_ptr;

    for (i = 0; i < cie_count; i++) {

	*(cie_list_ptr + i) = cur_cie_ptr;

	cur_cie_ptr = cur_cie_ptr->ci_next;

    }

    /* Now build array of FDEs from the list. */

    if (fde_count > 0) {

	fde_list_ptr = (Dwarf_Fde *)

	    _dwarf_get_alloc(dbg, DW_DLA_LIST, fde_count);

    } else {

	dwarf_fde_cie_list_dealloc(dbg, cie_list_ptr, cie_count,

				   /* fde_data */ 0,

				   /* fde_element_count */ 0);

	dealloc_fde_cie_list_internal(head_fde_ptr,	/* head cie_ptr 

							 */

				      0);

	return (DW_DLV_NO_ENTRY);

    }

    if (fde_list_ptr == NULL) {

	dwarf_fde_cie_list_dealloc(dbg, cie_list_ptr, cie_count,

				   /* fde_data */ 0,

				   /* fde_element_count */ 0);

	dealloc_fde_cie_list_internal(head_fde_ptr,	/* head cie_ptr 

							 */

				      0);

	_dwarf_error(dbg, error, DW_DLE_ALLOC_FAIL);

	return (DW_DLV_ERROR);

    }

    cur_fde_ptr = head_fde_ptr;

    for (i = 0; i < fde_count; i++) {

	*(fde_list_ptr + i) = cur_fde_ptr;

	cur_fde_ptr = cur_fde_ptr->fd_next;

    }

    /* Return arguments. */

    *cie_data = cie_list_ptr;

    *cie_element_count = cie_count;

    dbg->de_cie_data = cie_list_ptr;

    dbg->de_cie_count = cie_count;

    *fde_data = fde_list_ptr;

    *fde_element_count = fde_count;

    dbg->de_fde_data = fde_list_ptr;

    dbg->de_fde_count = fde_count;

    /* Sort the list by the address so that dwarf_get_fde_at_pc() can

       binary search this list. */

    qsort((void *) fde_list_ptr, fde_count, sizeof(Dwarf_Ptr),

	  qsort_compare);

    return (DW_DLV_OK);

}

/* Internal function, not called by consumer code.

   'prefix' has accumulated the info up thru the cie-id

   and now we consume the rest and build a Dwarf_Cie_s structure.

*/

int

dwarf_create_cie_from_after_start(Dwarf_Debug dbg,

				  struct cie_fde_prefix_s *prefix,

				  Dwarf_Small * section_pointer,

				  Dwarf_Small * frame_ptr,

				  Dwarf_Unsigned cie_count,

				  int use_gnu_cie_calc,

				  Dwarf_Cie * cie_ptr_out,

				  Dwarf_Error * error)

{

    Dwarf_Cie new_cie = 0;

    /* egcs-1.1.2 .eh_frame uses 0 as the distinguishing id. sgi uses

       -1 (in .debug_frame). .eh_frame not quite identical to

       .debug_frame */

    Dwarf_Small eh_fde_encoding = 0;

    Dwarf_Small *augmentation = 0;

    Dwarf_Sword data_alignment_factor = -1;

    Dwarf_Word code_alignment_factor = 4;

    Dwarf_Unsigned return_address_register = 31;

    int local_length_size = 0;

    Dwarf_Word leb128_length = 0;

    Dwarf_Unsigned cie_aug_data_len = 0;

    Dwarf_Small *cie_aug_data = 0;

    Dwarf_Addr gnu_personality_handler_addr = 0;

    unsigned char gnu_personality_handler_encoding = 0;

    unsigned char gnu_lsda_encoding = 0;

    unsigned char gnu_fde_begin_encoding = 0;

    enum Dwarf_augmentation_type augt = aug_unknown;

    /* this is a CIE, Common Information Entry: See the dwarf spec,

       section 6.4.1 */

    Dwarf_Small version = *(Dwarf_Small *) frame_ptr;

    frame_ptr++;

    if (version != DW_CIE_VERSION && version != DW_CIE_VERSION3) {

	_dwarf_error(dbg, error, DW_DLE_FRAME_VERSION_BAD);

	return (DW_DLV_ERROR);

    }

    augmentation = frame_ptr;

    frame_ptr = frame_ptr + strlen((char *) frame_ptr) + 1;

    augt = _dwarf_get_augmentation_type(dbg,

					augmentation, use_gnu_cie_calc);

    if (augt == aug_eh) {

	/* REFERENCED *//* Not used in this instance */

	Dwarf_Unsigned exception_table_addr;

	/* this is per egcs-1.1.2 as on RH 6.0 */

	READ_UNALIGNED(dbg, exception_table_addr,

		       Dwarf_Unsigned, frame_ptr, local_length_size);

	frame_ptr += local_length_size;

    }

    {

	Dwarf_Unsigned lreg = 0;

	unsigned long size = 0;

	DECODE_LEB128_UWORD(frame_ptr, lreg);

	code_alignment_factor = (Dwarf_Word) lreg;

	data_alignment_factor =

	    (Dwarf_Sword) _dwarf_decode_s_leb128(frame_ptr,

						 &leb128_length);

	frame_ptr = frame_ptr + leb128_length;

	return_address_register =

	    _dwarf_get_return_address_reg(frame_ptr, version, &size);

	if (return_address_register > DW_FRAME_LAST_REG_NUM) {

	    _dwarf_error(dbg, error, DW_DLE_CIE_RET_ADDR_REG_ERROR);

	    return (DW_DLV_ERROR);

	}

	frame_ptr += size;

    }

    switch (augt) {

    case aug_empty_string:

	break;

    case aug_irix_mti_v1:

	break;

    case aug_irix_exception_table:{

	    Dwarf_Unsigned lreg = 0;