前言

上节说到， MarkObjectsAsUnreachable() 与 PerformReachabilityAnalysisOnObjectsInternal() 是执行标记阶段两个步骤分别对应的函数，本节我们就来分析它们。

MarkObjectsAsUnreachable

由于这个函数比较长（200行左右），这里就不放出完整的函数内容而使用分段分析的方法，感兴趣的读者可以自行在 UObject/GarbageCollection.cpp 中查看该函数。

首先查看函数注释与签名，可以看出，该函数的作用为：将将已有的对象列表中的对象，标记为可达/不可达。并且根据 <bool bParallel, bool bWithClusters> 两个模板参数可以实例化出不同的函数以适用于各种情况。

1
2
3
4
5
6
/** 
* Marks all objects that don't have KeepFlags and EInternalObjectFlags::GarbageCollectionKeepFlags as unreachable
* This function is a template to speed up the case where we don't need to assemble the token stream (saves about 6ms on PS4)
*/
template <bool bParallel, bool bWithClusters>
void MarkObjectsAsUnreachable(TArray<UObject*>& ObjectsToSerialize, const EObjectFlags KeepFlags)

首先，该函数会计算出当前 GUObjectArray 中需要被 GC 的对象的数量，并根据线程数将这些对象平均分配给每个线程来处理。GUObjectArray 是一个定义在 UObjectHash.cpp 中的数组，用于存放全局的对象，GUObjectArray 的前部存储了一些不纳入GC的 object，因此扫描的object列表中会去掉前面这些object，只考虑后面的，得到MaxNumberOfObjects。

随后定义了两个 FIFO 的数据结构（类似于队列），分别是 ClustersToDissolveList 与 KeepClusterRefsList，这两个数组具体的作用会在之后进行分析。

此外，函数为每个线程都申请了一个 FGCArrayStruct 结构体，因此 ObjectsToSerializeArrays 是一个二维数组，想必这些结构体就是用来装每个线程要处理的对象的。

1
2
3
4
5
6
7
8
9
10
11
12
const EInternalObjectFlags FastKeepFlags = EInternalObjectFlags::GarbageCollectionKeepFlags;
const int32 MaxNumberOfObjects = GUObjectArray.GetObjectArrayNum() - GUObjectArray.GetFirstGCIndex();
const int32 NumThreads = FMath::Max(1, FTaskGraphInterface::Get().GetNumWorkerThreads());
const int32 NumberOfObjectsPerThread = (MaxNumberOfObjects / NumThreads) + 1;		

TLockFreePointerListFIFO<FUObjectItem, PLATFORM_CACHE_LINE_SIZE> ClustersToDissolveList;
TLockFreePointerListFIFO<FUObjectItem, PLATFORM_CACHE_LINE_SIZE> KeepClusterRefsList;
FGCArrayStruct** ObjectsToSerializeArrays = new FGCArrayStruct*[NumThreads];
for (int32 ThreadIndex = 0; ThreadIndex < NumThreads; ++ThreadIndex)
{
    ObjectsToSerializeArrays[ThreadIndex] = FGCArrayPool::Get().GetArrayStructFromPool();
}

这里先说结论：

  1. ObjectsToSerializeArrays 数组用于存放所有可达的对象
  2. KeepClusterRefsList 数组用于存放簇中可达的对象
  3. ClustersToDissolveList 数组用于存放簇中不可达的对象

其中，KeepClusterRefsList 与 ClustersToDissolveList 只会在当前 GC 启用了簇之后才会进行统计。结合后续的处理过程，可以更好地理解它们的作用。

随后是一个并行的 for 循环，在多线程条件下遍历GUobjectArray中的对象。从注释中可以看到，似乎标记阶段检查的 flag 就是 UObjectArray 结构体的一部分，因此可以降低 cache misses，缓存和缓存命中准备开个新坑再细说（标记一下以防忘掉）。

1
2
3
4
5
6
// Iterate over all objects. Note that we iterate over the UObjectArray and usually check only internal flags which
// are part of the array so we don't suffer from cache misses as much as we would if we were to check ObjectFlags.
ParallelFor(NumThreads, [ObjectsToSerializeArrays, &ClustersToDissolveList, &KeepClusterRefsList, FastKeepFlags, KeepFlags, NumberOfObjectsPerThread, NumThreads, MaxNumberOfObjects](int32 ThreadIndex)
{
    // ...
}, !bParallel);

