關(guān)于我的倉庫

• 這篇文章是我為面試準(zhǔn)備的iOS基礎(chǔ)知識學(xué)習(xí)中的一篇
• 我將準(zhǔn)備面試中找到的所有學(xué)習(xí)資料炒瘟，寫的Demo谈跛，寫的博客都放在了這個(gè)倉庫里iOS-Engineer-Interview
• 歡迎star????
• 其中的博客在簡書旁趟，CSDN都有發(fā)布
• 博客中提到的相關(guān)的代碼Demo可以在倉庫里相應(yīng)的文件夾里找到

前言

• 本文將會(huì)探究整個(gè)weak實(shí)現(xiàn)的流程，并盡可能深挖里面的源碼
• weak確實(shí)是runtime里的一個(gè)難點(diǎn)魄咕，主要我目前沒有系統(tǒng)學(xué)習(xí)過C++胧弛，數(shù)據(jù)結(jié)構(gòu)，很多知識都是現(xiàn)查的楚殿，本文可能有很多疏漏撮慨，請讀者斧正

準(zhǔn)備工作

• 請準(zhǔn)備好750.1版本的objc4源碼一份【目前最新的版本】，打開它，找到文章中提到的方法砌溺，類型影涉，對象
• 一切請以手中源碼為準(zhǔn)，不要輕信任何人规伐，任何文章蟹倾，包括本篇博客
• 文章中的源碼都請過了我的刪改，建議還是先看看源碼
• 源碼建議從Apple官方開源網(wǎng)站獲取obj4
• 官網(wǎng)上下載下來需要自己配置才能編譯運(yùn)行楷力，如果不想配置喊式，可以在RuntimeSourceCode中clone

數(shù)據(jù)模型

• 看過我的其他博文的讀者應(yīng)該發(fā)現(xiàn)我比較喜歡看源代碼方法調(diào)用棧，看到某個(gè)方法萧朝，再去研究其涉及的數(shù)據(jù)模型
• 但由于weak涉及到的數(shù)據(jù)模型過多岔留，不一口氣講完很容易搞混，所以在這里我會(huì)把所有涉及到的數(shù)據(jù)模型全部講清楚检柬，包括里面存什么献联，以什么方式存等等
• 這樣子也方便大家先對weak有個(gè)基礎(chǔ)的概念，下面看方法調(diào)用棧也不至于懵逼
• 如果看下一部分的方法調(diào)用棧里對數(shù)據(jù)模型模糊了何址，請切回這一部分研究

SideTables()

• SideTables()是一個(gè)全局的哈希表里逆，里面存儲了sideTable結(jié)構(gòu)體，根據(jù)對象的地址可以在sidetables()找到相應(yīng)的SideTable
• SideTables()的定義：

static StripedMap<SideTable>& SideTables() {
    return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);
}

• 可以大致理解為用爪，該方法會(huì)返回一個(gè)StripedMap類型的數(shù)據(jù)結(jié)構(gòu)原押，里面存儲的類型是SideTable

StripedMap

template<typename T>
class StripedMap {
#if TARGET_OS_IPHONE && !TARGET_OS_SIMULATOR
    enum { StripeCount = 8 };
#else
    enum { StripeCount = 64 };
#endif

    struct PaddedT {
        T value alignas(CacheLineSize);
        //enum { CacheLineSize = 64 };
    };

    PaddedT array[StripeCount];
    //enum { StripeCount = 64 };

    static unsigned int indexForPointer(const void *p) {
        uintptr_t addr = reinterpret_cast<uintptr_t>(p);
        return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
    }

 public:
    //重載
    T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
    }
    const T& operator[] (const void *p) const { 
        return const_cast<StripedMap<T>>(this)[p]; 
    }
};

• 這里面其實(shí)StripedMap里一共就一個(gè)PaddedT類型的數(shù)組，大小為StripeCount【64】
• SideTables() 返回的 StripedMap, 是一個(gè) value 為 SideTable 的哈希桶(由于 SideTable 內(nèi)部又在維護(hù)數(shù)組, 所以這是一個(gè)哈希桶結(jié)構(gòu)), 哈希值由對象的地址計(jì)算得出

補(bǔ)充知識：哈希桶

• 哈希桶算法就是鏈地址解決沖突的方法
• 所謂哈希桶偎血，以SideTables與SideTable的方式來舉例的話诸衔，就是本來數(shù)據(jù)數(shù)量不多的時(shí)候，只要有個(gè)SideTables就行颇玷，但由于數(shù)據(jù)數(shù)量超過了64【SideTables內(nèi)部數(shù)組的長度】笨农，導(dǎo)致出現(xiàn)了哈希沖突，兩個(gè)對象都有f（key）帖渠，需要占用同一個(gè)空間
• 哈希桶就是將這個(gè)數(shù)組的單個(gè)空間擴(kuò)展成一個(gè)拉鏈一樣的結(jié)構(gòu)谒亦，將指向同一個(gè)空間的值存到同一條拉鏈上
• 這里，SideTable就是一條拉鏈空郊，一個(gè)對象根據(jù)其地址在SideTables上找到相應(yīng)的SideTable份招，存入其中
• 拉鏈可以用數(shù)組/鏈表組織數(shù)據(jù)，Apple使用的是數(shù)組

補(bǔ)充知識：模版函數(shù)

• 面向?qū)ο蟮睦^承和多態(tài)機(jī)制有效提高了程序的可重用性和可擴(kuò)充性狞甚。在程序的可重用性方面脾还，程序員還希望得到更多支持。
• C++ 語言支持模板入愧。有了模板，可以只寫一個(gè) Swap 模板，編譯器會(huì)根據(jù) Swap 模板自動(dòng)生成多個(gè) Sawp 函數(shù)棺蛛，用以交換不同類型變量的值怔蚌。
• 這里也就是說，不規(guī)定T的數(shù)據(jù)類型旁赊，輸入什么桦踊，就使用進(jìn)行運(yùn)算

