Logo Search packages:      
Sourcecode: callgrind version File versions

callstack.c

/*--------------------------------------------------------------------*/
/*--- Callgrind                                                    ---*/
/*---                                               ct_callstack.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 "global.h"

/*------------------------------------------------------------*/
/*--- Call stack, operations                               ---*/
/*------------------------------------------------------------*/

/* Stack of current thread. Gets initialized when switching to 1st thread.
 *
 * The artificial call stack is an array of call_entry's, representing
 * stack frames of the executing program. 
 * Array call_stack and call_stack_esp have same size and grow on demand.
 * Array call_stack_esp holds ESPs of corresponding stack frames.
 *
 */

#define N_CALL_STACK_INITIAL_ENTRIES 500

call_stack SK_(current_call_stack);

void SK_(init_call_stack)(call_stack* s)
{
  Int i;

  CT_ASSERT(s != 0);

  s->size = N_CALL_STACK_INITIAL_ENTRIES;   
  s->entry = (call_entry*) VG_(malloc)(s->size * sizeof(call_entry));
  s->sp = 0;
  s->entry[0].cxt = 0; /* for assertion in push_cxt() */

  for(i=0; i<s->size; i++) s->entry[i].enter_cost = 0;
}

call_entry* SK_(get_call_entry)(Int sp)
{
  CT_ASSERT(sp <= SK_(current_call_stack).sp);
  return &(SK_(current_call_stack).entry[sp]);
}

void SK_(copy_current_call_stack)(call_stack* dst)
{
  CT_ASSERT(dst != 0);

  dst->size  = SK_(current_call_stack).size;
  dst->entry = SK_(current_call_stack).entry;
  dst->sp    = SK_(current_call_stack).sp;
}

void SK_(set_current_call_stack)(call_stack* s)
{
  CT_ASSERT(s != 0);

  SK_(current_call_stack).size  = s->size;
  SK_(current_call_stack).entry = s->entry;
  SK_(current_call_stack).sp    = s->sp;
}


static __inline__
void ensure_stack_size(Int i)
{
  Int oldsize;
  call_stack *cs = &SK_(current_call_stack);

  if (i < cs->size) return;

  oldsize = cs->size;
  cs->size *= 2;
  while (i > cs->size) cs->size *= 2;

  cs->entry = (call_entry*) VG_(realloc)(cs->entry,
                               cs->size * sizeof(call_entry));

  for(i=oldsize; i<cs->size; i++)
    cs->entry[i].enter_cost = 0;

  SK_(stat).call_stack_resizes++;
 
  CT_DEBUGIF(2)
    VG_(printf)("        call stack enlarged to %d entries\n",
            SK_(current_call_stack).size);
}



/* Called when function entered nonrecursive */
static void function_entered(fn_node* fn, BBCC* to)
{
  CT_ASSERT(fn != 0);

#if CT_ENABLE_DEBUG
  if (fn->verbosity >=0) {
    Int old = SK_(clo).verbose;
    SK_(clo).verbose = fn->verbosity;
    fn->verbosity = old;
    VG_(message)(Vg_DebugMsg, 
             "Entering %s: Verbosity set to %d",
             fn->name, SK_(clo).verbose);
  }
#endif            
          
  if (fn->dump_before) {
    Char trigger[FN_NAME_LEN];
    VG_(sprintf)(trigger, "--dump-before=%s", fn->name);
    SK_(dump_profile)(trigger, True);
  }
  else if (fn->zero_before) {
    SK_(zero_all_cost)(True);
  }

  if (fn->toggle_collect) {
    SK_(current_state).collect = !SK_(current_state).collect;
    CT_DEBUG(2,"   entering %s: toggled collection state to %s\n",
           fn->name,
           SK_(current_state).collect ? "ON" : "OFF");
  }

  if (SK_(clo).collect_data && fn->is_free) {
    int v = SK_(handle_free)( ((UInt*)VG_(get_stack_pointer)())[1] );
    if (SK_(clo).collect_alloc) {
      Int o = SK_(sets).off_full_user+2;
      if (o>0) {
      SK_(current_state).cost[o] ++;
      SK_(current_state).cost[o+1] += v;

      if (!to->skipped)
        SK_(init_cost_lz)(SK_(sets).full, &(to->skipped));
      to->skipped[o] ++;
      to->skipped[o+1] += v;
      }
    }
  }

  if (SK_(clo).collect_data && fn->is_constructor)
    SK_(handle_constructor)( ((UInt*)VG_(get_stack_pointer)())[1],
                       fn->name);

  if (SK_(clo).collect_alloc && fn->is_malloc) {
    Int o = SK_(sets).off_full_user;
    Int* sp = (Int*) VG_(get_stack_pointer)();
    Int v1 = sp ? sp[1]:0;
    CT_DEBUG(3,"   entering malloc (cost at %d, sp %x, [1]=%x)\n",
           o, sp, v1);
    if (o>0) {
      SK_(current_state).cost[o] ++;
      SK_(current_state).cost[o+1] += v1;

      if (!to->skipped)
      SK_(init_cost_lz)(SK_(sets).full, &(to->skipped));
      to->skipped[o] ++;
      to->skipped[o+1] += v1;
    }
  }  
}     

