Paste_Image.png

通過(guò)這張圖描述了實(shí)例對(duì)象，類，元類之間的關(guān)系；
圖中實(shí)線是 super_class 指針，虛線是 isa 指針。
從圖中看出：

• 當(dāng)發(fā)送一個(gè)實(shí)例方法的消息時(shí)，isa 指針會(huì)在這個(gè)類的實(shí)例方法列表中查找；
• 當(dāng)發(fā)送一個(gè)類方法的消息時(shí)，isa 指針會(huì)在這個(gè)類的 meta-class 的方法列表中查找，meta-class 之所以重要，是因?yàn)樗鎯?chǔ)著一個(gè)類的所有類方法。
• 每個(gè)類都會(huì)有一個(gè)單獨(dú)的 meta-class，因?yàn)槊總€(gè)類的類方法基本不可能完全相同。

image

[super class] 與 [self class] 的區(qū)別

@implementation Student

- (instancetype)init {
    self = [super init];
    if (self) {
        NSLog(@"%@", NSStringFromClass([self class]));
        NSLog(@"%@", NSStringFromClass([super class]));
    }
    return self;
}
@end

借助 clang 編譯器，會(huì)被編譯器轉(zhuǎn)化為：

static instancetype _I_Student_init(Student * self, SEL _cmd) {
 self = ((Student *(*)(__rw_objc_super *, SEL))(void *)objc_msgSendSuper)((__rw_objc_super){(id)self, (id)class_getSuperclass(objc_getClass("Student"))}, sel_registerName("init"));
 if (self) {
  id obj1 = ((Class (*)(id, SEL))(void *)objc_msgSend)((id)self, sel_registerName("class"));
  id obj2 = ((Class (*)(__rw_objc_super *, SEL))(void *)objc_msgSendSuper)((__rw_objc_super){(id)self, (id)class_getSuperclass(objc_getClass("Student"))}, sel_registerName("class"));
  NSLog((NSString *)&__NSConstantStringImpl__var_folders_hj_pwgsq9614nb0vq4zd315tcx80000gn_T_Student_e7cbc1_mi_0,obj1);
  NSLog((NSString *)&__NSConstantStringImpl__var_folders_hj_pwgsq9614nb0vq4zd315tcx80000gn_T_Student_e7cbc1_mi_1,obj2);
 }
 return self;
}

由此可見：
[self class] 編譯器最終轉(zhuǎn)成 objc_msgSend(self,@selector(class))，消息的接收者是當(dāng)前所在類的實(shí)例對(duì)象，這個(gè)時(shí)候就會(huì)去 self 所在類 Student 去查找 class 方法，如果當(dāng)前類 Student 沒有 class 會(huì)向 Student 父類 Person 類找 class 方法，如果 Person 類也沒有找到 class 方法，最終會(huì)找到最頂級(jí)父類 NSObject 的 class 方法，并調(diào)用了 object_getClass(self)，由于消息接收者是 self 當(dāng)前類實(shí)例對(duì)象，所以最終 [self class] 輸出 Student；

[super class] 最終編譯器轉(zhuǎn)化成了 objc_msgSendSuper(struct objc_super *,SEL)

OBJC_EXPORT void objc_msgSendSuper(void /* struct objc_super *super, SEL op, ... */ )

/// Specifies the superclass of an instance. 
struct objc_super {
    /// Specifies an instance of a class.
    __unsafe_unretained id receiver;

    /// Specifies the particular superclass of the instance to message. 
#if !defined(__cplusplus)  &&  !__OBJC2__
    /* For compatibility with old objc-runtime.h header */
    __unsafe_unretained Class class;
#else
    __unsafe_unretained Class super_class;
#endif
    /* super_class is the first class to search */
};

objc_super 是一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體里面有兩個(gè)指針，一個(gè)是接收消息的 receiver，另一個(gè)是指向當(dāng)前類的父類 super_class，通過(guò) super_class 指針從父類的方法列表開始查找 selector，由于消息接收者還是當(dāng)前類的實(shí)例對(duì)象 self，那么 objc_msgSendSuper 最后就轉(zhuǎn)變成，

objc_msgSend(objc_super->receiver, @selector(class))
- (Class)class {
    return object_getClass(self);
}

