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