補(bǔ)充知識：alignas()

• 指定類型或?qū)ο蟮膶R要求。
• alignas 說明符可應(yīng)用于變量或非位域類數(shù)據(jù)成員的聲明终畅，或可應(yīng)用于 class/struct/union 或枚舉的定義籍胯。它不能應(yīng)用于函數(shù)形參或 catch 子句的異常形參。
• 這種聲明所聲明的對象或類型的對齊要求离福，將等于用于該聲明的所有 alignas 說明符中最嚴(yán)格（最大）的非零 表達(dá)式杖狼，除非這會(huì)削弱類型的自然對齊。
• 也就是說妖爷，它保證了value中的值是與64對齊

補(bǔ)充知識：重載

• C++ 允許在同一作用域中的某個(gè)函數(shù)和運(yùn)算符指定多個(gè)定義蝶涩，分別稱為函數(shù)重載和運(yùn)算符重載。
• 重載聲明是指一個(gè)與之前已經(jīng)在該作用域內(nèi)聲明過的函數(shù)或方法具有相同名稱的聲明絮识，但是它們的參數(shù)列表和定義（實(shí)現(xiàn)）不相同绿聘。
• 當(dāng)您調(diào)用一個(gè)重載函數(shù)或重載運(yùn)算符時(shí)，編譯器通過把您所使用的參數(shù)類型與定義中的參數(shù)類型進(jìn)行比較次舌，決定選用最合適的定義熄攘。選擇最合適的重載函數(shù)或重載運(yùn)算符的過程，稱為重載決策彼念。
• 簡單來說挪圾，這里面

T& operator[] (const void *p) { 
        return array[indexForPointer(p)].value; 
}

• 就等同于把[]運(yùn)算符重新定義了，其作用現(xiàn)在是array[indexForPointer(p)].value
• 這里提一下這個(gè)国拇，因?yàn)榻酉聛頃?huì)用到[]運(yùn)算符

SideTable

• SideTable的定義一點(diǎn)都不長洛史，卻很麻煩

struct SideTable {
    spinlock_t slock;   //自旋鎖
    RefcountMap refcnts;    //存放引用計(jì)數(shù)
    weak_table_t weak_table;   //weak_table是一個(gè)哈希
};

• 這里先來看這三兄弟是干什么的

spinlock_t slock【自旋鎖】

補(bǔ)充知識：鎖

• 鎖是操作系統(tǒng)中的一個(gè)概念
• 為了保證數(shù)據(jù)的一致性，在多線程編程中我們會(huì)用到鎖酱吝，使得在某一時(shí)間點(diǎn)也殖，只有一個(gè)線程進(jìn)入臨界區(qū)代碼。雖然不同的語言可能會(huì)提供不同的鎖接口务热，但是底層調(diào)用的都是操作系統(tǒng)的提供的鎖忆嗜，不同的高級語言只是在操作系統(tǒng)的鎖機(jī)制基礎(chǔ)上進(jìn)行了些封裝而已，要真正理解鎖崎岂，還是得看操作系統(tǒng)是怎么實(shí)現(xiàn)鎖的捆毫。
• 以引用計(jì)數(shù)舉例，由于我們的程序是多線程的冲甘，可能在不同的線程都會(huì)對某個(gè)對象的應(yīng)用計(jì)數(shù)操作绩卤，導(dǎo)致混亂
• 這里使用鎖途样，當(dāng)某次訪問開始時(shí)，鎖就被持有濒憋，其余訪問就不能進(jìn)行何暇，當(dāng)訪問結(jié)束，鎖被空出來凛驮，才能輪到其他訪問去競爭這把鎖

補(bǔ)充知識：分離鎖&&拆分鎖

• 再以我們的SideTables以及SideTable舉例裆站，我們使用一把鎖，鎖住整個(gè)SideTables黔夭，只要SideTables里某個(gè)SideTable里的某個(gè)對象的引用計(jì)數(shù)被訪問了宏胯，我們就把整個(gè)SideTables禁止訪問
• 這樣顯然會(huì)導(dǎo)致效率低下
• 分離鎖和分拆鎖的區(qū)別
  • 降低鎖競爭的另一種方法是降低線程請求鎖的頻率。分拆鎖 (lock splitting) 和分離鎖 (lock striping) 是達(dá)到此目的兩種方式本姥。相互獨(dú)立的狀態(tài)變量肩袍，應(yīng)該使用獨(dú)立的鎖進(jìn)行保護(hù)。有時(shí)開發(fā)人員會(huì)錯(cuò)誤地使用一個(gè)鎖保護(hù)所有的狀態(tài)變量扣草。這些技術(shù)減小了鎖的粒度了牛，實(shí)現(xiàn)了更好的可伸縮性。但是辰妙，這些鎖需要仔細(xì)地分配鹰祸，以降低發(fā)生死鎖的危險(xiǎn)。
  • 如果一個(gè)鎖守護(hù)多個(gè)相互獨(dú)立的狀態(tài)變量密浑，你可能能夠通過分拆鎖蛙婴，使每一個(gè)鎖守護(hù)不同的變量，從而改進(jìn)可伸縮性尔破。通過這樣的改變街图，使每一個(gè)鎖被請求的頻率都變小了。分拆鎖對于中等競爭強(qiáng)度的鎖懒构，能夠有效地把它們大部分轉(zhuǎn)化為非競爭的鎖餐济，使性能和可伸縮性都得到提高。
  • 分拆鎖有時(shí)候可以被擴(kuò)展胆剧，分成若干加鎖塊的集合絮姆，并且它們歸屬于相互獨(dú)立的對象，這樣的情況就是分離鎖秩霍。
• 繼續(xù)舉例篙悯，我們將每個(gè)SideTable里的每個(gè)對象的引用計(jì)數(shù)都加一把鎖虐秋，這就是分拆鎖洛退，這樣雖然安全太雨，但卻是的消耗特別大
• 而我們將給每個(gè)SideTable上一把鎖纫雁，只讓某個(gè)SideTable不能多次訪問，這就是分離鎖赠尾，根據(jù)源碼也能看出來毡证，這就是蘋果的選擇

