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 to 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 (LIKELY(stack)) {
 276       *start = stack->start;
 277       *end = stack->end;
 278    }
 279
 280    /* SP is assumed to be in a RW segment or in the SkResvn segment of an
 281       extensible stack (normally, only the main thread has an extensible
 282       stack segment).
 283       If no such segment is found, assume we have no valid
 284       stack for SP, and set *start and *end to 0.
 285       Otherwise, possibly reduce the stack limits using the boundaries of
 286       the RW segment/SkResvn segments containing SP. */
 287    if (UNLIKELY(stackseg == NULL)) {
 288       VG_(debugLog)(2, "stacks",
 289                     "no addressable segment for SP %p\n",
 290                     (void*)SP);
 291       *start = 0;
 292       *end = 0;
 293       return;
 294    }
 295
 296    if (UNLIKELY((!stackseg->hasR || !stackseg->hasW)
 297                 && (stackseg->kind != SkResvn || stackseg->smode != SmUpper))) {
 298       VG_(debugLog)(2, "stacks",
 299                     "segment for SP %p is not RW or not a SmUpper Resvn\n",
 300                     (void*)SP);
 301       *start = 0;
 302       *end = 0;
 303       return;
 304    }
 305
 306    /* SP is in a RW segment, or in the SkResvn of an extensible stack.
 307       We can use the seg start as the stack start limit. */
 308    if (UNLIKELY(*start < stackseg->start)) {
 309       VG_(debugLog)(2, "stacks",
 310                     "segment for SP %p changed stack start limit"
 311                     " from %p to %p\n",
 312                     (void*)SP, (void*)*start, (void*)stackseg->start);
 313       *start = stackseg->start;
 314    }
 315
 316    /* Now, determine the stack end limit. If the stackseg is SkResvn,
 317       we need to get the neighbour segment (towards higher addresses).
 318       This segment must be anonymous and RW. */
 319    if (UNLIKELY(stackseg->kind == SkResvn)) {
 320       stackseg = VG_(am_next_nsegment)(stackseg, /*forward*/ True);
 321       if (!stackseg || !stackseg->hasR || !stackseg->hasW
 322           || stackseg->kind != SkAnonC) {
 323          VG_(debugLog)(2, "stacks",
 324                        "Next forward segment for SP %p Resvn segment"
 325                        " is not RW or not AnonC\n",
 326                        (void*)SP);
 327          *start = 0;
 328          *end = 0;
 329          return;
 330       }
 331    }
 332
 333    /* Limit the stack end limit, using the found segment. */
 334    if (UNLIKELY(*end > stackseg->end)) {
 335       VG_(debugLog)(2, "stacks",
 336                     "segment for SP %p changed stack end limit"
 337                     " from %p to %p\n",
 338                     (void*)SP, (void*)*end, (void*)stackseg->end);
 339       *end = stackseg->end;
 340    }
 341
 342    /* If reducing start and/or end to the SP segment gives an
 343       empty range, return 'empty' limits */
 344    if (UNLIKELY(*start > *end)) {
 345       VG_(debugLog)(2, "stacks",
 346                     "stack for SP %p start %p after end %p\n",
 347                     (void*)SP, (void*)*start, (void*)end);
 348       *start = 0;
 349       *end = 0;
 350    }
 351 }
 352
 353 /* complaints_stack_switch reports that SP has changed by more than some
 354    threshold amount (by default, 2MB).  We take this to mean that the
 355    application is switching to a new stack, for whatever reason.
 356
 357    JRS 20021001: following discussions with John Regehr, if a stack
 358    switch happens, it seems best not to mess at all with memory
 359    permissions.  Seems to work well with Netscape 4.X.  Really the
 360    only remaining difficulty is knowing exactly when a stack switch is
 361    happening. */
 362 __attribute__((noinline))
 363 static void complaints_stack_switch (Addr old_SP, Addr new_SP)
 364 {
 365    static Int complaints = 3;
 366    if (VG_(clo_verbosity) > 0 && complaints > 0 && !VG_(clo_xml)) {
 367       Word delta  = (Word)new_SP - (Word)old_SP;
 368       complaints--;
 369       VG_(message)(Vg_UserMsg,
 370                    "Warning: client switching stacks?  "
 371                    "SP change: 0x%lx --> 0x%lx\n", old_SP, new_SP);
 372       VG_(message)(Vg_UserMsg,
 373                    "         to suppress, use: --max-stackframe=%ld "
 374                    "or greater\n",
 375                    (delta < 0 ? -delta : delta));
 376       if (complaints == 0)
 377          VG_(message)(Vg_UserMsg,
 378                       "         further instances of this message "
 379                       "will not be shown.\n");
 380    }
 381 }
 382
 383 /* The functions VG_(unknown_SP_update) and VG_(unknown_SP_update_w_ECU)
 384    get called if new_mem_stack and/or die_mem_stack are
 385    tracked by the tool, and one of the specialised cases
 386    (eg. new_mem_stack_4) isn't used in preference.
 387
 388    These functions are performance critical, so are built with macros. */
 389
 390 // preamble + check if stack has switched.
 391 #define IF_STACK_SWITCH_SET_current_stack_AND_RETURN                    \
 392    Word delta  = (Word)new_SP - (Word)old_SP;                           \
 393                                                                         \
 394    EDEBUG("current_stack  %p-%p %lu new_SP %p old_SP %p\n",             \
 395           (void *) (current_stack ? current_stack->start : 0x0),        \
 396           (void *) (current_stack ? current_stack->end : 0x0),          \
 397           current_stack ? current_stack->id : 0,                        \
 398           (void *)new_SP, (void *)old_SP);                              \
 399                                                                         \
 400    /* Check if the stack pointer is still in the same stack as before. */ \
 401    if (UNLIKELY(current_stack == NULL ||                                \
 402       new_SP < current_stack->start || new_SP > current_stack->end)) {  \
 403       Stack* new_stack = find_stack_by_addr(new_SP);                    \
 404       if (new_stack                                                     \
 405           && (current_stack == NULL || new_stack->id != current_stack->id)) { \
 406          /* The stack pointer is now in another stack.  Update the current */ \
 407          /* stack information and return without doing anything else. */ \
 408          current_stack = new_stack;                                     \
 409          EDEBUG("new current_stack  %p-%p %lu \n",                      \
 410                 (void *) current_stack->start,                          \
 411                 (void *) current_stack->end,                            \
 412                 current_stack->id);                                     \
 413          return;                                                        \
 414       } else {                                                          \
 415          EDEBUG("new current_stack not found\n");                       \
 416       }                                                                 \
 417    }
 418
 419 #define IF_BIG_DELTA_complaints_AND_RETURN                              \
 420    if (UNLIKELY(delta < -VG_(clo_max_stackframe)                        \
 421                 || VG_(clo_max_stackframe) < delta)) {                  \
 422       complaints_stack_switch(old_SP, new_SP);                          \
 423       return;                                                           \
 424    }
 425
 426 #define IF_SMALLER_STACK_die_mem_stack_AND_RETURN                       \
 427    if (delta > 0) {                                                     \
 428       VG_TRACK( die_mem_stack, old_SP,  delta );                        \
 429       return;                                                           \
 430    }
 431
 432
 433 VG_REGPARM(3)
 434 void VG_(unknown_SP_update_w_ECU)( Addr old_SP, Addr new_SP, UInt ecu ) {
 435    IF_STACK_SWITCH_SET_current_stack_AND_RETURN;
 436    IF_BIG_DELTA_complaints_AND_RETURN;
 437    IF_SMALLER_STACK_die_mem_stack_AND_RETURN;
 438    if (delta < 0) { // IF_BIGGER_STACK
 439       VG_TRACK( new_mem_stack_w_ECU, new_SP, -delta, ecu );
 440       return;
 441    }
 442    // SAME_STACK. nothing to do.
 443 }
 444
 445 VG_REGPARM(2)
 446 void VG_(unknown_SP_update)( Addr old_SP, Addr new_SP ) {
 447    IF_STACK_SWITCH_SET_current_stack_AND_RETURN;
 448    IF_BIG_DELTA_complaints_AND_RETURN;
 449    IF_SMALLER_STACK_die_mem_stack_AND_RETURN;
 450    if (delta < 0) { // IF_BIGGER_STACK
 451       VG_TRACK( new_mem_stack,      new_SP, -delta );
 452       return;
 453    }
 454    // SAME_STACK. nothing to do.
 455 }
 456
 457 /*--------------------------------------------------------------------*/
 458 /*--- end                                                          ---*/
 459 /*--------------------------------------------------------------------*/
 460