[原创]UE— Garbage Collection

这是一篇长文,涵盖了UE4垃圾回收的大部分知识点。如若有错误之处,望留言纠正(亦可邮件探讨:lingzelove2008@163.com),感激不尽

垃圾回收起源

何为垃圾回收 (Garbage Collection) ?它是一种自动管理资产 (Assets) 生命周期的运行时机制

UE 采用的编程语言是 C++,这也是很多 Unity 程序员转行到 UE 的第一个重量级拦路虎。有好心的 UE 前辈会告诉你 : “UE 的 C++ 是魔改版,用起来跟 C# 差不多”。这句话有一定的道理,让前辈们有这种错觉最重要的一点就是,UE 引擎实现了垃圾回收(C++标准未实现 )

C++的内存管理,new 必须对应 delete ; 但是游戏项目非常庞大,指针满天飞,你压根不知道应该在哪儿 delete 。隔壁 Unity 只需要 new 系统会自动 delete,这让 UE 引擎专家甚是羡慕,就强撸了一个垃圾回收系统来自动 delete,让 UE 的开发难度骤降

垃圾回收的功能

如果让你来实现这个垃圾回收系统,你觉得垃圾回收系统应该具备哪些功能呢?

  • 实现自定义的 NewObject 方法( 无需调用对应的DeleteObject )
  • 自动回收没有被引用的垃圾对象
  • 不影响其他系统的正常功能

垃圾回收伪实现

垃圾回收的算法有很多, 标记-清除算法 、 复制算法 、标记-整理算法 、分代收集算法等。我们就用最”简单”的标记清除算法来实现。标记-清除算法,看名字就知道有两个阶段,标记和清除:

  • 标记:遍历所有对象,根据某种规则,标记其是否需要清除
  • 清除:遍历所有对象,清除标记了的对象,回收内存

因此可知,要实现标记清除垃圾回收,在标记阶段我们需要做到以下两点:

  • 能拿到所有对象
  • 确定对象清除的规则

在自定义的 NewObject 方法内,把生成的对象指针放入全局数组 GUObjectArray ,这样我就能拿到所有对象了

想象一个画面:空场景内站着一个英雄。这个情况下,垃圾回收系统是不是应该围绕着英雄来判断?英雄用到的对象就保留,没用到的对象就清除。此时这个英雄就是 “根对象”。因此,标记清除的规则就是,根对象用到的对象保留,其他对象清除。那根对象怎么确定?就得我们”手动”标记(AddToRoot)

以下就是垃圾回收的伪实现:

  • 启动垃圾回收,加锁( 保持所有对象的引用关系不变 )
  • 设置所有对象为”不可达”标记(根对象、特殊对象 除外)
  • 遍历根对象列表,根对象引用到的对象去除”不可达”标记
  • 收集所有仍然标记为”不可达”的对象,全部删除

垃圾回收 UE4 实现

UE4的垃圾回收过程,正是照着上文的伪实现一步步执行的,不过细节更丰富,效率也更高

GC 启动

手动调用:UWorld::ForceGarbageCollection( bool bFullPurge),它会在World.tick 的下一帧强行进行垃圾回收

自动调用:系统会根据默认的设置(可重新配置)一定的间隔时间或者条件下,自动调用垃圾回收

GC 锁

void CollectGarbage(EObjectFlags KeepFlags, bool bPerformFullPurge)
{
    AcquireGCLock(); //获取GC锁
    CollectGarbageInternal(KeepFlags, bPerformFullPurge); //垃圾回收
    ReleaseGCLock(); //释放GC锁
}

GC锁的主要用处就是为了暂停其他线程以免UObject对象的引用关系在GC过程中发生变化。主要步骤:

  • 发送信号,表示我想获取GC锁,GCWantsToRunCounter 自增(原子操作)
  • GC 线程 Sleep,查看 AsyncCounter 是否等于 0 判断其他线程是否有阻塞GC的操作还在执行,不等于 0 就继续等待
  • AsyncCounter = 0,通过另一个变量 GCCounter 递增(原子操作),来标识正在执行GC,其他所有线程将被阻塞
  • 执行内存屏障
  • 将 GCWantsToRunCounter 设为 0,开始真正的 GC 操作
  • GC 操作完毕, GCCounter 自减释放 GC 锁

