#include <stdint.h>
#include <math.h>
#include <unistd.h>
#include <dlfcn.h>
#include <mach/machine.h>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include "ld.hpp"
#include "order.h"
namespace ld {
namespace passes {
namespace order {
class Layout
{
public:
Layout(const Options& opts, ld::Internal& state);
void doPass();
private:
class Comparer {
public:
Comparer(const Layout& l, ld::Internal& s) : _layout(l), _state(s) {}
bool operator()(const ld::Atom* left, const ld::Atom* right);
private:
const Layout& _layout;
ld::Internal& _state;
};
typedef std::unordered_map<const char*, const ld::Atom*, CStringHash, CStringEquals> NameToAtom;
typedef std::map<const ld::Atom*, const ld::Atom*> AtomToAtom;
typedef std::map<const ld::Atom*, uint32_t> AtomToOrdinal;
const ld::Atom* findAtom(const Options::OrderedSymbol& orderedSymbol);
void buildNameTable();
void buildFollowOnTables();
void buildOrdinalOverrideMap();
const ld::Atom* follower(const ld::Atom* atom);
static bool matchesObjectFile(const ld::Atom* atom, const char* objectFileLeafName);
bool possibleToOrder(const ld::Internal::FinalSection*);
const Options& _options;
ld::Internal& _state;
AtomToAtom _followOnStarts;
AtomToAtom _followOnNexts;
NameToAtom _nameTable;
std::vector<const ld::Atom*> _nameCollisionAtoms;
AtomToOrdinal _ordinalOverrideMap;
Comparer _comparer;
bool _haveOrderFile;
static bool _s_log;
};
bool Layout::_s_log = false;
Layout::Layout(const Options& opts, ld::Internal& state)
: _options(opts), _state(state), _comparer(*this, state), _haveOrderFile(opts.orderedSymbolsCount() != 0)
{
}
bool Layout::Comparer::operator()(const ld::Atom* left, const ld::Atom* right)
{
if ( left == right )
return false;
if ( left->contentType() == ld::Atom::typeSectionStart )
return true;
if ( right->contentType() == ld::Atom::typeSectionStart )
return false;
if ( _layout._haveOrderFile ) {
AtomToOrdinal::const_iterator leftPos = _layout._ordinalOverrideMap.find(left);
AtomToOrdinal::const_iterator rightPos = _layout._ordinalOverrideMap.find(right);
AtomToOrdinal::const_iterator end = _layout._ordinalOverrideMap.end();
if ( leftPos != end ) {
if ( rightPos != end ) {
return leftPos->second < rightPos->second;
}
else {
return true;
}
}
else {
if ( rightPos != end ) {
return false;
}
else {
}
}
}
if ( left->contentType() == ld::Atom::typeSectionEnd )
return false;
if ( right->contentType() == ld::Atom::typeSectionEnd )
return true;
bool leftIsAlias = left->isAlias();
if ( leftIsAlias ) {
for (ld::Fixup::iterator fit=left->fixupsBegin(); fit != left->fixupsEnd(); ++fit) {
const ld::Atom* target = NULL;
if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
switch ( fit->binding ) {
case ld::Fixup::bindingsIndirectlyBound:
target = _state.indirectBindingTable[fit->u.bindingIndex];
break;
case ld::Fixup::bindingDirectlyBound:
target = fit->u.target;
break;
default:
break;
}
if ( target == right )
return true; left = target; break;
}
}
}
bool rightIsAlias = right->isAlias();
if ( rightIsAlias ) {
for (ld::Fixup::iterator fit=right->fixupsBegin(); fit != right->fixupsEnd(); ++fit) {
const ld::Atom* target = NULL;
if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
switch ( fit->binding ) {
case ld::Fixup::bindingsIndirectlyBound:
target = _state.indirectBindingTable[fit->u.bindingIndex];
break;
case ld::Fixup::bindingDirectlyBound:
target = fit->u.target;
break;
default:
break;
}
if ( target == left )
return false; right = target; break;
}
}
}
bool leftIsTent = (left->definition() == ld::Atom::definitionTentative);
bool rightIsTent = (right->definition() == ld::Atom::definitionTentative);
if ( leftIsTent != rightIsTent )
return rightIsTent;
#if 0
if ( !fInitializerSet.empty() ) {
bool leftFirst = (fInitializerSet.count(left) != 0);
bool rightFirst = (fInitializerSet.count(right) != 0);
if ( leftFirst != rightFirst )
return leftFirst;
}
if ( !fTerminatorSet.empty() ) {
bool leftLast = (fTerminatorSet.count(left) != 0);
bool rightLast = (fTerminatorSet.count(right) != 0);
if ( leftLast != rightLast )
return rightLast;
}
#endif
const ld::File* leftFile = left->file();
const ld::File* rightFile = right->file();
ld::File::Ordinal leftFileOrdinal = (leftFile != NULL) ? leftFile->ordinal() : ld::File::Ordinal::NullOrdinal();
ld::File::Ordinal rightFileOrdinal = (rightFile != NULL) ? rightFile->ordinal() : ld::File::Ordinal::NullOrdinal();
if ( leftFileOrdinal != rightFileOrdinal )
return leftFileOrdinal< rightFileOrdinal;
if ( leftIsTent && rightIsTent )
return (strcmp(left->name(), right->name()) < 0);
int64_t addrDiff = left->objectAddress() - right->objectAddress();
if ( addrDiff == 0 ) {
if ( leftIsAlias != rightIsAlias )
return leftIsAlias;
return (strcmp(left->name(), right->name()) < 0);
}
return (addrDiff < 0);
}
bool Layout::matchesObjectFile(const ld::Atom* atom, const char* objectFileLeafName)
{
if ( objectFileLeafName == NULL )
return true;
const char* atomFullPath = atom->file()->path();
const char* lastSlash = strrchr(atomFullPath, '/');
if ( lastSlash != NULL ) {
if ( strcmp(&lastSlash[1], objectFileLeafName) == 0 )
return true;
}
else {
if ( strcmp(atomFullPath, objectFileLeafName) == 0 )
return true;
}
return false;
}
bool Layout::possibleToOrder(const ld::Internal::FinalSection* sect)
{
switch ( sect->type() ) {
case ld::Section::typeUnclassified:
case ld::Section::typeCode:
case ld::Section::typeZeroFill:
return true;
case ld::Section::typeImportProxies:
return false;
default:
if ( _options.haveCmdLineAliases() ) {
for (std::vector<const ld::Atom*>::const_iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
const ld::Atom* atom = *ait;
if ( atom->isAlias() )
return true;
}
}
break;
}
return false;
}
void Layout::buildNameTable()
{
for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
ld::Internal::FinalSection* sect = *sit;
if ( ! possibleToOrder(sect) )
continue;
for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
const ld::Atom* atom = *ait;
if ( atom->symbolTableInclusion() == ld::Atom::symbolTableIn ) {
const char* name = atom->name();
if ( name != NULL) {
NameToAtom::iterator pos = _nameTable.find(name);
if ( pos == _nameTable.end() )
_nameTable[name] = atom;
else {
const ld::Atom* existing = _nameTable[name];
if ( existing != NULL ) {
_nameCollisionAtoms.push_back(existing);
_nameTable[name] = NULL; }
_nameCollisionAtoms.push_back(atom);
}
}
}
}
}
if ( _s_log ) {
fprintf(stderr, "buildNameTable() _nameTable:\n");
for(NameToAtom::iterator it=_nameTable.begin(); it != _nameTable.end(); ++it)
fprintf(stderr, " %p <- %s\n", it->second, it->first);
fprintf(stderr, "buildNameTable() _nameCollisionAtoms:\n");
for(std::vector<const ld::Atom*>::iterator it=_nameCollisionAtoms.begin(); it != _nameCollisionAtoms.end(); ++it)
fprintf(stderr, " %p, %s\n", *it, (*it)->name());
}
}
const ld::Atom* Layout::findAtom(const Options::OrderedSymbol& orderedSymbol)
{
NameToAtom::iterator pos = _nameTable.find(orderedSymbol.symbolName);
if ( pos != _nameTable.end() ) {
if ( (pos->second != NULL) && matchesObjectFile(pos->second, orderedSymbol.objectFileName) ) {
return pos->second;
}
if ( pos->second == NULL ) {
if ( ( orderedSymbol.objectFileName == NULL) && _options.printOrderFileStatistics() ) {
warning("%s specified in order_file but it exists in multiple .o files. "
"Prefix symbol with .o filename in order_file to disambiguate", orderedSymbol.symbolName);
}
for (std::vector<const ld::Atom*>::iterator it=_nameCollisionAtoms.begin(); it != _nameCollisionAtoms.end(); it++) {
const ld::Atom* atom = *it;
if ( strcmp(atom->name(), orderedSymbol.symbolName) == 0 ) {
if ( matchesObjectFile(atom, orderedSymbol.objectFileName) ) {
return atom;
}
}
}
}
}
return NULL;
}
const ld::Atom* Layout::follower(const ld::Atom* atom)
{
for (const ld::Atom* a = _followOnStarts[atom]; a != NULL; a = _followOnNexts[a]) {
assert(a != NULL);
if ( _followOnNexts[a] == atom ) {
return a;
}
}
return NULL;
}
void Layout::buildFollowOnTables()
{
if ( ! _haveOrderFile )
return;
for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
ld::Internal::FinalSection* sect = *sit;
if ( !possibleToOrder(sect) )
continue;
for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
const ld::Atom* atom = *ait;
for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
assert(fit->binding == ld::Fixup::bindingDirectlyBound);
const ld::Atom* followOnAtom = fit->u.target;
if ( _s_log ) fprintf(stderr, "ref %p %s -> %p %s\n", atom, atom->name(), followOnAtom, followOnAtom->name());
assert(_followOnNexts.count(atom) == 0);
_followOnNexts[atom] = followOnAtom;
if ( _followOnStarts.count(atom) == 0 ) {
_followOnStarts[atom] = atom;
if ( _s_log ) fprintf(stderr, " start %s -> %s\n", atom->name(), atom->name());
}
if ( _followOnStarts.count(followOnAtom) == 0 ) {
_followOnStarts[followOnAtom] = _followOnStarts[atom];
if ( _s_log ) fprintf(stderr, " start %s -> %s\n", followOnAtom->name(), _followOnStarts[atom]->name());
}
else {
if ( _followOnStarts[followOnAtom] == followOnAtom ) {
const ld::Atom* a = followOnAtom;
while ( true ) {
assert(_followOnStarts[a] == followOnAtom);
_followOnStarts[a] = _followOnStarts[atom];
if ( _s_log ) fprintf(stderr, " adjust start for %s -> %s\n", a->name(), _followOnStarts[atom]->name());
AtomToAtom::iterator pos = _followOnNexts.find(a);
if ( pos != _followOnNexts.end() )
a = pos->second;
else
break;
}
}
else {
const ld::Atom* curPrevToFollowOnAtom = this->follower(followOnAtom);
assert(curPrevToFollowOnAtom != NULL);
assert((atom->size() == 0) || (curPrevToFollowOnAtom->size() == 0));
if ( atom->size() == 0 ) {
_followOnNexts[curPrevToFollowOnAtom] = atom;
_followOnNexts[atom] = followOnAtom;
_followOnStarts[atom] = _followOnStarts[followOnAtom];
}
else {
const ld::Atom* curPrevPrevToFollowOn = this->follower(curPrevToFollowOnAtom);
if ( curPrevPrevToFollowOn == NULL ) {
_followOnNexts[atom] = curPrevToFollowOnAtom;
for (const ld::Atom* a = atom; a != NULL; a = _followOnNexts[a]) {
if ( _s_log ) fprintf(stderr, " adjust start for %s -> %s\n", a->name(), atom->name());
_followOnStarts[a] = atom;
}
}
else {
_followOnNexts[curPrevPrevToFollowOn] = atom;
_followOnNexts[atom] = curPrevToFollowOnAtom;
_followOnStarts[atom] = _followOnStarts[curPrevToFollowOnAtom];
}
}
}
}
}
}
}
}
if ( _s_log ) {
for(AtomToAtom::iterator it = _followOnStarts.begin(); it != _followOnStarts.end(); ++it)
fprintf(stderr, "start %s -> %s\n", it->first->name(), it->second->name());
for(AtomToAtom::iterator it = _followOnNexts.begin(); it != _followOnNexts.end(); ++it)
fprintf(stderr, "next %s -> %s\n", it->first->name(), (it->second != NULL) ? it->second->name() : "null");
}
}
class InSet
{
public:
InSet(const std::set<const ld::Atom*>& theSet) : _set(theSet) {}
bool operator()(const ld::Atom* atom) const {
return ( _set.count(atom) != 0 );
}
private:
const std::set<const ld::Atom*>& _set;
};
void Layout::buildOrdinalOverrideMap()
{
if ( ! _haveOrderFile )
return;
this->buildNameTable();
uint32_t index = 0;
uint32_t matchCount = 0;
std::set<const ld::Atom*> moveToData;
for(Options::OrderedSymbolsIterator it = _options.orderedSymbolsBegin(); it != _options.orderedSymbolsEnd(); ++it) {
const ld::Atom* atom = this->findAtom(*it);
if ( atom != NULL ) {
switch ( atom->section().type() ) {
case ld::Section::typeZeroFill:
case ld::Section::typeTentativeDefs:
if ( atom->size() <= 512 ) {
const char* dstSeg;
bool wildCardMatch;
const ld::File* f = atom->file();
const char* path = (f != NULL) ? f->path() : NULL;
if ( !_options.moveRwSymbol(atom->name(), path, dstSeg, wildCardMatch) )
moveToData.insert(atom);
}
break;
default:
break;
}
AtomToAtom::iterator start = _followOnStarts.find(atom);
if ( start != _followOnStarts.end() ) {
for(const ld::Atom* nextAtom = start->second; nextAtom != NULL; nextAtom = _followOnNexts[nextAtom]) {
AtomToOrdinal::iterator pos = _ordinalOverrideMap.find(nextAtom);
if ( pos == _ordinalOverrideMap.end() ) {
_ordinalOverrideMap[nextAtom] = index++;
if (_s_log ) fprintf(stderr, "override ordinal %u assigned to %s in cluster from %s\n", index, nextAtom->name(), nextAtom->file()->path());
}
else {
if (_s_log ) fprintf(stderr, "could not order %s as %u because it was already laid out earlier by %s as %u\n",
atom->name(), index, _followOnStarts[atom]->name(), _ordinalOverrideMap[atom] );
}
}
}
else {
_ordinalOverrideMap[atom] = index;
if (_s_log ) fprintf(stderr, "override ordinal %u assigned to %s from %s\n", index, atom->name(), atom->file()->path());
}
++matchCount;
}
else {
if ( _options.printOrderFileStatistics() ) {
if ( it->objectFileName == NULL )
warning("can't find match for order_file entry: %s", it->symbolName);
else
warning("can't find match for order_file entry: %s/%s", it->objectFileName, it->symbolName);
}
}
++index;
}
if ( _options.printOrderFileStatistics() && (_options.orderedSymbolsCount() != matchCount) ) {
warning("only %u out of %lu order_file symbols were applicable", matchCount, _options.orderedSymbolsCount() );
}
if ( ! moveToData.empty() ) {
ld::Internal::FinalSection* dataSect = NULL;
for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
ld::Internal::FinalSection* sect = *sit;
if ( sect->type() == ld::Section::typeUnclassified ) {
if ( (strcmp(sect->sectionName(), "__data") == 0) && (strcmp(sect->segmentName(), "__DATA") == 0) )
dataSect = sect;
}
}
if ( dataSect != NULL ) {
dataSect->atoms.insert(dataSect->atoms.end(), moveToData.begin(), moveToData.end());
for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
ld::Internal::FinalSection* sect = *sit;
switch ( sect->type() ) {
case ld::Section::typeZeroFill:
case ld::Section::typeTentativeDefs:
sect->atoms.erase(std::remove_if(sect->atoms.begin(), sect->atoms.end(), InSet(moveToData)), sect->atoms.end());
break;
default:
break;
}
}
for (std::set<const ld::Atom*>::iterator it=moveToData.begin(); it != moveToData.end(); ++it) {
_state.atomToSection[*it] = dataSect;
}
}
}
}
void Layout::doPass()
{
const bool log = false;
if ( log ) {
fprintf(stderr, "Unordered atoms:\n");
for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
ld::Internal::FinalSection* sect = *sit;
for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
const ld::Atom* atom = *ait;
fprintf(stderr, "\t%p\t%s\t%s\n", atom, sect->sectionName(), atom->name());
}
}
}
this->buildFollowOnTables();
this->buildOrdinalOverrideMap();
for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
ld::Internal::FinalSection* sect = *sit;
if ( sect->type() == ld::Section::typeTempAlias )
continue;
if ( log ) fprintf(stderr, "sorting section %s\n", sect->sectionName());
std::sort(sect->atoms.begin(), sect->atoms.end(), _comparer);
}
if ( log ) {
fprintf(stderr, "Sorted atoms:\n");
for (std::vector<ld::Internal::FinalSection*>::iterator sit=_state.sections.begin(); sit != _state.sections.end(); ++sit) {
ld::Internal::FinalSection* sect = *sit;
for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
const ld::Atom* atom = *ait;
fprintf(stderr, "\t%p\t%s\t%s\n", atom, sect->sectionName(), atom->name());
}
}
}
}
void doPass(const Options& opts, ld::Internal& state)
{
Layout layout(opts, state);
layout.doPass();
}
} } }