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