Re: [patch] Fix deadlock on looped solib list

[Tom Tromey <tromey@redhat.com>]

>>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> 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