由于找到了父類 NSObject 里面的 class 方法的 IMP，又因?yàn)閭魅氲娜雲(yún)?objc_super->receiver = self。self 就是 Student，調(diào)用 class，所以父類的方法 class 執(zhí)行 IMP 之后，輸出還是 Student，最后輸出兩個(gè)都一樣，都是輸出 Student。

isMemberOfClass 和 isKindOfClass 的區(qū)別

+ (BOOL)isMemberOfClass:(Class)cls {
    return object_getClass((id)self) == cls;
}

- (BOOL)isMemberOfClass:(Class)cls {
    return [self class] == cls;
}

+ (BOOL)isKindOfClass:(Class)cls {
    for (Class tcls = object_getClass((id)self); tcls; tcls = tcls->superclass) {
        if (tcls == cls) return YES;
    }
    return NO;
}

- (BOOL)isKindOfClass:(Class)cls {
    for (Class tcls = [self class]; tcls; tcls = tcls->superclass) {
        if (tcls == cls) return YES;
    }
    return NO;
}

isKindOfClass：是判斷方法調(diào)用者對(duì)象的類是否等于傳入的這個(gè)類或者其子類；
isMemberOfClass：object_getClass() 取得的是對(duì)象的 isa 指針指向的對(duì)象，也就是判斷傳入的類對(duì)象的元類對(duì)象是否與傳入的這個(gè)對(duì)象相等，所以這個(gè) cls 應(yīng)該是元類對(duì)象才有可能相等，是檢測(cè)方法調(diào)用者對(duì)象的類是否等于傳入的這個(gè)類；

objc_getClass 和 object_getClass 的區(qū)別

Class _Nullable objc_getClass(const char * _Nonnull name)
const char * _Nonnull object_getClassName(id _Nullable obj)

• objc_getClass
objc_getClass 參數(shù)是類名的字符串，返回的就是這個(gè)類的類對(duì)象；

• object_getClass
object_getClass 參數(shù)是 id 類型，它返回的是這個(gè) id 的 isa 指針?biāo)赶虻?Class，如果是 instance 對(duì)象，返回 class 對(duì)象；如果是 class 對(duì)象，返回 meta-class 對(duì)象；如果是 meta-class 對(duì)象，返回 NSObject 的 meta-class 對(duì)象；

NSObject

@interface NSObject <NSObject> {
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wobjc-interface-ivars"
    Class isa  OBJC_ISA_AVAILABILITY;
#pragma clang diagnostic pop
}
typedef struct objc_class *Class;

萬(wàn)物皆對(duì)象，通過(guò)源碼分析，NSObject 里面包含一個(gè) objc_class 結(jié)構(gòu)體類型的 isa 指針；

isa_t

// Class、uintptr_t、結(jié)構(gòu)體公用一塊內(nèi)存空間，isa_t 是一個(gè) Class、同時(shí)是一個(gè) 64 位地址 bits、是一個(gè) 64 位結(jié)構(gòu)體。
union isa_t 
{
    isa_t() { }
    isa_t(uintptr_t value) : bits(value) { }

    Class cls;
    uintptr_t bits;

#if SUPPORT_PACKED_ISA

# if __arm64__
#   define ISA_MASK        0x0000000ffffffff8ULL
#   define ISA_MAGIC_MASK  0x000003f000000001ULL
#   define ISA_MAGIC_VALUE 0x000001a000000001ULL
    struct {
        uintptr_t nonpointer        : 1;
        uintptr_t has_assoc         : 1;
        uintptr_t has_cxx_dtor      : 1;
        uintptr_t shiftcls          : 33; // MACH_VM_MAX_ADDRESS 0x1000000000
        uintptr_t magic             : 6;
        uintptr_t weakly_referenced : 1;
        uintptr_t deallocating      : 1;
        uintptr_t has_sidetable_rc  : 1;
        uintptr_t extra_rc          : 19;
#       define RC_ONE   (1ULL<<45)
#       define RC_HALF  (1ULL<<18)
    };

# elif __x86_64__
#   define ISA_MASK        0x00007ffffffffff8ULL
#   define ISA_MAGIC_MASK  0x001f800000000001ULL
#   define ISA_MAGIC_VALUE 0x001d800000000001ULL
    struct {
        uintptr_t nonpointer        : 1;
        uintptr_t has_assoc         : 1;
        uintptr_t has_cxx_dtor      : 1;
        uintptr_t shiftcls          : 44; // MACH_VM_MAX_ADDRESS 0x7fffffe00000
        uintptr_t magic             : 6;
        uintptr_t weakly_referenced : 1;
        uintptr_t deallocating      : 1;
        uintptr_t has_sidetable_rc  : 1;
        uintptr_t extra_rc          : 8;
#       define RC_ONE   (1ULL<<56)
#       define RC_HALF  (1ULL<<7)
    };

# else
#   error unknown architecture for packed isa
# endif

// SUPPORT_PACKED_ISA
#endif

};

