/*

  Copyright (C) 2000,2002,2004,2005 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.

*/

#undef  DEBUG

#include "config.h"

#include "dwarf_incl.h"

#include <sys/types.h>

#include <stdlib.h>

#include <stdio.h>

#include "malloc_check.h"

/*

    These files are included to get the sizes

    of structs to set the ah_bytes_one_struct field

    of the Dwarf_Alloc_Hdr_s structs for each

    allocation type.

*/

#include "dwarf_line.h"

#include "dwarf_global.h"

#include "dwarf_arange.h"

#include "dwarf_abbrev.h"

#include "dwarf_die_deliv.h"

#include "dwarf_frame.h"

#include "dwarf_loc.h"

#include "dwarf_funcs.h"

#include "dwarf_types.h"

#include "dwarf_vars.h"

#include "dwarf_weaks.h"

static void _dwarf_free_special_error(Dwarf_Ptr space);

#ifdef DWARF_SIMPLE_MALLOC

static void _dwarf_simple_malloc_add_to_list(Dwarf_Debug dbg,

					     Dwarf_Ptr addr,

					     unsigned long size,

					     short alloc_type);

static void _dwarf_simple_malloc_delete_from_list(Dwarf_Debug dbg,

						  Dwarf_Ptr space,

						  short alloc_type);

void _dwarf_simple_malloc_botch(int err);

#endif /* DWARF_SIMPLE_MALLOC */

/*

    This macro adds the size of a pointer to the size of a

    struct that is given to it.  It rounds up the size to

    be a multiple of the size of a pointer.  This is done

    so that every struct returned by _dwarf_get_alloc()

    can be preceded by a pointer to the chunk it came from.

    Before allocating, it checks if the size of struct is less than

    the size of a pointer.  If yes, it returns the size

    of 2 pointers.  The returned size should be at least

    the size of 2 pointers, since the first points to the

    chunk the struct was allocated from, and the second

    is used to link the free list.

    We want DW_RESERVE to be at least the size of

    a long long and at least the size of a pointer because

    our struct has a long long and we want that aligned right.

    Now Standard C defines long long as 8 bytes, so lets

    make that standard. It will become unworkable when

    long long or pointer grows beyound 8 bytes.

    Unclear what to do with wierd requirements, like

    36 bit pointers.

*/

#define DW_RESERVE 8

/* Round size up to the next multiple of DW_RESERVE bytes 

*/

#define ROUND_SIZE(inputsize)                 \

        (((inputsize) % (DW_RESERVE)) == 0 ? \

            (inputsize):                      \

            ((inputsize)  +                   \

               (DW_RESERVE) - ((inputsize) % (DW_RESERVE)) ))

#define ROUND_SIZE_WITH_POINTER(i_size) (ROUND_SIZE(i_size) + DW_RESERVE)

/* SMALL_ALLOC is for trivia where allocation is a waste.

   Things that should be removed, really. */

#define SMALL_ALLOC 2

/* BASE_ALLOC is where a basic allocation makes sense, but 'not too large'. 

   No thorough evaluation of this value has been done, though

   it was found wasteful of memory to have BASE_ALLOC be as large as

   BIG_ALLOC. */

#define BASE_ALLOC 64

/* BIG_ALLOC is where a larger-than-BASE_ALLOC 

   allocation makes sense, but still 'not too large'.

   No thorough evaluation of this value has been done. */

#define BIG_ALLOC  128

/* This translates into de_alloc_hdr index 

** the 0,1,1 entries are special: they don't use the

** table values at all.

** Rearranging the DW_DLA values would break binary compatibility

** so that is not an option.

*/

struct ial_s {

    int ia_al_num;		/* Index into de_alloc_hdr table. */

    /* In bytes, one struct instance. This does not account for extra

       space needed per block, but that (DW_RESERVE) will be added in

       later where it is needed (DW_RESERVE space never added in here). 

     */

    int ia_struct_size;

    /* Number of instances per alloc block. MUST be > 0. */

    int ia_base_count;

    int (*specialconstructor) (Dwarf_Debug, void *);

    void (*specialdestructor) (void *);

};

static const

