Lua代码阅读(2) 数据结构

根据http://lua.javaeye.com/blog/492260的推荐,第二部分应该是阅读lapi.c也就是C语言扩展时使用的函数,比如LUA_API int lua_error (lua_State *L),这类函数都是以LUA_API开头(LUA_API根据编译环境不同表现为__declspec(dllexport)或__declspec(dllimport)或者extern。

可是很多数据结构必须展示出来了,比如lua_State是什么?所以先做一个铺垫,看看这些数据结构的定义。具体它们的使用,我也是需要一步步深入学习以后才会知道,这篇文字只是个草稿,还需要根据以后的理解不断修订。

lstate.h定义了lua中最重要也最常用的一个数据结构lua_State。

/*
** `per thread’ state
*/
struct lua_State {
  CommonHeader;
  lu_byte status;
  StkId top;  /* first free slot in the stack *//*当前栈的第一个空闲槽*/
  StkId base;  /* base of current function *//*当前函数栈的基地址*/
  global_State *l_G;
  CallInfo *ci;  /* call info for current function */
  const Instruction *savedpc;  /* `savedpc’ of current function */
  StkId stack_last;  /* last free slot in the stack */
  StkId stack;  /* stack base */
  CallInfo *end_ci;  /* points after end of ci array*/
  CallInfo *base_ci;  /* array of CallInfo’s */
  int stacksize;
  int size_ci;  /* size of array `base_ci’ */
  unsigned short nCcalls;  /* number of nested C calls */
  unsigned short baseCcalls;  /* nested C calls when resuming coroutine */
  lu_byte hookmask;
  lu_byte allowhook;
  int basehookcount;
  int hookcount;
  lua_Hook hook;
  TValue l_gt;  /* table of globals */
  TValue env;  /* temporary place for environments */
  GCObject *openupval;  /* list of open upvalues in this stack */
  GCObject *gclist;
  struct lua_longjmp *errorJmp;  /* current error recover point */
  ptrdiff_t errfunc;  /* current error handling function (stack index) */
};

第一个成员为CommonHeader,它其实是一个宏定义,里面包含三个成员变量。注释说明是可以使用在所有可收集对象,可以包含在其他对象中。其中的marked跟GC机制有关,与luaC_white()这个函数经常同时使用。

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

还有另外一个结构其实跟它一样的,只不过是以结构(struct)形式表现:

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

lu_byte就是typedef unsigned char lu_byte。

top和base的类型为StkId,从名字上看跟stack元素非常密切。

typedef TValue *StkId;  /* index to stack elements */

#define TValuefields    Value value; int tt

typedef struct lua_TValue {
  TValuefields;
} TValue;

TValue结构包含了value和tt,而GCheader也有一个tt,从名字上暂时看不出用处。

而value的定义如下,从注释来看,是所有lua可能值的联合(union)。

/*
** Union of all Lua values
*/
typedef union {
  GCObject *gc;
  void *p;
  lua_Number n;
  int b;
} Value;

另外一个重要的对象就是GCObject

union GCObject {
  GCheader gch;
  union TString ts;
  union Udata u;
  union Closure cl;
  struct Table h;
  struct Proto p;
  struct UpVal uv;
  struct lua_State th;  /* thread */
};

gch已经介绍过,TString定义如下,里面比较值得注意的是有一个hash以及len。

/*
** String headers for string table
*/
typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;
    unsigned int hash;
    size_t len;
  } tsv;
} TString;

另外一个重要的数据类型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来说,在The implementation of lua 5.0这样说明:

在Lua5.0 中,对表被用作数组的情形使用了一种新的算法来进行优化:对于键是整数的表项,将不保存键,只将值存入一个真正的数组中。更准确地说,在Lua5.0 中,表以一种混合型数据结构来实现,它包含一个散列表部分和一个数组部分。

image

我们可以从这个函数中看出table两种数据的操作。一般来说对于table的操作都是成对出现的,比如setarrayvector操作值类型数组,setnodevector操作key-value对。

