aboutsummaryrefslogtreecommitdiff
path: root/gold/merge.cc
blob: fc6bffb2e1ed17e566425f1c102aed73c62ed05f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
// merge.cc -- handle section merging for gold

// Copyright 2006, 2007 Free Software Foundation, Inc.
// Written by Ian Lance Taylor <iant@google.com>.

// This file is part of gold.

// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
// MA 02110-1301, USA.

#include "gold.h"

#include <cstdlib>
#include <algorithm>

#include "merge.h"

namespace gold
{

// For each object with merge sections, we store an Object_merge_map.
// This is used to map locations in input sections to a merged output
// section.  The output section itself is not recorded here--it can be
// found in the map_to_output_ field of the Object.

class Object_merge_map
{
 public:
  Object_merge_map()
    : first_shnum_(-1U), first_map_(),
      second_shnum_(-1U), second_map_(),
      section_merge_maps_()
  { }

  ~Object_merge_map();

  // Add a mapping for MERGE_MAP, for the bytes from OFFSET to OFFSET
  // + LENGTH in the input section SHNDX to OUTPUT_OFFSET in the
  // output section.  An OUTPUT_OFFSET of -1 means that the bytes are
  // discarded.
  void
  add_mapping(const Merge_map*, unsigned int shndx, section_offset_type offset,
	      section_size_type length, section_offset_type output_offset);

  // Get the output offset for an input address in MERGE_MAP.  The
  // input address is at offset OFFSET in section SHNDX.  This sets
  // *OUTPUT_OFFSET to the offset in the output section; this will be
  // -1 if the bytes are not being copied to the output.  This returns
  // true if the mapping is known, false otherwise.
  bool
  get_output_offset(const Merge_map*, unsigned int shndx,
		    section_offset_type offset,
		    section_offset_type *output_offset);

 private:
  // Map input section offsets to a length and an output section
  // offset.  An output section offset of -1 means that this part of
  // the input section is being discarded.
  struct Input_merge_entry
  {
    // The offset in the input section.
    section_offset_type input_offset;
    // The length.
    section_size_type length;
    // The offset in the output section.
    section_offset_type output_offset;
  };

  // A less-than comparison routine for Input_merge_entry.
  struct Input_merge_compare
  {
    bool
    operator()(const Input_merge_entry& i1, const Input_merge_entry& i2) const
    { return i1.input_offset < i2.input_offset; }
  };

  // A list of entries for a particular section.
  struct Input_merge_map
  {
    // The Merge_map for this section.
    const Merge_map* merge_map;
    // The list of mappings.
    std::vector<Input_merge_entry> entries;
    // Whether the ENTRIES field is sorted by input_offset.
    bool sorted;

    Input_merge_map()
      : merge_map(NULL), entries(), sorted(true)
    { }
  };

  // Map input section indices to merge maps.
  typedef std::map<unsigned int, Input_merge_map*> Section_merge_maps;

  // Return a pointer to the Input_merge_map to use for the input
  // section SHNDX, or NULL.
  Input_merge_map*
  get_input_merge_map(unsigned int shndx);

  // Get or make the the Input_merge_map to use for the section SHNDX
  // with MERGE_MAP.
  Input_merge_map*
  get_or_make_input_merge_map(const Merge_map* merge_map, unsigned int shndx);

