客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
基础结构
Value与TValue lua为了方便对所有的类型进行统一管理，把它们都抽象成了一个叫做Value的union结构中 注：sizeof(Value)=8 /* ** Union of all Lua values */ typedef union Value { GCObject *gc; /* collectable objects */ void *p; /* light userdata */ int b; /* booleans */ lua_CFunction f; /* light C functions */ lua_Integer i; /* integer numbers */ lua_Number n; /* float numbers */ } Value; 从定义可以看出，主要把这些类型划分为了需要GC的类型和不需要GC的类型 由于Value是union的结构，所以每个Value实例里同时只会有一个字段是有效的 而为了知道具体哪个字段是有效的，也就是具体该Value是什么类型，从而有了TValue这个struct结构，主要在Value基础上wrap了一个_tt字段来标识Value的具体类型 注：sizeof(TValue)=16 #define TValuefields Value value_; int tt_ typedef struct lua_TValue { TValuefields; } TValue;
GCUnion、GCObject、CommonHeader lua把所有值按是否需要被GC，划分为了一般类型和被GC管理的类型。所有需要被GC的类型，被定义在了GCUnion里 /* ** Union of all collectable objects (only for conversions) */ union GCUnion { GCObject gc; /* common header */ struct TString ts; /* 字符串 */ struct Udata u; /* 用户数据 */ union Closure cl; /* 函数 */ struct Table h; /* 表 */ struct Proto p; /* 函数原型：存放函数字节码等信息 */ struct lua_State th; /* 线程 */ }; 可以发现String、UserData、Closure、Table、Proto、luaState等类型都是需要被GC的，GCUnion结构和Value类似，也是同时只有一个字段是有效的 所以我们自然而然会想到，是不是类似TValue一样，在外面给包一层type呢，但是lua实现这边并没有这样做 而是让TString、UData这些"子类"都在各自开头定义了一个叫做CommonHeader的宏，这个宏里包含了type和一些其他字 而每个GC类型都需要在在其struct头部定义该宏，从而可以造成一种所有GC类型都继承自一个带有CommonHeader宏的基类的假象 /* ** Common type for all collectable objects */ typedef struct GCObject GCObject; /* ** Common Header for all collectable objects (in macro form, to be ** included in other objects) */ #define CommonHeader GCObject *next; lu_byte tt; lu_byte marked // 注：tt，即该GC对象的具体类型 // 注：next，指向GCObject的指针，用于GC算法内部实现链表 // 注：marked，用于GC算法内部实现 /* ** Common type has only the common header */ struct GCObject { CommonHeader; }; 这样组织的好处在于lua可以把所有的GC类型的对象都视作是一个GCObject。 再比如，lua里创建单个gcobject的函数如下 /* ** create a new collectable object (with given type and size) and link ** it to 'allgc' list. */ GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) { global_State *g = G(L); GCObject *o = cast(GCObject *, luaM_newobject(L, novariant(tt), sz)); o->marked = luaC_white(g); o->tt = tt; o->next = g->allgc; g->allgc = o; return o; }
所有的gc类型就都会调用luaC_newobj函数来创建一个GCObject实例，区别只是在于传入的type和内存size不一样而已 该函数会根据实际传入的内存大小来开辟空间，然后填充CommonHeader部分的数据 最后，它还会把该obj挂接到global_state结构里定义的GC列表GCObject* allgc（保存所有gc类型对象的指针）的头部，以供GC模块使用 每个类型只用把创建出来的实例剩余内存部分的数据设置好即可，比如下面的String类型 #define sizelstring(l) (sizeof(union UTString) + ((l) + 1) * sizeof(char)) /* ** Get the actual string (array of bytes) from a 'TString'. ** (Access to 'extra' ensures that value is really a 'TString'.) */ #define getstr(ts) \ check_exp(sizeof((ts)->extra), cast(char *, (ts)) + sizeof(UTString)) #define gco2ts(o) \ check_exp(novariant((o)->tt) == LUA_TSTRING, &((cast_u(o))->ts)) /* ** creates a new string object */ static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) { TString *ts; GCObject *o; size_t totalsize; /* total size of TString object */ // 计算一个string实例实际内存占用大小：其实是UTString结构占用，再加上(charlength+1)个char大小 totalsize = sizelstring(l); // 创建GCObject o = luaC_newobj(L, tag, totalsize); ts = gco2ts(o); // 填充string实例特有字段 ts->hash = h; ts->extra = 0; // 取TString关联的char数组 getstr(ts)[l] = '\0'; /* ending 0 */ return ts; } string在创建完成以后，调用了内部的gco2ts函数，把本来指向GCObject指针强转成了指向TString的指针，然后对TString的额外元数据进行了赋值
字符串 考虑到性能和内存等方面，lua把String分成短字符串和长字符串两类来分开处理（注：长度大于40的为长串，反之则为短串；#define LUAI_MAXSHORTLEN 40） 如：短串会先在全局stringtable的hashmap结构表中查询，若查询不到才会创建；而长串不查询，直接创建；两个相同的长串将会是两个副本，占用两份内存。 主要原因是： ① 短串复用度会比长串要高。比如obj["id"] = 12, obj["type"] = 0，类似"id"、"type"这种短串可能会在程序很多处地方使用到，如果开辟多份就有点浪费了；而长串则很少会有重复的 ② 长串计算哈希耗时长
TString结构体 /* ** Header for string value; string bytes follow the end of this structure ** (aligned according to 'UTString'; see next). */ typedef struct TString { CommonHeader; lu_byte extra; /* reserved words for short strings; "has hash" for longs */ lu_byte shrlen; /* length for short strings */ unsigned int hash; union { size_t lnglen; /* length for long strings */ struct TString *hnext; /* linked list for hash table */ } u; } TString; 字段含义： CommonHeader -- GC对象通用的CommonHeader
UTString Union /* ** Ensures that address after this type is always fully aligned. */ typedef union UTString { L_Umaxalign dummy; /* ensures maximum alignment for strings */ TString tsv; } UTString; 为了实现TString结构的内存对齐，lua又在其上wrap了一层UTString结构 sizeof(L_Umaxalign)为8，保证UTString对象本身会按照8字节进行对齐
使用luaS_newlstr创建字符串 /* ** new string (with explicit length) 创建字符串 */ TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { if (l <= LUAI_MAXSHORTLEN) /* short string? */ return internshrstr(L, str, l); // 创建短串 else { TString *ts; if (l >= (MAX_SIZE - sizeof(TString))/sizeof(char)) // MAX_SIZE=0x7FFFFFFFFFFFFFFF luaM_toobig(L); // 长度太大了，直接报错 ts = luaS_createlngstrobj(L, l); // 创建长串 memcpy(getstr(ts), str, l * sizeof(char)); // 将str的内容拷贝到ts的内存中 return ts; } } /*************************************创建短串***************************************/ /* ** checks whether short string exists and reuses it or creates a new one */ static TString *internshrstr (lua_State *L, const char *str, size_t l) { TString *ts; global_State *g = G(L); unsigned int h = luaS_hash(str, l, g->seed); // 计算Hash 为了对长度较长的字符串不逐位hash，luaS_hash函数内部也是根据长度的2次幂计算出了一个步长step，来加速hash的过程 // 查找该Hash是否在全局stringtable对象g->strt中 TString **list = &g->strt.hash[lmod(h, g->strt.size)]; lua_assert(str != NULL); /* otherwise 'memcmp'/'memcpy' are undefined */ for (ts = *list; ts != NULL; ts = ts->u.hnext) { if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { /* found! */ if (isdead(g, ts)) /* dead (but not collected yet)? */ changewhite(ts); /* resurrect it */ // 如果在stringtable中，直接返回 return ts; } } // stringtable的元素数量已经大于桶数，那么以两倍的尺寸对stringtable进行resize if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) { // luaS_resize是实际改变stringtable桶数量的函数，只会在2个地方被调用 // 一个是这里：桶数量小于了元素数量，说明散列比较拥挤了，会对桶进行两倍的扩容 // 即：newsize>oldsize。这个时候会先进行扩容，然后进行rehash。扩容跟到里面去调用的就是realloc函数。而rehash的代码也很简洁，就是简单的遍历每个桶，把每个桶里的元素再哈希到正确的桶里去 // 另一个是在gc时，如果发现桶数量大于4倍的元素数量，说明散列太稀疏了，会对桶数量进行减半操作 // 即：newsize < oldsize，顺序是倒过来的，需要先根据newsize进行rehash，然后在保证所有元素已经收缩到newsize个数的桶里以后，才能进行shrink操作，这里也是调用的realloc函数来实现 luaS_resize(L, g->strt.size * 2); list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */ } // 调用createstrobj函数创建TString。其中包括了内存的分配，CommonHeader的填充，TString特化字段的填充等 ts = createstrobj(L, l, LUA_TSHRSTR, h); memcpy(getstr(ts), str, l * sizeof(char)); ts->shrlen = cast_byte(l); ts->u.hnext = *list; // 更新stringtable的链表，以及对stringtable的元素数量加1 *list = ts; g->strt.nuse++; return ts; } // 短串实现的hashmap结构体 typedef struct stringtable { TString **hash; // 基于TString的hashmap，也叫做散列桶。基本结构是一个数组，每个数组里存的是相同hash值的TString的链表 int nuse; /* number of elements */ // 当前实际的元素数 int size; // 当前的桶大小 } stringtable; /*************************************创建长串***************************************/ TString *luaS_createlngstrobj (lua_State *L, size_t l) { TString *ts = createstrobj(L, l, LUA_TLNGSTR, G(L)->seed); ts->u.lnglen = l; // 设置长串的长度变量 return ts; }
内存结构如下： 注1：将value_.gc指针强制转换为TString*类型，即可读取TString中数据 注2：(char*)(value_.gc) + sizeof(TString)即为字符串的内容
函数 lua函数及C函数，都是一个函数闭包。函数闭包存储了函数本身以及外围作用域的局部变量（upvalue）注：env环境也是upvalue的一种 #define ClosureHeader \ CommonHeader; lu_byte nupvalues; GCObject *gclist //包含了CommonHeader的宏，表明Closure是gc类型 //nupvalues为upvalue的个数 //GCObject* gclist：与gc有关，将table加入到gray表中时gclist指向gray表中的下一个元素或者为空 /* ** Upvalues for Lua closures // Lua函数闭包的Upvalues */ struct UpVal { TValue *v; /* points to stack or to its own value */ lu_mem refcount; /* reference counter */ // 引用计数 union { struct { /* (when open) */ UpVal *next; /* linked list */ int touched; /* mark to avoid cycles with dead threads */ } open; TValue value; /* the value (when closed) */ // 关闭状态时的value值 } u; }; // C函数闭包 typedef struct CClosure { ClosureHeader; lua_CFunction f; // 函数指针 TValue upvalue[1]; /* list of upvalues */ //C函数的闭包天生是关闭的，直接使用TValue来保存upvalue } CClosure; // Lua函数闭包 typedef struct LClosure { ClosureHeader; struct Proto *p; // 函数原型（Prototype）的结构 UpVal *upvals[1]; /* list of upvalues */ //函数的upvalue指针列表，记录了该函数引用的所有upvals } LClosure; typedef union Closure { CClosure c; LClosure l; } Closure;
Proto结构体 每个函数会被编译成一个称之为原型（Proto）的结构 原型主要包含6部分内容：函数基本信息（basic info：含参数数量、局部变量数量等信息）、字节码（bytecodes）、常量（constants）表、upvalue（闭包捕获的非局部变量）表、调试信息（debug info）、子函数原型列表（sub functions） // Lua虚拟机的指令集为定长（Fixed-width）指令集，每条指令占4个字节（32bits），其中操作码（OpCode）占6bits，操作数（Operand）使用剩余的26bits /* ** type for virtual-machine instructions; ** must be an unsigned with (at least) 4 bytes (see details in lopcodes.h) */ #if LUAI_BITSINT >= 32 typedef unsigned int Instruction; #else typedef unsigned long Instruction; #endif // 描述函数原型上的一个upvalue /* ** Description of an upvalue for function prototypes */ typedef struct Upvaldesc { TString *name; /* upvalue name (for debug information) */ // upvalue的名称（debug版字节码才有该信息） lu_byte instack; /* whether it is in stack (register) */ // 是否在寄存器中 lu_byte idx; /* index of upvalue (in stack or in outer function's list) */ // upvalue在栈或外部函数列表中index } Upvaldesc; // 描述函数原型上的一个局部变量（debug版字节码才有该信息） /* ** Description of a local variable for function prototypes ** (used for debug information) */ typedef struct LocVar { TString *varname; // 变量名 int startpc; /* first point where variable is active */ // 起始指令索引 int endpc; /* first point where variable is dead */ // 终止指令索引 } LocVar; // 函数原型 /* ** Function Prototypes */ typedef struct Proto { CommonHeader; // GC类型 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' */ // Upvaldesc *upvalues个数 int sizek; /* size of 'k' */ // 常量TValue *k个数 int sizecode; // 指令Instruction *code个数 int sizelineinfo; // 指令int *lineinfo行号个数 （debug版字节码才有该信息） int sizep; /* size of 'p' */ // 子函数原型个数 int sizelocvars; // 局部变量个数 int linedefined; /* debug information */ // 函数起始代码行（debug版字节码才有该信息） int lastlinedefined; /* debug information */ // 函数结束代码行（debug版字节码才有该信息） 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) */ // 指令行号表（debug版字节码才有该信息） LocVar *locvars; /* information about local variables (debug information) */ // 局部变量表（debug版字节码才有该信息） Upvaldesc *upvalues; /* upvalue information */ // upvalue表 struct LClosure *cache; /* last-created closure with this prototype */ // 最近一次使用该原型创建的closure TString *source; /* used for debug information */ // 源代码文件名（debug版字节码才有该信息） GCObject *gclist; // 与gc有关，将table加入到gray表中时gclist指向gray表中的下一个元素或者为空 } Proto; 这里的localvars和upvalues是函数原型中包含局部变量和upvalue的原始信息。在运行时，局部变量是存储在Lua栈上，upvalue索引是存储在LClosure的upvals字段中的
CClosure结构体 CClosure其实是lua在C侧对闭包的一个模拟。可以通过lua_pushcclosure函数来往栈上加入一个C闭包 // 该函数会先创建一个CClosure结构，然后把提前push到栈顶的n个元素作为upvalue，将其引用存储在CClosure的upvalue数组中 LUA_API void lua_pushcclosure (lua_State *L, lua_CFunction fn, int n) { lua_lock(L); if (n == 0) { setfvalue(L->top, fn); } else { CClosure *cl; api_checknelems(L, n); api_check(L, n <= MAXUPVAL, "upvalue index too large"); cl = luaF_newCclosure(L, n); cl->f = fn; L->top -= n; while (n--) { setobj2n(L, &cl->upvalue[n], L->top + n); /* does not need barrier because closure is white */ } setclCvalue(L, L->top, cl); } api_incr_top(L); luaC_checkGC(L); lua_unlock(L); } CClosure和LClosure最大区别，在于LClosure是需要去解析lua代码来得到upvalue以及字节码等信息，在执行时需要去根据opcode来执行； 而CClosure是一个直接的C函数，可直接执行，并且upvalue也是在创建前调用者手动push到栈上去的。
表（table） table应该算是lua最灵魂的一个结构了，它有以下特点： 容器功能：与其他语言相似，lua也内置了容器功能，也就是table。而与其他语言不同的是，lua内置容器只有table。 table的内部结构又分为了数组和哈希表（字典）两个部分，根据不同情况来决定使用哪个部分。 面向对象功能：与其他语言不同的时，lua并没有把面向对象的功能以语法的形式包装给开发者。 而是保留了这样一种能力，待开发者去实现自己的面向对象，而这一保留的能力，也是封装在table里的。 table里可以组合一个metatable，这个metatable本身也是一个table，它的字段用来描述原table的行为。 #define TValuefields Value value_; int tt_ typedef union TKey { struct { TValuefields; // 主要是为了方便对value_、tt_变量的访问，不用写成tvk.value_、tvk.tt_ int next; /* for chaining (offset for next node) */ // 相当于当前Node的下一个Node的索引Offset（在当前Node后面，next值为正；在当前Node前面，next值为负） } nk; TValue tvk; } TKey; typedef struct Node { TValue i_val; |
请发表评论