Lua源码剖析（三）数据结构体

发表于   |   更新于 | 分类于 | | 访问次数： 次
字数统计: 4.2k | 阅读时长 ≈ 16

一. 前言

  在第一讲里，我们提到了对于脚本语言来说，传值如何存储是很需要慎重考虑的事，本文就展开详细看看Lua的数值是如何存储的。

二. 基础数据结构体

  在第一讲有提到，如果我们希望传递多种不同的数值，那么脚本语言设计的时候，比较合理的一种方式就是让数值自带类型标记，然后再以联合的形式构建数据结构，类似于

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef union
{
    // 随便列几个数据类型
    bool  bBool;
    int   nInt;
    void* pPointer;
} Value;

struct ScriptValue
{
    int   nType;
    Value value;
}

  字节码为字面值时，先检查nType获取类型，再读取Value做对应类型数据的存储和处理。

  再结合之前提及的，需要做内存回收的数据类型和不需要做数据回收的，可以再封装一个GC头部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
union GCObject
{
    // 需要GC的数值类型  
};

typedef union
{
    GCObject* pGCObject;
    bool      bBool;
    int       nInt;
    void*     pPointer;
} Value;

struct ScriptValue
{
    int nType;
    Value;
}

  而实际上，Lua的数值结构封装可以说是一模一样。

  Lua的基础数据由宏定义可以看到

1
2
3
4
5
6
7
8
9
10
11
// lua.h
#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

  其中的LUA_TLIGHTUSERDATA和LUA_TUSERDATA一样，对应的都是void*指针，区别在于，LUA_TLIGHTUSERDATA的分配释放是由Lua外部的使用者如C/C++来完成，而LUA_TUSERDATA则是通过Lua内部来完成的。换言之，前者不需要Lua去关心它的生存期，由使用者自己去关注，后者则反之。

  然后看看Lua的数据结构，就很好懂了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
** Union of all Lua values
*/
typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;

#define TValuefields	Value value; int tt

typedef struct lua_TValue {
  TValuefields;
} TValue;

  其中GCObject为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//tt，即该GC对象的具体类型
//next，指向GCObject的指针，用于GC算法内部实现链表
//marked，用于GC算法内部实现
#define CommonHeader	GCObject *next; lu_byte tt; lu_byte marked

typedef struct GCheader {
  CommonHeader;
} GCheader;

/*
** Union of all collectable objects
*/
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 */
};

  其中有五个类型就是接下来要详细展开说明的：字符串TString、表Table以及上值UpVal与函数Proto（闭包Closure）。

三. 字符串

  字符串，无非就是字符数组，是每种语言都需要考虑存储的数据类型，对于脚本语言来说也不例外，通常来说会有以下需要考虑的因素

  • 如何存储：常见的无非是长度+变长指针申请空间
  • 如何使用：这里需要取舍的地方主要有
    • 是否允许对字符串进行截断/增长的操作：如果允许则可能带来内存碎片等问题，多个字符串的统一存取也会存在问题（redis中有类似处理）。如果不允许，那对字符串的操作就需要转化为新增字符串，内存的代价是否在接受范围内。
    • 如何节约空间：对于相同的字符串是否可以仅存一份？这很容易让人想到哈希，哈希的算法以及哈希后的存储方式也需要考虑。
  • 如何销毁：对于设计了自动垃圾回收的，当然也是将字符串归为垃圾回收对象内，进行统一处理。

  对于Lua来说，其设计也在此樊笼之内。关键性的取舍就在于为了节约内存和加快查找速度，选用了哈希桶+字符串哈希存储，将总表放置在全局变量中方便查找，然后针对各种上述细节挨个处理即可。下面就看看Lua的实现吧。

  先看看字符串的定义，其实就很常规，唯一比较有特色的地方时有一个dummy，注释也很详细了，其实就是做了一个字节对齐操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define LUAI_USER_ALIGNMENT_T	union { double u; void *s; long l; }

/* type to ensure maximum alignment */
typedef LUAI_USER_ALIGNMENT_T L_Umaxalign;

typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;
    unsigned int hash;
    size_t len;
  } tsv;
} TString;

  在上一讲中，我们提到过Lua栈的全局变量里，保存了所有字符串的统一集合：stringtable，其定义如下

1
2
3
4
5
6
7
8
9
typedef struct global_State {
    stringtable strt;  /* hash table for strings */
}

typedef struct stringtable {
    GCObject** hash; // 存放一系列链表的数组
    lu_int32 nuse;  /* number of elements */
    int size;
} stringtable;

