dyld3/shared-cache/ObjC2Abstraction.hpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2008-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 #include <iterator>
  26 #include <deque>
  27 #include <set>
  28
  29
  30 // iterate an entsize-based list
  31 // typedef entsize_iterator<P, type_t<P>, type_list_t<P> > type_iterator;
  32 template <typename P, typename T, typename Tlist>
  33 struct entsize_iterator {
  34     uint32_t entsize;
  35     uint32_t index;  // keeping track of this saves a divide in operator-
  36     T* current;
  37
  38     typedef std::random_access_iterator_tag iterator_category;
  39     typedef T value_type;
  40     typedef ptrdiff_t difference_type;
  41     typedef T* pointer;
  42     typedef T& reference;
  43
  44     entsize_iterator() { }
  45
  46     entsize_iterator(const Tlist& list, uint32_t start = 0)
  47         : entsize(list.getEntsize()), index(start), current((T*)list.get(start))
  48     { }
  49
  50     const entsize_iterator<P,T,Tlist>& operator += (ptrdiff_t count) {
  51         current = (T*)((uint8_t *)current + count*entsize);
  52         index += count;
  53         return *this;
  54     }
  55     const entsize_iterator<P,T,Tlist>& operator -= (ptrdiff_t count) {
  56         current = (T*)((uint8_t *)current - count*entsize);
  57         index -= count;
  58         return *this;
  59     }
  60     const entsize_iterator<P,T,Tlist> operator + (ptrdiff_t count) const {
  61         return entsize_iterator(*this) += count;
  62     }
  63     const entsize_iterator<P,T,Tlist> operator - (ptrdiff_t count) const {
  64         return entsize_iterator(*this) -= count;
  65     }
  66
  67     entsize_iterator<P,T,Tlist>& operator ++ () { *this += 1; return *this; }
  68     entsize_iterator<P,T,Tlist>& operator -- () { *this -= 1; return *this; }
  69     entsize_iterator<P,T,Tlist> operator ++ (int) {
  70         entsize_iterator<P,T,Tlist> result(*this); *this += 1; return result;
  71     }
  72     entsize_iterator<P,T,Tlist> operator -- (int) {
  73         entsize_iterator<P,T,Tlist> result(*this); *this -= 1; return result;
  74     }
  75
  76     ptrdiff_t operator - (const entsize_iterator<P,T,Tlist>& rhs) const {
  77         return (ptrdiff_t)this->index - (ptrdiff_t)rhs.index;
  78     }
  79
  80     T& operator * () { return *current; }
  81     T& operator * () const { return *current; }
  82     T& operator -> () { return *current; }
  83     const T& operator -> () const { return *current; }
  84
  85     operator T& () const { return *current; }
  86
  87     bool operator == (const entsize_iterator<P,T,Tlist>& rhs) {
  88         return this->current == rhs.current;
  89     }
  90     bool operator != (const entsize_iterator<P,T,Tlist>& rhs) {
  91         return this->current != rhs.current;
  92     }
  93
  94     bool operator < (const entsize_iterator<P,T,Tlist>& rhs) {
  95         return this->current < rhs.current;
  96     }
  97     bool operator > (const entsize_iterator<P,T,Tlist>& rhs) {
  98         return this->current > rhs.current;
  99     }
 100
 101
 102     static void overwrite(entsize_iterator<P,T,Tlist>& dst, const Tlist* srcList)
 103     {
 104         entsize_iterator<P,T,Tlist> src;
 105         uint32_t ee = srcList->getEntsize();
 106         for (src = srcList->begin(); src != srcList->end(); ++src) {
 107             memcpy(&*dst, &*src, ee);
 108             ++dst;
 109         }
 110     }
 111 };
 112
 113 template <typename P>
 114 class objc_header_info_rw_t {
 115
 116     typedef typename P::uint_t pint_t;
 117
 118     pint_t data;   // loaded:1, allRealised:1, objc_header_info *:ptr
 119
 120 public:
 121     objc_header_info_rw_t(ContentAccessor* cache, const macho_header<P>* mh)
 122         : data(0) {
 123     }
 124 };
 125
 126 template <typename P>
 127 class objc_header_info_ro_t {
 128
 129     typedef typename P::uint_t pint_t;
 130
 131     pint_t mhdr_offset;     // offset to mach_header or mach_header_64
 132     pint_t info_offset;     // offset to objc_image_info *
 133
 134 public:
 135     objc_header_info_ro_t(ContentAccessor* cache, const macho_header<P>* mh)
 136         : mhdr_offset(0), info_offset(0) {
 137         P::setP(mhdr_offset, (uint64_t)cache->vmAddrForContent((void*)mh) - (uint64_t)cache->vmAddrForContent(&mhdr_offset));
 138         assert(header_vmaddr(cache) == (uint64_t)cache->vmAddrForContent((void*)mh));
 139         const macho_section<P>* sect = mh->getSection("__DATA", "__objc_imageinfo");
 140         if (sect) {
 141             P::setP(info_offset, (uint64_t)sect->addr() - (uint64_t)cache->vmAddrForContent(&info_offset));
 142             // set bit in mach_header.flags to tell dyld that this image has objc content
 143             macho_header<P>* rwmh = const_cast<macho_header<P>*>(mh);
 144             rwmh->set_flags(mh->flags() | MH_HAS_OBJC);
 145         }
 146         else
 147             P::setP(info_offset, - (uint64_t)cache->vmAddrForContent(&info_offset));
 148     }
 149
 150     pint_t header_vmaddr(ContentAccessor* cache) const {
 151         return (pint_t)(((uint64_t)cache->vmAddrForContent(&mhdr_offset)) + mhdr_offset);
 152     }
 153 };
 154
 155 template <typename P>
 156 class objc_method_list_t {
 157
 158     typedef typename P::uint_t pint_t;
 159
 160     template <typename PtrTy>
 161     class objc_method_small_t {
 162         typedef typename PtrTy::uint_t pint_t;
 163         int32_t name;   // SEL
 164         int32_t types;  // const char *
 165         int32_t imp;    // IMP
 166         friend class objc_method_list_t<PtrTy>;
 167
 168         objc_method_small_t() = delete;
 169         ~objc_method_small_t() = delete;
 170         objc_method_small_t(const objc_method_small_t& other) = delete;
 171         objc_method_small_t(objc_method_small_t&& other) = delete;
 172         objc_method_small_t& operator=(const objc_method_small_t& other) = delete;
 173         objc_method_small_t& operator=(objc_method_small_t&& other) = delete;
 174
 175     public:
 176
 177         pint_t getName(ContentAccessor* cache, bool isOffsetToSel) const {
 178             // We want to return the VM address of the "const char*" our selector
 179             // reference is pointing at.
 180             pint_t* nameRef = (pint_t*)((uint8_t*)&name + name);
 181             if ( isOffsetToSel ) {
 182                 // Offset is directly to the SEL, not a selRef
 183                 return (pint_t)cache->vmAddrForContent(nameRef);
 184             } else {
 185                 return (pint_t)PtrTy::getP(*nameRef);
 186             }
 187         }
 188         // We want to update the selRef we are pointing at with the new content
 189         // We may share the same selRef with other method lists or @SEL expressions, but as
 190         // all of them want the same uniqued selector anyway, its safe to overwrite it here for
 191         // everyone.
 192         void setName(ContentAccessor* cache, pint_t newNameVMAddr, bool isOffsetToSel) {
 193             if ( isOffsetToSel ) {
 194                 // Offset is directly to the SEL, not a selRef
 195                 void* namePtr = cache->contentForVMAddr(newNameVMAddr);
 196                 this->name = (int32_t)(intptr_t)((uint8_t*)namePtr - (uint8_t*)&this->name);
 197             } else {
 198                 pint_t* selRef = (pint_t*)((uint8_t*)&name + name);
 199                 PtrTy::setP(*selRef, newNameVMAddr);
 200             }
 201         }
 202         // Returns the vmAddr of the types
 203         pint_t getTypes(ContentAccessor* cache) const {
 204             pint_t* typesRef = (pint_t*)((uint8_t*)&types + types);
 205             return (pint_t)cache->vmAddrForContent(typesRef);
 206         }
 207         void setTypes(ContentAccessor* cache, pint_t newTypesVMAddr) {
 208             void* typesPtr = cache->contentForVMAddr(newTypesVMAddr);
 209             this->types = (int32_t)(intptr_t)((uint8_t*)typesPtr - (uint8_t*)&this->types);
 210         }
 211         // Returns the vmAddr of the IMP
 212         pint_t getIMP(ContentAccessor* cache) const {
 213             pint_t* impRef = (pint_t*)((uint8_t*)&imp + imp);
 214             return (pint_t)cache->vmAddrForContent(impRef);
 215         }
 216         void setIMP(ContentAccessor* cache, pint_t newIMPVMAddr) {
 217             void* impPtr = cache->contentForVMAddr(newIMPVMAddr);
 218             this->imp = (int32_t)(intptr_t)((uint8_t*)impPtr - (uint8_t*)&this->imp);
 219         }
 220
 221         // Swap the contents of this value and other
 222         // This has to recompute all of the relative offsets
 223         void swap(objc_method_small_t<PtrTy>* other) {
 224             // Get our targets
 225             uint8_t* ourNameTarget  = (uint8_t*)&this->name + this->name;
 226             uint8_t* ourTypesTarget = (uint8_t*)&this->types + this->types;
 227             uint8_t* ourIMPTarget   = (uint8_t*)&this->imp + this->imp;
 228             // Get their targets
 229             uint8_t* theirNameTarget  = (uint8_t*)&other->name + other->name;
 230             uint8_t* theirTypesTarget = (uint8_t*)&other->types + other->types;
 231             uint8_t* theirIMPTarget   = (uint8_t*)&other->imp + other->imp;
 232             // Set our targets
 233             this->name = (int32_t)(intptr_t)(theirNameTarget - (uint8_t*)&this->name);
 234             this->types = (int32_t)(intptr_t)(theirTypesTarget - (uint8_t*)&this->types);
 235             this->imp = (int32_t)(intptr_t)(theirIMPTarget - (uint8_t*)&this->imp);
 236             // Set their targets
 237             other->name = (int32_t)(intptr_t)(ourNameTarget - (uint8_t*)&other->name);
 238             other->types = (int32_t)(intptr_t)(ourTypesTarget - (uint8_t*)&other->types);
 239             other->imp = (int32_t)(intptr_t)(ourIMPTarget - (uint8_t*)&other->imp);
 240         }
 241
 242         struct SortBySELAddress :
 243             public std::binary_function<const objc_method_small_t<PtrTy>&,
 244                                         const objc_method_small_t<PtrTy>&, bool>
 245         {
 246             SortBySELAddress(ContentAccessor* cache, bool isOffsetToSel)
 247                 : cache(cache), isOffsetToSel(isOffsetToSel) { }
 248
 249             bool operator() (const objc_method_small_t<PtrTy>& lhs,
 250                              const objc_method_small_t<PtrTy>& rhs)
 251             {
 252                 return lhs.getName(cache, isOffsetToSel) < rhs.getName(cache, isOffsetToSel);
 253             }
 254
 255             ContentAccessor* cache  = nullptr;
 256             bool isOffsetToSel      = false;
 257         };
 258     };
 259
 260     template <typename PtrTy>
 261     class objc_method_large_t {
 262         typedef typename PtrTy::uint_t pint_t;
 263         pint_t name;   // SEL
 264         pint_t types;  // const char *
 265         pint_t imp;    // IMP
 266         friend class objc_method_list_t<PtrTy>;
 267     public:
 268         pint_t getName() const {
 269             return (pint_t)PtrTy::getP(name);
 270         }
 271         void setName(pint_t newName) {
 272             PtrTy::setP(name, newName);
 273         }
 274         pint_t getTypes() const {
 275             return (pint_t)PtrTy::getP(types);
 276         }
 277         void setTypes(pint_t newTypes) {
 278             PtrTy::setP(types, newTypes);
 279         }
 280         pint_t getIMP() const {
 281             return (pint_t)PtrTy::getP(imp);
 282         }
 283         void setIMP(pint_t newIMP) {
 284             PtrTy::setP(imp, newIMP);
 285         }
 286
 287         struct SortBySELAddress :
 288             public std::binary_function<const objc_method_large_t<PtrTy>&,
 289                                         const objc_method_large_t<PtrTy>&, bool>
 290         {
 291             bool operator() (const objc_method_large_t<PtrTy>& lhs,
 292                              const objc_method_large_t<PtrTy>& rhs)
 293             {
 294                 return lhs.getName() < rhs.getName();
 295             }
 296         };
 297     };
 298
 299     // Temporary struct to use when sorting small methods as their int32_t offsets can't reach
 300     // from the stack where temporary values are placed, in to the shared cache buffer where the data lives
 301     struct TempMethod {
 302         // Relative methods in the shared cache always use direct offsets to the SEL
 303         // at the point where this is running.  That means we don't need to indirect through
 304         // a SEL reference.
 305         pint_t selVMAddr;
 306         pint_t typesVMAddr;
 307         pint_t impVMAddr;
 308     };
 309
 310     template <typename PtrTy>
 311     struct SortBySELAddress :
 312         public std::binary_function<const TempMethod&,
 313                                     const TempMethod&, bool>
 314     {
 315         SortBySELAddress(ContentAccessor* cache) : cache(cache) { }
 316
 317         bool operator() (const TempMethod& lhs,
 318                          const TempMethod& rhs)
 319         {
 320             return lhs.selVMAddr < rhs.selVMAddr;
 321         }
 322
 323         ContentAccessor* cache = nullptr;
 324     };
 325
 326     uint32_t entsize;
 327     uint32_t count;
 328     union {
 329         objc_method_small_t<P> small;
 330         objc_method_large_t<P> large;
 331     } first;
 332
 333     void* operator new (size_t, void* buf) { return buf; }
 334
 335     enum : uint32_t {
 336         // If this is set, the relative method lists name_offset field is an
 337         // offset directly to the SEL, not a SEL ref.
 338         relativeMethodSelectorsAreDirectFlag    = 0x40000000,
 339
 340         // If this is set, then method lists are the new relative format, not
 341         // the old pointer based format
 342         relativeMethodFlag                      = 0x80000000,
 343
 344         // The upper 16-bits are all defined to be flags
 345         methodListFlagsMask                     = 0xFFFF0000
 346     };
 347
 348     uint32_t getFlags() const {
 349         return (P::E::get32(entsize) & methodListFlagsMask);
 350     }
 351
 352     typedef entsize_iterator<P, objc_method_small_t<P>, objc_method_list_t<P> > small_method_iterator;
 353     typedef entsize_iterator<P, objc_method_large_t<P>, objc_method_list_t<P> > large_method_iterator;
 354
 355     small_method_iterator beginSmall() {
 356         assert(usesRelativeMethods());
 357         return small_method_iterator(*this, 0);
 358     }
 359     small_method_iterator endSmall() {
 360         assert(usesRelativeMethods());
 361         return small_method_iterator(*this, getCount());
 362     }
 363
 364     large_method_iterator beginLarge() {
 365         assert(!usesRelativeMethods());
 366         return large_method_iterator(*this, 0);
 367     }
 368     large_method_iterator endLarge() {
 369         assert(!usesRelativeMethods());
 370         return large_method_iterator(*this, getCount());
 371     }
 372
 373 public:
 374
 375     uint32_t getCount() const { return P::E::get32(count); }
 376
 377     uint32_t getEntsize() const {
 378         return P::E::get32(entsize) & ~(uint32_t)3 & ~methodListFlagsMask;
 379     }
 380
 381     uint32_t byteSize() const {
 382         return byteSizeForCount(getCount(), getEntsize());
 383     }
 384
 385     static uint32_t byteSizeForCount(uint32_t c, uint32_t e) {
 386         return sizeof(entsize) + sizeof(count) + c*e;
 387     }
 388
 389     bool usesRelativeMethods() const {
 390         return (P::E::get32(entsize) & relativeMethodFlag) != 0;
 391     }
 392
 393     void setFixedUp() {
 394         P::E::set32(entsize, getEntsize() | 3 | getFlags());
 395     }
 396
 397     void setMethodListSelectorsAreDirect() {
 398         P::E::set32(entsize, getEntsize() | getFlags() | relativeMethodSelectorsAreDirectFlag);
 399     }
 400
 401     void sortMethods(ContentAccessor* cache, pint_t *typelist, bool isOffsetToSel) {
 402         if ( usesRelativeMethods() ) {
 403             // At this point we assume we are using offsets directly to selectors.  This
 404             // is so that the TempMethod struct can also use direct offsets and not track the
 405             // SEL reference VMAddrs
 406             assert(isOffsetToSel);
 407
 408             if ( typelist == nullptr ) {
 409                 // This is the case when we are sorting the methods on a class.
 410                 // Only protocols have a type list which causes the other sort to be used
 411                 // We can't sort the small methods in place as their 32-bit offsets can't reach
 412                 // the VM space where the shared cache is being created.  Instead create a list
 413                 // of large methods and sort those.
 414
 415                 std::vector<TempMethod> largeMethods;
 416                 for (unsigned i = 0 ; i != count; ++i) {
 417                     const objc_method_small_t<P>* smallMethod = (const objc_method_small_t<P>*)get(i);
 418                     TempMethod largeMethod;
 419                     largeMethod.selVMAddr = smallMethod->getName(cache, isOffsetToSel);
 420                     largeMethod.typesVMAddr = smallMethod->getTypes(cache);
 421                     largeMethod.impVMAddr = smallMethod->getIMP(cache);
 422                     largeMethods.push_back(largeMethod);
 423                 }
 424
 425                 SortBySELAddress<P> sorter(cache);
 426                 std::stable_sort(largeMethods.begin(), largeMethods.end(), sorter);
 427
 428                 for (unsigned i = 0 ; i != count; ++i) {
 429                     const TempMethod& largeMethod = largeMethods[i];
 430                     objc_method_small_t<P>* smallMethod = (objc_method_small_t<P>*)get(i);
 431                     smallMethod->setName(cache, largeMethod.selVMAddr, isOffsetToSel);
 432                     smallMethod->setTypes(cache, largeMethod.typesVMAddr);
 433                     smallMethod->setIMP(cache, largeMethod.impVMAddr);
 434                 }
 435
 436 #if 0
 437                 // Check the method lists are sorted
 438                 {
 439                     typename objc_method_small_t<P>::SortBySELAddress sorter(cache);
 440                     for (uint32_t i = 0; i < getCount(); i++) {
 441                         for (uint32_t j = i+1; j < getCount(); j++) {
 442                             objc_method_small_t<P>* mi = (objc_method_small_t<P>*)get(i);
 443                             objc_method_small_t<P>* mj = (objc_method_small_t<P>*)get(j);
 444                             if ( mi->getName(cache) == mj->getName(cache) )
 445                                 continue;
 446                             if (! sorter(*mi, *mj)) {
 447                                 assert(false);
 448                             }
 449                         }
 450                     }
 451                 }
 452 #endif
 453             }
 454             else {
 455                 typename objc_method_small_t<P>::SortBySELAddress sorter(cache, isOffsetToSel);
 456                 // can't easily use std::stable_sort here
 457                 for (uint32_t i = 0; i < getCount(); i++) {
 458                     for (uint32_t j = i+1; j < getCount(); j++) {
 459                         objc_method_small_t<P>* mi = (objc_method_small_t<P>*)get(i);
 460                         objc_method_small_t<P>* mj = (objc_method_small_t<P>*)get(j);
 461                         if (! sorter(*mi, *mj)) {
 462                             mi->swap(mj);
 463                             if (typelist) std::swap(typelist[i], typelist[j]);
 464                         }
 465                     }
 466                 }
 467             }
 468         } else {
 469             typename objc_method_large_t<P>::SortBySELAddress sorter;
 470
 471             if ( typelist == nullptr ) {
 472                 // This is the case when we are sorting the methods on a class.
 473                 // Only protocols have a type list which causes the other sort to be used
 474                 std::stable_sort(beginLarge(), endLarge(), sorter);
 475             }
 476             else {
 477                 // can't easily use std::stable_sort here
 478                 for (uint32_t i = 0; i < getCount(); i++) {
 479                     for (uint32_t j = i+1; j < getCount(); j++) {
 480                         objc_method_large_t<P>* mi = (objc_method_large_t<P>*)get(i);
 481                         objc_method_large_t<P>* mj = (objc_method_large_t<P>*)get(j);
 482                         if (! sorter(*mi, *mj)) {
 483                             std::swap(*mi, *mj);
 484                             if (typelist) std::swap(typelist[i], typelist[j]);
 485                         }
 486                     }
 487                 }
 488             }
 489         }
 490         // mark method list as sorted
 491         this->setFixedUp();
 492     }
 493
 494     pint_t getName(ContentAccessor* cache, uint32_t i, bool isOffsetToSel) {
 495         pint_t name = 0;
 496         if ( usesRelativeMethods() ) {
 497             small_method_iterator it = beginSmall() + i;
 498             objc_method_small_t<P>& method = *it;
 499             name = method.getName(cache, isOffsetToSel);
 500         } else {
 501             large_method_iterator it = beginLarge() + i;
 502             objc_method_large_t<P>& method = *it;
 503             name = method.getName();
 504         }
 505         return name;
 506     }
 507
 508     void setName(ContentAccessor* cache, uint32_t i, pint_t name, bool isOffsetToSel) {
 509         if ( usesRelativeMethods() ) {
 510             small_method_iterator it = beginSmall() + i;
 511             objc_method_small_t<P>& method = *it;
 512             method.setName(cache, name, isOffsetToSel);
 513         } else {
 514             large_method_iterator it = beginLarge() + i;
 515             objc_method_large_t<P>& method = *it;
 516             method.setName(name);
 517         }
 518     }
 519
 520     const char* getStringName(ContentAccessor* cache, uint32_t i, bool isOffsetToSel) {
 521         return (const char*)cache->contentForVMAddr(getName(cache, i, isOffsetToSel));
 522     }
 523
 524     pint_t getImp(uint32_t i, ContentAccessor* cache) {
 525         pint_t name = 0;
 526         if ( usesRelativeMethods() ) {
 527             small_method_iterator it = beginSmall() + i;
 528             objc_method_small_t<P>& method = *it;
 529             name = method.getIMP(cache);
 530         } else {
 531             large_method_iterator it = beginLarge() + i;
 532             objc_method_large_t<P>& method = *it;
 533             name = method.getIMP();
 534         }
 535         return name;
 536     }
 537
 538     void* get(uint32_t i) const {
 539         if ( usesRelativeMethods() ) {
 540             return (void*)(objc_method_small_t<P> *)((uint8_t *)&first + i * getEntsize());
 541         } else {
 542             return (void*)(objc_method_large_t<P> *)((uint8_t *)&first + i * getEntsize());
 543         }
 544     }
 545
 546     void operator delete(void * p) {
 547         ::free(p);
 548     }
 549
 550 private:
 551
 552     // use newMethodList instead
 553     void* operator new (size_t);
 554 };
 555
 556
 557 template <typename P>
 558 class objc_ivar_t {
 559     typedef typename P::uint_t pint_t;
 560
 561     pint_t                    offset;  // uint32_t*  (uint64_t* on x86_64)
 562     pint_t                    name;    // const char*
 563     pint_t                    type;    // const char*
 564     uint32_t                alignment;
 565     uint32_t                size;
 566
 567 public:
 568     const char* getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 569
 570     bool hasOffset() const { return offset != 0; }
 571     uint32_t getOffset(ContentAccessor* cache) const { return P::E::get32(*(uint32_t*)(cache->contentForVMAddr(P::getP(offset)))); }
 572     void setOffset(ContentAccessor* cache, uint32_t newOffset) { P::E::set32(*(uint32_t*)(cache->contentForVMAddr(P::getP(offset))), newOffset); }
 573
 574
 575     uint32_t getAlignment() {
 576         uint32_t a = P::E::get32(alignment);
 577         return (a == (uint32_t)-1) ? sizeof(pint_t) : 1<<a;
 578     }
 579 };
 580
 581 template <typename P>
 582 class objc_ivar_list_t {
 583     typedef typename P::uint_t pint_t;
 584     uint32_t entsize;
 585     uint32_t count;
 586     objc_ivar_t<P> first;
 587
 588     void* operator new (size_t, void* buf) { return buf; }
 589
 590 public:
 591
 592     typedef entsize_iterator<P, objc_ivar_t<P>, objc_ivar_list_t<P> > ivar_iterator;
 593
 594     uint32_t getCount() const { return P::E::get32(count); }
 595
 596     uint32_t getEntsize() const { return P::E::get32(entsize); }
 597
 598     void* get(pint_t i) const { return (void*)(objc_ivar_t<P> *)((uint8_t *)&first + i * P::E::get32(entsize)); }
 599
 600     uint32_t byteSize() const {
 601         return byteSizeForCount(getCount(), getEntsize());
 602     }
 603
 604     static uint32_t byteSizeForCount(uint32_t c, uint32_t e = sizeof(objc_ivar_t<P>)) {
 605         return sizeof(objc_ivar_list_t<P>) - sizeof(objc_ivar_t<P>) + c*e;
 606     }
 607
 608     ivar_iterator begin() { return ivar_iterator(*this, 0); }
 609     ivar_iterator end() { return ivar_iterator(*this, getCount()); }
 610     const ivar_iterator begin() const { return ivar_iterator(*this, 0); }
 611     const ivar_iterator end() const { return ivar_iterator(*this, getCount()); }
 612
 613     static objc_ivar_list_t<P>* newIvarList(size_t newCount, uint32_t newEntsize) {
 614         void *buf = ::calloc(byteSizeForCount(newCount, newEntsize), 1);
 615         return new (buf) objc_ivar_list_t<P>(newCount, newEntsize);
 616     }
 617
 618     void operator delete(void * p) {
 619         ::free(p);
 620     }
 621
 622     objc_ivar_list_t(uint32_t newCount,
 623                          uint32_t newEntsize = sizeof(objc_ivar_t<P>))
 624         : entsize(newEntsize), count(newCount)
 625     { }
 626 private:
 627     // use newIvarList instead
 628     void* operator new (size_t);
 629 };
 630
 631
 632 template <typename P> class objc_property_list_t; // forward
 633
 634 template <typename P>
 635 class objc_property_t {
 636     typedef typename P::uint_t pint_t;
 637     pint_t name;
 638     pint_t attributes;
 639     friend class objc_property_list_t<P>;
 640 public:
 641
 642     const char * getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 643
 644     const char * getAttributes(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(attributes)); }
 645 };
 646
 647 template <typename P>
 648 class objc_property_list_t {
 649     uint32_t entsize;
 650     uint32_t count;
 651     objc_property_t<P> first;
 652
 653     void* operator new (size_t, void* buf) { return buf; }
 654
 655 public:
 656
 657     typedef entsize_iterator<P, objc_property_t<P>, objc_property_list_t<P> > property_iterator;
 658
 659     uint32_t getCount() const { return P::E::get32(count); }
 660
 661     uint32_t getEntsize() const { return P::E::get32(entsize); }
 662
 663     void* get(uint32_t i) const { return (objc_property_t<P> *)((uint8_t *)&first + i * getEntsize()); }
 664
 665     uint32_t byteSize() const {
 666         return byteSizeForCount(getCount(), getEntsize());
 667     }
 668
 669     static uint32_t byteSizeForCount(uint32_t c, uint32_t e = sizeof(objc_property_t<P>)) {
 670         return sizeof(objc_property_list_t<P>) - sizeof(objc_property_t<P>) + c*e;
 671     }
 672
 673     property_iterator begin() { return property_iterator(*this, 0); }
 674     property_iterator end() { return property_iterator(*this, getCount()); }
 675     const property_iterator begin() const { return property_iterator(*this, 0); }
 676     const property_iterator end() const { return property_iterator(*this, getCount()); }
 677
 678     void getPointers(std::set<void*>& pointersToRemove) {
 679         for(property_iterator it = begin(); it != end(); ++it) {
 680             objc_property_t<P>& entry = *it;
 681             pointersToRemove.insert(&(entry.name));
 682             pointersToRemove.insert(&(entry.attributes));
 683         }
 684     }
 685
 686     static void addPointers(uint8_t* propertyList, CacheBuilder::ASLR_Tracker& aslrTracker) {
 687         objc_property_list_t<P>* plist = (objc_property_list_t<P>*)propertyList;
 688         for(property_iterator it = plist->begin(); it != plist->end(); ++it) {
 689             objc_property_t<P>& entry = *it;
 690             aslrTracker.add(&(entry.name));
 691             aslrTracker.add(&(entry.attributes));
 692         }
 693     }
 694
 695      static objc_property_list_t<P>* newPropertyList(size_t newCount, uint32_t newEntsize) {
 696         void *buf = ::calloc(byteSizeForCount(newCount, newEntsize), 1);
 697         return new (buf) objc_property_list_t<P>(newCount, newEntsize);
 698     }
 699
 700     void operator delete(void * p) {
 701         ::free(p);
 702     }
 703
 704     objc_property_list_t(uint32_t newCount,
 705                          uint32_t newEntsize = sizeof(objc_property_t<P>))
 706         : entsize(newEntsize), count(newCount)
 707     { }
 708 private:
 709     // use newPropertyList instead
 710     void* operator new (size_t);
 711 };
 712
 713
 714 template <typename A> class objc_protocol_list_t;  // forward reference
 715
 716 template <typename P>
 717 class objc_protocol_t {
 718     typedef typename P::uint_t pint_t;
 719
 720     pint_t isa;
 721     pint_t name;
 722     pint_t protocols;
 723     pint_t instanceMethods;
 724     pint_t classMethods;
 725     pint_t optionalInstanceMethods;
 726     pint_t optionalClassMethods;
 727     pint_t instanceProperties;
 728     uint32_t size;
 729     uint32_t flags;
 730     pint_t extendedMethodTypes;
 731     pint_t demangledName;
 732     pint_t classProperties;
 733
 734 public:
 735     pint_t getIsaVMAddr() const { return (pint_t)P::getP(isa); }
 736     void setIsaVMAddr(pint_t newIsa) { P::setP(isa, newIsa); }
 737     void* getISALocation() const { return (void*)&isa; }
 738
 739     const char *getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 740
 741     uint32_t getSize() const { return P::E::get32(size); }
 742     void setSize(uint32_t newSize) { P::E::set32(size, newSize); }
 743
 744     uint32_t getFlags() const { return P::E::get32(flags); }
 745
 746     void setFixedUp() { P::E::set32(flags, getFlags() | (1<<30)); }
 747     void setIsCanonical() {
 748         assert((getFlags() & (1 << 29)) == 0);
 749         P::E::set32(flags, getFlags() | (1<<29));
 750     }
 751
 752     objc_protocol_list_t<P> *getProtocols(ContentAccessor* cache) const { return (objc_protocol_list_t<P> *)cache->contentForVMAddr(P::getP(protocols)); }
 753
 754     objc_method_list_t<P> *getInstanceMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(instanceMethods)); }
 755
 756     objc_method_list_t<P> *getClassMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(classMethods)); }
 757
 758     objc_method_list_t<P> *getOptionalInstanceMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(optionalInstanceMethods)); }
 759
 760     objc_method_list_t<P> *getOptionalClassMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(optionalClassMethods)); }
 761
 762     objc_property_list_t<P> *getInstanceProperties(ContentAccessor* cache) const { return (objc_property_list_t<P> *)cache->contentForVMAddr(P::getP(instanceProperties)); }
 763
 764     pint_t *getExtendedMethodTypes(ContentAccessor* cache) const {
 765         if (getSize() < offsetof(objc_protocol_t<P>, extendedMethodTypes) + sizeof(extendedMethodTypes)) {
 766             return NULL;
 767         }
 768         return (pint_t *)cache->contentForVMAddr(P::getP(extendedMethodTypes));
 769     }
 770
 771     const char *getDemangledName(ContentAccessor* cache) const {
 772         if (sizeof(*this) < offsetof(objc_protocol_t<P>, demangledName) + sizeof(demangledName)) {
 773             return NULL;
 774         }
 775         return (const char *)cache->contentForVMAddr(P::getP(demangledName));
 776     }
 777
 778     void setDemangledName(ContentAccessor* cache, const char *newName, Diagnostics& diag) {
 779         if (sizeof(*this) < offsetof(objc_protocol_t<P>, demangledName) + sizeof(demangledName))
 780             diag.error("objc protocol has the wrong size");
 781         else
 782             P::setP(demangledName, cache->vmAddrForContent((void*)newName));
 783     }
 784
 785     void addPointers(ContentAccessor* cache, CacheBuilder::ASLR_Tracker& aslrTracker)
 786     {
 787         aslrTracker.add(&isa);
 788         aslrTracker.add(&name);
 789         if (protocols)               aslrTracker.add(&protocols);
 790         if (instanceMethods)         aslrTracker.add(&instanceMethods);
 791         if (classMethods)            aslrTracker.add(&classMethods);
 792         if (optionalInstanceMethods) aslrTracker.add(&optionalInstanceMethods);
 793         if (optionalClassMethods)    aslrTracker.add(&optionalClassMethods);
 794         if (instanceProperties)      aslrTracker.add(&instanceProperties);
 795         if (extendedMethodTypes)     aslrTracker.add(&extendedMethodTypes);
 796         if (demangledName)           aslrTracker.add(&demangledName);
 797         if (classProperties)         aslrTracker.add(&classProperties);
 798     }
 799 };
 800
 801
 802 template <typename P>
 803 class objc_protocol_list_t {
 804     typedef typename P::uint_t pint_t;
 805     pint_t count;
 806     pint_t list[0];
 807
 808     void* operator new (size_t, void* buf) { return buf; }
 809
 810 public:
 811
 812     pint_t getCount() const { return (pint_t)P::getP(count); }
 813
 814     pint_t getVMAddress(pint_t i) {
 815         return (pint_t)P::getP(list[i]);
 816     }
 817
 818     objc_protocol_t<P>* get(ContentAccessor* cache, pint_t i) {
 819         return (objc_protocol_t<P>*)cache->contentForVMAddr(getVMAddress(i));
 820     }
 821
 822     void setVMAddress(pint_t i, pint_t protoVMAddr) {
 823         P::setP(list[i], protoVMAddr);
 824     }
 825
 826     void set(ContentAccessor* cache, pint_t i, objc_protocol_t<P>* proto) {
 827         setVMAddress(i, cache->vmAddrForContent(proto));
 828     }
 829
 830     uint32_t byteSize() const {
 831         return byteSizeForCount(getCount());
 832     }
 833     static uint32_t byteSizeForCount(pint_t c) {
 834         return sizeof(objc_protocol_list_t<P>) + c*sizeof(pint_t);
 835     }
 836
 837     void getPointers(std::set<void*>& pointersToRemove) {
 838         for(int i=0 ; i < count; ++i) {
 839             pointersToRemove.insert(&list[i]);
 840         }
 841     }
 842
 843      static void addPointers(uint8_t* protocolList, CacheBuilder::ASLR_Tracker& aslrTracker) {
 844         objc_protocol_list_t<P>* plist = (objc_protocol_list_t<P>*)protocolList;
 845         for(int i=0 ; i < plist->count; ++i) {
 846             aslrTracker.add(&plist->list[i]);
 847         }
 848     }
 849
 850     static objc_protocol_list_t<P>* newProtocolList(pint_t newCount) {
 851         void *buf = ::calloc(byteSizeForCount(newCount), 1);
 852         return new (buf) objc_protocol_list_t<P>(newCount);
 853     }
 854
 855     void operator delete(void * p) {
 856         ::free(p);
 857     }
 858
 859     objc_protocol_list_t(uint32_t newCount) : count(newCount) { }
 860 private:
 861     // use newProtocolList instead
 862     void* operator new (size_t);
 863 };
 864
 865
 866 template <typename P>
 867 class objc_class_data_t {
 868     typedef typename P::uint_t pint_t;
 869     uint32_t flags;
 870     uint32_t instanceStart;
 871     // Note there is 4-bytes of alignment padding between instanceSize and ivarLayout
 872     // on 64-bit archs, but no padding on 32-bit archs.
 873     // This union is a way to model that.
 874     union {
 875         uint32_t                instanceSize;
 876         pint_t   pad;
 877     } instanceSize;
 878     pint_t ivarLayout;
 879     pint_t name;
 880     pint_t baseMethods;
 881     pint_t baseProtocols;
 882     pint_t ivars;
 883     pint_t weakIvarLayout;
 884     pint_t baseProperties;
 885
 886 public:
 887     bool isMetaClass() { return P::E::get32(flags) & (1 << 0); }
 888     bool isRootClass() { return P::E::get32(flags) & (1 << 1); }
 889
 890     uint32_t getInstanceStart() { return P::E::get32(instanceStart); }
 891     void setInstanceStart(uint32_t newStart) { P::E::set32(instanceStart, newStart); }
 892
 893     uint32_t getInstanceSize() { return P::E::get32(instanceSize.instanceSize); }
 894     void setInstanceSize(uint32_t newSiz) { P::E::set32(instanceSize.instanceSize, newSiz); }
 895
 896     objc_method_list_t<P> *getMethodList(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(baseMethods)); }
 897
 898     objc_protocol_list_t<P> *getProtocolList(ContentAccessor* cache) const { return (objc_protocol_list_t<P> *)cache->contentForVMAddr(P::getP(baseProtocols)); }
 899
 900     objc_ivar_list_t<P> *getIvarList(ContentAccessor* cache) const { return (objc_ivar_list_t<P> *)cache->contentForVMAddr(P::getP(ivars)); }
 901
 902     objc_property_list_t<P> *getPropertyList(ContentAccessor* cache) const { return (objc_property_list_t<P> *)cache->contentForVMAddr(P::getP(baseProperties)); }
 903
 904     const char * getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 905
 906     void setMethodList(ContentAccessor* cache, objc_method_list_t<P>* mlist) {
 907         P::setP(baseMethods, cache->vmAddrForContent(mlist));
 908     }
 909
 910     void setProtocolList(ContentAccessor* cache, objc_protocol_list_t<P>* protolist) {
 911         P::setP(baseProtocols, cache->vmAddrForContent(protolist));
 912     }
 913
 914     void setPropertyList(ContentAccessor* cache, objc_property_list_t<P>* proplist) {
 915         P::setP(baseProperties, cache->vmAddrForContent(proplist));
 916     }
 917
 918     void addMethodListPointer(CacheBuilder::ASLR_Tracker& aslrTracker) {
 919         aslrTracker.add(&this->baseMethods);
 920     }
 921
 922     void addPropertyListPointer(CacheBuilder::ASLR_Tracker& aslrTracker) {
 923         aslrTracker.add(&this->baseProperties);
 924     }
 925
 926     void addProtocolListPointer(CacheBuilder::ASLR_Tracker& aslrTracker) {
 927         aslrTracker.add(&this->baseProtocols);
 928     }
 929 };
 930
 931 template <typename P>
 932 class objc_class_t {
 933     typedef typename P::uint_t pint_t;
 934
 935     pint_t isa;
 936     pint_t superclass;
 937     pint_t method_cache;
 938     pint_t vtable;
 939     pint_t data;
 940
 941 public:
 942     bool isMetaClass(ContentAccessor* cache) const { return getData(cache)->isMetaClass(); }
 943     bool isRootClass(ContentAccessor* cache) const { return getData(cache)->isRootClass(); }
 944
 945     objc_class_t<P> *getIsa(ContentAccessor* cache) const { return (objc_class_t<P> *)cache->contentForVMAddr(P::getP(isa)); }
 946
 947     objc_class_t<P> *getSuperclass(ContentAccessor* cache) const { return (objc_class_t<P> *)cache->contentForVMAddr(P::getP(superclass)); }
 948     const pint_t* getSuperClassAddress() const { return &superclass; }
 949
 950     // Low bit marks Swift classes.
 951     objc_class_data_t<P> *getData(ContentAccessor* cache) const { return (objc_class_data_t<P> *)cache->contentForVMAddr(P::getP(data & ~0x3LL)); }
 952
 953     objc_class_t<P> *getVTable(ContentAccessor* cache) const { return (objc_class_t<P> *)cache->contentForVMAddr(P::getP(vtable)); }
 954
 955     pint_t* getVTableAddress() { return &vtable; }
 956
 957     objc_method_list_t<P> *getMethodList(ContentAccessor* cache) const {
 958         objc_class_data_t<P>* d = getData(cache);
 959         return d->getMethodList(cache);
 960     }
 961
 962     objc_protocol_list_t<P> *getProtocolList(ContentAccessor* cache) const { return getData(cache)->getProtocolList(cache); }
 963
 964     objc_property_list_t<P> *getPropertyList(ContentAccessor* cache) const { return getData(cache)->getPropertyList(cache); }
 965
 966     const char* getName(ContentAccessor* cache) const {
 967         return getData(cache)->getName(cache);
 968     }
 969
 970     void setMethodList(ContentAccessor* cache, objc_method_list_t<P>* mlist) {
 971         getData(cache)->setMethodList(cache, mlist);
 972     }
 973
 974     void setProtocolList(ContentAccessor* cache, objc_protocol_list_t<P>* protolist) {
 975         getData(cache)->setProtocolList(cache, protolist);
 976     }
 977
 978     void setPropertyList(ContentAccessor* cache, objc_property_list_t<P>* proplist) {
 979         getData(cache)->setPropertyList(cache, proplist);
 980     }
 981
 982     void addMethodListPointer(ContentAccessor* cache, CacheBuilder::ASLR_Tracker& aslrTracker) {
 983         getData(cache)->addMethodListPointer(aslrTracker);
 984     }
 985
 986     void addPropertyListPointer(ContentAccessor* cache, CacheBuilder::ASLR_Tracker& aslrTracker) {
 987         getData(cache)->addPropertyListPointer(aslrTracker);
 988     }
 989
 990     void addProtocolListPointer(ContentAccessor* cache, CacheBuilder::ASLR_Tracker& aslrTracker) {
 991         getData(cache)->addProtocolListPointer(aslrTracker);
 992     }
 993
 994 };
 995
 996
 997
 998 template <typename P>
 999 class objc_category_t {
1000     typedef typename P::uint_t pint_t;
1001
1002     pint_t name;
1003     pint_t cls;
1004     pint_t instanceMethods;
1005     pint_t classMethods;
1006     pint_t protocols;
1007     pint_t instanceProperties;
1008
1009 public:
1010
1011     const char * getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
1012
1013     objc_class_t<P> *getClass(ContentAccessor* cache) const { return (objc_class_t<P> *)cache->contentForVMAddr(P::getP(cls)); }
1014
1015     objc_method_list_t<P> *getInstanceMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(instanceMethods)); }
1016
1017     objc_method_list_t<P> *getClassMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(classMethods)); }
1018
1019     objc_protocol_list_t<P> *getProtocols(ContentAccessor* cache) const { return (objc_protocol_list_t<P> *)cache->contentForVMAddr(P::getP(protocols)); }
1020
1021     objc_property_list_t<P> *getInstanceProperties(ContentAccessor* cache) const { return (objc_property_list_t<P> *)cache->contentForVMAddr(P::getP(instanceProperties)); }
1022
1023     void getPointers(std::set<void*>& pointersToRemove) {
1024         pointersToRemove.insert(&name);
1025         pointersToRemove.insert(&cls);
1026         pointersToRemove.insert(&instanceMethods);
1027         pointersToRemove.insert(&classMethods);
1028         pointersToRemove.insert(&protocols);
1029         pointersToRemove.insert(&instanceProperties);
1030     }
1031
1032
1033 };
1034
1035 template <typename P>
1036 class objc_message_ref_t {
1037     typedef typename P::uint_t pint_t;
1038
1039     pint_t imp;
1040     pint_t sel;
1041
1042 public:
1043     pint_t getName() const { return (pint_t)P::getP(sel); }
1044
1045     void setName(pint_t newName) { P::setP(sel, newName); }
1046 };
1047
1048 // Call visitor.visitIvar() on every ivar in a given class.
1049 template <typename P, typename V>
1050 class IvarWalker {
1051     typedef typename P::uint_t pint_t;
1052     V& ivarVisitor;
1053 public:
1054
1055     IvarWalker(V& visitor) : ivarVisitor(visitor) { }
1056
1057     void walk(ContentAccessor* cache, const macho_header<P>* header, objc_class_t<P> *cls)
1058     {
1059         objc_class_data_t<P> *data = cls->getData(cache);
1060         objc_ivar_list_t<P> *ivars = data->getIvarList(cache);
1061         if (ivars) {
1062             for (pint_t i = 0; i < ivars->getCount(); i++) {
1063                 objc_ivar_t<P>* ivar = (objc_ivar_t<P>*)ivars->get(i);
1064                 //fprintf(stderr, "visiting ivar: %s\n", ivar.getName(cache));
1065                 ivarVisitor.visitIvar(cache, header, cls, ivar);
1066             }
1067         } else {
1068             //fprintf(stderr, "no ivars\n");
1069         }
1070     }
1071
1072     void visitClass(ContentAccessor* cache, const macho_header<P>* header, objc_class_t<P> *cls)
1073     {
1074         walk(cache, header, cls);
1075     }
1076 };
1077
1078 enum class ClassWalkerMode {
1079     ClassesOnly,
1080     ClassAndMetaclasses,
1081 };
1082
1083 // Call visitor.visitClass() on every class.
1084 template <typename P, typename V>
1085 class ClassWalker {
1086     typedef typename P::uint_t pint_t;
1087     V& _visitor;
1088     ClassWalkerMode _mode;
1089 public:
1090
1091     ClassWalker(V& visitor, ClassWalkerMode mode = ClassWalkerMode::ClassesOnly) : _visitor(visitor), _mode(mode) { }
1092
1093     void walk(ContentAccessor* cache, const macho_header<P>* header)
1094     {
1095         PointerSection<P, objc_class_t<P>*> classList(cache, header, "__DATA", "__objc_classlist");
1096
1097         for (pint_t i = 0; i < classList.count(); i++) {
1098             objc_class_t<P>* cls = classList.get(i);
1099             if (cls) {
1100                 //fprintf(stderr, "visiting class: %s\n", cls->getName(cache));
1101                 _visitor.visitClass(cache, header, cls);
1102                 if (_mode == ClassWalkerMode::ClassAndMetaclasses) {
1103                     //fprintf(stderr, "visiting metaclass: %s\n", cls->getIsa(cache)->getName(cache));
1104                     _visitor.visitClass(cache, header, cls->getIsa(cache));
1105                 }
1106             }
1107         }
1108     }
1109 };
1110
1111 // Call visitor.visitProtocol() on every protocol.
1112 template <typename P, typename V>
1113 class ProtocolWalker {
1114     typedef typename P::uint_t pint_t;
1115     V& _protocolVisitor;
1116 public:
1117
1118     ProtocolWalker(V& visitor) : _protocolVisitor(visitor) { }
1119
1120     void walk(ContentAccessor* cache, const macho_header<P>* header)
1121     {
1122         PointerSection<P, objc_protocol_t<P> *>
1123             protocols(cache, header, "__DATA", "__objc_protolist");
1124
1125         for (pint_t i = 0; i < protocols.count(); i++) {
1126             objc_protocol_t<P> *proto = protocols.get(i);
1127             _protocolVisitor.visitProtocol(cache, header, proto);
1128         }
1129     }
1130 };
1131
1132 // Call visitor.visitProtocolReference() on every protocol.
1133 template <typename P, typename V>
1134 class ProtocolReferenceWalker {
1135     typedef typename P::uint_t pint_t;
1136     V& _visitor;
1137
1138     void visitProtocolList(ContentAccessor* cache,
1139                            objc_protocol_list_t<P>* protolist)
1140     {
1141         if (!protolist) return;
1142         for (pint_t i = 0; i < protolist->getCount(); i++) {
1143             pint_t oldValue = protolist->getVMAddress(i);
1144             pint_t newValue = _visitor.visitProtocolReference(cache, oldValue);
1145             protolist->setVMAddress(i, newValue);
1146         }
1147     }
1148
1149     friend class ClassWalker<P, ProtocolReferenceWalker<P, V>>;
1150
1151     void visitClass(ContentAccessor* cache, const macho_header<P>*,
1152                     objc_class_t<P>* cls)
1153     {
1154         visitProtocolList(cache, cls->getProtocolList(cache));
1155         visitProtocolList(cache, cls->getIsa(cache)->getProtocolList(cache));
1156     }
1157
1158 public:
1159
1160     ProtocolReferenceWalker(V& visitor) : _visitor(visitor) { }
1161     void walk(ContentAccessor* cache, const macho_header<P>* header)
1162     {
1163         // @protocol expressions
1164         PointerSection<P, objc_protocol_t<P> *>
1165             protorefs(cache, header, "__DATA", "__objc_protorefs");
1166         for (pint_t i = 0; i < protorefs.count(); i++) {
1167             pint_t oldValue = protorefs.getVMAddress(i);
1168             pint_t newValue = _visitor.visitProtocolReference(cache, oldValue);
1169             protorefs.setVMAddress(i, newValue);
1170         }
1171
1172         // protocol lists in classes
1173         ClassWalker<P, ProtocolReferenceWalker<P, V>> classes(*this);
1174         classes.walk(cache, header);
1175
1176         // protocol lists from categories
1177         PointerSection<P, objc_category_t<P> *>
1178         cats(cache, header, "__DATA", "__objc_catlist");
1179         for (pint_t i = 0; i < cats.count(); i++) {
1180             objc_category_t<P> *cat = cats.get(i);
1181             visitProtocolList(cache, cat->getProtocols(cache));
1182         }
1183
1184         // protocol lists in protocols
1185         // __objc_protolists itself is NOT updated
1186         PointerSection<P, objc_protocol_t<P> *>
1187             protocols(cache, header, "__DATA", "__objc_protolist");
1188         for (pint_t i = 0; i < protocols.count(); i++) {
1189             objc_protocol_t<P>* proto = protocols.get(i);
1190             visitProtocolList(cache, proto->getProtocols(cache));
1191             // not recursive: every old protocol object
1192             // must be in some protolist section somewhere
1193         }
1194     }
1195 };
1196
1197 // Call visitor.visitMethodList(mlist) on every
1198 // class and category method list in a header.
1199 // Call visitor.visitProtocolMethodList(mlist, typelist) on every
1200 // protocol method list in a header.
1201 template <typename P, typename V>
1202 class MethodListWalker {
1203
1204     typedef typename P::uint_t pint_t;
1205
1206     V& mVisitor;
1207
1208 public:
1209
1210     MethodListWalker(V& visitor) : mVisitor(visitor) { }
1211
1212     void walk(ContentAccessor* cache, const macho_header<P>* header)
1213     {
1214         // Method lists in classes
1215         PointerSection<P, objc_class_t<P> *>
1216             classes(cache, header, "__DATA", "__objc_classlist");
1217
1218         for (pint_t i = 0; i < classes.count(); i++) {
1219             objc_class_t<P> *cls = classes.get(i);
1220             objc_method_list_t<P> *mlist;
1221             if ((mlist = cls->getMethodList(cache))) {
1222                 mVisitor.visitMethodList(cache, mlist);
1223             }
1224             if ((mlist = cls->getIsa(cache)->getMethodList(cache))) {
1225                 mVisitor.visitMethodList(cache, mlist);
1226             }
1227         }
1228
1229         // Method lists from categories
1230         PointerSection<P, objc_category_t<P> *>
1231             cats(cache, header, "__DATA", "__objc_catlist");
1232         for (pint_t i = 0; i < cats.count(); i++) {
1233             objc_category_t<P> *cat = cats.get(i);
1234             objc_method_list_t<P> *mlist;
1235             if ((mlist = cat->getInstanceMethods(cache))) {
1236                 mVisitor.visitMethodList(cache, mlist);
1237             }
1238             if ((mlist = cat->getClassMethods(cache))) {
1239                 mVisitor.visitMethodList(cache, mlist);
1240             }
1241         }
1242
1243         // Method description lists from protocols
1244         PointerSection<P, objc_protocol_t<P> *>
1245             protocols(cache, header, "__DATA", "__objc_protolist");
1246         for (pint_t i = 0; i < protocols.count(); i++) {
1247             objc_protocol_t<P> *proto = protocols.get(i);
1248             objc_method_list_t<P> *mlist;
1249             pint_t *typelist = proto->getExtendedMethodTypes(cache);
1250
1251             if ((mlist = proto->getInstanceMethods(cache))) {
1252                 mVisitor.visitProtocolMethodList(cache, mlist, typelist);
1253                 if (typelist) typelist += mlist->getCount();
1254             }
1255             if ((mlist = proto->getClassMethods(cache))) {
1256                 mVisitor.visitProtocolMethodList(cache, mlist, typelist);
1257                 if (typelist) typelist += mlist->getCount();
1258             }
1259             if ((mlist = proto->getOptionalInstanceMethods(cache))) {
1260                 mVisitor.visitProtocolMethodList(cache, mlist, typelist);
1261                 if (typelist) typelist += mlist->getCount();
1262             }
1263             if ((mlist = proto->getOptionalClassMethods(cache))) {
1264                 mVisitor.visitProtocolMethodList(cache, mlist, typelist);
1265                 if (typelist) typelist += mlist->getCount();
1266             }
1267         }
1268     }
1269 };
1270
1271 // Update selector references. The visitor performs recording and uniquing.
1272 template <typename P, typename V>
1273 class SelectorOptimizer {
1274
1275     typedef typename P::uint_t pint_t;
1276
1277     V& mVisitor;
1278
1279     std::set<pint_t> selectorRefVMAddrs;
1280
1281     friend class MethodListWalker<P, SelectorOptimizer<P,V> >;
1282     void visitMethodList(ContentAccessor* cache, objc_method_list_t<P> *mlist)
1283     {
1284         // Gather selectors. Update method names.
1285         for (uint32_t m = 0; m < mlist->getCount(); m++) {
1286             // Read names as relative offsets to selRefs
1287             pint_t oldValue = mlist->getName(cache, m, false);
1288             pint_t newValue = mVisitor.visit(oldValue);
1289             // And write names as relative offsets to SELs themselves.
1290             mlist->setName(cache, m, newValue, true);
1291         }
1292         // Set this method list as now being relative offsets directly to the selector string
1293         if ( mlist->usesRelativeMethods() )
1294             mlist->setMethodListSelectorsAreDirect();
1295
1296         // Do not setFixedUp: the methods are not yet sorted.
1297     }
1298
1299     void visitProtocolMethodList(ContentAccessor* cache, objc_method_list_t<P> *mlist, pint_t *types)
1300     {
1301         visitMethodList(cache, mlist);
1302     }
1303
1304 public:
1305
1306     SelectorOptimizer(V& visitor, bool& relativeMethodListSelectorsAreDirect) : mVisitor(visitor) {
1307         // This pass requires that relative method lists are initially indirected via the selector
1308         // ref.  After this pass runs we'll use relative offsets to the selectors themselves
1309         assert(!relativeMethodListSelectorsAreDirect);
1310         relativeMethodListSelectorsAreDirect = true;
1311     }
1312
1313     void visitCoalescedStrings(const CacheBuilder::CacheCoalescedText& coalescedText) {
1314         mVisitor.visitCoalescedStrings(coalescedText);
1315     }
1316
1317     void optimize(ContentAccessor* cache, const macho_header<P>* header)
1318     {
1319         // method lists in classes, categories, and protocols
1320         MethodListWalker<P, SelectorOptimizer<P,V> > mw(*this);
1321         mw.walk(cache, header);
1322
1323         // @selector references
1324         PointerSection<P, const char *>
1325             selrefs(cache, header, "__DATA", "__objc_selrefs");
1326         for (pint_t i = 0; i < selrefs.count(); i++) {
1327             pint_t oldValue = selrefs.getVMAddress(i);
1328             pint_t newValue = mVisitor.visit(oldValue);
1329             selrefs.setVMAddress(i, newValue);
1330             selectorRefVMAddrs.insert(selrefs.getSectionVMAddress() + (i * sizeof(pint_t)));
1331         }
1332
1333         // message references
1334         ArraySection<P, objc_message_ref_t<P> >
1335             msgrefs(cache, header, "__DATA", "__objc_msgrefs");
1336         for (pint_t i = 0; i < msgrefs.count(); i++) {
1337             objc_message_ref_t<P>& msg = msgrefs.get(i);
1338             pint_t oldValue = msg.getName();
1339             pint_t newValue = mVisitor.visit(oldValue);
1340             msg.setName(newValue);
1341         }
1342     }
1343
1344     bool isSelectorRefAddress(pint_t vmAddr) const {
1345         return selectorRefVMAddrs.count(vmAddr);
1346     }
1347 };
1348
1349
1350 // Update selector references. The visitor performs recording and uniquing.
1351 template <typename P>
1352 class IvarOffsetOptimizer {
1353     uint32_t    _slide;
1354     uint32_t    _maxAlignment;
1355     uint32_t    _optimized;
1356
1357 public:
1358
1359     IvarOffsetOptimizer() : _optimized(0) { }
1360
1361     size_t optimized() const { return _optimized; }
1362
1363     // dual purpose ivar visitor function
1364     // if slide!=0 then slides the ivar by that amount, otherwise computes _maxAlignment
1365     void visitIvar(ContentAccessor* cache, const macho_header<P>* /*unused, may be NULL*/, objc_class_t<P> *cls, objc_ivar_t<P> *ivar)
1366     {
1367         if (_slide == 0) {
1368             uint32_t alignment = ivar->getAlignment();
1369             if (alignment > _maxAlignment) _maxAlignment = alignment;
1370         } else {
1371             // skip anonymous bitfields
1372             if (ivar->hasOffset()) {
1373                 uint32_t oldOffset = (uint32_t)ivar->getOffset(cache);
1374                 ivar->setOffset(cache, oldOffset + _slide);
1375                 _optimized++;
1376                 //fprintf(stderr, "%d -> %d for %s.%s\n", oldOffset, oldOffset + _slide, cls->getName(cache), ivar->getName(cache));
1377             } else {
1378                 //fprintf(stderr, "NULL offset\n");
1379             }
1380         }
1381     }
1382
1383     // Class visitor function. Evaluates whether to slide ivars and performs slide if needed.
1384     // The slide algorithm is also implemented in objc. Any changes here should be reflected there also.
1385     void visitClass(ContentAccessor* cache, const macho_header<P>* /*unused, may be NULL*/, objc_class_t<P> *cls)
1386     {
1387         objc_class_t<P> *super = cls->getSuperclass(cache);
1388         if (super) {
1389             // Recursively visit superclasses to ensure we have the correct superclass start
1390             // Note that we don't need the macho_header, so just pass NULL.
1391             visitClass(cache, nullptr, super);
1392
1393             objc_class_data_t<P> *data = cls->getData(cache);
1394             objc_class_data_t<P> *super_data = super->getData(cache);
1395             int32_t diff = super_data->getInstanceSize() - data->getInstanceStart();
1396             if (diff > 0) {
1397                 IvarWalker<P, IvarOffsetOptimizer<P> > ivarVisitor(*this);
1398                 _maxAlignment = 1;
1399                 _slide = 0;
1400
1401                 // This walk computes _maxAlignment
1402                 ivarVisitor.walk(cache, nullptr, cls);
1403
1404                 // Compute a slide value that preserves that alignment
1405                 uint32_t alignMask = _maxAlignment - 1;
1406                 if (diff & alignMask) diff = (diff + alignMask) & ~alignMask;
1407
1408                 // Slide all of this class's ivars en masse
1409                 _slide = diff;
1410                 if (_slide != 0) {
1411                     //fprintf(stderr, "Sliding ivars in %s by %u (superclass was %d, now %d)\n", cls->getName(cache), _slide, data->getInstanceStart(), super_data->getInstanceSize());
1412                     ivarVisitor.walk(cache, nullptr, cls);
1413                     data->setInstanceStart(data->getInstanceStart() + _slide);
1414                     data->setInstanceSize(data->getInstanceSize() + _slide);
1415                 }
1416             }
1417         }
1418     }
1419
1420     // Enumerates objc classes in the module and performs any ivar slides
1421     void optimize(ContentAccessor* cache, const macho_header<P>* header)
1422     {
1423         // The slide code cannot fix up GC layout strings so skip modules that support or require GC
1424         const macho_section<P> *imageInfoSection = header->getSection("__DATA", "__objc_imageinfo");
1425         if (imageInfoSection) {
1426             objc_image_info<P> *info = (objc_image_info<P> *)cache->contentForVMAddr(imageInfoSection->addr());
1427             if (!info->supportsGCFlagSet() && !info->requiresGCFlagSet()) {
1428                 ClassWalker<P, IvarOffsetOptimizer<P> > classVisitor(*this);
1429                 classVisitor.walk(cache, header);
1430             } else {
1431                 //fprintf(stderr, "GC support present - skipped module\n");
1432             }
1433         }
1434     }
1435 };
1436
1437
1438 // Detect classes that have missing weak-import superclasses.
1439 template <typename P>
1440 class WeakClassDetector {
1441     bool                                noMissing;
1442     const std::map<void*, std::string>* missingWeakImports = nullptr;
1443
1444     friend class ClassWalker<P, WeakClassDetector<P>>;
1445     void visitClass(ContentAccessor* cache, const macho_header<P>*,
1446                     objc_class_t<P>* cls)
1447     {
1448         auto supercls = cls->getSuperclass(cache);
1449         if (supercls) {
1450             // okay: class with superclass
1451             // Note that the superclass itself might have a missing superclass.
1452             // That is fine for mere detection because we will visit the
1453             // superclass separately.
1454         } else if (cls->isRootClass(cache)) {
1455             // okay: root class is expected to have no superclass
1456         } else {
1457             // bad: cls's superclass is missing.
1458             // See if we can find the name from the missing weak import map
1459             auto it = missingWeakImports->find((void*)cls->getSuperClassAddress());
1460             const char* dylibName = "unknown dylib";
1461             if (it != missingWeakImports->end()) {
1462                 dylibName = it->second.c_str();
1463             }
1464             cache->diagnostics().warning("Superclass of class '%s' is weak-import and missing.  Expected in %s",
1465                                          cls->getName(cache), dylibName);
1466             noMissing = false;
1467         }
1468     }
1469
1470 public:
1471     bool noMissingWeakSuperclasses(ContentAccessor* cache,
1472                                    const std::map<void*, std::string>& missingWeakImportsMap,
1473                                    std::vector<const macho_header<P>*> dylibs)
1474     {
1475         noMissing           = true;
1476         missingWeakImports  = &missingWeakImportsMap;
1477         ClassWalker<P, WeakClassDetector<P>> classes(*this);
1478         for (auto mh : dylibs) {
1479             classes.walk(cache, mh);
1480         }
1481         return noMissing;
1482     }
1483 };
1484
1485
1486 // Sort methods in place by selector.
1487 template <typename P>
1488 class MethodListSorter {
1489
1490     typedef typename P::uint_t pint_t;
1491
1492     uint32_t _optimized;
1493     bool     _isOffsetToSel;
1494
1495     friend class MethodListWalker<P, MethodListSorter<P> >;
1496
1497     void sortMethodList(ContentAccessor* cache, objc_method_list_t<P> *mlist, pint_t *typelist) {
1498         mlist->sortMethods(cache, typelist, _isOffsetToSel);
1499         _optimized++;
1500     }
1501
1502     void visitMethodList(ContentAccessor* cache, objc_method_list_t<P> *mlist)
1503     {
1504         sortMethodList(cache, mlist, nullptr);
1505     }
1506
1507     void visitProtocolMethodList(ContentAccessor* cache, objc_method_list_t<P> *mlist, pint_t *typelist)
1508     {
1509         sortMethodList(cache, mlist, typelist);
1510     }
1511
1512 public:
1513     MethodListSorter(bool isOffsetToSel) : _optimized(0), _isOffsetToSel(isOffsetToSel) { }
1514
1515     size_t optimized() const { return _optimized; }
1516
1517     void optimize(ContentAccessor* cache, const macho_header<P>* header)
1518     {
1519         MethodListWalker<P, MethodListSorter<P> > mw(*this);
1520         mw.walk(cache, header);
1521     }
1522 };
1523
1524
1525 template <typename P, typename InfoT>
1526 class HeaderInfoOptimizer {
1527 public:
1528
1529     typedef typename P::uint_t pint_t;
1530
1531     HeaderInfoOptimizer() : _hInfos(0), _count(0) { }
1532
1533     const char* init(uint32_t count, uint8_t*& buf, size_t& bufSize) {
1534         if (count == 0)
1535             return nullptr;
1536
1537         size_t requiredSize =
1538             2*sizeof(uint32_t) + count*sizeof(InfoT);
1539         if (bufSize < requiredSize) {
1540             return "libobjc's read/write section is too small (metadata not optimized)";
1541         }
1542
1543         uint32_t *buf32 = (uint32_t *)buf;
1544         P::E::set32(buf32[0], count);
1545         P::E::set32(buf32[1], sizeof(InfoT));
1546         _hInfos = (InfoT*)(buf32+2);
1547
1548         buf += requiredSize;
1549         bufSize -= requiredSize;
1550
1551         return nullptr;
1552     }
1553
1554     void update(ContentAccessor* cache, const macho_header<P>* mh, CacheBuilder::ASLR_Tracker& aslrTracker) {
1555         InfoT* hi = new(&_hInfos[_count++]) InfoT(cache, mh);
1556         (void)hi;
1557     }
1558
1559     InfoT* hinfoForHeader(ContentAccessor* cache, const macho_header<P>* mh) {
1560         // FIXME: could be binary search
1561         uint64_t mh_vmaddr = cache->vmAddrForContent((void*)mh);
1562         for (size_t i = 0; i < _count; i++) {
1563             InfoT* hi = &_hInfos[i];
1564             if (hi->header_vmaddr(cache) == mh_vmaddr) return hi;
1565         }
1566         return nullptr;
1567     }
1568 private:
1569     InfoT*                    _hInfos;
1570     size_t                    _count;
1571 };