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 */ 89typedef 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 96static Stack *stacks; 97static 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 */ 104static Stack *current_stack; 105 106/* Find 'st' in the stacks_list and move it one step closer the the 107 front of the list, so as to make subsequent searches for it 108 cheaper. */ 109static 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. */ 149static 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 */ 182UWord 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 */ 216void 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 */ 247void 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 */ 270void 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)) 363static 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#define IF_BIG_DELTA_complaints_AND_RETURN \ 419 if (UNLIKELY(delta < -VG_(clo_max_stackframe) \ 420 || VG_(clo_max_stackframe) < delta)) { \ 421 complaints_stack_switch(old_SP, new_SP); \ 422 return; \ 423 } 424 425#define IF_SMALLER_STACK_die_mem_stack_AND_RETURN \ 426 if (delta > 0) { \ 427 VG_TRACK( die_mem_stack, old_SP, delta ); \ 428 return; \ 429 } 430 431 432VG_REGPARM(3) 433void VG_(unknown_SP_update_w_ECU)( Addr old_SP, Addr new_SP, UInt ecu ) { 434 IF_STACK_SWITCH_SET_current_stack_AND_RETURN; 435 IF_BIG_DELTA_complaints_AND_RETURN; 436 IF_SMALLER_STACK_die_mem_stack_AND_RETURN; 437 if (delta < 0) { // IF_BIGGER_STACK 438 VG_TRACK( new_mem_stack_w_ECU, new_SP, -delta, ecu ); 439 return; 440 } 441 // SAME_STACK. nothing to do. 442} 443 444VG_REGPARM(2) 445void VG_(unknown_SP_update)( Addr old_SP, Addr new_SP ) { 446 IF_STACK_SWITCH_SET_current_stack_AND_RETURN; 447 IF_BIG_DELTA_complaints_AND_RETURN; 448 IF_SMALLER_STACK_die_mem_stack_AND_RETURN; 449 if (delta < 0) { // IF_BIGGER_STACK 450 VG_TRACK( new_mem_stack, new_SP, -delta ); 451 return; 452 } 453 // SAME_STACK. nothing to do. 454} 455 456/*--------------------------------------------------------------------*/ 457/*--- end ---*/ 458/*--------------------------------------------------------------------*/ 459 460