From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3163 invoked by alias); 7 Apr 2010 22:39:31 -0000 Received: (qmail 3152 invoked by uid 22791); 7 Apr 2010 22:39:31 -0000 X-SWARE-Spam-Status: No, hits=-6.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_HI,SPF_HELO_PASS,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 07 Apr 2010 22:39:26 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id o37MdOqp029839 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 7 Apr 2010 18:39:25 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id o37MdOXR017220; Wed, 7 Apr 2010 18:39:24 -0400 Received: from opsy.redhat.com (ovpn01.gateway.prod.ext.phx2.redhat.com [10.5.9.1]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id o37MdNeZ014888; Wed, 7 Apr 2010 18:39:24 -0400 Received: by opsy.redhat.com (Postfix, from userid 500) id 4E974379854; Wed, 7 Apr 2010 16:39:23 -0600 (MDT) From: Tom Tromey To: Jan Kratochvil Cc: gdb-patches@sourceware.org Subject: Re: [patch] Fix deadlock on looped solib list References: <20100403092301.GA21485@host0.dyn.jankratochvil.net> <20100407222411.GA2253@host0.dyn.jankratochvil.net> Reply-To: Tom Tromey Date: Wed, 07 Apr 2010 22:39:00 -0000 In-Reply-To: <20100407222411.GA2253@host0.dyn.jankratochvil.net> (Jan Kratochvil's message of "Thu, 8 Apr 2010 00:24:11 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii 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: 2010-04/txt/msg00168.txt.bz2 >>>>> "Jan" == Jan Kratochvil writes: Tom> I don't remember hearing about this... anybody know why this isn't Tom> in the FSF GDB? Jan> It should be checked-in: Jan> [rfc][patch] Eliminate quadratic slow-down on number of solibs. Jan> http://sourceware.org/ml/gdb-patches/2009-04/msg00548.html Jan> It were multiple long threads across multiple months. Thanks. I misunderstood you to mean some local patch. Jan> I have just found now Daniel J.'s (not checked in): Jan> [RFC] Detect loops in the solib chain Jan> http://sourceware.org/ml/gdb-patches/2008-07/msg00347.html Bummer that this didn't go in. Jan> This hashtab approach of mine is needlessly expensive. Jan> * One should do next<->prev crosschecking suggested above. Jan> * To find the loop one cannot just look for the first element as Jan> it may loop one some tail elements. One cannot find the last Jan> element as ... one could get looping trying to find it. Updating Jan> the "first" element to the current one each 2^n steps (with Jan> increasing n) should safely find the loop. And much cheaper in Jan> the common non-looping case (and at most 2x expensive in the Jan> looping case). I didn't understand what you meant but I guess "Brent's algorithm" (new to me, I'm used to the old tortoise and hare from lisp hacking). http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm Tom