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-2010 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