image

isa_t 是一個(gè) union 類型的結(jié)構(gòu)體，其中的 isa_t、cls、 bits 還有結(jié)構(gòu)體共用同一塊地址空間，而 isa 總共會(huì)占據(jù) 64 位的內(nèi)存空間。
詞語(yǔ)解析：
nonpointer：代表是否開啟 isa 指針優(yōu)化。nonpointer = 1，代表開啟 isa 指針優(yōu)化Tagged Pointer。
has_assoc：是否有設(shè)置過(guò)關(guān)聯(lián)對(duì)象，如果沒有，釋放時(shí)會(huì)更快。
has_cxx_dtor：是否有 C++ 或者 Objc 的析構(gòu)函數(shù)，如果沒有，釋放時(shí)會(huì)更快。
shiftcls：類指針，存儲(chǔ)著 Class、Meta-Class 對(duì)象的內(nèi)存地址信息，arm64 架構(gòu)中有 33 位可以存儲(chǔ)類指針，在 __x86_64__ 架構(gòu)中有 44 位可以存儲(chǔ)類指針。
magic：判斷對(duì)象是否初始化完成。
weakly_referenced：是否有被弱引用指向過(guò)，如果沒有，釋放時(shí)會(huì)更快。
deallocating：對(duì)象是否正在釋放。
has_sidetable_rc：判斷該對(duì)象的引用計(jì)數(shù)是否過(guò)大，如果過(guò)大則需要其他哈希表來(lái)進(jìn)行存儲(chǔ)。
extra_rc：存放該對(duì)象的引用計(jì)數(shù)值 -1 后的結(jié)果。對(duì)象的引用計(jì)數(shù)超過(guò) 1，會(huì)存在這個(gè)這個(gè)里面，如果引用計(jì)數(shù)為 10，extra_rc 的值就為 9。

注：本文提到的 nonpointer 等同于 indexed，在 objc 最新源碼已改名為 nonpointer。

isa 的初始化

inline void 
objc_object::initInstanceIsa(Class cls, bool hasCxxDtor)
{
    assert(!cls->instancesRequireRawIsa());
    assert(hasCxxDtor == cls->hasCxxDtor());

    initIsa(cls, true, hasCxxDtor);
}

inline void 
objc_object::initIsa(Class cls, bool nonpointer, bool hasCxxDtor) 
{ 
    assert(!isTaggedPointer()); 
    
    if (!nonpointer) {
        isa.cls = cls;
    } else {
        assert(!DisableNonpointerIsa);
        assert(!cls->instancesRequireRawIsa());

        isa_t newisa(0);

#if SUPPORT_INDEXED_ISA
        assert(cls->classArrayIndex() > 0);
        newisa.bits = ISA_INDEX_MAGIC_VALUE;
        // isa.magic is part of ISA_MAGIC_VALUE
        // isa.nonpointer is part of ISA_MAGIC_VALUE
        newisa.has_cxx_dtor = hasCxxDtor;
        newisa.indexcls = (uintptr_t)cls->classArrayIndex();
#else
        newisa.bits = ISA_MAGIC_VALUE;
        // isa.magic is part of ISA_MAGIC_VALUE
        // isa.nonpointer is part of ISA_MAGIC_VALUE
        newisa.has_cxx_dtor = hasCxxDtor;
        newisa.shiftcls = (uintptr_t)cls >> 3;
#endif
        isa = newisa;
    }
}

可以看到 nonpointer 是固定傳 true，因?yàn)楝F(xiàn)在 iOS 已經(jīng)遷移到 64 位系統(tǒng)了，也就是目前邏輯基本直走 else 分支，然后是 SUPPORT_INDEXED_ISA：

