* ld: Avoid overflows in string merging @ 2023-11-07 16:51 Michael Matz 2023-11-08 7:30 ` Jan Beulich 0 siblings, 1 reply; 8+ messages in thread From: Michael Matz @ 2023-11-07 16:51 UTC (permalink / raw) To: binutils 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: ld: Avoid overflows in string merging 2023-11-07 16:51 ld: Avoid overflows in string merging Michael Matz @ 2023-11-08 7:30 ` Jan Beulich 2023-11-08 14:31 ` Michael Matz 0 siblings, 1 reply; 8+ messages in thread From: Jan Beulich @ 2023-11-08 7:30 UTC (permalink / raw) To: Michael Matz; +Cc: binutils 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: ld: Avoid overflows in string merging 2023-11-08 7:30 ` Jan Beulich @ 2023-11-08 14:31 ` Michael Matz 2023-11-08 16:16 ` Michael Matz 2023-11-09 7:52 ` Jan Beulich 0 siblings, 2 replies; 8+ messages in thread From: Michael Matz @ 2023-11-08 14:31 UTC (permalink / raw) To: Jan Beulich; +Cc: binutils 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. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: ld: Avoid overflows in string merging 2023-11-08 14:31 ` Michael Matz @ 2023-11-08 16:16 ` Michael Matz 2023-11-09 7:55 ` Jan Beulich 2023-11-09 7:52 ` Jan Beulich 1 sibling, 1 reply; 8+ messages in thread From: Michael Matz @ 2023-11-08 16:16 UTC (permalink / raw) To: Jan Beulich; +Cc: binutils 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. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: ld: Avoid overflows in string merging 2023-11-08 16:16 ` Michael Matz @ 2023-11-09 7:55 ` Jan Beulich 0 siblings, 0 replies; 8+ messages in thread From: Jan Beulich @ 2023-11-09 7:55 UTC (permalink / raw) To: Michael Matz; +Cc: binutils 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: ld: Avoid overflows in string merging 2023-11-08 14:31 ` Michael Matz 2023-11-08 16:16 ` Michael Matz @ 2023-11-09 7:52 ` Jan Beulich 2023-11-09 16:27 ` Michael Matz 1 sibling, 1 reply; 8+ messages in thread From: Jan Beulich @ 2023-11-09 7:52 UTC (permalink / raw) To: Michael Matz; +Cc: binutils 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: ld: Avoid overflows in string merging 2023-11-09 7:52 ` Jan Beulich @ 2023-11-09 16:27 ` Michael Matz 2023-11-10 10:10 ` Jan Beulich 0 siblings, 1 reply; 8+ messages in thread From: Michael Matz @ 2023-11-09 16:27 UTC (permalink / raw) To: Jan Beulich; +Cc: binutils 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. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: ld: Avoid overflows in string merging 2023-11-09 16:27 ` Michael Matz @ 2023-11-10 10:10 ` Jan Beulich 0 siblings, 0 replies; 8+ messages in thread From: Jan Beulich @ 2023-11-10 10:10 UTC (permalink / raw) To: Michael Matz; +Cc: binutils 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2023-11-10 10:11 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2023-11-07 16:51 ld: Avoid overflows in string merging Michael Matz 2023-11-08 7:30 ` Jan Beulich 2023-11-08 14:31 ` Michael Matz 2023-11-08 16:16 ` Michael Matz 2023-11-09 7:55 ` Jan Beulich 2023-11-09 7:52 ` Jan Beulich 2023-11-09 16:27 ` Michael Matz 2023-11-10 10:10 ` Jan Beulich
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).