Lua5.4.3源码剖析01-字符串实现

全面梳理字符串在Lua虚拟机中的实现,以便以后查阅,也分享给我的朋友们。本笔记的内容是解析源码(lstring.c);说明字符串在虚拟机的具体实现,首先说明字符串管理器的结构以及初始化,这个管理器管理虚拟机中创建的所有常规字符串(相对长字符串类型),然后讲述调用接口(luaS_newlstr)创建字符串;创建字符串时要为这个字符串在管理器哈希表中确定一个位置;创建字符串时有可能引发字符串管理器的扩容和缩小,最后因为引入了长字符串,那么在创建字符串时要考虑长字符串类型的管理。

1. 字符串管理器

1.1 字符串管理结构

typedef struct stringtable {
  TString **hash;   //这个地方直接从GCObject改成了TString,与GC的结构更改有关
  int nuse;         //hash表中的元素实际数量
  int size;         //hash表的数组长度
} stringtable;

1.2 初始化函数

void luaS_init (lua_State *L) {
  // stringtable表是存在global_State结构的strt中.
  // 所有虚拟机共用global_State
  global_State *g = G(L);
  int i, j;
  stringtable *tb = &G(L)->strt;
  // hash表数组初始化为MINSTRTABSIZE(128)长度
  tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*);
  tablerehash(tb->hash, 0, MINSTRTABSIZE);  /* clear array */
  tb->size = MINSTRTABSIZE;
  // 初始化所有长度的Cache,为默认字符串MEMERRMSG(not enghou memory)
  // STRCACHE_N(53)
  g->memerrmsg = luaS_newliteral(L, MEMERRMSG);
  luaC_fix(L, obj2gco(g->memerrmsg));  /* it should never be collected */
  for (i = 0; i < STRCACHE_N; i++)  /* fill cache with valid strings */
    for (j = 0; j < STRCACHE_M; j++)
      g->strcache[i][j] = g->memerrmsg;
}

2. 字符串的创建

2.1 核心哈希算法

unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
  // hash的初始种子来源于global_State结构的seed
  // 这个是为了防止字符串的反编译
  // 这里要注意的是hash的循环跟长度正相关,所以长字符串的hash尤其耗时
  unsigned int h = seed ^ cast_uint(l);
  for (; l > 0; l--)
    h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
  return h;
}

unsigned int luaS_hashlongstr (TString *ts) {
  // 这个函数的hash值是用在table中的key位置
  // 使用extra标记是因为这个hash的过程耗时
  // hash过程使用了ts->hash实际就是g->seed
  lua_assert(ts->tt == LUA_VLNGSTR);
  if (ts->extra == 0) {  /* no hash? */
    size_t len = ts->u.lnglen;
    ts->hash = luaS_hash(getstr(ts), len, ts->hash);
    ts->extra = 1;  /* now it has its hash */
  }
  return ts->hash;
}

2.2 创建字符串接口

TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  // 小于LUAI_MAXSHORTLEN(40)时创建常规字符串
  // 保存在字符串哈希表中,调用internshrstr实现
  if (l <= LUAI_MAXSHORTLEN)  /* short string? */
    return internshrstr(L, str, l);
  else {
    // 长字符串的创建有一次memcpy
    TString *ts;
    if (l_unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char)))
      luaM_toobig(L);
    // 长字符串类型是LUA_VLNGSTR
    ts = luaS_createlngstrobj(L, l);
    memcpy(getstr(ts), str, l * sizeof(char));
    return ts;
  }
}

2.3 创建的核心函数

static TString *internshrstr (lua_State *L, const char *str, size_t l) {
  TString *ts;
  global_State *g = G(L);
  stringtable *tb = &g->strt;
  // 之前的哈希函数已说明
  unsigned int h = luaS_hash(str, l, g->seed);
  // 找到字符串所在哈希表位置
  // 因为存在碰撞的可能所以要逐一比较
  // 找到字符串时直接返回
  TString **list = &tb->hash[lmod(h, tb->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 */
      return ts;
    }
  }
  // 没有找到字符串需要重新生成一个新的字符串
  // 这里nuse >= size是说第一次size默认初始化值为128
  // 元素数量大于表长度.具体参见growstrtab说明
  if (tb->nuse >= tb->size) {  /* need to grow string table? */
    growstrtab(L, tb);
    list = &tb->hash[lmod(h, tb->size)];  /* rehash with new size */
  }
  // 这里是实际创建字符串
  // 默认的字符串类型是LUA_VSHRSTR
  ts = createstrobj(L, l, LUA_VSHRSTR, h);
  memcpy(getstr(ts), str, l * sizeof(char));
  ts->shrlen = cast_byte(l);
  // 碰撞处理,把原有字符串链接到当前字符串后面
  ts->u.hnext = *list;
  *list = ts;
  // 增加元素数量
  tb->nuse++;
  return ts;
}

