
/*--------------------------------------------------------------------*/
/*--- Stack management.                                 m_stacks.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Valgrind, a dynamic binary instrumentation
   framework.

   Copyright (C) 2000-2013 Julian Seward 
      jseward@acm.org

   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 "pub_core_basics.h"
#include "pub_core_debuglog.h"
#include "pub_core_libcassert.h"
#include "pub_core_libcprint.h"
#include "pub_core_mallocfree.h"
#include "pub_core_aspacemgr.h"
#include "pub_core_options.h"
#include "pub_core_stacks.h"
#include "pub_core_tooliface.h"

// For expensive debugging
#define EDEBUG(fmt, args...) //VG_(debugLog)(2, "stacks", fmt, ## args)

/*
   The stack
   ~~~~~~~~~
   The stack's segment seems to be dynamically extended downwards by
   the kernel as the stack pointer moves down.  Initially, a 1-page
   (4k) stack is allocated.  When SP moves below that for the first
   time, presumably a page fault occurs.  The kernel detects that the
   faulting address is in the range from SP - VG_STACK_REDZONE_SZB
   upwards to the current valid stack.  It then extends the stack
   segment downwards for enough to cover the faulting address, and
   resumes the process (invisibly).  The process is unaware of any of
   this.

   That means that Valgrind can't spot when the stack segment is being
   extended.  Fortunately, we want to precisely and continuously
   update stack permissions around SP, so we need to spot all writes
   to SP anyway.

   The deal is: when SP is assigned a lower value, the stack is being
   extended.  Create suitably-permissioned pages to fill in any holes
   between the old stack ptr and this one, if necessary.  Then mark
   all bytes in the area just "uncovered" by this SP change as
   write-only.

   When SP goes back up, mark the area receded over as unreadable and
   unwritable.

   Just to record the SP boundary conditions somewhere convenient: 
   SP - VG_STACK_REDZONE_SZB always points to the lowest live byte in
   the stack.  All addresses below SP - VG_STACK_REDZONE_SZB are not
   live; those at and above it are.

   We do not concern ourselves here with the VG_STACK_REDZONE_SZB
   bias; that is handled by new_mem_stack/die_mem_stack.
*/

/*
 * This structure holds information about the start and end addresses of
 * registered stacks.  There's always at least one stack registered:
 * the main process stack.  It will be the first stack registered and
 * so will have a stack id of 0.  The user does not need to register
 * this stack: Valgrind does it automatically right before it starts
 * running the client.  No other stacks are automatically registered by
 * Valgrind, however.
 */
typedef struct _Stack {
   UWord id;
   Addr start; // Lowest stack byte, included.
   Addr end;   // Highest stack byte, included.
   struct _Stack *next;
} Stack;

static Stack *stacks;
static UWord next_id;  /* Next id we hand out to a newly registered stack */

/*
 * These are the id, start and end values of the current stack.  If the
 * stack pointer falls outside the range of the current stack, we search
 * the stacks list above for a matching stack.
 */
static Stack *current_stack;

/* Find 'st' in the stacks_list and move it one step closer the the
   front of the list, so as to make subsequent searches for it
   cheaper. */
static void move_Stack_one_step_forward ( Stack* st )
{
   Stack *st0, *st1, *st2;
   if (st == stacks)
      return; /* already at head of list */
   vg_assert(st != NULL);
   st0 = stacks;
   st1 = NULL;
   st2 = NULL;
   while (True) {
      if (st0 == NULL || st0 == st) break;
      st2 = st1;
      st1 = st0;
      st0 = st0->next;
   }
   vg_assert(st0 == st);
   if (st0 != NULL && st1 != NULL && st2 != NULL) {
      Stack* tmp;
      /* st0 points to st, st1 to its predecessor, and st2 to st1's
         predecessor.  Swap st0 and st1, that is, move st0 one step
         closer to the start of the list. */
      vg_assert(st2->next == st1);
      vg_assert(st1->next == st0);
      tmp = st0->next;
      st2->next = st0;
      st0->next = st1;
      st1->next = tmp;
   }
   else
   if (st0 != NULL && st1 != NULL && st2 == NULL) {
      /* it's second in the list. */
      vg_assert(stacks == st1);
      vg_assert(st1->next == st0);
      st1->next = st0->next;
      st0->next = st1;
      stacks = st0;
   }
}

/* Find what stack an address falls into. */
static Stack* find_stack_by_addr(Addr sp)
{
   static UWord n_fails = 0;
   static UWord n_searches = 0;
   static UWord n_steps = 0;
   Stack *i = stacks;
   n_searches++;
   if (0 && 0 == (n_searches % 10000))
      VG_(printf)("(hgdev) %lu searches, %lu steps, %lu fails\n",
                  n_searches, n_steps+1, n_fails);
   /* fast track common case */
   if (i && sp >= i->start && sp <= i->end)
      return i;
   /* else search the list */
   while (i) {
      n_steps++;
      if (sp >= i->start && sp <= i->end) {
         if (1 && (n_searches & 0x3F) == 0) {
            move_Stack_one_step_forward( i );
         }
         return i;
      }
      i = i->next;
   }
   n_fails++;
   return NULL;
}

