gold/stringpool.cc

   1 // stringpool.cc -- a string pool for gold
   2
   3 // Copyright 2006, 2007 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 <cstring>
  26 #include <algorithm>
  27 #include <vector>
  28
  29 #include "output.h"
  30 #include "parameters.h"
  31 #include "stringpool.h"
  32
  33 namespace gold
  34 {
  35
  36 template<typename Stringpool_char>
  37 Stringpool_template<Stringpool_char>::Stringpool_template()
  38   : string_set_(), strings_(), strtab_size_(0), next_index_(1),
  39     next_uncopied_key_(-1), zero_null_(true)
  40 {
  41 }
  42
  43 template<typename Stringpool_char>
  44 Stringpool_template<Stringpool_char>::~Stringpool_template()
  45 {
  46   for (typename std::list<Stringdata*>::iterator p = this->strings_.begin();
  47        p != this->strings_.end();
  48        ++p)
  49     delete[] reinterpret_cast<char*>(*p);
  50 }
  51
  52 // Return the length of a string of arbitrary character type.
  53
  54 template<typename Stringpool_char>
  55 size_t
  56 Stringpool_template<Stringpool_char>::string_length(const Stringpool_char* p)
  57 {
  58   size_t len = 0;
  59   for (; *p != 0; ++p)
  60     ++len;
  61   return len;
  62 }
  63
  64 // Specialize string_length for char.  Maybe we could just use
  65 // std::char_traits<>::length?
  66
  67 template<>
  68 inline size_t
  69 Stringpool_template<char>::string_length(const char* p)
  70 {
  71   return strlen(p);
  72 }
  73
  74 // Equality comparison function.
  75
  76 template<typename Stringpool_char>
  77 bool
  78 Stringpool_template<Stringpool_char>::Stringpool_eq::operator()(
  79     const Stringpool_char* s1,
  80     const Stringpool_char* s2) const
  81 {
  82   while (*s1 != 0)
  83     if (*s1++ != *s2++)
  84       return false;
  85   return *s2 == 0;
  86 }
  87
  88 // Specialize equality comparison for char.
  89
  90 template<>
  91 bool
  92 Stringpool_template<char>::Stringpool_eq::operator()(const char* s1,
  93                                                      const char* s2) const
  94 {
  95   return strcmp(s1, s2) == 0;
  96 }
  97
  98 // Hash function.
  99
 100 template<typename Stringpool_char>
 101 size_t
 102 Stringpool_template<Stringpool_char>::Stringpool_hash::operator()(
 103     const Stringpool_char* s) const
 104 {
 105   // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
 106   if (sizeof(size_t) > 4)
 107     {
 108       size_t result = static_cast<size_t>(14695981039346656037ULL);
 109       while (*s != 0)
 110         {
 111           const char* p = reinterpret_cast<const char*>(s);
 112           for (size_t i = 0; i < sizeof(Stringpool_char); ++i)
 113             {
 114               result ^= (size_t) *p++;
 115               result *= 1099511628211ULL;
 116             }
 117           ++s;
 118         }
 119       return result;
 120     }
 121   else
 122     {
 123       size_t result = 2166136261UL;
 124       while (*s != 0)
 125         {
 126           const char* p = reinterpret_cast<const char*>(s);
 127           for (size_t i = 0; i < sizeof(Stringpool_char); ++i)
 128             {
 129               result ^= (size_t) *p++;
 130               result *= 16777619UL;
 131             }
 132           ++s;
 133         }
 134       return result;
 135     }
 136 }
 137
 138 // Add a string to the list of canonical strings.  Return a pointer to
 139 // the canonical string.  If PKEY is not NULL, set *PKEY to the key.
 140
 141 template<typename Stringpool_char>
 142 const Stringpool_char*
 143 Stringpool_template<Stringpool_char>::add_string(const Stringpool_char* s,
 144                                                  Key* pkey)
 145 {
 146   // We are in trouble if we've already computed the string offsets.
 147   gold_assert(this->strtab_size_ == 0);
 148
 149   // The size we allocate for a new Stringdata.
 150   const size_t buffer_size = 1000;
 151   // The amount we multiply the Stringdata index when calculating the
 152   // key.
 153   const size_t key_mult = 1024;
 154   gold_assert(key_mult >= buffer_size);
 155
 156   size_t len = (string_length(s) + 1) * sizeof(Stringpool_char);
 157
 158   size_t alc;
 159   bool front = true;
 160   if (len > buffer_size)
 161     {
 162       alc = sizeof(Stringdata) + len;
 163       front = false;
 164     }
 165   else if (this->strings_.empty())
 166     alc = sizeof(Stringdata) + buffer_size;
 167   else
 168     {
 169       Stringdata *psd = this->strings_.front();
 170       if (len > psd->alc - psd->len)
 171         alc = sizeof(Stringdata) + buffer_size;
 172       else
 173         {
 174           char* ret = psd->data + psd->len;
 175           memcpy(ret, s, len);
 176
 177           if (pkey != NULL)
 178             *pkey = psd->index * key_mult + psd->len;
 179
 180           psd->len += len;
 181
 182           return reinterpret_cast<const Stringpool_char*>(ret);
 183         }
 184     }
 185
 186   Stringdata *psd = reinterpret_cast<Stringdata*>(new char[alc]);
 187   psd->alc = alc - sizeof(Stringdata);
 188   memcpy(psd->data, s, len);
 189   psd->len = len;
 190   psd->index = this->next_index_;
 191   ++this->next_index_;
 192
 193   if (pkey != NULL)
 194     *pkey = psd->index * key_mult;
 195
 196   if (front)
 197     this->strings_.push_front(psd);
 198   else
 199     this->strings_.push_back(psd);
 200
 201   return reinterpret_cast<const Stringpool_char*>(psd->data);
 202 }
 203
 204 // Add a string to a string pool.
 205
 206 template<typename Stringpool_char>
 207 const Stringpool_char*
 208 Stringpool_template<Stringpool_char>::add(const Stringpool_char* s, bool copy,
 209                                           Key* pkey)
 210 {
 211   // FIXME: This will look up the entry twice in the hash table.  The
 212   // problem is that we can't insert S before we canonicalize it.  I
 213   // don't think there is a way to handle this correctly with
 214   // unordered_map, so this should be replaced with custom code to do
 215   // what we need, which is to return the empty slot.
 216
 217   typename String_set_type::const_iterator p = this->string_set_.find(s);
 218   if (p != this->string_set_.end())
 219     {
 220       if (pkey != NULL)
 221         *pkey = p->second.first;
 222       return p->first;
 223     }
 224
 225   Key k;
 226   const Stringpool_char* ret;
 227   if (copy)
 228     ret = this->add_string(s, &k);
 229   else
 230     {
 231       ret = s;
 232       k = this->next_uncopied_key_;
 233       --this->next_uncopied_key_;
 234     }
 235
 236   const off_t ozero = 0;
 237   std::pair<const Stringpool_char*, Val> element(ret,
 238                                                  std::make_pair(k, ozero));
 239   std::pair<typename String_set_type::iterator, bool> ins =
 240     this->string_set_.insert(element);
 241   gold_assert(ins.second);
 242
 243   if (pkey != NULL)
 244     *pkey = k;
 245
 246   return ret;
 247 }
 248
 249 // Add a prefix of a string to a string pool.
 250
 251 template<typename Stringpool_char>
 252 const Stringpool_char*
 253 Stringpool_template<Stringpool_char>::add_prefix(const Stringpool_char* s,
 254                                                  size_t len,
 255                                                  Key* pkey)
 256 {
 257   // FIXME: This implementation should be rewritten when we rewrite
 258   // the hash table to avoid copying.
 259   std::basic_string<Stringpool_char> st(s, len);
 260   return this->add(st.c_str(), true, pkey);
 261 }
 262
 263 template<typename Stringpool_char>
 264 const Stringpool_char*
 265 Stringpool_template<Stringpool_char>::find(const Stringpool_char* s,
 266                                            Key* pkey) const
 267 {
 268   typename String_set_type::const_iterator p = this->string_set_.find(s);
 269   if (p == this->string_set_.end())
 270     return NULL;
 271
 272   if (pkey != NULL)
 273     *pkey = p->second.first;
 274
 275   return p->first;
 276 }
 277
 278 // Comparison routine used when sorting into an ELF strtab.  We want
 279 // to sort this so that when one string is a suffix of another, we
 280 // always see the shorter string immediately after the longer string.
 281 // For example, we want to see these strings in this order:
 282 //   abcd
 283 //   cd
 284 //   d
 285 // When strings are not suffixes, we don't care what order they are
 286 // in, but we need to ensure that suffixes wind up next to each other.
 287 // So we do a reversed lexicographic sort on the reversed string.
 288
 289 template<typename Stringpool_char>
 290 bool
 291 Stringpool_template<Stringpool_char>::Stringpool_sort_comparison::operator()(
 292   const Stringpool_sort_info& sort_info1,
 293   const Stringpool_sort_info& sort_info2) const
 294 {
 295   const Stringpool_char* s1 = sort_info1.it->first;
 296   const Stringpool_char* s2 = sort_info2.it->first;
 297   const size_t len1 = sort_info1.string_length;
 298   const size_t len2 = sort_info2.string_length;
 299   const size_t minlen = len1 < len2 ? len1 : len2;
 300   const Stringpool_char* p1 = s1 + len1 - 1;
 301   const Stringpool_char* p2 = s2 + len2 - 1;
 302   for (size_t i = minlen; i > 0; --i, --p1, --p2)
 303     {
 304       if (*p1 != *p2)
 305         return *p1 > *p2;
 306     }
 307   return len1 > len2;
 308 }
 309
 310 // Return whether s1 is a suffix of s2.
 311
 312 template<typename Stringpool_char>
 313 bool
 314 Stringpool_template<Stringpool_char>::is_suffix(const Stringpool_char* s1,
 315                                                 size_t len1,
 316                                                 const Stringpool_char* s2,
 317                                                 size_t len2)
 318 {
 319   if (len1 > len2)
 320     return false;
 321   return memcmp(s1, s2 + len2 - len1, len1 * sizeof(Stringpool_char)) == 0;
 322 }
 323
 324 // Turn the stringpool into an ELF strtab: determine the offsets of
 325 // each string in the table.
 326
 327 template<typename Stringpool_char>
 328 void
 329 Stringpool_template<Stringpool_char>::set_string_offsets()
 330 {
 331   if (this->strtab_size_ != 0)
 332     {
 333       // We've already computed the offsets.
 334       return;
 335     }
 336
 337   const size_t charsize = sizeof(Stringpool_char);
 338
 339   // Offset 0 may be reserved for the empty string.
 340   off_t offset = this->zero_null_ ? charsize : 0;
 341
 342   // Sorting to find suffixes can take over 25% of the total CPU time
 343   // used by the linker.  Since it's merely an optimization to reduce
 344   // the strtab size, and gives a relatively small benefit (it's
 345   // typically rare for a symbol to be a suffix of another), we only
 346   // take the time to sort when the user asks for heavy optimization.
 347   if (parameters->optimization_level() < 2)
 348     {
 349       for (typename String_set_type::iterator curr = this->string_set_.begin();
 350            curr != this->string_set_.end();
 351            curr++)
 352         {
 353           if (this->zero_null_ && curr->first[0] == 0)
 354             curr->second.second = 0;
 355           else
 356             {
 357               curr->second.second = offset;
 358               offset += (string_length(curr->first) + 1) * charsize;
 359             }
 360         }
 361     }
 362   else
 363     {
 364       size_t count = this->string_set_.size();
 365
 366       std::vector<Stringpool_sort_info> v;
 367       v.reserve(count);
 368
 369       for (typename String_set_type::iterator p = this->string_set_.begin();
 370            p != this->string_set_.end();
 371            ++p)
 372         v.push_back(Stringpool_sort_info(p, string_length(p->first)));
 373
 374       std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
 375
 376       for (typename std::vector<Stringpool_sort_info>::iterator last = v.end(),
 377              curr = v.begin();
 378            curr != v.end();
 379            last = curr++)
 380         {
 381           if (this->zero_null_ && curr->it->first[0] == 0)
 382             curr->it->second.second = 0;
 383           else if (last != v.end()
 384                    && is_suffix(curr->it->first, curr->string_length,
 385                                 last->it->first, last->string_length))
 386             curr->it->second.second = (last->it->second.second
 387                                        + ((last->string_length
 388                                            - curr->string_length)
 389                                           * charsize));
 390           else
 391             {
 392               curr->it->second.second = offset;
 393               offset += (curr->string_length + 1) * charsize;
 394             }
 395         }
 396     }
 397
 398   this->strtab_size_ = offset;
 399 }
 400
 401 // Get the offset of a string in the ELF strtab.  The string must
 402 // exist.
 403
 404 template<typename Stringpool_char>
 405 off_t
 406 Stringpool_template<Stringpool_char>::get_offset(const Stringpool_char* s)
 407   const
 408 {
 409   gold_assert(this->strtab_size_ != 0);
 410   typename String_set_type::const_iterator p = this->string_set_.find(s);
 411   if (p != this->string_set_.end())
 412     return p->second.second;
 413   gold_unreachable();
 414 }
 415
 416 // Write the ELF strtab into the output file at the specified offset.
 417
 418 template<typename Stringpool_char>
 419 void
 420 Stringpool_template<Stringpool_char>::write(Output_file* of, off_t offset)
 421 {
 422   gold_assert(this->strtab_size_ != 0);
 423   unsigned char* viewu = of->get_output_view(offset, this->strtab_size_);
 424   char* view = reinterpret_cast<char*>(viewu);
 425   if (this->zero_null_)
 426     view[0] = '\0';
 427   for (typename String_set_type::const_iterator p = this->string_set_.begin();
 428        p != this->string_set_.end();
 429        ++p)
 430     memcpy(view + p->second.second, p->first,
 431            (string_length(p->first) + 1) * sizeof(Stringpool_char));
 432   of->write_output_view(offset, this->strtab_size_, viewu);
 433 }
 434
 435 // Instantiate the templates we need.
 436
 437 template
 438 class Stringpool_template<char>;
 439
 440 template
 441 class Stringpool_template<uint16_t>;
 442
 443 template
 444 class Stringpool_template<uint32_t>;
 445
 446 } // End namespace gold.