在isa的那節(jié)中我們提到當(dāng)extra_rc不夠用時(shí)，會借助sidetable來存儲計(jì)數(shù)值，同時(shí)，has_sidetable_rc會被標(biāo)志為1。那么這節(jié)我們就來介紹一下SideTable
SideTable
在runtime內(nèi)存空間中，SideTables是一個(gè)hash數(shù)組，里面存儲了SideTable。SideTables的hash鍵值就是一個(gè)對象obj的address。
因此可以說，一個(gè)obj，對應(yīng)了一個(gè)SideTable。但是一個(gè)SideTable，會對應(yīng)多個(gè)obj。因?yàn)镾ideTable的數(shù)量只有64個(gè)，所以會有很多obj共用同一個(gè)SideTable。
而在一個(gè)SideTable中
struct SideTable {
spinlock_t slock; // 自旋鎖，防止多線程訪問沖突
RefcountMap refcnts; // 對象引用計(jì)數(shù)map
weak_table_t weak_table; // 對象弱引用map
SideTable() {
memset(&weak_table, 0, sizeof(weak_table));
}
~SideTable() {
_objc_fatal("Do not delete SideTable.");
}
// 鎖操作 符合StripedMap對T的定義
void lock() { slock.lock(); }
void unlock() { slock.unlock(); }
void forceReset() { slock.forceReset(); }
// Address-ordered lock discipline for a pair of side tables.
template<HaveOld, HaveNew>
static void lockTwo(SideTable *lock1, SideTable *lock2);
template<HaveOld, HaveNew>
static void unlockTwo(SideTable *lock1, SideTable *lock2);
};
SideTable 翻譯過來的意思是“邊桌”，可以放一下小東西。這里，主要存放了OC對象的引用計(jì)數(shù)和弱引用相關(guān)信息
其中，refcents是一個(gè)hash map，其key是obj的地址，而value，則是obj對象的引用計(jì)數(shù)。
而weak_table則存儲了弱引用obj的指針的地址，其本質(zhì)是一個(gè)以obj地址為key，弱引用obj的指針的地址作為value的hash表。hash表的節(jié)點(diǎn)類型是weak_entry_t
SideTable的定義很清晰，有三個(gè)成員:
-
spinlock_t slock: 自旋鎖，用于上鎖/解鎖 SideTable。 -
RefcountMap refcnts：以DisguisedPtr<objc_object>為key的hash表，用來存儲OC對象的引用計(jì)數(shù)(僅在未開啟isa優(yōu)化 或 在isa優(yōu)化情況下isa_t的引用計(jì)數(shù)溢出時(shí)才會用到)。 -
weak_table_t weak_table: 存儲對象弱引用指針的hash表。是OC weak功能實(shí)現(xiàn)的核心數(shù)據(jù)結(jié)構(gòu)。
除了三個(gè)成員外，蘋果為SideTable還寫了構(gòu)造和析構(gòu)函數(shù)：
// 構(gòu)造函數(shù)
SideTable() {
memset(&weak_table, 0, sizeof(weak_table));
}
//析構(gòu)函數(shù)(看看函數(shù)體，蘋果設(shè)計(jì)的SideTable其實(shí)不希望被析構(gòu)，不然會引起fatal 錯(cuò)誤)
~SideTable() {
_objc_fatal("Do not delete SideTable.");
}
通過析構(gòu)函數(shù)可以知道，SideTable是不能被析構(gòu)的。
最后是一堆鎖的操作，用于多線程訪問SideTable：
// 鎖操作 符合StripedMap對T的定義
void lock() { slock.lock(); }
void unlock() { slock.unlock(); }
void forceReset() { slock.forceReset(); }
// Address-ordered lock discipline for a pair of side tables.
template<HaveOld, HaveNew>
static void lockTwo(SideTable *lock1, SideTable *lock2);
template<HaveOld, HaveNew>
static void unlockTwo(SideTable *lock1, SideTable *lock2);
spinlock_t slock
spinlock_t的最終定義實(shí)際上是一個(gè)uint32_t類型的非公平的自旋鎖。所謂非公平，就是說獲得鎖的順序和申請鎖的順序無關(guān)，也就是說，第一個(gè)申請鎖的線程有可能會是最后一個(gè)獲得到該鎖，或者是剛獲得鎖的線程會再次立刻獲得到該鎖，造成饑餓等待。 同時(shí)，在OC中，_os_unfair_lock_opaque也記錄了獲取它的線程信息，只有獲得該鎖的線程才能夠解開這把鎖。
typedef struct os_unfair_lock_s {
uint32_t _os_unfair_lock_opaque;
} os_unfair_lock, *os_unfair_lock_t;
關(guān)于自旋鎖的實(shí)現(xiàn)，蘋果并未公布，但是大體上應(yīng)該是通過操作_os_unfair_lock_opaque 這個(gè)uint32_t的值，當(dāng)大于0時(shí)，鎖可用，當(dāng)?shù)扔诨蛐∮?時(shí)，需要鎖等待。
RefcountMap refcnts
RefcountMap refcnts 用來存儲OC對象的引用計(jì)數(shù)。它實(shí)質(zhì)上是一個(gè)以objc_object為key的hash表，其vaule就是OC對象的引用計(jì)數(shù)。同時(shí)，當(dāng)OC對象的引用計(jì)數(shù)變?yōu)?時(shí)，會自動將相關(guān)的信息從hash表中剔除。RefcountMap的定義如下：
// RefcountMap disguises its pointers because we
// don't want the table to act as a root for `leaks`.
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;
實(shí)質(zhì)上是模板類型objc::DenseMap。模板的三個(gè)類型參數(shù)DisguisedPtr<objc_object>，size_t, true分別表示DenseMap的hash key類型，value類型，是否需要在value==0的時(shí)候自動釋放掉響應(yīng)的hash節(jié)點(diǎn)，這里是true。
weak_table_t weak_table
重點(diǎn)來了，weak_table_t weak_table 用來存儲OC對象弱引用的相關(guān)信息。我們知道，SideTables一共只有64個(gè)節(jié)點(diǎn)，而在我們的APP中，一般都會不只有64個(gè)對象，因此，多個(gè)對象一定會重用同一個(gè)SideTable節(jié)點(diǎn)，也就是說，一個(gè)weak_table會存儲多個(gè)對象的弱引用信息。因此在一個(gè)SideTable中，又會通過weak_table作為hash表再次分散存儲每一個(gè)對象的弱引用信息。
weak_table_t的定義如下：
/**
* 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; // hash數(shù)組，用來存儲弱引用對象的相關(guān)信息weak_entry_t
size_t num_entries; // hash數(shù)組中的元素個(gè)數(shù)
uintptr_t mask; // hash數(shù)組長度-1，會參與hash計(jì)算。（注意，這里是hash數(shù)組的長度，而不是元素個(gè)數(shù)。比如，數(shù)組長度可能是64，而元素個(gè)數(shù)僅存了2個(gè)）
uintptr_t max_hash_displacement; // 可能會發(fā)生的hash沖突的最大次數(shù)，用于判斷是否出現(xiàn)了邏輯錯(cuò)誤（hash表中的沖突次數(shù)絕不會超過改值）
};
weak_table_t是一個(gè)典型的hash結(jié)構(gòu)。其中 weak_entry_t *weak_entries是一個(gè)動態(tài)數(shù)組，用來存儲weak_table_t的數(shù)據(jù)元素weak_entry_t。
剩下的三個(gè)元素將會用于hash表的相關(guān)操作。weak_table的hash定位操作如下所示：
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; // 這里通過 & weak_table->mask的位操作，來確保index不會越界
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); // 觸發(fā)bad weak table crash
hash_displacement++;
if (hash_displacement > weak_table->max_hash_displacement) { // 當(dāng)hash沖突超過了可能的max hash 沖突時(shí)，說明元素沒有在hash表中，返回nil
return nil;
}
}
return &weak_table->weak_entries[index];
}
上面的定位操作還是比較清晰的，首先通過
size_t begin = hash_pointer(referent) & weak_table->mask;
來嘗試確定hash的初始位置。注意，這里做了& weak_table->mask 位操作來確保index不會越界，這同我們平時(shí)用到的取余%操作是一樣的功能。只不過這里改用了位操作，提升了效率。
然后，就開始對比hash表中的數(shù)據(jù)是否與目標(biāo)數(shù)據(jù)相等while (weak_table->weak_entries[index].referent != referent)，如果不相等，則index +1， 直到index == begin（繞了一圈）或超過了可能的hash沖突最大值。
這是weak_table_t如何進(jìn)行hash定位的相關(guān)操作。
weak_entry_t
weak_table_t中存儲的元素是weak_entry_t類型，每個(gè)weak_entry_t類型對應(yīng)了一個(gè)OC對象的弱引用信息。
weak_entry_t的結(jié)構(gòu)和weak_table_t很像，同樣也是一個(gè)hash表，其存儲的元素是weak_referrer_t，實(shí)質(zhì)上是弱引用該對象的指針的指針，即 objc_object **new_referrer ， 通過操作指針的指針，就可以使得weak 引用的指針在對象析構(gòu)后，指向nil。
// The address of a __weak variable.
// These pointers are stored disguised so memory analysis tools
// don't see lots of interior pointers from the weak table into objects.
typedef DisguisedPtr<objc_object *> weak_referrer_t;
weak_entry_t 的定義如下：
/**
* The internal structure stored in the weak references table.
* It maintains and stores
* a hash set of weak references pointing to an object.
* If out_of_line_ness != REFERRERS_OUT_OF_LINE then the set
* is instead a small inline array.
*/
#define WEAK_INLINE_COUNT 4
// out_of_line_ness field overlaps with the low two bits of inline_referrers[1].
// inline_referrers[1] is a DisguisedPtr of a pointer-aligned address.
// The low two bits of a pointer-aligned DisguisedPtr will always be 0b00
// (disguised nil or 0x80..00) or 0b11 (any other address).
// Therefore out_of_line_ness == 0b10 is used to mark the out-of-line state.
#define REFERRERS_OUT_OF_LINE 2
struct weak_entry_t {
DisguisedPtr<objc_object> referent; // 被弱引用的對象
// 引用該對象的對象列表，聯(lián)合。 引用個(gè)數(shù)小于4，用inline_referrers數(shù)組。 用個(gè)數(shù)大于4，用動態(tài)數(shù)組weak_referrer_t *referrers
union {
struct {
weak_referrer_t *referrers; // 弱引用該對象的對象指針地址的hash數(shù)組
uintptr_t out_of_line_ness : 2; // 是否使用動態(tài)hash數(shù)組標(biāo)記位
uintptr_t num_refs : PTR_MINUS_2; // hash數(shù)組中的元素個(gè)數(shù)
uintptr_t mask; // hash數(shù)組長度-1，會參與hash計(jì)算。（注意，這里是hash數(shù)組的長度，而不是元素個(gè)數(shù)。比如，數(shù)組長度可能是64，而元素個(gè)數(shù)僅存了2個(gè)）素個(gè)數(shù)）。
uintptr_t max_hash_displacement; // 可能會發(fā)生的hash沖突的最大次數(shù)，用于判斷是否出現(xiàn)了邏輯錯(cuò)誤（hash表中的沖突次數(shù)絕不會超過改值）
};
struct {
// out_of_line_ness field is low bits of inline_referrers[1]
weak_referrer_t inline_referrers[WEAK_INLINE_COUNT];
};
};
bool out_of_line() {
return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
}
weak_entry_t& operator=(const weak_entry_t& other) {
memcpy(this, &other, sizeof(other));
return *this;
}
weak_entry_t(objc_object *newReferent, objc_object **newReferrer)
: referent(newReferent) // 構(gòu)造方法，里面初始化了靜態(tài)數(shù)組
{
inline_referrers[0] = newReferrer;
for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
inline_referrers[i] = nil;
}
}
};
weak_entry_t的結(jié)構(gòu)也比較清晰：
-
DisguisedPtr<objc_object> referent：弱引用對象指針摘要。其實(shí)可以理解為弱引用對象的指針，只不過這里使用了摘要的形式存儲。（所謂摘要，其實(shí)是把地址取負(fù)）。 -
union：接下來是一個(gè)聯(lián)合，union有兩種形式：定長數(shù)組weak_referrer_t inline_referrers[WEAK_INLINE_COUNT]和動態(tài)數(shù)組 weak_referrer_t *referrers。這兩個(gè)數(shù)組是用來存儲弱引用該對象的指針的指針的，同樣也使用了指針摘要的形式存儲。當(dāng)弱引用該對象的指針數(shù)目小于等于WEAK_INLINE_COUNT時(shí)，使用定長數(shù)組。當(dāng)超過WEAK_INLINE_COUNT時(shí)，會將定長數(shù)組中的元素轉(zhuǎn)移到動態(tài)數(shù)組中，并之后都是用動態(tài)數(shù)組存儲。關(guān)于定長數(shù)組/動態(tài)數(shù)組 切換這部分，我們在稍后詳細(xì)分析。 -
bool out_of_line()： 該方法用來判斷當(dāng)前的weak_entry_t是使用的定長數(shù)組還是動態(tài)數(shù)組。當(dāng)返回true，此時(shí)使用的動態(tài)數(shù)組，當(dāng)返回false，使用靜態(tài)數(shù)組。 -
weak_entry_t& operator=(const weak_entry_t& other)：賦值方法 -
weak_entry_t(objc_object *newReferent, objc_object **newReferrer)：構(gòu)造方法。
定長數(shù)組 / 動態(tài)數(shù)組
weak_entry_t會存儲所有弱引用該對象的指針的指針。存儲類型為weak_referrer_t，其實(shí)就是弱引用指針的指針。但是是以指針摘要的形式存儲的：
typedef DisguisedPtr<objc_object *> weak_referrer_t;
weak_entry_t會將weak_referrer_t存儲到hash數(shù)組中，而這個(gè)hash數(shù)組會有兩種形態(tài)：定長數(shù)組/動態(tài)數(shù)組：
union {
// 動態(tài)數(shù)組模式
struct {
weak_referrer_t *referrers; // 弱引用該對象的對象指針地址的hash數(shù)組
uintptr_t out_of_line_ness : 2; // 是否使用動態(tài)hash數(shù)組標(biāo)記位
uintptr_t num_refs : PTR_MINUS_2; // hash數(shù)組中的元素個(gè)數(shù)
uintptr_t mask; // hash數(shù)組長度-1，會參與hash計(jì)算。（注意，這里是hash數(shù)組的長度，而不是元素個(gè)數(shù)。比如，數(shù)組長度可能是64，而元素個(gè)數(shù)僅存了2個(gè)）素個(gè)數(shù)）。
uintptr_t max_hash_displacement; // 可能會發(fā)生的hash沖突的最大次數(shù)，用于判斷是否出現(xiàn)了邏輯錯(cuò)誤（hash表中的沖突次數(shù)絕不會超過改值）
};
// 定長數(shù)組模式
struct {
// out_of_line_ness field is low bits of inline_referrers[1]
weak_referrer_t inline_referrers[WEAK_INLINE_COUNT];
};
};
bool out_of_line() {
return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
}
當(dāng)弱引用指針個(gè)數(shù)少于等于WEAK_INLINE_COUNT時(shí)，會使用定長數(shù)組inline_referrers。而當(dāng)大于WEAK_INLINE_COUNT時(shí)，則會轉(zhuǎn)換到動態(tài)數(shù)組模式 weak_referrer_t *referrers。
之所以做定長/動態(tài)數(shù)組的切換，應(yīng)該是蘋果考慮到弱引用的指針個(gè)數(shù)一般不會超過WEAK_INLINE_COUNT個(gè)。這時(shí)候使用定長數(shù)組，不需要動態(tài)的申請內(nèi)存空間，而是一次分配一塊連續(xù)的內(nèi)存空間。這會得到運(yùn)行效率上的提升。
至于weak_entry_t是使用的定長/動態(tài)數(shù)組，蘋果提供了方法：
#define REFERRERS_OUT_OF_LINE 2
bool out_of_line() {
return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
}
該方法的實(shí)質(zhì)是測試定長數(shù)組第二個(gè)元素值的2進(jìn)制位第2位是否等于01。因?yàn)楦鶕?jù)蘋果的注釋，inline_referrers[1]中存儲的是pointer-aligned DisguisedPtr ，即指針對齊的指針摘要，其最低位一定是0b00或0b11，因此可以用0b10 表示使用了動態(tài)數(shù)組。
下面我就來看一下weak_entry_t中是如何插入元素的：
/**
* Add the given referrer to set of weak pointers in this entry.
* Does not perform duplicate checking (b/c weak pointers are never
* added to a set twice).
*
* @param entry The entry holding the set of weak pointers.
* @param new_referrer The new weak pointer to be added.
*/
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
if (! entry->out_of_line()) { // 如果weak_entry 尚未使用動態(tài)數(shù)組，走這里
// Try to insert inline.
for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
if (entry->inline_referrers[i] == nil) {
entry->inline_referrers[i] = new_referrer;
return;
}
}
// 如果inline_referrers的位置已經(jīng)存滿了，則要轉(zhuǎn)型為referrers，做動態(tài)數(shù)組。
// Couldn't insert inline. Allocate out of line.
weak_referrer_t *new_referrers = (weak_referrer_t *)
calloc(WEAK_INLINE_COUNT, sizeof(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];
}
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;
}
// 對于動態(tài)數(shù)組的附加處理：
assert(entry->out_of_line()); // 斷言： 此時(shí)一定使用的動態(tài)數(shù)組
if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { // 如果動態(tài)數(shù)組中元素個(gè)數(shù)大于或等于數(shù)組位置總空間的3/4，則擴(kuò)展數(shù)組空間為當(dāng)前長度的一倍
return grow_refs_and_insert(entry, new_referrer); // 擴(kuò)容，并插入
}
// 如果不需要擴(kuò)容，直接插入到weak_entry中
// 注意，weak_entry是一個(gè)哈希表，key：w_hash_pointer(new_referrer) value: new_referrer
// 細(xì)心的人可能注意到了，這里weak_entry_t 的hash算法和 weak_table_t的hash算法是一樣的，同時(shí)擴(kuò)容/減容的算法也是一樣的
size_t begin = w_hash_pointer(new_referrer) & (entry->mask); // '& (entry->mask)' 確保了 begin的位置只能大于或等于 數(shù)組的長度
size_t index = begin; // 初始的hash index
size_t hash_displacement = 0; // 用于記錄hash沖突的次數(shù)，也就是hash再位移的次數(shù)
while (entry->referrers[index] != nil) {
hash_displacement++;
index = (index+1) & entry->mask; // index + 1, 移到下一個(gè)位置，再試一次能否插入。（這里要考慮到entry->mask取值，一定是：0x111, 0x1111, 0x11111, ... ，因?yàn)閿?shù)組每次都是*2增長，即8， 16， 32，對應(yīng)動態(tài)數(shù)組空間長度-1的mask，也就是前面的取值。）
if (index == begin) bad_weak_table(entry); // index == begin 意味著數(shù)組繞了一圈都沒有找到合適位置，這時(shí)候一定是出了什么問題。
}
if (hash_displacement > entry->max_hash_displacement) { // 記錄最大的hash沖突次數(shù), max_hash_displacement意味著: 我們嘗試至多max_hash_displacement次，肯定能夠找到object對應(yīng)的hash位置
entry->max_hash_displacement = hash_displacement;
}
// 將ref存入hash數(shù)組，同時(shí)，更新元素個(gè)數(shù)num_refs
weak_referrer_t &ref = entry->referrers[index];
ref = new_referrer;
entry->num_refs++;
}
代碼可以分成兩部分理解，一部分是使用定長數(shù)組的情況：
if (! entry->out_of_line()) { // 如果weak_entry 尚未使用動態(tài)數(shù)組，走這里
// Try to insert inline.
for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
if (entry->inline_referrers[i] == nil) {
entry->inline_referrers[i] = new_referrer;
return;
}
}
// 如果inline_referrers的位置已經(jīng)存滿了，則要轉(zhuǎn)型為referrers，做動態(tài)數(shù)組。
// Couldn't insert inline. Allocate out of line.
weak_referrer_t *new_referrers = (weak_referrer_t *)
calloc(WEAK_INLINE_COUNT, sizeof(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];
}
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;
}
定長數(shù)組的邏輯很簡單，直接安裝數(shù)組順序，將new_referrer插入即可。如果定長數(shù)組已經(jīng)用盡，則將定長數(shù)組轉(zhuǎn)型為動態(tài)數(shù)組：
weak_referrer_t *new_referrers = (weak_referrer_t *)
calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
...
entry->referrers = new_referrers; // hash數(shù)組由 entry->inline_referrers轉(zhuǎn)換為 entry->referrers
要注意，定長數(shù)組轉(zhuǎn)換為動態(tài)數(shù)組后，新的元素并沒有插入到數(shù)組中，而僅是將原來定長數(shù)組中的內(nèi)容轉(zhuǎn)移到了動態(tài)數(shù)組中。新元素的插入邏輯，在下面動態(tài)數(shù)組部分：
...
// 對于動態(tài)數(shù)組的附加處理：
assert(entry->out_of_line()); // 斷言： 此時(shí)一定使用的動態(tài)數(shù)組
if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { // 如果動態(tài)數(shù)組中元素個(gè)數(shù)大于或等于數(shù)組位置總空間的3/4，則擴(kuò)展數(shù)組空間為當(dāng)前長度的一倍
return grow_refs_and_insert(entry, new_referrer); // 擴(kuò)容，并插入
}
// 如果不需要擴(kuò)容，直接插入到weak_entry中
// 注意，weak_entry是一個(gè)哈希表，key：w_hash_pointer(new_referrer) value: new_referrer
// 細(xì)心的人可能注意到了，這里weak_entry_t 的hash算法和 weak_table_t的hash算法是一樣的，同時(shí)擴(kuò)容/減容的算法也是一樣的
size_t begin = w_hash_pointer(new_referrer) & (entry->mask); // '& (entry->mask)' 確保了 begin的位置只能大于或等于 數(shù)組的長度
size_t index = begin; // 初始的hash index
size_t hash_displacement = 0; // 用于記錄hash沖突的次數(shù)，也就是hash再位移的次數(shù)
while (entry->referrers[index] != nil) {
hash_displacement++;
index = (index+1) & entry->mask; // index + 1, 移到下一個(gè)位置，再試一次能否插入。（這里要考慮到entry->mask取值，一定是：0x111, 0x1111, 0x11111, ... ，因?yàn)閿?shù)組每次都是*2增長，即8， 16， 32，對應(yīng)動態(tài)數(shù)組空間長度-1的mask，也就是前面的取值。）
if (index == begin) bad_weak_table(entry); // index == begin 意味著數(shù)組繞了一圈都沒有找到合適位置，這時(shí)候一定是出了什么問題。
}
if (hash_displacement > entry->max_hash_displacement) { // 記錄最大的hash沖突次數(shù), max_hash_displacement意味著: 我們嘗試至多max_hash_displacement次，肯定能夠找到object對應(yīng)的hash位置
entry->max_hash_displacement = hash_displacement;
}
// 將ref存入hash數(shù)組，同時(shí)，更新元素個(gè)數(shù)num_refs
weak_referrer_t &ref = entry->referrers[index];
ref = new_referrer;
entry->num_refs++;
}
其實(shí)這部分的邏輯和weak_table_t中插入weak_entry_t是非常類似的。都使用了mask取余來解決hash沖突。
我們可以再細(xì)看一下動態(tài)數(shù)組是如何動態(tài)擴(kuò)容的：
if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { // 如果動態(tài)數(shù)組中元素個(gè)數(shù)大于或等于數(shù)組位置總空間的3/4，則擴(kuò)展數(shù)組空間為當(dāng)前長度的一倍
return grow_refs_and_insert(entry, new_referrer); // 擴(kuò)容，并插入
}
/**
* Grow the entry's hash table of referrers. Rehashes each
* of the referrers.
*
* @param entry Weak pointer hash set for a particular object.
*/
__attribute__((noinline, used))
static void grow_refs_and_insert(weak_entry_t *entry,
objc_object **new_referrer)
{
assert(entry->out_of_line());
size_t old_size = TABLE_SIZE(entry);
size_t new_size = old_size ? old_size * 2 : 8; // 每次擴(kuò)容為上一次容量的2倍
size_t num_refs = entry->num_refs;
weak_referrer_t *old_refs = entry->referrers;
entry->mask = new_size - 1;
entry->referrers = (weak_referrer_t *)
calloc(TABLE_SIZE(entry), sizeof(weak_referrer_t));
entry->num_refs = 0;
entry->max_hash_displacement = 0;
// 這里可以看到，舊的數(shù)據(jù)需要依次轉(zhuǎn)移到新的內(nèi)存中
for (size_t i = 0; i < old_size && num_refs > 0; i++) {
if (old_refs[i] != nil) {
append_referrer(entry, old_refs[i]); // 將舊的數(shù)據(jù)轉(zhuǎn)移到新的動態(tài)數(shù)組中
num_refs--;
}
}
// Insert
append_referrer(entry, new_referrer);
if (old_refs) free(old_refs); // 釋放舊的內(nèi)存
}
通過代碼可以看出，每一次動態(tài)數(shù)組的擴(kuò)容，都需要將舊的數(shù)據(jù)重新插入到新的數(shù)組中。
SideTables
再來說一下最外層的SideTables。SideTables可以理解為一個(gè)全局的hash數(shù)組，里面存儲了SideTable類型的數(shù)據(jù)，其長度為64。
SideTabls可以通過全局的靜態(tài)函數(shù)獲?。?/p>
static StripedMap<SideTable>& SideTables() {
return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);
}
可以看到，SideTabls 實(shí)質(zhì)類型為模板類型StripedMap 。
StripedMap
我們來看StripedMap模板的定義：
// StripedMap<T> is a map of void* -> T, sized appropriately
// for cache-friendly lock striping.
// For example, this may be used as StripedMap<spinlock_t>
// or as StripedMap<SomeStruct> where SomeStruct stores a spin lock.
template<typename T>
class StripedMap {
enum { CacheLineSize = 64 };
#if TARGET_OS_EMBEDDED
enum { StripeCount = 8 };
#else
enum { StripeCount = 64 }; // iOS 設(shè)備的StripeCount = 64
#endif
struct PaddedT {
T value alignas(CacheLineSize); // T value 64字節(jié)對齊
};
PaddedT array[StripeCount]; // 所有PaddedT struct 類型數(shù)據(jù)被存儲在array數(shù)組中。iOS 設(shè)備 StripeCount == 64
static unsigned int indexForPointer(const void *p) { // 該方法以void *作為key 來獲取void *對應(yīng)在StripedMap 中的位置
uintptr_t addr = reinterpret_cast<uintptr_t>(p);
return ((addr >> 4) ^ (addr >> 9)) % StripeCount; // % StripeCount 防止index越界
}
public:
// 取值方法 [p],
T& operator[] (const void *p) {
return array[indexForPointer(p)].value;
}
const T& operator[] (const void *p) const {
return const_cast<StripedMap<T>>(this)[p];
}
// Shortcuts for StripedMaps of locks.
void lockAll() {
for (unsigned int i = 0; i < StripeCount; i++) {
array[i].value.lock();
}
}
void unlockAll() {
for (unsigned int i = 0; i < StripeCount; i++) {
array[i].value.unlock();
}
}
void forceResetAll() {
for (unsigned int i = 0; i < StripeCount; i++) {
array[i].value.forceReset();
}
}
void defineLockOrder() {
for (unsigned int i = 1; i < StripeCount; i++) {
lockdebug_lock_precedes_lock(&array[i-1].value, &array[i].value);
}
}
void precedeLock(const void *newlock) {
// assumes defineLockOrder is also called
lockdebug_lock_precedes_lock(&array[StripeCount-1].value, newlock);
}
void succeedLock(const void *oldlock) {
// assumes defineLockOrder is also called
lockdebug_lock_precedes_lock(oldlock, &array[0].value);
}
const void *getLock(int i) {
if (i < StripeCount) return &array[i].value;
else return nil;
}
};
可以知道， StripedMap 是一個(gè)以void *為hash key，T為vaule的hash 表。
hash定位的算法如下：
static unsigned int indexForPointer(const void *p) { // 該方法以void *作為key 來獲取void *對應(yīng)在StripedMap 中的位置
uintptr_t addr = reinterpret_cast<uintptr_t>(p);
return ((addr >> 4) ^ (addr >> 9)) % StripeCount; // % StripeCount 防止index越界
}
把地址指針右移4位異或地址指針右移9位，為什么這么做，也不用關(guān)心。我們只要關(guān)心重點(diǎn)是最后的值要取余StripeCount，來防止index越界就好。
StripedMap的所有T類型數(shù)據(jù)都被封裝到PaddedT中：
struct PaddedT {
T value alignas(CacheLineSize); // T value 64字節(jié)對齊
};
之所以再次封裝到PaddedT （有填充的T）中，是為了字節(jié)對齊，估計(jì)是存取hash值時(shí)的效率考慮。
接下來，這些PaddedT被放到數(shù)組array中：
PaddedT array[StripeCount]; // 所有PaddedT struct 類型數(shù)據(jù)被存儲在array數(shù)組中。iOS 設(shè)備 StripeCount == 64
然后，蘋果為array數(shù)組寫了一些公共的存取數(shù)據(jù)的方法，主要是調(diào)用indexForPointer方法，使得外部傳入的對象地址指針直接hash到對應(yīng)的array節(jié)點(diǎn)：
// 取值方法 [p],
T& operator[] (const void *p) {
return array[indexForPointer(p)].value;
}
const T& operator[] (const void *p) const {
return const_cast<StripedMap<T>>(this)[p];
}
接下來是一堆鎖的操作，由于SideTabls是一個(gè)全局的hash表，因此當(dāng)然必須要帶鎖訪問。StripedMap提供了一些便捷的鎖操作方法：
// Shortcuts for StripedMaps of locks.
void lockAll() {
for (unsigned int i = 0; i < StripeCount; i++) {
array[i].value.lock();
}
}
void unlockAll() {
for (unsigned int i = 0; i < StripeCount; i++) {
array[i].value.unlock();
}
}
void forceResetAll() {
for (unsigned int i = 0; i < StripeCount; i++) {
array[i].value.forceReset();
}
}
void defineLockOrder() {
for (unsigned int i = 1; i < StripeCount; i++) {
lockdebug_lock_precedes_lock(&array[i-1].value, &array[i].value);
}
}
void precedeLock(const void *newlock) {
// assumes defineLockOrder is also called
lockdebug_lock_precedes_lock(&array[StripeCount-1].value, newlock);
}
void succeedLock(const void *oldlock) {
// assumes defineLockOrder is also called
lockdebug_lock_precedes_lock(oldlock, &array[0].value);
}
const void *getLock(int i) {
if (i < StripeCount) return &array[i].value;
else return nil;
}
可以看到，所有的StripedMap鎖操作，最終是調(diào)用的array[i].value的相關(guān)操作。因此，對于模板的抽象數(shù)據(jù)T類型，必須具備相關(guān)的lock操作接口。
因此，要用StripedMap作為模板hash表，對于T類型還是有所要求的。而在SideTables中，T即為SideTable類型，我們在上面也看到SideTable是如何符合StripedMap的數(shù)據(jù)類型要求的。
總結(jié)
以上面就是在runtime中，關(guān)于對象引用計(jì)數(shù)和weak引用相關(guān)的數(shù)據(jù)結(jié)構(gòu)。
