/*--------------------------------------------------------------------*/
/*--- Callgrind                                                    ---*/
/*---                                                      ct_fn.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Callgrind, a Valgrind tool for call tracing.

   Copyright (C) 2002-2004, Josef Weidendorfer (Josef.Weidendorfer@gmx.de)

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307, USA.

   The GNU General Public License is contained in the file COPYING.
*/

#include "ct_include.h"

#define N_INITIAL_FN_ARRAY_SIZE 10071

static fn_array current_fn_active;

/*------------------------------------------------------------*/
/*--- Object/File/Function hash entry operations           ---*/
/*------------------------------------------------------------*/

/* Object hash table, fixed */
static obj_node* obj_table[N_OBJ_ENTRIES];

void SK_(init_obj_table)()
{
    Int i;
    for (i = 0; i < N_OBJ_ENTRIES; i++)
	obj_table[i] = 0;
}

#define HASH_CONSTANT   256

static UInt str_hash(const UChar *s, UInt table_size)
{
    int hash_value = 0;
    for ( ; *s; s++)
        hash_value = (HASH_CONSTANT * hash_value + *s) % table_size;
    return hash_value;
}


static UChar* anonymous_obj = "???";

static __inline__ 
obj_node* new_obj_node(SegInfo* si, obj_node* next)
{
   Int i;
   obj_node* new = VG_(malloc)(sizeof(obj_node));
   new->name  = si ? (UChar*)VG_(strdup)( VG_(seg_filename)(si) )
                     : anonymous_obj;
   for (i = 0; i < N_FILE_ENTRIES; i++) {
      new->files[i] = NULL;
   }
   SK_(stat).distinct_objs ++;
   new->number  = SK_(stat).distinct_objs;
   new->start   = si ? VG_(seg_start)(si) : 0;
   new->size    = si ? VG_(seg_size)(si) : 0;
   new->offset  = si ? VG_(seg_sym_offset)(si) : 0;
   new->next    = next;

#if CT_ENABLE_DEBUG  
   new->last_slash_pos = 0;
   i = 0;
   while(new->name[i]) {
	if (new->name[i]=='/') new->last_slash_pos = i+1;
	i++;
   }
#endif
   
   return new;
}

obj_node* SK_(get_obj_node)(SegInfo* si)
{
    obj_node*    curr_obj_node;
    UInt         objname_hash;
    const UChar* obj_name;
    
    obj_name = si ? VG_(seg_filename)(si) : anonymous_obj;

    /* lookup in obj hash */
    objname_hash = str_hash(obj_name, N_OBJ_ENTRIES);
    curr_obj_node = obj_table[objname_hash];
    while (NULL != curr_obj_node && 
	   VG_(strcmp)(obj_name, curr_obj_node->name) != 0) {
	curr_obj_node = curr_obj_node->next;
    }
    if (NULL == curr_obj_node) {
	obj_table[objname_hash] = curr_obj_node = 
	    new_obj_node(si, obj_table[objname_hash]);
    }

    return curr_obj_node;
}


static __inline__ 
file_node* new_file_node(Char filename[FILENAME_LEN],
			 obj_node* obj, file_node* next)
{
  Int i;
  file_node* new = VG_(malloc)(sizeof(file_node));
  new->name  = VG_(strdup)(filename);
  for (i = 0; i < N_FN_ENTRIES; i++) {
    new->fns[i] = NULL;
  }
  SK_(stat).distinct_files++;
  new->number  = SK_(stat).distinct_files;
  new->obj     = obj;
  new->next      = next;
  return new;
}

 
file_node* SK_(get_file_node)(obj_node* curr_obj_node,
			      Char filename[FILENAME_LEN])
{
    file_node* curr_file_node;
    UInt       filename_hash;

    /* lookup in file hash */
    filename_hash = str_hash(filename, N_FILE_ENTRIES);
    curr_file_node = curr_obj_node->files[filename_hash];
    while (NULL != curr_file_node && 
	   VG_(strcmp)(filename, curr_file_node->name) != 0) {
	curr_file_node = curr_file_node->next;
    }
    if (NULL == curr_file_node) {
	curr_obj_node->files[filename_hash] = curr_file_node = 
	    new_file_node(filename, curr_obj_node, 
			  curr_obj_node->files[filename_hash]);
    }

    return curr_file_node;
}

/* forward decl. */
static void resize_fn_array();

