From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 13228 invoked by alias); 25 Jun 2008 13:51:30 -0000 Received: (qmail 13220 invoked by uid 22791); 25 Jun 2008 13:51:29 -0000 X-Spam-Check-By: sourceware.org Received: from NaN.false.org (HELO nan.false.org) (208.75.86.248) by sourceware.org (qpsmtpd/0.31) with ESMTP; Wed, 25 Jun 2008 13:51:10 +0000 Received: from nan.false.org (localhost [127.0.0.1]) by nan.false.org (Postfix) with ESMTP id 2F9DE9835A; Wed, 25 Jun 2008 13:51:08 +0000 (GMT) Received: from caradoc.them.org (22.svnf5.xdsl.nauticom.net [209.195.183.55]) by nan.false.org (Postfix) with ESMTP id 005769810F; Wed, 25 Jun 2008 13:51:07 +0000 (GMT) Received: from drow by caradoc.them.org with local (Exim 4.69) (envelope-from ) id 1KBVOt-0002OQ-38; Wed, 25 Jun 2008 09:51:07 -0400 Date: Wed, 25 Jun 2008 14:15:00 -0000 From: Daniel Jacobowitz To: Ulrich Weigand Cc: gdb-patches@sourceware.org Subject: Re: [rfc] Eliminate frame_id_inner comparisons Message-ID: <20080625135107.GB8020@caradoc.them.org> Mail-Followup-To: Ulrich Weigand , gdb-patches@sourceware.org References: <200806192034.m5JKY5gt004879@d12av02.megacenter.de.ibm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200806192034.m5JKY5gt004879@d12av02.megacenter.de.ibm.com> User-Agent: Mutt/1.5.17 (2008-05-11) X-IsSubscribed: yes 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/msg00433.txt.bz2 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