Lua Source——字符串

内容简介：Lua Source——字符串

博文内容基于云风前辈的readinglua中对 lua 的源码讲解，本人对lua源码的理解尚浅，所以笔记部分主要是对思路的梳理，以及书中简单带过的地方加以自己的实践，从而加深自己的理解。文中有误的地方望读者指出，原书的pdf文章末尾我也做了链接，有需要的人可以自己下载。

Lua虚拟机对象很容易创建，并且不同的虚拟机之间工作是线程安全的，与虚拟机相关的内存操作都被关联到虚拟机对象中，而没有利用其它的共享变量。

虚拟机的核心部分没有任何系统调用，是纯粹的黑盒，所有正确地使用Lua，不会对系统造成任何干扰。Lua让用户自己定义内存管理器，在创建Lua时传入，保证了Lua的整个运行状态是用户可控的。

字符串

Lua中的字符串可以包含任意的8位字符，包括了 C语言 中标示字符串结束的\0。它以带长度的内存块 的形式在内部保存字符串，同时在和C语言做交互时，又能保证在每个内部储存的字符串末尾添加\0以兼容C库函数。

Lua内部的字符串类型为LUA_TSTRING，宏定义在lua.h头文件里面。

#define LUA_TSTRING        4

具体的结构定义是在lobject.h里面。

/*
** Header for string value; string bytes follow the end of this structure
*/
typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
    unsigned int hash;
    size_t len;  /* number of characters in string */
  } tsv;
} TString;

CommonHeader用于GC，extra用于记录字符串是否为保留字（用于词法分析器对保留字的快速判断，对于长字符串，用于惰性求哈希值），hash用来加快字符串的匹配和查找，len域用来记录字符串的长度（Lua并不是以\0结尾来记录字符串的长度）。

字符串的数据内容并没有分配一块独立的内存来保存，而是直接加载TString结构的末尾，所以用lobject.h里面getstr这个宏就可以得到实际的C字符串指针。

/* get the actual string (array of bytes) from a TString */
#define getstr(ts)    cast(const char *, (ts) + 1)

Lua 5.2.1之后，字符串保存在Lua状态机内有两种内部形式，短字符串和长字符串。

/* 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的实现，不可以设置少于10。

/*
@@ 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

下面我们来看新建一个字符串时，Lua内部是如何运转的。

/*
** new zero-terminated string
*/
TString *luaS_new (lua_State *L, const char *str) {
  return luaS_newlstr(L, str, strlen(str));
}

/*
** 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 {
    if (l + 1 > (MAX_SIZET - sizeof(TString))/sizeof(char))
      luaM_toobig(L);
    return createstrobj(L, str, l, LUA_TLNGSTR, G(L)->seed, NULL);
  }
}

首先根据LUAI_MAXSHORTLEN区分长短字符串，短字符串计算Hash值，经过内部化存放在全局的字符串表中；如果是长字符串，则直接调用创建字符串的接口。

值得注意的是，在Lua 5.2.0之前，字符串是不分长短一律内部化以后存放在字符串表里面的。

对于长字符串，为了加快内部化的过程，计算长字符串哈希值是跳跃进行的。下面是Lua 5.2.0中的字符串哈希值计算代码：

unsigned int luaS_hash(const char *str, size_t l)
{
unsigned int h = (unsigned int)l;
size_t step = (l >> 5) + 1;
size_t l1;
for(l1 = l; l1 >= step; l1 -= step)
    h = h ^ ((h<<5)+(h>>2)+(unsigned char)str[l1-1]);
return h;
}

Lua 5.2.0发布后不久，有人在邮件列表中提出，Lua的这个设计有可能对其给于Hash DoS攻击的机会。攻击者可以轻易构造出上千万拥有相同哈希值的不同字符串，以此数十倍的降低Lua从外部压入字符串进入内部字符串表的效率。当Lua用于大量依赖字符串处理的诸如HTTP服务的处理时，输入的字符串不可控制，很容易被人恶意利用。

Lua 5.2.1为了解决这个问题，把长字符串独立出来。大量文本处理中的输入的字符串不再通过哈希内部化进入全局字符串表。同时，使用了一个随机种子用于哈希值的计算，使攻击者无法轻易构造出拥有相同哈希值的不同字符串。

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;
}

这个随机种子是在Lua State创建时放在全局表中的，它利用了构造状态机的内存地址随机性以及用户可配置的一个随机量同时来决定。

/*
** 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

/*
** Compute an initial seed as random as possible. In ANSI, 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);
}

下面我们细看下短字符串的内部化过程。

/*
** Union of all collectable objects
*/
union GCObject {
  GCheader gch;  /* common header */
  union TString ts;
  union Udata u;
  union Closure cl;
  struct Table h;
  struct Proto p;
  struct UpVal uv;
  struct lua_State th;  /* thread */
};

#define gch(o)        (&(o)->gch)

/*
** 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

/*
** Common header in struct form
*/
typedef struct GCheader {
  CommonHeader;
} GCheader;

typedef struct stringtable {
  GCObject **hash;
  lu_int32 nuse;  /* number of elements */
  int size;
} stringtable;

/*
** 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) {
  GCObject *o;
  global_State *g = G(L);
  unsigned int h = luaS_hash(str, l, g->seed);
  for (o = g->strt.hash[lmod(h, g->strt.size)];
       o != NULL;
       o = gch(o)->next) {
    TString *ts = rawgco2ts(o);
    if (h == ts->tsv.hash &&
        l == ts->tsv.len &&
        (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
      if (isdead(G(L), o))  /* string is dead (but was not collected yet)? */
        changewhite(o);  /* resurrect it */
      return ts;
    }
  }
  return newshrstr(L, str, l, h);  /* not found; create a new string */
}