補(bǔ)充知識：自旋鎖

• 自旋鎖比較適用于鎖使用者保持鎖時(shí)間比較短的情況转砖。正是由于自旋鎖使用者一般保持鎖時(shí)間非常短，因此選擇自旋而不是睡眠是非常必要的漏峰，自旋鎖的效率遠(yuǎn)高于互斥鎖糠悼。信號量和讀寫信號量適合于保持時(shí)間較長的情況，它們會(huì)導(dǎo)致調(diào)用者睡眠浅乔，因此只能在進(jìn)程上下文使用，而自旋鎖適合于保持時(shí)間非常短的情況铝条，它可以在任何上下文使用靖苇。
• 這是一種不太高級的鎖結(jié)構(gòu)，但卻很符合我們的需要班缰，因?yàn)橐糜?jì)數(shù)的操作是十分頻繁的贤壁，使用自旋鎖，只是讓訪問者自旋一會(huì)埠忘，一旦可以訪問了脾拆，立即訪問，增加效率

補(bǔ)充知識：并行&&并發(fā)

• 多線程的情況下莹妒，整個(gè)程序是一個(gè)并行的狀態(tài)名船，導(dǎo)致我們需要使用鎖

FC57708B-D697-4FC1-A508-7DAD9609697C

蘋果的抉擇

• 蘋果使用了自旋鎖，分離鎖旨怠，給單個(gè)的SideTable上鎖
• 保證了安全性的同時(shí)有兼具效率

RefcountMap refcnts【存放引用計(jì)數(shù)】

• 引用計(jì)數(shù)存在RefcountMap結(jié)構(gòu)里渠驼，也就是上文介紹哈希桶的時(shí)候提到的拉鏈
• 這也是個(gè)hash結(jié)構(gòu)，根據(jù)對象地址存儲引用計(jì)數(shù)

//RefcountMap 
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;

//DenseMap
template<typename KeyT, typename ValueT,
         bool ZeroValuesArePurgeable = false, 
         typename KeyInfoT = DenseMapInfo<KeyT> >
class DenseMap
    : public DenseMapBase<DenseMap<KeyT, ValueT, ZeroValuesArePurgeable, KeyInfoT>,
                          KeyT, ValueT, KeyInfoT, ZeroValuesArePurgeable> {
  // Lift some types from the dependent base class into this class for
  // simplicity of referring to them.
  typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, ZeroValuesArePurgeable> BaseT;
  //ZeroValuesArePurgeable：ZeroValuesArePurgeable 默認(rèn)值是 false, 但 RefcountMap 指定其初始化為 true. 這個(gè)成員標(biāo)記是否可以使用值為 0 (引用計(jì)數(shù)為 1) 的桶.

                              
  typedef typename BaseT::BucketT BucketT;
  friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, ZeroValuesArePurgeable>;

  BucketT *Buckets;
  //Buckets 指針管理一段連續(xù)內(nèi)存空間, 也就是數(shù)組, 數(shù)組成員是 BucketT 類型的對象桶的 key 為 EmptyKey 時(shí)是空桶
  //typedef std::pair<KeyT, ValueT> BucketT;
  //桶的數(shù)據(jù)類型std::pair鉴腻，將對象地址和對象的引用計(jì)數(shù)(這里的引用計(jì)數(shù)類似于 isa, 也是使用其中的幾個(gè) bit 來保存引用計(jì)數(shù), 留出幾個(gè) bit 來做其它標(biāo)記位)組合成一個(gè)數(shù)據(jù)類型.
  unsigned NumEntries;
  //NumEntries 記錄數(shù)組中已使用的非空的桶的個(gè)數(shù).
  unsigned NumTombstones;
  //當(dāng)一個(gè)對象的引用計(jì)數(shù)為0, 要從桶中取出時(shí), 其所處的位置會(huì)被標(biāo)記為 TombstoneNumTombstones 就是數(shù)組中的墓碑的個(gè)數(shù). 后面會(huì)介紹到墓碑的作用
  unsigned NumBuckets;
  //NumBuckets 桶的數(shù)量, 因?yàn)閿?shù)組中始終都充滿桶, 所以可以理解為數(shù)組大小.
}

DisguisedPtr

• DisguisedPtr是runtime對于普通對象指針(引用)的一個(gè)封裝迷扇，目的在于隱藏weak_table_t的內(nèi)部指針。

//蘋果的注釋：
//DisguisedPtr<T>與指針類型T*類似爽哎，除了對存儲值進(jìn)行偽裝蜓席，以使其不受“l(fā)eaks”等工具的影響。
//nil被偽裝成它自己课锌，所以零填充的內(nèi)存按預(yù)期工作厨内，
//這意味著0x80..00也被偽裝成自己，但我們不在乎产镐。
//注意隘庄，weak_entry_t不知道這個(gè)代碼。
template <typename T>
class DisguisedPtr {
    uintptr_t value;

    static uintptr_t disguise(T* ptr) {
        return -(uintptr_t)ptr;
    }

    static T* undisguise(uintptr_t val) {
        return (T*)-val;
    }

 public:
    DisguisedPtr() { }
    DisguisedPtr(T* ptr) 
        : value(disguise(ptr)) { }
    DisguisedPtr(const DisguisedPtr<T>& ptr) 
        : value(ptr.value) { }

    DisguisedPtr<T>& operator = (T* rhs) {
        value = disguise(rhs);
        return *this;
    }
    DisguisedPtr<T>& operator = (const DisguisedPtr<T>& rhs) {
        value = rhs.value;
        return *this;
    }

    operator T* () const {
        return undisguise(value);
    }
    T* operator -> () const { 
        return undisguise(value);
    }
    T& operator * () const { 
        return *undisguise(value);
    }
    T& operator [] (size_t i) const {
        return undisguise(value)[i];
    }
};