  // Any given object file will normally only have a couple of input
  // sections with mergeable contents.  So we keep the first two input
  // section numbers inline, and push any further ones into a map.  A
  // value of -1U in first_shnum_ or second_shnum_ means that we don't
  // have a corresponding entry.
  unsigned int first_shnum_;
  Input_merge_map first_map_;
  unsigned int second_shnum_;
  Input_merge_map second_map_;
  Section_merge_maps section_merge_maps_;
};

// Destructor.

Object_merge_map::~Object_merge_map()
{
  for (Section_merge_maps::iterator p = this->section_merge_maps_.begin();
       p != this->section_merge_maps_.end();
       ++p)
    delete p->second;
}

// Get the Input_merge_map to use for an input section, or NULL.

Object_merge_map::Input_merge_map*
Object_merge_map::get_input_merge_map(unsigned int shndx)
{
  gold_assert(shndx != -1U);
  if (shndx == this->first_shnum_)
    return &this->first_map_;
  if (shndx == this->second_shnum_)
    return &this->second_map_;
  Section_merge_maps::const_iterator p = this->section_merge_maps_.find(shndx);
  if (p != this->section_merge_maps_.end())
    return p->second;
  return NULL;
}

// Get or create the Input_merge_map to use for an input section.

Object_merge_map::Input_merge_map*
Object_merge_map::get_or_make_input_merge_map(const Merge_map* merge_map,
					      unsigned int shndx)
{
  Input_merge_map* map = this->get_input_merge_map(shndx);
  if (map != NULL)
    {
      // For a given input section in a given object, every mapping
      // must be donw with the same Merge_map.
      gold_assert(map->merge_map == merge_map);
      return map;
    }

  // We need to create a new entry.
  if (this->first_shnum_ == -1U)
    {
      this->first_shnum_ = shndx;
      this->first_map_.merge_map = merge_map;
      return &this->first_map_;
    }
  if (this->second_shnum_ == -1U)
    {
      this->second_shnum_ = shndx;
      this->second_map_.merge_map = merge_map;
      return &this->second_map_;
    }

  Input_merge_map* new_map = new Input_merge_map;
  new_map->merge_map = merge_map;
  this->section_merge_maps_[shndx] = new_map;
  return new_map;
}

// Add a mapping.

void
Object_merge_map::add_mapping(const Merge_map* merge_map, unsigned int shndx,
			      section_offset_type input_offset,
			      section_size_type length,
			      section_offset_type output_offset)
{
  Input_merge_map* map = this->get_or_make_input_merge_map(merge_map, shndx);

  // Try to merge the new entry in the last one we saw.
  if (!map->entries.empty())
    {
      Input_merge_entry& entry(map->entries.back());

      // Use section_size_type to avoid signed/unsigned warnings.
      section_size_type input_offset_u = input_offset;
      section_size_type output_offset_u = output_offset;

      // If this entry is not in order, we need to sort the vector
      // before looking anything up.
      if (input_offset_u < entry.input_offset + entry.length)
	{
	  gold_assert(input_offset < entry.input_offset);
	  gold_assert(input_offset_u + length
		      <= static_cast<section_size_type>(entry.input_offset));
	  map->sorted = false;
	}
      else if (entry.input_offset + entry.length == input_offset_u
	       && (output_offset == -1
		   ? entry.output_offset == -1
		   : entry.output_offset + entry.length == output_offset_u))
	{
	  entry.length += length;
	  return;
	}
    }

  Input_merge_entry entry;
  entry.input_offset = input_offset;
  entry.length = length;
  entry.output_offset = output_offset;
  map->entries.push_back(entry);
}

// Get the output offset for an input address.

inline bool
Object_merge_map::get_output_offset(const Merge_map* merge_map,
				    unsigned int shndx,
				    section_offset_type input_offset,
				    section_offset_type *output_offset)
{
  Input_merge_map* map = this->get_input_merge_map(shndx);
  if (map == NULL || map->merge_map != merge_map)
    return false;

  if (!map->sorted)
    {
      std::sort(map->entries.begin(), map->entries.end(),
		Input_merge_compare());
      map->sorted = true;
    }

  Input_merge_entry entry;
  entry.input_offset = input_offset;
  std::vector<Input_merge_entry>::const_iterator p =
    std::lower_bound(map->entries.begin(), map->entries.end(),
		     entry, Input_merge_compare());
  if (p == map->entries.end() || p->input_offset > input_offset)
    {
      if (p == map->entries.begin())
	return false;
      --p;
      gold_assert(p->input_offset <= input_offset);
    }

  if (input_offset - p->input_offset
      >= static_cast<section_offset_type>(p->length))
    return false;

  *output_offset = p->output_offset;
  if (*output_offset != -1)
    *output_offset += (input_offset - p->input_offset);
  return true;
}

// Class Merge_map.

// Add a mapping for the bytes from OFFSET to OFFSET + LENGTH in input
// section SHNDX in object OBJECT to an OUTPUT_OFFSET in a merged
// output section.

void
Merge_map::add_mapping(Relobj* object, unsigned int shndx,
		       section_offset_type offset, section_size_type length,
		       section_offset_type output_offset)
{
  Object_merge_map* object_merge_map = object->merge_map();
  if (object_merge_map == NULL)
    {
      object_merge_map = new Object_merge_map();
      object->set_merge_map(object_merge_map);
    }

  object_merge_map->add_mapping(this, shndx, offset, length, output_offset);
}

// Return the output offset for an input address.  The input address
// is at offset OFFSET in section SHNDX in OBJECT.  This sets
// *OUTPUT_OFFSET to the offset in the output section.  This returns
// true if the mapping is known, false otherwise.

bool
Merge_map::get_output_offset(const Relobj* object, unsigned int shndx,
			     section_offset_type offset,
			     section_offset_type* output_offset) const
{
  Object_merge_map* object_merge_map = object->merge_map();
  if (object_merge_map == NULL)
    return false;
  return object_merge_map->get_output_offset(this, shndx, offset,
					     output_offset);
}

// Class Output_merge_base.

// Return the output offset for an input offset.  The input address is
// at offset OFFSET in section SHNDX in OBJECT.  If we know the
// offset, set *POUTPUT and return true.  Otherwise return false.

bool
Output_merge_base::do_output_offset(const Relobj* object,
				    unsigned int shndx,
				    section_offset_type offset,
				    section_offset_type* poutput) const
{
  return this->merge_map_.get_output_offset(object, shndx, offset, poutput);
}

// Class Output_merge_data.

// Compute the hash code for a fixed-size constant.

size_t
Output_merge_data::Merge_data_hash::operator()(Merge_data_key k) const
{
  const unsigned char* p = this->pomd_->constant(k);
  section_size_type entsize =
    convert_to_section_size_type(this->pomd_->entsize());

  // Fowler/Noll/Vo (FNV) hash (type FNV-1a).
  if (sizeof(size_t) == 8)
    {
      size_t result = static_cast<size_t>(14695981039346656037ULL);
      for (section_size_type i = 0; i < entsize; ++i)
	{
	  result &= (size_t) *p++;
	  result *= 1099511628211ULL;
	}
      return result;
    }
  else
    {
      size_t result = 2166136261UL;
      for (section_size_type i = 0; i < entsize; ++i)
	{
	  result ^= (size_t) *p++;
	  result *= 16777619UL;
	}
      return result;
    }
}

// Return whether one hash table key equals another.

bool
Output_merge_data::Merge_data_eq::operator()(Merge_data_key k1,
					     Merge_data_key k2) const
{
  const unsigned char* p1 = this->pomd_->constant(k1);
  const unsigned char* p2 = this->pomd_->constant(k2);
  return memcmp(p1, p2, this->pomd_->entsize()) == 0;
}

// Add a constant to the end of the section contents.

void
Output_merge_data::add_constant(const unsigned char* p)
{
  section_size_type entsize = convert_to_section_size_type(this->entsize());
  section_size_type addralign =
    convert_to_section_size_type(this->addralign());
  section_size_type addsize = std::max(entsize, addralign);
  if (this->len_ + addsize > this->alc_)
    {
      if (this->alc_ == 0)
	this->alc_ = 128 * addsize;
      else
	this->alc_ *= 2;
      this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->alc_));
      if (this->p_ == NULL)
	gold_nomem();
    }

  memcpy(this->p_ + this->len_, p, entsize);
  if (addsize > entsize)
    memset(this->p_ + this->len_ + entsize, 0, addsize - entsize);
  this->len_ += addsize;
}

