• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

lua源码分析-gc篇(二)数据结构

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

1. 栈
定义
简单的图
2.栈元素TValue
定义
说明
3.GC对象
定义
说明
4.gc链表
定义
5.栈和gc链表的关系
答疑解惑
总结

这是这个gc系列的第二篇,这一篇主要讲GC用到的数据结构,有助于理解gc的,所以放在前面

1. 栈

栈就是我们平时写代码接到的lua_State。在实现上是用一个数组实现的。每个成员类型是TValue,看下文详细介绍。这里不打算详细介绍栈的结构和内容,只会介绍和gc相关的一些内容,主要是帮助我们更好的理解lua的gc。

定义

下面是lua_State的定义,会看到栈的身影,top和base指针。

 
struct lua_State {
  CommonHeader;
  lu_byte status;
  StkId top;  /* first free slot in the stack */
  StkId base;  /* base of current function */
  global_State *l_G;
  CallInfo *ci;  /* call info for current function */
  const Instruction *savedpc;  /* `savedpc' of current function */
  StkId stack_last;  /* last free slot in the stack */
  StkId stack;  /* stack base */
  CallInfo *end_ci;  /* points after end of ci array*/
  CallInfo *base_ci;  /* array of CallInfo's */
  int stacksize;
  int size_ci;  /* size of array `base_ci' */
  unsigned short nCcalls;  /* number of nested C calls */
  lu_byte hookmask;
  lu_byte allowhook;
  int basehookcount;
  int hookcount;
  lua_Hook hook;
  TValue l_gt;  /* table of globals */
  TValue env;  /* temporary place for environments */
  GCObject *openupval;  /* list of open upvalues in this stack */
  GCObject *gclist;
  struct lua_longjmp *errorJmp;  /* current error recover point */
  ptrdiff_t errfunc;  /* current error handling function (stack index) */
};

简单的图



至于base/top和stack/stack_last,以及base_ci/end_ci之间的关系和区别就不打算详细介绍了。主要是lua的指令操作的实现也是在栈上实现的,以及函数调用的时候也要用到栈,只是他们在这个数组的不同区间。

2.栈元素TValue

这个类型是给栈用的,前面说过栈其实是一个TValue的数组。

定义

 
typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;
#define TValuefields    Value value; int tt
typedef struct lua_TValue {
  TValuefields;
} TValue;

说明

  • TValue,是Value加了一个类型
    类型定义:
 
/*
** basic types
*/
#define LUA_TNONE        (-1)
#define LUA_TNIL        0
#define LUA_TBOOLEAN        1
#define LUA_TLIGHTUSERDATA    2
#define LUA_TNUMBER        3
#define LUA_TSTRING        4
#define LUA_TTABLE        5
#define LUA_TFUNCTION        6
#define LUA_TUSERDATA        7
#define LUA_TTHREAD        8
  • 可以看到存放真正值的是这是一个union结构
  • 用过lua的都知道,lua是一种动态类型语言,所有值都是first-class的。所以代码层就是这个Value
  • 简单介绍一下union中成员的含义
成员 含义
GCObject *gc 所有的需要gc的对象都是用的这个成员,所以本系列文章只关注这个成员就好了
void *p 存放lightuserdata
lua_Number n 数值类型,这里也可以看出来lua里面用到的整形浮点型都是用这个存储的,就是double类型
int b bool类型

看代码:

 
// bool类型的宏
#define setbvalue(obj,x) \
  { TValue *i_o=(obj); i_o->value.b=(x); i_o->tt=LUA_TBOOLEAN; }
// table类型的宏
#define sethvalue(L,obj,x) \
  { TValue *i_o=(obj); \
    i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TTABLE; \
    checkliveness(G(L),i_o); }

3.GC对象

gc对象就是指lua里面需要被回收的对象,类型是在LUA_TSTRING(4)到LUA_TTHREAD(8)之间(准确来说还有扩展的类型)。开始看的时候,难免会有疑问,lua里面的所有对象不都是放在栈里面的吗?这个gc对象是个什么的存在?

定义

 
union GCObject {
  GCheader gch;
  union TString ts;
  union Udata u;
  union Closure cl;
  struct Table h;
  struct Proto p;
  struct UpVal uv;
  struct lua_State th;  /* thread */
};
// head
#define CommonHeader    GCObject *next; lu_byte tt; lu_byte marked

说明

  • 这是一个union结构体
  • 这里必须提醒注意下这个GCheader,可以看到前面一个GCheader gch的定义,是跟类型无关的。后面在解答上面疑问的时候,一并说明一下。这个CommonHeader实现了一个链表结构(next),也指明了这个对象的类型(tt),以及颜色(marked)。
  • 会看到除了前面的基本类型之外,多了几个可以回收的类型
 
