[apple/ld64.git] / src / ld / passes / got.cpp

/* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
 *
 * Copyright (c) 2009 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */


#include <stdint.h>
#include <math.h>
#include <unistd.h>
#include <dlfcn.h>

#include <vector>
#include <map>
#include <ext/hash_map>

#include "ld.hpp"
#include "got.h"

namespace ld {
namespace passes {
namespace got {

class File; // forward reference

class GOTEntryAtom : public ld::Atom {
public:
											GOTEntryAtom(ld::Internal& internal, const ld::Atom* target, bool weakImport)
				: ld::Atom(_s_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
							ld::Atom::scopeLinkageUnit, ld::Atom::typeNonLazyPointer, 
							symbolTableNotIn, false, false, false, ld::Atom::Alignment(3)), 
				_fixup(0, ld::Fixup::k1of1, ld::Fixup::kindStoreTargetAddressLittleEndian64, target),
				_target(target)
					{ _fixup.weakImport = weakImport; internal.addAtom(*this); }

	virtual const ld::File*					file() const					{ return NULL; }
	virtual bool							translationUnitSource(const char** dir, const char**) const 
																			{ return false; }
	virtual const char*						name() const					{ return _target->name(); }
	virtual uint64_t						size() const					{ return 8; }
	virtual uint64_t						objectAddress() const			{ return 0; }
	virtual void							copyRawContent(uint8_t buffer[]) const { }
	virtual void							setScope(Scope)					{ }
	virtual ld::Fixup::iterator				fixupsBegin() const				{ return &_fixup; }
	virtual ld::Fixup::iterator				fixupsEnd()	const 				{ return &((ld::Fixup*)&_fixup)[1]; }

private:
	mutable ld::Fixup						_fixup;
	const ld::Atom*							_target;
	