• 對于這個(gè)我了解的也不是很清楚癣亚，大概理解就是通過static uintptr_t disguise(T* ptr) {return -(uintptr_t)ptr;}來實(shí)現(xiàn)隱藏
• 我們試著理解Apple注釋里說【0x80..00也被偽裝成自己】丑掺，由于這個(gè)數(shù)字就是首位是1，該位在有符號的情況下理解為-0述雾，則nil理解為+0【0正1負(fù)】街州，因此這里認(rèn)為它們被偽裝成了自己【還是不太懂凹娣帷！Ｋ艚伞鳍征！】

DenseMap

• 當(dāng)你進(jìn)入DenseMap定義的時(shí)候，抬頭看下最上方的文件名面徽，發(fā)現(xiàn)已經(jīng)離開objc4了艳丛，進(jìn)入了一個(gè)叫l(wèi)lvm-DenseMap.h的里世界，這里面的代碼也是開著全局搜索也搜不到的神仙代碼【但很奇怪趟紊，這里還是可以編輯】

補(bǔ)充知識：LLVM

• LLVM是構(gòu)架編譯器(compiler)的框架系統(tǒng)氮双，以C++編寫而成，用于優(yōu)化以任意程序語言編寫的程序的編譯時(shí)間(compile-time)霎匈、鏈接時(shí)間(link-time)戴差、運(yùn)行時(shí)間(run-time)以及空閑時(shí)間(idle-time)，對開發(fā)者保持開放铛嘱，并兼容已有腳本暖释。
• LLVM計(jì)劃啟動(dòng)于2000年，最初由美國UIUC大學(xué)的Chris Lattner博士主持開展墨吓。2006年Chris Lattner加盟Apple Inc.并致力于LLVM在Apple開發(fā)體系中的應(yīng)用球匕。Apple也是LLVM計(jì)劃的主要資助者。
• 目前LLVM已經(jīng)被蘋果IOS開發(fā)工具肛真、Xilinx Vivado谐丢、Facebook、Google等各大公司采用蚓让。
• 簡單來說乾忱，把這里的理解成某個(gè)第三方庫就行
• 這個(gè)DenseMap中的操作我只不講源碼，只分析其流程历极，感興趣可以自己深入

哈希實(shí)現(xiàn)

• 這個(gè)DenseMap本質(zhì)上是std::pair<KeyT, ValueT>窄瘟，C++中的pair類型，反正也是個(gè)鍵值對

• DenseMap同樣是個(gè)hash結(jié)構(gòu)趟卸，下面來分析它的流程【很多參數(shù)的解釋我都在代碼注釋里寫了】

• 這里借用下runtime(二) SideTables大神的圖解完全講清楚了問題蹄葱，厲害

• 首先我們有一個(gè)初始化好的, 大小為 9 的桶數(shù)組

1479888-47765d58b3dbe9b8

• 同時(shí)有 a b c d e 五個(gè)對象要使用桶數(shù)組, 這里我們假設(shè)五個(gè)對象都被哈希算法分配到下標(biāo) 0 的位置里. a 第一個(gè)進(jìn)入, 但 b c d e 由于下標(biāo) 0 處已經(jīng)不是空桶, 則需要進(jìn)行下一步哈希算法來查找合適的位置, 假設(shè)這 4 個(gè)對象又恰巧都被分配到了下標(biāo)為 1 的位置, 但只有 b 可以存入. 假設(shè)每一次哈希計(jì)算都只給下標(biāo)增加了 1, 以此類推我們能得到:

1479888-ea61e198d6f13201

• 假設(shè)這個(gè)時(shí)候 c 對象被釋放了, 之前提到過這個(gè)時(shí)候會(huì)把對應(yīng)的位置的 key 設(shè)置為 TombstoneKey:

1479888-ad718f8f3272421e

• 接下來就體現(xiàn)了墓碑的作用:
  1. 如果 c 對象銷毀后將下標(biāo) 2 的桶設(shè)置為空桶, 此時(shí)為 e 對象增加引用計(jì)數(shù), 根據(jù)哈希算法查找到下標(biāo)為 2 的桶時(shí), 就會(huì)直接插入, 無法為已經(jīng)在下標(biāo)為 4 的桶中的 e 增加引用計(jì)數(shù).
  2. 如果此時(shí)初始化了一個(gè)新的對象 f, 根據(jù)哈希算法查找到下標(biāo)為 2 的桶時(shí)發(fā)現(xiàn)桶中放置了墓碑, 此時(shí)會(huì)記錄下來下標(biāo) 2. 接下來繼續(xù)哈希算法查找位置, 查找到空桶時(shí), 就證明表中沒有對象 f, 此時(shí) f 使用記錄好的下標(biāo) 2 的桶而不是查找到的空桶, 就可以利用到已經(jīng)釋放的位置.
• 對于DenseMap的分析我們就到這

weak_table_t weak_table

/**
 * The global weak references table. Stores object ids as keys,
 * and weak_entry_t structs as their values.
 */
struct weak_table_t {
    weak_entry_t *weak_entries;  //連續(xù)地址空間的頭指針, 數(shù)組
    //管理所有指向某對象的weak指針，也是一個(gè)hash
    size_t    num_entries;  //數(shù)組中已占用位置的個(gè)數(shù)
    uintptr_t mask;  //數(shù)組下標(biāo)最大值(即數(shù)組大小 -1)
    uintptr_t max_hash_displacement;  //最大哈希偏移值
};

• weak_table并沒有直接是個(gè)數(shù)組存放weak指針锄列，而是使用一個(gè)結(jié)構(gòu)體weak_entry_t *weak_entries;去存放weak指針

weak_entry_t *weak_entries【存放weak指針】

