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-2012 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 /*
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. */
move_Stack_one_step_forward(Stack * st)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. */
find_stack_by_addr(Addr sp)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 */
VG_(register_stack)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 */
VG_(deregister_stack)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 */
VG_(change_stack)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 */
VG_(stack_limits)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)
VG_(unknown_SP_update)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