Commit | Line | Data |
---|---|---|
b8e6aad9 ILT |
1 | // merge.cc -- handle section merging for gold |
2 | ||
6cb15b7f ILT |
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 | ||
b8e6aad9 ILT |
23 | #include "gold.h" |
24 | ||
25 | #include <cstdlib> | |
87f95776 | 26 | #include <algorithm> |
b8e6aad9 ILT |
27 | |
28 | #include "merge.h" | |
29 | ||
30 | namespace gold | |
31 | { | |
32 | ||
730cdc88 ILT |
33 | // Class Merge_map::Merge_key_less. |
34 | ||
b8e6aad9 ILT |
35 | // Sort the entries in a merge mapping. The key is an input object, a |
36 | // section index in that object, and an offset in that section. | |
37 | ||
d8a88976 | 38 | inline bool |
730cdc88 ILT |
39 | Merge_map::Merge_key_less::operator()(const Merge_key& mk1, |
40 | const Merge_key& mk2) const | |
b8e6aad9 ILT |
41 | { |
42 | // The order of different objects and different sections doesn't | |
43 | // matter. We want to get consistent results across links so we | |
44 | // don't use pointer comparison. | |
45 | if (mk1.object != mk2.object) | |
cec9d2f3 ILT |
46 | { |
47 | // Two different object files can have the same name: if foo.a | |
48 | // includes both bar/qux.o and baz/qux.o, then both end up with | |
49 | // the name foo.a(qux.o). But it's impossible for two different | |
50 | // object files to have both the same name and the same offset. | |
51 | if (mk1.object->offset() != mk2.object->offset()) | |
52 | return mk1.object->offset() < mk2.object->offset(); | |
53 | return mk1.object->name() < mk2.object->name(); | |
54 | } | |
b8e6aad9 ILT |
55 | if (mk1.shndx != mk2.shndx) |
56 | return mk1.shndx < mk2.shndx; | |
57 | return mk1.offset < mk2.offset; | |
58 | } | |
59 | ||
730cdc88 ILT |
60 | // Class Merge_map. |
61 | ||
62 | // Add a mapping for the bytes from OFFSET to OFFSET + LENGTH in input | |
63 | // section SHNDX in object OBJECT to an OUTPUT_OFFSET in a merged | |
64 | // output section. | |
b8e6aad9 ILT |
65 | |
66 | void | |
730cdc88 ILT |
67 | Merge_map::add_mapping(Relobj* object, unsigned int shndx, |
68 | off_t offset, off_t length, off_t output_offset) | |
b8e6aad9 ILT |
69 | { |
70 | Merge_key mk; | |
71 | mk.object = object; | |
72 | mk.shndx = shndx; | |
73 | mk.offset = offset; | |
730cdc88 ILT |
74 | |
75 | Merge_value mv; | |
76 | mv.length = length; | |
77 | mv.output_offset = output_offset; | |
78 | ||
79 | std::pair<Merge_mapping::iterator, bool> ins = | |
80 | this->merge_map_.insert(std::make_pair(mk, mv)); | |
b8e6aad9 ILT |
81 | gold_assert(ins.second); |
82 | } | |
83 | ||
730cdc88 ILT |
84 | // Return the output offset for an input address. The input address |
85 | // is at offset OFFSET in section SHNDX in OBJECT. This sets | |
86 | // *OUTPUT_OFFSET to the offset in the output section. This returns | |
87 | // true if the mapping is known, false otherwise. | |
b8e6aad9 ILT |
88 | |
89 | bool | |
730cdc88 ILT |
90 | Merge_map::get_output_offset(const Relobj* object, unsigned int shndx, |
91 | off_t offset, off_t* output_offset) const | |
b8e6aad9 | 92 | { |
b8e6aad9 ILT |
93 | Merge_key mk; |
94 | mk.object = object; | |
95 | mk.shndx = shndx; | |
96 | mk.offset = offset; | |
730cdc88 | 97 | Merge_mapping::const_iterator p = this->merge_map_.lower_bound(mk); |
b8e6aad9 ILT |
98 | |
99 | // If MK is not in the map, lower_bound returns the next iterator | |
100 | // larger than it. | |
c077629b ILT |
101 | if (p == this->merge_map_.end() |
102 | || p->first.object != object | |
b8e6aad9 ILT |
103 | || p->first.shndx != shndx |
104 | || p->first.offset != offset) | |
105 | { | |
106 | if (p == this->merge_map_.begin()) | |
107 | return false; | |
108 | --p; | |
109 | } | |
110 | ||
111 | if (p->first.object != object || p->first.shndx != shndx) | |
112 | return false; | |
113 | ||
730cdc88 ILT |
114 | if (offset - p->first.offset >= p->second.length) |
115 | return false; | |
116 | ||
117 | *output_offset = p->second.output_offset; | |
118 | if (*output_offset != -1) | |
119 | *output_offset += (offset - p->first.offset); | |
b8e6aad9 ILT |
120 | return true; |
121 | } | |
122 | ||
730cdc88 ILT |
123 | // Class Output_merge_base. |
124 | ||
125 | // Return the output offset for an input offset. The input address is | |
126 | // at offset OFFSET in section SHNDX in OBJECT. If we know the | |
127 | // offset, set *POUTPUT and return true. Otherwise return false. | |
128 | ||
129 | bool | |
130 | Output_merge_base::do_output_offset(const Relobj* object, | |
131 | unsigned int shndx, | |
132 | off_t offset, | |
133 | off_t* poutput) const | |
134 | { | |
135 | return this->merge_map_.get_output_offset(object, shndx, offset, poutput); | |
136 | } | |
137 | ||
138 | // Class Output_merge_data. | |
139 | ||
b8e6aad9 ILT |
140 | // Compute the hash code for a fixed-size constant. |
141 | ||
142 | size_t | |
143 | Output_merge_data::Merge_data_hash::operator()(Merge_data_key k) const | |
144 | { | |
145 | const unsigned char* p = this->pomd_->constant(k); | |
146 | uint64_t entsize = this->pomd_->entsize(); | |
147 | ||
148 | // Fowler/Noll/Vo (FNV) hash (type FNV-1a). | |
149 | if (sizeof(size_t) == 8) | |
150 | { | |
151 | size_t result = static_cast<size_t>(14695981039346656037ULL); | |
152 | for (uint64_t i = 0; i < entsize; ++i) | |
153 | { | |
154 | result &= (size_t) *p++; | |
155 | result *= 1099511628211ULL; | |
156 | } | |
157 | return result; | |
158 | } | |
159 | else | |
160 | { | |
161 | size_t result = 2166136261UL; | |
162 | for (uint64_t i = 0; i < entsize; ++i) | |
163 | { | |
164 | result ^= (size_t) *p++; | |
165 | result *= 16777619UL; | |
166 | } | |
167 | return result; | |
168 | } | |
169 | } | |
170 | ||
171 | // Return whether one hash table key equals another. | |
172 | ||
173 | bool | |
174 | Output_merge_data::Merge_data_eq::operator()(Merge_data_key k1, | |
175 | Merge_data_key k2) const | |
176 | { | |
177 | const unsigned char* p1 = this->pomd_->constant(k1); | |
178 | const unsigned char* p2 = this->pomd_->constant(k2); | |
179 | return memcmp(p1, p2, this->pomd_->entsize()) == 0; | |
180 | } | |
181 | ||
182 | // Add a constant to the end of the section contents. | |
183 | ||
184 | void | |
185 | Output_merge_data::add_constant(const unsigned char* p) | |
186 | { | |
187 | uint64_t entsize = this->entsize(); | |
87f95776 ILT |
188 | uint64_t addsize = std::max(entsize, this->addralign()); |
189 | if (this->len_ + addsize > this->alc_) | |
b8e6aad9 ILT |
190 | { |
191 | if (this->alc_ == 0) | |
87f95776 | 192 | this->alc_ = 128 * addsize; |
b8e6aad9 ILT |
193 | else |
194 | this->alc_ *= 2; | |
195 | this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->alc_)); | |
196 | if (this->p_ == NULL) | |
75f2446e | 197 | gold_nomem(); |
b8e6aad9 ILT |
198 | } |
199 | ||
200 | memcpy(this->p_ + this->len_, p, entsize); | |
87f95776 ILT |
201 | if (addsize > entsize) |
202 | memset(this->p_ + this->len_ + entsize, 0, addsize - entsize); | |
203 | this->len_ += addsize; | |
b8e6aad9 ILT |
204 | } |
205 | ||
206 | // Add the input section SHNDX in OBJECT to a merged output section | |
207 | // which holds fixed length constants. Return whether we were able to | |
208 | // handle the section; if not, it will be linked as usual without | |
209 | // constant merging. | |
210 | ||
211 | bool | |
212 | Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx) | |
213 | { | |
214 | off_t len; | |
9eb9fa57 | 215 | const unsigned char* p = object->section_contents(shndx, &len, false); |
b8e6aad9 ILT |
216 | |
217 | uint64_t entsize = this->entsize(); | |
218 | ||
219 | if (len % entsize != 0) | |
220 | return false; | |
221 | ||
222 | for (off_t i = 0; i < len; i += entsize, p += entsize) | |
223 | { | |
224 | // Add the constant to the section contents. If we find that it | |
225 | // is already in the hash table, we will remove it again. | |
226 | Merge_data_key k = this->len_; | |
227 | this->add_constant(p); | |
228 | ||
229 | std::pair<Merge_data_hashtable::iterator, bool> ins = | |
230 | this->hashtable_.insert(k); | |
231 | ||
232 | if (!ins.second) | |
233 | { | |
234 | // Key was already present. Remove the copy we just added. | |
235 | this->len_ -= entsize; | |
236 | k = *ins.first; | |
237 | } | |
238 | ||
239 | // Record the offset of this constant in the output section. | |
730cdc88 | 240 | this->add_mapping(object, shndx, i, entsize, k); |
b8e6aad9 ILT |
241 | } |
242 | ||
243 | return true; | |
244 | } | |
245 | ||
246 | // Set the final data size in a merged output section with fixed size | |
247 | // constants. | |
248 | ||
249 | void | |
250 | Output_merge_data::do_set_address(uint64_t, off_t) | |
251 | { | |
252 | // Release the memory we don't need. | |
253 | this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->len_)); | |
254 | gold_assert(this->p_ != NULL); | |
255 | this->set_data_size(this->len_); | |
256 | } | |
257 | ||
258 | // Write the data of a merged output section with fixed size constants | |
259 | // to the file. | |
260 | ||
261 | void | |
262 | Output_merge_data::do_write(Output_file* of) | |
263 | { | |
264 | of->write(this->offset(), this->p_, this->len_); | |
265 | } | |
266 | ||
730cdc88 ILT |
267 | // Class Output_merge_string. |
268 | ||
b8e6aad9 ILT |
269 | // Add an input section to a merged string section. |
270 | ||
271 | template<typename Char_type> | |
272 | bool | |
273 | Output_merge_string<Char_type>::do_add_input_section(Relobj* object, | |
274 | unsigned int shndx) | |
275 | { | |
276 | off_t len; | |
9eb9fa57 | 277 | const unsigned char* pdata = object->section_contents(shndx, &len, false); |
b8e6aad9 ILT |
278 | |
279 | const Char_type* p = reinterpret_cast<const Char_type*>(pdata); | |
280 | ||
281 | if (len % sizeof(Char_type) != 0) | |
282 | { | |
75f2446e ILT |
283 | object->error(_("mergeable string section length not multiple of " |
284 | "character size")); | |
285 | return false; | |
b8e6aad9 | 286 | } |
b8e6aad9 | 287 | |
fa1bd4fb | 288 | // The index I is in bytes, not characters. |
b8e6aad9 ILT |
289 | off_t i = 0; |
290 | while (i < len) | |
291 | { | |
292 | off_t plen = 0; | |
293 | for (const Char_type* pl = p; *pl != 0; ++pl) | |
294 | { | |
fa1bd4fb | 295 | // The length PLEN is in characters, not bytes. |
b8e6aad9 | 296 | ++plen; |
291eaac6 | 297 | if (i + plen * static_cast<off_t>(sizeof(Char_type)) >= len) |
b8e6aad9 | 298 | { |
75f2446e ILT |
299 | object->error(_("entry in mergeable string section " |
300 | "not null terminated")); | |
301 | break; | |
b8e6aad9 ILT |
302 | } |
303 | } | |
304 | ||
cfd73a4e | 305 | const Char_type* str = this->stringpool_.add(p, true, NULL); |
b8e6aad9 | 306 | |
730cdc88 ILT |
307 | off_t bytelen_with_null = (plen + 1) * sizeof(Char_type); |
308 | this->merged_strings_.push_back(Merged_string(object, shndx, i, str, | |
309 | bytelen_with_null)); | |
b8e6aad9 ILT |
310 | |
311 | p += plen + 1; | |
730cdc88 | 312 | i += bytelen_with_null; |
b8e6aad9 ILT |
313 | } |
314 | ||
315 | return true; | |
316 | } | |
317 | ||
318 | // Set the final data size of a merged string section. This is where | |
319 | // we finalize the mappings from the input sections to the output | |
320 | // section. | |
321 | ||
322 | template<typename Char_type> | |
323 | void | |
324 | Output_merge_string<Char_type>::do_set_address(uint64_t, off_t) | |
325 | { | |
326 | this->stringpool_.set_string_offsets(); | |
327 | ||
42e3fe0d ILT |
328 | for (typename Merged_strings::const_iterator p = |
329 | this->merged_strings_.begin(); | |
330 | p != this->merged_strings_.end(); | |
b8e6aad9 | 331 | ++p) |
730cdc88 | 332 | this->add_mapping(p->object, p->shndx, p->offset, p->length, |
42e3fe0d | 333 | this->stringpool_.get_offset(p->string)); |
b8e6aad9 ILT |
334 | |
335 | this->set_data_size(this->stringpool_.get_strtab_size()); | |
336 | ||
337 | // Save some memory. | |
42e3fe0d | 338 | this->merged_strings_.clear(); |
b8e6aad9 ILT |
339 | } |
340 | ||
341 | // Write out a merged string section. | |
342 | ||
343 | template<typename Char_type> | |
344 | void | |
345 | Output_merge_string<Char_type>::do_write(Output_file* of) | |
346 | { | |
347 | this->stringpool_.write(of, this->offset()); | |
348 | } | |
349 | ||
350 | // Instantiate the templates we need. | |
351 | ||
352 | template | |
353 | class Output_merge_string<char>; | |
354 | ||
355 | template | |
356 | class Output_merge_string<uint16_t>; | |
357 | ||
358 | template | |
359 | class Output_merge_string<uint32_t>; | |
360 | ||
361 | } // End namespace gold. |