struct weak_entry_t {
    DisguisedPtr<objc_object> referent; //被指對象的地址图云。前面循環(huán)遍歷查找的時(shí)候就是判斷目標(biāo)地址是否和他相等。
    union {
        struct {
            weak_referrer_t *referrers; //可變數(shù)組,里面保存著所有指向這個(gè)對象的弱引用的地址邻邮。當(dāng)這個(gè)對象被釋放的時(shí)候竣况，referrers里的所有指針都會(huì)被設(shè)置成nil。
            //指向 referent 對象的 weak 指針數(shù)組
            uintptr_t        out_of_line_ness : 2; //這里標(biāo)記是否超過內(nèi)聯(lián)邊界, 下面會(huì)提到
            uintptr_t        num_refs : PTR_MINUS_2; //數(shù)組中已占用的大小
            uintptr_t        mask; //數(shù)組下標(biāo)最大值(數(shù)組大小 - 1)
            uintptr_t        max_hash_displacement; //最大哈希偏移值
        };
        struct {
            // out_of_line_ness field is low bits of inline_referrers[1]
            weak_referrer_t  inline_referrers[WEAK_INLINE_COUNT]; //只有4個(gè)元素的數(shù)組筒严，默認(rèn)情況下用它來存儲弱引用的指針丹泉。當(dāng)大于4個(gè)的時(shí)候使用referrers來存儲指針情萤。
            //當(dāng)指向這個(gè)對象的weak指針不超過4個(gè)，則直接使用數(shù)組inline_referrers摹恨，省去hash
        };
    };

• 這里有見到了我們的老朋友union筋岛，也就提示我們Apple同樣是使用過同一段內(nèi)存去存放不同的信息

• 這里有兩個(gè)數(shù)組，一個(gè)是weak_referrer_t inline_referrers[WEAK_INLINE_COUNT]晒哄，數(shù)組長度只有4睁宰，當(dāng)某個(gè)對象的weak指針個(gè)數(shù)小于四的時(shí)候，會(huì)存入這個(gè)數(shù)組揩晴，當(dāng)大于四的時(shí)候才會(huì)存到referrers當(dāng)中

• 至此勋陪，所有的數(shù)據(jù)模型總結(jié)完畢

• 是不是感覺有點(diǎn)懵？

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

9970D0DFF099F1E7DE96C437DB317714

• 總之只要是數(shù)組的基本都是哈希結(jié)構(gòu)

SideTables以及SideTable的關(guān)系

• 這里借用下iOS管理對象內(nèi)存的數(shù)據(jù)結(jié)構(gòu)以及操作算法--SideTables硫兰、RefcountMap、weak_table_t-二大神的比喻
• 假設(shè)有80個(gè)學(xué)生需要咱們安排住宿寒锚，同時(shí)還要保證學(xué)生們的財(cái)產(chǎn)安全劫映。應(yīng)該怎么安排？
• 顯然不會(huì)給80個(gè)學(xué)生分別安排80間宿舍刹前，然后給每個(gè)宿舍的大門上加一把鎖泳赋。那樣太浪費(fèi)資源了鎖也挺貴的，太多的宿舍維護(hù)起來也很費(fèi)力氣喇喉。
• 我們一般的做法是把80個(gè)學(xué)生分配到10間宿舍里祖今，每個(gè)宿舍住8個(gè)人。假設(shè)宿舍號分別是101拣技、102 千诬、... 110。然后再給他們分配床位膏斤，01號床徐绑、02號床等。然后給每個(gè)宿舍配一把鎖來保護(hù)宿舍內(nèi)同學(xué)的財(cái)產(chǎn)安全莫辨。為什么不只給整個(gè)宿舍樓上一把鎖傲茄，每次有人進(jìn)出的時(shí)候都把整個(gè)宿舍樓鎖上？顯然這樣會(huì)造成宿舍樓大門口阻塞沮榜。
• OK假如現(xiàn)在有人要找102號宿舍的2號床的人聊天盘榨。這個(gè)人會(huì)怎么做？
  1蟆融、找到宿舍樓(SideTables)的宿管草巡，跟他說自己要找10202(內(nèi)存地址當(dāng)做key)。
  2振愿、宿管帶著他SideTables[10202]找到了102宿舍SideTable捷犹，然后把102的門一鎖lock弛饭，在他訪問102期間不再允許其他訪客訪問102了。(這樣只是阻塞了102的8個(gè)兄弟的訪問萍歉，而不會(huì)影響整棟宿舍樓的訪問)
  3侣颂、然后在宿舍里大喊一聲:"2號床的兄弟在哪里？"table.refcnts.find(02)你就可以找到2號床的兄弟了枪孩。
  4憔晒、等這個(gè)訪客離開的時(shí)候會(huì)把房門的鎖打開unlock，這樣其他需要訪問102的人就可以繼續(xù)進(jìn)來訪問了蔑舞。
• SideTables == 宿舍樓拒担；SideTable == 宿舍；RefcountMap里存放著具體的床位
• 蘋果之所以需要?jiǎng)?chuàng)造SideTables的Hash沖突是為了把對象放到宿舍里管理攻询，把鎖的粒度縮小到一個(gè)宿舍SideTable从撼。RefcountMap的工作是在找到宿舍以后幫助大家找到正確的床位的兄弟。
• 討論完這些問題之后钧栖，我們終于可以開始研究weak調(diào)用的方法了

weak相關(guān)的方法

objc_initWeak(id *location, id newObj)

id
objc_initWeak(id *location, id newObj)
{
    if (!newObj) {
        *location = nil;
        return nil;
    }

    return storeWeak<DontHaveOld, DoHaveNew, DoCrashIfDeallocating>
        (location, (objc_object*)newObj);
}

• 該方法中的兩個(gè)參數(shù)location是指weak 指針低零，newObj 是 weak 指針將要指向的對象

