cache的數(shù)據(jù)結(jié)構(gòu)

我們需要知道cache中存儲(chǔ)的到底是什么？我們通過objc源碼分析cache_t的結(jié)構(gòu)，發(fā)現(xiàn)其根據(jù)架構(gòu)處理分成了三種情況，分別為:

• CACHE_MASK_STORAGE_OUTLINED 表示運(yùn)行的環(huán)境 模擬器 或者 macOS
• CACHE_MASK_STORAGE_HIGH_16 表示運(yùn)行環(huán)境是ram64架構(gòu)64位的真機(jī)
• CACHE_MASK_STORAGE_LOW_4 表示運(yùn)行環(huán)境是ram64架構(gòu)非64位的真機(jī)
  其中這三種情況在源碼中的處理又區(qū)分為真機(jī)與非真機(jī)，真機(jī)時(shí)cache_t有_maskAndBuckets而非真機(jī)則分為_buckets、_mask。對(duì)于存儲(chǔ)bucket及mask，真機(jī)上有做優(yōu)化。
  源碼分析bucket_t結(jié)構(gòu)，發(fā)現(xiàn)其主要有sel跟imp的。

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

所以可以得出一個(gè)結(jié)論cache中存儲(chǔ)是方法編碼及方法實(shí)現(xiàn)。

驗(yàn)證cache緩存方法

我們之前使用過lldb調(diào)試去分析objc_class的內(nèi)部結(jié)構(gòu)，同樣我們可以通過lldb調(diào)試去看，到底方法是如何存儲(chǔ)到cache中的。

LGPerson *p  = [LGPerson alloc];
Class pClass = [LGPerson class];
//在此斷點(diǎn)

(lldb) p/x pClass //pClass是LGPerson類
(Class) $0 = 0x0000000100002350 LGPerson 
(lldb) p (cache_t *)0x0000000100002360 //通過首地址偏移16位定位到cache的地址
(cache_t *) $1 = 0x0000000100002360
(lldb) p *$1 //讀取
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x000000010032e430 {
      _sel = {
        std::__1::atomic<objc_selector *> = (null)
      }
      _imp = {
        std::__1::atomic<unsigned long> = 0
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 0
  }
  _flags = 32820
  _occupied = 0
}
(lldb) p $2.buckets() //獲取cache中的buckets
(bucket_t *) $3 = 0x000000010032e430
(lldb) p * $3 //讀取buckets存儲(chǔ)的信息
(bucket_t) $4 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}

LGPerson是我們定義的一個(gè)類，通過調(diào)試獲取其類首地址。通過lldb調(diào)試我們可以看到，實(shí)例創(chuàng)建后我們沒有做其他處理。接下來我們調(diào)用一次實(shí)例方法，繼續(xù)lldb調(diào)試。

2020-09-19 15:14:40.256183+0800 KCObjc[11077:193815] sayHelloWorld方法調(diào)用
(lldb) p $2.buckets()
(bucket_t *) $6 = 0x0000000102904fc0
(lldb) p *$6
(bucket_t) $7 = {
  _sel = {
    std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
    std::__1::atomic<unsigned long> = 10336
  }
}
(lldb) p $7.sel()
(SEL) $8 = "sayHelloWorld"
(lldb) p $7.imp([LGPerson class])
(IMP) $9 = 0x0000000100000b30 (KCObjc`-[LGPerson sayHelloWorld])

調(diào)用一次方法后，繼續(xù)去讀cache，發(fā)現(xiàn)確實(shí)能夠讀取到方法的sel及imp。驗(yàn)證了cache確實(shí)是存儲(chǔ)了我們定義的實(shí)例方法。
只緩存了一個(gè)方法的調(diào)試我們已經(jīng)清楚了，那么多個(gè)方法的情況怎么辦呢？

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

因?yàn)閎uckets返回的是個(gè)數(shù)組，我們可以直接通過下標(biāo)的方式訪問到數(shù)組中的其他的bucket_t。
注意:cache緩存方法不是順序的而是亂序的。

cache_t底層源碼分析

通過源碼，我們可以對(duì)cache有一個(gè)初步的了解，其內(nèi)部主要的一些屬性buckets、occupied、mask，
通過對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)，初步有一個(gè)模糊的概念，cache_t內(nèi)部主要是為了存儲(chǔ)bucket_t,在前面的lldb調(diào)試時(shí)，可以看到occupied在緩存方法后是發(fā)生了變化的，猜測(cè)其是用來記錄緩存方法數(shù)的，mask是用來做掩碼處理的。
cache_t的public方法

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

這些方法中我們主要看的是incrementOccupied。通過查找incrementOccupied，我們找到了

void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
    ....
}

在insert方法的源碼中我們可以找到兩個(gè)很關(guān)鍵的處理，
1.cache_t擴(kuò)容的邏輯

  if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    } else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4  3 + 1 bucket    cache_t
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 擴(kuò)容兩倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 內(nèi)存 庫(kù)容完畢
    }

最初容量值定義為4.容量如果達(dá)到當(dāng)前容量的3/4，就會(huì)在當(dāng)前容量的基礎(chǔ)上擴(kuò)容兩倍。
擴(kuò)容完畢后調(diào)用reallocate方法，重新開辟空間，再進(jìn)行存儲(chǔ)。這里注意，擴(kuò)容開辟存儲(chǔ)時(shí)，之前的存儲(chǔ)的方法在新的存儲(chǔ)中時(shí)沒有了。

2. 存儲(chǔ)sel、imp的處理

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin));

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

#if __arm__  ||  __x86_64__  ||  __i386__
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;
}

存儲(chǔ)的位置begin是通過cache_hash計(jì)算得到的，然后使用&mask計(jì)算得到具體的位置，mask值為當(dāng)前容量減一，如果這個(gè)位置為空則插入存儲(chǔ)，如果已經(jīng)被緩存則退出，否則繼續(xù)cache_next。
cache_next在真機(jī)跟非真機(jī)上是處理不同的。