ParallelFor() 的第二个参数是一个非常巨大的 lambda 函数，由对应的函数签名可以看出，这个匿名函数 PerParticleFunction 就是每个线程需要执行的函数了。

1
static void ParallelFor(const int32 Size, std::function<void(int32)> PerParticleFunction)

从捕获参数列表中我们可以看到，这个匿名函数捕获了上述定义的三个数组。其中，ClustersToDissolveList 与 KeepClusterRefsList 是引用捕获，ObjectsToSerializeArrays 是值捕获。

1
[ObjectsToSerializeArrays, &ClustersToDissolveList, &KeepClusterRefsList, ...]

GetOwnerIndex()

在分析这个函数之前，需要了解一些额外的知识。

在 GCObjectInfo.h 中，有一个名为 FGCObjectInfo 的类，该类的作用是保存 UObject 的一些信息以用于 GC，这样可以避免对于 UObject 的直接访问。

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
/**
 * Structure containing information about a UObject participating in Garbage Collection.
 * It's purpose is to avoid holding onto direct references to UObjects which may have already been Garbage Collected.
 * FGCObjectInfo interface mimics that of UObject.
 **/
class COREUOBJECT_API FGCObjectInfo
{
    // ...

    /** Name of the object */
    FName Name;
    /** Pointer to class info */
    FGCObjectInfo* Class = nullptr;
    /** Pointer to Outer info */
    FGCObjectInfo* Outer = nullptr;
    /** Captured Object flags */
    EObjectFlags Flags = RF_NoFlags;
    /** Captured Internal flags */
    EInternalObjectFlags InternalFlags = EInternalObjectFlags::None;
    /** Object's FGCObjectItem cluster root index */
    int32 ClusterRootIndex = -1;
    /** True if the object was inside of the disregard for GC set */
    bool bDisregardForGC = false;

    // ...

    int32 GetOwnerIndex() const
    {
        return ClusterRootIndex;
    }

    // ...
};

其中有一个成员变量名为 ClusterRootIndex，并且默认值被赋予了 -1。而 GetOwnerIndex() 则会返回 ClusterRootIndex。我们可以做出如下的猜测：

在 GC 的设置中，如果启用了 Cluster，那么会对当前的对象进行划分，将它们整合到不同的簇中，而簇的标识就是 ClusterRootIndex，这个值表示了当前对象所在簇的根节点下标。如果该值为 -1，则表明当前的对象为簇的根节点；相反地，如果该值不为 -1（判断条件可以是 >= 0，因为 ClusterRootIndex 是一个下标，如果不是初始值的话必然 >= 0），则说明当前对象处于一个以其他对象为根节点的簇中。

如此说来，这莫非是一个类似于并查集的数据结构？

在 PerParticleFunction 这个匿名函数中，会用到很多次对于 GetOwnerIndex() 的条件判断。

PerParticleFunction

