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

lua字符串

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

       本文内容基于版本:Lua 5.3.0


       Lua字符串中的合法字符可以是任何的1字节数据,这包括了C语言中表示字符串结束的'\0'字符,也就是说Lua字符串在内部将以带长度的内存块的形式存储,存储的是二进制数据,解释器遇到'\0'字符并不会截断数据。同时在和C语言交互时,Lua又能保证为每个内部储存的字符串末尾添加'\0'字符以兼容C库函数,这使得Lua的字符串应用范围相当广泛。

       Lua字符串一旦被创建,就不可被改写。Lua的值对象若为字符串类型,则它将以引用方式存在。字符串对象属于需要被垃圾收集器管理的对象,也就是说一个字符串一旦没有被任何地方引用就可以回收它。

       Lua管理及操作字符串的方式和C语言不太相同,通过阅读其实现代码,可以加深对Lua字符串的理解,从而能更为高效的使用它。

TString结构


• TString结构的声明

       Lua字符串对应的C结构为TString,该类型定义在lobject.h中。

// lobject.h
/*
** 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

// lobject.h
/*
** 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 */
  unsigned int hash;
  size_t len;  /* number of characters in string */
  struct TString *hnext;  /* linked list for hash table */
} TString;

       CommonHeader : 用于GC的信息。

       extra : 用于记录辅助信息。对于短字符串,该字段用来标记字符串是否为保留字,用于词法分析器中对保留字的快速判断;对于长字符串,该字段将用于惰性求哈希值的策略(第一次用到才进行哈希)。

       hash : 记录字符串的hash值,可以用来加快字符串的匹配和查找。

       len : 由于Lua并不以'\0'字符结尾来识别字符串的长度,因此需要一个len域来记录其长度。

       hnext : hash table中相同hash值的字符串将串成一个列表,hnext域为指向下一个列表节点的指针。

TString存储结构图

       Lua字符串的数据内容部分并未分配独立的内存来存储,而是直接追加在TString结构的后面TString存储结构如下图:

      

         Lua字符串对象 = TString结构 + 实际字符串数据
        • TString结构 = GCObject *指针 + 字符串信息数据

短字符串和长字符串


• 长短字符串的划分

       字符串将以两种内部形式保存在lua_State中:短字符串及长字符串。Lua中每个基本内建类型都对应了一个宏定义,其中字符串类型对应于LUA_TSTRING宏定义。对于长短字符串,Lua在LUA_TSTRING宏上扩展了两个小类型LUA_TSHRSTRLUA_TLNGSTR,这两个类型在类型字节高四位存放0和1加以区别。这两个小类型为内部使用,不为外部API所见,因此对于最终用户来说,他们只见到LUA_TSTRING一种类型。

// lua.h
/*
** 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

#define LUA_NUMTAGS           9

// lobject.h
/* Variant tags for strings */
#define LUA_TSHRSTR    (LUA_TSTRING | (0 << 4))  /* short strings */
#define LUA_TLNGSTR    (LUA_TSTRING | (1 << 4))  /* long strings */

       长短字符串的界限是由定义在luaconf.h中的宏LUAI_MAXSHORTLEN来决定的,其默认设置为40(字节)。在Lua的设计中,元方法名和保留字必须是短字符串,所以短字符串长度不得短于最长的元方法__newindex和保留字function的长度,也就是说LUAI_MAXSHORTLEN最小不可以设置低于10(字节)。

// luaconf.h
/*
@@ LUAI_MAXSHORTLEN is the maximum length for short strings, that is, ** strings that are internalized. (Cannot be smaller than reserved words ** or tags for metamethods, as these strings must be internalized; ** #("function") = 8, #("__newindex") = 10.) */ #define LUAI_MAXSHORTLEN 40

• 字符串创建的函数调用图

      

       抛开短字符串的内部化过程来看,创建字符串最终调用的都是createstrobj函数,该函数创建一个可被GC管理的对象,并将字符串内容拷贝到其中。

// lgc.c
/*
** 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;
  // 放入GC对象列表
o
->next = g->allgc; g->allgc = o; return o; } // lstring.c /* ** creates a new string object */ static TString *createstrobj (lua_State *L, const char *str, size_t l, int tag, unsigned int h) { TString *ts; GCObject *o; size_t totalsize; /* total size of TString object */ totalsize = sizelstring(l); o = luaC_newobj(L, tag, totalsize); ts = gco2ts(o); ts->len = l; ts->hash = h; ts->extra = 0; memcpy(getaddrstr(ts), str, l * sizeof(char)); getaddrstr(ts)[l] = '\0'; /* ending 0 */ return ts; }

字符串的哈希算法


• 哈希算法

       Lua中字符串的哈希算法可以在luaS_hash函数中查看到。对于比较长的字符串(32字节以上),为了加快哈希过程,计算字符串哈希值是跳跃进行的。跳跃的步长(step)是由LUAI_HASHLIMIT宏控制的。

// lstring.c
/*
** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to
** compute its hash
*/
#if !defined(LUAI_HASHLIMIT)
#define LUAI_HASHLIMIT        5
#endif