struct ial_s index_into_allocated[ALLOC_AREA_INDEX_TABLE_MAX] = {

    {0, 1, 1, 0, 0},		/* none */

    {0, 1, 1, 0, 0},		/* 1 DW_DLA_STRING */

    {1, sizeof(Dwarf_Loc), BASE_ALLOC, 0, 0}

    ,				/* 2 DW_DLA_LOC */

    {2, sizeof(Dwarf_Locdesc), BASE_ALLOC, 0, 0}

    ,				/* 3 DW_DLA_LOCDESC */

    {0, 1, 1, 0, 0}

    ,				/* not used *//* 4 DW_DLA_ELLIST */

    {0, 1, 1, 0, 0}

    ,				/* not used *//* 5 DW_DLA_BOUNDS */

    {3, sizeof(Dwarf_Block), BASE_ALLOC, 0, 0}

    ,				/* 6 DW_DLA_BLOCK */

    {0, 1, 1, 0, 0}

    ,				/* the actual dwarf_debug structure *//* 7 DW_DLA_DEBUG */

    {4, sizeof(struct Dwarf_Die_s), BIG_ALLOC, 0, 0},	/* 8 DW_DLA_DIE 

							 */

    {5, sizeof(struct Dwarf_Line_s), BIG_ALLOC, 0, 0},	/* 9

							   DW_DLA_LINE */

    {6, sizeof(struct Dwarf_Attribute_s), BIG_ALLOC * 2, 0, 0},

    /* 10 DW_DLA_ATTR */

    {0, 1, 1, 0, 0},		/* not used *//* 11 DW_DLA_TYPE */

    {0, 1, 1, 0, 0},		/* not used *//* 12 DW_DLA_SUBSCR */

    {7, sizeof(struct Dwarf_Global_s), BASE_ALLOC, 0, 0},	/* 13

								   DW_DLA_GLOBAL 

								 */

    {8, sizeof(struct Dwarf_Error_s), BASE_ALLOC, 0, 0},	/* 14

								   DW_DLA_ERROR 

								 */

    {0, 1, 1, 0, 0},		/* 15 DW_DLA_LIST */

    {0, 1, 1, 0, 0},		/* not used *//* 16 DW_DLA_LINEBUF */

    {9, sizeof(struct Dwarf_Arange_s), BASE_ALLOC, 0, 0},	/* 17

								   DW_DLA_ARANGE 

								 */

    {10, sizeof(struct Dwarf_Abbrev_s), BIG_ALLOC, 0, 0},	/* 18

								   DW_DLA_ABBREV 

								 */

    {11, sizeof(Dwarf_Frame_Op), BIG_ALLOC, 0, 0}

    ,				/* 19 DW_DLA_FRAME_OP */

    {12, sizeof(struct Dwarf_Cie_s), BASE_ALLOC, 0, 0},	/* 20

							   DW_DLA_CIE */

    {13, sizeof(struct Dwarf_Fde_s), BASE_ALLOC, 0, 0},	/* 21

							   DW_DLA_FDE */

    {0, 1, 1, 0, 0},		/* 22 DW_DLA_LOC_BLOCK */

    {0, 1, 1, 0, 0},		/* 23 DW_DLA_FRAME_BLOCK */

    {14, sizeof(struct Dwarf_Global_s), BASE_ALLOC, 0, 0},	/* 24

								   DW_DLA_FUNC 

								   UNUSED 

								 */

    {15, sizeof(struct Dwarf_Global_s), BASE_ALLOC, 0, 0},	/* 25

								   DW_DLA_TYPENAME

								   UNUSED */

    {16, sizeof(struct Dwarf_Global_s), BASE_ALLOC, 0, 0},	/* 26

								   DW_DLA_VAR 

								   UNUSED 

								 */

    {17, sizeof(struct Dwarf_Global_s), BASE_ALLOC, 0, 0},	/* 27

								   DW_DLA_WEAK 

								   UNUSED 

								 */

    {0, 1, 1, 0, 0},		/* 28 DW_DLA_ADDR */

    {18, sizeof(struct Dwarf_Abbrev_List_s), BIG_ALLOC, 0, 0},

