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 (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_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 469
