前面兩篇文章中分析了類的bits号显，其實(shí)還有一個(gè)重要的字段cache（cache_t）嘿架。這篇文章將詳細(xì)分析cache的結(jié)構(gòu)以及原理松捉。

一涩赢、cache 數(shù)據(jù)結(jié)構(gòu)

HPObject *obj = [HPObject alloc];
Class objClass = [HPObject class];

1.1 cache_t 分析定位數(shù)據(jù)

首先根據(jù)源碼明確objc_class：

struct objc_class : objc_object {
    Class ISA;//繼承
    Class superclass;
    cache_t cache;   
    class_data_bits_t bits; 
};

以及cache_t：

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask; //unsigned long 8字節(jié)
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask;//uint32_t 4字節(jié)
#if __LP64__
            uint16_t                   _flags;//2字節(jié)
#endif
            uint16_t                   _occupied;//2字節(jié)
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache;//指針 8字節(jié)
    };
};

LLDB驗(yàn)證:

(lldb) p/x [HPObject class]
(Class) $0 = 0x00000001000083c8 HPObject
(lldb) p (cache_t *)0x00000001000083D8
(cache_t *) $1 = 0x00000001000083d8
(lldb) p *$1
(cache_t) $2 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4298437472
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 0
        }
      }
      _flags = 32820
      _occupied = 0
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0000803400000000
      }
    }
  }
}

• 獲取類地址后平移0x10得到了cache的指針缘滥。
• 打印cache結(jié)構(gòu)與源碼中看到的相同。

根據(jù)源碼_originalPreoptCache與內(nèi)部結(jié)構(gòu)體是同一份數(shù)據(jù)谒主，那么緩存數(shù)據(jù)是保存在_bucketsAndMaybeMask中呢朝扼？還是_originalPreoptCache中呢？sel和imp在哪塊呢霎肯？

官方在這塊并沒有給注釋擎颖，但是有個(gè)思路。既然是緩存那就應(yīng)該有增刪改查相應(yīng)的操作观游。直接在cache_t中查找對(duì)應(yīng)的方法會(huì)找到bucket_t相關(guān)的方法：

static bucket_t *emptyBuckets();
static bucket_t *allocateBuckets(mask_t newCapacity);
static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);

并且還有一個(gè)insert方法：

void insert(SEL sel, IMP imp, id receiver);

insert內(nèi)部也是對(duì)bucket的操作搂捧。顯然緩存應(yīng)該與bucket(_bucketsAndMaybeMask）有關(guān)。

1.2 bucket_t

bucket_t源碼結(jié)構(gòu)如下：

struct bucket_t {
private:
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
    // SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
};

發(fā)現(xiàn)了imp與sel懂缕，果然方法與bucket_t有關(guān)允跑。
那么就有了如下結(jié)構(gòu)對(duì)應(yīng)關(guān)系：

cache_t結(jié)構(gòu)

• arm64下bucket_t中_sel與_imp順序不同。注釋也說了順序與架構(gòu)有關(guān)搪柑，arm64e下imp在前更好聋丝，估計(jì)是有優(yōu)化。

二工碾、cache底層LLDB分析

上面分析出了_sel與_imp保存在bucket_t中弱睦，那么接下來就驗(yàn)證下：

(lldb) p $2._bucketsAndMaybeMask
(explicit_atomic<unsigned long>) $3 = {
  std::__1::atomic<unsigned long> = {
    Value = 4298437472
  }
}
(lldb) p $3.Value
error: <user expression 4>:1:4: no member named 'Value' in 'explicit_atomic<unsigned long>'
$3.Value
~~ ^

_bucketsAndMaybeMask能正常獲取但是Value卻獲取不到。同樣的_maybeMask以及_flags渊额、_occupied的Value也獲取不到况木。
只好分析下cache_t看有沒有暴露什么方法，在源碼中發(fā)現(xiàn)了buckets()：

struct bucket_t *buckets() const;

驗(yàn)證：

(lldb) p $2.buckets()
(bucket_t *) $4 = 0x000000010034f360
(lldb) p *$4
(bucket_t) $5 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}

這樣數(shù)據(jù)結(jié)構(gòu)是正常拿到了旬迹，但是沒有數(shù)據(jù)（沒有調(diào)用實(shí)例方法）火惊。調(diào)用一個(gè)方法繼續(xù)驗(yàn)證：

