[patch] Fix deadlock on looped solib list

[patch] Fix deadlock on looped solib list

[Jan Kratochvil]

Hi,

this has curiously happened on a real world Thunderbird core file.
	lm 0x7fb5ba3cb000
	lm 0x7fb5bb12a000
	lm 0x7fb5b7056000
	lm 0x7fb5b7058000
	lm 0x7fb5b60c6800
	lm 0x7fb5b69f1800
	lm 0x7fb5b60c6800 <--

Now it will:
(gdb) info sharedlibrary
From        To          Syms Read   Shared Object Library
0xf7fde830  0xf7ff5ccf  Yes         /lib/ld-linux.so.2
0xf7fa8420  0xf7fc2718  Yes         /lib/libm.so.6
0xf7e46990  0xf7f524e0  Yes         /lib/libc.so.6
(gdb) PASS: gdb.base/solib-loop.exp: normal list
p/x _r_debug->r_map->l_next = _r_debug->r_map
$1 = 0xf7ffd8e0
(gdb) PASS: gdb.base/solib-loop.exp: make solibs looping
info sharedlibrary
warning: List of loaded shared objects loops at link_map 0xf7ffd8e0
From        To          Syms Read   Shared Object Library
0xf7fde830  0xf7ff5ccf  Yes         /lib/ld-linux.so.2
(gdb) PASS: gdb.base/solib-loop.exp: looped list

While some simple n^2 check or maximal allowed libraries list could be more
simple remembering Google was patching GDB for very large solib lists.

No regressions on {x86_64,x86_64-m32,i686}-fedora12-linux-gnu.


Thanks,
Jan


gdb/
2010-04-03  Jan Kratochvil  <jan.kratochvil@redhat.com>

	Fix deadlock on looped list of loaded shared objects.
	* arch-utils.c (core_addr_hash, core_addr_eq): New.
	* arch-utils.h: Include hashtab.h.
	(core_addr_hash, core_addr_eq): New prototypes.
	* defs.h: Include hashtab.h.
	(make_cleanup_htab_delete): New prototype.
	* solib-svr4.c: Include arch-utils.h.
	(svr4_current_sos): New variables lm_obstack, lm_hash, outer_chain,
	initialize them, call outer_chain do_cleanups at the bottom.  Move new
	and old_chain initializations after a new duplicity check of LM using
	new variable lm_slot.
	* utils.c (do_htab_delete_cleanup, make_cleanup_htab_delete): New.

gdb/testsuite/
2010-04-03  Jan Kratochvil  <jan.kratochvil@redhat.com>

	Fix deadlock on looped list of loaded shared objects.
	* gdb.base/solib-loop.exp: New.

--- a/gdb/arch-utils.c
+++ b/gdb/arch-utils.c
@@ -154,6 +154,25 @@ core_addr_identity (struct gdbarch *gdbarch, CORE_ADDR addr)
   return addr;
 }
 
+/* Helper functions for htab_create_alloc or htab_create_alloc_ex.  */
+
+hashval_t
+core_addr_hash (const void *ap)
+{
+  const CORE_ADDR *addrp = ap;
+
+  return *addrp;
+}
+
+int
+core_addr_eq (const void *ap, const void *bp)
+{
+  const CORE_ADDR *addr_ap = ap;
+  const CORE_ADDR *addr_bp = bp;
+
+  return *addr_ap == *addr_bp;
+}
+
 CORE_ADDR
 convert_from_func_ptr_addr_identity (struct gdbarch *gdbarch, CORE_ADDR addr,
 				     struct target_ops *targ)
--- a/gdb/arch-utils.h
+++ b/gdb/arch-utils.h
@@ -21,6 +21,8 @@
 #ifndef GDBARCH_UTILS_H
 #define GDBARCH_UTILS_H
 
+#include "hashtab.h"
+
 struct gdbarch;
 struct frame_info;
 struct minimal_symbol;
@@ -68,6 +70,11 @@ extern int core_addr_greaterthan (CORE_ADDR lhs, CORE_ADDR rhs);
 extern CORE_ADDR core_addr_identity (struct gdbarch *gdbarch, CORE_ADDR addr);
 extern gdbarch_convert_from_func_ptr_addr_ftype convert_from_func_ptr_addr_identity;
 
+/* Callback hash_f and eq_f for htab_create_alloc or htab_create_alloc_ex.  */
+
+extern hashval_t core_addr_hash (const void *ap);
+extern int core_addr_eq (const void *ap, const void *bp);
+
 /* No-op conversion of reg to regnum. */
 
 extern int no_op_reg_to_regnum (struct gdbarch *gdbarch, int reg);
--- a/gdb/defs.h
+++ b/gdb/defs.h
@@ -88,6 +88,7 @@
 #include <stdarg.h>		/* For va_list.  */
 
 #include "libiberty.h"
