Re: [rfc] Eliminate frame_id_inner comparisons

[Daniel Jacobowitz <drow at false dot org>]

On Thu, Jun 19, 2008 at 10:34:05PM +0200, Ulrich Weigand wrote:
> Hello,
> 
> the frame_id_inner function makes assumptions how to use the
> values of the stack pointer to try to figure out whether one
> frame is inner-to another one.  These assumptions may not in
> fact be valid in certain situations today (e.g. when switching
> stacks like with sigaltstack), and they will become invalid
> with per-frame architecture support.

I had a concern about this patch, which I couldn't explain well in
person - let me see if I can do better with examples.

> - dummy_frame_push checks for stale dummy frame IDs.  As suggested
>   in a comment by Andrew, this can simply do a frame_find_by_id check.

frame_find_by_id is a loop calling get_prev_frame until we run out of
stack.  By default there is no limit on the number of frames GDB will
unwind.  So if the stack is very deep, or if the unwinder is confused
and the resulting stack is essentially infinite (a common failure
mode), frame_find_by_id may take a very long time.  frame_find_by_id
is constant time (though, as you've noted, sometimes wrong).

On the other hand, if the user has set a backtrace depth limit, then
frame_find_by_id may fail if a function with a deep stack is called.
We'll discard the dummy frame when it's still valid and get an extra
sigtrap.  This behavior should be straightforward to write a test case
for: set the backtrace limit to ten, call a function which recurses
twenty times and then hits a breakpoint, call another function, raise
the backtrace limit and see if we've lost the outer dummy frame.

> - return_command uses frame_id_inner as a safety check while popping
>   frames one by one.  Again as already noted by Andrew, this should
>   really be just popping to the target frame in one go.
> 
> - handle_inferior_event has a call to frame_id_inner that is
>   actually dead:
> 
>     struct frame_info *frame = get_current_frame ();
>     struct frame_id current_frame = get_frame_id (frame);
>     if (!(frame_id_inner (get_frame_arch (frame), current_frame,
>                          step_frame_id)))
>       step_frame_id = current_frame;
> 
>   as step_frame_id was already unconditionally set to
>     get_frame_id (get_current_frame ())
>   immediately before that check.

These both look fine.  IIRC the inlining patch also removes one or
both of these, I know I've run into them before.

> - frame_find_by_id used frame_id_inner as a sanity check to detect
>   infinite cycles in the frame chain.  This is really redundant as
>   frame_find_by_id calls get_prev_frame which already has a similar
>   check.

No, it's not checking for cycles.

-      if (frame_id_inner (get_frame_arch (frame), id, this))
-	/* Gone to far.  */
-	return NULL;
-      /* Either we're not yet gone far enough out along the frame
-         chain (inner(this,id)), or we're comparing frameless functions
-         (same .base, different .func, no test available).  Struggle
-         on until we've definitly gone to far.  */

This is a limit on the number of cycles frame_find_by_id will travel
if we're in a new location or if we have a confused unwinder.
Suppose we record a varobj at frame sp==0x1000 (stack grows down).
We continue.  Next time we hit a breakpoint sp==0xfc0.  The frontend
requests a varobj update.  We unwind, find the next frame is
sp==0x1200.  The old frame is gone; we stop.  Good thing, since if
we'd kept backtracing we'd find the stack went all the way up to
0xff00... it'd take seconds or minutes to get up there.

> - get_prev_frame_1 also used frame_id_inner as sanity check to 
>   detect cycles.  I've replaced this by using Floyd's algorithm
>   to find cycles, without having to compare frame IDs.  (This 
>   keeps a backtrac pass linear in the number of stack frames;
>   a simple comparison loop would make in quadratic.  Not sure
>   whether this actually matters in practice ...)

I think the part using frame_id_inner is another corrupt stack check,
and the chances of it forming an exact cycle are slim to none.  But
it's clear that there's a problem with the multi-stack or multi-arch
cases that you're fixing.

Is there some other way we can avoid unnecessary backtracing?  Maybe a
predicate which determines whether two consecutive frames are
reasonably on the same stack - in the presence of sigaltstack that
could be quite fragile though.

-- 
Daniel Jacobowitz
CodeSourcery