[3/10] introduce psymtab users

[3/10] introduce psymtab users

[Tom Tromey]

Adding support for imported PUs means modifying both symtabs and
psymtabs to understand the inclusions.

This patch adds some basic infrastructure to psymtabs.  It adds a
"users" field which the psymtab readers can set.  Then, it changes the
psymtab code to handle included psymtabs properly.

There are a few cases to consider.  I did this by auditing all the code
in psymtab.c.

When doing lookups using the file name, we can just ignore PUs.

When doing a lookup by name or by PC, it is ok to find a PU.  However,
we have a rule that we can only expand a full CU, so we modify
psymtab_to_symtab to find a user (any will do) of the PU.

Then, finally, there is some hair in expand_symtabs_matching_via_partial
to search PUs while searching CUs.

This patch has no immediate effect, because no psymtab readers are
updated yet.

Tom

From 9d29b92217dd4e363d88f7cbc357d4cf9d28e51b Mon Sep 17 00:00:00 2001
From: Tom Tromey <tromey@redhat.com>
Date: Wed, 18 Apr 2012 14:49:36 -0600
Subject: [PATCH 03/10] introduce psymtab users notion

	* psymtab.c (partial_map_expand_apply): Add assertion.
	(partial_map_symtabs_matching_filename): Skip included psymtabs.
	(psymtab_to_symtab): Find unshared psymtab.
	(dump_psymtab): Print including psymtabs.
	(PST_NOT_SEARCHED, PST_SEARCHED_AND_FOUND)
	(PST_SEARCHED_AND_NOT_FOUND): New constants.
	(recursively_search_psymtabs): New function.
	(expand_symtabs_matching_via_partial): Use it.
	* psympriv.h (struct partial_symtab) <users, searched_flag>: New
	fields.
---
 gdb/psympriv.h |   29 +++++++++
 gdb/psymtab.c  |  177 +++++++++++++++++++++++++++++++++++++++++--------------
 2 files changed, 161 insertions(+), 45 deletions(-)

diff --git a/gdb/psympriv.h b/gdb/psympriv.h
index df7b874..5515d6c 100644
--- a/gdb/psympriv.h
+++ b/gdb/psympriv.h
@@ -111,6 +111,31 @@ struct partial_symtab
 
   int number_of_dependencies;
 
+  /* If NULL, this is an ordinary partial symbol table.
+
+     If non-NULL, this holds a NULL-terminated vector of includers of
+     this partial symbol table, and this partial symbol table is a
+     shared one.
+
+     A shared psymtab is one that is referenced by multiple other
+     psymtabs, and which conceptually has its contents directly
+     included in those.
+
+     Shared psymtabs have special semantics.  When a search finds a
+     symbol in a shared table, we instead return one of the non-shared
+     tables that include this one.
+
+     A shared psymtabs can be referred to by other shared ones.
+
+     The psymtabs that refer to a shared psymtab will list the shared
+     psymtab in their 'dependencies' array.
+
+     In DWARF terms, a shared psymtab is a DW_TAG_partial_unit; but
+     of course using a name based on that would be too confusing, so
+     "shared" was chosen instead.  */
+
+  struct partial_symtab **users;
+
   /* Global symbol list.  This list will be sorted after readin to
      improve access.  Binary search will be the usual method of
      finding a symbol within it.  globals_offset is an integer offset
@@ -142,6 +167,10 @@ struct partial_symtab
 
   unsigned char psymtabs_addrmap_supported;
 
+  /* A flag that is temporarily used when searching psymtabs.  */
+
+  unsigned char searched_flag;
+
   /* Pointer to symtab eventually allocated for this source file, 0 if
      !readin or if we haven't looked for the symtab after it was readin.  */
 
