Re: PATCH: 2 stage BFD linker for LTO plugin

[Ian Lance Taylor <iant at google dot com>]

After some discussion on IRC, here is another approach to resolving the
issue with static linking and LTO.

In this approach, the linker keeps track of all archives found after the
first file claimed by the plugin.  If the plugin adds any object files,
and the object files refer to any symbols which are not yet defined,
then the linker will scan all the saved archives, in order, for a
definition of the symbol.  If a definition is found, the linker will
pull in the appropriate object from the archive.  If that object, in
turn, has any undefined symbols, the linker will pull in the appropriate
object from that archive or any later ones, and so forth.  The linker
will honor --start-group/--end-group while rescanning.

This should ensure that any previously unseen undefined symbols
introduced by the compiler are handled correctly.  I think it is
appropriate to do this unconditionally when using plugins, as there is
no other reasonable way to handle undefined symbols in a file added by a
plugin.

I've appended a patch to gold which implements this approach.  The patch
is reasonably efficient and introduces no unnecessary file I/O.  With
this patch to gold, and no change to gcc, the problematic -static test
cases which I know about pass.  Also all the current lto.exp tests pass.
All those tests also pass if I edit the gcc LTO plugin to ignore the
-pass-through option, as that option is not necessary when the linker
implements this approach.

As this patch does not require any changes to gcc, and fixes some cases
which are clearly bugs, I plan to commit this patch to binutils mainline
and to binutils 2.21 branch after a few days if I don't hear any
comments.

Ian


2011-01-18  Ian Lance Taylor  <iant@google.com>

	* plugin.cc (class Plugin_rescan): Define new class.
	(Plugin_manager::claim_file): Set any_claimed_.
	(Plugin_manager::save_archive): New function.
	(Plugin_manager::save_input_group): New function.
	(Plugin_manager::all_symbols_read): Create Plugin_rescan task if
	necessary.
	(Plugin_manager::new_undefined_symbol): New function.
	(Plugin_manager::rescan): New function.
	(Plugin_manager::rescannable_defines): New function.
	(Plugin_manager::add_input_file): Set any_added_.
	* plugin.h (class Plugin_manager): define new fields rescannable_,
	undefined_symbols_, any_claimed_, and any_added_.  Declare
	Plugin_rescan as friend.  Declare new functions.
	(Plugin_manager::Rescannable): Define type.
	(Plugin_manager::Rescannable_list): Define type.
	(Plugin_manager::Undefined_symbol_list): Define type.
	(Plugin_manager::Plugin_manager): Initialize new fields.
	* archive.cc (Archive::defines_symbol): New function.
	(Add_archive_symbols::run): Pass archive to plugins if any.
	* archive.h (class Archive): Declare defines_symbol.
	* readsyms.cc (Input_group::~Input_group): New function.
	(Finish_group::run): Pass input_group to plugins if any.
	* readsyms.h (class Input_group): Declare destructor.
	* symtab.cc (add_from_object): Pass undefined symbol to plugins if
	any.


Index: archive.h
===================================================================
RCS file: /cvs/src/src/gold/archive.h,v
retrieving revision 1.32
diff -u -p -r1.32 archive.h
--- archive.h	14 Dec 2010 19:03:29 -0000	1.32
+++ archive.h	18 Jan 2011 23:19:23 -0000
@@ -152,6 +152,10 @@ class Archive
   bool
   add_symbols(Symbol_table*, Layout*, Input_objects*, Mapfile*);
 
+  // Return whether the archive defines the symbol.
+  bool
+  defines_symbol(Symbol*) const;
+
   // Dump statistical information to stderr.
   static void
   print_stats();
Index: archive.cc
===================================================================
RCS file: /cvs/src/src/gold/archive.cc,v
retrieving revision 1.62
diff -u -p -r1.62 archive.cc
--- archive.cc	14 Dec 2010 19:03:29 -0000	1.62
+++ archive.cc	18 Jan 2011 23:19:24 -0000
@@ -779,6 +779,42 @@ Archive::add_symbols(Symbol_table* symta
   return true;
 }
 
