UE4GC中一種標記流程使用FRealtimeGC的PerformReachabilityAnalysis方法進行uobject可達性分析。FRealTimeGC繼承自FGarbageCollectionTracer，可以多線程、實時的分析對象引用關系。
<bdo id='8ugnh'></bdo><ul id='8ugnh'></ul>
關鍵代碼如下：
// Make sure GC referencer object is checked for references to other objects even if it resides in permanent object pool
if (FPlatformProperties::RequiresCookedData() && FGCObject::GGCObjectReferencer && GUObjectArray.IsDisregardForGC(FGCObject::GGCObjectReferencer))
{
ObjectsToSerialize.Add(FGCObject::GGCObjectReferencer);
}
{
const double StartTime = FPlatformTime::Seconds();
MarkObjectsAsUnreachable(ObjectsToSerialize, KeepFlags, bForceSingleThreaded);
UE_LOG(LogGarbage, Verbose, TEXT("%f ms for Mark Phase (%d Objects To Serialize"), (FPlatformTime::Seconds() - StartTime) * 1000, ObjectsToSerialize.Num());
}
{
const double StartTime = FPlatformTime::Seconds();
PerformReachabilityAnalysisOnObjects(ArrayStruct, bForceSingleThreaded);
UE_LOG(LogGarbage, Verbose, TEXT("%f ms for Reachability Analysis"), (FPlatformTime::Seconds() - StartTime) * 1000);
}
這里用到了一個FGCArrayStruct類型數據結構ArrayStruct，用于存儲用于序列化uobject的array和weak reference列表。
第一步，我們可以向ObjectsToSerialize添加FGCObject::GGCObjectReferencer
后者是一個靜態的UGCObjectReferencer，添加后可用于在非UObject對象上調用AddReferencedObjects方法。
第二步，調用MarkObjectsAsUnreachable方法，把所有不帶KeepFlags和EInternalObjectFlags::GarbageCollectionKeepFlags標記的對象標記為不可達
首先，這里涉及到GUObjectArray這個變量，這是一個全局的Uobject allocator，其中的ObjObjects數組保存了所有的UObject（通過FUObjectItem進行封裝），UObjectBase::InternalIndex屬性就是對象對應的FUObjectItem在數組中的下標，因此可以方便的根據下標找到UObject或者通過UObject找到對應下標。
GUObjectArray中前部存儲了一些不納入GC的object，因此scan的object列表中會去掉前面這些object，只考慮后面的，得到MaxNumberOfObjects。具體哪些對象不被GC考慮，可以查看FUObjectArray的實現。
接下來就需要對這些uobject進行不可達標記，這里使用了多線程版本的For循環。多線程執行的原理并不復雜，首先可以獲取當前可用的工作線程，然后把待標記的object平均分配給這些線程進行遍歷，多線程底層使用了UE的GraphTask框架。在對一個uobject進行標記時，正常情況下都讀對應的FUObjectItem中屬性，特殊情況才讀uobject，因為FUObjectItem是一個結構體，而且在GUObjectArray中緊密排列，所以在順序遍歷下是緩存友好的。
值得一提的是，UE使用了簇（Cluster）來提高效率，具體如何提高會在下面介紹。如果一個object屬于RootSet，則直接加入到ObjectsToSerializeList中，如果是ClusterRoot或在Cluster中，也加入到KeepClusterRefsList列表中。如果object的ClusterRootIndex<=0（不在cluster中或者為ClusterRoot），則先根據是否有KeepFlags，判斷是否要標記為不可達，如果不要標記，則把object加到ObjectsToSerializeList中，且如果為ClusterRoot就加入到KeepClusterRefsList中，如果要標記，則加入到ClustersToDissolveList中，且對ObjectItem設置Unreachable標記。會對Cluster做一些額外的處理，細節可看代碼。
第三步，調用PerformReachabilityAnalysisOnObjects來判斷uobject可達性
這里會用到FGCReferenceProcessor，TFastReferenceCollector，FGCCollector這幾個類，都同時支持單線程和多線程。
先介紹一下ReferenceToken概念
在UObject體系中，每個類有一個UClass實例用于描述該類的反射信息，使用UProperty可描述每個類的成員變量，但在GC中如果直接遍歷UProperty來Scan
對象引用關系，效率會比較低（因為存在許多非Object引用型Property），所以UE創建了ReferenceToken，它是一組toke流，描述類中對象的引用情況。下Scan中列舉了引用的類型：
/**
* Enum of different supported reference type tokens.
*/
enum EGCReferenceType
{
GCRT_None = 0,
GCRT_Object,
GCRT_PersistentObject,
GCRT_ArrayObject,
GCRT_ArrayStruct,
GCRT_FixedArray,
GCRT_AddStructReferencedObjects,
GCRT_AddReferencedObjects,
GCRT_AddTMapReferencedObjects,
GCRT_AddTSetReferencedObjects,
GCRT_EndOfPointer,
GCRT_EndOfStream,
};
FGCReferenceTokenStream
這個類用于創建tokenstream和從tokenstream中解析出object引用，可以算是GC的一個核心理念了。ReferenceToken在其中保存為TArray<uint32>的形式，為什么是這種形式呢，下面就分析一下ReferenceToken的工作原理：
FGCReferenceInfo這個類描述了一個引用所需的信息，有一個union成員變量：
/** Mapping to exactly one uint32 */
union
{
/** Mapping to exactly one uint32 */
struct
{
/** Return depth, e.g. 1 for last entry in an array, 2 for last entry in an array of structs of arrays, ... */
uint32 ReturnCount : 8;
/** Type of reference */
uint32 Type : 4;
/** Offset into struct/ object */
uint32 Offset : 20;
};
/** uint32 value of reference info, used for easy conversion to/ from uint32 for token array */
uint32 Value;
};
Type：引用的類型，就是EGCRefenceType
Offset：這個引用對應的屬性在類中的Address偏移
ReturnCount：返回的嵌套深度
UE巧妙的把這3個信息編碼成了一個uint32，因此FGCReferenceTokenStream可以通過TArray<uint32>形式存儲tokens。
當我們處理TokenStream時，可以先從中解析出一個個referencetoken，然后通過Offset直接獲取屬性，不僅處理起來更簡單，更能有效利用緩存，加快速度。
TokenStream還有一種特殊的用法，就是用兩個連續的token來存儲一個指針（64位），比如運行時可以通過執行AddReferencedObjects來動態添加引用的對象，而這個函數的指針就儲存在TokenStream中。
UClass::AssembleReferenceTokenStream(bool bForce)方法
可以實時創建tokenstream，只需執行一次，就能把結果保存下來，并在ClassFlags中通過CLASS_TokenStreamAssembled進行體現，防止重復計算。如果之前已經創建過TokenStream，就替換調舊的。
具體流程為：
-
遍歷自身的UProperty（不包括父類的），依次調用UProperty的EmitReferenceInfo方法。這是一個虛函數，不同的UProperty會實現它，主要會把自己在Class中的內存偏移，ReferenceType信息發送給UClass，UClass再通過EmitObjectReference把這個引用信息編碼成token，加入到ReferenceTokenStream中。不同的UProperty處理方式有很大區別，普通的UObjectProperty比較好處理，UArrayProperty和UMapProperty就比較復雜，因為它們內部的數據類型也需要生成TokenStream，如果碰到struct，還會涉及到遞歸。
-
如果這個類有父類，則遞歸調用父類的AssembleReferenceTokenStream方法，生成父類的ReferenceTokenStream，并把父類的stream添加到自己的stream之前。這個步驟會一直到UObjectBase這個類為止，UObjectBase的處理方式比較特殊，只會把ClassPrivate和OuterPrivate添加到stream中。
-
如果自身的AddReferencedObjects()函數不是指向Uobject::AddReferencedObjects，則向TokenStream中加入或更新這個函數指針對應的token，在執行可達性分析時即可調用到這個函數了。
-
TokenStream添加完畢，把"EndOfStream"token添加到TokenStream，并對tokens array進行shrink，去掉空閑的array slack，因為toneks數組長度在接下來應該是固定的。
-
ClassFlags中把CLASS_TokenStreamAssembled設為true。
TFastReferenceCollector
CollectReferences方法用于可達性分析，如果時單線程，就直接調用ProcessObjectArray方法，遍歷uobject的token stream來尋找引用關系。如果是多線程，就會把uobject列表分割給多個線程處理，每個線程同樣會調用到ProcessObjectArray。
ProcessObjectArray方法會遍歷ObjectsToSerialize中的UObject，找到引用關系，判斷可達性。注意，過程中ObjectsToSerialize會不斷增長，直到全部遍歷完。內部使用了遞歸的方法，但用棧來模擬。
1.如果是單線程且開啟了自動生成tokenstream，則當object對應的UClass還沒有tokenstream時，就實時調用UClass的AssembleReferneceTokenStreams創建tokenstream
2.獲取當前uobject的TokenStream，解析出FGCReferenceInfo，來找到正被引用的UObject。
token的ReferenceInfo會是不同的類型，需要分多種情況處理。像GCRT_Object和GCRT_ArrayObject都比較好處理，只要把其中的uobject對象添加到ObjectsToSerialize中就行了。
GCRT_ArrayStruct就比較麻煩，需要遞歸處理。這里說的"struct"并不單指C++中的struct結構體，一些不屬于UObject體系的class也算，比如UEdGraphPin。處理GCRT_ArrayStruct時，需要先把遞歸的棧遞增，然后逐個處理Array中的"Struct"。
GCRT_AddStructReferencedObjects表示struct或不繼承自FGCObject的class也可以對UOBject添加引用關系，UStructProperty::EmitReferenceInfo中代碼也確實顯示structproperty可以添加引用。但看代碼和注釋，覺得UE4應該以后會把這些特殊的struct和class都繼承FGCObject，使用AddReferencedObjects函數來添加引用。
GCRT_AddReferencedObjects就表示需要調用這個對象的AddReferencedObjects函數來添加引用。讓我們回想一下FGCObject，這個類不繼承UObject，但也能通過AddReferencedObjects函數來對UObject添加引用，同時這個函數又只能由UClass來添加到TokenStream中，那FGCObject是怎么工作的？其實UE中有一個專門的UObject實例來管理FGCObject，就是UGCObjectReferencer，看一下這個類的AddReferencedObjects函數：
void UGCObjectReferencer::AddReferencedObjects(UObject* InThis, FReferenceCollector& Collector)
{
UGCObjectReferencer* This = CastChecked<UGCObjectReferencer>(InThis);
// Note we're not locking ReferencedObjectsCritical here because we guard
// against adding new references during GC in AddObject and RemoveObject.
// Let each registered object handle its AddReferencedObjects call
for (FGCObject* Object : This->ReferencedObjects)
{
check(Object);
Object->AddReferencedObjects(Collector);
}
Super::AddReferencedObjects( This, Collector );
}
引用標記階段搜集到這個類的實例時，它會逐個調用FGCObject上的AddReferencedObjects方法，搜集UObject引用，從而把FGCObject納入到GC體系中。
3. 得到被引用的UObject后，一般會對其添加引用，并加入到ObjectsToSerialize數組中。
如果一個UObject已經被標記為isPendingKill了，那么即使它被引用到，也會忽略。
由于標記可以多線程進行，因此有可能兩個線程同時對一個對象標記為可達，并加入到ObjectsToSerialize數組，繼續進行引用檢查，這顯然是浪費的。因此對一個對象進行標記時，不僅要檢查這個對象當前是否為Unreachable，清理它的Unreachable標記也要有一個原子的“比較再替換”操作，防止兩個線程碰巧同時設置。
如果這個UObject在Cluster中，則把它標記為ReachableInCluster，同時如果需要也把它的ClusterOwner標記為可達，并加入到ObjectsToSerialize中做后續處理。
4. 對ObjectsToSerialize數組的Scan會一輪一輪進行，一輪Scan過程中Scan到的新的UObject會暫時存放在NewObjectsToSerialize數組中，當對ObjectsToSerialize一輪Scan完時，如果NewObjectsToSerialize中元素數量超過MinDesiredObjectsPerSubTask這一閾值，則新開多個線程處理，如果不到閾值，則在當前線程中繼續新的一輪處理。
