This is the mail archive of the gdb-patches@sourceware.org mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[RFC] identifying if a variable/msymbol has a symbol...


so, there is a bug where `info vars' looks up symbols by name,
if it finds a debug-info symbol for the symbol name,
it does not output non-debug info variables of the same name, or check
its address,
lookup symbol only searches for the first one of name, these could be ambiguous

it also happens to be real slow because there doesn't seem to be a
good way to go from msym->symbol

in the msym_var_has_symbol function, the if is for non-gdb-index
files, and the else is for gdb-index...
when looking for a symbol we end up searching through all symtabs in
the objfile, for every msym,  I couldn't figure out a better way than
storing these at psymbol creation time... e.g. msymbol->filename is
garbage for finding the associated symtab.

minsym->symtab search order is non-linear though _almost_ linear,
there are about 7 symbols in gdb that find symtabs out of linear
order... so we can't do a single pass through all symtabs, and have to
do a full pass for every minsym, circular order based on last symtab
works OK, except for the non-debug symbols. in addition .gdb-index and
non-gdb-index use different orders so that won't work...

in theory it should use .debug_aranges i suppose, but
since its optional, I imagine we'd end up having to search through
symtabs for non-debug symbols 'just in case some compiler left out the
optional .debug_aranges for that...', or similarly looking up each
symbol to see if its in an arange and if not adding that to a tree
similar to the one i've added...
since theres typically alot less globals/statics than aranges that
seems kinda futile.

with my copy of gdb/lacking debug symbols for all libraries it depends
on.  Looking for symbols which we'll never find takes roughly 50% of
the total 30 seconds of 'info var'.

stowing these global/statics away in a tree cuts `info var' 5 seconds total
I imagine this currently doesn't fare so well on reread (is it
possible to re-read only parts of an objfile or is the whole objfile?)
i seem to recall this partial destroying being mentioned in objfile.h.

 increase in memory usage is about 200k (when doing info var on gdb
itself)... so i'm assuming if we wanted to add these to .gdb-index
it'd be a little bit more compact than that..

I wrote an interval tree for it before really looking at .debug_aranges issues,
but didn't end up using it which is where the rbtree came from...
i wrote it instead of the addrmap, because things like overlays end up
hitting slow paths because
addrmap doesn't support overlapping intervals, i also figured it'd be
required to store all objfile's psymtabs addrmaps into a objfile
intsead of on a per-block basis... I now see there is a per-objfile
addrmap, not sure if that is .gdb-index specific though.
so if there is interest in the interval tree let me know...

obviously I need to do stuff like make it use an obstack, didn't try a
hash yet...
diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 826d339..a5224e7 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -717,7 +717,7 @@ SFILES = ada-exp.y ada-lang.c ada-typeprint.c ada-valprint.c ada-tasks.c \
 	p-exp.y p-lang.c p-typeprint.c p-valprint.c parse.c printcmd.c \
 	proc-service.list progspace.c \
 	prologue-value.c psymtab.c \
-	regcache.c reggroups.c remote.c remote-fileio.c reverse.c \
+	regcache.c reggroups.c remote.c remote-fileio.c reverse.c rbtree.c \
 	sentinel-frame.c \
 	serial.c ser-base.c ser-unix.c \
 	solib.c solib-target.c source.c \
@@ -794,7 +794,7 @@ complaints.h gdb_proc_service.h gdb_regex.h xtensa-tdep.h inf-loop.h \
 gdb_wait.h common/gdb_assert.h solib.h ppc-tdep.h cp-support.h glibc-tdep.h \
 interps.h auxv.h gdbcmd.h tramp-frame.h mipsnbsd-tdep.h	\
 amd64-linux-tdep.h linespec.h i387-tdep.h mn10300-tdep.h \
