[patch][gold] Change how we compute merge mapping for strings

[patch][gold] Change how we compute merge mapping for strings

[Rafael Espíndola]

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

Currently we first record the offset and hash of each string. We then
walk that computing the size from the difference in the offsets.

This doesn't work if not every string is kept, which is what I am
trying to do (gc unused parts of SHF_MERGE sections).

With the attached patch we first add a mapping that is missing the
output offset and once the strings are merged we just set the output
offset.

Cheers,
Rafael

2015-05-20  Rafael Ávila de Espíndola <rafael.espindola@gmail.com>

* merge.cc (do_add_input_section): Create mappings with no output
offset.
(finalize_merged_data): Set the output offsets.
* merge.h (Merged_string): Delete.

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

diff --git a/gold/merge.cc b/gold/merge.cc
index d395312..fa70698 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -509,6 +509,9 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
   uintptr_t init_align_modulo = (reinterpret_cast<uintptr_t>(pdata)
 				 & (this->addralign() - 1));
   bool has_misaligned_strings = false;
+  Object_merge_map* merge_map = object->get_or_create_merge_map();
+  Object_merge_map::Input_merge_map* input_merge_map =
+    merge_map->get_or_make_input_merge_map(this, shndx);
 
   while (p < pend)
     {
@@ -523,15 +526,15 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
       Stringpool::Key key;
       this->stringpool_.add_with_length(p, len, true, &key);
 
-      merged_strings.push_back(Merged_string(i, key));
+      merged_strings.push_back(key);
+      // We will compute the output offset afterwards
+      size_t size = (len + 1) * sizeof(Char_type);
+      input_merge_map->add_mapping(i, size, 0);
+
       p += len + 1;
-      i += (len + 1) * sizeof(Char_type);
+      i += size;
     }
 
-  // Record the last offset in the input section so that we can
-  // compute the length of the last string.
-  merged_strings.push_back(Merged_string(i, 0));
-
   this->input_count_ += count;
   this->input_size_ += i;
 
@@ -565,28 +568,26 @@ Output_merge_string<Char_type>::finalize_merged_data()
        l != this->merged_strings_lists_.end();
        ++l)
     {
-      section_offset_type last_input_offset = 0;
-      section_offset_type last_output_offset = 0;
-      Relobj *object = (*l)->object;
+      const Merged_strings_list *ms = *l;
+      Relobj *object = ms->object;
       Object_merge_map* merge_map = object->get_or_create_merge_map();
       Object_merge_map::Input_merge_map* input_merge_map =
-        merge_map->get_or_make_input_merge_map(this, (*l)->shndx);
+        merge_map->get_or_make_input_merge_map(this, ms->shndx);
+      gold_assert(input_merge_map->sorted);
+      Object_merge_map::Input_merge_map::Entries &entries =
+        input_merge_map->entries;
+      Object_merge_map::Input_merge_map::Entries::iterator entry_i =
+        entries.begin();
 
       for (typename Merged_strings::const_iterator p =
-	     (*l)->merged_strings.begin();
-	   p != (*l)->merged_strings.end();
-	   ++p)
+	     ms->merged_strings.begin(),
+	     e = ms->merged_strings.end();
+	   p != e;
+	   ++p, ++entry_i)
 	{
-	  section_size_type length = p->offset - last_input_offset;
-	  if (length > 0)
-	    input_merge_map->add_mapping(last_input_offset, length,
-                                         last_output_offset);
-	  last_input_offset = p->offset;
-	  if (p->stringpool_key != 0)
-	    last_output_offset =
-	        this->stringpool_.get_offset_from_key(p->stringpool_key);
+          entry_i->output_offset = this->stringpool_.get_offset_from_key(*p);
 	}
-      delete *l;
+      delete ms;
     }
 
   // Save some memory.  This also ensures that this function will work
diff --git a/gold/merge.h b/gold/merge.h
index 54caed8..b956ee6 100644
--- a/gold/merge.h
+++ b/gold/merge.h
@@ -476,21 +476,7 @@ class Output_merge_string : public Output_merge_base
   const char*
   string_name();
 
