Mirror of the gdb-patches mailing list
 help / color / mirror / Atom feed
* [rfc] Eliminate frame_id_inner comparisons
@ 2008-06-20  4:42 Ulrich Weigand
  2008-06-25 13:32 ` Joel Brobecker
  2008-06-25 14:15 ` Daniel Jacobowitz
  0 siblings, 2 replies; 9+ messages in thread
From: Ulrich Weigand @ 2008-06-20  4:42 UTC (permalink / raw)
  To: gdb-patches

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.

This patch eliminates the need for performing this type of
frame ID comparison.  These were used for:

- 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.

- 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.

- 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.

- 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 ...)

What do you think?  Is that a reasonable approach?

Tested on i386-linux, s390-linux and s390x-linux with no regressions.

Bye,
Ulrich


ChangeLog:

	* frame.h (struct frame_id): Update comments.
	(frame_id_inner): Remove prototype.
	(enum unwind_stop_reason): Remove UNWIND_INNER_ID and
	UNWIND_SAME_ID, add UNWIND_CYCLE.
	* frame.c (struct frame_info): New member "cycle".
	(frame_id_inner): Delete.
	(frame_find_by_id): Remove frame_id_inner check.
	(create_sentinel_frame): Initialize frame->cycle.
	(get_prev_frame_1): Remove frame_id_inner check.  Check for
	cycles in the frame chain using Floyd's algorithm.
	Initialize prev_frame->cycle.
	(frame_stop_reason_string): Handle UNWIND_CYCLE instead of
	UNWIND_INNER_ID and UNWIND_SAME_ID.

	* dummy-frame.c (dummy_frame_push): Use frame_find_by_id to
	detect stale dummy frames.
	* stack.c (return_command): Directly pop the selected frame.
	* infrun.c (handle_inferior_event): Remove dead code.
	* i386-tdep.c (i386_push_dummy_call): Update comment.


