WIP mul64 dlsym optimization

Change-Id: I4caf4f14deb7a106c17e3ca89bdff5cd89f9541b

elf/dl-lookup.c

@@ -28,6 +28,7 @@
 #include <libc-lock.h>
 #include <tls.h>
 #include <atomic.h>
+#include <divopt.h>
 
 #include <assert.h>
 
@@ -394,8 +395,17 @@ do_lookup_x (const char *undef_name, uint_fast32_t new_hash,
 	  if (__glibc_unlikely ((bitmask_word >> hashbit1)
 				& (bitmask_word >> hashbit2) & 1))
 	    {
-	      Elf32_Word bucket = map->l_gnu_buckets[new_hash
-						     % map->l_nbuckets];
+	      Elf32_Word bucket;
+	      if (powerof2 (map->l_nbuckets))
+		bucket = map->l_gnu_buckets[new_hash & (map->l_nbuckets - 1)];
+	      else
+		{
+		  uint32_t quotient
+		    = ((unsigned __int128) map->l_nbuckets_multiplier * ((uint64_t) new_hash + 1)) >> 64;
+		  uint32_t remainder = new_hash - map->l_nbuckets * quotient;
+		  bucket = map->l_gnu_buckets[remainder];
+		}
+
 	      if (bucket != 0)
 		{
 		  const Elf32_Word *hasharr = &map->l_gnu_chain_zero[bucket];
@@ -931,6 +941,10 @@ _dl_setup_hash (struct link_map *map)
       /* Initialize MIPS xhash translation table.  */
       ELF_MACHINE_XHASH_SETUP (hash32, symbias, map);
 
+      if (powerof2 (map->l_nbuckets))
+	map->l_nbuckets_multiplier = __builtin_ctz (map->l_nbuckets);
+      else
+	map->l_nbuckets_multiplier = ((unsigned __int128) 1 << 64) / map->l_nbuckets;
       return;
     }
 

elf/dl-sym.c

@@ -80,6 +80,18 @@ call_dl_lookup (void *ptr)
 					args->flags, NULL);
 }
 
+/* Return the link map containing the caller address.  */
+static inline struct link_map *
+find_caller_link_map (ElfW(Addr) caller)
+{
+  struct link_map *l = _dl_find_dso_for_object (caller);
+  if (l != NULL)
+    return l;
+  else
+    /* If the address is not recognized the call comes from the main
+       program (we hope).  */
+    return GL(dl_ns)[LM_ID_BASE]._ns_loaded;
+}
 
 static void *
 do_sym (void *handle, const char *name, void *who,
@@ -89,13 +101,13 @@ do_sym (void *handle, const char *name, void *who,
   lookup_t result;
   ElfW(Addr) caller = (ElfW(Addr)) who;
 
-  struct link_map *l = _dl_find_dso_for_object (caller);
-  /* If the address is not recognized the call comes from the main
-     program (we hope).  */
-  struct link_map *match = l ? l : GL(dl_ns)[LM_ID_BASE]._ns_loaded;
+  /* Link map of the caller if needed.  */
+  struct link_map *match = NULL;
 
   if (handle == RTLD_DEFAULT)
     {
+      match = find_caller_link_map (caller);
+
       /* Search the global scope.  We have the simple case where
 	 we look up in the scope of an object which was part of
 	 the initial binary.  And then the more complex part
@@ -128,6 +140,8 @@ do_sym (void *handle, const char *name, void *who,
     }
   else if (handle == RTLD_NEXT)
     {
+      match = find_caller_link_map (caller);
+
       if (__glibc_unlikely (match == GL(dl_ns)[LM_ID_BASE]._ns_loaded))
 	{
 	  if (match == NULL
@@ -187,6 +201,9 @@ RTLD_NEXT used in code not dynamically loaded"));
 	  unsigned int ndx = (ref - (ElfW(Sym) *) D_PTR (result,
 							 l_info[DT_SYMTAB]));
 
+	  if (match == NULL)
+	    match = find_caller_link_map (caller);
+
 	  if ((match->l_audit_any_plt | result->l_audit_any_plt) != 0)
 	    {
 	      unsigned int altvalue = 0;

include/divopt.h

@@ -0,0 +1,78 @@
+/* Optimization of repeated integer division.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <https://www.gnu.org/licenses/>.  */
+
+#include <stdint.h>
+#include <sys/param.h>
+
+/* Precompute *MULTIPLIER for dividing by DIVISOR, which must be two
+   or larger, and return the shift count (non-negative and less than
+   32), for use with divopt_32 below.  */
+static int __attribute__ ((used))
+precompute_divopt_32 (uint32_t divisor, uint32_t *multiplier)
+{
+  if (divisor == 1)
+    {
+      *multiplier = 1;
+      return 0;
+    }
+
+  int log2 = 32 - __builtin_clz (divisor);
+
+  /* Handle powers-of-two first, so that we do not need to deal with
+     the clz corner cases below.  */
+  if (powerof2 (divisor))
+    {
+      *multiplier = 1;
+      return log2 - 2;
+    }
+
+  if (log2 != 32)
+    {
+      /* Compute ceil (2**(32 + log2) / divisor).  The
+         most-significant bit is always set and is discarded.  */
+      *multiplier = (((uint64_t) 1 << (32 + log2)) + divisor) / divisor;
+      return log2 - 1;
+    }
+  else
+    {
+      /* Perform a long division of 2**64 + (divisor - 1) by the
+         divisor, encoded in base-2**32, using a 64-by-32 division.
+         Start out with the first two digits, which are (1, 0).  2**32
+         divided by the divisor is 1 because the divisor is larger
+         than 2**31.  This set bit is discarded.  */
+      uint64_t remainder = -divisor;
+
+      /* Combine the remainder of the first division with the third
+         and final base 2**32 digit.  */
+      *multiplier = ((remainder << 32) | (divisor - 1)) / divisor;
+      return 31;
+    }
+}
+
+/* Return the quotient of DIVIDEND devided by the divisor that was
+   used to compute MULTIPLIER and SHIFT via precompute_divopt_32.  */
+static inline uint32_t
+divopt_32 (uint32_t dividend, uint32_t multiplier, int shift)
+{
+  /* Approximation to the quotient.  */
+  uint32_t quotient = ((uint64_t) dividend * multiplier) >> 32;
+  /* Compute (dividend + quotient) / 2 without overflow.  */
+  uint32_t temp = ((dividend - quotient) >> 1) + quotient;
+  /* The result is in the higher-order bits.  */
+  return temp >> shift;
+}

include/link.h

@@ -153,6 +153,7 @@ struct link_map
 
     /* Symbol hash table.  */
     Elf_Symndx l_nbuckets;
+    uint64_t l_nbuckets_multiplier;
     Elf32_Word l_gnu_bitmask_idxbits;
     Elf32_Word l_gnu_shift;
     const ElfW(Addr) *l_gnu_bitmask;