#if __ARM_ARCH_7K__ >= 2
#   define SUPPORT_INDEXED_ISA 1
#else
#   define SUPPORT_INDEXED_ISA 0
#endif

SUPPORT_INDEXED_ISA = 1 是另外一種優(yōu)化，用 isa 內(nèi) indexcls 存儲(chǔ)著類在類列表內(nèi)的索引，用于 apple watch 設(shè)備。

newisa.bits = ISA_MAGIC_VALUE

這里給 bits 賦初始，ISA_MAGIC_VALUE = 0x001d800000000001ULL，我們把它轉(zhuǎn)化成二進(jìn)制：

ISA_MAGIC_VALUE = 0x000001a000000001ULL轉(zhuǎn)換成二進(jìn)制是11010000000000000000000000000000000000001

image

isa.shiftcls = (uintptr_t)cls >> 3

將當(dāng)前地址右移三位的主要原因是用于將 Class 指針中無(wú)用的后三位清楚減小內(nèi)存的消耗，因?yàn)轭惖闹羔樢凑兆止?jié)（8 bits）對(duì)齊內(nèi)存，其指針后三位都是沒有意義的 0。

ISA_MASK 分別是通過(guò)掩碼的方式獲取 isa 的類指針。

inline Class 
objc_object::ISA() 
{
    assert(!isTaggedPointer()); 
    return (Class)(isa.bits & ISA_MASK);
}

Tagged Pointer

在2013年9月蘋果提出了 Tagged Pointer 的概念，對(duì)于64位程序，引入 Tagged Pointer 后，相關(guān)邏輯能減少一半的內(nèi)存占用，以及 3 倍的訪問(wèn)速度提升，100 倍的創(chuàng)建、銷毀速度提升。
例如，要存儲(chǔ)一個(gè) NSNumber 對(duì)象，其值是一個(gè)整數(shù)。正常情況下，如果這個(gè)整數(shù)只是一個(gè) NSInteger 的普通變量，那么它所占用的內(nèi)存是與 CPU 的位數(shù)有關(guān)，在 32 位 CPU 下占 4 個(gè)字節(jié)，在 64 位 CPU 下是占 8 個(gè)字節(jié)的。而指針類型的大小通常也是與 CPU 位數(shù)相關(guān)，一個(gè)指針?biāo)加玫膬?nèi)存在 32 位 CPU 下為 4 個(gè)字節(jié)，在 64 位 CPU 下也是 8 個(gè)字節(jié)。如果沒有Tagged Pointer對(duì)象，從 32 位機(jī)器遷移到 64 位機(jī)器中后，雖然邏輯沒有任何變化，但這種 NSNumber、NSDate 一類的對(duì)象所占用的內(nèi)存會(huì)翻倍。

image

為了改進(jìn)上面提到的內(nèi)存占用和效率問(wèn)題，蘋果提出了Tagged Pointer對(duì)象。由于 NSNumber、NSDate 一類的變量本身的值需要占用的內(nèi)存大小常常不需要 8 個(gè)字節(jié)，拿整數(shù)來(lái)說(shuō)，4 個(gè)字節(jié)所能表示的有符號(hào)整數(shù)就可以達(dá)到 20 多億（注：2^31=2147483648，另外 1 位作為符號(hào)位)，對(duì)于絕大多數(shù)情況都是可以處理的。

所以我們可以將一個(gè)對(duì)象的指針拆成兩部分，一部分直接保存數(shù)據(jù)，另一部分作為特殊標(biāo)記，表示這是一個(gè)特別的指針，不指向任何一個(gè)地址。所以，引入了Tagged Pointer對(duì)象之后，64 位 CPU 下 NSNumber 的內(nèi)存圖變成了以下這樣：

image

運(yùn)行之后，我們得到的結(jié)果如下，可以看到，除去最后的數(shù)字最末尾的 2 以及最開頭的 0xb，其它數(shù)字剛好表示了相應(yīng) NSNumber 的值。

2017-08-26 19:58:08.232 TaggedPointer[87063:1919845] number1 Tagged Pointer is 0xb000000000000072
2017-08-26 19:58:08.232 TaggedPointer[87063:1919845] number2 Tagged Pointer is 0xb0000000000006f2
2017-08-26 19:58:08.232 TaggedPointer[87063:1919845] number3 Tagged Pointer is 0xb0000000000022b2

