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