内存屏障的主要意思就是,在这个屏障之前的所有读和写的操作,一定会在这个屏障后面的读和写的操作之前执行。为了防范多线程读写操作时序问题导致的逻辑 bug,详细内容自行 Google

获取所有对象

上文伪实现,NewObject的时候把生成的对象的指针放入一个全局数组,实际上UE4确实也是这么做的。UObject对象继承自UObjectBase,它的构造方法如下(代码有删减改动):

//UObjectBase.cpp

//NewUObject方法调用后,UObject对象初始化
UObjectBase::UObjectBase(UClass* InClass, EObjectFlags InFlags, EInternalObjectFlags InInternalFlags, UObject *InOuter, FName InName)
{
   AddObject(InName, InInternalFlags); 
}

void UObjectBase::AddObject(FName InName, EInternalObjectFlags InSetInternalFlags)
{ 
   //将对象加入GUObjectArray,并且为Object分配InternalIndex(对象的索引位置)
   GUObjectArray.AllocateUObjectIndex(Object);
}

GUObjectArray 虽然命名是 Array 结尾,实际上它是个容器体。虽然它里面一堆花里胡哨的东西,实际上只要理解它是为了多线程的时候分块扫描其存储的内容而设计就行。UObject对象不接存入容器的,而是被组装成了 FUObjectItem 结构:

//UObjectArray.h

//对象存储的结构体,GC操作的就是这个对象
struct FUObjectItem
{
   class UObjectBase* Object; //对象
   int32 Flags;               //EInternalObjectFlags标识
   int32 ClusterRootIndex;    //当前所属簇索引
   int32 SerialNumber;        //对象唯一序列码(WeakObjectPtr实现用到它)
}

这个结构体对于理解GC很重要。成员 Object 是 NewObject 生成的对象的指针,EInternalObjectFlags 是啥呢?就是用来做标记的枚举类型。结构如下:

//ObjectMacros.h

enum class EInternalObjectFlags : int32
{
   None = 0,
   ReachableInCluster = 1 << 23, ///< 簇中可达
   ClusterRoot = 1 << 24, //cluster root 不会被GC回收,簇根节点
   Native = 1 << 25, // UClass
   Async = 1 << 26, //异步对象
   AsyncLoading = 1 << 27, //异步加载中
   Unreachable = 1 << 28, // 不可达对象,会被GC删除
   PendingKill = 1 << 29, // 等待析构,会被GC删除
   RootSet = 1 << 30, // 根节点
   
   GarbageCollectionKeepFlags = Native | Async | AsyncLoading, //拥有这三种标记之一的对象在GC检测时会被跳过
};

标记不可达

以下代码就是获取所有对象,并根据标签 标记部分对象为不可达;可达对象都放入 ObjectsToSerialize 数组内 ( 代码有删减,部分变量名用auto替换,是为了减少长度)

//GarbageCollection.cpp

void PerformReachabilityAnalysis(EObjectFlags KeepFlags, bool bForceSingleThreaded, bool bWithClusters)
   {
      //从系统提供的数组池中获取数组(为了支持多线程)
      auto ArrayStruct = FGCArrayPool::Get().GetArrayStructFromPool();
      auto ObjectsToSerialize = ArrayStruct->ObjectsToSerialize;

      // 继承了FGCObject的非Uobject对象,放入ObjectsToSerialize
      ObjectsToSerialize.Add(FGCObject::GGCObjectReferencer);

      //将对象标记为不可达,并且将根节点以及不可删除对象放入ObjectsToSerialize
      MarkObjectsAsUnreachable(ObjectsToSerialize, KeepFlags);
      
      //分析ObjectsToSerialize数组内的对象,它能达到的对象,去掉不可达标签
      PerformReachabilityAnalysisOnObjectsInternal(ArrayStruct)
   }