+// Return whether the archive includes a member which defines the
+// symbol SYM.
+
+bool
+Archive::defines_symbol(Symbol* sym) const
+{
+  const char* symname = sym->name();
+  size_t symname_len = strlen(symname);
+  size_t armap_size = this->armap_.size();
+  for (size_t i = 0; i < armap_size; ++i)
+    {
+      if (this->armap_checked_[i])
+	continue;
+      const char* archive_symname = (this->armap_names_.data()
+				     + this->armap_[i].name_offset);
+      if (strncmp(archive_symname, symname, symname_len) != 0)
+	continue;
+      char c = archive_symname[symname_len];
+      if (c == '\0' && sym->version() == NULL)
+	return true;
+      if (c == '@')
+	{
+	  const char* ver = archive_symname + symname_len + 1;
+	  if (*ver == '@')
+	    {
+	      if (sym->version() == NULL)
+		return true;
+	      ++ver;
+	    }
+	  if (sym->version() != NULL && strcmp(sym->version(), ver) == 0)
+	    return true;
+	}
+    }
+  return false;
+}
+
 // Include all the archive members in the link.  This is for --whole-archive.
 
 bool
@@ -1001,8 +1037,18 @@ Add_archive_symbols::run(Workqueue* work
       if (incremental_inputs != NULL)
 	incremental_inputs->report_archive_end(this->archive_);
 
-      // We no longer need to know about this archive.
-      delete this->archive_;
+      if (!parameters->options().has_plugins()
+	  || this->archive_->input_file()->options().whole_archive())
+	{
+	  // We no longer need to know about this archive.
+	  delete this->archive_;
+	}
+      else
+	{
+	  // The plugin interface may want to rescan this archive.
+	  parameters->options().plugins()->save_archive(this->archive_);
+	}
+
       this->archive_ = NULL;
     }
 }
Index: plugin.h
===================================================================
RCS file: /cvs/src/src/gold/plugin.h,v
retrieving revision 1.15
diff -u -p -r1.15 plugin.h
--- plugin.h	25 Aug 2010 08:36:54 -0000	1.15
+++ plugin.h	18 Jan 2011 23:19:24 -0000
@@ -36,12 +36,17 @@ namespace gold
 class General_options;
 class Input_file;
 class Input_objects;
+class Archive;
+class Input_group;
+class Symbol;
 class Symbol_table;
 class Layout;
 class Dirsearch;
 class Mapfile;
+class Task;
 class Task_token;
 class Pluginobj;
+class Plugin_rescan;
 
 // This class represents a single plugin library.
 
@@ -124,7 +129,8 @@ class Plugin_manager
  public:
   Plugin_manager(const General_options& options)
     : plugins_(), objects_(), deferred_layout_objects_(), input_file_(NULL),
-      plugin_input_file_(), in_replacement_phase_(false),
+      plugin_input_file_(), rescannable_(), undefined_symbols_(),
+      any_claimed_(false), in_replacement_phase_(false), any_added_(false),
       options_(options), workqueue_(NULL), task_(NULL), input_objects_(NULL),
       symtab_(NULL), layout_(NULL), dirpath_(NULL), mapfile_(NULL),
       this_blocker_(NULL), extra_search_path_()
@@ -153,6 +159,16 @@ class Plugin_manager
   Pluginobj*
   claim_file(Input_file* input_file, off_t offset, off_t filesize);
 
+  // Let the plugin manager save an archive for later rescanning.
+  // This takes ownership of the Archive pointer.
+  void
+  save_archive(Archive*);
+
+  // Let the plugin manager save an input group for later rescanning.
+  // This takes ownership of the Input_group pointer.
+  void
+  save_input_group(Input_group*);
+
   // Call the all-symbols-read handlers.
   void
   all_symbols_read(Workqueue* workqueue, Task* task,
@@ -160,6 +176,11 @@ class Plugin_manager
                    Layout* layout, Dirsearch* dirpath, Mapfile* mapfile,
                    Task_token** last_blocker);
 
+  // Tell the plugin manager that we've a new undefined symbol which
+  // may require rescanning.
+  void
+  new_undefined_symbol(Symbol*);
+
   // Run deferred layout.
   void
   layout_deferred_objects();
@@ -245,9 +266,42 @@ class Plugin_manager
   Plugin_manager(const Plugin_manager&);
   Plugin_manager& operator=(const Plugin_manager&);
 
