学计算机的那个

不是我觉到、悟到，你给不了我，给了也拿不住;只有我觉到、悟到，才有可能做到，能做到的才是我的.

0%

Objective-C方法缓存实现

发表于 更新于 分类于 ，

为什么需要学习Objective-C底层实现，因为底层使用的技术都是值得花时间学习的，特别是使用的数据结构，通常都是权衡使用场景，以及考虑后续可持续迭代的优质代码。

OC为了实现其动态性，将方法的调用包装成了SEL寻找IMP的过程。OC采用了方法缓存的机制来提高调用效率，也就是cache_t，其作用就是缓存已调用的方法。

cache_t 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct cache_t {
    struct bucket_t *_buckets;  //8		缓存数组，即哈希桶
    mask_t _mask;               //4      typedef uint32_t mask_t;  缓存数组的容量临界值
    mask_t _occupied;           //4		缓存数组中已缓存方法数量

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

    mask_t capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

    static size_t bytesForCapacity(uint32_t cap);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);

    void expand();
    void reallocate(mask_t oldCapacity, mask_t newCapacity);
    struct bucket_t * find(SEL sel, id receiver);

    static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn));
};

mask_t cache_t::mask() 
{
    return _mask; 
}

mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}

typedef unsigned long 	uintptr_t;
typedef uintptr_t 	cache_key_t;

struct bucket_t {
    cache_key_t _key;
    MethodCacheIMP _imp;
}

_buckets：一个指向bucket_t结构体的数组，bucket_t是用来存放方法的SEL内存地址和IMP的；
_mask的大小是数组大小 - 1，用作掩码（因为这里维护的数组大小都是2的整数次幂，所以_mask的二进制位000011, 000111, 001111）刚好可以用作hash取余数的掩码。刚好保证相与后不超过缓存大小。
_occupied是当前已缓存的方法数。即数组中已使用了多少位置

_key:cache_key_t 就是 unsigned long类型，用来存储SEL的内存地址。SEL应该是char*类型的字符串，char*强转unsigned long，其实就是SEL的内存地址。代码如下
_imp就是方法实现IMP了

1
2
3
4
5
6
7
cache_key_t key = getKey(sel);

cache_key_t getKey(SEL sel) 
{
    assert(sel);
    return (cache_key_t)sel;
}

掩码_mask设计

如果_mask是0，说明未调用实例方法，即桶的容量为0；
当_mask不等于0的时候，意味着已经调用过实例方法，此时桶的容量为_mask + 1。故，_mask从侧面反映了桶的容量。

掩码（Mask）在计算机科学及数字逻辑中指的是一串二进制数字，通过与目标数字的按位操作，达到屏蔽指定位而实现需求。（eg：子网掩码）

SEL

  • 使用 @selector(hello) 生成的选择子，是否会因为类的不同而不同？
    使用 @selector() 生成的选择子不会因为类的不同而改变，其内存地址在编译期间就已经确定了。也就是说向不同的类发送相同的消息时，其生成的选择子是完全相同的。

  • SEL特性

  1. Objective-C 为我们维护了一个巨大的选择子表
  2. 在使用 @selector() 时会从这个选择子表中根据选择子的名字查找对应的 SEL。如果没有找到，则会生成一个 SEL 并添加到表中
  3. 在编译期间会扫描全部的头文件和实现文件将其中的方法以及使用 @selector() 生成的选择子加入到选择子表中

cache_t方法缓存原理

OC方法的本质是消息发送（objc_msgSend),底层是通过方法的SEL查找IMP

cache_t的存入

  1. 先看缓存中是否已经存在了该方法，如果已经存在，直接return，不再缓存

  2. 从class中拿到cache列表，将sel转换为内存地址

  • 如果当前cache还没被初始化，则分配一个大小为4的数组，并设置_mask为3
  • 如果存入缓存后的大小小于当前大小的3/4，则当前缓存大小还可以使用，无需扩容
  • 否则缓存太满，需要扩容，扩容为原来大小的2倍，放弃旧的缓存，新扩容的缓存为空。
  1. 将_key与_mask相与，因为_mask是原数组的大小-1，所以得到的结果刚好小于数组的大小
  2. 如果得到的位置已经被占用，则往后寻找，直到找到空的位置，把缓存设置到这个位置。

cache_fill_nolock 方法

这个函数的作用是将方法的SEL和IMP写入_buckets,同时更新_mask和_occupied

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    // 因为cache_t内部用来储存的结构其实就是个数组
    // 所以操作的时候需要先加个锁，保证线程安全。
    mutex_locker_t lock(cacheUpdateLock);
    cache_fill_nolock(cls, sel, imp, receiver);
}


static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();

    // Never cache before +initialize is done
    if (!cls->isInitialized()) return; //如果类未初始化

    // Make sure the entry wasnot added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    //判断方法是否已经缓存了，如果缓存了，直接返回，如果没有，则进入下面的逻辑进行缓存。
    if (cache_getImp(cls, sel)) return; 

    cache_t *cache = getCache(cls);
     // 将方法名转成对应的key
    cache_key_t key = getKey(sel);

    // Use the cache as-is if it is less than 3/4 full
    // 通过cache获取已经缓存的数量occupied，并且+1，得到新的缓存数量。
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
       // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        // Cache is too full. Expand it.
        cache->expand();//如果大于3/4，就需要expand()即缓存扩容。
    }

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot because the 
    // minimum size is 4 and we resized at 3/4 full.
    // 根据sel获取bucket，此bucket的sel一般为0（说明这个位置还没缓存方法），
    // 也可能与实参sel相等（hash冲突，可能性很低）
    bucket_t *bucket = cache->find(sel, receiver);
    // 当且仅当bucket的sel为0时，执行_occupied++
    if (bucket->sel() == 0) cache->incrementOccupied();
    // 更新bucket的sel和imp
    bucket->set<Atomic>(sel, imp);
}

