ld64-134.9/src/ld/SymbolTable.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-*
   2  *
   3  * Copyright (c) 2009-2010 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 <stdlib.h>
  27 #include <sys/types.h>
  28 #include <sys/stat.h>
  29 #include <sys/mman.h>
  30 #include <sys/sysctl.h>
  31 #include <fcntl.h>
  32 #include <errno.h>
  33 #include <limits.h>
  34 #include <unistd.h>
  35 #include <assert.h>
  36
  37 #include <iostream>
  38 #include <sstream>
  39 #include <string>
  40 #include <map>
  41 #include <set>
  42 #include <vector>
  43 #include <algorithm>
  44 #include <ext/hash_map>
  45 #include <ext/hash_set>
  46
  47 #include "Options.h"
  48
  49 #include "ld.hpp"
  50 #include "InputFiles.h"
  51 #include "SymbolTable.h"
  52
  53
  54
  55 namespace ld {
  56 namespace tool {
  57
  58
  59 // HACK, I can't find a way to pass values in the compare classes (e.g. ContentFuncs)
  60 // so use global variable to pass info.
  61 static ld::IndirectBindingTable*        _s_indirectBindingTable = NULL;
  62
  63
  64 SymbolTable::SymbolTable(const Options& opts, std::vector<const ld::Atom*>& ibt)
  65         : _options(opts), _cstringTable(6151), _indirectBindingTable(ibt), _hasExternalTentativeDefinitions(false)
  66 {
  67         _s_indirectBindingTable = this;
  68 }
  69
  70
  71 size_t SymbolTable::ContentFuncs::operator()(const ld::Atom* atom) const
  72 {
  73         return atom->contentHash(*_s_indirectBindingTable);
  74 }
  75
  76 bool SymbolTable::ContentFuncs::operator()(const ld::Atom* left, const ld::Atom* right) const
  77 {
  78         return (memcmp(left->rawContentPointer(), right->rawContentPointer(), left->size()) == 0);
  79 }
  80
  81
  82
  83 size_t SymbolTable::CStringHashFuncs::operator()(const ld::Atom* atom) const
  84 {
  85         return atom->contentHash(*_s_indirectBindingTable);
  86 }
  87
  88 bool SymbolTable::CStringHashFuncs::operator()(const ld::Atom* left, const ld::Atom* right) const
  89 {
  90         return (strcmp((char*)left->rawContentPointer(), (char*)right->rawContentPointer()) == 0);
  91 }
  92
  93
  94 size_t SymbolTable::UTF16StringHashFuncs::operator()(const ld::Atom* atom) const
  95 {
  96         return atom->contentHash(*_s_indirectBindingTable);
  97 }
  98
  99 bool SymbolTable::UTF16StringHashFuncs::operator()(const ld::Atom* left, const ld::Atom* right) const
 100 {
 101         if ( left == right )
 102                 return true;
 103         const void* leftContent = left->rawContentPointer();
 104         const void* rightContent = right->rawContentPointer();
 105         unsigned int amount = left->size()-2;
 106         bool result = (memcmp(leftContent, rightContent, amount) == 0);
 107         return result;
 108 }
 109
 110
 111 size_t SymbolTable::ReferencesHashFuncs::operator()(const ld::Atom* atom) const
 112 {
 113         return atom->contentHash(*_s_indirectBindingTable);
 114 }
 115
 116 bool SymbolTable::ReferencesHashFuncs::operator()(const ld::Atom* left, const ld::Atom* right) const
 117 {
 118         return left->canCoalesceWith(*right, *_s_indirectBindingTable);
 119 }
 120
 121
 122 void SymbolTable::addDuplicateSymbol(const char *name, const ld::Atom *atom)
 123 {
 124     // Look up or create the file list for name.
 125     DuplicateSymbols::iterator symbolsIterator = _duplicateSymbols.find(name);
 126     DuplicatedSymbolAtomList *atoms = NULL;
 127     if (symbolsIterator != _duplicateSymbols.end()) {
 128         atoms = symbolsIterator->second;
 129     } else {
 130         atoms = new std::vector<const ld::Atom *>;
 131         _duplicateSymbols.insert(std::pair<const char *, DuplicatedSymbolAtomList *>(name, atoms));
 132     }
 133
 134     // check if file is already in the list, add it if not
 135     bool found = false;
 136     for (DuplicatedSymbolAtomList::iterator it = atoms->begin(); !found && it != atoms->end(); it++)
 137         if (strcmp((*it)->file()->path(), atom->file()->path()) == 0)
 138             found = true;
 139     if (!found)
 140         atoms->push_back(atom);
 141 }
 142
 143 void SymbolTable::checkDuplicateSymbols() const
 144 {
 145     bool foundDuplicate = false;
 146     for (DuplicateSymbols::const_iterator symbolIt = _duplicateSymbols.begin(); symbolIt != _duplicateSymbols.end(); symbolIt++) {
 147         DuplicatedSymbolAtomList *atoms = symbolIt->second;
 148         bool reportDuplicate;
 149         if (_options.deadCodeStrip()) {
 150             // search for a live atom
 151             reportDuplicate = false;
 152             for (DuplicatedSymbolAtomList::iterator it = atoms->begin(); !reportDuplicate && it != atoms->end(); it++) {
 153                 if ((*it)->live())
 154                     reportDuplicate = true;
 155             }
 156         } else {
 157             reportDuplicate = true;
 158         }
 159         if (reportDuplicate) {
 160             foundDuplicate = true;
 161             fprintf(stderr, "duplicate symbol %s in:\n", symbolIt->first);
 162             for (DuplicatedSymbolAtomList::iterator atomIt = atoms->begin(); atomIt != atoms->end(); atomIt++) {
 163                 fprintf(stderr, "    %s\n", (*atomIt)->file()->path());
 164             }
 165         }
 166     }
 167     if (foundDuplicate)
 168         throwf("%d duplicate symbol%s", (int)_duplicateSymbols.size(), _duplicateSymbols.size()==1?"":"s");
 169 }
 170
 171 // AtomPicker encapsulates the logic for picking which atom to use when adding an atom by name results in a collision
 172 class NameCollisionResolution {
 173 public:
 174         NameCollisionResolution(const ld::Atom& a, const ld::Atom& b, bool ignoreDuplicates, const Options& options) : _atomA(a), _atomB(b), _options(options), _reportDuplicate(false), _ignoreDuplicates(ignoreDuplicates) {
 175                 pickAtom();
 176         }
 177
 178         // Returns which atom to use
 179         const ld::Atom& chosen() { return *_chosen; }
 180         bool choseAtom(const ld::Atom& atom) { return _chosen == &atom; }
 181
 182         // Returns true if the two atoms should be reported as a duplicate symbol
 183         bool reportDuplicate()  { return _reportDuplicate; }
 184
 185 private:
 186         const ld::Atom& _atomA;
 187         const ld::Atom& _atomB;
 188         const Options& _options;
 189         const ld::Atom* _chosen;
 190         bool _reportDuplicate;
 191         bool _ignoreDuplicates;
 192
 193         void pickAtom(const ld::Atom& atom) { _chosen = &atom; } // primitive to set which atom is picked
 194         void pickAtomA() { pickAtom(_atomA); }  // primitive to pick atom A
 195         void pickAtomB() { pickAtom(_atomB); }  // primitive to pick atom B
 196
 197         // use atom A if pickA, otherwise use atom B
 198         void pickAOrB(bool pickA) { if (pickA) pickAtomA(); else pickAtomB(); }
 199
 200         void pickHigherOrdinal() {
 201                 pickAOrB(_atomA.file()->ordinal() < _atomB.file()->ordinal());
 202         }
 203
 204         void pickLowerOrdinal() {
 205                 pickAOrB(_atomA.file()->ordinal() > _atomB.file()->ordinal());
 206         }
 207
 208         void pickLargerSize() {
 209                 if (_atomA.size() == _atomB.size())
 210                         pickLowerOrdinal();
 211                 else
 212                         pickAOrB(_atomA.size() > _atomB.size());
 213         }
 214
 215         void pickGreaterAlignment() {
 216                 pickAOrB(_atomA.alignment().trailingZeros() > _atomB.alignment().trailingZeros());
 217         }
 218
 219         void pickBetweenRegularAtoms() {
 220                 if ( _atomA.combine() == ld::Atom::combineByName ) {
 221                         if ( _atomB.combine() == ld::Atom::combineByName ) {
 222                                 // <rdar://problem/9183821> always choose mach-o over llvm bit code, otherwise LTO may eliminate the llvm atom
 223                                 const bool aIsLTO = (_atomA.contentType() == ld::Atom::typeLTOtemporary);
 224                                 const bool bIsLTO = (_atomB.contentType() == ld::Atom::typeLTOtemporary);
 225                                 // <rdar://problem/9183821> always choose mach-o over llvm bit code, otherwise LTO may eliminate the llvm atom
 226                                 if ( aIsLTO != bIsLTO ) {
 227                                         pickAOrB(!aIsLTO);
 228                                 }
 229                                 else {
 230                                         // both weak, prefer non-auto-hide one
 231                                         if ( _atomA.autoHide() != _atomB.autoHide() ) {
 232                                                 // <rdar://problem/6783167> support auto hidden weak symbols: .weak_def_can_be_hidden
 233                                                 pickAOrB(!_atomA.autoHide());
 234                                         }
 235                                         else if ( _atomA.autoHide() && _atomB.autoHide() ) {
 236                                                 // both have auto-hide, so use one with greater alignment
 237                                                 pickGreaterAlignment();
 238                                         }
 239                                         else {
 240                                                 // neither auto-hide, check visibility
 241                                                 if ( _atomA.scope() != _atomB.scope() ) {
 242                                                         // <rdar://problem/8304984> use more visible weak def symbol
 243                                                         pickAOrB(_atomA.scope() == ld::Atom::scopeGlobal);
 244                                                 }
 245                                                 else {
 246                                                         // both have same visibility, use one with greater alignment
 247                                                         pickGreaterAlignment();
 248                                                 }
 249                                         }
 250                                 }
 251                         }
 252                         else {
 253                                 pickAtomB(); // pick not-weak
 254
 255                         }
 256                 }
 257                 else {
 258                         if ( _atomB.combine() == ld::Atom::combineByName ) {
 259                                 pickAtomA(); // pick not-weak
 260
 261                         }
 262                         else {
 263                                 // both are not-weak
 264                                 if ( _atomA.section().type() == ld::Section::typeMachHeader ) {
 265                                         pickAtomA();
 266                                 }
 267                                 else if ( _atomB.section().type() == ld::Section::typeMachHeader ) {
 268                                         pickAtomB();
 269                                 }
 270                                 else {
 271                                         if ( _ignoreDuplicates ) {
 272                                                 pickLowerOrdinal();
 273                                         }
 274                                         else {
 275                                                 _reportDuplicate = true;
 276                                         }
 277                                 }
 278                         }
 279                 }
 280         }
 281
 282         void pickCommonsMode(const ld::Atom& dylib, const ld::Atom& proxy) {
 283                 assert(dylib.definition() == ld::Atom::definitionTentative);
 284                 assert(proxy.definition() == ld::Atom::definitionProxy);
 285                 switch ( _options.commonsMode() ) {
 286                         case Options::kCommonsIgnoreDylibs:
 287                                 if ( _options.warnCommons() )
 288                                         warning("using common symbol %s from %s and ignoring defintion from dylib %s",
 289                                                         proxy.name(), proxy.file()->path(), dylib.file()->path());
 290                                 pickAtom(dylib);
 291                                 break;
 292                         case Options::kCommonsOverriddenByDylibs:
 293                                 if ( _options.warnCommons() )
 294                                         warning("replacing common symbol %s from %s with true definition from dylib %s",
 295                                                         proxy.name(), proxy.file()->path(), dylib.file()->path());
 296                                 pickAtom(proxy);
 297                                 break;
 298                         case Options::kCommonsConflictsDylibsError:
 299                                 throwf("common symbol %s from %s conflicts with defintion from dylib %s",
 300                                            proxy.name(), proxy.file()->path(), dylib.file()->path());
 301                 }
 302         }
 303
 304         void pickProxyAtom() {
 305                 // both atoms are definitionProxy
 306                 // <rdar://problem/5137732> ld should keep looking when it finds a weak definition in a dylib
 307                 if ( _atomA.combine() == ld::Atom::combineByName ) {
 308                         pickAtomB();
 309                 } else if ( _atomB.combine() == ld::Atom::combineByName ) {
 310                         pickAtomA();
 311                 } else {
 312                                 throwf("symbol %s exported from both %s and %s\n", _atomA.name(), _atomA.file()->path(), _atomB.file()->path());
 313                 }
 314         }
 315
 316         void pickAtom() {
 317                 // First, discriminate by definition
 318                 switch (_atomA.definition()) {
 319                         case ld::Atom::definitionRegular:
 320                                 switch (_atomB.definition()) {
 321                                         case ld::Atom::definitionRegular:
 322                                                 pickBetweenRegularAtoms();
 323                                                 break;
 324                                         case ld::Atom::definitionTentative:
 325                                                 pickAtomA();
 326                                                 break;
 327                                         case ld::Atom::definitionAbsolute:
 328                                                 _reportDuplicate = true;
 329                                                 pickHigherOrdinal();
 330                                                 break;
 331                                         case ld::Atom::definitionProxy:
 332                                                 pickAtomA();
 333                                                 break;
 334                                 }
 335                                 break;
 336                         case ld::Atom::definitionTentative:
 337                                 switch (_atomB.definition()) {
 338                                         case ld::Atom::definitionRegular:
 339                                                 pickAtomB();
 340                                                 break;
 341                                         case ld::Atom::definitionTentative:
 342                                                 pickLargerSize();
 343                                                 break;
 344                                         case ld::Atom::definitionAbsolute:
 345                                                 pickHigherOrdinal();
 346                                                 break;
 347                                         case ld::Atom::definitionProxy:
 348                                                 pickCommonsMode(_atomA, _atomB);
 349                                                 break;
 350                                 }
 351                                 break;
 352                         case ld::Atom::definitionAbsolute:
 353                                 switch (_atomB.definition()) {
 354                                         case ld::Atom::definitionRegular:
 355                                                 _reportDuplicate = true;
 356                                                 pickHigherOrdinal();
 357                                                 break;
 358                                         case ld::Atom::definitionTentative:
 359                                                 pickAtomA();
 360                                                 break;
 361                                         case ld::Atom::definitionAbsolute:
 362                                                 _reportDuplicate = true;
 363                                                 pickHigherOrdinal();
 364                                                 break;
 365                                         case ld::Atom::definitionProxy:
 366                                                 pickAtomA();
 367                                                 break;
 368                                 }
 369                                 break;
 370                         case ld::Atom::definitionProxy:
 371                                 switch (_atomB.definition()) {
 372                                         case ld::Atom::definitionRegular:
 373                                                 pickAtomB();
 374                                                 break;
 375                                         case ld::Atom::definitionTentative:
 376                                                 pickCommonsMode(_atomB, _atomA);
 377                                                 break;
 378                                         case ld::Atom::definitionAbsolute:
 379                                                 pickAtomB();
 380                                                 break;
 381                                         case ld::Atom::definitionProxy:
 382                                                 pickProxyAtom();
 383                                                 break;
 384                                 }
 385                                 break;
 386                 }
 387         }
 388 };
 389
 390 bool SymbolTable::addByName(const ld::Atom& newAtom, bool ignoreDuplicates)
 391 {
 392         bool useNew = true;
 393         assert(newAtom.name() != NULL);
 394         const char* name = newAtom.name();
 395         IndirectBindingSlot slot = this->findSlotForName(name);
 396         const ld::Atom* existingAtom = _indirectBindingTable[slot];
 397         //fprintf(stderr, "addByName(%p) name=%s, slot=%u, existing=%p\n", &newAtom, newAtom.name(), slot, existingAtom);
 398         if ( existingAtom != NULL ) {
 399                 assert(&newAtom != existingAtom);
 400                 NameCollisionResolution picker(newAtom, *existingAtom, ignoreDuplicates, _options);
 401                 if (picker.reportDuplicate()) {
 402                         addDuplicateSymbol(name, existingAtom);
 403                         addDuplicateSymbol(name, &newAtom);
 404                 }
 405                 useNew = picker.choseAtom(newAtom);
 406         }
 407         if ( useNew ) {
 408                 _indirectBindingTable[slot] = &newAtom;
 409                 if ( existingAtom != NULL ) {
 410                         markCoalescedAway(existingAtom);
 411                 }
 412                 if ( newAtom.scope() == ld::Atom::scopeGlobal ) {
 413                         if ( newAtom.definition() == ld::Atom::definitionTentative ) {
 414                                 _hasExternalTentativeDefinitions = true;
 415                         }
 416                 }
 417         }
 418         else {
 419                 markCoalescedAway(&newAtom);
 420         }
 421         // return if existing atom in symbol table was replaced
 422         return useNew && (existingAtom != NULL);
 423 }
 424
 425
 426 bool SymbolTable::addByContent(const ld::Atom& newAtom)
 427 {
 428         bool useNew = true;
 429         const ld::Atom* existingAtom;
 430         IndirectBindingSlot slot = this->findSlotForContent(&newAtom, &existingAtom);
 431         //fprintf(stderr, "addByContent(%p) name=%s, slot=%u, existing=%p\n", &newAtom, newAtom.name(), slot, existingAtom);
 432         if ( existingAtom != NULL ) {
 433                 // use existing unless new one has greater alignment requirements
 434                 useNew = ( newAtom.alignment().trailingZeros() > existingAtom->alignment().trailingZeros() );
 435         }
 436         if ( useNew ) {
 437                 _indirectBindingTable[slot] = &newAtom;
 438                 if ( existingAtom != NULL )
 439                         markCoalescedAway(existingAtom);
 440         }
 441         else {
 442                 _indirectBindingTable[slot] = existingAtom;
 443                 if ( existingAtom != &newAtom )
 444                         markCoalescedAway(&newAtom);
 445         }
 446         // return if existing atom in symbol table was replaced
 447         return useNew && (existingAtom != NULL);
 448 }
 449
 450 bool SymbolTable::addByReferences(const ld::Atom& newAtom)
 451 {
 452         bool useNew = true;
 453         const ld::Atom* existingAtom;
 454         IndirectBindingSlot slot = this->findSlotForReferences(&newAtom, &existingAtom);
 455         //fprintf(stderr, "addByReferences(%p) name=%s, slot=%u, existing=%p\n", &newAtom, newAtom.name(), slot, existingAtom);
 456         if ( existingAtom != NULL ) {
 457                 // use existing unless new one has greater alignment requirements
 458                 useNew = ( newAtom.alignment().trailingZeros() > existingAtom->alignment().trailingZeros() );
 459         }
 460         if ( useNew ) {
 461                 _indirectBindingTable[slot] = &newAtom;
 462                 if ( existingAtom != NULL )
 463                         markCoalescedAway(existingAtom);
 464         }
 465         else {
 466                 if ( existingAtom != &newAtom )
 467                         markCoalescedAway(&newAtom);
 468         }
 469         // return if existing atom in symbol table was replaced
 470         return useNew && (existingAtom != NULL);
 471 }
 472
 473
 474 bool SymbolTable::add(const ld::Atom& atom, bool ignoreDuplicates)
 475 {
 476         //fprintf(stderr, "SymbolTable::add(%p), name=%s\n", &atom, atom.name());
 477         assert(atom.scope() != ld::Atom::scopeTranslationUnit);
 478         switch ( atom.combine() ) {
 479                 case ld::Atom::combineNever:
 480                 case ld::Atom::combineByName:
 481                         return this->addByName(atom, ignoreDuplicates);
 482                         break;
 483                 case ld::Atom::combineByNameAndContent:
 484                         return this->addByContent(atom);
 485                         break;
 486                 case ld::Atom::combineByNameAndReferences:
 487                         return this->addByReferences(atom);
 488                         break;
 489         }
 490
 491         return false;
 492 }
 493
 494 void SymbolTable::markCoalescedAway(const ld::Atom* atom)
 495 {
 496         // remove this from list of all atoms used
 497         //fprintf(stderr, "markCoalescedAway(%p) from %s\n", atom, atom->file()->path());
 498         (const_cast<ld::Atom*>(atom))->setCoalescedAway();
 499
 500         //
 501         // The fixupNoneGroupSubordinate* fixup kind is used to model group comdat.
 502         // The "signature" atom in the group has a fixupNoneGroupSubordinate* fixup to
 503         // all other members of the group.  So, if the signature atom is
 504         // coalesced away, all other atoms in the group should also be removed.
 505         //
 506         for (ld::Fixup::iterator fit=atom->fixupsBegin(), fend=atom->fixupsEnd(); fit != fend; ++fit) {
 507                 switch ( fit->kind ) {
 508                         case ld::Fixup::kindNoneGroupSubordinate:
 509                         case ld::Fixup::kindNoneGroupSubordinateFDE:
 510                         case ld::Fixup::kindNoneGroupSubordinateLSDA:
 511                                 assert(fit->binding == ld::Fixup::bindingDirectlyBound);
 512                                 this->markCoalescedAway(fit->u.target);
 513                                 break;
 514                         default:
 515                                 break;
 516                 }
 517         }
 518
 519 }
 520
 521
 522 struct StrcmpSorter {
 523                 bool operator() (const char* i,const char* j) {
 524                         if (i==NULL)
 525                                 return true;
 526                         if (j==NULL)
 527                                 return false;
 528                         return strcmp(i, j)<0;}
 529 };
 530
 531 void SymbolTable::undefines(std::vector<const char*>& undefs)
 532 {
 533         // return all names in _byNameTable that have no associated atom
 534         for (NameToSlot::iterator it=_byNameTable.begin(); it != _byNameTable.end(); ++it) {
 535                 //fprintf(stderr, "  _byNameTable[%s] = slot %d which has atom %p\n", it->first, it->second, _indirectBindingTable[it->second]);
 536                 if ( _indirectBindingTable[it->second] == NULL )
 537                         undefs.push_back(it->first);
 538         }
 539         // sort so that undefines are in a stable order (not dependent on hashing functions)
 540         struct StrcmpSorter strcmpSorter;
 541         std::sort(undefs.begin(), undefs.end(), strcmpSorter);
 542 }
 543
 544
 545 void SymbolTable::tentativeDefs(std::vector<const char*>& tents)
 546 {
 547         // return all names in _byNameTable that have no associated atom
 548         for (NameToSlot::iterator it=_byNameTable.begin(); it != _byNameTable.end(); ++it) {
 549                 const char* name = it->first;
 550                 const ld::Atom* atom = _indirectBindingTable[it->second];
 551                 if ( (atom != NULL) && (atom->definition() == ld::Atom::definitionTentative) )
 552                         tents.push_back(name);
 553         }
 554         std::sort(tents.begin(), tents.end());
 555 }
 556
 557
 558 bool SymbolTable::hasName(const char* name)
 559 {
 560         NameToSlot::iterator pos = _byNameTable.find(name);
 561         if ( pos == _byNameTable.end() )
 562                 return false;
 563         return (_indirectBindingTable[pos->second] != NULL);
 564 }
 565
 566 // find existing or create new slot
 567 SymbolTable::IndirectBindingSlot SymbolTable::findSlotForName(const char* name)
 568 {
 569         NameToSlot::iterator pos = _byNameTable.find(name);
 570         if ( pos != _byNameTable.end() )
 571                 return pos->second;
 572         // create new slot for this name
 573         SymbolTable::IndirectBindingSlot slot = _indirectBindingTable.size();
 574         _indirectBindingTable.push_back(NULL);
 575         _byNameTable[name] = slot;
 576         _byNameReverseTable[slot] = name;
 577         return slot;
 578 }
 579
 580
 581 // find existing or create new slot
 582 SymbolTable::IndirectBindingSlot SymbolTable::findSlotForContent(const ld::Atom* atom, const ld::Atom** existingAtom)
 583 {
 584         //fprintf(stderr, "findSlotForContent(%p)\n", atom);
 585         SymbolTable::IndirectBindingSlot slot = 0;
 586         UTF16StringToSlot::iterator upos;
 587         CStringToSlot::iterator cspos;
 588         ContentToSlot::iterator pos;
 589         switch ( atom->section().type() ) {
 590                 case ld::Section::typeCString:
 591                         cspos = _cstringTable.find(atom);
 592                         if ( cspos != _cstringTable.end() ) {
 593                                 *existingAtom = _indirectBindingTable[cspos->second];
 594                                 return cspos->second;
 595                         }
 596                         slot = _indirectBindingTable.size();
 597                         _cstringTable[atom] = slot;
 598                         break;
 599                 case ld::Section::typeNonStdCString:
 600                         {
 601                                 // use seg/sect name is key to map to avoid coalescing across segments and sections
 602                                 char segsect[64];
 603                                 sprintf(segsect, "%s/%s", atom->section().segmentName(), atom->section().sectionName());
 604                                 NameToMap::iterator mpos = _nonStdCStringSectionToMap.find(segsect);
 605                                 CStringToSlot* map = NULL;
 606                                 if ( mpos == _nonStdCStringSectionToMap.end() ) {
 607                                         map = new CStringToSlot();
 608                                         _nonStdCStringSectionToMap[strdup(segsect)] = map;
 609                                 }
 610                                 else {
 611                                         map = mpos->second;
 612                                 }
 613                                 cspos = map->find(atom);
 614                                 if ( cspos != map->end() ) {
 615                                         *existingAtom = _indirectBindingTable[cspos->second];
 616                                         return cspos->second;
 617                                 }
 618                                 slot = _indirectBindingTable.size();
 619                                 map->operator[](atom) = slot;
 620                         }
 621                         break;
 622                 case ld::Section::typeUTF16Strings:
 623                         upos = _utf16Table.find(atom);
 624                         if ( upos != _utf16Table.end() ) {
 625                                 *existingAtom = _indirectBindingTable[upos->second];
 626                                 return upos->second;
 627                         }
 628                         slot = _indirectBindingTable.size();
 629                         _utf16Table[atom] = slot;
 630                         break;
 631                 case ld::Section::typeLiteral4:
 632                         pos = _literal4Table.find(atom);
 633                         if ( pos != _literal4Table.end() ) {
 634                                 *existingAtom = _indirectBindingTable[pos->second];
 635                                 return pos->second;
 636                         }
 637                         slot = _indirectBindingTable.size();
 638                         _literal4Table[atom] = slot;
 639                         break;
 640                 case ld::Section::typeLiteral8:
 641                         pos = _literal8Table.find(atom);
 642                         if ( pos != _literal8Table.end() ) {
 643                                 *existingAtom = _indirectBindingTable[pos->second];
 644                                 return pos->second;
 645                         }
 646                         slot = _indirectBindingTable.size();
 647                         _literal8Table[atom] = slot;
 648                         break;
 649                 case ld::Section::typeLiteral16:
 650                         pos = _literal16Table.find(atom);
 651                         if ( pos != _literal16Table.end() ) {
 652                                 *existingAtom = _indirectBindingTable[pos->second];
 653                                 return pos->second;
 654                         }
 655                         slot = _indirectBindingTable.size();
 656                         _literal16Table[atom] = slot;
 657                         break;
 658                 default:
 659                         assert(0 && "section type does not support coalescing by content");
 660         }
 661         _indirectBindingTable.push_back(atom);
 662         *existingAtom = NULL;
 663         return slot;
 664 }
 665
 666
 667
 668 // find existing or create new slot
 669 SymbolTable::IndirectBindingSlot SymbolTable::findSlotForReferences(const ld::Atom* atom, const ld::Atom** existingAtom)
 670 {
 671         //fprintf(stderr, "findSlotForReferences(%p)\n", atom);
 672
 673         SymbolTable::IndirectBindingSlot slot = 0;
 674         ReferencesToSlot::iterator pos;
 675         switch ( atom->section().type() ) {
 676                 case ld::Section::typeNonLazyPointer:
 677                         pos = _nonLazyPointerTable.find(atom);
 678                         if ( pos != _nonLazyPointerTable.end() ) {
 679                                 *existingAtom = _indirectBindingTable[pos->second];
 680                                 return pos->second;
 681                         }
 682                         slot = _indirectBindingTable.size();
 683                         _nonLazyPointerTable[atom] = slot;
 684                         break;
 685                 case ld::Section::typeCFString:
 686                         pos = _cfStringTable.find(atom);
 687                         if ( pos != _cfStringTable.end() ) {
 688                                 *existingAtom = _indirectBindingTable[pos->second];
 689                                 return pos->second;
 690                         }
 691                         slot = _indirectBindingTable.size();
 692                         _cfStringTable[atom] = slot;
 693                         break;
 694                 case ld::Section::typeObjCClassRefs:
 695                         pos = _objc2ClassRefTable.find(atom);
 696                         if ( pos != _objc2ClassRefTable.end() ) {
 697                                 *existingAtom = _indirectBindingTable[pos->second];
 698                                 return pos->second;
 699                         }
 700                         slot = _indirectBindingTable.size();
 701                         _objc2ClassRefTable[atom] = slot;
 702                         break;
 703                 case ld::Section::typeCStringPointer:
 704                         pos = _pointerToCStringTable.find(atom);
 705                         if ( pos != _pointerToCStringTable.end() ) {
 706                                 *existingAtom = _indirectBindingTable[pos->second];
 707                                 return pos->second;
 708                         }
 709                         slot = _indirectBindingTable.size();
 710                         _pointerToCStringTable[atom] = slot;
 711                         break;
 712                 default:
 713                         assert(0 && "section type does not support coalescing by references");
 714         }
 715         _indirectBindingTable.push_back(atom);
 716         *existingAtom = NULL;
 717         return slot;
 718 }
 719
 720
 721 const char*     SymbolTable::indirectName(IndirectBindingSlot slot) const
 722 {
 723         assert(slot < _indirectBindingTable.size());
 724         const ld::Atom* target = _indirectBindingTable[slot];
 725         if ( target != NULL )  {
 726                 return target->name();
 727         }
 728         // handle case when by-name reference is indirected and no atom yet in _byNameTable
 729         SlotToName::const_iterator pos = _byNameReverseTable.find(slot);
 730         if ( pos != _byNameReverseTable.end() )
 731                 return pos->second;
 732         assert(0);
 733         return NULL;
 734 }
 735
 736 const ld::Atom* SymbolTable::indirectAtom(IndirectBindingSlot slot) const
 737 {
 738         assert(slot < _indirectBindingTable.size());
 739         return _indirectBindingTable[slot];
 740 }
 741
 742 void SymbolTable::printStatistics()
 743 {
 744 //      fprintf(stderr, "cstring table size: %lu, bucket count: %lu, hash func called %u times\n",
 745 //                              _cstringTable.size(), _cstringTable.bucket_count(), cstringHashCount);
 746         int count[11];
 747         for(unsigned int b=0; b < 11; ++b) {
 748                 count[b] = 0;
 749         }
 750         for(unsigned int i=0; i < _cstringTable.bucket_count(); ++i) {
 751                 unsigned int n = _cstringTable.elems_in_bucket(i);
 752                 if ( n < 10 )
 753                         count[n] += 1;
 754                 else
 755                         count[10] += 1;
 756         }
 757         fprintf(stderr, "cstring table distribution\n");
 758         for(unsigned int b=0; b < 11; ++b) {
 759                 fprintf(stderr, "%u buckets have %u elements\n", count[b], b);
 760         }
 761         fprintf(stderr, "indirect table size: %lu\n", _indirectBindingTable.size());
 762         fprintf(stderr, "by-name table size: %lu\n", _byNameTable.size());
 763 //      fprintf(stderr, "by-content table size: %lu, hash count: %u, equals count: %u, lookup count: %u\n",
 764 //                                              _byContentTable.size(), contentHashCount, contentEqualCount, contentLookupCount);
 765 //      fprintf(stderr, "by-ref table size: %lu, hashed count: %u, equals count: %u, lookup count: %u, insert count: %u\n",
 766 //                                              _byReferencesTable.size(), refHashCount, refEqualsCount, refLookupCount, refInsertCount);
 767
 768         //ReferencesHash obj;
 769         //for(ReferencesHashToSlot::iterator it=_byReferencesTable.begin(); it != _byReferencesTable.end(); ++it) {
 770         //      if ( obj.operator()(it->first) == 0x2F3AC0EAC744EA70 ) {
 771         //              fprintf(stderr, "hash=0x2F3AC0EAC744EA70 for %p %s from %s\n", it->first, it->first->name(), it->first->file()->path());
 772         //
 773         //      }
 774         //}
 775
 776 }
 777
 778 } // namespace tool
 779 } // namespace ld
 780