嘗試放一個(gè) 8 字節(jié)的長(zhǎng)的整數(shù)到NSNumber實(shí)例中，對(duì)于這樣的實(shí)例，由于Tagged Pointer無(wú)法將其按上面的壓縮方式來(lái)保存，那么應(yīng)該就會(huì)以普通對(duì)象的方式來(lái)保存，我們的實(shí)驗(yàn)代碼如下：

2017-08-26 20:00:11.833 TaggedPointer[87122:1921799] number1 Tagged Pointer is 0xb000000000000072
2017-08-26 20:00:11.833 TaggedPointer[87122:1921799] number2 Tagged Pointer is 0xb0000000000006f2
2017-08-26 20:00:11.833 TaggedPointer[87122:1921799] number3 Tagged Pointer is 0xb0000000000022b2
2017-08-26 20:00:11.833 TaggedPointer[87122:1921799] bigNumber Tagged Pointer is 0x6100000251a0

運(yùn)行之后，結(jié)果如下，驗(yàn)證了我們的猜測(cè)，bigNumber的地址更像是一個(gè)普通的指針地址，和它本身的值看不出任何關(guān)系。

可見，當(dāng) 8 字節(jié)可以承載用于表示的數(shù)值時(shí)，系統(tǒng)就會(huì)以Tagged Pointer的方式生成指針，如果 8 字節(jié)承載不了時(shí)，則又用以前的方式來(lái)生成普通的指針。

蘋果引入Tagged Pointer，不但減少了 64 位機(jī)器下程序的內(nèi)存占用，還提高了運(yùn)行效率。完美地解決了小內(nèi)存對(duì)象在存儲(chǔ)和訪問(wèn)效率上的問(wèn)題。

objc_class

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags

    class_rw_t *data() { 
        return bits.data();
    }
}

class_rw_t* data() {
    return (class_rw_t *)(bits & FAST_DATA_MASK);
}

通過(guò)源碼分析：
objc_class 里面包含一個(gè) objc_class 結(jié)構(gòu)體類型的 superclass 指針，可以通過(guò) superclass 指針，查找到父類；
cache_t 結(jié)構(gòu)體的 cache 指針，cache 主要用于方法性能優(yōu)化，對(duì)使用過(guò)的方法進(jìn)行緩存，便于第二次查找；
class_data_bits_t 結(jié)構(gòu)體的 bits 指針，只含有一個(gè) 64 位的 bits 用于存儲(chǔ)與類有關(guān)的信息；

在 objc_class 結(jié)構(gòu)體中的注釋寫到 class_data_bits_t 相當(dāng)于 class_rw_t 指針加上 rr/alloc 的標(biāo)志。

通過(guò)將 bits 與 FAST_DATA_MASK 進(jìn)行位運(yùn)算，返回 class_rw_t * 指針，其中 Objc 的類的屬性、方法、以及遵循的協(xié)議都放在 class_rw_t 結(jié)構(gòu)體中；

cache_t

struct cache_t {
    struct bucket_t *_buckets;
    mask_t _mask;
    mask_t _occupied;

public:
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();

    mask_t capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

    static size_t bytesForCapacity(uint32_t cap);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);

    void expand();
    void reallocate(mask_t oldCapacity, mask_t newCapacity);
    struct bucket_t * find(cache_key_t key, id receiver);

    static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn));
};

struct bucket_t {
private:
    cache_key_t _key;
    IMP _imp;

public:
    inline cache_key_t key() const { return _key; }
    inline IMP imp() const { return (IMP)_imp; }
    inline void setKey(cache_key_t newKey) { _key = newKey; }
    inline void setImp(IMP newImp) { _imp = newImp; }

    void set(cache_key_t newKey, IMP newImp);
};