// Add the input section SHNDX in OBJECT to a merged output section
// which holds fixed length constants.  Return whether we were able to
// handle the section; if not, it will be linked as usual without
// constant merging.

bool
Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
{
  section_size_type len;
  const unsigned char* p = object->section_contents(shndx, &len, false);

  section_size_type entsize = convert_to_section_size_type(this->entsize());

  if (len % entsize != 0)
    return false;

  this->input_count_ += len / entsize;

  for (section_size_type i = 0; i < len; i += entsize, p += entsize)
    {
      // Add the constant to the section contents.  If we find that it
      // is already in the hash table, we will remove it again.
      Merge_data_key k = this->len_;
      this->add_constant(p);

      std::pair<Merge_data_hashtable::iterator, bool> ins =
	this->hashtable_.insert(k);

      if (!ins.second)
	{
	  // Key was already present.  Remove the copy we just added.
	  this->len_ -= entsize;
	  k = *ins.first;
	}

      // Record the offset of this constant in the output section.
      this->add_mapping(object, shndx, i, entsize, k);
    }

  return true;
}

// Set the final data size in a merged output section with fixed size
// constants.

void
Output_merge_data::set_final_data_size()
{
  // Release the memory we don't need.
  this->p_ = static_cast<unsigned char*>(realloc(this->p_, this->len_));
  gold_assert(this->p_ != NULL);
  this->set_data_size(this->len_);
}

