Home | History | Annotate | Download | only in gold
      1 // stringpool.h -- a string pool for gold    -*- C++ -*-
      2 
      3 // Copyright (C) 2006-2014 Free Software Foundation, Inc.
      4 // Written by Ian Lance Taylor <iant (at) 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 <string>
     24 #include <list>
     25 #include <vector>
     26 
     27 #ifndef GOLD_STRINGPOOL_H
     28 #define GOLD_STRINGPOOL_H
     29 
     30 namespace gold
     31 {
     32 
     33 class Output_file;
     34 
     35 // Return the length of a string in units of Char_type.
     36 
     37 template<typename Char_type>
     38 inline size_t
     39 string_length(const Char_type* p)
     40 {
     41   size_t len = 0;
     42   for (; *p != 0; ++p)
     43     ++len;
     44   return len;
     45 }
     46 
     47 // Specialize string_length for char.  Maybe we could just use
     48 // std::char_traits<>::length?
     49 
     50 template<>
     51 inline size_t
     52 string_length(const char* p)
     53 {
     54   return strlen(p);
     55 }
     56 
     57 // A Stringpool is a pool of unique strings.  It provides the
     58 // following features:
     59 
     60 // Every string in the pool is unique.  Thus, if you have two strings
     61 // in the Stringpool, you can compare them for equality by using
     62 // pointer comparison rather than string comparison.
     63 
     64 // There is a key associated with every string in the pool.  If you
     65 // add strings to the Stringpool in the same order, then the key for
     66 // each string will always be the same for any run of the linker.
     67 // This is not true of the string pointers themselves, as they may
     68 // change due to address space randomization.  Some parts of the
     69 // linker (e.g., the symbol table) use the key value instead of the
     70 // string pointer so that repeated runs of the linker will generate
     71 // precisely the same output.
     72 
     73 // When you add a string to a Stringpool, Stringpool will optionally
     74 // make a copy of it.  Thus there is no requirement to keep a copy
     75 // elsewhere.
     76 
     77 // A Stringpool can be turned into a string table, a sequential series
     78 // of null terminated strings.  The first string may optionally be a
     79 // single zero byte, as required for SHT_STRTAB sections.  This
     80 // conversion is only permitted after all strings have been added to
     81 // the Stringpool.  After doing this conversion, you can ask for the
     82 // offset of any string (or any key) in the stringpool in the string
     83 // table, and you can write the resulting string table to an output
     84 // file.
     85 
     86 // When a Stringpool is turned into a string table, then as an
     87 // optimization it will reuse string suffixes to avoid duplicating
     88 // strings.  That is, given the strings "abc" and "bc", only the
     89 // string "abc" will be stored, and "bc" will be represented by an
     90 // offset into the middle of the string "abc".
     91 
     92 
     93 // A simple chunked vector class--this is a subset of std::vector
     94 // which stores memory in chunks.  We don't provide iterators, because
     95 // we don't need them.
     96 
     97 template<typename Element>
     98 class Chunked_vector
     99 {
    100  public:
    101   Chunked_vector()
    102     : chunks_(), size_(0)
    103   { }
    104 
    105   // Clear the elements.
    106   void
    107   clear()
    108   {
    109     this->chunks_.clear();
    110     this->size_ = 0;
    111   }
    112 
    113   // Reserve elements.
    114   void
    115   reserve(unsigned int n)
    116   {
    117     if (n > this->chunks_.size() * chunk_size)
    118       {
    119 	this->chunks_.resize((n + chunk_size - 1) / chunk_size);
    120 	// We need to call reserve() of all chunks since changing
    121 	// this->chunks_ casues Element_vectors to be copied.  The
    122 	// reserved capacity of an Element_vector may be lost in copying.
    123 	for (size_t i = 0; i < this->chunks_.size(); ++i)
    124 	  this->chunks_[i].reserve(chunk_size);
    125       }
    126   }
    127 
    128   // Get the number of elements.
    129   size_t
    130   size() const
    131   { return this->size_; }
    132 
    133   // Push a new element on the back of the vector.
    134   void
    135   push_back(const Element& element)
    136   {
    137     size_t chunk_index = this->size_ / chunk_size;
    138     if (chunk_index >= this->chunks_.size())
    139       {
    140 	this->chunks_.push_back(Element_vector());
    141 	this->chunks_.back().reserve(chunk_size);
    142 	gold_assert(chunk_index < this->chunks_.size());
    143       }
    144     this->chunks_[chunk_index].push_back(element);
    145     this->size_++;
    146   }
    147 
    148   // Return a reference to an entry in the vector.
    149   Element&
    150   operator[](size_t i)
    151   { return this->chunks_[i / chunk_size][i % chunk_size]; }
    152 
    153   const Element&
    154   operator[](size_t i) const
    155   { return this->chunks_[i / chunk_size][i % chunk_size]; }
    156 
    157  private:
    158   static const unsigned int chunk_size = 8192;
    159 
    160   typedef std::vector<Element> Element_vector;
    161   typedef std::vector<Element_vector> Chunk_vector;
    162 
    163   Chunk_vector chunks_;
    164   size_t size_;
    165 };
    166 
    167 
    168 // Stringpools are implemented in terms of Stringpool_template, which
    169 // is generalized on the type of character used for the strings.  Most
    170 // uses will want the Stringpool type which uses char.  Other cases
    171 // are used for merging wide string constants.
    172 
    173 template<typename Stringpool_char>
    174 class Stringpool_template
    175 {
    176  public:
    177   // The type of a key into the stringpool.  As described above, a key
    178   // value will always be the same during any run of the linker.  Zero
    179   // is never a valid key value.
    180   typedef size_t Key;
    181 
    182   // Create a Stringpool.
    183   Stringpool_template(uint64_t addralign = 1);
    184 
    185   ~Stringpool_template();
    186 
    187   // Clear all the data from the stringpool.
    188   void
    189   clear();
    190 
    191   // Hint to the stringpool class that you intend to insert n additional
    192   // elements.  The stringpool class can use this info however it likes;
    193   // in practice it will resize its internal hashtables to make room.
    194   void
    195   reserve(unsigned int n);
    196 
    197   // Indicate that we should not reserve offset 0 to hold the empty
    198   // string when converting the stringpool to a string table.  This
    199   // should not be called for a proper ELF SHT_STRTAB section.
    200   void
    201   set_no_zero_null()
    202   {
    203     gold_assert(this->string_set_.empty()
    204 		&& this->offset_ == sizeof(Stringpool_char));
    205     this->zero_null_ = false;
    206     this->offset_ = 0;
    207   }
    208 
    209   // Indicate that this string pool should be optimized, even if not
    210   // running with -O2.
    211   void
    212   set_optimize()
    213   { this->optimize_ = true; }
    214 
    215   // Add the string S to the pool.  This returns a canonical permanent
    216   // pointer to the string in the pool.  If COPY is true, the string
    217   // is copied into permanent storage.  If PKEY is not NULL, this sets
    218   // *PKEY to the key for the string.
    219   const Stringpool_char*
    220   add(const Stringpool_char* s, bool copy, Key* pkey);
    221 
    222   // Add the string S to the pool.
    223   const Stringpool_char*
    224   add(const std::basic_string<Stringpool_char>& s, bool copy, Key* pkey)
    225   { return this->add_with_length(s.data(), s.size(), copy, pkey); }
    226 
    227   // Add string S of length LEN characters to the pool.  If COPY is
    228   // true, S need not be null terminated.
    229   const Stringpool_char*
    230   add_with_length(const Stringpool_char* s, size_t len, bool copy, Key* pkey);
    231 
    232   // If the string S is present in the pool, return the canonical
    233   // string pointer.  Otherwise, return NULL.  If PKEY is not NULL,
    234   // set *PKEY to the key.
    235   const Stringpool_char*
    236   find(const Stringpool_char* s, Key* pkey) const;
    237 
    238   // Turn the stringpool into a string table: determine the offsets of
    239   // all the strings.  After this is called, no more strings may be
    240   // added to the stringpool.
    241   void
    242   set_string_offsets();
    243 
    244   // Get the offset of the string S in the string table.  This returns
    245   // the offset in bytes, not in units of Stringpool_char.  This may
    246   // only be called after set_string_offsets has been called.
    247   section_offset_type
    248   get_offset(const Stringpool_char* s) const;
    249 
    250   // Get the offset of the string S in the string table.
    251   section_offset_type
    252   get_offset(const std::basic_string<Stringpool_char>& s) const
    253   { return this->get_offset_with_length(s.c_str(), s.size()); }
    254 
    255   // Get the offset of string S, with length LENGTH characters, in the
    256   // string table.
    257   section_offset_type
    258   get_offset_with_length(const Stringpool_char* s, size_t length) const;
    259 
    260   // Get the offset of the string with key K.
    261   section_offset_type
    262   get_offset_from_key(Key k) const
    263   {
    264     gold_assert(k <= this->key_to_offset_.size());
    265     return this->key_to_offset_[k - 1];
    266   }
    267 
    268   // Get the size of the string table.  This returns the number of
    269   // bytes, not in units of Stringpool_char.
    270   section_size_type
    271   get_strtab_size() const
    272   {
    273     gold_assert(this->strtab_size_ != 0);
    274     return this->strtab_size_;
    275   }
    276 
    277   // Write the string table into the output file at the specified
    278   // offset.
    279   void
    280   write(Output_file*, off_t offset);
    281 
    282   // Write the string table into the specified buffer, of the
    283   // specified size.  buffer_size should be at least
    284   // get_strtab_size().
    285   void
    286   write_to_buffer(unsigned char* buffer, section_size_type buffer_size);
    287 
    288   // Dump statistical information to stderr.
    289   void
    290   print_stats(const char*) const;
    291 
    292  private:
    293   Stringpool_template(const Stringpool_template&);
    294   Stringpool_template& operator=(const Stringpool_template&);
    295 
    296   // Return whether two strings are equal.
    297   static bool
    298   string_equal(const Stringpool_char*, const Stringpool_char*);
    299 
    300   // Compute a hash code for a string.  LENGTH is the length of the
    301   // string in characters.
    302   static size_t
    303   string_hash(const Stringpool_char*, size_t length);
    304 
    305   // We store the actual data in a list of these buffers.
    306   struct Stringdata
    307   {
    308     // Length of data in buffer.
    309     size_t len;
    310     // Allocated size of buffer.
    311     size_t alc;
    312     // Buffer.
    313     char data[1];
    314   };
    315 
    316   // Add a new key offset entry.
    317   void
    318   new_key_offset(size_t);
    319 
    320   // Copy a string into the buffers, returning a canonical string.
    321   const Stringpool_char*
    322   add_string(const Stringpool_char*, size_t);
    323 
    324   // Return whether s1 is a suffix of s2.
    325   static bool
    326   is_suffix(const Stringpool_char* s1, size_t len1,
    327             const Stringpool_char* s2, size_t len2);
    328 
    329   // The hash table key includes the string, the length of the string,
    330   // and the hash code for the string.  We put the hash code
    331   // explicitly into the key so that we can do a find()/insert()
    332   // sequence without having to recompute the hash.  Computing the
    333   // hash code is a significant user of CPU time in the linker.
    334   struct Hashkey
    335   {
    336     const Stringpool_char* string;
    337     // Length is in characters, not bytes.
    338     size_t length;
    339     size_t hash_code;
    340 
    341     // This goes in an STL container, so we need a default
    342     // constructor.
    343     Hashkey()
    344       : string(NULL), length(0), hash_code(0)
    345     { }
    346 
    347     // Note that these constructors are relatively expensive, because
    348     // they compute the hash code.
    349     explicit Hashkey(const Stringpool_char* s)
    350       : string(s), length(string_length(s)), hash_code(string_hash(s, length))
    351     { }
    352 
    353     Hashkey(const Stringpool_char* s, size_t len)
    354       : string(s), length(len), hash_code(string_hash(s, len))
    355     { }
    356   };
    357 
    358   // Hash function.  This is trivial, since we have already computed
    359   // the hash.
    360   struct Stringpool_hash
    361   {
    362     size_t
    363     operator()(const Hashkey& hk) const
    364     { return hk.hash_code; }
    365   };
    366 
    367   // Equality comparison function for hash table.
    368   struct Stringpool_eq
    369   {
    370     bool
    371     operator()(const Hashkey&, const Hashkey&) const;
    372   };
    373 
    374   // The hash table is a map from strings to Keys.
    375 
    376   typedef Key Hashval;
    377 
    378   typedef Unordered_map<Hashkey, Hashval, Stringpool_hash,
    379 			Stringpool_eq> String_set_type;
    380 
    381   // Comparison routine used when sorting into a string table.
    382 
    383   typedef typename String_set_type::iterator Stringpool_sort_info;
    384 
    385   struct Stringpool_sort_comparison
    386   {
    387     bool
    388     operator()(const Stringpool_sort_info&, const Stringpool_sort_info&) const;
    389   };
    390 
    391   // Keys map to offsets via a Chunked_vector.  We only use the
    392   // offsets if we turn this into an string table section.
    393   typedef Chunked_vector<section_offset_type> Key_to_offset;
    394 
    395   // List of Stringdata structures.
    396   typedef std::list<Stringdata*> Stringdata_list;
    397 
    398   // Mapping from const char* to namepool entry.
    399   String_set_type string_set_;
    400   // Mapping from Key to string table offset.
    401   Key_to_offset key_to_offset_;
    402   // List of buffers.
    403   Stringdata_list strings_;
    404   // Size of string table.
    405   section_size_type strtab_size_;
    406   // Whether to reserve offset 0 to hold the null string.
    407   bool zero_null_;
    408   // Whether to optimize the string table.
    409   bool optimize_;
    410   // offset of the next string.
    411   section_offset_type offset_;
    412   // The alignment of strings in the stringpool.
    413   uint64_t addralign_;
    414 };
    415 
    416 // The most common type of Stringpool.
    417 typedef Stringpool_template<char> Stringpool;
    418 
    419 } // End namespace gold.
    420 
    421 #endif // !defined(GOLD_STRINGPOOL_H)
    422