-  // As we see input sections, we build a mapping from object, section
-  // index and offset to strings.
-  struct Merged_string
-  {
-    // The offset in the input section.
-    section_offset_type offset;
-    // The key in the Stringpool.
-    Stringpool::Key stringpool_key;
-
-    Merged_string(section_offset_type offseta, Stringpool::Key stringpool_keya)
-      : offset(offseta), stringpool_key(stringpool_keya)
-    { }
-  };
-
-  typedef std::vector<Merged_string> Merged_strings;
+  typedef std::vector<Stringpool::Key> Merged_strings;
 
   struct Merged_strings_list
   {

Re: [patch][gold] Change how we compute merge mapping for strings

[Rafael Espíndola]

Now with the correct email address. Sorry about that.

On 20 May 2015 at 11:12, Rafael Espíndola <rafael.espindola@gmail.com> wrote:
> Currently we first record the offset and hash of each string. We then
> walk that computing the size from the difference in the offsets.
>
> This doesn't work if not every string is kept, which is what I am
> trying to do (gc unused parts of SHF_MERGE sections).
>
> With the attached patch we first add a mapping that is missing the
> output offset and once the strings are merged we just set the output
> offset.
>
> Cheers,
> Rafael
>
> 2015-05-20  Rafael Ávila de Espíndola <rafael.espindola@gmail.com>
>
> * merge.cc (do_add_input_section): Create mappings with no output
> offset.
> (finalize_merged_data): Set the output offsets.
> * merge.h (Merged_string): Delete.

Re: [patch][gold] Change how we compute merge mapping for strings

[Rafael Espíndola]

ping

On 20 May 2015 at 11:13, Rafael Espíndola <rafael.espindola@gmail.com> wrote:
> Now with the correct email address. Sorry about that.
>
> On 20 May 2015 at 11:12, Rafael Espíndola <rafael.espindola@gmail.com> wrote:
>> Currently we first record the offset and hash of each string. We then
>> walk that computing the size from the difference in the offsets.
>>
>> This doesn't work if not every string is kept, which is what I am
>> trying to do (gc unused parts of SHF_MERGE sections).
>>
>> With the attached patch we first add a mapping that is missing the
>> output offset and once the strings are merged we just set the output
>> offset.
>>
>> Cheers,
>> Rafael
>>
>> 2015-05-20  Rafael Ávila de Espíndola <rafael.espindola@gmail.com>
>>
>> * merge.cc (do_add_input_section): Create mappings with no output
>> offset.
>> (finalize_merged_data): Set the output offsets.
>> * merge.h (Merged_string): Delete.

Re: [patch][gold] Change how we compute merge mapping for strings

[Rafael Espíndola]

ping

On 27 May 2015 at 11:27, Rafael Espíndola <rafael.espindola@gmail.com> wrote:
> ping
>
> On 20 May 2015 at 11:13, Rafael Espíndola <rafael.espindola@gmail.com> wrote:
>> Now with the correct email address. Sorry about that.
>>
>> On 20 May 2015 at 11:12, Rafael Espíndola <rafael.espindola@gmail.com> wrote:
>>> Currently we first record the offset and hash of each string. We then
>>> walk that computing the size from the difference in the offsets.
>>>
>>> This doesn't work if not every string is kept, which is what I am
>>> trying to do (gc unused parts of SHF_MERGE sections).
>>>
>>> With the attached patch we first add a mapping that is missing the
>>> output offset and once the strings are merged we just set the output
>>> offset.
>>>
>>> Cheers,
>>> Rafael
>>>
>>> 2015-05-20  Rafael Ávila de Espíndola <rafael.espindola@gmail.com>
>>>
>>> * merge.cc (do_add_input_section): Create mappings with no output
>>> offset.
>>> (finalize_merged_data): Set the output offsets.
>>> * merge.h (Merged_string): Delete.