FBRetainCycleDetector解析

一. 原理分析

FBRetainCycleDetector的原理:是基于DFS算法，把整个对象之间的强引用关系当做图进行处理，查找其中的环，就找到了循环引用。

二. 检测NSObject对象持有的强指针

1. 如何确定对象类型

@encode(type-name)返回类型的字符串编码，在确定循环引用关系的过程中,只有三种编码字符串存在强引用关系:

编码.jpg

判断代码:

- (FBType)_convertEncodingToType:(const char *)typeEncoding {
    if (typeEncoding[0] == '{') return FBStructType;

    if (typeEncoding[0] == '@') {
        if (strncmp(typeEncoding, "@?", 2) == 0) return FBBlockType;
        return FBObjectType;
    }

    return FBUnknownType;
}

2. 获取Ivar的引用属性

class_getIvarLayout可以返回一个字符串用来描述成员变量的布局信息。假设存在类:

@interface XXObject: NSObject

@property(nonatomic, strong) id first;
@property(nonatomic, weak) id second;
@property(nonatomic, strong) id third;
@property(nonatomic, strong) id forth;
@property(nonatomic, weak) id fifth;
@property(nonatomic, strong) id sixth;

@end

这个类返回的布局字符串为\x01\x12\x11,以此为例，字符串表示共存在0+1+1+2+1+1 总共6个成员变量。其中一个\xAB表示存在A个非强引用属性，和B个强引用属性，因此该布局字符串也可表示为:

- 0个非强引用属性，1个强引用属性
- 1个非强引用属性，2个强引用属性
- 1个非强引用属性，1个强引用属性

3. 获取变量布局偏移

ivar_getOffset可以获取成员变量在类结构中的偏移地址，由于ivar是指针类型，通过offset/sizeof(void *)可以获取偏移数量。通过range的方式可以用来匹配某个成员变量是否属于强引用属性:

static NSIndexSet *FBGetLayoutAsIndexesForDescription(NSUInteger minimumIndex, const uint8_t *layoutDescription) {
    NSMutableIndexSet *interestingIndexes = [NSMutableIndexSet new];
    NSUInteger currentIndex = minimumIndex;

    while (*layoutDescription != '\x00') {
        int upperNibble = (*layoutDescription & 0xf0) >> 4;
        int lowerNibble = *layoutDescription & 0xf;

        currentIndex += upperNibble;
        [interestingIndexes addIndexesInRange:NSMakeRange(currentIndex, lowerNibble)];
        currentIndex += lowerNibble;

        ++layoutDescription;
    }

    return interestingIndexes;
}

因为高位表示非强引用的数量,所以我们需要加上upperNibble，然后NSMakeRange(currentIndex, lowerNibble)就表示强引用的范围，然后加上lowerNibble的长度，移动layoutDescription,直到所有NSRange都加入到interestingIndexes这一集合中，就可以返回了。

二. 关联属性强引用的获取

FBRetainCycleDetector在对关联对象进行追踪时，通过fishhook第三方库hook了关联对象的两个C函数，objc_setAssociatedObject 和 objc_removeAssociatedObjects,然后重新实现了关联对象模块，将通过OBJC_ASSOCIATION_RETAIN和OBJC_ASSOCIATION_RETAIN_NONATOMIC策略，保存起来，只追踪强引用的属性。

三. Block引用属性获取

首先需要声明一个类似block的结构体类型，用于强制类型转换:

struct BlockLiteral {
    void *isa;
    int flags;
    int reserved;
    void (*invoke)(void *, ...);
    struct BlockDescriptor *descriptor;
    // imported variables
};

被block引用的对象总是基于block地址偏移整个结构体的size，并且被持有的对象按照强引用在前，弱引用在后的顺序排列

这里block变量其实只是一个指向结构体的指针，所以大小为8,结构体的大小为32

struct BlockDescriptor {
    unsigned long int reserved;                // NULL
    unsigned long int size;
    // optional helper functions
    void (*copy_helper)(void *dst, void *src); // IFF (1<<25)
    void (*dispose_helper)(void *src);         // IFF (1<<25)
    const char *signature;                     // IFF (1<<30)
};

block中存在两个helper函数协助完成copy到堆上和释放对象引用的工作，后者会对所有的strong类型的对象进行一次release调用，因此可以通过手动调用dispose_helper的方式来识别block强引用的对象:

最后就是用于从dispose_helper的接收类FBBlockStrongRelationDetector，它的实例在接收release消息时，并不会真正的释放，只会将标记_strong为YES.

- (oneway void)release {
    _strong = YES;
}

- (oneway void)trueRelease {
    [super release];
}

真正调用trueRelease的时候才会向对象发送release消息。

如果block持有另一个block对象，FBBlockStrongRelationDetector也会将自身伪装成一个假的block防止在接收到关于block释放的消息时发生crash.

struct _block_byref_block;
@interface FBBlockStrongRelationDetector : NSObject {
    // __block fakery
    void *forwarding;
    int flags;   //refcount;
    int size;
    void (*byref_keep)(struct _block_byref_block *dst, struct _block_byref_block *src);
    void (*byref_dispose)(struct _block_byref_block *);
    void *captured[16];
}

1. 获取block强引用对象

