src/ld/passes/order.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2009-2011 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 <mach/machine.h>
  31
  32 #include <vector>
  33 #include <map>
  34 #include <set>
  35 #include <unordered_map>
  36
  37 #include "ld.hpp"
  38 #include "order.h"
  39
  40 namespace ld {
  41 namespace passes {
  42 namespace order {
  43
  44 //
  45 // The purpose of this pass is to take the graph of all Atoms and produce an ordered
  46 // sequence of atoms.  The constraints are that: 1) all Atoms of the same Segment must
  47 // be contiguous, 2)  all Atoms of the same Section must be contigous, 3) Atoms specified
  48 // in an order are sequenced as in the order file and before Atoms not specified,
  49 // 4) Atoms in the same section from the same .o file should be contiguous and sequenced
  50 // in the same order they were in the .o file, 5) Atoms in the same Section but which came
  51 // from different .o files should be sequenced in the same order that the .o files
  52 // were passed to the linker (i.e. command line order).
  53 //
  54 // The way this is implemented is that the linker passes a "base ordinal" to each File
  55 // as it is constructed. Add each atom has an objectAddress() method. Then
  56 // sorting is just sorting by section, then by file ordinal, then by object address.
  57 //
  58 // If an -order_file is specified, it gets more complicated.  First, an override-ordinal map
  59 // is created.  It causes the sort routine to ignore the value returned by ordinal() and objectAddress()
  60 // and use the override value instead.  Next some Atoms must be laid out consecutively
  61 // (e.g. hand written assembly that does not end with return, but rather falls into
  62 // the next label).  This is modeled in via a kindNoneFollowOn fixup.  The use of
  63 // kindNoneFollowOn fixups produces "clusters" of atoms that must stay together.
  64 // If an order_file tries to move one atom, it may need to move a whole cluster.  The
  65 // algorithm to do this models clusters using two maps.  The "starts" maps maps any
  66 // atom in a cluster to the first Atom in the cluster.  The "nexts" maps an Atom in a
  67 // cluster to the next Atom in the cluster.  With this in place, while processing an
  68 // order_file, if any entry is in a cluster (in "starts" map), then the entire cluster is
  69 // given ordinal overrides.
  70 //
  71
  72 class Layout
  73 {
  74 public:
  75                                 Layout(const Options& opts, ld::Internal& state);
  76         void            doPass();
  77 private:
  78
  79         class Comparer {
  80         public:
  81                                         Comparer(const Layout& l, ld::Internal& s) : _layout(l), _state(s) {}
  82                 bool            operator()(const ld::Atom* left, const ld::Atom* right);
  83         private:
  84                 const Layout&   _layout;
  85                 ld::Internal&   _state;
  86         };
  87
  88         typedef std::unordered_map<const char*, const ld::Atom*, CStringHash, CStringEquals> NameToAtom;
  89
  90         typedef std::map<const ld::Atom*, const ld::Atom*> AtomToAtom;
  91
  92         typedef std::map<const ld::Atom*, uint32_t> AtomToOrdinal;
  93
  94         const ld::Atom*         findAtom(const Options::OrderedSymbol& orderedSymbol);
  95         void                            buildNameTable();
  96         void                            buildFollowOnTables();
  97         void                            buildOrdinalOverrideMap();
  98         const ld::Atom*         follower(const ld::Atom* atom);
  99         static bool                     matchesObjectFile(const ld::Atom* atom, const char* objectFileLeafName);
 100                         bool            possibleToOrder(const ld::Internal::FinalSection*);
 101
 102         const Options&                                          _options;
 103         ld::Internal&                                           _state;
 104         AtomToAtom                                                      _followOnStarts;
 105         AtomToAtom                                                      _followOnNexts;
 106         NameToAtom                                                      _nameTable;
 107         std::vector<const ld::Atom*>            _nameCollisionAtoms;
 108         AtomToOrdinal                                           _ordinalOverrideMap;
 109         Comparer                                                        _comparer;
 110         bool                                                            _haveOrderFile;
 111
 112         static bool                                                     _s_log;
 113 };
 114
 115 bool Layout::_s_log = false;
 116
 117 Layout::Layout(const Options& opts, ld::Internal& state)
 118         : _options(opts), _state(state), _comparer(*this, state), _haveOrderFile(opts.orderedSymbolsCount() != 0)
 119 {
 120 }
 121
 122
 123 bool Layout::Comparer::operator()(const ld::Atom* left, const ld::Atom* right)
 124 {
 125         if ( left == right )
 126                 return false;
 127
 128         // magic section$start symbol always sorts to the start of its section
 129         if ( left->contentType() == ld::Atom::typeSectionStart )
 130                 return true;
 131         if ( right->contentType() == ld::Atom::typeSectionStart )
 132                 return false;
 133
 134         // if an -order_file is specified, then sorting is altered to sort those symbols first
 135         if ( _layout._haveOrderFile ) {
 136                 AtomToOrdinal::const_iterator leftPos  = _layout._ordinalOverrideMap.find(left);
 137                 AtomToOrdinal::const_iterator rightPos = _layout._ordinalOverrideMap.find(right);
 138                 AtomToOrdinal::const_iterator end = _layout._ordinalOverrideMap.end();
 139                 if ( leftPos != end ) {
 140                         if ( rightPos != end ) {
 141                                 // both left and right are overridden, so compare overridden ordinals
 142                                 return leftPos->second < rightPos->second;
 143                         }
 144                         else {
 145                                 // left is overridden and right is not, so left < right
 146                                 return true;
 147                         }
 148                 }
 149                 else {
 150                         if ( rightPos != end ) {
 151                                 // right is overridden and left is not, so right < left
 152                                 return false;
 153                         }
 154                         else {
 155                                 // neither are overridden,
 156                                 // fall into default sorting below
 157                         }
 158                 }
 159         }
 160
 161         // magic section$end symbol always sorts to the end of its section
 162         if ( left->contentType() == ld::Atom::typeSectionEnd )
 163                 return false;
 164         if ( right->contentType() == ld::Atom::typeSectionEnd )
 165                 return true;
 166
 167         // aliases sort before their target
 168         bool leftIsAlias = left->isAlias();
 169         if ( leftIsAlias ) {
 170                 for (ld::Fixup::iterator fit=left->fixupsBegin(); fit != left->fixupsEnd(); ++fit) {
 171                         const ld::Atom* target = NULL;
 172                         if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
 173                                 switch ( fit->binding ) {
 174                                         case ld::Fixup::bindingsIndirectlyBound:
 175                                                 target = _state.indirectBindingTable[fit->u.bindingIndex];
 176                                                 break;
 177                                         case ld::Fixup::bindingDirectlyBound:
 178                                                 target = fit->u.target;
 179                                                 break;
 180                     default:
 181                         break;
 182                                 }
 183                             if ( target == right )
 184                                         return true; // left already before right
 185                                 left = target; // sort as if alias was its target
 186                                 break;
 187                     }
 188                 }
 189         }
 190         bool rightIsAlias = right->isAlias();
 191     if ( rightIsAlias ) {
 192         for (ld::Fixup::iterator fit=right->fixupsBegin(); fit != right->fixupsEnd(); ++fit) {
 193                         const ld::Atom* target = NULL;
 194                         if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
 195                                 switch ( fit->binding ) {
 196                                         case ld::Fixup::bindingsIndirectlyBound:
 197                                                 target = _state.indirectBindingTable[fit->u.bindingIndex];
 198                                                 break;
 199                                         case ld::Fixup::bindingDirectlyBound:
 200                                                 target = fit->u.target;
 201                                                 break;
 202                     default:
 203                         break;
 204                                 }
 205                             if ( target == left )
 206                     return false; // need to swap, alias is after target
 207                                 right = target; // continue with sort as if right was target
 208                 break;
 209                         }
 210                 }
 211     }
 212
 213         // the __common section can have real or tentative definitions
 214         // we want the real ones to sort before tentative ones
 215         bool leftIsTent  =  (left->definition() == ld::Atom::definitionTentative);
 216         bool rightIsTent =  (right->definition() == ld::Atom::definitionTentative);
 217         if ( leftIsTent != rightIsTent )
 218                 return rightIsTent;
 219
 220 #if 0
 221         // initializers are auto sorted to start of section
 222         if ( !fInitializerSet.empty() ) {
 223                 bool leftFirst  = (fInitializerSet.count(left) != 0);
 224                 bool rightFirst = (fInitializerSet.count(right) != 0);
 225                 if ( leftFirst != rightFirst )
 226                         return leftFirst;
 227         }
 228
 229         // terminators are auto sorted to end of section
 230         if ( !fTerminatorSet.empty() ) {
 231                 bool leftLast  = (fTerminatorSet.count(left) != 0);
 232                 bool rightLast = (fTerminatorSet.count(right) != 0);
 233                 if ( leftLast != rightLast )
 234                         return rightLast;
 235         }
 236 #endif
 237
 238         // sort by .o order
 239         const ld::File* leftFile = left->file();
 240         const ld::File* rightFile = right->file();
 241         // <rdar://problem/10830126> properly sort if on file is NULL and the other is not
 242         ld::File::Ordinal leftFileOrdinal = (leftFile != NULL) ? leftFile->ordinal() : ld::File::Ordinal::NullOrdinal();
 243         ld::File::Ordinal rightFileOrdinal = (rightFile != NULL) ? rightFile->ordinal() : ld::File::Ordinal::NullOrdinal();
 244         if ( leftFileOrdinal != rightFileOrdinal )
 245                 return leftFileOrdinal< rightFileOrdinal;
 246
 247         // tentative defintions have no address in .o file, they are traditionally laid out by name
 248         if ( leftIsTent && rightIsTent )
 249                 return (strcmp(left->name(), right->name()) < 0);
 250
 251         // lastly sort by atom address
 252         int64_t addrDiff = left->objectAddress() - right->objectAddress();
 253         if ( addrDiff == 0 ) {
 254                 // have same address so one might be an alias, and aliases need to sort before target
 255                 if ( leftIsAlias != rightIsAlias )
 256                         return leftIsAlias;
 257
 258                 // both at same address, sort by name
 259                 return (strcmp(left->name(), right->name()) < 0);
 260         }
 261         return (addrDiff < 0);
 262 }
 263
 264 bool Layout::matchesObjectFile(const ld::Atom* atom, const char* objectFileLeafName)
 265 {
 266         if ( objectFileLeafName == NULL )
 267                 return true;
 268         const char* atomFullPath = atom->file()->path();
 269         const char* lastSlash = strrchr(atomFullPath, '/');
 270         if ( lastSlash != NULL ) {
 271                 if ( strcmp(&lastSlash[1], objectFileLeafName) == 0 )
 272                         return true;
 273         }
 274         else {
 275                 if ( strcmp(atomFullPath, objectFileLeafName) == 0 )
 276                         return true;
 277         }
 278         return false;
 279 }
 280
 281
 282 bool Layout::possibleToOrder(const ld::Internal::FinalSection* sect)
 283 {
 284         // atoms in only some sections can have order_file applied
 285         switch ( sect->type() ) {
 286                 case ld::Section::typeUnclassified:
 287                 case ld::Section::typeCode:
 288                 case ld::Section::typeZeroFill:
 289                         return true;
 290                 case ld::Section::typeImportProxies:
 291                         return false;
 292                 default:
 293                         // if section has command line aliases, then we must apply ordering so aliases layout before targets
 294                         if ( _options.haveCmdLineAliases() ) {
 295                                 for (std::vector<const ld::Atom*>::const_iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 296                                         const ld::Atom* atom = *ait;
 297                                         if ( atom->isAlias() )
 298                                                 return true;
 299                                 }
 300                         }
 301                         break;
 302         }
 303         return false;
 304 }
 305
 306 void Layout::buildNameTable()
 307 {
 308         for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
 309                 ld::Internal::FinalSection* sect = *sit;
 310                 // some sections are not worth scanning for names
 311                 if ( ! possibleToOrder(sect) )
 312                         continue;
 313                 for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 314                         const ld::Atom* atom = *ait;
 315                         if ( atom->symbolTableInclusion() == ld::Atom::symbolTableIn ) {
 316                                 const char* name = atom->name();
 317                                 if ( name != NULL) {
 318                                         // static function or data
 319                                         NameToAtom::iterator pos = _nameTable.find(name);
 320                                         if ( pos == _nameTable.end() )
 321                                                 _nameTable[name] = atom;
 322                                         else {
 323                                                 const ld::Atom* existing = _nameTable[name];
 324                                                 if ( existing != NULL ) {
 325                                                         _nameCollisionAtoms.push_back(existing);
 326                                                         _nameTable[name] = NULL;        // collision, denote with NULL
 327                                                 }
 328                                                 _nameCollisionAtoms.push_back(atom);
 329                                         }
 330                                 }
 331                         }
 332                 }
 333         }
 334         if ( _s_log ) {
 335                 fprintf(stderr, "buildNameTable() _nameTable:\n");
 336                 for(NameToAtom::iterator it=_nameTable.begin(); it != _nameTable.end(); ++it)
 337                         fprintf(stderr, "  %p <- %s\n", it->second, it->first);
 338                 fprintf(stderr, "buildNameTable() _nameCollisionAtoms:\n");
 339                 for(std::vector<const ld::Atom*>::iterator it=_nameCollisionAtoms.begin(); it != _nameCollisionAtoms.end(); ++it)
 340                         fprintf(stderr, "  %p, %s\n", *it, (*it)->name());
 341         }
 342 }
 343
 344
 345 const ld::Atom* Layout::findAtom(const Options::OrderedSymbol& orderedSymbol)
 346 {
 347         // look for name in _nameTable
 348         NameToAtom::iterator pos = _nameTable.find(orderedSymbol.symbolName);
 349         if ( pos != _nameTable.end() ) {
 350                 if ( (pos->second != NULL) && matchesObjectFile(pos->second, orderedSymbol.objectFileName) ) {
 351                         //fprintf(stderr, "found %s in hash table\n", orderedSymbol.symbolName);
 352                         return pos->second;
 353                 }
 354                 if ( pos->second == NULL ) {
 355                         // name is in hash table, but atom is NULL, so that means there are duplicates, so we use super slow way
 356                         if ( ( orderedSymbol.objectFileName == NULL) && _options.printOrderFileStatistics() ) {
 357                                 warning("%s specified in order_file but it exists in multiple .o files. "
 358                                                 "Prefix symbol with .o filename in order_file to disambiguate", orderedSymbol.symbolName);
 359                         }
 360                         for (std::vector<const ld::Atom*>::iterator it=_nameCollisionAtoms.begin(); it != _nameCollisionAtoms.end(); it++) {
 361                                 const ld::Atom* atom = *it;
 362                                 if ( strcmp(atom->name(), orderedSymbol.symbolName) == 0 ) {
 363                                         if ( matchesObjectFile(atom, orderedSymbol.objectFileName) ) {
 364                                                 return atom;
 365                                         }
 366                                 }
 367                         }
 368                 }
 369         }
 370
 371         return NULL;
 372 }
 373
 374 const ld::Atom* Layout::follower(const ld::Atom* atom)
 375 {
 376         for (const ld::Atom* a = _followOnStarts[atom]; a != NULL; a = _followOnNexts[a]) {
 377                 assert(a != NULL);
 378                 if ( _followOnNexts[a] == atom ) {
 379                         return a;
 380                 }
 381         }
 382         // no follower, first in chain
 383         return NULL;
 384 }
 385
 386 void Layout::buildFollowOnTables()
 387 {
 388         // if no -order_file, then skip building follow on table
 389         if ( ! _haveOrderFile )
 390                 return;
 391
 392         // first make a pass to find all follow-on references and build start/next maps
 393         // which are a way to represent clusters of atoms that must layout together
 394         for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
 395                 ld::Internal::FinalSection* sect = *sit;
 396                 if ( !possibleToOrder(sect) )
 397                         continue;
 398                 for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 399                         const ld::Atom* atom = *ait;
 400                         for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
 401                                 if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
 402                                         assert(fit->binding == ld::Fixup::bindingDirectlyBound);
 403                                         const ld::Atom* followOnAtom = fit->u.target;
 404                                         if ( _s_log ) fprintf(stderr, "ref %p %s -> %p %s\n", atom, atom->name(), followOnAtom, followOnAtom->name());
 405                                         assert(_followOnNexts.count(atom) == 0);
 406                                         _followOnNexts[atom] = followOnAtom;
 407                                         if ( _followOnStarts.count(atom) == 0 ) {
 408                                                 // first time atom has been seen, make it start of chain
 409                                                 _followOnStarts[atom] = atom;
 410                                                 if ( _s_log ) fprintf(stderr, "  start %s -> %s\n", atom->name(), atom->name());
 411                                         }
 412                                         if ( _followOnStarts.count(followOnAtom) == 0 ) {
 413                                                 // first time followOnAtom has been seen, make atom start of chain
 414                                                 _followOnStarts[followOnAtom] = _followOnStarts[atom];
 415                                                 if ( _s_log ) fprintf(stderr, "  start %s -> %s\n", followOnAtom->name(), _followOnStarts[atom]->name());
 416                                         }
 417                                         else {
 418                                                 if ( _followOnStarts[followOnAtom] == followOnAtom ) {
 419                                                         // followOnAtom atom already start of another chain, hook together
 420                                                         // and change all to use atom as start
 421                                                         const ld::Atom* a = followOnAtom;
 422                                                         while ( true ) {
 423                                                                 assert(_followOnStarts[a] == followOnAtom);
 424                                                                 _followOnStarts[a] = _followOnStarts[atom];
 425                                                                 if ( _s_log ) fprintf(stderr, "  adjust start for %s -> %s\n", a->name(), _followOnStarts[atom]->name());
 426                                                                 AtomToAtom::iterator pos = _followOnNexts.find(a);
 427                                                                 if ( pos != _followOnNexts.end() )
 428                                                                         a = pos->second;
 429                                                                 else
 430                                                                         break;
 431                                                         }
 432                                                 }
 433                                                 else {
 434                                                         // attempt to insert atom into existing followOn chain
 435                                                         const ld::Atom* curPrevToFollowOnAtom = this->follower(followOnAtom);
 436                                                         assert(curPrevToFollowOnAtom != NULL);
 437                                                         assert((atom->size() == 0) || (curPrevToFollowOnAtom->size() == 0));
 438                                                         if ( atom->size() == 0 ) {
 439                                                                 // insert alias into existing chain right before followOnAtom
 440                                                                 _followOnNexts[curPrevToFollowOnAtom] = atom;
 441                                                                 _followOnNexts[atom] = followOnAtom;
 442                                                                 _followOnStarts[atom] = _followOnStarts[followOnAtom];
 443                                                         }
 444                                                         else {
 445                                                                 // insert real atom into existing chain right before alias of followOnAtom
 446                                                                 const ld::Atom* curPrevPrevToFollowOn = this->follower(curPrevToFollowOnAtom);
 447                                                                 if ( curPrevPrevToFollowOn == NULL ) {
 448                                                                         // nothing previous, so make this a start of a new chain
 449                                                                         _followOnNexts[atom] = curPrevToFollowOnAtom;
 450                                                                         for (const ld::Atom* a = atom; a != NULL; a = _followOnNexts[a]) {
 451                                                                                 if ( _s_log ) fprintf(stderr, "  adjust start for %s -> %s\n", a->name(), atom->name());
 452                                                                                 _followOnStarts[a] = atom;
 453                                                                         }
 454                                                                 }
 455                                                                 else {
 456                                                                         // is previous, insert into existing chain before previous
 457                                                                         _followOnNexts[curPrevPrevToFollowOn] = atom;
 458                                                                         _followOnNexts[atom] = curPrevToFollowOnAtom;
 459                                                                         _followOnStarts[atom] = _followOnStarts[curPrevToFollowOnAtom];
 460                                                                 }
 461                                                         }
 462                                                 }
 463                                         }
 464                                 }
 465                         }
 466                 }
 467         }
 468
 469         if ( _s_log ) {
 470                 for(AtomToAtom::iterator it = _followOnStarts.begin(); it != _followOnStarts.end(); ++it)
 471                         fprintf(stderr, "start %s -> %s\n", it->first->name(), it->second->name());
 472
 473                 for(AtomToAtom::iterator it = _followOnNexts.begin(); it != _followOnNexts.end(); ++it)
 474                         fprintf(stderr, "next %s -> %s\n", it->first->name(), (it->second != NULL) ? it->second->name() : "null");
 475         }
 476 }
 477
 478
 479 class InSet
 480 {
 481 public:
 482         InSet(const std::set<const ld::Atom*>& theSet) : _set(theSet)  {}
 483
 484         bool operator()(const ld::Atom* atom) const {
 485                 return ( _set.count(atom) != 0 );
 486         }
 487 private:
 488         const std::set<const ld::Atom*>&  _set;
 489 };
 490
 491
 492 void Layout::buildOrdinalOverrideMap()
 493 {
 494         // if no -order_file, then skip building override map
 495         if ( ! _haveOrderFile )
 496                 return;
 497
 498         // build fast name->atom table
 499         this->buildNameTable();
 500
 501         // handle .o files that cannot have their atoms rearranged
 502         // with the start/next maps of follow-on atoms we can process the order file and produce override ordinals
 503         uint32_t index = 0;
 504         uint32_t matchCount = 0;
 505         std::set<const ld::Atom*> moveToData;
 506         for(Options::OrderedSymbolsIterator it = _options.orderedSymbolsBegin(); it != _options.orderedSymbolsEnd(); ++it) {
 507                 const ld::Atom* atom = this->findAtom(*it);
 508                 if ( atom != NULL ) {
 509                         // <rdar://problem/8612550> When order file used on data, turn ordered zero fill symbols into zero data
 510                         switch ( atom->section().type() ) {
 511                                 case ld::Section::typeZeroFill:
 512                                 case ld::Section::typeTentativeDefs:
 513                                         if ( atom->size() <= 512 ) {
 514                                                 const char* dstSeg;
 515                                                 bool wildCardMatch;
 516                                                 const ld::File* f = atom->file();
 517                                                 const char* path = (f != NULL) ? f->path() : NULL;
 518                                                 if ( !_options.moveRwSymbol(atom->name(), path, dstSeg, wildCardMatch) )
 519                                                         moveToData.insert(atom);
 520                                         }
 521                                         break;
 522                                 default:
 523                                         break;
 524                         }
 525
 526                         AtomToAtom::iterator start = _followOnStarts.find(atom);
 527                         if ( start != _followOnStarts.end() ) {
 528                                 // this symbol for the order file corresponds to an atom that is in a cluster that must lay out together
 529                                 for(const ld::Atom* nextAtom = start->second; nextAtom != NULL; nextAtom = _followOnNexts[nextAtom]) {
 530                                         AtomToOrdinal::iterator pos = _ordinalOverrideMap.find(nextAtom);
 531                                         if ( pos == _ordinalOverrideMap.end() ) {
 532                                                 _ordinalOverrideMap[nextAtom] = index++;
 533                                                 if (_s_log ) fprintf(stderr, "override ordinal %u assigned to %s in cluster from %s\n", index, nextAtom->name(), nextAtom->file()->path());
 534                                         }
 535                                         else {
 536                                                 if (_s_log ) fprintf(stderr, "could not order %s as %u because it was already laid out earlier by %s as %u\n",
 537                                                                                 atom->name(), index, _followOnStarts[atom]->name(), _ordinalOverrideMap[atom] );
 538                                         }
 539                                 }
 540                         }
 541                         else {
 542                                 _ordinalOverrideMap[atom] = index;
 543                                 if (_s_log ) fprintf(stderr, "override ordinal %u assigned to %s from %s\n", index, atom->name(), atom->file()->path());
 544                         }
 545                         ++matchCount;
 546                 }
 547                 else {
 548                         if ( _options.printOrderFileStatistics() ) {
 549                                 if ( it->objectFileName == NULL )
 550                                         warning("can't find match for order_file entry: %s", it->symbolName);
 551                                 else
 552                                         warning("can't find match for order_file entry: %s/%s", it->objectFileName, it->symbolName);
 553                         }
 554                 }
 555                  ++index;
 556         }
 557         if ( _options.printOrderFileStatistics() && (_options.orderedSymbolsCount() != matchCount) ) {
 558                 warning("only %u out of %lu order_file symbols were applicable", matchCount, _options.orderedSymbolsCount() );
 559         }
 560
 561         // <rdar://problem/8612550> When order file used on data, turn ordered zero fill symbols into zeroed data
 562         if ( ! moveToData.empty() ) {
 563                 // <rdar://problem/14919139> only move zero fill symbols to __data if there is a __data section
 564                 ld::Internal::FinalSection* dataSect = NULL;
 565                 for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
 566                         ld::Internal::FinalSection* sect = *sit;
 567                         if ( sect->type() == ld::Section::typeUnclassified ) {
 568                                 if ( (strcmp(sect->sectionName(), "__data") == 0) && (strcmp(sect->segmentName(), "__DATA") == 0) )
 569                                         dataSect = sect;
 570                         }
 571                 }
 572
 573                 if ( dataSect != NULL ) {
 574                         // add atoms to __data
 575                         dataSect->atoms.insert(dataSect->atoms.end(), moveToData.begin(), moveToData.end());
 576                         // remove atoms from original sections
 577                         for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
 578                                 ld::Internal::FinalSection* sect = *sit;
 579                                 switch ( sect->type() ) {
 580                                         case ld::Section::typeZeroFill:
 581                                         case ld::Section::typeTentativeDefs:
 582                                                 sect->atoms.erase(std::remove_if(sect->atoms.begin(), sect->atoms.end(), InSet(moveToData)), sect->atoms.end());
 583                                                 break;
 584                                         default:
 585                                                 break;
 586                                 }
 587                         }
 588                         // update atom-to-section map
 589                         for (std::set<const ld::Atom*>::iterator it=moveToData.begin(); it != moveToData.end(); ++it) {
 590                                 _state.atomToSection[*it] = dataSect;
 591                         }
 592                 }
 593         }
 594
 595 }
 596
 597 void Layout::doPass()
 598 {
 599         const bool log = false;
 600         if ( log ) {
 601                 fprintf(stderr, "Unordered atoms:\n");
 602                 for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
 603                         ld::Internal::FinalSection* sect = *sit;
 604                         for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 605                                 const ld::Atom* atom = *ait;
 606                                 fprintf(stderr, "\t%p\t%s\t%s\n", atom, sect->sectionName(), atom->name());
 607                         }
 608                 }
 609         }
 610
 611         // handle .o files that cannot have their atoms rearranged
 612         this->buildFollowOnTables();
 613
 614         // assign new ordinal value to all ordered atoms
 615         this->buildOrdinalOverrideMap();
 616
 617         // sort atoms in each section
 618         for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
 619                 ld::Internal::FinalSection* sect = *sit;
 620                 if ( sect->type() ==  ld::Section::typeTempAlias )
 621                         continue;
 622                 if ( log ) fprintf(stderr, "sorting section %s\n", sect->sectionName());
 623                 std::sort(sect->atoms.begin(), sect->atoms.end(), _comparer);
 624         }
 625
 626         if ( log ) {
 627                 fprintf(stderr, "Sorted atoms:\n");
 628                 for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
 629                         ld::Internal::FinalSection* sect = *sit;
 630                         for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 631                                 const ld::Atom* atom = *ait;
 632                                 fprintf(stderr, "\t%p\t%s\t%s\n", atom, sect->sectionName(), atom->name());
 633                         }
 634                 }
 635         }
 636 }
 637
 638
 639 void doPass(const Options& opts, ld::Internal& state)
 640 {
 641         Layout layout(opts, state);
 642         layout.doPass();
 643 }
 644
 645
 646 } // namespace order_file
 647 } // namespace passes
 648 } // namespace ld