storeWeak(id *location, objc_object *newObj)

    id oldObj;
    SideTable *oldTable;
    SideTable *newTable;

    // Clean up old value, if any.
    if (haveOld) {
        weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);
    }

    // Assign new value, if any.
    if (haveNew) {
        newObj = (objc_object *)
            weak_register_no_lock(&newTable->weak_table, (id)newObj, location, 
                                  crashIfDeallocating);
        // weak_register_no_lock returns nil if weak store should be rejected

        // Set is-weakly-referenced bit in refcount table.
        if (newObj  &&  !newObj->isTaggedPointer()) {
            newObj->setWeaklyReferenced_nolock();
        }

        // Do not set *location anywhere else. That would introduce a race.
        *location = (id)newObj;
    }
    else {
        // No new value. The storage is not changed.
    }
    return (id)newObj;

• 這里要先進(jìn)行haveOld判斷，也就是如果該指針有指向的舊值拯杠，先要weak_unregister_no_lock(&oldTable->weak_table, oldObj, location);處理舊值
• 之后在weak_register_no_lock(&newTable->weak_table, (id)newObj, location,crashIfDeallocating);進(jìn)行賦值操作

weak_unregister_no_lock

//從原有的表中先刪除這個(gè) weak 指針注銷已注冊的弱引用掏婶。當(dāng)引用者的存儲即將消失，但引用還沒有死潭陪。（否則雄妥，稍后歸零引用將是內(nèi)存訪問錯(cuò)誤。）如果引用/引用不是當(dāng)前活動(dòng)的弱引用依溯，則不執(zhí)行任何操作老厌。引用不為零。
void
weak_unregister_no_lock(weak_table_t *weak_table, id referent_id, 
                        id *referrer_id)
{
    objc_object *referent = (objc_object *)referent_id; //weak 指針指向的對象
    objc_object **referrer = (objc_object **)referrer_id;  //referrer_id是 weak 指針, 操作時(shí)需要用到這個(gè)指針的地址

    weak_entry_t *entry;

    if (!referent) return;

    if ((entry = weak_entry_for_referent(weak_table, referent))) {  //查找 referent 對象對應(yīng)的 entry
        remove_referrer(entry, referrer);  //從 referent 對應(yīng)的 entry 中刪除地址為 referrer 的 weak 指針
        bool empty = true;
        if (entry->out_of_line()  &&  entry->num_refs != 0) { //如果 entry 中的數(shù)組容量大于 4 并且數(shù)組中還有元素
            empty = false; //entry 非空
        }
        else {
            for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
                if (entry->inline_referrers[i]) { //否則循環(huán)查找 entry 數(shù)組, 如果 4 個(gè)位置中有一個(gè)非空
                    empty = false;  //entry 非空
                    break;
                }
            }
        }
        if (empty) {
            weak_entry_remove(weak_table, entry); //從 weak_table 中移除該條 entry
        }
    }
}

• 這里先是remove_referrer(entry, referrer);從對應(yīng)的entry中刪除該weak記錄
• 之后我們需要判斷誓沸，還有沒有指向這個(gè)地址的weak指針了梅桩，所以有下面的判空操作，如果這個(gè)entry已經(jīng)沒有東西了拜隧，將整個(gè)刪除

weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)

• 該方法通過對象的地址宿百，獲取到該weak_table中的entry【保存著指向某對象的所有weak指針】

static weak_entry_t *
weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
{
    assert(referent);

    weak_entry_t *weak_entries = weak_table->weak_entries;

    if (!weak_entries) return nil;

    size_t begin = hash_pointer(referent) & weak_table->mask;
    size_t index = begin;
    size_t hash_displacement = 0;
    while (weak_table->weak_entries[index].referent != referent) {
        index = (index+1) & weak_table->mask;
        if (index == begin) bad_weak_table(weak_table->weak_entries);
        hash_displacement++;
        if (hash_displacement > weak_table->max_hash_displacement) {
            return nil;
        }
    }
    
    return &weak_table->weak_entries[index];
}

• hash_pointer也是使用指針地址，映射到一個(gè)索引洪添。&weak_table->mask這個(gè)操作是垦页？這個(gè)mask實(shí)際值是表的size-1,而size是2的n次方進(jìn)行擴(kuò)張的，所以mask的形式就1111 1111 1111這種干奢，索引和mask位與之后的值必定就落在了[0, size]范圍內(nèi)痊焊。也就是說，先是通過hash_pointer對地址進(jìn)行hash映射，得到下標(biāo)薄啥，接下來通過位遮蔽辕羽，保證這個(gè)映射是在范圍內(nèi)的，不會(huì)超出范圍
• index = (index+1) & weak_table->mask;是在遇到哈希沖突的時(shí)候垄惧，就一直往下找下一個(gè)位置

weak_register_no_lock

id 
weak_register_no_lock(weak_table_t *weak_table, id referent_id, 
                      id *referrer_id, bool crashIfDeallocating)
{
    objc_object *referent = (objc_object *)referent_id;
    objc_object **referrer = (objc_object **)referrer_id;
    // now remember it and where it is being stored
    weak_entry_t *entry; //如果 weak_table 有對應(yīng)的 entry
    if ((entry = weak_entry_for_referent(weak_table, referent))) {
        append_referrer(entry, referrer); //將 weak 指針存入對應(yīng)的 entry 中
    } 
    else {
        weak_entry_t new_entry(referent, referrer); //創(chuàng)建新的 entry
        weak_grow_maybe(weak_table); //查看是否需要調(diào)整 weak_table 中 weak_entries 數(shù)組大小
        weak_entry_insert(weak_table, &new_entry); //將新的 entry 插入到 weak_table 中
    }
    return referent_id;
}

• 這里如果該地址有對應(yīng)的entry刁愿，在里面存入指針；如果沒有entry到逊，就新建entry铣口，在里面插入weak指針，并插入weak_table
• 下面我們看下append_referrer的實(shí)現(xiàn)

