src/ld/passes/branch_island.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2009 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
  26 #include <stdint.h>
  27 #include <math.h>
  28 #include <unistd.h>
  29 #include <dlfcn.h>
  30 #include <libkern/OSByteOrder.h>
  31
  32 #include <vector>
  33 #include <map>
  34
  35 #include "MachOFileAbstraction.hpp"
  36 #include "ld.hpp"
  37 #include "branch_island.h"
  38
  39 namespace ld {
  40 namespace passes {
  41 namespace branch_island {
  42
  43
  44 static std::map<const Atom*, uint64_t> sAtomToAddress;
  45
  46
  47 struct TargetAndOffset { const ld::Atom* atom; uint32_t offset; };
  48 class TargetAndOffsetComparor
  49 {
  50 public:
  51         bool operator()(const TargetAndOffset& left, const TargetAndOffset& right) const
  52         {
  53                 if ( left.atom != right.atom )
  54                         return ( left.atom < right.atom );
  55                 return ( left.offset < right.offset );
  56         }
  57 };
  58
  59
  60 static bool _s_log = false;
  61 static ld::Section _s_text_section("__TEXT", "__text", ld::Section::typeCode);
  62
  63
  64 #if SUPPORT_ARCH_arm64
  65
  66 class ARM64BranchIslandAtom : public ld::Atom {
  67 public:
  68                                                                                         ARM64BranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
  69                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
  70                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
  71                                                         ld::Atom::symbolTableIn, false, false, false, ld::Atom::Alignment(2)),
  72                                 _name(nm),
  73                                 _fixup1(0, ld::Fixup::k1of1, ld::Fixup::kindStoreTargetAddressARM64Branch26, target),
  74                                 _fixup2(0, ld::Fixup::k1of1, ld::Fixup::kindIslandTarget, finalTarget.atom) {
  75                                         if (_s_log) fprintf(stderr, "%p: ARM64 branch island to final target %s\n",
  76                                                                                 this, finalTarget.atom->name());
  77                                 }
  78
  79         virtual const ld::File*                                 file() const                                    { return NULL; }
  80         virtual const char*                                             name() const                                    { return _name; }
  81         virtual uint64_t                                                size() const                                    { return 4; }
  82         virtual uint64_t                                                objectAddress() const                   { return 0; }
  83         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
  84                 OSWriteLittleInt32(buffer, 0, 0x14000000);
  85         }
  86         virtual void                                                    setScope(Scope)                                 { }
  87         virtual ld::Fixup::iterator                             fixupsBegin() const                             { return (ld::Fixup*)&_fixup1; }
  88         virtual ld::Fixup::iterator                             fixupsEnd()     const                           { return &((ld::Fixup*)&_fixup2)[1]; }
  89
  90 private:
  91         const char*                                                             _name;
  92         ld::Fixup                                                               _fixup1;
  93         ld::Fixup                                                               _fixup2;
  94 };
  95 #endif
  96
  97
  98 class ARMtoARMBranchIslandAtom : public ld::Atom {
  99 public:
 100                                                                                         ARMtoARMBranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
 101                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
 102                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 103                                                         ld::Atom::symbolTableIn, false, false, false, ld::Atom::Alignment(2)),
 104                                 _name(nm),
 105                                 _fixup1(0, ld::Fixup::k1of1, ld::Fixup::kindStoreTargetAddressARMBranch24, target),
 106                                 _fixup2(0, ld::Fixup::k1of1, ld::Fixup::kindIslandTarget, finalTarget.atom) {
 107                                         if (_s_log) fprintf(stderr, "%p: ARM-to-ARM branch island to final target %s\n",
 108                                                                                 this, finalTarget.atom->name());
 109                                 }
 110
 111         virtual const ld::File*                                 file() const                                    { return NULL; }
 112         virtual const char*                                             name() const                                    { return _name; }
 113         virtual uint64_t                                                size() const                                    { return 4; }
 114         virtual uint64_t                                                objectAddress() const                   { return 0; }
 115         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 116                 OSWriteLittleInt32(buffer, 0, 0xEA000000);
 117         }
 118         virtual void                                                    setScope(Scope)                                 { }
 119         virtual ld::Fixup::iterator                             fixupsBegin() const                             { return (ld::Fixup*)&_fixup1; }
 120         virtual ld::Fixup::iterator                             fixupsEnd()     const                           { return &((ld::Fixup*)&_fixup2)[1]; }
 121
 122 private:
 123         const char*                                                             _name;
 124         ld::Fixup                                                               _fixup1;
 125         ld::Fixup                                                               _fixup2;
 126 };
 127
 128
 129
 130 class ARMtoThumb1BranchIslandAtom : public ld::Atom {
 131 public:
 132                                                                                         ARMtoThumb1BranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
 133                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
 134                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 135                                                         ld::Atom::symbolTableIn, false, false, false, ld::Atom::Alignment(2)),
 136                                 _name(nm),
 137                                 _finalTarget(finalTarget) {
 138                                         if (_s_log) fprintf(stderr, "%p: ARM-to-thumb1 branch island to final target %s\n",
 139                                                                                 this, finalTarget.atom->name());
 140                                 }
 141
 142         virtual const ld::File*                                 file() const                                    { return NULL; }
 143         virtual const char*                                             name() const                                    { return _name; }
 144         virtual uint64_t                                                size() const                                    { return 16; }
 145         virtual uint64_t                                                objectAddress() const                   { return 0; }
 146         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 147                 // There is no large displacement thumb1 branch instruction.
 148                 // Instead use ARM instructions that can jump to thumb.
 149                 // we use a 32-bit displacement, so we can directly jump to target which means no island hopping
 150                 int64_t displacement = _finalTarget.atom->finalAddress() + _finalTarget.offset - (this->finalAddress() + 12);
 151                 if ( _finalTarget.atom->isThumb() )
 152                         displacement |= 1;
 153                 OSWriteLittleInt32(&buffer[ 0], 0, 0xe59fc004); //      ldr  ip, pc + 4
 154                 OSWriteLittleInt32(&buffer[ 4], 0, 0xe08fc00c); //      add      ip, pc, ip
 155                 OSWriteLittleInt32(&buffer[ 8], 0, 0xe12fff1c); //      bx       ip
 156                 OSWriteLittleInt32(&buffer[12], 0, displacement);       //      .long target-this
 157         }
 158         virtual void                                                    setScope(Scope)                                 { }
 159
 160 private:
 161         const char*                                                             _name;
 162         TargetAndOffset                                                 _finalTarget;
 163 };
 164
 165
 166
 167 class Thumb2toThumbBranchIslandAtom : public ld::Atom {
 168 public:
 169                                                                                         Thumb2toThumbBranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
 170                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
 171                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 172                                                         ld::Atom::symbolTableIn, false, true, false, ld::Atom::Alignment(1)),
 173                                 _name(nm),
 174                                 _fixup1(0, ld::Fixup::k1of1, ld::Fixup::kindStoreTargetAddressThumbBranch22, target),
 175                                 _fixup2(0, ld::Fixup::k1of1, ld::Fixup::kindIslandTarget, finalTarget.atom)             {
 176                                         if (_s_log) fprintf(stderr, "%p: Thumb-to-thumb branch island to final target %s\n",
 177                                                                                 this, finalTarget.atom->name());
 178                                         }
 179
 180         virtual const ld::File*                                 file() const                                    { return NULL; }
 181         virtual const char*                                             name() const                                    { return _name; }
 182         virtual uint64_t                                                size() const                                    { return 4; }
 183         virtual uint64_t                                                objectAddress() const                   { return 0; }
 184         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 185                 OSWriteLittleInt32(buffer, 0, 0xf0008000);
 186         }
 187         virtual void                                                    setScope(Scope)                                 { }
 188         virtual ld::Fixup::iterator                             fixupsBegin() const                             { return (ld::Fixup*)&_fixup1; }
 189         virtual ld::Fixup::iterator                             fixupsEnd()     const                           { return &((ld::Fixup*)&_fixup2)[1]; }
 190
 191 private:
 192         const char*                                                             _name;
 193         ld::Fixup                                                               _fixup1;
 194         ld::Fixup                                                               _fixup2;
 195 };
 196
 197
 198
 199 class Thumb2toThumbBranchAbsoluteIslandAtom : public ld::Atom {
 200 public:
 201                                                                                         Thumb2toThumbBranchAbsoluteIslandAtom(const char* nm, const ld::Section& inSect, TargetAndOffset finalTarget)
 202                                 : ld::Atom(inSect, ld::Atom::definitionRegular, ld::Atom::combineNever,
 203                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 204                                                         ld::Atom::symbolTableIn, false, true, false, ld::Atom::Alignment(1)),
 205                                 _name(nm),
 206                                 _fixup1(0, ld::Fixup::k1of2, ld::Fixup::kindSetTargetAddress, finalTarget.atom),
 207                                 _fixup2(0, ld::Fixup::k2of2, ld::Fixup::kindStoreThumbLow16),
 208                                 _fixup3(4, ld::Fixup::k1of2, ld::Fixup::kindSetTargetAddress, finalTarget.atom),
 209                                 _fixup4(4, ld::Fixup::k2of2, ld::Fixup::kindStoreThumbHigh16),
 210                                 _fixup5(0, ld::Fixup::k1of1, ld::Fixup::kindIslandTarget, finalTarget.atom) {
 211                                         if (_s_log) fprintf(stderr, "%p: Thumb-to-thumb absolute branch island to final target %s\n",
 212                                                                                 this, finalTarget.atom->name());
 213                                         }
 214
 215         virtual const ld::File*                                 file() const                                    { return NULL; }
 216         virtual const char*                                             name() const                                    { return _name; }
 217         virtual uint64_t                                                size() const                                    { return 10; }
 218         virtual uint64_t                                                objectAddress() const                   { return 0; }
 219         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 220                 OSWriteLittleInt32(&buffer[0], 0, 0x0c00f240);  //      movw    r12, #0x5678
 221                 OSWriteLittleInt32(&buffer[4], 0, 0x0c00f2c0);  //      movt    r12, #0x1234
 222                 OSWriteLittleInt16(&buffer[8], 0, 0x4760);              //      bx              r12
 223         }
 224         virtual void                                                    setScope(Scope)                                 { }
 225         virtual ld::Fixup::iterator                             fixupsBegin() const                             { return (ld::Fixup*)&_fixup1; }
 226         virtual ld::Fixup::iterator                             fixupsEnd()     const                           { return &((ld::Fixup*)&_fixup5)[1]; }
 227
 228 private:
 229         const char*                                                             _name;
 230         ld::Fixup                                                               _fixup1;
 231         ld::Fixup                                                               _fixup2;
 232         ld::Fixup                                                               _fixup3;
 233         ld::Fixup                                                               _fixup4;
 234         ld::Fixup                                                               _fixup5;
 235 };
 236
 237
 238
 239 class NoPicARMtoThumbMBranchIslandAtom : public ld::Atom {
 240 public:
 241                                                                                         NoPicARMtoThumbMBranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
 242                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
 243                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 244                                                         ld::Atom::symbolTableIn, false, false, false, ld::Atom::Alignment(2)),
 245                                 _name(nm),
 246                                 _finalTarget(finalTarget) {
 247                                         if (_s_log) fprintf(stderr, "%p: NoPIC ARM-to-Thumb branch island to final target %s\n",
 248                                                                                 this, finalTarget.atom->name());
 249                                         }
 250
 251         virtual const ld::File*                                 file() const                                    { return NULL; }
 252         virtual const char*                                             name() const                                    { return _name; }
 253         virtual uint64_t                                                size() const                                    { return 8; }
 254         virtual uint64_t                                                objectAddress() const                   { return 0; }
 255         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 256                 // There is no large displacement thumb1 branch instruction.
 257                 // Instead use ARM instructions that can jump to thumb.
 258                 // we use a 32-bit displacement, so we can directly jump to final target which means no island hopping
 259                 uint32_t targetAddr = _finalTarget.atom->finalAddress();
 260                 if ( _finalTarget.atom->isThumb() )
 261                         targetAddr |= 1;
 262                 OSWriteLittleInt32(&buffer[0], 0, 0xe51ff004);  //      ldr     pc, [pc, #-4]
 263                 OSWriteLittleInt32(&buffer[4], 0, targetAddr);  //      .long target-this
 264         }
 265         virtual void                                                    setScope(Scope)                                 { }
 266
 267 private:
 268         const char*                                                             _name;
 269         TargetAndOffset                                                 _finalTarget;
 270 };
 271
 272
 273 static ld::Atom* makeBranchIsland(const Options& opts, ld::Fixup::Kind kind, int islandRegion, const ld::Atom* nextTarget,
 274                                                                         TargetAndOffset finalTarget, const ld::Section& inSect, bool crossSectionBranch)
 275 {
 276         char* name;
 277         if ( finalTarget.offset == 0 ) {
 278                 if ( islandRegion == 0 )
 279                         asprintf(&name, "%s.island", finalTarget.atom->name());
 280                 else
 281                         asprintf(&name, "%s.island.%d", finalTarget.atom->name(), islandRegion+1);
 282         }
 283         else {
 284                 asprintf(&name, "%s_plus_%d.island.%d", finalTarget.atom->name(), finalTarget.offset, islandRegion);
 285         }
 286
 287         switch ( kind ) {
 288                 case ld::Fixup::kindStoreARMBranch24:
 289                 case ld::Fixup::kindStoreThumbBranch22:
 290                 case ld::Fixup::kindStoreTargetAddressARMBranch24:
 291                 case ld::Fixup::kindStoreTargetAddressThumbBranch22:
 292                         if ( crossSectionBranch && opts.preferSubArchitecture() && opts.archSupportsThumb2() ) {
 293                                 return new Thumb2toThumbBranchAbsoluteIslandAtom(name, inSect, finalTarget);
 294                         }
 295                         else if ( finalTarget.atom->isThumb() ) {
 296                                 if ( opts.preferSubArchitecture() && opts.archSupportsThumb2() ) {
 297                                         return new Thumb2toThumbBranchIslandAtom(name, nextTarget, finalTarget);
 298                                 }
 299                                 else if ( opts.outputSlidable() ) {
 300                                         return new ARMtoThumb1BranchIslandAtom(name, nextTarget, finalTarget);
 301                                 }
 302                                 else {
 303                                         return new NoPicARMtoThumbMBranchIslandAtom(name, nextTarget, finalTarget);
 304                                 }
 305                         }
 306                         else {
 307                                 return new ARMtoARMBranchIslandAtom(name, nextTarget, finalTarget);
 308                         }
 309                         break;
 310 #if SUPPORT_ARCH_arm64
 311             case ld::Fixup::kindStoreARM64Branch26:
 312                 case ld::Fixup::kindStoreTargetAddressARM64Branch26:
 313                         return new ARM64BranchIslandAtom(name, nextTarget, finalTarget);
 314                         break;
 315 #endif
 316                 default:
 317                         assert(0 && "unexpected branch kind");
 318                         break;
 319         }
 320         return NULL;
 321 }
 322
 323
 324 static uint64_t textSizeWhenMightNeedBranchIslands(const Options& opts, bool seenThumbBranch)
 325 {
 326         switch ( opts.architecture() ) {
 327                 case CPU_TYPE_ARM:
 328                         if ( ! seenThumbBranch )
 329                                 return 32000000;  // ARM can branch +/- 32MB
 330                         else if ( opts.preferSubArchitecture() && opts.archSupportsThumb2() )
 331                                 return 16000000;  // thumb2 can branch +/- 16MB
 332                         else
 333                                 return  4000000;  // thumb1 can branch +/- 4MB
 334                         break;
 335 #if SUPPORT_ARCH_arm64
 336                 case CPU_TYPE_ARM64:
 337                         return 128000000; // arm64 can branch +/- 128MB
 338                         break;
 339 #endif
 340         }
 341         assert(0 && "unexpected architecture");
 342         return 0x100000000LL;
 343 }
 344
 345
 346 static uint64_t maxDistanceBetweenIslands(const Options& opts, bool seenThumbBranch)
 347 {
 348         switch ( opts.architecture() ) {
 349                 case CPU_TYPE_ARM:
 350                         if ( ! seenThumbBranch )
 351                                 return 30*1024*1024;    // 2MB of branch islands per 32MB
 352                         else if ( opts.preferSubArchitecture() && opts.archSupportsThumb2() )
 353                                 return 14*1024*1024;    // 2MB of branch islands per 16MB
 354                         else
 355                                 return 3500000;                 // 0.5MB of branch islands per 4MB
 356                         break;
 357 #if SUPPORT_ARCH_arm64
 358                 case CPU_TYPE_ARM64:
 359                         return 124*1024*1024;            // 4MB of branch islands per 128MB
 360                         break;
 361 #endif
 362         }
 363         assert(0 && "unexpected architecture");
 364         return 0x100000000LL;
 365 }
 366
 367
 368 //
 369 // PowerPC can do PC relative branches as far as +/-16MB.
 370 // If a branch target is >16MB then we insert one or more
 371 // "branch islands" between the branch and its target that
 372 // allows island hopping to the target.
 373 //
 374 // Branch Island Algorithm
 375 //
 376 // If the __TEXT segment < 16MB, then no branch islands needed
 377 // Otherwise, every 14MB into the __TEXT segment a region is
 378 // added which can contain branch islands.  Every out-of-range
 379 // bl instruction is checked.  If it crosses a region, an island
 380 // is added to that region with the same target and the bl is
 381 // adjusted to target the island instead.
 382 //
 383 // In theory, if too many islands are added to one region, it
 384 // could grow the __TEXT enough that other previously in-range
 385 // bl branches could be pushed out of range.  We reduce the
 386 // probability this could happen by placing the ranges every
 387 // 14MB which means the region would have to be 2MB (512,000 islands)
 388 // before any branches could be pushed out of range.
 389 //
 390
 391
 392 static void makeIslandsForSection(const Options& opts, ld::Internal& state, ld::Internal::FinalSection* textSection, unsigned stubCount)
 393 {
 394         // assign section offsets to each atom in __text section, watch for thumb branches, and find total size
 395         bool hasThumbBranches = false;
 396         bool haveCrossSectionBranches = false;
 397         const bool preload = (opts.outputKind() == Options::kPreload);
 398         uint64_t offset = 0;
 399         for (std::vector<const ld::Atom*>::iterator ait=textSection->atoms.begin();  ait != textSection->atoms.end(); ++ait) {
 400                 const ld::Atom* atom = *ait;
 401                 // check for thumb branches and cross section branches
 402                 const ld::Atom* target = NULL;
 403                 for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
 404                         if ( fit->firstInCluster() ) {
 405                                 target = NULL;
 406                         }
 407                         switch ( fit->binding ) {
 408                                 case ld::Fixup::bindingNone:
 409                                 case ld::Fixup::bindingByNameUnbound:
 410                                         break;
 411                                 case ld::Fixup::bindingByContentBound:
 412                                 case ld::Fixup::bindingDirectlyBound:
 413                                         target = fit->u.target;
 414                                         break;
 415                                 case ld::Fixup::bindingsIndirectlyBound:
 416                                         target = state.indirectBindingTable[fit->u.bindingIndex];
 417                                         break;
 418                         }
 419                         bool haveBranch = false;
 420                         switch (fit->kind) {
 421                                 case ld::Fixup::kindStoreThumbBranch22:
 422                                 case ld::Fixup::kindStoreTargetAddressThumbBranch22:
 423                                         hasThumbBranches = true;
 424                                         // fall into arm branch case
 425                                 case ld::Fixup::kindStoreARMBranch24:
 426                                 case ld::Fixup::kindStoreTargetAddressARMBranch24:
 427                                         haveBranch = true;
 428                                         break;
 429                 default:
 430                     break;
 431                         }
 432                         if ( haveBranch && (target->contentType() != ld::Atom::typeStub) ) {
 433                                 // <rdar://problem/14792124> haveCrossSectionBranches only applies to -preload builds
 434                                 if ( preload && (atom->section() != target->section()) )
 435                                         haveCrossSectionBranches = true;
 436                         }
 437                 }
 438                 // align atom
 439                 ld::Atom::Alignment atomAlign = atom->alignment();
 440                 uint64_t atomAlignP2 = (1 << atomAlign.powerOf2);
 441                 uint64_t currentModulus = (offset % atomAlignP2);
 442                 if ( currentModulus != atomAlign.modulus ) {
 443                         if ( atomAlign.modulus > currentModulus )
 444                                 offset += atomAlign.modulus-currentModulus;
 445                         else
 446                                 offset += atomAlign.modulus+atomAlignP2-currentModulus;
 447                 }
 448                 (const_cast<ld::Atom*>(atom))->setSectionOffset(offset);
 449                 offset += atom->size();
 450         }
 451         uint64_t totalTextSize = offset + stubCount*16;
 452         if ( (totalTextSize < textSizeWhenMightNeedBranchIslands(opts, hasThumbBranches)) && !haveCrossSectionBranches )
 453                 return;
 454         if (_s_log) fprintf(stderr, "ld: section %s size=%llu, might need branch islands\n", textSection->sectionName(), totalTextSize);
 455
 456         // Figure out how many regions of branch islands will be needed, and their locations.
 457         // Construct a vector containing the atoms after which branch islands will be inserted,
 458         // taking into account follow on fixups. No atom run without an island can exceed kBetweenRegions.
 459         const uint64_t kBetweenRegions = maxDistanceBetweenIslands(opts, hasThumbBranches); // place regions of islands every 14MB in __text section
 460         std::vector<const ld::Atom*> branchIslandInsertionPoints; // atoms in the atom list after which branch islands will be inserted
 461         uint64_t previousIslandEndAddr = 0;
 462         const ld::Atom *insertionPoint = NULL;
 463         branchIslandInsertionPoints.reserve(totalTextSize/kBetweenRegions*2);
 464         for (std::vector<const ld::Atom*>::iterator it=textSection->atoms.begin(); it != textSection->atoms.end(); it++) {
 465                 const ld::Atom* atom = *it;
 466                 // if we move past the next atom, will the run length exceed kBetweenRegions?
 467                 if ( atom->sectionOffset() + atom->size() > previousIslandEndAddr + kBetweenRegions ) {
 468                         // yes. Add the last known good location (atom) for inserting a branch island.
 469                         if ( insertionPoint == NULL )
 470                                 throwf("Unable to insert branch island. No insertion point available.");
 471                         branchIslandInsertionPoints.push_back(insertionPoint);
 472                         previousIslandEndAddr = insertionPoint->sectionOffset()+insertionPoint->size();
 473                         insertionPoint = NULL;
 474                 }
 475                 // Can we insert an island after this atom? If so then keep track of it.
 476                 if ( !atom->hasFixupsOfKind(ld::Fixup::kindNoneFollowOn) )
 477                         insertionPoint = atom;
 478         }
 479         // add one more island after the last atom if close to limit
 480         if ( (insertionPoint != NULL) && (insertionPoint->sectionOffset() + insertionPoint->size() > previousIslandEndAddr + (kBetweenRegions-0x100000)) )
 481                 branchIslandInsertionPoints.push_back(insertionPoint);
 482         if ( haveCrossSectionBranches && branchIslandInsertionPoints.empty() ) {
 483                 branchIslandInsertionPoints.push_back(textSection->atoms.back());
 484         }
 485         const int kIslandRegionsCount = branchIslandInsertionPoints.size();
 486
 487         if (_s_log) fprintf(stderr, "ld: will use %u branch island regions\n", kIslandRegionsCount);
 488         typedef std::map<TargetAndOffset,const ld::Atom*, TargetAndOffsetComparor> AtomToIsland;
 489     AtomToIsland* regionsMap[kIslandRegionsCount];
 490         uint64_t regionAddresses[kIslandRegionsCount];
 491         std::vector<const ld::Atom*>* regionsIslands[kIslandRegionsCount];
 492         for(int i=0; i < kIslandRegionsCount; ++i) {
 493                 regionsMap[i] = new AtomToIsland();
 494                 regionsIslands[i] = new std::vector<const ld::Atom*>();
 495                 regionAddresses[i] = branchIslandInsertionPoints[i]->sectionOffset() + branchIslandInsertionPoints[i]->size();
 496                 if (_s_log) fprintf(stderr, "ld: branch islands will be inserted at 0x%08llX after %s\n", regionAddresses[i], branchIslandInsertionPoints[i]->name());
 497         }
 498         unsigned int islandCount = 0;
 499
 500         // create islands for branches in __text that are out of range
 501         for (std::vector<const ld::Atom*>::iterator ait=textSection->atoms.begin(); ait != textSection->atoms.end(); ++ait) {
 502                 const ld::Atom* atom = *ait;
 503                 const ld::Atom* target = NULL;
 504                 uint64_t addend = 0;
 505                 ld::Fixup* fixupWithTarget = NULL;
 506                 for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
 507                         if ( fit->firstInCluster() ) {
 508                                 target = NULL;
 509                                 fixupWithTarget = NULL;
 510                                 addend = 0;
 511                         }
 512                         switch ( fit->binding ) {
 513                                 case ld::Fixup::bindingNone:
 514                                 case ld::Fixup::bindingByNameUnbound:
 515                                         break;
 516                                 case ld::Fixup::bindingByContentBound:
 517                                 case ld::Fixup::bindingDirectlyBound:
 518                                         target = fit->u.target;
 519                                         fixupWithTarget = fit;
 520                                         break;
 521                                 case ld::Fixup::bindingsIndirectlyBound:
 522                                         target = state.indirectBindingTable[fit->u.bindingIndex];
 523                                         fixupWithTarget = fit;
 524                                         break;
 525                         }
 526                         bool haveBranch = false;
 527                         switch (fit->kind) {
 528                                 case ld::Fixup::kindAddAddend:
 529                                         addend = fit->u.addend;
 530                                         break;
 531                                 case ld::Fixup::kindStoreARMBranch24:
 532                                 case ld::Fixup::kindStoreThumbBranch22:
 533                                 case ld::Fixup::kindStoreTargetAddressARMBranch24:
 534                                 case ld::Fixup::kindStoreTargetAddressThumbBranch22:
 535 #if SUPPORT_ARCH_arm64
 536                                 case ld::Fixup::kindStoreARM64Branch26:
 537                                 case ld::Fixup::kindStoreTargetAddressARM64Branch26:
 538 #endif
 539                                         haveBranch = true;
 540                                         break;
 541                 default:
 542                     break;
 543                         }
 544                         if ( haveBranch ) {
 545                                 bool crossSectionBranch = ( preload && (atom->section() != target->section()) );
 546                                 int64_t srcAddr = atom->sectionOffset() + fit->offsetInAtom;
 547                                 int64_t dstAddr = target->sectionOffset() + addend;
 548                                 if ( preload ) {
 549                                         srcAddr = sAtomToAddress[atom] + fit->offsetInAtom;
 550                                         dstAddr = sAtomToAddress[target] + addend;
 551                                 }
 552                                 if ( target->section().type() == ld::Section::typeStub )
 553                                         dstAddr = totalTextSize;
 554                                 int64_t displacement = dstAddr - srcAddr;
 555                                 TargetAndOffset finalTargetAndOffset = { target, (uint32_t)addend };
 556                                 const int64_t kBranchLimit = kBetweenRegions;
 557                                 if ( crossSectionBranch && ((displacement > kBranchLimit) || (displacement < (-kBranchLimit))) ) {
 558                                         const ld::Atom* island;
 559                                         AtomToIsland* region = regionsMap[0];
 560                                         AtomToIsland::iterator pos = region->find(finalTargetAndOffset);
 561                                         if ( pos == region->end() ) {
 562                                                 island = makeBranchIsland(opts, fit->kind, 0, target, finalTargetAndOffset, atom->section(), true);
 563                                                 (*region)[finalTargetAndOffset] = island;
 564                                                 if (_s_log) fprintf(stderr, "added absolute branching island %p %s, displacement=%lld\n",
 565                                                                                                 island, island->name(), displacement);
 566                                                 ++islandCount;
 567                                                 regionsIslands[0]->push_back(island);
 568                                                 state.atomToSection[island] = textSection;
 569                                         }
 570                                         else {
 571                                                 island = pos->second;
 572                                         }
 573                                         if (_s_log) fprintf(stderr, "using island %p %s for branch to %s from %s\n", island, island->name(), target->name(), atom->name());
 574                                         fixupWithTarget->u.target = island;
 575                                         fixupWithTarget->binding = ld::Fixup::bindingDirectlyBound;
 576                                 }
 577                                 else if ( displacement > kBranchLimit ) {
 578                                         // create forward branch chain
 579                                         const ld::Atom* nextTarget = target;
 580                                         if (_s_log) fprintf(stderr, "need forward branching island srcAdr=0x%08llX, dstAdr=0x%08llX, target=%s\n",
 581                                                                                                                 srcAddr, dstAddr, target->name());
 582                                         for (int i=kIslandRegionsCount-1; i >=0 ; --i) {
 583                                                 AtomToIsland* region = regionsMap[i];
 584                                                 int64_t islandRegionAddr = regionAddresses[i];
 585                                                 if ( (srcAddr < islandRegionAddr) && ((islandRegionAddr <= dstAddr)) ) {
 586                                                         AtomToIsland::iterator pos = region->find(finalTargetAndOffset);
 587                                                         if ( pos == region->end() ) {
 588                                                                 ld::Atom* island = makeBranchIsland(opts, fit->kind, i, nextTarget, finalTargetAndOffset, atom->section(), false);
 589                                                                 (*region)[finalTargetAndOffset] = island;
 590                                                                 if (_s_log) fprintf(stderr, "added forward branching island %p %s to region %d for %s\n", island, island->name(), i, atom->name());
 591                                                                 regionsIslands[i]->push_back(island);
 592                                                                 state.atomToSection[island] = textSection;
 593                                                                 ++islandCount;
 594                                                                 nextTarget = island;
 595                                                         }
 596                                                         else {
 597                                                                 nextTarget = pos->second;
 598                                                         }
 599                                                 }
 600                                         }
 601                                         if (_s_log) fprintf(stderr, "using island %p %s for branch to %s from %s\n", nextTarget, nextTarget->name(), target->name(), atom->name());
 602                                         fixupWithTarget->u.target = nextTarget;
 603                                         fixupWithTarget->binding = ld::Fixup::bindingDirectlyBound;
 604                                 }
 605                                 else if ( displacement < (-kBranchLimit) ) {
 606                                         // create back branching chain
 607                                         const ld::Atom* prevTarget = target;
 608                                         for (int i=0; i < kIslandRegionsCount ; ++i) {
 609                                                 AtomToIsland* region = regionsMap[i];
 610                                                 int64_t islandRegionAddr = regionAddresses[i];
 611                                                 if ( (dstAddr < islandRegionAddr) && (islandRegionAddr <= srcAddr) ) {
 612                                                         if (_s_log) fprintf(stderr, "need backward branching island srcAdr=0x%08llX, dstAdr=0x%08llX, target=%s\n", srcAddr, dstAddr, target->name());
 613                                                         AtomToIsland::iterator pos = region->find(finalTargetAndOffset);
 614                                                         if ( pos == region->end() ) {
 615                                                                 ld::Atom* island = makeBranchIsland(opts, fit->kind, i, prevTarget, finalTargetAndOffset, atom->section(), false);
 616                                                                 (*region)[finalTargetAndOffset] = island;
 617                                                                 if (_s_log) fprintf(stderr, "added back branching island %p %s to region %d for %s\n", island, island->name(), i, atom->name());
 618                                                                 regionsIslands[i]->push_back(island);
 619                                                                 state.atomToSection[island] = textSection;
 620                                                                 ++islandCount;
 621                                                                 prevTarget = island;
 622                                                         }
 623                                                         else {
 624                                                                 prevTarget = pos->second;
 625                                                         }
 626                                                 }
 627                                         }
 628                                         if (_s_log) fprintf(stderr, "using back island %p %s for %s\n", prevTarget, prevTarget->name(), atom->name());
 629                                         fixupWithTarget->u.target = prevTarget;
 630                                         fixupWithTarget->binding = ld::Fixup::bindingDirectlyBound;
 631                                 }
 632                         }
 633                 }
 634         }
 635
 636
 637         // insert islands into __text section and adjust section offsets
 638         if ( islandCount > 0 ) {
 639                 if ( _s_log ) fprintf(stderr, "ld: %u branch islands required in %u regions\n", islandCount, kIslandRegionsCount);
 640                 std::vector<const ld::Atom*> newAtomList;
 641                 newAtomList.reserve(textSection->atoms.size()+islandCount);
 642
 643                 int regionIndex = 0;
 644                 for (std::vector<const ld::Atom*>::iterator ait=textSection->atoms.begin(); ait != textSection->atoms.end(); ait++) {
 645                         const ld::Atom* atom = *ait;
 646                         newAtomList.push_back(atom);
 647                         if ( (regionIndex < kIslandRegionsCount) && (atom == branchIslandInsertionPoints[regionIndex]) ) {
 648                                 std::vector<const ld::Atom*>* islands = regionsIslands[regionIndex];
 649                                 newAtomList.insert(newAtomList.end(), islands->begin(), islands->end());
 650                                 ++regionIndex;
 651                         }
 652                 }
 653                 // swap in new list of atoms for __text section
 654                 textSection->atoms.clear();
 655                 textSection->atoms = newAtomList;
 656         }
 657
 658 }
 659
 660
 661 static void buildAddressMap(const Options& opts, ld::Internal& state) {
 662         // Assign addresses to sections
 663         state.setSectionSizesAndAlignments();
 664         state.assignFileOffsets();
 665
 666         // Assign addresses to atoms in a side table
 667         const bool log = false;
 668         if ( log ) fprintf(stderr, "buildAddressMap()\n");
 669         for (std::vector<ld::Internal::FinalSection*>::iterator sit = state.sections.begin(); sit != state.sections.end(); ++sit) {
 670                 ld::Internal::FinalSection* sect = *sit;
 671                 uint16_t maxAlignment = 0;
 672                 uint64_t offset = 0;
 673                 if ( log ) fprintf(stderr, "  section=%s/%s, address=0x%08llX\n", sect->segmentName(), sect->sectionName(), sect->address);
 674                 for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 675                         const ld::Atom* atom = *ait;
 676                         uint32_t atomAlignmentPowerOf2 = atom->alignment().powerOf2;
 677                         uint32_t atomModulus = atom->alignment().modulus;
 678                         if ( atomAlignmentPowerOf2 > maxAlignment )
 679                                 maxAlignment = atomAlignmentPowerOf2;
 680                         // calculate section offset for this atom
 681                         uint64_t alignment = 1 << atomAlignmentPowerOf2;
 682                         uint64_t currentModulus = (offset % alignment);
 683                         uint64_t requiredModulus = atomModulus;
 684                         if ( currentModulus != requiredModulus ) {
 685                                 if ( requiredModulus > currentModulus )
 686                                         offset += requiredModulus-currentModulus;
 687                                 else
 688                                         offset += requiredModulus+alignment-currentModulus;
 689                         }
 690
 691                         if ( log ) fprintf(stderr, "    0x%08llX atom=%p, name=%s\n", sect->address+offset, atom, atom->name());
 692                         sAtomToAddress[atom] = sect->address + offset;
 693
 694                         offset += atom->size();
 695                 }
 696         }
 697
 698
 699 }
 700
 701 void doPass(const Options& opts, ld::Internal& state)
 702 {
 703         // only make branch islands in final linked images
 704         if ( opts.outputKind() == Options::kObjectFile )
 705                 return;
 706
 707         // Allow user to disable branch island generation
 708         if ( !opts.allowBranchIslands() )
 709                 return;
 710
 711         // only ARM[64] needs branch islands
 712         switch ( opts.architecture() ) {
 713                 case CPU_TYPE_ARM:
 714 #if SUPPORT_ARCH_arm64
 715                 case CPU_TYPE_ARM64:
 716 #endif
 717                         break;
 718                 default:
 719                         return;
 720         }
 721
 722         if ( opts.outputKind() == Options::kPreload ) {
 723                 buildAddressMap(opts, state);
 724         }
 725
 726         // scan sections for number of stubs
 727         unsigned stubCount = 0;
 728         for (std::vector<ld::Internal::FinalSection*>::iterator sit=state.sections.begin(); sit != state.sections.end(); ++sit) {
 729                 ld::Internal::FinalSection* sect = *sit;
 730                 if ( sect->type() == ld::Section::typeStub )
 731                         stubCount = sect->atoms.size();
 732         }
 733
 734         // scan sections and add island to each code section
 735         for (std::vector<ld::Internal::FinalSection*>::iterator sit=state.sections.begin(); sit != state.sections.end(); ++sit) {
 736                 ld::Internal::FinalSection* sect = *sit;
 737                 if ( sect->type() == ld::Section::typeCode )
 738                         makeIslandsForSection(opts, state, sect, stubCount);
 739         }
 740 }
 741
 742
 743 } // namespace branch_island
 744 } // namespace passes
 745 } // namespace ld