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_options.h"
37 #include "pub_core_stacks.h"
38 #include "pub_core_tooliface.h"
39
40 // For expensive debugging
41 #define EDEBUG(fmt, args...) //VG_(debugLog)(2, "stacks", fmt, ## args)
42
43 /*
44 The stack
45 ~~~~~~~~~
46 The stack's segment seems to be dynamically extended downwards by
47 the kernel as the stack pointer moves down. Initially, a 1-page
48 (4k) stack is allocated. When SP moves below that for the first
49 time, presumably a page fault occurs. The kernel detects that the
50 faulting address is in the range from SP - VG_STACK_REDZONE_SZB
51 upwards to the current valid stack. It then extends the stack
52 segment downwards for enough to cover the faulting address, and
53 resumes the process (invisibly). The process is unaware of any of
54 this.
55
56 That means that Valgrind can't spot when the stack segment is being
57 extended. Fortunately, we want to precisely and continuously
58 update stack permissions around SP, so we need to spot all writes
59 to SP anyway.
60
61 The deal is: when SP is assigned a lower value, the stack is being
62 extended. Create suitably-permissioned pages to fill in any holes
63 between the old stack ptr and this one, if necessary. Then mark
64 all bytes in the area just "uncovered" by this SP change as
65 write-only.
66
67 When SP goes back up, mark the area receded over as unreadable and
68 unwritable.
69
70 Just to record the SP boundary conditions somewhere convenient:
71 SP - VG_STACK_REDZONE_SZB always points to the lowest live byte in
72 the stack. All addresses below SP - VG_STACK_REDZONE_SZB are not
73 live; those at and above it are.
74
75 We do not concern ourselves here with the VG_STACK_REDZONE_SZB
76 bias; that is handled by new_mem_stack/die_mem_stack.
77 */
78
79 /*
80 * This structure holds information about the start and end addresses of
81 * registered stacks. There's always at least one stack registered:
82 * the main process stack. It will be the first stack registered and
83 * so will have a stack id of 0. The user does not need to register
84 * this stack: Valgrind does it automatically right before it starts
85 * running the client. No other stacks are automatically registered by
86 * Valgrind, however.
87 */
88 typedef struct _Stack {
89 UWord id;
90 Addr start;
91 Addr end;
92 struct _Stack *next;
93 } Stack;
94
95 static Stack *stacks;
96 static UWord next_id; /* Next id we hand out to a newly registered stack */
97
98 /*
99 * These are the id, start and end values of the current stack. If the
100 * stack pointer falls outside the range of the current stack, we search
101 * the stacks list above for a matching stack.
102 */
103 static Stack *current_stack;
104
105 /* Find 'st' in the stacks_list and move it one step closer the the
106 front of the list, so as to make subsequent searches for it
107 cheaper. */
move_Stack_one_step_forward(Stack * st)108 static void move_Stack_one_step_forward ( Stack* st )
109 {
110 Stack *st0, *st1, *st2;
111 if (st == stacks)
112 return; /* already at head of list */
113 vg_assert(st != NULL);
114 st0 = stacks;
115 st1 = NULL;
116 st2 = NULL;
117 while (True) {
118 if (st0 == NULL || st0 == st) break;
119 st2 = st1;
120 st1 = st0;
121 st0 = st0->next;
122 }
123 vg_assert(st0 == st);
124 if (st0 != NULL && st1 != NULL && st2 != NULL) {
125 Stack* tmp;
126 /* st0 points to st, st1 to its predecessor, and st2 to st1's
127 predecessor. Swap st0 and st1, that is, move st0 one step
128 closer to the start of the list. */
129 vg_assert(st2->next == st1);
130 vg_assert(st1->next == st0);
131 tmp = st0->next;
132 st2->next = st0;
133 st0->next = st1;
134 st1->next = tmp;
135 }
136 else
137 if (st0 != NULL && st1 != NULL && st2 == NULL) {
138 /* it's second in the list. */
139 vg_assert(stacks == st1);
140 vg_assert(st1->next == st0);
141 st1->next = st0->next;
142 st0->next = st1;
143 stacks = st0;
144 }
145 }
146
147 /* Find what stack an address falls into. */
find_stack_by_addr(Addr sp)148 static Stack* find_stack_by_addr(Addr sp)
149 {
150 static UWord n_fails = 0;
151 static UWord n_searches = 0;
152 static UWord n_steps = 0;
153 Stack *i = stacks;
154 n_searches++;
155 if (0 && 0 == (n_searches % 10000))
156 VG_(printf)("(hgdev) %lu searches, %lu steps, %lu fails\n",
157 n_searches, n_steps+1, n_fails);
158 /* fast track common case */
159 if (i && sp >= i->start && sp <= i->end)
160 return i;
161 /* else search the list */
162 while (i) {
163 n_steps++;
164 if (sp >= i->start && sp <= i->end) {
165 if (1 && (n_searches & 0x3F) == 0) {
166 move_Stack_one_step_forward( i );
167 }
168 return i;
169 }
170 i = i->next;
171 }
172 n_fails++;
173 return NULL;
174 }
175
176 /*
177 * Register a new stack from start - end. This is invoked from the
178 * VALGRIND_STACK_REGISTER client request, and is also called just before
179 * we start the client running, to register the main process stack.
180 */
VG_(register_stack)181 UWord VG_(register_stack)(Addr start, Addr end)
182 {
183 Stack *i;
184
185 if (start > end) {
186 Addr t = end;
187 end = start;
188 start = t;
189 }
190
191 i = (Stack *)VG_(arena_malloc)(VG_AR_CORE, "stacks.rs.1", sizeof(Stack));
192 i->start = start;
193 i->end = end;
194 i->id = next_id++;
195 i->next = stacks;
196 stacks = i;
197
198 if (i->id == 0) {
199 current_stack = i;
200 }
201
202 VG_(debugLog)(2, "stacks", "register %p-%p as stack %lu\n",
203 (void*)start, (void*)end, i->id);
204
205 return i->id;
206 }
207
208 /*
209 * Deregister a stack. This is invoked from the VALGRIND_STACK_DEREGISTER
210 * client request.
211 */
VG_(deregister_stack)212 void VG_(deregister_stack)(UWord id)
213 {
214 Stack *i = stacks;
215 Stack *prev = NULL;
216
217 VG_(debugLog)(2, "stacks", "deregister stack %lu\n", id);
218
219 if (current_stack && current_stack->id == id) {
220 current_stack = NULL;
221 }
222
223 while(i) {
224 if (i->id == id) {
225 if(prev == NULL) {
226 stacks = i->next;
227 } else {
228 prev->next = i->next;
229 }
230 VG_(arena_free)(VG_AR_CORE, i);
231 return;
232 }
233 prev = i;
234 i = i->next;
235 }
236 }
237
238 /*
239 * Change a stack. This is invoked from the VALGRIND_STACK_CHANGE client
240 * request and from the stack growth stuff the signals module when
241 * extending the main process stack.
242 */
VG_(change_stack)243 void VG_(change_stack)(UWord id, Addr start, Addr end)
244 {
245 Stack *i = stacks;
246
247 while (i) {
248 if (i->id == id) {
249 VG_(debugLog)(2, "stacks", "change stack %lu from %p-%p to %p-%p\n",
250 id, (void*)i->start, (void*)i->end,
251 (void*)start, (void*)end);
252 i->start = start;
253 i->end = end;
254 return;
255 }
256 i = i->next;
257 }
258 }
259
260 /*
261 * Find the bounds of the stack (if any) which includes the
262 * specified stack pointer.
263 */
VG_(stack_limits)264 void VG_(stack_limits)(Addr SP, Addr *start, Addr *end )
265 {
266 Stack* stack = find_stack_by_addr(SP);
267
268 if (stack) {
269 *start = stack->start;
270 *end = stack->end;
271 }
272 }
273
274
275 /* complaints_stack_switch reports that SP has changed by more than some
276 threshold amount (by default, 2MB). We take this to mean that the
277 application is switching to a new stack, for whatever reason.
278
279 JRS 20021001: following discussions with John Regehr, if a stack
280 switch happens, it seems best not to mess at all with memory
281 permissions. Seems to work well with Netscape 4.X. Really the
282 only remaining difficulty is knowing exactly when a stack switch is
283 happening. */
284 __attribute__((noinline))
complaints_stack_switch(Addr old_SP,Addr new_SP)285 static void complaints_stack_switch (Addr old_SP, Addr new_SP)
286 {
287 static Int complaints = 3;
288 if (VG_(clo_verbosity) > 0 && complaints > 0 && !VG_(clo_xml)) {
289 Word delta = (Word)new_SP - (Word)old_SP;
290 complaints--;
291 VG_(message)(Vg_UserMsg,
292 "Warning: client switching stacks? "
293 "SP change: 0x%lx --> 0x%lx\n", old_SP, new_SP);
294 VG_(message)(Vg_UserMsg,
295 " to suppress, use: --max-stackframe=%ld "
296 "or greater\n",
297 (delta < 0 ? -delta : delta));
298 if (complaints == 0)
299 VG_(message)(Vg_UserMsg,
300 " further instances of this message "
301 "will not be shown.\n");
302 }
303 }
304
305 /* The functions VG_(unknown_SP_update) and VG_(unknown_SP_update_w_ECU)
306 get called if new_mem_stack and/or die_mem_stack are
307 tracked by the tool, and one of the specialised cases
308 (eg. new_mem_stack_4) isn't used in preference.
309
310 These functions are performance critical, so are built with macros. */
311
312 // preamble + check if stack has switched.
313 #define IF_STACK_SWITCH_SET_current_stack_AND_RETURN \
314 Word delta = (Word)new_SP - (Word)old_SP; \
315 \
316 EDEBUG("current_stack %p-%p %lu new_SP %p old_SP %p\n", \
317 (void *) (current_stack ? current_stack->start : 0x0), \
318 (void *) (current_stack ? current_stack->end : 0x0), \
319 current_stack ? current_stack->id : 0, \
320 (void *)new_SP, (void *)old_SP); \
321 \
322 /* Check if the stack pointer is still in the same stack as before. */ \
323 if (UNLIKELY(current_stack == NULL || \
324 new_SP < current_stack->start || new_SP > current_stack->end)) { \
325 Stack* new_stack = find_stack_by_addr(new_SP); \
326 if (new_stack \
327 && (current_stack == NULL || new_stack->id != current_stack->id)) { \
328 /* The stack pointer is now in another stack. Update the current */ \
329 /* stack information and return without doing anything else. */ \
330 current_stack = new_stack; \
331 EDEBUG("new current_stack %p-%p %lu \n", \
332 (void *) current_stack->start, \
333 (void *) current_stack->end, \
334 current_stack->id); \
335 return; \
336 } else \
337 EDEBUG("new current_stack not found\n"); \
338 }
339
340 #define IF_BIG_DELTA_complaints_AND_RETURN \
341 if (UNLIKELY(delta < -VG_(clo_max_stackframe) \
342 || VG_(clo_max_stackframe) < delta)) { \
343 complaints_stack_switch(old_SP, new_SP); \
344 return; \
345 }
346
347 #define IF_SMALLER_STACK_die_mem_stack_AND_RETURN \
348 if (delta > 0) { \
349 VG_TRACK( die_mem_stack, old_SP, delta ); \
350 return; \
351 }
352
353
354 VG_REGPARM(3)
VG_(unknown_SP_update_w_ECU)355 void VG_(unknown_SP_update_w_ECU)( Addr old_SP, Addr new_SP, UInt ecu ) {
356 IF_STACK_SWITCH_SET_current_stack_AND_RETURN;
357 IF_BIG_DELTA_complaints_AND_RETURN;
358 IF_SMALLER_STACK_die_mem_stack_AND_RETURN;
359 if (delta < 0) { // IF_BIGGER_STACK
360 VG_TRACK( new_mem_stack_w_ECU, new_SP, -delta, ecu );
361 return;
362 }
363 // SAME_STACK. nothing to do.
364 }
365
366 VG_REGPARM(2)
VG_(unknown_SP_update)367 void VG_(unknown_SP_update)( Addr old_SP, Addr new_SP ) {
368 IF_STACK_SWITCH_SET_current_stack_AND_RETURN;
369 IF_BIG_DELTA_complaints_AND_RETURN;
370 IF_SMALLER_STACK_die_mem_stack_AND_RETURN;
371 if (delta < 0) { // IF_BIGGER_STACK
372 VG_TRACK( new_mem_stack, new_SP, -delta );
373 return;
374 }
375 // SAME_STACK. nothing to do.
376 }
377
378 /*--------------------------------------------------------------------*/
379 /*--- end ---*/
380 /*--------------------------------------------------------------------*/
381
382