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 // iterate an entsize-based list
  30 // typedef entsize_iterator<P, type_t<P>, type_list_t<P> > type_iterator;
  31 template <typename P, typename T, typename Tlist>
  32 struct entsize_iterator {
  33     uint32_t entsize;
  34     uint32_t index;  // keeping track of this saves a divide in operator-
  35     T* current;
  36
  37     typedef std::random_access_iterator_tag iterator_category;
  38     typedef T value_type;
  39     typedef ptrdiff_t difference_type;
  40     typedef T* pointer;
  41     typedef T& reference;
  42
  43     entsize_iterator() { }
  44
  45     entsize_iterator(const Tlist& list, uint32_t start = 0)
  46         : entsize(list.getEntsize()), index(start), current(&list.get(start))
  47     { }
  48
  49     const entsize_iterator<P,T,Tlist>& operator += (ptrdiff_t count) {
  50         current = (T*)((uint8_t *)current + count*entsize);
  51         index += count;
  52         return *this;
  53     }
  54     const entsize_iterator<P,T,Tlist>& operator -= (ptrdiff_t count) {
  55         current = (T*)((uint8_t *)current - count*entsize);
  56         index -= count;
  57         return *this;
  58     }
  59     const entsize_iterator<P,T,Tlist> operator + (ptrdiff_t count) const {
  60         return entsize_iterator(*this) += count;
  61     }
  62     const entsize_iterator<P,T,Tlist> operator - (ptrdiff_t count) const {
  63         return entsize_iterator(*this) -= count;
  64     }
  65
  66     entsize_iterator<P,T,Tlist>& operator ++ () { *this += 1; return *this; }
  67     entsize_iterator<P,T,Tlist>& operator -- () { *this -= 1; return *this; }
  68     entsize_iterator<P,T,Tlist> operator ++ (int) {
  69         entsize_iterator<P,T,Tlist> result(*this); *this += 1; return result;
  70     }
  71     entsize_iterator<P,T,Tlist> operator -- (int) {
  72         entsize_iterator<P,T,Tlist> result(*this); *this -= 1; return result;
  73     }
  74
  75     ptrdiff_t operator - (const entsize_iterator<P,T,Tlist>& rhs) const {
  76         return (ptrdiff_t)this->index - (ptrdiff_t)rhs.index;
  77     }
  78
  79     T& operator * () { return *current; }
  80     T& operator * () const { return *current; }
  81     T& operator -> () { return *current; }
  82     const T& operator -> () const { return *current; }
  83
  84     operator T& () const { return *current; }
  85
  86     bool operator == (const entsize_iterator<P,T,Tlist>& rhs) {
  87         return this->current == rhs.current;
  88     }
  89     bool operator != (const entsize_iterator<P,T,Tlist>& rhs) {
  90         return this->current != rhs.current;
  91     }
  92
  93     bool operator < (const entsize_iterator<P,T,Tlist>& rhs) {
  94         return this->current < rhs.current;
  95     }
  96     bool operator > (const entsize_iterator<P,T,Tlist>& rhs) {
  97         return this->current > rhs.current;
  98     }
  99
 100
 101     static void overwrite(entsize_iterator<P,T,Tlist>& dst, const Tlist* srcList)
 102     {
 103         entsize_iterator<P,T,Tlist> src;
 104         uint32_t ee = srcList->getEntsize();
 105         for (src = srcList->begin(); src != srcList->end(); ++src) {
 106             memcpy(&*dst, &*src, ee);
 107             ++dst;
 108         }
 109     }
 110 };
 111
 112 template <typename P>
 113 class objc_header_info_rw_t {
 114
 115     typedef typename P::uint_t pint_t;
 116
 117     pint_t data;   // loaded:1, allRealised:1, objc_header_info *:ptr
 118
 119 public:
 120     objc_header_info_rw_t(ContentAccessor* cache, const macho_header<P>* mh)
 121         : data(0) {
 122     }
 123 };
 124
 125 template <typename P>
 126 class objc_header_info_ro_t {
 127
 128     typedef typename P::uint_t pint_t;
 129
 130     pint_t mhdr_offset;     // offset to mach_header or mach_header_64
 131     pint_t info_offset;     // offset to objc_image_info *
 132
 133 public:
 134     objc_header_info_ro_t(ContentAccessor* cache, const macho_header<P>* mh)
 135         : mhdr_offset(0), info_offset(0) {
 136         P::setP(mhdr_offset, (uint64_t)cache->vmAddrForContent((void*)mh) - (uint64_t)cache->vmAddrForContent(&mhdr_offset));
 137         assert(header_vmaddr(cache) == (uint64_t)cache->vmAddrForContent((void*)mh));
 138         const macho_section<P>* sect = mh->getSection("__DATA", "__objc_imageinfo");
 139         if (sect) {
 140             P::setP(info_offset, (uint64_t)sect->addr() - (uint64_t)cache->vmAddrForContent(&info_offset));
 141             // set bit in mach_header.flags to tell dyld that this image has objc content
 142             macho_header<P>* rwmh = const_cast<macho_header<P>*>(mh);
 143             rwmh->set_flags(mh->flags() | MH_HAS_OBJC);
 144         }
 145         else
 146             P::setP(info_offset, - (uint64_t)cache->vmAddrForContent(&info_offset));
 147     }
 148
 149     pint_t header_vmaddr(ContentAccessor* cache) const {
 150         return (pint_t)(((uint64_t)cache->vmAddrForContent(&mhdr_offset)) + mhdr_offset);
 151     }
 152 };
 153
 154
 155 template <typename P>
 156 class objc_method_list_t;  // forward reference
 157
 158
 159 template <typename P>
 160 class objc_method_t {
 161     typedef typename P::uint_t pint_t;
 162     pint_t name;   // SEL
 163     pint_t types;  // const char *
 164     pint_t imp;    // IMP
 165     friend class objc_method_list_t<P>;
 166 public:
 167     pint_t getName() const { return (pint_t)P::getP(name); }
 168     void setName(pint_t newName) { P::setP(name, newName); }
 169
 170     struct SortBySELAddress :
 171         public std::binary_function<const objc_method_t<P>&,
 172                                     const objc_method_t<P>&, bool>
 173     {
 174         bool operator() (const objc_method_t<P>& lhs,
 175                          const objc_method_t<P>& rhs)
 176         {
 177             return lhs.getName() < rhs.getName();
 178         }
 179     };
 180 };
 181
 182 template <typename P>
 183 class objc_method_list_t {
 184     uint32_t entsize;
 185     uint32_t count;
 186     objc_method_t<P> first;
 187
 188     void* operator new (size_t, void* buf) { return buf; }
 189
 190 public:
 191
 192     typedef entsize_iterator<P, objc_method_t<P>, objc_method_list_t<P> > method_iterator;
 193
 194     uint32_t getCount() const { return P::E::get32(count); }
 195
 196     uint32_t getEntsize() const {return P::E::get32(entsize)&~(uint32_t)3;}
 197
 198     objc_method_t<P>& get(uint32_t i) const { return *(objc_method_t<P> *)((uint8_t *)&first + i * getEntsize()); }
 199
 200     uint32_t byteSize() const {
 201         return byteSizeForCount(getCount(), getEntsize());
 202     }
 203
 204     static uint32_t byteSizeForCount(uint32_t c, uint32_t e = sizeof(objc_method_t<P>)) {
 205         return sizeof(objc_method_list_t<P>) - sizeof(objc_method_t<P>) + c*e;
 206     }
 207
 208     method_iterator begin() { return method_iterator(*this, 0); }
 209     method_iterator end() { return method_iterator(*this, getCount()); }
 210     const method_iterator begin() const { return method_iterator(*this, 0); }
 211     const method_iterator end() const { return method_iterator(*this, getCount()); }
 212
 213     void setFixedUp() { P::E::set32(entsize, getEntsize() | 3); }
 214
 215     void getPointers(std::set<void*>& pointersToRemove) {
 216         for(method_iterator it = begin(); it != end(); ++it) {
 217             objc_method_t<P>& entry = *it;
 218             pointersToRemove.insert(&(entry.name));
 219             pointersToRemove.insert(&(entry.types));
 220             pointersToRemove.insert(&(entry.imp));
 221         }
 222     }
 223
 224     static void addPointers(uint8_t* methodList, CacheBuilder::ASLR_Tracker& aslrTracker) {
 225         objc_method_list_t<P>* mlist = (objc_method_list_t<P>*)methodList;
 226         for(method_iterator it = mlist->begin(); it != mlist->end(); ++it) {
 227             objc_method_t<P>& entry = *it;
 228             aslrTracker.add(&(entry.name));
 229             aslrTracker.add(&(entry.types));
 230             aslrTracker.add(&(entry.imp));
 231         }
 232     }
 233
 234     static objc_method_list_t<P>* newMethodList(size_t newCount, uint32_t newEntsize) {
 235         void *buf = ::calloc(byteSizeForCount(newCount, newEntsize), 1);
 236         return new (buf) objc_method_list_t<P>(newCount, newEntsize);
 237     }
 238
 239     void operator delete(void * p) {
 240         ::free(p);
 241     }
 242
 243     objc_method_list_t(uint32_t newCount,
 244                        uint32_t newEntsize = sizeof(objc_method_t<P>))
 245         : entsize(newEntsize), count(newCount)
 246     { }
 247
 248 private:
 249     // use newMethodList instead
 250     void* operator new (size_t);
 251 };
 252
 253
 254 template <typename P>
 255 class objc_ivar_t {
 256     typedef typename P::uint_t pint_t;
 257
 258     pint_t                    offset;  // uint32_t*  (uint64_t* on x86_64)
 259     pint_t                    name;    // const char*
 260     pint_t                    type;    // const char*
 261     uint32_t                alignment;
 262     uint32_t                size;
 263
 264 public:
 265     const char* getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 266
 267     bool hasOffset() const { return offset != 0; }
 268     uint32_t getOffset(ContentAccessor* cache) const { return P::E::get32(*(uint32_t*)(cache->contentForVMAddr(P::getP(offset)))); }
 269     void setOffset(ContentAccessor* cache, uint32_t newOffset) { P::E::set32(*(uint32_t*)(cache->contentForVMAddr(P::getP(offset))), newOffset); }
 270
 271
 272     uint32_t getAlignment() {
 273         uint32_t a = P::E::get32(alignment);
 274         return (a == (uint32_t)-1) ? sizeof(pint_t) : 1<<a;
 275     }
 276 };
 277
 278 template <typename P>
 279 class objc_ivar_list_t {
 280     typedef typename P::uint_t pint_t;
 281     uint32_t entsize;
 282     uint32_t count;
 283     objc_ivar_t<P> first;
 284
 285     void* operator new (size_t, void* buf) { return buf; }
 286
 287 public:
 288
 289     typedef entsize_iterator<P, objc_ivar_t<P>, objc_ivar_list_t<P> > ivar_iterator;
 290
 291     uint32_t getCount() const { return P::E::get32(count); }
 292
 293     uint32_t getEntsize() const { return P::E::get32(entsize); }
 294
 295     objc_ivar_t<P>& get(pint_t i) const { return *(objc_ivar_t<P> *)((uint8_t *)&first + i * P::E::get32(entsize)); }
 296
 297     uint32_t byteSize() const {
 298         return byteSizeForCount(getCount(), getEntsize());
 299     }
 300
 301     static uint32_t byteSizeForCount(uint32_t c, uint32_t e = sizeof(objc_ivar_t<P>)) {
 302         return sizeof(objc_ivar_list_t<P>) - sizeof(objc_ivar_t<P>) + c*e;
 303     }
 304
 305     ivar_iterator begin() { return ivar_iterator(*this, 0); }
 306     ivar_iterator end() { return ivar_iterator(*this, getCount()); }
 307     const ivar_iterator begin() const { return ivar_iterator(*this, 0); }
 308     const ivar_iterator end() const { return ivar_iterator(*this, getCount()); }
 309
 310     static objc_ivar_list_t<P>* newIvarList(size_t newCount, uint32_t newEntsize) {
 311         void *buf = ::calloc(byteSizeForCount(newCount, newEntsize), 1);
 312         return new (buf) objc_ivar_list_t<P>(newCount, newEntsize);
 313     }
 314
 315     void operator delete(void * p) {
 316         ::free(p);
 317     }
 318
 319     objc_ivar_list_t(uint32_t newCount,
 320                          uint32_t newEntsize = sizeof(objc_ivar_t<P>))
 321         : entsize(newEntsize), count(newCount)
 322     { }
 323 private:
 324     // use newIvarList instead
 325     void* operator new (size_t);
 326 };
 327
 328
 329 template <typename P> class objc_property_list_t; // forward
 330
 331 template <typename P>
 332 class objc_property_t {
 333     typedef typename P::uint_t pint_t;
 334     pint_t name;
 335     pint_t attributes;
 336     friend class objc_property_list_t<P>;
 337 public:
 338
 339     const char * getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 340
 341     const char * getAttributes(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(attributes)); }
 342 };
 343
 344 template <typename P>
 345 class objc_property_list_t {
 346     uint32_t entsize;
 347     uint32_t count;
 348     objc_property_t<P> first;
 349
 350     void* operator new (size_t, void* buf) { return buf; }
 351
 352 public:
 353
 354     typedef entsize_iterator<P, objc_property_t<P>, objc_property_list_t<P> > property_iterator;
 355
 356     uint32_t getCount() const { return P::E::get32(count); }
 357
 358     uint32_t getEntsize() const { return P::E::get32(entsize); }
 359
 360     objc_property_t<P>& get(uint32_t i) const { return *(objc_property_t<P> *)((uint8_t *)&first + i * getEntsize()); }
 361
 362     uint32_t byteSize() const {
 363         return byteSizeForCount(getCount(), getEntsize());
 364     }
 365
 366     static uint32_t byteSizeForCount(uint32_t c, uint32_t e = sizeof(objc_property_t<P>)) {
 367         return sizeof(objc_property_list_t<P>) - sizeof(objc_property_t<P>) + c*e;
 368     }
 369
 370     property_iterator begin() { return property_iterator(*this, 0); }
 371     property_iterator end() { return property_iterator(*this, getCount()); }
 372     const property_iterator begin() const { return property_iterator(*this, 0); }
 373     const property_iterator end() const { return property_iterator(*this, getCount()); }
 374
 375     void getPointers(std::set<void*>& pointersToRemove) {
 376         for(property_iterator it = begin(); it != end(); ++it) {
 377             objc_property_t<P>& entry = *it;
 378             pointersToRemove.insert(&(entry.name));
 379             pointersToRemove.insert(&(entry.attributes));
 380         }
 381     }
 382
 383     static void addPointers(uint8_t* propertyList, CacheBuilder::ASLR_Tracker& aslrTracker) {
 384         objc_property_list_t<P>* plist = (objc_property_list_t<P>*)propertyList;
 385         for(property_iterator it = plist->begin(); it != plist->end(); ++it) {
 386             objc_property_t<P>& entry = *it;
 387             aslrTracker.add(&(entry.name));
 388             aslrTracker.add(&(entry.attributes));
 389         }
 390     }
 391
 392      static objc_property_list_t<P>* newPropertyList(size_t newCount, uint32_t newEntsize) {
 393         void *buf = ::calloc(byteSizeForCount(newCount, newEntsize), 1);
 394         return new (buf) objc_property_list_t<P>(newCount, newEntsize);
 395     }
 396
 397     void operator delete(void * p) {
 398         ::free(p);
 399     }
 400
 401     objc_property_list_t(uint32_t newCount,
 402                          uint32_t newEntsize = sizeof(objc_property_t<P>))
 403         : entsize(newEntsize), count(newCount)
 404     { }
 405 private:
 406     // use newPropertyList instead
 407     void* operator new (size_t);
 408 };
 409
 410
 411 template <typename A> class objc_protocol_list_t;  // forward reference
 412
 413 template <typename P>
 414 class objc_protocol_t {
 415     typedef typename P::uint_t pint_t;
 416
 417     pint_t isa;
 418     pint_t name;
 419     pint_t protocols;
 420     pint_t instanceMethods;
 421     pint_t classMethods;
 422     pint_t optionalInstanceMethods;
 423     pint_t optionalClassMethods;
 424     pint_t instanceProperties;
 425     uint32_t size;
 426     uint32_t flags;
 427     pint_t extendedMethodTypes;
 428     pint_t demangledName;
 429     pint_t classProperties;
 430
 431 public:
 432     pint_t getIsaVMAddr() const { return (pint_t)P::getP(isa); }
 433     void setIsaVMAddr(pint_t newIsa) { P::setP(isa, newIsa); }
 434
 435     const char *getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 436
 437     uint32_t getSize() const { return P::E::get32(size); }
 438     void setSize(uint32_t newSize) { P::E::set32(size, newSize); }
 439
 440     uint32_t getFlags() const { return P::E::get32(flags); }
 441
 442     void setFixedUp() { P::E::set32(flags, getFlags() | (1<<30)); }
 443
 444     objc_protocol_list_t<P> *getProtocols(ContentAccessor* cache) const { return (objc_protocol_list_t<P> *)cache->contentForVMAddr(P::getP(protocols)); }
 445
 446     objc_method_list_t<P> *getInstanceMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(instanceMethods)); }
 447
 448     objc_method_list_t<P> *getClassMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(classMethods)); }
 449
 450     objc_method_list_t<P> *getOptionalInstanceMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(optionalInstanceMethods)); }
 451
 452     objc_method_list_t<P> *getOptionalClassMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(optionalClassMethods)); }
 453
 454     objc_property_list_t<P> *getInstanceProperties(ContentAccessor* cache) const { return (objc_property_list_t<P> *)cache->contentForVMAddr(P::getP(instanceProperties)); }
 455
 456     pint_t *getExtendedMethodTypes(ContentAccessor* cache) const {
 457         if (getSize() < offsetof(objc_protocol_t<P>, extendedMethodTypes) + sizeof(extendedMethodTypes)) {
 458             return NULL;
 459         }
 460         return (pint_t *)cache->contentForVMAddr(P::getP(extendedMethodTypes));
 461     }
 462
 463     const char *getDemangledName(ContentAccessor* cache) const {
 464         if (sizeof(*this) < offsetof(objc_protocol_t<P>, demangledName) + sizeof(demangledName)) {
 465             return NULL;
 466         }
 467         return (const char *)cache->contentForVMAddr(P::getP(demangledName));
 468     }
 469
 470     void setDemangledName(ContentAccessor* cache, const char *newName, Diagnostics& diag) {
 471         if (sizeof(*this) < offsetof(objc_protocol_t<P>, demangledName) + sizeof(demangledName))
 472             diag.error("objc protocol has the wrong size");
 473         else
 474             P::setP(demangledName, cache->vmAddrForContent((void*)newName));
 475     }
 476
 477     void addPointers(ContentAccessor* cache, CacheBuilder::ASLR_Tracker& aslrTracker)
 478     {
 479         aslrTracker.add(&isa);
 480         aslrTracker.add(&name);
 481         if (protocols)               aslrTracker.add(&protocols);
 482         if (instanceMethods)         aslrTracker.add(&instanceMethods);
 483         if (classMethods)            aslrTracker.add(&classMethods);
 484         if (optionalInstanceMethods) aslrTracker.add(&optionalInstanceMethods);
 485         if (optionalClassMethods)    aslrTracker.add(&optionalClassMethods);
 486         if (instanceProperties)      aslrTracker.add(&instanceProperties);
 487         if (extendedMethodTypes)     aslrTracker.add(&extendedMethodTypes);
 488         if (demangledName)           aslrTracker.add(&demangledName);
 489     }
 490 };
 491
 492
 493 template <typename P>
 494 class objc_protocol_list_t {
 495     typedef typename P::uint_t pint_t;
 496     pint_t count;
 497     pint_t list[0];
 498
 499     void* operator new (size_t, void* buf) { return buf; }
 500
 501 public:
 502
 503     pint_t getCount() const { return (pint_t)P::getP(count); }
 504
 505     pint_t getVMAddress(pint_t i) {
 506         return (pint_t)P::getP(list[i]);
 507     }
 508
 509     objc_protocol_t<P>* get(ContentAccessor* cache, pint_t i) {
 510         return (objc_protocol_t<P>*)cache->contentForVMAddr(getVMAddress(i));
 511     }
 512
 513     void setVMAddress(pint_t i, pint_t protoVMAddr) {
 514         P::setP(list[i], protoVMAddr);
 515     }
 516
 517     void set(ContentAccessor* cache, pint_t i, objc_protocol_t<P>* proto) {
 518         setVMAddress(i, cache->vmAddrForContent(proto));
 519     }
 520
 521     uint32_t byteSize() const {
 522         return byteSizeForCount(getCount());
 523     }
 524     static uint32_t byteSizeForCount(pint_t c) {
 525         return sizeof(objc_protocol_list_t<P>) + c*sizeof(pint_t);
 526     }
 527
 528     void getPointers(std::set<void*>& pointersToRemove) {
 529         for(int i=0 ; i < count; ++i) {
 530             pointersToRemove.insert(&list[i]);
 531         }
 532     }
 533
 534      static void addPointers(uint8_t* protocolList, CacheBuilder::ASLR_Tracker& aslrTracker) {
 535         objc_protocol_list_t<P>* plist = (objc_protocol_list_t<P>*)protocolList;
 536         for(int i=0 ; i < plist->count; ++i) {
 537             aslrTracker.add(&plist->list[i]);
 538         }
 539     }
 540
 541     static objc_protocol_list_t<P>* newProtocolList(pint_t newCount) {
 542         void *buf = ::calloc(byteSizeForCount(newCount), 1);
 543         return new (buf) objc_protocol_list_t<P>(newCount);
 544     }
 545
 546     void operator delete(void * p) {
 547         ::free(p);
 548     }
 549
 550     objc_protocol_list_t(uint32_t newCount) : count(newCount) { }
 551 private:
 552     // use newProtocolList instead
 553     void* operator new (size_t);
 554 };
 555
 556
 557 template <typename P>
 558 class objc_class_data_t {
 559     typedef typename P::uint_t pint_t;
 560     uint32_t flags;
 561     uint32_t instanceStart;
 562     // Note there is 4-bytes of alignment padding between instanceSize and ivarLayout
 563     // on 64-bit archs, but no padding on 32-bit archs.
 564     // This union is a way to model that.
 565     union {
 566         uint32_t                instanceSize;
 567         pint_t   pad;
 568     } instanceSize;
 569     pint_t ivarLayout;
 570     pint_t name;
 571     pint_t baseMethods;
 572     pint_t baseProtocols;
 573     pint_t ivars;
 574     pint_t weakIvarLayout;
 575     pint_t baseProperties;
 576
 577 public:
 578     bool isMetaClass() { return P::E::get32(flags) & (1 << 0); }
 579     bool isRootClass() { return P::E::get32(flags) & (1 << 1); }
 580
 581     uint32_t getInstanceStart() { return P::E::get32(instanceStart); }
 582     void setInstanceStart(uint32_t newStart) { P::E::set32(instanceStart, newStart); }
 583
 584     uint32_t getInstanceSize() { return P::E::get32(instanceSize.instanceSize); }
 585     void setInstanceSize(uint32_t newSiz) { P::E::set32(instanceSize.instanceSize, newSiz); }
 586
 587     objc_method_list_t<P> *getMethodList(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(baseMethods)); }
 588
 589     objc_protocol_list_t<P> *getProtocolList(ContentAccessor* cache) const { return (objc_protocol_list_t<P> *)cache->contentForVMAddr(P::getP(baseProtocols)); }
 590
 591     objc_ivar_list_t<P> *getIvarList(ContentAccessor* cache) const { return (objc_ivar_list_t<P> *)cache->contentForVMAddr(P::getP(ivars)); }
 592
 593     objc_property_list_t<P> *getPropertyList(ContentAccessor* cache) const { return (objc_property_list_t<P> *)cache->contentForVMAddr(P::getP(baseProperties)); }
 594
 595     const char * getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 596
 597     void setMethodList(ContentAccessor* cache, objc_method_list_t<P>* mlist) {
 598         P::setP(baseMethods, cache->vmAddrForContent(mlist));
 599     }
 600
 601     void setProtocolList(ContentAccessor* cache, objc_protocol_list_t<P>* protolist) {
 602         P::setP(baseProtocols, cache->vmAddrForContent(protolist));
 603     }
 604
 605     void setPropertyList(ContentAccessor* cache, objc_property_list_t<P>* proplist) {
 606         P::setP(baseProperties, cache->vmAddrForContent(proplist));
 607     }
 608
 609     void addMethodListPointer(CacheBuilder::ASLR_Tracker& aslrTracker) {
 610         aslrTracker.add(&this->baseMethods);
 611     }
 612
 613     void addPropertyListPointer(CacheBuilder::ASLR_Tracker& aslrTracker) {
 614         aslrTracker.add(&this->baseProperties);
 615     }
 616
 617     void addProtocolListPointer(CacheBuilder::ASLR_Tracker& aslrTracker) {
 618         aslrTracker.add(&this->baseProtocols);
 619     }
 620 };
 621
 622 template <typename P>
 623 class objc_class_t {
 624     typedef typename P::uint_t pint_t;
 625
 626     pint_t isa;
 627     pint_t superclass;
 628     pint_t method_cache;
 629     pint_t vtable;
 630     pint_t data;
 631
 632 public:
 633     bool isMetaClass(ContentAccessor* cache) const { return getData(cache)->isMetaClass(); }
 634     bool isRootClass(ContentAccessor* cache) const { return getData(cache)->isRootClass(); }
 635
 636     objc_class_t<P> *getIsa(ContentAccessor* cache) const { return (objc_class_t<P> *)cache->contentForVMAddr(P::getP(isa)); }
 637
 638     objc_class_t<P> *getSuperclass(ContentAccessor* cache) const { return (objc_class_t<P> *)cache->contentForVMAddr(P::getP(superclass)); }
 639
 640     const pint_t* getSuperClassAddress() const { return &superclass; }
 641
 642     // Low bit marks Swift classes.
 643     objc_class_data_t<P> *getData(ContentAccessor* cache) const { return (objc_class_data_t<P> *)cache->contentForVMAddr(P::getP(data & ~0x3LL)); }
 644
 645     objc_method_list_t<P> *getMethodList(ContentAccessor* cache) const {
 646         objc_class_data_t<P>* d = getData(cache);
 647         return d->getMethodList(cache);
 648     }
 649
 650     objc_protocol_list_t<P> *getProtocolList(ContentAccessor* cache) const { return getData(cache)->getProtocolList(cache); }
 651
 652     objc_property_list_t<P> *getPropertyList(ContentAccessor* cache) const { return getData(cache)->getPropertyList(cache); }
 653
 654     const char* getName(ContentAccessor* cache) const {
 655         return getData(cache)->getName(cache);
 656     }
 657
 658     void setMethodList(ContentAccessor* cache, objc_method_list_t<P>* mlist) {
 659         getData(cache)->setMethodList(cache, mlist);
 660     }
 661
 662     void setProtocolList(ContentAccessor* cache, objc_protocol_list_t<P>* protolist) {
 663         getData(cache)->setProtocolList(cache, protolist);
 664     }
 665
 666     void setPropertyList(ContentAccessor* cache, objc_property_list_t<P>* proplist) {
 667         getData(cache)->setPropertyList(cache, proplist);
 668     }
 669
 670     void addMethodListPointer(ContentAccessor* cache, CacheBuilder::ASLR_Tracker& aslrTracker) {
 671         getData(cache)->addMethodListPointer(aslrTracker);
 672     }
 673
 674     void addPropertyListPointer(ContentAccessor* cache, CacheBuilder::ASLR_Tracker& aslrTracker) {
 675         getData(cache)->addPropertyListPointer(aslrTracker);
 676     }
 677
 678     void addProtocolListPointer(ContentAccessor* cache, CacheBuilder::ASLR_Tracker& aslrTracker) {
 679         getData(cache)->addProtocolListPointer(aslrTracker);
 680     }
 681
 682 };
 683
 684
 685
 686 template <typename P>
 687 class objc_category_t {
 688     typedef typename P::uint_t pint_t;
 689
 690     pint_t name;
 691     pint_t cls;
 692     pint_t instanceMethods;
 693     pint_t classMethods;
 694     pint_t protocols;
 695     pint_t instanceProperties;
 696
 697 public:
 698
 699     const char * getName(ContentAccessor* cache) const { return (const char *)cache->contentForVMAddr(P::getP(name)); }
 700
 701     objc_class_t<P> *getClass(ContentAccessor* cache) const { return (objc_class_t<P> *)cache->contentForVMAddr(P::getP(cls)); }
 702
 703     objc_method_list_t<P> *getInstanceMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(instanceMethods)); }
 704
 705     objc_method_list_t<P> *getClassMethods(ContentAccessor* cache) const { return (objc_method_list_t<P> *)cache->contentForVMAddr(P::getP(classMethods)); }
 706
 707     objc_protocol_list_t<P> *getProtocols(ContentAccessor* cache) const { return (objc_protocol_list_t<P> *)cache->contentForVMAddr(P::getP(protocols)); }
 708
 709     objc_property_list_t<P> *getInstanceProperties(ContentAccessor* cache) const { return (objc_property_list_t<P> *)cache->contentForVMAddr(P::getP(instanceProperties)); }
 710
 711     void getPointers(std::set<void*>& pointersToRemove) {
 712         pointersToRemove.insert(&name);
 713         pointersToRemove.insert(&cls);
 714         pointersToRemove.insert(&instanceMethods);
 715         pointersToRemove.insert(&classMethods);
 716         pointersToRemove.insert(&protocols);
 717         pointersToRemove.insert(&instanceProperties);
 718     }
 719
 720
 721 };
 722
 723 template <typename P>
 724 class objc_message_ref_t {
 725     typedef typename P::uint_t pint_t;
 726
 727     pint_t imp;
 728     pint_t sel;
 729
 730 public:
 731     pint_t getName() const { return (pint_t)P::getP(sel); }
 732
 733     void setName(pint_t newName) { P::setP(sel, newName); }
 734 };
 735
 736 // Call visitor.visitIvar() on every ivar in a given class.
 737 template <typename P, typename V>
 738 class IvarWalker {
 739     typedef typename P::uint_t pint_t;
 740     V& ivarVisitor;
 741 public:
 742
 743     IvarWalker(V& visitor) : ivarVisitor(visitor) { }
 744
 745     void walk(ContentAccessor* cache, const macho_header<P>* header, objc_class_t<P> *cls)
 746     {
 747         objc_class_data_t<P> *data = cls->getData(cache);
 748         objc_ivar_list_t<P> *ivars = data->getIvarList(cache);
 749         if (ivars) {
 750             for (pint_t i = 0; i < ivars->getCount(); i++) {
 751                 objc_ivar_t<P>& ivar = ivars->get(i);
 752                 //fprintf(stderr, "visiting ivar: %s\n", ivar.getName(cache));
 753                 ivarVisitor.visitIvar(cache, header, cls, &ivar);
 754             }
 755         } else {
 756             //fprintf(stderr, "no ivars\n");
 757         }
 758     }
 759
 760     void visitClass(ContentAccessor* cache, const macho_header<P>* header, objc_class_t<P> *cls)
 761     {
 762         walk(cache, header, cls);
 763     }
 764 };
 765
 766 // Call visitor.visitClass() on every class.
 767 template <typename P, typename V>
 768 class ClassWalker {
 769     typedef typename P::uint_t pint_t;
 770     V& _visitor;
 771 public:
 772
 773     ClassWalker(V& visitor) : _visitor(visitor) { }
 774
 775     void walk(ContentAccessor* cache, const macho_header<P>* header)
 776     {
 777         PointerSection<P, objc_class_t<P>*> classList(cache, header, "__DATA", "__objc_classlist");
 778
 779         for (pint_t i = 0; i < classList.count(); i++) {
 780             objc_class_t<P>* cls = classList.get(i);
 781             //fprintf(stderr, "visiting class: %s\n", cls->getName(cache));
 782             if (cls) _visitor.visitClass(cache, header, cls);
 783         }
 784     }
 785 };
 786
 787 // Call visitor.visitProtocol() on every protocol.
 788 template <typename P, typename V>
 789 class ProtocolWalker {
 790     typedef typename P::uint_t pint_t;
 791     V& _protocolVisitor;
 792 public:
 793
 794     ProtocolWalker(V& visitor) : _protocolVisitor(visitor) { }
 795
 796     void walk(ContentAccessor* cache, const macho_header<P>* header)
 797     {
 798         PointerSection<P, objc_protocol_t<P> *>
 799             protocols(cache, header, "__DATA", "__objc_protolist");
 800
 801         for (pint_t i = 0; i < protocols.count(); i++) {
 802             objc_protocol_t<P> *proto = protocols.get(i);
 803             _protocolVisitor.visitProtocol(cache, header, proto);
 804         }
 805     }
 806 };
 807
 808 // Call visitor.visitProtocolReference() on every protocol.
 809 template <typename P, typename V>
 810 class ProtocolReferenceWalker {
 811     typedef typename P::uint_t pint_t;
 812     V& _visitor;
 813
 814     void visitProtocolList(ContentAccessor* cache,
 815                            objc_protocol_list_t<P>* protolist)
 816     {
 817         if (!protolist) return;
 818         for (pint_t i = 0; i < protolist->getCount(); i++) {
 819             pint_t oldValue = protolist->getVMAddress(i);
 820             pint_t newValue = _visitor.visitProtocolReference(cache, oldValue);
 821             protolist->setVMAddress(i, newValue);
 822         }
 823     }
 824
 825     friend class ClassWalker<P, ProtocolReferenceWalker<P, V>>;
 826
 827     void visitClass(ContentAccessor* cache, const macho_header<P>*,
 828                     objc_class_t<P>* cls)
 829     {
 830         visitProtocolList(cache, cls->getProtocolList(cache));
 831         visitProtocolList(cache, cls->getIsa(cache)->getProtocolList(cache));
 832     }
 833
 834 public:
 835
 836     ProtocolReferenceWalker(V& visitor) : _visitor(visitor) { }
 837     void walk(ContentAccessor* cache, const macho_header<P>* header)
 838     {
 839         // @protocol expressions
 840         PointerSection<P, objc_protocol_t<P> *>
 841             protorefs(cache, header, "__DATA", "__objc_protorefs");
 842         for (pint_t i = 0; i < protorefs.count(); i++) {
 843             pint_t oldValue = protorefs.getVMAddress(i);
 844             pint_t newValue = _visitor.visitProtocolReference(cache, oldValue);
 845             protorefs.setVMAddress(i, newValue);
 846         }
 847
 848         // protocol lists in classes
 849         ClassWalker<P, ProtocolReferenceWalker<P, V>> classes(*this);
 850         classes.walk(cache, header);
 851
 852         // protocol lists in protocols
 853         // __objc_protolists itself is NOT updated
 854         PointerSection<P, objc_protocol_t<P> *>
 855             protocols(cache, header, "__DATA", "__objc_protolist");
 856         for (pint_t i = 0; i < protocols.count(); i++) {
 857             objc_protocol_t<P>* proto = protocols.get(i);
 858             visitProtocolList(cache, proto->getProtocols(cache));
 859             // not recursive: every old protocol object
 860             // must be in some protolist section somewhere
 861         }
 862     }
 863 };
 864
 865 // Call visitor.visitMethodList(mlist) on every
 866 // class and category method list in a header.
 867 // Call visitor.visitProtocolMethodList(mlist, typelist) on every
 868 // protocol method list in a header.
 869 template <typename P, typename V>
 870 class MethodListWalker {
 871
 872     typedef typename P::uint_t pint_t;
 873
 874     V& mVisitor;
 875
 876 public:
 877
 878     MethodListWalker(V& visitor) : mVisitor(visitor) { }
 879
 880     void walk(ContentAccessor* cache, const macho_header<P>* header)
 881     {
 882         // Method lists in classes
 883         PointerSection<P, objc_class_t<P> *>
 884             classes(cache, header, "__DATA", "__objc_classlist");
 885
 886         for (pint_t i = 0; i < classes.count(); i++) {
 887             objc_class_t<P> *cls = classes.get(i);
 888             objc_method_list_t<P> *mlist;
 889             if ((mlist = cls->getMethodList(cache))) {
 890                 mVisitor.visitMethodList(mlist);
 891             }
 892             if ((mlist = cls->getIsa(cache)->getMethodList(cache))) {
 893                 mVisitor.visitMethodList(mlist);
 894             }
 895         }
 896
 897         // Method lists from categories
 898         PointerSection<P, objc_category_t<P> *>
 899             cats(cache, header, "__DATA", "__objc_catlist");
 900         for (pint_t i = 0; i < cats.count(); i++) {
 901             objc_category_t<P> *cat = cats.get(i);
 902             objc_method_list_t<P> *mlist;
 903             if ((mlist = cat->getInstanceMethods(cache))) {
 904                 mVisitor.visitMethodList(mlist);
 905             }
 906             if ((mlist = cat->getClassMethods(cache))) {
 907                 mVisitor.visitMethodList(mlist);
 908             }
 909         }
 910
 911         // Method description lists from protocols
 912         PointerSection<P, objc_protocol_t<P> *>
 913             protocols(cache, header, "__DATA", "__objc_protolist");
 914         for (pint_t i = 0; i < protocols.count(); i++) {
 915             objc_protocol_t<P> *proto = protocols.get(i);
 916             objc_method_list_t<P> *mlist;
 917             pint_t *typelist = proto->getExtendedMethodTypes(cache);
 918
 919             if ((mlist = proto->getInstanceMethods(cache))) {
 920                 mVisitor.visitProtocolMethodList(mlist, typelist);
 921                 if (typelist) typelist += mlist->getCount();
 922             }
 923             if ((mlist = proto->getClassMethods(cache))) {
 924                 mVisitor.visitProtocolMethodList(mlist, typelist);
 925                 if (typelist) typelist += mlist->getCount();
 926             }
 927             if ((mlist = proto->getOptionalInstanceMethods(cache))) {
 928                 mVisitor.visitProtocolMethodList(mlist, typelist);
 929                 if (typelist) typelist += mlist->getCount();
 930             }
 931             if ((mlist = proto->getOptionalClassMethods(cache))) {
 932                 mVisitor.visitProtocolMethodList(mlist, typelist);
 933                 if (typelist) typelist += mlist->getCount();
 934             }
 935         }
 936     }
 937 };
 938
 939
 940 // Update selector references. The visitor performs recording and uniquing.
 941 template <typename P, typename V>
 942 class SelectorOptimizer {
 943
 944     typedef typename P::uint_t pint_t;
 945
 946     V& mVisitor;
 947
 948     std::set<pint_t> selectorRefVMAddrs;
 949
 950     friend class MethodListWalker<P, SelectorOptimizer<P,V> >;
 951     void visitMethodList(objc_method_list_t<P> *mlist)
 952     {
 953         // Gather selectors. Update method names.
 954         for (uint32_t m = 0; m < mlist->getCount(); m++) {
 955             pint_t oldValue = mlist->get(m).getName();
 956             pint_t newValue = mVisitor.visit(oldValue);
 957             mlist->get(m).setName(newValue);
 958         }
 959         // Do not setFixedUp: the methods are not yet sorted.
 960     }
 961
 962     void visitProtocolMethodList(objc_method_list_t<P> *mlist, pint_t *types)
 963     {
 964         visitMethodList(mlist);
 965     }
 966
 967 public:
 968
 969     SelectorOptimizer(V& visitor) : mVisitor(visitor) { }
 970
 971     void optimize(ContentAccessor* cache, const macho_header<P>* header)
 972     {
 973         // method lists in classes, categories, and protocols
 974         MethodListWalker<P, SelectorOptimizer<P,V> > mw(*this);
 975         mw.walk(cache, header);
 976
 977         // @selector references
 978         PointerSection<P, const char *>
 979             selrefs(cache, header, "__DATA", "__objc_selrefs");
 980         for (pint_t i = 0; i < selrefs.count(); i++) {
 981             pint_t oldValue = selrefs.getVMAddress(i);
 982             pint_t newValue = mVisitor.visit(oldValue);
 983             selrefs.setVMAddress(i, newValue);
 984             selectorRefVMAddrs.insert(selrefs.getSectionVMAddress() + (i * sizeof(pint_t)));
 985         }
 986
 987         // message references
 988         ArraySection<P, objc_message_ref_t<P> >
 989             msgrefs(cache, header, "__DATA", "__objc_msgrefs");
 990         for (pint_t i = 0; i < msgrefs.count(); i++) {
 991             objc_message_ref_t<P>& msg = msgrefs.get(i);
 992             pint_t oldValue = msg.getName();
 993             pint_t newValue = mVisitor.visit(oldValue);
 994             msg.setName(newValue);
 995         }
 996     }
 997
 998     bool isSelectorRefAddress(pint_t vmAddr) const {
 999         return selectorRefVMAddrs.count(vmAddr);
1000     }
1001 };
1002
1003
1004 // Update selector references. The visitor performs recording and uniquing.
1005 template <typename P>
1006 class IvarOffsetOptimizer {
1007     uint32_t    _slide;
1008     uint32_t    _maxAlignment;
1009     uint32_t    _optimized;
1010
1011 public:
1012
1013     IvarOffsetOptimizer() : _optimized(0) { }
1014
1015     size_t optimized() const { return _optimized; }
1016
1017     // dual purpose ivar visitor function
1018     // if slide!=0 then slides the ivar by that amount, otherwise computes _maxAlignment
1019     void visitIvar(ContentAccessor* cache, const macho_header<P>* /*unused, may be NULL*/, objc_class_t<P> *cls, objc_ivar_t<P> *ivar)
1020     {
1021         if (_slide == 0) {
1022             uint32_t alignment = ivar->getAlignment();
1023             if (alignment > _maxAlignment) _maxAlignment = alignment;
1024         } else {
1025             // skip anonymous bitfields
1026             if (ivar->hasOffset()) {
1027                 uint32_t oldOffset = (uint32_t)ivar->getOffset(cache);
1028                 ivar->setOffset(cache, oldOffset + _slide);
1029                 _optimized++;
1030                 //fprintf(stderr, "%d -> %d for %s.%s\n", oldOffset, oldOffset + _slide, cls->getName(cache), ivar->getName(cache));
1031             } else {
1032                 //fprintf(stderr, "NULL offset\n");
1033             }
1034         }
1035     }
1036
1037     // Class visitor function. Evaluates whether to slide ivars and performs slide if needed.
1038     // The slide algorithm is also implemented in objc. Any changes here should be reflected there also.
1039     void visitClass(ContentAccessor* cache, const macho_header<P>* /*unused, may be NULL*/, objc_class_t<P> *cls)
1040     {
1041         objc_class_t<P> *super = cls->getSuperclass(cache);
1042         if (super) {
1043             // Recursively visit superclasses to ensure we have the correct superclass start
1044             // Note that we don't need the macho_header, so just pass NULL.
1045             visitClass(cache, nullptr, super);
1046
1047             objc_class_data_t<P> *data = cls->getData(cache);
1048             objc_class_data_t<P> *super_data = super->getData(cache);
1049             int32_t diff = super_data->getInstanceSize() - data->getInstanceStart();
1050             if (diff > 0) {
1051                 IvarWalker<P, IvarOffsetOptimizer<P> > ivarVisitor(*this);
1052                 _maxAlignment = 1;
1053                 _slide = 0;
1054
1055                 // This walk computes _maxAlignment
1056                 ivarVisitor.walk(cache, nullptr, cls);
1057
1058                 // Compute a slide value that preserves that alignment
1059                 uint32_t alignMask = _maxAlignment - 1;
1060                 if (diff & alignMask) diff = (diff + alignMask) & ~alignMask;
1061
1062                 // Slide all of this class's ivars en masse
1063                 _slide = diff;
1064                 if (_slide != 0) {
1065                     //fprintf(stderr, "Sliding ivars in %s by %u (superclass was %d, now %d)\n", cls->getName(cache), _slide, data->getInstanceStart(), super_data->getInstanceSize());
1066                     ivarVisitor.walk(cache, nullptr, cls);
1067                     data->setInstanceStart(data->getInstanceStart() + _slide);
1068                     data->setInstanceSize(data->getInstanceSize() + _slide);
1069                 }
1070             }
1071         }
1072     }
1073
1074     // Enumerates objc classes in the module and performs any ivar slides
1075     void optimize(ContentAccessor* cache, const macho_header<P>* header)
1076     {
1077         // The slide code cannot fix up GC layout strings so skip modules that support or require GC
1078         const macho_section<P> *imageInfoSection = header->getSection("__DATA", "__objc_imageinfo");
1079         if (imageInfoSection) {
1080             objc_image_info<P> *info = (objc_image_info<P> *)cache->contentForVMAddr(imageInfoSection->addr());
1081             if (!info->supportsGCFlagSet() && !info->requiresGCFlagSet()) {
1082                 ClassWalker<P, IvarOffsetOptimizer<P> > classVisitor(*this);
1083                 classVisitor.walk(cache, header);
1084             } else {
1085                 //fprintf(stderr, "GC support present - skipped module\n");
1086             }
1087         }
1088     }
1089 };
1090
1091
1092 // Detect classes that have missing weak-import superclasses.
1093 template <typename P>
1094 class WeakClassDetector {
1095     bool                                noMissing;
1096     const std::map<void*, std::string>* missingWeakImports = nullptr;
1097
1098     friend class ClassWalker<P, WeakClassDetector<P>>;
1099     void visitClass(ContentAccessor* cache, const macho_header<P>*,
1100                     objc_class_t<P>* cls)
1101     {
1102         auto supercls = cls->getSuperclass(cache);
1103         if (supercls) {
1104             // okay: class with superclass
1105             // Note that the superclass itself might have a missing superclass.
1106             // That is fine for mere detection because we will visit the
1107             // superclass separately.
1108         } else if (cls->isRootClass(cache)) {
1109             // okay: root class is expected to have no superclass
1110         } else {
1111             // bad: cls's superclass is missing.
1112             // See if we can find the name from the missing weak import map
1113             auto it = missingWeakImports->find((void*)cls->getSuperClassAddress());
1114             const char* dylibName = "unknown dylib";
1115             if (it != missingWeakImports->end()) {
1116                 dylibName = it->second.c_str();
1117             }
1118             cache->diagnostics().warning("Superclass of class '%s' is weak-import and missing.  Expected in %s",
1119                                          cls->getName(cache), dylibName);
1120             noMissing = false;
1121         }
1122     }
1123
1124 public:
1125     bool noMissingWeakSuperclasses(ContentAccessor* cache,
1126                                    const std::map<void*, std::string>& missingWeakImportsMap,
1127                                    std::vector<const macho_header<P>*> dylibs)
1128     {
1129         noMissing           = true;
1130         missingWeakImports  = &missingWeakImportsMap;
1131         ClassWalker<P, WeakClassDetector<P>> classes(*this);
1132         for (auto mh : dylibs) {
1133             classes.walk(cache, mh);
1134         }
1135         return noMissing;
1136     }
1137 };
1138
1139
1140 // Sort methods in place by selector.
1141 template <typename P>
1142 class MethodListSorter {
1143
1144     typedef typename P::uint_t pint_t;
1145
1146     uint32_t _optimized;
1147
1148     friend class MethodListWalker<P, MethodListSorter<P> >;
1149     void visitMethodList(objc_method_list_t<P> *mlist)
1150     {
1151         typename objc_method_t<P>::SortBySELAddress sorter;
1152         std::stable_sort(mlist->begin(), mlist->end(), sorter);
1153         mlist->setFixedUp();
1154         _optimized++;
1155     }
1156
1157     void visitProtocolMethodList(objc_method_list_t<P> *mlist, pint_t *typelist)
1158     {
1159         typename objc_method_t<P>::SortBySELAddress sorter;
1160         // can't easily use std::stable_sort here
1161         for (uint32_t i = 0; i < mlist->getCount(); i++) {
1162             for (uint32_t j = i+1; j < mlist->getCount(); j++) {
1163                 objc_method_t<P>& mi = mlist->get(i);
1164                 objc_method_t<P>& mj = mlist->get(j);
1165                 if (! sorter(mi, mj)) {
1166                     std::swap(mi, mj);
1167                     if (typelist) std::swap(typelist[i], typelist[j]);
1168                 }
1169             }
1170         }
1171
1172         mlist->setFixedUp();
1173         _optimized++;
1174     }
1175
1176 public:
1177     MethodListSorter() : _optimized(0) { }
1178
1179     size_t optimized() const { return _optimized; }
1180
1181     void optimize(ContentAccessor* cache, const macho_header<P>* header)
1182     {
1183         MethodListWalker<P, MethodListSorter<P> > mw(*this);
1184         mw.walk(cache, header);
1185     }
1186 };
1187
1188
1189 template <typename P, typename InfoT>
1190 class HeaderInfoOptimizer {
1191 public:
1192
1193     typedef typename P::uint_t pint_t;
1194
1195     HeaderInfoOptimizer() : _hInfos(0), _count(0) { }
1196
1197     const char* init(uint32_t count, uint8_t*& buf, size_t& bufSize) {
1198         if (count == 0)
1199             return nullptr;
1200
1201         size_t requiredSize =
1202             2*sizeof(uint32_t) + count*sizeof(InfoT);
1203         if (bufSize < requiredSize) {
1204             return "libobjc's read/write section is too small (metadata not optimized)";
1205         }
1206
1207         uint32_t *buf32 = (uint32_t *)buf;
1208         P::E::set32(buf32[0], count);
1209         P::E::set32(buf32[1], sizeof(InfoT));
1210         _hInfos = (InfoT*)(buf32+2);
1211
1212         buf += requiredSize;
1213         bufSize -= requiredSize;
1214
1215         return nullptr;
1216     }
1217
1218     void update(ContentAccessor* cache, const macho_header<P>* mh, CacheBuilder::ASLR_Tracker& aslrTracker) {
1219         InfoT* hi = new(&_hInfos[_count++]) InfoT(cache, mh);
1220         (void)hi;
1221     }
1222
1223     InfoT* hinfoForHeader(ContentAccessor* cache, const macho_header<P>* mh) {
1224         // FIXME: could be binary search
1225         uint64_t mh_vmaddr = cache->vmAddrForContent((void*)mh);
1226         for (size_t i = 0; i < _count; i++) {
1227             InfoT* hi = &_hInfos[i];
1228             if (hi->header_vmaddr(cache) == mh_vmaddr) return hi;
1229         }
1230         return nullptr;
1231     }
1232 private:
1233     InfoT*                    _hInfos;
1234     size_t                    _count;
1235 };