diff --git a/gdb/psymtab.c b/gdb/psymtab.c
index 9620de8..9e64275 100644
--- a/gdb/psymtab.c
+++ b/gdb/psymtab.c
@@ -135,6 +135,10 @@ partial_map_expand_apply (struct objfile *objfile,
 {
   struct symtab *last_made = objfile->symtabs;
 
+  /* Shared psymtabs should never be seen here.  Instead they should
+     be handled properly by the caller.  */
+  gdb_assert (pst->users == NULL);
+
   /* Don't visit already-expanded psymtabs.  */
   if (pst->readin)
     return 0;
@@ -165,6 +169,11 @@ partial_map_symtabs_matching_filename (struct objfile *objfile,
 
   ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, pst)
   {
+    /* We can skip shared psymtabs here, because any file name will be
+       attached to the unshared psymtab.  */
+    if (pst->users != NULL)
+      continue;
+
     if (FILENAME_CMP (name, pst->filename) == 0
 	|| (!is_abs && compare_filenames_for_search (pst->filename,
 						     name, name_len)))
@@ -760,6 +769,11 @@ lookup_partial_symbol (struct partial_symtab *pst, const char *name,
 static struct symtab *
 psymtab_to_symtab (struct partial_symtab *pst)
 {
+  /* If it is a shared psymtab, find an unshared psymtab that includes
+     it.  Any such psymtab will do.  */
+  while (pst->users != NULL)
+    pst = pst->users[0];
+
   /* If it's been looked up before, return it.  */
   if (pst->symtab)
     return pst->symtab;
@@ -1000,6 +1014,16 @@ dump_psymtab (struct objfile *objfile, struct partial_symtab *psymtab,
       fprintf_filtered (outfile, " %s\n",
 			psymtab->dependencies[i]->filename);
     }
+  if (psymtab->users != NULL)
+    {
+      fprintf_filtered (outfile, "  Shared partial symtab with users:\n");
+      for (i = 0; psymtab->users[i] != NULL; ++i)
+	{
+	  fprintf_filtered (outfile, "    ");
+	  gdb_print_host_address (psymtab->users[i], outfile);
+	  fprintf_filtered (outfile, "\n");
+	}
+    }
   if (psymtab->n_global_syms > 0)
     {
       print_partial_symbols (gdbarch,
@@ -1236,6 +1260,102 @@ map_matching_symbols_psymtab (const char *name, domain_enum namespace,
     }
 }	    
 
+/* A convenience enum to give names to some constants used in
+   recursively_search_psymtabs.  */
+
+enum
+  {
+    PST_NOT_SEARCHED,
+    PST_SEARCHED_AND_FOUND,
+    PST_SEARCHED_AND_NOT_FOUND
+  };
+
+/* A helper for expand_symtabs_matching_via_partial that handles
+   searching included psymtabs.  */
+
+static int
+recursively_search_psymtabs (struct partial_symtab *ps,
+			     struct objfile *objfile,
+			     enum search_domain kind,
+			     int (*name_matcher) (const char *, void *),
+			     void *data)
+{
+  struct partial_symbol **psym;
+  struct partial_symbol **bound, **gbound, **sbound;
+  int keep_going = 1;
+  int result = PST_SEARCHED_AND_NOT_FOUND;
+  int i;
+
+  if (ps->searched_flag != PST_NOT_SEARCHED)
+    return ps->searched_flag == PST_SEARCHED_AND_FOUND;
+
+  /* Recurse into shared psymtabs first, because they may have already
+     been searched, and this could save some time.  */
+  for (i = 0; i < ps->number_of_dependencies; ++i)
+    {
+      int r;
+
+      /* Skip non-shared dependencies, these are handled elsewhere.  */
+      if (ps->dependencies[i]->users == NULL)
+	continue;
+
+      r = recursively_search_psymtabs (ps->dependencies[i],
+				       objfile, kind, name_matcher, data);
+      if (r != 0)
+	{
+	  ps->searched_flag = PST_SEARCHED_AND_FOUND;
+	  return 1;
+	}
+    }
+
+  gbound = (objfile->global_psymbols.list
+	    + ps->globals_offset + ps->n_global_syms);
+  sbound = (objfile->static_psymbols.list
+	    + ps->statics_offset + ps->n_static_syms);
+  bound = gbound;
+
+  /* Go through all of the symbols stored in a partial
+     symtab in one loop.  */
+  psym = objfile->global_psymbols.list + ps->globals_offset;
+  while (keep_going)
+    {
+      if (psym >= bound)
+	{
+	  if (bound == gbound && ps->n_static_syms != 0)
+	    {
+	      psym = objfile->static_psymbols.list + ps->statics_offset;
+	      bound = sbound;
+	    }
+	  else
+	    keep_going = 0;
+	  continue;
+	}
+      else
+	{
+	  QUIT;
+
+	  if ((kind == ALL_DOMAIN
+	       || (kind == VARIABLES_DOMAIN
+		   && SYMBOL_CLASS (*psym) != LOC_TYPEDEF
+		   && SYMBOL_CLASS (*psym) != LOC_BLOCK)
+	       || (kind == FUNCTIONS_DOMAIN
+		   && SYMBOL_CLASS (*psym) == LOC_BLOCK)
+	       || (kind == TYPES_DOMAIN
+		   && SYMBOL_CLASS (*psym) == LOC_TYPEDEF))
+	      && (*name_matcher) (SYMBOL_SEARCH_NAME (*psym), data))
+	    {
+	      /* Found a match, so notify our caller.  */
+	      result = PST_SEARCHED_AND_FOUND;
+	      keep_going = 0;
+	    }
+	}
+      psym++;
+    }
+
+  ps->searched_flag = result;
+  return result == PST_SEARCHED_AND_FOUND;
+}
+
 static void
 expand_symtabs_matching_via_partial
   (struct objfile *objfile,
@@ -1246,60 +1366,27 @@ expand_symtabs_matching_via_partial
 {
   struct partial_symtab *ps;
 
+  /* Clear the search flags.  */
   ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, ps)
     {
-      struct partial_symbol **psym;
-      struct partial_symbol **bound, **gbound, **sbound;
-      int keep_going = 1;
+      ps->searched_flag = PST_NOT_SEARCHED;
+    }
 
+  ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, ps)
+    {
       if (ps->readin)
 	continue;
 
-      if (file_matcher && ! (*file_matcher) (ps->filename, data))
+      /* We skip shared psymtabs because file-matching doesn't apply
+	 to them; but we search them later in the loop.  */
+      if (ps->users != NULL)
 	continue;
 
-      gbound = objfile->global_psymbols.list
-	+ ps->globals_offset + ps->n_global_syms;
-      sbound = objfile->static_psymbols.list
-	+ ps->statics_offset + ps->n_static_syms;
-      bound = gbound;
+      if (file_matcher && ! (*file_matcher) (ps->filename, data))
+	continue;
 
-      /* Go through all of the symbols stored in a partial
-	 symtab in one loop.  */
-      psym = objfile->global_psymbols.list + ps->globals_offset;
-      while (keep_going)
-	{
-	  if (psym >= bound)
-	    {
-	      if (bound == gbound && ps->n_static_syms != 0)
-		{
-		  psym = objfile->static_psymbols.list + ps->statics_offset;
-		  bound = sbound;
-		}
-	      else
-		keep_going = 0;
-	      continue;
-	    }
-	  else
-	    {
-	      QUIT;
-
-	      if ((kind == ALL_DOMAIN
-		   || (kind == VARIABLES_DOMAIN
-		       && SYMBOL_CLASS (*psym) != LOC_TYPEDEF
-		       && SYMBOL_CLASS (*psym) != LOC_BLOCK)
-		   || (kind == FUNCTIONS_DOMAIN
-		       && SYMBOL_CLASS (*psym) == LOC_BLOCK)
-		   || (kind == TYPES_DOMAIN
-		       && SYMBOL_CLASS (*psym) == LOC_TYPEDEF))
-		  && (*name_matcher) (SYMBOL_SEARCH_NAME (*psym), data))
-		{
-		  psymtab_to_symtab (ps);
-		  keep_going = 0;
-		}
-	    }
-	  psym++;
-	}
+      if (recursively_search_psymtabs (ps, objfile, kind, name_matcher, data))
+	psymtab_to_symtab (ps);
     }
 }
 
-- 
1.7.7.6

Re: [3/10] introduce psymtab users

[Jan Kratochvil]

On Wed, 25 Apr 2012 20:21:23 +0200, Tom Tromey wrote:
[...]
> @@ -142,6 +167,10 @@ struct partial_symtab
>  
>    unsigned char psymtabs_addrmap_supported;
>  
> +  /* A flag that is temporarily used when searching psymtabs.  */
> +
> +  unsigned char searched_flag;

Please make it the enum.


> @@ -760,6 +769,11 @@ lookup_partial_symbol (struct partial_symtab *pst, const char *name,
>  static struct symtab *
>  psymtab_to_symtab (struct partial_symtab *pst)
>  {
> +  /* If it is a shared psymtab, find an unshared psymtab that includes
> +     it.  Any such psymtab will do.  */
> +  while (pst->users != NULL)
> +    pst = pst->users[0];

Currently GDB already has a problem that if it needs to expand symtab A to get
symbol X it already expands also symtabs B, C and D, all of them pretty big
for C++.

With such random choosing of a symtab for expansion this multi-expand
performance hit may get even worse for big C++ programs.

(Not sure if you do not already plan some more general fix for that.)


> @@ -1236,6 +1260,102 @@ map_matching_symbols_psymtab (const char *name, domain_enum namespace,
>      }
>  }	    
>  
> +/* A convenience enum to give names to some constants used in
> +   recursively_search_psymtabs.  */
> +
> +enum
> +  {
> +    PST_NOT_SEARCHED,
> +    PST_SEARCHED_AND_FOUND,
> +    PST_SEARCHED_AND_NOT_FOUND
> +  };
> +
> +/* A helper for expand_symtabs_matching_via_partial that handles
> +   searching included psymtabs.  */

Describe return value, please.

> +
> +static int
> +recursively_search_psymtabs (struct partial_symtab *ps,
> +			     struct objfile *objfile,
> +			     enum search_domain kind,
> +			     int (*name_matcher) (const char *, void *),
> +			     void *data)
> +{
> +  struct partial_symbol **psym;
> +  struct partial_symbol **bound, **gbound, **sbound;
> +  int keep_going = 1;
> +  int result = PST_SEARCHED_AND_NOT_FOUND;
> +  int i;
> +
> +  if (ps->searched_flag != PST_NOT_SEARCHED)
> +    return ps->searched_flag == PST_SEARCHED_AND_FOUND;
> +
> +  /* Recurse into shared psymtabs first, because they may have already
> +     been searched, and this could save some time.  */
> +  for (i = 0; i < ps->number_of_dependencies; ++i)
> +    {
> +      int r;
> +
> +      /* Skip non-shared dependencies, these are handled elsewhere.  */
> +      if (ps->dependencies[i]->users == NULL)
> +	continue;
> +
> +      r = recursively_search_psymtabs (ps->dependencies[i],
> +				       objfile, kind, name_matcher, data);
> +      if (r != 0)
> +	{
> +	  ps->searched_flag = PST_SEARCHED_AND_FOUND;
> +	  return 1;
> +	}
> +    }
> +
> +  gbound = (objfile->global_psymbols.list
> +	    + ps->globals_offset + ps->n_global_syms);

nitpick: While I do not like it IMO GNU Coding Standard says:
	gbound = &objfile->global_psymbols.list[ps->globals_offset + ps->n_global_syms];

But it applies also to the current code.

> +  sbound = (objfile->static_psymbols.list
> +	    + ps->statics_offset + ps->n_static_syms);
> +  bound = gbound;
> +
> +  /* Go through all of the symbols stored in a partial
> +     symtab in one loop.  */
> +  psym = objfile->global_psymbols.list + ps->globals_offset;
> +  while (keep_going)

I do not see why to use the 'keep_going' variable here, just use 'break;'.

But it applies also to the current code.

> +    {
> +      if (psym >= bound)
> +	{
> +	  if (bound == gbound && ps->n_static_syms != 0)
> +	    {
> +	      psym = objfile->static_psymbols.list + ps->statics_offset;
> +	      bound = sbound;
> +	    }
> +	  else
> +	    keep_going = 0;
> +	  continue;
> +	}
> +      else
> +	{
> +	  QUIT;
> +
> +	  if ((kind == ALL_DOMAIN
> +	       || (kind == VARIABLES_DOMAIN
> +		   && SYMBOL_CLASS (*psym) != LOC_TYPEDEF
> +		   && SYMBOL_CLASS (*psym) != LOC_BLOCK)
> +	       || (kind == FUNCTIONS_DOMAIN
> +		   && SYMBOL_CLASS (*psym) == LOC_BLOCK)
> +	       || (kind == TYPES_DOMAIN
> +		   && SYMBOL_CLASS (*psym) == LOC_TYPEDEF))
> +	      && (*name_matcher) (SYMBOL_SEARCH_NAME (*psym), data))
> +	    {
> +	      /* Found a match, so notify our caller.  */
> +	      result = PST_SEARCHED_AND_FOUND;
> +	      keep_going = 0;
> +	    }
> +	}
> +      psym++;
> +    }
> +
> +  ps->searched_flag = result;
> +  return result == PST_SEARCHED_AND_FOUND;
> +}
> +
>  static void
>  expand_symtabs_matching_via_partial
>    (struct objfile *objfile,


Thanks,
Jan

Re: [3/10] introduce psymtab users

[Tom Tromey]

>> +  /* A flag that is temporarily used when searching psymtabs.  */
>> +
>> +  unsigned char searched_flag;

Jan> Please make it the enum.

I didn't do this originally because this field and the enum values are
purely temporary.  They have no meaning outside one little bit of the
code.

But, I don't mind, I will make the change.  Very little should be
including psympriv.h anyway.

>> @@ -760,6 +769,11 @@ lookup_partial_symbol (struct partial_symtab
>> *pst, const char *name,
>> static struct symtab *
>> psymtab_to_symtab (struct partial_symtab *pst)
>> {
>> +  /* If it is a shared psymtab, find an unshared psymtab that includes
>> +     it.  Any such psymtab will do.  */
>> +  while (pst->users != NULL)
>> +    pst = pst->users[0];

Jan> Currently GDB already has a problem that if it needs to expand
Jan> symtab A to get symbol X it already expands also symtabs B, C and
Jan> D, all of them pretty big for C++.

Jan> With such random choosing of a symtab for expansion this multi-expand
Jan> performance hit may get even worse for big C++ programs.

Jan> (Not sure if you do not already plan some more general fix for that.)

Someday I would like to implement my lazy CU expansion ideas.
Well, unless we think of something better.  And if we think they'll help
enough; first one of us should redo the performance comparisons.

In the short term, though, I don't think this makes things any worse.
My reasoning is that in the uncompressed DWARF, gdb would read the first
matching CU.  With the compressed DWARF, gdb still does exactly this,
only it reads the CU and the included PUs.

Jan> I do not see why to use the 'keep_going' variable here, just use 'break;'.

Jan> But it applies also to the current code.

Yeah, I don't want to change code I just moved around.
Cleanups are fine separately.

Tom

Re: [3/10] introduce psymtab users

[Jan Kratochvil]

On Thu, 26 Apr 2012 20:38:12 +0200, Tom Tromey wrote:
> >> @@ -760,6 +769,11 @@ lookup_partial_symbol (struct partial_symtab
> >> *pst, const char *name,
> >> static struct symtab *
> >> psymtab_to_symtab (struct partial_symtab *pst)
> >> {
> >> +  /* If it is a shared psymtab, find an unshared psymtab that includes
> >> +     it.  Any such psymtab will do.  */
> >> +  while (pst->users != NULL)
> >> +    pst = pst->users[0];
> 
> Jan> Currently GDB already has a problem that if it needs to expand
> Jan> symtab A to get symbol X it already expands also symtabs B, C and
> Jan> D, all of them pretty big for C++.
> 
> Jan> With such random choosing of a symtab for expansion this multi-expand
> Jan> performance hit may get even worse for big C++ programs.
> 
> Jan> (Not sure if you do not already plan some more general fix for that.)
> 
> Someday I would like to implement my lazy CU expansion ideas.
> Well, unless we think of something better.  And if we think they'll help
> enough; first one of us should redo the performance comparisons.
> 
> In the short term, though, I don't think this makes things any worse.
> My reasoning is that in the uncompressed DWARF, gdb would read the first
> matching CU.  With the compressed DWARF, gdb still does exactly this,
> only it reads the CU and the included PUs.

I had on my mind a case where it can make the performance worse but I see now
it cannot.

If PST is not yet expanded it means very every pst->users[i] element is also
not expanded, right?


Thanks,
Jan

Re: [3/10] introduce psymtab users

[Tom Tromey]

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

Jan> If PST is not yet expanded it means very every pst->users[i]
Jan> element is also not expanded, right?

That's right.

When expanding a PU, we look for a canonical including CU, and expand
that instead.  This is handled by the loop in psymtab_to_symtab.

When expanding a CU, we expand all of the PUs it includes (but in
isolation, we don't go "back up the chain" to the canonical CU).  This
is handled by how the symtab reader processes DW_TAG_imported_unit.

Tom

Re: [3/10] introduce psymtab users

[Jan Kratochvil]

On Wed, 25 Apr 2012 20:21:23 +0200, Tom Tromey wrote:
[...]
> +  struct partial_symtab **users;
[...]
> @@ -760,6 +769,11 @@ lookup_partial_symbol (struct partial_symtab *pst, const char *name,
>  static struct symtab *
>  psymtab_to_symtab (struct partial_symtab *pst)
>  {
> +  /* If it is a shared psymtab, find an unshared psymtab that includes
> +     it.  Any such psymtab will do.  */
> +  while (pst->users != NULL)
> +    pst = pst->users[0];

Currently pst->users is used in the whole patchset only
for 'pst->users == NULL', 'pst->users != NULL' and for 'pst->users[0]'.
I think the array can be dropped.


Thanks,
Jan

Re: [3/10] introduce psymtab users

[Doug Evans]

On Wed, Apr 25, 2012 at 11:21 AM, Tom Tromey <tromey@redhat.com> wrote:
> @@ -165,6 +169,11 @@ partial_map_symtabs_matching_filename (struct objfile *objfile,
>
>   ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, pst)
>   {
> +    /* We can skip shared psymtabs here, because any file name will be
> +       attached to the unshared psymtab.  */
> +    if (pst->users != NULL)
> +      continue;
> +
>     if (FILENAME_CMP (name, pst->filename) == 0
>        || (!is_abs && compare_filenames_for_search (pst->filename,
>                                                     name, name_len)))

The abstraction feels broken if ALL_OBJFILE_PSYMTABS* includes these
special shared psymtabs.

[This is akin to the objfile list including separate debug file objfiles.]

Re: [3/10] introduce psymtab users

[Doug Evans]

On Mon, Apr 30, 2012 at 11:44 AM, Doug Evans <dje@google.com> wrote:
> On Wed, Apr 25, 2012 at 11:21 AM, Tom Tromey <tromey@redhat.com> wrote:
>> @@ -165,6 +169,11 @@ partial_map_symtabs_matching_filename (struct objfile *objfile,
>>
>>   ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, pst)
>>   {
>> +    /* We can skip shared psymtabs here, because any file name will be
>> +       attached to the unshared psymtab.  */
>> +    if (pst->users != NULL)
>> +      continue;
>> +
>>     if (FILENAME_CMP (name, pst->filename) == 0
>>        || (!is_abs && compare_filenames_for_search (pst->filename,
>>                                                     name, name_len)))
>
> The abstraction feels broken if ALL_OBJFILE_PSYMTABS* includes these
> special shared psymtabs.
>
> [This is akin to the objfile list including separate debug file objfiles.]

Actually, I take that back.
Looking into something unrelated, I can understand implementing them
that way (given the source as it is today).
Still, IWBN to have an iterator that did just iterate over the "real" psymtabs.
e.g., have a version of ALL_OBJFILE_PSYMTABS_REQUIRED that skipped
shared psymtabs so the caller didn't have to do that.

Re: [3/10] introduce psymtab users

[Tom Tromey]

>>>>> "Tom" == Tom Tromey <tromey@redhat.com> writes:

Tom> This patch adds some basic infrastructure to psymtabs.  It adds a
Tom> "users" field which the psymtab readers can set.  Then, it changes the
Tom> psymtab code to handle included psymtabs properly.

Here is the updated version of this patch.
I think it takes all the comments into account.

Tom

From d8efcf6e2771975d8e314641b9265ce06e94d629 Mon Sep 17 00:00:00 2001
From: Tom Tromey <tromey@redhat.com>
Date: Wed, 18 Apr 2012 14:49:36 -0600
Subject: [PATCH 03/10] introduce psymtab users notion

	* psymtab.c (partial_map_expand_apply): Add assertion.
	(partial_map_symtabs_matching_filename): Skip included psymtabs.
	(psymtab_to_symtab): Find unshared psymtab.
	(dump_psymtab): Print including psymtabs.
	(recursively_search_psymtabs): New function.
	(expand_symtabs_matching_via_partial): Use it.
	* psympriv.h (struct partial_symtab) <user, searched_flag>: New
	fields.
	(enum psymtab_search_status): New.
---
 gdb/psympriv.h |   44 +++++++++++++++
 gdb/psymtab.c  |  165 ++++++++++++++++++++++++++++++++++++++++---------------
 2 files changed, 164 insertions(+), 45 deletions(-)

diff --git a/gdb/psympriv.h b/gdb/psympriv.h
index df7b874..370ce86 100644
--- a/gdb/psympriv.h
+++ b/gdb/psympriv.h
@@ -54,6 +54,17 @@ struct partial_symbol
 #define PSYMBOL_DOMAIN(psymbol)	(psymbol)->domain
 #define PSYMBOL_CLASS(psymbol)		(psymbol)->aclass
 
+/* A convenience enum to give names to some constants used when
+   searching psymtabs.  This is internal to psymtab and should not be
+   used elsewhere.  */
+
+enum psymtab_search_status
+  {
+    PST_NOT_SEARCHED,
+    PST_SEARCHED_AND_FOUND,
+    PST_SEARCHED_AND_NOT_FOUND
+  };
+
 /* Each source file that has not been fully read in is represented by
    a partial_symtab.  This contains the information on where in the
    executable the debugging symbols for a specific file are, and a
@@ -111,6 +122,35 @@ struct partial_symtab
 
   int number_of_dependencies;
 
+  /* If NULL, this is an ordinary partial symbol table.
+
+     If non-NULL, this holds a single includer of this partial symbol
+     table, and this partial symbol table is a shared one.
+
+     A shared psymtab is one that is referenced by multiple other
+     psymtabs, and which conceptually has its contents directly
+     included in those.
+
+     Shared psymtabs have special semantics.  When a search finds a
+     symbol in a shared table, we instead return one of the non-shared
+     tables that include this one.
+
+     A shared psymtabs can be referred to by other shared ones.
+
+     The psymtabs that refer to a shared psymtab will list the shared
+     psymtab in their 'dependencies' array.
+
+     In DWARF terms, a shared psymtab is a DW_TAG_partial_unit; but
+     of course using a name based on that would be too confusing, so
+     "shared" was chosen instead.
+     
+     Only a single user is needed because, when expanding a shared
+     psymtab, we only need to expand its "canonical" non-shared user.
+     The choice of which one should be canonical is left to the
+     debuginfo reader; it can be arbitrary.  */
+
+  struct partial_symtab *user;
+
   /* Global symbol list.  This list will be sorted after readin to
      improve access.  Binary search will be the usual method of
      finding a symbol within it.  globals_offset is an integer offset
@@ -142,6 +182,10 @@ struct partial_symtab
 
   unsigned char psymtabs_addrmap_supported;
 
+  /* A flag that is temporarily used when searching psymtabs.  */
+
+  ENUM_BITFIELD (psymtab_search_status) searched_flag : 2;
+
   /* Pointer to symtab eventually allocated for this source file, 0 if
      !readin or if we haven't looked for the symtab after it was readin.  */
 
diff --git a/gdb/psymtab.c b/gdb/psymtab.c
index 9620de8..814023e 100644
--- a/gdb/psymtab.c
+++ b/gdb/psymtab.c
@@ -135,6 +135,10 @@ partial_map_expand_apply (struct objfile *objfile,
 {
   struct symtab *last_made = objfile->symtabs;
 
+  /* Shared psymtabs should never be seen here.  Instead they should
+     be handled properly by the caller.  */
+  gdb_assert (pst->user == NULL);
+
   /* Don't visit already-expanded psymtabs.  */
   if (pst->readin)
     return 0;
@@ -165,6 +169,11 @@ partial_map_symtabs_matching_filename (struct objfile *objfile,
 
   ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, pst)
   {
+    /* We can skip shared psymtabs here, because any file name will be
+       attached to the unshared psymtab.  */
+    if (pst->user != NULL)
+      continue;
+
     if (FILENAME_CMP (name, pst->filename) == 0
 	|| (!is_abs && compare_filenames_for_search (pst->filename,
 						     name, name_len)))
@@ -760,6 +769,11 @@ lookup_partial_symbol (struct partial_symtab *pst, const char *name,
 static struct symtab *
 psymtab_to_symtab (struct partial_symtab *pst)
 {
+  /* If it is a shared psymtab, find an unshared psymtab that includes
+     it.  Any such psymtab will do.  */
+  while (pst->user != NULL)
+    pst = pst->user;
+
   /* If it's been looked up before, return it.  */
   if (pst->symtab)
     return pst->symtab;
@@ -1000,6 +1014,12 @@ dump_psymtab (struct objfile *objfile, struct partial_symtab *psymtab,
       fprintf_filtered (outfile, " %s\n",
 			psymtab->dependencies[i]->filename);
     }
+  if (psymtab->user != NULL)
+    {
+      fprintf_filtered (outfile, "  Shared partial symtab with user ");
+      gdb_print_host_address (psymtab->user, outfile);
+      fprintf_filtered (outfile, "\n");
+    }
   if (psymtab->n_global_syms > 0)
     {
       print_partial_symbols (gdbarch,
@@ -1236,6 +1256,94 @@ map_matching_symbols_psymtab (const char *name, domain_enum namespace,
     }
 }	    
 
+/* A helper for expand_symtabs_matching_via_partial that handles
+   searching included psymtabs.  This returns 1 if a symbol is found,
+   and zero otherwise.  It also updates the 'searched_flag' on the
+   various psymtabs that it searches.  */
+
+static int
+recursively_search_psymtabs (struct partial_symtab *ps,
+			     struct objfile *objfile,
+			     enum search_domain kind,
+			     int (*name_matcher) (const char *, void *),
+			     void *data)
+{
+  struct partial_symbol **psym;
+  struct partial_symbol **bound, **gbound, **sbound;
+  int keep_going = 1;
+  int result = PST_SEARCHED_AND_NOT_FOUND;
+  int i;
+
+  if (ps->searched_flag != PST_NOT_SEARCHED)
+    return ps->searched_flag == PST_SEARCHED_AND_FOUND;
+
+  /* Recurse into shared psymtabs first, because they may have already
+     been searched, and this could save some time.  */
+  for (i = 0; i < ps->number_of_dependencies; ++i)
+    {
+      int r;
+
+      /* Skip non-shared dependencies, these are handled elsewhere.  */
+      if (ps->dependencies[i]->user == NULL)
+	continue;
+
+      r = recursively_search_psymtabs (ps->dependencies[i],
+				       objfile, kind, name_matcher, data);
+      if (r != 0)
+	{
+	  ps->searched_flag = PST_SEARCHED_AND_FOUND;
+	  return 1;
+	}
+    }
+
+  gbound = (objfile->global_psymbols.list
+	    + ps->globals_offset + ps->n_global_syms);
+  sbound = (objfile->static_psymbols.list
+	    + ps->statics_offset + ps->n_static_syms);
+  bound = gbound;
+
+  /* Go through all of the symbols stored in a partial
+     symtab in one loop.  */
+  psym = objfile->global_psymbols.list + ps->globals_offset;
+  while (keep_going)
+    {
+      if (psym >= bound)
+	{
+	  if (bound == gbound && ps->n_static_syms != 0)
+	    {
+	      psym = objfile->static_psymbols.list + ps->statics_offset;
+	      bound = sbound;
+	    }
+	  else
+	    keep_going = 0;
+	  continue;
+	}
+      else
+	{
+	  QUIT;
+
+	  if ((kind == ALL_DOMAIN
+	       || (kind == VARIABLES_DOMAIN
+		   && SYMBOL_CLASS (*psym) != LOC_TYPEDEF
+		   && SYMBOL_CLASS (*psym) != LOC_BLOCK)
+	       || (kind == FUNCTIONS_DOMAIN
+		   && SYMBOL_CLASS (*psym) == LOC_BLOCK)
+	       || (kind == TYPES_DOMAIN
+		   && SYMBOL_CLASS (*psym) == LOC_TYPEDEF))
+	      && (*name_matcher) (SYMBOL_SEARCH_NAME (*psym), data))
+	    {
+	      /* Found a match, so notify our caller.  */
+	      result = PST_SEARCHED_AND_FOUND;
+	      keep_going = 0;
+	    }
+	}
+      psym++;
+    }
+
+  ps->searched_flag = result;
+  return result == PST_SEARCHED_AND_FOUND;
+}
+
 static void
 expand_symtabs_matching_via_partial
   (struct objfile *objfile,
@@ -1246,60 +1354,27 @@ expand_symtabs_matching_via_partial
 {
   struct partial_symtab *ps;
 
+  /* Clear the search flags.  */
   ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, ps)
     {
-      struct partial_symbol **psym;
-      struct partial_symbol **bound, **gbound, **sbound;
-      int keep_going = 1;
+      ps->searched_flag = PST_NOT_SEARCHED;
+    }
 
+  ALL_OBJFILE_PSYMTABS_REQUIRED (objfile, ps)
+    {
       if (ps->readin)
 	continue;
 
-      if (file_matcher && ! (*file_matcher) (ps->filename, data))
+      /* We skip shared psymtabs because file-matching doesn't apply
+	 to them; but we search them later in the loop.  */
+      if (ps->user != NULL)
 	continue;
 
-      gbound = objfile->global_psymbols.list
-	+ ps->globals_offset + ps->n_global_syms;
-      sbound = objfile->static_psymbols.list
-	+ ps->statics_offset + ps->n_static_syms;
-      bound = gbound;
+      if (file_matcher && ! (*file_matcher) (ps->filename, data))
+	continue;
 
-      /* Go through all of the symbols stored in a partial
-	 symtab in one loop.  */
-      psym = objfile->global_psymbols.list + ps->globals_offset;
-      while (keep_going)
-	{
-	  if (psym >= bound)
-	    {
-	      if (bound == gbound && ps->n_static_syms != 0)
-		{
-		  psym = objfile->static_psymbols.list + ps->statics_offset;
-		  bound = sbound;
-		}
-	      else
-		keep_going = 0;
-	      continue;
-	    }
-	  else
-	    {
-	      QUIT;
-
-	      if ((kind == ALL_DOMAIN
-		   || (kind == VARIABLES_DOMAIN
-		       && SYMBOL_CLASS (*psym) != LOC_TYPEDEF
-		       && SYMBOL_CLASS (*psym) != LOC_BLOCK)
-		   || (kind == FUNCTIONS_DOMAIN
-		       && SYMBOL_CLASS (*psym) == LOC_BLOCK)
-		   || (kind == TYPES_DOMAIN
-		       && SYMBOL_CLASS (*psym) == LOC_TYPEDEF))
-		  && (*name_matcher) (SYMBOL_SEARCH_NAME (*psym), data))
-		{
-		  psymtab_to_symtab (ps);
-		  keep_going = 0;
-		}
-	    }
-	  psym++;
-	}
+      if (recursively_search_psymtabs (ps, objfile, kind, name_matcher, data))
+	psymtab_to_symtab (ps);
     }
 }
 
-- 
1.7.7.6