Don't let two frames with the same id end up in the frame chain.

The UNWIND_SAME_ID check is done between THIS_FRAME and the next frame
when we go try to unwind the previous frame.  But at this point, it's
already too late -- we ended up with two frames with the same ID in
the frame chain.  Each frame having its own ID is an invariant assumed
throughout GDB.  This patch applies the UNWIND_SAME_ID detection
earlier, right after the previous frame is unwound, discarding the dup
frame if a cycle is detected.

The patch includes a new test that fails before the change.  Before
the patch, the test causes an infinite loop in GDB, after the patch,
the UNWIND_SAME_ID logic kicks in and makes the backtrace stop with:

  Backtrace stopped: previous frame identical to this frame (corrupt stack?)

The test uses dwarf CFI to emulate a corrupted stack with a cycle.  It
has a function with registers marked DW_CFA_same_value (most
importantly RSP/RIP), so that GDB computes the same ID for that frame
and its caller.  IOW, something like this:

 #0 - frame_id_1
 #1 - frame_id_2
 #2 - frame_id_3
 #3 - frame_id_4
 #4 - frame_id_4  <<<< outermost (UNWIND_SAME_ID).

(The test's code is just a copy of dw2-reg-undefined.S /
dw2-reg-undefined.c, adjusted to use DW_CFA_same_value instead of
DW_CFA_undefined, and to mark a different set of registers.)

The infinite loop is here, in value_fetch_lazy:

      while (VALUE_LVAL (new_val) == lval_register && value_lazy (new_val))
	{
	  frame = frame_find_by_id (VALUE_FRAME_ID (new_val));
...
	  new_val = get_frame_register_value (frame, regnum);
	}

get_frame_register_value can return a lazy register value pointing to
the next frame.  This means that the register wasn't clobbered by
FRAME; the debugger should therefore retrieve its value from the next
frame.

To be clear, get_frame_register_value unwinds the value in question
from the next frame:

 struct value *
 get_frame_register_value (struct frame_info *frame, int regnum)
 {
   return frame_unwind_register_value (frame->next, regnum);
                                       ^^^^^^^^^^^
 }

In other words, if we get a lazy lval_register, it should have the
frame ID of the _next_ frame, never of FRAME.

At this point in value_fetch_lazy, the whole relevant chunk of the
stack up to frame #4 has already been unwound.  The loop always
"unlazies" lval_registers in the "next/innermost" direction, not in
the "prev/unwind further/outermost" direction.

So say we're looking at frame #4.  get_frame_register_value in frame
#4 can return a lazy register value of frame #3.  So the next
iteration, frame_find_by_id tries to read the register from frame #3.
But, since frame #4 happens to have same id as frame #3,
frame_find_by_id returns frame #4 instead.  Rinse, repeat, and we have
an infinite loop.

This is an old latent problem, exposed by the recent addition of the
frame stash.  Before we had a stash, frame_find_by_id(frame_id_4)
would walk over all frames starting at the current frame, and would
always find #3 first.  The stash happens to return #4 instead:

struct frame_info *
frame_find_by_id (struct frame_id id)
{
  struct frame_info *frame, *prev_frame;

...
  /* Try using the frame stash first.  Finding it there removes the need
     to perform the search by looping over all frames, which can be very
     CPU-intensive if the number of frames is very high (the loop is O(n)
     and get_prev_frame performs a series of checks that are relatively
     expensive).  This optimization is particularly useful when this function
     is called from another function (such as value_fetch_lazy, case
     VALUE_LVAL (val) == lval_register) which already loops over all frames,
     making the overall behavior O(n^2).  */
  frame = frame_stash_find (id);
  if (frame)
    return frame;

  for (frame = get_current_frame (); ; frame = prev_frame)
    {

gdb/
2013-11-22  Pedro Alves  <palves@redhat.com>

	PR 16155
	* frame.c (get_prev_frame_1): Do the UNWIND_SAME_ID check between
	this frame and the new previous frame, not between this frame and
	the next frame.

gdb/testsuite/
2013-11-22  Pedro Alves  <palves@redhat.com>

	PR 16155
	* gdb.dwarf2/dw2-dup-frame.S: New file.
	* gdb.dwarf2/dw2-dup-frame.c: New file.
	* gdb.dwarf2/dw2-dup-frame.exp: New file.

1 files changed, 26 insertions, 17 deletions

diff --git a/gdb/frame.c b/gdb/frame.c
index 63f20d5..535a5a6 100644
--- a/gdb/frame.c
+++ b/gdb/frame.c
@@ -1666,6 +1666,7 @@ get_prev_frame_1 (struct frame_info *this_frame)
 {
   struct frame_id this_id;
   struct gdbarch *gdbarch;
+  struct frame_info *prev_frame;
 
   gdb_assert (this_frame != NULL);
   gdbarch = get_frame_arch (this_frame);
@@ -1767,22 +1768,6 @@ get_prev_frame_1 (struct frame_info *this_frame)
 	}
     }
 
-  /* 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.  */
-  if (this_frame->level > 0
-      && frame_id_eq (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 has same ID }\n");
-	}
-      this_frame->stop_reason = UNWIND_SAME_ID;
-      return NULL;
-    }
-
   /* Check that this and the next frame do not unwind the PC register
      to the same memory location.  If they do, then even though they
      have different frame IDs, the new frame will be bogus; two
@@ -1830,7 +1815,31 @@ get_prev_frame_1 (struct frame_info *this_frame)
 	}
     }
 
-  return get_prev_frame_raw (this_frame);
+  prev_frame = get_prev_frame_raw (this_frame);
+
+  /* Check that this and the prev frame are not identical.  If they
+     are, there is most likely a stack cycle.  Unlike the tests above,
+     we do this right after creating the prev frame, to avoid ever
+     ending up with two frames with the same id in the frame
+     chain.  */
+  if (prev_frame != NULL
+      && frame_id_eq (get_frame_id (prev_frame),
+		      get_frame_id (this_frame)))
+    {
+      if (frame_debug)
+	{
+	  fprintf_unfiltered (gdb_stdlog, "-> ");
+	  fprint_frame (gdb_stdlog, NULL);
+	  fprintf_unfiltered (gdb_stdlog, " // this frame has same ID }\n");
+	}
+      this_frame->stop_reason = UNWIND_SAME_ID;
+      /* Unlink.  */
+      prev_frame->next = NULL;
+      this_frame->prev = NULL;
+      return NULL;
+    }
+
+  return prev_frame;
 }
 
 /* Construct a new "struct frame_info" and link it previous to