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   /* Index within the merged section.  */
  38   bfd_size_type index;
  39   /* Which section is it in.  */
  40   asection *sec;
  41   /* Next entity in the hash table.  */
  42   struct sec_merge_hash_entry *next;
  43 };
  44
  45 /* The section merge hash table.  */
  46
  47 struct sec_merge_hash
  48 {
  49   struct bfd_hash_table table;
  50   /* Next available index.  */
  51   bfd_size_type size;
  52   /* First entity in the SEC_MERGE sections of this type.  */
  53   struct sec_merge_hash_entry *first;
  54   /* Last entity in the SEC_MERGE sections of this type.  */
  55   struct sec_merge_hash_entry *last;
  56   /* Entity size.  */
  57   unsigned int entsize;
  58   /* Start of each string needs to be aligned to 1 << alignment_power
  59      octets.  */
  60   unsigned int alignment_power;
  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 *, boolean));
  89 static struct sec_merge_hash *sec_merge_init
  90   PARAMS ((unsigned int, unsigned int, boolean));
  91 static struct sec_merge_hash_entry *sec_merge_add
  92   PARAMS ((struct sec_merge_hash *, const char *));
  93 static boolean sec_merge_emit
  94   PARAMS ((bfd *, struct sec_merge_hash *, 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->sec = NULL;
 123       ret->next = NULL;
 124     }
 125
 126   return (struct bfd_hash_entry *)ret;
 127 }
 128
 129 /* Look up an entry in a section merge hash table.  */
 130
 131 static struct sec_merge_hash_entry *
 132 sec_merge_hash_lookup (table, string, create)
 133      struct sec_merge_hash *table;
 134      const char *string;
 135      boolean create;
 136 {
 137   register const unsigned char *s;
 138   register unsigned long hash;
 139   register unsigned int c;
 140   struct sec_merge_hash_entry *hashp;
 141   unsigned int len, i;
 142   unsigned int index;
 143
 144   hash = 0;
 145   len = 0;
 146   s = (const unsigned char *) string;
 147   if (table->strings)
 148     {
 149       if (table->entsize == 1)
 150         {
 151           while ((c = *s++) != '\0')
 152             {
 153               hash += c + (c << 17);
 154               hash ^= hash >> 2;
 155               ++len;
 156             }
 157           hash += len + (len << 17);
 158         }
 159       else
 160         {
 161           for (;;)
 162             {
 163               for (i = 0; i < table->entsize; ++i)
 164                 if (s[i] != '\0')
 165                   break;
 166               if (i == table->entsize)
 167                 break;
 168               for (i = 0; i < table->entsize; ++i)
 169                 {
 170                   c = *s++;
 171                   hash += c + (c << 17);
 172                   hash ^= hash >> 2;
 173                 }
 174               ++len;
 175             }
 176           hash += len + (len << 17);
 177           len *= table->entsize;
 178         }
 179       hash ^= hash >> 2;
 180       len += table->entsize;
 181     }
 182   else
 183     {
 184       for (i = 0; i < table->entsize; ++i)
 185         {
 186           c = *s++;
 187           hash += c + (c << 17);
 188           hash ^= hash >> 2;
 189         }
 190       len = table->entsize;
 191     }
 192
 193   index = hash % table->table.size;
 194   for (hashp = (struct sec_merge_hash_entry *) table->table.table[index];
 195        hashp != (struct sec_merge_hash_entry *) NULL;
 196        hashp = (struct sec_merge_hash_entry *) hashp->next)
 197     {
 198       if (hashp->root.hash == hash
 199           && len == hashp->len
 200           && memcmp (hashp->root.string, string, len) == 0)
 201         return hashp;
 202     }
 203
 204   if (! create)
 205     return (struct sec_merge_hash_entry *) NULL;
 206
 207   hashp = (struct sec_merge_hash_entry *)
 208           sec_merge_hash_newfunc ((struct bfd_hash_entry *) NULL,
 209                                   (struct bfd_hash_table *) table, string);
 210   if (hashp == (struct sec_merge_hash_entry *) NULL)
 211     return (struct sec_merge_hash_entry *) NULL;
 212   hashp->root.string = string;
 213   hashp->root.hash = hash;
 214   hashp->len = len;
 215   hashp->root.next = table->table.table[index];
 216   table->table.table[index] = (struct bfd_hash_entry *) hashp;
 217
 218   return hashp;
 219 }
 220
 221 /* Create a new hash table.  */
 222
 223 static struct sec_merge_hash *
 224 sec_merge_init (alignment_power, entsize, strings)
 225      unsigned int alignment_power, entsize;
 226      boolean strings;
 227 {
 228   struct sec_merge_hash *table;
 229
 230   table = ((struct sec_merge_hash *)
 231            bfd_malloc (sizeof (struct sec_merge_hash)));
 232   if (table == NULL)
 233     return NULL;
 234
 235   if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
 236     {
 237       free (table);
 238       return NULL;
 239     }
 240
 241   table->size = 0;
 242   table->first = NULL;
 243   table->last = NULL;
 244   table->alignment_power = alignment_power;
 245   table->entsize = entsize;
 246   table->strings = strings;
 247
 248   return table;
 249 }
 250
 251 /* Get the index of an entity in a hash table, adding it if it is not
 252    already present.  */
 253
 254 static struct sec_merge_hash_entry *
 255 sec_merge_add (tab, str)
 256      struct sec_merge_hash *tab;
 257      const char *str;
 258 {
 259   register struct sec_merge_hash_entry *entry;
 260
 261   entry = sec_merge_hash_lookup (tab, str, true);
 262   if (entry == NULL)
 263     return NULL;
 264
 265   if (entry->index == (bfd_size_type) -1)
 266     {
 267       entry->index = tab->size;
 268       tab->size += entry->len;
 269       tab->size = align_power (tab->size, tab->alignment_power);
 270       if (tab->first == NULL)
 271         tab->first = entry;
 272       else
 273         tab->last->next = entry;
 274       tab->last = entry;
 275     }
 276
 277   return entry;
 278 }
 279
 280 static boolean
 281 sec_merge_emit (abfd, tab, entry)
 282      register bfd *abfd;
 283      struct sec_merge_hash *tab;
 284      struct sec_merge_hash_entry *entry;
 285 {
 286   asection *sec = entry->sec;
 287   char *pad = "";
 288
 289   if (tab->alignment_power)
 290     pad = bfd_zmalloc (1 << tab->alignment_power);
 291
 292   for (; entry != NULL && entry->sec == sec; entry = entry->next)
 293     {
 294       register const char *str;
 295       register size_t len;
 296
 297       str = entry->root.string;
 298       len = entry->len;
 299
 300       if (bfd_write ((PTR) str, 1, len, abfd) != len)
 301         break;
 302
 303       if (tab->alignment_power)
 304         {
 305           len &= (1 << tab->alignment_power) - 1;
 306           if (len && bfd_write ((PTR) pad, 1,
 307                                 (1 << tab->alignment_power) - len,
 308                                 abfd) != (1 << tab->alignment_power) - len)
 309             break;
 310         }
 311     }
 312
 313   if (tab->alignment_power)
 314     free (pad);
 315
 316   return entry == NULL || entry->sec != sec;
 317 }
 318
 319 /* This function is called for each input file from the add_symbols
 320    pass of the linker.  */
 321
 322 boolean
 323 _bfd_merge_section (abfd, psinfo, sec, psecinfo)
 324      bfd *abfd;
 325      PTR *psinfo;
 326      asection *sec;
 327      PTR *psecinfo;
 328 {
 329   boolean first, nul;
 330   struct sec_merge_info *sinfo;
 331   struct sec_merge_sec_info *secinfo;
 332   unsigned char *p, *end;
 333   bfd_vma mask;
 334   unsigned int align;
 335   unsigned int i;
 336
 337   if (sec->_raw_size == 0
 338       || (sec->flags & SEC_MERGE) == 0
 339       || sec->entsize == 0)
 340     return true;
 341
 342   if ((sec->flags & SEC_RELOC) != 0)
 343     {
 344       /* We aren't prepared to handle relocations in merged sections.  */
 345       return true;
 346     }
 347
 348   if (sec->output_section != NULL
 349       && bfd_is_abs_section (sec->output_section))
 350     {
 351       /* The section is being discarded from the link, so we should
 352          just ignore it.  */
 353       return true;
 354     }
 355
 356   align = bfd_get_section_alignment (abfd, sec);
 357   if ((sec->flags & SEC_STRINGS)
 358       && ((sec->entsize < (unsigned int)(1 << align)
 359            && (sec->entsize & (sec->entsize - 1)))
 360           || (sec->entsize > (unsigned int)(1 << align)
 361               && (sec->entsize & ((1 << align) - 1)))))
 362     {
 363       /* Sanity check.  If string character size is smaller than
 364          alignment, then we require character size to be a power
 365          of 2, otherwise character size must be integer multiple
 366          of alignment.  */
 367       return true;
 368     }
 369
 370   first = false;
 371
 372   for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next)
 373     if (! ((sinfo->last->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS))
 374         && sinfo->last->entsize == sec->entsize
 375         && ! strcmp (sinfo->last->name, sec->name)
 376         && bfd_get_section_alignment (abfd, sinfo->last) == align)
 377       break;
 378
 379   if (sinfo == NULL)
 380     {
 381       /* Initialize the information we need to keep track of.  */
 382       first = true;
 383       sinfo = (struct sec_merge_info *)
 384               bfd_alloc (abfd, sizeof (struct sec_merge_info));
 385       if (sinfo == NULL)
 386         goto error_return;
 387       sinfo->next = (struct sec_merge_info *) *psinfo;
 388       *psinfo = (PTR) sinfo;
 389       sinfo->htab =
 390         sec_merge_init ((sec->flags & SEC_STRINGS) ? align : 0,
 391                         sec->entsize, (sec->flags & SEC_STRINGS));
 392       if (sinfo->htab == NULL)
 393         goto error_return;
 394     }
 395
 396   /* Read the section from abfd.  */
 397
 398   *psecinfo = bfd_alloc (abfd, sizeof (struct sec_merge_sec_info)
 399                                + sec->_raw_size - 1);
 400   if (*psecinfo == NULL)
 401     goto error_return;
 402
 403   secinfo = (struct sec_merge_sec_info *)*psecinfo;
 404   secinfo->htab = sinfo->htab;
 405   sinfo->htab->size = 0;
 406   secinfo->first = NULL;
 407
 408   if (! bfd_get_section_contents (abfd, sec, secinfo->contents, 0,
 409                                   sec->_raw_size))
 410     goto error_return;
 411
 412   end = secinfo->contents + sec->_raw_size;
 413   nul = false;
 414   mask = ((bfd_vma)1 << sinfo->htab->alignment_power) - 1;
 415   if (sec->flags & SEC_STRINGS)
 416     {
 417       for (p = secinfo->contents; p < end;)
 418         {
 419           struct sec_merge_hash_entry *entry;
 420
 421           entry = sec_merge_add (sinfo->htab, p);
 422           if (entry->sec == NULL)
 423             {
 424               if (secinfo->first == NULL)
 425                 secinfo->first = entry;
 426               entry->sec = sec;
 427             }
 428           p += entry->len;
 429           if (sec->entsize == 1)
 430             {
 431               while (p < end && *p == 0)
 432                 {
 433                   if (!nul && !((p - secinfo->contents) & mask))
 434                     {
 435                       nul = true;
 436                       entry = sec_merge_add (sinfo->htab, "");
 437                       if (entry->sec == NULL)
 438                         {
 439                           if (secinfo->first == NULL)
 440                             secinfo->first = entry;
 441                           entry->sec = sec;
 442                         }
 443                     }
 444                   p++;
 445                 }
 446             }
 447           else
 448             {
 449               while (p < end)
 450                 {
 451                   for (i = 0; i < sec->entsize; i++)
 452                     if (p[i] != '\0')
 453                       break;
 454                   if (i != sec->entsize)
 455                     break;
 456                   if (!nul && !((p - secinfo->contents) & mask))
 457                     {
 458                       nul = true;
 459                       entry = sec_merge_add (sinfo->htab, p);
 460                       if (entry->sec == NULL)
 461                         {
 462                           if (secinfo->first == NULL)
 463                             secinfo->first = entry;
 464                           entry->sec = sec;
 465                         }
 466                     }
 467                   p += sec->entsize;
 468                 }
 469             }
 470         }
 471     }
 472   else
 473     {
 474       for (p = secinfo->contents; p < end; p += sec->entsize)
 475         {
 476           struct sec_merge_hash_entry *entry;
 477
 478           entry = sec_merge_add (sinfo->htab, p);
 479           if (entry->sec == NULL)
 480             {
 481               if (secinfo->first == NULL)
 482                 secinfo->first = entry;
 483               entry->sec = sec;
 484             }
 485         }
 486     }
 487
 488   sec->_cooked_size = sinfo->htab->size;
 489   if (!sec->_cooked_size)
 490     sec->flags |= SEC_EXCLUDE;
 491   sinfo->last = sec;
 492   return true;
 493
 494  error_return:
 495   if (*psecinfo != NULL)
 496     free (*psecinfo);
 497   *psecinfo = NULL;
 498   return false;
 499 }
 500
 501 /* Write out the merged section.  */
 502
 503 boolean
 504 _bfd_write_merged_section (output_bfd, sec, psecinfo)
 505      bfd *output_bfd;
 506      asection *sec;
 507      PTR psecinfo;
 508 {
 509   struct sec_merge_sec_info *secinfo;
 510
 511   secinfo = (struct sec_merge_sec_info *) psecinfo;
 512
 513   if (!secinfo->first)
 514     return true;
 515
 516   if (bfd_seek (output_bfd,
 517                 (sec->output_section->filepos + sec->output_offset),
 518                 SEEK_SET) != 0)
 519     return false;
 520
 521   if (! sec_merge_emit (output_bfd, secinfo->htab, secinfo->first))
 522     return false;
 523
 524   return true;
 525 }
 526
 527 /* Adjust an address in the SEC_MERGE section.  Given OFFSET within
 528    *PSEC, this returns the new offset in the adjusted SEC_MERGE
 529    section and writes the new section back into *PSEC.  */
 530
 531 bfd_vma
 532 _bfd_merged_section_offset (output_bfd, psec, psecinfo, offset, addend)
 533      bfd *output_bfd ATTRIBUTE_UNUSED;
 534      asection **psec;
 535      PTR psecinfo;
 536      bfd_vma offset, addend;
 537 {
 538   struct sec_merge_sec_info *secinfo;
 539   struct sec_merge_hash_entry *entry;
 540   unsigned char *p;
 541   asection *sec = *psec;
 542
 543   secinfo = (struct sec_merge_sec_info *) psecinfo;
 544
 545   if (offset + addend >= sec->_raw_size)
 546     {
 547       if (offset + addend > sec->_raw_size)
 548         (*_bfd_error_handler) (_("%s: access beyond end of merged section (%ld + %ld)"),
 549                                bfd_get_filename (sec->owner), (long)offset,
 550                                (long) addend);
 551       return (secinfo->first ? sec->_cooked_size : 0);
 552     }
 553
 554   if (secinfo->htab->strings)
 555     {
 556       if (sec->entsize == 1)
 557         {
 558           p = secinfo->contents + offset + addend - 1;
 559           while (*p && p >= secinfo->contents)
 560             --p;
 561           ++p;
 562         }
 563       else
 564         {
 565           p = secinfo->contents
 566               + ((offset + addend) / sec->entsize) * sec->entsize;
 567           p -= sec->entsize;
 568           while (p >= secinfo->contents)
 569             {
 570               unsigned int i;
 571
 572               for (i = 0; i < sec->entsize; ++i)
 573                 if (p[i] != '\0')
 574                   break;
 575               if (i == sec->entsize)
 576                 break;
 577               p -= sec->entsize;
 578             }
 579           p += sec->entsize;
 580         }
 581     }
 582   else
 583     {
 584       p = secinfo->contents
 585           + ((offset + addend) / sec->entsize) * sec->entsize;
 586     }
 587   entry = sec_merge_hash_lookup (secinfo->htab, p, false);
 588   if (!entry)
 589     {
 590       if (! secinfo->htab->strings)
 591         abort ();
 592       /* This should only happen if somebody points into the padding
 593          after a NUL character but before next entity.  */
 594       if (*p)
 595         abort ();
 596       if (! secinfo->htab->first)
 597         abort ();
 598       entry = secinfo->htab->first;
 599       p = secinfo->contents
 600           + ((offset + addend) / sec->entsize + 1) * sec->entsize
 601           - entry->len;
 602     }
 603
 604   *psec = entry->sec;
 605   return entry->index + (secinfo->contents + offset - p);
 606 }