ld: Avoid overflows in string merging

[Michael Matz]

Hello,

On Wed, 8 Nov 2023, Jan Beulich wrote:

> > --- a/bfd/merge.c
> > +++ b/bfd/merge.c
> > @@ -167,7 +167,7 @@ static bool
> >  sec_merge_maybe_resize (struct sec_merge_hash *table, unsigned added)
> >  {
> >    struct bfd_hash_table *bfdtab = &table->table;
> > -  if (bfdtab->count + added > table->nbuckets * 2 / 3)
> > +  if (bfdtab->count + added > table->nbuckets / 3 * 2)
> >      {
> >        unsigned i;
> >        unsigned long newnb = table->nbuckets * 2;
> > @@ -175,7 +175,7 @@ sec_merge_maybe_resize (struct sec_merge_hash *table, unsigned added)
> >        uint64_t *newl;
> >        unsigned long alloc;
> >  
> > -      while (bfdtab->count + added > newnb * 2 / 3)
> > +      while (bfdtab->count + added > newnb / 3 * 2)
> >  	{
> >  	  newnb *= 2;
> >  	  if (!newnb)
> 
> Isn't this overly aggressive? We want to resize when past two thirds,
> but why would we go by two thirds even within this loop?

Because doubling newnb once doesn't ensure that count+added will fit.  
Consider count==1, oldbuckets==0x2000, and added==1<<24.  The above loop 
seemed more obvious to me than the other method: bit magic to round up 
(count+added)*3/2 to next power of two (which still would need a loop).

> We've doubled once already, and all we care about is that new capacity 
> be enough to cover "added". The more that - as the comment there says - 
> the caller already overestimates heavily.
> 
> Even that estimate could do with tweaking.

Yes.  As you say, there can be max. 255 one-char strings, and 65535 
two-char strings (and so on), making for a better estimation divider of 3 
starting with section sizes of 512 (and so on).  But in the grand scheme, 
and if it weren't for the bug, whatever is over-estimated at one time will 
likely be used up at a later time (of course it will remain waste when it 
so happens to be one of the last input sections).  Fixing the estimation 
would merely mean a reallocation a little later.  Back at the time I 
measured the overall waste and while it could have been better it wasn't 
terrible either.

In the bug report case we hit an extreme: it has a 2GB input string 
section, that turns out to be only adding 750k new strings.  Whatever 
method I had used to estimate, it still would have been grossly off: a 2GB 
section could contain 429m invididual four-byte strings (i.e. 5 bytes with 
the terminator), so that's the lowest number any estimation could validly 
produce, and it would be off by a factor of 1000.

> Otoh aren't we also at risk of underestimating when entsize == 1 and
> we're not dealing with strings?

Hmm, that's true.  I need to fix that.

> > @@ -240,7 +240,7 @@ sec_merge_hash_insert (struct sec_merge_hash *table,
> >    hashp->u.suffix = NULL;
> >    hashp->next = NULL;
> >    // We must not need resizing, otherwise _index is wrong
> > -  BFD_ASSERT (bfdtab->count + 1 <= table->nbuckets * 2 / 3);
> > +  BFD_ASSERT (bfdtab->count + 1 <= table->nbuckets / 3 * 2);
> >    bfdtab->count++;
> >    table->key_lens[_index] = (hash << 32) | (uint32_t)len;
> >    table->values[_index] = hashp;
> 
> I'm puzzled by both comment and assertion here: Afaict we're past
> resizing already, and hence all that matters is that the new index
> is within table boundaries.

But as the resize is based on an estimation this assert makes sure that it 
was in fact a conservative estimation.  E.g. that assert would trigger in 
the case you worry about above: non-strings entsize==1, and 
underestimated.

The comment mentioning _index being wrong is indeed outdated, though.  
There was a time when I did resize the hash table when necessary (instead 
of the assert), eventually I precomputed _index in the caller which would 
have been invalidated if it was in fact resized (because nbuckets would 
have changed); that's what the comment still refers to.  When I removed 
the resizing (and replaced with an assert) I didn't update the comment.  
I'll update it to "We must not need resizing, the estimation has to be 
conservatively correct" or suchlike.

> Further, the same expression occurring three times (and now needing
> updating consistently) pretty clearly calls for putting in a macro
> or function. (Assuming of course the same calculation remains to
> be there three times, which may not be the case as per above.)

Agreed, I'll do that before pushing.

> Finally, is using unsigned int variables / fields actually
> appropriate when BFD64 and hence section sizes can be wider than 32
> bits?

They can be larger, and in that case they won't be part of the whole 
section merging.  That's a conscious decision.  The code is so terribly 
performance sensitive that even cache pressure matters and going from 32 
to 64bit for the offsets has a non-trivial cost that I wasn't willing for 
everyone reasonable to pay to cater for the crazy cases.  At some point in 
time this might need revisiting, with a whole bunch of benchmarking and 
pondering if it's really worth it.  IMHO we aren't there yet.

I'll change the comment and use a macro for the calculation, then push.  
I'm trying to come up with a testcase for the underestimation plus fix 
separately.  Thanks for the review.


Ciao,
Michael.