src/ld/LinkEdit.hpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-*
   2  *
   3  * Copyright (c) 2009-2010 Apple Inc. All rights reserved.
   4  *
   5  * @APPLE_LICENSE_HEADER_START@
   6  *
   7  * This file contains Original Code and/or Modifications of Original Code
   8  * as defined in and that are subject to the Apple Public Source License
   9  * Version 2.0 (the 'License'). You may not use this file except in
  10  * compliance with the License. Please obtain a copy of the License at
  11  * http://www.opensource.apple.com/apsl/ and read it before using this
  12  * file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  19  * Please see the License for the specific language governing rights and
  20  * limitations under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24
  25 #ifndef __LINKEDIT_HPP__
  26 #define __LINKEDIT_HPP__
  27
  28 #include <stdlib.h>
  29 #include <sys/types.h>
  30 #include <errno.h>
  31 #include <limits.h>
  32 #include <unistd.h>
  33
  34 #include <vector>
  35
  36 #include "Options.h"
  37 #include "ld.hpp"
  38 #include "Architectures.hpp"
  39 #include "MachOFileAbstraction.hpp"
  40
  41 namespace ld {
  42 namespace tool {
  43
  44 class ByteStream {
  45 private:
  46         std::vector<uint8_t>            _data;
  47 public:
  48         std::vector<uint8_t>& bytes() { return _data; }
  49         unsigned long size() const { return _data.size(); }
  50         void reserve(unsigned long l) { _data.reserve(l); }
  51         const uint8_t* start() const { return &_data[0]; }
  52
  53         void append_uleb128(uint64_t value) {
  54                 uint8_t byte;
  55                 do {
  56                         byte = value & 0x7F;
  57                         value &= ~0x7F;
  58                         if ( value != 0 )
  59                                 byte |= 0x80;
  60                         _data.push_back(byte);
  61                         value = value >> 7;
  62                 } while( byte >= 0x80 );
  63         }
  64
  65         void append_sleb128(int64_t value) {
  66                 bool isNeg = ( value < 0 );
  67                 uint8_t byte;
  68                 bool more;
  69                 do {
  70                         byte = value & 0x7F;
  71                         value = value >> 7;
  72                         if ( isNeg )
  73                                 more = ( (value != -1) || ((byte & 0x40) == 0) );
  74                         else
  75                                 more = ( (value != 0) || ((byte & 0x40) != 0) );
  76                         if ( more )
  77                                 byte |= 0x80;
  78                         _data.push_back(byte);
  79                 }
  80                 while( more );
  81         }
  82
  83         void append_string(const char* str) {
  84                 for (const char* s = str; *s != '\0'; ++s)
  85                         _data.push_back(*s);
  86                 _data.push_back('\0');
  87         }
  88
  89         void append_byte(uint8_t byte) {
  90                 _data.push_back(byte);
  91         }
  92
  93         static unsigned int     uleb128_size(uint64_t value) {
  94                 uint32_t result = 0;
  95                 do {
  96                         value = value >> 7;
  97                         ++result;
  98                 } while ( value != 0 );
  99                 return result;
 100         }
 101
 102         void pad_to_size(unsigned int alignment) {
 103                 while ( (_data.size() % alignment) != 0 )
 104                         _data.push_back(0);
 105         }
 106 };
 107
 108
 109 class LinkEditAtom : public ld::Atom
 110 {
 111 public:
 112
 113         // overrides of ld::Atom
 114         virtual ld::File*                                                       file() const            { return NULL; }
 115         virtual bool                                                            translationUnitSource(const char** dir, const char** nm) const
 116                                                                                                                                         { return false; }
 117         virtual uint64_t                                                        objectAddress() const { return 0; }
 118         virtual uint64_t                                                        size() const;
 119         virtual void                                                            copyRawContent(uint8_t buffer[]) const;
 120
 121         virtual void                                                            encode() const = 0;
 122
 123                                                                                                 LinkEditAtom(const Options& opts, ld::Internal& state,
 124                                                                                                                                 OutputFile& writer, const ld::Section& sect,
 125                                                                                                                                 unsigned int pointerSize)
 126                                                                                                 : ld::Atom(sect, ld::Atom::definitionRegular,
 127                                                                                                                         ld::Atom::combineNever, ld::Atom::scopeTranslationUnit,
 128                                                                                                                         ld::Atom::typeUnclassified, ld::Atom::symbolTableNotIn,
 129                                                                                                                         false, false, false, ld::Atom::Alignment(log2(pointerSize))),
 130                                                                                                                 _options(opts), _state(state), _writer(writer),
 131                                                                                                                 _encoded(false) { }
 132 protected:
 133         const Options&                          _options;
 134         ld::Internal&                           _state;
 135         OutputFile&                                     _writer;
 136         mutable ByteStream                      _encodedData;
 137         mutable bool                            _encoded;
 138 };
 139
 140 uint64_t LinkEditAtom::size() const
 141 {
 142         assert(_encoded);
 143         return _encodedData.size();
 144 }
 145
 146 void LinkEditAtom::copyRawContent(uint8_t buffer[]) const
 147 {
 148         assert(_encoded);
 149         memcpy(buffer, _encodedData.start(), _encodedData.size());
 150 }
 151
 152
 153
 154
 155 template <typename A>
 156 class RebaseInfoAtom : public LinkEditAtom
 157 {
 158 public:
 159                                                                                                 RebaseInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 160                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { _encoded = true; }
 161
 162         // overrides of ld::Atom
 163         virtual const char*                                                     name() const            { return "rebase info"; }
 164         // overrides of LinkEditAtom
 165         virtual void                                                            encode() const;
 166
 167 private:
 168         struct rebase_tmp
 169         {
 170                 rebase_tmp(uint8_t op, uint64_t p1, uint64_t p2=0) : opcode(op), operand1(p1), operand2(p2) {}
 171                 uint8_t         opcode;
 172                 uint64_t        operand1;
 173                 uint64_t        operand2;
 174         };
 175
 176         typedef typename A::P                                           P;
 177         typedef typename A::P::E                                        E;
 178         typedef typename A::P::uint_t                           pint_t;
 179
 180         static ld::Section                      _s_section;
 181 };
 182
 183 template <typename A>
 184 ld::Section RebaseInfoAtom<A>::_s_section("__LINKEDIT", "__rebase", ld::Section::typeLinkEdit, true);
 185
 186
 187 template <typename A>
 188 void RebaseInfoAtom<A>::encode() const
 189 {
 190         // omit relocs if this was supposed to be PIE but PIE not possible
 191         if ( _options.positionIndependentExecutable() && this->_writer.pieDisabled )
 192                 return;
 193
 194         // sort rebase info by type, then address
 195         std::vector<OutputFile::RebaseInfo>& info = this->_writer._rebaseInfo;
 196         std::sort(info.begin(), info.end());
 197
 198         // convert to temp encoding that can be more easily optimized
 199         std::vector<rebase_tmp> mid;
 200         uint64_t curSegStart = 0;
 201         uint64_t curSegEnd = 0;
 202         uint32_t curSegIndex = 0;
 203         uint8_t type = 0;
 204         uint64_t address = (uint64_t)(-1);
 205         for (std::vector<OutputFile::RebaseInfo>::iterator it = info.begin(); it != info.end(); ++it) {
 206                 if ( type != it->_type ) {
 207                         mid.push_back(rebase_tmp(REBASE_OPCODE_SET_TYPE_IMM, it->_type));
 208                         type = it->_type;
 209                 }
 210                 if ( address != it->_address ) {
 211                         if ( (it->_address < curSegStart) || ( it->_address >= curSegEnd) ) {
 212                                 if ( ! this->_writer.findSegment(this->_state, it->_address, &curSegStart, &curSegEnd, &curSegIndex) )
 213                                         throw "binding address outside range of any segment";
 214                                 mid.push_back(rebase_tmp(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB, curSegIndex, it->_address - curSegStart));
 215                         }
 216                         else {
 217                                 mid.push_back(rebase_tmp(REBASE_OPCODE_ADD_ADDR_ULEB, it->_address-address));
 218                         }
 219                         address = it->_address;
 220                 }
 221                 mid.push_back(rebase_tmp(REBASE_OPCODE_DO_REBASE_ULEB_TIMES, 1));
 222                 address += sizeof(pint_t);
 223         }
 224         mid.push_back(rebase_tmp(REBASE_OPCODE_DONE, 0));
 225
 226         // optimize phase 1, compress packed runs of pointers
 227         rebase_tmp* dst = &mid[0];
 228         for (const rebase_tmp* src = &mid[0]; src->opcode != REBASE_OPCODE_DONE; ++src) {
 229                 if ( (src->opcode == REBASE_OPCODE_DO_REBASE_ULEB_TIMES) && (src->operand1 == 1) ) {
 230                         *dst = *src++;
 231                         while (src->opcode == REBASE_OPCODE_DO_REBASE_ULEB_TIMES ) {
 232                                 dst->operand1 += src->operand1;
 233                                 ++src;
 234                         }
 235                         --src;
 236                         ++dst;
 237                 }
 238                 else {
 239                         *dst++ = *src;
 240                 }
 241         }
 242         dst->opcode = REBASE_OPCODE_DONE;
 243
 244         // optimize phase 2, combine rebase/add pairs
 245         dst = &mid[0];
 246         for (const rebase_tmp* src = &mid[0]; src->opcode != REBASE_OPCODE_DONE; ++src) {
 247                 if ( (src->opcode == REBASE_OPCODE_DO_REBASE_ULEB_TIMES)
 248                                 && (src->operand1 == 1)
 249                                 && (src[1].opcode == REBASE_OPCODE_ADD_ADDR_ULEB)) {
 250                         dst->opcode = REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB;
 251                         dst->operand1 = src[1].operand1;
 252                         ++src;
 253                         ++dst;
 254                 }
 255                 else {
 256                         *dst++ = *src;
 257                 }
 258         }
 259         dst->opcode = REBASE_OPCODE_DONE;
 260
 261         // optimize phase 3, compress packed runs of REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB with
 262         // same addr delta into one REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB
 263         dst = &mid[0];
 264         for (const rebase_tmp* src = &mid[0]; src->opcode != REBASE_OPCODE_DONE; ++src) {
 265                 uint64_t delta = src->operand1;
 266                 if ( (src->opcode == REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB)
 267                                 && (src[1].opcode == REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB)
 268                                 && (src[2].opcode == REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB)
 269                                 && (src[1].operand1 == delta)
 270                                 && (src[2].operand1 == delta) ) {
 271                         // found at least three in a row, this is worth compressing
 272                         dst->opcode = REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB;
 273                         dst->operand1 = 1;
 274                         dst->operand2 = delta;
 275                         ++src;
 276                         while ( (src->opcode == REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB)
 277                                         && (src->operand1 == delta) ) {
 278                                 dst->operand1++;
 279                                 ++src;
 280                         }
 281                         --src;
 282                         ++dst;
 283                 }
 284                 else {
 285                         *dst++ = *src;
 286                 }
 287         }
 288         dst->opcode = REBASE_OPCODE_DONE;
 289
 290         // optimize phase 4, use immediate encodings
 291         for (rebase_tmp* p = &mid[0]; p->opcode != REBASE_OPCODE_DONE; ++p) {
 292                 if ( (p->opcode == REBASE_OPCODE_ADD_ADDR_ULEB)
 293                         && (p->operand1 < (15*sizeof(pint_t)))
 294                         && ((p->operand1 % sizeof(pint_t)) == 0) ) {
 295                         p->opcode = REBASE_OPCODE_ADD_ADDR_IMM_SCALED;
 296                         p->operand1 = p->operand1/sizeof(pint_t);
 297                 }
 298                 else if ( (p->opcode == REBASE_OPCODE_DO_REBASE_ULEB_TIMES) && (p->operand1 < 15) ) {
 299                         p->opcode = REBASE_OPCODE_DO_REBASE_IMM_TIMES;
 300                 }
 301         }
 302
 303         // convert to compressed encoding
 304         const static bool log = false;
 305         this->_encodedData.reserve(info.size()*2);
 306         bool done = false;
 307         for (typename std::vector<rebase_tmp>::iterator it = mid.begin(); !done && it != mid.end() ; ++it) {
 308                 switch ( it->opcode ) {
 309                         case REBASE_OPCODE_DONE:
 310                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DONE()\n");
 311                                 done = true;
 312                                 break;
 313                         case REBASE_OPCODE_SET_TYPE_IMM:
 314                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_SET_TYPE_IMM(%lld)\n", it->operand1);
 315                                 this->_encodedData.append_byte(REBASE_OPCODE_SET_TYPE_IMM | it->operand1);
 316                                 break;
 317                         case REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
 318                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB(%lld, 0x%llX)\n", it->operand1, it->operand2);
 319                                 this->_encodedData.append_byte(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | it->operand1);
 320                                 this->_encodedData.append_uleb128(it->operand2);
 321                                 break;
 322                         case REBASE_OPCODE_ADD_ADDR_ULEB:
 323                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 324                                 this->_encodedData.append_byte(REBASE_OPCODE_ADD_ADDR_ULEB);
 325                                 this->_encodedData.append_uleb128(it->operand1);
 326                                 break;
 327                         case REBASE_OPCODE_ADD_ADDR_IMM_SCALED:
 328                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_ADD_ADDR_IMM_SCALED(%lld=0x%llX)\n", it->operand1, it->operand1*sizeof(pint_t));
 329                                 this->_encodedData.append_byte(REBASE_OPCODE_ADD_ADDR_IMM_SCALED | it->operand1 );
 330                                 break;
 331                         case REBASE_OPCODE_DO_REBASE_IMM_TIMES:
 332                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DO_REBASE_IMM_TIMES(%lld)\n", it->operand1);
 333                                 this->_encodedData.append_byte(REBASE_OPCODE_DO_REBASE_IMM_TIMES | it->operand1);
 334                                 break;
 335                         case REBASE_OPCODE_DO_REBASE_ULEB_TIMES:
 336                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DO_REBASE_ULEB_TIMES(%lld)\n", it->operand1);
 337                                 this->_encodedData.append_byte(REBASE_OPCODE_DO_REBASE_ULEB_TIMES);
 338                                 this->_encodedData.append_uleb128(it->operand1);
 339                                 break;
 340                         case REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB:
 341                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 342                                 this->_encodedData.append_byte(REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB);
 343                                 this->_encodedData.append_uleb128(it->operand1);
 344                                 break;
 345                         case REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB:
 346                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB(%lld, %lld)\n", it->operand1, it->operand2);
 347                                 this->_encodedData.append_byte(REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB);
 348                                 this->_encodedData.append_uleb128(it->operand1);
 349                                 this->_encodedData.append_uleb128(it->operand2);
 350                                 break;
 351                 }
 352         }
 353
 354
 355         // align to pointer size
 356         this->_encodedData.pad_to_size(sizeof(pint_t));
 357
 358         this->_encoded = true;
 359
 360         if (log) fprintf(stderr, "total rebase info size = %ld\n", this->_encodedData.size());
 361 }
 362
 363
 364 template <typename A>
 365 class BindingInfoAtom : public LinkEditAtom
 366 {
 367 public:
 368                                                                                                 BindingInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 369                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { }
 370
 371         // overrides of ld::Atom
 372         virtual const char*                                                     name() const            { return "binding info"; }
 373         // overrides of LinkEditAtom
 374         virtual void                                                            encode() const;
 375
 376
 377 private:
 378         typedef typename A::P                                           P;
 379         typedef typename A::P::E                                        E;
 380         typedef typename A::P::uint_t                           pint_t;
 381
 382         struct binding_tmp
 383         {
 384                 binding_tmp(uint8_t op, uint64_t p1, uint64_t p2=0, const char* s=NULL)
 385                         : opcode(op), operand1(p1), operand2(p2), name(s) {}
 386                 uint8_t         opcode;
 387                 uint64_t        operand1;
 388                 uint64_t        operand2;
 389                 const char*     name;
 390         };
 391
 392         static ld::Section                      _s_section;
 393 };
 394
 395 template <typename A>
 396 ld::Section BindingInfoAtom<A>::_s_section("__LINKEDIT", "__binding", ld::Section::typeLinkEdit, true);
 397
 398
 399 template <typename A>
 400 void BindingInfoAtom<A>::encode() const
 401 {
 402         // sort by library, symbol, type, then address
 403         std::vector<OutputFile::BindingInfo>& info = this->_writer._bindingInfo;
 404         std::sort(info.begin(), info.end());
 405
 406         // convert to temp encoding that can be more easily optimized
 407         std::vector<binding_tmp> mid;
 408         uint64_t curSegStart = 0;
 409         uint64_t curSegEnd = 0;
 410         uint32_t curSegIndex = 0;
 411         int ordinal = 0x80000000;
 412         const char* symbolName = NULL;
 413         uint8_t type = 0;
 414         uint64_t address = (uint64_t)(-1);
 415         int64_t addend = 0;
 416         for (std::vector<OutputFile::BindingInfo>::const_iterator it = info.begin(); it != info.end(); ++it) {
 417                 if ( ordinal != it->_libraryOrdinal ) {
 418                         if ( it->_libraryOrdinal <= 0 ) {
 419                                 // special lookups are encoded as negative numbers in BindingInfo
 420                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM, it->_libraryOrdinal));
 421                         }
 422                         else {
 423                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB, it->_libraryOrdinal));
 424                         }
 425                         ordinal = it->_libraryOrdinal;
 426                 }
 427                 if ( symbolName != it->_symbolName ) {
 428                         mid.push_back(binding_tmp(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM, it->_flags, 0, it->_symbolName));
 429                         symbolName = it->_symbolName;
 430                 }
 431                 if ( type != it->_type ) {
 432                         mid.push_back(binding_tmp(BIND_OPCODE_SET_TYPE_IMM, it->_type));
 433                         type = it->_type;
 434                 }
 435                 if ( address != it->_address ) {
 436                         if ( (it->_address < curSegStart) || ( it->_address >= curSegEnd) ) {
 437                                 if ( ! this->_writer.findSegment(this->_state, it->_address, &curSegStart, &curSegEnd, &curSegIndex) )
 438                                         throw "binding address outside range of any segment";
 439                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB, curSegIndex, it->_address - curSegStart));
 440                         }
 441                         else {
 442                                 mid.push_back(binding_tmp(BIND_OPCODE_ADD_ADDR_ULEB, it->_address-address));
 443                         }
 444                         address = it->_address;
 445                 }
 446                 if ( addend != it->_addend ) {
 447                         mid.push_back(binding_tmp(BIND_OPCODE_SET_ADDEND_SLEB, it->_addend));
 448                         addend = it->_addend;
 449                 }
 450                 mid.push_back(binding_tmp(BIND_OPCODE_DO_BIND, 0));
 451                 address += sizeof(pint_t);
 452         }
 453         mid.push_back(binding_tmp(BIND_OPCODE_DONE, 0));
 454
 455
 456         // optimize phase 1, combine bind/add pairs
 457         binding_tmp* dst = &mid[0];
 458         for (const binding_tmp* src = &mid[0]; src->opcode != BIND_OPCODE_DONE; ++src) {
 459                 if ( (src->opcode == BIND_OPCODE_DO_BIND)
 460                                 && (src[1].opcode == BIND_OPCODE_ADD_ADDR_ULEB) ) {
 461                         dst->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
 462                         dst->operand1 = src[1].operand1;
 463                         ++src;
 464                         ++dst;
 465                 }
 466                 else {
 467                         *dst++ = *src;
 468                 }
 469         }
 470         dst->opcode = BIND_OPCODE_DONE;
 471
 472         // optimize phase 2, compress packed runs of BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB with
 473         // same addr delta into one BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB
 474         dst = &mid[0];
 475         for (const binding_tmp* src = &mid[0]; src->opcode != BIND_OPCODE_DONE; ++src) {
 476                 uint64_t delta = src->operand1;
 477                 if ( (src->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 478                                 && (src[1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 479                                 && (src[1].operand1 == delta) ) {
 480                         // found at least two in a row, this is worth compressing
 481                         dst->opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
 482                         dst->operand1 = 1;
 483                         dst->operand2 = delta;
 484                         ++src;
 485                         while ( (src->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 486                                         && (src->operand1 == delta) ) {
 487                                 dst->operand1++;
 488                                 ++src;
 489                         }
 490                         --src;
 491                         ++dst;
 492                 }
 493                 else {
 494                         *dst++ = *src;
 495                 }
 496         }
 497         dst->opcode = BIND_OPCODE_DONE;
 498
 499         // optimize phase 3, use immediate encodings
 500         for (binding_tmp* p = &mid[0]; p->opcode != REBASE_OPCODE_DONE; ++p) {
 501                 if ( (p->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 502                         && (p->operand1 < (15*sizeof(pint_t)))
 503                         && ((p->operand1 % sizeof(pint_t)) == 0) ) {
 504                         p->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
 505                         p->operand1 = p->operand1/sizeof(pint_t);
 506                 }
 507                 else if ( (p->opcode == BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB) && (p->operand1 <= 15) ) {
 508                         p->opcode = BIND_OPCODE_SET_DYLIB_ORDINAL_IMM;
 509                 }
 510         }
 511         dst->opcode = BIND_OPCODE_DONE;
 512
 513         // convert to compressed encoding
 514         const static bool log = false;
 515         this->_encodedData.reserve(info.size()*2);
 516         bool done = false;
 517         for (typename std::vector<binding_tmp>::iterator it = mid.begin(); !done && it != mid.end() ; ++it) {
 518                 switch ( it->opcode ) {
 519                         case BIND_OPCODE_DONE:
 520                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DONE()\n");
 521                                 done = true;
 522                                 break;
 523                         case BIND_OPCODE_SET_DYLIB_ORDINAL_IMM:
 524                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_ORDINAL_IMM(%lld)\n", it->operand1);
 525                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | it->operand1);
 526                                 break;
 527                         case BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB:
 528                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB(%lld)\n", it->operand1);
 529                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
 530                                 this->_encodedData.append_uleb128(it->operand1);
 531                                 break;
 532                         case BIND_OPCODE_SET_DYLIB_SPECIAL_IMM:
 533                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_SPECIAL_IMM(%lld)\n", it->operand1);
 534                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM | (it->operand1 & BIND_IMMEDIATE_MASK));
 535                                 break;
 536                         case BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
 537                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM(0x%0llX, %s)\n", it->operand1, it->name);
 538                                 this->_encodedData.append_byte(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | it->operand1);
 539                                 this->_encodedData.append_string(it->name);
 540                                 break;
 541                         case BIND_OPCODE_SET_TYPE_IMM:
 542                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_TYPE_IMM(%lld)\n", it->operand1);
 543                                 this->_encodedData.append_byte(BIND_OPCODE_SET_TYPE_IMM | it->operand1);
 544                                 break;
 545                         case BIND_OPCODE_SET_ADDEND_SLEB:
 546                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_ADDEND_SLEB(%lld)\n", it->operand1);
 547                                 this->_encodedData.append_byte(BIND_OPCODE_SET_ADDEND_SLEB);
 548                                 this->_encodedData.append_sleb128(it->operand1);
 549                                 break;
 550                         case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
 551                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB(%lld, 0x%llX)\n", it->operand1, it->operand2);
 552                                 this->_encodedData.append_byte(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | it->operand1);
 553                                 this->_encodedData.append_uleb128(it->operand2);
 554                                 break;
 555                         case BIND_OPCODE_ADD_ADDR_ULEB:
 556                                 if ( log ) fprintf(stderr, "BIND_OPCODE_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 557                                 this->_encodedData.append_byte(BIND_OPCODE_ADD_ADDR_ULEB);
 558                                 this->_encodedData.append_uleb128(it->operand1);
 559                                 break;
 560                         case BIND_OPCODE_DO_BIND:
 561                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND()\n");
 562                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND);
 563                                 break;
 564                         case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
 565                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 566                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB);
 567                                 this->_encodedData.append_uleb128(it->operand1);
 568                                 break;
 569                         case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
 570                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED(%lld=0x%llX)\n", it->operand1, it->operand1*sizeof(pint_t));
 571                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED | it->operand1 );
 572                                 break;
 573                         case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
 574                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB(%lld, %lld)\n", it->operand1, it->operand2);
 575                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB);
 576                                 this->_encodedData.append_uleb128(it->operand1);
 577                                 this->_encodedData.append_uleb128(it->operand2);
 578                                 break;
 579                 }
 580         }
 581
 582         // align to pointer size
 583         this->_encodedData.pad_to_size(sizeof(pint_t));
 584
 585         this->_encoded = true;
 586
 587         if (log) fprintf(stderr, "total binding info size = %ld\n", this->_encodedData.size());
 588 }
 589
 590
 591
 592 template <typename A>
 593 class WeakBindingInfoAtom : public LinkEditAtom
 594 {
 595 public:
 596                                                                                                 WeakBindingInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 597                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { _encoded = true; }
 598
 599         // overrides of ld::Atom
 600         virtual const char*                                                     name() const            { return "weak binding info"; }
 601         // overrides of LinkEditAtom
 602         virtual void                                                            encode() const;
 603
 604 private:
 605         typedef typename A::P                                           P;
 606         typedef typename A::P::E                                        E;
 607         typedef typename A::P::uint_t                           pint_t;
 608
 609         struct WeakBindingSorter
 610         {
 611                  bool operator()(const OutputFile::BindingInfo& left, const OutputFile::BindingInfo& right)
 612                  {
 613                         // sort by symbol, type, address
 614                         if ( left._symbolName != right._symbolName )
 615                                 return ( strcmp(left._symbolName, right._symbolName) < 0 );
 616                         if ( left._type != right._type )
 617                                 return  (left._type < right._type);
 618                         return  (left._address < right._address);
 619                  }
 620         };
 621
 622         struct binding_tmp
 623         {
 624                 binding_tmp(uint8_t op, uint64_t p1, uint64_t p2=0, const char* s=NULL)
 625                         : opcode(op), operand1(p1), operand2(p2), name(s) {}
 626                 uint8_t         opcode;
 627                 uint64_t        operand1;
 628                 uint64_t        operand2;
 629                 const char*     name;
 630         };
 631
 632         static ld::Section                      _s_section;
 633 };
 634
 635 template <typename A>
 636 ld::Section WeakBindingInfoAtom<A>::_s_section("__LINKEDIT", "__weak_binding", ld::Section::typeLinkEdit, true);
 637
 638
 639 template <typename A>
 640 void WeakBindingInfoAtom<A>::encode() const
 641 {
 642         // sort by symbol, type, address
 643         std::vector<OutputFile::BindingInfo>& info = this->_writer._weakBindingInfo;
 644         if ( info.size() == 0 ) {
 645                 // short circuit if no weak binding needed
 646                 this->_encoded = true;
 647                 return;
 648         }
 649         std::sort(info.begin(), info.end(), WeakBindingSorter());
 650
 651         // convert to temp encoding that can be more easily optimized
 652         std::vector<binding_tmp> mid;
 653         mid.reserve(info.size());
 654         uint64_t curSegStart = 0;
 655         uint64_t curSegEnd = 0;
 656         uint32_t curSegIndex = 0;
 657         const char* symbolName = NULL;
 658         uint8_t type = 0;
 659         uint64_t address = (uint64_t)(-1);
 660         int64_t addend = 0;
 661         for (typename std::vector<OutputFile::BindingInfo>::const_iterator it = info.begin(); it != info.end(); ++it) {
 662                 if ( symbolName != it->_symbolName ) {
 663                         mid.push_back(binding_tmp(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM, it->_flags, 0, it->_symbolName));
 664                         symbolName = it->_symbolName;
 665                 }
 666                 // non-weak symbols just have BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
 667                 // weak symbols have SET_SEG, ADD_ADDR, SET_ADDED, DO_BIND
 668                 if ( it->_type != BIND_TYPE_OVERRIDE_OF_WEAKDEF_IN_DYLIB ) {
 669                         if ( type != it->_type ) {
 670                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_TYPE_IMM, it->_type));
 671                                 type = it->_type;
 672                         }
 673                         if ( address != it->_address ) {
 674                                 if ( (it->_address < curSegStart) || ( it->_address >= curSegEnd) ) {
 675                                         if ( ! this->_writer.findSegment(this->_state, it->_address, &curSegStart, &curSegEnd, &curSegIndex) )
 676                                                 throw "binding address outside range of any segment";
 677                                         mid.push_back(binding_tmp(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB, curSegIndex, it->_address - curSegStart));
 678                                 }
 679                                 else {
 680                                         mid.push_back(binding_tmp(BIND_OPCODE_ADD_ADDR_ULEB, it->_address-address));
 681                                 }
 682                                 address = it->_address;
 683                         }
 684                         if ( addend != it->_addend ) {
 685                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_ADDEND_SLEB, it->_addend));
 686                                 addend = it->_addend;
 687                         }
 688                         mid.push_back(binding_tmp(BIND_OPCODE_DO_BIND, 0));
 689                         address += sizeof(pint_t);
 690                 }
 691         }
 692         mid.push_back(binding_tmp(BIND_OPCODE_DONE, 0));
 693
 694
 695         // optimize phase 1, combine bind/add pairs
 696         binding_tmp* dst = &mid[0];
 697         for (const binding_tmp* src = &mid[0]; src->opcode != BIND_OPCODE_DONE; ++src) {
 698                 if ( (src->opcode == BIND_OPCODE_DO_BIND)
 699                                 && (src[1].opcode == BIND_OPCODE_ADD_ADDR_ULEB) ) {
 700                         dst->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
 701                         dst->operand1 = src[1].operand1;
 702                         ++src;
 703                         ++dst;
 704                 }
 705                 else {
 706                         *dst++ = *src;
 707                 }
 708         }
 709         dst->opcode = BIND_OPCODE_DONE;
 710
 711         // optimize phase 2, compress packed runs of BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB with
 712         // same addr delta into one BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB
 713         dst = &mid[0];
 714         for (const binding_tmp* src = &mid[0]; src->opcode != BIND_OPCODE_DONE; ++src) {
 715                 uint64_t delta = src->operand1;
 716                 if ( (src->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 717                                 && (src[1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 718                                 && (src[1].operand1 == delta) ) {
 719                         // found at least two in a row, this is worth compressing
 720                         dst->opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
 721                         dst->operand1 = 1;
 722                         dst->operand2 = delta;
 723                         ++src;
 724                         while ( (src->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 725                                         && (src->operand1 == delta) ) {
 726                                 dst->operand1++;
 727                                 ++src;
 728                         }
 729                         --src;
 730                         ++dst;
 731                 }
 732                 else {
 733                         *dst++ = *src;
 734                 }
 735         }
 736         dst->opcode = BIND_OPCODE_DONE;
 737
 738         // optimize phase 3, use immediate encodings
 739         for (binding_tmp* p = &mid[0]; p->opcode != REBASE_OPCODE_DONE; ++p) {
 740                 if ( (p->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 741                         && (p->operand1 < (15*sizeof(pint_t)))
 742                         && ((p->operand1 % sizeof(pint_t)) == 0) ) {
 743                         p->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
 744                         p->operand1 = p->operand1/sizeof(pint_t);
 745                 }
 746         }
 747         dst->opcode = BIND_OPCODE_DONE;
 748
 749
 750         // convert to compressed encoding
 751         const static bool log = false;
 752         this->_encodedData.reserve(info.size()*2);
 753         bool done = false;
 754         for (typename std::vector<binding_tmp>::iterator it = mid.begin(); !done && it != mid.end() ; ++it) {
 755                 switch ( it->opcode ) {
 756                         case BIND_OPCODE_DONE:
 757                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DONE()\n");
 758                                 this->_encodedData.append_byte(BIND_OPCODE_DONE);
 759                                 done = true;
 760                                 break;
 761                         case BIND_OPCODE_SET_DYLIB_ORDINAL_IMM:
 762                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_ORDINAL_IMM(%lld)\n", it->operand1);
 763                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | it->operand1);
 764                                 break;
 765                         case BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB:
 766                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB(%lld)\n", it->operand1);
 767                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
 768                                 this->_encodedData.append_uleb128(it->operand1);
 769                                 break;
 770                         case BIND_OPCODE_SET_DYLIB_SPECIAL_IMM:
 771                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_SPECIAL_IMM(%lld)\n", it->operand1);
 772                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM | (it->operand1 & BIND_IMMEDIATE_MASK));
 773                                 break;
 774                         case BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
 775                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM(0x%0llX, %s)\n", it->operand1, it->name);
 776                                 this->_encodedData.append_byte(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | it->operand1);
 777                                 this->_encodedData.append_string(it->name);
 778                                 break;
 779                         case BIND_OPCODE_SET_TYPE_IMM:
 780                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_TYPE_IMM(%lld)\n", it->operand1);
 781                                 this->_encodedData.append_byte(BIND_OPCODE_SET_TYPE_IMM | it->operand1);
 782                                 break;
 783                         case BIND_OPCODE_SET_ADDEND_SLEB:
 784                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_ADDEND_SLEB(%lld)\n", it->operand1);
 785                                 this->_encodedData.append_byte(BIND_OPCODE_SET_ADDEND_SLEB);
 786                                 this->_encodedData.append_sleb128(it->operand1);
 787                                 break;
 788                         case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
 789                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB(%lld, 0x%llX)\n", it->operand1, it->operand2);
 790                                 this->_encodedData.append_byte(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | it->operand1);
 791                                 this->_encodedData.append_uleb128(it->operand2);
 792                                 break;
 793                         case BIND_OPCODE_ADD_ADDR_ULEB:
 794                                 if ( log ) fprintf(stderr, "BIND_OPCODE_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 795                                 this->_encodedData.append_byte(BIND_OPCODE_ADD_ADDR_ULEB);
 796                                 this->_encodedData.append_uleb128(it->operand1);
 797                                 break;
 798                         case BIND_OPCODE_DO_BIND:
 799                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND()\n");
 800                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND);
 801                                 break;
 802                         case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
 803                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 804                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB);
 805                                 this->_encodedData.append_uleb128(it->operand1);
 806                                 break;
 807                         case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
 808                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED(%lld=0x%llX)\n", it->operand1, it->operand1*sizeof(pint_t));
 809                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED | it->operand1 );
 810                                 break;
 811                         case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
 812                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB(%lld, %lld)\n", it->operand1, it->operand2);
 813                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB);
 814                                 this->_encodedData.append_uleb128(it->operand1);
 815                                 this->_encodedData.append_uleb128(it->operand2);
 816                                 break;
 817                 }
 818         }
 819
 820         // align to pointer size
 821         this->_encodedData.pad_to_size(sizeof(pint_t));
 822
 823         this->_encoded = true;
 824
 825         if (log) fprintf(stderr, "total weak binding info size = %ld\n", this->_encodedData.size());
 826
 827 }
 828
 829
 830
 831 template <typename A>
 832 class LazyBindingInfoAtom : public LinkEditAtom
 833 {
 834 public:
 835                                                                                                 LazyBindingInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 836                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) {_encoded = true;  }
 837
 838         // overrides of ld::Atom
 839         virtual const char*                                                     name() const            { return "lazy binding info"; }
 840         // overrides of LinkEditAtom
 841         virtual void                                                            encode() const;
 842
 843 private:
 844         typedef typename A::P                                           P;
 845         typedef typename A::P::E                                        E;
 846         typedef typename A::P::uint_t                           pint_t;
 847
 848         static ld::Section                      _s_section;
 849 };
 850
 851 template <typename A>
 852 ld::Section LazyBindingInfoAtom<A>::_s_section("__LINKEDIT", "__lazy_binding", ld::Section::typeLinkEdit, true);
 853
 854
 855
 856 template <typename A>
 857 void LazyBindingInfoAtom<A>::encode() const
 858 {
 859         // stream all lazy bindings and record start offsets
 860         std::vector<OutputFile::BindingInfo>& info = this->_writer._lazyBindingInfo;
 861         for (std::vector<OutputFile::BindingInfo>::const_iterator it = info.begin(); it != info.end(); ++it) {
 862                 // record start offset for use by stub helper
 863                 this->_writer.setLazyBindingInfoOffset(it->_address, this->_encodedData.size());
 864
 865                 // write address to bind
 866                 uint64_t segStart = 0;
 867                 uint64_t segEnd = 0;
 868                 uint32_t segIndex = 0;
 869                 if ( ! this->_writer.findSegment(this->_state, it->_address, &segStart, &segEnd, &segIndex) )
 870                         throw "lazy binding address outside range of any segment";
 871                 this->_encodedData.append_byte(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | segIndex);
 872                 this->_encodedData.append_uleb128(it->_address - segStart);
 873
 874                 // write ordinal
 875                 if ( it->_libraryOrdinal <= 0 ) {
 876                         // special lookups are encoded as negative numbers in BindingInfo
 877                         this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM | (it->_libraryOrdinal & BIND_IMMEDIATE_MASK) );
 878                 }
 879                 else if ( it->_libraryOrdinal <= 15 ) {
 880                         // small ordinals are encoded in opcode
 881                         this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | it->_libraryOrdinal);
 882                 }
 883                 else {
 884                         this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
 885                         this->_encodedData.append_uleb128(it->_libraryOrdinal);
 886                 }
 887                 // write symbol name
 888                 this->_encodedData.append_byte(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | it->_flags);
 889                 this->_encodedData.append_string(it->_symbolName);
 890                 // write do bind
 891                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND);
 892                 this->_encodedData.append_byte(BIND_OPCODE_DONE);
 893         }
 894
 895         // align to pointer size
 896         this->_encodedData.pad_to_size(sizeof(pint_t));
 897
 898         this->_encoded = true;
 899         //fprintf(stderr, "lazy binding info size = %ld, for %ld entries\n", _encodedData.size(), allLazys.size());
 900 }
 901
 902
 903
 904 template <typename A>
 905 class ExportInfoAtom : public LinkEditAtom
 906 {
 907 public:
 908                                                                                                 ExportInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 909                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { _encoded = true; }
 910
 911         // overrides of ld::Atom
 912         virtual const char*                                                     name() const            { return "export info"; }
 913         // overrides of LinkEditAtom
 914         virtual void                                                            encode() const;
 915
 916 private:
 917         typedef typename A::P                                           P;
 918         typedef typename A::P::E                                        E;
 919         typedef typename A::P::uint_t                           pint_t;
 920
 921         const ld::Atom*                                                         stubForResolverFunction(const ld::Atom* resolver) const;
 922
 923         struct TrieEntriesSorter
 924         {
 925                 TrieEntriesSorter(const Options& o) : _options(o) {}
 926
 927                  bool operator()(const mach_o::trie::Entry& left, const mach_o::trie::Entry& right)
 928                  {
 929                         unsigned int leftOrder;
 930                         unsigned int rightOrder;
 931                         _options.exportedSymbolOrder(left.name, &leftOrder);
 932                         _options.exportedSymbolOrder(right.name, &rightOrder);
 933                         if ( leftOrder != rightOrder )
 934                                 return (leftOrder < rightOrder);
 935                         else
 936                                 return (left.address < right.address);
 937                  }
 938         private:
 939                 const Options&  _options;
 940         };
 941
 942         static ld::Section                      _s_section;
 943 };
 944
 945 template <typename A>
 946 ld::Section ExportInfoAtom<A>::_s_section("__LINKEDIT", "__export", ld::Section::typeLinkEdit, true);
 947
 948 template <typename A>
 949 const ld::Atom* ExportInfoAtom<A>::stubForResolverFunction(const ld::Atom* resolver) const
 950 {
 951         for (std::vector<ld::Internal::FinalSection*>::iterator sit = _state.sections.begin(); sit != _state.sections.end(); ++sit) {
 952                 ld::Internal::FinalSection* sect = *sit;
 953                 if ( (sect->type() == ld::Section::typeStub) || (sect->type() == ld::Section::typeStubClose) ) {
 954                         for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 955                                 const ld::Atom* atom = *ait;
 956                                 if ( strcmp(atom->name(), resolver->name()) == 0 )
 957                                         return atom;
 958                         }
 959                 }
 960         }
 961         assert(0 && "no stub for resolver function");
 962         return NULL;
 963 }
 964
 965
 966 template <typename A>
 967 void ExportInfoAtom<A>::encode() const
 968 {
 969         // make vector of mach_o::trie::Entry for all exported symbols
 970         std::vector<const ld::Atom*>& exports = this->_writer._exportedAtoms;
 971         uint64_t imageBaseAddress = this->_writer.headerAndLoadCommandsSection->address;
 972         std::vector<mach_o::trie::Entry> entries;
 973         entries.reserve(exports.size());
 974         for (std::vector<const ld::Atom*>::const_iterator it = exports.begin(); it != exports.end(); ++it) {
 975                 const ld::Atom* atom = *it;
 976                 mach_o::trie::Entry entry;
 977                 uint64_t flags = (atom->contentType() == ld::Atom::typeTLV) ? EXPORT_SYMBOL_FLAGS_KIND_THREAD_LOCAL : EXPORT_SYMBOL_FLAGS_KIND_REGULAR;
 978                 uint64_t other = 0;
 979                 uint64_t address = atom->finalAddress() - imageBaseAddress;
 980                 if ( (atom->definition() == ld::Atom::definitionRegular) && (atom->combine() == ld::Atom::combineByName) )
 981                         flags |= EXPORT_SYMBOL_FLAGS_WEAK_DEFINITION;
 982                 if ( atom->definition() == ld::Atom::definitionProxy ) {
 983                         entry.name = atom->name();
 984                         entry.flags = flags | EXPORT_SYMBOL_FLAGS_REEXPORT;
 985                         entry.other = this->_writer.compressedOrdinalForAtom(atom);
 986                         if ( entry.other == BIND_SPECIAL_DYLIB_SELF ) {
 987                                 warning("not adding explict export for symbol %s because it is already re-exported from dylib %s", entry.name, atom->file()->path());
 988                                 continue;
 989                         }
 990                         if ( atom->isAlias() ) {
 991                                 // alias proxy means symbol was re-exported with a name change
 992                                 const ld::Atom* aliasOf = NULL;
 993                                 for (ld::Fixup::iterator fit = atom->fixupsBegin(); fit != atom->fixupsEnd(); ++fit) {
 994                                         if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
 995                                                 assert(fit->binding == ld::Fixup::bindingDirectlyBound);
 996                                                 aliasOf = fit->u.target;
 997                                         }
 998                                 }
 999                                 assert(aliasOf != NULL);
1000                                 entry.importName = aliasOf->name();
1001                         }
1002                         else {
1003                                 // symbol name stays same as re-export
1004                                 entry.importName = atom->name();
1005                         }
1006                         entries.push_back(entry);
1007                         //fprintf(stderr, "re-export %s from lib %llu as %s\n", entry.importName, entry.other, entry.name);
1008                 }
1009                 else {
1010                         if ( atom->isThumb() )
1011                                 address |= 1;
1012                         if ( atom->contentType() == ld::Atom::typeResolver ) {
1013                                 flags |= EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER;
1014                                 // set normal lookup to return stub address
1015                                 // and add resolver function in new location that newer dyld's can access
1016                                 other = address;
1017                                 const ld::Atom* stub = stubForResolverFunction(atom);
1018                                 address = stub->finalAddress() - imageBaseAddress;
1019                                 if ( stub->isThumb() )
1020                                         address |= 1;
1021                         }
1022                         entry.name = atom->name();
1023                         entry.flags = flags;
1024                         entry.address = address;
1025                         entry.other = other;
1026                         entry.importName = NULL;
1027                         entries.push_back(entry);
1028                 }
1029         }
1030
1031         // sort vector by -exported_symbols_order, and any others by address
1032         std::sort(entries.begin(), entries.end(), TrieEntriesSorter(_options));
1033
1034         // create trie
1035         mach_o::trie::makeTrie(entries, this->_encodedData.bytes());
1036
1037         // align to pointer size
1038         this->_encodedData.pad_to_size(sizeof(pint_t));
1039
1040         this->_encoded = true;
1041 }
1042
1043
1044 template <typename A>
1045 class SplitSegInfoAtom : public LinkEditAtom
1046 {
1047 public:
1048                                                                                                 SplitSegInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
1049                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { }
1050
1051         // overrides of ld::Atom
1052         virtual const char*                                                     name() const            { return "split seg info"; }
1053         // overrides of LinkEditAtom
1054         virtual void                                                            encode() const;
1055
1056 private:
1057         typedef typename A::P                                           P;
1058         typedef typename A::P::E                                        E;
1059         typedef typename A::P::uint_t                           pint_t;
1060
1061         void                                                                            addSplitSegInfo(uint64_t address, ld::Fixup::Kind k, uint32_t) const;
1062         void                                                                            uleb128EncodeAddresses(const std::vector<uint64_t>& locations) const;
1063
1064         mutable std::vector<uint64_t>                           _32bitPointerLocations;
1065         mutable std::vector<uint64_t>                           _64bitPointerLocations;
1066         mutable std::vector<uint64_t>                           _thumbLo16Locations;
1067         mutable std::vector<uint64_t>                           _thumbHi16Locations[16];
1068         mutable std::vector<uint64_t>                           _armLo16Locations;
1069         mutable std::vector<uint64_t>                           _armHi16Locations[16];
1070
1071
1072         static ld::Section                      _s_section;
1073 };
1074
1075 template <typename A>
1076 ld::Section SplitSegInfoAtom<A>::_s_section("__LINKEDIT", "__splitSegInfo", ld::Section::typeLinkEdit, true);
1077
1078 template <>
1079 void SplitSegInfoAtom<x86_64>::addSplitSegInfo(uint64_t address, ld::Fixup::Kind kind, uint32_t extra) const
1080 {
1081         switch (kind) {
1082                 case ld::Fixup::kindStoreX86PCRel32:
1083                 case ld::Fixup::kindStoreX86PCRel32_1:
1084                 case ld::Fixup::kindStoreX86PCRel32_2:
1085                 case ld::Fixup::kindStoreX86PCRel32_4:
1086                 case ld::Fixup::kindStoreX86PCRel32GOTLoad:
1087                 case ld::Fixup::kindStoreX86PCRel32GOTLoadNowLEA:
1088                 case ld::Fixup::kindStoreX86PCRel32GOT:
1089                 case ld::Fixup::kindStoreLittleEndian32:
1090                 case ld::Fixup::kindStoreTargetAddressLittleEndian32:
1091                 case ld::Fixup::kindStoreTargetAddressX86PCRel32:
1092                 case ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoad:
1093                 case ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoadNowLEA:
1094                         _32bitPointerLocations.push_back(address);
1095                         break;
1096                 case ld::Fixup::kindStoreLittleEndian64:
1097                 case ld::Fixup::kindStoreTargetAddressLittleEndian64:
1098                         _64bitPointerLocations.push_back(address);
1099                         break;
1100                 default:
1101                         warning("codegen at address 0x%08llX prevents image from working in dyld shared cache", address);
1102                         break;
1103         }
1104 }
1105
1106 template <>
1107 void SplitSegInfoAtom<x86>::addSplitSegInfo(uint64_t address, ld::Fixup::Kind kind, uint32_t extra) const
1108 {
1109         switch (kind) {
1110                 case ld::Fixup::kindStoreLittleEndian32:
1111                 case ld::Fixup::kindStoreTargetAddressLittleEndian32:
1112                         _32bitPointerLocations.push_back(address);
1113                         break;
1114                 default:
1115                         warning("codegen at address 0x%08llX prevents image from working in dyld shared cache", address);
1116                         break;
1117         }
1118 }
1119
1120 template <>
1121 void SplitSegInfoAtom<arm>::addSplitSegInfo(uint64_t address, ld::Fixup::Kind kind, uint32_t extra) const
1122 {
1123         switch (kind) {
1124                 case ld::Fixup::kindStoreLittleEndian32:
1125                         _32bitPointerLocations.push_back(address);
1126                         break;
1127         case ld::Fixup::kindStoreARMLow16:
1128                         _armLo16Locations.push_back(address);
1129                         break;
1130        case ld::Fixup::kindStoreThumbLow16:
1131                         _thumbLo16Locations.push_back(address);
1132                         break;
1133         case ld::Fixup::kindStoreARMHigh16:
1134             assert(extra < 16);
1135                         _armHi16Locations[extra].push_back(address);
1136                         break;
1137         case ld::Fixup::kindStoreThumbHigh16:
1138             assert(extra < 16);
1139                         _thumbHi16Locations[extra].push_back(address);
1140                         break;
1141                 default:
1142                         warning("codegen at address 0x%08llX prevents image from working in dyld shared cache", address);
1143                         break;
1144         }
1145 }
1146
1147
1148
1149 template <typename A>
1150 void SplitSegInfoAtom<A>::uleb128EncodeAddresses(const std::vector<uint64_t>& locations) const
1151 {
1152         pint_t addr = this->_options.baseAddress();
1153         for(typename std::vector<uint64_t>::const_iterator it = locations.begin(); it != locations.end(); ++it) {
1154                 pint_t nextAddr = *it;
1155                 //fprintf(stderr, "nextAddr=0x%0llX\n", (uint64_t)nextAddr);
1156                 uint64_t delta = nextAddr - addr;
1157                 //fprintf(stderr, "delta=0x%0llX\n", delta);
1158                 if ( delta == 0 )
1159                         throw "double split seg info for same address";
1160                 // uleb128 encode
1161                 uint8_t byte;
1162                 do {
1163                         byte = delta & 0x7F;
1164                         delta &= ~0x7F;
1165                         if ( delta != 0 )
1166                                 byte |= 0x80;
1167                         this->_encodedData.append_byte(byte);
1168                         delta = delta >> 7;
1169                 }
1170                 while( byte >= 0x80 );
1171                 addr = nextAddr;
1172         }
1173 }
1174
1175
1176 template <typename A>
1177 void SplitSegInfoAtom<A>::encode() const
1178 {
1179         // sort into group by pointer adjustment kind
1180         std::vector<OutputFile::SplitSegInfoEntry>& info = this->_writer._splitSegInfos;
1181         for (std::vector<OutputFile::SplitSegInfoEntry>::const_iterator it = info.begin(); it != info.end(); ++it) {
1182                 this->addSplitSegInfo(it->address, it->kind, it->extra);
1183         }
1184
1185         // delta compress runs of addresses
1186         this->_encodedData.reserve(8192);
1187         if ( _32bitPointerLocations.size() != 0 ) {
1188                 this->_encodedData.append_byte(1);
1189                 //fprintf(stderr, "type 1:\n");
1190                 std::sort(_32bitPointerLocations.begin(), _32bitPointerLocations.end());
1191                 this->uleb128EncodeAddresses(_32bitPointerLocations);
1192                 this->_encodedData.append_byte(0); // terminator
1193         }
1194
1195         if ( _64bitPointerLocations.size() != 0 ) {
1196                 this->_encodedData.append_byte(2);
1197                 //fprintf(stderr, "type 2:\n");
1198                 std::sort(_64bitPointerLocations.begin(), _64bitPointerLocations.end());
1199                 this->uleb128EncodeAddresses(_64bitPointerLocations);
1200                 this->_encodedData.append_byte(0); // terminator
1201         }
1202
1203         if ( _thumbLo16Locations.size() != 0 ) {
1204                 this->_encodedData.append_byte(5);
1205                 //fprintf(stderr, "type 5:\n");
1206                 std::sort(_thumbLo16Locations.begin(), _thumbLo16Locations.end());
1207                 this->uleb128EncodeAddresses(_thumbLo16Locations);
1208                 this->_encodedData.append_byte(0); // terminator
1209         }
1210
1211         if ( _armLo16Locations.size() != 0 ) {
1212                 this->_encodedData.append_byte(6);
1213                 //fprintf(stderr, "type 6:\n");
1214                 std::sort(_armLo16Locations.begin(), _armLo16Locations.end());
1215                 this->uleb128EncodeAddresses(_armLo16Locations);
1216                 this->_encodedData.append_byte(0); // terminator
1217         }
1218
1219         for (uint32_t i=0; i < 16; ++i) {
1220                 if ( _thumbHi16Locations[i].size() != 0 ) {
1221                         this->_encodedData.append_byte(16+i);
1222                         //fprintf(stderr, "type 16+%d:\n", i);
1223                         std::sort(_thumbHi16Locations[i].begin(), _thumbHi16Locations[i].end());
1224                         this->uleb128EncodeAddresses(_thumbHi16Locations[i]);
1225                         this->_encodedData.append_byte(0); // terminator
1226                 }
1227         }
1228
1229         for (uint32_t i=0; i < 16; ++i) {
1230                 if ( _armHi16Locations[i].size() != 0 ) {
1231                         this->_encodedData.append_byte(32+i);
1232                         //fprintf(stderr, "type 32+%d:\n", i);
1233                         std::sort(_armHi16Locations[i].begin(), _armHi16Locations[i].end());
1234                         this->uleb128EncodeAddresses(_armHi16Locations[i]);
1235                         this->_encodedData.append_byte(0); // terminator
1236                 }
1237         }
1238
1239         // always add zero byte to mark end
1240         this->_encodedData.append_byte(0);
1241
1242         // align to pointer size
1243         this->_encodedData.pad_to_size(sizeof(pint_t));
1244
1245         this->_encoded = true;
1246
1247         // clean up temporaries
1248         _32bitPointerLocations.clear();
1249         _64bitPointerLocations.clear();
1250 }
1251
1252
1253 template <typename A>
1254 class FunctionStartsAtom : public LinkEditAtom
1255 {
1256 public:
1257                                                                                                 FunctionStartsAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
1258                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { }
1259
1260         // overrides of ld::Atom
1261         virtual const char*                                                     name() const            { return "function starts"; }
1262         // overrides of LinkEditAtom
1263         virtual void                                                            encode() const;
1264
1265 private:
1266         typedef typename A::P                                           P;
1267         typedef typename A::P::E                                        E;
1268         typedef typename A::P::uint_t                           pint_t;
1269
1270         static ld::Section                      _s_section;
1271 };
1272
1273 template <typename A>
1274 ld::Section FunctionStartsAtom<A>::_s_section("__LINKEDIT", "__funcStarts", ld::Section::typeLinkEdit, true);
1275
1276
1277 template <typename A>
1278 void FunctionStartsAtom<A>::encode() const
1279 {
1280         this->_encodedData.reserve(8192);
1281         const uint64_t badAddress = 1;
1282         uint64_t addr = badAddress;
1283         // delta compress all function addresses
1284         for (std::vector<ld::Internal::FinalSection*>::iterator it = this->_state.sections.begin(); it != this->_state.sections.end(); ++it) {
1285                 ld::Internal::FinalSection* sect = *it;
1286                 if ( sect->type() == ld::Section::typeMachHeader ) {
1287                         // start with delta from start of __TEXT
1288                         addr = sect->address;
1289                 }
1290                 else if ( sect->type() == ld::Section::typeCode ) {
1291                         assert(addr != badAddress);
1292                         std::vector<const ld::Atom*>& atoms = sect->atoms;
1293                         for (std::vector<const ld::Atom*>::iterator ait = atoms.begin(); ait != atoms.end(); ++ait) {
1294                                 const ld::Atom* atom = *ait;
1295                                 uint64_t nextAddr = atom->finalAddress();
1296                                 if ( atom->isThumb() )
1297                                         nextAddr |= 1;
1298                                 uint64_t delta = nextAddr - addr;
1299                                 if ( delta != 0 )
1300                                         this->_encodedData.append_uleb128(delta);
1301                                 addr = nextAddr;
1302                         }
1303                 }
1304         }
1305
1306         // terminator
1307         this->_encodedData.append_byte(0);
1308
1309         // align to pointer size
1310         this->_encodedData.pad_to_size(sizeof(pint_t));
1311
1312         this->_encoded = true;
1313 }
1314
1315
1316
1317 } // namespace tool
1318 } // namespace ld
1319
1320 #endif // __LINKEDIT_HPP__