cache 主要是為了優(yōu)化方法調(diào)用的性能，一個(gè)接收者對(duì)象接收到一個(gè)消息時(shí)，它會(huì)根據(jù) isa 指針去查找能夠響應(yīng)這個(gè)消息的對(duì)象。在實(shí)際使用中，這個(gè)對(duì)象只有一部分方法是常用的，很多方法其實(shí)很少用或者根本用不上。這種情況下，如果每次消息來(lái)時(shí)，我們都是 methodLists 中遍歷一遍，性能勢(shì)必很差。這時(shí)，cache 就派上用場(chǎng)了。在我們每次調(diào)用過(guò)一個(gè)方法后，這個(gè)方法就會(huì)被緩存到 cache 列表中，下次調(diào)用的時(shí)候就會(huì)優(yōu)先去 cache 中查找，才去 methodLists 中查找方法。

從源碼中可以看出，
_buckets 指針是一個(gè)指向 bucket_t 結(jié)構(gòu)體的哈希表，_buckets 哈希表里面包含多個(gè) bucket_t，每個(gè) bucket_t 里面存放著 SEL 和 imp 函數(shù)的內(nèi)存地址的對(duì)應(yīng)關(guān)系；
_mask 是一個(gè) uint32_t 的指針，表示整個(gè) _buckets 哈希表的長(zhǎng)度；
_occupied 也是一個(gè) uint32_t 的指針，在 _buckets 哈希表中已經(jīng)緩存的方法數(shù)量；

在 bucket_t 結(jié)構(gòu)體中，_key 是一個(gè) unsigned long 的指針，其實(shí)是一個(gè)被 hash 化的一串?dāng)?shù)值，就是方法的 sel，也就是方法名；_imp 指針保持著對(duì)應(yīng)的函數(shù)地址；

cache_t 如何緩存 sel

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    cache_fill_nolock(cls, sel, imp, receiver);
}

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    // Never cache before +initialize is done
    // 系統(tǒng)要求在類初始化完成之前，不能進(jìn)行方法返回，因此如果類沒有完成初始化就 return
    if (!cls->isInitialized()) return;

    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    // 因?yàn)橛锌赡芷渌€程已經(jīng)把該方法緩存起來(lái)，如果緩存中已經(jīng)緩存過(guò)了，不用再緩存，直接 return
    if (cache_getImp(cls, sel)) return;

    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        // Cache is too full. Expand it.
        cache->expand();
    }

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot because the 
    // minimum size is 4 and we resized at 3/4 full.
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
}

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }

    reallocate(oldCapacity, newCapacity);
}

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();

    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    // Cache's old contents are not propagated. 
    // This is thought to save cache memory at the cost of extra cache fills.
    // fixme re-measure this

    assert(newCapacity > 0);
    assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);

    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

• 先看緩存中是否已經(jīng)存在了該方法，如果已經(jīng)存在，直接return掉；
• 如果緩存是只讀的，則需要重新申請(qǐng)緩存空間；
• 如果存入緩存后的大小小于當(dāng)前大小的 3/4，則當(dāng)前緩存大小還可以使用，無(wú)需擴(kuò)容；
• 如果緩存太滿，需要擴(kuò)容，擴(kuò)容為原來(lái)大小的 2 倍，重新申請(qǐng)緩存空間；

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

如果是首次調(diào)用這個(gè)函數(shù)，會(huì)使用一個(gè)初始容量值 INIT_CACHE_SIZE 來(lái)設(shè)定緩存容量；從 INIT_CACHE_SIZE 的定義顯示它的值是 4，也就是說(shuō)蘋果給 cache_t 設(shè)定的初始容量是 4。

• 重新設(shè)置哈希表的長(zhǎng)度 _mask = newCapacity-1，然后將舊內(nèi)存釋放掉，清空緩存；
• 當(dāng)通過(guò) find() 方法返回的 bucket->key() == 0，就說(shuō)明該位置上是空的，沒有緩存過(guò)方法，因此可以進(jìn)行插入操作 bucket->set(key, imp)，也就是將方法緩存到這個(gè)位置上。

注意：傳入 cls 得到緩存列表，如果是 instance 對(duì)象，返回 class 對(duì)象；如果是 class 對(duì)象，返回 meta-class 對(duì)象；如果是 meta-class 對(duì)象，返回 NSObject 的 meta-class 對(duì)象；