static __inline__ 
fn_node* new_fn_node(Char fnname[FILENAME_LEN],
		     file_node* file, fn_node* next)
{
    fn_node* new = VG_(malloc)(sizeof(fn_node));
    new->name = VG_(strdup)(fnname);

    SK_(stat).distinct_fns++;
    new->number   = SK_(stat).distinct_fns;
    new->last_cxt = 0;
    new->pure_cxt = 0;
    new->file     = file;
    new->next     = next;

    new->dump_before  = False;
    new->dump_after   = False;
    new->zero_before  = False;
    new->toggle_collect = False;
    new->skip         = False;
    new->group        = 0;
    new->separate_callers    = SK_(clo).separate_callers;
    new->separate_recursions = SK_(clo).separate_recursions;

#if CT_ENABLE_DEBUG
    new->verbosity    = -1;
#endif

    if (SK_(stat).distinct_fns >= current_fn_active.size)
	resize_fn_array();

    return new;
}


/* Get a function node in hash2 with known file node.
 * hash nodes are created if needed
 */
static
fn_node* get_fn_node_infile(file_node* curr_file_node,
			    Char fnname[FN_NAME_LEN])
{
    fn_node* curr_fn_node;
    UInt     fnname_hash;

    CT_ASSERT(curr_file_node != 0);

    /* lookup in function hash */
    fnname_hash = str_hash(fnname, N_FN_ENTRIES);
    curr_fn_node = curr_file_node->fns[fnname_hash];
    while (NULL != curr_fn_node && 
	   VG_(strcmp)(fnname, curr_fn_node->name) != 0) {
	curr_fn_node = curr_fn_node->next;
    }
    if (NULL == curr_fn_node) {
	curr_file_node->fns[fnname_hash] = curr_fn_node = 
            new_fn_node(fnname, curr_file_node,
			curr_file_node->fns[fnname_hash]);
    }

    return curr_fn_node;
}


/* Get a function node in a Valgrind Segment.
 * Hash nodes are created if needed.
 */
static __inline__
fn_node* get_fn_node_inseg(SegInfo* si,
			   Char filename[FILENAME_LEN],
			   Char fnname[FN_NAME_LEN])
{
  obj_node  *obj  = SK_(get_obj_node)(si);
  file_node *file = SK_(get_file_node)(obj, filename);
  fn_node   *fn   = get_fn_node_infile(file, fnname);

  return fn;
}


Bool SK_(get_debug_info)(Addr instr_addr, 
			 Char filename[FILENAME_LEN],
			 Char fn_name[FN_NAME_LEN], Int* line_num,
			 SegInfo** pSegInfo)
{
  Bool found1, found2, result = True;
  int line;
  
  CT_DEBUG(6, "  + get_debug_info(0x%08x)\n", instr_addr);

  if (pSegInfo) {
      *pSegInfo = VG_(get_obj)(instr_addr);

      // for generated code in anonymous space, pSegInfo is 0
   }

   found1 = VG_(get_filename_linenum)(instr_addr, filename,
				      FILENAME_LEN, &line);
   found2 = VG_(get_fnname)(instr_addr, 
			    fn_name, FN_NAME_LEN);

   if (!found1 && !found2) {
     SK_(stat).no_debug_BBs++;
     VG_(strcpy)(filename, "???");
     VG_(strcpy)(fn_name,  "???");
     if (line_num) *line_num=0;
     result = False;

   } else if ( found1 &&  found2) {
     SK_(stat).full_debug_BBs++;
     if (line_num) *line_num=line;

   } else if ( found1 && !found2) {
     SK_(stat).file_line_debug_BBs++;
     VG_(strcpy)(fn_name,  "???");
     if (line_num) *line_num=line;

   } else  /*(!found1 &&  found2)*/ {
     SK_(stat).fn_name_debug_BBs++;
     VG_(strcpy)(filename, "???");
     if (line_num) *line_num=0;
   }

   CT_DEBUG(6, "  - get_debug_info(0x%08x): seg %s\n, fn %s\n",
	    instr_addr,
	    !pSegInfo   ? (const UChar*)"-" :
	    (*pSegInfo) ? VG_(seg_filename)(*pSegInfo) :
	    (const UChar*)"(None)",
	    fn_name);

  return result;
}

/* for _libc_freeres_wrapper => _exit renaming */
static BB* exit_bb = 0;

/*
 * Attach function struct to a BB from debug info.
 */