(lldb) p [obj instanceMethod]
(lldb) p/x [HPObject class]
(Class) $9 = 0x00000001000083c8 HPObject
(lldb) p (cache_t *)0x00000001000083D8
(cache_t *) $10 = 0x00000001000083d8
(lldb) p *$10
(cache_t) $11 = {
  _bucketsAndMaybeMask = {
    std::__1::atomic<unsigned long> = {
      Value = 4301540560
    }
  }
   = {
     = {
      _maybeMask = {
        std::__1::atomic<unsigned int> = {
          Value = 7
        }
      }
      _flags = 32820
      _occupied = 3
    }
    _originalPreoptCache = {
      std::__1::atomic<preopt_cache_t *> = {
        Value = 0x0003803400000007
      }
    }
  }
}
(lldb) p $11.buckets()
(bucket_t *) $12 = 0x0000000100644cd0
(lldb) p *$12
(bucket_t) $13 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}

仍然沒有數(shù)據(jù)，但是_maybeMask與_occupied有值了奔垦。既然buckets是個(gè)指針屹耐，那么平移繼續(xù)查找發(fā)現(xiàn)index為6的時(shí)候有值了。

(lldb) p $2.buckets()[6]
(bucket_t) $11 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 49016
    }
  }
}

雖然有值了宴倍，但是打印出來的數(shù)據(jù)仍然不是需要的张症，繼續(xù)分析下bucket_t的方法在源碼中找到了sel()和imp()方法：

inline SEL sel() const { return _sel.load(memory_order_relaxed); }

inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
    uintptr_t imp = _imp.load(memory_order_relaxed);
    if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
    SEL sel = _sel.load(memory_order_relaxed);
    return (IMP)
        ptrauth_auth_and_resign((const void *)imp,
                                ptrauth_key_process_dependent_code,
                                modifierForSEL(base, sel, cls),
                                ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
    return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
    return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
}

驗(yàn)證：

