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 <string>
  38 #include <map>
  39 #include <set>
  40 #include <vector>
  41 #include <algorithm>
  42 #include <ext/hash_map>
  43 #include <ext/hash_set>
  44
  45 #include "Options.h"
  46
  47 #include "ld.hpp"
  48 #include "InputFiles.h"
  49 #include "SymbolTable.h"
  50
  51
  52
  53 namespace ld {
  54 namespace tool {
  55
  56
  57 // HACK, I can't find a way to pass values in the compare classes (e.g. ContentFuncs)
  58 // so use global variable to pass info.
  59 static ld::IndirectBindingTable*        _s_indirectBindingTable = NULL;
  60 bool                                                                            SymbolTable::_s_doDemangle = false;
  61
  62
  63 SymbolTable::SymbolTable(const Options& opts, std::vector<const ld::Atom*>& ibt)
  64         : _options(opts), _cstringTable(6151), _indirectBindingTable(ibt), _hasExternalTentativeDefinitions(false)
  65 {
  66         _s_indirectBindingTable = this;
  67         _s_doDemangle = _options.demangleSymbols();
  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
 123 bool SymbolTable::addByName(const ld::Atom& newAtom, bool ignoreDuplicates)
 124 {
 125         bool useNew = true;
 126         bool checkVisibilityMismatch = false;
 127         assert(newAtom.name() != NULL);
 128         const char* name = newAtom.name();
 129         IndirectBindingSlot slot = this->findSlotForName(name);
 130         const ld::Atom* existingAtom = _indirectBindingTable[slot];
 131         //fprintf(stderr, "addByName(%p) name=%s, slot=%u, existing=%p\n", &newAtom, newAtom.name(), slot, existingAtom);
 132         if ( existingAtom != NULL ) {
 133                 assert(&newAtom != existingAtom);
 134                 switch ( existingAtom->definition() ) {
 135                         case ld::Atom::definitionRegular:
 136                                 switch ( newAtom.definition() ) {
 137                                         case ld::Atom::definitionRegular:
 138                                                 if ( existingAtom->combine() == ld::Atom::combineByName ) {
 139                                                         if ( newAtom.combine() == ld::Atom::combineByName ) {
 140                                                                 // <rdar://problem/9183821> always choose mach-o over llvm bit code, otherwise LTO may eliminate the llvm atom
 141                                                                 const bool existingIsLTO = (existingAtom->contentType() == ld::Atom::typeLTOtemporary);
 142                                                                 const bool newIsLTO = (newAtom.contentType() == ld::Atom::typeLTOtemporary);
 143                                                                 if ( existingIsLTO != newIsLTO ) {
 144                                                                         useNew = existingIsLTO;
 145                                                                 }
 146                                                                 else {
 147                                                                         // both weak, prefer non-auto-hide one
 148                                                                         if ( newAtom.autoHide() != existingAtom->autoHide() ) {
 149                                                                                 // <rdar://problem/6783167> support auto hidden weak symbols: .weak_def_can_be_hidden
 150                                                                                 useNew = existingAtom->autoHide();
 151                                                                                 // don't check for visibility mismatch
 152                                                                         }
 153                                                                         else if ( newAtom.autoHide() && existingAtom->autoHide() ) {
 154                                                                                 // both have auto-hide, so use one with greater alignment
 155                                                                                 useNew = ( newAtom.alignment().trailingZeros() > existingAtom->alignment().trailingZeros() );
 156                                                                         }
 157                                                                         else {
 158                                                                                 // neither auto-hide, check visibility
 159                                                                                 if ( newAtom.scope() != existingAtom->scope() ) {
 160                                                                                         // <rdar://problem/8304984> use more visible weak def symbol
 161                                                                                         useNew = (newAtom.scope() == ld::Atom::scopeGlobal);
 162                                                                                 }
 163                                                                                 else {
 164                                                                                         // both have same visibility, use one with greater alignment
 165                                                                                         useNew = ( newAtom.alignment().trailingZeros() > existingAtom->alignment().trailingZeros() );
 166                                                                                 }
 167                                                                         }
 168                                                                 }
 169                                                         }
 170                                                         else {
 171                                                                 // existing weak, new is not-weak
 172                                                                 useNew = true;
 173                                                         }
 174                                                 }
 175                                                 else {
 176                                                         if ( newAtom.combine() == ld::Atom::combineByName ) {
 177                                                                 // existing not-weak, new is weak
 178                                                                 useNew = false;
 179                                                         }
 180                                                         else {
 181                                                                 // existing not-weak, new is not-weak
 182                                                                 if ( newAtom.section().type() == ld::Section::typeMachHeader ) {
 183                                                                         warning("ignoring override of built-in symbol %s from %s", newAtom.name(), existingAtom->file()->path());
 184                                                                         useNew = true;
 185                                                                 }
 186                                                                 else if ( existingAtom->section().type() == ld::Section::typeMachHeader ) {
 187                                                                         warning("ignoring override of built-in symbol %s from %s", newAtom.name(), newAtom.file()->path());
 188                                                                         useNew = false;
 189                                                                 }
 190                                                                 else {
 191                                                                         if ( ignoreDuplicates ) {
 192                                                                                 useNew = false;
 193                                                                                 static bool fullWarning = false;
 194                                                                                 if ( ! fullWarning ) {
 195                                                                                         warning("-dead_strip with lazy loaded static (library) archives "
 196                                                                                                         "has resulted in a duplicate symbol.  You can change your "
 197                                                                                                         "source code to rename symbols to avoid the collision.  "
 198                                                                                                         "This will be an error in a future linker.");
 199                                                                                         fullWarning = true;
 200                                                                                 }
 201                                                                                 warning("duplicate symbol %s originally in %s now lazily loaded from %s",
 202                                                                                                 SymbolTable::demangle(name), existingAtom->file()->path(), newAtom.file()->path());
 203                                                                         }
 204                                                                         else {
 205                                                                                 throwf("duplicate symbol %s in %s and %s",
 206                                                                                                 SymbolTable::demangle(name), newAtom.file()->path(), existingAtom->file()->path());
 207                                                                         }
 208                                                                 }
 209                                                         }
 210                                                 }
 211                                                 break;
 212                                         case ld::Atom::definitionTentative:
 213                                                 // ignore new tentative atom, because we already have a regular one
 214                                                 useNew = false;
 215                                                 checkVisibilityMismatch = true;
 216                                                 if ( newAtom.size() > existingAtom->size() ) {
 217                                                         warning("for symbol %s tentative definition of size %llu from %s is "
 218                                                                                         "is smaller than the real definition of size %llu from %s",
 219                                                                                         newAtom.name(), newAtom.size(), newAtom.file()->path(),
 220                                                                                         existingAtom->size(), existingAtom->file()->path());
 221                                                 }
 222                                                 break;
 223                                         case ld::Atom::definitionAbsolute:
 224                                                 throwf("duplicate symbol %s in %s and %s", name, newAtom.file()->path(), existingAtom->file()->path());
 225                                         case ld::Atom::definitionProxy:
 226                                                 // ignore external atom, because we already have a one
 227                                                 useNew = false;
 228                                                 break;
 229                                 }
 230                                 break;
 231                         case ld::Atom::definitionTentative:
 232                                 switch ( newAtom.definition() ) {
 233                                         case ld::Atom::definitionRegular:
 234                                                 // replace existing tentative atom with regular one
 235                                                 if ( newAtom.section().type() == ld::Section::typeMachHeader ) {
 236                                                         // silently replace tentative __dso_handle with real linker created symbol
 237                                                         useNew = true;
 238                                                 }
 239                                                 else if ( existingAtom->section().type() == ld::Section::typeMachHeader ) {
 240                                                         // silently replace tentative __dso_handle with real linker created symbol
 241                                                         useNew = false;
 242                                                 }
 243                                                 else {
 244                                                         checkVisibilityMismatch = true;
 245                                                         if ( newAtom.size() < existingAtom->size() ) {
 246                                                                 warning("for symbol %s tentative definition of size %llu from %s is "
 247                                                                                                 "being replaced by a real definition of size %llu from %s",
 248                                                                                                 newAtom.name(), existingAtom->size(), existingAtom->file()->path(),
 249                                                                                                 newAtom.size(), newAtom.file()->path());
 250                                                         }
 251                                                         if ( newAtom.section().type() == ld::Section::typeCode ) {
 252                                                                 warning("for symbol %s tentative (data) defintion from %s is "
 253                                                                                 "being replaced by code from %s", newAtom.name(), existingAtom->file()->path(),
 254                                                                                 newAtom.file()->path());
 255                                                         }
 256                                                 }
 257                                                 break;
 258                                         case ld::Atom::definitionTentative:
 259                                                 // new and existing are both tentative definitions, use largest
 260                                                 checkVisibilityMismatch = true;
 261                                                 if ( newAtom.size() < existingAtom->size() ) {
 262                                                         useNew = false;
 263                                                 }
 264                                                 else {
 265                                                         if ( newAtom.alignment().trailingZeros() < existingAtom->alignment().trailingZeros() )
 266                                                                 warning("alignment lost in merging tentative definition %s", newAtom.name());
 267                                                 }
 268                                                 break;
 269                                         case ld::Atom::definitionAbsolute:
 270                                                 // replace tentative with absolute
 271                                                 useNew = true;
 272                                                 break;
 273                                         case ld::Atom::definitionProxy:
 274                                                 // a tentative definition and a dylib definition, so commons-mode decides how to handle
 275                                                 switch ( _options.commonsMode() ) {
 276                                                         case Options::kCommonsIgnoreDylibs:
 277                                                                 if ( _options.warnCommons() )
 278                                                                         warning("using common symbol %s from %s and ignoring defintion from dylib %s",
 279                                                                                         existingAtom->name(), existingAtom->file()->path(), newAtom.file()->path());
 280                                                                 useNew = false;
 281                                                                 break;
 282                                                         case Options::kCommonsOverriddenByDylibs:
 283                                                                 if ( _options.warnCommons() )
 284                                                                         warning("replacing common symbol %s from %s with true definition from dylib %s",
 285                                                                                         existingAtom->name(), existingAtom->file()->path(), newAtom.file()->path());
 286                                                                 break;
 287                                                         case Options::kCommonsConflictsDylibsError:
 288                                                                 throwf("common symbol %s from %s conflicts with defintion from dylib %s",
 289                                                                                 existingAtom->name(), existingAtom->file()->path(), newAtom.file()->path());
 290                                                 }
 291                                                 break;
 292                                 }
 293                                 break;
 294                         case ld::Atom::definitionAbsolute:
 295                                 switch ( newAtom.definition() ) {
 296                                         case ld::Atom::definitionRegular:
 297                                                 throwf("duplicate symbol %s in %s and %s", name, newAtom.file()->path(), existingAtom->file()->path());
 298                                         case ld::Atom::definitionTentative:
 299                                                 // ignore new tentative atom, because we already have a regular one
 300                                                 useNew = false;
 301                                                 break;
 302                                         case ld::Atom::definitionAbsolute:
 303                                                 throwf("duplicate symbol %s in %s and %s", name, newAtom.file()->path(), existingAtom->file()->path());
 304                                         case ld::Atom::definitionProxy:
 305                                                 // ignore external atom, because we already have a one
 306                                                 useNew = false;
 307                                                 break;
 308                                 }
 309                                 break;
 310                         case ld::Atom::definitionProxy:
 311                                 switch ( newAtom.definition() ) {
 312                                         case ld::Atom::definitionRegular:
 313                                                 // replace external atom with regular one
 314                                                 useNew = true;
 315                                                 break;
 316                                         case ld::Atom::definitionTentative:
 317                                                 // a tentative definition and a dylib definition, so commons-mode decides how to handle
 318                                                 switch ( _options.commonsMode() ) {
 319                                                         case Options::kCommonsIgnoreDylibs:
 320                                                                 if ( _options.warnCommons() )
 321                                                                         warning("using common symbol %s from %s and ignoring defintion from dylib %s",
 322                                                                                         newAtom.name(), newAtom.file()->path(), existingAtom->file()->path());
 323                                                                 break;
 324                                                         case Options::kCommonsOverriddenByDylibs:
 325                                                                 if ( _options.warnCommons() )
 326                                                                         warning("replacing defintion of %s from dylib %s with common symbol from %s",
 327                                                                                         newAtom.name(), existingAtom->file()->path(), newAtom.file()->path());
 328                                                                 useNew = false;
 329                                                                 break;
 330                                                         case Options::kCommonsConflictsDylibsError:
 331                                                                 throwf("common symbol %s from %s conflicts with defintion from dylib %s",
 332                                                                                         newAtom.name(), newAtom.file()->path(), existingAtom->file()->path());
 333                                                 }
 334                                                 break;
 335                                         case ld::Atom::definitionAbsolute:
 336                                                 // replace external atom with absolute one
 337                                                 useNew = true;
 338                                                 break;
 339                                         case ld::Atom::definitionProxy:
 340                                                 // <rdar://problem/5137732> ld should keep looking when it finds a weak definition in a dylib
 341                                                 if ( newAtom.combine() == ld::Atom::combineByName ) {
 342                                                         useNew = false;
 343                                                 }
 344                                                 else {
 345                                                         if ( existingAtom->combine() == ld::Atom::combineByName )
 346                                                                 useNew = true;
 347                                                         else
 348                                                                 throwf("symbol %s exported from both %s and %s\n", name, newAtom.file()->path(), existingAtom->file()->path());
 349                                                 }
 350                                                 break;
 351                                 }
 352                                 break;
 353                 }
 354         }
 355         if ( (existingAtom != NULL) && checkVisibilityMismatch && (newAtom.scope() != existingAtom->scope()) ) {
 356                 warning("%s has different visibility (%s) in %s and (%s) in %s",
 357                         SymbolTable::demangle(newAtom.name()), (newAtom.scope() == 1 ? "hidden" : "default"), newAtom.file()->path(), (existingAtom->scope()  == 1 ? "hidden" : "default"), existingAtom->file()->path());
 358         }
 359         if ( useNew ) {
 360                 _indirectBindingTable[slot] = &newAtom;
 361                 if ( existingAtom != NULL ) {
 362                         markCoalescedAway(existingAtom);
 363 //                      if ( fOwner.fInitialLoadsDone ) {
 364 //                              //fprintf(stderr, "existing %p %s overridden by %p\n", existingAtom, existingAtom->name(), &newAtom);
 365 //                              fOwner.fAtomsOverriddenByLateLoads.insert(existingAtom);
 366 //                      }
 367                 }
 368                 if ( newAtom.scope() == ld::Atom::scopeGlobal ) {
 369                         if ( newAtom.definition() == ld::Atom::definitionTentative ) {
 370                                 _hasExternalTentativeDefinitions = true;
 371                         }
 372                 }
 373         }
 374         else {
 375                 markCoalescedAway(&newAtom);
 376         }
 377         // return if existing atom in symbol table was replaced
 378         return useNew && (existingAtom != NULL);
 379 }
 380
 381
 382 bool SymbolTable::addByContent(const ld::Atom& newAtom)
 383 {
 384         bool useNew = true;
 385         const ld::Atom* existingAtom;
 386         IndirectBindingSlot slot = this->findSlotForContent(&newAtom, &existingAtom);
 387         //fprintf(stderr, "addByContent(%p) name=%s, slot=%u, existing=%p\n", &newAtom, newAtom.name(), slot, existingAtom);
 388         if ( existingAtom != NULL ) {
 389                 // use existing unless new one has greater alignment requirements
 390                 useNew = ( newAtom.alignment().trailingZeros() > existingAtom->alignment().trailingZeros() );
 391         }
 392         if ( useNew ) {
 393                 _indirectBindingTable[slot] = &newAtom;
 394                 if ( existingAtom != NULL )
 395                         markCoalescedAway(existingAtom);
 396         }
 397         else {
 398                 _indirectBindingTable[slot] = existingAtom;
 399                 if ( existingAtom != &newAtom )
 400                         markCoalescedAway(&newAtom);
 401         }
 402         // return if existing atom in symbol table was replaced
 403         return useNew && (existingAtom != NULL);
 404 }
 405
 406 bool SymbolTable::addByReferences(const ld::Atom& newAtom)
 407 {
 408         bool useNew = true;
 409         const ld::Atom* existingAtom;
 410         IndirectBindingSlot slot = this->findSlotForReferences(&newAtom, &existingAtom);
 411         //fprintf(stderr, "addByReferences(%p) name=%s, slot=%u, existing=%p\n", &newAtom, newAtom.name(), slot, existingAtom);
 412         if ( existingAtom != NULL ) {
 413                 // use existing unless new one has greater alignment requirements
 414                 useNew = ( newAtom.alignment().trailingZeros() > existingAtom->alignment().trailingZeros() );
 415         }
 416         if ( useNew ) {
 417                 _indirectBindingTable[slot] = &newAtom;
 418                 if ( existingAtom != NULL )
 419                         markCoalescedAway(existingAtom);
 420         }
 421         else {
 422                 if ( existingAtom != &newAtom )
 423                         markCoalescedAway(&newAtom);
 424         }
 425         // return if existing atom in symbol table was replaced
 426         return useNew && (existingAtom != NULL);
 427 }
 428
 429
 430 bool SymbolTable::add(const ld::Atom& atom, bool ignoreDuplicates)
 431 {
 432         //fprintf(stderr, "SymbolTable::add(%p), name=%s\n", &atom, atom.name());
 433         assert(atom.scope() != ld::Atom::scopeTranslationUnit);
 434         switch ( atom.combine() ) {
 435                 case ld::Atom::combineNever:
 436                 case ld::Atom::combineByName:
 437                         return this->addByName(atom, ignoreDuplicates);
 438                         break;
 439                 case ld::Atom::combineByNameAndContent:
 440                         return this->addByContent(atom);
 441                         break;
 442                 case ld::Atom::combineByNameAndReferences:
 443                         return this->addByReferences(atom);
 444                         break;
 445         }
 446
 447         return false;
 448 }
 449
 450 void SymbolTable::markCoalescedAway(const ld::Atom* atom)
 451 {
 452         // remove this from list of all atoms used
 453         //fprintf(stderr, "markCoalescedAway(%p) from %s\n", atom, atom->file()->path());
 454         (const_cast<ld::Atom*>(atom))->setCoalescedAway();
 455
 456         //
 457         // The fixupNoneGroupSubordinate* fixup kind is used to model group comdat.
 458         // The "signature" atom in the group has a fixupNoneGroupSubordinate* fixup to
 459         // all other members of the group.  So, if the signature atom is
 460         // coalesced away, all other atoms in the group should also be removed.
 461         //
 462         for (ld::Fixup::iterator fit=atom->fixupsBegin(), fend=atom->fixupsEnd(); fit != fend; ++fit) {
 463                 switch ( fit->kind ) {
 464                         case ld::Fixup::kindNoneGroupSubordinate:
 465                         case ld::Fixup::kindNoneGroupSubordinateFDE:
 466                         case ld::Fixup::kindNoneGroupSubordinateLSDA:
 467                                 assert(fit->binding == ld::Fixup::bindingDirectlyBound);
 468                                 this->markCoalescedAway(fit->u.target);
 469                                 break;
 470                         default:
 471                                 break;
 472                 }
 473         }
 474
 475 }
 476
 477 void SymbolTable::undefines(std::vector<const char*>& undefs)
 478 {
 479         // return all names in _byNameTable that have no associated atom
 480         for (NameToSlot::iterator it=_byNameTable.begin(); it != _byNameTable.end(); ++it) {
 481                 //fprintf(stderr, "  _byNameTable[%s] = slot %d which has atom %p\n", it->first, it->second, _indirectBindingTable[it->second]);
 482                 if ( _indirectBindingTable[it->second] == NULL )
 483                         undefs.push_back(it->first);
 484         }
 485         // sort so that undefines are in a stable order (not dependent on hashing functions)
 486         std::sort(undefs.begin(), undefs.end());
 487 }
 488
 489
 490 void SymbolTable::tentativeDefs(std::vector<const char*>& tents)
 491 {
 492         // return all names in _byNameTable that have no associated atom
 493         for (NameToSlot::iterator it=_byNameTable.begin(); it != _byNameTable.end(); ++it) {
 494                 const char* name = it->first;
 495                 const ld::Atom* atom = _indirectBindingTable[it->second];
 496                 if ( (atom != NULL) && (atom->definition() == ld::Atom::definitionTentative) )
 497                         tents.push_back(name);
 498         }
 499         std::sort(tents.begin(), tents.end());
 500 }
 501
 502
 503 bool SymbolTable::hasName(const char* name)
 504 {
 505         NameToSlot::iterator pos = _byNameTable.find(name);
 506         if ( pos == _byNameTable.end() )
 507                 return false;
 508         return (_indirectBindingTable[pos->second] != NULL);
 509 }
 510
 511 // find existing or create new slot
 512 SymbolTable::IndirectBindingSlot SymbolTable::findSlotForName(const char* name)
 513 {
 514         NameToSlot::iterator pos = _byNameTable.find(name);
 515         if ( pos != _byNameTable.end() )
 516                 return pos->second;
 517         // create new slot for this name
 518         SymbolTable::IndirectBindingSlot slot = _indirectBindingTable.size();
 519         _indirectBindingTable.push_back(NULL);
 520         _byNameTable[name] = slot;
 521         _byNameReverseTable[slot] = name;
 522         return slot;
 523 }
 524
 525
 526 // find existing or create new slot
 527 SymbolTable::IndirectBindingSlot SymbolTable::findSlotForContent(const ld::Atom* atom, const ld::Atom** existingAtom)
 528 {
 529         //fprintf(stderr, "findSlotForContent(%p)\n", atom);
 530         SymbolTable::IndirectBindingSlot slot = 0;
 531         UTF16StringToSlot::iterator upos;
 532         CStringToSlot::iterator cspos;
 533         ContentToSlot::iterator pos;
 534         switch ( atom->section().type() ) {
 535                 case ld::Section::typeCString:
 536                         cspos = _cstringTable.find(atom);
 537                         if ( cspos != _cstringTable.end() ) {
 538                                 *existingAtom = _indirectBindingTable[cspos->second];
 539                                 return cspos->second;
 540                         }
 541                         slot = _indirectBindingTable.size();
 542                         _cstringTable[atom] = slot;
 543                         break;
 544                 case ld::Section::typeNonStdCString:
 545                         {
 546                                 // use seg/sect name is key to map to avoid coalescing across segments and sections
 547                                 char segsect[64];
 548                                 sprintf(segsect, "%s/%s", atom->section().segmentName(), atom->section().sectionName());
 549                                 NameToMap::iterator mpos = _nonStdCStringSectionToMap.find(segsect);
 550                                 CStringToSlot* map = NULL;
 551                                 if ( mpos == _nonStdCStringSectionToMap.end() ) {
 552                                         map = new CStringToSlot();
 553                                         _nonStdCStringSectionToMap[strdup(segsect)] = map;
 554                                 }
 555                                 else {
 556                                         map = mpos->second;
 557                                 }
 558                                 cspos = map->find(atom);
 559                                 if ( cspos != map->end() ) {
 560                                         *existingAtom = _indirectBindingTable[cspos->second];
 561                                         return cspos->second;
 562                                 }
 563                                 slot = _indirectBindingTable.size();
 564                                 map->operator[](atom) = slot;
 565                         }
 566                         break;
 567                 case ld::Section::typeUTF16Strings:
 568                         upos = _utf16Table.find(atom);
 569                         if ( upos != _utf16Table.end() ) {
 570                                 *existingAtom = _indirectBindingTable[upos->second];
 571                                 return upos->second;
 572                         }
 573                         slot = _indirectBindingTable.size();
 574                         _utf16Table[atom] = slot;
 575                         break;
 576                 case ld::Section::typeLiteral4:
 577                         pos = _literal4Table.find(atom);
 578                         if ( pos != _literal4Table.end() ) {
 579                                 *existingAtom = _indirectBindingTable[pos->second];
 580                                 return pos->second;
 581                         }
 582                         slot = _indirectBindingTable.size();
 583                         _literal4Table[atom] = slot;
 584                         break;
 585                 case ld::Section::typeLiteral8:
 586                         pos = _literal8Table.find(atom);
 587                         if ( pos != _literal8Table.end() ) {
 588                                 *existingAtom = _indirectBindingTable[pos->second];
 589                                 return pos->second;
 590                         }
 591                         slot = _indirectBindingTable.size();
 592                         _literal8Table[atom] = slot;
 593                         break;
 594                 case ld::Section::typeLiteral16:
 595                         pos = _literal16Table.find(atom);
 596                         if ( pos != _literal16Table.end() ) {
 597                                 *existingAtom = _indirectBindingTable[pos->second];
 598                                 return pos->second;
 599                         }
 600                         slot = _indirectBindingTable.size();
 601                         _literal16Table[atom] = slot;
 602                         break;
 603                 default:
 604                         assert(0 && "section type does not support coalescing by content");
 605         }
 606         _indirectBindingTable.push_back(atom);
 607         *existingAtom = NULL;
 608         return slot;
 609 }
 610
 611
 612
 613 // find existing or create new slot
 614 SymbolTable::IndirectBindingSlot SymbolTable::findSlotForReferences(const ld::Atom* atom, const ld::Atom** existingAtom)
 615 {
 616         //fprintf(stderr, "findSlotForReferences(%p)\n", atom);
 617
 618         SymbolTable::IndirectBindingSlot slot = 0;
 619         ReferencesToSlot::iterator pos;
 620         switch ( atom->section().type() ) {
 621                 case ld::Section::typeNonLazyPointer:
 622                         pos = _nonLazyPointerTable.find(atom);
 623                         if ( pos != _nonLazyPointerTable.end() ) {
 624                                 *existingAtom = _indirectBindingTable[pos->second];
 625                                 return pos->second;
 626                         }
 627                         slot = _indirectBindingTable.size();
 628                         _nonLazyPointerTable[atom] = slot;
 629                         break;
 630                 case ld::Section::typeCFString:
 631                         pos = _cfStringTable.find(atom);
 632                         if ( pos != _cfStringTable.end() ) {
 633                                 *existingAtom = _indirectBindingTable[pos->second];
 634                                 return pos->second;
 635                         }
 636                         slot = _indirectBindingTable.size();
 637                         _cfStringTable[atom] = slot;
 638                         break;
 639                 case ld::Section::typeObjCClassRefs:
 640                         pos = _objc2ClassRefTable.find(atom);
 641                         if ( pos != _objc2ClassRefTable.end() ) {
 642                                 *existingAtom = _indirectBindingTable[pos->second];
 643                                 return pos->second;
 644                         }
 645                         slot = _indirectBindingTable.size();
 646                         _objc2ClassRefTable[atom] = slot;
 647                         break;
 648                 case ld::Section::typeCStringPointer:
 649                         pos = _pointerToCStringTable.find(atom);
 650                         if ( pos != _pointerToCStringTable.end() ) {
 651                                 *existingAtom = _indirectBindingTable[pos->second];
 652                                 return pos->second;
 653                         }
 654                         slot = _indirectBindingTable.size();
 655                         _pointerToCStringTable[atom] = slot;
 656                         break;
 657                 default:
 658                         assert(0 && "section type does not support coalescing by references");
 659         }
 660         _indirectBindingTable.push_back(atom);
 661         *existingAtom = NULL;
 662         return slot;
 663 }
 664
 665
 666 const char*     SymbolTable::indirectName(IndirectBindingSlot slot) const
 667 {
 668         assert(slot < _indirectBindingTable.size());
 669         const ld::Atom* target = _indirectBindingTable[slot];
 670         if ( target != NULL )  {
 671                 return target->name();
 672         }
 673         // handle case when by-name reference is indirected and no atom yet in _byNameTable
 674         SlotToName::const_iterator pos = _byNameReverseTable.find(slot);
 675         if ( pos != _byNameReverseTable.end() )
 676                 return pos->second;
 677         assert(0);
 678         return NULL;
 679 }
 680
 681 const ld::Atom* SymbolTable::indirectAtom(IndirectBindingSlot slot) const
 682 {
 683         assert(slot < _indirectBindingTable.size());
 684         return _indirectBindingTable[slot];
 685 }
 686
 687 extern "C" char* __cxa_demangle (const char* mangled_name,
 688                                    char* buf,
 689                                    size_t* n,
 690                                    int* status);
 691
 692 const char* SymbolTable::demangle(const char* sym)
 693 {
 694         // only try to demangle symbols if -demangle on command line
 695         if ( !_s_doDemangle )
 696                 return sym;
 697
 698         // only try to demangle symbols that look like C++ symbols
 699         if ( strncmp(sym, "__Z", 3) != 0 )
 700                 return sym;
 701
 702         static size_t size = 1024;
 703         static char* buff = (char*)malloc(size);
 704         int status;
 705
 706         char* result = __cxa_demangle(&sym[1], buff, &size, &status);
 707         if ( result != NULL ) {
 708                 // if demangling succesful, keep buffer for next demangle
 709                 buff = result;
 710                 return buff;
 711         }
 712         return sym;
 713 }
 714
 715
 716 void SymbolTable::printStatistics()
 717 {
 718 //      fprintf(stderr, "cstring table size: %lu, bucket count: %lu, hash func called %u times\n",
 719 //                              _cstringTable.size(), _cstringTable.bucket_count(), cstringHashCount);
 720         int count[11];
 721         for(unsigned int b=0; b < 11; ++b) {
 722                 count[b] = 0;
 723         }
 724         for(unsigned int i=0; i < _cstringTable.bucket_count(); ++i) {
 725                 unsigned int n = _cstringTable.elems_in_bucket(i);
 726                 if ( n < 10 )
 727                         count[n] += 1;
 728                 else
 729                         count[10] += 1;
 730         }
 731         fprintf(stderr, "cstring table distribution\n");
 732         for(unsigned int b=0; b < 11; ++b) {
 733                 fprintf(stderr, "%u buckets have %u elements\n", count[b], b);
 734         }
 735         fprintf(stderr, "indirect table size: %lu\n", _indirectBindingTable.size());
 736         fprintf(stderr, "by-name table size: %lu\n", _byNameTable.size());
 737 //      fprintf(stderr, "by-content table size: %lu, hash count: %u, equals count: %u, lookup count: %u\n",
 738 //                                              _byContentTable.size(), contentHashCount, contentEqualCount, contentLookupCount);
 739 //      fprintf(stderr, "by-ref table size: %lu, hashed count: %u, equals count: %u, lookup count: %u, insert count: %u\n",
 740 //                                              _byReferencesTable.size(), refHashCount, refEqualsCount, refLookupCount, refInsertCount);
 741
 742         //ReferencesHash obj;
 743         //for(ReferencesHashToSlot::iterator it=_byReferencesTable.begin(); it != _byReferencesTable.end(); ++it) {
 744         //      if ( obj.operator()(it->first) == 0x2F3AC0EAC744EA70 ) {
 745         //              fprintf(stderr, "hash=0x2F3AC0EAC744EA70 for %p %s from %s\n", it->first, it->first->name(), it->first->file()->path());
 746         //
 747         //      }
 748         //}
 749
 750 }
 751
 752 } // namespace tool
 753 } // namespace ld
 754