[apple/ld64.git] / src / ld / SymbolTable.h

/* -*- 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@
 */

#ifndef __SYMBOL_TABLE_H__
#define __SYMBOL_TABLE_H__

#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <sys/sysctl.h>
#include <fcntl.h>
#include <errno.h>
#include <limits.h>
#include <unistd.h>
#include <mach/mach_time.h>
#include <mach/vm_statistics.h>
#include <mach/mach_init.h>
#include <mach/mach_host.h>
#include <dlfcn.h>
#include <mach-o/dyld.h>

#include <vector>
#include <unordered_map>

#include "Options.h"
#include "ld.hpp"

namespace ld {
namespace tool {


class SymbolTable : public ld::IndirectBindingTable
{
public:
	typedef uint32_t IndirectBindingSlot;

private:
	typedef std::unordered_map<const char*, IndirectBindingSlot, CStringHash, CStringEquals> NameToSlot;

	class ContentFuncs {
	public:
		size_t	operator()(const ld::Atom*) const;
		bool	operator()(const ld::Atom* left, const ld::Atom* right) const;
	};
	typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, ContentFuncs, ContentFuncs> ContentToSlot;

	class ReferencesHashFuncs {
	public:
		size_t	operator()(const ld::Atom*) const;
		bool	operator()(const ld::Atom* left, const ld::Atom* right) const;
	};
	typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, ReferencesHashFuncs, ReferencesHashFuncs> ReferencesToSlot;

	class CStringHashFuncs {
	public:
		size_t	operator()(const ld::Atom*) const;
		bool	operator()(const ld::Atom* left, const ld::Atom* right) const;
	};
	typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, CStringHashFuncs, CStringHashFuncs> CStringToSlot;

	class UTF16StringHashFuncs {
	public:
		size_t	operator()(const ld::Atom*) const;
		bool	operator()(const ld::Atom* left, const ld::Atom* right) const;
	};
	typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, UTF16StringHashFuncs, UTF16StringHashFuncs> UTF16StringToSlot;

	typedef std::map<IndirectBindingSlot, const char*> SlotToName;
	typedef std::unordered_map<const char*, CStringToSlot*, CStringHash, CStringEquals> NameToMap;
    
    typedef std::vector<const ld::Atom *> DuplicatedSymbolAtomList;
    typedef std::map<const char *, DuplicatedSymbolAtomList * > DuplicateSymbols;
	
public:

	class byNameIterator {
	public:
		byNameIterator&			operator++(int) { ++_nameTableIterator; return *this; }
		const ld::Atom*			operator*() { return _slotTable[_nameTableIterator->second]; }
		bool					operator!=(const byNameIterator& lhs) { return _nameTableIterator != lhs._nameTableIterator; }

	private:
		friend class SymbolTable;
								byNameIterator(NameToSlot::iterator it, std::vector<const ld::Atom*>& indirectTable)
									: _nameTableIterator(it), _slotTable(indirectTable) {} 
		
		NameToSlot::iterator			_nameTableIterator;
		std::vector<const ld::Atom*>&	_slotTable;
	};
	
						SymbolTable(const Options& opts, std::vector<const ld::Atom*>& ibt);

	bool				add(const ld::Atom& atom, bool ignoreDuplicates);
	IndirectBindingSlot	findSlotForName(const char* name);
	IndirectBindingSlot	findSlotForContent(const ld::Atom* atom, const ld::Atom** existingAtom);
	IndirectBindingSlot	findSlotForReferences(const ld::Atom* atom, const ld::Atom** existingAtom);
	const ld::Atom*		atomForSlot(IndirectBindingSlot s)	{ return _indirectBindingTable[s]; }
	unsigned int		updateCount()						{ return _indirectBindingTable.size(); }
	void				undefines(std::vector<const char*>& undefines);
	void				tentativeDefs(std::vector<const char*>& undefines);
	void				mustPreserveForBitcode(std::unordered_set<const char*>& syms);
	void				removeDeadAtoms();
	bool				hasName(const char* name);
	bool				hasExternalTentativeDefinitions()	{ return _hasExternalTentativeDefinitions; }
	byNameIterator		begin()								{ return byNameIterator(_byNameTable.begin(),_indirectBindingTable); }
	byNameIterator		end()								{ return byNameIterator(_byNameTable.end(),_indirectBindingTable); }
	void				printStatistics();
	void				removeDeadUndefs(std::vector<const ld::Atom *>& allAtoms, const std::unordered_set<const ld::Atom*>& keep);