(lldb) p $11.sel()
(SEL) $12 = "instanceMethod"
(lldb) p $11.imp(nil,HPObject.class)
(IMP) $13 = 0x0000000100003cb0 (HPObjcTest`-[HPObject instanceMethod])

這樣就獲取了sel和imp的值了仓技。

• sel獲取：cls->偏移0x10-> cache_t ->buckets()-> bucket_t （根據(jù)index）->sel()
• imp獲人姿：cls->偏移0x10-> cache_t ->buckets()-> bucket_t （根據(jù)index）->imp(nil,cls)

上面分析完就有了以下疑問脖捻，這些問題將在后續(xù)分析解讀。（在第六部分）

1. 為什么imp需要cls兆衅？
2. 為什么_maybeMask值為7地沮，_occupied值為3。羡亩？
3. 為什么放在了6號(hào)位置摩疑？

三、cache模擬代碼分析

由于lldb調(diào)試并不方便畏铆，更好的方式是模擬cache的結(jié)構(gòu)將數(shù)據(jù)轉(zhuǎn)換為結(jié)構(gòu)體雷袋。

3.1 模擬代碼

模擬代碼如下：

struct hp_cache_t {
    unsigned long _bucketsAndMaybeMask;
    uint32_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct hp_class_data_bits_t {
    uintptr_t bits;
};

struct hp_objc_class {
    Class ISA;
    Class superclass;
    struct hp_cache_t cache;
    struct hp_class_data_bits_t bits;
};

• hp_cache_t這樣定義是因?yàn)閮?nèi)部有一個(gè)共用體，可以只保留一個(gè)結(jié)構(gòu)體辞居。
• 內(nèi)部結(jié)構(gòu)體可以拆出來放在外層就有了hp_cache_t的結(jié)構(gòu)楷怒。

由于最終存儲(chǔ)的數(shù)據(jù)是bucket_t，所以還需要模擬下bucket_t的實(shí)現(xiàn)：

//非arm64
struct hp_bucket_t {
    SEL _sel;
    IMP _imp;
};

這樣基本的數(shù)據(jù)結(jié)構(gòu)就還原了瓦灶。但是有個(gè)問題是怎么從_bucketsAndMaybeMask獲取buckets呢鸠删？
源碼如下:

struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}

是_bucketsAndMaybeMask進(jìn)行了load操作，這塊還原的話內(nèi)容就太多了贼陶，那么直接將_bucketsAndMaybeMask替換為bucket_t的指針呢刃泡？然后通過平移去獲取下一個(gè)元素。這樣hp_cache_t內(nèi)容修改如下：

struct hp_cache_t {
    struct hp_bucket_t *_buckets;
    uint32_t _maybeMask;
    uint16_t _flags;
    uint16_t _occupied;
};

3.2 代碼驗(yàn)證

HPObject增加以下方法：

- (void)instanceMethod1;

- (void)instanceMethod2;

- (void)instanceMethod3;

- (void)instanceMethod4;

- (void)instanceMethod5;

- (void)instanceMethod6;

- (void)instanceMethod7;

+ (void)classMethod;

方法實(shí)現(xiàn)都是打印方法名碉怔。
調(diào)用：

HPObject *obj  = [HPObject alloc];
[obj instanceMethod1];
Class objClass = obj.class;
//obj強(qiáng)轉(zhuǎn)成hp_objc_class
struct hp_objc_class *hp_class = (__bridge struct hp_objc_class *)(objClass);
NSLog(@"_occupied :%u _maybeMask :%u",hp_class->cache._occupied,hp_class->cache._maybeMask);
//循環(huán)打印bucket數(shù)據(jù)烘贴，_maybeMask為容器大小
for (uint32_t i = 0; i < hp_class->cache._maybeMask; i++) {
    //獲取bucket
    struct hp_bucket_t bucket = hp_class->cache._buckets[i];
    NSLog(@"SEL:%@ --- IMP:%p",NSStringFromSelector(bucket._sel),bucket._imp);
}

這段代碼先創(chuàng)建HPObject的實(shí)例對(duì)象然后調(diào)用instanceMethod1。最后將objClass轉(zhuǎn)換為hp_objc_class結(jié)構(gòu)體取到_buckets進(jìn)行循環(huán)打印眨层。

輸出：

//方法調(diào)用信息
HPObject method : -[HPObject instanceMethod1]
//容器信息
_occupied :1 _maybeMask :3
//buckets信息
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:instanceMethod1 --- IMP:0xbb48

_occupied為了1庙楚，_maybeMask為3。輸出結(jié)果符合預(yù)期趴樱，那么多調(diào)用幾個(gè)方法呢。
增加instanceMethod2調(diào)用：

[obj instanceMethod2];

輸出：

HPObject method : -[HPObject instanceMethod1]
HPObject method : -[HPObject instanceMethod2]
_occupied :2 _maybeMask :3
SEL:instanceMethod2 --- IMP:0xbb50
SEL:(null) --- IMP:0x0
SEL:instanceMethod1 --- IMP:0xbb60

_occupied變?yōu)榱?code>2酪捡，_maybeMask變?yōu)榱?code>3叁征。
再調(diào)用個(gè)方法以及類方法：

[obj instanceMethod1];
[obj instanceMethod2];
[obj instanceMethod3];
Class objClass = obj.class;
[objClass classMethod];

輸出：

HPObject method : -[HPObject instanceMethod1]
HPObject method : -[HPObject instanceMethod2]
HPObject method : -[HPObject instanceMethod3]
HPObject class method : +[HPObject classMethod]
_occupied :1 _maybeMask :7
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:instanceMethod3 --- IMP:0xbb30
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0

_occupied變?yōu)榱?code>1，_maybeMask為7逛薇。
在調(diào)用個(gè)init方法:

[obj init];

輸出：

_occupied :2 _maybeMask :7
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:instanceMethod3 --- IMP:0xbb68
SEL:init --- IMP:0x7ffe67244ed5
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0
SEL:(null) --- IMP:0x0

_occupied變?yōu)榱?code>2捺疼，_maybeMask仍為7。

至此可以得到以下結(jié)論：

• _occupied為容器中元素個(gè)數(shù)永罚。
• _maybeMask容器容量大衅『簟（其實(shí)是容器容量大小-1卧秘。在__x86_64__ / __i386__ / __arm__架構(gòu)下由于存在CACHE_END_MARKER，所以最后一個(gè)元素存儲(chǔ)的sel -imp為0x1-bucket指針地址官扣，其它架構(gòu)正常存儲(chǔ)翅敌。mask的值都是減了1，架構(gòu)不同存儲(chǔ)位置不同）惕蹄。
• 類方法不在類的cache中蚯涮，按照之前的分析應(yīng)該在元類的cache中。
• 父類方法(init)也會(huì)存到cache中卖陵。
• 當(dāng)_maybeMask的值變化的時(shí)候遭顶，_occupied會(huì)重新計(jì)數(shù)。也就意味著擴(kuò)容的時(shí)候之前的緩存都被清空了泪蔫。

四棒旗、cache_t底層原理

上面的結(jié)論都是通過代碼輸出驗(yàn)證的，那么_occupied和_maybeMask到底是怎么變化的呢撩荣？父類的init為什么也會(huì)被緩存起來呢铣揉？這就需要查看底層的源碼實(shí)現(xiàn)了。

通過之前的驗(yàn)證清楚了數(shù)據(jù)是存在_bucketsAndMaybeMask中的婿滓，根據(jù)名字就能判斷出來結(jié)構(gòu)類似isa不僅存儲(chǔ)_buckets還有MaybeMask信息老速。

那么切入點(diǎn)就是bucket插入_buckets的邏輯，也就是insert方法凸主。

4.1 insert

核心邏輯如下：

//sel imp 接收者
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    //對(duì)_occupied賦值 + 1橘券。首次 newOccupied = 1。
    mask_t newOccupied = occupied() + 1;
    //舊容量卿吐，（mask + 1） 或者 0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    //是否為空旁舰，首次進(jìn)入這里
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        //默認(rèn)容量給4
        if (!capacity) capacity = INIT_CACHE_SIZE;//1 << 2 = 4
        //0 4 false 開辟新的容器空間。由于舊容器為空這里不需要釋放傳false嗡官。
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    //newOccupied + 1 (相當(dāng)于 _occupied + 2) <= capacity * 3 / 4 容量夠的時(shí)候什么都不做箭窜，直接插入。<=75%的容積正常插入衍腥，否則擴(kuò)容磺樱。
    //## ??在arm64位的情況下，CACHE_END_MARKER 0 擴(kuò)容條件為：7 / 8 87.5% 這個(gè)時(shí)候CACHE_ALLOW_FULL_UTILIZATION 為 1
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    //capacity <= 1<<3 (8), _occupied + 1（CACHE_END_MARKER為0） <= 容量婆咸。少于8個(gè)元素的時(shí)候允許100%占滿竹捉。
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    //擴(kuò)容
    else {
        //容量不為空返回 2倍的容量，否則返回4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        //MAX_CACHE_SIZE 1<<16 = 2^16尚骄。最大緩存65536
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        //開辟新的容器控件块差，釋放舊的空間。
        reallocate(oldCapacity, capacity, true);
    }
    //從_bucketsAndMaybeMask獲取buckets
    bucket_t *b = buckets();
    mask_t m = capacity - 1;//首次是4-1 這里也就解釋了前面代碼調(diào)試的時(shí)候maybeMask為什么為3,7。
    //計(jì)算插入的index
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
    //循環(huán)判斷插入數(shù)據(jù)憨闰。
    do {
        //能走到這里大概率是cache不存在状蜗，所以這里走fastpath
        if (fastpath(b[i].sel() == 0)) {
            //Occupied + 1
            incrementOccupied();
            //buckets中插入bucket
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        //已經(jīng)存在了，不進(jìn)行任何處理鹉动。有可能是其它線程插入的轧坎。
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
        //cache_next為了防止hash沖突。再hash了一次训裆。
    } while (fastpath((i = cache_next(i, m)) != begin));
    //異常處理
    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}

• 首次進(jìn)入isConstantEmptyCache分支态坦。會(huì)創(chuàng)建一個(gè)容量為4/2的空buckets酪刀。這個(gè)時(shí)候由于舊buckets不存在不需要釋放所以參數(shù)傳遞false铝量。

是4還是2取決于INIT_CACHE_SIZE的值秃症，在__x86_64__ / __i386__ / __arm__ / __arm64__ && !__LP64__架構(gòu)下值為4，在arm64 && LP64架構(gòu)下值為2变姨。

• 當(dāng)容量大于等于3/4或7/8的情況下擴(kuò)容族扰。arm64_64的條件下為7 / 8，其它條件為3/4定欧。
• arm64_64條件下容量小于等于8的時(shí)候會(huì)占用100%才擴(kuò)容渔呵。

CACHE_ALLOW_FULL_UTILIZATION是arm64_64才為1。FULL_UTILIZATION_CACHE_SIZE值為8砍鸠。

• 擴(kuò)容是直接翻倍扩氢，默認(rèn)值4/2。最大值MAX_CACHE_SIZE為2¹⁶(65536)爷辱。在擴(kuò)容的時(shí)候直接釋放了舊值录豺。
• mask值為capacity - 1，這也就是調(diào)試的時(shí)候輸出3饭弓、7的原因（因?yàn)樽詈笠粋€(gè)元素有可能存儲(chǔ)的是buckets的地址双饥，格式為(sel-imp)0x1-buckets address，存不存在與架構(gòu)有關(guān)）弟断。
• 通過cache_hash計(jì)算插入的index咏花，后面會(huì)通過cache_next再進(jìn)行計(jì)算hash解決沖突問題。
• 循環(huán)判斷通過b[i].set插入bucket數(shù)據(jù)阀趴。

為什么擴(kuò)容后不復(fù)制之前的cache昏翰？因?yàn)閮?nèi)存平移很消耗性能。

4.2 reallocate

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    //舊buckets
    bucket_t *oldBuckets = buckets();
    //創(chuàng)建新buckets
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    //存儲(chǔ)buckets和mask  mask = newCapacity - 1刘急，這里newBuckets為新開辟的矩父，沒有數(shù)據(jù)∨琶梗空桶
//（其實(shí)是有數(shù)據(jù)的，最后一個(gè)存儲(chǔ)的是自己的指針，這也是這里為什么傳遞newCapacity - 1的原因）
    setBucketsAndMask(newBuckets, newCapacity - 1);
    //釋放舊bucket
    if (freeOld) {
        //底層垃圾椆ツ回收
        collect_free(oldBuckets, oldCapacity);
    }
}

• reallocate是重新開辟空間球订。
• 如果是擴(kuò)容會(huì)釋放掉舊的buckets

4.3 allocateBuckets

#if CACHE_END_MARKER

bucket_t *cache_t::endMarker(struct bucket_t *b, uint32_t cap)
{
    return (bucket_t *)((uintptr_t)b + bytesForCapacity(cap)) - 1;
}

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // This can't overflow mask_t because newCapacity is a power of 2.
    bucket_t *newBuckets = (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
//    printf("newBuckets---:%p\n",newBuckets);
    //取最后一個(gè)元素
    bucket_t *end = endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // End marker's sel is 1 and imp points to the first bucket.
    //新buckets的最后一個(gè)元素存儲(chǔ)的是自身的指針地址。格式為sel-imp（0x1-buckets address）
    end->set<NotAtomic, Raw>(newBuckets, (SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

#else

bucket_t *cache_t::allocateBuckets(mask_t newCapacity)
{
    if (PrintCaches) recordNewCache(newCapacity);
    //最后一個(gè)不插入 endmarker
    return (bucket_t *)calloc(bytesForCapacity(newCapacity), 1);
}

#endif

• 調(diào)用calloc開辟空間瑰钮。
• x86/i382/arm架構(gòu)下newBuckets最后一個(gè)元素存儲(chǔ)SEL-IMP(0x1-bucket address)冒滩。
• arm64架構(gòu)不存儲(chǔ)自身地址（包含32位以及64位）。

4.4 setBucketsAndMask

#define CACHE_MASK_STORAGE_OUTLINED 1
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3
#define CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS 4

#if defined(__arm64__) && __LP64__
#if TARGET_OS_OSX || TARGET_OS_SIMULATOR
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
#else
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
#endif
#elif defined(__arm64__) && !__LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
#ifdef __arm__
    // ensure other threads see buckets contents before buckets pointer
    mega_barrier();

    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);

    // ensure other threads see new buckets before new mask
    //內(nèi)存屏障
    mega_barrier();

    _maybeMask.store(newMask, memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    //_bucketsAndMaybeMask 存儲(chǔ)buckets浪谴，這里進(jìn)行了強(qiáng)轉(zhuǎn)开睡。_bucketsAndMaybeMask只存儲(chǔ)buckets的指針。
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);

    // ensure other threads see new buckets before new mask
    //_maybeMask存儲(chǔ)newCapacity-1
    _maybeMask.store(newMask, memory_order_release);
    //元素值賦值為0苟耻，由于是新桶篇恒。
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 || CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    uintptr_t buckets = (uintptr_t)newBuckets;
    uintptr_t mask = (uintptr_t)newMask;

    ASSERT(buckets <= bucketsMask);
    ASSERT(mask <= maxMask);

    _bucketsAndMaybeMask.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, memory_order_relaxed);
    _occupied = 0;
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    uintptr_t buckets = (uintptr_t)newBuckets;
    unsigned mask = (unsigned)newMask;

    ASSERT(buckets == (buckets & bucketsMask));
    ASSERT(mask <= 0xffff);

    _bucketsAndMaybeMask.store(buckets | objc::mask16ShiftBits(mask), memory_order_relaxed);
    _occupied = 0;

    ASSERT(this->buckets() == newBuckets);
    ASSERT(this->mask() == newMask);
}
#else
#error Unknown cache mask storage type.
#endif

CACHE_MASK_STORAGE對(duì)應(yīng)的值：

• arm64 64位運(yùn)行設(shè)備
  • OSX/SIMULATOR：CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS（4）
  • 真機(jī)（手機(jī)，pad等）：CACHE_MASK_STORAGE_HIGH_16(2)
• arm64 32位設(shè)備：CACHE_MASK_STORAGE_LOW_4(3)
• x86_64/i386/arm：CACHE_MASK_STORAGE_OUTLINED(1)

CACHE_MASK_STORAGE_OUTLINED intel/arm

• 強(qiáng)轉(zhuǎn)newBuckets為地址存儲(chǔ)在_bucketsAndMaybeMask中凶杖，這也是為什么前面代碼驗(yàn)證的時(shí)候能直接用buckets接收這個(gè)數(shù)據(jù)的原因（只存buckets地址）胁艰。
• _maybeMask存儲(chǔ)的值為capacity-1（容量-1，最后一個(gè)存儲(chǔ)的有可能是自身的地址智蝠，與架構(gòu)有關(guān)）腾么。

CACHE_MASK_STORAGE_HIGH_16 或 CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS arm64指令64位設(shè)備上

• mask與buckets都存儲(chǔ)在_bucketsAndMaybeMask中，mask << maskShift | newBuckets
• 此時(shí)maskShift為48/44也就是mask存儲(chǔ)在高16/20位杈湾，buckets存儲(chǔ)在低48/44位解虱。（mac以及模擬器maskShift是48，其它為44）漆撞。

CACHE_MASK_STORAGE_LOW_4 arm64指令32位設(shè)備

• mask與buckets都存儲(chǔ)在_bucketsAndMaybeMask中殴泰，buckets | objc::mask16ShiftBits(mask)
• buckets存儲(chǔ)在高60位，mask存儲(chǔ)在低4位叫挟，mask16ShiftBits的具體邏輯會(huì)在后面分析（其實(shí)存儲(chǔ)的不是mask艰匙，而是mask前置的0）。

??：開辟/擴(kuò)容空間后_occupied都會(huì)賦值為0抹恳。其實(shí)不存在擴(kuò)容员凝，都是新開辟空間。_occupied不包括最后一個(gè)元素buckets自身的地址奋献。

4.5 cache_fill_ratio

#if __arm__  ||  __x86_64__  ||  __i386__
#define CACHE_END_MARKER 1
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}

#elif __arm64__ && !__LP64__

#define CACHE_END_MARKER 0

static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}

#elif __arm64__ && __LP64__

#define CACHE_END_MARKER 0
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 7 / 8;
}
#define CACHE_ALLOW_FULL_UTILIZATION 1

#else
#error unknown architecture
#endif

• 不同架構(gòu)下容量算法有差異健霹，__arm64__ && __LP64__（__arm64指令64位 ）的情況下為7/8 87.5%，其它情況為3/4 75%擴(kuò)容瓶蚂。
• arm64_64在容量小于8的時(shí)候執(zhí)行100%填滿再擴(kuò)充的邏輯糖埋。
• 為什么是這兩個(gè)值？這里就涉及到了 負(fù)載因子窃这，具體可以查閱哈希函數(shù)相關(guān)知識(shí)瞳别。在3/4和7/8空間利用率最高，對(duì)哈希沖突能進(jìn)行有效避免。

4.6 cache_hash

#if defined(__arm64__) && TARGET_OS_IOS && !TARGET_OS_SIMULATOR && !TARGET_OS_MACCATALYST
#define CONFIG_USE_PREOPT_CACHES 1
#else
#define CONFIG_USE_PREOPT_CACHES 0
#endif

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    uintptr_t value = (uintptr_t)sel;
    //真機(jī)
#if CONFIG_USE_PREOPT_CACHES
    value ^= value >> 7;
#endif
    //sel & mask 得到hash地址祟敛。
    return (mask_t)(value & mask);
}

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}
#else

• CONFIG_USE_PREOPT_CACHES表示arm64指令并且非iOS模擬器非MACCATALYST疤坝，也就是arm64指令真機(jī)。
• cache_next在intel mac以及arm 32的情況是向后(+)插入馆铁，在 arm64的情況下是向前(-)插入跑揉。
  • (i+1) & mask的邏輯是向前(+)插入，會(huì)進(jìn)行二次&mask埠巨。
  • i ? i-1 : mask沖突的時(shí)候向前(-)历谍，直接娜沒有二次hash。當(dāng)i為0時(shí)會(huì)返回mask相當(dāng)于娜到最后了(這里是arm64架構(gòu)可以占用最后一個(gè)位置)辣垒。

那么insert是在什么時(shí)候調(diào)用的呢望侈？打個(gè)斷點(diǎn)查看下調(diào)用棧：

image.png

五甜无、_bucketsAndMaybeMask

上面分析道_bucketsAndMaybeMask不僅僅存儲(chǔ)buckets還存儲(chǔ)MaybeMask，那么它是怎么分布的呢哥遮？
這就要看獲取buckets()與獲取mask()的方法了岂丘。

5.1 buckets

struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}

可以看到關(guān)鍵是bucketsMask，需要確認(rèn)bucketsMask值是怎么分布的眠饮。

//intel芯片
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    static constexpr uintptr_t bucketsMask = ~0ul;//全1

//arm64 64位OSX`/`SIMULATOR`
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;//1<<15（低15位是0）
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1;   //(1<<48) - 1(低48位都是1)

 //`arm64真機(jī)`
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maskZeroBits = 4;

    // The largest mask value we can store.
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;//1<<15(低15位0)
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1; //(1 << 44)-1（低44位1）

//arm64 32 位
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4

    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;// (1<<4) -1（低4位1）
    static constexpr uintptr_t bucketsMask = ~maskMask; // ~((1<<4) -1)（低4位為0奥帘，其余全為1）
#endif
#end

• intel/arm：直接存儲(chǔ)的就是buckets地址，64/32位存儲(chǔ)buckets仪召。
• arm64指令 64位OSX/SIMULATOR：(1<<48) - 1寨蹋，低48位存儲(chǔ)buckets。
• arm64指令64 位真機(jī)（除了mac以及模擬器）： (1 << 44)-1扔茅，低44位存儲(chǔ)buckets已旧。
• arm64指令 32位： ~((1<<4) -1)：高60位存儲(chǔ)buckets。

5.2 mask

上面分析了buckets存儲(chǔ)的內(nèi)容是地址召娜，會(huì)根據(jù)平臺(tái)不同占用_bucketsAndMaybeMask的位數(shù)和位置不同运褪。那么mask是怎么存儲(chǔ)的呢？

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
mask_t cache_t::mask() const
{
    return _maybeMask.load(memory_order_relaxed);
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 || CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS

mask_t cache_t::mask() const
{
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
//maskShift 為48,
    return maskAndBuckets >> maskShift;
}
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
mask_t cache_t::mask() const
{
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
   //maskMask =  (1<<4) -1（低4位1）
    uintptr_t maskShift = (maskAndBuckets & maskMask);//保留后4位玖瘸。
//0xffff >> maskShift 獲取mask值秸讹。
    return 0xffff >> maskShift;
}

#else
#error Unknown cache mask storage type.
#endif

• intel/arm：需要直接從_maybeMask字段讀取。
• arm64 64位OSX/SIMULATOR：maskAndBuckets >> maskShift雅倒，取高16位璃诀。
• arm64 64位真機(jī)：maskAndBuckets >> maskShift，取高16位蔑匣。劣欢。
• arm64 32位： 0xffff >> maskShift棕诵，取低4位存儲(chǔ)的mask的值。

5.3 mask存儲(chǔ)的到底是什么氧秘？

通過上面的分析有兩個(gè)問題年鸳。

5.3.1 arm64指令32位下 0xffff >> maskShift 就取到了 mask，怎么做到的丸相？

要分析這個(gè)問題，我們要結(jié)合存儲(chǔ)的時(shí)候邏輯來看彼棍，在存儲(chǔ)的時(shí)候調(diào)用了objc::mask16ShiftBits(mask)

static inline uintptr_t mask16ShiftBits(uint16_t mask)
{
    // returns by how much 0xffff must be shifted "right" to return mask
    uintptr_t maskShift = __builtin_clz(mask) - 16;
    ASSERT((0xffff >> maskShift) == mask);
    return maskShift;
}

那么顯然核心在__builtin_clz究竟是干什么的灭忠？

• __builtin_clz返回前導(dǎo)的0的個(gè)數(shù)。
  驗(yàn)證：
  

  image.png
  
  也就是說返回的傳遞進(jìn)去的值在32位的前置0的個(gè)數(shù)座硕。0是沒有定義的弛作，會(huì)返回不確定的值。

• __builtin_clz(mask) - 16減16也就意味著要計(jì)算在16位下有多少前置位為0华匾，這里不會(huì)為負(fù)數(shù)映琳。因?yàn)樵谏厦娣治鲋幸呀?jīng)說了buckets擴(kuò)容的時(shí)候最大值為2¹⁶。