	static ld::Section						_s_section;
};

ld::Section GOTEntryAtom::_s_section("__DATA", "__got", ld::Section::typeNonLazyPointer);


static bool gotFixup(const Options& opts, ld::Internal& internal, const ld::Atom* targetOfGOT, const ld::Fixup* fixup, bool* optimizable)
{
	switch (fixup->kind) {
		case ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoad:
			// start by assuming this can be optimized
			*optimizable = true;
			// cannot do LEA optimization if target is in another dylib
			if ( targetOfGOT->definition() == ld::Atom::definitionProxy ) 
				*optimizable = false;
			// cannot do LEA optimization if target in __huge section
			if ( internal.usingHugeSections && (targetOfGOT->size() > 1024*1024)
											&& (   (targetOfGOT->section().type() == ld::Section::typeZeroFill)
												|| (targetOfGOT->section().type() == ld::Section::typeTentativeDefs)) ) {
				*optimizable = false;
			}
			if ( targetOfGOT->scope() == ld::Atom::scopeGlobal ) {	
				// cannot do LEA optimization if target is weak exported symbol
				if ( (targetOfGOT->definition() == ld::Atom::definitionRegular) && (targetOfGOT->combine() == ld::Atom::combineByName) ) {
					switch ( opts.outputKind() ) {
						case Options::kDynamicExecutable:
						case Options::kDynamicLibrary:
						case Options::kDynamicBundle:
						case Options::kKextBundle:
							*optimizable = false;
							break;
						case Options::kStaticExecutable:
						case Options::kDyld:
						case Options::kPreload:
						case Options::kObjectFile:
							break;
					}
				}
				// cannot do LEA optimization if target is interposable
				if ( opts.interposable(targetOfGOT->name()) ) 
					*optimizable = false;
				// cannot do LEA optimization if target is resolver function
				if ( targetOfGOT->contentType() == ld::Atom::typeResolver ) 
					*optimizable = false;
				// cannot do LEA optimization for flat-namespace
				if ( opts.nameSpace() != Options::kTwoLevelNameSpace ) 
					*optimizable = false;
			}
			return true;
		case ld::Fixup::kindStoreX86PCRel32GOT:
			*optimizable = false;
			return true;
		case ld::Fixup::kindNoneGroupSubordinatePersonality:
			*optimizable = false;
			return true;
		default:
			break;
	}
	
	return false;
}

struct AtomByNameSorter
{
	 bool operator()(const ld::Atom* left, const ld::Atom* right)
	 {
		  return (strcmp(left->name(), right->name()) < 0);
	 }
};

void doPass(const Options& opts, ld::Internal& internal)
{
	const bool log = false;
	
	// only make got section in final linked images
	if ( opts.outputKind() == Options::kObjectFile )
		return;

	// walk all atoms and fixups looking for GOT-able references
	// don't create GOT atoms during this loop because that could invalidate the sections iterator
	std::vector<const ld::Atom*> atomsReferencingGOT;
	std::map<const ld::Atom*,ld::Atom*> gotMap;
	std::map<const ld::Atom*,bool>		weakImportMap;
	atomsReferencingGOT.reserve(128);
	for (std::vector<ld::Internal::FinalSection*>::iterator sit=internal.sections.begin(); sit != internal.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;
			bool atomUsesGOT = false;
			const ld::Atom* targetOfGOT = NULL;
			bool targetIsWeakImport = false;
			for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
				if ( fit->firstInCluster() ) 
					targetOfGOT = NULL;
				switch ( fit->binding ) {
					case ld::Fixup::bindingsIndirectlyBound:
						targetOfGOT = internal.indirectBindingTable[fit->u.bindingIndex];
						targetIsWeakImport = fit->weakImport;
						break;
					case ld::Fixup::bindingDirectlyBound:
						targetOfGOT = fit->u.target;
						targetIsWeakImport = fit->weakImport;
						break;
                    default:
                        break;   
				}
				bool optimizable;
				if ( !gotFixup(opts, internal, targetOfGOT, fit, &optimizable) )
					continue;
				if ( optimizable ) {
					// change from load of GOT entry to lea of target
					if ( log ) fprintf(stderr, "optimized GOT usage in %s to %s\n", atom->name(), targetOfGOT->name());
					switch ( fit->binding ) {
						case ld::Fixup::bindingsIndirectlyBound:
						case ld::Fixup::bindingDirectlyBound:
							fit->binding = ld::Fixup::bindingDirectlyBound;
							fit->u.target = targetOfGOT;
							fit->kind = ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoadNowLEA;
							break;
						default:
							assert(0 && "unsupported GOT reference");
							break;
					}
				}
				else {
					// remember that we need to use GOT in this function
					if ( log ) fprintf(stderr, "found GOT use in %s to %s\n", atom->name(), targetOfGOT->name());
					if ( !atomUsesGOT ) {
						atomsReferencingGOT.push_back(atom);
						atomUsesGOT = true;
					}
					gotMap[targetOfGOT] = NULL;
					// record weak_import attribute
					std::map<const ld::Atom*,bool>::iterator pos = weakImportMap.find(targetOfGOT);
					if ( pos == weakImportMap.end() ) {
						// target not in weakImportMap, so add
						if ( log ) fprintf(stderr, "weakImportMap[%s] = %d\n", targetOfGOT->name(), targetIsWeakImport);
						weakImportMap[targetOfGOT] = targetIsWeakImport; 
					}
					else {
						// target in weakImportMap, check for weakness mismatch
						if ( pos->second != targetIsWeakImport ) {
							// found mismatch
							switch ( opts.weakReferenceMismatchTreatment() ) {
								case Options::kWeakReferenceMismatchError:
									throwf("mismatching weak references for symbol: %s", targetOfGOT->name());
								case Options::kWeakReferenceMismatchWeak:
									pos->second = true;
									break;
								case Options::kWeakReferenceMismatchNonWeak:
									pos->second = false;
									break;
							}
						}
					}
				}
			}
		}
	}
	
	// make GOT entries	
	for (std::map<const ld::Atom*,ld::Atom*>::iterator it = gotMap.begin(); it != gotMap.end(); ++it) {
		it->second = new GOTEntryAtom(internal, it->first, weakImportMap[it->first]);
	}
	
