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

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.