bfd/merge.c

   1 /* SEC_MERGE support.
   2    Copyright 2001 Free Software Foundation, Inc.
   3    Written by Jakub Jelinek <jakub@redhat.com>.
   4
   5 This file is part of BFD, the Binary File Descriptor library.
   6
   7 This program is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 This program is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  20
  21 /* This file contains support for merging duplicate entities within sections,
  22    as used in ELF SHF_MERGE.  */
  23
  24 #include "bfd.h"
  25 #include "sysdep.h"
  26 #include "libbfd.h"
  27
  28 #include <ctype.h>
  29
  30 /* An entry in the section merge hash table.  */
  31
  32 struct sec_merge_hash_entry
  33 {
  34   struct bfd_hash_entry root;
  35   /* Length of this entry.  */
  36   unsigned int len;
  37   /* Start of this string needs to be aligned to
  38      alignment octets (not 1 << align).  */
  39   unsigned int alignment;
  40   /* Index within the merged section.  */
  41   bfd_size_type index;
  42   /* Which section is it in.  */
  43   asection *sec;
  44   /* Next entity in the hash table.  */
  45   struct sec_merge_hash_entry *next;
  46 };
  47
  48 /* The section merge hash table.  */
  49
  50 struct sec_merge_hash
  51 {
  52   struct bfd_hash_table table;
  53   /* Next available index.  */
  54   bfd_size_type size;
  55   /* First entity in the SEC_MERGE sections of this type.  */
  56   struct sec_merge_hash_entry *first;
  57   /* Last entity in the SEC_MERGE sections of this type.  */
  58   struct sec_merge_hash_entry *last;
  59   /* Entity size.  */
  60   unsigned int entsize;
  61   /* Are entries fixed size or zero terminated strings?  */
  62   boolean strings;
  63 };
  64
  65 struct sec_merge_info
  66 {
  67   /* Chain of sec_merge_infos.  */
  68   struct sec_merge_info *next;
  69   /* A hash table used to hold section content.  */
  70   struct sec_merge_hash *htab;
  71   /* The last section attempted for merge.  */
  72   asection *last;
  73 };
  74
  75 struct sec_merge_sec_info
  76 {
  77   /* A hash table used to hold section content.  */
  78   struct sec_merge_hash *htab;
  79   /* First string in this section.  */
  80   struct sec_merge_hash_entry *first;
  81   /* Original section content.  */
  82   unsigned char contents[1];
  83 };
  84
  85 static struct bfd_hash_entry *sec_merge_hash_newfunc
  86   PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
  87 static struct sec_merge_hash_entry *sec_merge_hash_lookup
  88   PARAMS ((struct sec_merge_hash *, const char *, unsigned int, boolean));
  89 static struct sec_merge_hash *sec_merge_init
  90   PARAMS ((unsigned int, boolean));
  91 static struct sec_merge_hash_entry *sec_merge_add
  92   PARAMS ((struct sec_merge_hash *, const char *, unsigned int));
  93 static boolean sec_merge_emit
  94   PARAMS ((bfd *, struct sec_merge_hash_entry *));
  95
  96 /* Routine to create an entry in a section merge hashtab.  */
  97
  98 static struct bfd_hash_entry *
  99 sec_merge_hash_newfunc (entry, table, string)
 100      struct bfd_hash_entry *entry;
 101      struct bfd_hash_table *table;
 102      const char *string;
 103 {
 104   struct sec_merge_hash_entry *ret = (struct sec_merge_hash_entry *) entry;
 105
 106   /* Allocate the structure if it has not already been allocated by a
 107      subclass.  */
 108   if (ret == (struct sec_merge_hash_entry *) NULL)
 109     ret = ((struct sec_merge_hash_entry *)
 110            bfd_hash_allocate (table, sizeof (struct sec_merge_hash_entry)));
 111   if (ret == (struct sec_merge_hash_entry *) NULL)
 112     return NULL;
 113
 114   /* Call the allocation method of the superclass.  */
 115   ret = ((struct sec_merge_hash_entry *)
 116          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
 117
 118   if (ret)
 119     {
 120       /* Initialize the local fields.  */
 121       ret->index = (bfd_size_type) -1;
 122       ret->alignment = 0;
 123       ret->sec = NULL;
 124       ret->next = NULL;
 125     }
 126
 127   return (struct bfd_hash_entry *)ret;
 128 }
 129
 130 /* Look up an entry in a section merge hash table.  */
 131
 132 static struct sec_merge_hash_entry *
 133 sec_merge_hash_lookup (table, string, alignment, create)
 134      struct sec_merge_hash *table;
 135      const char *string;
 136      unsigned int alignment;
 137      boolean create;
 138 {
 139   register const unsigned char *s;
 140   register unsigned long hash;
 141   register unsigned int c;
 142   struct sec_merge_hash_entry *hashp;
 143   unsigned int len, i;
 144   unsigned int index;
 145
 146   hash = 0;
 147   len = 0;
 148   s = (const unsigned char *) string;
 149   if (table->strings)
 150     {
 151       if (table->entsize == 1)
 152         {
 153           while ((c = *s++) != '\0')
 154             {
 155               hash += c + (c << 17);
 156               hash ^= hash >> 2;
 157               ++len;
 158             }
 159           hash += len + (len << 17);
 160         }
 161       else
 162         {
 163           for (;;)
 164             {
 165               for (i = 0; i < table->entsize; ++i)
 166                 if (s[i] != '\0')
 167                   break;
 168               if (i == table->entsize)
 169                 break;
 170               for (i = 0; i < table->entsize; ++i)
 171                 {
 172                   c = *s++;
 173                   hash += c + (c << 17);
 174                   hash ^= hash >> 2;
 175                 }
 176               ++len;
 177             }
 178           hash += len + (len << 17);
 179           len *= table->entsize;
 180         }
 181       hash ^= hash >> 2;
 182       len += table->entsize;
 183     }
 184   else
 185     {
 186       for (i = 0; i < table->entsize; ++i)
 187         {
 188           c = *s++;
 189           hash += c + (c << 17);
 190           hash ^= hash >> 2;
 191         }
 192       len = table->entsize;
 193     }
 194
 195   index = hash % table->table.size;
 196   for (hashp = (struct sec_merge_hash_entry *) table->table.table[index];
 197        hashp != (struct sec_merge_hash_entry *) NULL;
 198        hashp = (struct sec_merge_hash_entry *) hashp->root.next)
 199     {
 200       if (hashp->root.hash == hash
 201           && len == hashp->len
 202           && memcmp (hashp->root.string, string, len) == 0)
 203         {
 204           /* If the string we found does not have at least the required
 205              alignment, we need to insert another copy.
 206              FIXME: The old copy could be removed and the space allocated
 207              for it filled by some new string (similarly with padding).  */
 208           if (hashp->alignment < alignment)
 209             break;
 210           return hashp;
 211         }
 212     }
 213
 214   if (! create)
 215     return (struct sec_merge_hash_entry *) NULL;
 216
 217   hashp = (struct sec_merge_hash_entry *)
 218           sec_merge_hash_newfunc ((struct bfd_hash_entry *) NULL,
 219                                   (struct bfd_hash_table *) table, string);
 220   if (hashp == (struct sec_merge_hash_entry *) NULL)
 221     return (struct sec_merge_hash_entry *) NULL;
 222   hashp->root.string = string;
 223   hashp->root.hash = hash;
 224   hashp->len = len;
 225   hashp->alignment = alignment;
 226   hashp->root.next = table->table.table[index];
 227   table->table.table[index] = (struct bfd_hash_entry *) hashp;
 228
 229   return hashp;
 230 }
 231
 232 /* Create a new hash table.  */
 233
 234 static struct sec_merge_hash *
 235 sec_merge_init (entsize, strings)
 236      unsigned int entsize;
 237      boolean strings;
 238 {
 239   struct sec_merge_hash *table;
 240
 241   table = ((struct sec_merge_hash *)
 242            bfd_malloc (sizeof (struct sec_merge_hash)));
 243   if (table == NULL)
 244     return NULL;
 245
 246   if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
 247     {
 248       free (table);
 249       return NULL;
 250     }
 251
 252   table->size = 0;
 253   table->first = NULL;
 254   table->last = NULL;
 255   table->entsize = entsize;
 256   table->strings = strings;
 257
 258   return table;
 259 }
 260
 261 /* Get the index of an entity in a hash table, adding it if it is not
 262    already present.  */
 263
 264 static struct sec_merge_hash_entry *
 265 sec_merge_add (tab, str, alignment)
 266      struct sec_merge_hash *tab;
 267      const char *str;
 268      unsigned int alignment;
 269 {
 270   register struct sec_merge_hash_entry *entry;
 271
 272   entry = sec_merge_hash_lookup (tab, str, alignment, true);
 273   if (entry == NULL)
 274     return NULL;
 275
 276   if (entry->index == (bfd_size_type) -1)
 277     {
 278       tab->size = (tab->size + alignment - 1) & ~((bfd_vma) alignment - 1);
 279       entry->index = tab->size;
 280       tab->size += entry->len;
 281       if (tab->first == NULL)
 282         tab->first = entry;
 283       else
 284         tab->last->next = entry;
 285       tab->last = entry;
 286     }
 287
 288   return entry;
 289 }
 290
 291 static boolean
 292 sec_merge_emit (abfd, entry)
 293      register bfd *abfd;
 294      struct sec_merge_hash_entry *entry;
 295 {
 296   asection *sec = entry->sec;
 297   char *pad = "";
 298   bfd_size_type off = 0;
 299   int alignment_power = bfd_get_section_alignment (abfd, sec->output_section);
 300
 301   if (alignment_power)
 302     pad = bfd_zmalloc (1 << alignment_power);
 303
 304   for (; entry != NULL && entry->sec == sec; entry = entry->next)
 305     {
 306       register const char *str;
 307       register size_t len;
 308
 309       len = off & (entry->alignment - 1);
 310       if (len)
 311         {
 312           len = entry->alignment - len;
 313           if (bfd_write ((PTR) pad, 1, len, abfd) != len)
 314             break;
 315           off += len;
 316         }
 317
 318       str = entry->root.string;
 319       len = entry->len;
 320
 321       if (bfd_write ((PTR) str, 1, len, abfd) != len)
 322         break;
 323
 324       off += len;
 325     }
 326
 327   if (alignment_power)
 328     free (pad);
 329
 330   return entry == NULL || entry->sec != sec;
 331 }
 332
 333 /* This function is called for each input file from the add_symbols
 334    pass of the linker.  */
 335
 336 boolean
 337 _bfd_merge_section (abfd, psinfo, sec, psecinfo)
 338      bfd *abfd;
 339      PTR *psinfo;
 340      asection *sec;
 341      PTR *psecinfo;
 342 {
 343   boolean first, nul;
 344   struct sec_merge_info *sinfo;
 345   struct sec_merge_sec_info *secinfo;
 346   unsigned char *p, *end;
 347   bfd_vma mask, eltalign;
 348   unsigned int align;
 349   unsigned int i;
 350
 351   if (sec->_raw_size == 0
 352       || (sec->flags & SEC_MERGE) == 0
 353       || sec->entsize == 0)
 354     return true;
 355
 356   if ((sec->flags & SEC_RELOC) != 0)
 357     {
 358       /* We aren't prepared to handle relocations in merged sections.  */
 359       return true;
 360     }
 361
 362   if (sec->output_section != NULL
 363       && bfd_is_abs_section (sec->output_section))
 364     {
 365       /* The section is being discarded from the link, so we should
 366          just ignore it.  */
 367       return true;
 368     }
 369
 370   align = bfd_get_section_alignment (abfd, sec);
 371   if ((sec->entsize < (unsigned int)(1 << align)
 372        && ((sec->entsize & (sec->entsize - 1))
 373            || !(sec->flags & SEC_STRINGS)))
 374       || (sec->entsize > (unsigned int)(1 << align)
 375           && (sec->entsize & ((1 << align) - 1))))
 376     {
 377       /* Sanity check.  If string character size is smaller than
 378          alignment, then we require character size to be a power
 379          of 2, otherwise character size must be integer multiple
 380          of alignment.  For non-string constants, alignment must
 381          be smaller than or equal to entity size and entity size
 382          must be integer multiple of alignment.  */
 383       return true;
 384     }
 385
 386   first = false;
 387
 388   for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next)
 389     if (! ((sinfo->last->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS))
 390         && sinfo->last->entsize == sec->entsize
 391         && ! strcmp (sinfo->last->name, sec->name))
 392       break;
 393
 394   if (sinfo == NULL)
 395     {
 396       /* Initialize the information we need to keep track of.  */
 397       first = true;
 398       sinfo = (struct sec_merge_info *)
 399               bfd_alloc (abfd, sizeof (struct sec_merge_info));
 400       if (sinfo == NULL)
 401         goto error_return;
 402       sinfo->next = (struct sec_merge_info *) *psinfo;
 403       *psinfo = (PTR) sinfo;
 404       sinfo->htab =
 405         sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS));
 406       if (sinfo->htab == NULL)
 407         goto error_return;
 408     }
 409
 410   /* Read the section from abfd.  */
 411
 412   *psecinfo = bfd_alloc (abfd, sizeof (struct sec_merge_sec_info)
 413                                + sec->_raw_size - 1);
 414   if (*psecinfo == NULL)
 415     goto error_return;
 416
 417   secinfo = (struct sec_merge_sec_info *)*psecinfo;
 418   secinfo->htab = sinfo->htab;
 419   sinfo->htab->size = 0;
 420   secinfo->first = NULL;
 421
 422   if (! bfd_get_section_contents (abfd, sec, secinfo->contents, 0,
 423                                   sec->_raw_size))
 424     goto error_return;
 425
 426   end = secinfo->contents + sec->_raw_size;
 427   nul = false;
 428   mask = ((bfd_vma)1 << align) - 1;
 429   if (sec->flags & SEC_STRINGS)
 430     {
 431       for (p = secinfo->contents; p < end;)
 432         {
 433           struct sec_merge_hash_entry *entry;
 434
 435           eltalign = p - secinfo->contents;
 436           eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1;
 437           if (!eltalign || eltalign > mask)
 438             eltalign = mask + 1;
 439           entry = sec_merge_add (sinfo->htab, p, eltalign);
 440           if (entry->sec == NULL)
 441             {
 442               if (secinfo->first == NULL)
 443                 secinfo->first = entry;
 444               entry->sec = sec;
 445             }
 446           p += entry->len;
 447           if (sec->entsize == 1)
 448             {
 449               while (p < end && *p == 0)
 450                 {
 451                   if (!nul && !((p - secinfo->contents) & mask))
 452                     {
 453                       nul = true;
 454                       entry = sec_merge_add (sinfo->htab, "", mask + 1);
 455                       if (entry->sec == NULL)
 456                         {
 457                           if (secinfo->first == NULL)
 458                             secinfo->first = entry;
 459                           entry->sec = sec;
 460                         }
 461                     }
 462                   p++;
 463                 }
 464             }
 465           else
 466             {
 467               while (p < end)
 468                 {
 469                   for (i = 0; i < sec->entsize; i++)
 470                     if (p[i] != '\0')
 471                       break;
 472                   if (i != sec->entsize)
 473                     break;
 474                   if (!nul && !((p - secinfo->contents) & mask))
 475                     {
 476                       nul = true;
 477                       entry = sec_merge_add (sinfo->htab, p, mask + 1);
 478                       if (entry->sec == NULL)
 479                         {
 480                           if (secinfo->first == NULL)
 481                             secinfo->first = entry;
 482                           entry->sec = sec;
 483                         }
 484                     }
 485                   p += sec->entsize;
 486                 }
 487             }
 488         }
 489     }
 490   else
 491     {
 492       for (p = secinfo->contents; p < end; p += sec->entsize)
 493         {
 494           struct sec_merge_hash_entry *entry;
 495
 496           entry = sec_merge_add (sinfo->htab, p, 1);
 497           if (entry->sec == NULL)
 498             {
 499               if (secinfo->first == NULL)
 500                 secinfo->first = entry;
 501               entry->sec = sec;
 502             }
 503         }
 504     }
 505
 506   sec->_cooked_size = sinfo->htab->size;
 507   if (!sec->_cooked_size)
 508     sec->flags |= SEC_EXCLUDE;
 509   sinfo->last = sec;
 510   return true;
 511
 512  error_return:
 513   if (*psecinfo != NULL)
 514     free (*psecinfo);
 515   *psecinfo = NULL;
 516   return false;
 517 }
 518
 519 /* Write out the merged section.  */
 520
 521 boolean
 522 _bfd_write_merged_section (output_bfd, sec, psecinfo)
 523      bfd *output_bfd;
 524      asection *sec;
 525      PTR psecinfo;
 526 {
 527   struct sec_merge_sec_info *secinfo;
 528
 529   secinfo = (struct sec_merge_sec_info *) psecinfo;
 530
 531   if (!secinfo->first)
 532     return true;
 533
 534   if (bfd_seek (output_bfd,
 535                 (sec->output_section->filepos + sec->output_offset),
 536                 SEEK_SET) != 0)
 537     return false;
 538
 539   if (! sec_merge_emit (output_bfd, secinfo->first))
 540     return false;
 541
 542   return true;
 543 }
 544
 545 /* Adjust an address in the SEC_MERGE section.  Given OFFSET within
 546    *PSEC, this returns the new offset in the adjusted SEC_MERGE
 547    section and writes the new section back into *PSEC.  */
 548
 549 bfd_vma
 550 _bfd_merged_section_offset (output_bfd, psec, psecinfo, offset, addend)
 551      bfd *output_bfd ATTRIBUTE_UNUSED;
 552      asection **psec;
 553      PTR psecinfo;
 554      bfd_vma offset, addend;
 555 {
 556   struct sec_merge_sec_info *secinfo;
 557   struct sec_merge_hash_entry *entry;
 558   unsigned char *p;
 559   asection *sec = *psec;
 560
 561   secinfo = (struct sec_merge_sec_info *) psecinfo;
 562
 563   if (offset + addend >= sec->_raw_size)
 564     {
 565       if (offset + addend > sec->_raw_size)
 566         (*_bfd_error_handler) (_("%s: access beyond end of merged section (%ld + %ld)"),
 567                                bfd_get_filename (sec->owner), (long)offset,
 568                                (long) addend);
 569       return (secinfo->first ? sec->_cooked_size : 0);
 570     }
 571
 572   if (secinfo->htab->strings)
 573     {
 574       if (sec->entsize == 1)
 575         {
 576           p = secinfo->contents + offset + addend - 1;
 577           while (*p && p >= secinfo->contents)
 578             --p;
 579           ++p;
 580         }
 581       else
 582         {
 583           p = secinfo->contents
 584               + ((offset + addend) / sec->entsize) * sec->entsize;
 585           p -= sec->entsize;
 586           while (p >= secinfo->contents)
 587             {
 588               unsigned int i;
 589
 590               for (i = 0; i < sec->entsize; ++i)
 591                 if (p[i] != '\0')
 592                   break;
 593               if (i == sec->entsize)
 594                 break;
 595               p -= sec->entsize;
 596             }
 597           p += sec->entsize;
 598         }
 599     }
 600   else
 601     {
 602       p = secinfo->contents
 603           + ((offset + addend) / sec->entsize) * sec->entsize;
 604     }
 605   entry = sec_merge_hash_lookup (secinfo->htab, p, 0, false);
 606   if (!entry)
 607     {
 608       if (! secinfo->htab->strings)
 609         abort ();
 610       /* This should only happen if somebody points into the padding
 611          after a NUL character but before next entity.  */
 612       if (*p)
 613         abort ();
 614       if (! secinfo->htab->first)
 615         abort ();
 616       entry = secinfo->htab->first;
 617       p = secinfo->contents
 618           + ((offset + addend) / sec->entsize + 1) * sec->entsize
 619           - entry->len;
 620     }
 621
 622   *psec = entry->sec;
 623   return entry->index + (secinfo->contents + offset - p);
 624 }