+#include "hashtab.h"
 
 /* Rather than duplicate all the logic in BFD for figuring out what
    types to use (which can be pretty complicated), symply define them
@@ -381,6 +382,8 @@ extern struct cleanup *make_final_cleanup (make_cleanup_ftype *, void *);
 extern struct cleanup *make_my_cleanup (struct cleanup **,
 					make_cleanup_ftype *, void *);
 
+extern struct cleanup *make_cleanup_htab_delete (htab_t htab);
+
 extern struct cleanup *make_my_cleanup2 (struct cleanup **,
 					 make_cleanup_ftype *, void *,
 					 void (*free_arg) (void *));
--- a/gdb/solib-svr4.c
+++ b/gdb/solib-svr4.c
@@ -35,6 +35,7 @@
 #include "regcache.h"
 #include "gdbthread.h"
 #include "observer.h"
+#include "arch-utils.h"
 
 #include "gdb_assert.h"
 
@@ -1106,6 +1107,9 @@ svr4_current_sos (void)
   struct so_list **link_ptr = &head;
   CORE_ADDR ldsomap = 0;
   struct svr4_info *info;
+  struct obstack lm_obstack;
+  htab_t lm_hash;
+  struct cleanup *outer_chain;
 
   info = get_svr4_info ();
 
@@ -1118,6 +1122,12 @@ svr4_current_sos (void)
   if (! info->debug_base)
     return svr4_default_sos ();
 
+  obstack_init (&lm_obstack);
+  outer_chain = make_cleanup_obstack_free (&lm_obstack);
+  lm_hash = htab_create_alloc_ex (64, core_addr_hash, core_addr_eq, NULL,
+				  &lm_obstack, hashtab_obstack_allocate, NULL);
+  make_cleanup_htab_delete (lm_hash);
+
   /* Walk the inferior's link map list, and build our list of
      `struct so_list' nodes.  */
   lm = solib_svr4_r_map (info);
@@ -1125,9 +1135,22 @@ svr4_current_sos (void)
   while (lm)
     {
       struct link_map_offsets *lmo = svr4_fetch_link_map_offsets ();
-      struct so_list *new = XZALLOC (struct so_list);
-      struct cleanup *old_chain = make_cleanup (xfree, new);
+      struct so_list *new;
+      struct cleanup *old_chain;
+      CORE_ADDR **lm_slot;
+
+      lm_slot = (CORE_ADDR **) htab_find_slot (lm_hash, &lm, INSERT);
+      if (*lm_slot != NULL)
+	{
+	  warning (_("List of loaded shared objects loops at link_map %s"),
+		   paddress (target_gdbarch, lm));
+	  break;
+	}
+      *lm_slot = obstack_alloc (&lm_obstack, sizeof (**lm_slot));
+      **lm_slot = lm;
 
+      new = XZALLOC (struct so_list);
+      old_chain = make_cleanup (xfree, new);
       new->lm_info = xmalloc (sizeof (struct lm_info));
       make_cleanup (xfree, new->lm_info);
 
@@ -1192,6 +1215,8 @@ svr4_current_sos (void)
       discard_cleanups (old_chain);
     }
 
+  do_cleanups (outer_chain);
+
   if (head == NULL)
     return svr4_default_sos ();
 
--- a/gdb/utils.c
+++ b/gdb/utils.c
@@ -346,6 +346,24 @@ make_cleanup_restore_integer (int *variable)
 			   xfree);
 }
 
+/* Helper for make_cleanup_htab_delete compile time checking the types.  */
+
+static void
+do_htab_delete_cleanup (void *htab_voidp)
+{
+  htab_t htab = htab_voidp;
+
+  htab_delete (htab);
+}
+
+/* Return a new cleanup that deletes HTAB.  */
+
+struct cleanup *
+make_cleanup_htab_delete (htab_t htab)
+{
+  return make_cleanup (do_htab_delete_cleanup, htab);
+}
+
 struct cleanup *
 make_my_cleanup2 (struct cleanup **pmy_chain, make_cleanup_ftype *function,
 		  void *arg,  void (*free_arg) (void *))
--- /dev/null
+++ b/gdb/testsuite/gdb.base/solib-loop.exp
@@ -0,0 +1,46 @@
+# Copyright 2010 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+set testfile "solib-loop"
+set srcfile start.c
+
+if { [prepare_for_testing ${testfile}.exp ${testfile} ${srcfile}] } {
+    untested ${testfile}.exp
+    return -1
+}
+
+if ![runto_main] {
+    fail "Can't run to main"
+    return
+}
+
+gdb_test "info sharedlibrary" "" "normal list"
+
+set addr ""
+set test "make solibs looping"
+gdb_test_multiple "p/x _r_debug->r_map->l_next = _r_debug->r_map" $test {
+    -re "(No symbol \"_r_debug\" in current context\\.|Attempt to extract a component of a value that is not a structure pointer\\.)\r\n$gdb_prompt $" {
+	# glibc debug info is not available and it is too difficult to find and
+	# parse it from this testcase without the gdb supporting functions.
+	xfail "$test (no _r_debug symbol)"
+    }
+    -re " = (0x\[0-9a-f\]+)\r\n$gdb_prompt $" {
+	set addr $expect_out(1,string)
+	pass $test
+    }
+}
+if {$addr != ""} {
+    gdb_test "info sharedlibrary" "warning: List of loaded shared objects loops at link_map $addr\r\n.*" "looped list"
+}