-sparc64-tdep.h monitor.h ppcobsd-tdep.h srec.h solib-pa64.h \
+sparc64-tdep.h monitor.h ppcobsd-tdep.h rbtree.h srec.h solib-pa64.h \
 coff-pe-read.h parser-defs.h gdb_ptrace.h mips-linux-tdep.h \
 m68k-tdep.h spu-tdep.h jv-lang.h environ.h solib-irix.h amd64-tdep.h \
 doublest.h regset.h hppa-tdep.h ppc-linux-tdep.h rs6000-tdep.h \
@@ -900,6 +900,7 @@ COMMON_OBS = $(DEPFILES) $(CONFIG_OBS) $(YYOBJ) \
 	gnu-v2-abi.o gnu-v3-abi.o cp-abi.o cp-support.o \
 	cp-namespace.o \
 	reggroups.o regset.o \
+	rbtree.o \
 	trad-frame.o \
 	tramp-frame.o \
 	solib.o solib-target.o \
diff --git a/gdb/dwarf2read.c b/gdb/dwarf2read.c
index fc6a4d50..abf0035 100644
--- a/gdb/dwarf2read.c
+++ b/gdb/dwarf2read.c
@@ -50,6 +50,7 @@
 #include "addrmap.h"
 #include "typeprint.h"
 #include "jv-lang.h"
+#include "rbtree.h"
 #include "psympriv.h"
 #include "exceptions.h"
 #include "gdb_stat.h"
@@ -2242,6 +2243,9 @@ dwarf2_read_index (struct objfile *objfile)
   dwarf2_per_objfile->quick_file_names_table =
     create_quick_file_names_table (dwarf2_per_objfile->n_comp_units);
 
+  xfree (objfile->var_psym_tree);
+  objfile->var_psym_tree = NULL;
+
   return 1;
 }
 
@@ -4040,12 +4044,16 @@ add_partial_symbol (struct partial_die_info *pdi, struct dwarf2_cu *cu)
 	     table building.  */
 
 	  if (pdi->locdesc || pdi->has_type)
-	    add_psymbol_to_list (actual_name, strlen (actual_name),
-				 built_actual_name,
-				 VAR_DOMAIN, LOC_STATIC,
-				 &objfile->global_psymbols,
-				 0, addr + baseaddr,
-				 cu->language, objfile);
+	    {
+	      psym =  add_psymbol_to_list (actual_name, strlen (actual_name),
+					   built_actual_name,
+					   VAR_DOMAIN, LOC_STATIC,
+					   &objfile->global_psymbols,
+					   0, addr + baseaddr,
+					   cu->language, objfile);
+	      rbtree_insert_value (objfile->var_psym_tree, addr + baseaddr,
+				   (void *) psym);
+	    }
 	}
       else
 	{
@@ -4058,12 +4066,14 @@ add_partial_symbol (struct partial_die_info *pdi, struct dwarf2_cu *cu)
 	    }
 	  /* prim_record_minimal_symbol (actual_name, addr + baseaddr,
 	     mst_file_data, objfile); */
-	  add_psymbol_to_list (actual_name, strlen (actual_name),
-			       built_actual_name,
-			       VAR_DOMAIN, LOC_STATIC,
-			       &objfile->static_psymbols,
-			       0, addr + baseaddr,
-			       cu->language, objfile);
+	  psym = add_psymbol_to_list (actual_name, strlen (actual_name),
+				      built_actual_name,
+				      VAR_DOMAIN, LOC_STATIC,
+				      &objfile->static_psymbols,
+				      0, addr + baseaddr,
+				      cu->language, objfile);
+	  rbtree_insert_value (objfile->var_psym_tree, addr + baseaddr,
+			       (void *) psym);
 	}
       break;
     case DW_TAG_typedef:
diff --git a/gdb/objfiles.c b/gdb/objfiles.c
index 34d6422..e27d1c2 100644
--- a/gdb/objfiles.c
+++ b/gdb/objfiles.c
@@ -54,6 +54,7 @@
 #include "observer.h"
 #include "complaints.h"
 #include "psymtab.h"
+#include "rbtree.h"
 #include "solist.h"
 
 /* Prototypes for local functions */