fn_node* SK_(get_fn_node)(BB* bb)
{
    Char       filename[FILENAME_LEN], fnname[FN_NAME_LEN];
    SegInfo*   si;
    Int        line_num;
    fn_node*   fn;

    /* fn from debug info is idempotent for a BB */
    if (bb->fn) return bb->fn;

    CT_DEBUG(3,"+ get_fn_node(BB 0x%x)\n", bb_addr(bb));

    SK_(get_debug_info)(bb_addr(bb),
			filename, fnname, &line_num, &si);

    if (0 == VG_(strcmp)(fnname, "???")) {
	/* Use address as found in library */
	VG_(sprintf)(fnname, "0x%08x%s", 
		     bb->offset,
		     (bb->sect_kind == Vg_SectData) ? " [Data]" :
		     (bb->sect_kind == Vg_SectBSS)  ? " [BSS]"  :
		     (bb->sect_kind == Vg_SectGOT)  ? " [GOT]"  :
		     (bb->sect_kind == Vg_SectPLT)  ? " [PLT]"  : "");
    }
    else {
      if (VG_(get_fnname_if_entry)(bb_addr(bb), fnname, FN_NAME_LEN))
	bb->is_entry = 1;
    }

    /* HACK for correct _exit: 
     * _exit is redirected to VG_(__libc_freeres_wrapper) by valgrind,
     * so we rename it back again :-)
     */
    if (0 == VG_(strcmp)(fnname, "vgPlain___libc_freeres_wrapper")
	&& exit_bb) {
      SK_(get_debug_info)(bb_addr(exit_bb),
			  filename, fnname, &line_num, &si);
	
	CT_DEBUG(1, "__libc_freeres_wrapper renamed to _exit\n");
    }
    if (0 == VG_(strcmp)(fnname, "_exit") && !exit_bb)
	exit_bb = bb;
    

    fn = get_fn_node_inseg( si, filename, fnname);

    if (bb->sect_kind == Vg_SectPLT)	
	fn->skip = SK_(clo).skip_plt;
    
    SK_(update_fn_config)(fn);

    /* Every function gets a "pure" context, i.e. a context with stack
     * depth 1 only with this function. This is for compression of mangled
     * names
     */
    if (!fn->pure_cxt) {
	fn_node* pure[2];
	pure[0] = 0;
	pure[1] = fn;
	fn->pure_cxt = SK_(get_cxt)(pure+1);
    }

    bb->fn   = fn;
    bb->line = line_num;

    CT_DEBUG(3,"- get_fn_node(BB 0x%x): %s (in %s:%d)\n",
	     bb_addr(bb), fnname, filename, line_num);

    return fn;
}


/*------------------------------------------------------------*/
/*--- Active function array operations                     ---*/
/*------------------------------------------------------------*/

/* The active function array is a thread-specific array
 * of UInts, mapping function numbers to the active count of
 * functions.
 * The active count is the number of times a function appears
 * in the current call stack, and is used when costs for recursion
 * levels should be separated.
 */

UInt* SK_(get_fn_entry)(Int n)
{
  CT_ASSERT(n < current_fn_active.size);
  return current_fn_active.array + n;
}

void SK_(init_fn_array)(fn_array* a)
{
  Int i;

  CT_ASSERT(a != 0);

  a->size = N_INITIAL_FN_ARRAY_SIZE;
  if (a->size <= SK_(stat).distinct_fns)
    a->size = SK_(stat).distinct_fns+1;
  
  a->array = (UInt*) VG_(malloc)(a->size * sizeof(UInt));
  for(i=0;i<a->size;i++)
    a->array[i] = 0;
}

void SK_(copy_current_fn_array)(fn_array* dst)
{
  CT_ASSERT(dst != 0);

  dst->size  = current_fn_active.size;
  dst->array = current_fn_active.array;
}

fn_array* SK_(get_current_fn_array)()
{
  return &current_fn_active;
}

void SK_(set_current_fn_array)(fn_array* a)
{
  CT_ASSERT(a != 0);

  current_fn_active.size  = a->size;
  current_fn_active.array = a->array;
  if (current_fn_active.size <= SK_(stat).distinct_fns)
    resize_fn_array();
}

/* ensure that active_array is big enough:
 *  <distinct_fns> is the highest index, so <fn_active_array_size>
 *  has to be bigger than that.
 */
static void resize_fn_array()
{
    UInt* new;
    Int i, newsize;

    newsize = current_fn_active.size;
    while (newsize <= SK_(stat).distinct_fns) newsize *=2;

    CT_DEBUG(0, "Resize fn_active_array: %d => %d\n",
	     current_fn_active.size, newsize);

    new = VG_(malloc)(newsize * sizeof(UInt));
    for(i=0;i<current_fn_active.size;i++)
      new[i] = current_fn_active.array[i];
    while(i<newsize)
	new[i++] = 0;

    VG_(free)(current_fn_active.array);
    current_fn_active.size = newsize;
    current_fn_active.array = new;
    SK_(stat).fn_array_resizes++;
}