    /* 29 DW_DLA_ABBREV_LIST */

    {19, sizeof(struct Dwarf_Chain_s), BIG_ALLOC, 0, 0},	/* 30

								   DW_DLA_CHAIN 

								 */

    {20, sizeof(struct Dwarf_CU_Context_s), BASE_ALLOC, 0, 0},

    /* 31 DW_DLA_CU_CONTEXT */

    {21, sizeof(struct Dwarf_Frame_s), BASE_ALLOC,

     _dwarf_frame_constructor,

     _dwarf_frame_destructor},	/* 32 DW_DLA_FRAME */

    {22, sizeof(struct Dwarf_Global_Context_s), BASE_ALLOC, 0, 0},

    /* 33 DW_DLA_GLOBAL_CONTEXT */

    {23, sizeof(struct Dwarf_File_Entry_s), BASE_ALLOC, 0, 0},	/* 34 */

    /* 34 DW_DLA_FILE_ENTRY */

    {24, sizeof(struct Dwarf_Line_Context_s), BASE_ALLOC, 0, 0},

    /* 35 DW_DLA_LINE_CONTEXT */

    {25, sizeof(struct Dwarf_Loc_Chain_s), BASE_ALLOC, 0, 0},	/* 36 */

    /* 36 DW_DLA_LOC_CHAIN */

    /* See use of ABBREV_HASH_TABLE_SIZE below for final dealloc. */

    {26, ABBREV_HASH_TABLE_SIZE * sizeof(struct Dwarf_Hash_Table_s),

     BASE_ALLOC, 0, 0},		/* 37 */

    /* 37 DW_DLA_HASH_TABLE */

/* The following really use Global struct: used to be unique struct

   per type, but now merged (11/99).  The opaque types

   are visible in the interface. The types  for

   DW_DLA_FUNC,

   DW_DLA_TYPENAME, DW_DLA_VAR, DW_DLA_WEAK also use

   the global types.

*/

    {27, sizeof(struct Dwarf_Global_Context_s), BASE_ALLOC, 0, 0},

    /* 38 DW_DLA_FUNC_CONTEXT */

    {28, sizeof(struct Dwarf_Global_Context_s), BASE_ALLOC, 0, 0},

    /* 39 DW_DLA_TYPENAME_CONTEXT */

    {29, sizeof(struct Dwarf_Global_Context_s), BASE_ALLOC, 0, 0},

    /* 40 DW_DLA_VAR_CONTEXT */

    {30, sizeof(struct Dwarf_Global_Context_s), BASE_ALLOC, 0, 0},

    /* 41 DW_DLA_WEAK_CONTEXT */

    {31, sizeof(struct Dwarf_Global_Context_s), BASE_ALLOC, 0, 0},

    /* 42 DW_DLA_PUBTYPES_CONTEXT DWARF3 */

};

#ifndef DWARF_SIMPLE_MALLOC

/*

    This function is given a pointer to the header

    structure that is used to allocate 1 struct of

    the type given by alloc_type.  It first checks

    if a struct is available in its free list.  If

    not, it checks if 1 is available in its blob, 

    which is a chunk of memory that is reserved for

    its use.  If not, it malloc's a chunk.  The

    initial part of it is used to store the end

    address of the chunk, and also to keep track 

    of the number of free structs in that chunk.

    This information is used for freeing the chunk

    when all the structs in it are free.

    Assume all input arguments have been validated.

    This function can be used only to allocate 1

    struct of the given type.

    It returns a pointer to the struct that the

    user can use.  It returns NULL only when it

    is out of free structs, and cannot malloc 

    any more.  The struct returned is zero-ed.

    A pointer to the chunk that the struct belongs

    to is stored in the bytes preceding the

    returned address.  Since this pointer it

    never overwritten, when a struct is allocated

    from the free_list this pointer does not

    have to be written.  In the 2 other cases,

    where the struct is allocated from a new

    chunk, or the blob, a pointer to the chunk

    is written.

*/

static Dwarf_Ptr

_dwarf_find_memory(Dwarf_Alloc_Hdr alloc_hdr)