• 所以objc::mask16ShiftBits(mask)存儲(chǔ)的就是16位下mask的前置的0的個(gè)數(shù)蜘拉。

那么0xffff >> maskShift也就是0xffff >> 前置的0的值 這樣就恢復(fù)了mask萨西。

為什么能恢復(fù)？
0xffff就是0b1111111111111111旭旭，而mask的值是從1~65535（當(dāng)然是1谎脯，3，7持寄，15這樣的都是全1111111的值源梭，不存在0）這樣前置0的取值就從15~0。也就是通過0xffff右移15~0位就能恢復(fù)mask的值了稍味。相當(dāng)于通過前置位的個(gè)數(shù)將0xffff前面的1抹0而還原了mask(mask有規(guī)律废麻，是全1的值。)

在上面mask分別出現(xiàn)過3和7模庐，我們就用這兩個(gè)值來驗(yàn)證（mask最小為3/1烛愧，根據(jù)架構(gòu)不同值不同）：

image.png

為什么蘋果要這么存呢赖欣？
因?yàn)橹挥?code>4位存儲(chǔ)mask()屑彻，而在這種情況下前置0的個(gè)數(shù)最多15個(gè)所以4位剛好夠存。

在這里我只想給Apple扣666顶吮。

具體可以看下這個(gè)：_builtin