/*
** clear collected entries from weaktables
*/
static void cleartable (GCObject *l) {
  while (l) {
    Table *h = gco2h(l);

    int i = h->sizearray;
    lua_assert(testbit(h->marked, VALUEWEAKBIT) ||
               testbit(h->marked, KEYWEAKBIT));

    if (testbit(h->marked, VALUEWEAKBIT)) {
      while (i–) {
        TValue *o = &h->array[i]; // 先是循环操作array
        if (iscleared(o, 0))  /* value was collected? */
          setnilvalue(o);  /* remove value */
      }
    }

    i = sizenode(h); 
    while (i–) {
      Node *n = gnode(h, i); // 然后循环操作node
      if (!ttisnil(gval(n)) &&  /* non-empty entry? */
          (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
        setnilvalue(gval(n));  /* remove value … */
        removeentry(n);  /* remove entry from table */
      }
    }

    l = h->gclist;
  }
}

————————————————

在Table数据结构中,Node包含了TValue和TKey两个成员。

typedef union TKey {
  struct {
    TValuefields;
    struct Node *next;  /* for chaining */
  } nk;
  TValue tvk;
} TKey;

typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

在the implementation of lua 5.0中文版中是这样说明key和value对的:

  Lua 将值表示成带标志的联合结构,即,(t,v)对,其中t 是个整数,代表值v 的类型,v 是一个C 语言union 类型数据结构,它存储有实际的值。
  nil 型只有单个值。boolean 和number 实现为未包装的值:v 直接对应于union 中由t指示的域。这意味着union 必须有足够空间容纳一个double 型。string,table,function,thread 和userdata 型数据通过引用来实现:v 中含有一个指向结构的指针,该结构实现由t 指定的类型。
  这些结构共用一个头结构,头结构中含有垃圾回收所需的信息。结构的剩余部分包含的信息对应于指定的数据类型。

先走马观花看了这些数据结构,其他的用到再提。

关于lua_State,它的初始化函数是lua_newstate,每个c语言扩展lua都需要调用lua_open,其实就是luaL_newstate的别名。

LUALIB_API lua_State *luaL_newstate (void) {
  lua_State *L = lua_newstate(l_alloc, NULL);
  if (L) lua_atpanic(L, &panic);
  return L;
}

可以看出默认的内存分配函数都是l_alloc。
下面是我注释的代码。

LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
  int i;
  lua_State *L;
  global_State *g;
  // 调用alloc函数,分配L以及g的内存。
  void *l = (*f)(ud, NULL, 0, state_size(LG));
  if (l == NULL)
      return NULL;

  // LUAI_EXTRASPACE 可以让用户可以扩展lua_State,现在为0.
  L = ((lua_State*)( (lu_byte*)l + LUAI_EXTRASPACE );
  // 全局state指针指向所分配的内存。
  g = &((LG *)L)->g;
  L->next = NULL;
  // 定义L的类型为thread?
  L->tt = LUA_TTHREAD;
  // GC状态初始化。
  g->currentwhite = bit2mask(WHITE0BIT, FIXEDBIT);
  L->marked = luaC_white(g);
  set2bits(L->marked, FIXEDBIT, SFIXEDBIT);

  // 初始化L的状态,关联L和g。
  preinit_state(L, g);
  // 设置全局state的内存分配函数
  g->frealloc = f;
  // ud默认为NULL
  g->ud = ud;
  g->mainthread = L;
  g->uvhead.u.l.prev = &g->uvhead;
  g->uvhead.u.l.next = &g->uvhead;
  g->GCthreshold = 0;  /* mark it as unfinished state */
  g->strt.size = 0;
  g->strt.nuse = 0;
  g->strt.hash = NULL;
  setnilvalue(registry(L));
  luaZ_initbuffer(L, &g->buff);
  g->panic = NULL;
  g->gcstate = GCSpause;
  g->rootgc = obj2gco(L);
  g->sweepstrgc = 0;
  g->sweepgc = &g->rootgc;
  g->gray = NULL;
  g->grayagain = NULL;
  g->weak = NULL;
  g->tmudata = NULL;
  g->totalbytes = sizeof(LG);
  g->gcpause = LUAI_GCPAUSE;
  g->gcstepmul = LUAI_GCMUL;
  g->gcdept = 0;
  for (i=0; i<NUM_TAGS; i++)
      g->mt[i] = NULL;

  // 运行f_luaopen命令
  if (luaD_rawrunprotected(L, f_luaopen, NULL) != 0) {
    /* memory allocation error: free partial state *//*出错了,关闭state*/
    close_state(L);
    L = NULL;
  }
  else
    luai_userstateopen(L);
  return L;
}

另外比较值得一提的是luaD_rawrunprotected,当我们正常运行的时候,也是使用这个函数。

/*
** open parts that may cause memory-allocation errors
*/
static void f_luaopen (lua_State *L, void *ud) {
    // 通过G(L)得到全局state
  global_State *g = G(L);
  UNUSED(ud);
  stack_init(L, L);  /* init stack */
  sethvalue(L, gt(L), luaH_new(L, 0, 2));  /* table of globals */
  sethvalue(L, registry(L), luaH_new(L, 0, 2));  /* registry */
  luaS_resize(L, MINSTRTABSIZE);  /* initial size of string table */
  luaT_init(L);
  luaX_init(L);
  luaS_fix(luaS_newliteral(L, MEMERRMSG));
  g->GCthreshold = 4*g->totalbytes;
}

其中的stack_init会调用luaM_newvector,它会间接调用全局state中的内存分配函数:
block = (*g->frealloc)(g->ud, block, osize, nsize);
BASIC_CI_SIZE为8,LUA_MINSTACK为20,BASIC_STACK_SIZE为40(2*LUA_MINSTACK),而EXTRA_STACK为5。

static void stack_init (lua_State *L1, lua_State *L) {
  /* initialize CallInfo array */
  L1->base_ci = luaM_newvector(L, BASIC_CI_SIZE, CallInfo);
  L1->ci = L1->base_ci;
  L1->size_ci = BASIC_CI_SIZE;
  L1->end_ci = L1->base_ci + L1->size_ci – 1;
  /* initialize stack array */
  L1->stack = luaM_newvector(L, BASIC_STACK_SIZE + EXTRA_STACK, TValue);
  L1->stacksize = BASIC_STACK_SIZE + EXTRA_STACK;
  L1->top = L1->stack;
  L1->stack_last = L1->stack+(L1->stacksize – EXTRA_STACK)-1;
  /* initialize first ci */
  L1->ci->func = L1->top;
  setnilvalue(L1->top++);  /* `function’ entry for this `ci’ */
  L1->base = L1->ci->base = L1->top;
  L1->ci->top = L1->top + LUA_MINSTACK;
}

————————————

我们在lua_newstate上加一个断点,看看它运行起来的状态,为了方便起见,我们修改lua project的命令行为c:\test.lua,里面只有两行代码"local str = ‘aabbcc’ "和"print(str)"。

可以看到lua_newstate在main函数中被调用,在Smain这个结构中保存了程序的参数。

int main (int argc, char **argv) {
  int status;
  struct Smain s;
  lua_State *L = lua_open();  /* create state */
  if (L == NULL) {
    l_message(argv[0], "cannot create state: not enough memory");
    return EXIT_FAILURE;
  }
  s.argc = argc;
  s.argv = argv;
  status = lua_cpcall(L, &pmain, &s);
  report(L, status);
  lua_close(L);
  return (status || s.status) ? EXIT_FAILURE : EXIT_SUCCESS;
}

当lua_newstate运行完毕,global_state的状态如下图。

image

而lua_State的状态如下图。

image

前面做的分析基本上等于没有,只是为了熟悉一下这些数据类型。下一篇要阅读的是lapi.c。

发表评论