	// update atoms to use GOT entries
	for (std::vector<const ld::Atom*>::iterator it=atomsReferencingGOT.begin(); it != atomsReferencingGOT.end(); ++it) {
		const ld::Atom* atom = *it;
		const ld::Atom* targetOfGOT = NULL;
		ld::Fixup::iterator fitThatSetTarget = NULL;
		for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
			if ( fit->firstInCluster() ) {
				targetOfGOT = NULL;
				fitThatSetTarget = NULL;
			}
			switch ( fit->binding ) {
				case ld::Fixup::bindingsIndirectlyBound:
					targetOfGOT = internal.indirectBindingTable[fit->u.bindingIndex];
					fitThatSetTarget = fit;
					break;
				case ld::Fixup::bindingDirectlyBound:
					targetOfGOT = fit->u.target;
					fitThatSetTarget = fit;
					break;
                default:
                    break;    
			}
			bool optimizable;
			if ( (targetOfGOT == NULL) || !gotFixup(opts, internal, targetOfGOT, fit, &optimizable) )
				continue;
			if ( !optimizable ) {
				// GOT use not optimized away, update to bind to GOT entry
				assert(fitThatSetTarget != NULL);
				switch ( fitThatSetTarget->binding ) {
					case ld::Fixup::bindingsIndirectlyBound:
					case ld::Fixup::bindingDirectlyBound:
						fitThatSetTarget->binding = ld::Fixup::bindingDirectlyBound;
						fitThatSetTarget->u.target = gotMap[targetOfGOT];
						break;
					default:
						assert(0 && "unsupported GOT reference");
						break;
				}
			}
		}
	}
	