5.3.2 arm64 64位真機(jī)(非mac以及模擬器) mask 占用了高16位社牲，但是buckes占用了低44位。那么中間4位存儲(chǔ)了什么悴了？也就是maskZeroBits存儲(chǔ)了什么搏恤。

在maskZeroBits定義的地方有以下注釋：

// Additional bits after the mask which must be zero. msgSend
// takes advantage of these additional bits to construct the value
// `mask << 4` from `_maskAndBuckets` in a single instruction.
static constexpr uintptr_t maskZeroBits = 4;

image.png

image.png

buckets與mask分布

_bucketsAndMaybeMask數(shù)據(jù)分布

六、補(bǔ)充知識(shí)

在lldb分析的時(shí)候遺留了3個(gè)問題挨摸，接下來將進(jìn)行分析孩革。

6.1 為什么imp()需要參數(shù)cls？

解決這個(gè)問題需要解讀源碼得运，分別看下imp的取值和設(shè)置

    inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const {
        uintptr_t imp = _imp.load(memory_order_relaxed);
        if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, sel, cls),
                                    ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
    }

void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
    ASSERT(_sel.load(memory_order_relaxed) == 0 ||
           _sel.load(memory_order_relaxed) == newSel);

    // objc_msgSend uses sel and imp with no locks.
    // It is safe for objc_msgSend to see new imp but NULL sel
    // (It will get a cache miss but not dispatch to the wrong place.)
    // It is unsafe for objc_msgSend to see old imp and new sel.
    // Therefore we write new imp, wait a lot, then write new sel.
    
    uintptr_t newIMP = (impEncoding == Encoded
                        ? encodeImp(base, newImp, newSel, cls)
                        : (uintptr_t)newImp);

    if (atomicity == Atomic) {
        _imp.store(newIMP, memory_order_relaxed);
        
        if (_sel.load(memory_order_relaxed) != newSel) {
#ifdef __arm__
            mega_barrier();
            _sel.store(newSel, memory_order_relaxed);
#elif __x86_64__ || __i386__
            _sel.store(newSel, memory_order_release);
#else
#error Don't know how to do bucket_t::set on this architecture.
#endif
        }
    } else {
        _imp.store(newIMP, memory_order_relaxed);
        _sel.store(newSel, memory_order_relaxed);
    }
}

    // Sign newImp, with &_imp, newSel, and cls as modifiers.
    uintptr_t encodeImp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, IMP newImp, UNUSED_WITHOUT_PTRAUTH SEL newSel, Class cls) const {
        if (!newImp) return 0;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        return (uintptr_t)
            ptrauth_auth_and_resign(newImp,
                                    ptrauth_key_function_pointer, 0,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(base, newSel, cls));
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        return (uintptr_t)newImp ^ (uintptr_t)cls;
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (uintptr_t)newImp;
#else
#error Unknown method cache IMP encoding.
#endif
    }

