SideTables分析
SideTables與iOS內(nèi)存管理息息相關(guān)圃阳，今天就來研究一下SideTables怀读，先看一下SideTables的定義
static StripedMap<SideTable>& SideTables() {
return *reinterpret_cast<StripedMap<SideTable>*>(SideTableBuf);
}
SideTablesde的實(shí)質(zhì)類型是存儲SideTable的StripedMap蘸炸。在StripedMap類中有StripeCount定義存儲sidetable的最大數(shù)量揽涮，所以每個(gè)SideTablesdes可以對應(yīng)多個(gè)對象，而每個(gè)對象對應(yīng)一個(gè)sidetable。
SideTable中包含三個(gè)成員桦卒，自旋鎖，引用計(jì)數(shù)表匿又，弱引用表方灾。
- spinlock_t slock;
- RefcountMap refcnts;
- weak_table_t weak_table;
這里的slock是一個(gè)自旋鎖，就是為了保證多線程訪問安全性
refcnts本質(zhì)是一個(gè)存儲對象引用計(jì)數(shù)的hash表碌更，key為對象裕偿，value為引用計(jì)數(shù)（優(yōu)化過得isa中，引用計(jì)數(shù)主要存儲在isa中）
weak_table是存儲對象弱引用的一個(gè)結(jié)構(gòu)體痛单，該結(jié)構(gòu)體內(nèi)成員如下
- weak_entry_t *weak_entries;
- size_t num_entries;
- uintptr_t mask;
- uintptr_t max_hash_displacement;
簡單介紹完SideTables相關(guān)數(shù)據(jù)結(jié)構(gòu)關(guān)系嘿棘，下面來逐個(gè)分析分析一下
StripedMap
StripedMap是定義在objc-private.h中的一個(gè)類，具體代碼太長旭绒，不再這里貼了鸟妙，只介紹里面重要的內(nèi)容
1、StripeCount定義了里面存儲對象最大數(shù)量挥吵。
enum { StripeCount = 8 };
2重父、定義結(jié)構(gòu)體PaddedT包裝傳入泛型(這里指的是SideTable)，這里使alignas(CacheLineSize)方法使字節(jié)對齊忽匈。猜測字節(jié)對齊的目的是提高存取hash值時(shí)的效率房午。
struct PaddedT {
T value alignas(CacheLineSize);
};
3、實(shí)現(xiàn)了index計(jì)算的hash算法indexForPointer
static unsigned int indexForPointer(const void *p) {
uintptr_t addr = reinterpret_cast<uintptr_t>(p);
return ((addr >> 4) ^ (addr >> 9)) % StripeCount;
}
4脉幢、獲取sidetable的操作getLock方法
const void *getLock(int i) {
if (i < StripeCount) return &array[i].value;
else return nil;
}
5歪沃、其他鎖操作array[i].value.lock，或者array[i].value.unlock(),調(diào)用的是sidetable中的鎖
void lockAll() {
for (unsigned int i = 0; i < StripeCount; i++) {
array[i].value.lock();
}
}
6嫌松、構(gòu)造方法StripedMap(),具體實(shí)現(xiàn)沒有開元沪曙，只能看出DEBUG模式下有部分操作
#if DEBUG
StripedMap() {
// Verify alignment expectations.
uintptr_t base = (uintptr_t)&array[0].value;
uintptr_t delta = (uintptr_t)&array[1].value - base;
assert(delta % CacheLineSize == 0);
assert(base % CacheLineSize == 0);
}
#else
constexpr StripedMap() {}
#endif
引用計(jì)數(shù)refcnts 存儲結(jié)構(gòu)RefcountMap
RefcountMap定義如下，他的類型是objc::DenseMap萎羔。
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;
三個(gè)參數(shù)分別代表對象的hash key液走，引用計(jì)數(shù)，是否需要在引用計(jì)數(shù)為0的時(shí)候自動釋放相應(yīng)的hash節(jié)點(diǎn)贾陷。這里默認(rèn)傳true缘眶。所以對象的引用計(jì)數(shù)refcnts不一定存在。在優(yōu)化過得isa中由extra_rc來存儲引用計(jì)數(shù)髓废，只有其存儲計(jì)數(shù)上溢出的時(shí)候才會存入sidetable中的refcnts巷懈。
弱引用表 weak_table_t weak_table
上面有說過一個(gè)sidetable中存儲多個(gè)對象的信息，弱引用表weak_table_t又是一個(gè)結(jié)構(gòu)體慌洪，所以在weak_table_t里面也存儲著多個(gè)對象信息顶燕。其中weak_entries是一個(gè)hash數(shù)組凑保，存儲弱引用對象的相關(guān)信息weak_entry_t。num_entries表示weak_entries數(shù)組中元素個(gè)數(shù)涌攻。另外兩個(gè)參數(shù)mask和 max_hash_displacement 都是uintptr_t(無符號long)類型的欧引，mask一般是做位運(yùn)算定義的值。max_hash_displacement則表示hash沖突的最大次數(shù)
下面的代碼是weak_table中通過對象獲取weak_entry_t的方法恳谎。在這個(gè)方法中可以看出mask餐椅了hash值的計(jì)算芝此，hash沖突次數(shù)超過max_hash_displacement之后，就直接返回nil因痛。
使用hash_pointer(referent) 和 weak_table->mask進(jìn)行與運(yùn)算婚苹。通過&運(yùn)算保證index不會越界，所以可以推測出mask的值為hash數(shù)組長度-1鸵膏。
這里hash沖突的解決方案是計(jì)算出hash位置index租副，判斷index中存儲referent是否與目標(biāo)referent相等，不相等的話后移一位繼續(xù)判斷较性，并將hash_displacement++，記錄移動次數(shù)结胀。當(dāng)hash_displacement的值大于max_hash_displacement時(shí)赞咙，直接返回nil。當(dāng)index == begin時(shí)糟港，即遍歷一圈也沒找到目標(biāo)對象攀操，直接調(diào)用bad_weak_table報(bào)錯。
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];
}
weak_entry_t
weak_entry_t存儲著某個(gè)對象的弱引用信息秸抚，又是一個(gè)結(jié)構(gòu)體速和。跟weak_table_t類似，里面存儲一個(gè)hash表weak_referrer_t剥汤，弱引用該"對象的指針"的指針颠放。通過weak_referrer_t的操作，可以使該對象的弱引用指針在對象釋放后吭敢，置為nil碰凶。
weak_entry_t的定義如下：
struct weak_entry_t {
DisguisedPtr<objc_object> referent;
union {
struct {
weak_referrer_t *referrers;
uintptr_t out_of_line_ness : 2;
uintptr_t num_refs : PTR_MINUS_2;
uintptr_t mask;
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];
};
};
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)
{
inline_referrers[0] = newReferrer;
for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
inline_referrers[i] = nil;
}
}
};
DisguisedPtr<objc_object> referent ：弱引用對象指針摘要。其實(shí)可以理解為弱引用對象的指針鹿驼，只不過這里使用了摘要的形式存儲欲低。（所謂摘要，其實(shí)是把地址取負(fù)）畜晰。
weak_referrer_t：這是一個(gè)共用體砾莱，分動態(tài)數(shù)組和固定長度數(shù)組兩種情況，
out_of_line：bool類型區(qū)分是weak_referrer_t中數(shù)組類型
weak_entry_t& operator=(const weak_entry_t& other)：賦值
weak_entry_t(objc_object *newReferent, objc_object **newReferrer) 構(gòu)造
指針數(shù)組weak_referrer_t
typedef DisguisedPtr<objc_object *> weak_referrer_t;
weak_referrer_t以指針摘要的形式凄鼻，存儲 弱引用指針 的指針腊瑟。weak_referrer_t數(shù)組這里設(shè)置了兩種模式聚假，畢竟動態(tài)數(shù)組涉及到更多的操作，在小數(shù)據(jù)量的情況下扫步，使用定長數(shù)組效率更高魔策。
總結(jié)
全局維護(hù)一個(gè)sidetables，
sidetables里面包含多個(gè)sidetabl河胎，可以通過對象的hash查找到對象存在的sidetable闯袒。
一個(gè)sidetable對應(yīng)多個(gè)對象。里面有一個(gè)引用計(jì)數(shù)表游岳，一個(gè)弱引用表
再次對對象hash計(jì)算值可以從sidetable中RefcountMap中獲取對象引用計(jì)數(shù)
從weak_table_t中保存著的一個(gè)sidetable中所有weak_entries表
從weak_entries中通過對象查找著某個(gè)對象對應(yīng)的弱引用信息weak_entry_t
weak_entry_t中保存著弱引用該對象的 指針地址的hash數(shù)組
弱引用表使用舉例
其他還好理解政敢，弱引用比較繞。這里舉個(gè)實(shí)例
NSObject *obj = [[NSObject alloc] init];
__weak id weakObj = obj;
在這段代碼里胚迫，用weakObj指向obj時(shí)
1喷户、會通過obj從sidetables中找到sidetable
2、找到sidetable中的弱引用表weak_table_t
3访锻、通過obj從weak_table_t中的weak_entries找到obj對應(yīng)的weak_entry_t
4褪尝、在obj對應(yīng)的weak_entry_t的weak_referrer_t中加入weakObj指針
當(dāng)obj釋放時(shí)，會判斷obj的weakly_referenced是否為1期犬，即obj是否被弱引用河哑。如果被弱引用，則進(jìn)行下面的操作
1龟虎、會通過obj從sidetables中找到sidetable
2璃谨、找到sidetable中的弱引用表weak_table_t
3、通過obj從weak_table_t中的weak_entries找到obj對應(yīng)的weak_entry_t
4鲤妥、查找weak_entry_t中的weak_referrer_t數(shù)組佳吞，并將weak_referrer_t中存儲的指針（這里指weakObj）指向nil