代码都有注释,很好理解;ObjectsToSerialize.Add(FGCObject::GGCObjectReferencer); 这一行,很关键,这也是为什么你看很多文章,都说非UObject对象,继承 FGCObject 后,也可以将它引用的对象加入垃圾回收

class FMyStruct: public FGCObject
{
    UObject* NoGCObj;

    void AddReferencedObjects(FReferenceCollector& Collector) override
    {
	Collector.AddReferencedObject(NoGCObj);
    }
}

这部分的代码分析,可见我的上一篇文章:[原创]UE —UObject类智能指针

引用关系分析

MarkObjectsAsUnreachable() 方法消耗不大,因为是多线程操作,且这些 FUObjectItem 结构体对象是内存块连续的数据,遍历不会有缓存 miss。PerformReachabilityAnalysisOnObjectsInternal(ArrayStruct) 才是最复杂,最耗时的操作

UE 是怎么获取一个对象引用了哪些其他对象呢?

UE 中每个 UObject 对象都有一个与之对应的 UClass , 这个UClass保存了对应UObject 的所有反射系统相关信息,描述了各个 Property 之间的内存布局和关系;通过UObject对象的实例化地址就可以将相应的属性遍历出来,进行读写(注意:UClass描述的属性是我们手动加了 UPROPERTY() 标签的)

Obj 对象所引用的其他 UObject 对象,伪代码如下:

//遍历Obj对象的所有属性,如果属性的类型是UObjectle类型,就取消不可达标签
for(TFieldIterator<FProperty> PropertyIter(Obj->GetClass()); PropertyIter; ++PropertyIter)
{
    const FProperty* PropertyIns = *PropertyIter;
    //该属性是否是UObject,是否是Tarray<UObject>,是否是TMap<key,UObject>等
    //然后依次取消 "不可达"标记
    //然后递归遍历该属性对象所引用的对象......
}

这么实现,确实可以 ;但是 UE 并没有这么做,为什么呢?因为属性内其实大部分都是非 UObject类型 ,全部遍历效率太低。因此在生成 UObject对应 UClass 的时候,就构造了一个新的概念,将所引用的其他对象用一个很巧妙的整数,存入 ReferenceTokenStream 变量的 Tokens 数组内

ReferenceTokenStream

断点一个UObject对象,查看其ReferenceTokenStream,内容如下:

这个里面包含当前对象 Obj 引用到的所有标记了 UPROPERTY() 的属性(包括它的父类),那这个数字到底是啥意思呢 ?其实它是三个数字的合并。前8位, 引用对象的嵌套深度 ;中间5位,引用对象的类型( EGCRefenceType );最后则是当前引用的对象的变量在 Obj 对象内的内存偏移值(根据这个偏移值,可获取这个引用的对象)

struct FGCReferenceInfo
{
    union
    {
        struct
        {
            uint32 ReturnCount  : 8;
            uint32 Type         : 5;
            uint32 Offset       : 19;
        };
        //ReturnCount + Type  + Offset
        //00000000    + 00000 + 0000000000000000000
        uint32 Value; 
    };
};

根据 Tokens 内的值,我们可以获取它引用的属性的类型。比如: GCRT_ArrayObject 、 GCRT_ArrayStruct、 GCRT_Object等,根据它们的类型做不同的操作。PerformReachabilityAnalysisOnObjectsInternal 代码内最后调用的分析代码是 ProcessObjectArray (以下代码有删减):

