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     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) == 8)
 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, Key* pkey)
 209 {
 210   // FIXME: This will look up the entry twice in the hash table.  The
 211   // problem is that we can't insert S before we canonicalize it.  I
 212   // don't think there is a way to handle this correctly with
 213   // unordered_map, so this should be replaced with custom code to do
 214   // what we need, which is to return the empty slot.
 215
 216   typename String_set_type::const_iterator p = this->string_set_.find(s);
 217   if (p != this->string_set_.end())
 218     {
 219       if (pkey != NULL)
 220         *pkey = p->second.first;
 221       return p->first;
 222     }
 223
 224   Key k;
 225   const Stringpool_char* ret = this->add_string(s, &k);
 226
 227   const off_t ozero = 0;
 228   std::pair<const Stringpool_char*, Val> element(ret,
 229                                                  std::make_pair(k, ozero));
 230   std::pair<typename String_set_type::iterator, bool> ins =
 231     this->string_set_.insert(element);
 232   gold_assert(ins.second);
 233
 234   if (pkey != NULL)
 235     *pkey = k;
 236
 237   return ret;
 238 }
 239
 240 // Add a prefix of a string to a string pool.
 241
 242 template<typename Stringpool_char>
 243 const Stringpool_char*
 244 Stringpool_template<Stringpool_char>::add(const Stringpool_char* s, size_t len,
 245                                  Key* pkey)
 246 {
 247   // FIXME: This implementation should be rewritten when we rewrite
 248   // the hash table to avoid copying.
 249   std::basic_string<Stringpool_char> st(s, len);
 250   return this->add(st, pkey);
 251 }
 252
 253 template<typename Stringpool_char>
 254 const Stringpool_char*
 255 Stringpool_template<Stringpool_char>::find(const Stringpool_char* s,
 256                                            Key* pkey) const
 257 {
 258   typename String_set_type::const_iterator p = this->string_set_.find(s);
 259   if (p == this->string_set_.end())
 260     return NULL;
 261
 262   if (pkey != NULL)
 263     *pkey = p->second.first;
 264
 265   return p->first;
 266 }
 267
 268 // Comparison routine used when sorting into an ELF strtab.  We want
 269 // to sort this so that when one string is a suffix of another, we
 270 // always see the shorter string immediately after the longer string.
 271 // For example, we want to see these strings in this order:
 272 //   abcd
 273 //   cd
 274 //   d
 275 // When strings are not suffixes, we don't care what order they are
 276 // in, but we need to ensure that suffixes wind up next to each other.
 277 // So we do a reversed lexicographic sort on the reversed string.
 278
 279 template<typename Stringpool_char>
 280 bool
 281 Stringpool_template<Stringpool_char>::Stringpool_sort_comparison::operator()(
 282   const Stringpool_sort_info& sort_info1,
 283   const Stringpool_sort_info& sort_info2) const
 284 {
 285   const Stringpool_char* s1 = sort_info1.it->first;
 286   const Stringpool_char* s2 = sort_info2.it->first;
 287   const size_t len1 = sort_info1.string_length;
 288   const size_t len2 = sort_info2.string_length;
 289   const size_t minlen = len1 < len2 ? len1 : len2;
 290   const Stringpool_char* p1 = s1 + len1 - 1;
 291   const Stringpool_char* p2 = s2 + len2 - 1;
 292   for (size_t i = minlen; i > 0; --i, --p1, --p2)
 293     {
 294       if (*p1 != *p2)
 295         return *p1 > *p2;
 296     }
 297   return len1 > len2;
 298 }
 299
 300 // Return whether s1 is a suffix of s2.
 301
 302 template<typename Stringpool_char>
 303 bool
 304 Stringpool_template<Stringpool_char>::is_suffix(const Stringpool_char* s1,
 305                                                 size_t len1,
 306                                                 const Stringpool_char* s2,
 307                                                 size_t len2)
 308 {
 309   if (len1 > len2)
 310     return false;
 311   return memcmp(s1, s2 + len2 - len1, len1 * sizeof(Stringpool_char)) == 0;
 312 }
 313
 314 // Turn the stringpool into an ELF strtab: determine the offsets of
 315 // each string in the table.
 316
 317 template<typename Stringpool_char>
 318 void
 319 Stringpool_template<Stringpool_char>::set_string_offsets()
 320 {
 321   if (this->strtab_size_ != 0)
 322     {
 323       // We've already computed the offsets.
 324       return;
 325     }
 326
 327   const size_t charsize = sizeof(Stringpool_char);
 328
 329   // Offset 0 may be reserved for the empty string.
 330   off_t offset = this->zero_null_ ? charsize : 0;
 331
 332   // Sorting to find suffixes can take over 25% of the total CPU time
 333   // used by the linker.  Since it's merely an optimization to reduce
 334   // the strtab size, and gives a relatively small benefit (it's
 335   // typically rare for a symbol to be a suffix of another), we only
 336   // take the time to sort when the user asks for heavy optimization.
 337   if (parameters->optimization_level() < 2)
 338     {
 339       for (typename String_set_type::iterator curr = this->string_set_.begin();
 340            curr != this->string_set_.end();
 341            curr++)
 342         {
 343           if (this->zero_null_ && curr->first[0] == 0)
 344             curr->second.second = 0;
 345           else
 346             {
 347               curr->second.second = offset;
 348               offset += (string_length(curr->first) + 1) * charsize;
 349             }
 350         }
 351     }
 352   else
 353     {
 354       size_t count = this->string_set_.size();
 355
 356       std::vector<Stringpool_sort_info> v;
 357       v.reserve(count);
 358
 359       for (typename String_set_type::iterator p = this->string_set_.begin();
 360            p != this->string_set_.end();
 361            ++p)
 362         v.push_back(Stringpool_sort_info(p, string_length(p->first)));
 363
 364       std::sort(v.begin(), v.end(), Stringpool_sort_comparison());
 365
 366       for (typename std::vector<Stringpool_sort_info>::iterator last = v.end(),
 367              curr = v.begin();
 368            curr != v.end();
 369            last = curr++)
 370         {
 371           if (this->zero_null_ && curr->it->first[0] == 0)
 372             curr->it->second.second = 0;
 373           else if (last != v.end()
 374                    && is_suffix(curr->it->first, curr->string_length,
 375                                 last->it->first, last->string_length))
 376             curr->it->second.second = (last->it->second.second
 377                                        + ((last->string_length
 378                                            - curr->string_length)
 379                                           * charsize));
 380           else
 381             {
 382               curr->it->second.second = offset;
 383               offset += (curr->string_length + 1) * charsize;
 384             }
 385         }
 386     }
 387
 388   this->strtab_size_ = offset;
 389 }
 390
 391 // Get the offset of a string in the ELF strtab.  The string must
 392 // exist.
 393
 394 template<typename Stringpool_char>
 395 off_t
 396 Stringpool_template<Stringpool_char>::get_offset(const Stringpool_char* s)
 397   const
 398 {
 399   gold_assert(this->strtab_size_ != 0);
 400   typename String_set_type::const_iterator p = this->string_set_.find(s);
 401   if (p != this->string_set_.end())
 402     return p->second.second;
 403   gold_unreachable();
 404 }
 405
 406 // Write the ELF strtab into the output file at the specified offset.
 407
 408 template<typename Stringpool_char>
 409 void
 410 Stringpool_template<Stringpool_char>::write(Output_file* of, off_t offset)
 411 {
 412   gold_assert(this->strtab_size_ != 0);
 413   unsigned char* viewu = of->get_output_view(offset, this->strtab_size_);
 414   char* view = reinterpret_cast<char*>(viewu);
 415   if (this->zero_null_)
 416     view[0] = '\0';
 417   for (typename String_set_type::const_iterator p = this->string_set_.begin();
 418        p != this->string_set_.end();
 419        ++p)
 420     memcpy(view + p->second.second, p->first,
 421            (string_length(p->first) + 1) * sizeof(Stringpool_char));
 422   of->write_output_view(offset, this->strtab_size_, viewu);
 423 }
 424
 425 // Instantiate the templates we need.
 426
 427 template
 428 class Stringpool_template<char>;
 429
 430 template
 431 class Stringpool_template<uint16_t>;
 432
 433 template
 434 class Stringpool_template<uint32_t>;
 435
 436 } // End namespace gold.