src/ld/SymbolTable.h

   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>
  45 #include <unordered_map>
  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:
  60         typedef std::unordered_map<const char*, IndirectBindingSlot, CStringHash, CStringEquals> NameToSlot;
  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         };
  67         typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, ContentFuncs, ContentFuncs> ContentToSlot;
  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         };
  74         typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, ReferencesHashFuncs, ReferencesHashFuncs> ReferencesToSlot;
  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         };
  81         typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, CStringHashFuncs, CStringHashFuncs> CStringToSlot;
  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         };
  88         typedef std::unordered_map<const ld::Atom*, IndirectBindingSlot, UTF16StringHashFuncs, UTF16StringHashFuncs> UTF16StringToSlot;
  89
  90         typedef std::map<IndirectBindingSlot, const char*> SlotToName;
  91         typedef std::unordered_map<const char*, CStringToSlot*, CStringHash, CStringEquals> NameToMap;
  92
  93     typedef std::vector<const ld::Atom *> DuplicatedSymbolAtomList;
  94     typedef std::map<const char *, DuplicatedSymbolAtomList * > DuplicateSymbols;
  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);
 123         void                            mustPreserveForBitcode(std::unordered_set<const char*>& syms);
 124         void                            removeDeadAtoms();
 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();
 130         void                            removeDeadUndefs(std::vector<const ld::Atom *>& allAtoms, const std::unordered_set<const ld::Atom*>& keep);
 131
 132         // from ld::IndirectBindingTable
 133         virtual const char*                     indirectName(IndirectBindingSlot slot) const;
 134         virtual const ld::Atom*         indirectAtom(IndirectBindingSlot slot) const;
 135
 136     // Prints the duplicated symbols to stderr and throws. Only valid to call if hasDuplicateSymbols() returns true.
 137     void                checkDuplicateSymbols() const;
 138
 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);
 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);
 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;
 160         ReferencesToSlot                                _threadPointerTable;
 161         ReferencesToSlot                                _cfStringTable;
 162         ReferencesToSlot                                _objc2ClassRefTable;
 163         ReferencesToSlot                                _pointerToCStringTable;
 164         std::vector<const ld::Atom*>&   _indirectBindingTable;
 165         bool                                                    _hasExternalTentativeDefinitions;
 166
 167     DuplicateSymbols                _duplicateSymbols;
 168
 169 };
 170
 171 } // namespace tool
 172 } // namespace ld
 173
 174
 175 #endif // __SYMBOL_TABLE_H__