@@ -203,6 +204,8 @@ allocate_objfile (bfd *abfd, int flags)
   objfile->psymbol_cache = psymbol_bcache_init ();
   objfile->macro_cache = bcache_xmalloc (NULL, NULL);
   objfile->filename_cache = bcache_xmalloc (NULL, NULL);
+  objfile->var_psym_tree = rbtree_new ();
+
   /* We could use obstack_specify_allocation here instead, but
      gdb_obstack.h specifies the alloc/dealloc functions.  */
   obstack_init (&objfile->objfile_obstack);
diff --git a/gdb/objfiles.h b/gdb/objfiles.h
index bb28dc1..c5ea8b5 100644
--- a/gdb/objfiles.h
+++ b/gdb/objfiles.h
@@ -30,6 +30,7 @@ struct bcache;
 struct htab;
 struct symtab;
 struct objfile_data;
+struct rbtree;
 
 /* This structure maintains information on a per-objfile basis about the
    "entry point" of the objfile, and the scope within which the entry point
@@ -223,6 +224,10 @@ struct objfile
 
     struct addrmap *psymtabs_addrmap;
 
+    /* A rbtree containing global and static variables with
+       psymtabs as values.  */
+    struct rbtree *var_psym_tree;
+
     /* List of freed partial symtabs, available for re-use.  */
 
     struct partial_symtab *free_psymtabs;
