Home | History | Annotate | Download | only in coregrind
      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-2012 Julian Seward
     11       jseward (at) 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_options.h"
     37 #include "pub_core_stacks.h"
     38 #include "pub_core_tooliface.h"
     39 
     40 /*
     41    The stack
     42    ~~~~~~~~~
     43    The stack's segment seems to be dynamically extended downwards by
     44    the kernel as the stack pointer moves down.  Initially, a 1-page
     45    (4k) stack is allocated.  When SP moves below that for the first
     46    time, presumably a page fault occurs.  The kernel detects that the
     47    faulting address is in the range from SP - VG_STACK_REDZONE_SZB
     48    upwards to the current valid stack.  It then extends the stack
     49    segment downwards for enough to cover the faulting address, and
     50    resumes the process (invisibly).  The process is unaware of any of
     51    this.
     52 
     53    That means that Valgrind can't spot when the stack segment is being
     54    extended.  Fortunately, we want to precisely and continuously
     55    update stack permissions around SP, so we need to spot all writes
     56    to SP anyway.
     57 
     58    The deal is: when SP is assigned a lower value, the stack is being
     59    extended.  Create suitably-permissioned pages to fill in any holes
     60    between the old stack ptr and this one, if necessary.  Then mark
     61    all bytes in the area just "uncovered" by this SP change as
     62    write-only.
     63 
     64    When SP goes back up, mark the area receded over as unreadable and
     65    unwritable.
     66 
     67    Just to record the SP boundary conditions somewhere convenient:
     68    SP - VG_STACK_REDZONE_SZB always points to the lowest live byte in
     69    the stack.  All addresses below SP - VG_STACK_REDZONE_SZB are not
     70    live; those at and above it are.
     71 
     72    We do not concern ourselves here with the VG_STACK_REDZONE_SZB
     73    bias; that is handled by new_mem_stack/die_mem_stack.
     74 */
     75 
     76 /*
     77  * This structure holds information about the start and end addresses of
     78  * registered stacks.  There's always at least one stack registered:
     79  * the main process stack.  It will be the first stack registered and
     80  * so will have a stack id of 0.  The user does not need to register
     81  * this stack: Valgrind does it automatically right before it starts
     82  * running the client.  No other stacks are automatically registered by
     83  * Valgrind, however.
     84  */
     85 typedef struct _Stack {
     86    UWord id;
     87    Addr start;
     88    Addr end;
     89    struct _Stack *next;
     90 } Stack;
     91 
     92 static Stack *stacks;
     93 static UWord next_id;  /* Next id we hand out to a newly registered stack */
     94 
     95 /*
     96  * These are the id, start and end values of the current stack.  If the
     97  * stack pointer falls outside the range of the current stack, we search
     98  * the stacks list above for a matching stack.
     99  */
    100 static Stack *current_stack;
    101 
    102 /* Find 'st' in the stacks_list and move it one step closer the the
    103    front of the list, so as to make subsequent searches for it
    104    cheaper. */
    105 static void move_Stack_one_step_forward ( Stack* st )
    106 {
    107    Stack *st0, *st1, *st2;
    108    if (st == stacks)
    109       return; /* already at head of list */
    110    vg_assert(st != NULL);
    111    st0 = stacks;
    112    st1 = NULL;
    113    st2 = NULL;
    114    while (True) {
    115       if (st0 == NULL || st0 == st) break;
    116       st2 = st1;
    117       st1 = st0;
    118       st0 = st0->next;
    119    }
    120    vg_assert(st0 == st);
    121    if (st0 != NULL && st1 != NULL && st2 != NULL) {
    122       Stack* tmp;
    123       /* st0 points to st, st1 to its predecessor, and st2 to st1's
    124          predecessor.  Swap st0 and st1, that is, move st0 one step
    125          closer to the start of the list. */
    126       vg_assert(st2->next == st1);
    127       vg_assert(st1->next == st0);
    128       tmp = st0->next;
    129       st2->next = st0;
    130       st0->next = st1;
    131       st1->next = tmp;
    132    }
    133    else
    134    if (st0 != NULL && st1 != NULL && st2 == NULL) {
    135       /* it's second in the list. */
    136       vg_assert(stacks == st1);
    137       vg_assert(st1->next == st0);
    138       st1->next = st0->next;
    139       st0->next = st1;
    140       stacks = st0;
    141    }
    142 }
    143 
    144 /* Find what stack an address falls into. */
    145 static Stack* find_stack_by_addr(Addr sp)
    146 {
    147    static UWord n_fails = 0;
    148    static UWord n_searches = 0;
    149    static UWord n_steps = 0;
    150    Stack *i = stacks;
    151    n_searches++;
    152    if (0 && 0 == (n_searches % 10000))
    153       VG_(printf)("(hgdev) %lu searches, %lu steps, %lu fails\n",
    154                   n_searches, n_steps+1, n_fails);
    155    /* fast track common case */
    156    if (i && sp >= i->start && sp <= i->end)
    157       return i;
    158    /* else search the list */
    159    while (i) {
    160       n_steps++;
    161       if (sp >= i->start && sp <= i->end) {
    162          if (1 && (n_searches & 0x3F) == 0) {
    163             move_Stack_one_step_forward( i );
    164          }
    165          return i;
    166       }
    167       i = i->next;
    168    }
    169    n_fails++;
    170    return NULL;
    171 }
    172 
    173 /*
    174  * Register a new stack from start - end.  This is invoked from the
    175  * VALGRIND_STACK_REGISTER client request, and is also called just before
    176  * we start the client running, to register the main process stack.
    177  */
    178 UWord VG_(register_stack)(Addr start, Addr end)
    179 {
    180    Stack *i;
    181 
    182    if (start > end) {
    183       Addr t = end;
    184       end = start;
    185       start = t;
    186    }
    187 
    188    i = (Stack *)VG_(arena_malloc)(VG_AR_CORE, "stacks.rs.1", sizeof(Stack));
    189    i->start = start;
    190    i->end = end;
    191    i->id = next_id++;
    192    i->next = stacks;
    193    stacks = i;
    194 
    195    if (i->id == 0) {
    196       current_stack = i;
    197    }
    198 
    199    VG_(debugLog)(2, "stacks", "register %p-%p as stack %lu\n",
    200                     (void*)start, (void*)end, i->id);
    201 
    202    return i->id;
    203 }
    204 
    205 /*
    206  * Deregister a stack.  This is invoked from the VALGRIND_STACK_DEREGISTER
    207  * client request.
    208  */
    209 void VG_(deregister_stack)(UWord id)
    210 {
    211    Stack *i = stacks;
    212    Stack *prev = NULL;
    213 
    214    VG_(debugLog)(2, "stacks", "deregister stack %lu\n", id);
    215 
    216    if (current_stack && current_stack->id == id) {
    217       current_stack = NULL;
    218    }
    219 
    220    while(i) {
    221       if (i->id == id) {
    222          if(prev == NULL) {
    223             stacks = i->next;
    224          } else {
    225             prev->next = i->next;
    226          }
    227          VG_(arena_free)(VG_AR_CORE, i);
    228          return;
    229       }
    230       prev = i;
    231       i = i->next;
    232    }
    233 }
    234 
    235 /*
    236  * Change a stack.  This is invoked from the VALGRIND_STACK_CHANGE client
    237  * request and from the stack growth stuff the signals module when
    238  * extending the main process stack.
    239  */
    240 void VG_(change_stack)(UWord id, Addr start, Addr end)
    241 {
    242    Stack *i = stacks;
    243 
    244    while (i) {
    245       if (i->id == id) {
    246          VG_(debugLog)(2, "stacks", "change stack %lu from %p-%p to %p-%p\n",
    247                        id, (void*)i->start, (void*)i->end,
    248                            (void*)start,    (void*)end);
    249          i->start = start;
    250          i->end = end;
    251          return;
    252       }
    253       i = i->next;
    254    }
    255 }
    256 
    257 /*
    258  * Find the bounds of the stack (if any) which includes the
    259  * specified stack pointer.
    260  */
    261 void VG_(stack_limits)(Addr SP, Addr *start, Addr *end )
    262 {
    263    Stack* stack = find_stack_by_addr(SP);
    264 
    265    if (stack) {
    266       *start = stack->start;
    267       *end = stack->end;
    268    }
    269 }
    270 
    271 /* This function gets called if new_mem_stack and/or die_mem_stack are
    272    tracked by the tool, and one of the specialised cases
    273    (eg. new_mem_stack_4) isn't used in preference.
    274 */
    275 VG_REGPARM(3)
    276 void VG_(unknown_SP_update)( Addr old_SP, Addr new_SP, UInt ecu )
    277 {
    278    static Int moans = 3;
    279    Word delta  = (Word)new_SP - (Word)old_SP;
    280 
    281    /* Check if the stack pointer is still in the same stack as before. */
    282    if (current_stack == NULL ||
    283        new_SP < current_stack->start || new_SP > current_stack->end) {
    284       Stack* new_stack = find_stack_by_addr(new_SP);
    285       if (new_stack
    286           && (current_stack == NULL || new_stack->id != current_stack->id)) {
    287          /* The stack pointer is now in another stack.  Update the current
    288             stack information and return without doing anything else. */
    289          current_stack = new_stack;
    290          return;
    291       }
    292    }
    293 
    294    if (delta < -VG_(clo_max_stackframe) || VG_(clo_max_stackframe) < delta) {
    295       /* SP has changed by more than some threshold amount (by
    296          default, 2MB).  We take this to mean that the application is
    297          switching to a new stack, for whatever reason.
    298 
    299          JRS 20021001: following discussions with John Regehr, if a stack
    300          switch happens, it seems best not to mess at all with memory
    301          permissions.  Seems to work well with Netscape 4.X.  Really the
    302          only remaining difficulty is knowing exactly when a stack switch is
    303          happening. */
    304       if (VG_(clo_verbosity) > 0 && moans > 0 && !VG_(clo_xml)) {
    305          moans--;
    306          VG_(message)(Vg_UserMsg,
    307             "Warning: client switching stacks?  "
    308             "SP change: 0x%lx --> 0x%lx\n", old_SP, new_SP);
    309          VG_(message)(Vg_UserMsg,
    310             "         to suppress, use: --max-stackframe=%ld or greater\n",
    311             (delta < 0 ? -delta : delta));
    312          if (moans == 0)
    313             VG_(message)(Vg_UserMsg,
    314                 "         further instances of this message "
    315                 "will not be shown.\n");
    316       }
    317    } else if (delta < 0) {
    318       VG_TRACK( new_mem_stack_w_ECU, new_SP, -delta, ecu );
    319       VG_TRACK( new_mem_stack,       new_SP, -delta );
    320 
    321    } else if (delta > 0) {
    322       VG_TRACK( die_mem_stack, old_SP,  delta );
    323    }
    324 }
    325 
    326 /*--------------------------------------------------------------------*/
    327 /*--- end                                                          ---*/
    328 /*--------------------------------------------------------------------*/
    329 
    330