// lstring.h
LUAI_FUNC unsigned int luaS_hash (const char *str, size_t l, unsigned int seed);

// lstring.c
unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
  unsigned int h = seed ^ cast(unsigned int, l);
  size_t l1;
  size_t step = (l >> LUAI_HASHLIMIT) + 1;
  for (l1 = l; l1 >= step; l1 -= step)
    h = h ^ ((h<<5) + (h>>2) + cast_byte(str[l1 - 1]));
  return h;
}

       • str   : 待哈希的字符串;

       • l    : 待哈希的字符串长度(字符数);

       • seed  : 哈希算法随机种子;

• 随机种子

       Hash DoS攻击:攻击者构造出上千万个拥有相同哈希值的不同字符串,用来数十倍地降低Lua从外部压入字符串到内部字符串表的效率。当Lua用于大量依赖字符串处理的服务(例如HTTP)的处理时,输入的字符串将不可控制, 很容易被人恶意利用 。

       为了防止Hash DoS攻击的发生,Lua一方面将长字符串独立出来,大文本的输入字符串将不再通过哈希内部化进入全局字符串表中;另一方面使用一个随机种子用于字符串哈希值的计算,使得攻击者无法轻易构造出拥有相同哈希值的不同字符串

       随机种子是在创建虚拟机的global_State(全局状态机)时构造并存储在global_State中的。随机种子也是使用luaS_hash函数生成,它利用内存地址随机性以及一个用户可配置的一个随机量(luai_makeseed宏)同时来决定。

       用户可以在luaconf.h中配置luai_makeseed来定义自己的随机方法,Lua默认是利用time函数获取系统当前时间来构造随机种子。luai_makeseed的默认行为有可能给调试带来一些困扰: 由于字符串hash值的不同,程序每次运行过程中的内部布局将有一些细微变化,不过字符串池使用的是开散列算法, 这个影响将非常小。如果用户希望让嵌入Lua的程序每次运行都严格一致,那么可以自定义luai_makeseed函数来实现。

// lstate.c
/*
** a macro to help the creation of a unique random seed when a state is
** created; the seed is used to randomize hashes.
*/
#if !defined(luai_makeseed)
#include <time.h>
#define luai_makeseed()        cast(unsigned int, time(NULL))
#endif

// lstate.c
/*
** Compute an initial seed as random as possible. Rely on Address Space
** Layout Randomization (if present) to increase randomness..
*/
#define addbuff(b,p,e) \
  { size_t t = cast(size_t, e); \
    memcpy(buff + p, &t, sizeof(t)); p += sizeof(t); }

static unsigned int makeseed (lua_State *L) {
  char buff[4 * sizeof(size_t)];
  unsigned int h = luai_makeseed();
  int p = 0;
  addbuff(buff, p, L);  /* heap variable */
  addbuff(buff, p, &h);  /* local variable */
  addbuff(buff, p, luaO_nilobject);  /* global variable */
  addbuff(buff, p, &lua_newstate);  /* public function */
  lua_assert(p == sizeof(buff));
  return luaS_hash(buff, p, h);
}

// lstate.c
LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
  int i;
  lua_State *L;
  global_State *g;
  LG *l = cast(LG *, (*f)(ud, NULL, LUA_TTHREAD, sizeof(LG)));
  if (l == NULL) return NULL;
  L = &l->l.l;
  g = &l->g;
  ......
  g->seed = makeseed(L);
  ......
  return L;
}

 短字符串的内部化


       Lua中所有的短字符串均被存放在全局状态表(global_State)的strt域中,strtstringtable的简写,它是一个哈希表。

       相同的短字符串在同一个lua_State中将只存在唯一一份实例,这被称为字符串的内部化。合并相同的字符串可以大量减少内存占用,缩短比较字符串的时间。由于相同的字符串只需要保存一份在内存中,当用这个字符串做键匹配时,比较字符串只需要比较地址是否相同就够了,而不必逐字节比较。下面将着重对stringtable进行分析。

• stringtable结构类型

// lstate.h
typedef struct stringtable {
  TString **hash;
  int nuse;  /* number of elements */
  int size;
} stringtable;

       • hash  : 字符串开散列算法哈希表,hash是一维数组指针,其中数组元素类型为TString *(指向TString类型对象指针),它并不是一个二维数组(数组元素类型为TString)指针;

       • nuse  : 字符串表当前字符串数量;

       • size : 字符串表最大字符串数量;

• stringtable存储结构图

• 短字符串内部化(散列过程描述)

       首先求得传入短字符串的哈希值,然后将该哈希值与stringtable大小取模,从而得到该字符串在stringtable中存放位置(相同哈希值的字符串链表);接着从该字符串链表的第一个位置开始,将链表中每个字符串与传入字符串比较字符串内容,如果相等说明传入字符串已经在表中使用;如果不相等说明不是同一个字符串,继续往后查找。如果字符串链表中都没有查找到,那么需要创建一个新的字符串。创建过程中,碰到哈希值相同的字符串,简单地串在同一个哈希位的链表上即可。简单地用一句话描述开散列的哈希过程:传入字符串被放入字符串表的时候,先检查一下表中有没有相同的字符串,如果有则复用已有的字符串,如果没有则创建一个新的字符串

       由于Lua的垃圾回收过程是分步完成的, 而向stringtable添加新字符串在垃圾回收的任何步骤之间都可能发生,所以这个过程中需要检查表中的字符串是否已经死掉(标记为可垃圾回收):有可能在标记完字符串死掉后, 在下个步骤中又产生了相同的字符串导致这个字符串复活。

// lstring.c
/*
** 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);   // 找到目标位置字符串链表
TString
**list = &g->strt.hash[lmod(h, g->strt.size)];   // 在字符串链表搜索传入字符串
for (ts = *list; ts != NULL; ts = ts->hnext) { if (l == ts->len && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) { /* found! */ if (isdead(g, ts)) /* dead (but not collected yet)? */ changewhite(ts); /* resurrect it */ return ts; } } if (g->strt.nuse >= g->strt.size && g->strt.size <= MAX_INT/2) { luaS_resize(L, g->strt.size * 2); list = &g->strt.hash[lmod(h, g->strt.size)]; /* recompute with new size */ } // 没有找到创建新的字符串
ts
= createstrobj(L, str, l, LUA_TSHRSTR, h); ts->hnext = *list; *list = ts; g->strt.nuse++; return ts; }

 • stringtable的扩大及字符串的重新哈希

       当stringtable中的字符串数量(stringtable.muse域)超过预定容量(stringtable.size域)时,说明stringtable太拥挤,许多字符串可能都哈希到同一个维度中去,这将会降低stringtable的遍历效率。这个时候需要调用luaS_resize方法将stringtable的哈希链表数组扩大,重新排列所有字符串的位置。

// lstring.h
LUAI_FUNC void luaS_resize (lua_State *L, int newsize);

// lstring.c
/*
** resizes the string table
*/
void luaS_resize (lua_State *L, int newsize) {
  int i;
  // 取得全局stringtable
stringtable
*tb = &G(L)->strt; if (newsize > tb->size) { /* grow table if needed */   // 如果stringtable的新容量大于旧容量,重新分配
luaM_reallocvector
(L, tb
->hash, tb->size, newsize, TString *); for (i = tb->size; i < newsize; i++) tb->hash[i] = NULL; } // 根据新容量进行重新哈希
for (i = 0; i < tb->size; i++) { /* rehash */ TString *p = tb->hash[i]; tb->hash[i] = NULL; // 将每个哈希链表中的元素哈希到新的位置(头插法)
while (p) { /* for each node in the list */ TString *hnext = p->hnext; /* save next */ unsigned int h = lmod(p->hash, newsize); /* new position */ p->hnext = tb->hash[h]; /* chain it */ tb->hash[h] = p; p = hnext; } } // 如果stringtable的新容量小于旧容量,那么要减小表的长度
if (newsize < tb->size) { /* shrink table if needed */ /* vanishing slice should be empty */ lua_assert(tb->hash[newsize] == NULL && tb->hash[tb->size - 1] == NULL); luaM_reallocvector(L, tb->hash, tb->size, newsize, TString *); } tb->size = newsize; }

        stringtable初始大小由宏MINSTRTABSIZE控制,默认是64,用户可以在luaconf.h重新定义MINSTRTABSIZE宏来改变默认大小。在为stringtable初次分配空间的时候,调用的也是luaS_resize方法,将stringtable空间由0调整到MINSTRTABSIZE的大小。

// llimits.h
/* minimum size for the string table (must be power of 2) */
#if !defined(MINSTRTABSIZE)
#define MINSTRTABSIZE    64    /* minimum size for "predefined" strings */
#endif

// lstate.c
/*
** open parts of the state that may cause memory-allocation errors.
** ('g->version' != NULL flags that the state was completely build)
*/
static void f_luaopen (lua_State *L, void *ud) {
  global_State *g = G(L);
  UNUSED(ud);
  stack_init(L, L);  /* init stack */
  init_registry(L, g);
  luaS_resize(L, MINSTRTABSIZE);  /* initial size of string table */
  ...
}

// lstate.c
LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
  int i;
  lua_State *L;
  global_State *g;
  LG *l = cast(LG *, (*f)(ud, NULL, LUA_TTHREAD, sizeof(LG)));
  if (l == NULL) return NULL;
  L = &l->l.l;
  g = &l->g;
  ...
  g->strt.size = g->strt.nuse = 0;
  g->strt.hash = NULL;

...
if (luaD_rawrunprotected(L, f_luaopen, NULL) != LUA_OK) { /* memory allocation error: free partial state */ close_state(L); L = NULL; } return L; }

        stringtable在字符串内部化的过程中扩大的策略和STL中的vector比较类似:当空间不足时,大小扩大为当前空间的两倍大小。

// lstring.c
/*
** 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);
  
                      

鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
基于CClosure实现lua访问C++对象成员发布时间:2022-07-22
下一篇:
(二)Lua脚本语言入门发布时间: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