/*
** Extra tags for non-values
*/
#define LUA_TPROTO    (LAST_TAG+1)
#define LUA_TUPVAL    (LAST_TAG+2)
#define LUA_TDEADKEY    (LAST_TAG+3)

4.gc链表

这个链表是记录了lua里面所有的可回收对象,另外注意这是一个单向链表。真因为是单向链表,为了效率,才不会去整个遍历一遍,才会再增加扫描的链表等,这些后面详细介绍。

定义

这个链表的指针是放在global_State中rootgc中的。

 
/*
** `global state', shared by all threads of this state
*/
typedef struct global_State {
  stringtable strt;  /* hash table for strings */
  lua_Alloc frealloc;  /* function to reallocate memory */
  void *ud;         /* auxiliary data to `frealloc' */
  lu_byte currentwhite;
  lu_byte gcstate;  /* state of garbage collector */
  int sweepstrgc;  /* position of sweep in `strt' */
  GCObject *rootgc;  /* list of all collectable objects */
  GCObject **sweepgc;  /* position of sweep in `rootgc' */
  GCObject *gray;  /* list of gray objects */
  GCObject *grayagain;  /* list of objects to be traversed atomically */
  GCObject *weak;  /* list of weak tables (to be cleared) */
  GCObject *tmudata;  /* last element of list of userdata to be GC */
  Mbuffer buff;  /* temporary buffer for string concatentation */
  lu_mem GCthreshold;
  lu_mem totalbytes;  /* number of bytes currently allocated */
  lu_mem estimate;  /* an estimate of number of bytes actually in use */
  lu_mem gcdept;  /* how much GC is `behind schedule' */
  int gcpause;  /* size of pause between successive GCs */
  int gcstepmul;  /* GC `granularity' */
  lua_CFunction panic;  /* to be called in unprotected errors */
  TValue l_registry;
  struct lua_State *mainthread;
  UpVal uvhead;  /* head of double-linked list of all open upvalues */
  struct Table *mt[NUM_TAGS];  /* metatables for basic types */
  TString *tmname[TM_N];  /* array with tag-method names */
} global_State;

这个结构放了所有关于gc的内容(对着后面的注释看一下):

  • currentwhite:这个就是第一篇中提到的gc流程中的当前白色,如果清理阶段某个对象是otherwhite,那么他就会被清理掉
  • gcstate:控制gc流程的,后面流程中说的状态就是记录在这里
  • rootgc:前面刚提到过,所有可回收的gc对象单向链表
  • gray:为了gc的效率增加的一个gc链表
  • grayagain:为了实现增量式gc,过程中处理中断问题的一个链表
  • GCthreshold,totalbytes,estimate,gcdept,gcpause:这几个单次gc相关的控制或者状态量,直接关系到lua提供的接口collectgarbage
  • 另外一些是全局的一些变量的定义,metatable等。这些跟gc扫描不会遍历整个gc链表有关系。

5.栈和gc链表的关系

栈没有细说,但是他和gc链表的关系必须详细说明一下。如下图所示


答疑解惑

就着问题,说一下栈和gc链表之间的关系。

  • 1.GCObject的存在
    这里就需要了解gc链表和栈中元素的关系。lua的栈是一个数组,里面真正存放了lua里面的所有对象。gc链表存放了lua所有的可回收对象,而事实上gc链表存放的只是所有可回收对象的指针,真正的对象还是以TValue(GCObject* gc成员)的形式放在lua栈中的。当然,对象真正的内容是在堆上(需要自己回收)。而栈和gc链表中存在的只是真实对象的指针,不同类型的结构不一样,所以以这种方式才能存在一起管理

  • 2.怎么做到的?
    前面提到了CommonHead,它在栈和gc链表关系中起了关键的作用。有相同的头部,所以可以通过强制转换在TValue和GCObject直接为了当时需要进行切换.看源码更清晰了,能够转换为GCObject的结构体都是必须包含这个头部的,需要GC的结构都要添加这个头部,如下所所示:

 
//
struct lua_State {
  CommonHeader;
//
typedef struct Table {
  CommonHeader;
// 
typedef struct UpVal {
  CommonHeader;
//
typedef struct Proto {
  CommonHeader;
//
typedef union Udata {
  L_Umaxalign dummy;  /* ensures maximum alignment for `local' udata */
  struct {
    CommonHeader;
typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;

总结

  • 这里并没有把所有的结构体都解释一遍,userdata,upvalue相关的都是比较细节的东西,可以单独看相关的内容,在全局理解的情况下根据自身特性去看也会很容易明白

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
游戏算法中lua脚本详解发布时间:2022-07-22
下一篇:
Lua的sleep函数(转)发布时间:2022-07-22
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap