PR32260: Improve estimate of number of strings

[Michael Matz]

we want to pre-size the hashtable for mergable strings,
and so need an estimate for the number of them in one input
section.  This reduces the over-estimation a little.

	bfd/

	PR ld/32260
	* merge.c (record_section): Throttle down the overestimation
	of number of entries in a section.
---
Tested without regressions on Alans list of targets.  Okay for master?

 bfd/merge.c | 34 +++++++++++++++++++++++++++++++++-
 1 file changed, 33 insertions(+), 1 deletion(-)

diff --git a/bfd/merge.c b/bfd/merge.c
index c811bc57eae..2b4d2e428d4 100644
--- a/bfd/merge.c
+++ b/bfd/merge.c
@@ -736,10 +736,42 @@ record_section (struct sec_merge_info *sinfo,
 
   /* Now populate the hash table and offset mapping.  */
 
+  /* We use an upper bounds of the number of strings that can be
+     possibly contained in this section.  There are a maximum of
+     NMAX=255^n strings of length n, which then need NMAX*(n+1)
+     bytes.  We also know that the section size fits into mapofs_type
+     (i.e. is smaller than 4G).  */
+  mapofs_type nestimate;
+  if (sec->flags & SEC_STRINGS)
+    {
+      mapofs_type nmax, slen, remaining;
+      nestimate = 1;
+      nmax = 255;
+      slen = 2;
+      remaining = sec->size;
+      while (remaining > 0)
+	{
+	  mapofs_type fits = remaining / slen;
+	  if (fits <= nmax)
+	    {
+	      nestimate += fits;
+	      break;
+	    }
+	  nestimate += nmax;
+	  /* Ensure that nmax doesn't overflow.  */
+	  BFD_ASSERT (slen < 5);
+	  remaining -= nmax * slen;
+	  nmax *= 255;
+	  slen++;
+	}
+    }
+  else
+    nestimate = sec->size / sec->entsize;
+
   /* Presize the hash table for what we're going to add.  We overestimate
      quite a bit, but if it turns out to be too much then other sections
      merged into this area will make use of that as well.  */
-  if (!sec_merge_maybe_resize (sinfo->htab, 1 + sec->size / 2))
+  if (!sec_merge_maybe_resize (sinfo->htab, nestimate))
     {
       free (contents);
       return 2;
-- 
2.42.0