diff --git a/gdb/rbtree.c b/gdb/rbtree.c
new file mode 100644
index 0000000..fb37fad
--- /dev/null
+++ b/gdb/rbtree.c
@@ -0,0 +1,333 @@
+/* A red black tree.
+
+   Copyright (C) 2011
+   Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   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/>.  */
+
+//#include <stdlib.h>
+#include "rbtree.h"
+#include "defs.h"
+#include "arch-utils.h"
+
+/* Structure definitions.  */
+enum rbtree_direction {
+  direction_left = 0,
+  direction_right = 1
+};
+
+enum rbtree_update_case {
+  update_case_1,
+  update_case_2,
+  update_case_3
+};
+
+enum rbtree_color {
+  black,
+  red
+};
+
+struct rbtree_node
+{
+  struct rbtree_node *parent;
+  struct rbtree_node *side[2];
+  enum rbtree_color color;
+  CORE_ADDR key;
+  void *value;
+};
+
+struct rbtree
+{
+  size_t size;
+  struct rbtree_node *root;
+};
+
+
+/* Macros.  */
+#define RBTREE_NIL(x) ((x) == &rbtree_nil_node)
+#define GRANDPARENT(x) ((x)->parent->parent)
+#define LEFT(x) ((x)->side[direction_left])
+#define RIGHT(x) ((x)->side[direction_right])
+#define LOW(x) ((x)->key)
+#define HIGH(x) ((x)->interval.high)
+#define MAX(x) ((x)->max)
+#define SIDE_ON_PARENT(x) ((x) == x->parent->side[direction_right])
+
+/* Sentinels.  */
+struct rbtree_node rbtree_nil_node =
+{
+  NULL,
+  {NULL, NULL},
+  black,
+  0,
+  NULL
+};
+
+
+/* Functions.  */
+void tree_insert (struct rbtree *t, struct rbtree_node *z)
+{
+  struct rbtree_node *y = &rbtree_nil_node;
+  struct rbtree_node *x = t->root;
+
+  while (!RBTREE_NIL (x))
+    {
+      y = x;
+      x = x->side[z->key > x->key];
+    }
+  z->parent = y;
+  if (RBTREE_NIL (y))
+    {
+      t->root = z;
+    }
+  else
+    {
+      y->side[z->key > y->key] = z;
+    }
+}
+
+struct rbtree_node *
+rbtree_search (struct rbtree *t, CORE_ADDR key, void **value)
+{
+  struct rbtree_node *x = t->root;
+
+  while (!RBTREE_NIL (x) && key != x->key)
+    {
+      x = x->side[key > x->key];
+    }
+
+  if (value)
+    *value = x->value;
+
+  return x;
+}
+
+void rbtree_rotate (struct rbtree *t, struct rbtree_node *x,
+		    enum rbtree_direction direction)
+{
+  struct rbtree_node *y;
+
+  y = x->side[!direction];
+  x->side[!direction] = y->side[direction];
+
+  if (!RBTREE_NIL (y->side[direction]))
+    y->side[direction]->parent = x;
+
+  y->parent = x->parent;
+
+  if (RBTREE_NIL (x->parent))
+    t->root = y;
+  else if (x == x->parent->side[direction])
+    x->parent->side[direction] = y;
+  else
+    x->parent->side[!direction] = y;
+
+  y->side[direction] = x;
+  x->parent = y;
+}
+
+enum rbtree_update_case
+rbtree__insertion_case (struct rbtree_node *x,
+			struct rbtree_node *y,
+			enum rbtree_direction direction)
+{
+  if (y->color == red)
+    return update_case_1;
+  else if (SIDE_ON_PARENT (x) != direction)
+    return update_case_2;
+  else
+    return update_case_3;
+}
+
+void rbtree_insert (struct rbtree *t, struct rbtree_node *x)
+{
+  struct rbtree_node *y;
+  tree_insert (t, x);
+  t->size++;
+  x->color = red;
+  while (x != t->root && x->parent->color == red)
+    {
+      enum rbtree_direction direction;
+      enum rbtree_update_case update_case;
+
+      direction = SIDE_ON_PARENT (x->parent);
+      y = GRANDPARENT (x)->side[!direction];
+      update_case = rbtree__insertion_case (x, y, direction);
+
+      switch (update_case)
+	{
+	  case update_case_1:
+	      x->parent->color = black;
+	      y->color = black;
+	      GRANDPARENT (x)->color = red;
+	      x = GRANDPARENT (x);
+	    break;
+	  case update_case_2:
+	      x = x->parent;
+	      rbtree_rotate (t, x, direction);
+	      /* Fall through.  */
+	  case update_case_3:
+	      x->parent->color = black;
+	      GRANDPARENT (x)->color = red;
+              rbtree_rotate (t, GRANDPARENT (x), !direction);
+	    break;
+	}
+    }
+  t->root->color = black;
+}
+
+struct rbtree_node *
+rbtree_insert_value (struct rbtree *t, CORE_ADDR address, void *value)
+{
+  struct rbtree_node *n = xmalloc (sizeof (struct rbtree_node));
+
+  n->key = address;
+  n->value = value;
+  n->parent = &rbtree_nil_node;
+  n->side[direction_left] = &rbtree_nil_node;
+  n->side[direction_right] = &rbtree_nil_node;
+
+  rbtree_insert (t, n);
+
+  return n;
+}
+
+struct rbtree_node *
+tree_min (struct rbtree_node *x)
+{
+  while (!RBTREE_NIL (x->side[direction_left]))
+    x = x->side[direction_left];
+  return x;
+}
+
+struct rbtree_node *
+tree_max (struct rbtree_node *x)
+{
+  while (!RBTREE_NIL (x->side[direction_right]))
+    x = x->side[direction_right];
+  return x;
+}
+
+struct rbtree_node *
+tree_successor (struct rbtree_node *x)
+{
+  struct rbtree_node *y;
+
+  if (!RBTREE_NIL (x->side[direction_right]))
+    return tree_min (x->side[direction_right]);
+  y = x->parent;
+  while (!RBTREE_NIL (y) && x == y->side[direction_right])
+    {
+      x = y;
+      y = y->parent;
+    }
+
+  return y;
+}
+
+enum rbtree_update_case
+rbtree__deletion_case (struct rbtree_node *w, enum rbtree_direction direction)
+{
+  if (w->side[direction_left]->color == black
+      && w->side[direction_right]->color == black)
+    return update_case_1;
+  else if (w->side[!direction]->color == black)
+    return update_case_2;
+  else
+    return update_case_3;
+}
+
+void rbtree_delete_fixup (struct rbtree *t, struct rbtree_node *x)
+{
+  struct rbtree_node *w;
+
+  while (x != t->root && x->color == black)
+    {
+      enum rbtree_update_case deletion_case;
+      enum rbtree_direction direction;
+
+      direction = SIDE_ON_PARENT (x);
+      w = x->parent->side[!direction];
+
+      if (w->color == red)
+	{
+	   w->color = black;
+	   x->parent->color = red;
+	   rbtree_rotate (t, x->parent, direction);
+	   w = x->parent->side[!direction];
+	}
+
+      deletion_case = rbtree__deletion_case (w, direction);
+
+      switch (deletion_case)
+	{
+	  case update_case_1:
+	    w->color = red;
+	    x = x->parent;
+	    break;
+	  case update_case_2:
+	    w->side[direction]->color = black;
+	    w->color = red;
+	    rbtree_rotate (t, w, !direction);
+	    w = x->parent->side[!direction];
+	    /* Fall through.  */
+	  case update_case_3:
+	    w->color = x->parent->color;
+	    x->parent->color = black;
+	    w->side[!direction]->color = black;
+	    rbtree_rotate (t, x->parent, direction);
+	    x = t->root;
+	    break;
+	}
+    }
+  x->color = black;
+}
+
+struct rbtree_node *
+rbtree_delete (struct rbtree *t, struct rbtree_node *z)
+{
+  struct rbtree_node *y, *x;
+
+  if (RBTREE_NIL (z->side[direction_left]) || RBTREE_NIL (z->side[direction_right]))
+    y = z;
+  else
+    y = tree_successor (z);
+
+  x = y->side[RBTREE_NIL (y->side[direction_left])];
+  x->parent = y->parent;
+
+  if (RBTREE_NIL (y->parent))
+    t->root = x;
+  else
+    y->parent->side[SIDE_ON_PARENT (y)] = x;
+
+  if (y != z)
+    z->key = y->key;
+
+  if (y->color == black)
+    rbtree_delete_fixup (t, x);
+  t->size--;
+  return y;
+}
+
+struct rbtree *
+rbtree_new (void)
+{
+  struct rbtree *t = malloc (sizeof (*t));
+  t->size = 0;
+  t->root = &rbtree_nil_node;
+  return t;
+}
diff --git a/gdb/rbtree.h b/gdb/rbtree.h
new file mode 100644
index 0000000..3565210
--- /dev/null
+++ b/gdb/rbtree.h
@@ -0,0 +1,42 @@
+/* A red black tree.
+
+   Copyright (C) 2011
+   Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   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/>.  */
+
+#ifndef GDB_RBTREE_H
+#define GDB_RBTREE_H
+#include "defs.h"
+
+struct rbtree;
+struct rbtree_node;
+
+#define RBTREE_NIL(x) ((x) == &rbtree_nil_node)
+
+extern struct rbtree_node rbtree_nil_node;
+
+struct rbtree_node *rbtree_search (struct rbtree *t,
+				   CORE_ADDR key,
+				   void **valuePtr);
+
+void rbtree_insert (struct rbtree *t, struct rbtree_node *x);
+struct rbtree_node *rbtree_delete (struct rbtree *t, struct rbtree_node *z);
+struct rbtree *rbtree_new (void);
+struct rbtree_node *rbtree_insert_value (struct rbtree *t, CORE_ADDR address, void *value);
+void rbtree_dump_graphviz_file (FILE *stream, struct rbtree *t);
+
+#endif /* GDB_RBTREE_H */
diff --git a/gdb/symtab.c b/gdb/symtab.c
index 9447bd9..cc063af 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -64,6 +64,7 @@
 #include "macroscope.h"
 
 #include "psymtab.h"
