njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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 | |
sewardj | ec062e8 | 2011-10-23 07:32:08 +0000 | [diff] [blame] | 10 | Copyright (C) 2000-2011 Julian Seward |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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" |
tom | de3cf13 | 2005-11-10 14:24:08 +0000 | [diff] [blame] | 32 | #include "pub_core_debuglog.h" |
sewardj | 25b079c | 2008-03-12 00:14:01 +0000 | [diff] [blame] | 33 | #include "pub_core_libcassert.h" |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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 | */ |
tom | de3cf13 | 2005-11-10 14:24:08 +0000 | [diff] [blame] | 100 | static Stack *current_stack; |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 101 | |
sewardj | 25b079c | 2008-03-12 00:14:01 +0000 | [diff] [blame] | 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 | |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 144 | /* Find what stack an address falls into. */ |
njn | 4e72d20 | 2005-08-14 04:12:40 +0000 | [diff] [blame] | 145 | static Stack* find_stack_by_addr(Addr sp) |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 146 | { |
sewardj | 25b079c | 2008-03-12 00:14:01 +0000 | [diff] [blame] | 147 | static UWord n_fails = 0; |
| 148 | static UWord n_searches = 0; |
| 149 | static UWord n_steps = 0; |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 150 | Stack *i = stacks; |
sewardj | 25b079c | 2008-03-12 00:14:01 +0000 | [diff] [blame] | 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 */ |
njn | 4e72d20 | 2005-08-14 04:12:40 +0000 | [diff] [blame] | 159 | while (i) { |
sewardj | 25b079c | 2008-03-12 00:14:01 +0000 | [diff] [blame] | 160 | n_steps++; |
njn | 4e72d20 | 2005-08-14 04:12:40 +0000 | [diff] [blame] | 161 | if (sp >= i->start && sp <= i->end) { |
sewardj | 25b079c | 2008-03-12 00:14:01 +0000 | [diff] [blame] | 162 | if (1 && (n_searches & 0x3F) == 0) { |
| 163 | move_Stack_one_step_forward( i ); |
| 164 | } |
njn | 4e72d20 | 2005-08-14 04:12:40 +0000 | [diff] [blame] | 165 | return i; |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 166 | } |
| 167 | i = i->next; |
| 168 | } |
sewardj | 25b079c | 2008-03-12 00:14:01 +0000 | [diff] [blame] | 169 | n_fails++; |
njn | 4e72d20 | 2005-08-14 04:12:40 +0000 | [diff] [blame] | 170 | return NULL; |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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; |
sewardj | 45f4e7c | 2005-09-27 19:20:21 +0000 | [diff] [blame] | 181 | |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 182 | if (start > end) { |
| 183 | Addr t = end; |
| 184 | end = start; |
| 185 | start = t; |
| 186 | } |
| 187 | |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 188 | i = (Stack *)VG_(arena_malloc)(VG_AR_CORE, "stacks.rs.1", sizeof(Stack)); |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 189 | i->start = start; |
| 190 | i->end = end; |
| 191 | i->id = next_id++; |
| 192 | i->next = stacks; |
| 193 | stacks = i; |
| 194 | |
njn | 4e72d20 | 2005-08-14 04:12:40 +0000 | [diff] [blame] | 195 | if (i->id == 0) { |
tom | de3cf13 | 2005-11-10 14:24:08 +0000 | [diff] [blame] | 196 | current_stack = i; |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 197 | } |
| 198 | |
njn | 4818d73 | 2005-11-10 15:03:26 +0000 | [diff] [blame] | 199 | VG_(debugLog)(2, "stacks", "register %p-%p as stack %lu\n", |
| 200 | (void*)start, (void*)end, i->id); |
tom | de3cf13 | 2005-11-10 14:24:08 +0000 | [diff] [blame] | 201 | |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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 | |
njn | 4818d73 | 2005-11-10 15:03:26 +0000 | [diff] [blame] | 214 | VG_(debugLog)(2, "stacks", "deregister stack %lu\n", id); |
tom | de3cf13 | 2005-11-10 14:24:08 +0000 | [diff] [blame] | 215 | |
sewardj | 0edccdd | 2007-11-17 02:05:57 +0000 | [diff] [blame] | 216 | if (current_stack && current_stack->id == id) { |
tom | de3cf13 | 2005-11-10 14:24:08 +0000 | [diff] [blame] | 217 | current_stack = NULL; |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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 | |
njn | 4e72d20 | 2005-08-14 04:12:40 +0000 | [diff] [blame] | 244 | while (i) { |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 245 | if (i->id == id) { |
njn | 4818d73 | 2005-11-10 15:03:26 +0000 | [diff] [blame] | 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); |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 249 | i->start = start; |
| 250 | i->end = end; |
| 251 | return; |
| 252 | } |
| 253 | i = i->next; |
| 254 | } |
| 255 | } |
| 256 | |
tom | 690c3c8 | 2008-02-08 15:17:07 +0000 | [diff] [blame] | 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 | |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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 | */ |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 275 | VG_REGPARM(3) |
| 276 | void VG_(unknown_SP_update)( Addr old_SP, Addr new_SP, UInt ecu ) |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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. */ |
tom | de3cf13 | 2005-11-10 14:24:08 +0000 | [diff] [blame] | 282 | if (current_stack == NULL || |
| 283 | new_SP < current_stack->start || new_SP > current_stack->end) { |
njn | 4e72d20 | 2005-08-14 04:12:40 +0000 | [diff] [blame] | 284 | Stack* new_stack = find_stack_by_addr(new_SP); |
sewardj | 0edccdd | 2007-11-17 02:05:57 +0000 | [diff] [blame] | 285 | if (new_stack |
| 286 | && (current_stack == NULL || new_stack->id != current_stack->id)) { |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 287 | /* The stack pointer is now in another stack. Update the current |
| 288 | stack information and return without doing anything else. */ |
tom | de3cf13 | 2005-11-10 14:24:08 +0000 | [diff] [blame] | 289 | current_stack = new_stack; |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 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. */ |
sewardj | 352122c | 2008-05-06 21:01:19 +0000 | [diff] [blame] | 304 | if (VG_(clo_verbosity) > 0 && moans > 0 && !VG_(clo_xml)) { |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 305 | moans--; |
| 306 | VG_(message)(Vg_UserMsg, |
| 307 | "Warning: client switching stacks? " |
sewardj | 738856f | 2009-07-15 14:48:32 +0000 | [diff] [blame] | 308 | "SP change: 0x%lx --> 0x%lx\n", old_SP, new_SP); |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 309 | VG_(message)(Vg_UserMsg, |
sewardj | 738856f | 2009-07-15 14:48:32 +0000 | [diff] [blame] | 310 | " to suppress, use: --max-stackframe=%ld or greater\n", |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 311 | (delta < 0 ? -delta : delta)); |
| 312 | if (moans == 0) |
| 313 | VG_(message)(Vg_UserMsg, |
| 314 | " further instances of this message " |
sewardj | 738856f | 2009-07-15 14:48:32 +0000 | [diff] [blame] | 315 | "will not be shown.\n"); |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 316 | } |
| 317 | } else if (delta < 0) { |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 318 | VG_TRACK( new_mem_stack_w_ECU, new_SP, -delta, ecu ); |
| 319 | VG_TRACK( new_mem_stack, new_SP, -delta ); |
njn | 945ed2e | 2005-06-24 03:28:30 +0000 | [diff] [blame] | 320 | |
| 321 | } else if (delta > 0) { |
| 322 | VG_TRACK( die_mem_stack, old_SP, delta ); |
| 323 | } |
| 324 | } |
| 325 | |
| 326 | /*--------------------------------------------------------------------*/ |
| 327 | /*--- end ---*/ |
| 328 | /*--------------------------------------------------------------------*/ |
| 329 | |