// INIT_CACHE_SIZE 即为4
enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};


cache_t *getCache(Class cls) 
{
    assert(cls);
    return &cls->cache;
}

mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}

cache_getImp的实现是不开源的，同时也是用汇编实现

expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    // 获取当前总容量，即_mask+1
    uint32_t oldCapacity = capacity();
    // 新的容量 = 旧容量 * 2
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }
    
    reallocate(oldCapacity, newCapacity);
}

注意：

  1. 在不超过uint32_t大小（4字节）时，每次扩容为原来的2倍
  2. 如果超过了uint32_t，则重新申请跟原来一样大小的buckets

find

find具体做的事情就是根据方法的SEL，返回一个复合要求的bucket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bucket_t * cache_t::find(SEL s, id receiver)
{
    assert(s != 0);

    bucket_t *b = buckets(); // 获取当前buckets，即_buckets
    mask_t m = mask(); // 获取当前mask，即_mask

    mask_t begin = cache_hash(s, m);
    mask_t i = begin;
    do {
    	// sel为0：说明 i 这个位置尚未缓存方法；
    	// sel等于s：命中缓存，说明 i 这个位置已缓存方法，可能是hash冲突
        if (b[i].sel() == 0  ||  b[i].sel() == s) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin); 
    
    // hack
    // 找不到多余的哈希桶（出错的处理，打印问题）
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)s, cls);
}

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

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

find找bucket的方式用到了hash的思想：以_buckets作为哈希桶，以cache_hash作为哈希函数，进行哈希运算后得出索引值index（xx & mask，所以index最大值就是_mask的值）.由于所以值是通过哈希运算得出的，其结果自然是无序的。

_mask的作用

  1. 反映了cache_t中哈希桶的数量（哈希桶的数量=_mask+1）,保证了查找哈希桶时不会出现越界的情况。

哈希桶的数量一定是>=4且能被4整除的，_mask则等于哈希桶的数量-1，也就是说_mask的二进制位上全都是1，而索引是由xx & _mask 运算得出，因此索引值是小于哈希桶的数量的(index<=_mask,故index<capacity),也就不会出现越界的问题

扩容临界点3/4的讨论

一般设定临界点就不得不权衡 空间利用率 和 时间利用率 。在 3/4 这个临界点的时候，空间利用率比较高，同时又避免了相当多的哈希冲突，时间利用率也比较高。

cache_t的取出

cache_t的取出操作为cache_getImp(cls,sel)，该代码是使用汇编语言实现。cache_getImp方法将参数cls放到r10寄存器，然后调用了CacheLookup方法

1
2
3
4
5
STATIC_ENTRY _cache_getImp

// do lookup
movq	%a1, %r10		// move class to r10 for CacheLookup
CacheLookup NORMAL, GETIMP	// returns IMP on success

将sel放进r11寄存器，然后将 sel和cls->cache.mask相与的结果放进r11寄存器，找到key与现有的sel比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
.macro	CacheLookup
	movq	%a2, %r11		// r11 = _cmd
	andl	24(%r10), %r11d		// r11 = _cmd & class->cache.mask
	shlq	$$4, %r11		// r11 = offset = (_cmd & mask)<<4
	addq	16(%r10), %r11		// r11 = class->cache.buckets + offset

	cmpq	cached_sel(%r11), %a2	// if (bucket->sel != _cmd)
	jne 	1f			//     scan more
	// CacheHit must always be preceded by a not-taken `jne` instruction
	CacheHit $0, $1			// call or return imp

1:
	// loop
	cmpq	$$1, cached_sel(%r11)
	jbe	3f			// if (bucket->sel <= 1) wrap or miss

	addq	$$16, %r11		// bucket++
2:	
	cmpq	cached_sel(%r11), %a2	// if (bucket->sel != _cmd)
	jne 	1b			//     scan more
	// CacheHit must always be preceded by a not-taken `jne` instruction
	CacheHit $0, $1			// call or return imp

3:
	// wrap or miss
	jb	LCacheMiss_f		// if (bucket->sel < 1) cache miss
	// wrap
	movq	cached_imp(%r11), %r11	// bucket->imp is really first bucket
	jmp 	2f

	// Clone scanning loop to miss instead of hang when cache is corrupt.
	// The slow path may detect any corruption and halt later.

1:
	// loop
	cmpq	$$1, cached_sel(%r11)
	jbe	3f			// if (bucket->sel <= 1) wrap or miss

	addq	$$16, %r11		// bucket++
2:	
	cmpq	cached_sel(%r11), %a2	// if (bucket->sel != _cmd)
	jne 	1b			//     scan more
	// CacheHit must always be preceded by a not-taken `jne` instruction
	CacheHit $0, $1			// call or return imp

3:
	// double wrap or miss
	jmp	LCacheMiss_f

.endmacro

总结

cache_t是一个开放地址法的hash表

参考

1.OC源码分析之方法的缓存原理
2.从源代码看 ObjC 中消息的发送
3.iOS的方法缓存（cache_t）是如何实现