diff -urNp gdb-orig/gdb/dummy-frame.c gdb-head/gdb/dummy-frame.c
--- gdb-orig/gdb/dummy-frame.c	2008-05-09 19:20:22.000000000 +0200
+++ gdb-head/gdb/dummy-frame.c	2008-06-19 21:36:37.000000000 +0200
@@ -87,7 +87,6 @@ void
 dummy_frame_push (struct regcache *caller_regcache,
 		  const struct frame_id *dummy_id)
 {
-  struct gdbarch *gdbarch = get_regcache_arch (caller_regcache);
   struct dummy_frame *dummy_frame;
 
   /* Check to see if there are stale dummy frames, perhaps left over
@@ -95,8 +94,7 @@ dummy_frame_push (struct regcache *calle
      the debugger.  */
   dummy_frame = dummy_frame_stack;
   while (dummy_frame)
-    /* FIXME: cagney/2004-08-02: Should just test IDs.  */
-    if (frame_id_inner (gdbarch, dummy_frame->id, (*dummy_id)))
+    if (frame_find_by_id (dummy_frame->id) == NULL)
       /* Stale -- destroy!  */
       {
 	dummy_frame_stack = dummy_frame->next;
diff -urNp gdb-orig/gdb/frame.c gdb-head/gdb/frame.c
--- gdb-orig/gdb/frame.c	2008-05-26 17:21:58.000000000 +0200
+++ gdb-head/gdb/frame.c	2008-06-19 21:43:35.000000000 +0200
@@ -106,6 +106,12 @@ struct frame_info
   int prev_p;
   struct frame_info *prev; /* up, outer, older */
 
+  /* Cached pointer to frame of level LEVEL/2, where LEVEL is the
+     level of this frame.  We use this to implement Floyd's cycle
+     detection algorithm (the frame chain has a cycle iff for some I
+     the frame of level I has the same ID as the frame of level 2*I).  */
+  struct frame_info *cycle;
+
   /* The reason why we could not set PREV, or UNWIND_NO_REASON if we
      could.  Only valid when PREV_P is set.  */
   enum unwind_stop_reason stop_reason;
@@ -367,30 +373,6 @@ frame_id_eq (struct frame_id l, struct f
   return eq;
 }
 
-int
-frame_id_inner (struct gdbarch *gdbarch, struct frame_id l, struct frame_id r)
-{
-  int inner;
-  if (!l.stack_addr_p || !r.stack_addr_p)
-    /* Like NaN, any operation involving an invalid ID always fails.  */
-    inner = 0;
-  else
-    /* Only return non-zero when strictly inner than.  Note that, per
-       comment in "frame.h", there is some fuzz here.  Frameless
-       functions are not strictly inner than (same .stack but
-       different .code and/or .special address).  */
-    inner = gdbarch_inner_than (gdbarch, l.stack_addr, r.stack_addr);
-  if (frame_debug)
-    {
-      fprintf_unfiltered (gdb_stdlog, "{ frame_id_inner (l=");
-      fprint_frame_id (gdb_stdlog, l);
-      fprintf_unfiltered (gdb_stdlog, ",r=");
-      fprint_frame_id (gdb_stdlog, r);
-      fprintf_unfiltered (gdb_stdlog, ") -> %d }\n", inner);
-    }
-  return inner;
-}
-
 struct frame_info *
 frame_find_by_id (struct frame_id id)
 {
@@ -409,13 +391,6 @@ frame_find_by_id (struct frame_id id)
       if (frame_id_eq (id, this))
 	/* An exact match.  */
 	return frame;
-      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.  */
     }
   return NULL;
 }
@@ -868,6 +843,7 @@ create_sentinel_frame (struct regcache *
   /* Link this frame back to itself.  The frame is self referential
      (the unwound PC is the same as the pc), so make it so.  */
   frame->next = frame;
+  frame->cycle = frame;
   /* Make the sentinel frame's ID valid, but invalid.  That way all
      comparisons with it should fail.  */
   frame->this_id.p = 1;
@@ -1202,38 +1178,25 @@ get_prev_frame_1 (struct frame_info *thi
       return NULL;
     }
 
-  /* Check that this frame's ID isn't inner to (younger, below, next)
-     the next frame.  This happens when a frame unwind goes backwards.
-     Exclude signal trampolines (due to sigaltstack the frame ID can
-     go backwards) and sentinel frames (the test is meaningless).  */
-  if (this_frame->next->level >= 0
-      && this_frame->next->unwind->type != SIGTRAMP_FRAME
-      && frame_id_inner (get_frame_arch (this_frame), this_id,
-			 get_frame_id (this_frame->next)))
-    {
-      if (frame_debug)
-	{
-	  fprintf_unfiltered (gdb_stdlog, "-> ");
-	  fprint_frame (gdb_stdlog, NULL);
-	  fprintf_unfiltered (gdb_stdlog, " // this frame ID is inner }\n");
-	}
-      this_frame->stop_reason = UNWIND_INNER_ID;
-      return NULL;
-    }
-
-  /* Check that this and the next frame are not identical.  If they
-     are, there is most likely a stack cycle.  As with the inner-than
-     test above, avoid comparing the inner-most and sentinel frames.  */
+  /* Check for cycles in the frame chain.  These are an indication
+     of either unwinder failure or stack corruption; we want to detect
+     them to avoid infinite loops in backtrace or frame_find_by_id.
+
+     We detect short cycles of length 1 or 2 (hopefully the most
+     frequent instances) by direct comparison.  To detect longer
+     cycles in linear time, we use Floyd's algorithm.  */
   if (this_frame->level > 0
-      && frame_id_eq (this_id, get_frame_id (this_frame->next)))
+      && (frame_id_eq (this_id, get_frame_id (this_frame->next))
+	  || frame_id_eq (this_id, get_frame_id (this_frame->next->next))
+	  || frame_id_eq (this_id, get_frame_id (this_frame->cycle))))
     {
       if (frame_debug)
 	{
 	  fprintf_unfiltered (gdb_stdlog, "-> ");
 	  fprint_frame (gdb_stdlog, NULL);
-	  fprintf_unfiltered (gdb_stdlog, " // this frame has same ID }\n");
+	  fprintf_unfiltered (gdb_stdlog, " // cycle detected }\n");
 	}
-      this_frame->stop_reason = UNWIND_SAME_ID;
+      this_frame->stop_reason = UNWIND_CYCLE;
       return NULL;
     }
 
@@ -1319,6 +1282,12 @@ get_prev_frame_1 (struct frame_info *thi
   this_frame->prev = prev_frame;
   prev_frame->next = this_frame;
 
+  /* Set the cached link to the LEVEL/2 frame.  */
+  if (prev_frame->level & 1)
+    prev_frame->cycle = this_frame->cycle;
+  else
+    prev_frame->cycle = this_frame->cycle->prev;
+
   if (frame_debug)
     {
       fprintf_unfiltered (gdb_stdlog, "-> ");
@@ -1778,11 +1747,8 @@ frame_stop_reason_string (enum unwind_st
     case UNWIND_NULL_ID:
       return _("unwinder did not report frame ID");
 
-    case UNWIND_INNER_ID:
-      return _("previous frame inner to this frame (corrupt stack?)");
-
-    case UNWIND_SAME_ID:
-      return _("previous frame identical to this frame (corrupt stack?)");
+    case UNWIND_CYCLE:
+      return _("same frame ID as some inner frame (corrupt stack?)");
 
     case UNWIND_NO_SAVED_PC:
       return _("frame did not save the PC");
diff -urNp gdb-orig/gdb/frame.h gdb-head/gdb/frame.h
--- gdb-orig/gdb/frame.h	2008-05-26 17:21:58.000000000 +0200
+++ gdb-head/gdb/frame.h	2008-06-19 21:36:37.000000000 +0200
@@ -110,8 +110,7 @@ struct frame_id
      lifetime of the frame.  This is used for architectures that may have
      frames that do not change the stack but are still distinct and have 
      some form of distinct identifier (e.g. the ia64 which uses a 2nd 
-     stack for registers).  This field is treated as unordered - i.e. will
-     not be used in frame ordering comparisons such as frame_id_inner().
+     stack for registers).
 
      This field is valid only if special_addr_p is true.  Otherwise, this
      frame is considered to have a wildcard special address, i.e. one that
@@ -126,19 +125,10 @@ struct frame_id
 
 /* Methods for constructing and comparing Frame IDs.
 
-   NOTE: Given stackless functions A and B, where A calls B (and hence
-   B is inner-to A).  The relationships: !eq(A,B); !eq(B,A);
-   !inner(A,B); !inner(B,A); all hold.
-
-   This is because, while B is inner-to A, B is not strictly inner-to A.  
-   Being stackless, they have an identical .stack_addr value, and differ 
-   only by their unordered .code_addr and/or .special_addr values.
-
-   Because frame_id_inner is only used as a safety net (e.g.,
-   detect a corrupt stack) the lack of strictness is not a problem.
-   Code needing to determine an exact relationship between two frames
-   must instead use frame_id_eq and frame_id_unwind.  For instance,
-   in the above, to determine that A stepped-into B, the equation
+   We only support comparing frame IDs for identity, because we cannot
+   in general rely on stack addresses to be linearly ordered.  The inner-to
+   relationship can be discovered by unwinding.  For example, to discover
+   that a function A has just stepped into another function B, the equation
    "A.id != B.id && A.id == id_unwind (B)" can be used.  */
 
 /* For convenience.  All fields are zero.  */
@@ -176,12 +166,6 @@ extern int frame_id_p (struct frame_id l
    either L or R have a zero .func, then the same frame base.  */
 extern int frame_id_eq (struct frame_id l, struct frame_id r);
 
-/* Returns non-zero when L is strictly inner-than R (they have
-   different frame .bases).  Neither L, nor R can be `null'.  See note
-   above about frameless functions.  */
-extern int frame_id_inner (struct gdbarch *gdbarch, struct frame_id l,
-			   struct frame_id r);
-
 /* Write the internal representation of a frame ID on the specified
    stream.  */
 extern void fprint_frame_id (struct ui_file *file, struct frame_id id);
@@ -427,17 +411,11 @@ enum unwind_stop_reason
        is not a valid stop reason.  */
     UNWIND_FIRST_ERROR,
 
-    /* This frame ID looks like it ought to belong to a NEXT frame,
-       but we got it for a PREV frame.  Normally, this is a sign of
+    /* This frame has the same ID some frame inner to it.  That means
+       that unwinding further would almost certainly get stuck in an
+       infinite loop, so break the chain.  Normally, this is a sign of
        unwinder failure.  It could also indicate stack corruption.  */
-    UNWIND_INNER_ID,
-
-    /* This frame has the same ID as the previous one.  That means
-       that unwinding further would almost certainly give us another
-       frame with exactly the same ID, so break the chain.  Normally,
-       this is a sign of unwinder failure.  It could also indicate
-       stack corruption.  */
-    UNWIND_SAME_ID,
+    UNWIND_CYCLE,
 
     /* The frame unwinder didn't find any saved PC, but we needed
        one to unwind further.  */
diff -urNp gdb-orig/gdb/i386-tdep.c gdb-head/gdb/i386-tdep.c
--- gdb-orig/gdb/i386-tdep.c	2008-06-16 00:02:04.000000000 +0200
+++ gdb-head/gdb/i386-tdep.c	2008-06-19 21:36:37.000000000 +0200
@@ -1570,8 +1570,8 @@ i386_push_dummy_call (struct gdbarch *gd
      (i386_frame_this_id, i386_sigtramp_frame_this_id,
      i386_dummy_id).  It's there, since all frame unwinders for
      a given target have to agree (within a certain margin) on the
-     definition of the stack address of a frame.  Otherwise
-     frame_id_inner() won't work correctly.  Since DWARF2/GCC uses the
+     definition of the stack address of a frame.  Otherwise frame id
+     comparison might not work correctly.  Since DWARF2/GCC uses the
      stack address *before* the function call as a frame's CFA.  On
      the i386, when %ebp is used as a frame pointer, the offset
      between the contents %ebp and the CFA as defined by GCC.  */
diff -urNp gdb-orig/gdb/infrun.c gdb-head/gdb/infrun.c
--- gdb-orig/gdb/infrun.c	2008-06-16 00:02:04.000000000 +0200
+++ gdb-head/gdb/infrun.c	2008-06-19 21:36:37.000000000 +0200
@@ -3144,33 +3144,6 @@ infrun: BPSTAT_WHAT_SET_LONGJMP_RESUME (
   ecs->current_line = ecs->sal.line;
   ecs->current_symtab = ecs->sal.symtab;
 
-  /* In the case where we just stepped out of a function into the
-     middle of a line of the caller, continue stepping, but
-     step_frame_id must be modified to current frame */
-#if 0
-  /* NOTE: cagney/2003-10-16: I think this frame ID inner test is too
-     generous.  It will trigger on things like a step into a frameless
-     stackless leaf function.  I think the logic should instead look
-     at the unwound frame ID has that should give a more robust
-     indication of what happened.  */
-  if (step - ID == current - ID)
-    still stepping in same function;
-  else if (step - ID == unwind (current - ID))
-    stepped into a function;
-  else
-    stepped out of a function;
-  /* Of course this assumes that the frame ID unwind code is robust
-     and we're willing to introduce frame unwind logic into this
-     function.  Fortunately, those days are nearly upon us.  */
-#endif
-  {
-    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;
-  }
-
   if (debug_infrun)
      fprintf_unfiltered (gdb_stdlog, "infrun: keep going\n");
   keep_going (ecs);
diff -urNp gdb-orig/gdb/stack.c gdb-head/gdb/stack.c
--- gdb-orig/gdb/stack.c	2008-05-28 19:39:56.000000000 +0200
+++ gdb-head/gdb/stack.c	2008-06-19 21:36:37.000000000 +0200
@@ -1851,29 +1851,8 @@ If you continue, the return value that y
 	error (_("Not confirmed"));
     }
 
-  /* NOTE: cagney/2003-01-18: Is this silly?  Rather than pop each
-     frame in turn, should this code just go straight to the relevant
-     frame and pop that?  */
-
-  /* First discard all frames inner-to the selected frame (making the
-     selected frame current).  */
-  {
-    struct frame_id selected_id = get_frame_id (get_selected_frame (NULL));
-    while (!frame_id_eq (selected_id, get_frame_id (get_current_frame ())))
-      {
-	struct frame_info *frame = get_current_frame ();
-	if (frame_id_inner (get_frame_arch (frame), selected_id,
-			    get_frame_id (frame)))
-	  /* Caught in the safety net, oops!  We've gone way past the
-             selected frame.  */
-	  error (_("Problem while popping stack frames (corrupt stack?)"));
-	frame_pop (get_current_frame ());
-      }
-  }
-
-  /* Second discard the selected frame (which is now also the current
-     frame).  */
-  frame_pop (get_current_frame ());
+  /* Discard the selected frame and all frames inner-to it.  */
+  frame_pop (get_selected_frame (NULL));
 
   /* Store RETURN_VALUE in the just-returned register set.  */
   if (return_value != NULL)
-- 
  Dr. Ulrich Weigand
  GNU Toolchain for Linux on System z and Cell BE
  Ulrich.Weigand@de.ibm.com


^ permalink raw reply	[flat|nested] 9+ messages in thread
end of thread, other threads:[~2008-08-26 22:19 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-06-20  4:42 [rfc] Eliminate frame_id_inner comparisons Ulrich Weigand
2008-06-25 13:32 ` Joel Brobecker
2008-06-25 14:15 ` Daniel Jacobowitz
2008-08-21 19:43   ` [rfc, v2] Fix frame_id_inner comparison false positives Ulrich Weigand
2008-08-21 20:16     ` Daniel Jacobowitz
2008-08-21 21:47       ` [rfc, v3] " Ulrich Weigand
2008-08-22  1:45         ` Ulrich Weigand
2008-08-26 17:46           ` Ulrich Weigand
2008-08-26 22:19             ` Daniel Jacobowitz

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox