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