ldso/ldso/frv/dl-inlines.h

   1 /* Copyright (C) 2003, 2004 Red Hat, Inc.
   2  * Contributed by Alexandre Oliva <aoliva@redhat.com>
   3  *
   4  * Licensed under the LGPL v2.1, see the file COPYING.LIB in this tarball.
   5  */
   6
   7 #ifndef _dl_assert
   8 # define _dl_assert(expr)
   9 #endif
  10
  11 /* Initialize a DL_LOADADDR_TYPE given a got pointer and a complete
  12    load map.  */
  13 inline static void
  14 __dl_init_loadaddr_map (struct elf32_fdpic_loadaddr *loadaddr, void *got_value,
  15                         struct elf32_fdpic_loadmap *map)
  16 {
  17   if (map->version != 0)
  18     {
  19       SEND_EARLY_STDERR ("Invalid loadmap version number\n");
  20       _dl_exit(-1);
  21     }
  22   if (map->nsegs == 0)
  23     {
  24       SEND_EARLY_STDERR ("Invalid segment count in loadmap\n");
  25       _dl_exit(-1);
  26     }
  27   loadaddr->got_value = got_value;
  28   loadaddr->map = map;
  29 }
  30
  31 /* Figure out how many LOAD segments there are in the given headers,
  32    and allocate a block for the load map big enough for them.
  33    got_value will be properly initialized later on, with INIT_GOT.  */
  34 inline static int
  35 __dl_init_loadaddr (struct elf32_fdpic_loadaddr *loadaddr, Elf32_Phdr *ppnt,
  36                     int pcnt)
  37 {
  38   int count = 0, i;
  39   size_t size;
  40
  41   for (i = 0; i < pcnt; i++)
  42     if (ppnt[i].p_type == PT_LOAD)
  43       count++;
  44
  45   loadaddr->got_value = 0;
  46
  47   size = sizeof (struct elf32_fdpic_loadmap)
  48     + sizeof (struct elf32_fdpic_loadseg) * count;
  49   loadaddr->map = _dl_malloc (size);
  50   if (! loadaddr->map)
  51     _dl_exit (-1);
  52
  53   loadaddr->map->version = 0;
  54   loadaddr->map->nsegs = 0;
  55
  56   return count;
  57 }
  58
  59 /* Incrementally initialize a load map.  */
  60 inline static void
  61 __dl_init_loadaddr_hdr (struct elf32_fdpic_loadaddr loadaddr, void *addr,
  62                         Elf32_Phdr *phdr, int maxsegs)
  63 {
  64   struct elf32_fdpic_loadseg *segdata;
  65
  66   if (loadaddr.map->nsegs == maxsegs)
  67     _dl_exit (-1);
  68
  69   segdata = &loadaddr.map->segs[loadaddr.map->nsegs++];
  70   segdata->addr = (Elf32_Addr) addr;
  71   segdata->p_vaddr = phdr->p_vaddr;
  72   segdata->p_memsz = phdr->p_memsz;
  73
  74 #if defined (__SUPPORT_LD_DEBUG__)
  75   {
  76     extern char *_dl_debug;
  77     extern int _dl_debug_file;
  78     if (_dl_debug)
  79       _dl_dprintf(_dl_debug_file, "%i: mapped %x at %x, size %x\n",
  80                   loadaddr.map->nsegs-1,
  81                   segdata->p_vaddr, segdata->addr, segdata->p_memsz);
  82   }
  83 #endif
  84 }
  85
  86 inline static void __dl_loadaddr_unmap
  87 (struct elf32_fdpic_loadaddr loadaddr, struct funcdesc_ht *funcdesc_ht);
  88
  89 /* Figure out whether the given address is in one of the mapped
  90    segments.  */
  91 inline static int
  92 __dl_addr_in_loadaddr (void *p, struct elf32_fdpic_loadaddr loadaddr)
  93 {
  94   struct elf32_fdpic_loadmap *map = loadaddr.map;
  95   int c;
  96
  97   for (c = 0; c < map->nsegs; c++)
  98     if ((void*)map->segs[c].addr <= p
  99         && (char*)p < (char*)map->segs[c].addr + map->segs[c].p_memsz)
 100       return 1;
 101
 102   return 0;
 103 }
 104
 105 inline static void * _dl_funcdesc_for (void *entry_point, void *got_value);
 106
 107 /* The hashcode handling code below is heavily inspired in libiberty's
 108    hashtab code, but with most adaptation points and support for
 109    deleting elements removed.
 110
 111    Copyright (C) 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
 112    Contributed by Vladimir Makarov (vmakarov@cygnus.com).  */
 113
 114 inline static unsigned long
 115 higher_prime_number (unsigned long n)
 116 {
 117   /* These are primes that are near, but slightly smaller than, a
 118      power of two.  */
 119   static const unsigned long primes[] = {
 120     (unsigned long) 7,
 121     (unsigned long) 13,
 122     (unsigned long) 31,
 123     (unsigned long) 61,
 124     (unsigned long) 127,
 125     (unsigned long) 251,
 126     (unsigned long) 509,
 127     (unsigned long) 1021,
 128     (unsigned long) 2039,
 129     (unsigned long) 4093,
 130     (unsigned long) 8191,
 131     (unsigned long) 16381,
 132     (unsigned long) 32749,
 133     (unsigned long) 65521,
 134     (unsigned long) 131071,
 135     (unsigned long) 262139,
 136     (unsigned long) 524287,
 137     (unsigned long) 1048573,
 138     (unsigned long) 2097143,
 139     (unsigned long) 4194301,
 140     (unsigned long) 8388593,
 141     (unsigned long) 16777213,
 142     (unsigned long) 33554393,
 143     (unsigned long) 67108859,
 144     (unsigned long) 134217689,
 145     (unsigned long) 268435399,
 146     (unsigned long) 536870909,
 147     (unsigned long) 1073741789,
 148     (unsigned long) 2147483647,
 149                                         /* 4294967291L */
 150     ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
 151   };
 152
 153   const unsigned long *low = &primes[0];
 154   const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
 155
 156   while (low != high)
 157     {
 158       const unsigned long *mid = low + (high - low) / 2;
 159       if (n > *mid)
 160         low = mid + 1;
 161       else
 162         high = mid;
 163     }
 164
 165 #if 0
 166   /* If we've run out of primes, abort.  */
 167   if (n > *low)
 168     {
 169       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
 170       abort ();
 171     }
 172 #endif
 173
 174   return *low;
 175 }
 176
 177 struct funcdesc_ht
 178 {
 179   /* Table itself.  */
 180   struct funcdesc_value **entries;
 181
 182   /* Current size (in entries) of the hash table */
 183   size_t size;
 184
 185   /* Current number of elements.  */
 186   size_t n_elements;
 187 };
 188
 189 inline static int
 190 hash_pointer (const void *p)
 191 {
 192   return (int) ((long)p >> 3);
 193 }
 194
 195 inline static struct funcdesc_ht *
 196 htab_create (void)
 197 {
 198   struct funcdesc_ht *ht = _dl_malloc (sizeof (struct funcdesc_ht));
 199
 200   if (! ht)
 201     return NULL;
 202   ht->size = 3;
 203   ht->entries = _dl_malloc (sizeof (struct funcdesc_ht_value *) * ht->size);
 204   if (! ht->entries)
 205     return NULL;
 206
 207   ht->n_elements = 0;
 208
 209   _dl_memset (ht->entries, 0, sizeof (struct funcdesc_ht_value *) * ht->size);
 210
 211   return ht;
 212 }
 213
 214 /* This is only called from _dl_loadaddr_unmap, so it's safe to call
 215    _dl_free().  See the discussion below.  */
 216 inline static void
 217 htab_delete (struct funcdesc_ht *htab)
 218 {
 219   int i;
 220
 221   for (i = htab->size - 1; i >= 0; i--)
 222     if (htab->entries[i])
 223       _dl_free (htab->entries[i]);
 224
 225   _dl_free (htab->entries);
 226   _dl_free (htab);
 227 }
 228
 229 /* Similar to htab_find_slot, but without several unwanted side effects:
 230     - Does not call htab->eq_f when it finds an existing entry.
 231     - Does not change the count of elements/searches/collisions in the
 232       hash table.
 233    This function also assumes there are no deleted entries in the table.
 234    HASH is the hash value for the element to be inserted.  */
 235
 236 inline static struct funcdesc_value **
 237 find_empty_slot_for_expand (struct funcdesc_ht *htab, int hash)
 238 {
 239   size_t size = htab->size;
 240   unsigned int index = hash % size;
 241   struct funcdesc_value **slot = htab->entries + index;
 242   int hash2;
 243
 244   if (! *slot)
 245     return slot;
 246
 247   hash2 = 1 + hash % (size - 2);
 248   for (;;)
 249     {
 250       index += hash2;
 251       if (index >= size)
 252         index -= size;
 253
 254       slot = htab->entries + index;
 255       if (! *slot)
 256         return slot;
 257     }
 258 }
 259
 260 /* The following function changes size of memory allocated for the
 261    entries and repeatedly inserts the table elements.  The occupancy
 262    of the table after the call will be about 50%.  Naturally the hash
 263    table must already exist.  Remember also that the place of the
 264    table entries is changed.  If memory allocation failures are allowed,
 265    this function will return zero, indicating that the table could not be
 266    expanded.  If all goes well, it will return a non-zero value.  */
 267
 268 inline static int
 269 htab_expand (struct funcdesc_ht *htab)
 270 {
 271   struct funcdesc_value **oentries;
 272   struct funcdesc_value **olimit;
 273   struct funcdesc_value **p;
 274   struct funcdesc_value **nentries;
 275   size_t nsize;
 276
 277   oentries = htab->entries;
 278   olimit = oentries + htab->size;
 279
 280   /* Resize only when table after removal of unused elements is either
 281      too full or too empty.  */
 282   if (htab->n_elements * 2 > htab->size)
 283     nsize = higher_prime_number (htab->n_elements * 2);
 284   else
 285     nsize = htab->size;
 286
 287   nentries = _dl_malloc (sizeof (struct funcdesc_value *) * nsize);
 288   _dl_memset (nentries, 0, sizeof (struct funcdesc_value *) * nsize);
 289   if (nentries == NULL)
 290     return 0;
 291   htab->entries = nentries;
 292   htab->size = nsize;
 293
 294   p = oentries;
 295   do
 296     {
 297       if (*p)
 298         *find_empty_slot_for_expand (htab, hash_pointer ((*p)->entry_point))
 299           = *p;
 300
 301       p++;
 302     }
 303   while (p < olimit);
 304
 305 #if 0 /* We can't tell whether this was allocated by the _dl_malloc()
 306          built into ld.so or malloc() in the main executable or libc,
 307          and calling free() for something that wasn't malloc()ed could
 308          do Very Bad Things (TM).  Take the conservative approach
 309          here, potentially wasting as much memory as actually used by
 310          the hash table, even if multiple growths occur.  That's not
 311          so bad as to require some overengineered solution that would
 312          enable us to keep track of how it was allocated. */
 313   _dl_free (oentries);
 314 #endif
 315   return 1;
 316 }
 317
 318 /* This function searches for a hash table slot containing an entry
 319    equal to the given element.  To delete an entry, call this with
 320    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
 321    after doing some checks).  To insert an entry, call this with
 322    INSERT = 1, then write the value you want into the returned slot.
 323    When inserting an entry, NULL may be returned if memory allocation
 324    fails.  */
 325
 326 inline static struct funcdesc_value **
 327 htab_find_slot (struct funcdesc_ht *htab, void *ptr, int insert)
 328 {
 329   unsigned int index;
 330   int hash, hash2;
 331   size_t size;
 332   struct funcdesc_value **entry;
 333
 334   if (htab->size * 3 <= htab->n_elements * 4
 335       && htab_expand (htab) == 0)
 336     return NULL;
 337
 338   hash = hash_pointer (ptr);
 339
 340   size = htab->size;
 341   index = hash % size;
 342
 343   entry = &htab->entries[index];
 344   if (!*entry)
 345     goto empty_entry;
 346   else if ((*entry)->entry_point == ptr)
 347     return entry;
 348
 349   hash2 = 1 + hash % (size - 2);
 350   for (;;)
 351     {
 352       index += hash2;
 353       if (index >= size)
 354         index -= size;
 355
 356       entry = &htab->entries[index];
 357       if (!*entry)
 358         goto empty_entry;
 359       else if ((*entry)->entry_point == ptr)
 360         return entry;
 361     }
 362
 363  empty_entry:
 364   if (!insert)
 365     return NULL;
 366
 367   htab->n_elements++;
 368   return entry;
 369 }
 370
 371 void *
 372 _dl_funcdesc_for (void *entry_point, void *got_value)
 373 {
 374   struct elf_resolve *tpnt = ((void**)got_value)[2];
 375   struct funcdesc_ht *ht = tpnt->funcdesc_ht;
 376   struct funcdesc_value **entry;
 377
 378   _dl_assert (got_value == tpnt->loadaddr.got_value);
 379
 380   if (! ht)
 381     {
 382       ht = htab_create ();
 383       if (! ht)
 384         return (void*)-1;
 385       tpnt->funcdesc_ht = ht;
 386     }
 387
 388   entry = htab_find_slot (ht, entry_point, 1);
 389   if (*entry)
 390     {
 391       _dl_assert ((*entry)->entry_point == entry_point);
 392       return _dl_stabilize_funcdesc (*entry);
 393     }
 394
 395   *entry = _dl_malloc (sizeof (struct funcdesc_value));
 396   (*entry)->entry_point = entry_point;
 397   (*entry)->got_value = got_value;
 398
 399   return _dl_stabilize_funcdesc (*entry);
 400 }
 401
 402 inline static void const *
 403 _dl_lookup_address (void const *address)
 404 {
 405   struct elf_resolve *rpnt;
 406   struct funcdesc_value const *fd;
 407
 408   /* Make sure we don't make assumptions about its alignment.  */
 409   __asm__ ("" : "+r" (address));
 410
 411   if ((Elf32_Addr)address & 7)
 412     /* It's not a function descriptor.  */
 413     return address;
 414
 415   fd = (struct funcdesc_value const *)address;
 416
 417   for (rpnt = _dl_loaded_modules; rpnt; rpnt = rpnt->next)
 418     {
 419       if (! rpnt->funcdesc_ht)
 420         continue;
 421
 422       if (fd->got_value != rpnt->loadaddr.got_value)
 423         continue;
 424
 425       address = htab_find_slot (rpnt->funcdesc_ht, (void*)fd->entry_point, 0);
 426
 427       if (address && *(struct funcdesc_value *const*)address == fd)
 428         {
 429           address = (*(struct funcdesc_value *const*)address)->entry_point;
 430           break;
 431         }
 432       else
 433         address = fd;
 434     }
 435
 436   return address;
 437 }
 438
 439 void
 440 __dl_loadaddr_unmap (struct elf32_fdpic_loadaddr loadaddr,
 441                      struct funcdesc_ht *funcdesc_ht)
 442 {
 443   int i;
 444
 445   for (i = 0; i < loadaddr.map->nsegs; i++)
 446     _dl_munmap ((void*)loadaddr.map->segs[i].addr,
 447                 loadaddr.map->segs[i].p_memsz);
 448
 449   /* _dl_unmap is only called for dlopen()ed libraries, for which
 450      calling free() is safe, or before we've completed the initial
 451      relocation, in which case calling free() is probably pointless,
 452      but still safe.  */
 453   _dl_free (loadaddr.map);
 454   if (funcdesc_ht)
 455     htab_delete (funcdesc_ht);
 456 }