cache的數據結構

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

• CACHE_MASK_STORAGE_OUTLINED 表示運行的環(huán)境 模擬器 或者 macOS
• CACHE_MASK_STORAGE_HIGH_16 表示運行環(huán)境是ram64架構64位的真機
• CACHE_MASK_STORAGE_LOW_4 表示運行環(huán)境是ram64架構非64位的真機
  其中這三種情況在源碼中的處理又區(qū)分為真機與非真機，真機時cache_t有_maskAndBuckets而非真機則分為_buckets、_mask。對于存儲bucket及mask，真機上有做優(yōu)化。
  源碼分析bucket_t結構，發(fā)現其主要有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

所以可以得出一個結論cache中存儲是方法編碼及方法實現。

驗證cache緩存方法

我們之前使用過lldb調試去分析objc_class的內部結構，同樣我們可以通過lldb調試去看，到底方法是如何存儲到cache中的。

LGPerson *p  = [LGPerson alloc];
Class pClass = [LGPerson class];
//在此斷點

(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存儲的信息
(bucket_t) $4 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null)
  }
  _imp = {
    std::__1::atomic<unsigned long> = 0
  }
}

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

2020-09-19 15:14:40.256183+0800 KCObjc[11077:193815] sayHelloWorld方法調用
(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])

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

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

因為buckets返回的是個數組，我們可以直接通過下標的方式訪問到數組中的其他的bucket_t。
注意:cache緩存方法不是順序的而是亂序的。

cache_t底層源碼分析

通過源碼，我們可以對cache有一個初步的了解，其內部主要的一些屬性buckets、occupied、mask，
通過對應的數據結構，初步有一個模糊的概念，cache_t內部主要是為了存儲bucket_t,在前面的lldb調試時，可以看到occupied在緩存方法后是發(fā)生了變化的，猜測其是用來記錄緩存方法數的，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方法的源碼中我們可以找到兩個很關鍵的處理，
1.cache_t擴容的邏輯

  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;  // 擴容兩倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 內存 庫容完畢
    }

最初容量值定義為4.容量如果達到當前容量的3/4，就會在當前容量的基礎上擴容兩倍。
擴容完畢后調用reallocate方法，重新開辟空間，再進行存儲。這里注意，擴容開辟存儲時，之前的存儲的方法在新的存儲中時沒有了。

2. 存儲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;
}

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