coregrind/m_stacks.c

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- Stack management.                                 m_stacks.c ---*/
   4 /*--------------------------------------------------------------------*/
   5
   6 /*
   7    This file is part of Valgrind, a dynamic binary instrumentation
   8    framework.
   9
  10    Copyright (C) 2000-2013 Julian Seward
  11       jseward@acm.org
  12
  13    This program is free software; you can redistribute it and/or
  14    modify it under the terms of the GNU General Public License as
  15    published by the Free Software Foundation; either version 2 of the
  16    License, or (at your option) any later version.
  17
  18    This program is distributed in the hope that it will be useful, but
  19    WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21    General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, write to the Free Software
  25    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  26    02111-1307, USA.
  27
  28    The GNU General Public License is contained in the file COPYING.
  29 */
  30
  31 #include "pub_core_basics.h"
  32 #include "pub_core_debuglog.h"
  33 #include "pub_core_libcassert.h"
  34 #include "pub_core_libcprint.h"
  35 #include "pub_core_mallocfree.h"
  36 #include "pub_core_aspacemgr.h"
  37 #include "pub_core_options.h"
  38 #include "pub_core_stacks.h"
  39 #include "pub_core_tooliface.h"
  40
  41 // For expensive debugging
  42 #define EDEBUG(fmt, args...) //VG_(debugLog)(2, "stacks", fmt, ## args)
  43
  44 /*
  45    The stack
  46    ~~~~~~~~~
  47    The stack's segment seems to be dynamically extended downwards by
  48    the kernel as the stack pointer moves down.  Initially, a 1-page
  49    (4k) stack is allocated.  When SP moves below that for the first
  50    time, presumably a page fault occurs.  The kernel detects that the
  51    faulting address is in the range from SP - VG_STACK_REDZONE_SZB
  52    upwards to the current valid stack.  It then extends the stack
  53    segment downwards for enough to cover the faulting address, and
  54    resumes the process (invisibly).  The process is unaware of any of
  55    this.
  56
  57    That means that Valgrind can't spot when the stack segment is being
  58    extended.  Fortunately, we want to precisely and continuously
  59    update stack permissions around SP, so we need to spot all writes
  60    to SP anyway.
  61
  62    The deal is: when SP is assigned a lower value, the stack is being
  63    extended.  Create suitably-permissioned pages to fill in any holes
  64    between the old stack ptr and this one, if necessary.  Then mark
  65    all bytes in the area just "uncovered" by this SP change as
  66    write-only.
  67
  68    When SP goes back up, mark the area receded over as unreadable and
  69    unwritable.
  70
  71    Just to record the SP boundary conditions somewhere convenient:
  72    SP - VG_STACK_REDZONE_SZB always points to the lowest live byte in
  73    the stack.  All addresses below SP - VG_STACK_REDZONE_SZB are not
  74    live; those at and above it are.
  75
  76    We do not concern ourselves here with the VG_STACK_REDZONE_SZB
  77    bias; that is handled by new_mem_stack/die_mem_stack.
  78 */
  79
  80 /*
  81  * This structure holds information about the start and end addresses of
  82  * registered stacks.  There's always at least one stack registered:
  83  * the main process stack.  It will be the first stack registered and
  84  * so will have a stack id of 0.  The user does not need to register
  85  * this stack: Valgrind does it automatically right before it starts
  86  * running the client.  No other stacks are automatically registered by
  87  * Valgrind, however.
  88  */
  89 typedef struct _Stack {
  90    UWord id;
  91    Addr start; // Lowest stack byte, included.
  92    Addr end;   // Highest stack byte, included.
  93    struct _Stack *next;
  94 } Stack;
  95
  96 static Stack *stacks;
  97 static UWord next_id;  /* Next id we hand out to a newly registered stack */
  98
  99 /*
 100  * These are the id, start and end values of the current stack.  If the
 101  * stack pointer falls outside the range of the current stack, we search
 102  * the stacks list above for a matching stack.
 103  */
 104 static Stack *current_stack;
 105
 106 /* Find 'st' in the stacks_list and move it one step closer the the
 107    front of the list, so as to make subsequent searches for it
 108    cheaper. */
 109 static void move_Stack_one_step_forward ( Stack* st )
 110 {
 111    Stack *st0, *st1, *st2;
 112    if (st == stacks)
 113       return; /* already at head of list */
 114    vg_assert(st != NULL);
 115    st0 = stacks;
 116    st1 = NULL;
 117    st2 = NULL;
 118    while (True) {
 119       if (st0 == NULL || st0 == st) break;
 120       st2 = st1;
 121       st1 = st0;
 122       st0 = st0->next;
 123    }
 124    vg_assert(st0 == st);
 125    if (st0 != NULL && st1 != NULL && st2 != NULL) {
 126       Stack* tmp;
 127       /* st0 points to st, st1 to its predecessor, and st2 to st1's
 128          predecessor.  Swap st0 and st1, that is, move st0 one step
 129          closer to the start of the list. */
 130       vg_assert(st2->next == st1);
 131       vg_assert(st1->next == st0);
 132       tmp = st0->next;
 133       st2->next = st0;
 134       st0->next = st1;
 135       st1->next = tmp;
 136    }
 137    else
 138    if (st0 != NULL && st1 != NULL && st2 == NULL) {
 139       /* it's second in the list. */
 140       vg_assert(stacks == st1);
 141       vg_assert(st1->next == st0);
 142       st1->next = st0->next;
 143       st0->next = st1;
 144       stacks = st0;
 145    }
 146 }
 147
 148 /* Find what stack an address falls into. */
 149 static Stack* find_stack_by_addr(Addr sp)
 150 {
 151    static UWord n_fails = 0;
 152    static UWord n_searches = 0;
 153    static UWord n_steps = 0;
 154    Stack *i = stacks;
 155    n_searches++;
 156    if (0 && 0 == (n_searches % 10000))
 157       VG_(printf)("(hgdev) %lu searches, %lu steps, %lu fails\n",
 158                   n_searches, n_steps+1, n_fails);
 159    /* fast track common case */
 160    if (i && sp >= i->start && sp <= i->end)
 161       return i;
 162    /* else search the list */
 163    while (i) {
 164       n_steps++;
 165       if (sp >= i->start && sp <= i->end) {
 166          if (1 && (n_searches & 0x3F) == 0) {
 167             move_Stack_one_step_forward( i );
 168          }
 169          return i;
 170       }
 171       i = i->next;
 172    }
 173    n_fails++;
 174    return NULL;
 175 }
 176
 177 /*
 178  * Register a new stack from start - end.  This is invoked from the
 179  * VALGRIND_STACK_REGISTER client request, and is also called just before
 180  * we start the client running, to register the main process stack.
 181  */
 182 UWord VG_(register_stack)(Addr start, Addr end)
 183 {
 184    Stack *i;
 185
 186    if (start > end) {
 187       /* If caller provides addresses in reverse order, swap them.
 188          Ugly but not doing that breaks backward compatibility with
 189          (user) code registering stacks with start/end inverted . */
 190       Addr t = end;
 191       end = start;
 192       start = t;
 193    }
 194
 195    i = VG_(malloc)("stacks.rs.1", sizeof(Stack));
 196    i->start = start;
 197    i->end = end;
 198    i->id = next_id++;
 199    i->next = stacks;
 200    stacks = i;
 201
 202    if (i->id == 0) {
 203       current_stack = i;
 204    }
 205
 206    VG_(debugLog)(2, "stacks", "register [start-end] [%p-%p] as stack %lu\n",
 207                     (void*)start, (void*)end, i->id);
 208
 209    return i->id;
 210 }
 211
 212 /*
 213  * Deregister a stack.  This is invoked from the VALGRIND_STACK_DEREGISTER
 214  * client request.
 215  */
 216 void VG_(deregister_stack)(UWord id)
 217 {
 218    Stack *i = stacks;
 219    Stack *prev = NULL;
 220
 221    VG_(debugLog)(2, "stacks", "deregister stack %lu\n", id);
 222
 223    if (current_stack && current_stack->id == id) {
 224       current_stack = NULL;
 225    }
 226
 227    while(i) {
 228       if (i->id == id) {
 229          if(prev == NULL) {
 230             stacks = i->next;
 231          } else {
 232             prev->next = i->next;
 233          }
 234          VG_(free)(i);
 235          return;
 236       }
 237       prev = i;
 238       i = i->next;
 239    }
 240 }
 241
 242 /*
 243  * Change a stack.  This is invoked from the VALGRIND_STACK_CHANGE client
 244  * request and from the stack growth stuff the signals module when
 245  * extending the main process stack.
 246  */
 247 void VG_(change_stack)(UWord id, Addr start, Addr end)
 248 {
 249    Stack *i = stacks;
 250
 251    while (i) {
 252       if (i->id == id) {
 253          VG_(debugLog)(2, "stacks",
 254                        "change stack %lu from [%p-%p] to [%p-%p]\n",
 255                        id, (void*)i->start, (void*)i->end,
 256                            (void*)start,    (void*)end);
 257          /* FIXME : swap start/end like VG_(register_stack) ??? */
 258          i->start = start;
 259          i->end = end;
 260          return;
 261       }
 262       i = i->next;
 263    }
 264 }
 265
 266 /*
 267  * Find the bounds of the stack (if any) which includes the
 268  * specified stack pointer.
 269  */
 270 void VG_(stack_limits)(Addr SP, Addr *start, Addr *end )
 271 {
 272    Stack* stack = find_stack_by_addr(SP);
 273    NSegment const *stackseg = VG_(am_find_nsegment) (SP);
 274
 275    if (stack) {
 276       *start = stack->start;
 277       *end = stack->end;
 278    }
 279
 280    /* SP is assumed to be in a RW segment.
 281       If no such segment is found, assume we have no valid
 282       stack for SP, and set *start and *end to 0.
 283       Otherwise, possibly reduce the stack limits to the boundaries of the
 284       RW segment containing SP. */
 285    if (stackseg == NULL) {
 286       VG_(debugLog)(2, "stacks",
 287                     "no addressable segment for SP %p\n",
 288                     (void*)SP);
 289       *start = 0;
 290       *end = 0;
 291    } else if (!stackseg->hasR || !stackseg->hasW) {
 292       VG_(debugLog)(2, "stacks",
 293                     "segment for SP %p is not Readable and/or not Writable\n",
 294                     (void*)SP);
 295       *start = 0;
 296       *end = 0;
 297    } else {
 298       if (*start < stackseg->start) {
 299          VG_(debugLog)(2, "stacks",
 300                        "segment for SP %p changed stack start limit"
 301                        " from %p to %p\n",
 302                        (void*)SP, (void*)*start, (void*)stackseg->start);
 303          *start = stackseg->start;
 304       }
 305       if (*end > stackseg->end) {
 306          VG_(debugLog)(2, "stacks",
 307                        "segment for SP %p changed stack end limit"
 308                        " from %p to %p\n",
 309                        (void*)SP, (void*)*end, (void*)stackseg->end);
 310          *end = stackseg->end;
 311       }
 312
 313       /* If reducing start and/or end to the SP segment gives an
 314          empty range, return 'empty' limits */
 315       if (*start > *end) {
 316          VG_(debugLog)(2, "stacks",
 317                        "stack for SP %p start %p after end %p\n",
 318                        (void*)SP, (void*)*start, (void*)end);
 319          *start = 0;
 320          *end = 0;
 321       }
 322    }
 323 }
 324
 325 /* complaints_stack_switch reports that SP has changed by more than some
 326    threshold amount (by default, 2MB).  We take this to mean that the
 327    application is switching to a new stack, for whatever reason.
 328
 329    JRS 20021001: following discussions with John Regehr, if a stack
 330    switch happens, it seems best not to mess at all with memory
 331    permissions.  Seems to work well with Netscape 4.X.  Really the
 332    only remaining difficulty is knowing exactly when a stack switch is
 333    happening. */
 334 __attribute__((noinline))
 335 static void complaints_stack_switch (Addr old_SP, Addr new_SP)
 336 {
 337    static Int complaints = 3;
 338    if (VG_(clo_verbosity) > 0 && complaints > 0 && !VG_(clo_xml)) {
 339       Word delta  = (Word)new_SP - (Word)old_SP;
 340       complaints--;
 341       VG_(message)(Vg_UserMsg,
 342                    "Warning: client switching stacks?  "
 343                    "SP change: 0x%lx --> 0x%lx\n", old_SP, new_SP);
 344       VG_(message)(Vg_UserMsg,
 345                    "         to suppress, use: --max-stackframe=%ld "
 346                    "or greater\n",
 347                    (delta < 0 ? -delta : delta));
 348       if (complaints == 0)
 349          VG_(message)(Vg_UserMsg,
 350                       "         further instances of this message "
 351                       "will not be shown.\n");
 352    }
 353 }
 354
 355 /* The functions VG_(unknown_SP_update) and VG_(unknown_SP_update_w_ECU)
 356    get called if new_mem_stack and/or die_mem_stack are
 357    tracked by the tool, and one of the specialised cases
 358    (eg. new_mem_stack_4) isn't used in preference.
 359
 360    These functions are performance critical, so are built with macros. */
 361
 362 // preamble + check if stack has switched.
 363 #define IF_STACK_SWITCH_SET_current_stack_AND_RETURN                    \
 364    Word delta  = (Word)new_SP - (Word)old_SP;                           \
 365                                                                         \
 366    EDEBUG("current_stack  %p-%p %lu new_SP %p old_SP %p\n",             \
 367           (void *) (current_stack ? current_stack->start : 0x0),        \
 368           (void *) (current_stack ? current_stack->end : 0x0),          \
 369           current_stack ? current_stack->id : 0,                        \
 370           (void *)new_SP, (void *)old_SP);                              \
 371                                                                         \
 372    /* Check if the stack pointer is still in the same stack as before. */ \
 373    if (UNLIKELY(current_stack == NULL ||                                \
 374       new_SP < current_stack->start || new_SP > current_stack->end)) {  \
 375       Stack* new_stack = find_stack_by_addr(new_SP);                    \
 376       if (new_stack                                                     \
 377           && (current_stack == NULL || new_stack->id != current_stack->id)) { \
 378          /* The stack pointer is now in another stack.  Update the current */ \
 379          /* stack information and return without doing anything else. */ \
 380          current_stack = new_stack;                                     \
 381          EDEBUG("new current_stack  %p-%p %lu \n",                      \
 382                 (void *) current_stack->start,                          \
 383                 (void *) current_stack->end,                            \
 384                 current_stack->id);                                     \
 385          return;                                                        \
 386       } else                                                            \
 387          EDEBUG("new current_stack not found\n");                       \
 388    }
 389
 390 #define IF_BIG_DELTA_complaints_AND_RETURN                              \
 391    if (UNLIKELY(delta < -VG_(clo_max_stackframe)                        \
 392                 || VG_(clo_max_stackframe) < delta)) {                  \
 393       complaints_stack_switch(old_SP, new_SP);                          \
 394       return;                                                           \
 395    }
 396
 397 #define IF_SMALLER_STACK_die_mem_stack_AND_RETURN                       \
 398    if (delta > 0) {                                                     \
 399       VG_TRACK( die_mem_stack, old_SP,  delta );                        \
 400       return;                                                           \
 401    }
 402
 403
 404 VG_REGPARM(3)
 405 void VG_(unknown_SP_update_w_ECU)( Addr old_SP, Addr new_SP, UInt ecu ) {
 406    IF_STACK_SWITCH_SET_current_stack_AND_RETURN;
 407    IF_BIG_DELTA_complaints_AND_RETURN;
 408    IF_SMALLER_STACK_die_mem_stack_AND_RETURN;
 409    if (delta < 0) { // IF_BIGGER_STACK
 410       VG_TRACK( new_mem_stack_w_ECU, new_SP, -delta, ecu );
 411       return;
 412    }
 413    // SAME_STACK. nothing to do.
 414 }
 415
 416 VG_REGPARM(2)
 417 void VG_(unknown_SP_update)( Addr old_SP, Addr new_SP ) {
 418    IF_STACK_SWITCH_SET_current_stack_AND_RETURN;
 419    IF_BIG_DELTA_complaints_AND_RETURN;
 420    IF_SMALLER_STACK_die_mem_stack_AND_RETURN;
 421    if (delta < 0) { // IF_BIGGER_STACK
 422       VG_TRACK( new_mem_stack,      new_SP, -delta );
 423       return;
 424    }
 425    // SAME_STACK. nothing to do.
 426 }
 427
 428 /*--------------------------------------------------------------------*/
 429 /*--- end                                                          ---*/
 430 /*--------------------------------------------------------------------*/
 431