// Write the data of a merged output section with fixed size constants
// to the file.

void
Output_merge_data::do_write(Output_file* of)
{
  of->write(this->offset(), this->p_, this->len_);
}

// Write the data to a buffer.

void
Output_merge_data::do_write_to_buffer(unsigned char* buffer)
{
  memcpy(buffer, this->p_, this->len_);
}

// Print merge stats to stderr.

void
Output_merge_data::do_print_merge_stats(const char* section_name)
{
  fprintf(stderr,
	  _("%s: %s merged constants size: %lu; input: %zu; output: %zu\n"),
	  program_name, section_name,
	  static_cast<unsigned long>(this->entsize()),
	  this->input_count_, this->hashtable_.size());
}

// Class Output_merge_string.

// Add an input section to a merged string section.

template<typename Char_type>
bool
Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
						     unsigned int shndx)
{
  section_size_type len;
  const unsigned char* pdata = object->section_contents(shndx, &len, false);

  const Char_type* p = reinterpret_cast<const Char_type*>(pdata);
  const Char_type* pend = p + len;

  if (len % sizeof(Char_type) != 0)
    {
      object->error(_("mergeable string section length not multiple of "
		      "character size"));
      return false;
    }

  size_t count = 0;

  // The index I is in bytes, not characters.
  section_size_type i = 0;
  while (i < len)
    {
      const Char_type* pl;
      for (pl = p; *pl != 0; ++pl)
	{
	  if (pl >= pend)
	    {
	      object->error(_("entry in mergeable string section "
			      "not null terminated"));
	      break;
	    }
	}

      Stringpool::Key key;
      const Char_type* str = this->stringpool_.add_with_length(p, pl - p, true,
							       &key);

      section_size_type bytelen_with_null = ((pl - p) + 1) * sizeof(Char_type);
      this->merged_strings_.push_back(Merged_string(object, shndx, i, str,
						    bytelen_with_null, key));

      p = pl + 1;
      i += bytelen_with_null;
      ++count;
    }

  this->input_count_ += count;

  return true;
}

// Finalize the mappings from the input sections to the output
// section, and return the final data size.

template<typename Char_type>
section_size_type
Output_merge_string<Char_type>::finalize_merged_data()
{
  this->stringpool_.set_string_offsets();

  for (typename Merged_strings::const_iterator p =
	 this->merged_strings_.begin();
       p != this->merged_strings_.end();
       ++p)
    {
      section_offset_type offset =
	this->stringpool_.get_offset_from_key(p->stringpool_key);
      this->add_mapping(p->object, p->shndx, p->offset, p->length, offset);
    }

  // Save some memory.
  this->merged_strings_.clear();

  return this->stringpool_.get_strtab_size();
}

template<typename Char_type>
void
Output_merge_string<Char_type>::set_final_data_size()
{
  const off_t final_data_size = this->finalize_merged_data();
  this->set_data_size(final_data_size);
}

// Write out a merged string section.

template<typename Char_type>
void
Output_merge_string<Char_type>::do_write(Output_file* of)
{
  this->stringpool_.write(of, this->offset());
}

// Write a merged string section to a buffer.

template<typename Char_type>
void
Output_merge_string<Char_type>::do_write_to_buffer(unsigned char* buffer)
{
  this->stringpool_.write_to_buffer(buffer, this->data_size());
}

// Return the name of the types of string to use with
// do_print_merge_stats.

template<typename Char_type>
const char*
Output_merge_string<Char_type>::string_name()
{
  gold_unreachable();
  return NULL;
}

template<>
const char*
Output_merge_string<char>::string_name()
{
  return "strings";
}

template<>
const char*
Output_merge_string<uint16_t>::string_name()
{
  return "16-bit strings";
}

template<>
const char*
Output_merge_string<uint32_t>::string_name()
{
  return "32-bit strings";
}

// Print merge stats to stderr.

template<typename Char_type>
void
Output_merge_string<Char_type>::do_print_merge_stats(const char* section_name)
{
  char buf[200];
  snprintf(buf, sizeof buf, "%s merged %s", section_name, this->string_name());
  fprintf(stderr, _("%s: %s input: %zu\n"),
	  program_name, buf, this->input_count_);
  this->stringpool_.print_stats(buf);
}

// Instantiate the templates we need.

template
class Output_merge_string<char>;

template
class Output_merge_string<uint16_t>;

template
class Output_merge_string<uint32_t>;

} // End namespace gold.