cache_t 如何查找 sel

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    assert(k != 0);

    bucket_t *b = buckets();
    mask_t m = mask();
    // 通過(guò) cache_hash() 計(jì)算出 key 值 k 對(duì)應(yīng)的 index 值 begin，用來(lái)記錄查詢起始索引；
    mask_t begin = cache_hash(k, m);
    // begin 賦值給 i，用于切換索引
    mask_t i = begin;
    do {
        // 用這個(gè) i 從哈希表取值，如果取出來(lái)的 bucket_t 的 key = k，則查詢成功，返回該 bucket_t。
        // 如果 key = 0，說(shuō)明在索引 i 的位置上還沒有緩存過(guò)方法，同樣需要返回該 bucket_t，用于中止緩存查詢。
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);

    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

cache_t 如何查找 sel，本質(zhì)上就是根據(jù) key 如何查找 index 的過(guò)程；
根據(jù) key 計(jì)算出 index 值的這個(gè)算法稱作哈希算法，盡可能減少不同的 key 得出相同 index 的情況出現(xiàn)，這種情況被稱作哈希碰撞，同時(shí)還要保證得出的 index 值在合理的范圍。index 越大，意味著對(duì)應(yīng)的哈希表的長(zhǎng)度越長(zhǎng)，這是需要占用實(shí)際物理空間的，而內(nèi)存是有限的。
哈希表是一種通過(guò)犧牲一定空間，來(lái)?yè)Q取時(shí)間效率的設(shè)計(jì)思想。

SEL

objc_msgSend函數(shù)第二個(gè)參數(shù)類型為SEL，它是selector在Objc中的表示類型（Swift中是Selector類）。selector是方法選擇器，可以理解為區(qū)分方法的id，而這個(gè)id的數(shù)據(jù)結(jié)構(gòu)是SEL，即表示一個(gè)方法的selector的指針。

Paste_Image.png

• 方法的selector用于表示運(yùn)行時(shí)方法的名字，Objective-C在編譯時(shí)，會(huì)依據(jù)每一個(gè)方法的名字、參數(shù)序列，生成一個(gè)唯一的整型標(biāo)識(shí)(int類型的地址)，這個(gè)標(biāo)識(shí)就是SEL。
• 在Objective-C中，只要方法名相同，那么方法的SEL就是一樣的，每一個(gè)方法都對(duì)應(yīng)著一個(gè)SEL，所以在Objective-C中，同一個(gè)類中或者這個(gè)類的繼承體系中，不能存在2個(gè)同名的方法，不同的類可以擁有相同的selector，不同的類的實(shí)例對(duì)象執(zhí)行相同的selector，會(huì)在各自的方法列表中根據(jù)selector去尋找對(duì)應(yīng)的IMP。
• 在本質(zhì)上，SEL只是一個(gè)指向方法的指針（被hash化得KEY值），能提高方法的查詢速度。

IMP

IMP實(shí)際上是一個(gè)函數(shù)指針，指向方法實(shí)現(xiàn)的首地址。其定義如下：

id (*IMP)(id, SEL, ...)

第一個(gè)參數(shù)是指向 self 的指針(如果是實(shí)例方法，則是類實(shí)例的內(nèi)存地址；如果是類方法，則是指向元類的指針)，第二個(gè)參數(shù)是方法選擇器( selector )，接下來(lái)是方法的實(shí)際參數(shù)列表。

SEL就是為了查找方法的最終實(shí)現(xiàn)IMP的，由于每個(gè)方法對(duì)應(yīng)唯一的SEL，因此我們可以通過(guò)SEL方便快速準(zhǔn)確地獲得它所對(duì)應(yīng)的IMP。

Method

Method是一種代表類中的某個(gè)方法的類型。

Paste_Image.png

而objc_method在上面的方法列表中提到過(guò)，它存儲(chǔ)了方法名，方法類型和方法實(shí)現(xiàn)：

Paste_Image.png

注意：

• 方法名類型為SEL，前面提到過(guò)相同名字的方法即使在不同類中定義，它們的方法選擇器也相同。
• 方法類型method_types是個(gè)char指針，其實(shí)存儲(chǔ)著方法的參數(shù)類型和返回值類型。
• method_imp指向了方法的實(shí)現(xiàn)，本質(zhì)上是一個(gè)函數(shù)指針。

Ivar

Ivar是一種代表類中實(shí)例變量的類型。

Paste_Image.png

Paste_Image.png

參考資料
https://www.infoq.cn/article/deep-understanding-of-tagged-pointer/
https://draveness.me/isa