通過源碼可以看到bucket_t::set的時(shí)候會(huì)判斷是否需要impEncoding膝蜈，如果需要會(huì)進(jìn)行(uintptr_t)newImp ^ (uintptr_t)cls，所以在讀取imp的時(shí)候需要傳參數(shù)cls進(jìn)行還原熔掺。相當(dāng)于(uintptr_t)cls^imp^(uintptr_t)cls = imp饱搏。那么就說明buckets中存儲(chǔ)的imp不一定是真實(shí)的imp，有可能是經(jīng)過編碼的瞬女。

6.2 為什么在調(diào)用了一個(gè)方法后_maybeMask值為7窍帝，_occupied值為3？

在lldb調(diào)試的時(shí)候在調(diào)用了一個(gè)方法后發(fā)現(xiàn)_maybeMask為7诽偷，_occupied為3坤学。正常情況應(yīng)該是3和1。
根據(jù)前面的源碼分析既然_maybeMask為7了那么肯定進(jìn)行了擴(kuò)容操作报慕，在擴(kuò)容前打印buckets中的內(nèi)容查看下是什么數(shù)據(jù)：

image.png

• 這里cls傳nil是為了恢復(fù)0x1的imp眠冈，因?yàn)樵谠创a添加第一個(gè)元素的時(shí)候cls是nil飞苇。

image.png

這樣就清晰了在lldb調(diào)試的過程中會(huì)調(diào)用class以及responseToSelector方法。0x1是最后一個(gè)數(shù)據(jù)buckets的地址蜗顽。

image.png

代碼驗(yàn)證：

image.png

?? 非arm64架構(gòu)下buckes最后一個(gè)元素是自身的地址布卡。

6.3 為什么第一個(gè)元素放在了6號(hào)位置？

簡(jiǎn)單說就是

• 數(shù)組：方便讀取雇盖，插入和刪除不方便
• 鏈表：方便插入和刪除忿等，讀取不便。

所以就有了哈希數(shù)據(jù)結(jié)構(gòu)崔挖，哈希結(jié)合了數(shù)據(jù)和鏈表的能力方便增刪和查找贸街。4.6中分析了cache_hash庵寞。哈希函數(shù)用的是sel & mask，解決沖突用的是開放定址法的線性探查法

具體參考
哈希函數(shù)
哈希表理論

Cache_t原理分析圖

cache_t流程