回到正题，在这个函数中，会针对对象进行不同情况的不同处理：

  1. 对象属于根集

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // Special case handling for objects that are part of the root set.
    if (ObjectItem->IsRootSet())
    {
        // ...

        if (bWithClusters)
        {
            if (ObjectItem->HasAnyFlags(EInternalObjectFlags::ClusterRoot) || ObjectItem->GetOwnerIndex() > 0)
            {
                KeepClusterRefsList.Push(ObjectItem);
            }
        }

        LocalObjectsToSerialize.Add(Object);
    }

    如果对象属于根集，那么一定是可达的，因此无论如何都会被添加进 LocalObjectsToSerialize，我们可以在 for 循环的外部看到这个数组的定义，就是 ObjectsToSerializeArrays 对应当前线程的可达对象数组。

    1
    TArray<UObject*>& LocalObjectsToSerialize = ObjectsToSerializeArrays[ThreadIndex]->ObjectsToSerialize;

    此外，如果启用了簇，即 bWithClusters == true，在当前的对象为一个簇的根（ClusterRoot）或 GetOwnerIndex() > 0 时，将对象添加进 KeepClusterRefsList。从上文的分析中我们可以得知，GetOwnerIndex() > 0 意味着当前对象处于以其他对象为根的簇中。结合这两个条件可以知道，当前对象一定是可达的，因此添加进 KeepClusterRefsList 数组。

  2. 常规对象

    第二个判断条件是：没有启用簇或者当前对象为簇的根节点。由于第一个判断处理了所有根对象的情况，因此这里处理的都是普通对象。

    首先，会假设当前对象不可达，如果当前对象带有一些指定的 flag 或者本身不是 PendingKill 等情况就会标记为可达。如果当前对象被标记为 PendingKill 或 Garbage 且当前对象为 ClusterRoot，则会将该对象添加进 ClustersToDissolveList。

    最后会对 bMarkAsUnreachable 做检查，如果对象可达，则会被添加进 LocalObjectsToSerialize，如果启用了簇且当前对象为某个簇的根则对象会被添加进 KeepClusterRefsList。如果对象不可达则会设置对象的 Unreachable 标志位。

    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
    // Regular objects or cluster root objects
    else if (!bWithClusters || ObjectItem->GetOwnerIndex() <= 0)
    {
        bool bMarkAsUnreachable = true;
        // Internal flags are super fast to check and is used by async loading and must have higher precedence than PendingKill
        if (ObjectItem->HasAnyFlags(FastKeepFlags))
        {
            bMarkAsUnreachable = false;
        }
        // If KeepFlags is non zero this is going to be very slow due to cache misses
        else if (!ObjectItem->IsPendingKill() && KeepFlags != RF_NoFlags && Object->HasAnyFlags(KeepFlags))
        {
            bMarkAsUnreachable = false;
        }
        PRAGMA_DISABLE_DEPRECATION_WARNINGS
        else if (ObjectItem->HasAnyFlags(EInternalObjectFlags::PendingKill | EInternalObjectFlags::Garbage) && bWithClusters && ObjectItem->HasAnyFlags(EInternalObjectFlags::ClusterRoot))
        PRAGMA_ENABLE_DEPRECATION_WARNINGS
        {
            ClustersToDissolveList.Push(ObjectItem);
        }

        // Mark objects as unreachable unless they have any of the passed in KeepFlags set and it's not marked for elimination..
        if (!bMarkAsUnreachable)
        {
            // IsValidLowLevel is extremely slow in this loop so only do it in debug
            checkSlow(Object->IsValidLowLevel());
            LocalObjectsToSerialize.Add(Object);

            if (bWithClusters)
            {
                if (ObjectItem->HasAnyFlags(EInternalObjectFlags::ClusterRoot))
                {
                    KeepClusterRefsList.Push(ObjectItem);
                }
            }
        }
        else
        {
            ObjectItem->SetFlags(EInternalObjectFlags::Unreachable);
        }
    }

  3. 簇中的常规对象

    最后，针对簇中的常规对象，如果有特定的 flag，则会被添加进两个数组中。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // Cluster objects 
    else if (bWithClusters && ObjectItem->GetOwnerIndex() > 0)
    {
        // treat cluster objects with FastKeepFlags the same way as if they are in the root set
        if (ObjectItem->HasAnyFlags(FastKeepFlags))
        {
            KeepClusterRefsList.Push(ObjectItem);
            LocalObjectsToSerialize.Add(Object);
        }
    }

到此为止，多线程的 for 循环基本就结束了，也完成了对于 GUObjectArray 中所有参与 GC 的对象 可达/不可达 的标记。接下来就是对于三个列表的不同处理。

首先是 ObjectsToSerializeArrays，该二维数组存放的是每个线程收集到的可达的对象。这里会统计全部可达对象的数量，并且将该数组内的对象移交给 ObjectsToSerialize 数组，最后再向 FGCArrayPool 归还列表空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Collect all objects to serialize from all threads and put them into a single array
{
    int32 NumObjectsToSerialize = 0;
    for (int32 ThreadIndex = 0; ThreadIndex < NumThreads; ++ThreadIndex)
    {
        NumObjectsToSerialize += ObjectsToSerializeArrays[ThreadIndex]->ObjectsToSerialize.Num();
    }
    ObjectsToSerialize.Reserve(NumObjectsToSerialize);
    for (int32 ThreadIndex = 0; ThreadIndex < NumThreads; ++ThreadIndex)
    {
        ObjectsToSerialize.Append(ObjectsToSerializeArrays[ThreadIndex]->ObjectsToSerialize);
        FGCArrayPool::Get().ReturnToPool(ObjectsToSerializeArrays[ThreadIndex]);
    }
    delete[] ObjectsToSerializeArrays;
}

ObjectsToSerialize 不知道大家还有没有印象，这就是 MarkObjectsAsUnreachable() 的参数之一，可以参考上一节的内容：UE 补完计划（二） GC-1，我们在 PerformReachabilityAnalysis() 中申请了一个名为 ObjectsToSerialize 的数组并且将它传递给了 MarkObjectsAsUnreachable 函数。

