src/ld/passes/code_dedup.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2015 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 <stdint.h>
  27 #include <math.h>
  28 #include <unistd.h>
  29 #include <dlfcn.h>
  30 #include <mach/machine.h>
  31
  32 #include <vector>
  33 #include <map>
  34 #include <algorithm>
  35 #include <unordered_map>
  36
  37 #include "ld.hpp"
  38 #include "code_dedup.h"
  39
  40 namespace ld {
  41 namespace passes {
  42 namespace dedup {
  43
  44
  45
  46 class DeDupAliasAtom : public ld::Atom
  47 {
  48 public:
  49                                                                                 DeDupAliasAtom(const ld::Atom* dupOf, const ld::Atom* replacement) :
  50                                                                                         ld::Atom(dupOf->section(), ld::Atom::definitionRegular, ld::Atom::combineNever,
  51                                                                                                         dupOf->scope(), dupOf->contentType(), ld::Atom::symbolTableIn,
  52                                                                                                         false, false, true, 0),
  53                                                                                         _dedupOf(dupOf),
  54                                                                                         _fixup(0, ld::Fixup::k1of1, ld::Fixup::kindNoneFollowOn, ld::Fixup::bindingDirectlyBound, replacement) {
  55                                                 if ( dupOf->autoHide() )
  56                                                     setAutoHide();
  57                                             }
  58
  59         virtual const ld::File*                         file() const            { return _dedupOf->file(); }
  60         virtual const char*                                     translationUnitSource() const
  61                                                                                                                         { return NULL; }
  62         virtual const char*                                     name() const            { return _dedupOf->name(); }
  63         virtual uint64_t                                        size() const            { return 0; }
  64         virtual uint64_t                                        objectAddress() const { return 0; }
  65         virtual void                                            copyRawContent(uint8_t buffer[]) const { }
  66         virtual ld::Fixup::iterator                     fixupsBegin() const     { return &((ld::Fixup*)&_fixup)[0]; }
  67         virtual ld::Fixup::iterator                     fixupsEnd()     const   { return &((ld::Fixup*)&_fixup)[1]; }
  68
  69 private:
  70         const ld::Atom*                     _dedupOf;
  71         ld::Fixup                                                       _fixup;
  72 };
  73
  74
  75 namespace {
  76     typedef std::unordered_map<const ld::Atom*, unsigned long> CachedHashes;
  77
  78     ld::Internal*   sState = nullptr;
  79     CachedHashes    sSavedHashes;
  80     unsigned long   sHashCount = 0;
  81     unsigned long   sFixupCompareCount = 0;
  82 };
  83
  84
  85 // A helper for std::unordered_map<> that hashes the instructions of a function
  86 struct atom_hashing {
  87
  88     static unsigned long hash(const ld::Atom* atom) {
  89         auto pos = sSavedHashes.find(atom);
  90         if ( pos != sSavedHashes.end() )
  91             return pos->second;
  92
  93         const unsigned instructionBytes = atom->size();
  94         const uint8_t*  instructions = atom->rawContentPointer();
  95         unsigned long hash = instructionBytes;
  96         for (unsigned i=0; i < instructionBytes; ++i) {
  97             hash = (hash * 33) + instructions[i];
  98         }
  99                 for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
 100             const Atom* target = NULL;
 101             switch ( fit->binding ) {
 102                 case ld::Fixup::bindingDirectlyBound:
 103                     target = fit->u.target;
 104                     break;
 105                 case ld::Fixup::bindingsIndirectlyBound:
 106                     target = sState->indirectBindingTable[fit->u.bindingIndex];
 107                     break;
 108                 default:
 109                     break;
 110             }
 111             // don't include calls to auto-hide functions in hash because they might be de-dup'ed
 112             switch ( fit->kind ) {
 113 #if SUPPORT_ARCH_arm64
 114                 case ld::Fixup::kindStoreTargetAddressARM64Branch26:
 115 #endif
 116                 case ld::Fixup::kindStoreTargetAddressX86BranchPCRel32:
 117                     if ( target && target->autoHide() )
 118                         continue; // don't include
 119                     break;
 120                 default:
 121                     break;
 122             }
 123             if ( target != NULL ) {
 124                 const char* name = target->name();
 125                 if ( target->contentType() == ld::Atom::typeCString )
 126                     name = (const char*)target->rawContentPointer();
 127                 for (const char* s = name; *s != '\0'; ++s)
 128                     hash = (hash * 33) + *s;
 129             }
 130         }
 131         ++sHashCount;
 132         sSavedHashes[atom] = hash;
 133         return hash;
 134     }
 135
 136     unsigned long operator()(const ld::Atom* atom) const {
 137         return hash(atom);
 138     }
 139 };
 140
 141
 142 // A helper for std::unordered_map<> that compares functions
 143 struct atom_equal {
 144
 145     struct VisitedSet {
 146         std::unordered_set<const ld::Atom*> atoms1;
 147         std::unordered_set<const ld::Atom*> atoms2;
 148     };
 149
 150     static bool sameFixups(const ld::Atom* atom1, const ld::Atom* atom2, VisitedSet& visited) {
 151         ++sFixupCompareCount;
 152         //fprintf(stderr, "sameFixups(%s,%s)\n", atom1->name(), atom2->name());
 153         Fixup::iterator f1   = atom1->fixupsBegin();
 154         Fixup::iterator end1 = atom1->fixupsEnd();
 155         Fixup::iterator f2   = atom2->fixupsBegin();
 156         Fixup::iterator end2 = atom2->fixupsEnd();
 157         // two atoms must have same number of fixups
 158         if ( (end1 - f1) != (end2 - f2) )
 159             return false;
 160         // if no fixups, fixups are equal
 161         if ( f1 == end1 )
 162             return true;
 163         // all fixups must be the same
 164         do {
 165             if ( f1->offsetInAtom != f2->offsetInAtom )
 166                 return false;
 167             if ( f1->kind != f2->kind )
 168                 return false;
 169             if ( f1->clusterSize != f2->clusterSize )
 170                 return false;
 171             if ( f1->binding != f2->binding )
 172                 return false;
 173             const Atom* target1 = NULL;
 174             const Atom* target2 = NULL;
 175             switch ( f1->binding ) {
 176                 case ld::Fixup::bindingDirectlyBound:
 177                     target1 = f1->u.target;
 178                     target2 = f2->u.target;
 179                     break;
 180                 case ld::Fixup::bindingsIndirectlyBound:
 181                     target1 = sState->indirectBindingTable[f1->u.bindingIndex];
 182                     target2 = sState->indirectBindingTable[f2->u.bindingIndex];
 183                     break;
 184                  case ld::Fixup::bindingNone:
 185                     break;
 186                default:
 187                     return false;
 188             }
 189             if ( target1 != target2 ) {
 190                 // targets must match unless they are both calls to functions that will de-dup together
 191     #if SUPPORT_ARCH_arm64
 192                 if ( (f1->kind != ld::Fixup::kindStoreTargetAddressARM64Branch26) && (f1->kind != ld::Fixup::kindStoreTargetAddressX86BranchPCRel32) )
 193     #else
 194                 if ( f1->kind != ld::Fixup::kindStoreTargetAddressX86BranchPCRel32 )
 195     #endif
 196                     return false;
 197                 if ( target1->section().type() != target2->section().type() )
 198                     return false;
 199                 if ( target1->section().type() != ld::Section::typeCode )
 200                     return false;
 201                 // to support co-recursive functions, don't call equals() on targets we've already visited
 202                 if ( ((visited.atoms1.count(target1) == 0) || (visited.atoms2.count(target2) == 0)) && !equal(target1, target2, visited) )
 203                     return false;
 204               }
 205
 206             ++f1;
 207             ++f2;
 208         } while (f1 != end1);
 209
 210         return true;
 211     }
 212
 213     static bool equal(const ld::Atom* atom1, const ld::Atom* atom2, VisitedSet& visited) {
 214         if ( atom_hashing::hash(atom1) != atom_hashing::hash(atom2) )
 215             return false;
 216         visited.atoms1.insert(atom1);
 217         visited.atoms2.insert(atom2);
 218         return sameFixups(atom1, atom2, visited);
 219     }
 220
 221     bool operator()(const ld::Atom* atom1, const ld::Atom* atom2) const {
 222         VisitedSet visited;
 223         return equal(atom1, atom2, visited);
 224     }
 225 };
 226
 227
 228
 229 void doPass(const Options& opts, ld::Internal& state)
 230 {
 231         const bool log = false;
 232
 233         // only de-duplicate in final linked images
 234         if ( opts.outputKind() == Options::kObjectFile )
 235                 return;
 236
 237         // only de-duplicate for architectures that use relocations that don't store bits in instructions
 238         if ( (opts.architecture() != CPU_TYPE_ARM64) && (opts.architecture() != CPU_TYPE_X86_64) )
 239                 return;
 240
 241     // support -no_deduplicate to suppress this pass
 242     if ( ! opts.deduplicateFunctions() )
 243         return;
 244
 245     const bool verbose = opts.verboseDeduplicate();
 246
 247     // find __text section
 248     ld::Internal::FinalSection* textSection = NULL;
 249     for (ld::Internal::FinalSection* sect : state.sections) {
 250         if ( (sect->type() == ld::Section::typeCode) && (strcmp(sect->sectionName(), "__text") == 0) ) {
 251             textSection = sect;
 252             break;
 253         }
 254     }
 255     if ( textSection == NULL )
 256         return;
 257
 258     // build map of auto-hide functions and their duplicates
 259     // the key for the map is always the first element in the value vector
 260     // the key is always earlier in the atoms list then matching other atoms
 261     sState = &state;
 262     std::unordered_map<const ld::Atom*, std::vector<const ld::Atom*>, atom_hashing, atom_equal> map;
 263     std::unordered_set<const ld::Atom*> masterAtoms;
 264     for (const ld::Atom* atom : textSection->atoms) {
 265         // ignore empty (alias) atoms
 266         if ( atom->size() == 0 )
 267             continue;
 268         if ( atom->autoHide() )
 269             map[atom].push_back(atom);
 270         }
 271
 272     if ( log ) {
 273         for (auto& entry : map) {
 274             if ( entry.second.size() > 1 ) {
 275                 printf("Found following matching functions:\n");
 276                 for (const ld::Atom* atom : entry.second) {
 277                     printf("  %p %s\n", atom, atom->name());
 278                 }
 279             }
 280         }
 281         fprintf(stderr, "duplicate sets count:\n");
 282         for (auto& entry : map)
 283             fprintf(stderr, "  %p -> %lu\n", entry.first, entry.second.size());
 284     }
 285
 286     // construct alias atoms to replace atoms found to be duplicates
 287     unsigned atomsBeingComparedCount = 0;
 288     uint64_t dedupSavings = 0;
 289     std::vector<const ld::Atom*>& textAtoms = textSection->atoms;
 290     std::unordered_map<const ld::Atom*, const ld::Atom*> replacementMap;
 291     for (auto& entry : map) {
 292         const ld::Atom* masterAtom = entry.first;
 293         std::vector<const ld::Atom*>& dups = entry.second;
 294         atomsBeingComparedCount += dups.size();
 295         if ( dups.size() == 1 )
 296             continue;
 297         if ( verbose )  {
 298             dedupSavings += ((dups.size() - 1) * masterAtom->size());
 299             fprintf(stderr, "deduplicate the following %lu functions (%llu bytes apiece):\n", dups.size(), masterAtom->size());
 300         }
 301         for (const ld::Atom* dupAtom : dups) {
 302             if ( verbose )
 303                 fprintf(stderr, "    %s\n", dupAtom->name());
 304             if ( dupAtom == masterAtom )
 305                 continue;
 306             const ld::Atom* aliasAtom = new DeDupAliasAtom(dupAtom, masterAtom);
 307             auto pos = std::find(textAtoms.begin(), textAtoms.end(), masterAtom);
 308             if ( pos != textAtoms.end() ) {
 309                 textAtoms.insert(pos, aliasAtom);
 310                 state.atomToSection[aliasAtom] = textSection;
 311                 replacementMap[dupAtom] = aliasAtom;
 312             }
 313         }
 314     }
 315     if ( verbose )  {
 316         fprintf(stderr, "deduplication saved %llu bytes of __text\n", dedupSavings);
 317     }
 318
 319     if ( log ) {
 320         fprintf(stderr, "replacement map:\n");
 321         for (auto& entry : replacementMap)
 322             fprintf(stderr, "  %p -> %p\n", entry.first, entry.second);
 323     }
 324
 325     // walk all atoms and replace references to dups with references to alias
 326     for (ld::Internal::FinalSection* sect : state.sections) {
 327         for (const ld::Atom* atom : sect->atoms) {
 328                         for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
 329                 std::unordered_map<const ld::Atom*, const ld::Atom*>::iterator pos;
 330                 switch ( fit->binding ) {
 331                     case ld::Fixup::bindingsIndirectlyBound:
 332                         pos = replacementMap.find(state.indirectBindingTable[fit->u.bindingIndex]);
 333                         if ( pos != replacementMap.end() )
 334                             state.indirectBindingTable[fit->u.bindingIndex] = pos->second;
 335                         break;
 336                     case ld::Fixup::bindingDirectlyBound:
 337                         pos = replacementMap.find(fit->u.target);
 338                         if ( pos != replacementMap.end() )
 339                             fit->u.target = pos->second;
 340                         break;
 341                     default:
 342                         break;
 343                 }
 344                         }
 345         }
 346     }
 347
 348     if ( log ) {
 349         fprintf(stderr, "atoms before pruning:\n");
 350         for (const ld::Atom* atom : textSection->atoms)
 351             fprintf(stderr, "  %p (size=%llu) %sp\n", atom, atom->size(), atom->name());
 352     }
 353     // remove replaced atoms from section
 354         textSection->atoms.erase(std::remove_if(textSection->atoms.begin(), textSection->atoms.end(),
 355                 [&](const ld::Atom* atom) {
 356                     return (replacementMap.count(atom) != 0);
 357                 }),
 358                 textSection->atoms.end());
 359
 360    for (auto& entry : replacementMap)
 361         state.atomToSection.erase(entry.first);
 362
 363     if ( log ) {
 364         fprintf(stderr, "atoms after pruning:\n");
 365         for (const ld::Atom* atom : textSection->atoms)
 366             fprintf(stderr, "  %p (size=%llu) %sp\n", atom, atom->size(), atom->name());
 367     }
 368
 369    //fprintf(stderr, "hash-count=%lu, fixup-compares=%lu, atom-count=%u\n", sHashCount, sFixupCompareCount, atomsBeingComparedCount);
 370 }
 371
 372
 373 } // namespace dedup
 374 } // namespace passes
 375 } // namespace ld