2.4 长字符串创建

TString *luaS_createlngstrobj (lua_State *L, size_t l) {
  // 这里和上面创建常规的字符串调用同一个接口,只是类型不同
  // 这里类型为 LUA_VLNGSTR
  TString *ts = createstrobj(L, l, LUA_VLNGSTR, G(L)->seed);
  ts->u.lnglen = l;
  return ts;
}

3. 字符串表扩展

触发哈希字符串表空间扩展是在哈希表中元素大于表的长度时,调用growstrtab函数

3.1 扩展接口

static void growstrtab (lua_State *L, stringtable *tb) {
  // 当元素等于最大值时强制gc回收
  if (l_unlikely(tb->nuse == MAX_INT)) {  /* too many strings? */
    luaC_fullgc(L, 1);  /* try to free some... */
    if (tb->nuse == MAX_INT)  /* still too many? */
      luaM_error(L);  /* cannot even create a message... */
  }
  // MAXSTRTB = MAX_INT / sizeof(TString*)
  // 这里说明只要元素数量大于元素表长度
  // 并且空间小于最大值的一半时允许扩展空间
  if (tb->size <= MAXSTRTB / 2)  /* can grow string table? */
    luaS_resize(L, tb->size * 2);//参见下面的注释
}

3.2 扩展实现

void luaS_resize (lua_State *L, int nsize) {
  stringtable *tb = &G(L)->strt;
  int osize = tb->size;
  TString **newvect;
  // 当目标长度小于现有长度时可能要缩小哈希字符串表
  if (nsize < osize)  /* shrinking table? */
    tablerehash(tb->hash, osize, nsize);  // 参见后面的注释
  newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*);
  if (l_unlikely(newvect == NULL)) {  /* reallocation failed? */
    // 这里是扩展失败的情况就不处理并还原原来的hash表长度
    if (nsize < osize)  /* was it shrinking table? */
      tablerehash(tb->hash, nsize, osize);  /* restore to original size */
    /* leave table as it was */
  }
  else {  /* allocation succeeded */
    // 扩展哈希表长度的处理
    tb->hash = newvect;
    tb->size = nsize;
    if (nsize > osize)
      tablerehash(newvect, osize, nsize);  /* rehash for new size */
  }
}

3.3 重新哈希位置

static void tablerehash (TString **vect, int osize, int nsize) {
  int i;
  // 如果是缩小空间时把大于的部分置空
  for (i = osize; i < nsize; i++)  /* clear new elements */
    vect[i] = NULL;
  // 逐个根据哈希表中的字符串重新哈希定位
  // 这里要注意的问题是重新哈希位置时使用的hash值还是原来的哈希值
  // 重新哈希跟元素的数量正相关
  for (i = 0; i < osize; i++) {  /* rehash old part of the array */
    TString *p = vect[i];
    vect[i] = NULL;
    // 这里对这个节点的每个元素进行处理
    while (p) {  /* for each string in the list */
      // 首先保存下一个元素
      TString *hnext = p->u.hnext;  /* save next */
      // 处理当前元素哈希到新的位置
      unsigned int h = lmod(p->hash, nsize);  /* new position */
      p->u.hnext = vect[h];  /* chain it into array */
      vect[h] = p;
      // 处理下一个节点元素
      p = hnext;
    }
  }
}

总结与Lua5.1.4的区别

1. 重新resize的策略发生变化,hash表默认长度为MINSTRTABSIZE(128),当元素数量大于128时size称指数扩展,当元素数量等于MAX_INT时做一次gc回收多余的字符串空间,空间小于最大值的一半时允许扩展空间;缩小空间时只是置空交由GC去负责回收。
2. luaS_new增加了字符串的指针的cache,主要提供给虚拟机api使用,内部仍然使用luaS_newlstr函数.
3. 增加了一个大字符串类型,小于LUAI_MAXSHORTLEN(40)长度默认是LUA_VSHRSTR类型,长字符串类型为LUA_VLNGSTR