1
2
template <bool bParallel, bool bWithClusters>
void MarkObjectsAsUnreachable(TArray<UObject*>& ObjectsToSerialize, const EObjectFlags KeepFlags)

由于 ObjectsToSerialize 是引用传递，因此可以将所有可达对象传递给上层的函数，即 PerformReachabilityAnalysis()。

然后是对 ClustersToDissolveList 的处理，DissolveClusterAndMarkObjectsAsUnreachable 函数可以解散当前对象所属的集群(簇,也就是cluster)，并且执行真正的“标记对象为不可达”。准确的说是调用SetFlags(EInternalObjectFlags::Unreachable);来标记对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (bWithClusters)
{
    TArray<FUObjectItem*> ClustersToDissolve;
    ClustersToDissolveList.PopAll(ClustersToDissolve);
    for (FUObjectItem* ObjectItem : ClustersToDissolve)
    {
        // Check if the object is still a cluster root - it's possible one of the previous
        // DissolveClusterAndMarkObjectsAsUnreachable calls already dissolved its cluster
        if (ObjectItem->HasAnyFlags(EInternalObjectFlags::ClusterRoot))
        {
            GUObjectClusters.DissolveClusterAndMarkObjectsAsUnreachable(ObjectItem);
            GUObjectClusters.SetClustersNeedDissolving();
        }
    }
}

最后是对 KeepClusterRefsList 的处理。前面说过，这个列表存放的是可达的簇中的对象，因此这里也会遍历数组并且将相关的对象全都标记为可达。

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
if (bWithClusters)
{
    TArray<FUObjectItem*> KeepClusterRefs;
    KeepClusterRefsList.PopAll(KeepClusterRefs);
    for (FUObjectItem* ObjectItem : KeepClusterRefs)
    {
        if (ObjectItem->GetOwnerIndex() > 0)
        {
            checkSlow(!ObjectItem->HasAnyFlags(EInternalObjectFlags::ClusterRoot));
            bool bNeedsDoing = !ObjectItem->HasAnyFlags(EInternalObjectFlags::ReachableInCluster);
            if (bNeedsDoing)
            {
                ObjectItem->SetFlags(EInternalObjectFlags::ReachableInCluster);
                // Make sure cluster root object is reachable too
                const int32 OwnerIndex = ObjectItem->GetOwnerIndex();
                FUObjectItem* RootObjectItem = GUObjectArray.IndexToObjectUnsafeForGC(OwnerIndex);
                checkSlow(RootObjectItem->HasAnyFlags(EInternalObjectFlags::ClusterRoot));
                // if it is reachable via keep flags we will do this below (or maybe already have)
                if (RootObjectItem->IsUnreachable()) 
                {
                    RootObjectItem->ClearFlags(EInternalObjectFlags::Unreachable);
                    // Make sure all referenced clusters are marked as reachable too
                    FGCReferenceProcessor<EFastReferenceCollectorOptions::WithClusters>::MarkReferencedClustersAsReachable(RootObjectItem->GetClusterIndex(), ObjectsToSerialize);
                }
            }
        }
        else
        {
            checkSlow(ObjectItem->HasAnyFlags(EInternalObjectFlags::ClusterRoot));
            // this thing is definitely not marked unreachable, so don't test it here
            // Make sure all referenced clusters are marked as reachable too
            FGCReferenceProcessor<EFastReferenceCollectorOptions::WithClusters>::MarkReferencedClustersAsReachable(ObjectItem->GetClusterIndex(), ObjectsToSerialize);
        }
    }
}

有一点需要注意的是，MarkObjectsAsUnreachable() 向上级函数，也就是 PerformReachabilityAnalysis() 传递信息的方式只有 ObjectsToSerialize 数组，而后续对于 ClustersToDissolveList 与 KeepClusterRefsList 数组中对象的标记也会反映在 ObjectsToSerialize 数组中。

到这里为止，MarkObjectsAsUnreachable() 函数的内容也就基本分析完毕了。

小结

本节主要分析了标记的第一阶段 MarkObjectsAsUnreachable() 的内容，这个函数的主要作用就是遍历 GUObjectArray 中的所有参与 GC 的对象，并将收集到的所有可达对象传递给 ObjectsToSerialize 数组，该数组也是一个引用传递的函数参数，因此可以将信息传递到更上层的 PerformReachabilityAnalysis() 函数中。

此外，该函数还会对簇中的对象做进一步的处理与标记，但最终的标记结果都会体现在 ObjectsToSerialize 中。