四. 表

  每种语言在设计的时候都需要考虑，是否需要增加容器，以及增加哪些容器。如C++广为使用的多种stl容器，就极大的丰富了语言的能力，提高了开发效率。那么设想，如果我们仅设计一种简介但是提供了诸多扩展的容器，是否也可以满足脚本编写者们的需要呢？

  如果要这么做，那这个容器大概需要有以下特点

  • 基本的数据存储和查找能力：所有容器都是用来存东西的，只是存放的方法、查找的方法不同，所以最少需要提供一种以上的数据存储方式，便于存储且便于查找
  • 扩展能力：仅有以上功能的话不能满足更高自由度的操作，如果我们可以给出方法接口让用户自己实现方法去做想做的事，那就可以极大的提高这种容器的易用性

  结合以上，我们可以简单的做一个容器，假设我们也称之为表，那可能可以写作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ExtendMethod
{
    // 扩展函数指针结构体，这里随便列两个
    void (OperateValue*)(TValue value);
    void (OperateTable*)(Table* pTable1, Table* pTable2);
    .......
};

struct Table
{
    CommonHeader;	         
    GCObject*     gclist;    // 表也属于GC对象，加上一个指针
    ExtendMethod* pMethod;   // 提供扩展点
    int           nArraySize;   
    Tvalue*       pArray;
};

  这样的表存在一个缺点：虽然值存储可以是任意TValue类型，但是索引只能是数字，如果想存储键值对而键非数字则会非常麻烦，当然也不是不能解决，只是还有更好的方法，就是再加入一个数组存储k/v型，将结构体改为如下所示。每个节点Node，均用Tvalue类型的key和value，从而做到任意的键值均可存储。插入k/v时，对key做哈希（假设为i)，然后存入对应的Node数组索引下标为i的地方。这种做法的好处不言而喻，但是同时也带来了个问题：插入和查询都需要去考虑在哪种数组，扩容和缩容亦然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct ExtendMethod{.......};

typedef struct Node 
{
    TValue key;
    TValue val;
} Node;

struct Table
{
    CommonHeader;	         
    GCObject*     gclist;    
    ExtendMethod* pMethod;   
    int           nArraySize;   
    Tvalue*       pArray;
    int           nNodeSize;
    Node*         pNode;
};

  在此情况下，其实ExtendMethod已经没有特别去申请的必要了，因为函数指针也可以包含在TValue之中实现，因此可以做进一步简化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct Node 
{
    TValue key;
    TValue val;
} Node;

struct Table
{
    CommonHeader;	         
    GCObject*     gclist;    
    Table*        pMethod;   
    int           nArraySize;   
    Tvalue*       pArray;
    int           nNodeSize;
    Node*         pNode;
};

  现在呢，我们拥有了一个能够存储任意类型的数据、关联数据的容器，然后再实现一些相应的操作，看起来就可以让一个普通的容器跑起来了。不过为了追求完美，我们还可以做一些优化。

  首先第一个问题就是，哈希得到的结果会很分散，如果我们希望能存放在比较规整的数组中，我们可以用哈希对数组大小取余，余数即数组索引。为此我们对key单独创建一个结构体增加链表指针，即通过哈希找到该key所在数组位置后，再根据key的链表取找寻对应的key。（实际Lua会比这个更复杂一点，用一定的运算复杂度换取了空间的优化，在后文中会详细说明）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct TKey
{
    TValue value;
    Node*  pNext;
} TKey;

typedef struct Node 
{
    TKey   key;
    TValue val;
} Node;

struct Table
{
    CommonHeader;	         
    GCObject*     gclist;    
    Table*        pMethod;   
    int           nArraySize;   
    Tvalue*       pArray;
    int           nNodeSize;
    Node*         pNode;
};

  第二个问题，已经有了一个k/v型数组了，那纯数字索引的数组是否还有存在的必要呢？是否可以删掉呢？其实是可以不要的，但是哈希的速度一定是没有一个简单的判断+直接地址索引来得快的，所以适当的数字索引数组可以提高表的查询/插入速度，这就是一个速度、内存以及实现的复杂度上的考量。Lua的开发者判定存在合理，但是自己在设计和实现的时候，需要根据实际的需求、使用场景以及测试数据来判断是否需要保留。事实上早期的Lua版本仅保留了k/v，后面为了提高运行速率又加上了数组。

  至此，我们已经设计了一个简洁高效且扩展性极强的容器数据结构，而实际上，Lua源码几乎就是这么做的。下面再看看源码一定有着一目了然的感觉。

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
// Lua 5.1
typedef union TKey {
  struct {
    TValuefields;
    struct Node *next;  /* for chaining */
  } nk;
  TValue tvk;
} TKey;


typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */ 
  lu_byte lsizenode;  /* log2 of size of `node' array */
  struct Table *metatable;
  TValue *array;  /* array part */
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  GCObject *gclist;
  int sizearray;  /* size of `array' array */
} Table;

  考虑到表的包容性以及复杂性，其各种操作函数如初始化、查询、扩容等，其实也存在着诸多考量。考虑到篇幅问题以及本文主旨，在此不做展开，后文中会单独拎出来详谈，有兴趣的可以自己先思考实现，再和Lua进行比对，就更有收获了。如果发现自己写的更优秀，那岂不是一个重大的创新。

五. 上值和函数（闭包）

  让我们看看如下的两个函数

1
2
3
4
5
6
7
8
9
10
function a(int a)
{
    printf(a);
}

function b()
{
    int val;
    a(val);    
}

  非常好理解，函数a()会打印传参，函数b()调用了a，传递了一个值进去实现打印。

  这是一个简单的函数调用，如果我们希望脚本语言支持函数（这都不支持可能没人愿意用了吧），那我们就要想办法用数据结构来表示函数，并且该数据结构最好还能够方便的表达层级关系以及传值。所以至少需要几方面基本的元素：

  • 指令集的存储
  • 局部变量
  • 指针指向栈上的传参及上层函数、全局变量、静态变量等

  由此可以实现一个基本的雏形，如下所示

1
2
3
4
5
6
typedef struct TFunction
{
    Instruction* pPC;		  // 函数指令集
    TValue*	     pLocalVal;    // 函数内定义的变量
    TValue*      pExternalVal; // 外部变量
}TFunction;

  当然实际实现的时候，还需要加上一些比如变量数量，指令数量等，如果想要加上调试信息，还得配上和指令对应的行号等信息，这里简单的称之为Others

1
2
3
4
5
6
7
typedef struct TFunction
{
    Instruction* pPC;		  // 函数指令集
    TValue*	     pLocalVal;    // 函数内定义的变量
    TValue*      pExternalVal; // 外部变量
    Other	     otherVal;     // 辅助变量
}TFunction;

  这样的函数结构，可以满足C/C++中的函数使用。但是如果我们希望函数能够更灵活，做到如同变量一样的生效，那么这还是不够的。在前面数值定义时，我们将函数也定义为了TValue，那么函数只要不是定义为局部变量，嵌套的函数应该也可不受外层约束。比如下面这个例子，b()在a()之外也可以调用，这样的灵活性可以提高脚本的丰富程度，同时也减少了约束。

1
2
3
4
5
6
7
8
9
10
11
12
local var1 = 1
function a()
    local var2 = 1
    function b()
        var1 = var1 + 1
        var2 = var2 + 1
    end 
    b()
end

a()
b()

  为此，我们需要对当前的外部变量做一些调整：当前的外部变量由指针指向栈，而如上例a()函数调用完成释放后，栈上已经没有了var2，那b()的调用就会出错。因此，我们对外部变量进行结构体封装：

  • 用一个指针pStackVal指向栈，如果栈上的变量回收，则改为指向自身的value结构体获取数值
  • 封装value联合体，若值仍在栈上，则通过pNext进行链表连接后续的外部变量值；若不在栈上，则存储于FixedVal中。
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct ExternalVal
{
    TValue* pStackVal;

    union 
    {
        Tvalue FixedVal;
        struct 
        {
            ExternalVal* pNext;
        }list;
    }value;
}ExternalVal;

  由此，我们再改写一下函数的定义

1
2
3
4
5
6
7
typedef struct TFunction
{
    Instruction* pPC;		  // 函数指令集
    TValue*	     pLocalVal;    // 函数内定义的变量
    ExternalVal* pExternalVal; // 外部变量
    Other	     otherVal;     // 辅助变量
}TFunction;

  接下来要考虑的，是脚本语言是要和静态语言进行交互的，因此难免会有例如C/C++的函数调用，而此类函数其实仅需要存储函数指针及传值，并不需要用到指令集之类，所以我们对刚刚做的TFunction进行调整，新建CFunction和LFunction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct TFunction
{
    Instruction* pPC;		  // 函数指令集
    TValue*	     pLocalVal;    // 函数内定义的变量
    Other	     otherVal;     // 辅助变量
}TFunction;