static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
    if (! entry->out_of_line()) { //如果數(shù)組大小沒超過 4
        // Try to insert inline.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            if (entry->inline_referrers[i] == nil) { //循環(huán)查找數(shù)組成員
                entry->inline_referrers[i] = new_referrer; //把新的 weak 指針插入到空位置
                return;
            }
        }
        //也就是說走到這就是剛好之前有四個(gè)引用觉壶，現(xiàn)在添加第五個(gè)
        //數(shù)組中的 4 個(gè)位置都非空, 就要調(diào)整策略使用 referrers 了
        //從這里開始, 這一段是把 inline_referrers 數(shù)組調(diào)整為使用 referrers 的形式
        // Couldn't insert inline. Allocate out of line.
        weak_referrer_t *new_referrers = (weak_referrer_t *)
            calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t)); //還是開辟 4 個(gè) weak_referrer_t 大小的空間
        // This constructed table is invalid, but grow_refs_and_insert
        // will fix it and rehash it.
        for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
            new_referrers[i] = entry->inline_referrers[i]; //將 inline_referrers 中的值賦值給 referrers
        }
        entry->referrers = new_referrers;
        entry->num_refs = WEAK_INLINE_COUNT;
        entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
        entry->mask = WEAK_INLINE_COUNT-1;
        entry->max_hash_displacement = 0;
    }

    assert(entry->out_of_line());

    if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) {
        return grow_refs_and_insert(entry, new_referrer);
    }
    
    //開始哈希算法
    size_t begin = w_hash_pointer(new_referrer) & (entry->mask);
    size_t index = begin; //使用哈希算法計(jì)算到一個(gè)起始下標(biāo)
    size_t hash_displacement = 0; //哈希偏移次數(shù)
    while (entry->referrers[index] != nil) {  //循環(huán)找空位置
        hash_displacement++;
        index = (index+1) & entry->mask;
        if (index == begin) bad_weak_table(entry);
    }
    //這里記錄下移位的最大值, 那么數(shù)組里的任何一個(gè)數(shù)據(jù), 存儲時(shí)的移位次數(shù)都不大于這個(gè)值
    //可以提升查找時(shí)的效率, 如果移位次數(shù)超過了這個(gè)值都沒有找到, 就證明要查找的項(xiàng)不在數(shù)組中
    if (hash_displacement > entry->max_hash_displacement) {
        entry->max_hash_displacement = hash_displacement;
    }
    weak_referrer_t &ref = entry->referrers[index];
    ref = new_referrer;
    entry->num_refs++;
}

• 這里首先是要判斷關(guān)聯(lián)數(shù)組里有沒有空位【關(guān)聯(lián)數(shù)組沒有使用哈夏蕴猓】，如果關(guān)聯(lián)數(shù)組有空位的話铜靶，直接插入
• 沒有空位需要使用且是剛好第五個(gè)的情況叔遂，需要初始化一個(gè)weak_referrer_t，將關(guān)聯(lián)數(shù)組里的數(shù)據(jù)先存進(jìn)去【也就是說不會(huì)兩個(gè)一起用】
• 接下來通過哈希操作存入

賦值操作

weak_referrer_t &ref = entry->referrers[index];
ref = new_referrer;
entry->num_refs++;

• 這個(gè)賦值語句之前一直讓我百思不得其解争剿，現(xiàn)在感覺還是C語言學(xué)的不到位呀
• 首先掏熬，現(xiàn)在的index就是我們正確的插入下標(biāo)，按照我們正常人明顯應(yīng)該這么寫

entry->referrers[index] = new_referrer;
entry->num_refs++;

• 這是Apple偏偏沒有這么寫秒梅，寫了上面這三行
• 說來慚愧，我之前都覺得weak_referrer_t &ref = entry->referrers[index];明顯是錯(cuò)的舌胶，哪有初始化一個(gè)地址這個(gè)說法的
• 現(xiàn)在我的理解可能依然不太對捆蜀，我覺得是這樣，ref依然是個(gè)weak_referrer_t類型的變量幔嫂，現(xiàn)在通過&取地址符辆它，設(shè)置這個(gè)變量的地址【這里就覺得很迷了，一個(gè)結(jié)構(gòu)體的地址怎么可以變呢履恩？或者理解成ref不是一個(gè)實(shí)際上的變量锰茉，只是一個(gè)標(biāo)志符】
• 現(xiàn)在我們把referrers[index]賦給了這個(gè)地址，也就相當(dāng)于ref現(xiàn)在就是referrers[index]【自己都覺得解釋的很不清楚切心。飒筑。≌阑瑁】
• 放一段自己做的實(shí)驗(yàn)

#include <iostream>
using namespace std;

struct Padd {
    int a;
    float b;
}bucket[10];

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    int j = 0;
    float k = 16;
    for (Padd &i : bucket) {
        i.a = j++;
        i.b = k++;
    }
    for (Padd &i : bucket) {
        cout << i.a << "XXX" << i.b << endl;
    }
    
    Padd *testPadd = (Padd *)malloc(sizeof(Padd));
    testPadd->a = 99;
    testPadd->b = 109;
    Padd &ref = bucket[4];
    ref = *testPadd;
    printf("%p\n", &bucket[4]);
    printf("%p\n", &ref);
    
    for (Padd &i : bucket) {
        cout << i.a << "XXX" << i.b << endl;
    }
    
    return 0;
}

dealloc后將weak指針置nil【weak_clear_no_lock(weak_table_t *weak_table, id referent_id) 】

void 
weak_clear_no_lock(weak_table_t *weak_table, id referent_id) 
{
    objc_object *referent = (objc_object *)referent_id;
    weak_entry_t *entry = weak_entry_for_referent(weak_table, referent);
    if (entry == nil) {
        return;
    }
    weak_referrer_t *referrers;
    size_t count;
    
    if (entry->out_of_line()) {
        referrers = entry->referrers;
        count = TABLE_SIZE(entry);
    } 
    else {
        referrers = entry->inline_referrers;
        count = WEAK_INLINE_COUNT;
    }
    
    for (size_t i = 0; i < count; ++i) {
        objc_object **referrer = referrers[i];
        if (referrer) {
            if (*referrer == referent) {
                *referrer = nil;
            }
        }
    }
    
    weak_entry_remove(weak_table, entry);
}

