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