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 #include <unordered_map>
  36
  37 #include "Options.h"
  38 #include "ld.hpp"
  39 #include "Architectures.hpp"
  40 #include "MachOFileAbstraction.hpp"
  41 #include "code-sign-blobs/superblob.h"
  42
  43 namespace ld {
  44 namespace tool {
  45
  46 class ByteStream {
  47 private:
  48         std::vector<uint8_t>            _data;
  49 public:
  50         std::vector<uint8_t>& bytes() { return _data; }
  51         unsigned long size() const { return _data.size(); }
  52         void reserve(unsigned long l) { _data.reserve(l); }
  53         const uint8_t* start() const { return &_data[0]; }
  54
  55         void append_uleb128(uint64_t value) {
  56                 uint8_t byte;
  57                 do {
  58                         byte = value & 0x7F;
  59                         value &= ~0x7F;
  60                         if ( value != 0 )
  61                                 byte |= 0x80;
  62                         _data.push_back(byte);
  63                         value = value >> 7;
  64                 } while( byte >= 0x80 );
  65         }
  66
  67         void append_sleb128(int64_t value) {
  68                 bool isNeg = ( value < 0 );
  69                 uint8_t byte;
  70                 bool more;
  71                 do {
  72                         byte = value & 0x7F;
  73                         value = value >> 7;
  74                         if ( isNeg )
  75                                 more = ( (value != -1) || ((byte & 0x40) == 0) );
  76                         else
  77                                 more = ( (value != 0) || ((byte & 0x40) != 0) );
  78                         if ( more )
  79                                 byte |= 0x80;
  80                         _data.push_back(byte);
  81                 }
  82                 while( more );
  83         }
  84
  85         void append_delta_encoded_uleb128_run(uint64_t start, const std::vector<uint64_t>& locations) {
  86                 uint64_t lastAddr = start;
  87                 for(std::vector<uint64_t>::const_iterator it = locations.begin(); it != locations.end(); ++it) {
  88                         uint64_t nextAddr = *it;
  89                         uint64_t delta = nextAddr - lastAddr;
  90                         assert(delta != 0);
  91                         append_uleb128(delta);
  92                         lastAddr = nextAddr;
  93                 }
  94         }
  95
  96         void append_string(const char* str) {
  97                 for (const char* s = str; *s != '\0'; ++s)
  98                         _data.push_back(*s);
  99                 _data.push_back('\0');
 100         }
 101
 102         void append_byte(uint8_t byte) {
 103                 _data.push_back(byte);
 104         }
 105
 106         static unsigned int     uleb128_size(uint64_t value) {
 107                 uint32_t result = 0;
 108                 do {
 109                         value = value >> 7;
 110                         ++result;
 111                 } while ( value != 0 );
 112                 return result;
 113         }
 114
 115         void pad_to_size(unsigned int alignment) {
 116                 while ( (_data.size() % alignment) != 0 )
 117                         _data.push_back(0);
 118         }
 119 };
 120
 121
 122 class LinkEditAtom : public ld::Atom
 123 {
 124 public:
 125
 126         // overrides of ld::Atom
 127         virtual ld::File*                                                       file() const            { return NULL; }
 128         virtual uint64_t                                                        objectAddress() const { return 0; }
 129         virtual uint64_t                                                        size() const;
 130         virtual void                                                            copyRawContent(uint8_t buffer[]) const;
 131
 132         virtual void                                                            encode() const = 0;
 133
 134                                                                                                 LinkEditAtom(const Options& opts, ld::Internal& state,
 135                                                                                                                                 OutputFile& writer, const ld::Section& sect,
 136                                                                                                                                 unsigned int pointerSize)
 137                                                                                                 : ld::Atom(sect, ld::Atom::definitionRegular,
 138                                                                                                                         ld::Atom::combineNever, ld::Atom::scopeTranslationUnit,
 139                                                                                                                         ld::Atom::typeUnclassified, ld::Atom::symbolTableNotIn,
 140                                                                                                                         false, false, false, ld::Atom::Alignment(log2(pointerSize))),
 141                                                                                                                 _options(opts), _state(state), _writer(writer),
 142                                                                                                                 _encoded(false) { }
 143 protected:
 144         const Options&                          _options;
 145         ld::Internal&                           _state;
 146         OutputFile&                                     _writer;
 147         mutable ByteStream                      _encodedData;
 148         mutable bool                            _encoded;
 149 };
 150
 151 uint64_t LinkEditAtom::size() const
 152 {
 153         assert(_encoded);
 154         return _encodedData.size();
 155 }
 156
 157 void LinkEditAtom::copyRawContent(uint8_t buffer[]) const
 158 {
 159         assert(_encoded);
 160         memcpy(buffer, _encodedData.start(), _encodedData.size());
 161 }
 162
 163
 164
 165
 166 template <typename A>
 167 class RebaseInfoAtom : public LinkEditAtom
 168 {
 169 public:
 170                                                                                                 RebaseInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 171                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { _encoded = true; }
 172
 173         // overrides of ld::Atom
 174         virtual const char*                                                     name() const            { return "rebase info"; }
 175         // overrides of LinkEditAtom
 176         virtual void                                                            encode() const;
 177
 178 private:
 179         struct rebase_tmp
 180         {
 181                 rebase_tmp(uint8_t op, uint64_t p1, uint64_t p2=0) : opcode(op), operand1(p1), operand2(p2) {}
 182                 uint8_t         opcode;
 183                 uint64_t        operand1;
 184                 uint64_t        operand2;
 185         };
 186
 187         typedef typename A::P                                           P;
 188         typedef typename A::P::E                                        E;
 189         typedef typename A::P::uint_t                           pint_t;
 190
 191         static ld::Section                      _s_section;
 192 };
 193
 194 template <typename A>
 195 ld::Section RebaseInfoAtom<A>::_s_section("__LINKEDIT", "__rebase", ld::Section::typeLinkEdit, true);
 196
 197
 198 template <typename A>
 199 void RebaseInfoAtom<A>::encode() const
 200 {
 201         // omit relocs if this was supposed to be PIE but PIE not possible
 202         if ( _options.positionIndependentExecutable() && this->_writer.pieDisabled )
 203                 return;
 204
 205         // sort rebase info by type, then address
 206         std::vector<OutputFile::RebaseInfo>& info = this->_writer._rebaseInfo;
 207         std::sort(info.begin(), info.end());
 208
 209         // convert to temp encoding that can be more easily optimized
 210         std::vector<rebase_tmp> mid;
 211         uint64_t curSegStart = 0;
 212         uint64_t curSegEnd = 0;
 213         uint32_t curSegIndex = 0;
 214         uint8_t type = 0;
 215         uint64_t address = (uint64_t)(-1);
 216         for (std::vector<OutputFile::RebaseInfo>::iterator it = info.begin(); it != info.end(); ++it) {
 217                 if ( type != it->_type ) {
 218                         mid.push_back(rebase_tmp(REBASE_OPCODE_SET_TYPE_IMM, it->_type));
 219                         type = it->_type;
 220                 }
 221                 if ( address != it->_address ) {
 222                         if ( (it->_address < curSegStart) || ( it->_address >= curSegEnd) ) {
 223                                 if ( ! this->_writer.findSegment(this->_state, it->_address, &curSegStart, &curSegEnd, &curSegIndex) )
 224                                         throw "binding address outside range of any segment";
 225                                 mid.push_back(rebase_tmp(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB, curSegIndex, it->_address - curSegStart));
 226                         }
 227                         else {
 228                                 mid.push_back(rebase_tmp(REBASE_OPCODE_ADD_ADDR_ULEB, it->_address-address));
 229                         }
 230                         address = it->_address;
 231                 }
 232                 mid.push_back(rebase_tmp(REBASE_OPCODE_DO_REBASE_ULEB_TIMES, 1));
 233                 address += sizeof(pint_t);
 234                 if ( address >= curSegEnd )
 235                         address = 0;
 236         }
 237         mid.push_back(rebase_tmp(REBASE_OPCODE_DONE, 0));
 238
 239         // optimize phase 1, compress packed runs of pointers
 240         rebase_tmp* dst = &mid[0];
 241         for (const rebase_tmp* src = &mid[0]; src->opcode != REBASE_OPCODE_DONE; ++src) {
 242                 if ( (src->opcode == REBASE_OPCODE_DO_REBASE_ULEB_TIMES) && (src->operand1 == 1) ) {
 243                         *dst = *src++;
 244                         while (src->opcode == REBASE_OPCODE_DO_REBASE_ULEB_TIMES ) {
 245                                 dst->operand1 += src->operand1;
 246                                 ++src;
 247                         }
 248                         --src;
 249                         ++dst;
 250                 }
 251                 else {
 252                         *dst++ = *src;
 253                 }
 254         }
 255         dst->opcode = REBASE_OPCODE_DONE;
 256
 257         // optimize phase 2, combine rebase/add pairs
 258         dst = &mid[0];
 259         for (const rebase_tmp* src = &mid[0]; src->opcode != REBASE_OPCODE_DONE; ++src) {
 260                 if ( (src->opcode == REBASE_OPCODE_DO_REBASE_ULEB_TIMES)
 261                                 && (src->operand1 == 1)
 262                                 && (src[1].opcode == REBASE_OPCODE_ADD_ADDR_ULEB)) {
 263                         dst->opcode = REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB;
 264                         dst->operand1 = src[1].operand1;
 265                         ++src;
 266                         ++dst;
 267                 }
 268                 else {
 269                         *dst++ = *src;
 270                 }
 271         }
 272         dst->opcode = REBASE_OPCODE_DONE;
 273
 274         // optimize phase 3, compress packed runs of REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB with
 275         // same addr delta into one REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB
 276         dst = &mid[0];
 277         for (const rebase_tmp* src = &mid[0]; src->opcode != REBASE_OPCODE_DONE; ++src) {
 278                 uint64_t delta = src->operand1;
 279                 if ( (src->opcode == REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB)
 280                                 && (src[1].opcode == REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB)
 281                                 && (src[2].opcode == REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB)
 282                                 && (src[1].operand1 == delta)
 283                                 && (src[2].operand1 == delta) ) {
 284                         // found at least three in a row, this is worth compressing
 285                         dst->opcode = REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB;
 286                         dst->operand1 = 1;
 287                         dst->operand2 = delta;
 288                         ++src;
 289                         while ( (src->opcode == REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB)
 290                                         && (src->operand1 == delta) ) {
 291                                 dst->operand1++;
 292                                 ++src;
 293                         }
 294                         --src;
 295                         ++dst;
 296                 }
 297                 else {
 298                         *dst++ = *src;
 299                 }
 300         }
 301         dst->opcode = REBASE_OPCODE_DONE;
 302
 303         // optimize phase 4, use immediate encodings
 304         for (rebase_tmp* p = &mid[0]; p->opcode != REBASE_OPCODE_DONE; ++p) {
 305                 if ( (p->opcode == REBASE_OPCODE_ADD_ADDR_ULEB)
 306                         && (p->operand1 < (15*sizeof(pint_t)))
 307                         && ((p->operand1 % sizeof(pint_t)) == 0) ) {
 308                         p->opcode = REBASE_OPCODE_ADD_ADDR_IMM_SCALED;
 309                         p->operand1 = p->operand1/sizeof(pint_t);
 310                 }
 311                 else if ( (p->opcode == REBASE_OPCODE_DO_REBASE_ULEB_TIMES) && (p->operand1 < 15) ) {
 312                         p->opcode = REBASE_OPCODE_DO_REBASE_IMM_TIMES;
 313                 }
 314         }
 315
 316         // convert to compressed encoding
 317         const static bool log = false;
 318         this->_encodedData.reserve(info.size()*2);
 319         bool done = false;
 320         for (typename std::vector<rebase_tmp>::iterator it = mid.begin(); !done && it != mid.end() ; ++it) {
 321                 switch ( it->opcode ) {
 322                         case REBASE_OPCODE_DONE:
 323                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DONE()\n");
 324                                 done = true;
 325                                 break;
 326                         case REBASE_OPCODE_SET_TYPE_IMM:
 327                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_SET_TYPE_IMM(%lld)\n", it->operand1);
 328                                 this->_encodedData.append_byte(REBASE_OPCODE_SET_TYPE_IMM | it->operand1);
 329                                 break;
 330                         case REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
 331                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB(%lld, 0x%llX)\n", it->operand1, it->operand2);
 332                                 this->_encodedData.append_byte(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | it->operand1);
 333                                 this->_encodedData.append_uleb128(it->operand2);
 334                                 break;
 335                         case REBASE_OPCODE_ADD_ADDR_ULEB:
 336                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 337                                 this->_encodedData.append_byte(REBASE_OPCODE_ADD_ADDR_ULEB);
 338                                 this->_encodedData.append_uleb128(it->operand1);
 339                                 break;
 340                         case REBASE_OPCODE_ADD_ADDR_IMM_SCALED:
 341                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_ADD_ADDR_IMM_SCALED(%lld=0x%llX)\n", it->operand1, it->operand1*sizeof(pint_t));
 342                                 this->_encodedData.append_byte(REBASE_OPCODE_ADD_ADDR_IMM_SCALED | it->operand1 );
 343                                 break;
 344                         case REBASE_OPCODE_DO_REBASE_IMM_TIMES:
 345                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DO_REBASE_IMM_TIMES(%lld)\n", it->operand1);
 346                                 this->_encodedData.append_byte(REBASE_OPCODE_DO_REBASE_IMM_TIMES | it->operand1);
 347                                 break;
 348                         case REBASE_OPCODE_DO_REBASE_ULEB_TIMES:
 349                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DO_REBASE_ULEB_TIMES(%lld)\n", it->operand1);
 350                                 this->_encodedData.append_byte(REBASE_OPCODE_DO_REBASE_ULEB_TIMES);
 351                                 this->_encodedData.append_uleb128(it->operand1);
 352                                 break;
 353                         case REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB:
 354                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 355                                 this->_encodedData.append_byte(REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB);
 356                                 this->_encodedData.append_uleb128(it->operand1);
 357                                 break;
 358                         case REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB:
 359                                 if ( log ) fprintf(stderr, "REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB(%lld, %lld)\n", it->operand1, it->operand2);
 360                                 this->_encodedData.append_byte(REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB);
 361                                 this->_encodedData.append_uleb128(it->operand1);
 362                                 this->_encodedData.append_uleb128(it->operand2);
 363                                 break;
 364                 }
 365         }
 366
 367
 368         // align to pointer size
 369         this->_encodedData.pad_to_size(sizeof(pint_t));
 370
 371         this->_encoded = true;
 372
 373         if (log) fprintf(stderr, "total rebase info size = %ld\n", this->_encodedData.size());
 374 }
 375
 376
 377 template <typename A>
 378 class BindingInfoAtom : public LinkEditAtom
 379 {
 380 public:
 381                                                                                                 BindingInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 382                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { }
 383
 384         // overrides of ld::Atom
 385         virtual const char*                                                     name() const            { return "binding info"; }
 386         // overrides of LinkEditAtom
 387         virtual void                                                            encode() const;
 388
 389
 390 private:
 391         typedef typename A::P                                           P;
 392         typedef typename A::P::E                                        E;
 393         typedef typename A::P::uint_t                           pint_t;
 394
 395         struct binding_tmp
 396         {
 397                 binding_tmp(uint8_t op, uint64_t p1, uint64_t p2=0, const char* s=NULL)
 398                         : opcode(op), operand1(p1), operand2(p2), name(s) {}
 399                 uint8_t         opcode;
 400                 uint64_t        operand1;
 401                 uint64_t        operand2;
 402                 const char*     name;
 403         };
 404
 405         static ld::Section                      _s_section;
 406 };
 407
 408 template <typename A>
 409 ld::Section BindingInfoAtom<A>::_s_section("__LINKEDIT", "__binding", ld::Section::typeLinkEdit, true);
 410
 411
 412 template <typename A>
 413 void BindingInfoAtom<A>::encode() const
 414 {
 415         // sort by library, symbol, type, then address
 416         std::vector<OutputFile::BindingInfo>& info = this->_writer._bindingInfo;
 417         std::sort(info.begin(), info.end());
 418
 419         // convert to temp encoding that can be more easily optimized
 420         std::vector<binding_tmp> mid;
 421         uint64_t curSegStart = 0;
 422         uint64_t curSegEnd = 0;
 423         uint32_t curSegIndex = 0;
 424         int ordinal = 0x80000000;
 425         const char* symbolName = NULL;
 426         uint8_t type = 0;
 427         uint64_t address = (uint64_t)(-1);
 428         int64_t addend = 0;
 429         for (std::vector<OutputFile::BindingInfo>::const_iterator it = info.begin(); it != info.end(); ++it) {
 430                 if ( ordinal != it->_libraryOrdinal ) {
 431                         if ( it->_libraryOrdinal <= 0 ) {
 432                                 // special lookups are encoded as negative numbers in BindingInfo
 433                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM, it->_libraryOrdinal));
 434                         }
 435                         else {
 436                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB, it->_libraryOrdinal));
 437                         }
 438                         ordinal = it->_libraryOrdinal;
 439                 }
 440                 if ( symbolName != it->_symbolName ) {
 441                         mid.push_back(binding_tmp(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM, it->_flags, 0, it->_symbolName));
 442                         symbolName = it->_symbolName;
 443                 }
 444                 if ( type != it->_type ) {
 445                         mid.push_back(binding_tmp(BIND_OPCODE_SET_TYPE_IMM, it->_type));
 446                         type = it->_type;
 447                 }
 448                 if ( address != it->_address ) {
 449                         if ( (it->_address < curSegStart) || ( it->_address >= curSegEnd) ) {
 450                                 if ( ! this->_writer.findSegment(this->_state, it->_address, &curSegStart, &curSegEnd, &curSegIndex) )
 451                                         throw "binding address outside range of any segment";
 452                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB, curSegIndex, it->_address - curSegStart));
 453                         }
 454                         else {
 455                                 mid.push_back(binding_tmp(BIND_OPCODE_ADD_ADDR_ULEB, it->_address-address));
 456                         }
 457                         address = it->_address;
 458                 }
 459                 if ( addend != it->_addend ) {
 460                         mid.push_back(binding_tmp(BIND_OPCODE_SET_ADDEND_SLEB, it->_addend));
 461                         addend = it->_addend;
 462                 }
 463                 mid.push_back(binding_tmp(BIND_OPCODE_DO_BIND, 0));
 464                 address += sizeof(pint_t);
 465         }
 466         mid.push_back(binding_tmp(BIND_OPCODE_DONE, 0));
 467
 468
 469         // optimize phase 1, combine bind/add pairs
 470         binding_tmp* dst = &mid[0];
 471         for (const binding_tmp* src = &mid[0]; src->opcode != BIND_OPCODE_DONE; ++src) {
 472                 if ( (src->opcode == BIND_OPCODE_DO_BIND)
 473                                 && (src[1].opcode == BIND_OPCODE_ADD_ADDR_ULEB) ) {
 474                         dst->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
 475                         dst->operand1 = src[1].operand1;
 476                         ++src;
 477                         ++dst;
 478                 }
 479                 else {
 480                         *dst++ = *src;
 481                 }
 482         }
 483         dst->opcode = BIND_OPCODE_DONE;
 484
 485         // optimize phase 2, compress packed runs of BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB with
 486         // same addr delta into one BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB
 487         dst = &mid[0];
 488         for (const binding_tmp* src = &mid[0]; src->opcode != BIND_OPCODE_DONE; ++src) {
 489                 uint64_t delta = src->operand1;
 490                 if ( (src->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 491                                 && (src[1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 492                                 && (src[1].operand1 == delta) ) {
 493                         // found at least two in a row, this is worth compressing
 494                         dst->opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
 495                         dst->operand1 = 1;
 496                         dst->operand2 = delta;
 497                         ++src;
 498                         while ( (src->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 499                                         && (src->operand1 == delta) ) {
 500                                 dst->operand1++;
 501                                 ++src;
 502                         }
 503                         --src;
 504                         ++dst;
 505                 }
 506                 else {
 507                         *dst++ = *src;
 508                 }
 509         }
 510         dst->opcode = BIND_OPCODE_DONE;
 511
 512         // optimize phase 3, use immediate encodings
 513         for (binding_tmp* p = &mid[0]; p->opcode != REBASE_OPCODE_DONE; ++p) {
 514                 if ( (p->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 515                         && (p->operand1 < (15*sizeof(pint_t)))
 516                         && ((p->operand1 % sizeof(pint_t)) == 0) ) {
 517                         p->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
 518                         p->operand1 = p->operand1/sizeof(pint_t);
 519                 }
 520                 else if ( (p->opcode == BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB) && (p->operand1 <= 15) ) {
 521                         p->opcode = BIND_OPCODE_SET_DYLIB_ORDINAL_IMM;
 522                 }
 523         }
 524         dst->opcode = BIND_OPCODE_DONE;
 525
 526         // convert to compressed encoding
 527         const static bool log = false;
 528         this->_encodedData.reserve(info.size()*2);
 529         bool done = false;
 530         for (typename std::vector<binding_tmp>::iterator it = mid.begin(); !done && it != mid.end() ; ++it) {
 531                 switch ( it->opcode ) {
 532                         case BIND_OPCODE_DONE:
 533                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DONE()\n");
 534                                 done = true;
 535                                 break;
 536                         case BIND_OPCODE_SET_DYLIB_ORDINAL_IMM:
 537                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_ORDINAL_IMM(%lld)\n", it->operand1);
 538                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | it->operand1);
 539                                 break;
 540                         case BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB:
 541                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB(%lld)\n", it->operand1);
 542                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
 543                                 this->_encodedData.append_uleb128(it->operand1);
 544                                 break;
 545                         case BIND_OPCODE_SET_DYLIB_SPECIAL_IMM:
 546                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_SPECIAL_IMM(%lld)\n", it->operand1);
 547                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM | (it->operand1 & BIND_IMMEDIATE_MASK));
 548                                 break;
 549                         case BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
 550                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM(0x%0llX, %s)\n", it->operand1, it->name);
 551                                 this->_encodedData.append_byte(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | it->operand1);
 552                                 this->_encodedData.append_string(it->name);
 553                                 break;
 554                         case BIND_OPCODE_SET_TYPE_IMM:
 555                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_TYPE_IMM(%lld)\n", it->operand1);
 556                                 this->_encodedData.append_byte(BIND_OPCODE_SET_TYPE_IMM | it->operand1);
 557                                 break;
 558                         case BIND_OPCODE_SET_ADDEND_SLEB:
 559                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_ADDEND_SLEB(%lld)\n", it->operand1);
 560                                 this->_encodedData.append_byte(BIND_OPCODE_SET_ADDEND_SLEB);
 561                                 this->_encodedData.append_sleb128(it->operand1);
 562                                 break;
 563                         case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
 564                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB(%lld, 0x%llX)\n", it->operand1, it->operand2);
 565                                 this->_encodedData.append_byte(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | it->operand1);
 566                                 this->_encodedData.append_uleb128(it->operand2);
 567                                 break;
 568                         case BIND_OPCODE_ADD_ADDR_ULEB:
 569                                 if ( log ) fprintf(stderr, "BIND_OPCODE_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 570                                 this->_encodedData.append_byte(BIND_OPCODE_ADD_ADDR_ULEB);
 571                                 this->_encodedData.append_uleb128(it->operand1);
 572                                 break;
 573                         case BIND_OPCODE_DO_BIND:
 574                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND()\n");
 575                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND);
 576                                 break;
 577                         case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
 578                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 579                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB);
 580                                 this->_encodedData.append_uleb128(it->operand1);
 581                                 break;
 582                         case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
 583                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED(%lld=0x%llX)\n", it->operand1, it->operand1*sizeof(pint_t));
 584                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED | it->operand1 );
 585                                 break;
 586                         case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
 587                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB(%lld, %lld)\n", it->operand1, it->operand2);
 588                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB);
 589                                 this->_encodedData.append_uleb128(it->operand1);
 590                                 this->_encodedData.append_uleb128(it->operand2);
 591                                 break;
 592                 }
 593         }
 594
 595         // align to pointer size
 596         this->_encodedData.pad_to_size(sizeof(pint_t));
 597
 598         this->_encoded = true;
 599
 600         if (log) fprintf(stderr, "total binding info size = %ld\n", this->_encodedData.size());
 601 }
 602
 603
 604
 605 template <typename A>
 606 class WeakBindingInfoAtom : public LinkEditAtom
 607 {
 608 public:
 609                                                                                                 WeakBindingInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 610                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { _encoded = true; }
 611
 612         // overrides of ld::Atom
 613         virtual const char*                                                     name() const            { return "weak binding info"; }
 614         // overrides of LinkEditAtom
 615         virtual void                                                            encode() const;
 616
 617 private:
 618         typedef typename A::P                                           P;
 619         typedef typename A::P::E                                        E;
 620         typedef typename A::P::uint_t                           pint_t;
 621
 622         struct WeakBindingSorter
 623         {
 624                  bool operator()(const OutputFile::BindingInfo& left, const OutputFile::BindingInfo& right)
 625                  {
 626                         // sort by symbol, type, address
 627                         if ( left._symbolName != right._symbolName )
 628                                 return ( strcmp(left._symbolName, right._symbolName) < 0 );
 629                         if ( left._type != right._type )
 630                                 return  (left._type < right._type);
 631                         return  (left._address < right._address);
 632                  }
 633         };
 634
 635         struct binding_tmp
 636         {
 637                 binding_tmp(uint8_t op, uint64_t p1, uint64_t p2=0, const char* s=NULL)
 638                         : opcode(op), operand1(p1), operand2(p2), name(s) {}
 639                 uint8_t         opcode;
 640                 uint64_t        operand1;
 641                 uint64_t        operand2;
 642                 const char*     name;
 643         };
 644
 645         static ld::Section                      _s_section;
 646 };
 647
 648 template <typename A>
 649 ld::Section WeakBindingInfoAtom<A>::_s_section("__LINKEDIT", "__weak_binding", ld::Section::typeLinkEdit, true);
 650
 651
 652 template <typename A>
 653 void WeakBindingInfoAtom<A>::encode() const
 654 {
 655         // sort by symbol, type, address
 656         std::vector<OutputFile::BindingInfo>& info = this->_writer._weakBindingInfo;
 657         if ( info.size() == 0 ) {
 658                 // short circuit if no weak binding needed
 659                 this->_encoded = true;
 660                 return;
 661         }
 662         std::sort(info.begin(), info.end(), WeakBindingSorter());
 663
 664         // convert to temp encoding that can be more easily optimized
 665         std::vector<binding_tmp> mid;
 666         mid.reserve(info.size());
 667         uint64_t curSegStart = 0;
 668         uint64_t curSegEnd = 0;
 669         uint32_t curSegIndex = 0;
 670         const char* symbolName = NULL;
 671         uint8_t type = 0;
 672         uint64_t address = (uint64_t)(-1);
 673         int64_t addend = 0;
 674         for (typename std::vector<OutputFile::BindingInfo>::const_iterator it = info.begin(); it != info.end(); ++it) {
 675                 if ( symbolName != it->_symbolName ) {
 676                         mid.push_back(binding_tmp(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM, it->_flags, 0, it->_symbolName));
 677                         symbolName = it->_symbolName;
 678                 }
 679                 // non-weak symbols just have BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM
 680                 // weak symbols have SET_SEG, ADD_ADDR, SET_ADDED, DO_BIND
 681                 if ( it->_type != BIND_TYPE_OVERRIDE_OF_WEAKDEF_IN_DYLIB ) {
 682                         if ( type != it->_type ) {
 683                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_TYPE_IMM, it->_type));
 684                                 type = it->_type;
 685                         }
 686                         if ( address != it->_address ) {
 687                                 if ( (it->_address < curSegStart) || ( it->_address >= curSegEnd) ) {
 688                                         if ( ! this->_writer.findSegment(this->_state, it->_address, &curSegStart, &curSegEnd, &curSegIndex) )
 689                                                 throw "binding address outside range of any segment";
 690                                         mid.push_back(binding_tmp(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB, curSegIndex, it->_address - curSegStart));
 691                                 }
 692                                 else {
 693                                         mid.push_back(binding_tmp(BIND_OPCODE_ADD_ADDR_ULEB, it->_address-address));
 694                                 }
 695                                 address = it->_address;
 696                         }
 697                         if ( addend != it->_addend ) {
 698                                 mid.push_back(binding_tmp(BIND_OPCODE_SET_ADDEND_SLEB, it->_addend));
 699                                 addend = it->_addend;
 700                         }
 701                         mid.push_back(binding_tmp(BIND_OPCODE_DO_BIND, 0));
 702                         address += sizeof(pint_t);
 703                 }
 704         }
 705         mid.push_back(binding_tmp(BIND_OPCODE_DONE, 0));
 706
 707
 708         // optimize phase 1, combine bind/add pairs
 709         binding_tmp* dst = &mid[0];
 710         for (const binding_tmp* src = &mid[0]; src->opcode != BIND_OPCODE_DONE; ++src) {
 711                 if ( (src->opcode == BIND_OPCODE_DO_BIND)
 712                                 && (src[1].opcode == BIND_OPCODE_ADD_ADDR_ULEB) ) {
 713                         dst->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
 714                         dst->operand1 = src[1].operand1;
 715                         ++src;
 716                         ++dst;
 717                 }
 718                 else {
 719                         *dst++ = *src;
 720                 }
 721         }
 722         dst->opcode = BIND_OPCODE_DONE;
 723
 724         // optimize phase 2, compress packed runs of BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB with
 725         // same addr delta into one BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB
 726         dst = &mid[0];
 727         for (const binding_tmp* src = &mid[0]; src->opcode != BIND_OPCODE_DONE; ++src) {
 728                 uint64_t delta = src->operand1;
 729                 if ( (src->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 730                                 && (src[1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 731                                 && (src[1].operand1 == delta) ) {
 732                         // found at least two in a row, this is worth compressing
 733                         dst->opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
 734                         dst->operand1 = 1;
 735                         dst->operand2 = delta;
 736                         ++src;
 737                         while ( (src->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 738                                         && (src->operand1 == delta) ) {
 739                                 dst->operand1++;
 740                                 ++src;
 741                         }
 742                         --src;
 743                         ++dst;
 744                 }
 745                 else {
 746                         *dst++ = *src;
 747                 }
 748         }
 749         dst->opcode = BIND_OPCODE_DONE;
 750
 751         // optimize phase 3, use immediate encodings
 752         for (binding_tmp* p = &mid[0]; p->opcode != REBASE_OPCODE_DONE; ++p) {
 753                 if ( (p->opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB)
 754                         && (p->operand1 < (15*sizeof(pint_t)))
 755                         && ((p->operand1 % sizeof(pint_t)) == 0) ) {
 756                         p->opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
 757                         p->operand1 = p->operand1/sizeof(pint_t);
 758                 }
 759         }
 760         dst->opcode = BIND_OPCODE_DONE;
 761
 762
 763         // convert to compressed encoding
 764         const static bool log = false;
 765         this->_encodedData.reserve(info.size()*2);
 766         bool done = false;
 767         for (typename std::vector<binding_tmp>::iterator it = mid.begin(); !done && it != mid.end() ; ++it) {
 768                 switch ( it->opcode ) {
 769                         case BIND_OPCODE_DONE:
 770                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DONE()\n");
 771                                 this->_encodedData.append_byte(BIND_OPCODE_DONE);
 772                                 done = true;
 773                                 break;
 774                         case BIND_OPCODE_SET_DYLIB_ORDINAL_IMM:
 775                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_ORDINAL_IMM(%lld)\n", it->operand1);
 776                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | it->operand1);
 777                                 break;
 778                         case BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB:
 779                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB(%lld)\n", it->operand1);
 780                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
 781                                 this->_encodedData.append_uleb128(it->operand1);
 782                                 break;
 783                         case BIND_OPCODE_SET_DYLIB_SPECIAL_IMM:
 784                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_DYLIB_SPECIAL_IMM(%lld)\n", it->operand1);
 785                                 this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM | (it->operand1 & BIND_IMMEDIATE_MASK));
 786                                 break;
 787                         case BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
 788                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM(0x%0llX, %s)\n", it->operand1, it->name);
 789                                 this->_encodedData.append_byte(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | it->operand1);
 790                                 this->_encodedData.append_string(it->name);
 791                                 break;
 792                         case BIND_OPCODE_SET_TYPE_IMM:
 793                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_TYPE_IMM(%lld)\n", it->operand1);
 794                                 this->_encodedData.append_byte(BIND_OPCODE_SET_TYPE_IMM | it->operand1);
 795                                 break;
 796                         case BIND_OPCODE_SET_ADDEND_SLEB:
 797                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_ADDEND_SLEB(%lld)\n", it->operand1);
 798                                 this->_encodedData.append_byte(BIND_OPCODE_SET_ADDEND_SLEB);
 799                                 this->_encodedData.append_sleb128(it->operand1);
 800                                 break;
 801                         case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
 802                                 if ( log ) fprintf(stderr, "BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB(%lld, 0x%llX)\n", it->operand1, it->operand2);
 803                                 this->_encodedData.append_byte(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | it->operand1);
 804                                 this->_encodedData.append_uleb128(it->operand2);
 805                                 break;
 806                         case BIND_OPCODE_ADD_ADDR_ULEB:
 807                                 if ( log ) fprintf(stderr, "BIND_OPCODE_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 808                                 this->_encodedData.append_byte(BIND_OPCODE_ADD_ADDR_ULEB);
 809                                 this->_encodedData.append_uleb128(it->operand1);
 810                                 break;
 811                         case BIND_OPCODE_DO_BIND:
 812                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND()\n");
 813                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND);
 814                                 break;
 815                         case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
 816                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB(0x%llX)\n", it->operand1);
 817                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB);
 818                                 this->_encodedData.append_uleb128(it->operand1);
 819                                 break;
 820                         case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
 821                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED(%lld=0x%llX)\n", it->operand1, it->operand1*sizeof(pint_t));
 822                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED | it->operand1 );
 823                                 break;
 824                         case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
 825                                 if ( log ) fprintf(stderr, "BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB(%lld, %lld)\n", it->operand1, it->operand2);
 826                                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB);
 827                                 this->_encodedData.append_uleb128(it->operand1);
 828                                 this->_encodedData.append_uleb128(it->operand2);
 829                                 break;
 830                 }
 831         }
 832
 833         // align to pointer size
 834         this->_encodedData.pad_to_size(sizeof(pint_t));
 835
 836         this->_encoded = true;
 837
 838         if (log) fprintf(stderr, "total weak binding info size = %ld\n", this->_encodedData.size());
 839
 840 }
 841
 842
 843
 844 template <typename A>
 845 class LazyBindingInfoAtom : public LinkEditAtom
 846 {
 847 public:
 848                                                                                                 LazyBindingInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 849                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) {_encoded = true;  }
 850
 851         // overrides of ld::Atom
 852         virtual const char*                                                     name() const            { return "lazy binding info"; }
 853         // overrides of LinkEditAtom
 854         virtual void                                                            encode() const;
 855
 856 private:
 857         typedef typename A::P                                           P;
 858         typedef typename A::P::E                                        E;
 859         typedef typename A::P::uint_t                           pint_t;
 860
 861         static ld::Section                      _s_section;
 862 };
 863
 864 template <typename A>
 865 ld::Section LazyBindingInfoAtom<A>::_s_section("__LINKEDIT", "__lazy_binding", ld::Section::typeLinkEdit, true);
 866
 867
 868
 869 template <typename A>
 870 void LazyBindingInfoAtom<A>::encode() const
 871 {
 872         // stream all lazy bindings and record start offsets
 873         std::vector<OutputFile::BindingInfo>& info = this->_writer._lazyBindingInfo;
 874         for (std::vector<OutputFile::BindingInfo>::const_iterator it = info.begin(); it != info.end(); ++it) {
 875                 // record start offset for use by stub helper
 876                 this->_writer.setLazyBindingInfoOffset(it->_address, this->_encodedData.size());
 877
 878                 // write address to bind
 879                 uint64_t segStart = 0;
 880                 uint64_t segEnd = 0;
 881                 uint32_t segIndex = 0;
 882                 if ( ! this->_writer.findSegment(this->_state, it->_address, &segStart, &segEnd, &segIndex) )
 883                         throw "lazy binding address outside range of any segment";
 884                 this->_encodedData.append_byte(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | segIndex);
 885                 this->_encodedData.append_uleb128(it->_address - segStart);
 886
 887                 // write ordinal
 888                 if ( it->_libraryOrdinal <= 0 ) {
 889                         // special lookups are encoded as negative numbers in BindingInfo
 890                         this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM | (it->_libraryOrdinal & BIND_IMMEDIATE_MASK) );
 891                 }
 892                 else if ( it->_libraryOrdinal <= 15 ) {
 893                         // small ordinals are encoded in opcode
 894                         this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | it->_libraryOrdinal);
 895                 }
 896                 else {
 897                         this->_encodedData.append_byte(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
 898                         this->_encodedData.append_uleb128(it->_libraryOrdinal);
 899                 }
 900                 // write symbol name
 901                 this->_encodedData.append_byte(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | it->_flags);
 902                 this->_encodedData.append_string(it->_symbolName);
 903                 // write do bind
 904                 this->_encodedData.append_byte(BIND_OPCODE_DO_BIND);
 905                 this->_encodedData.append_byte(BIND_OPCODE_DONE);
 906         }
 907
 908         // align to pointer size
 909         this->_encodedData.pad_to_size(sizeof(pint_t));
 910
 911         this->_encoded = true;
 912         //fprintf(stderr, "lazy binding info size = %ld, for %ld entries\n", _encodedData.size(), allLazys.size());
 913 }
 914
 915
 916
 917 template <typename A>
 918 class ExportInfoAtom : public LinkEditAtom
 919 {
 920 public:
 921                                                                                                 ExportInfoAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
 922                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { _encoded = true; }
 923
 924         // overrides of ld::Atom
 925         virtual const char*                                                     name() const            { return "export info"; }
 926         // overrides of LinkEditAtom
 927         virtual void                                                            encode() const;
 928
 929 private:
 930         typedef typename A::P                                           P;
 931         typedef typename A::P::E                                        E;
 932         typedef typename A::P::uint_t                           pint_t;
 933
 934         const ld::Atom*                                                         stubForResolverFunction(const ld::Atom* resolver) const;
 935
 936         struct TrieEntriesSorter
 937         {
 938                 TrieEntriesSorter(const Options& o) : _options(o) {}
 939
 940                  bool operator()(const mach_o::trie::Entry& left, const mach_o::trie::Entry& right)
 941                  {
 942                         unsigned int leftOrder;
 943                         unsigned int rightOrder;
 944                         _options.exportedSymbolOrder(left.name, &leftOrder);
 945                         _options.exportedSymbolOrder(right.name, &rightOrder);
 946                         if ( leftOrder != rightOrder )
 947                                 return (leftOrder < rightOrder);
 948                         else
 949                                 return (left.address < right.address);
 950                  }
 951         private:
 952                 const Options&  _options;
 953         };
 954
 955         static ld::Section                      _s_section;
 956 };
 957
 958 template <typename A>
 959 ld::Section ExportInfoAtom<A>::_s_section("__LINKEDIT", "__export", ld::Section::typeLinkEdit, true);
 960
 961 template <typename A>
 962 const ld::Atom* ExportInfoAtom<A>::stubForResolverFunction(const ld::Atom* resolver) const
 963 {
 964         for (std::vector<ld::Internal::FinalSection*>::iterator sit = _state.sections.begin(); sit != _state.sections.end(); ++sit) {
 965                 ld::Internal::FinalSection* sect = *sit;
 966                 if ( (sect->type() == ld::Section::typeStub) || (sect->type() == ld::Section::typeStubClose) ) {
 967                         for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 968                                 const ld::Atom* atom = *ait;
 969                                 if ( strcmp(atom->name(), resolver->name()) == 0 )
 970                                         return atom;
 971                         }
 972                 }
 973         }
 974         assert(0 && "no stub for resolver function");
 975         return NULL;
 976 }
 977
 978
 979 template <typename A>
 980 void ExportInfoAtom<A>::encode() const
 981 {
 982         // make vector of mach_o::trie::Entry for all exported symbols
 983         std::vector<const ld::Atom*>& exports = this->_writer._exportedAtoms;
 984         uint64_t imageBaseAddress = this->_writer.headerAndLoadCommandsSection->address;
 985         std::vector<mach_o::trie::Entry> entries;
 986         unsigned int padding = 0;
 987         entries.reserve(exports.size());
 988         for (std::vector<const ld::Atom*>::const_iterator it = exports.begin(); it != exports.end(); ++it) {
 989                 const ld::Atom* atom = *it;
 990                 mach_o::trie::Entry entry;
 991                 uint64_t flags = (atom->contentType() == ld::Atom::typeTLV) ? EXPORT_SYMBOL_FLAGS_KIND_THREAD_LOCAL : EXPORT_SYMBOL_FLAGS_KIND_REGULAR;
 992                 uint64_t other = 0;
 993                 uint64_t address = atom->finalAddress() - imageBaseAddress;
 994                 if ( atom->definition() == ld::Atom::definitionProxy ) {
 995                         entry.name = atom->name();
 996                         entry.flags = flags | EXPORT_SYMBOL_FLAGS_REEXPORT;
 997                         if ( atom->combine() == ld::Atom::combineByName )
 998                                 entry.flags |= EXPORT_SYMBOL_FLAGS_WEAK_DEFINITION;
 999                         entry.other = this->_writer.compressedOrdinalForAtom(atom);
1000                         if ( entry.other == BIND_SPECIAL_DYLIB_SELF ) {
1001                                 warning("not adding explict export for symbol %s because it is already re-exported from dylib %s", entry.name, atom->file()->path());
1002                                 continue;
1003                         }
1004                         if ( atom->isAlias() ) {
1005                                 // alias proxy means symbol was re-exported with a name change
1006                                 const ld::Atom* aliasOf = NULL;
1007                                 for (ld::Fixup::iterator fit = atom->fixupsBegin(); fit != atom->fixupsEnd(); ++fit) {
1008                                         if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
1009                                                 assert(fit->binding == ld::Fixup::bindingDirectlyBound);
1010                                                 aliasOf = fit->u.target;
1011                                         }
1012                                 }
1013                                 assert(aliasOf != NULL);
1014                                 entry.importName = aliasOf->name();
1015                         }
1016                         else {
1017                                 // symbol name stays same as re-export
1018                                 entry.importName = atom->name();
1019                         }
1020                         entries.push_back(entry);
1021                         //fprintf(stderr, "re-export %s from lib %llu as %s\n", entry.importName, entry.other, entry.name);
1022                 }
1023                 else if ( atom->definition() == ld::Atom::definitionAbsolute ) {
1024                         entry.name = atom->name();
1025                         entry.flags = _options.canUseAbsoluteSymbols() ? EXPORT_SYMBOL_FLAGS_KIND_ABSOLUTE : EXPORT_SYMBOL_FLAGS_KIND_REGULAR;
1026                         entry.address = address;
1027                         entry.other = other;
1028                         entry.importName = NULL;
1029                         entries.push_back(entry);
1030                 }
1031                 else {
1032                         if ( (atom->definition() == ld::Atom::definitionRegular) && (atom->combine() == ld::Atom::combineByName) )
1033                                 flags |= EXPORT_SYMBOL_FLAGS_WEAK_DEFINITION;
1034                         if ( atom->isThumb() )
1035                                 address |= 1;
1036                         if ( atom->contentType() == ld::Atom::typeResolver ) {
1037                                 flags |= EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER;
1038                                 // set normal lookup to return stub address
1039                                 // and add resolver function in new location that newer dyld's can access
1040                                 other = address;
1041                                 const ld::Atom* stub = stubForResolverFunction(atom);
1042                                 address = stub->finalAddress() - imageBaseAddress;
1043                                 if ( stub->isThumb() )
1044                                         address |= 1;
1045                         }
1046                         entry.name = atom->name();
1047                         entry.flags = flags;
1048                         entry.address = address;
1049                         entry.other = other;
1050                         entry.importName = NULL;
1051                         entries.push_back(entry);
1052                 }
1053
1054                 if (_options.sharedRegionEligible() && strncmp(atom->section().segmentName(), "__DATA", 6) == 0) {
1055                         // Maximum address is 64bit which is 10 bytes as a uleb128. Minimum is 1 byte
1056                         // Pad the section out so we can deal with addresses getting larger when __DATA segment
1057                         // is moved before __TEXT in dyld shared cache.
1058                         padding += 9;
1059                 }
1060         }
1061
1062         // sort vector by -exported_symbols_order, and any others by address
1063         std::sort(entries.begin(), entries.end(), TrieEntriesSorter(_options));
1064
1065         // create trie
1066         mach_o::trie::makeTrie(entries, this->_encodedData.bytes());
1067
1068         //Add additional data padding for the unoptimized shared cache
1069         for (unsigned int i = 0; i < padding; ++i)
1070                 this->_encodedData.append_byte(0);
1071
1072         // align to pointer size
1073         this->_encodedData.pad_to_size(sizeof(pint_t));
1074
1075         this->_encoded = true;
1076 }
1077
1078
1079 template <typename A>
1080 class SplitSegInfoV1Atom : public LinkEditAtom
1081 {
1082 public:
1083                                                                                                 SplitSegInfoV1Atom(const Options& opts, ld::Internal& state, OutputFile& writer)
1084                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { }
1085
1086         // overrides of ld::Atom
1087         virtual const char*                                                     name() const            { return "split seg info"; }
1088         // overrides of LinkEditAtom
1089         virtual void                                                            encode() const;
1090
1091 private:
1092         typedef typename A::P                                           P;
1093         typedef typename A::P::E                                        E;
1094         typedef typename A::P::uint_t                           pint_t;
1095
1096         void                                                                            addSplitSegInfo(uint64_t address, ld::Fixup::Kind k, uint32_t) const;
1097         void                                                                            uleb128EncodeAddresses(const std::vector<uint64_t>& locations) const;
1098
1099         mutable std::vector<uint64_t>                           _32bitPointerLocations;
1100         mutable std::vector<uint64_t>                           _64bitPointerLocations;
1101         mutable std::vector<uint64_t>                           _thumbLo16Locations;
1102         mutable std::vector<uint64_t>                           _thumbHi16Locations[16];
1103         mutable std::vector<uint64_t>                           _armLo16Locations;
1104         mutable std::vector<uint64_t>                           _armHi16Locations[16];
1105         mutable std::vector<uint64_t>                           _adrpLocations;
1106
1107
1108         static ld::Section                      _s_section;
1109 };
1110
1111 template <typename A>
1112 ld::Section SplitSegInfoV1Atom<A>::_s_section("__LINKEDIT", "__splitSegInfo", ld::Section::typeLinkEdit, true);
1113
1114 template <>
1115 void SplitSegInfoV1Atom<x86_64>::addSplitSegInfo(uint64_t address, ld::Fixup::Kind kind, uint32_t extra) const
1116 {
1117         switch (kind) {
1118                 case ld::Fixup::kindStoreX86PCRel32:
1119                 case ld::Fixup::kindStoreX86PCRel32_1:
1120                 case ld::Fixup::kindStoreX86PCRel32_2:
1121                 case ld::Fixup::kindStoreX86PCRel32_4:
1122                 case ld::Fixup::kindStoreX86PCRel32GOTLoad:
1123                 case ld::Fixup::kindStoreX86PCRel32GOTLoadNowLEA:
1124                 case ld::Fixup::kindStoreX86PCRel32GOT:
1125                 case ld::Fixup::kindStoreLittleEndian32:
1126                 case ld::Fixup::kindStoreTargetAddressLittleEndian32:
1127                 case ld::Fixup::kindStoreTargetAddressX86PCRel32:
1128                 case ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoad:
1129                 case ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoadNowLEA:
1130                 case ld::Fixup::kindStoreTargetAddressX86PCRel32TLVLoad:
1131                 case ld::Fixup::kindStoreTargetAddressX86PCRel32TLVLoadNowLEA:
1132                         _32bitPointerLocations.push_back(address);
1133                         break;
1134                 case ld::Fixup::kindStoreLittleEndian64:
1135                 case ld::Fixup::kindStoreTargetAddressLittleEndian64:
1136                         _64bitPointerLocations.push_back(address);
1137                         break;
1138                 default:
1139                         warning("codegen at address 0x%08llX prevents image from working in dyld shared cache", address);
1140                         break;
1141         }
1142 }
1143
1144 template <>
1145 void SplitSegInfoV1Atom<x86>::addSplitSegInfo(uint64_t address, ld::Fixup::Kind kind, uint32_t extra) const
1146 {
1147         switch (kind) {
1148                 case ld::Fixup::kindStoreLittleEndian32:
1149                 case ld::Fixup::kindStoreTargetAddressLittleEndian32:
1150                 case ld::Fixup::kindStoreX86PCRel32TLVLoad:
1151                 case ld::Fixup::kindStoreX86PCRel32TLVLoadNowLEA:
1152                         _32bitPointerLocations.push_back(address);
1153                         break;
1154                 default:
1155                         warning("codegen at address 0x%08llX prevents image from working in dyld shared cache", address);
1156                         break;
1157         }
1158 }
1159
1160 template <>
1161 void SplitSegInfoV1Atom<arm>::addSplitSegInfo(uint64_t address, ld::Fixup::Kind kind, uint32_t extra) const
1162 {
1163         switch (kind) {
1164                 case ld::Fixup::kindStoreLittleEndian32:
1165                         _32bitPointerLocations.push_back(address);
1166                         break;
1167         case ld::Fixup::kindStoreARMLow16:
1168                         _armLo16Locations.push_back(address);
1169                         break;
1170        case ld::Fixup::kindStoreThumbLow16:
1171                         _thumbLo16Locations.push_back(address);
1172                         break;
1173         case ld::Fixup::kindStoreARMHigh16:
1174             assert(extra < 16);
1175                         _armHi16Locations[extra].push_back(address);
1176                         break;
1177         case ld::Fixup::kindStoreThumbHigh16:
1178             assert(extra < 16);
1179                         _thumbHi16Locations[extra].push_back(address);
1180                         break;
1181                 default:
1182                         warning("codegen at address 0x%08llX prevents image from working in dyld shared cache", address);
1183                         break;
1184         }
1185 }
1186
1187 #if SUPPORT_ARCH_arm64
1188 template <>
1189 void SplitSegInfoV1Atom<arm64>::addSplitSegInfo(uint64_t address, ld::Fixup::Kind kind, uint32_t extra) const
1190 {
1191         switch (kind) {
1192                 case ld::Fixup::kindStoreARM64Page21:
1193                 case ld::Fixup::kindStoreARM64GOTLoadPage21:
1194                 case ld::Fixup::kindStoreARM64GOTLeaPage21:
1195                 case ld::Fixup::kindStoreARM64TLVPLoadPage21:
1196                 case ld::Fixup::kindStoreTargetAddressARM64Page21:
1197                 case ld::Fixup::kindStoreTargetAddressARM64GOTLoadPage21:
1198                 case ld::Fixup::kindStoreTargetAddressARM64GOTLeaPage21:
1199                         _adrpLocations.push_back(address);
1200                         break;
1201                 case ld::Fixup::kindStoreLittleEndian32:
1202                 case ld::Fixup::kindStoreARM64PCRelToGOT:
1203                         _32bitPointerLocations.push_back(address);
1204                         break;
1205                 case ld::Fixup::kindStoreLittleEndian64:
1206                 case ld::Fixup::kindStoreTargetAddressLittleEndian64:
1207                         _64bitPointerLocations.push_back(address);
1208                         break;
1209                 default:
1210                         warning("codegen at address 0x%08llX prevents image from working in dyld shared cache", address);
1211                         break;
1212         }
1213 }
1214 #endif
1215
1216 template <typename A>
1217 void SplitSegInfoV1Atom<A>::uleb128EncodeAddresses(const std::vector<uint64_t>& locations) const
1218 {
1219         pint_t addr = this->_options.baseAddress();
1220         for(typename std::vector<uint64_t>::const_iterator it = locations.begin(); it != locations.end(); ++it) {
1221                 pint_t nextAddr = *it;
1222                 //fprintf(stderr, "nextAddr=0x%0llX\n", (uint64_t)nextAddr);
1223                 uint64_t delta = nextAddr - addr;
1224                 //fprintf(stderr, "delta=0x%0llX\n", delta);
1225                 if ( delta == 0 )
1226                         throw "double split seg info for same address";
1227                 // uleb128 encode
1228                 uint8_t byte;
1229                 do {
1230                         byte = delta & 0x7F;
1231                         delta &= ~0x7F;
1232                         if ( delta != 0 )
1233                                 byte |= 0x80;
1234                         this->_encodedData.append_byte(byte);
1235                         delta = delta >> 7;
1236                 }
1237                 while( byte >= 0x80 );
1238                 addr = nextAddr;
1239         }
1240 }
1241
1242
1243 template <typename A>
1244 void SplitSegInfoV1Atom<A>::encode() const
1245 {
1246         // sort into group by pointer adjustment kind
1247         std::vector<OutputFile::SplitSegInfoEntry>& info = this->_writer._splitSegInfos;
1248         for (std::vector<OutputFile::SplitSegInfoEntry>::const_iterator it = info.begin(); it != info.end(); ++it) {
1249                 this->addSplitSegInfo(it->fixupAddress, it->kind, it->extra);
1250         }
1251
1252         // delta compress runs of addresses
1253         this->_encodedData.reserve(8192);
1254         if ( _32bitPointerLocations.size() != 0 ) {
1255                 this->_encodedData.append_byte(1);
1256                 //fprintf(stderr, "type 1:\n");
1257                 std::sort(_32bitPointerLocations.begin(), _32bitPointerLocations.end());
1258                 this->uleb128EncodeAddresses(_32bitPointerLocations);
1259                 this->_encodedData.append_byte(0); // terminator
1260         }
1261
1262         if ( _64bitPointerLocations.size() != 0 ) {
1263                 this->_encodedData.append_byte(2);
1264                 //fprintf(stderr, "type 2:\n");
1265                 std::sort(_64bitPointerLocations.begin(), _64bitPointerLocations.end());
1266                 this->uleb128EncodeAddresses(_64bitPointerLocations);
1267                 this->_encodedData.append_byte(0); // terminator
1268         }
1269
1270         if ( _adrpLocations.size() != 0 ) {
1271                 this->_encodedData.append_byte(3);
1272                 //fprintf(stderr, "type 3:\n");
1273                 std::sort(_adrpLocations.begin(), _adrpLocations.end());
1274                 this->uleb128EncodeAddresses(_adrpLocations);
1275                 this->_encodedData.append_byte(0); // terminator
1276         }
1277
1278         if ( _thumbLo16Locations.size() != 0 ) {
1279                 this->_encodedData.append_byte(5);
1280                 //fprintf(stderr, "type 5:\n");
1281                 std::sort(_thumbLo16Locations.begin(), _thumbLo16Locations.end());
1282                 this->uleb128EncodeAddresses(_thumbLo16Locations);
1283                 this->_encodedData.append_byte(0); // terminator
1284         }
1285
1286         if ( _armLo16Locations.size() != 0 ) {
1287                 this->_encodedData.append_byte(6);
1288                 //fprintf(stderr, "type 6:\n");
1289                 std::sort(_armLo16Locations.begin(), _armLo16Locations.end());
1290                 this->uleb128EncodeAddresses(_armLo16Locations);
1291                 this->_encodedData.append_byte(0); // terminator
1292         }
1293
1294         for (uint32_t i=0; i < 16; ++i) {
1295                 if ( _thumbHi16Locations[i].size() != 0 ) {
1296                         this->_encodedData.append_byte(16+i);
1297                         //fprintf(stderr, "type 16+%d:\n", i);
1298                         std::sort(_thumbHi16Locations[i].begin(), _thumbHi16Locations[i].end());
1299                         this->uleb128EncodeAddresses(_thumbHi16Locations[i]);
1300                         this->_encodedData.append_byte(0); // terminator
1301                 }
1302         }
1303
1304         for (uint32_t i=0; i < 16; ++i) {
1305                 if ( _armHi16Locations[i].size() != 0 ) {
1306                         this->_encodedData.append_byte(32+i);
1307                         //fprintf(stderr, "type 32+%d:\n", i);
1308                         std::sort(_armHi16Locations[i].begin(), _armHi16Locations[i].end());
1309                         this->uleb128EncodeAddresses(_armHi16Locations[i]);
1310                         this->_encodedData.append_byte(0); // terminator
1311                 }
1312         }
1313
1314         // always add zero byte to mark end
1315         this->_encodedData.append_byte(0);
1316
1317         // align to pointer size
1318         this->_encodedData.pad_to_size(sizeof(pint_t));
1319
1320         this->_encoded = true;
1321
1322         // clean up temporaries
1323         _32bitPointerLocations.clear();
1324         _64bitPointerLocations.clear();
1325 }
1326
1327
1328 template <typename A>
1329 class SplitSegInfoV2Atom : public LinkEditAtom
1330 {
1331 public:
1332                                                                                                 SplitSegInfoV2Atom(const Options& opts, ld::Internal& state, OutputFile& writer)
1333                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { }
1334
1335         // overrides of ld::Atom
1336         virtual const char*                                                     name() const            { return "split seg info"; }
1337         // overrides of LinkEditAtom
1338         virtual void                                                            encode() const;
1339
1340 private:
1341         typedef typename A::P                                           P;
1342         typedef typename A::P::E                                        E;
1343         typedef typename A::P::uint_t                           pint_t;
1344
1345         // Whole                 :== <count> FromToSection+
1346         // FromToSection :== <from-sect-index> <to-sect-index> <count> ToOffset+
1347         // ToOffset              :== <to-sect-offset-delta> <count> FromOffset+
1348         // FromOffset    :== <kind> <count> <from-sect-offset-delta>
1349
1350         typedef uint32_t SectionIndexes;
1351         typedef std::map<uint8_t, std::vector<uint64_t> > FromOffsetMap;
1352         typedef std::map<uint64_t, FromOffsetMap> ToOffsetMap;
1353         typedef std::map<SectionIndexes, ToOffsetMap> WholeMap;
1354
1355
1356         static ld::Section                      _s_section;
1357 };
1358
1359 template <typename A>
1360 ld::Section SplitSegInfoV2Atom<A>::_s_section("__LINKEDIT", "__splitSegInfo", ld::Section::typeLinkEdit, true);
1361
1362
1363 template <typename A>
1364 void SplitSegInfoV2Atom<A>::encode() const
1365 {
1366         // sort into group by adjustment kind
1367         //fprintf(stderr, "_splitSegV2Infos.size=%lu\n", this->_writer._splitSegV2Infos.size());
1368         WholeMap whole;
1369         for (const OutputFile::SplitSegInfoV2Entry&  entry : this->_writer._splitSegV2Infos) {
1370                 //fprintf(stderr, "from=%d, to=%d\n", entry.fixupSectionIndex, entry.targetSectionIndex);
1371                 SectionIndexes index = entry.fixupSectionIndex << 16 | entry.targetSectionIndex;
1372                 ToOffsetMap& toOffsets = whole[index];
1373                 FromOffsetMap& fromOffsets = toOffsets[entry.targetSectionOffset];
1374                 fromOffsets[entry.referenceKind].push_back(entry.fixupSectionOffset);
1375         }
1376
1377         // Add marker that this is V2 data
1378         this->_encodedData.reserve(8192);
1379         this->_encodedData.append_byte(DYLD_CACHE_ADJ_V2_FORMAT);
1380
1381         // stream out
1382         // Whole :== <count> FromToSection+
1383         this->_encodedData.append_uleb128(whole.size());
1384         for (auto& fromToSection : whole) {
1385                 uint8_t fromSectionIndex = fromToSection.first >> 16;
1386                 uint8_t toSectionIndex   = fromToSection.first & 0xFFFF;
1387                 ToOffsetMap& toOffsets   = fromToSection.second;
1388                 // FromToSection :== <from-sect-index> <to-sect-index> <count> ToOffset+
1389                 this->_encodedData.append_uleb128(fromSectionIndex);
1390                 this->_encodedData.append_uleb128(toSectionIndex);
1391                 this->_encodedData.append_uleb128(toOffsets.size());
1392                 //fprintf(stderr, "from sect=%d, to sect=%d, count=%lu\n", fromSectionIndex, toSectionIndex, toOffsets.size());
1393                 uint64_t lastToOffset = 0;
1394                 for (auto& fromToOffsets : toOffsets) {
1395                         uint64_t toSectionOffset = fromToOffsets.first;
1396                         FromOffsetMap& fromOffsets = fromToOffsets.second;
1397                         // ToOffset     :== <to-sect-offset-delta> <count> FromOffset+
1398                         this->_encodedData.append_uleb128(toSectionOffset - lastToOffset);
1399                         this->_encodedData.append_uleb128(fromOffsets.size());
1400                         for (auto& kindAndOffsets : fromOffsets) {
1401                                 uint8_t kind = kindAndOffsets.first;
1402                                 std::vector<uint64_t>& fromOffsets = kindAndOffsets.second;
1403                                 // FromOffset :== <kind> <count> <from-sect-offset-delta>
1404                                 this->_encodedData.append_uleb128(kind);
1405                                 this->_encodedData.append_uleb128(fromOffsets.size());
1406                                 std::sort(fromOffsets.begin(), fromOffsets.end());
1407                                 uint64_t lastFromOffset = 0;
1408                                 for (uint64_t offset : fromOffsets) {
1409                                         this->_encodedData.append_uleb128(offset - lastFromOffset);
1410                                         lastFromOffset = offset;
1411                                 }
1412                         }
1413                         lastToOffset = toSectionOffset;
1414                 }
1415         }
1416
1417
1418         // always add zero byte to mark end
1419         this->_encodedData.append_byte(0);
1420
1421         // align to pointer size
1422         this->_encodedData.pad_to_size(sizeof(pint_t));
1423
1424         this->_encoded = true;
1425 }
1426
1427
1428
1429 template <typename A>
1430 class FunctionStartsAtom : public LinkEditAtom
1431 {
1432 public:
1433                                                                                                 FunctionStartsAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
1434                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { }
1435
1436         // overrides of ld::Atom
1437         virtual const char*                                                     name() const            { return "function starts"; }
1438         // overrides of LinkEditAtom
1439         virtual void                                                            encode() const;
1440
1441 private:
1442         typedef typename A::P                                           P;
1443         typedef typename A::P::E                                        E;
1444         typedef typename A::P::uint_t                           pint_t;
1445
1446         static ld::Section                      _s_section;
1447 };
1448
1449 template <typename A>
1450 ld::Section FunctionStartsAtom<A>::_s_section("__LINKEDIT", "__funcStarts", ld::Section::typeLinkEdit, true);
1451
1452
1453 template <typename A>
1454 void FunctionStartsAtom<A>::encode() const
1455 {
1456         this->_encodedData.reserve(8192);
1457         const uint64_t badAddress = 0xFFFFFFFFFFFFFFFF;
1458         uint64_t addr = badAddress;
1459         // delta compress all function addresses
1460         for (std::vector<ld::Internal::FinalSection*>::iterator it = this->_state.sections.begin(); it != this->_state.sections.end(); ++it) {
1461                 ld::Internal::FinalSection* sect = *it;
1462                 if ( sect->type() == ld::Section::typeMachHeader ) {
1463                         // start with delta from start of __TEXT
1464                         addr = sect->address;
1465                 }
1466                 else if ( sect->type() == ld::Section::typeCode ) {
1467                         assert(addr != badAddress);
1468                         std::vector<const ld::Atom*>& atoms = sect->atoms;
1469                         for (std::vector<const ld::Atom*>::iterator ait = atoms.begin(); ait != atoms.end(); ++ait) {
1470                                 const ld::Atom* atom = *ait;
1471                                 // <rdar://problem/10422823> filter out zero-length atoms, so LC_FUNCTION_STARTS address can't spill into next section
1472                                 if ( atom->size() == 0 )
1473                                         continue;
1474                                 uint64_t nextAddr = atom->finalAddress();
1475                                 if ( atom->isThumb() )
1476                                         nextAddr |= 1;
1477                                 uint64_t delta = nextAddr - addr;
1478                                 if ( delta != 0 )
1479                                         this->_encodedData.append_uleb128(delta);
1480                                 addr = nextAddr;
1481                         }
1482                 }
1483         }
1484
1485         // terminator
1486         this->_encodedData.append_byte(0);
1487
1488         // align to pointer size
1489         this->_encodedData.pad_to_size(sizeof(pint_t));
1490
1491         this->_encoded = true;
1492 }
1493
1494
1495 // <rdar://problem/9218847> Need way to formalize data in code
1496 template <typename A>
1497 class DataInCodeAtom : public LinkEditAtom
1498 {
1499 public:
1500                                                                                                 DataInCodeAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
1501                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) { }
1502
1503         // overrides of ld::Atom
1504         virtual const char*                                                     name() const            { return "data-in-code info"; }
1505         // overrides of LinkEditAtom
1506         virtual void                                                            encode() const;
1507
1508 private:
1509         typedef typename A::P                                           P;
1510         typedef typename A::P::E                                        E;
1511         typedef typename A::P::uint_t                           pint_t;
1512
1513         struct FixupByAddressSorter
1514         {
1515                  bool operator()(const ld::Fixup* left, const ld::Fixup* right)
1516                  {
1517                           return (left->offsetInAtom < right->offsetInAtom);
1518                  }
1519         };
1520
1521         void encodeEntry(uint32_t startImageOffset, int len, ld::Fixup::Kind kind) const {
1522                 //fprintf(stderr, "encodeEntry(start=0x%08X, len=0x%04X, kind=%04X\n", startImageOffset, len, kind);
1523                 do {
1524                         macho_data_in_code_entry<P> entry;
1525                         entry.set_offset(startImageOffset);
1526                         entry.set_length(len);
1527                         switch ( kind ) {
1528                                 case ld::Fixup::kindDataInCodeStartData:
1529                                         entry.set_kind(DICE_KIND_DATA);
1530                                         break;
1531                                 case ld::Fixup::kindDataInCodeStartJT8:
1532                                         entry.set_kind(DICE_KIND_JUMP_TABLE8);
1533                                         break;
1534                                 case ld::Fixup::kindDataInCodeStartJT16:
1535                                         entry.set_kind(DICE_KIND_JUMP_TABLE16);
1536                                         break;
1537                                 case ld::Fixup::kindDataInCodeStartJT32:
1538                                         entry.set_kind(DICE_KIND_JUMP_TABLE32);
1539                                         break;
1540                                 case ld::Fixup::kindDataInCodeStartJTA32:
1541                                         entry.set_kind(DICE_KIND_ABS_JUMP_TABLE32);
1542                                         break;
1543                                 default:
1544                                         assert(0 && "bad L$start$ label to encode");
1545                         }
1546                         uint8_t* bp = (uint8_t*)&entry;
1547                         this->_encodedData.append_byte(bp[0]);
1548                         this->_encodedData.append_byte(bp[1]);
1549                         this->_encodedData.append_byte(bp[2]);
1550                         this->_encodedData.append_byte(bp[3]);
1551                         this->_encodedData.append_byte(bp[4]);
1552                         this->_encodedData.append_byte(bp[5]);
1553                         this->_encodedData.append_byte(bp[6]);
1554                         this->_encodedData.append_byte(bp[7]);
1555                         // in rare case data range is huge, create multiple entries
1556                         len -= 0xFFF8;
1557                         startImageOffset += 0xFFF8;
1558                 } while ( len > 0 );
1559         }
1560
1561         static ld::Section                      _s_section;
1562 };
1563
1564 template <typename A>
1565 ld::Section DataInCodeAtom<A>::_s_section("__LINKEDIT", "__dataInCode", ld::Section::typeLinkEdit, true);
1566
1567
1568 template <typename A>
1569 void DataInCodeAtom<A>::encode() const
1570 {
1571         if ( this->_writer.hasDataInCode ) {
1572                 uint64_t mhAddress = 0;
1573                 for (std::vector<ld::Internal::FinalSection*>::iterator sit = _state.sections.begin(); sit != _state.sections.end(); ++sit) {
1574                         ld::Internal::FinalSection* sect = *sit;
1575                         if ( sect->type() == ld::Section::typeMachHeader )
1576                                 mhAddress = sect->address;
1577                         if ( sect->type() != ld::Section::typeCode )
1578                                 continue;
1579                         for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
1580                                 const ld::Atom* atom = *ait;
1581                                 // gather all code-in-data labels
1582                                 std::vector<const ld::Fixup*> dataInCodeLabels;
1583                                 for (ld::Fixup::iterator fit = atom->fixupsBegin(); fit != atom->fixupsEnd(); ++fit) {
1584                                         switch ( fit->kind ) {
1585                                                 case ld::Fixup::kindDataInCodeStartData:
1586                                                 case ld::Fixup::kindDataInCodeStartJT8:
1587                                                 case ld::Fixup::kindDataInCodeStartJT16:
1588                                                 case ld::Fixup::kindDataInCodeStartJT32:
1589                                                 case ld::Fixup::kindDataInCodeStartJTA32:
1590                                                 case ld::Fixup::kindDataInCodeEnd:
1591                                                         dataInCodeLabels.push_back(fit);
1592                                                         break;
1593                                                 default:
1594                                                         break;
1595                                         }
1596                                 }
1597                                 // to do: sort labels by address
1598                                 std::sort(dataInCodeLabels.begin(), dataInCodeLabels.end(), FixupByAddressSorter());
1599
1600                                 // convert to array of struct data_in_code_entry
1601                                 ld::Fixup::Kind prevKind = ld::Fixup::kindDataInCodeEnd;
1602                                 uint32_t prevOffset = 0;
1603                                 for ( std::vector<const ld::Fixup*>::iterator sfit = dataInCodeLabels.begin(); sfit != dataInCodeLabels.end(); ++sfit) {
1604                                         if ( ((*sfit)->kind != prevKind) && (prevKind != ld::Fixup::kindDataInCodeEnd) ) {
1605                                                 int len = (*sfit)->offsetInAtom - prevOffset;
1606                                                 if ( len == 0 )
1607                                                         warning("multiple L$start$ labels found at same address in %s at offset 0x%04X", atom->name(), prevOffset);
1608                                                 this->encodeEntry(atom->finalAddress()+prevOffset-mhAddress, (*sfit)->offsetInAtom - prevOffset, prevKind);
1609                                         }
1610                                         prevKind = (*sfit)->kind;
1611                                         prevOffset = (*sfit)->offsetInAtom;
1612                                 }
1613                                 if ( prevKind != ld::Fixup::kindDataInCodeEnd ) {
1614                                         // add entry if function ends with data
1615                                         this->encodeEntry(atom->finalAddress()+prevOffset-mhAddress, atom->size() - prevOffset, prevKind);
1616                                 }
1617                         }
1618                 }
1619         }
1620
1621         this->_encoded = true;
1622 }
1623
1624
1625
1626
1627
1628
1629 template <typename A>
1630 class OptimizationHintsAtom : public LinkEditAtom
1631 {
1632 public:
1633                                                                                                 OptimizationHintsAtom(const Options& opts, ld::Internal& state, OutputFile& writer)
1634                                                                                                         : LinkEditAtom(opts, state, writer, _s_section, sizeof(pint_t)) {
1635                                                                                                                 assert(opts.outputKind() == Options::kObjectFile);
1636                                                                                                         }
1637
1638         // overrides of ld::Atom
1639         virtual const char*                                                     name() const            { return "linker optimization hints"; }
1640         // overrides of LinkEditAtom
1641         virtual void                                                            encode() const;
1642
1643 private:
1644         typedef typename A::P                                           P;
1645         typedef typename A::P::E                                        E;
1646         typedef typename A::P::uint_t                           pint_t;
1647
1648         static ld::Section                      _s_section;
1649
1650 };
1651
1652 template <typename A>
1653 ld::Section OptimizationHintsAtom<A>::_s_section("__LINKEDIT", "__opt_hints", ld::Section::typeLinkEdit, true);
1654
1655 template <typename A>
1656 void OptimizationHintsAtom<A>::encode() const
1657 {
1658         if ( _state.someObjectHasOptimizationHints ) {
1659                 for (std::vector<ld::Internal::FinalSection*>::iterator sit = _state.sections.begin(); sit != _state.sections.end(); ++sit) {
1660                         ld::Internal::FinalSection* sect = *sit;
1661                         if ( sect->type() != ld::Section::typeCode )
1662                                 continue;
1663                         for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
1664                                 const ld::Atom* atom = *ait;
1665                                 uint64_t address = atom->finalAddress();
1666                                 for (ld::Fixup::iterator fit = atom->fixupsBegin(); fit != atom->fixupsEnd(); ++fit) {
1667                                         if ( fit->kind != ld::Fixup::kindLinkerOptimizationHint)
1668                                                 continue;
1669                                         ld::Fixup::LOH_arm64 extra;
1670                                         extra.addend = fit->u.addend;
1671                                         _encodedData.append_uleb128(extra.info.kind);
1672                                         _encodedData.append_uleb128(extra.info.count+1);
1673                                         _encodedData.append_uleb128((extra.info.delta1 << 2) + fit->offsetInAtom + address);
1674                                         if ( extra.info.count > 0 )
1675                                                 _encodedData.append_uleb128((extra.info.delta2 << 2) + fit->offsetInAtom + address);
1676                                         if ( extra.info.count > 1 )
1677                                                 _encodedData.append_uleb128((extra.info.delta3 << 2) + fit->offsetInAtom + address);
1678                                         if ( extra.info.count > 2 )
1679                                                 _encodedData.append_uleb128((extra.info.delta4 << 2) + fit->offsetInAtom + address);
1680                                 }
1681                         }
1682                 }
1683
1684                 this->_encodedData.pad_to_size(sizeof(pint_t));
1685         }
1686
1687         this->_encoded = true;
1688 }
1689
1690
1691 } // namespace tool
1692 } // namespace ld
1693
1694 #endif // __LINKEDIT_HPP__