/* Called when function left (no recursive level active) */
static void function_left(fn_node* fn, BBCC* from)
{
  CT_ASSERT(fn != 0);

  if (fn->dump_after) {
    Char trigger[FN_NAME_LEN];
    VG_(sprintf)(trigger, "--dump-after=%s", fn->name);
    SK_(dump_profile)(trigger, True);
  }
  if (fn->toggle_collect) {
    SK_(current_state).collect = !SK_(current_state).collect;
    CT_DEBUG(2,"   leaving %s: toggled collection state to %s\n",
           fn->name,
           SK_(current_state).collect ? "ON" : "OFF");
  }

  if (SK_(clo).collect_data) {
    if (fn->is_malloc || fn->is_realloc) {
      UInt* sp = (Int*) VG_(get_stack_pointer)();
      UInt v0 = sp ? sp[0]:0;
      UInt v1 = sp ? sp[1]:0;
#if VG_CORE_INTERFACE_MAJOR_VERSION < 7
      UInt eax = VG_(get_archreg)(R_EAX);
#else
      /* VG 2.3 gets rid of baseblock with current arch regs */
      UInt eax = VG_(get_thread_archreg)(VG_(get_running_tid)(), R_EAX);
#endif
      CT_DEBUG(3,"   leaving %s (sp %x, eax=%x, [0]=%x, [1]=%x)\n",
             fn->is_malloc ? "malloc":"realloc",
             sp, eax, v0, v1);
      if (fn->is_malloc)
      SK_(handle_malloc)(eax, v0);
      else {
      /* fn->is_realloc */
      Int sizeold = SK_(handle_realloc)(eax, v0, v1);

      Int o = SK_(sets).off_full_user;
      if (SK_(clo).collect_alloc && (o>0)) {
        /* alloc counter */
        SK_(current_state).cost[o] ++;
        SK_(current_state).cost[o+1] += v1;
        /* free counter */
        SK_(current_state).cost[o+2] ++;
        SK_(current_state).cost[o+3] += sizeold;
        
        if (!from->skipped)
          SK_(init_cost_lz)(SK_(sets).full, &(from->skipped));
        from->skipped[o] ++;
        from->skipped[o+1] += v1;
        from->skipped[o+2] ++;
        from->skipped[o+3] += sizeold;
      }
      }
    }
    else if (fn->is_destructor) {
      SK_(handle_destructor)( ((UInt*)VG_(get_stack_pointer)())[0],
                        fn->name);
    }
  }

#if CT_ENABLE_DEBUG
  if (fn->verbosity >=0) {
    Int old = SK_(clo).verbose;
    SK_(clo).verbose = fn->verbosity;
    fn->verbosity = old;
    VG_(message)(Vg_DebugMsg, 
             "Leaving %s: Verbosity set back to %d",
             fn->name, SK_(clo).verbose);
  }
#endif            
}


