From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20084 invoked by alias); 19 Jun 2008 20:35:11 -0000 Received: (qmail 20072 invoked by uid 22791); 19 Jun 2008 20:35:08 -0000 X-Spam-Check-By: sourceware.org Received: from mtagate7.de.ibm.com (HELO mtagate7.de.ibm.com) (195.212.29.156) by sourceware.org (qpsmtpd/0.31) with ESMTP; Thu, 19 Jun 2008 20:34:42 +0000 Received: from d12nrmr1607.megacenter.de.ibm.com (d12nrmr1607.megacenter.de.ibm.com [9.149.167.49]) by mtagate7.de.ibm.com (8.13.8/8.13.8) with ESMTP id m5JKY52Q367064 for ; Thu, 19 Jun 2008 20:34:05 GMT Received: from d12av02.megacenter.de.ibm.com (d12av02.megacenter.de.ibm.com [9.149.165.228]) by d12nrmr1607.megacenter.de.ibm.com (8.13.8/8.13.8/NCO v9.0) with ESMTP id m5JKY5bn3686446 for ; Thu, 19 Jun 2008 22:34:05 +0200 Received: from d12av02.megacenter.de.ibm.com (loopback [127.0.0.1]) by d12av02.megacenter.de.ibm.com (8.12.11.20060308/8.13.3) with ESMTP id m5JKY5p5004882 for ; Thu, 19 Jun 2008 22:34:05 +0200 Received: from tuxmaker.boeblingen.de.ibm.com (tuxmaker.boeblingen.de.ibm.com [9.152.85.9]) by d12av02.megacenter.de.ibm.com (8.12.11.20060308/8.12.11) with SMTP id m5JKY5gt004879 for ; Thu, 19 Jun 2008 22:34:05 +0200 Message-Id: <200806192034.m5JKY5gt004879@d12av02.megacenter.de.ibm.com> Received: by tuxmaker.boeblingen.de.ibm.com (sSMTP sendmail emulation); Thu, 19 Jun 2008 22:34:05 +0200 Subject: [rfc] Eliminate frame_id_inner comparisons To: gdb-patches@sourceware.org Date: Fri, 20 Jun 2008 04:42:00 -0000 From: "Ulrich Weigand" X-Mailer: ELM [version 2.5 PL2] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2008-06/txt/msg00357.txt.bz2 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