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-2011 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 */
85typedef struct _Stack {
86   UWord id;
87   Addr start;
88   Addr end;
89   struct _Stack *next;
90} Stack;
91
92static Stack *stacks;
93static 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 */
100static 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. */
105static 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. */
145static 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 */
178UWord 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 */
209void 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 */
240void 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 */
261void 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*/
275VG_REGPARM(3)
276void 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