typedef struct CFunction
{
    CommonFunctionHeader;
    void (func*)(Lua_state* L);
    ExternalVal* pVal;
}CFunction;

typedef struct LFunction
{
    CommonFunctionHeader;
    struct TFunction* pFunction;
    ExternalVal*      pVal;
}

  考虑到C仅需要传参和返回值，其实用不上这么复杂的ExternalVal，可以直接换为普通的TValue结构体，所以最后可以改为

1
2
3
4
5
6
typedef struct CFunction
{
    CommonFunctionHeader;
    void (func*)(Lua_state* L);
    TValue* pVal;
}CFunction;

  至此，一个灵活的函数结构体就实现完成了。对比Lua，函数原型Proto即为此处的函数通用结构体TFunction，上值UpVal即为外部变量ExternalVal，而上值和函数原型的组合，就称之为闭包Closure。

  下面看看Lua的实现，相关的结构体有Closure及Proto。Lua的函数有三种类型：

  • Lua 函数 (LUA_TLCL)：T Lua Closure
  • C 函数 (LUA_TCCL)：T C Closure
  • 轻量级 C 函数 (LUA_TLCF)：Light C Function（5.2之后才有）

  其中 LUA_TLCL 和 LUA_TCCL 属于 GCUnion，即需要被回收的类型，被称为 Closure。当 LUA_TCCL 不包含 upvalue 时，直接用 C 函数指针即可，不必构造 Closure 对象, 也就是 LUA_TLCF。

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
/*
** Closures
*/
#define ClosureHeader  \
    CommonHeader;      \
    lu_byte nupvalues; \
    GCObject *gclist

typedef struct CClosure
{
    ClosureHeader;
    lua_CFunction f;
    TValue upvalue[1]; /* list of upvalues */
} CClosure;

typedef struct LClosure
{
    ClosureHeader;
    struct Proto *p;
    UpVal *upvals[1]; /* list of upvalues */
} LClosure;

typedef union Closure
{
    CClosure c;
    LClosure l;
} Closure;

  Proto结构体则是用于将函数解析后的opcode结果传递给后续执行所必备的桥梁，一个Lua文件有一个总的Proto结构体,如果它内部还有定义函数,那么每个函数也有一个对应的Proto结构体，其关键数据结构和我们自己构建的一样。

  • TValue : 存放常量的数组.
  • Instruction : 存放指令的数组.
  • struct Proto : 该Proto内定义的函数相关的Proto数据.
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
/*
** Function Prototypes
*/
typedef struct Proto
{
    CommonHeader;
    lu_byte numparams; /* number of fixed parameters */
    lu_byte is_vararg;
    lu_byte maxstacksize; /* number of registers needed by this function */
    int sizeupvalues;     /* size of 'upvalues' */
    int sizek;            /* size of 'k' */
    int sizecode;
    int sizelineinfo;
    int sizep; /* size of 'p' */
    int sizelocvars;
    int linedefined;        /* debug information  */
    int lastlinedefined;    /* debug information  */
    TValue *k;              /* constants used by the function */
    Instruction *code;      /* opcodes */
    struct Proto **p;       /* functions defined inside the function */
    int *lineinfo;          /* map from opcodes to source lines (debug information) */
    LocVar *locvars;        /* information about local variables (debug information) */
    Upvaldesc *upvalues;    /* upvalue information */
    struct LClosure *cache; /* last-created closure with this prototype */
    TString *source;        /* used for debug information */
    GCObject *gclist;
} Proto;

  上值UpVal对应的代码如下，这里的closed和open指的就是上文所说明的栈上是否还存在变量的情况。

1
2
3
4
5
6
7
8
9
10
11
typedef struct UpVal {
  CommonHeader;
  TValue *v;  /* points to stack or to its own value */
  union {
    TValue value;  /* the value (when closed) */
    struct {  /* double linked list (when open) */
      struct UpVal *prev;
      struct UpVal *next;
    } l;
  } u;
} UpVal;

  这样一来，函数相关的结构体实现就一目了然了。

六. 总结

  本文内容涵盖了从零开始构建各种数值数据结构的思路和实现，并比对了Lua源码的实现，相信认真阅读的你一定有所收获，当然如果能边思考边写边自行对比，那一定获益更多了。

参考文献

  1. Lua-Source-Internal
  2. 《A Look at the Design of Lua》
  3. http://lua-users.org/wiki/LuaSource
  4. 《Lua 源码欣赏》
  5. 《The Implementation of Lua 5.0》
坚持原创，坚持分享，谢谢鼓励和支持