ld: Avoid overflows in string merging

ld: Avoid overflows in string merging

[Michael Matz]

as the bug report shows we had an overflow in the test if
hash table resizing is needed.  Reorder the expression to avoid
that.  There's still a bug somewhere in gracefully handling
failure in resizing (e.g. out of memory), but this pushes the
boundary for that occurring somewhen into the future and
immediately helps the reporter.

    bfd/

    PR ld/31009
    * merge.c (sec_merge_maybe_resize): Avoid overflow in expression.
    (sec_merge_hash_insert): Adjust assert.
---

regtested on many targets, okay for master?


 bfd/merge.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/bfd/merge.c b/bfd/merge.c
index 722e6659486..4aa2f838679 100644
--- 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)
@@ -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;
-- 
2.42.0

Re: ld: Avoid overflows in string merging

[Jan Beulich]

On 07.11.2023 17:51, Michael Matz wrote:
> as the bug report shows we had an overflow in the test if
> hash table resizing is needed.  Reorder the expression to avoid
> that.  There's still a bug somewhere in gracefully handling
> failure in resizing (e.g. out of memory), but this pushes the
> boundary for that occurring somewhen into the future and
> immediately helps the reporter.
> 
>     bfd/
> 
>     PR ld/31009
>     * merge.c (sec_merge_maybe_resize): Avoid overflow in expression.
>     (sec_merge_hash_insert): Adjust assert.
> ---
> 
> regtested on many targets, okay for master?

This is an improvement, so okay to put in, but:

> --- 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? 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. For small sections,
assuming there may be relatively many very short strings is certainly
okay. But there can be only 255 of them (for 8-bit chars). So for
larger sections, the estimate could surely be more realistic.

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

> @@ -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.

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.)

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

Jan

Re: 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.

Re: ld: Avoid overflows in string merging

[Michael Matz]

Hey,

On Wed, 8 Nov 2023, Michael Matz wrote:

> > 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.

Ah, no.  I remember: the nr of buckets starts out as 0x2000, which is 
impossible to reach by distinct size 1 entities, no matter how 
underestimating the estimation is.  So, it's confusing but not wrong :)


Ciao,
Michael.

Re: ld: Avoid overflows in string merging

[Jan Beulich]

On 08.11.2023 15:31, Michael Matz wrote:
> 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).

I didn't mean to suggest to remove the loop. What I was getting at is that
the loop condition is more strict that necessary, as I tried to explain ...

>> 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.

... here. The "whether" is deliberately at 2/3 aiui, and that's fine. The
"how much", however, could be reduced to the next power of 2 that fits, to
avoid excessive growth.

Jan

Re: ld: Avoid overflows in string merging

[Jan Beulich]

On 08.11.2023 17:16, Michael Matz wrote:
> On Wed, 8 Nov 2023, Michael Matz wrote:
> 
>>> 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.
> 
> Ah, no.  I remember: the nr of buckets starts out as 0x2000, which is 
> impossible to reach by distinct size 1 entities, no matter how 
> underestimating the estimation is.  So, it's confusing but not wrong :)

Oh, indeed (should have connected the two things I said in the earlier
reply). That means, though, that for entsize == 1 (and not strings)
there would _never_ be a reason to resize (and, just to extend that
slightly, there would never be a reason to further resize once for
entsize == 2 we've reached 64k entries).

Jan

Re: ld: Avoid overflows in string merging

[Michael Matz]

Hello,

On Thu, 9 Nov 2023, Jan Beulich wrote:

> > 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).
> 
> I didn't mean to suggest to remove the loop. What I was getting at is that
> the loop condition is more strict that necessary, as I tried to explain ...
> 
> >> 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.
> 
> ... here. The "whether" is deliberately at 2/3 aiui, and that's fine. The
> "how much", however, could be reduced to the next power of 2 that fits, to
> avoid excessive growth.

Ah, I see.  So, you had preferred the loop condition (but not the 
if-condition) to be merely
  while (count + added > newnb)
right?  If so, I disagree:
a) on principle grounds: the post-condition of the resize function 
should include that an immediately following resize with same args should 
do nothing.
b) on practical grounds: this is (deliberately) an internal hash 
structure, and that degrades terribly when it's almost full; so the post 
condition of the resize has to be "even if we added this many elements it 
still would only be 66% full".  I.e. no, we don't just care about the new 
capacity covering the newly added stuff, it has to well over-cover it, if 
that's a word :-)

We could talk about the concrete percentage, 75% for instance would still 
be reasonable, maybe even higher given that the hash function itself is 
relatively good.  But the resize function needs to be exited such that the 
bucket list definitely remains reasonably sparse even if all the input 
elements turn out to be distinct.

(When seeing it together with the heavy overestimating I see the point of 
course, but any change in that should tackle the estimation, not the 
resize function).


Ciao,
Michael.

Re: ld: Avoid overflows in string merging

[Jan Beulich]

On 09.11.2023 17:27, Michael Matz wrote:
> On Thu, 9 Nov 2023, Jan Beulich wrote:
> 
>>> 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).
>>
>> I didn't mean to suggest to remove the loop. What I was getting at is that
>> the loop condition is more strict that necessary, as I tried to explain ...
>>
>>>> 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.
>>
>> ... here. The "whether" is deliberately at 2/3 aiui, and that's fine. The
>> "how much", however, could be reduced to the next power of 2 that fits, to
>> avoid excessive growth.
> 
> Ah, I see.  So, you had preferred the loop condition (but not the 
> if-condition) to be merely
>   while (count + added > newnb)
> right?  If so, I disagree:
> a) on principle grounds: the post-condition of the resize function 
> should include that an immediately following resize with same args should 
> do nothing.
> b) on practical grounds: this is (deliberately) an internal hash 
> structure, and that degrades terribly when it's almost full; so the post 
> condition of the resize has to be "even if we added this many elements it 
> still would only be 66% full".  I.e. no, we don't just care about the new 
> capacity covering the newly added stuff, it has to well over-cover it, if 
> that's a word :-)

Hmm, I see. I will admit that I didn't look at the hash lookup function
at all. Instead when seeing "hash" I assumed "hash" in the (to me) more
conventional sense, where lookup speed doesn't depend on how full the
hash table is, but merely on how long the collision chains are that
hang off of every table entry (and them growing to long then typically
being a sign of a not overly good hash function).

Jan