+  // Plugin_rescan is a Task which calls the private rescan method.
+  friend class Plugin_rescan;
+
+  // An archive or input group which may have to be rescanned if a
+  // plugin adds a new file.
+  struct Rescannable
+  {
+    bool is_archive;
+    union
+    {
+      Archive* archive;
+      Input_group* input_group;
+    } u;
+
+    Rescannable(Archive* archive)
+      : is_archive(true)
+    { this->u.archive = archive; }
+
+    Rescannable(Input_group* input_group)
+      : is_archive(false)
+    { this->u.input_group = input_group; }
+  };
+
   typedef std::list<Plugin*> Plugin_list;
   typedef std::vector<Pluginobj*> Object_list;
   typedef std::vector<Relobj*> Deferred_layout_list;
+  typedef std::vector<Rescannable> Rescannable_list;
+  typedef std::vector<Symbol*> Undefined_symbol_list;
+
+  // Rescan archives for undefined symbols.
+  void
+  rescan(Task*);
+
+  // See whether the rescannable at index I defines SYM.
+  bool
+  rescannable_defines(size_t i, Symbol* sym);
 
   // The list of plugin libraries.
   Plugin_list plugins_;
@@ -265,11 +319,24 @@ class Plugin_manager
   Input_file* input_file_;
   struct ld_plugin_input_file plugin_input_file_;
 
-  // TRUE after the all symbols read event; indicates that we are
-  // processing replacement files whose symbols should replace the
+  // A list of archives and input groups being saved for possible
+  // later rescanning.
+  Rescannable_list rescannable_;
+
+  // A list of undefined symbols found in added files.
+  Undefined_symbol_list undefined_symbols_;
+
+  // Whether any input files have been claimed by a plugin.
+  bool any_claimed_;
+
+  // Set to true after the all symbols read event; indicates that we
+  // are processing replacement files whose symbols should replace the
   // placeholder symbols from the Pluginobj objects.
   bool in_replacement_phase_;
 
+  // Whether any input files or libraries were added by a plugin.
+  bool any_added_;
+
   const General_options& options_;
   Workqueue* workqueue_;
   Task* task_;
Index: plugin.cc
===================================================================
RCS file: /cvs/src/src/gold/plugin.cc,v
retrieving revision 1.41
diff -u -p -r1.41 plugin.cc
--- plugin.cc	5 Nov 2010 21:14:12 -0000	1.41
+++ plugin.cc	18 Jan 2011 23:19:24 -0000
@@ -261,6 +261,45 @@ Plugin::cleanup()
     }
 }
 
+// This task is used to rescan archives as needed.
+
+class Plugin_rescan : public Task
+{
+ public:
+  Plugin_rescan(Task_token* this_blocker, Task_token* next_blocker)
+    : this_blocker_(this_blocker), next_blocker_(next_blocker)
+  { }
+
+  ~Plugin_rescan()
+  {
+    delete this->this_blocker_;
+  }
+
+  Task_token*
+  is_runnable()
+  {
+    if (this->this_blocker_->is_blocked())
+      return this->this_blocker_;
+    return NULL;
+  }
+
+  void
+  locks(Task_locker* tl)
+  { tl->add(this, this->next_blocker_); }
+
+  void
+  run(Workqueue*)
+  { parameters->options().plugins()->rescan(this); }
+
+  std::string
+  get_name() const
+  { return "Plugin_rescan"; }
+
+ private:
+  Task_token* this_blocker_;
+  Task_token* next_blocker_;
+};
+
 // Plugin_manager methods.
 
 Plugin_manager::~Plugin_manager()
@@ -311,6 +350,8 @@ Plugin_manager::claim_file(Input_file* i
     {
       if ((*this->current_)->claim_file(&this->plugin_input_file_))
         {
+	  this->any_claimed_ = true;
+
           if (this->objects_.size() > handle)
             return this->objects_[handle];
 
@@ -324,6 +365,31 @@ Plugin_manager::claim_file(Input_file* i
   return NULL;
 }
 
+// Save an archive.  This is used so that a plugin can add a file
+// which refers to a symbol which was not previously referenced.  In
+// that case we want to pretend that the symbol was referenced before,
+// and pull in the archive object.
+
+void
+Plugin_manager::save_archive(Archive* archive)
+{
+  if (this->in_replacement_phase_ || !this->any_claimed_)
+    delete archive;
+  else
+    this->rescannable_.push_back(Rescannable(archive));
+}
+
+// Save an Input_group.  This is like save_archive.
+
+void
+Plugin_manager::save_input_group(Input_group* input_group)
+{
+  if (this->in_replacement_phase_ || !this->any_claimed_)
+    delete input_group;
+  else
+    this->rescannable_.push_back(Rescannable(input_group));
+}
+
 // Call the all-symbols-read handlers.
 
 void
@@ -348,9 +414,146 @@ Plugin_manager::all_symbols_read(Workque
        ++this->current_)
     (*this->current_)->all_symbols_read();
 
+  if (this->any_added_)
+    {
+      Task_token* next_blocker = new Task_token(true);
+      next_blocker->add_blocker();
+      workqueue->queue(new Plugin_rescan(this->this_blocker_, next_blocker));
+      this->this_blocker_ = next_blocker;
+    }
+
   *last_blocker = this->this_blocker_;
 }
 
+// This is called when we see a new undefined symbol.  If we are in
+// the replacement phase, this means that we may need to rescan some
+// archives we have previously seen.
+
+void
+Plugin_manager::new_undefined_symbol(Symbol* sym)
+{
+  if (this->in_replacement_phase_)
+    this->undefined_symbols_.push_back(sym);
+}
+
+// Rescan archives as needed.  This handles the case where a new
+// object file added by a plugin has an undefined reference to some
+// symbol defined in an archive.
+
+void
+Plugin_manager::rescan(Task* task)
+{
+  size_t rescan_pos = 0;
+  size_t rescan_size = this->rescannable_.size();
+  while (!this->undefined_symbols_.empty())
+    {
+      if (rescan_pos >= rescan_size)
+	{
+	  this->undefined_symbols_.clear();
+	  return;
+	}
+
+      Undefined_symbol_list undefs;
+      undefs.reserve(this->undefined_symbols_.size());
+      this->undefined_symbols_.swap(undefs);
+
+      size_t min_rescan_pos = rescan_size;
+
+      for (Undefined_symbol_list::const_iterator p = undefs.begin();
+	   p != undefs.end();
+	   ++p)
+	{
+	  if (!(*p)->is_undefined())
+	    continue;
+
+	  this->undefined_symbols_.push_back(*p);
+
+	  // Find the first rescan archive which defines this symbol,
+	  // starting at the current rescan position.  The rescan position
+	  // exists so that given -la -lb -lc we don't look for undefined
+	  // symbols in -lb back in -la, but instead get the definition
+	  // from -lc.  Don't bother to look past the current minimum
+	  // rescan position.
+	  for (size_t i = rescan_pos; i < min_rescan_pos; ++i)
+	    {
+	      if (this->rescannable_defines(i, *p))
+		{
+		  min_rescan_pos = i;
+		  break;
+		}
+	    }
+	}
+
+      if (min_rescan_pos >= rescan_size)
+	{
+	  // We didn't find any rescannable archives which define any
+	  // undefined symbols.
+	  return;
+	}
+
+      const Rescannable& r(this->rescannable_[min_rescan_pos]);
+      if (r.is_archive)
+	{
+	  Task_lock_obj<Archive> tl(task, r.u.archive);
+	  r.u.archive->add_symbols(this->symtab_, this->layout_,
+				   this->input_objects_, this->mapfile_);
+	}
+      else
+	{
+	  size_t next_saw_undefined = this->symtab_->saw_undefined();
+	  size_t saw_undefined;
+	  do
+	    {
+	      saw_undefined = next_saw_undefined;
+
+	      for (Input_group::const_iterator p = r.u.input_group->begin();
+		   p != r.u.input_group->end();
+		   ++p)
+		{
+		  Task_lock_obj<Archive> tl(task, *p);
+
+		  (*p)->add_symbols(this->symtab_, this->layout_,
+				    this->input_objects_, this->mapfile_);
+		}
+
+	      next_saw_undefined = this->symtab_->saw_undefined();
+	    }
+	  while (saw_undefined != next_saw_undefined);
+	}
+
+      for (size_t i = rescan_pos; i < min_rescan_pos + 1; ++i)
+	{
+	  if (this->rescannable_[i].is_archive)
+	    delete this->rescannable_[i].u.archive;
+	  else
+	    delete this->rescannable_[i].u.input_group;
+	}
+
+      rescan_pos = min_rescan_pos + 1;
+    }
+}
+
+// Return whether the rescannable at index I defines SYM.
+
+bool
+Plugin_manager::rescannable_defines(size_t i, Symbol* sym)
+{
+  const Rescannable& r(this->rescannable_[i]);
+  if (r.is_archive)
+    return r.u.archive->defines_symbol(sym);
+  else
+    {
+      for (Input_group::const_iterator p = r.u.input_group->begin();
+	   p != r.u.input_group->end();
+	   ++p)
+	{
+	  if ((*p)->defines_symbol(sym))
+	    return true;
+	}
+      return false;
+    }
+}
+
 // Layout deferred objects.
 
 void
@@ -473,6 +676,7 @@ Plugin_manager::add_input_file(const cha
                                                 this->this_blocker_,
                                                 next_blocker));
   this->this_blocker_ = next_blocker;
+  this->any_added_ = true;
   return LDPS_OK;
 }
 
Index: readsyms.h
===================================================================
RCS file: /cvs/src/src/gold/readsyms.h,v
retrieving revision 1.21
diff -u -p -r1.21 readsyms.h
--- readsyms.h	22 Mar 2010 14:18:24 -0000	1.21
+++ readsyms.h	18 Jan 2011 23:19:24 -0000
@@ -191,6 +191,8 @@ class Input_group
     : archives_()
   { }
 
+  ~Input_group();
+
   // Add an archive to the group.
   void
   add_archive(Archive* arch)
Index: readsyms.cc
===================================================================
RCS file: /cvs/src/src/gold/readsyms.cc,v
retrieving revision 1.46
diff -u -p -r1.46 readsyms.cc
--- readsyms.cc	14 Dec 2010 19:03:30 -0000	1.46
+++ readsyms.cc	18 Jan 2011 23:19:24 -0000
@@ -599,6 +599,19 @@ Add_symbols::run(Workqueue*)
     }
 }
 
+// Class Input_group.
+
+// When we delete an Input_group we can delete the archive
+// information.
+
+Input_group::~Input_group()
+{
+  for (Input_group::const_iterator p = this->begin();
+       p != this->end();
+       ++p)
+    delete *p;
+}
+
 // Class Start_group.
 
 Start_group::~Start_group()
@@ -680,8 +693,8 @@ Finish_group::run(Workqueue*)
 	}
     }
 
-  // Now that we're done with the archives, record the incremental layout
-  // information, then delete them.
+  // Now that we're done with the archives, record the incremental
+  // layout information.
   for (Input_group::const_iterator p = this->input_group_->begin();
        p != this->input_group_->end();
        ++p)
@@ -691,10 +704,12 @@ Finish_group::run(Workqueue*)
           this->layout_->incremental_inputs();
       if (incremental_inputs != NULL)
 	incremental_inputs->report_archive_end(*p);
-
-      delete *p;
     }
-  delete this->input_group_;
+
+  if (parameters->options().has_plugins())
+    parameters->options().plugins()->save_input_group(this->input_group_);
+  else
+    delete this->input_group_;
 }
 
 // Class Read_script
Index: symtab.cc
===================================================================
RCS file: /cvs/src/src/gold/symtab.cc,v
retrieving revision 1.145
diff -u -p -r1.145 symtab.cc
--- symtab.cc	2 Oct 2010 09:35:19 -0000	1.145
+++ symtab.cc	18 Jan 2011 23:19:24 -0000
@@ -1002,7 +1002,11 @@ Symbol_table::add_from_object(Object* ob
   // Record every time we see a new undefined symbol, to speed up
   // archive groups.
   if (!was_undefined && ret->is_undefined())
-    ++this->saw_undefined_;
+    {
+      ++this->saw_undefined_;
+      if (parameters->options().has_plugins())
+	parameters->options().plugins()->new_undefined_symbol(ret);
+    }
 
   // Keep track of common symbols, to speed up common symbol
   // allocation.