	// sort new atoms so links are consistent
	for (std::vector<ld::Internal::FinalSection*>::iterator sit=internal.sections.begin(); sit != internal.sections.end(); ++sit) {
		ld::Internal::FinalSection* sect = *sit;
		if ( sect->type() == ld::Section::typeNonLazyPointer ) {
			std::sort(sect->atoms.begin(), sect->atoms.end(), AtomByNameSorter());
		}
	}
}


} // namespace got
} // namespace passes 
} // namespace ld
Commit	Line	Data
a645023d A	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
	31	#include <vector>
	32	#include <map>
	33	#include <ext/hash_map>
	34
	35	#include "ld.hpp"
	36	#include "got.h"
	37
	38	namespace ld {
	39	namespace passes {
	40	namespace got {
	41
	42	class File; // forward reference
	43
	44	class GOTEntryAtom : public ld::Atom {
	45	public:
	46	GOTEntryAtom(ld::Internal& internal, const ld::Atom* target, bool weakImport)
	47	: ld::Atom(_s_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
	48	ld::Atom::scopeLinkageUnit, ld::Atom::typeNonLazyPointer,
	49	symbolTableNotIn, false, false, false, ld::Atom::Alignment(3)),
	50	_fixup(0, ld::Fixup::k1of1, ld::Fixup::kindStoreTargetAddressLittleEndian64, target),
	51	_target(target)
	52	{ _fixup.weakImport = weakImport; internal.addAtom(*this); }
	53
	54	virtual const ld::File* file() const { return NULL; }
	55	virtual bool translationUnitSource(const char dir, const char) const
	56	{ return false; }
	57	virtual const char* name() const { return _target->name(); }
	58	virtual uint64_t size() const { return 8; }
	59	virtual uint64_t objectAddress() const { return 0; }
	60	virtual void copyRawContent(uint8_t buffer[]) const { }
	61	virtual void setScope(Scope) { }
	62	virtual ld::Fixup::iterator fixupsBegin() const { return &_fixup; }
	63	virtual ld::Fixup::iterator fixupsEnd() const { return &((ld::Fixup*)&_fixup)[1]; }
	64
65	private:
66	mutable ld::Fixup _fixup;
67	const ld::Atom* _target;
68
69	static ld::Section _s_section;
70	};
71
72	ld::Section GOTEntryAtom::_s_section("__DATA", "__got", ld::Section::typeNonLazyPointer);
73
74
75	static bool gotFixup(const Options& opts, ld::Internal& internal, const ld::Atom* targetOfGOT, const ld::Fixup* fixup, bool* optimizable)
76	{
77	switch (fixup->kind) {
78	case ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoad:
79	// start by assuming this can be optimized
80	*optimizable = true;
81	// cannot do LEA optimization if target is in another dylib
82	if ( targetOfGOT->definition() == ld::Atom::definitionProxy )
83	*optimizable = false;
84	// cannot do LEA optimization if target in __huge section
85	if ( internal.usingHugeSections && (targetOfGOT->size() > 1024*1024)
86	&& ( (targetOfGOT->section().type() == ld::Section::typeZeroFill)
87	\|\| (targetOfGOT->section().type() == ld::Section::typeTentativeDefs)) ) {
88	*optimizable = false;
89	}
90	if ( targetOfGOT->scope() == ld::Atom::scopeGlobal ) {
91	// cannot do LEA optimization if target is weak exported symbol
b2fa67a8 A	92	if ( (targetOfGOT->definition() == ld::Atom::definitionRegular) && (targetOfGOT->combine() == ld::Atom::combineByName) ) {
	93	switch ( opts.outputKind() ) {
	94	case Options::kDynamicExecutable:
	95	case Options::kDynamicLibrary:
	96	case Options::kDynamicBundle:
	97	case Options::kKextBundle:
	98	*optimizable = false;
	99	break;
	100	case Options::kStaticExecutable:
	101	case Options::kDyld:
	102	case Options::kPreload:
	103	case Options::kObjectFile:
	104	break;
	105	}
	106	}
a645023d A	107	// cannot do LEA optimization if target is interposable
	108	if ( opts.interposable(targetOfGOT->name()) )
	109	*optimizable = false;
	110	// cannot do LEA optimization if target is resolver function
	111	if ( targetOfGOT->contentType() == ld::Atom::typeResolver )
	112	*optimizable = false;
	113	// cannot do LEA optimization for flat-namespace
	114	if ( opts.nameSpace() != Options::kTwoLevelNameSpace )
	115	*optimizable = false;
	116	}
	117	return true;
	118	case ld::Fixup::kindStoreX86PCRel32GOT:
	119	*optimizable = false;
	120	return true;
afe874b1 A	121	case ld::Fixup::kindNoneGroupSubordinatePersonality:
	122	*optimizable = false;
	123	return true;
a645023d A	124	default:
	125	break;
	126	}
	127
	128	return false;
	129	}
	130
	131	struct AtomByNameSorter
	132	{
	133	bool operator()(const ld::Atom* left, const ld::Atom* right)
	134	{
	135	return (strcmp(left->name(), right->name()) < 0);
	136	}
	137	};
	138
	139	void doPass(const Options& opts, ld::Internal& internal)
	140	{
	141	const bool log = false;
	142
	143	// only make got section in final linked images
	144	if ( opts.outputKind() == Options::kObjectFile )
	145	return;
	146
afe874b1 A	147	// walk all atoms and fixups looking for GOT-able references
afe874b1 A	148	// don't create GOT atoms during this loop because that could invalidate the sections iterator
a645023d A	149	std::vector<const ld::Atom*> atomsReferencingGOT;
	150	std::map<const ld::Atom,ld::Atom> gotMap;
	151	std::map<const ld::Atom*,bool> weakImportMap;
	152	atomsReferencingGOT.reserve(128);
	153	for (std::vector<ld::Internal::FinalSection*>::iterator sit=internal.sections.begin(); sit != internal.sections.end(); ++sit) {
	154	ld::Internal::FinalSection* sect = *sit;
	155	for (std::vector<const ld::Atom*>::iterator ait=sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
	156	const ld::Atom* atom = *ait;
	157	bool atomUsesGOT = false;
	158	const ld::Atom* targetOfGOT = NULL;
afe874b1	159	bool targetIsWeakImport = false;
a645023d A	160	for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
	161	if ( fit->firstInCluster() )
	162	targetOfGOT = NULL;
	163	switch ( fit->binding ) {
	164	case ld::Fixup::bindingsIndirectlyBound:
	165	targetOfGOT = internal.indirectBindingTable[fit->u.bindingIndex];
afe874b1	166	targetIsWeakImport = fit->weakImport;
a645023d A	167	break;
	168	case ld::Fixup::bindingDirectlyBound:
	169	targetOfGOT = fit->u.target;
afe874b1	170	targetIsWeakImport = fit->weakImport;
a645023d A	171	break;
	172	default:
	173	break;
	174	}
	175	bool optimizable;
	176	if ( !gotFixup(opts, internal, targetOfGOT, fit, &optimizable) )
	177	continue;
	178	if ( optimizable ) {
	179	// change from load of GOT entry to lea of target
	180	if ( log ) fprintf(stderr, "optimized GOT usage in %s to %s\n", atom->name(), targetOfGOT->name());
	181	switch ( fit->binding ) {
	182	case ld::Fixup::bindingsIndirectlyBound:
	183	case ld::Fixup::bindingDirectlyBound:
	184	fit->binding = ld::Fixup::bindingDirectlyBound;
	185	fit->u.target = targetOfGOT;
	186	fit->kind = ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoadNowLEA;
	187	break;
	188	default:
	189	assert(0 && "unsupported GOT reference");
	190	break;
	191	}
	192	}
	193	else {
	194	// remember that we need to use GOT in this function
	195	if ( log ) fprintf(stderr, "found GOT use in %s to %s\n", atom->name(), targetOfGOT->name());
	196	if ( !atomUsesGOT ) {
	197	atomsReferencingGOT.push_back(atom);
	198	atomUsesGOT = true;
	199	}
	200	gotMap[targetOfGOT] = NULL;
	201	// record weak_import attribute
	202	std::map<const ld::Atom*,bool>::iterator pos = weakImportMap.find(targetOfGOT);
	203	if ( pos == weakImportMap.end() ) {
	204	// target not in weakImportMap, so add
afe874b1 A	205	if ( log ) fprintf(stderr, "weakImportMap[%s] = %d\n", targetOfGOT->name(), targetIsWeakImport);
afe874b1 A	206	weakImportMap[targetOfGOT] = targetIsWeakImport;
a645023d A	207	}
	208	else {
	209	// target in weakImportMap, check for weakness mismatch
afe874b1	210	if ( pos->second != targetIsWeakImport ) {
a645023d A	211	// found mismatch
	212	switch ( opts.weakReferenceMismatchTreatment() ) {
	213	case Options::kWeakReferenceMismatchError:
	214	throwf("mismatching weak references for symbol: %s", targetOfGOT->name());
	215	case Options::kWeakReferenceMismatchWeak:
	216	pos->second = true;
	217	break;
	218	case Options::kWeakReferenceMismatchNonWeak:
	219	pos->second = false;
	220	break;
	221	}
	222	}
	223	}
	224	}
	225	}
	226	}
	227	}
	228
	229	// make GOT entries
	230	for (std::map<const ld::Atom,ld::Atom>::iterator it = gotMap.begin(); it != gotMap.end(); ++it) {
	231	it->second = new GOTEntryAtom(internal, it->first, weakImportMap[it->first]);
	232	}
	233
	234	// update atoms to use GOT entries
	235	for (std::vector<const ld::Atom*>::iterator it=atomsReferencingGOT.begin(); it != atomsReferencingGOT.end(); ++it) {
	236	const ld::Atom* atom = *it;
	237	const ld::Atom* targetOfGOT = NULL;
	238	ld::Fixup::iterator fitThatSetTarget = NULL;
	239	for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
	240	if ( fit->firstInCluster() ) {
	241	targetOfGOT = NULL;
	242	fitThatSetTarget = NULL;
	243	}
	244	switch ( fit->binding ) {
	245	case ld::Fixup::bindingsIndirectlyBound:
	246	targetOfGOT = internal.indirectBindingTable[fit->u.bindingIndex];
	247	fitThatSetTarget = fit;
	248	break;
	249	case ld::Fixup::bindingDirectlyBound:
	250	targetOfGOT = fit->u.target;
	251	fitThatSetTarget = fit;
	252	break;
	253	default:
	254	break;
	255	}
	256	bool optimizable;
	257	if ( (targetOfGOT == NULL) \|\| !gotFixup(opts, internal, targetOfGOT, fit, &optimizable) )
	258	continue;
	259	if ( !optimizable ) {
	260	// GOT use not optimized away, update to bind to GOT entry
	261	assert(fitThatSetTarget != NULL);
	262	switch ( fitThatSetTarget->binding ) {
	263	case ld::Fixup::bindingsIndirectlyBound:
	264	case ld::Fixup::bindingDirectlyBound:
	265	fitThatSetTarget->binding = ld::Fixup::bindingDirectlyBound;
	266	fitThatSetTarget->u.target = gotMap[targetOfGOT];
	267	break;
	268	default:
	269	assert(0 && "unsupported GOT reference");
	270	break;
	271	}
	272	}
	273	}
	274	}
275
276	// sort new atoms so links are consistent
277	for (std::vector<ld::Internal::FinalSection*>::iterator sit=internal.sections.begin(); sit != internal.sections.end(); ++sit) {
278	ld::Internal::FinalSection* sect = *sit;
279	if ( sect->type() == ld::Section::typeNonLazyPointer ) {
280	std::sort(sect->atoms.begin(), sect->atoms.end(), AtomByNameSorter());
281	}
282	}
283	}
284
285
286	} // namespace got
287	} // namespace passes
288	} // namespace ld