* aoutx.h (NAME(aout,swap_ext_reloc_in)): Cast bytes->r_index to
[external/binutils.git] / bfd / merge.c
1 /* SEC_MERGE support.
2    Copyright 2001, 2002 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 #include "hashtab.h"
28 #include "libiberty.h"
29
30 struct sec_merge_sec_info;
31
32 /* An entry in the section merge hash table.  */
33
34 struct sec_merge_hash_entry
35 {
36   struct bfd_hash_entry root;
37   /* Length of this entry.  */
38   unsigned int len;
39   /* Start of this string needs to be aligned to
40      alignment octets (not 1 << align).  */
41   unsigned int alignment;
42   union
43   {
44     /* Index within the merged section.  */
45     bfd_size_type index;
46     /* Entity size (if present in suffix hash tables).  */
47     unsigned int entsize;
48     /* Entry this is a suffix of (if alignment is 0).  */
49     struct sec_merge_hash_entry *suffix;
50   } u;
51   /* Which section is it in.  */
52   struct sec_merge_sec_info *secinfo;
53   /* Next entity in the hash table.  */
54   struct sec_merge_hash_entry *next;
55 };
56
57 /* The section merge hash table.  */
58
59 struct sec_merge_hash
60 {
61   struct bfd_hash_table table;
62   /* Next available index.  */
63   bfd_size_type size;
64   /* First entity in the SEC_MERGE sections of this type.  */
65   struct sec_merge_hash_entry *first;
66   /* Last entity in the SEC_MERGE sections of this type.  */
67   struct sec_merge_hash_entry *last;
68   /* Entity size.  */
69   unsigned int entsize;
70   /* Are entries fixed size or zero terminated strings?  */
71   boolean strings;
72 };
73
74 struct sec_merge_info
75 {
76   /* Chain of sec_merge_infos.  */
77   struct sec_merge_info *next;
78   /* Chain of sec_merge_sec_infos.  */
79   struct sec_merge_sec_info *chain;
80   /* A hash table used to hold section content.  */
81   struct sec_merge_hash *htab;
82 };
83
84 struct sec_merge_sec_info
85 {
86   /* Chain of sec_merge_sec_infos.  */
87   struct sec_merge_sec_info *next;
88   /* The corresponding section.  */
89   asection *sec;
90   /* Pointer to merge_info pointing to us.  */
91   PTR *psecinfo;
92   /* A hash table used to hold section content.  */
93   struct sec_merge_hash *htab;
94   /* First string in this section.  */
95   struct sec_merge_hash_entry *first;
96   /* Original section content.  */
97   unsigned char contents[1];
98 };
99
100 static struct bfd_hash_entry *sec_merge_hash_newfunc
101   PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
102 static struct sec_merge_hash_entry *sec_merge_hash_lookup
103   PARAMS ((struct sec_merge_hash *, const char *, unsigned int, boolean));
104 static struct sec_merge_hash *sec_merge_init
105   PARAMS ((unsigned int, boolean));
106 static struct sec_merge_hash_entry *sec_merge_add
107   PARAMS ((struct sec_merge_hash *, const char *, unsigned int,
108            struct sec_merge_sec_info *));
109 static boolean sec_merge_emit
110   PARAMS ((bfd *, struct sec_merge_hash_entry *));
111 static int cmplengthentry PARAMS ((const PTR, const PTR));
112 static int last4_eq PARAMS ((const PTR, const PTR));
113 static int last_eq PARAMS ((const PTR, const PTR));
114 static boolean record_section
115   PARAMS ((struct sec_merge_info *, struct sec_merge_sec_info *));
116 static void merge_strings PARAMS ((struct sec_merge_info *));
117
118 /* Routine to create an entry in a section merge hashtab.  */
119
120 static struct bfd_hash_entry *
121 sec_merge_hash_newfunc (entry, table, string)
122      struct bfd_hash_entry *entry;
123      struct bfd_hash_table *table;
124      const char *string;
125 {
126   struct sec_merge_hash_entry *ret = (struct sec_merge_hash_entry *) entry;
127
128   /* Allocate the structure if it has not already been allocated by a
129      subclass.  */
130   if (ret == (struct sec_merge_hash_entry *) NULL)
131     ret = ((struct sec_merge_hash_entry *)
132            bfd_hash_allocate (table, sizeof (struct sec_merge_hash_entry)));
133   if (ret == (struct sec_merge_hash_entry *) NULL)
134     return NULL;
135
136   /* Call the allocation method of the superclass.  */
137   ret = ((struct sec_merge_hash_entry *)
138          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
139
140   if (ret)
141     {
142       /* Initialize the local fields.  */
143       ret->u.suffix = NULL;
144       ret->alignment = 0;
145       ret->secinfo = NULL;
146       ret->next = NULL;
147     }
148
149   return (struct bfd_hash_entry *) ret;
150 }
151
152 /* Look up an entry in a section merge hash table.  */
153
154 static struct sec_merge_hash_entry *
155 sec_merge_hash_lookup (table, string, alignment, create)
156      struct sec_merge_hash *table;
157      const char *string;
158      unsigned int alignment;
159      boolean create;
160 {
161   register const unsigned char *s;
162   register unsigned long hash;
163   register unsigned int c;
164   struct sec_merge_hash_entry *hashp;
165   unsigned int len, i;
166   unsigned int index;
167
168   hash = 0;
169   len = 0;
170   s = (const unsigned char *) string;
171   if (table->strings)
172     {
173       if (table->entsize == 1)
174         {
175           while ((c = *s++) != '\0')
176             {
177               hash += c + (c << 17);
178               hash ^= hash >> 2;
179               ++len;
180             }
181           hash += len + (len << 17);
182         }
183       else
184         {
185           for (;;)
186             {
187               for (i = 0; i < table->entsize; ++i)
188                 if (s[i] != '\0')
189                   break;
190               if (i == table->entsize)
191                 break;
192               for (i = 0; i < table->entsize; ++i)
193                 {
194                   c = *s++;
195                   hash += c + (c << 17);
196                   hash ^= hash >> 2;
197                 }
198               ++len;
199             }
200           hash += len + (len << 17);
201           len *= table->entsize;
202         }
203       hash ^= hash >> 2;
204       len += table->entsize;
205     }
206   else
207     {
208       for (i = 0; i < table->entsize; ++i)
209         {
210           c = *s++;
211           hash += c + (c << 17);
212           hash ^= hash >> 2;
213         }
214       len = table->entsize;
215     }
216
217   index = hash % table->table.size;
218   for (hashp = (struct sec_merge_hash_entry *) table->table.table[index];
219        hashp != (struct sec_merge_hash_entry *) NULL;
220        hashp = (struct sec_merge_hash_entry *) hashp->root.next)
221     {
222       if (hashp->root.hash == hash
223           && len == hashp->len
224           && memcmp (hashp->root.string, string, len) == 0)
225         {
226           /* If the string we found does not have at least the required
227              alignment, we need to insert another copy.  */
228           if (hashp->alignment < alignment)
229             {
230               /*  Mark the less aligned copy as deleted.  */
231               hashp->len = 0;
232               hashp->alignment = 0;
233               break;
234             }
235           return hashp;
236         }
237     }
238
239   if (! create)
240     return (struct sec_merge_hash_entry *) NULL;
241
242   hashp = (struct sec_merge_hash_entry *)
243           sec_merge_hash_newfunc ((struct bfd_hash_entry *) NULL,
244                                   (struct bfd_hash_table *) table, string);
245   if (hashp == (struct sec_merge_hash_entry *) NULL)
246     return (struct sec_merge_hash_entry *) NULL;
247   hashp->root.string = string;
248   hashp->root.hash = hash;
249   hashp->len = len;
250   hashp->alignment = alignment;
251   hashp->root.next = table->table.table[index];
252   table->table.table[index] = (struct bfd_hash_entry *) hashp;
253
254   return hashp;
255 }
256
257 /* Create a new hash table.  */
258
259 static struct sec_merge_hash *
260 sec_merge_init (entsize, strings)
261      unsigned int entsize;
262      boolean strings;
263 {
264   struct sec_merge_hash *table;
265   bfd_size_type amt = sizeof (struct sec_merge_hash);
266
267   table = (struct sec_merge_hash *) bfd_malloc (amt);
268   if (table == NULL)
269     return NULL;
270
271   if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
272     {
273       free (table);
274       return NULL;
275     }
276
277   table->size = 0;
278   table->first = NULL;
279   table->last = NULL;
280   table->entsize = entsize;
281   table->strings = strings;
282
283   return table;
284 }
285
286 /* Get the index of an entity in a hash table, adding it if it is not
287    already present.  */
288
289 static struct sec_merge_hash_entry *
290 sec_merge_add (tab, str, alignment, secinfo)
291      struct sec_merge_hash *tab;
292      const char *str;
293      unsigned int alignment;
294      struct sec_merge_sec_info *secinfo;
295 {
296   register struct sec_merge_hash_entry *entry;
297
298   entry = sec_merge_hash_lookup (tab, str, alignment, true);
299   if (entry == NULL)
300     return NULL;
301
302   if (entry->secinfo == NULL)
303     {
304       tab->size++;
305       entry->secinfo = secinfo;
306       if (tab->first == NULL)
307         tab->first = entry;
308       else
309         tab->last->next = entry;
310       tab->last = entry;
311     }
312
313   return entry;
314 }
315
316 static boolean
317 sec_merge_emit (abfd, entry)
318      register bfd *abfd;
319      struct sec_merge_hash_entry *entry;
320 {
321   struct sec_merge_sec_info *secinfo = entry->secinfo;
322   asection *sec = secinfo->sec;
323   char *pad = "";
324   bfd_size_type off = 0;
325   int alignment_power = bfd_get_section_alignment (abfd, sec->output_section);
326
327   if (alignment_power)
328     pad = bfd_zmalloc ((bfd_size_type) 1 << alignment_power);
329
330   for (; entry != NULL && entry->secinfo == secinfo; entry = entry->next)
331     {
332       register const char *str;
333       register size_t len;
334
335       len = off & (entry->alignment - 1);
336       if (len)
337         {
338           len = entry->alignment - len;
339           if (bfd_bwrite ((PTR) pad, (bfd_size_type) len, abfd) != len)
340             break;
341           off += len;
342         }
343
344       str = entry->root.string;
345       len = entry->len;
346
347       if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
348         break;
349
350       off += len;
351     }
352
353   if (alignment_power)
354     free (pad);
355
356   return (boolean) (entry == NULL || entry->secinfo != secinfo);
357 }
358
359 /* This function is called for each input file from the add_symbols
360    pass of the linker.  */
361
362 boolean
363 _bfd_merge_section (abfd, psinfo, sec, psecinfo)
364      bfd *abfd;
365      PTR *psinfo;
366      asection *sec;
367      PTR *psecinfo;
368 {
369   struct sec_merge_info *sinfo;
370   struct sec_merge_sec_info *secinfo;
371   unsigned int align;
372   bfd_size_type amt;
373
374   if (sec->_raw_size == 0
375       || (sec->flags & SEC_EXCLUDE)
376       || (sec->flags & SEC_MERGE) == 0
377       || sec->entsize == 0)
378     return true;
379
380   if ((sec->flags & SEC_RELOC) != 0)
381     {
382       /* We aren't prepared to handle relocations in merged sections.  */
383       return true;
384     }
385
386   align = bfd_get_section_alignment (sec->owner, sec);
387   if ((sec->entsize < (unsigned int)(1 << align)
388        && ((sec->entsize & (sec->entsize - 1))
389            || !(sec->flags & SEC_STRINGS)))
390       || (sec->entsize > (unsigned int)(1 << align)
391           && (sec->entsize & ((1 << align) - 1))))
392     {
393       /* Sanity check.  If string character size is smaller than
394          alignment, then we require character size to be a power
395          of 2, otherwise character size must be integer multiple
396          of alignment.  For non-string constants, alignment must
397          be smaller than or equal to entity size and entity size
398          must be integer multiple of alignment.  */
399       return true;
400     }
401
402   for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next)
403     if ((secinfo = sinfo->chain)
404         && ! ((secinfo->sec->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS))
405         && secinfo->sec->entsize == sec->entsize
406         && ! strcmp (secinfo->sec->name, sec->name))
407       break;
408
409   if (sinfo == NULL)
410     {
411       /* Initialize the information we need to keep track of.  */
412       amt = sizeof (struct sec_merge_info);
413       sinfo = (struct sec_merge_info *) bfd_alloc (abfd, amt);
414       if (sinfo == NULL)
415         goto error_return;
416       sinfo->next = (struct sec_merge_info *) *psinfo;
417       sinfo->chain = NULL;
418       *psinfo = (PTR) sinfo;
419       sinfo->htab = sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS));
420       if (sinfo->htab == NULL)
421         goto error_return;
422     }
423
424   /* Read the section from abfd.  */
425
426   amt = sizeof (struct sec_merge_sec_info) + sec->_raw_size - 1;
427   *psecinfo = bfd_alloc (abfd, amt);
428   if (*psecinfo == NULL)
429     goto error_return;
430
431   secinfo = (struct sec_merge_sec_info *)*psecinfo;
432   if (sinfo->chain)
433     {
434       secinfo->next = sinfo->chain->next;
435       sinfo->chain->next = secinfo;
436     }
437   else
438     secinfo->next = secinfo;
439   sinfo->chain = secinfo;
440   secinfo->sec = sec;
441   secinfo->psecinfo = psecinfo;
442   secinfo->htab = sinfo->htab;
443   secinfo->first = NULL;
444
445   if (! bfd_get_section_contents (sec->owner, sec, secinfo->contents,
446                                   (bfd_vma) 0, sec->_raw_size))
447     goto error_return;
448
449   return true;
450
451  error_return:
452   *psecinfo = NULL;
453   return false;
454 }
455
456 /* Compare two sec_merge_hash_entry structures.  This is called via qsort.  */
457
458 static int
459 cmplengthentry (a, b)
460      const PTR a;
461      const PTR b;
462 {
463   struct sec_merge_hash_entry * A = *(struct sec_merge_hash_entry **) a;
464   struct sec_merge_hash_entry * B = *(struct sec_merge_hash_entry **) b;
465
466   if (A->len < B->len)
467     return 1;
468   else if (A->len > B->len)
469     return -1;
470
471   return memcmp (A->root.string, B->root.string, A->len);
472 }
473
474 static int
475 last4_eq (a, b)
476      const PTR a;
477      const PTR b;
478 {
479   struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a;
480   struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b;
481
482   if (memcmp (A->root.string + A->len - 5 * A->u.entsize,
483               B->root.string + B->len - 5 * A->u.entsize,
484               4 * A->u.entsize) != 0)
485     /* This was a hashtable collision.  */
486     return 0;
487
488   if (A->len <= B->len)
489     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
490        not to be equal by the hash table.  */
491     return 0;
492
493   if (A->alignment < B->alignment
494       || ((A->len - B->len) & (B->alignment - 1)))
495     /* The suffix is not sufficiently aligned.  */
496     return 0;
497
498   return memcmp (A->root.string + (A->len - B->len),
499                  B->root.string, B->len - 5 * A->u.entsize) == 0;
500 }
501
502 static int
503 last_eq (a, b)
504      const PTR a;
505      const PTR b;
506 {
507   struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a;
508   struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b;
509
510   if (B->len >= 5 * A->u.entsize)
511     /* Longer strings are just pushed into the hash table,
512        they'll be used when looking up for very short strings.  */
513     return 0;
514
515   if (memcmp (A->root.string + A->len - 2 * A->u.entsize,
516               B->root.string + B->len - 2 * A->u.entsize,
517               A->u.entsize) != 0)
518     /* This was a hashtable collision.  */
519     return 0;
520
521   if (A->len <= B->len)
522     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
523        not to be equal by the hash table.  */
524     return 0;
525
526   if (A->alignment < B->alignment
527       || ((A->len - B->len) & (B->alignment - 1)))
528     /* The suffix is not sufficiently aligned.  */
529     return 0;
530
531   return memcmp (A->root.string + (A->len - B->len),
532                  B->root.string, B->len - 2 * A->u.entsize) == 0;
533 }
534
535 /* Record one section into the hash table.  */
536 static boolean
537 record_section (sinfo, secinfo)
538      struct sec_merge_info *sinfo;
539      struct sec_merge_sec_info *secinfo;
540 {
541   asection *sec = secinfo->sec;
542   struct sec_merge_hash_entry *entry;
543   boolean nul;
544   unsigned char *p, *end;
545   bfd_vma mask, eltalign;
546   unsigned int align, i;
547
548   align = bfd_get_section_alignment (sec->owner, sec);
549   end = secinfo->contents + sec->_raw_size;
550   nul = false;
551   mask = ((bfd_vma) 1 << align) - 1;
552   if (sec->flags & SEC_STRINGS)
553     {
554       for (p = secinfo->contents; p < end; )
555         {
556           eltalign = p - secinfo->contents;
557           eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1;
558           if (!eltalign || eltalign > mask)
559             eltalign = mask + 1;
560           entry = sec_merge_add (sinfo->htab, p, (unsigned) eltalign, secinfo);
561           if (! entry)
562             goto error_return;
563           p += entry->len;
564           if (sec->entsize == 1)
565             {
566               while (p < end && *p == 0)
567                 {
568                   if (!nul && !((p - secinfo->contents) & mask))
569                     {
570                       nul = true;
571                       entry = sec_merge_add (sinfo->htab, "",
572                                              (unsigned) mask + 1, secinfo);
573                       if (! entry)
574                         goto error_return;
575                     }
576                   p++;
577                 }
578             }
579           else
580             {
581               while (p < end)
582                 {
583                   for (i = 0; i < sec->entsize; i++)
584                     if (p[i] != '\0')
585                       break;
586                   if (i != sec->entsize)
587                     break;
588                   if (!nul && !((p - secinfo->contents) & mask))
589                     {
590                       nul = true;
591                       entry = sec_merge_add (sinfo->htab, p,
592                                              (unsigned) mask + 1, secinfo);
593                       if (! entry)
594                         goto error_return;
595                     }
596                   p += sec->entsize;
597                 }
598             }
599         }
600     }
601   else
602     {
603       for (p = secinfo->contents; p < end; p += sec->entsize)
604         {
605           entry = sec_merge_add (sinfo->htab, p, 1, secinfo);
606           if (! entry)
607             goto error_return;
608         }
609     }
610
611   return true;
612
613 error_return:
614   for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
615     *secinfo->psecinfo = NULL;
616   return false;
617 }
618
619 /* This is a helper function for _bfd_merge_sections.  It attempts to
620    merge strings matching suffixes of longer strings.  */
621 static void
622 merge_strings (sinfo)
623      struct sec_merge_info *sinfo;
624 {
625   struct sec_merge_hash_entry **array, **a, **end, *e;
626   struct sec_merge_sec_info *secinfo;
627   htab_t lasttab = NULL, last4tab = NULL;
628   bfd_size_type size, amt;
629
630   /* Now sort the strings by length, longest first.  */
631   array = NULL;
632   amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *);
633   array = (struct sec_merge_hash_entry **) bfd_malloc (amt);
634   if (array == NULL)
635     goto alloc_failure;
636
637   for (e = sinfo->htab->first, a = array; e; e = e->next)
638     if (e->alignment)
639       *a++ = e;
640
641   sinfo->htab->size = a - array;
642
643   qsort (array, (size_t) sinfo->htab->size,
644          sizeof (struct sec_merge_hash_entry *), cmplengthentry);
645
646   last4tab = htab_create_alloc ((size_t) sinfo->htab->size * 4, 
647                                 NULL, last4_eq, NULL, calloc, free);
648   lasttab = htab_create_alloc ((size_t) sinfo->htab->size * 4, 
649                                NULL, last_eq, NULL, calloc, free);
650   if (lasttab == NULL || last4tab == NULL)
651     goto alloc_failure;
652
653   /* Now insert the strings into hash tables (strings with last 4 characters
654      and strings with last character equal), look for longer strings which
655      we're suffix of.  */
656   for (a = array, end = array + sinfo->htab->size; a < end; a++)
657     {
658       register hashval_t hash;
659       unsigned int c;
660       unsigned int i;
661       const unsigned char *s;
662       PTR *p;
663
664       e = *a;
665       e->u.entsize = sinfo->htab->entsize;
666       if (e->len <= e->u.entsize)
667         break;
668       if (e->len > 4 * e->u.entsize)
669         {
670           s = (const unsigned char *) (e->root.string + e->len - e->u.entsize);
671           hash = 0;
672           for (i = 0; i < 4 * e->u.entsize; i++)
673             {
674               c = *--s;
675               hash += c + (c << 17);
676               hash ^= hash >> 2;
677             }
678           p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
679           if (p == NULL)
680             goto alloc_failure;
681           if (*p)
682             {
683               struct sec_merge_hash_entry *ent;
684
685               ent = (struct sec_merge_hash_entry *) *p;
686               e->u.suffix = ent;
687               e->alignment = 0;
688               continue;
689             }
690           else
691             *p = (PTR) e;
692         }
693       s = (const unsigned char *) (e->root.string + e->len - e->u.entsize);
694       hash = 0;
695       for (i = 0; i < e->u.entsize; i++)
696         {
697           c = *--s;
698           hash += c + (c << 17);
699           hash ^= hash >> 2;
700         }
701       p = htab_find_slot_with_hash (lasttab, e, hash, INSERT);
702       if (p == NULL)
703         goto alloc_failure;
704       if (*p)
705         {
706           struct sec_merge_hash_entry *ent;
707
708           ent = (struct sec_merge_hash_entry *) *p;
709           e->u.suffix = ent;
710           e->alignment = 0;
711         }
712       else
713         *p = (PTR) e;
714     }
715
716 alloc_failure:
717   if (array)
718     free (array);
719   if (lasttab)
720     htab_delete (lasttab);
721   if (last4tab)
722     htab_delete (last4tab);
723
724   /* Now assign positions to the strings we want to keep.  */
725   size = 0;
726   secinfo = sinfo->htab->first->secinfo;
727   for (e = sinfo->htab->first; e; e = e->next)
728     {
729       if (e->secinfo != secinfo)
730         {
731           secinfo->sec->_cooked_size = size;
732           secinfo = e->secinfo;
733         }
734       if (e->alignment)
735         {
736           if (e->secinfo->first == NULL)
737             {
738               e->secinfo->first = e;
739               size = 0;
740             }
741           size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1);
742           e->u.index = size;
743           size += e->len;
744         }
745     }
746   secinfo->sec->_cooked_size = size;
747
748   /* And now adjust the rest, removing them from the chain (but not hashtable)
749      at the same time.  */
750   for (a = &sinfo->htab->first, e = *a; e; e = e->next)
751     if (e->alignment)
752       a = &e->next;
753     else
754       {
755         *a = e->next;
756         if (e->len)
757           {
758             e->secinfo = e->u.suffix->secinfo;
759             e->alignment = e->u.suffix->alignment;
760             e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len);
761           }
762       }
763 }
764
765 /* This function is called once after all SEC_MERGE sections are registered
766    with _bfd_merge_section.  */
767
768 boolean
769 _bfd_merge_sections (abfd, xsinfo, remove_hook)
770      bfd *abfd ATTRIBUTE_UNUSED;
771      PTR xsinfo;
772      void (*remove_hook) PARAMS((bfd *, asection *));
773 {
774   struct sec_merge_info *sinfo;
775
776   for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next)
777     {
778       struct sec_merge_sec_info * secinfo;
779
780       if (! sinfo->chain)
781         continue;
782
783       /* Move sinfo->chain to head of the chain, terminate it.  */
784       secinfo = sinfo->chain;
785       sinfo->chain = secinfo->next;
786       secinfo->next = NULL;
787
788       /* Record the sections into the hash table.  */
789       for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
790         if (secinfo->sec->flags & SEC_EXCLUDE)
791           {
792             *secinfo->psecinfo = NULL;
793             if (remove_hook)
794               (*remove_hook) (abfd, secinfo->sec);
795           }
796         else if (! record_section (sinfo, secinfo))
797           break;
798
799       if (secinfo)
800         continue;
801
802       if (sinfo->htab->first == NULL)
803         continue;
804
805       if (sinfo->htab->strings)
806         merge_strings (sinfo);
807       else
808         {
809           struct sec_merge_hash_entry *e;
810           bfd_size_type size = 0;
811
812           /* Things are much simpler for non-strings.
813              Just assign them slots in the section.  */
814           secinfo = NULL;
815           for (e = sinfo->htab->first; e; e = e->next)
816             {
817               if (e->secinfo->first == NULL)
818                 {
819                   if (secinfo)
820                     secinfo->sec->_cooked_size = size;
821                   e->secinfo->first = e;
822                   size = 0;
823                 }
824               size = (size + e->alignment - 1)
825                      & ~((bfd_vma) e->alignment - 1);
826               e->u.index = size;
827               size += e->len;
828               secinfo = e->secinfo;
829             }
830           secinfo->sec->_cooked_size = size;
831         }
832
833         /* Finally shrink all input sections which have not made it into
834            the hash table at all.  */
835         for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
836           if (secinfo->first == NULL)
837             secinfo->sec->_cooked_size = 0;
838     }
839
840   return true;
841 }
842
843 /* Write out the merged section.  */
844
845 boolean
846 _bfd_write_merged_section (output_bfd, sec, psecinfo)
847      bfd *output_bfd;
848      asection *sec;
849      PTR psecinfo;
850 {
851   struct sec_merge_sec_info *secinfo;
852   file_ptr pos;
853
854   secinfo = (struct sec_merge_sec_info *) psecinfo;
855
856   if (!secinfo->first)
857     return true;
858
859   pos = sec->output_section->filepos + sec->output_offset;
860   if (bfd_seek (output_bfd, pos, SEEK_SET) != 0)
861     return false;
862
863   if (! sec_merge_emit (output_bfd, secinfo->first))
864     return false;
865
866   return true;
867 }
868
869 /* Adjust an address in the SEC_MERGE section.  Given OFFSET within
870    *PSEC, this returns the new offset in the adjusted SEC_MERGE
871    section and writes the new section back into *PSEC.  */
872
873 bfd_vma
874 _bfd_merged_section_offset (output_bfd, psec, psecinfo, offset, addend)
875      bfd *output_bfd ATTRIBUTE_UNUSED;
876      asection **psec;
877      PTR psecinfo;
878      bfd_vma offset, addend;
879 {
880   struct sec_merge_sec_info *secinfo;
881   struct sec_merge_hash_entry *entry;
882   unsigned char *p;
883   asection *sec = *psec;
884
885   secinfo = (struct sec_merge_sec_info *) psecinfo;
886
887   if (offset + addend >= sec->_raw_size)
888     {
889       if (offset + addend > sec->_raw_size)
890         {
891           (*_bfd_error_handler)
892             (_("%s: access beyond end of merged section (%ld + %ld)"),
893              bfd_get_filename (sec->owner), (long) offset, (long) addend);
894         }
895       return (secinfo->first ? sec->_cooked_size : 0);
896     }
897
898   if (secinfo->htab->strings)
899     {
900       if (sec->entsize == 1)
901         {
902           p = secinfo->contents + offset + addend - 1;
903           while (p >= secinfo->contents && *p)
904             --p;
905           ++p;
906         }
907       else
908         {
909           p = secinfo->contents
910               + ((offset + addend) / sec->entsize) * sec->entsize;
911           p -= sec->entsize;
912           while (p >= secinfo->contents)
913             {
914               unsigned int i;
915
916               for (i = 0; i < sec->entsize; ++i)
917                 if (p[i] != '\0')
918                   break;
919               if (i == sec->entsize)
920                 break;
921               p -= sec->entsize;
922             }
923           p += sec->entsize;
924         }
925     }
926   else
927     {
928       p = secinfo->contents
929           + ((offset + addend) / sec->entsize) * sec->entsize;
930     }
931   entry = sec_merge_hash_lookup (secinfo->htab, p, 0, false);
932   if (!entry)
933     {
934       if (! secinfo->htab->strings)
935         abort ();
936       /* This should only happen if somebody points into the padding
937          after a NUL character but before next entity.  */
938       if (*p)
939         abort ();
940       if (! secinfo->htab->first)
941         abort ();
942       entry = secinfo->htab->first;
943       p = secinfo->contents
944           + ((offset + addend) / sec->entsize + 1) * sec->entsize
945           - entry->len;
946     }
947
948   *psec = entry->secinfo->sec;
949   return entry->u.index + (secinfo->contents + offset - p);
950 }