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@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. */
move_Stack_one_step_forward(Stack * st)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. */
find_stack_by_addr(Addr sp)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 */
VG_(register_stack)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 */
VG_(deregister_stack)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 */
VG_(change_stack)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 */
VG_(stack_limits)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))
complaints_stack_switch(Addr old_SP,Addr new_SP)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)
VG_(unknown_SP_update_w_ECU)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)
VG_(unknown_SP_update)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