/*
** creates a new short string, inserting it into string table
*/
static TString *newshrstr (lua_State *L, const char *str, size_t l, unsigned int h) {
  GCObject **list;  /* (pointer to) list where it will be inserted */
  stringtable *tb = &G(L)->strt;
  TString *s;
  if (tb->nuse >= cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
    luaS_resize(L, tb->size*2);  /* too crowded */
  list = &tb->hash[lmod(h, tb->size)];
  s = createstrobj(L, str, l, LUA_TSHRSTR, h, list);
  tb->nuse++;
  return s;
}

/*
** creates a new string object
*/
static TString *createstrobj (lua_State *L, const char *str, size_t l, int tag, unsigned int h, GCObject **list) {
  TString *ts;
  size_t totalsize;  /* total size of TString object */
  totalsize = sizeof(TString) + ((l + 1) * sizeof(char));
  ts = &luaC_newobj(L, tag, totalsize, list, 0)->ts;
  ts->tsv.len = l;
  ts->tsv.hash = h;
  ts->tsv.extra = 0;
  memcpy(ts+1, str, l*sizeof(char));
  ((char *)(ts+1))[l] = '\0';  /* ending 0 */
  return ts;
}

这是一个开散列的哈希表实现。一个字符串被放入字符串表的时候，先检查一下表中有没有相同的字符串。如果有，则复用已有的字符串；没有则创建一个新的。碰到哈希值相同的字符串，简单的串在同一个哈希位的链表上即可。

过程中需要检查表中的字符串是否是死掉的字符串。这是因为Lua的垃圾收集过程是分步完成的。而向字符串池添加新字符串在任何步骤之间都可能发生。 有可能在标记完字符串后发现有些字符串没有任何引用，但在下个步骤中又产生了相同的字符串导致这个字符串复活。

当哈希表中字符串的数量(nuse域)超过预定容量(size 域)时。可以预计hash冲突必然发生。这个时候就调用luaS_resize方法把字符串表的哈希链表数组扩大，重新排列所有字符串的位置。

在Lua状态机内部创建字符串，都会按C风格字符串存放，以兼容C接口。 即在字符串的末尾加上一个\0。这样不违背Lua自己用内存块加长度的方式储存字符串的规则，在把Lua字符串传递出去和C语言做交互时，又不必做额外的转换。

比较两个字符串是否相同，首先区分长短字符串。子类型不同自然不是相同的字符串。长字符串比较，当长度不同时，自然是不同的字符串，而长度相同时，则需要逐字节比较。短字符串因为经过的内部化，所以不必比较字符串内容，而仅需要比较对象地址即可。Lua用一个宏来高效的实现它

/*
** equality for long strings
*/
int luaS_eqlngstr (TString *a, TString *b) {
  size_t len = a->tsv.len;
  lua_assert(a->tsv.tt == LUA_TLNGSTR && b->tsv.tt == LUA_TLNGSTR);
  return (a == b) ||  /* same instance or... */
    ((len == b->tsv.len) &&  /* equal length and ... */
     (memcmp(getstr(a), getstr(b), len) == 0));  /* equal contents */
}

/*
** equality for strings
*/
int luaS_eqstr (TString *a, TString *b) {
  return (a->tsv.tt == b->tsv.tt) &&
         (a->tsv.tt == LUA_TSHRSTR ? eqshrstr(a, b) : luaS_eqlngstr(a, b));
}

/*
** equality for short strings, which are always    internalized
*/
#define eqshrstr(a,b)    check_exp((a)->tsv.tt == LUA_TSHRSTR, (a) == (b))

Userdata在Lua中并没有太特别的地方，在储存形式上和字符串相同。可以看成是拥有独立元表，不被内部化处理，也不需要追加\0的字符串。在实现上，只是对象结构从TString换成了UData。所以实现代码也被放在lstring.c中，其api也以luaS开头。数据部分和字符串一样，紧接在这个结构后面，并没有单独分配内存。

/*
** Header for userdata; memory area follows the end of this structure
*/
typedef union Udata {
  L_Umaxalign dummy;  /* ensures maximum alignment for `local' udata */
  struct {
    CommonHeader;
    struct Table *metatable;
    struct Table *env;
    size_t len;  /* number of bytes */
  } uv;
} Udata;

Udata *luaS_newudata (lua_State *L, size_t s, Table *e) {
  Udata *u;
  if (s > MAX_SIZET - sizeof(Udata))
    luaM_toobig(L);
  u = &luaC_newobj(L, LUA_TUSERDATA, sizeof(Udata) + s, NULL, 0)->u;
  u->uv.len = s;
  u->uv.metatable = NULL;
  u->uv.env = e;
  return u;
}

PS:

1、位运算技巧

// 反码求最大值
#define MAX_SIZET    ((size_t)(~(size_t)0)-2)

/*
** `module' operation for hashing (size is always a power of 2)
*/
// size大小是2的整数次幂，所以模运算只需要对size-1进行与运算
#define lmod(s,size) \
(check_exp((size&(size-1))==0, (cast(int, (s) & ((size)-1)))))

readinglua

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• 查找一个字符串中最长不含重复字符的子字符串，计算该最长子字符串的长度
• 字符串、字符处理总结
• 高频算法面试题（字符串）leetcode 387. 字符串中的第一个唯一字符
• php删除字符串最后一个字符
• （三）C语言之字符串与字符串函数
• 算法笔记字符串处理问题H：编排字符串（2064）

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。