字符串
实现在lstring.c中。
字符串类型TString定义如下:
typedef union TString {
L_Umaxalign dummy; /* ensures maximum alignment for strings */
struct {
CommonHeader;
lu_byte reserved;
unsigned int hash;
size_t len;
} tsv;
} TString;
字符串内容紧随其后,以\0结尾,用宏getstr来获取字符串指针:
#define getstr(ts) (const char *)((ts) + 1)
len是字符串的长度,不包括结尾的\0。CommonHeader用于GC。hash是由字符串内容计算出来的哈希值。dummy可能是为了让字符串指针内存对齐,提高访问速度。
lua的字符串内容不可修改,相同字符串会合并存储在一个全局字符串表中,字符串表定义如下:
typedef struct stringtable {
GCObject **hash;
lu_int32 nuse; /* number of elements */
int size;
} stringtable;
这是一个开散列的哈希表实现。一个字符串被放入字符串表的时候,先检查一下表中有没有相同的字符串。如果有,则复用己有的字符串;没有则创建一个新的。碰到哈希值相同的字符串,简单的串在同一个哈希位的链表上即可。
创建一个lua字符串的函数如下:
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
GCObject *o;
unsigned int h = cast(unsigned int, l); /* seed */
size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */
size_t l1;
for (l1=l; l1>=step; l1-=step) /* compute hash */
h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
o != NULL;
o = o->gch.next) {
TString *ts = rawgco2ts(o);
if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
/* string may be dead */
if (isdead(G(L), o)) changewhite(o);
return ts;
}
}
return newlstr(L, str, l, h); /* not found */
}
Real-World Impact of Hash DoS in Lua 指出该哈希计算方法面临Dos攻击的风险,攻击者可以轻易构造出上千万拥有相同哈希值的不同字符串,以此数十倍的降低lua从外部压入字符串进入内部字符串表的效率。
Lua 5.2.1为了解决这个问题,把长字符串独立出来,长字符串不再通过哈希内部化进入全局字符串表。同时使用了一个随机种子用于哈希值的计算,使攻击者无法轻易构造出拥有相同哈希值的不同字符串。
userdata在储存形式上和字符串相同,可以看成是拥有独立元表,不被内部化处理,也不需要追加\0的字符串。在实现上,只是对象结构从TString换成了UData,所以实现代码也被放在lstring.c中,其api也以luaS开头。
Table
实现在ltable.c中。
Table类型定义如下:
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;
table的储存分为数组部分和哈希表部分。
数组部分在TValue *array
,数组大小是sizearray。
哈希表以闭散列方式实现,节点类型:
typedef struct Node {
TValue i_val;
TKey i_key;
} Node;
TKey相比TValue多了一个struct Node *next
成员,用以链接冲突的节点。
非dummynode哈希表的大小为2^lsizenode。
为了减少空表的维护成本,定义了一个不可改写的全局空哈希表dummynode,当以大小0初始化或resize哈希表时,node域指向这个dummy节点,此时lsizenode也为0。
云风在 一个链接 lua 引起的 bug , 事不过三 中描述了一个dummynode的问题,用NULL来替换dummynode或许可以更好的解决这个问题。
所以每个table结构,最多会由三块连续内存构成。一个Table结构,一块存放了连续整数索引的数组,和一块大小为2的整数次幂的哈希表。
lastfree最初指向node末尾,每当需要一个空闲节点时,就从lastfree倒着查找,如果lastfree到达node起始位置,说明空间已满,需要扩容了。
是不是所有key是正整数的节点一定在数组部分?
不是的,刚创建的空表数组部分长度为0,哈希表也为空,插入新元素时,如果key是数字但不在[1,sizearray]范围内,会往哈希表里插,如果发现哈希表没有空闲节点,便会执行rehash(),rehash()会依据一定规则(computesizes()函数,调整数组部分的大小使其利用率不小于50%),重新设置数组和哈希表的大小。
往哈希表中插入节点的流程可直接参考newkey()的注释:
/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
static TValue *newkey (lua_State *L, Table *t, const TValue *key);
table的长度定义只对序列表有效,所以在实现的时候,仅需要遍历数组部分。只有当数组部分填满时才需要进一步的去检索哈希表。
元表
实现在ltm.c中。
Lua实现复杂数据结构大量依赖给table附加一个元表(metatable)来实现,故而table本身的一大作用就是作为元表存在。但并非所有元表都提供了所有元方法,对于不存在的元方法查询就是一个浪费了。
在上面代码中,可以看到每个Table结构中都有一个fags域,它记录了那些元方法不存在,查询元方法时用于缓存查询结果:
const TValue *luaT_gettm (Table *events, TMS event, TString *ename) {
const TValue *tm = luaH_getstr(events, ename);
lua_assert(event <= TM_EQ);
if (ttisnil(tm)) { /* no tag method? */
events->flags |= cast_byte(1u<<event); /* cache this fact */
return NULL;
}
else return tm;
}
lua仅对table的元表做了这个优化,而没有理会其它类型的元表的元方法查询。这大概是因为只有table容易缺失一些诸如__index这样的元方法,而使用table的默认行为。当lua代码把这些操作作用于其它类型如userdata时,它没有table那样的默认行为,故对应的元方法通常存在。
参考
Lua 源码欣赏 云风
lua 5.1.4 源码