Annotation of src/external/gpl3/binutils.old/dist/gold/merge.h, Revision 1.6
1.1 christos 1: // merge.h -- handle section merging for gold -*- C++ -*-
2:
1.6 ! christos 3: // Copyright (C) 2006-2018 Free Software Foundation, Inc.
1.1 christos 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: #ifndef GOLD_MERGE_H
24: #define GOLD_MERGE_H
25:
26: #include <climits>
27: #include <map>
28: #include <vector>
29:
30: #include "stringpool.h"
31: #include "output.h"
32:
33: namespace gold
34: {
35:
36: // For each object with merge sections, we store an Object_merge_map.
37: // This is used to map locations in input sections to a merged output
38: // section. The output section itself is not recorded here--it can be
39: // found in the output_sections_ field of the Object.
40:
41: class Object_merge_map
42: {
43: public:
44: Object_merge_map()
1.3 christos 45: : section_merge_maps_()
1.1 christos 46: { }
47:
48: ~Object_merge_map();
49:
50: // Add a mapping for MERGE_MAP, for the bytes from OFFSET to OFFSET
51: // + LENGTH in the input section SHNDX to OUTPUT_OFFSET in the
52: // output section. An OUTPUT_OFFSET of -1 means that the bytes are
53: // discarded. OUTPUT_OFFSET is relative to the start of the merged
54: // data in the output section.
55: void
1.3 christos 56: add_mapping(const Output_section_data*, unsigned int shndx,
57: section_offset_type offset, section_size_type length,
58: section_offset_type output_offset);
1.1 christos 59:
60: // Get the output offset for an input address. MERGE_MAP is the map
61: // we are looking for, or NULL if we don't care. The input address
62: // is at offset OFFSET in section SHNDX. This sets *OUTPUT_OFFSET
63: // to the offset in the output section; this will be -1 if the bytes
64: // are not being copied to the output. This returns true if the
65: // mapping is known, false otherwise. *OUTPUT_OFFSET is relative to
66: // the start of the merged data in the output section.
67: bool
1.3 christos 68: get_output_offset(unsigned int shndx,
1.1 christos 69: section_offset_type offset,
70: section_offset_type* output_offset);
71:
1.3 christos 72: const Output_section_data*
73: find_merge_section(unsigned int shndx) const;
1.1 christos 74:
75: // Initialize an mapping from input offsets to output addresses for
76: // section SHNDX. STARTING_ADDRESS is the output address of the
77: // merged section.
78: template<int size>
79: void
80: initialize_input_to_output_map(
81: unsigned int shndx,
82: typename elfcpp::Elf_types<size>::Elf_Addr starting_address,
83: Unordered_map<section_offset_type,
84: typename elfcpp::Elf_types<size>::Elf_Addr>*);
85:
86: // Map input section offsets to a length and an output section
87: // offset. An output section offset of -1 means that this part of
88: // the input section is being discarded.
89: struct Input_merge_entry
90: {
91: // The offset in the input section.
92: section_offset_type input_offset;
93: // The length.
94: section_size_type length;
95: // The offset in the output section.
96: section_offset_type output_offset;
97: };
98:
99: // A list of entries for a particular input section.
100: struct Input_merge_map
101: {
1.3 christos 102: void add_mapping(section_offset_type input_offset, section_size_type length,
103: section_offset_type output_offset);
104:
1.1 christos 105: typedef std::vector<Input_merge_entry> Entries;
106:
107: // We store these with the Relobj, and we look them up by input
108: // section. It is possible to have two different merge maps
109: // associated with a single output section. For example, this
110: // happens routinely with .rodata, when merged string constants
111: // and merged fixed size constants are both put into .rodata. The
112: // output offset that we store is not the offset from the start of
113: // the output section; it is the offset from the start of the
114: // merged data in the output section. That means that the caller
115: // is going to add the offset of the merged data within the output
116: // section, which means that the caller needs to know which set of
117: // merged data it found the entry in. So it's not enough to find
118: // this data based on the input section and the output section; we
119: // also have to find it based on a set of merged data in the
120: // output section. In order to verify that we are looking at the
121: // right data, we store a pointer to the Merge_map here, and we
122: // pass in a pointer when looking at the data. If we are asked to
123: // look up information for a different Merge_map, we report that
124: // we don't have it, rather than trying a lookup and returning an
125: // answer which will receive the wrong offset.
1.3 christos 126: const Output_section_data* output_data;
1.1 christos 127: // The list of mappings.
128: Entries entries;
129: // Whether the ENTRIES field is sorted by input_offset.
130: bool sorted;
131:
132: Input_merge_map()
1.3 christos 133: : output_data(NULL), entries(), sorted(true)
1.1 christos 134: { }
135: };
136:
137: // Get or make the Input_merge_map to use for the section SHNDX
138: // with MERGE_MAP.
139: Input_merge_map*
1.3 christos 140: get_or_make_input_merge_map(const Output_section_data* merge_map,
141: unsigned int shndx);
1.1 christos 142:
1.3 christos 143: private:
144: // A less-than comparison routine for Input_merge_entry.
145: struct Input_merge_compare
146: {
147: bool
148: operator()(const Input_merge_entry& i1, const Input_merge_entry& i2) const
149: { return i1.input_offset < i2.input_offset; }
150: };
1.1 christos 151:
1.3 christos 152: // Map input section indices to merge maps.
153: typedef std::vector<std::pair<unsigned int, Input_merge_map*> >
154: Section_merge_maps;
1.1 christos 155:
1.3 christos 156: // Return a pointer to the Input_merge_map to use for the input
157: // section SHNDX, or NULL.
158: const Input_merge_map*
159: get_input_merge_map(unsigned int shndx) const;
1.1 christos 160:
1.3 christos 161: Input_merge_map *
162: get_input_merge_map(unsigned int shndx) {
163: return const_cast<Input_merge_map *>(static_cast<const Object_merge_map *>(
164: this)->get_input_merge_map(shndx));
165: }
1.1 christos 166:
1.3 christos 167: Section_merge_maps section_merge_maps_;
1.1 christos 168: };
169:
170: // A general class for SHF_MERGE data, to hold functions shared by
171: // fixed-size constant data and string data.
172:
173: class Output_merge_base : public Output_section_data
174: {
175: public:
176: Output_merge_base(uint64_t entsize, uint64_t addralign)
1.3 christos 177: : Output_section_data(addralign), entsize_(entsize),
1.1 christos 178: keeps_input_sections_(false), first_relobj_(NULL), first_shndx_(-1),
179: input_sections_()
180: { }
181:
182: // Return the entry size.
183: uint64_t
184: entsize() const
185: { return this->entsize_; }
186:
187: // Whether this is a merge string section. This is only true of
188: // Output_merge_string.
189: bool
190: is_string()
191: { return this->do_is_string(); }
192:
193: // Whether this keeps input sections.
194: bool
195: keeps_input_sections() const
196: { return this->keeps_input_sections_; }
197:
198: // Set the keeps-input-sections flag. This is virtual so that sub-classes
199: // can perform additional checks.
200: void
201: set_keeps_input_sections()
202: { this->do_set_keeps_input_sections(); }
203:
204: // Return the object of the first merged input section. This used
205: // for script processing. This is NULL if merge section is empty.
206: Relobj*
207: first_relobj() const
208: { return this->first_relobj_; }
209:
210: // Return the section index of the first merged input section. This
211: // is used for script processing. This is valid only if merge section
212: // is not valid.
213: unsigned int
214: first_shndx() const
215: {
216: gold_assert(this->first_relobj_ != NULL);
217: return this->first_shndx_;
218: }
219:
220: // Set of merged input sections.
221: typedef Unordered_set<Section_id, Section_id_hash> Input_sections;
222:
223: // Beginning of merged input sections.
224: Input_sections::const_iterator
225: input_sections_begin() const
226: {
227: gold_assert(this->keeps_input_sections_);
228: return this->input_sections_.begin();
229: }
230:
231: // Beginning of merged input sections.
232: Input_sections::const_iterator
233: input_sections_end() const
234: {
235: gold_assert(this->keeps_input_sections_);
236: return this->input_sections_.end();
237: }
238:
239: protected:
240: // Return the output offset for an input offset.
241: bool
242: do_output_offset(const Relobj* object, unsigned int shndx,
243: section_offset_type offset,
244: section_offset_type* poutput) const;
245:
246: // This may be overridden by the child class.
247: virtual bool
248: do_is_string()
249: { return false; }
250:
251: // This may be overridden by the child class.
252: virtual void
253: do_set_keeps_input_sections()
254: { this->keeps_input_sections_ = true; }
255:
256: // Record the merged input section for script processing.
257: void
258: record_input_section(Relobj* relobj, unsigned int shndx);
259:
260: private:
261: // The entry size. For fixed-size constants, this is the size of
262: // the constants. For strings, this is the size of a character.
263: uint64_t entsize_;
264: // Whether we keep input sections.
265: bool keeps_input_sections_;
266: // Object of the first merged input section. We use this for script
267: // processing.
268: Relobj* first_relobj_;
269: // Section index of the first merged input section.
270: unsigned int first_shndx_;
271: // Input sections. We only keep them is keeps_input_sections_ is true.
272: Input_sections input_sections_;
273: };
274:
275: // Handle SHF_MERGE sections with fixed-size constant data.
276:
277: class Output_merge_data : public Output_merge_base
278: {
279: public:
280: Output_merge_data(uint64_t entsize, uint64_t addralign)
281: : Output_merge_base(entsize, addralign), p_(NULL), len_(0), alc_(0),
282: input_count_(0),
283: hashtable_(128, Merge_data_hash(this), Merge_data_eq(this))
284: { }
285:
286: protected:
287: // Add an input section.
288: bool
289: do_add_input_section(Relobj* object, unsigned int shndx);
290:
291: // Set the final data size.
292: void
293: set_final_data_size();
294:
295: // Write the data to the file.
296: void
297: do_write(Output_file*);
298:
299: // Write the data to a buffer.
300: void
301: do_write_to_buffer(unsigned char*);
302:
303: // Write to a map file.
304: void
305: do_print_to_mapfile(Mapfile* mapfile) const
306: { mapfile->print_output_data(this, _("** merge constants")); }
307:
308: // Print merge stats to stderr.
309: void
310: do_print_merge_stats(const char* section_name);
311:
312: // Set keeps-input-sections flag.
313: void
314: do_set_keeps_input_sections()
315: {
316: gold_assert(this->input_count_ == 0);
317: Output_merge_base::do_set_keeps_input_sections();
318: }
319:
320: private:
321: // We build a hash table of the fixed-size constants. Each constant
322: // is stored as a pointer into the section data we are accumulating.
323:
324: // A key in the hash table. This is an offset in the section
325: // contents we are building.
326: typedef section_offset_type Merge_data_key;
327:
328: // Compute the hash code. To do this we need a pointer back to the
329: // object holding the data.
330: class Merge_data_hash
331: {
332: public:
333: Merge_data_hash(const Output_merge_data* pomd)
334: : pomd_(pomd)
335: { }
336:
337: size_t
338: operator()(Merge_data_key) const;
339:
340: private:
341: const Output_merge_data* pomd_;
342: };
343:
344: friend class Merge_data_hash;
345:
346: // Compare two entries in the hash table for equality. To do this
347: // we need a pointer back to the object holding the data. Note that
348: // we now have a pointer to the object stored in two places in the
349: // hash table. Fixing this would require specializing the hash
350: // table, which would be hard to do portably.
351: class Merge_data_eq
352: {
353: public:
354: Merge_data_eq(const Output_merge_data* pomd)
355: : pomd_(pomd)
356: { }
357:
358: bool
359: operator()(Merge_data_key k1, Merge_data_key k2) const;
360:
361: private:
362: const Output_merge_data* pomd_;
363: };
364:
365: friend class Merge_data_eq;
366:
367: // The type of the hash table.
368: typedef Unordered_set<Merge_data_key, Merge_data_hash, Merge_data_eq>
369: Merge_data_hashtable;
370:
371: // Given a hash table key, which is just an offset into the section
372: // data, return a pointer to the corresponding constant.
373: const unsigned char*
374: constant(Merge_data_key k) const
375: {
376: gold_assert(k >= 0 && k < static_cast<section_offset_type>(this->len_));
377: return this->p_ + k;
378: }
379:
380: // Add a constant to the output.
381: void
382: add_constant(const unsigned char*);
383:
384: // The accumulated data.
385: unsigned char* p_;
386: // The length of the accumulated data.
387: section_size_type len_;
388: // The size of the allocated buffer.
389: section_size_type alc_;
390: // The number of entries seen in input files.
391: size_t input_count_;
392: // The hash table.
393: Merge_data_hashtable hashtable_;
394: };
395:
396: // Handle SHF_MERGE sections with string data. This is a template
397: // based on the type of the characters in the string.
398:
399: template<typename Char_type>
400: class Output_merge_string : public Output_merge_base
401: {
402: public:
403: Output_merge_string(uint64_t addralign)
1.3 christos 404: : Output_merge_base(sizeof(Char_type), addralign), stringpool_(addralign),
1.1 christos 405: merged_strings_lists_(), input_count_(0), input_size_(0)
406: {
407: this->stringpool_.set_no_zero_null();
408: }
409:
410: protected:
411: // Add an input section.
412: bool
413: do_add_input_section(Relobj* object, unsigned int shndx);
414:
415: // Do all the final processing after the input sections are read in.
416: // Returns the final data size.
417: section_size_type
418: finalize_merged_data();
419:
420: // Set the final data size.
421: void
422: set_final_data_size();
423:
424: // Write the data to the file.
425: void
426: do_write(Output_file*);
427:
428: // Write the data to a buffer.
429: void
430: do_write_to_buffer(unsigned char*);
431:
432: // Write to a map file.
433: void
434: do_print_to_mapfile(Mapfile* mapfile) const
435: { mapfile->print_output_data(this, _("** merge strings")); }
436:
437: // Print merge stats to stderr.
438: void
439: do_print_merge_stats(const char* section_name);
440:
441: // Writes the stringpool to a buffer.
442: void
443: stringpool_to_buffer(unsigned char* buffer, section_size_type buffer_size)
444: { this->stringpool_.write_to_buffer(buffer, buffer_size); }
445:
446: // Clears all the data in the stringpool, to save on memory.
447: void
448: clear_stringpool()
449: { this->stringpool_.clear(); }
450:
451: // Whether this is a merge string section.
452: virtual bool
453: do_is_string()
454: { return true; }
455:
456: // Set keeps-input-sections flag.
457: void
458: do_set_keeps_input_sections()
459: {
460: gold_assert(this->input_count_ == 0);
461: Output_merge_base::do_set_keeps_input_sections();
462: }
463:
464: private:
465: // The name of the string type, for stats.
466: const char*
467: string_name();
468:
469: // As we see input sections, we build a mapping from object, section
470: // index and offset to strings.
471: struct Merged_string
472: {
473: // The offset in the input section.
474: section_offset_type offset;
475: // The key in the Stringpool.
476: Stringpool::Key stringpool_key;
477:
478: Merged_string(section_offset_type offseta, Stringpool::Key stringpool_keya)
479: : offset(offseta), stringpool_key(stringpool_keya)
480: { }
481: };
482:
483: typedef std::vector<Merged_string> Merged_strings;
484:
485: struct Merged_strings_list
486: {
487: // The input object where the strings were found.
488: Relobj* object;
489: // The input section in the input object.
490: unsigned int shndx;
491: // The list of merged strings.
492: Merged_strings merged_strings;
493:
494: Merged_strings_list(Relobj* objecta, unsigned int shndxa)
495: : object(objecta), shndx(shndxa), merged_strings()
496: { }
497: };
498:
499: typedef std::vector<Merged_strings_list*> Merged_strings_lists;
500:
501: // As we see the strings, we add them to a Stringpool.
502: Stringpool_template<Char_type> stringpool_;
503: // Map from a location in an input object to an entry in the
504: // Stringpool.
505: Merged_strings_lists merged_strings_lists_;
506: // The number of entries seen in input files.
507: size_t input_count_;
508: // The total size of input sections.
509: size_t input_size_;
510: };
511:
512: } // End namespace gold.
513:
514: #endif // !defined(GOLD_MERGE_H)
CVSweb <webmaster@jp.NetBSD.org>