{

    /* Pointer to the struct allocated. */

    Dwarf_Small *ret_mem = 0;

    /* Pointer to info about chunks allocated. */

    Dwarf_Alloc_Area alloc_area;

    /* Size of chunk malloc'ed when no free structs left. */

    Dwarf_Signed mem_block_size;

    /* Pointer to block malloc'ed. */

    Dwarf_Small *mem_block;

    /* 

       Check the alloc_area from which the last allocation was made

       (most recent new block). If that is not successful, then search

       the list of alloc_area's from alloc_header. */

    alloc_area = alloc_hdr->ah_last_alloc_area;

    if (alloc_area == NULL || alloc_area->aa_free_structs_in_chunk == 0)

	for (alloc_area = alloc_hdr->ah_alloc_area_head;

	     alloc_area != NULL; alloc_area = alloc_area->aa_next) {

	    if (alloc_area->aa_free_structs_in_chunk > 0) {

		break;		/* found a free entry! */

	    }

	}

    if (alloc_area != NULL) {

	alloc_area->aa_free_structs_in_chunk--;

	if (alloc_area->aa_free_list != NULL) {

	    ret_mem = alloc_area->aa_free_list;

	    /* 

	       Update the free list.  The initial part of the struct is 

	       used to hold a pointer to the next struct on the free

	       list.  In this way, the free list chain is maintained at

	       0 memory cost. */

	    alloc_area->aa_free_list =

		((Dwarf_Free_List) ret_mem)->fl_next;

	} else if (alloc_area->aa_blob_start < alloc_area->aa_blob_end) {

	    ret_mem = alloc_area->aa_blob_start;

	    /* 

	       Store pointer to chunk this struct belongs to in the

	       first few bytes.  Return pointer to bytes after this

	       pointer storage. */

	    *(Dwarf_Alloc_Area *) ret_mem = alloc_area;

	    ret_mem += DW_RESERVE;

	    alloc_area->aa_blob_start += alloc_hdr->ah_bytes_one_struct;

	} else {

	    /* else fall thru , though it should be impossible to fall

	       thru. And represents a disastrous programming error if

	       we get here. */

#ifdef DEBUG

	    fprintf(stderr, "libdwarf Internal error start %x end %x\n",

		    (int) alloc_area->aa_blob_start,

		    (int) alloc_area->aa_blob_end);

#endif

	}

    }

    /* New memory has to malloc'ed since there are no free structs. */

    if (ret_mem == 0) {

	Dwarf_Word rounded_area_hdr_size;

	alloc_hdr->ah_chunks_allocated++;

	{			/* this nonsense avoids a warning */

	    /* CONSTCOND would be better */

	    unsigned long v = sizeof(struct Dwarf_Alloc_Area_s);

	    rounded_area_hdr_size = ROUND_SIZE(v);

	}

	/* 

	   Allocate memory to contain the required number of structs

	   and the Dwarf_Alloc_Area_s to control it. */

	mem_block_size = alloc_hdr->ah_bytes_malloc_per_chunk +

	    rounded_area_hdr_size;

	mem_block = malloc(mem_block_size);

	if (mem_block == NULL) {

	    return (NULL);

	}

	/* 

	   Attach the Dwarf_Alloc_Area_s struct to the list of chunks

	   malloc'ed for this struct type. Also initialize the fields

	   of the Dwarf_Alloc_Area_s. */

	alloc_area = (Dwarf_Alloc_Area) mem_block;

	alloc_area->aa_prev = 0;

	if (alloc_hdr->ah_alloc_area_head != NULL) {

	    alloc_hdr->ah_alloc_area_head->aa_prev = alloc_area;

	}

	alloc_area->aa_free_list = 0;

	alloc_area->aa_next = alloc_hdr->ah_alloc_area_head;

	alloc_hdr->ah_alloc_area_head = alloc_area;

	alloc_area->aa_alloc_hdr = alloc_hdr;

	alloc_area->aa_free_structs_in_chunk =

	    (Dwarf_Sword) alloc_hdr->ah_structs_per_chunk - 1;

	if (alloc_area->aa_free_structs_in_chunk < 1) {

	    /* If we get here, there is a disastrous programming error

	       somewhere. */

#ifdef DEBUG

	    fprintf(stderr,

		    "libdwarf Internal error: free structs in chunk %d\n",

		    (int) alloc_area->aa_free_structs_in_chunk);

#endif

	    return NULL;

	}

	/* 

	   The struct returned begins immediately after the

	   Dwarf_Alloc_Area_s struct. */

	ret_mem = mem_block + rounded_area_hdr_size;

	alloc_area->aa_blob_start =

	    ret_mem + alloc_hdr->ah_bytes_one_struct;

	alloc_area->aa_blob_end = mem_block + mem_block_size;

	/* 

	   Store pointer to chunk this struct belongs to in the first

	   few bytes.  Return pointer to bytes after this pointer

	   storage. */

	*(Dwarf_Alloc_Area *) ret_mem = alloc_area;

	ret_mem += DW_RESERVE;

    }

    alloc_hdr->ah_last_alloc_area = alloc_area;

    alloc_hdr->ah_struct_user_holds++;

    memset(ret_mem, 0, alloc_hdr->ah_bytes_one_struct - DW_RESERVE);

    return (ret_mem);

}