/*
 * Register a new stack from start - end.  This is invoked from the
 * VALGRIND_STACK_REGISTER client request, and is also called just before
 * we start the client running, to register the main process stack.
 */
UWord VG_(register_stack)(Addr start, Addr end)
{
   Stack *i;

   if (start > end) {
      /* If caller provides addresses in reverse order, swap them.
         Ugly but not doing that breaks backward compatibility with
         (user) code registering stacks with start/end inverted . */
      Addr t = end;
      end = start;
      start = t;
   }

   i = VG_(malloc)("stacks.rs.1", sizeof(Stack));
   i->start = start;
   i->end = end;
   i->id = next_id++;
   i->next = stacks;
   stacks = i;

   if (i->id == 0) {
      current_stack = i;
   }

   VG_(debugLog)(2, "stacks", "register [start-end] [%p-%p] as stack %lu\n",
                    (void*)start, (void*)end, i->id);

   return i->id;
}

/*
 * Deregister a stack.  This is invoked from the VALGRIND_STACK_DEREGISTER
 * client request.
 */
void VG_(deregister_stack)(UWord id)
{
   Stack *i = stacks;
   Stack *prev = NULL;

   VG_(debugLog)(2, "stacks", "deregister stack %lu\n", id);

   if (current_stack && current_stack->id == id) { 
      current_stack = NULL;
   }

   while(i) {
      if (i->id == id) {
         if(prev == NULL) {
            stacks = i->next;
         } else {
            prev->next = i->next;
         }
         VG_(free)(i);
         return;
      }
      prev = i;
      i = i->next;
   }
}

/*
 * Change a stack.  This is invoked from the VALGRIND_STACK_CHANGE client
 * request and from the stack growth stuff the signals module when
 * extending the main process stack.
 */
void VG_(change_stack)(UWord id, Addr start, Addr end)
{
   Stack *i = stacks;

   while (i) {
      if (i->id == id) {
         VG_(debugLog)(2, "stacks", 
                       "change stack %lu from [%p-%p] to [%p-%p]\n",
                       id, (void*)i->start, (void*)i->end,
                           (void*)start,    (void*)end);
         /* FIXME : swap start/end like VG_(register_stack) ??? */
         i->start = start;
         i->end = end;
         return;
      }
      i = i->next;
   }
}

/*
 * Find the bounds of the stack (if any) which includes the
 * specified stack pointer.
 */
void VG_(stack_limits)(Addr SP, Addr *start, Addr *end )
{
   Stack* stack = find_stack_by_addr(SP);
   NSegment const *stackseg = VG_(am_find_nsegment) (SP);

   if (stack) {
      *start = stack->start;
      *end = stack->end;
   }

   /* SP is assumed to be in a RW segment or in the SkResvn segment of an
      extensible stack (normally, only the main thread has an extensible
      stack segment).
      If no such segment is found, assume we have no valid
      stack for SP, and set *start and *end to 0.
      Otherwise, possibly reduce the stack limits using the boundaries of
      the RW segment/SkResvn segments containing SP. */
   if (stackseg == NULL) {
      VG_(debugLog)(2, "stacks", 
                    "no addressable segment for SP %p\n", 
                    (void*)SP);
      *start = 0;
      *end = 0;
      return;
   } 

   if ((!stackseg->hasR || !stackseg->hasW)
       && (stackseg->kind != SkResvn || stackseg->smode != SmUpper)) {
      VG_(debugLog)(2, "stacks", 
                    "segment for SP %p is not RW or not a SmUpper Resvn\n",
                    (void*)SP);
      *start = 0;
      *end = 0;
      return;
   } 

   // SP is in a RW segment, or in the SkResvn of an extensible stack.
   if (*start < stackseg->start) {
      VG_(debugLog)(2, "stacks", 
                    "segment for SP %p changed stack start limit"
                    " from %p to %p\n",
                    (void*)SP, (void*)*start, (void*)stackseg->start);
      *start = stackseg->start;
   }

   if (stackseg->kind == SkResvn) {
      stackseg = VG_(am_next_nsegment)(stackseg, /*forward*/ True);
      if (!stackseg || !stackseg->hasR || !stackseg->hasW
          || stackseg->kind != SkAnonC) {
         VG_(debugLog)(2, "stacks", 
                       "Next forward segment for SP %p Resvn segment"
                       " is not RW or not AnonC\n",
                       (void*)SP);
         *start = 0;
         *end = 0;
         return;
      }
   }

   if (*end > stackseg->end) {
      VG_(debugLog)(2, "stacks", 
                    "segment for SP %p changed stack end limit"
                    " from %p to %p\n",
                    (void*)SP, (void*)*end, (void*)stackseg->end);
      *end = stackseg->end;
   }

   /* If reducing start and/or end to the SP segment gives an
      empty range, return 'empty' limits */
   if (*start > *end) {
      VG_(debugLog)(2, "stacks", 
                    "stack for SP %p start %p after end %p\n",
                    (void*)SP, (void*)*start, (void*)end);
      *start = 0;
      *end = 0;
   }
}

