Lua趣题分析¶
本文主要分析和讨论如下几个问题：
- 如何自己设计一个searcher（搜索器）？（搜索器函数原型为接收一个模块名为参数，返回加载器和模块绝对路径两个值）
- 在不关闭VM的情况下，如何触发Lua卸载动态加载库？（通过dlclose函数去卸载动态库）
- 是否table中还存在值为nil的槽就不会触发rehash？
- 针对table遍历过程对table进行增删改，如何构造这些情况：同一对key-value被扫描多次？某一对或某一些key-value没被遍历到？遍历过程找不到key而报错？（key为table自身原本拥有的，而不是随意构造一个不存在的key）
- 某个table在大量key置为nil之后，如何缩减该table自身所占用的内存空间？能否收缩到原始长度？
- 我们知道：通过”setmetatable({}, { __gc = function(o) setmetatable({}, getmetatable(o)) end })”这句代码，可以在一个析构过程构造另一个需要析构函数的无引用对象。我们还知道：通过lua_close关闭Lua虚拟机的时候，会调用所有对象的Finalizer进行析构。那么，Lua是如何避免在lua_close中陷入析构死循环呢？
设计一个searcher（搜索器）¶
package.searchers表中存放了自带的4个搜索器，搜索器函数原型为：
function searcher(modname)
-- do search
-- return errmsg
return loader, abspath
end
其中，loader为编译Lua源码而得到的闭包，abspath为Lua文件的绝对路径。搜索不到则返回错误字符串。
理解了搜索器函数原型的具体含义，写出一个可用的搜索器就很简单，如：
local modules = {
a = "return { a = 1 }",
b = "return { b = 2 }",
}
local function mysearcher(modname)
local modstr = modules[modname]
if modstr == nil then
return modname .. " not found in my modules"
end
return load(modstr), "mysearcher/" .. modname
end
local function insertsearcher(searcher)
table.insert(package.searchers, 1, searcher)
end
insertsearcher(mysearcher)
print(require("a").a) --> 1
print(require("b").b) --> 2
require("c") --> module 'c' not found:c not found in my modules
触发Lua卸载动态加载库¶
require函数在加载C语言形式的Lua模块时，支持动态加载共享库，针对Linux/MacOSX平台是使用dlopen系列API。Lua本身并没有直接提供相关函数来卸载这些动态库，仅在关闭整个虚拟机的时候通过gc的析构器一次性卸载所有动态库。（这么做主要是加载了动态库之后，Lua的某些table就会存在对动态库中函数的引用，错误的卸载动态库可能会导致后续函数库调用出现进程崩溃）
Lua将加载进来的动态库句柄都统一放在注册表中的一个特殊键中，因此，我们需要先添加新的函数来获取该key，函数为：debug.getspecialkeys()，返回一个table，其中的键“CLIBS”存放该特殊key。（debug.getspecialkeys()函数具体实现见此处）
手动模拟一次性卸载所有动态库的实现如下：
function dlcloseall()
-- TODO: Clear all c mod in package.loaded
local nclibs = {}
setmetatable(nclibs, getmetatable(debug.getregistry()[debug.getspecialkeys().CLIBS]))
debug.getregistry()[debug.getspecialkeys().CLIBS] = nclibs
collectgarbage()
end
卸载动态库的具体方式，其实是__gc原方法中做了dlclose，因此，我们可以直接调用该原方法来卸载单独的某个动态库：
function dlclose(path)
local clibs = debug.getregistry()[debug.getspecialkeys().CLIBS]
local handler = clibs[path]
if handler == nil then return end
clibs[path] = nil --> remove first reference
local targetkey = 0
for key = 1, #clibs, 1 do
if clibs[key] == handler then
targetkey = key
break
end
end
table.remove(clibs, targetkey) --> remove another reference
getmetatable(clibs).__gc({handler})
end
基于此dlclose函数，我们可以实现单独卸载某一个不需要的模块，并实现require的反向操作unrequire：
function dlclosemod(modname)
local path = package.searchpath(modname, package.cpath)
dlclose(path)
end
function unrequire(modname)
package.loaded[modname] = nil
dlclosemod(modname)
end
Lua本身还提供了package.loadlib用于手动加载动态库，我们可以直接使用这个函数来定向加载C语言模块：
function dlopenmod(modname)
local path = package.searchpath(modname, package.cpath)
return package.loadlib(path, string.format("luaopen_%s", modname))
end
比如，我们有libhello.so，并且其中注册的模块中有hellomod函数，那么单纯调用此hellomod函数可以这么做：
do
dlopenmod("libhello")("libhello", "abspath").hellomod()
dlclosemod("libhello")
end
或者通过require和unrequire函数：
do
require("libhello").hellomod()
unrequire("libhello")
end
table中存在值为nil的槽时触发rehash¶
针对问题：是否table中还存在值为nil的槽就不会触发rehash？这里先给出解答：只要将table中哈希部分的所有槽都写过一次，再构造一次哈希冲突，就可以触发rehash，即使是table中存在值为nil的槽。（使用过某个槽之后将其置为nil）
根据上述内容，可以推导出：
- table中不存在值为nil的槽 ==> 该table是满的（该table中哈希部分的所有槽都至少写过一次）
- table是满的意味着任何一个新key的写入操作都会造成哈希冲突，从而触发rehash
- 触发rehash的时候，table中可以存在值为nil的槽
简单分析可得出如下结论：
- table中不存在值为nil的槽，下一个新key插入一定会触发rehash
- table中存在值为nil的槽，下一个新key插入有可能触发rehash
- table中并非所有槽都写过一次，下一个新key插入一定不会触发rehash
因此，“table中不存在值为nil的槽”是“下一个新key插入会触发rehash”的充分不必要条件。
table自身所占用的存储空间只会在rehash过程发生变化，也就是说，“table自身存储空间发生变化”是“table发生了rehash”的充分不必要条件。我开发debug.tablemem(t)函数用于获取table自身占用内存空间的大小，该函数返回四个字段：table占用内存大小、数组部分长度、以 2 为底哈希表部分长度的对数、哈希表部分是否为假节点。（debug.tablemem函数具体实现见此处）
构造哈希冲突有很多种方式，比较简单的两种是通过整数形式的key和字符串形式的key。根据table自身内存设计形式，我们可以清楚的知道table中数组部分和哈希表部分的大小，Lua针对整数放到哈希部分的下标索引是直接将整数对哈希部分长度的取模（哈希部分长度为8，则7和15这两个key存在哈希冲突），针对字符串的哈希值计算则可能存在空洞（字符串长度大于等于32则并不是所有字符都参与哈希值的计算）。
比如以下两个长度为32的字符串，就会发生哈希冲突：
local str1 = "axaxaxaxaxaxaxaxaxaxaxaxaxaxaxax" -- string.rep("ax", 16)
local str2 = "bxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbx" -- string.rep("bx", 16)
相关测试代码如下：(64位系统)
local tbl = {
a = 1,
b = 1,
c = 1,
d = 1,
e = 1,
f = 1,
g = 1,
h = 1,
}
print(debug.tablemem(tbl)) --> 312 0 3 false
for k, v in pairs(tbl) do tbl[k] = nil end
tbl[7] = true
for k, v in pairs(tbl) do print(k, v) end --> 7 true
print(debug.tablemem(tbl)) --> 312 0 3 false
tbl[15] = true --> fire rehash
for k, v in pairs(tbl) do print(k, v) end --> print two key-value
print(debug.tablemem(tbl)) --> 120 0 1 false
执行 tbl[15] = true 会触发rehash，此时tbl中仅有一个key-value，存在着多个value为nil的槽。
构造table遍历过程的几种情况¶
table遍历过程对其进行增删改，主要有以下三种异常情况：
- 同一对key-value被扫描多次
- 某一对或某一些key-value没被扫描到
- 遍历过程找不到key而报错（key为table自身原本拥有的，而不是随意构造一个不存在的key）
遍历异常是由table的rehash导致的，因此构造这三种情况，也需要利用一下rehash。
通过pairs/next扫描table的时候，会先扫描数组部分，因此，某一对key-value被扫描多次，可先放到数组部分被扫描一次，再通过rehash将其转移到哈希表部分并再次被扫描到。
do
local tbl = {
1,2,3,4,5,6,7,8,
a=1,b=2,c=3,d=4,
}
for i = 1, 6, 1 do tbl[i] = nil end --> after rehash, 7 and 8 will come to hash part
for k,v in pairs(tbl) do
if k == 8 then
tbl.e = 5 --> fire rehash
end
print(k,v)
end
end
针对哈希部分长度为8的情况，key为8的mainposition在第一个槽，key为7的mainposition在最后一个槽，因此可以保证key为7的key-value会被扫描两次。
有了上述经验，我们很容易构造出某些key-value不被扫描到的情况：
do
local tbl = {
1,2,3,4,5,6,7,8,
a=1,b=2,c=3,d=4,
}
for i = 1, 6, 1 do tbl[i] = nil end --> after rehash, 7 and 8 will come to hash part
for k,v in pairs(tbl) do
if k == 7 then
tbl.e = 5 --> fire rehash
end
print(k,v)
end
end
针对哈希部分长度为8的情况，key为7的mainposition在最后一个槽，在扫描到还在数组部分的7时，我们触发rehash，7被安排到哈希表部分的最后一个槽，因此就直接扫描结束了，key为8和key为字符串的所有key-value都被跳过。
要构造遍历过程找不到key而报错，我们只需要多做一步，将对应值置为nil，触发rehash的时候该key就不见了，稳定报错：
do
local tbl = {
1,2,3,4,
a=1,b=2,
}
for i = 1, 3, 1 do tbl[i] = nil end --> after rehash, 4 will come to hash part
for k,v in pairs(tbl) do
if k == 4 then
tbl[4] = nil --> remove it
tbl.c = 3 --> fire rehash
end
print(k,v)
end
end
缩减table自身占用的内存空间¶
table自身内存空间包括了三部分：
- Table结构体
- 数组部分
- 哈希表部分
Table结构体不可变，可变的只有数组部分和哈希表部分，这两个可变部分在初始化之后，就只会在rehash过程发生变化，因此，缩减table自身空间需要一些技巧。
我们可以通过两次rehash来缩减table自身的内存空间，第一次rehash将所有key-value转移到数组部分去，第二次rehash则缩减数组长度。
local tbl = {}
print(debug.tablemem(tbl)) --> 56 0 0 true
tbl[1] = "Good"
tbl.h1 = "hello"
tbl.h2 = "hello"
tbl.h3 = "hello"
tbl.h4 = "hello"
tbl.h5 = "hello"
tbl.h6 = "hello"
tbl.h7 = "hello"
tbl.h8 = "hello"
print(debug.tablemem(tbl)) --> 328 1 3 false
tbl.h1 = nil
tbl.h2 = nil
tbl.h3 = nil
tbl.h4 = nil
tbl.h5 = nil
tbl.h6 = nil
tbl.h7 = nil
tbl.h8 = nil
for k, v in pairs(tbl) do print(k, v) end --> 1 Good
print(debug.tablemem(tbl)) --> 328 1 3 false
tbl[2] = 1
tbl[3] = 1
tbl[4] = 1
tbl[5] = 1
tbl[6] = 1
tbl[7] = 1
tbl[8] = 1
tbl[9] = 1 -- every integer key should be hashed to different slot
print(debug.tablemem(tbl)) --> 328 1 3 false
tbl[10] = "Good" -- fire the rehash
print("rehash:", debug.tablemem(tbl)) --> rehash: 312 16 0 true
for i=1,10 do tbl[i]=nil end --> remove all key-value
tbl[""] = nil --> fire the second rehash
print("second rehash:", debug.tablemem(tbl)) --> second rehash: 88 0 0 false
根据代码打印出来的数据，我们可以发现，一个空table的大小是56字节（64位系统，Table结构体的大小），经过一顿操作之后，table被使用，其大小便无法缩减为56字节了，顶多是缩减到88字节（Table的56字节+哈希部分一个槽32字节）。当然，这种强行缩减table自身占用内存空间在实际使用中意义不大，我们总是会在不需要的时候直接丢弃该table，需要的时候再构造一个新的。深入研究此缩减方式仅仅是加强我们对于table底层实现的认识。
避免lua_close中陷入析构死循环¶
我们知道：通过”setmetatable({}, { __gc = function(o) setmetatable({}, getmetatable(o)) end })”这句代码，可以在一个析构过程构造另一个需要析构函数的无引用对象。我们还知道：通过lua_close关闭Lua虚拟机的时候，会调用所有对象的Finalizer进行析构。那么，Lua是如何避免在lua_close中陷入析构死循环呢？
对于这个问题的分析，主要划分为如下三个小问题：
- setmetatable函数中，对带有析构器的对象是如何处理的？
- 垃圾收集过程是如何调用析构器的？
- lua_close函数内部执行析构函数和释放所有对象内存的顺序是怎样的？
setmetatable相关逻辑：
- 全局表中的setmetatable函数底层是通过lua_setmetatable函数实现的
- Lua5.3.5实现的lua_setmetatable中，针对Table和Userdata，会调用一个luaC_checkfinalizer函数
- luaC_checkfinalizer函数中会检查该元表是否存在__gc字段，如果存在，则将该对象从g->allgc取出并放入g->finobj
- 由于检查__gc字段是在setmetatable过程进行的，因此该字段必须在setmetatable之前设置好，否则不生效
GC过程的相关逻辑：
- atomic阶段会调用separatetobefnz函数，作用是将g->finobj链表中的所有已经dead对象放入g->tobefnz链表，并复活这些对象
- callfin阶段依次调用这些对象的析构器，并将其放入g->allgc链表中（每次setmetatable之后，__gc析构器只生效一次）
lua_close实现中关于清理所有对象的流程：（lgc.c文件中的luaC_freeallobjects函数）
- 将g->finobj链表中的所有对象放入g->tobefnz链表中（操作之后g->finobj链表为空）
- 调用g->tobefnz链表中所有对象的析构器
- 释放g->finobj链表的所有对象（这一步存在的必要性在于释放析构器新构造出来的带有析构器的对象）
- 释放g->allgc链表的所有对象
- 释放g->fixedgc链表的所有对象
有了这些理解，我们可以得到结论：lua_close函数释放所有对象的过程中，只做一次析构器的调用，对于析构器所创建的带有析构器的对象，则直接做释放而不调用其析构器，这样就避开了析构死循环。
总结¶
Lua中包含了许多有趣的实现细节：
- 优雅的判断当前环境大小端模式
- 针对ASCII字符高效的大小写互转
- 通过三次翻转来旋转数组
- 类浮点形式的单字节整数表示法，局部降低精度扩大表示范围
- 开散列实现全局字符串表和闭散列实现table的哈希部分
- …
Lua语言的官方实现细节，是不可多得的优秀学习资料，有待我们更多的去发掘和发现。