lua-1.1学习笔记

Lua 1.1 技术剖析报告个人代码学习文件地址written by Quirkybrain1. 环境搭建与编译运行1.1 编译与构建方式项目根目录提供了一个历史风格的构建脚本domake./domake它本质上只是导出当前目录为LUA环境变量然后调用顶层Makefile。顶层Makefile再分别进入以下三个子目录完成构建src/构建解释器核心库clients/lib/构建标准库clients/lua/构建命令行解释器1.2 现代 Linux / GCC 环境下的兼容问题与处理环境信息Ubuntu 24.04 LTS为了方便进行改动和测试本次修改每一层的 MakeFile 文件写出了路径的具体值可以直接调用顶层的 MakeFile。问题原因当前处理方式ar ruvl过时旧版静态库打包命令不适合现代工具链改为ar rcs旧式动态库构建方式不兼容过去的ld调用方式与现代平台差异较大改为$(CC) -shared -o $ $(OBJS)调试困难旧工程默认偏优化构建不利于定位问题改为CFLAGS -g -Wall -O0 -fPIC -I$(INC) $(DEFS)main返回类型过时现代 C 规范要求main返回intclients/lua/lua.c中改为int main(...)floatingpoint.h在现代系统不可用历史头文件已不再需要在clients/lib/iolib.c中移除stdin/stdout静态初始化不兼容宏/静态初始化方式在现代编译器下不稳定改为先声明in/out再在iolib_open()中赋值修改上述信息后可进行编译并生成 lua 的可执行文件。1.3 运行方式lua 解释器允许两种运行方式直接执行 Lua 文件./bin/lua test/save.lua交互式从标准输入读取脚本行./bin/lua print(hello world)2. 整体架构2.1 流程分析进入 main() 入口函数注册 clients/lib 文件夹中的标准库函数判断输入来源文件通过 lua_openfile 打开交互形式通过 lua_openstring 打开lex yylex 进行词法分析lua.stx 中 yyparce 进行语法分析生成字节码并且通过 lua_execute 进行执行创建数据tabel.c符号表、常量表、字符串表hash.clua 中的 tabel 数据类型对虚拟栈以及全局符号表进行 GC 标记并回收字符串和数组对象2.2 核心数据结构Object是 lua 中的对象结构对值的统一表示虚拟栈负责表达式求值、函数调用Hash是 lua 中 tabel 结构的底层实现的容器全局符号表、常量表、字符串表都是为 lua 解释器提供数据的3. 核心机制剖析3.1 动态数据类型实现lua 的动态类型实际是一个标签空间用于表示类型一个数值空间用于存储数据。Typeenum 用于表示当前的数据类型Valueunion 用同一块内存空间能够存储不同类型的数值Object一个数据对象本质是一个Type类型的tag标签与一个Value类型的value数值构成的 struct这种动态类型的设计带来了很大的方便与优势统一数值表示 (封装的思想)巧妙通过 union struct 的组合将 C 语言中不同的类型 (int,float,char*以及其它指针类型) 进行了封装对 lua 仅暴露了Objuct的简单类型接口。lua 解释器不需要再担心不同类型的区分与存储困难只需要通过tag进行区分放在栈中的是什么 lua 数值。是设计中的封装的思想。解释器识别类型在代码中大部分的判断都是对于tag标签的。例如算术运算会检查对象tag T_NUMBER字符串拼接需要对象是或者能转换成T_STRING类型tabel 进行索引操作需要被索引的对象是T_ARRAY类型函数的调用需要对象是T_CFUNCTION或T_FUNCTION类型由此可知 lua 中动态类型的识别只是在运行时判断了tag标签并没有很深奥的东西。T_MARK类型的作用lua 中很多栈都是采用了 C 中的数组在通过指针访问的时候很容易超出栈底造成内存不安全虚拟栈中压入了大量的数据和函数方法需要加以区分。对于这些问题引入了不对用户可见的T_MARK类型。主要用于栈底哨兵防止栈的超出函数调用时虚拟栈中的分隔参数边界的定位3.2 符号表、常量表、字符串表src/tabel.c中设计了三个关键的表用于辅助 lua 的正常运行。1. 全局符号表lua_table它保存所有全局变量及其当前值。初始化时解释器会预装入几个内建函数typetonumbernextnextvarprintdofiledostring之后clients/lua/lua.c中又会注册iolib、strlib、mathlib提供的更多标准库函数。查找全局变量时lua_findsymbol()额外维护了一个searchlist名字一旦被访问到就把对应节点移到链表前端从而加速后续访问。是一种对于访问速度的优化策略。2. 常量表lua_constant它保存编译期出现的字符串常量例如关键类型名number、string、table源码中的字符串字面量记录字段名词法分析阶段识别出字符串后会把字符串放入常量表并返回一个索引。后续字节码中并不直接嵌入完整字符串而是通过PUSHSTRING 常量索引的形式引用它。这样避免了相同字符串的重复创建。3. 字符串驻留表lua_string运行时动态产生的字符串不会随便散落在堆里而是统一交给lua_createstring()管理。运行机制先查字符串表看是否已有同内容字符串如果已有就释放新分配的副本直接复用旧指针如果没有就把它插入字符串表提高了底层数据管理的效率并且方便后续 GC 对于对象的管理3.3 GC 机制在lua_pack()中触发其流程非常清晰从 lua 虚拟栈出发标记对象从全局符号表出发继续标记对象回收未标记的字符串回收未标记的表清空本轮标记等待下一次 GC对于字符串的标记有一个设计字符串分配内存空间时前面会多预留一个位置作为 GC 标记位不暴露给普通字符串接口只会暴露给 GC 操作的函数。3.4 Table 结构的实现对比 C 语言lua 最独特的数据结构是 Table(表结构)其底层由src/hash.c实现其结构是Hash哈希表头记录桶数nhash、桶数组list、GC 标记markNode链表节点保存键ref、值val和下一节点next对于Node的设计源自于 Tabel 结构本质上是一个映射key - value所以每个节点需要ref键对象val值对象这里ref和val都是Object键和值本身也都拥有完整的动态类型信息。1. 冲突处理方式拉链法为了解决常见的哈希冲突lua 设计了哈希桶的结构将冲突的元素放入同一个桶中构成一个链表。2. 两类桶索引的计算支持两类键进行查找桶索引number直接取模string逐字符移位累加后取模这正好对应 lua Table 结构中里最常见的两类索引方式数组式索引t[1]字典式索引t[name]3. 本次修改的最大 bug 即对 Table 类型读写的分离历史版本的做法是查找失败时顺手创建一个值为 nil 的节点。这样做对写操作有帮助但对读操作是危险的因为“读一个不存在的键”应该只是返回一个空表示不存在但是创建 nil 节点会改变原来表的结构并且我们可以尝试运行以下脚本明白其危害-- 现代计算机内存大我们可以在终端进行限制可用内存的大小-- 通过如下命令进行限制-- ulimit -v 51200-- 再执行这个脚本就会在 i 1013538 时产生 not enough memory 的错误-- 这是由于不断读取不存在的节点lua 就会不断创建 nil 的僵尸节点而表一直被使用GC 无法识别并清除僵尸节点不断消耗堆内存直到占用完。bug_table{}print(开始执行恶意的不断读取操作...)i1dummy0while1dodummybug_table[i]ifi100000thenprint(已分配 10 万个无用的 nil 节点...)elseifi500000thenprint(已分配 50 万个无用的 nil 节点...)elseifi1000000thenprint(已分配 100 万个无用的 nil 节点...)elseifi1500000thenprint(已分配 150 万个无用的 nil 节点...)elseifi2000000thenprint(已分配 200 万个无用的 nil 节点...)elseifi3000000thenprint(已分配 300 万个无用的 nil 节点...)endii1end修改后已经把旧逻辑拆成两条路径路径当前接口行为只读查询lua_hashGet()找不到直接返回NULL不创建节点写入确保存在lua_hashEnsure()找不到就创建新节点4.next操作由于原来未修改的代码读写会创建 nil 节点并且部分操作会将节点改为 nil 节点对于这种没有意义的空值遍历时必须主动跳过这些节点否则就会把“逻辑上不存在的元素”又遍历出来。这也是firstnode()和lua_next()中大量判断tag(node-val) ! T_NIL的原因。虽然读写时候创建 nil 节点的 bug 已经被修改了但是 lua_next 函数还是保留了这种跳过的严谨操作。3.4 词法分析、语法分析和操作码生成lua 的分析会直接生成字节码1.lex.c把字符流切成 Tokenyylex()负责识别标识符与关键字数字字符串运算符注释$debug/$nodebug例如字符串字面量在识别后不会直接把内容塞进字节码而是会调用lua_findconstant()把它放进常量表再把常量索引交给语法分析器。2.lua.stx语法规则中直接发射字节码src/yacc/lua.stx承担两项职责描述 lua 语法在语法归约时生成字节码例如算术表达式的语义动作大致就是先编译左表达式再编译右表达式然后生成ADDOP、SUBOP等操作码控制流先用PrepJump预留跳转位置语句块编译完以后再用code_word_at()回填偏移量这是单遍编译器的典型写法边解析边生成边回填。3. 局部变量与临时值管理lua.stx里还维护了localvar[]局部变量表nlocalvar当前局部变量数量ntemp表达式求值过程中临时值的数量帮助生成字节码时准确知道某个名字是局部变量还是全局变量当前栈帧还剩多少空间是否需要插入ADJUST调整栈布局3.5 虚拟机执行lua_execute()的主循环解释器的最重要的部分位于src/opcode.c的lua_execute()。1. 栈式虚拟机lua 采用栈类型的虚拟机。大多数指令并不显式写出寄存器编号而是默认对栈顶附近的数据操作。这种设计的优点是指令格式简单编译器前端更容易生成代码缺点是当前栈不能出错调试时必须时刻跟踪top和base指针不然难以理解背后发生了什么2.top与base虚拟机维护两个最重要的指针top当前栈顶base当前函数调用帧的基址进入函数时base会移动到参数区退出函数时base再恢复到调用前的位置。会将返回地址旧的base参数局部变量临时值全部压在同一个对象栈里。3. 函数调用布局CALLFUNC的处理逻辑说明Lua 函数调用前的栈布局大致是函数对象 | T_MARK | 参数1 | 参数2 | ...进入 lua 函数后原来“函数对象”的位置会被写成返回地址原来T_MARK的位置会被写成旧base偏移base被移动到第一个参数因此这种调用操作是对栈空间的复用很类似于C 函数调用的地址操作。极大节省了空间占用但是设计上的细节就多了很多在阅读代码的时候也是一个难点。4. C 函数与 Lua 函数共用调用机制当CALLFUNC发现被调用对象是T_FUNCTION跳到 Lua 字节码继续执行T_CFUNCTION直接调用 C 函数指针5. 错误处理模式通过lua_reportbug()拼出带文件、函数、行号的信息最后调用lua_error()默认行为是向stderr输出消息4. 追踪解释器工作示例-- 示例代码print(12)1. 输入printfprint(12)\n|./bin/lua主程序clients/lua/lua.c会读取这一行然后调用lua_dostring()。2. 输入源注册lua_dostring()调用lua_openstring()记录当前描述设置输入函数为stringinput把行号重置为 13. 词法分析阶段yylex()会把print(12)切成 token 序列4. 语法分析与字节码生成PUSHGLOBAL print PUSHMARK PUSH1 PUSH2 ADDOP CALLFUNC ADJUST 0 HALT5. 虚拟机执行压入print压入T_MARK压入1压入2ADDOP后变成3CALLFUNC识别出print是T_CFUNCTIONlua_print()通过lua_getparam(1)读到参数3输出结果35. 已有修改与 Bug 复盘5.1 查询与创建逻辑分离(部分见 3.4.3 中分析)原问题旧逻辑中读取表元素和写入表元素共享同一个“查找或创建节点”的函数。这样一来查找不存在的节点时会悄悄插入 nil 节点到表里。当前修复当前源码中已经拆成lua_hashGet()只读查询lua_hashEnsure()写入前确保节点存在并且所有调用点也已经随之分流PUSHINDEXED、lua_getfield()、lua_getindexed()使用只读查询STOREINDEXED0、STOREINDEXED、STORELIST0、STORELIST、STORERECORD、lua_storefield()、lua_storeindexed()使用创建路径5.2 针对 test 文件中 save.lua 报错的修改原问题lua_pushstring()的 GC 时序段错误/** * brief 将 string 类型对象压入 lua stack。 * * return 压栈成功则返回 0压栈失败(lua stack 溢出)则返回 1。 * * warning bug使用 test.lua 文件中的 save.lua 触发段错误。 * 错误类型判断 * 时序错误。 * 错误原因分析 * 调用链(string 类型为例) * lua_type() - lua_pushstring() - * lua_createstring() - lua_pack() - * lua_markobject() * 在 lua_pushstring 函数中在栈创建了对象对 tag 进行了标记 * 压栈过程中触发了 GC然后 GC 扫栈时读到了一个 tag 已经是 T_STRING * 但字符串指针还没真正写好的半初始化对象 * 最后在 markstring(svalue(o)) 这里解引用野指针导致段错误。 * * 时序 * 理想情况下先进行赋值后指针上移动 * 所以赋值的时候这个对象并未压入栈中GC 扫描不到。 * 但是函数的赋值和 top 的完成顺序属于未定义行为 * 存在先完成 top (即完成压栈)再 GC 进行扫描导致崩溃的情况。 */intlua_pushstring(char*s){// lua stack 溢出if((top-stack)MAXSTACK-1){lua_error(stack overflow);return1;}char*str;strlua_createstring(lua_strdup(s));if(strNULL){return1;}tag(top)T_STRING;svalue(top)str;top;// tag(top) T_STRING;// svalue(top) lua_createstring(lua_strdup(s)); // 赋值并将栈顶指针(top)向上移动return0;}当前修复方式是先完整创建好字符串再把tag和svalue明确写入当前栈槽最后再执行top避免半初始化对象被 GC 看见。5.3 边界与栈安全修复1.stringinput()越界读取(见 details 对原逻辑注释)旧逻辑的读取顺序可能让指针先跨过字符串结尾再去访问数据存在越界风险。当前实现改为先检查/** * brief 输入源为字符串时读取字符。 * * details 先递增指向下一个位置再返回原位置 * st 先递增到 \0 之后的位置然后返回原位置的 \0。 * return 读取到的字符。 * warning 这个函数会导致字符串数组的访问越界行为 * 需要调用者确保内存安全。 * note 是否需要注意 st 为 Null 呢 * 如果追求安全可以先检查当前指针是否指向空字符。 */staticintstringinput(void){if(*st0)return0;// 修改了访问越界的 bug先检查当前指针是否指向空字符。st;return(*(st-1));}2.lua_pushnil()缺失top如果压入 nil 后不推进栈顶那么表面上“压栈成功”实际上栈状态没有变化会导致后续调用看到错误的栈布局。/** * brief 将 nil 类型对象压入 lua stack。 * * return 压栈成功则返回 0压栈失败(lua stack 溢出)则返回 1。 */intlua_pushnil(void){// lua stack 溢出if((top-stack)MAXSTACK-1){lua_error(stack overflow);return1;}// tag(top) T_NIL; // 这里可能是一个bug,没有进行toptag(top)T_NIL;return0;}3.lua_popfunction()的下溢保护函数信息栈如果在空栈状态下继续弹出就会发生下溢。/** * brief 将函数信息弹出 function stack。 * * 在执行 RESET 操作码的时候 * 将函数对应的文件的文件索引和函数名索引弹出 function stack。 * note 补充了下溢报错。 */voidlua_popfunction(void){if(nfuncstack0){lua_error(function stack underflow);nfuncstack0;return;}nfuncstack--;// 计数器自减}5.4 其余小问题1.lua_dostring()的失败路径清理旧逻辑中如果lua_parse()失败字符串输入源不会被关闭。/** * brief 执行 lua 脚本字符串。 * * 将给定的字符串作为 lua 代码解析并执行全局代码 * 执行结束后自动关闭字符串源头。 * * param string 脚本字符串。 * return 执行成功则返回 0执行失败则返回错误码 1。 * note 原版在此处发生错误时未释放内存现已修复。 */intlua_dostring(char*string){if(lua_openstring(string))return1;if(lua_parse()){lua_closestring();// 添加释放指向字符串源的指针return1;}lua_closestring();return0;}2.lua_closestring()置空st原代码只做文件栈弹出没有把字符串输入指针清空。这会带来悬空指针风险。/** * brief 关闭当前已打开的字符串输入源。 * * 该函数用于清理通过 lua_openstring 打开的字符串资源。 * warning 原来代码中仅有 lua_delfile 的调用 * 会导致 st 指针悬空造成误用。 */voidlua_closestring(void){if(st!NULL)// 为提高代码安全性将 st 指针置为 Null。{lua_delfile();// 将字符串弹出 file stackstNULL;}}3.lua_createstring()溢出后的释放如果字符串表在 GC 后仍然溢出旧版本会直接报错返回却没有释放传入的新字符串造成内存泄漏。/** * brief 创建新的字符串。 * * 先在字符串表进行查找如果已经存在了这个字符串释放传入的字符串 * 如果不存在先检查是否有溢出的危险或者触发 GC * 如果有则先进行垃圾回收并且检查是否还有溢出风险 * 如果有则返回 Null没有则将传入的字符串加入字符串表的结尾。 * * param s 已经分配了内存并带有标记位前缀的字符串。 * return 如果成功则返回唯一字符串指针如果失败则返回 Null。 * note 原版本在进行垃圾回收后如果字符串表仍然即将溢出没有释放字符串 s 的内存空间 * 调用 lua_createstring 的地方传入的 s 都是通过 calloc 分配的堆内存 * 加入表中也不手动释放就会导致内存失去跟踪。 */char*lua_createstring(char*s){inti;// 如果字符串为空则返回空if(sNULL)returnNULL;// 遍历字符串表查找是否已经存在for(i0;ilua_nstring;i)// 如果在表中找到这个字符串if(streq(s,lua_string[i])){// 释放传入的字符串 sfree(s-1);// 将存在的唯一字符串指针返回returnlua_string[i];}// 如果实例计数器到达阈值(触发GC)或者字符串表即将溢出if(lua_nentitylua_block||lua_nstringMAXSTRING-1){lua_pack();// 触发 GC// 如果字符串表仍然即将溢出if(lua_nstringMAXSTRING-1){// 抛出 lua_errorlua_error(string table overflow);free(s-1);// 原版本在这里会造成内存泄漏returnNULL;}}// 将传入的字符串加入字符串表的结尾并将字符串计数器自增lua_string[lua_nstring]s;lua_nentity;// 实例计数器自增returns;}4.lua_execute中NOTOP乱码执行以下代码anilprint(a)-- 正确得到 nilanotnilprint(a)-- 得到垃圾值当前修改// 逻辑非caseNOTOP:// 如果栈顶对象是 nil 类型(假)那么设置成 number 类型(真)不是 nil 则设置成 nil// tag(top-1) tag(top-1) T_NIL ? T_NUMBER : T_NIL;// 应该将 nil 反成数字 1 表示真而不是乱码if(tag(top-1)T_NIL){tag(top-1)T_NUMBER;nvalue(top-1)1;}else{tag(top-1)T_NIL;}break;修改后将not nil设置成 1, 与部分函数中的操作相同。收获从这次实践中我最大的收获是更具体地理解了lua 的动态类型在 C 中是如何落地的表为什么本质上是哈希表函数调用为什么最终会退化成栈布局操作垃圾回收为什么必须依赖对象可达性一个看似很小的时序错误为什么会在 GC 参与后变成段错误了解哈希表、链表、虚拟栈的运作等内容