+#include "rbtree.h"
 
 /* Prototypes for local functions */
 
@@ -3006,6 +3007,63 @@ search_symbols_name_matches (const char *symname, void *user_data)
   return !data->preg_p || regexec (&data->preg, symname, 0, NULL, 0) == 0;
 }
 
+
+/* Helper for minsym_var_has_symbol.  */
+struct symbol *
+lookup_block_symbol_for_minsym (const struct block *block,
+                                struct minimal_symbol *msym)
+{
+  struct dict_iterator iter;
+  struct symbol *sym;
+
+  for (sym = dict_iter_name_first (BLOCK_DICT (block),
+                                   SYMBOL_LINKAGE_NAME (msym), &iter);
+       sym != NULL;
+       sym = dict_iter_name_next (SYMBOL_LINKAGE_NAME (msym), &iter))
+     {
+       if (SYMBOL_VALUE_ADDRESS (msym) == SYMBOL_VALUE_ADDRESS (sym))
+         return sym;
+     }
+  return NULL;
+}
+
+/* Returns 1 if a minsym representing a global or static variable has a
+   psymbol or a symbol.  0 otherwise.  */
+static int
+minsym_var_has_symbol (struct minimal_symbol *msym)
+{
+  struct objfile *objfile = msymbol_objfile (msym);
+  CORE_ADDR addr = SYMBOL_VALUE_ADDRESS (msym);
+
+  if (objfile->var_psym_tree)
+    return (0 == RBTREE_NIL (rbtree_search (objfile->var_psym_tree, addr,
+					    NULL)));
+  else
+    {
+      struct symtab *current_symtab;
+
+      for (current_symtab = objfile->symtabs;
+           current_symtab != NULL; current_symtab = current_symtab->next)
+        if (current_symtab->primary)
+          {
+	    struct symbol *sym;
+            struct blockvector *bv = BLOCKVECTOR (current_symtab);
+	    struct block *block = BLOCKVECTOR_BLOCK (bv, GLOBAL_BLOCK);
+
+            sym = lookup_block_symbol_for_minsym (block, msym);
+	    if (sym)
+	      return 1;
+
+	    block = BLOCKVECTOR_BLOCK (bv, STATIC_BLOCK);
+            sym = lookup_block_symbol_for_minsym (block, msym);
+	    if (sym)
+	      return 1;
+         }
+      return 0;
+    }
+}
+
+
 /* Search the symbol table for matches to the regular expression REGEXP,
    returning the results in *MATCHES.
 
@@ -3167,17 +3225,8 @@ search_symbols (char *regexp, enum search_domain kind,
 	      {
 		if (0 == find_pc_symtab (SYMBOL_VALUE_ADDRESS (msymbol)))
 		  {
-		    /* FIXME: carlton/2003-02-04: Given that the
-		       semantics of lookup_symbol keeps on changing
-		       slightly, it would be a nice idea if we had a
-		       function lookup_symbol_minsym that found the
-		       symbol associated to a given minimal symbol (if
-		       any).  */
 		    if (kind == FUNCTIONS_DOMAIN
-			|| lookup_symbol (SYMBOL_LINKAGE_NAME (msymbol),
-					  (struct block *) NULL,
-					  VAR_DOMAIN, 0)
-			== NULL)
+			|| minsym_var_has_symbol (msymbol) == 0)
 		      found_misc = 1;
 		  }
 	      }
@@ -3275,10 +3324,8 @@ search_symbols (char *regexp, enum search_domain kind,
 		if (kind != FUNCTIONS_DOMAIN ||
 		    (0 == find_pc_symtab (SYMBOL_VALUE_ADDRESS (msymbol))))
 		  {
-		    /* Variables/Absolutes:  Look up by name.  */
-		    if (lookup_symbol (SYMBOL_LINKAGE_NAME (msymbol),
-				       (struct block *) NULL, VAR_DOMAIN, 0)
-			 == NULL)
+		    /* Variables/Absolutes.  */
+		    if (minsym_var_has_symbol (msymbol) == 0)
 		      {
 			/* match */
 			psr = (struct symbol_search *)

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]