void ProcessObjectArray(FGCArrayStruct& InObjectsToSerializeStruct, const FGraphEventRef& MyCompletionGraphEvent)
{
    while (CurrentIndex < ObjectsToSerialize.Num())
    {
        CurrentObject = ObjectsToSerialize[CurrentIndex++];
        // 获取当前对象的ReferenceTokenStream
        auto* TokenStream = &CurrentObject->GetClass()->ReferenceTokenStream;
        uint32 ReferenceTokenStreamIndex = 0;
        //当前对象的起始地址
        uint8* StackEntryData = (uint8*)CurrentObject;
        while (true)
        {
			//注意:源码这里不是直接++,但是为了方便理解,这里直接用
	    ReferenceTokenStreamIndex++;
	    FGCReferenceInfo ReferenceInfo = TokenStream->AccessReferenceInfo(ReferenceTokenStreamIndex);
            switch(ReferenceInfo.Type)
            {
                case GCRT_Object:
                case GCRT_Class:
                {
                    // 引用对象的地址: 起始地址 + Offset
                    UObject**   ObjectPtr = (UObject**)(StackEntryData + ReferenceInfo.Offset);
                    UObject*&   Object = *ObjectPtr;
             ReferenceProcessor.HandleTokenStreamObjectReference(Object...);
                }
                break;
                case GCRT_ArrayObject:
                {
                    TArray<UObject*>& ObjectArray = *((TArray<UObject*>*)(StackEntryData + ReferenceInfo.Offset));
                    for (int32 ObjectIndex = 0, ObjectNum = ObjectArray.Num(); ObjectIndex < ObjectNum; ++ObjectIndex)
                    {
          ReferenceProcessor.HandleTokenStreamObjectReference(Object...);
                    }
                }
                break;
            }
        }
    }
}

HandleTokenStreamObjectReference 会调用 HandleObjectReference,它会去除它的”不可达”标记,并将它加入NewObjectsToSerialize,开辟新的 task 线程去处理,而不是在当前线程递归

清理

GC 的清理过程,在函数 IncrementalPurgeGarbage 内,它的两个参数可以让我们选择是增量清理还是全量清理,清理的过程分为两步:收集 和 清理

收集不可达对象:GatherUnreachableObjects,多线程操作, 遍历GUObjectArray 将所有标记为”不可达”的 FUObjectItem 加入 GUnreachableObjects 数组

清理看起来实现应该很简单, 直接遍历 GUnreachableObjects 数组,然后delete就行,实际很复杂,具体步骤如下:

  • 获取 GC 锁(因为 BeginDestroy 到 FinishDestroy 之间可能会有异步操作)
  • 执行 UnhashUnreachableObjects 方法,遍历数组GUnreachableObjects,调用对象的 BeginDestroy 方法,可重载这个方法进行自定义操作
  • 执行 IncrementalDestroyGarbage 方法,遍历数组 GUnreachableObjects ,调用对象的 FinishDestroy 方法,注意:此时可能 BeginDestroy 内的异步方法还没执行完毕,因此 FinishDestroy 方法会执行失败,先把对象存储到 GGCObjectsPendingDestruction 中,之后再处理
  • 遍历数组 GGCObjectsPendingDestruction, 尝试调用对象的 FinishDestroy 方法
  • TickDestroyGameThreadObjects 执行真正的删除对象,遍历 GUnreachableObjects 内的所有对象;执行之后的操作,代码如下:
// TickDestroyGameThreadObjects 对垃圾对象最后的处理 
FUObjectItem* ObjectItem = GUnreachableObjects[ObjCurrentPurgeObjectIndexOnGameThread];       
if (ObjectItem)
{
   //将GUObject内的对象设置为nullptr
   GUnreachableObjects[ObjCurrentPurgeObjectIndexOnGameThread] = nullptr;
   UObject* Object = (UObject*)ObjectItem->Object;
   //调用析构函数
   Object->~UObject();
   //释放内存
   GUObjectAllocator.FreeUObject(Object);
}

至此,本文告一段落。当然,关于垃圾回收还有很多未解之谜。比如:神秘的UClass 是怎么生成的 ?它又是如何收集 UObject 的属性(标记了 UPROPERTY ),方法(标记了 UFUNCTION) ?ReferenceTokenStream是如何生成的 ? Cluster (簇) 是什么 ,它对GC有何影响?这些巨坑,等以后再慢慢填