	// from ld::IndirectBindingTable
	virtual const char*			indirectName(IndirectBindingSlot slot) const;
	virtual const ld::Atom*		indirectAtom(IndirectBindingSlot slot) const;
    
    // Prints the duplicated symbols to stderr and throws. Only valid to call if hasDuplicateSymbols() returns true.
    void                checkDuplicateSymbols() const;


private:
	bool					addByName(const ld::Atom& atom, bool ignoreDuplicates);
	bool					addByContent(const ld::Atom& atom);
	bool					addByReferences(const ld::Atom& atom);
	void					markCoalescedAway(const ld::Atom* atom);
    
    // Tracks duplicated symbols. Each call adds file to the list of files defining symbol.
    // The file list is uniqued per symbol, so calling multiple times for the same symbol/file pair is permitted.
    void                    addDuplicateSymbol(const char *symbol, const ld::Atom* atom);

	const Options&					_options;
	NameToSlot						_byNameTable;
	SlotToName						_byNameReverseTable;
	ContentToSlot					_literal4Table;
	ContentToSlot					_literal8Table;
	ContentToSlot					_literal16Table;
	UTF16StringToSlot				_utf16Table;
	CStringToSlot					_cstringTable;
	NameToMap						_nonStdCStringSectionToMap;
	ReferencesToSlot				_nonLazyPointerTable;
	ReferencesToSlot				_threadPointerTable;
	ReferencesToSlot				_cfStringTable;
	ReferencesToSlot				_objc2ClassRefTable;
	ReferencesToSlot				_pointerToCStringTable;
	std::vector<const ld::Atom*>&	_indirectBindingTable;
	bool							_hasExternalTentativeDefinitions;
	
    DuplicateSymbols                _duplicateSymbols;

};

} // namespace tool 
} // namespace ld 


#endif // __SYMBOL_TABLE_H__
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	#ifndef __SYMBOL_TABLE_H__
	26	#define __SYMBOL_TABLE_H__
	27
	28	#include <stdlib.h>
	29	#include <sys/types.h>
	30	#include <sys/stat.h>
	31	#include <sys/mman.h>
	32	#include <sys/sysctl.h>
	33	#include <fcntl.h>
	34	#include <errno.h>
	35	#include <limits.h>
	36	#include <unistd.h>
	37	#include <mach/mach_time.h>
	38	#include <mach/vm_statistics.h>
	39	#include <mach/mach_init.h>
	40	#include <mach/mach_host.h>
	41	#include <dlfcn.h>
	42	#include <mach-o/dyld.h>
	43
	44	#include <vector>
