2010-03-22 Rafael Espindola <espindola@google.com>
[external/binutils.git] / gold / gold.cc
1 // gold.cc -- main linker functions
2
3 // Copyright 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4 // Written by Ian Lance Taylor <iant@google.com>.
5
6 // This file is part of gold.
7
8 // This program is free software; you can redistribute it and/or modify
9 // it under the terms of the GNU General Public License as published by
10 // the Free Software Foundation; either version 3 of the License, or
11 // (at your option) any later version.
12
13 // This program is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 // GNU General Public License for more details.
17
18 // You should have received a copy of the GNU General Public License
19 // along with this program; if not, write to the Free Software
20 // Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
21 // MA 02110-1301, USA.
22
23 #include "gold.h"
24
25 #include <cstdlib>
26 #include <cstdio>
27 #include <cstring>
28 #include <unistd.h>
29 #include <algorithm>
30 #include "libiberty.h"
31
32 #include "options.h"
33 #include "debug.h"
34 #include "workqueue.h"
35 #include "dirsearch.h"
36 #include "readsyms.h"
37 #include "symtab.h"
38 #include "common.h"
39 #include "object.h"
40 #include "layout.h"
41 #include "reloc.h"
42 #include "defstd.h"
43 #include "plugin.h"
44 #include "gc.h"
45 #include "icf.h"
46 #include "incremental.h"
47
48 namespace gold
49 {
50
51 const char* program_name;
52
53 void
54 gold_exit(bool status)
55 {
56   if (parameters != NULL
57       && parameters->options_valid()
58       && parameters->options().has_plugins())
59     parameters->options().plugins()->cleanup();
60   if (!status && parameters != NULL && parameters->options_valid())
61     unlink_if_ordinary(parameters->options().output_file_name());
62   exit(status ? EXIT_SUCCESS : EXIT_FAILURE);
63 }
64
65 void
66 gold_nomem()
67 {
68   // We are out of memory, so try hard to print a reasonable message.
69   // Note that we don't try to translate this message, since the
70   // translation process itself will require memory.
71
72   // LEN only exists to avoid a pointless warning when write is
73   // declared with warn_use_result, as when compiling with
74   // -D_USE_FORTIFY on GNU/Linux.  Casting to void does not appear to
75   // work, at least not with gcc 4.3.0.
76
77   ssize_t len = write(2, program_name, strlen(program_name));
78   if (len >= 0)
79     {
80       const char* const s = ": out of memory\n";
81       len = write(2, s, strlen(s));
82     }
83   gold_exit(false);
84 }
85
86 // Handle an unreachable case.
87
88 void
89 do_gold_unreachable(const char* filename, int lineno, const char* function)
90 {
91   fprintf(stderr, _("%s: internal error in %s, at %s:%d\n"),
92           program_name, function, filename, lineno);
93   gold_exit(false);
94 }
95
96 // This class arranges to run the functions done in the middle of the
97 // link.  It is just a closure.
98
99 class Middle_runner : public Task_function_runner
100 {
101  public:
102   Middle_runner(const General_options& options,
103                 const Input_objects* input_objects,
104                 Symbol_table* symtab,
105                 Layout* layout, Mapfile* mapfile)
106     : options_(options), input_objects_(input_objects), symtab_(symtab),
107       layout_(layout), mapfile_(mapfile)
108   { }
109
110   void
111   run(Workqueue*, const Task*);
112
113  private:
114   const General_options& options_;
115   const Input_objects* input_objects_;
116   Symbol_table* symtab_;
117   Layout* layout_;
118   Mapfile* mapfile_;
119 };
120
121 void
122 Middle_runner::run(Workqueue* workqueue, const Task* task)
123 {
124   queue_middle_tasks(this->options_, task, this->input_objects_, this->symtab_,
125                      this->layout_, workqueue, this->mapfile_);
126 }
127
128 // This class arranges the tasks to process the relocs for garbage collection.
129
130 class Gc_runner : public Task_function_runner 
131 {
132   public:
133    Gc_runner(const General_options& options,
134              const Input_objects* input_objects,
135              Symbol_table* symtab,
136              Layout* layout, Mapfile* mapfile)
137     : options_(options), input_objects_(input_objects), symtab_(symtab),
138       layout_(layout), mapfile_(mapfile)
139    { }
140
141   void
142   run(Workqueue*, const Task*);
143
144  private:
145   const General_options& options_;
146   const Input_objects* input_objects_;
147   Symbol_table* symtab_;
148   Layout* layout_;
149   Mapfile* mapfile_;
150 };
151
152 void
153 Gc_runner::run(Workqueue* workqueue, const Task* task)
154 {
155   queue_middle_gc_tasks(this->options_, task, this->input_objects_, 
156                         this->symtab_, this->layout_, workqueue, 
157                         this->mapfile_);
158 }
159
160 // Queue up the initial set of tasks for this link job.
161
162 void
163 queue_initial_tasks(const General_options& options,
164                     Dirsearch& search_path,
165                     const Command_line& cmdline,
166                     Workqueue* workqueue, Input_objects* input_objects,
167                     Symbol_table* symtab, Layout* layout, Mapfile* mapfile)
168 {
169   if (cmdline.begin() == cmdline.end())
170     {
171       if (options.printed_version())
172         gold_exit(true);
173       gold_fatal(_("no input files"));
174     }
175
176   int thread_count = options.thread_count_initial();
177   if (thread_count == 0)
178     thread_count = cmdline.number_of_input_files();
179   workqueue->set_thread_count(thread_count);
180
181   if (cmdline.options().incremental())
182     {
183       Incremental_checker incremental_checker(
184           parameters->options().output_file_name(),
185           layout->incremental_inputs());
186       if (incremental_checker.can_incrementally_link_output_file())
187         {
188           // TODO: remove when incremental linking implemented.
189           printf("Incremental linking might be possible "
190               "(not implemented yet)\n");
191         }
192       // TODO: If we decide on an incremental build, fewer tasks
193       // should be scheduled.
194     }
195
196   // Read the input files.  We have to add the symbols to the symbol
197   // table in order.  We do this by creating a separate blocker for
198   // each input file.  We associate the blocker with the following
199   // input file, to give us a convenient place to delete it.
200   Task_token* this_blocker = NULL;
201   for (Command_line::const_iterator p = cmdline.begin();
202        p != cmdline.end();
203        ++p)
204     {
205       Task_token* next_blocker = new Task_token(true);
206       next_blocker->add_blocker();
207       workqueue->queue(new Read_symbols(input_objects, symtab, layout,
208                                         &search_path, 0, mapfile, &*p, NULL,
209                                         NULL, this_blocker, next_blocker));
210       this_blocker = next_blocker;
211     }
212
213   if (options.has_plugins())
214     {
215       Task_token* next_blocker = new Task_token(true);
216       next_blocker->add_blocker();
217       workqueue->queue(new Plugin_hook(options, input_objects, symtab, layout,
218                                        &search_path, mapfile, this_blocker,
219                                        next_blocker));
220       this_blocker = next_blocker;
221     }
222
223   if (parameters->options().relocatable()
224       && (parameters->options().gc_sections()
225           || parameters->options().icf_enabled()))
226     gold_error(_("cannot mix -r with --gc-sections or --icf"));
227
228   if (parameters->options().gc_sections()
229       || parameters->options().icf_enabled())
230     {
231       workqueue->queue(new Task_function(new Gc_runner(options,
232                                                        input_objects,
233                                                        symtab,
234                                                        layout,
235                                                        mapfile),
236                                          this_blocker,
237                                          "Task_function Gc_runner"));
238     }
239   else
240     {
241       workqueue->queue(new Task_function(new Middle_runner(options,
242                                                            input_objects,
243                                                            symtab,
244                                                            layout,
245                                                            mapfile),
246                                          this_blocker,
247                                          "Task_function Middle_runner"));
248     }
249 }
250
251 // Queue up a set of tasks to be done before queueing the middle set
252 // of tasks.  This is only necessary when garbage collection
253 // (--gc-sections) of unused sections is desired.  The relocs are read
254 // and processed here early to determine the garbage sections before the
255 // relocs can be scanned in later tasks.
256
257 void
258 queue_middle_gc_tasks(const General_options& options,
259                       const Task* ,
260                       const Input_objects* input_objects,
261                       Symbol_table* symtab,
262                       Layout* layout,
263                       Workqueue* workqueue,
264                       Mapfile* mapfile)
265 {
266   // Read_relocs for all the objects must be done and processed to find
267   // unused sections before any scanning of the relocs can take place.
268   Task_token* this_blocker = NULL;
269   for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
270        p != input_objects->relobj_end();
271        ++p)
272     {
273       Task_token* next_blocker = new Task_token(true);
274       next_blocker->add_blocker();
275       workqueue->queue(new Read_relocs(symtab, layout, *p, this_blocker,
276                                        next_blocker));
277       this_blocker = next_blocker;
278     }
279   workqueue->queue(new Task_function(new Middle_runner(options,
280                                                        input_objects,
281                                                        symtab,
282                                                        layout,
283                                                        mapfile),
284                                      this_blocker,
285                                      "Task_function Middle_runner"));
286 }
287
288 // Queue up the middle set of tasks.  These are the tasks which run
289 // after all the input objects have been found and all the symbols
290 // have been read, but before we lay out the output file.
291
292 void
293 queue_middle_tasks(const General_options& options,
294                    const Task* task,
295                    const Input_objects* input_objects,
296                    Symbol_table* symtab,
297                    Layout* layout,
298                    Workqueue* workqueue,
299                    Mapfile* mapfile)
300 {
301   // Add any symbols named with -u options to the symbol table.
302   symtab->add_undefined_symbols_from_command_line();
303
304   // If garbage collection was chosen, relocs have been read and processed
305   // at this point by pre_middle_tasks.  Layout can then be done for all 
306   // objects.
307   if (parameters->options().gc_sections())
308     {
309       // Find the start symbol if any.
310       Symbol* start_sym;
311       if (parameters->options().entry())
312         start_sym = symtab->lookup(parameters->options().entry());
313       else
314         start_sym = symtab->lookup("_start");
315       if (start_sym != NULL)
316         {
317           bool is_ordinary;
318           unsigned int shndx = start_sym->shndx(&is_ordinary);
319           if (is_ordinary) 
320             {
321               symtab->gc()->worklist().push(
322                 Section_id(start_sym->object(), shndx));
323             }
324         }
325       // Symbols named with -u should not be considered garbage.
326       symtab->gc_mark_undef_symbols();
327       gold_assert(symtab->gc() != NULL);
328       // Do a transitive closure on all references to determine the worklist.
329       symtab->gc()->do_transitive_closure();
330     }
331
332   // If identical code folding (--icf) is chosen it makes sense to do it 
333   // only after garbage collection (--gc-sections) as we do not want to 
334   // be folding sections that will be garbage.
335   if (parameters->options().icf_enabled())
336     {
337       symtab->icf()->find_identical_sections(input_objects, symtab);
338     }
339
340   // Call Object::layout for the second time to determine the 
341   // output_sections for all referenced input sections.  When 
342   // --gc-sections or --icf is turned on, Object::layout is 
343   // called twice.  It is called the first time when the 
344   // symbols are added.
345   if (parameters->options().gc_sections()
346       || parameters->options().icf_enabled())
347     {
348       for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
349            p != input_objects->relobj_end();
350            ++p)
351         {
352           (*p)->layout(symtab, layout, NULL);
353         }
354     }
355
356   // Layout deferred objects due to plugins.
357   if (parameters->options().has_plugins())
358     {
359       Plugin_manager* plugins = parameters->options().plugins();
360       gold_assert(plugins != NULL);
361       plugins->layout_deferred_objects();
362     }     
363
364   if (parameters->options().gc_sections()
365       || parameters->options().icf_enabled())
366     {
367       for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
368            p != input_objects->relobj_end();
369            ++p)
370         {
371           // Update the value of output_section stored in rd.
372           Read_relocs_data *rd = (*p)->get_relocs_data();
373           for (Read_relocs_data::Relocs_list::iterator q = rd->relocs.begin();
374                q != rd->relocs.end();
375                ++q)
376             {
377               q->output_section = (*p)->output_section(q->data_shndx);
378               q->needs_special_offset_handling = 
379                       (*p)->is_output_section_offset_invalid(q->data_shndx);
380             }
381         }
382     }
383
384   // We have to support the case of not seeing any input objects, and
385   // generate an empty file.  Existing builds depend on being able to
386   // pass an empty archive to the linker and get an empty object file
387   // out.  In order to do this we need to use a default target.
388   if (input_objects->number_of_input_objects() == 0)
389     parameters_force_valid_target();
390
391   int thread_count = options.thread_count_middle();
392   if (thread_count == 0)
393     thread_count = std::max(2, input_objects->number_of_input_objects());
394   workqueue->set_thread_count(thread_count);
395
396   // Now we have seen all the input files.
397   const bool doing_static_link =
398     (!input_objects->any_dynamic()
399      && !parameters->options().output_is_position_independent());
400   set_parameters_doing_static_link(doing_static_link);
401   if (!doing_static_link && options.is_static())
402     {
403       // We print out just the first .so we see; there may be others.
404       gold_assert(input_objects->dynobj_begin() != input_objects->dynobj_end());
405       gold_error(_("cannot mix -static with dynamic object %s"),
406                  (*input_objects->dynobj_begin())->name().c_str());
407     }
408   if (!doing_static_link && parameters->options().relocatable())
409     gold_fatal(_("cannot mix -r with dynamic object %s"),
410                (*input_objects->dynobj_begin())->name().c_str());
411   if (!doing_static_link
412       && options.oformat_enum() != General_options::OBJECT_FORMAT_ELF)
413     gold_fatal(_("cannot use non-ELF output format with dynamic object %s"),
414                (*input_objects->dynobj_begin())->name().c_str());
415
416   if (parameters->options().relocatable())
417     {
418       Input_objects::Relobj_iterator p = input_objects->relobj_begin();
419       if (p != input_objects->relobj_end())
420         {
421           bool uses_split_stack = (*p)->uses_split_stack();
422           for (++p; p != input_objects->relobj_end(); ++p)
423             {
424               if ((*p)->uses_split_stack() != uses_split_stack)
425                 gold_fatal(_("cannot mix split-stack '%s' and "
426                              "non-split-stack '%s' when using -r"),
427                            (*input_objects->relobj_begin())->name().c_str(),
428                            (*p)->name().c_str());
429             }
430         }
431     }
432
433   if (is_debugging_enabled(DEBUG_SCRIPT))
434     layout->script_options()->print(stderr);
435
436   // For each dynamic object, record whether we've seen all the
437   // dynamic objects that it depends upon.
438   input_objects->check_dynamic_dependencies();
439
440   // See if any of the input definitions violate the One Definition Rule.
441   // TODO: if this is too slow, do this as a task, rather than inline.
442   symtab->detect_odr_violations(task, options.output_file_name());
443
444   // Do the --no-undefined-version check.
445   if (!parameters->options().undefined_version())
446     {
447       Script_options* so = layout->script_options();
448       so->version_script_info()->check_unmatched_names(symtab);
449     }
450
451   // Create any automatic note sections.
452   layout->create_notes();
453
454   // Create any output sections required by any linker script.
455   layout->create_script_sections();
456
457   // Define some sections and symbols needed for a dynamic link.  This
458   // handles some cases we want to see before we read the relocs.
459   layout->create_initial_dynamic_sections(symtab);
460
461   // Define symbols from any linker scripts.
462   layout->define_script_symbols(symtab);
463
464   // Attach sections to segments.
465   layout->attach_sections_to_segments();
466
467   if (!parameters->options().relocatable())
468     {
469       // Predefine standard symbols.
470       define_standard_symbols(symtab, layout);
471
472       // Define __start and __stop symbols for output sections where
473       // appropriate.
474       layout->define_section_symbols(symtab);
475     }
476
477   // Make sure we have symbols for any required group signatures.
478   layout->define_group_signatures(symtab);
479
480   Task_token* this_blocker = NULL;
481
482   // Allocate common symbols.  We use a blocker to run this before the
483   // Scan_relocs tasks, because it writes to the symbol table just as
484   // they do.
485   if (parameters->options().define_common())
486     {
487       this_blocker = new Task_token(true);
488       this_blocker->add_blocker();
489       workqueue->queue(new Allocate_commons_task(symtab, layout, mapfile,
490                                                  this_blocker));
491     }
492
493   // If doing garbage collection, the relocations have already been read.
494   // Otherwise, read and scan the relocations.
495   if (parameters->options().gc_sections()
496       || parameters->options().icf_enabled())
497     {
498       for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
499            p != input_objects->relobj_end();
500            ++p)
501         {
502           Task_token* next_blocker = new Task_token(true);
503           next_blocker->add_blocker();
504           workqueue->queue(new Scan_relocs(symtab, layout, *p, 
505                                            (*p)->get_relocs_data(),
506                                            this_blocker, next_blocker));
507           this_blocker = next_blocker;
508         }
509     }
510   else
511     {
512       // Read the relocations of the input files.  We do this to find
513       // which symbols are used by relocations which require a GOT and/or
514       // a PLT entry, or a COPY reloc.  When we implement garbage
515       // collection we will do it here by reading the relocations in a
516       // breadth first search by references.
517       //
518       // We could also read the relocations during the first pass, and
519       // mark symbols at that time.  That is how the old GNU linker works.
520       // Doing that is more complex, since we may later decide to discard
521       // some of the sections, and thus change our minds about the types
522       // of references made to the symbols.
523       for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
524            p != input_objects->relobj_end();
525            ++p)
526         {
527           Task_token* next_blocker = new Task_token(true);
528           next_blocker->add_blocker();
529           workqueue->queue(new Read_relocs(symtab, layout, *p, this_blocker,
530                                            next_blocker));
531           this_blocker = next_blocker;
532         }
533     }
534
535   // If we failed to open any input files, it's possible for
536   // THIS_BLOCKER to be NULL here.  There's no real point in
537   // continuing if that happens.
538   if (this_blocker == NULL)
539     {
540       gold_assert(parameters->errors()->error_count() > 0);
541       gold_exit(false);
542     }
543
544   // When all those tasks are complete, we can start laying out the
545   // output file.
546   // TODO(csilvers): figure out a more principled way to get the target
547   Target* target = const_cast<Target*>(&parameters->target());
548   workqueue->queue(new Task_function(new Layout_task_runner(options,
549                                                             input_objects,
550                                                             symtab,
551                                                             target,
552                                                             layout,
553                                                             mapfile),
554                                      this_blocker,
555                                      "Task_function Layout_task_runner"));
556 }
557
558 // Queue up the final set of tasks.  This is called at the end of
559 // Layout_task.
560
561 void
562 queue_final_tasks(const General_options& options,
563                   const Input_objects* input_objects,
564                   const Symbol_table* symtab,
565                   Layout* layout,
566                   Workqueue* workqueue,
567                   Output_file* of)
568 {
569   int thread_count = options.thread_count_final();
570   if (thread_count == 0)
571     thread_count = std::max(2, input_objects->number_of_input_objects());
572   workqueue->set_thread_count(thread_count);
573
574   bool any_postprocessing_sections = layout->any_postprocessing_sections();
575
576   // Use a blocker to wait until all the input sections have been
577   // written out.
578   Task_token* input_sections_blocker = NULL;
579   if (!any_postprocessing_sections)
580     {
581       input_sections_blocker = new Task_token(true);
582       input_sections_blocker->add_blockers(input_objects->number_of_relobjs());
583     }
584
585   // Use a blocker to block any objects which have to wait for the
586   // output sections to complete before they can apply relocations.
587   Task_token* output_sections_blocker = new Task_token(true);
588   output_sections_blocker->add_blocker();
589
590   // Use a blocker to block the final cleanup task.
591   Task_token* final_blocker = new Task_token(true);
592   // Write_symbols_task, Write_sections_task, Write_data_task,
593   // Relocate_tasks.
594   final_blocker->add_blockers(3);
595   final_blocker->add_blockers(input_objects->number_of_relobjs());
596   if (!any_postprocessing_sections)
597     final_blocker->add_blocker();
598
599   // Queue a task to write out the symbol table.
600   workqueue->queue(new Write_symbols_task(layout,
601                                           symtab,
602                                           input_objects,
603                                           layout->sympool(),
604                                           layout->dynpool(),
605                                           of,
606                                           final_blocker));
607
608   // Queue a task to write out the output sections.
609   workqueue->queue(new Write_sections_task(layout, of, output_sections_blocker,
610                                            final_blocker));
611
612   // Queue a task to write out everything else.
613   workqueue->queue(new Write_data_task(layout, symtab, of, final_blocker));
614
615   // Queue a task for each input object to relocate the sections and
616   // write out the local symbols.
617   for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
618        p != input_objects->relobj_end();
619        ++p)
620     workqueue->queue(new Relocate_task(symtab, layout, *p, of,
621                                        input_sections_blocker,
622                                        output_sections_blocker,
623                                        final_blocker));
624
625   // Queue a task to write out the output sections which depend on
626   // input sections.  If there are any sections which require
627   // postprocessing, then we need to do this last, since it may resize
628   // the output file.
629   if (!any_postprocessing_sections)
630     {
631       Task* t = new Write_after_input_sections_task(layout, of,
632                                                     input_sections_blocker,
633                                                     final_blocker);
634       workqueue->queue(t);
635     }
636   else
637     {
638       Task_token *new_final_blocker = new Task_token(true);
639       new_final_blocker->add_blocker();
640       Task* t = new Write_after_input_sections_task(layout, of,
641                                                     final_blocker,
642                                                     new_final_blocker);
643       workqueue->queue(t);
644       final_blocker = new_final_blocker;
645     }
646
647   // Queue a task to close the output file.  This will be blocked by
648   // FINAL_BLOCKER.
649   workqueue->queue(new Task_function(new Close_task_runner(&options, layout,
650                                                            of),
651                                      final_blocker,
652                                      "Task_function Close_task_runner"));
653 }
654
655 } // End namespace gold.