bfd/linker.c

   1 /* linker.c -- BFD linker routines
   2    Copyright 1993 Free Software Foundation, Inc.
   3    Written by Steve Chamberlain and Ian Lance Taylor, Cygnus Support
   4
   5 This file is part of BFD
   6
   7 GLD 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, or (at your option)
  10 any later version.
  11
  12 GLD 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 GLD; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21 #include "bfd.h"
  22 #include "sysdep.h"
  23 #include "libbfd.h"
  24 #include "bfdlink.h"
  25 #include "genlink.h"
  26
  27 /*
  28 SECTION
  29         Linker Functions
  30
  31 @cindex Linker
  32         The linker uses three special entry points in the BFD target
  33         vector.  It is not necessary to write special routines for
  34         these entry points when creating a new BFD back end, since
  35         generic versions are provided.  However, writing them can
  36         speed up linking and make it use significantly less runtime
  37         memory.
  38
  39         The first routine creates a hash table used by the other
  40         routines.  The second routine adds the symbols from an object
  41         file to the hash table.  The third routine takes all the
  42         object files and links them together to create the output
  43         file.  These routines are designed so that the linker proper
  44         does not need to know anything about the symbols in the object
  45         files that it is linking.  The linker merely arranges the
  46         sections as directed by the linker script and lets BFD handle
  47         the details of symbols and relocs.
  48
  49         The second routine and third routines are passed a pointer to
  50         a <<struct bfd_link_info>> structure (defined in
  51         <<bfdlink.h>>) which holds information relevant to the link,
  52         including the linker hash table (which was created by the
  53         first routine) and a set of callback functions to the linker
  54         proper.
  55
  56         The generic linker routines are in <<linker.c>>, and use the
  57         header file <<genlink.h>>.  As of this writing, the only back
  58         ends which have implemented versions of these routines are
  59         a.out (in <<aoutx.h>>) and ECOFF (in <<ecoff.c>>).  The a.out
  60         routines are used as examples throughout this section.
  61
  62 @menu
  63 @* Creating a Linker Hash Table::
  64 @* Adding Symbols to the Hash Table::
  65 @* Performing the Final Link::
  66 @end menu
  67
  68 INODE
  69 Creating a Linker Hash Table, Adding Symbols to the Hash Table, Linker Functions, Linker Functions
  70 SUBSECTION
  71         Creating a linker hash table
  72
  73 @cindex _bfd_link_hash_table_create in target vector
  74 @cindex target vector (_bfd_link_hash_table_create)
  75         The linker routines must create a hash table, which must be
  76         derived from <<struct bfd_link_hash_table>> described in
  77         <<bfdlink.c>>.  @xref{Hash Tables} for information on how to
  78         create a derived hash table.  This entry point is called using
  79         the target vector of the linker output file.
  80
  81         The <<_bfd_link_hash_table_create>> entry point must allocate
  82         and initialize an instance of the desired hash table.  If the
  83         back end does not require any additional information to be
  84         stored with the entries in the hash table, the entry point may
  85         simply create a <<struct bfd_link_hash_table>>.  Most likely,
  86         however, some additional information will be needed.
  87
  88         For example, with each entry in the hash table the a.out
  89         linker keeps the index the symbol has in the final output file
  90         (this index number is used so that when doing a relocateable
  91         link the symbol index used in the output file can be quickly
  92         filled in when copying over a reloc).  The a.out linker code
  93         defines the required structures and functions for a hash table
  94         derived from <<struct bfd_link_hash_table>>.  The a.out linker
  95         hash table is created by the function
  96         <<NAME(aout,link_hash_table_create)>>; it simply allocates
  97         space for the hash table, initializes it, and returns a
  98         pointer to it.
  99
 100         When writing the linker routines for a new back end, you will
 101         generally not know exactly which fields will be required until
 102         you have finished.  You should simply create a new hash table
 103         which defines no additional fields, and then simply add fields
 104         as they become necessary.
 105
 106 INODE
 107 Adding Symbols to the Hash Table, Performing the Final Link, Creating a Linker Hash Table, Linker Functions
 108 SUBSECTION
 109         Adding symbols to the hash table
 110
 111 @cindex _bfd_link_add_symbols in target vector
 112 @cindex target vector (_bfd_link_add_symbols)
 113         The linker proper will call the <<_bfd_link_add_symbols>>
 114         entry point for each object file or archive which is to be
 115         linked (typically these are the files named on the command
 116         line, but some may also come from the linker script).  The
 117         entry point is responsible for examining the file.  For an
 118         object file, BFD must add any relevant symbol information to
 119         the hash table.  For an archive, BFD must determine which
 120         elements of the archive should be used and adding them to the
 121         link.
 122
 123         The a.out version of this entry point is
 124         <<NAME(aout,link_add_symbols)>>.
 125
 126 @menu
 127 @* Differing file formats::
 128 @* Adding symbols from an object file::
 129 @* Adding symbols from an archive::
 130 @end menu
 131
 132 INODE
 133 Differing file formats, Adding symbols from an object file, Adding Symbols to the Hash Table, Adding Symbols to the Hash Table
 134 SUBSUBSECTION
 135         Differing file formats
 136
 137         Normally all the files involved in a link will be of the same
 138         format, but it is also possible to link together different
 139         format object files, and the back end must support that.  The
 140         <<_bfd_link_add_symbols>> entry point is called via the target
 141         vector of the file to be added.  This has an important
 142         consequence: the function may not assume that the hash table
 143         is the type created by the corresponding
 144         <<_bfd_link_hash_table_create>> vector.  All the
 145         <<_bfd_link_add_symbols>> function can assume about the hash
 146         table is that it is derived from <<struct
 147         bfd_link_hash_table>>.
 148
 149         Sometimes the <<_bfd_link_add_symbols>> function must store
 150         some information in the hash table entry to be used by the
 151         <<_bfd_final_link>> function.  In such a case the <<creator>>
 152         field of the hash table must be checked to make sure that the
 153         hash table was created by an object file of the same format.
 154
 155         The <<_bfd_final_link>> routine must be prepared to handle a
 156         hash entry without any extra information added by the
 157         <<_bfd_link_add_symbols>> function.  A hash entry without
 158         extra information will also occur when the linker script
 159         directs the linker to create a symbol.  Note that, regardless
 160         of how a hash table entry is added, all the fields will be
 161         initialized to some sort of null value by the hash table entry
 162         initialization function.
 163
 164         See <<ecoff_link_add_externals>> for an example of how to
 165         check the <<creator>> field before saving information (in this
 166         case, the ECOFF external symbol debugging information) in a
 167         hash table entry.
 168
 169 INODE
 170 Adding symbols from an object file, Adding symbols from an archive, Differing file formats, Adding Symbols to the Hash Table
 171 SUBSUBSECTION
 172         Adding symbols from an object file
 173
 174         When the <<_bfd_link_add_symbols>> routine is passed an object
 175         file, it must add all externally visible symbols in that
 176         object file to the hash table.  The actual work of adding the
 177         symbol to the hash table is normally handled by the function
 178         <<_bfd_generic_link_add_one_symbol>>.  The
 179         <<_bfd_link_add_symbols>> routine is responsible for reading
 180         all the symbols from the object file and passing the correct
 181         information to <<_bfd_generic_link_add_one_symbol>>.
 182
 183         The <<_bfd_link_add_symbols>> routine should not use
 184         <<bfd_canonicalize_symtab>> to read the symbols.  The point of
 185         providing this routine is to avoid the overhead of converting
 186         the symbols into generic <<asymbol>> structures.
 187
 188 @findex _bfd_generic_link_add_one_symbol
 189         <<_bfd_generic_link_add_one_symbol>> handles the details of
 190         combining common symbols, warning about multiple definitions,
 191         and so forth.  It takes arguments which describe the symbol to
 192         add, notably symbol flags, a section, and an offset.  The
 193         symbol flags include such things as <<BSF_WEAK>> or
 194         <<BSF_INDIRECT>>.  The section is a section in the object
 195         file, or something like <<bfd_und_section>> for an undefined
 196         symbol or <<bfd_com_section>> for a common symbol.
 197
 198         If the <<_bfd_final_link>> routine is also going to need to
 199         read the symbol information, the <<_bfd_link_add_symbols>>
 200         routine should save it somewhere attached to the object file
 201         BFD.  However, the information should only be saved if the
 202         <<keep_memory>> field of the <<info>> argument is true, so
 203         that the <<-no-keep-memory>> linker switch is effective.
 204
 205         The a.out function which adds symbols from an object file is
 206         <<aout_link_add_object_symbols>>, and most of the interesting
 207         work is in <<aout_link_add_symbols>>.  The latter saves
 208         pointers to the hash tables entries created by
 209         <<_bfd_generic_link_add_one_symbol>> indexed by symbol number,
 210         so that the <<_bfd_final_link>> routine does not have to call
 211         the hash table lookup routine to locate the entry.
 212
 213 INODE
 214 Adding symbols from an archive, , Adding symbols from an object file, Adding Symbols to the Hash Table
 215 SUBSUBSECTION
 216         Adding symbols from an archive
 217
 218         When the <<_bfd_link_add_symbols>> routine is passed an
 219         archive, it must look through the symbols defined by the
 220         archive and decide which elements of the archive should be
 221         included in the link.  For each such element it must call the
 222         <<add_archive_element>> linker callback, and it must add the
 223         symbols from the object file to the linker hash table.
 224
 225 @findex _bfd_generic_link_add_archive_symbols
 226         In most cases the work of looking through the symbols in the
 227         archive should be done by the
 228         <<_bfd_generic_link_add_archive_symbols>> function.  This
 229         function builds a hash table from the archive symbol table and
 230         looks through the list of undefined symbols to see which
 231         elements should be included.
 232         <<_bfd_generic_link_add_archive_symbols>> is passed a function
 233         to call to make the final decision about adding an archive
 234         element to the link and to do the actual work of adding the
 235         symbols to the linker hash table.
 236
 237         The function passed to
 238         <<_bfd_generic_link_add_archive_symbols>> must read the
 239         symbols of the archive element and decide whether the archive
 240         element should be included in the link.  If the element is to
 241         be included, the <<add_archive_element>> linker callback
 242         routine must be called with the element as an argument, and
 243         the elements symbols must be added to the linker hash table
 244         just as though the element had itself been passed to the
 245         <<_bfd_link_add_symbols>> function.
 246
 247         When the a.out <<_bfd_link_add_symbols>> function receives an
 248         archive, it calls <<_bfd_generic_link_add_archive_symbols>>
 249         passing <<aout_link_check_archive_element>> as the function
 250         argument. <<aout_link_check_archive_element>> calls
 251         <<aout_link_check_ar_symbols>>.  If the latter decides to add
 252         the element (an element is only added if it provides a real,
 253         non-common, definition for a previously undefined or common
 254         symbol) it calls the <<add_archive_element>> callback and then
 255         <<aout_link_check_archive_element>> calls
 256         <<aout_link_add_symbols>> to actually add the symbols to the
 257         linker hash table.
 258
 259         The ECOFF back end is unusual in that it does not normally
 260         call <<_bfd_generic_link_add_archive_symbols>>, because ECOFF
 261         archives already contain a hash table of symbols.  The ECOFF
 262         back end searches the archive itself to avoid the overhead of
 263         creating a new hash table.
 264
 265 INODE
 266 Performing the Final Link, , Adding Symbols to the Hash Table, Linker Functions
 267 SUBSECTION
 268         Performing the final link
 269
 270 @cindex _bfd_link_final_link in target vector
 271 @cindex target vector (_bfd_final_link)
 272         When all the input files have been processed, the linker calls
 273         the <<_bfd_final_link>> entry point of the output BFD.  This
 274         routine is responsible for producing the final output file,
 275         which has several aspects.  It must relocate the contents of
 276         the input sections and copy the data into the output sections.
 277         It must build an output symbol table including any local
 278         symbols from the input files and the global symbols from the
 279         hash table.  When producing relocateable output, it must
 280         modify the input relocs and write them into the output file.
 281         There may also be object format dependent work to be done.
 282
 283         The linker will also call the <<write_object_contents>> entry
 284         point when the BFD is closed.  The two entry points must work
 285         together in order to produce the correct output file.
 286
 287         The details of how this works are inevitably dependent upon
 288         the specific object file format.  The a.out
 289         <<_bfd_final_link>> routine is <<NAME(aout,final_link)>>.
 290
 291 @menu
 292 @* Information provided by the linker::
 293 @* Relocating the section contents::
 294 @* Writing the symbol table::
 295 @end menu
 296
 297 INODE
 298 Information provided by the linker, Relocating the section contents, Performing the Final Link, Performing the Final Link
 299 SUBSUBSECTION
 300         Information provided by the linker
 301
 302         Before the linker calls the <<_bfd_final_link>> entry point,
 303         it sets up some data structures for the function to use.
 304
 305         The <<input_bfds>> field of the <<bfd_link_info>> structure
 306         will point to a list of all the input files included in the
 307         link.  These files are linked through the <<link_next>> field
 308         of the <<bfd>> structure.
 309
 310         Each section in the output file will have a list of
 311         <<link_order>> structures attached to the <<link_order_head>>
 312         field (the <<link_order>> structure is defined in
 313         <<bfdlink.h>>).  These structures describe how to create the
 314         contents of the output section in terms of the contents of
 315         various input sections, fill constants, and, eventually, other
 316         types of information.
 317
 318 INODE
 319 Relocating the section contents, Writing the symbol table, Information provided by the linker, Performing the Final Link
 320 SUBSUBSECTION
 321         Relocating the section contents
 322
 323         The <<_bfd_final_link>> function should look through the
 324         <<link_order>> structures attached to each section of the
 325         output file.  Each <<link_order>> structure should either be
 326         handled specially, or it should be passed to the function
 327         <<_bfd_default_link_order>> which will do the right thing
 328         (<<_bfd_default_link_order>> is defined in <<linker.c>>).
 329
 330         For efficiency, a <<link_order>> of type
 331         <<bfd_indirect_link_order>> whose associated section belongs
 332         to a BFD of the same format as the output BFD must be handled
 333         specially.  This type of <<link_order>> describes part of an
 334         output section in terms of a section belonging to one of the
 335         input files.  The <<_bfd_final_link>> function should read the
 336         contents of the section and any associated relocs, apply the
 337         relocs to the section contents, and write out the modified
 338         section contents.  If performing a relocateable link, the
 339         relocs themselves must also be modified and written out.
 340
 341 @findex _bfd_relocate_contents
 342 @findex _bfd_final_link_relocate
 343         The functions <<_bfd_relocate_contents>> and
 344         <<_bfd_final_link_relocate>> provide some general support for
 345         performing the actual relocations, notably overflow checking.
 346         Their arguments include information about the symbol the
 347         relocation is against and a <<reloc_howto_type>> argument
 348         which describes the relocation to perform.  These functions
 349         are defined in <<reloc.c>>.
 350
 351         The a.out function which handles reading, relocating, and
 352         writing section contents is <<aout_link_input_section>>.  The
 353         actual relocation is done in <<aout_link_input_section_std>>
 354         and <<aout_link_input_section_ext>>.
 355
 356 INODE
 357 Writing the symbol table, , Relocating the section contents, Performing the Final Link
 358 SUBSUBSECTION
 359         Writing the symbol table
 360
 361         The <<_bfd_final_link>> function must gather all the symbols
 362         in the input files and write them out.  It must also write out
 363         all the symbols in the global hash table.  This must be
 364         controlled by the <<strip>> and <<discard>> fields of the
 365         <<bfd_link_info>> structure.
 366
 367         The local symbols of the input files will not have been
 368         entered into the linker hash table.  The <<_bfd_final_link>>
 369         routine must consider each input file and include the symbols
 370         in the output file.  It may be convenient to do this when
 371         looking through the <<link_order>> structures, or it may be
 372         done by stepping through the <<input_bfds>> list.
 373
 374         The <<_bfd_final_link>> routine must also traverse the global
 375         hash table to gather all the externally visible symbols.  It
 376         is possible that most of the externally visible symbols may be
 377         written out when considering the symbols of each input file,
 378         but it is still necessary to traverse the hash table since the
 379         linker script may have defined some symbols that are not in
 380         any of the input files.  The <<written>> field in the
 381         <<bfd_link_hash_entry>> structure may be used to determine
 382         which entries in the hash table have not already been written
 383         out.
 384
 385         The <<strip>> field of the <<bfd_link_info>> structure
 386         controls which symbols are written out.  The possible values
 387         are listed in <<bfdlink.h>>.  If the value is <<strip_some>>,
 388         then the <<keep_hash>> field of the <<bfd_link_info>>
 389         structure is a hash table of symbols to keep; each symbol
 390         should be looked up in this hash table, and only symbols which
 391         are present should be included in the output file.
 392
 393         If the <<strip>> field of the <<bfd_link_info>> structure
 394         permits local symbols to be written out, the <<discard>> field
 395         is used to further controls which local symbols are included
 396         in the output file.  If the value is <<discard_l>>, then all
 397         local symbols which begin with a certain prefix are discarded;
 398         this prefix is described by the <<lprefix>> and
 399         <<lprefix_len>> fields of the <<bfd_link_info>> structure.
 400
 401         The a.out backend handles symbols by calling
 402         <<aout_link_write_symbols>> on each input BFD and then
 403         traversing the global hash table with the function
 404         <<aout_link_write_other_symbol>>.  It builds a string table
 405         while writing out the symbols, which is written to the output
 406         file at the end of <<NAME(aout,final_link)>>.
 407 */
 408
 409 static struct bfd_hash_entry *generic_link_hash_newfunc
 410   PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *,
 411            const char *));
 412 static boolean generic_link_add_object_symbols
 413   PARAMS ((bfd *, struct bfd_link_info *));
 414 static boolean generic_link_check_archive_element
 415   PARAMS ((bfd *, struct bfd_link_info *, boolean *pneeded));
 416 static boolean generic_link_add_symbol_list
 417   PARAMS ((bfd *, struct bfd_link_info *, bfd_size_type count, asymbol **));
 418 static boolean generic_add_output_symbol
 419   PARAMS ((bfd *, size_t *psymalloc, asymbol *));
 420 static boolean default_fill_link_order
 421   PARAMS ((bfd *, struct bfd_link_info *, asection *,
 422            struct bfd_link_order *));
 423 static boolean default_indirect_link_order
 424   PARAMS ((bfd *, struct bfd_link_info *, asection *,
 425            struct bfd_link_order *));
 426
 427 /* The link hash table structure is defined in bfdlink.h.  It provides
 428    a base hash table which the backend specific hash tables are built
 429    upon.  */
 430
 431 /* Routine to create an entry in the link hash table.  */
 432
 433 struct bfd_hash_entry *
 434 _bfd_link_hash_newfunc (entry, table, string)
 435      struct bfd_hash_entry *entry;
 436      struct bfd_hash_table *table;
 437      const char *string;
 438 {
 439   struct bfd_link_hash_entry *ret = (struct bfd_link_hash_entry *) entry;
 440
 441   /* Allocate the structure if it has not already been allocated by a
 442      subclass.  */
 443   if (ret == (struct bfd_link_hash_entry *) NULL)
 444     ret = ((struct bfd_link_hash_entry *)
 445            bfd_hash_allocate (table, sizeof (struct bfd_link_hash_entry)));
 446
 447   /* Call the allocation method of the superclass.  */
 448   ret = ((struct bfd_link_hash_entry *)
 449          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
 450
 451   /* Initialize the local fields.  */
 452   ret->type = bfd_link_hash_new;
 453   ret->written = false;
 454   ret->next = NULL;
 455
 456   return (struct bfd_hash_entry *) ret;
 457 }
 458
 459 /* Initialize a link hash table.  The BFD argument is the one
 460    responsible for creating this table.  */
 461
 462 boolean
 463 _bfd_link_hash_table_init (table, abfd, newfunc)
 464      struct bfd_link_hash_table *table;
 465      bfd *abfd;
 466      struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *,
 467                                                 struct bfd_hash_table *,
 468                                                 const char *));
 469 {
 470   table->creator = abfd->xvec;
 471   table->undefs = NULL;
 472   table->undefs_tail = NULL;
 473   return bfd_hash_table_init (&table->table, newfunc);
 474 }
 475
 476 /* Look up a symbol in a link hash table.  If follow is true, we
 477    follow bfd_link_hash_indirect and bfd_link_hash_warning links to
 478    the real symbol.  */
 479
 480 struct bfd_link_hash_entry *
 481 bfd_link_hash_lookup (table, string, create, copy, follow)
 482      struct bfd_link_hash_table *table;
 483      const char *string;
 484      boolean create;
 485      boolean copy;
 486      boolean follow;
 487 {
 488   struct bfd_link_hash_entry *ret;
 489
 490   ret = ((struct bfd_link_hash_entry *)
 491          bfd_hash_lookup (&table->table, string, create, copy));
 492
 493   if (follow && ret != (struct bfd_link_hash_entry *) NULL)
 494     {
 495       while (ret->type == bfd_link_hash_indirect
 496              || ret->type == bfd_link_hash_warning)
 497         ret = ret->u.i.link;
 498     }
 499
 500   return ret;
 501 }
 502
 503 /* Traverse a generic link hash table.  The only reason this is not a
 504    macro is to do better type checking.  This code presumes that an
 505    argument passed as a struct bfd_hash_entry * may be caught as a
 506    struct bfd_link_hash_entry * with no explicit cast required on the
 507    call.  */
 508
 509 void
 510 bfd_link_hash_traverse (table, func, info)
 511      struct bfd_link_hash_table *table;
 512      boolean (*func) PARAMS ((struct bfd_link_hash_entry *, PTR));
 513      PTR info;
 514 {
 515   bfd_hash_traverse (&table->table,
 516                      ((boolean (*) PARAMS ((struct bfd_hash_entry *, PTR)))
 517                       func),
 518                      info);
 519 }
 520
 521 /* Add a symbol to the linker hash table undefs list.  */
 522
 523 INLINE void
 524 bfd_link_add_undef (table, h)
 525      struct bfd_link_hash_table *table;
 526      struct bfd_link_hash_entry *h;
 527 {
 528   BFD_ASSERT (h->next == NULL);
 529   if (table->undefs_tail != (struct bfd_link_hash_entry *) NULL)
 530     table->undefs_tail->next = h;
 531   if (table->undefs == (struct bfd_link_hash_entry *) NULL)
 532     table->undefs = h;
 533   table->undefs_tail = h;
 534 }
 535 \f
 536 /* Routine to create an entry in an generic link hash table.  */
 537
 538 static struct bfd_hash_entry *
 539 generic_link_hash_newfunc (entry, table, string)
 540      struct bfd_hash_entry *entry;
 541      struct bfd_hash_table *table;
 542      const char *string;
 543 {
 544   struct generic_link_hash_entry *ret =
 545     (struct generic_link_hash_entry *) entry;
 546
 547   /* Allocate the structure if it has not already been allocated by a
 548      subclass.  */
 549   if (ret == (struct generic_link_hash_entry *) NULL)
 550     ret = ((struct generic_link_hash_entry *)
 551            bfd_hash_allocate (table, sizeof (struct generic_link_hash_entry)));
 552
 553   /* Call the allocation method of the superclass.  */
 554   ret = ((struct generic_link_hash_entry *)
 555          _bfd_link_hash_newfunc ((struct bfd_hash_entry *) ret,
 556                                  table, string));
 557
 558   /* Set local fields.  */
 559   ret->sym = NULL;
 560
 561   return (struct bfd_hash_entry *) ret;
 562 }
 563
 564 /* Create an generic link hash table.  */
 565
 566 struct bfd_link_hash_table *
 567 _bfd_generic_link_hash_table_create (abfd)
 568      bfd *abfd;
 569 {
 570   struct generic_link_hash_table *ret;
 571
 572   ret = ((struct generic_link_hash_table *)
 573          bfd_xmalloc (sizeof (struct generic_link_hash_table)));
 574   if (! _bfd_link_hash_table_init (&ret->root, abfd,
 575                                    generic_link_hash_newfunc))
 576     {
 577       free (ret);
 578       return (struct bfd_link_hash_table *) NULL;
 579     }
 580   return &ret->root;
 581 }
 582 \f
 583 /* Generic function to add symbols from an object file to the global
 584    hash table.  */
 585
 586 boolean
 587 _bfd_generic_link_add_symbols (abfd, info)
 588      bfd *abfd;
 589      struct bfd_link_info *info;
 590 {
 591   boolean ret;
 592
 593   switch (bfd_get_format (abfd))
 594     {
 595     case bfd_object:
 596       ret = generic_link_add_object_symbols (abfd, info);
 597       break;
 598     case bfd_archive:
 599       ret = _bfd_generic_link_add_archive_symbols
 600         (abfd, info, generic_link_check_archive_element);
 601       break;
 602     default:
 603       bfd_error = wrong_format;
 604       ret = false;
 605     }
 606
 607   /* If we might be using the C based alloca function, make sure we
 608      have dumped the symbol tables we just allocated.  */
 609 #ifndef __GNUC__
 610 #ifndef alloca
 611   alloca (0);
 612 #endif
 613 #endif
 614
 615   return ret;
 616 }
 617
 618 /* Add symbols from an object file to the global hash table.  */
 619
 620 static boolean
 621 generic_link_add_object_symbols (abfd, info)
 622      bfd *abfd;
 623      struct bfd_link_info *info;
 624 {
 625   size_t symsize;
 626   asymbol **symbols;
 627   bfd_size_type symbol_count;
 628
 629   symsize = get_symtab_upper_bound (abfd);
 630   symbols = (asymbol **) alloca (symsize);
 631   symbol_count = bfd_canonicalize_symtab (abfd, symbols);
 632
 633   return generic_link_add_symbol_list (abfd, info, symbol_count, symbols);
 634 }
 635 \f
 636 /* We build a hash table of all symbols defined in an archive.  */
 637
 638 /* An archive symbol may be defined by multiple archive elements.
 639    This linked list is used to hold the elements.  */
 640
 641 struct archive_list
 642 {
 643   struct archive_list *next;
 644   int indx;
 645 };
 646
 647 /* An entry in an archive hash table.  */
 648
 649 struct archive_hash_entry
 650 {
 651   struct bfd_hash_entry root;
 652   /* Where the symbol is defined.  */
 653   struct archive_list *defs;
 654 };
 655
 656 /* An archive hash table itself.  */
 657
 658 struct archive_hash_table
 659 {
 660   struct bfd_hash_table table;
 661 };
 662
 663 static struct bfd_hash_entry *archive_hash_newfunc
 664   PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
 665 static boolean archive_hash_table_init
 666   PARAMS ((struct archive_hash_table *,
 667            struct bfd_hash_entry *(*) (struct bfd_hash_entry *,
 668                                        struct bfd_hash_table *,
 669                                        const char *)));
 670
 671 /* Create a new entry for an archive hash table.  */
 672
 673 static struct bfd_hash_entry *
 674 archive_hash_newfunc (entry, table, string)
 675      struct bfd_hash_entry *entry;
 676      struct bfd_hash_table *table;
 677      const char *string;
 678 {
 679   struct archive_hash_entry *ret = (struct archive_hash_entry *) entry;
 680
 681   /* Allocate the structure if it has not already been allocated by a
 682      subclass.  */
 683   if (ret == (struct archive_hash_entry *) NULL)
 684     ret = ((struct archive_hash_entry *)
 685            bfd_hash_allocate (table, sizeof (struct archive_hash_entry)));
 686
 687   /* Call the allocation method of the superclass.  */
 688   ret = ((struct archive_hash_entry *)
 689          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
 690
 691   /* Initialize the local fields.  */
 692   ret->defs = (struct archive_list *) NULL;
 693
 694   return (struct bfd_hash_entry *) ret;
 695 }
 696
 697 /* Initialize an archive hash table.  */
 698
 699 static boolean
 700 archive_hash_table_init (table, newfunc)
 701      struct archive_hash_table *table;
 702      struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *,
 703                                                 struct bfd_hash_table *,
 704                                                 const char *));
 705 {
 706   return bfd_hash_table_init (&table->table, newfunc);
 707 }
 708
 709 /* Look up an entry in an archive hash table.  */
 710
 711 #define archive_hash_lookup(t, string, create, copy) \
 712   ((struct archive_hash_entry *) \
 713    bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
 714
 715 /* Free an archive hash table.  */
 716
 717 #define archive_hash_table_free(t) bfd_hash_table_free (&(t)->table)
 718
 719 /* Generic function to add symbols from an archive file to the global
 720    hash file.  This function presumes that the archive symbol table
 721    has already been read in (this is normally done by the
 722    bfd_check_format entry point).  It looks through the undefined and
 723    common symbols and searches the archive symbol table for them.  If
 724    it finds an entry, it includes the associated object file in the
 725    link.
 726
 727    The old linker looked through the archive symbol table for
 728    undefined symbols.  We do it the other way around, looking through
 729    undefined symbols for symbols defined in the archive.  The
 730    advantage of the newer scheme is that we only have to look through
 731    the list of undefined symbols once, whereas the old method had to
 732    re-search the symbol table each time a new object file was added.
 733
 734    The CHECKFN argument is used to see if an object file should be
 735    included.  CHECKFN should set *PNEEDED to true if the object file
 736    should be included, and must also call the bfd_link_info
 737    add_archive_element callback function and handle adding the symbols
 738    to the global hash table.  CHECKFN should only return false if some
 739    sort of error occurs.
 740
 741    For some formats, such as a.out, it is possible to look through an
 742    object file but not actually include it in the link.  The
 743    archive_pass field in a BFD is used to avoid checking the symbols
 744    of an object files too many times.  When an object is included in
 745    the link, archive_pass is set to -1.  If an object is scanned but
 746    not included, archive_pass is set to the pass number.  The pass
 747    number is incremented each time a new object file is included.  The
 748    pass number is used because when a new object file is included it
 749    may create new undefined symbols which cause a previously examined
 750    object file to be included.  */
 751
 752 boolean
 753 _bfd_generic_link_add_archive_symbols (abfd, info, checkfn)
 754      bfd *abfd;
 755      struct bfd_link_info *info;
 756      boolean (*checkfn) PARAMS ((bfd *, struct bfd_link_info *,
 757                                  boolean *pneeded));
 758 {
 759   carsym *arsyms;
 760   carsym *arsym_end;
 761   register carsym *arsym;
 762   int pass;
 763   struct archive_hash_table arsym_hash;
 764   int indx;
 765   struct bfd_link_hash_entry **pundef;
 766
 767   if (! bfd_has_map (abfd))
 768     {
 769       bfd_error = no_symbols;
 770       return false;
 771     }
 772
 773   arsyms = bfd_ardata (abfd)->symdefs;
 774   arsym_end = arsyms + bfd_ardata (abfd)->symdef_count;
 775
 776   /* In order to quickly determine whether an symbol is defined in
 777      this archive, we build a hash table of the symbols.  */
 778   if (! archive_hash_table_init (&arsym_hash, archive_hash_newfunc))
 779     return false;
 780   for (arsym = arsyms, indx = 0; arsym < arsym_end; arsym++, indx++)
 781     {
 782       struct archive_hash_entry *arh;
 783       struct archive_list *l;
 784
 785       arh = archive_hash_lookup (&arsym_hash, arsym->name, true, false);
 786       if (arh == (struct archive_hash_entry *) NULL)
 787         return false;
 788       l = (struct archive_list *) alloca (sizeof (struct archive_list));
 789       l->next = arh->defs;
 790       arh->defs = l;
 791       l->indx = indx;
 792     }
 793
 794   pass = 1;
 795
 796   /* New undefined symbols are added to the end of the list, so we
 797      only need to look through it once.  */
 798   pundef = &info->hash->undefs;
 799   while (*pundef != (struct bfd_link_hash_entry *) NULL)
 800     {
 801       struct bfd_link_hash_entry *h;
 802       struct archive_hash_entry *arh;
 803       struct archive_list *l;
 804
 805       h = *pundef;
 806
 807       /* When a symbol is defined, it is not necessarily removed from
 808          the list.  */
 809       if (h->type != bfd_link_hash_undefined
 810           && h->type != bfd_link_hash_common)
 811         {
 812           /* Remove this entry from the list, for general cleanliness
 813              and because we are going to look through the list again
 814              if we search any more libraries.  We can't remove the
 815              entry if it is the tail, because that would lose any
 816              entries we add to the list later on.  */
 817           if (*pundef != info->hash->undefs_tail)
 818             *pundef = (*pundef)->next;
 819           else
 820             pundef = &(*pundef)->next;
 821           continue;
 822         }
 823
 824       /* Look for this symbol in the archive symbol map.  */
 825       arh = archive_hash_lookup (&arsym_hash, h->root.string, false, false);
 826       if (arh == (struct archive_hash_entry *) NULL)
 827         {
 828           pundef = &(*pundef)->next;
 829           continue;
 830         }
 831
 832       /* Look at all the objects which define this symbol.  */
 833       for (l = arh->defs; l != (struct archive_list *) NULL; l = l->next)
 834         {
 835           bfd *element;
 836           boolean needed;
 837
 838           /* If the symbol has gotten defined along the way, quit.  */
 839           if (h->type != bfd_link_hash_undefined
 840               && h->type != bfd_link_hash_common)
 841             break;
 842
 843           element = bfd_get_elt_at_index (abfd, l->indx);
 844           if (element == (bfd *) NULL)
 845             return false;
 846
 847           /* If we've already included this element, or if we've
 848              already checked it on this pass, continue.  */
 849           if (element->archive_pass == -1
 850               || element->archive_pass == pass)
 851             continue;
 852
 853           /* If we can't figure this element out, just ignore it.  */
 854           if (! bfd_check_format (element, bfd_object))
 855             {
 856               element->archive_pass = -1;
 857               continue;
 858             }
 859
 860           /* CHECKFN will see if this element should be included, and
 861              go ahead and include it if appropriate.  */
 862           if (! (*checkfn) (element, info, &needed))
 863             return false;
 864
 865           if (! needed)
 866             element->archive_pass = pass;
 867           else
 868             {
 869               element->archive_pass = -1;
 870
 871               /* Increment the pass count to show that we may need to
 872                  recheck object files which were already checked.  */
 873               ++pass;
 874             }
 875         }
 876
 877       pundef = &(*pundef)->next;
 878     }
 879
 880   archive_hash_table_free (&arsym_hash);
 881
 882   return true;
 883 }
 884 \f
 885 /* See if we should include an archive element.  */
 886
 887 static boolean
 888 generic_link_check_archive_element (abfd, info, pneeded)
 889      bfd *abfd;
 890      struct bfd_link_info *info;
 891      boolean *pneeded;
 892 {
 893   size_t symsize;
 894   asymbol **symbols;
 895   bfd_size_type symbol_count;
 896   asymbol **pp, **ppend;
 897
 898   *pneeded = false;
 899
 900   symsize = get_symtab_upper_bound (abfd);
 901   symbols = (asymbol **) alloca (symsize);
 902   symbol_count = bfd_canonicalize_symtab (abfd, symbols);
 903
 904   pp = symbols;
 905   ppend = symbols + symbol_count;
 906   for (; pp < ppend; pp++)
 907     {
 908       asymbol *p;
 909       struct bfd_link_hash_entry *h;
 910
 911       p = *pp;
 912
 913       /* We are only interested in globally visible symbols.  */
 914       if (! bfd_is_com_section (p->section)
 915           && (p->flags & (BSF_GLOBAL | BSF_INDIRECT | BSF_WEAK)) == 0)
 916         continue;
 917
 918       /* We are only interested if we know something about this
 919          symbol, and it is undefined or common.  An undefined weak
 920          symbol (type bfd_link_hash_weak) is not considered to be a
 921          reference when pulling files out of an archive.  See the SVR4
 922          ABI, p. 4-27.  */
 923       h = bfd_link_hash_lookup (info->hash, bfd_asymbol_name (p), false,
 924                                 false, true);
 925       if (h == (struct bfd_link_hash_entry *) NULL
 926           || (h->type != bfd_link_hash_undefined
 927               && h->type != bfd_link_hash_common))
 928         continue;
 929
 930       /* P is a symbol we are looking for.  */
 931
 932       if (! bfd_is_com_section (p->section))
 933         {
 934           /* This object file defines this symbol, so pull it in.  */
 935           if (! (*info->callbacks->add_archive_element) (info, abfd,
 936                                                          bfd_asymbol_name (p)))
 937             return false;
 938           if (! generic_link_add_symbol_list (abfd, info, symbol_count,
 939                                               symbols))
 940             return false;
 941           *pneeded = true;
 942           return true;
 943         }
 944
 945       /* P is a common symbol.  */
 946
 947       if (h->type == bfd_link_hash_undefined)
 948         {
 949           bfd *symbfd;
 950
 951           symbfd = h->u.undef.abfd;
 952           if (symbfd == (bfd *) NULL)
 953             {
 954               /* This symbol was created as undefined from outside
 955                  BFD.  We assume that we should link in the object
 956                  file.  This is for the -u option in the linker.  */
 957               if (! (*info->callbacks->add_archive_element)
 958                   (info, abfd, bfd_asymbol_name (p)))
 959                 return false;
 960               *pneeded = true;
 961               return true;
 962             }
 963
 964           /* Turn the symbol into a common symbol but do not link in
 965              the object file.  This is how a.out works.  Object
 966              formats that require different semantics must implement
 967              this function differently.  This symbol is already on the
 968              undefs list.  We add the section to a common section
 969              attached to symbfd to ensure that it is in a BFD which
 970              will be linked in.  */
 971           h->type = bfd_link_hash_common;
 972           h->u.c.size = bfd_asymbol_value (p);
 973           if (p->section == &bfd_com_section)
 974             h->u.c.section = bfd_make_section_old_way (symbfd, "COMMON");
 975           else
 976             h->u.c.section = bfd_make_section_old_way (symbfd,
 977                                                        p->section->name);
 978           h->u.c.section->flags = SEC_ALLOC;
 979         }
 980       else
 981         {
 982           /* Adjust the size of the common symbol if necessary.  This
 983              is how a.out works.  Object formats that require
 984              different semantics must implement this function
 985              differently.  */
 986           if (bfd_asymbol_value (p) > h->u.c.size)
 987             h->u.c.size = bfd_asymbol_value (p);
 988         }
 989     }
 990
 991   /* This archive element is not needed.  */
 992   return true;
 993 }
 994
 995 /* Add the symbol from an object file to the global hash table.  */
 996
 997 static boolean
 998 generic_link_add_symbol_list (abfd, info, symbol_count, symbols)
 999      bfd *abfd;
1000      struct bfd_link_info *info;
1001      bfd_size_type symbol_count;
1002      asymbol **symbols;
1003 {
1004   asymbol **pp, **ppend;
1005
1006   pp = symbols;
1007   ppend = symbols + symbol_count;
1008   for (; pp < ppend; pp++)
1009     {
1010       asymbol *p;
1011
1012       p = *pp;
1013
1014       if ((p->flags & (BSF_INDIRECT
1015                        | BSF_WARNING
1016                        | BSF_GLOBAL
1017                        | BSF_CONSTRUCTOR
1018                        | BSF_WEAK)) != 0
1019           || bfd_get_section (p) == &bfd_und_section
1020           || bfd_is_com_section (bfd_get_section (p))
1021           || bfd_get_section (p) == &bfd_ind_section)
1022         {
1023           const char *name;
1024           const char *string;
1025           struct generic_link_hash_entry *h;
1026
1027           name = bfd_asymbol_name (p);
1028           if ((p->flags & BSF_INDIRECT) != 0
1029               || p->section == &bfd_ind_section)
1030             string = bfd_asymbol_name ((asymbol *) p->value);
1031           else if ((p->flags & BSF_WARNING) != 0)
1032             {
1033               /* The name of P is actually the warning string, and the
1034                  value is actually a pointer to the symbol to warn
1035                  about.  */
1036               string = name;
1037               name = bfd_asymbol_name ((asymbol *) p->value);
1038             }
1039           else
1040             string = NULL;
1041
1042           /* We pass the constructor argument as false, for
1043              compatibility.  As backends are converted they can
1044              arrange to pass the right value (the right value is the
1045              size of a function pointer if gcc uses collect2 for the
1046              object file format, zero if it does not).
1047              FIXME: We pass the bitsize as 32, which is just plain
1048              wrong, but actually doesn't matter very much.  */
1049           if (! (_bfd_generic_link_add_one_symbol
1050                  (info, abfd, name, p->flags, bfd_get_section (p),
1051                   p->value, string, false, 0, 32,
1052                   (struct bfd_link_hash_entry **) &h)))
1053             return false;
1054
1055           /* Save the BFD symbol so that we don't lose any backend
1056              specific information that may be attached to it.  We only
1057              want this one if it gives more information than the
1058              existing one; we don't want to replace a defined symbol
1059              with an undefined one.  This routine may be called with a
1060              hash table other than the generic hash table, so we only
1061              do this if we are certain that the hash table is a
1062              generic one.  */
1063           if (info->hash->creator == abfd->xvec)
1064             {
1065               if (h->sym == (asymbol *) NULL
1066                   || (bfd_get_section (p) != &bfd_und_section
1067                       && (! bfd_is_com_section (bfd_get_section (p))
1068                           || (bfd_get_section (h->sym) == &bfd_und_section))))
1069                 {
1070                   h->sym = p;
1071                   /* BSF_OLD_COMMON is a hack to support COFF reloc
1072                      reading, and it should go away when the COFF
1073                      linker is switched to the new version.  */
1074                   if (bfd_is_com_section (bfd_get_section (p)))
1075                     p->flags |= BSF_OLD_COMMON;
1076                 }
1077             }
1078         }
1079     }
1080
1081   return true;
1082 }
1083 \f
1084 /* We use a state table to deal with adding symbols from an object
1085    file.  The first index into the state table describes the symbol
1086    from the object file.  The second index into the state table is the
1087    type of the symbol in the hash table.  */
1088
1089 /* The symbol from the object file is turned into one of these row
1090    values.  */
1091
1092 enum link_row
1093 {
1094   UNDEF_ROW,            /* Undefined.  */
1095   UNDEFW_ROW,           /* Weak undefined.  */
1096   DEF_ROW,              /* Defined.  */
1097   DEFW_ROW,             /* Weak defined.  */
1098   COMMON_ROW,           /* Common.  */
1099   INDR_ROW,             /* Indirect.  */
1100   WARN_ROW,             /* Warning.  */
1101   SET_ROW               /* Member of set.  */
1102 };
1103
1104 /* The actions to take in the state table.  */
1105
1106 enum link_action
1107 {
1108   FAIL,         /* Abort. */
1109   UND,          /* Mark symbol undefined.  */
1110   WEAK,         /* Mark symbol weak undefined.  */
1111   DEF,          /* Mark symbol defined.  */
1112   COM,          /* Mark symbol common.  */
1113   CREF,         /* Possibly warn about common reference to defined symbol.  */
1114   CDEF,         /* Define existing common symbol.  */
1115   NOACT,        /* No action.  */
1116   BIG,          /* Mark symbol common using largest size.  */
1117   MDEF,         /* Multiple definition error.  */
1118   IND,          /* Make indirect symbol.  */
1119   SET,          /* Add value to set.  */
1120   MWARN,        /* Make warning symbol.  */
1121   WARN,         /* Issue warning.  */
1122   CYCLE,        /* Repeat with symbol pointed to.  */
1123   WARNC         /* Issue warning and then CYCLE.  */
1124 };
1125
1126 /* The state table itself.  The first index is a link_row and the
1127    second index is a bfd_link_hash_type.  */
1128
1129 static const enum link_action link_action[8][7] =
1130 {
1131   /* current\prev    new    undef  weak   def    com    indr   warn  */
1132   /* UNDEF_ROW  */  {UND,   NOACT, NOACT, NOACT, NOACT, CYCLE, WARNC },
1133   /* UNDEFW_ROW */  {WEAK,  WEAK,  NOACT, NOACT, NOACT, CYCLE, WARNC },
1134   /* DEF_ROW    */  {DEF,   DEF,   DEF,   MDEF,  CDEF,  CYCLE, CYCLE },
1135   /* DEFW_ROW   */  {DEF,   DEF,   DEF,   NOACT, NOACT, CYCLE, CYCLE },
1136   /* COMMON_ROW */  {COM,   COM,   COM,   CREF,  BIG,   CYCLE, WARNC },
1137   /* INDR_ROW   */  {IND,   IND,   IND,   MDEF,  MDEF,  MDEF,  WARNC },
1138   /* WARN_ROW   */  {MWARN, WARN,  WARN,  MWARN, MWARN, MWARN, NOACT },
1139   /* SET_ROW    */  {SET,   SET,   SET,   SET,   SET,   CYCLE, WARNC }
1140 };
1141
1142 /* Add a symbol to the global hash table.
1143    ABFD is the BFD the symbol comes from.
1144    NAME is the name of the symbol.
1145    FLAGS is the BSF_* bits associated with the symbol.
1146    SECTION is the section in which the symbol is defined; this may be
1147      bfd_und_section or bfd_com_section.
1148    VALUE is the value of the symbol, relative to the section.
1149    STRING is used for either an indirect symbol, in which case it is
1150      the name of the symbol to indirect to, or a warning symbol, in
1151      which case it is the warning string.
1152    COPY is true if NAME or STRING must be copied into locally
1153      allocated memory if they need to be saved.
1154    CONSTRUCTOR is true if we should automatically collect gcc
1155      constructor or destructor names.
1156    BITSIZE is the number of bits in constructor or set entries.
1157    HASHP, if not NULL, is a place to store the created hash table
1158      entry.  */
1159
1160 boolean
1161 _bfd_generic_link_add_one_symbol (info, abfd, name, flags, section, value,
1162                                   string, copy, constructor, bitsize, hashp)
1163      struct bfd_link_info *info;
1164      bfd *abfd;
1165      const char *name;
1166      flagword flags;
1167      asection *section;
1168      bfd_vma value;
1169      const char *string;
1170      boolean copy;
1171      boolean constructor;
1172      unsigned int bitsize;
1173      struct bfd_link_hash_entry **hashp;
1174 {
1175   enum link_row row;
1176   struct bfd_link_hash_entry *h;
1177   boolean cycle;
1178
1179   if (section == &bfd_ind_section
1180       || (flags & BSF_INDIRECT) != 0)
1181     row = INDR_ROW;
1182   else if ((flags & BSF_WARNING) != 0)
1183     row = WARN_ROW;
1184   else if ((flags & BSF_CONSTRUCTOR) != 0)
1185     row = SET_ROW;
1186   else if (section == &bfd_und_section)
1187     {
1188       if ((flags & BSF_WEAK) != 0)
1189         row = UNDEFW_ROW;
1190       else
1191         row = UNDEF_ROW;
1192     }
1193   else if ((flags & BSF_WEAK) != 0)
1194     row = DEFW_ROW;
1195   else if (bfd_is_com_section (section))
1196     row = COMMON_ROW;
1197   else
1198     row = DEF_ROW;
1199
1200   h = bfd_link_hash_lookup (info->hash, name, true, copy, false);
1201   if (h == (struct bfd_link_hash_entry *) NULL)
1202     {
1203       if (hashp != (struct bfd_link_hash_entry **) NULL)
1204         *hashp = NULL;
1205       return false;
1206     }
1207
1208   if (info->notice_hash != (struct bfd_hash_table *) NULL
1209       && (bfd_hash_lookup (info->notice_hash, name, false, false)
1210           != (struct bfd_hash_entry *) NULL))
1211     {
1212       if (! (*info->callbacks->notice) (info, name, abfd, section, value))
1213         return false;
1214     }
1215
1216   if (hashp != (struct bfd_link_hash_entry **) NULL)
1217     *hashp = h;
1218
1219   do
1220     {
1221       enum link_action action;
1222
1223       cycle = false;
1224       action = link_action[(int) row][(int) h->type];
1225       switch (action)
1226         {
1227         case FAIL:
1228           abort ();
1229         case UND:
1230           h->type = bfd_link_hash_undefined;
1231           h->u.undef.abfd = abfd;
1232           bfd_link_add_undef (info->hash, h);
1233           break;
1234         case WEAK:
1235           h->type = bfd_link_hash_weak;
1236           h->u.undef.abfd = abfd;
1237           break;
1238         case CDEF:
1239           BFD_ASSERT (h->type == bfd_link_hash_common);
1240           if (! ((*info->callbacks->multiple_common)
1241                  (info, name,
1242                   h->u.c.section->owner, bfd_link_hash_common, h->u.c.size,
1243                   abfd, bfd_link_hash_defined, (bfd_vma) 0)))
1244             return false;
1245           /* Fall through.  */
1246         case DEF:
1247           h->type = bfd_link_hash_defined;
1248           h->u.def.section = section;
1249           h->u.def.value = value;
1250
1251           /* If we have been asked to, we act like collect2 and
1252              identify all functions that might be global constructors
1253              and destructors and pass them up in a callback.  We only
1254              do this for certain object file types, since many object
1255              file types can handle this automatically.  */
1256           if (constructor && name[0] == '_')
1257             {
1258               const char *s;
1259
1260               /* A constructor or destructor name starts like this:
1261                    _+GLOBAL_[_.$][ID][_.$]
1262                  where the first [_.$] and the second are the same
1263                  character (we accept any character there, in case a
1264                  new object file format comes along with even worse
1265                  naming restrictions).  */
1266
1267 #define CONS_PREFIX "GLOBAL_"
1268 #define CONS_PREFIX_LEN (sizeof CONS_PREFIX - 1)
1269
1270               s = name + 1;
1271               while (*s == '_')
1272                 ++s;
1273               if (s[0] == 'G'
1274                   && strncmp (s, CONS_PREFIX, CONS_PREFIX_LEN - 1) == 0)
1275                 {
1276                   char c;
1277
1278                   c = s[CONS_PREFIX_LEN + 1];
1279                   if ((c == 'I' || c == 'D')
1280                       && s[CONS_PREFIX_LEN] == s[CONS_PREFIX_LEN + 2])
1281                     {
1282                       if (! ((*info->callbacks->constructor)
1283                              (info,
1284                               c == 'I' ? true : false, bitsize,
1285                               name, abfd, section, value)))
1286                         return false;
1287                     }
1288                 }
1289             }
1290
1291           break;
1292         case COM:
1293           if (h->type == bfd_link_hash_new)
1294             bfd_link_add_undef (info->hash, h);
1295           h->type = bfd_link_hash_common;
1296           h->u.c.size = value;
1297           if (section == &bfd_com_section)
1298             {
1299               h->u.c.section = bfd_make_section_old_way (abfd, "COMMON");
1300               h->u.c.section->flags = SEC_ALLOC;
1301             }
1302           else if (section->owner != abfd)
1303             {
1304               h->u.c.section = bfd_make_section_old_way (abfd, section->name);
1305               h->u.c.section->flags = SEC_ALLOC;
1306             }
1307           else
1308             h->u.c.section = section;
1309           break;
1310         case NOACT:
1311           break;
1312         case BIG:
1313           BFD_ASSERT (h->type == bfd_link_hash_common);
1314           if (! ((*info->callbacks->multiple_common)
1315                  (info, name,
1316                   h->u.c.section->owner, bfd_link_hash_common, h->u.c.size,
1317                   abfd, bfd_link_hash_common, value)))
1318             return false;
1319           if (value > h->u.c.size)
1320             h->u.c.size = value;
1321           break;
1322         case CREF:
1323           BFD_ASSERT (h->type == bfd_link_hash_defined);
1324           if (! ((*info->callbacks->multiple_common)
1325                  (info, name,
1326                   h->u.def.section->owner, bfd_link_hash_defined, (bfd_vma) 0,
1327                   abfd, bfd_link_hash_common, value)))
1328             return false;
1329           break;
1330         case MDEF:
1331           {
1332             asection *msec;
1333             bfd_vma mval;
1334
1335             switch (h->type)
1336               {
1337               case bfd_link_hash_defined:
1338                 msec = h->u.def.section;
1339                 mval = h->u.def.value;
1340                 break;
1341               case bfd_link_hash_common:
1342                 msec = &bfd_com_section;
1343                 mval = h->u.c.size;
1344                 break;
1345               case bfd_link_hash_indirect:
1346                 msec = &bfd_ind_section;
1347                 mval = 0;
1348                 break;
1349               default:
1350                 abort ();
1351               }
1352
1353             if (! ((*info->callbacks->multiple_definition)
1354                    (info, name, msec->owner, msec, mval, abfd, section,
1355                     value)))
1356               return false;
1357           }
1358           break;
1359         case IND:
1360           {
1361             struct bfd_link_hash_entry *inh;
1362
1363             /* STRING is the name of the symbol we want to indirect
1364                to.  */
1365             inh = bfd_link_hash_lookup (info->hash, string, true, copy,
1366                                         false);
1367             if (inh == (struct bfd_link_hash_entry *) NULL)
1368               return false;
1369             if (inh->type == bfd_link_hash_new)
1370               {
1371                 inh->type = bfd_link_hash_undefined;
1372                 inh->u.undef.abfd = abfd;
1373                 bfd_link_add_undef (info->hash, inh);
1374               }
1375             h->type = bfd_link_hash_indirect;
1376             h->u.i.link = inh;
1377           }
1378           break;
1379         case SET:
1380           if (! (*info->callbacks->add_to_set) (info, h, bitsize, abfd,
1381                                                 section, value))
1382             return false;
1383           break;
1384         case WARN:
1385         case WARNC:
1386           if (h->u.i.warning != NULL)
1387             {
1388               if (! (*info->callbacks->warning) (info, h->u.i.warning))
1389                 return false;
1390               /* Only issue a warning once.  */
1391               h->u.i.warning = NULL;
1392             }
1393           if (action == WARN)
1394             break;
1395           /* Fall through.  */
1396         case CYCLE:
1397           h = h->u.i.link;
1398           cycle = true;
1399           break;
1400         case MWARN:
1401           {
1402             struct bfd_link_hash_entry *sub;
1403
1404             /* STRING is the warning to give.  */
1405             sub = ((struct bfd_link_hash_entry *)
1406                    bfd_hash_allocate (&info->hash->table,
1407                                       sizeof (struct bfd_link_hash_entry)));
1408             *sub = *h;
1409             h->type = bfd_link_hash_warning;
1410             h->u.i.link = sub;
1411             if (! copy)
1412               h->u.i.warning = string;
1413             else
1414               {
1415                 char *w;
1416
1417                 w = bfd_hash_allocate (&info->hash->table,
1418                                        strlen (string) + 1);
1419                 strcpy (w, string);
1420                 h->u.i.warning = w;
1421               }
1422           }
1423           break;
1424         }
1425     }
1426   while (cycle);
1427
1428   return true;
1429 }
1430 \f
1431 /* Generic final link routine.  */
1432
1433 boolean
1434 _bfd_generic_final_link (abfd, info)
1435      bfd *abfd;
1436      struct bfd_link_info *info;
1437 {
1438   bfd *sub;
1439   asection *o;
1440   struct bfd_link_order *p;
1441   size_t outsymalloc;
1442   struct generic_write_global_symbol_info wginfo;
1443
1444   abfd->outsymbols = (asymbol **) NULL;
1445   abfd->symcount = 0;
1446   outsymalloc = 0;
1447
1448   /* Build the output symbol table.  This also reads in the symbols
1449      for all the input BFDs, keeping them in the outsymbols field.  */
1450   for (sub = info->input_bfds; sub != (bfd *) NULL; sub = sub->link_next)
1451     if (! _bfd_generic_link_output_symbols (abfd, sub, info, &outsymalloc))
1452       return false;
1453
1454   /* Accumulate the global symbols.  */
1455   wginfo.output_bfd = abfd;
1456   wginfo.psymalloc = &outsymalloc;
1457   _bfd_generic_link_hash_traverse (_bfd_generic_hash_table (info),
1458                                    _bfd_generic_link_write_global_symbol,
1459                                    (PTR) &wginfo);
1460
1461   if (info->relocateable)
1462     {
1463       /* Allocate space for the output relocs for each section.  */
1464       for (o = abfd->sections;
1465            o != (asection *) NULL;
1466            o = o->next)
1467         {
1468           o->reloc_count = 0;
1469           for (p = o->link_order_head;
1470                p != (struct bfd_link_order *) NULL;
1471                p = p->next)
1472             {
1473               if (p->type == bfd_indirect_link_order)
1474                 {
1475                   asection *input_section;
1476                   bfd *input_bfd;
1477                   bfd_size_type relsize;
1478                   arelent **relocs;
1479                   bfd_size_type reloc_count;
1480
1481                   input_section = p->u.indirect.section;
1482                   input_bfd = input_section->owner;
1483                   relsize = bfd_get_reloc_upper_bound (input_bfd,
1484                                                        input_section);
1485                   relocs = (arelent **) bfd_xmalloc (relsize);
1486                   reloc_count =
1487                     bfd_canonicalize_reloc (input_bfd, input_section,
1488                                             relocs,
1489                                             bfd_get_outsymbols (input_bfd));
1490                   BFD_ASSERT (reloc_count == input_section->reloc_count);
1491                   o->reloc_count += reloc_count;
1492                   free (relocs);
1493                 }
1494             }
1495           if (o->reloc_count > 0)
1496             {
1497               o->orelocation = ((arelent **)
1498                                 bfd_alloc (abfd,
1499                                            (o->reloc_count
1500                                             * sizeof (arelent *))));
1501               /* Reset the count so that it can be used as an index
1502                  when putting in the output relocs.  */
1503               o->reloc_count = 0;
1504             }
1505         }
1506     }
1507
1508   /* Handle all the link order information for the sections.  */
1509   for (o = abfd->sections;
1510        o != (asection *) NULL;
1511        o = o->next)
1512     {
1513       for (p = o->link_order_head;
1514            p != (struct bfd_link_order *) NULL;
1515            p = p->next)
1516         {
1517           if (! _bfd_default_link_order (abfd, info, o, p))
1518             return false;
1519         }
1520     }
1521
1522   return true;
1523 }
1524
1525 /* Add an output symbol to the output BFD.  */
1526
1527 static boolean
1528 generic_add_output_symbol (output_bfd, psymalloc, sym)
1529      bfd *output_bfd;
1530      size_t *psymalloc;
1531      asymbol *sym;
1532 {
1533   if (output_bfd->symcount >= *psymalloc)
1534     {
1535       asymbol **newsyms;
1536
1537       if (*psymalloc == 0)
1538         *psymalloc = 124;
1539       else
1540         *psymalloc *= 2;
1541       if (output_bfd->outsymbols == (asymbol **) NULL)
1542         newsyms = (asymbol **) malloc (*psymalloc * sizeof (asymbol *));
1543       else
1544         newsyms = (asymbol **) realloc (output_bfd->outsymbols,
1545                                         *psymalloc * sizeof (asymbol *));
1546       if (newsyms == (asymbol **) NULL)
1547         {
1548           bfd_error = no_memory;
1549           return false;
1550         }
1551       output_bfd->outsymbols = newsyms;
1552     }
1553
1554   output_bfd->outsymbols[output_bfd->symcount] = sym;
1555   ++output_bfd->symcount;
1556
1557   return true;
1558 }
1559
1560 /* Handle the symbols for an input BFD.  */
1561
1562 boolean
1563 _bfd_generic_link_output_symbols (output_bfd, input_bfd, info, psymalloc)
1564      bfd *output_bfd;
1565      bfd *input_bfd;
1566      struct bfd_link_info *info;
1567      size_t *psymalloc;
1568 {
1569   size_t symsize;
1570   asymbol **sym_ptr;
1571   asymbol **sym_end;
1572
1573   symsize = get_symtab_upper_bound (input_bfd);
1574   input_bfd->outsymbols = (asymbol **) bfd_alloc (input_bfd, symsize);
1575   input_bfd->symcount = bfd_canonicalize_symtab (input_bfd,
1576                                                  input_bfd->outsymbols);
1577
1578   /* Create a filename symbol if we are supposed to.  */
1579   if (info->create_object_symbols_section != (asection *) NULL)
1580     {
1581       asection *sec;
1582
1583       for (sec = input_bfd->sections;
1584            sec != (asection *) NULL;
1585            sec = sec->next)
1586         {
1587           if (sec->output_section == info->create_object_symbols_section)
1588             {
1589               asymbol *newsym;
1590
1591               newsym = bfd_make_empty_symbol (input_bfd);
1592               newsym->name = input_bfd->filename;
1593               newsym->value = 0;
1594               newsym->flags = BSF_LOCAL | BSF_FILE;
1595               newsym->section = sec;
1596
1597               if (! generic_add_output_symbol (output_bfd, psymalloc,
1598                                                newsym))
1599                 return false;
1600
1601               break;
1602             }
1603         }
1604     }
1605
1606   /* Adjust the values of the globally visible symbols, and write out
1607      local symbols.  */
1608   sym_ptr = bfd_get_outsymbols (input_bfd);
1609   sym_end = sym_ptr + bfd_get_symcount (input_bfd);
1610   for (; sym_ptr < sym_end; sym_ptr++)
1611     {
1612       asymbol *sym;
1613       struct generic_link_hash_entry *h;
1614       boolean output;
1615
1616       h = (struct generic_link_hash_entry *) NULL;
1617       sym = *sym_ptr;
1618       if ((sym->flags & (BSF_INDIRECT
1619                          | BSF_WARNING
1620                          | BSF_GLOBAL
1621                          | BSF_CONSTRUCTOR
1622                          | BSF_WEAK)) != 0
1623           || bfd_get_section (sym) == &bfd_und_section
1624           || bfd_is_com_section (bfd_get_section (sym))
1625           || bfd_get_section (sym) == &bfd_ind_section)
1626         {
1627           h = _bfd_generic_link_hash_lookup (_bfd_generic_hash_table (info),
1628                                              bfd_asymbol_name (sym),
1629                                              false, false, true);
1630           if (h != (struct generic_link_hash_entry *) NULL)
1631             {
1632               /* Force all references to this symbol to point to
1633                  the same area in memory.  It is possible that
1634                  this routine will be called with a hash table
1635                  other than a generic hash table, so we double
1636                  check that.  */
1637               if (info->hash->creator == input_bfd->xvec)
1638                 {
1639                   if (h->sym != (asymbol *) NULL)
1640                     *sym_ptr = sym = h->sym;
1641                 }
1642
1643               switch (h->root.type)
1644                 {
1645                 default:
1646                 case bfd_link_hash_new:
1647                   abort ();
1648                 case bfd_link_hash_undefined:
1649                 case bfd_link_hash_weak:
1650                   break;
1651                 case bfd_link_hash_defined:
1652                   sym->value = h->root.u.def.value;
1653                   sym->section = h->root.u.def.section;
1654                   sym->flags |= BSF_GLOBAL;
1655                   break;
1656                 case bfd_link_hash_common:
1657                   sym->value = h->root.u.c.size;
1658                   sym->flags |= BSF_GLOBAL;
1659                   /* We do not set the section of the symbol to
1660                      c.section.  c.section is saved so that we know
1661                      where to allocate the symbol if we define it.  In
1662                      this case the type is still bfd_link_hash_common,
1663                      so we did not define it, so we do not want to use
1664                      that section.  */
1665                   BFD_ASSERT (bfd_is_com_section (sym->section));
1666                   break;
1667                 }
1668             }
1669         }
1670
1671       /* This switch is straight from the old code in
1672          write_file_locals in ldsym.c.  */
1673       if (info->strip == strip_some
1674           && (bfd_hash_lookup (info->keep_hash, bfd_asymbol_name (sym),
1675                                false, false)
1676               == (struct bfd_hash_entry *) NULL))
1677         output = false;
1678       else if ((sym->flags & (BSF_GLOBAL | BSF_WEAK)) != 0)
1679         {
1680           /* If this symbol is marked as occurring now, rather
1681              than at the end, output it now.  This is used for
1682              COFF C_EXT FCN symbols.  FIXME: There must be a
1683              better way.  */
1684           if (bfd_asymbol_bfd (sym) == input_bfd
1685               && (sym->flags & BSF_NOT_AT_END) != 0)
1686             output = true;
1687           else
1688             output = false;
1689         }
1690       else if (sym->section == &bfd_ind_section)
1691         output = false;
1692       else if ((sym->flags & BSF_DEBUGGING) != 0)
1693         {
1694           if (info->strip == strip_none)
1695             output = true;
1696           else
1697             output = false;
1698         }
1699       else if (sym->section == &bfd_und_section
1700                || bfd_is_com_section (sym->section))
1701         output = false;
1702       else if ((sym->flags & BSF_LOCAL) != 0)
1703         {
1704           if ((sym->flags & BSF_WARNING) != 0)
1705             output = false;
1706           else
1707             {
1708               switch (info->discard)
1709                 {
1710                 default:
1711                 case discard_all:
1712                   output = false;
1713                   break;
1714                 case discard_l:
1715                   if (bfd_asymbol_name (sym)[0] == info->lprefix[0]
1716                       && (info->lprefix_len == 1
1717                           || strncmp (bfd_asymbol_name (sym), info->lprefix,
1718                                       info->lprefix_len) == 0))
1719                     output = false;
1720                   else
1721                     output = true;
1722                   break;
1723                 case discard_none:
1724                   output = true;
1725                   break;
1726                 }
1727             }
1728         }
1729       else if ((sym->flags & BSF_CONSTRUCTOR))
1730         {
1731           if (info->strip != strip_all)
1732             output = true;
1733           else
1734             output = false;
1735         }
1736       else
1737         abort ();
1738
1739       if (output)
1740         {
1741           if (! generic_add_output_symbol (output_bfd, psymalloc, sym))
1742             return false;
1743           if (h != (struct generic_link_hash_entry *) NULL)
1744             h->root.written = true;
1745         }
1746     }
1747
1748   return true;
1749 }
1750
1751 /* Write out a global symbol, if it hasn't already been written out.
1752    This is called for each symbol in the hash table.  */
1753
1754 boolean
1755 _bfd_generic_link_write_global_symbol (h, data)
1756      struct generic_link_hash_entry *h;
1757      PTR data;
1758 {
1759   struct generic_write_global_symbol_info *wginfo =
1760     (struct generic_write_global_symbol_info *) data;
1761   asymbol *sym;
1762
1763   if (h->root.written)
1764     return true;
1765
1766   if (h->sym != (asymbol *) NULL)
1767     {
1768       sym = h->sym;
1769       BFD_ASSERT (strcmp (bfd_asymbol_name (sym), h->root.root.string) == 0);
1770     }
1771   else
1772     {
1773       sym = bfd_make_empty_symbol (wginfo->output_bfd);
1774       sym->name = h->root.root.string;
1775       sym->flags = 0;
1776     }
1777
1778   switch (h->root.type)
1779     {
1780     default:
1781     case bfd_link_hash_new:
1782       abort ();
1783     case bfd_link_hash_undefined:
1784       sym->section = &bfd_und_section;
1785       sym->value = 0;
1786       break;
1787     case bfd_link_hash_weak:
1788       sym->section = &bfd_und_section;
1789       sym->value = 0;
1790       sym->flags |= BSF_WEAK;
1791     case bfd_link_hash_defined:
1792       sym->section = h->root.u.def.section;
1793       sym->value = h->root.u.def.value;
1794       break;
1795     case bfd_link_hash_common:
1796       sym->value = h->root.u.c.size;
1797       /* Do not set the section; see _bfd_generic_link_output_symbols.  */
1798       BFD_ASSERT (bfd_is_com_section (sym->section));
1799       break;
1800     case bfd_link_hash_indirect:
1801     case bfd_link_hash_warning:
1802       /* FIXME: What should we do here?  */
1803       break;
1804     }
1805
1806   sym->flags |= BSF_GLOBAL;
1807
1808   if (! generic_add_output_symbol (wginfo->output_bfd, wginfo->psymalloc,
1809                                    sym))
1810     {
1811       /* FIXME: No way to return failure.  */
1812       abort ();
1813     }
1814
1815   h->root.written = true;
1816
1817   return true;
1818 }
1819 \f
1820 /* Allocate a new link_order for a section.  */
1821
1822 struct bfd_link_order *
1823 bfd_new_link_order (abfd, section)
1824      bfd *abfd;
1825      asection *section;
1826 {
1827   struct bfd_link_order *new;
1828
1829   new = ((struct bfd_link_order *)
1830          bfd_alloc_by_size_t (abfd, sizeof (struct bfd_link_order)));
1831
1832   new->type = bfd_undefined_link_order;
1833   new->offset = 0;
1834   new->size = 0;
1835   new->next = (struct bfd_link_order *) NULL;
1836
1837   if (section->link_order_tail != (struct bfd_link_order *) NULL)
1838     section->link_order_tail->next = new;
1839   else
1840     section->link_order_head = new;
1841   section->link_order_tail = new;
1842
1843   return new;
1844 }
1845
1846 /* Default link order processing routine.  */
1847
1848 boolean
1849 _bfd_default_link_order (abfd, info, sec, link_order)
1850      bfd *abfd;
1851      struct bfd_link_info *info;
1852      asection *sec;
1853      struct bfd_link_order *link_order;
1854 {
1855   switch (link_order->type)
1856     {
1857     case bfd_undefined_link_order:
1858     default:
1859       abort ();
1860     case bfd_indirect_link_order:
1861       return default_indirect_link_order (abfd, info, sec, link_order);
1862     case bfd_fill_link_order:
1863       return default_fill_link_order (abfd, info, sec, link_order);
1864     }
1865 }
1866
1867 /* Default routine to handle a bfd_fill_link_order.  */
1868
1869 /*ARGSUSED*/
1870 static boolean
1871 default_fill_link_order (abfd, info, sec, link_order)
1872      bfd *abfd;
1873      struct bfd_link_info *info;
1874      asection *sec;
1875      struct bfd_link_order *link_order;
1876 {
1877   size_t size;
1878   char *space;
1879   size_t i;
1880   int fill;
1881
1882   BFD_ASSERT ((sec->flags & SEC_HAS_CONTENTS) != 0);
1883
1884   size = (size_t) link_order->size;
1885   space = (char *) alloca (size);
1886   fill = link_order->u.fill.value;
1887   for (i = 0; i < size; i += 2)
1888     space[i] = fill >> 8;
1889   for (i = 1; i < size; i += 2)
1890     space[i] = fill;
1891   return bfd_set_section_contents (abfd, sec, space,
1892                                    (file_ptr) link_order->offset,
1893                                    link_order->size);
1894 }
1895
1896 /* Default routine to handle a bfd_indirect_link_order.  */
1897
1898 static boolean
1899 default_indirect_link_order (output_bfd, info, output_section, link_order)
1900      bfd *output_bfd;
1901      struct bfd_link_info *info;
1902      asection *output_section;
1903      struct bfd_link_order *link_order;
1904 {
1905   asection *input_section;
1906   bfd *input_bfd;
1907   bfd_byte *contents;
1908
1909   BFD_ASSERT ((output_section->flags & SEC_HAS_CONTENTS) != 0);
1910
1911   if (link_order->size == 0)
1912     return true;
1913
1914   input_section = link_order->u.indirect.section;
1915   input_bfd = input_section->owner;
1916
1917   BFD_ASSERT (input_section->output_section == output_section);
1918   BFD_ASSERT (input_section->output_offset == link_order->offset);
1919   BFD_ASSERT (bfd_section_size (input_bfd, input_section) == link_order->size);
1920
1921   if (info->relocateable
1922       && input_section->reloc_count > 0
1923       && output_section->orelocation == (arelent **) NULL)
1924     {
1925       /* Space has not been allocated for the output relocations.
1926          This can happen when we are called by a specific backend
1927          because somebody is attempting to link together different
1928          types of object files.  Handling this case correctly is
1929          difficult, and sometimes impossible.  */
1930       abort ();
1931     }
1932
1933   /* Get the canonical symbols.  The generic linker will always have
1934      retrieved them by this point, but we may be being called by a
1935      specific linker when linking different types of object files
1936      together.  */
1937   if (bfd_get_outsymbols (input_bfd) == (asymbol **) NULL)
1938     {
1939       size_t symsize;
1940
1941       symsize = get_symtab_upper_bound (input_bfd);
1942       input_bfd->outsymbols = (asymbol **) bfd_alloc (input_bfd, symsize);
1943       input_bfd->symcount = bfd_canonicalize_symtab (input_bfd,
1944                                                      input_bfd->outsymbols);
1945     }
1946
1947   /* Get and relocate the section contents.  */
1948   contents = (bfd_byte *) alloca (bfd_section_size (input_bfd, input_section));
1949   contents = (bfd_get_relocated_section_contents
1950               (output_bfd, info, link_order, contents, info->relocateable,
1951                bfd_get_outsymbols (input_bfd)));
1952
1953   /* Output the section contents.  */
1954   if (! bfd_set_section_contents (output_bfd, output_section, (PTR) contents,
1955                                   link_order->offset, link_order->size))
1956     return false;
1957
1958   return true;
1959 }