static NSIndexSet *_GetBlockStrongLayout(void *block) {
    struct BlockLiteral *blockLiteral = block;

    /// 如果拥有CPP析构器，说明持有的对象可能没有按照指针大小对齐，很难检测到所有对象
    /// 如果没有dispose函数，说明无法retain对象，因此也无法测试强引用了哪些对象
    if ((blockLiteral->flags & BLOCK_HAS_CTOR)
    || !(blockLiteral->flags & BLOCK_HAS_COPY_DISPOSE)) {
        return nil;
    }

    /// 通过获取dispose_helper，并且将一个mock的对象数组传入进去，检测哪些mock对象会被release
    void (*dispose_helper)(void *src) = blockLiteral->descriptor->dispose_helper;
    const size_t ptrSize = sizeof(void *);
    const size_t elements = (blockLiteral->descriptor->size + ptrSize - 1) / ptrSize;

    void *obj[elements];
    void *detectors[elements];

    /// 遍历所有mock对象，如果标记位为YES，说明被release，此时对应位置的变量被block强引用
    for (size_t i = 0; i < elements; ++i) {
        FBBlockStrongRelationDetector *detector = [FBBlockStrongRelationDetector new];
        obj[i] = detectors[i] = detector;
    }

    @autoreleasepool {
        dispose_helper(obj);
    }

    NSMutableIndexSet *layout = [NSMutableIndexSet indexSet];

    for (size_t i = 0; i < elements; ++i) {
        FBBlockStrongRelationDetector *detector = (FBBlockStrongRelationDetector *)(detectors[i]);
        if (detector.isStrong) {
            [layout addIndex:i];
        }
        [detector trueRelease];
    }

    return layout;
}

四. DFS深度遍历检测是否存在循环引用

采用stack的方式，对某个对象获取所有被其强引用的对象，然后依次以递归思想将这些对象入栈，如果某次入栈的对象已经存在stack中，说明该对象在stack中的位置直到当前为止，存在引用环.

- (NSSet<NSArray<FBObjectiveCGraphElement *> *> *)_findRetainCyclesInObject:(FBObjectiveCGraphElement *)graphElement
                                 stackDepth:(NSUInteger)stackDepth {
    ...
    [stack addObject:wrappedObject];

    while ([stack count] > 0) {
        @autoreleasepool {
            FBNodeEnumerator *top = [stack lastObject];
            [objectsOnPath addObject:top];

            FBNodeEnumerator *firstAdjacent = [top nextObject];
            if (firstAdjacent) {
                BOOL shouldPushToStack = NO;

                if ([objectsOnPath containsObject:firstAdjacent]) {
                    NSUInteger index = [stack indexOfObject:firstAdjacent];
                    NSInteger length = [stack count] - index;

                    if (index == NSNotFound) {
                    shouldPushToStack = YES;
                    } else {
                        NSRange cycleRange = NSMakeRange(index, length);
                        NSMutableArray<FBNodeEnumerator *> *cycle = [[stack subarrayWithRange:cycleRange] mutableCopy];
                        [cycle replaceObjectAtIndex:0 withObject:firstAdjacent];

                        [retainCycles addObject:[self _shiftToUnifiedCycle:[self _unwrapCycle:cycle]]];
                    }
                } else {
                    shouldPushToStack = YES;
                }

                if (shouldPushToStack) {
                    if ([stack count] < stackDepth) {
                        [stack addObject:firstAdjacent];
                    }
                }
            } else {
                [stack removeLastObject];
                [objectsOnPath removeObject:top];
            }
        }
    }
    return retainCycles;
}

五. 总结

FBRetainCycleDetector进行循环引用检测的思路如下:

对于正常类的类的成员变量，通过runtime的class_getIvarLayout获取描述该类成员变量的布局信息，然后通过ivar_getOffset遍历获取成员变量在类结构中的偏移地址,然后获取强引用变量的集合。
对于关联对象的成员变量，通过fishhook第三方库hook了关联对象的两个C函数，objc_setAssociatedObject 和 objc_removeAssociatedObjects,然后重新实现了关联对象模块，将通过OBJC_ASSOCIATION_RETAIN和OBJC_ASSOCIATION_RETAIN_NONATOMIC策略进行关联的对象保存起来，只追踪强引用的属性。
对于block持有的强引用变量的获取，依据block引用的对象总是基于block地址偏移整个结构体的size,并且被持有的对象按照强引用在前，弱引用在后的顺序排列，因为block强引用的对象都会进行copy到堆上和release对象引用的操作，因此可以通过接收类FBBlockStrongRelationDetector构造detector对象，然后用block的dispose_helper方法调用，判断如果detector对象调用release方法，就说明当前对象是强引用对象，然后获取block持有的所有强引用变量的集合
对所有检测到的强引用变量，利用DFS(深度优先搜索)，采用stack栈的形式，将遍历到的对象依次入栈，如果某次入栈的对象已经存在stack中，说明该对象在stack中的位置直到当前为止，存在引用环.

这里只是做了过程的总结，详细分析可以参考以下文章:

如何在 iOS 中解决循环引用的问题
 检测 NSObject 对象持有的强指针
 如何实现 iOS 中的 Associated Object
iOS 中的 block 是如何持有对象的