#endif /* ndef DWARF_SIMPLE_MALLOC */

/*

    This function returns a pointer to a region

    of memory.  For alloc_types that are not

    strings or lists of pointers, only 1 struct

    can be requested at a time.  This is indicated

    by an input count of 1.  For strings, count 

    equals the length of the string it will

    contain, i.e it the length of the string

    plus 1 for the terminating null.  For lists

    of pointers, count is equal to the number of

    pointers.  For DW_DLA_FRAME_BLOCK, and

    DW_DLA_LOC_BLOCK allocation types also, count

    is the count of the number of structs needed.

    This function cannot be used to allocate a 

    Dwarf_Debug_s struct.

*/

Dwarf_Ptr

_dwarf_get_alloc(Dwarf_Debug dbg,

		 Dwarf_Small alloc_type, Dwarf_Unsigned count)

{

    Dwarf_Alloc_Hdr alloc_hdr;

    Dwarf_Ptr ret_mem;

    Dwarf_Signed size = 0;

    unsigned int index;

    unsigned int type = alloc_type;

    if (dbg == NULL) {

	return (NULL);

    }

    if (type >= ALLOC_AREA_INDEX_TABLE_MAX) {

	/* internal error */

	return NULL;

    }

    index = index_into_allocated[type].ia_al_num;

    /* zero also illegal but not tested for */

    /* If the Dwarf_Debug is not fully set up, we will get index 0 for

       any type and must do something.  'Not fully set up' can only

       happen for DW_DLA_ERROR, I (davea) believe, and for that we call 

       special code here.. */

    if (index == 0) {

	if (alloc_type == DW_DLA_STRING) {

	    size = count;

	} else if (alloc_type == DW_DLA_LIST) {

	    size = count * sizeof(Dwarf_Ptr);

	} else if (alloc_type == DW_DLA_FRAME_BLOCK) {

	    size = count * sizeof(Dwarf_Frame_Op);

	} else if (alloc_type == DW_DLA_LOC_BLOCK) {

	    size = count * sizeof(Dwarf_Loc);

	} else if (alloc_type == DW_DLA_ADDR) {

	    size = count *

		(sizeof(Dwarf_Addr) > sizeof(Dwarf_Off) ?

		 sizeof(Dwarf_Addr) : sizeof(Dwarf_Off));

	} else if (alloc_type == DW_DLA_ERROR) {

	    void *m = _dwarf_special_no_dbg_error_malloc();

	    dwarf_malloc_check_alloc_data(m, DW_DLA_ERROR);

	    return m;

	} else {

	    /* If we get here, there is a disastrous programming error

	       somewhere. */

#ifdef DEBUG

	    fprintf(stderr,

		    "libdwarf Internal error: type %d  unexpected\n",

		    (int) type);

#endif

	}

    } else {

	alloc_hdr = &dbg->de_alloc_hdr[index];

	if (alloc_hdr->ah_bytes_one_struct > 0) {

#ifdef DWARF_SIMPLE_MALLOC

	    size = alloc_hdr->ah_bytes_one_struct;

#else