Re: [patch] Fix deadlock on looped solib list

[Tom Tromey]

>>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:

Jan> While some simple n^2 check or maximal allowed libraries list could
Jan> be more simple remembering Google was patching GDB for very large
Jan> solib lists.

I don't remember hearing about this... anybody know why this isn't
in the FSF GDB?

Jan> gdb/
Jan> 2010-04-03  Jan Kratochvil  <jan.kratochvil@redhat.com>
Jan> 	Fix deadlock on looped list of loaded shared objects.
Jan> 	* arch-utils.c (core_addr_hash, core_addr_eq): New.
Jan> 	* arch-utils.h: Include hashtab.h.
Jan> 	(core_addr_hash, core_addr_eq): New prototypes.
Jan> 	* defs.h: Include hashtab.h.
Jan> 	(make_cleanup_htab_delete): New prototype.
Jan> 	* solib-svr4.c: Include arch-utils.h.
Jan> 	(svr4_current_sos): New variables lm_obstack, lm_hash, outer_chain,
Jan> 	initialize them, call outer_chain do_cleanups at the bottom.  Move new
Jan> 	and old_chain initializations after a new duplicity check of LM using
Jan> 	new variable lm_slot.
Jan> 	* utils.c (do_htab_delete_cleanup, make_cleanup_htab_delete): New.

This is ok.  Thanks.

Tom

Re: [patch] Fix deadlock on looped solib list

[Jan Kratochvil]

On Wed, 07 Apr 2010 21:47:09 +0200, Tom Tromey wrote:
> >>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:
> 
> Jan> While some simple n^2 check or maximal allowed libraries list could
> Jan> be more simple remembering Google was patching GDB for very large
> Jan> solib lists.
> 
> I don't remember hearing about this... anybody know why this isn't
> in the FSF GDB?

It should be checked-in:
	[rfc][patch] Eliminate quadratic slow-down on number of solibs.
	http://sourceware.org/ml/gdb-patches/2009-04/msg00548.html

It were multiple long threads across multiple months.


> Jan> gdb/
> Jan> 2010-04-03  Jan Kratochvil  <jan.kratochvil@redhat.com>
> Jan> 	Fix deadlock on looped list of loaded shared objects.
> Jan> 	* arch-utils.c (core_addr_hash, core_addr_eq): New.
> Jan> 	* arch-utils.h: Include hashtab.h.
> Jan> 	(core_addr_hash, core_addr_eq): New prototypes.
> Jan> 	* defs.h: Include hashtab.h.
> Jan> 	(make_cleanup_htab_delete): New prototype.
> Jan> 	* solib-svr4.c: Include arch-utils.h.
> Jan> 	(svr4_current_sos): New variables lm_obstack, lm_hash, outer_chain,
> Jan> 	initialize them, call outer_chain do_cleanups at the bottom.  Move new
> Jan> 	and old_chain initializations after a new duplicity check of LM using
> Jan> 	new variable lm_slot.
> Jan> 	* utils.c (do_htab_delete_cleanup, make_cleanup_htab_delete): New.
> 
> This is ok.  Thanks.

I have just found now Daniel J.'s (not checked in):
	[RFC] Detect loops in the solib chain
	http://sourceware.org/ml/gdb-patches/2008-07/msg00347.html

This hashtab approach of mine is needlessly expensive.

 * One should do next<->prev crosschecking suggested above.

 * To find the loop one cannot just look for the first element as it may loop
   one some tail elements.  One cannot find the last element as ... one could
   get looping trying to find it.  Updating the "first" element to the current
   one each 2^n steps (with increasing n) should safely find the loop.  And
   much cheaper in the common non-looping case (and at most 2x expensive in
   the looping case).

I will post the new patch.


Thanks,
Jan

Re: [patch] Fix deadlock on looped solib list

[Tom Tromey]

>>>>> "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

[cancel] Re: [patch] Fix deadlock on looped solib list

[Jan Kratochvil]

On Thu, 08 Apr 2010 00:39:23 +0200, Tom Tromey wrote:
> >>>>> "Jan" == Jan Kratochvil <jan.kratochvil@redhat.com> writes:
> 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.

therefore cancelling this thread in favor of the revived:
	Re: [RFC] Detect loops in the solib chain
	http://sourceware.org/ml/gdb-patches/2010-04/msg00245.html


Thanks,
Jan