前言

本篇以源码角度解析UE中标记清除算法GC的实现

https://zhuanlan.zhihu.com/p/401956734

UE 4.26

垃圾回收伪实现

标记清除算法 、 复制算法 、标记-整理算法 、分代收集算法等。我们就用标记清除算法来实现。标记-清除算法，看名字就知道有两个阶段，标记和清除：

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

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

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

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

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

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

GC过程

GC 启动

  • 手动：UWorld::ForceGarbageCollection( bool bFullPurge)会在World.tick 的下一帧强行进行GC
  • 系统会根据默认的设置（可重新配置）一定的间隔时间或者条件下，自动调用垃圾回收

GC锁

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

1
2
3
4
5
6
void CollectGarbage(EObjectFlags KeepFlags, bool bPerformFullPurge)
{
    AcquireGCLock(); //获取GC锁
    CollectGarbageInternal(KeepFlags, bPerformFullPurge); //垃圾回收
    ReleaseGCLock(); //释放GC锁
}
  • 发送信号，表示我想获取GC锁，GCWantsToRunCounter 自增(原子操作)
  • GC 线程 Sleep，查看 AsyncCounter 是否等于 0 判断其他线程是否有阻塞GC的操作还在执行，不等于 0 就继续等待
  • AsyncCounter = 0，通过另一个变量 GCCounter 递增(原子操作)，来标识正在执行GC，其他所有线程将被阻塞
  • 执行内存屏障
  • 将 GCWantsToRunCounter 设为 0，开始真正的 GC 操作
  • GC 操作完毕， GCCounter 自减释放 GC 锁

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

获取所有对象

NewObject的时候把生成的对象的指针放入一个全局数组。

这边GUObjectArray 不是数组，就是一个容器体，为了多线程分块扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
//UObjectBase.cpp
//NewUObject方法调用后,UObject对象初始化
UObjectBase::UObjectBase(UClass* InClass..等参数)
{
   AddObject(InName, InInternalFlags); 
}

void UObjectBase::AddObject(FName InName, 
EInternalObjectFlags InSetInternalFlags)
{ 
   //加入GUObjectArray,为Object分配InternalIndex
   GUObjectArray.AllocateUObjectIndex(Object);
}

UObject对象不直接存入容器的，而是被组装成 FUObjectItem 结构：

1
2
3
4
5
6
7
8
9
//UObjectArray.h
//对象存储的结构体,GC操作的就是这个对象
struct FUObjectItem
{
   class UObjectBase* Object; //对象
   int32 Flags;               //EInternalObjectFlags标识
   int32 ClusterRootIndex;    //当前所属簇索引
   int32 SerialNumber;        //对象序列码(WeakObjectPtr实现用到它)
}

对与上面的Flags的标识 有:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//ObjectMacros.h
enum class EInternalObjectFlags : int32
{
   None = 0,
   ReachableInCluster = 1 << 23, ///< 簇中可达
   ClusterRoot = 1 << 24, //cluster root 不会被GC回收,簇根节点
   Native = 1 << 25, // C++类对象
   Async = 1 << 26, //异步对象
   AsyncLoading = 1 << 27, //异步加载中
   Unreachable = 1 << 28, // 不可达对象，会被GC删除
   PendingKill = 1 << 29, // 等待析构，会被GC删除
   RootSet = 1 << 30, // 根节点

    //拥有这三种标记之一的对象在GC检测时会被跳过
   GarbageCollectionKeepFlags = Native | Async | AsyncLoading,
};

