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