A gdb+bfd string pool?

A gdb+bfd string pool?

[Andrew Cagney]

Hello,

GDB, to contain its run-time size is, uses gdb/bcaches where ...
/* A bcache is a data structure for factoring out duplication in
    read-only structures.  You give the bcache some string of bytes S.
    If the bcache already contains a copy of S, it hands you back a
    pointer to its copy.  Otherwise, it makes a fresh copy of S, and
    hands you back a pointer to that.  In either case, you can throw
    away your copy of S, and use the bcache's.
One notable feature of this mechanism is that it lets you eliminate 
string equality comparisons - equal bcache values implies equal strings.

Now, if I'm reading the BFD elf reader correctly, elf-strtab implements 
a similar mechanism (But I think it is currently only used by the linker?).

Should/could BFD export a string pool that GDB could use and then use 
that for any slurped symbol names?

Andrew

Re: A gdb+bfd string pool?

[Daniel Jacobowitz]

On Fri, Oct 31, 2003 at 10:15:39AM -0500, Andrew Cagney wrote:
> Hello,
> 
> GDB, to contain its run-time size is, uses gdb/bcaches where ...
> /* A bcache is a data structure for factoring out duplication in
>    read-only structures.  You give the bcache some string of bytes S.
>    If the bcache already contains a copy of S, it hands you back a
>    pointer to its copy.  Otherwise, it makes a fresh copy of S, and
>    hands you back a pointer to that.  In either case, you can throw
>    away your copy of S, and use the bcache's.
> One notable feature of this mechanism is that it lets you eliminate 
> string equality comparisons - equal bcache values implies equal strings.
> 
> Now, if I'm reading the BFD elf reader correctly, elf-strtab implements 
> a similar mechanism (But I think it is currently only used by the linker?).
> 
> Should/could BFD export a string pool that GDB could use and then use 
> that for any slurped symbol names?

Well, if so, it should go in libiberty - and in fact, is the hash table
in libiberty in any way unsuited to replace bcache?

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: A gdb+bfd string pool?

[Andrew Cagney]

> On Fri, Oct 31, 2003 at 10:15:39AM -0500, Andrew Cagney wrote:
> 
>> Hello,
>> 
>> GDB, to contain its run-time size is, uses gdb/bcaches where ...
>> /* A bcache is a data structure for factoring out duplication in
>>    read-only structures.  You give the bcache some string of bytes S.
>>    If the bcache already contains a copy of S, it hands you back a
>>    pointer to its copy.  Otherwise, it makes a fresh copy of S, and
>>    hands you back a pointer to that.  In either case, you can throw
>>    away your copy of S, and use the bcache's.
>> One notable feature of this mechanism is that it lets you eliminate 
>> string equality comparisons - equal bcache values implies equal strings.
>> 
>> Now, if I'm reading the BFD elf reader correctly, elf-strtab implements 
>> a similar mechanism (But I think it is currently only used by the linker?).
>> 
>> Should/could BFD export a string pool that GDB could use and then use 
>> that for any slurped symbol names?
> 
> 
> Well, if so, it should go in libiberty - and in fact, is the hash table
> in libiberty in any way unsuited to replace bcache?

The interface or the implementation?  The bcache interface is focused 
and simple (something that can't be said for that hash table).  The 
hashtab could certainly be used in the implementation (as elf-strtab did).

Anyway, back to the question.  Does a [global] common pool make sense 
for BFD?

Andrew

Re: A gdb+bfd string pool?

[Daniel Jacobowitz]

On Fri, Oct 31, 2003 at 10:45:43AM -0500, Andrew Cagney wrote:
> >On Fri, Oct 31, 2003 at 10:15:39AM -0500, Andrew Cagney wrote:
> >
> >>Hello,
> >>
> >>GDB, to contain its run-time size is, uses gdb/bcaches where ...
> >>/* A bcache is a data structure for factoring out duplication in
> >>   read-only structures.  You give the bcache some string of bytes S.
> >>   If the bcache already contains a copy of S, it hands you back a
> >>   pointer to its copy.  Otherwise, it makes a fresh copy of S, and
> >>   hands you back a pointer to that.  In either case, you can throw
> >>   away your copy of S, and use the bcache's.
> >>One notable feature of this mechanism is that it lets you eliminate 
> >>string equality comparisons - equal bcache values implies equal strings.
> >>
> >>Now, if I'm reading the BFD elf reader correctly, elf-strtab implements 
> >>a similar mechanism (But I think it is currently only used by the 
> >>linker?).
> >>
> >>Should/could BFD export a string pool that GDB could use and then use 
> >>that for any slurped symbol names?
> >
> >
> >Well, if so, it should go in libiberty - and in fact, is the hash table
> >in libiberty in any way unsuited to replace bcache?
> 
> The interface or the implementation?  The bcache interface is focused 
> and simple (something that can't be said for that hash table).  The 
> hashtab could certainly be used in the implementation (as elf-strtab did).

So does gdb/symtab.c.

> Anyway, back to the question.  Does a [global] common pool make sense 
> for BFD?

Oh, you meant an _instance_, not a data structure.  Sorry.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer

Re: A gdb+bfd string pool?

[Andrew Cagney]

>> The interface or the implementation?  The bcache interface is focused 
>> and simple (something that can't be said for that hash table).  The 
>> hashtab could certainly be used in the implementation (as elf-strtab did).
> 
> 
> So does gdb/symtab.c.
> 
> 
>> Anyway, back to the question.  Does a [global] common pool make sense 
>> for BFD?
> 
> 
> Oh, you meant an _instance_, not a data structure.  Sorry.

More specifically, a single instance.  Instead of having something like 
a per-object file symbol bcache as was done with GDB, there would just 
be a single global bcache (and it would never shrink).

Andrew

Re: A gdb+bfd string pool?

[Jakub Jelinek]

On Fri, Oct 31, 2003 at 12:29:03PM -0500, Andrew Cagney wrote:
> 
> >>The interface or the implementation?  The bcache interface is focused 
> >>and simple (something that can't be said for that hash table).  The 
> >>hashtab could certainly be used in the implementation (as elf-strtab did).
> >
> >
> >So does gdb/symtab.c.
> >
> >
> >>Anyway, back to the question.  Does a [global] common pool make sense 
> >>for BFD?
> >
> >
> >Oh, you meant an _instance_, not a data structure.  Sorry.
> 
> More specifically, a single instance.  Instead of having something like 
> a per-object file symbol bcache as was done with GDB, there would just 
> be a single global bcache (and it would never shrink).

elf-strtab has a property which I'm not sure you really need in GDB,
as it slow things down.  It attempts to do suffix merging, ie. if you have
p = "abcde" and q = "cde", r = "cde", s = "abcde" strings,
then p = "abcde", q = p + 2, r = q, s = p.  Storing strings in a hashtable
is certainly cheaper for CPU time than this.

	Jakub

Re: A gdb+bfd string pool?

[Andrew Cagney]

>>> Oh, you meant an _instance_, not a data structure.  Sorry.
> 
>> 
>> More specifically, a single instance.  Instead of having something like 
>> a per-object file symbol bcache as was done with GDB, there would just 
>> be a single global bcache (and it would never shrink).
> 
> 
> elf-strtab has a property which I'm not sure you really need in GDB,
> as it slow things down.  It attempts to do suffix merging, ie. if you have
> p = "abcde" and q = "cde", r = "cde", s = "abcde" strings,
> then p = "abcde", q = p + 2, r = q, s = p.  Storing strings in a hashtable
> is certainly cheaper for CPU time than this.

As best I could tell, the suffix merging was being done as a separate 
pass so could be separated out?

Andrew

Re: A gdb+bfd string pool?

[David Carlton]

On Fri, 31 Oct 2003 10:15:39 -0500, Andrew Cagney <ac131313@redhat.com> said:

> Should/could BFD export a string pool that GDB could use and then
> use that for any slurped symbol names?

Personally, I'd be against this unless we have reason to believe that
it's an important optimization.  I don't like global data in general,
even if it's only global to one component of a program, and having
that data shared by both GDB and BFD makes me even more nervous.
(Singleton is not my favorite design pattern.)  So it sets of warning
bells for general design reasons; our lack of const-correctness when
dealing with names makes me even more nervous.

David Carlton
carlton@kealia.com

Re: A gdb+bfd string pool?

[Joel Brobecker]

> Personally, I'd be against this unless we have reason to believe that
> it's an important optimization.  I don't like global data in general,
> even if it's only global to one component of a program, and having
> that data shared by both GDB and BFD makes me even more nervous.
> (Singleton is not my favorite design pattern.)  So it sets of warning
> bells for general design reasons; our lack of const-correctness when
> dealing with names makes me even more nervous.

I have the exact same feeling.

May I recommend that, should we decide to use one, we isolate it from
GDB's code via a layer. So each module would use it's layer as if it was
not shared. It will make the move back easier, in case it's ever needed.

-- 
Joel

Re: A gdb+bfd string pool?

[Andrew Cagney]

> Personally, I'd be against this unless we have reason to believe that
>> it's an important optimization.  I don't like global data in general,
>> even if it's only global to one component of a program, and having
>> that data shared by both GDB and BFD makes me even more nervous.
>> (Singleton is not my favorite design pattern.)  So it sets of warning
>> bells for general design reasons; our lack of const-correctness when
>> dealing with names makes me even more nervous.
> 
> 
> I have the exact same feeling.
> 
> May I recommend that, should we decide to use one, we isolate it from
> GDB's code via a layer. So each module would use it's layer as if it was
> not shared. It will make the move back easier, in case it's ever needed.

Ok, ok, I've been sufficiently beaten to a pulp :-)

I've also come across a reason that a single pool may not be such a good 
idea.  GDB had (it broke >4 years ago and is now beyond repair) a 
technique for caching per-object data on a memory-mapped disk.  Having 
the objfile symbol table point into a shared pool would make any future 
plans to re-implement that technique unworkable.

enjoy,
Andrew

Re: A gdb+bfd string pool?

[Andrew Cagney]

> our lack of const-correctness when
> dealing with names makes me even more nervous.

Can someone please convince me that this ...

> struct partial_symbol *
> fixup_psymbol_section (struct partial_symbol *psym, struct objfile *objfile)
> {
>   if (!psym)
>     return NULL;
> 
>   if (SYMBOL_BFD_SECTION (psym))
>     return psym;
> 
>   fixup_section (&psym->ginfo, objfile);
> 
>   return psym;
> }

and this:

> 	if (SYMBOL_SECTION (*psym) >= 0)
> 	  SYMBOL_VALUE_ADDRESS (*psym) += ANOFFSET (delta,

aren't modifying the bcached minimal symbol? :-(

Andrew