/* complaints_stack_switch reports that SP has changed by more than some
   threshold amount (by default, 2MB).  We take this to mean that the
   application is switching to a new stack, for whatever reason.
   
   JRS 20021001: following discussions with John Regehr, if a stack
   switch happens, it seems best not to mess at all with memory
   permissions.  Seems to work well with Netscape 4.X.  Really the
   only remaining difficulty is knowing exactly when a stack switch is
   happening. */
__attribute__((noinline))
static void complaints_stack_switch (Addr old_SP, Addr new_SP)
{
   static Int complaints = 3;
   if (VG_(clo_verbosity) > 0 && complaints > 0 && !VG_(clo_xml)) {
      Word delta  = (Word)new_SP - (Word)old_SP;
      complaints--;
      VG_(message)(Vg_UserMsg,
                   "Warning: client switching stacks?  "
                   "SP change: 0x%lx --> 0x%lx\n", old_SP, new_SP);
      VG_(message)(Vg_UserMsg,
                   "         to suppress, use: --max-stackframe=%ld "
                   "or greater\n",
                   (delta < 0 ? -delta : delta));
      if (complaints == 0)
         VG_(message)(Vg_UserMsg,
                      "         further instances of this message "
                      "will not be shown.\n");
   }
}

/* The functions VG_(unknown_SP_update) and VG_(unknown_SP_update_w_ECU)
   get called if new_mem_stack and/or die_mem_stack are
   tracked by the tool, and one of the specialised cases
   (eg. new_mem_stack_4) isn't used in preference.  

   These functions are performance critical, so are built with macros. */

// preamble + check if stack has switched.
#define IF_STACK_SWITCH_SET_current_stack_AND_RETURN                    \
   Word delta  = (Word)new_SP - (Word)old_SP;                           \
                                                                        \
   EDEBUG("current_stack  %p-%p %lu new_SP %p old_SP %p\n",             \
          (void *) (current_stack ? current_stack->start : 0x0),        \
          (void *) (current_stack ? current_stack->end : 0x0),          \
          current_stack ? current_stack->id : 0,                        \
          (void *)new_SP, (void *)old_SP);                              \
                                                                        \
   /* Check if the stack pointer is still in the same stack as before. */ \
   if (UNLIKELY(current_stack == NULL ||                                \
      new_SP < current_stack->start || new_SP > current_stack->end)) {  \
      Stack* new_stack = find_stack_by_addr(new_SP);                    \
      if (new_stack                                                     \
          && (current_stack == NULL || new_stack->id != current_stack->id)) { \
         /* The stack pointer is now in another stack.  Update the current */ \
         /* stack information and return without doing anything else. */ \
         current_stack = new_stack;                                     \
         EDEBUG("new current_stack  %p-%p %lu \n",                      \
                (void *) current_stack->start,                          \
                (void *) current_stack->end,                            \
                current_stack->id);                                     \
         return;                                                        \
      } else                                                            \
         EDEBUG("new current_stack not found\n");                       \
   }

#define IF_BIG_DELTA_complaints_AND_RETURN                              \
   if (UNLIKELY(delta < -VG_(clo_max_stackframe)                        \
                || VG_(clo_max_stackframe) < delta)) {                  \
      complaints_stack_switch(old_SP, new_SP);                          \
      return;                                                           \
   }

#define IF_SMALLER_STACK_die_mem_stack_AND_RETURN                       \
   if (delta > 0) {                                                     \
      VG_TRACK( die_mem_stack, old_SP,  delta );                        \
      return;                                                           \
   }

  
VG_REGPARM(3)
void VG_(unknown_SP_update_w_ECU)( Addr old_SP, Addr new_SP, UInt ecu ) {
   IF_STACK_SWITCH_SET_current_stack_AND_RETURN;
   IF_BIG_DELTA_complaints_AND_RETURN;
   IF_SMALLER_STACK_die_mem_stack_AND_RETURN;
   if (delta < 0) { // IF_BIGGER_STACK
      VG_TRACK( new_mem_stack_w_ECU, new_SP, -delta, ecu );
      return;
   }
   // SAME_STACK. nothing to do.
}

VG_REGPARM(2)
void VG_(unknown_SP_update)( Addr old_SP, Addr new_SP ) {
   IF_STACK_SWITCH_SET_current_stack_AND_RETURN;
   IF_BIG_DELTA_complaints_AND_RETURN;
   IF_SMALLER_STACK_die_mem_stack_AND_RETURN;
   if (delta < 0) { // IF_BIGGER_STACK
      VG_TRACK( new_mem_stack,      new_SP, -delta );
      return;
   }
   // SAME_STACK. nothing to do.
}

/*--------------------------------------------------------------------*/
/*--- end                                                          ---*/
/*--------------------------------------------------------------------*/