• 前面將關(guān)聯(lián)數(shù)組和referrers都看作一個(gè)數(shù)組协屡，獲取相應(yīng)的count，進(jìn)行nil操作

方法總結(jié)

2664540-255e050c9fafa044

后續(xù)更新

對于weak對象的訪問：objc_loadWeakRetained

• 先回看下《iOS高級編程》中的描述

id  __weak obj1 = obj0;
NSLog(@"class = %@",[obj1 class]);

id __weak obj1 = obj0;
id __autoreleasing tmp = obj1;
NSLog(@"class = %@",[tmp class]);//實(shí)際訪問的是注冊到自動(dòng)釋放池的對象

• 現(xiàn)在我們有源碼了全谤，可以看看具體是怎么實(shí)現(xiàn)的

//實(shí)驗(yàn)代碼
NSObject *obj0 = [[NSObject alloc] init];
NSObject *obj1 __weak = obj0;
printf("retain count = %ld\n",CFGetRetainCount((__bridge CFTypeRef)(obj0))); //結(jié)果為1
printf("retain count = %ld\n",CFGetRetainCount((__bridge CFTypeRef)(obj1)));    //斷點(diǎn)打在這里 結(jié)果為2

• 接著跟著方法調(diào)用棧往下走肤晓，發(fā)現(xiàn)來到objc_loadWeakRetained

id
objc_loadWeakRetained(id *location)
{
    id obj;
    id result;
    Class cls;

    SideTable *table;
    
 retry:
    // fixme std::atomic this load
    obj = *location;
    if (!obj) return nil;
    if (obj->isTaggedPointer()) return obj;
    
    table = &SideTables()[obj];
    
    table->lock();
    if (*location != obj) {
        table->unlock();
        goto retry;
    }
    result = obj;

    cls = obj->ISA();
    if (! cls->hasCustomRR()) {
        // Fast case. We know +initialize is complete because
        // default-RR can never be set before then.
        assert(cls->isInitialized());
        if (! obj->rootTryRetain()) {   //rootTryRetain執(zhí)行了retain操作
            result = nil;
        }
    }    
    table->unlock();
    return result;
}

• 這過方法里的 if (! obj->rootTryRetain())這一句調(diào)用了retain方法，達(dá)到了引用計(jì)數(shù)+1，防止dealloc的作用
• 接著我們給objc_release方法打上斷點(diǎn)补憾，發(fā)現(xiàn)這句打印一結(jié)束漫萄，就會(huì)調(diào)用release方法【是誰調(diào)用的，為什么會(huì)調(diào)用的盈匾，我是一問三不知】
• 也就是說對于weak修飾對象的訪問都會(huì)調(diào)用該方法腾务，進(jìn)行retain【包括NSObject *obj0 = [[NSObject alloc] init];NSObject *obj1 __weak = obj0;NSObject *obj2 = obj1;中的第三句，也算是訪問】
• 因此威酒，書上說的autorelease的方式并不是目前真正的實(shí)現(xiàn)方式了
• 我個(gè)人認(rèn)為這種方式還要比autorelease更好理解些

isa_t中存放的引用計(jì)數(shù)

• isa_t中有這兩塊內(nèi)容窑睁，uintptr_t has_sidetable_rc【是否使用sidetable來存放引用計(jì)數(shù)】，uintptr_t extra_rc【引用計(jì)數(shù)】
• 也就是說對于能存的下的引用計(jì)數(shù)是通過isa來存儲的
• 這里我們可觀察下retainCount方法來了解下這兩塊之間的關(guān)系

inline uintptr_t 
objc_object::rootRetainCount()
{
    if (isTaggedPointer()) return (uintptr_t)this;

    sidetable_lock();
    isa_t bits = LoadExclusive(&isa.bits);
    ClearExclusive(&isa.bits);
    if (bits.nonpointer) {
        uintptr_t rc = 1 + bits.extra_rc;
        if (bits.has_sidetable_rc) {
            rc += sidetable_getExtraRC_nolock();
        }
        sidetable_unlock();
        return rc;
    }

    sidetable_unlock();
    return sidetable_retainCount();
}

• 哇葵孤，真的是好久沒看到這么簡單易懂的源碼担钮，在經(jīng)歷了各色妖魔鬼怪，現(xiàn)在這種跟幼兒讀物一樣的源碼我們讀起來完全跟割黃油一樣easy尤仍，絲滑??
• 也就是說箫津，最后返回的引用計(jì)數(shù)會(huì)是isa中的加上【如果超過限制】，sideTable中的

2019年7.27更新：為什么weak_entries中referrers要使用hash宰啦？

• 我們來理一理思路苏遥，在weak_entries中，已經(jīng)有referent存儲了被指對象的地址赡模，referrers中存放的是所有指向該對象的weak指針的地址
• 而我們使用了hash的方式存儲田炭，我們將weak指針的地址hash出一個(gè)index來存放weak指針的地址
• 有沒有覺得怪怪的？一般來說我們用key【一般是對象地址】哈希出一個(gè)index作為存放地址漓柑，存放的是對象本身教硫，也就是value
• 但在這里，等于就是用key存key了辆布。因此我之前以為這里沒必要hash瞬矩，因?yàn)榧偃缥覀兿Ｍ樵兊皆搘eak指針的地址，我們得拿weak指針的地址去找锋玲。景用。。
• 但其實(shí)這里還是因?yàn)闆]有很好的理解他的意義惭蹂，這張表不是為了查找weak指針的地址而存在的伞插，而是要記錄指向某一對象的所有weak指針而存在的，其存在的意義就是在記錄上有本身
• 我們查找某一weak指針往往基本上就是為了把記錄這個(gè)東西
• 在這張表上刪除剿干，我們的目的在于記錄本身蜂怎，而不是其value本身，以上置尔。