标记不可达

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//GarbageCollection.cpp
   void PerformReachabilityAnalysis(EObjectFlags KeepFlags......等参数)
   {
      //从系统提供的数组池中获取数组（为了支持多线程）
      auto ArrayStruct = FGCArrayPool::Get().GetArrayStructFromPool();
      auto ObjectsToSerialize = ArrayStruct->ObjectsToSerialize;

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

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

所以 非UObject 对象的 FMyStruct 类继承与FGCObject 可以变成可GC

1
2
3
4
5
6
7
8
9
class FMyStruct: public FGCObject
{
    UObject* NoGCObj;

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

引用关系分析

MarkObjectsAsUnreachable() 方法消耗不大，因为是多线程操作，且这些 FUObjectItem 结构体对象是内存块连续的数据，对CPU很友好。

怎么去处理对象的引用依赖关系呢？

遍历：通过UObject对象的实例化地址就可以将相应的属性遍历出来，进行读写，等于就是遍历了一整个引用树，这样效率过低。

所以在反射生成阶段就已经用ReferenceTokenStream收集到Token数组中了。

在 https://zhuanlan.zhihu.com/p/58868952有提到这个结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct FGCReferenceInfo
{
    union
    {
        struct
        {
            uint32 ReturnCount  : 8; //引用对象的嵌套深度
            uint32 Type         : 5; //引用对象的类型( EGCRefenceType )
            uint32 Offset       : 19; //当前引用的对象的变量在 Obj 对象内的内存偏移值
        };
        //ReturnCount + Type  + Offset
        //00000000    + 00000 + 0000000000000000000
        uint32 Value; 
    };
};

img

PerformReachabilityAnalysisOnObjectsInternal 代码内最后调用的分析代码是 ProcessObjectArray

代码看原文

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

清理

遍历 GObjectArray内的数组仍然被标记为不可达的对象放入 GUnreachableObjects ，随后就是执行清除

清理有分俩个逻辑

  • UnhashUnreachableObjects：调用不可达对象的ConditionalBeginDestroy()方法，最终会调用 BeginDestroy()
    • 通知UObject对象，告知这个对象即将被销毁，销毁之前需要做什么事情这是最后的机会
  • IncrementalDestroyGarbage：调用不可达对象的ConditionalFinishDestroy()方法，最终会调用 FinishDestroy()
    • 内部其实也没有真正销毁对象，因为没有调用对象的析构函数
  • TickDestroyGameThreadObjects 调用析构方法的地方
    • 根据GC的设置在下一帧或者规则的时间内执行
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
//标记RF_BeginDestroyed
bool UnhashUnreachableObjects(bool bUseTimeLimit, float TimeLimit)
{
   while (GUnrechableObjectIndex < GUnreachableObjects.Num())
   {
      ObjectItem = GUnreachableObjects[GUnrechableObjectIndex++];
      UObject* Object = static_cast<UObject*>(ObjectItem->Object);
      Object->ConditionalBeginDestroy();//调用BeginDestroy();
      ++GUnrechableObjectIndex;
   }
   return bTimeLimitReached;
}

//标记RF_FinishDestroyed
bool IncrementalDestroyGarbage(bool bUseTimeLimit, float TimeLimit)
{
         GObjCurrentPurgeObjectIndex = 0;
   while (GObjCurrentPurgeObjectIndex < GUnreachableObjects.Num())
   {
      FUObjectItem* ObjectItem = GUnreachableObjects[GObjCurrentPurgeObjectIndex];
      UObject* Object = static_cast<UObject*>(ObjectItem->Object);
      Object->ConditionalFinishDestroy();//调用FinishDestroy();
      ++GObjCurrentPurgeObjectIndex;
   }
   //真正调用析构函数释放内存的地方
   TickDestroyGameThreadObjects(bUseTimeLimit, TimeLimit, StartTime);
   return bCompleted;
}

因此，GC以后可能会出现的情况是：isVaild(Obj) 仍为 true, 实际上这个对象已经被标记为 PendingKill，只是还未置空。因此可使用 isVaildLowLevel(Obj) 来判断更准确

整个分析过程中，我省略了GC锁操作，多线程分析引用等，是为了更专注分析垃圾回收的流程；其实省略的最大一个块就是：Cluster。为什么需要Cluster ? 因为在游戏过程中很多对象的生命周期一致，是命运共同体。比如：粒子内的一堆东西其实就可以当成一个”对象”来处理，能加快分析速度。

总结

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
void CollectGarbageInternal(EObjectFlags KeepFlags, bool bPerformFullPurge)
{
   FCoreUObjectDelegates::GetPreGarbageCollectDelegate().Broadcast();
   {
      FGCScopeLock GCLock;
      //可达性分析
      {
         PerformReachabilityAnalysis(...);
      }
      //解散簇
      if (GUObjectClusters.ClustersNeedDissolving())
      {
         GUObjectClusters.DissolveClusters();
      }      
      //收集不可达对象释放
      {
         GatherUnreachableObjects(bForceSingleThreadedGC);
         if (bPerformFullPurge || !GIncrementalBeginDestroyEnabled)
         {
            UnhashUnreachableObjects(false);//BeginDestory
         }
      }
      //全量回收
      //执行FinishDestory 必须IsReadyForFinishDestroy(异步对象清理完毕) 
      IncrementalPurgeGarbage(false);     
   }
   FCoreUObjectDelegates::GetPostGarbageCollect().Broadcast();
}

GC问答

了解了GC的流程，你觉得应该怎么优化GC？

  1. 打开簇，将Character，Weapon等生命周期一致的 Actor 对象勾选 Cluster
  2. 最好的优化还是减少UObject对象数量（包括：少用蓝图宏，Level内的Actor数量控制）
  3. 优化GC调用时机，原则上能不调用就不调用，可在关键点调用
  4. 采用对象池，不要频繁清理和生成大的对象
  5. 优化源代码，将可达性分析这块看看能不能改成无锁的方式，加快速度

源码阅读

UE5.2

https://www.bilibili.com/video/BV1qu4y1J7Uj?spm_id_from=333.788.videopod.sections&vd_source=d19e47552f1614194f0d0b0662850083

  • UObjectBasse::ProcessNewlyLoadedUObjects() 中会调用Class->AssembleReferenceTokenStream();
    • 引用关系分析开始
    • 为GC做准备
    • 遍历类型中所有FProperty->EmitReferenceInfo(..);
      • 会设置类型 偏移量->加入Tokens 中
  • 入口
  • TryCollectGarbage（）
    • 和CollectGarbage（） 差别就是能不能获取GC锁
    • Try有上限 Try10次的话都获取失败的话就会强制 Force GC
  • CollectGarbage（）
    • CollectGarbageInternal（） 上文有提到
    • CollectGarbageImpl<>()
      • !IsLoading return
      • 执行Flush 等待所有异步加载结束
      • 可达性分析 PerformReachabilityAnalysis()
        • 找出根节点 MarkObjectsFunctions（）
          • 找到Root节点以及flag对象 放入函数指针数组 获取所有对象
          • 将root对象放入 LocalObjectsToSerialize[] 中
          • 其他对象组织簇 Cluster objects
          • 分析不需要GC的Flags对象 这些对象会标记不可达 并加一个Flag
          • 可达对象加入 LocalObjectsToSerialize[] 中
          • 每个线程的 LocalObjectsToSerialize[] 会加到 总数组 ObjectsToSerializeArrays[] 中
        • 遍历每个Root节点 PerformReachabilityAnalysisOnObjects（）
          • 多线程与普通的遍历 Root[] 调用ProcessObjectArray（）
            • 取出与遍历TokenStream[]（第一步反射时写入内存的）
            • 最后调用到把对象设置为可达对象
        • 把不可达对象放到一个数组中GUnreachableObjects[]
      • 清理
        • UnhashUnreachableObjects
          • UnhashUnreachableObjects -> 调用BeginDestory（）
          • IncrementalPurgeGarbage -> IncrementalDestroyGarbage（）
            • 对每个不可达对象调用ConditionalFinishDestroy（）->调用FinishDestroy（）
            • 会进行俩次while 因为可能多线程会某些obj依旧在加载中第二次while会等待渲染线程完成
          • TickPurge
            • TickDestroyGameThreadObjects（）调用 obj析构函数
            • 这里会清理内存碎片 省略