d425e388	45	#include <unordered_map>
a645023d A	46
	47	#include "Options.h"
	48	#include "ld.hpp"
	49
	50	namespace ld {
	51	namespace tool {
	52
	53
	54	class SymbolTable : public ld::IndirectBindingTable
	55	{
	56	public:
	57	typedef uint32_t IndirectBindingSlot;
	58
	59	private:
d425e388	60	typedef std::unordered_map<const char*, IndirectBindingSlot, CStringHash, CStringEquals> NameToSlot;
a645023d A	61
	62	class ContentFuncs {
	63	public:
	64	size_t operator()(const ld::Atom*) const;
	65	bool operator()(const ld::Atom* left, const ld::Atom* right) const;
	66	};
d425e388	67	typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, ContentFuncs, ContentFuncs> ContentToSlot;
a645023d A	68
	69	class ReferencesHashFuncs {
	70	public:
	71	size_t operator()(const ld::Atom*) const;
	72	bool operator()(const ld::Atom* left, const ld::Atom* right) const;
	73	};
d425e388	74	typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, ReferencesHashFuncs, ReferencesHashFuncs> ReferencesToSlot;
a645023d A	75
	76	class CStringHashFuncs {
	77	public:
	78	size_t operator()(const ld::Atom*) const;
	79	bool operator()(const ld::Atom* left, const ld::Atom* right) const;
	80	};
d425e388	81	typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, CStringHashFuncs, CStringHashFuncs> CStringToSlot;
a645023d A	82
	83	class UTF16StringHashFuncs {
	84	public:
	85	size_t operator()(const ld::Atom*) const;
	86	bool operator()(const ld::Atom* left, const ld::Atom* right) const;
	87	};
d425e388	88	typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, UTF16StringHashFuncs, UTF16StringHashFuncs> UTF16StringToSlot;
a645023d A	89
a645023d A	90	typedef std::map<IndirectBindingSlot, const char*> SlotToName;
d425e388	91	typedef std::unordered_map<const char, CStringToSlot, CStringHash, CStringEquals> NameToMap;
ebf6f434 A	92
	93	typedef std::vector<const ld::Atom *> DuplicatedSymbolAtomList;
	94	typedef std::map<const char , DuplicatedSymbolAtomList > DuplicateSymbols;
a645023d A	95
	96	public:
	97
	98	class byNameIterator {
	99	public:
	100	byNameIterator& operator++(int) { ++_nameTableIterator; return *this; }
	101	const ld::Atom* operator*() { return _slotTable[_nameTableIterator->second]; }
	102	bool operator!=(const byNameIterator& lhs) { return _nameTableIterator != lhs._nameTableIterator; }
	103
	104	private:
	105	friend class SymbolTable;
	106	byNameIterator(NameToSlot::iterator it, std::vector<const ld::Atom*>& indirectTable)
	107	: _nameTableIterator(it), _slotTable(indirectTable) {}
	108
	109	NameToSlot::iterator _nameTableIterator;
	110	std::vector<const ld::Atom*>& _slotTable;
	111	};
	112
	113	SymbolTable(const Options& opts, std::vector<const ld::Atom*>& ibt);
	114
	115	bool add(const ld::Atom& atom, bool ignoreDuplicates);
	116	IndirectBindingSlot findSlotForName(const char* name);
	117	IndirectBindingSlot findSlotForContent(const ld::Atom* atom, const ld::Atom** existingAtom);
	118	IndirectBindingSlot findSlotForReferences(const ld::Atom* atom, const ld::Atom** existingAtom);
	119	const ld::Atom* atomForSlot(IndirectBindingSlot s) { return _indirectBindingTable[s]; }
	120	unsigned int updateCount() { return _indirectBindingTable.size(); }
	121	void undefines(std::vector<const char*>& undefines);
	122	void tentativeDefs(std::vector<const char*>& undefines);
ec29ba20	123	void mustPreserveForBitcode(std::unordered_set<const char*>& syms);
9543cb2f	124	void removeDeadAtoms();
a645023d A	125	bool hasName(const char* name);
	126	bool hasExternalTentativeDefinitions() { return _hasExternalTentativeDefinitions; }
	127	byNameIterator begin() { return byNameIterator(_byNameTable.begin(),_indirectBindingTable); }
	128	byNameIterator end() { return byNameIterator(_byNameTable.end(),_indirectBindingTable); }
	129	void printStatistics();
f410558f A	130	void removeDeadUndefs(std::vector<const ld::Atom >& allAtoms, const std::unordered_set<const ld::Atom>& keep);
f410558f A	131
a645023d A	132	// from ld::IndirectBindingTable
	133	virtual const char* indirectName(IndirectBindingSlot slot) const;
	134	virtual const ld::Atom* indirectAtom(IndirectBindingSlot slot) const;
ebf6f434 A	135
	136	// Prints the duplicated symbols to stderr and throws. Only valid to call if hasDuplicateSymbols() returns true.
	137	void checkDuplicateSymbols() const;
	138
a645023d A	139
	140	private:
	141	bool addByName(const ld::Atom& atom, bool ignoreDuplicates);
	142	bool addByContent(const ld::Atom& atom);
	143	bool addByReferences(const ld::Atom& atom);
	144	void markCoalescedAway(const ld::Atom* atom);
ebf6f434 A	145
	146	// Tracks duplicated symbols. Each call adds file to the list of files defining symbol.
	147	// The file list is uniqued per symbol, so calling multiple times for the same symbol/file pair is permitted.
	148	void addDuplicateSymbol(const char symbol, const ld::Atom atom);
a645023d A	149
	150	const Options& _options;
	151	NameToSlot _byNameTable;
	152	SlotToName _byNameReverseTable;
	153	ContentToSlot _literal4Table;
	154	ContentToSlot _literal8Table;
	155	ContentToSlot _literal16Table;
	156	UTF16StringToSlot _utf16Table;
	157	CStringToSlot _cstringTable;
	158	NameToMap _nonStdCStringSectionToMap;
	159	ReferencesToSlot _nonLazyPointerTable;
eaf282aa	160	ReferencesToSlot _threadPointerTable;
a645023d A	161	ReferencesToSlot _cfStringTable;
	162	ReferencesToSlot _objc2ClassRefTable;
	163	ReferencesToSlot _pointerToCStringTable;
	164	std::vector<const ld::Atom*>& _indirectBindingTable;
	165	bool _hasExternalTentativeDefinitions;
	166
ebf6f434	167	DuplicateSymbols _duplicateSymbols;
a645023d A	168
	169	};
	170
	171	} // namespace tool
	172	} // namespace ld
	173
	174
	175	#endif // __SYMBOL_TABLE_H__