/* Push call on call stack.
 *
 * Increment the usage count for the function called.
 * A jump from <from> to <to>, with <esp>.
 * If <skip> is true, this is a call to a function to be skipped;
 * for this, we set jcc = 0.
 */
void SK_(push_call_stack)(BBCC* from, BBCC* to, Addr esp, Bool skip)
{
    jCC* jcc;
    UInt* pdepth;
    call_entry* current_entry;

    /* Ensure a call stack of size <current_sp>+1.
     * The +1 is needed as push_cxt will store the
     * context at [current_sp]
     */
    ensure_stack_size(SK_(current_call_stack).sp +1);
    current_entry = &(SK_(current_call_stack).entry[SK_(current_call_stack).sp]);

    if (skip) {
      jcc = 0;
    }
    else {
      fn_node* to_fn = to->cxt->fn[0];

      if (SK_(current_state).nonskipped) {
          /* this is a jmp from skipped to nonskipped */
          CT_ASSERT(SK_(current_state).nonskipped == from);
      }

      /* As push_cxt() has to be called before push_call_stack if not
       * skipping, the old context should already be saved on the stack */
      CT_ASSERT(current_entry->cxt != 0);
      SK_(copy_cost_lz)( SK_(sets).full, &(current_entry->enter_cost),
                     SK_(current_state).cost );

      jcc = SK_(get_jcc)(from, to);
      CT_ASSERT(jcc != 0);

      pdepth = SK_(get_fn_entry)(to_fn->number);
      if (SK_(clo).skip_direct_recursion) {
          /* only increment depth if another function is called */
        if (jcc->from->cxt->fn[0] != to_fn) (*pdepth)++;
      }
      else (*pdepth)++;

      if (*pdepth>1)
        SK_(stat).rec_call_counter++;
      
      jcc->call_counter++;
      SK_(stat).call_counter++;

      if (*pdepth == 1) function_entered(to_fn, to);
    }

    /* put jcc on call stack */
    current_entry->jcc = jcc;
    current_entry->esp = esp;
    current_entry->nonskipped = SK_(current_state).nonskipped;

    SK_(current_call_stack).sp++;

    /* To allow for above assertion we set context of next frame to 0 */
    CT_ASSERT(SK_(current_call_stack).sp < SK_(current_call_stack).size);
    current_entry++;
    current_entry->cxt = 0;

    if (!skip)
      SK_(current_state).nonskipped = 0;
    else if (!SK_(current_state).nonskipped) {
      /* a call from nonskipped to skipped */
      SK_(current_state).nonskipped = from;
      if (!SK_(current_state).nonskipped->skipped) {
        SK_(init_cost_lz)( SK_(sets).full,
                       &SK_(current_state).nonskipped->skipped);
        SK_(stat).distinct_skips++;
      }
    }

#if CT_ENABLE_DEBUG
    CT_DEBUGIF(0) {
      if (SK_(clo).verbose<2) {
        if (jcc && jcc->to && jcc->to->bb) {
          char sp[][41] = { "   .   .   .   .   .   .   .   .   .   .",
                        "  .   .   .   .   .   .   .   .   .   . ",
                        " .   .   .   .   .   .   .   .   .   .  ",
                        ".   .   .   .   .   .   .   .   .   .   " };

          int s = SK_(current_call_stack).sp;
          BB* bb = jcc->to->bb;
          if (s>40) s=40;
          VG_(printf)("%s> %s (%s / %x)\n", sp[s%4]+40-s, bb->fn->name,
                  bb->obj->name + bb->obj->last_slash_pos,
                  bb->offset);
        }
      }
      else if (SK_(clo).verbose<4) {
          VG_(printf)("+ %2d ", SK_(current_call_stack).sp);
          SK_(print_short_jcc)(jcc);
          VG_(printf)(", ESP %x\n", esp);
      }
      else {
          VG_(printf)("  Pushed ");
          SK_(print_stackentry)(3, SK_(current_call_stack).sp-1);
      }
    }
#endif

}


