| 1 | // merge.cc -- handle section merging for gold |
| 2 | |
| 3 | #include "gold.h" |
| 4 | |
| 5 | #include <cstdlib> |
| 6 | |
| 7 | #include "merge.h" |
| 8 | |
| 9 | namespace gold |
| 10 | { |
| 11 | |
| 12 | // Sort the entries in a merge mapping. The key is an input object, a |
| 13 | // section index in that object, and an offset in that section. |
| 14 | |
| 15 | bool |
| 16 | Output_merge_base::Merge_key_less::operator()(const Merge_key& mk1, |
| 17 | const Merge_key& mk2) const |
| 18 | { |
| 19 | // The order of different objects and different sections doesn't |
| 20 | // matter. We want to get consistent results across links so we |
| 21 | // don't use pointer comparison. |
| 22 | if (mk1.object != mk2.object) |
| 23 | return mk1.object->name() < mk2.object->name(); |
| 24 | if (mk1.shndx != mk2.shndx) |
| 25 | return mk1.shndx < mk2.shndx; |
| 26 | return mk1.offset < mk2.offset; |
| 27 | } |
| 28 | |
| 29 | // Add a mapping from an OFFSET in input section SHNDX in object |
| 30 | // OBJECT to an OUTPUT_OFFSET in a merged output section. This |
| 31 | // manages the mapping used to resolve relocations against merged |
| 32 | // sections. |
| 33 | |
| 34 | void |
| 35 | Output_merge_base::add_mapping(Relobj* object, unsigned int shndx, |
| 36 | off_t offset, off_t output_offset) |
| 37 | { |
| 38 | Merge_key mk; |
| 39 | mk.object = object; |
| 40 | mk.shndx = shndx; |
| 41 | mk.offset = offset; |
| 42 | std::pair<Merge_map::iterator, bool> ins = |
| 43 | this->merge_map_.insert(std::make_pair(mk, output_offset)); |
| 44 | gold_assert(ins.second); |
| 45 | } |
| 46 | |
| 47 | // Return the output address for an input address. The input address |
| 48 | // is at offset OFFSET in section SHNDX in OBJECT. |
| 49 | // OUTPUT_SECTION_ADDRESS is the address of the output section. If we |
| 50 | // know the address, set *POUTPUT and return true. Otherwise return |
| 51 | // false. |
| 52 | |
| 53 | bool |
| 54 | Output_merge_base::do_output_address(const Relobj* object, unsigned int shndx, |
| 55 | off_t offset, |
| 56 | uint64_t output_section_address, |
| 57 | uint64_t* poutput) const |
| 58 | { |
| 59 | gold_assert(output_section_address == this->address()); |
| 60 | |
| 61 | Merge_key mk; |
| 62 | mk.object = object; |
| 63 | mk.shndx = shndx; |
| 64 | mk.offset = offset; |
| 65 | Merge_map::const_iterator p = this->merge_map_.lower_bound(mk); |
| 66 | |
| 67 | // If MK is not in the map, lower_bound returns the next iterator |
| 68 | // larger than it. |
| 69 | if (p->first.object != object |
| 70 | || p->first.shndx != shndx |
| 71 | || p->first.offset != offset) |
| 72 | { |
| 73 | if (p == this->merge_map_.begin()) |
| 74 | return false; |
| 75 | --p; |
| 76 | } |
| 77 | |
| 78 | if (p->first.object != object || p->first.shndx != shndx) |
| 79 | return false; |
| 80 | |
| 81 | // Any input section is fully mapped: we don't need to know the size |
| 82 | // of the range starting at P->FIRST.OFFSET. |
| 83 | *poutput = output_section_address + p->second + (offset - p->first.offset); |
| 84 | return true; |
| 85 | } |
| 86 | |
| 87 | // Compute the hash code for a fixed-size constant. |
| 88 | |
| 89 | size_t |
| 90 | Output_merge_data::Merge_data_hash::operator()(Merge_data_key k) const |
| 91 | { |
| 92 | const unsigned char* p = this->pomd_->constant(k); |
| 93 | uint64_t entsize = this->pomd_->entsize(); |
| 94 | |
| 95 | // Fowler/Noll/Vo (FNV) hash (type FNV-1a). |
| 96 | if (sizeof(size_t) == 8) |
| 97 | { |
| 98 | size_t result = static_cast<size_t>(14695981039346656037ULL); |
| 99 | for (uint64_t i = 0; i < entsize; ++i) |
| 100 | { |
| 101 | result &= (size_t) *p++; |
| 102 | result *= 1099511628211ULL; |
| 103 | } |
| 104 | return result; |
| 105 | } |
| 106 | else |
| 107 | { |
| 108 | size_t result = 2166136261UL; |
| 109 | for (uint64_t i = 0; i < entsize; ++i) |
| 110 | { |
| 111 | result ^= (size_t) *p++; |
| 112 | result *= 16777619UL; |
| 113 | } |
| 114 | return result; |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | // Return whether one hash table key equals another. |
| 119 | |
| 120 | bool |
| 121 | Output_merge_data::Merge_data_eq::operator()(Merge_data_key k1, |
| 122 | Merge_data_key k2) const |
| 123 | { |
| 124 | const unsigned char* p1 = this->pomd_->constant(k1); |
| 125 | const unsigned char* p2 = this->pomd_->constant(k2); |
| 126 | return memcmp(p1, p2, this->pomd_->entsize()) == 0; |
| 127 | } |
| 128 | |
| 129 | // Add a constant to the end of the section contents. |
| 130 | |
| 131 | void |
| 132 | Output_merge_data::add_constant(const unsigned char* p) |
| 133 | { |
| 134 | uint64_t entsize = this->entsize(); |
| 135 | if (this->len_ + entsize > this->alc_) |
| 136 | { |
| 137 | if (this->alc_ == 0) |
| 138 | this->alc_ = 128 * entsize; |
| 139 | else |
| 140 | this->alc_ *= 2; |
| 141 | this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->alc_)); |
| 142 | if (this->p_ == NULL) |
| 143 | gold_fatal("out of memory", true); |
| 144 | } |
| 145 | |
| 146 | memcpy(this->p_ + this->len_, p, entsize); |
| 147 | this->len_ += entsize; |
| 148 | } |
| 149 | |
| 150 | // Add the input section SHNDX in OBJECT to a merged output section |
| 151 | // which holds fixed length constants. Return whether we were able to |
| 152 | // handle the section; if not, it will be linked as usual without |
| 153 | // constant merging. |
| 154 | |
| 155 | bool |
| 156 | Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx) |
| 157 | { |
| 158 | off_t len; |
| 159 | const unsigned char* p = object->section_contents(shndx, &len); |
| 160 | |
| 161 | uint64_t entsize = this->entsize(); |
| 162 | |
| 163 | if (len % entsize != 0) |
| 164 | return false; |
| 165 | |
| 166 | for (off_t i = 0; i < len; i += entsize, p += entsize) |
| 167 | { |
| 168 | // Add the constant to the section contents. If we find that it |
| 169 | // is already in the hash table, we will remove it again. |
| 170 | Merge_data_key k = this->len_; |
| 171 | this->add_constant(p); |
| 172 | |
| 173 | std::pair<Merge_data_hashtable::iterator, bool> ins = |
| 174 | this->hashtable_.insert(k); |
| 175 | |
| 176 | if (!ins.second) |
| 177 | { |
| 178 | // Key was already present. Remove the copy we just added. |
| 179 | this->len_ -= entsize; |
| 180 | k = *ins.first; |
| 181 | } |
| 182 | |
| 183 | // Record the offset of this constant in the output section. |
| 184 | this->add_mapping(object, shndx, i, k); |
| 185 | } |
| 186 | |
| 187 | return true; |
| 188 | } |
| 189 | |
| 190 | // Set the final data size in a merged output section with fixed size |
| 191 | // constants. |
| 192 | |
| 193 | void |
| 194 | Output_merge_data::do_set_address(uint64_t, off_t) |
| 195 | { |
| 196 | // Release the memory we don't need. |
| 197 | this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->len_)); |
| 198 | gold_assert(this->p_ != NULL); |
| 199 | this->set_data_size(this->len_); |
| 200 | } |
| 201 | |
| 202 | // Write the data of a merged output section with fixed size constants |
| 203 | // to the file. |
| 204 | |
| 205 | void |
| 206 | Output_merge_data::do_write(Output_file* of) |
| 207 | { |
| 208 | of->write(this->offset(), this->p_, this->len_); |
| 209 | } |
| 210 | |
| 211 | // Compute a hash code for a Merge_string_key, which is an object, a |
| 212 | // section index, and an offset. |
| 213 | |
| 214 | template<typename Char_type> |
| 215 | size_t |
| 216 | Output_merge_string<Char_type>::Merge_string_key_hash::operator()( |
| 217 | const Merge_string_key& key) const |
| 218 | { |
| 219 | // This is a very simple minded hash code. Fix it if it we get too |
| 220 | // many collisions. |
| 221 | const std::string& oname(key.object->name()); |
| 222 | return oname[0] + oname.length() + key.shndx + key.offset; |
| 223 | } |
| 224 | |
| 225 | // Compare two Merge_string_keys for equality. |
| 226 | |
| 227 | template<typename Char_type> |
| 228 | bool |
| 229 | Output_merge_string<Char_type>::Merge_string_key_eq::operator()( |
| 230 | const Merge_string_key& k1, const Merge_string_key& k2) const |
| 231 | { |
| 232 | return (k1.object == k2.object |
| 233 | && k1.shndx == k2.shndx |
| 234 | && k1.offset == k2.offset); |
| 235 | } |
| 236 | |
| 237 | // Add an input section to a merged string section. |
| 238 | |
| 239 | template<typename Char_type> |
| 240 | bool |
| 241 | Output_merge_string<Char_type>::do_add_input_section(Relobj* object, |
| 242 | unsigned int shndx) |
| 243 | { |
| 244 | off_t len; |
| 245 | const unsigned char* pdata = object->section_contents(shndx, &len); |
| 246 | |
| 247 | const Char_type* p = reinterpret_cast<const Char_type*>(pdata); |
| 248 | |
| 249 | if (len % sizeof(Char_type) != 0) |
| 250 | { |
| 251 | fprintf(stderr, |
| 252 | _("%s: %s: mergeable string section length not multiple of " |
| 253 | "character size\n"), |
| 254 | program_name, object->name().c_str()); |
| 255 | gold_exit(false); |
| 256 | } |
| 257 | len /= sizeof(Char_type); |
| 258 | |
| 259 | off_t i = 0; |
| 260 | while (i < len) |
| 261 | { |
| 262 | off_t plen = 0; |
| 263 | for (const Char_type* pl = p; *pl != 0; ++pl) |
| 264 | { |
| 265 | ++plen; |
| 266 | if (i + plen >= len) |
| 267 | { |
| 268 | fprintf(stderr, |
| 269 | _("%s: %s: entry in mergeable string section " |
| 270 | "not null terminated\n"), |
| 271 | program_name, object->name().c_str()); |
| 272 | gold_exit(false); |
| 273 | } |
| 274 | } |
| 275 | |
| 276 | const Char_type* str = this->stringpool_.add(p, NULL); |
| 277 | |
| 278 | Merge_string_key k(object, shndx, i); |
| 279 | typename Merge_string_hashtable::value_type v(k, str); |
| 280 | bool b = this->hashtable_.insert(v).second; |
| 281 | gold_assert(b); |
| 282 | |
| 283 | p += plen + 1; |
| 284 | i += plen + 1; |
| 285 | } |
| 286 | |
| 287 | return true; |
| 288 | } |
| 289 | |
| 290 | // Set the final data size of a merged string section. This is where |
| 291 | // we finalize the mappings from the input sections to the output |
| 292 | // section. |
| 293 | |
| 294 | template<typename Char_type> |
| 295 | void |
| 296 | Output_merge_string<Char_type>::do_set_address(uint64_t, off_t) |
| 297 | { |
| 298 | this->stringpool_.set_string_offsets(); |
| 299 | |
| 300 | for (typename Merge_string_hashtable::const_iterator p = |
| 301 | this->hashtable_.begin(); |
| 302 | p != this->hashtable_.end(); |
| 303 | ++p) |
| 304 | this->add_mapping(p->first.object, p->first.shndx, p->first.offset, |
| 305 | this->stringpool_.get_offset(p->second)); |
| 306 | |
| 307 | this->set_data_size(this->stringpool_.get_strtab_size()); |
| 308 | |
| 309 | // Save some memory. |
| 310 | this->hashtable_.clear(); |
| 311 | } |
| 312 | |
| 313 | // Write out a merged string section. |
| 314 | |
| 315 | template<typename Char_type> |
| 316 | void |
| 317 | Output_merge_string<Char_type>::do_write(Output_file* of) |
| 318 | { |
| 319 | this->stringpool_.write(of, this->offset()); |
| 320 | } |
| 321 | |
| 322 | // Instantiate the templates we need. |
| 323 | |
| 324 | template |
| 325 | class Output_merge_string<char>; |
| 326 | |
| 327 | template |
| 328 | class Output_merge_string<uint16_t>; |
| 329 | |
| 330 | template |
| 331 | class Output_merge_string<uint32_t>; |
| 332 | |
| 333 | } // End namespace gold. |