Re: _bfd_link_section_stabs: hash value weakness

[Daniel Jacobowitz <drow at mvista dot com>]

On Sun, Sep 15, 2002 at 01:00:04AM -0700, Ian Lance Taylor wrote:
> "Paul N. Hilfinger" <hilfingr@otisco.mckusick.com> writes:
> 
> > Forgive me if, as a newcomer, I heedlessly stumble over an over-
> > discussed issue.  I recently encountered a case (on Linux) in which
> > STABS data in several .o files for a certain header file were
> > improperly merged in the executable.  That is, the version of the
> > STABS data for one include file from one .o file was removed, and
> > replaced with an EXCL reference to the STABS data for the same include
> > file from another .o file, even though the two versions were not, in
> > fact identical (specifically, the type indices did not quite agree).
> 
> This normally only happens when you're doing something odd, like using
> the same name for two different objects.  Can you describe the failure
> in more detail?
> 
> You can always use --traditional to avoid the problem.
> 
> > A little rooting around led quickly to _bfd_line_section_stabs, which uses
> > a simple hashing scheme to determine if two versions of data between
> > matching BINCL and EINCL entries are identical.  The problem is that the
> > hashing scheme is a little TOO simple: simply remove all file numbers
> > from the type references and then add all character values.  
> > 
> > Is mine really the ONLY instance of this sort of collision?  If so,
> > I'm a little surprised: that particular hashing algorithm is example
> > #1 of a bad hashing function that I use when teaching data structures
> > classes!  Admittedly, for this particular purpose, I'd expect it
> > usually to work, and it IS really simple.  On the other hand, when
> > there is a collision, the results are rather mysterious and annoying.
> > Has there been any discussion of using a slightly stronger hashing
> > function?  I don't think time is an issue; my workstation can do an
> > MD5 checksum of 18MBytes in 0.3 sec, and a MUCH simpler hash function
> > than that would do a fine job in this application.
> 
> The idea and the implementation, including the hash function used, are
> taken from Solaris.  That's not to say that it couldn't be done
> differently; it's just the explanation for why that particular hash
> function was chosen.

I'm not sure how often this could ever work, in practice, in a large
application.  The type numbers must depend on the include hierarchy. 
If you look at the sample Paul posted, the difference is that one of
them has an earlier header defining 'struct value' and the other has an
earlier header just declaring 'struct value;' and leaving it at that. 
Thus the "xs" stab, in evaluate_exp.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer