[PATCH] Loosen the Gold ODR checker to only compare filenames

[PATCH] Loosen the Gold ODR checker to only compare filenames

[Jeffrey Yasskin]

[-- Attachment #1: Type: text/plain, Size: 1178 bytes --]

Code compiled with different flags, especially -O, may have a
different line number for the first instruction in a function. This
produces false positives in the ODR checker when linking object files
that should be ABI-compatible.

The best fixes would be to A) look at the DW_AT_decl_line of the
DW_TAG_subprogram for the function, but this would require gold to
parse a whole new debug section, or B) hash the ODR-relevant aspects
of each function into a new dwarf attribute, but this would require
gcc to produce the hash and gold to parse a whole new debug section.

Instead, loosening the ODR check to allow a function's definitions to
be from anywhere within the same file removes the false positives with
much less work, and would have caused very few extra false negatives
in Google's codebase.

2011-02-02  Jeffrey Yasskin  <jyasskin@google.com>

       * dwarf_reader.h: Add a Source_location type, and change the
addr2line functions to return it.
       * dwarf_reader.cc: Implement Source_location, and change the
addr2line functions to return it.
       * symtab.cc: Sort by just the filename.
       * object.cc: Convert a Source_location return to a std::string.

[-- Attachment #2: looser_odr_check.patch --]
[-- Type: application/octet-stream, Size: 10582 bytes --]

Index: gold/dwarf_reader.cc
===================================================================
RCS file: /cvs/src/src/gold/dwarf_reader.cc,v
retrieving revision 1.31
diff -u -r1.31 dwarf_reader.cc
--- gold/dwarf_reader.cc	20 Dec 2010 18:37:36 -0000	1.31
+++ gold/dwarf_reader.cc	3 Feb 2011 06:15:20 -0000
@@ -61,6 +61,29 @@
   lsm->end_sequence = false;
 }
 
+std::string
+Source_location::str() const
+{
+  std::string ret;
+  if (this->filename == NULL)
+    return ret;  // "", but in a way that the NRVO still works.
+  if (this->dirname != NULL && !this->dirname->empty())
+    {
+      ret += *this->dirname;
+      ret += '/';
+    }
+  ret += *this->filename;
+  if (ret.empty())
+    ret = "(unknown)";
+
+  char buffer[64];   // enough to hold a line number
+  snprintf(buffer, sizeof(buffer), "%d", this->line_num);
+  ret += ':';
+  ret += buffer;
+
+  return ret;
+}
+
 template<int size, bool big_endian>
 Sized_dwarf_line_info<size, big_endian>::Sized_dwarf_line_info(Object* object,
                                                                unsigned int read_shndx)
@@ -717,15 +740,15 @@
   return offsets->end();
 }
 
-// Return a string for a file name and line number.
+// Return a Source_location for an offset.
 
 template<int size, bool big_endian>
-std::string
+Source_location
 Sized_dwarf_line_info<size, big_endian>::do_addr2line(unsigned int shndx,
                                                       off_t offset)
 {
   if (this->data_valid_ == false)
-    return "";
+    return Source_location();
 
   const std::vector<Offset_to_lineno_entry>* offsets;
   // If we do not have reloc information, then our input is a .so or
@@ -736,16 +759,14 @@
   else
     offsets = &this->line_number_map_[-1U];
   if (offsets->empty())
-    return "";
+    return Source_location();
 
   typename std::vector<Offset_to_lineno_entry>::const_iterator it
       = offset_to_iterator(offsets, offset);
   if (it == offsets->end())
-    return "";
-
-  // Convert the file_num + line_num into a string.
-  std::string ret;
+    return Source_location();
 
+  // Convert the file_num into a directory and file name.
   gold_assert(it->header_num < static_cast<int>(this->files_.size()));
   gold_assert(it->file_num
 	      < static_cast<int>(this->files_[it->header_num].size()));
@@ -759,21 +780,7 @@
   const std::string& dirname
       = this->directories_[it->header_num][filename_pair.first];
 
-  if (!dirname.empty())
-    {
-      ret += dirname;
-      ret += "/";
-    }
-  ret += filename;
-  if (ret.empty())
-    ret = "(unknown)";
-
-  char buffer[64];   // enough to hold a line number
-  snprintf(buffer, sizeof(buffer), "%d", it->line_num);
-  ret += ":";
-  ret += buffer;
-
-  return ret;
+  return Source_location(&dirname, &filename, it->line_num);
 }
 
 // Dwarf_line_info routines.
@@ -800,7 +807,7 @@
 // or priority queue or anything: just use a simple vector.
 static std::vector<Addr2line_cache_entry> addr2line_cache;
 
-std::string
+Source_location
 Dwarf_line_info::one_addr2line(Object* object,
                                unsigned int shndx, off_t offset,
                                size_t cache_size)
@@ -854,7 +861,7 @@
   }
 
   // Now that we have our object, figure out the answer
-  std::string retval = lineinfo->addr2line(shndx, offset);
+  Source_location retval = lineinfo->addr2line(shndx, offset);
 
   // Finally, if our cache has grown too big, delete old objects.  We
   // assume the common (probably only) case is deleting only one object.
Index: gold/dwarf_reader.h
===================================================================
RCS file: /cvs/src/src/gold/dwarf_reader.h,v
retrieving revision 1.19
diff -u -r1.19 dwarf_reader.h
--- gold/dwarf_reader.h	20 Dec 2010 18:37:36 -0000	1.19
+++ gold/dwarf_reader.h	3 Feb 2011 06:15:20 -0000
@@ -54,6 +54,32 @@
   { return this->offset < that.offset; }
 };
 
+// Stores a triple of directory, file, and line number and can format
+// these to a string.
+struct Source_location
+{
+  const std::string* dirname;
+  const std::string* filename;
+  int line_num;
+
+  Source_location()
+      : dirname(NULL), filename(NULL), line_num(0)
+  {}
+
+  Source_location(const std::string* dirname,
+                  const std::string* filename,
+                  int line_num)
+      : dirname(dirname), filename(filename), line_num(line_num)
+  {}
+
+  bool
+  empty() const
+  { return this->filename == NULL; }
+
+  std::string
+  str() const;
+};
+
 // This class is used to read the line information from the debugging
 // section of an object file.
 
@@ -71,7 +97,7 @@
   // file and line-number, as a string: "file:lineno".  If unable
   // to do the mapping, returns the empty string.  You must call
   // read_line_mappings() before calling this function.
-  std::string
+  Source_location
   addr2line(unsigned int shndx, off_t offset)
   { return do_addr2line(shndx, offset); }
 
@@ -81,7 +107,7 @@
   // chance this routine won't have to re-create a Dwarf_line_info
   // object for its addr2line computation; such creations are slow.
   // NOTE: Not thread-safe, so only call from one thread at a time.
-  static std::string
+  static Source_location
   one_addr2line(Object* object, unsigned int shndx, off_t offset,
                 size_t cache_size);
 
@@ -91,7 +117,7 @@
   clear_addr2line_cache();
 
  private:
-  virtual std::string
+  virtual Source_location
   do_addr2line(unsigned int shndx, off_t offset) = 0;
 };
 
@@ -105,7 +131,7 @@
   Sized_dwarf_line_info(Object* object, unsigned int read_shndx = -1U);
 
  private:
-  std::string
+  virtual Source_location
   do_addr2line(unsigned int shndx, off_t offset);
 
   // Start processing line info, and populates the offset_map_.
@@ -191,8 +217,10 @@
   // Holds the directories and files as we see them.  We have an array
   // of directory-lists, one for each .o file we're reading (usually
   // there will just be one, but there may be more if input is a .so).
+  // This never changes after construction.
   std::vector<std::vector<std::string> > directories_;
   // The first part is an index into directories_, the second the filename.
+  // This never changes after construction.
   std::vector<std::vector< std::pair<int, std::string> > > files_;
 
   // An index into the current directories_ and files_ vectors.
Index: gold/object.cc
===================================================================
RCS file: /cvs/src/src/gold/object.cc,v
retrieving revision 1.134
diff -u -r1.134 object.cc
--- gold/object.cc	14 Dec 2010 19:03:30 -0000	1.134
+++ gold/object.cc	3 Feb 2011 06:15:20 -0000
@@ -2582,7 +2582,7 @@
 
   Sized_dwarf_line_info<size, big_endian> line_info(this->object);
   // This will be "" if we failed to parse the debug info for any reason.
-  file_and_lineno = line_info.addr2line(this->data_shndx, offset);
+  file_and_lineno = line_info.addr2line(this->data_shndx, offset).str();
 
   std::string ret(this->object->name());
   ret += ':';
Index: gold/symtab.cc
===================================================================
RCS file: /cvs/src/src/gold/symtab.cc,v
retrieving revision 1.146
diff -u -r1.146 symtab.cc
--- gold/symtab.cc	24 Jan 2011 21:48:40 -0000	1.146
+++ gold/symtab.cc	3 Feb 2011 06:15:20 -0000
@@ -3012,11 +3012,12 @@
 // We check for ODR violations by looking for symbols with the same
 // name for which the debugging information reports that they were
 // defined in different source locations.  When comparing the source
-// location, we consider instances with the same base filename and
-// line number to be the same.  This is because different object
-// files/shared libraries can include the same header file using
-// different paths, and we don't want to report an ODR violation in
-// that case.
+// location, we consider instances with the same base filename to be
+// the same.  This is because different object files/shared libraries
+// can include the same header file using different paths, and
+// different optimization settings can make the line number appear to
+// be a couple lines off, and we don't want to report an ODR violation
+// in those cases.
 
 // This struct is used to compare line information, as returned by
 // Dwarf_line_info::one_addr2line.  It implements a < comparison
@@ -3025,15 +3026,11 @@
 struct Odr_violation_compare
 {
   bool
-  operator()(const std::string& s1, const std::string& s2) const
+  operator()(const Source_location& s1, const Source_location& s2) const
   {
-    std::string::size_type pos1 = s1.rfind('/');
-    std::string::size_type pos2 = s2.rfind('/');
-    if (pos1 == std::string::npos
-	|| pos2 == std::string::npos)
-      return s1 < s2;
-    return s1.compare(pos1, std::string::npos,
-		      s2, pos2, std::string::npos) < 0;
+    if (s1.filename == NULL || s2.filename == NULL)
+      return s1.filename == NULL && s2.filename != NULL;
+    return *s1.filename < *s2.filename;
   }
 };
 
@@ -3053,7 +3050,7 @@
       // that location in.  We use a sorted map so the location order
       // is deterministic, but we only store an arbitrary object file
       // to avoid copying lots of names.
-      std::map<std::string, std::string, Odr_violation_compare> line_nums;
+      std::map<Source_location, std::string, Odr_violation_compare> line_nums;
 
       for (Unordered_set<Symbol_location, Symbol_location_hash>::const_iterator
                locs = it->second.begin();
@@ -3069,7 +3066,7 @@
           // currently thread-safe.
 	  Task_lock_obj<Object> tl(task, locs->object);
           // 16 is the size of the object-cache that one_addr2line should use.
-          std::string lineno = Dwarf_line_info::one_addr2line(
+          Source_location lineno = Dwarf_line_info::one_addr2line(
               locs->object, locs->shndx, locs->offset, 16);
           if (!lineno.empty())
             {
@@ -3084,12 +3081,12 @@
           gold_warning(_("while linking %s: symbol '%s' defined in multiple "
                          "places (possible ODR violation):"),
                        output_file_name, demangle(symbol_name).c_str());
-          for (std::map<std::string, std::string>::const_iterator it2 =
+          for (std::map<Source_location, std::string>::const_iterator it2 =
 		 line_nums.begin();
 	       it2 != line_nums.end();
 	       ++it2)
             fprintf(stderr, _("  %s from %s\n"),
-                    it2->first.c_str(), it2->second.c_str());
+                    it2->first.str().c_str(), it2->second.c_str());
         }
     }
   // We only call one_addr2line() in this function, so we can clear its cache.

Re: [PATCH] Loosen the Gold ODR checker to only compare filenames

[Jeffrey Yasskin]

Whoops, please don't submit this. The strings that Source_location
points at don't live long enough to use them in the way I'm using
them. I'll send a working patch shortly.

On Wed, Feb 2, 2011 at 10:44 PM, Jeffrey Yasskin <jyasskin@google.com> wrote:
> Code compiled with different flags, especially -O, may have a
> different line number for the first instruction in a function. This
> produces false positives in the ODR checker when linking object files
> that should be ABI-compatible.
>
> The best fixes would be to A) look at the DW_AT_decl_line of the
> DW_TAG_subprogram for the function, but this would require gold to
> parse a whole new debug section, or B) hash the ODR-relevant aspects
> of each function into a new dwarf attribute, but this would require
> gcc to produce the hash and gold to parse a whole new debug section.
>
> Instead, loosening the ODR check to allow a function's definitions to
> be from anywhere within the same file removes the false positives with
> much less work, and would have caused very few extra false negatives
> in Google's codebase.
>
> 2011-02-02  Jeffrey Yasskin  <jyasskin@google.com>
>
>       * dwarf_reader.h: Add a Source_location type, and change the
> addr2line functions to return it.
>       * dwarf_reader.cc: Implement Source_location, and change the
> addr2line functions to return it.
>       * symtab.cc: Sort by just the filename.
>       * object.cc: Convert a Source_location return to a std::string.
>

Re: [PATCH] Loosen the Gold ODR checker to only compare filenames

[Jeffrey Yasskin]

[-- Attachment #1: Type: text/plain, Size: 2043 bytes --]

This patch should do a better job. I went back to the
substring-comparison the original code used, and chopped off the line
number in addition to the directory. The code to remove the directory
is different because the original code wasn't a transitive relation:
it reported that "c:1" < "d/a:1" < "a/b:1" < "c:1".

2011-02-03  Jeffrey Yasskin  <jyasskin@google.com>

      * symtab.cc: Sort by just the filename.

On Thu, Feb 3, 2011 at 2:10 PM, Jeffrey Yasskin <jyasskin@google.com> wrote:
> Whoops, please don't submit this. The strings that Source_location
> points at don't live long enough to use them in the way I'm using
> them. I'll send a working patch shortly.
>
> On Wed, Feb 2, 2011 at 10:44 PM, Jeffrey Yasskin <jyasskin@google.com> wrote:
>> Code compiled with different flags, especially -O, may have a
>> different line number for the first instruction in a function. This
>> produces false positives in the ODR checker when linking object files
>> that should be ABI-compatible.
>>
>> The best fixes would be to A) look at the DW_AT_decl_line of the
>> DW_TAG_subprogram for the function, but this would require gold to
>> parse a whole new debug section, or B) hash the ODR-relevant aspects
>> of each function into a new dwarf attribute, but this would require
>> gcc to produce the hash and gold to parse a whole new debug section.
>>
>> Instead, loosening the ODR check to allow a function's definitions to
>> be from anywhere within the same file removes the false positives with
>> much less work, and would have caused very few extra false negatives
>> in Google's codebase.
>>
>> 2011-02-02  Jeffrey Yasskin  <jyasskin@google.com>
>>
>>       * dwarf_reader.h: Add a Source_location type, and change the
>> addr2line functions to return it.
>>       * dwarf_reader.cc: Implement Source_location, and change the
>> addr2line functions to return it.
>>       * symtab.cc: Sort by just the filename.
>>       * object.cc: Convert a Source_location return to a std::string.
>>
>

[-- Attachment #2: looser_odr_check.patch --]
[-- Type: text/x-patch, Size: 2716 bytes --]

Index: gold/symtab.cc
===================================================================
RCS file: /cvs/src/src/gold/symtab.cc,v
retrieving revision 1.146
diff -u -r1.146 symtab.cc
--- gold/symtab.cc	24 Jan 2011 21:48:40 -0000	1.146
+++ gold/symtab.cc	3 Feb 2011 22:37:54 -0000
@@ -3012,11 +3012,12 @@
 // We check for ODR violations by looking for symbols with the same
 // name for which the debugging information reports that they were
 // defined in different source locations.  When comparing the source
-// location, we consider instances with the same base filename and
-// line number to be the same.  This is because different object
-// files/shared libraries can include the same header file using
-// different paths, and we don't want to report an ODR violation in
-// that case.
+// location, we consider instances with the same base filename to be
+// the same.  This is because different object files/shared libraries
+// can include the same header file using different paths, and
+// different optimization settings can make the line number appear to
+// be a couple lines off, and we don't want to report an ODR violation
+// in those cases.
 
 // This struct is used to compare line information, as returned by
 // Dwarf_line_info::one_addr2line.  It implements a < comparison
@@ -3027,13 +3028,29 @@
   bool
   operator()(const std::string& s1, const std::string& s2) const
   {
-    std::string::size_type pos1 = s1.rfind('/');
-    std::string::size_type pos2 = s2.rfind('/');
-    if (pos1 == std::string::npos
-	|| pos2 == std::string::npos)
-      return s1 < s2;
-    return s1.compare(pos1, std::string::npos,
-		      s2, pos2, std::string::npos) < 0;
+    // Inputs should be of the form "dirname/filename:linenum" where
+    // "dirname/" is optional.  We want to compare just the filename.
+
+    // Find the last '/' and ':' in each string.
+    std::string::size_type s1begin = s1.rfind('/');
+    std::string::size_type s2begin = s2.rfind('/');
+    std::string::size_type s1end = s1.rfind(':');
+    std::string::size_type s2end = s2.rfind(':');
+    // If there was no '/' in a string, start at the beginning.
+    if (s1begin == std::string::npos)
+      s1begin = 0;
+    if (s2begin == std::string::npos)
+      s2begin = 0;
+    // If the ':' appeared in the directory name, compare to the end
+    // of the string.
+    if (s1end < s1begin)
+      s1end = std::string::npos;
+    if (s2end < s2begin)
+      s2end = std::string::npos;
+    // Compare takes lengths, not end indices.  Passing slightly less
+    // than npos will still extend to the end of the string.
+    return s1.compare(s1begin, s1end - s1begin,
+		      s2, s2begin, s2end - s2begin) < 0;
   }
 };
 

Re: [PATCH] Loosen the Gold ODR checker to only compare filenames

[Jeffrey Yasskin]

[-- Attachment #1: Type: text/plain, Size: 2230 bytes --]

Here's a tweaked version in response to Ian's review.

On Thu, Feb 3, 2011 at 3:09 PM, Jeffrey Yasskin <jyasskin@google.com> wrote:
> This patch should do a better job. I went back to the
> substring-comparison the original code used, and chopped off the line
> number in addition to the directory. The code to remove the directory
> is different because the original code wasn't a transitive relation:
> it reported that "c:1" < "d/a:1" < "a/b:1" < "c:1".
>
> 2011-02-03  Jeffrey Yasskin  <jyasskin@google.com>
>
>      * symtab.cc: Sort by just the filename.
>
> On Thu, Feb 3, 2011 at 2:10 PM, Jeffrey Yasskin <jyasskin@google.com> wrote:
>> Whoops, please don't submit this. The strings that Source_location
>> points at don't live long enough to use them in the way I'm using
>> them. I'll send a working patch shortly.
>>
>> On Wed, Feb 2, 2011 at 10:44 PM, Jeffrey Yasskin <jyasskin@google.com> wrote:
>>> Code compiled with different flags, especially -O, may have a
>>> different line number for the first instruction in a function. This
>>> produces false positives in the ODR checker when linking object files
>>> that should be ABI-compatible.
>>>
>>> The best fixes would be to A) look at the DW_AT_decl_line of the
>>> DW_TAG_subprogram for the function, but this would require gold to
>>> parse a whole new debug section, or B) hash the ODR-relevant aspects
>>> of each function into a new dwarf attribute, but this would require
>>> gcc to produce the hash and gold to parse a whole new debug section.
>>>
>>> Instead, loosening the ODR check to allow a function's definitions to
>>> be from anywhere within the same file removes the false positives with
>>> much less work, and would have caused very few extra false negatives
>>> in Google's codebase.
>>>
>>> 2011-02-02  Jeffrey Yasskin  <jyasskin@google.com>
>>>
>>>       * dwarf_reader.h: Add a Source_location type, and change the
>>> addr2line functions to return it.
>>>       * dwarf_reader.cc: Implement Source_location, and change the
>>> addr2line functions to return it.
>>>       * symtab.cc: Sort by just the filename.
>>>       * object.cc: Convert a Source_location return to a std::string.
>>>
>>
>

[-- Attachment #2: looser_odr_check.patch --]
[-- Type: text/x-patch, Size: 2615 bytes --]

Index: gold/symtab.cc
===================================================================
RCS file: /cvs/src/src/gold/symtab.cc,v
retrieving revision 1.146
diff -u -r1.146 symtab.cc
--- gold/symtab.cc	24 Jan 2011 21:48:40 -0000	1.146
+++ gold/symtab.cc	4 Feb 2011 19:19:49 -0000
@@ -3012,11 +3012,12 @@
 // We check for ODR violations by looking for symbols with the same
 // name for which the debugging information reports that they were
 // defined in different source locations.  When comparing the source
-// location, we consider instances with the same base filename and
-// line number to be the same.  This is because different object
-// files/shared libraries can include the same header file using
-// different paths, and we don't want to report an ODR violation in
-// that case.
+// location, we consider instances with the same base filename to be
+// the same.  This is because different object files/shared libraries
+// can include the same header file using different paths, and
+// different optimization settings can make the line number appear to
+// be a couple lines off, and we don't want to report an ODR violation
+// in those cases.
 
 // This struct is used to compare line information, as returned by
 // Dwarf_line_info::one_addr2line.  It implements a < comparison
@@ -3027,13 +3028,28 @@
   bool
   operator()(const std::string& s1, const std::string& s2) const
   {
-    std::string::size_type pos1 = s1.rfind('/');
-    std::string::size_type pos2 = s2.rfind('/');
-    if (pos1 == std::string::npos
-	|| pos2 == std::string::npos)
-      return s1 < s2;
-    return s1.compare(pos1, std::string::npos,
-		      s2, pos2, std::string::npos) < 0;
+    // Inputs should be of the form "dirname/filename:linenum" where
+    // "dirname/" is optional.  We want to compare just the filename.
+
+    // Find the last '/' and ':' in each string.
+    std::string::size_type s1begin = s1.rfind('/');
+    std::string::size_type s2begin = s2.rfind('/');
+    std::string::size_type s1end = s1.rfind(':');
+    std::string::size_type s2end = s2.rfind(':');
+    // If there was no '/' in a string, start at the beginning.
+    if (s1begin == std::string::npos)
+      s1begin = 0;
+    if (s2begin == std::string::npos)
+      s2begin = 0;
+    // If the ':' appeared in the directory name, compare to the end
+    // of the string.
+    if (s1end < s1begin)
+      s1end = s1.size();
+    if (s2end < s2begin)
+      s2end = s2.size();
+    // Compare takes lengths, not end indices.
+    return s1.compare(s1begin, s1end - s1begin,
+		      s2, s2begin, s2end - s2begin) < 0;
   }
 };
 

Re: [PATCH] Loosen the Gold ODR checker to only compare filenames

[Ian Lance Taylor]

Jeffrey Yasskin <jyasskin@google.com> writes:

> Here's a tweaked version in response to Ian's review.

>>>> 2011-02-02  Jeffrey Yasskin  <jyasskin@google.com>
>>>>
>>>>       * dwarf_reader.h: Add a Source_location type, and change the
>>>> addr2line functions to return it.
>>>>       * dwarf_reader.cc: Implement Source_location, and change the
>>>> addr2line functions to return it.
>>>>       * symtab.cc: Sort by just the filename.
>>>>       * object.cc: Convert a Source_location return to a std::string.

This is OK.

Thanks.

Ian

Re: [PATCH] Loosen the Gold ODR checker to only compare filenames

[Ian Lance Taylor]

Jeffrey Yasskin <jyasskin@google.com> writes:

>>>> 2011-02-02  Jeffrey Yasskin  <jyasskin@google.com>
>>>>
>>>>       * dwarf_reader.h: Add a Source_location type, and change the
>>>> addr2line functions to return it.
>>>>       * dwarf_reader.cc: Implement Source_location, and change the
>>>> addr2line functions to return it.
>>>>       * symtab.cc: Sort by just the filename.
>>>>       * object.cc: Convert a Source_location return to a std::string.


Committed to mainline and binutils 2.21 branch with this ChangeLog
entry.

Ian

2011-02-04  Jeffrey Yasskin  <jyasskin@google.com>

	* symtab.cc (Odr_violation_compare::operator()): Sort by just the
	filename.