/* Pop call stack and update inclusive sums.
 * Returns modified fcc.
 *
 * If the JCC becomes inactive, call entries are freed if possible
 */
void SK_(pop_call_stack)()
{
    jCC* jcc;
    Int depth = 0;
    call_entry* lower_entry =
      &(SK_(current_call_stack).entry[SK_(current_call_stack).sp-1]);

    CT_DEBUG(4,"+ pop_call_stack: frame %d, jcc 0x%p\n", 
            SK_(current_call_stack).sp, lower_entry->jcc);

    /* jCC item not any more on real stack: pop */
    jcc = lower_entry->jcc;
    SK_(current_state).nonskipped = lower_entry->nonskipped;

    if (jcc) {
      fn_node* to_fn  = jcc->to->cxt->fn[0];
      UInt* pdepth =  SK_(get_fn_entry)(to_fn->number);
      if (SK_(clo).skip_direct_recursion) {
          /* only decrement depth if another function was called */
        if (jcc->from->cxt->fn[0] != to_fn) (*pdepth)--;
      }
      else (*pdepth)--;
      depth = *pdepth;

      /* add cost difference to sum */
      if ( SK_(add_diff_cost_lz)( SK_(sets).full, &(jcc->cost),
                            lower_entry->enter_cost,
                            SK_(current_state).cost) ) {
          
        /* only count this call if it attributed some cost.
         * the ret_counter is used to check if a BBCC dump is needed.
         */
        jcc->from->ret_counter++;
      }
      SK_(stat).ret_counter++;

      /* restore context */
      SK_(current_state).cxt  = lower_entry->cxt;
      SK_(current_fn_stack).top =
        SK_(current_fn_stack).bottom + lower_entry->fn_sp;
      CT_ASSERT(SK_(current_state).cxt != 0);

      if (depth == 0) function_left(to_fn, jcc->from);
    }

    /* To allow for an assertion in push_call_stack() */
    lower_entry->cxt = 0;

    SK_(current_call_stack).sp--;

#if CT_ENABLE_DEBUG
    CT_DEBUGIF(1) {
      if (SK_(clo).verbose<4) {
          if (jcc) {
            /* popped JCC target first */
            VG_(printf)("- %2d %x => ", 
                      SK_(current_call_stack).sp,
                      bb_addr(jcc->to->bb));
            SK_(print_addr)(bb_jmpaddr(jcc->from->bb));
            VG_(printf)(", ESP %x\n",
                      SK_(current_call_stack).entry[SK_(current_call_stack).sp].esp);
            SK_(print_cost)(10, SK_(sets).full, jcc->cost);
          }
          else
            VG_(printf)("- %2d [Skipped JCC], ESP %x\n",
                      SK_(current_call_stack).sp,
                      SK_(current_call_stack).entry[SK_(current_call_stack).sp].esp);
      }
      else {
          VG_(printf)("  Popped ");
          SK_(print_stackentry)(7, SK_(current_call_stack).sp);
          if (jcc) {
            VG_(printf)("       returned to ");
            SK_(print_addr_ln)(bb_jmpaddr(jcc->from->bb));
          }
      }
    }
#endif

}


/* remove CallStack items to sync with current ESP
 */
Int SK_(unwind_call_stack)(Addr esp)
{
    Int old_current_sp = SK_(current_call_stack).sp;

    CT_DEBUG(4,"+ unwind_call_stack: esp 0x%x, frame %d\n", 
            esp, SK_(current_call_stack).sp);


    /* We pop old stack frames.
     * For a call, be p the stack address with return address.
     *  - call_stack_esp[] has ESP after the CALL: p-4
     *  - current esp is after a RET: >= p
     */
    while((SK_(current_call_stack).sp >0) &&
        (SK_(current_call_stack).entry[SK_(current_call_stack).sp-1].esp < esp))
      SK_(pop_call_stack)();

    CT_DEBUG(4,"- unwind_call_stack: diff %d\n", 
            old_current_sp - SK_(current_call_stack).sp);

    return old_current_sp - SK_(current_call_stack).sp;
}



Generated by  Doxygen 1.6.0   Back to index