Lua中如何實現類似gdb的斷點調試–05優化斷點資訊數據結構
在上一篇04優化鉤子事件處理中，我們在鉤子函數中引入了call和return事件的處理，對性能進行了優化。
細心的同學可能已經發現了，我們的hook函數中call事件和line都需要對整個斷點表進行遍歷，這其中其實是存在著一些冗餘的。因為call事件只關心函數是否有斷點，而line事件則只關心本函數內有哪些斷點。所以我們可以想辦法優化一下斷點資訊的數據結構，進一步提升性能。
源碼已經上傳Github，歡迎watch/star😘。
本部落格已遷移至CatBro’s Blog，那裡是我自己搭建的個人部落格，歡迎關注。
實現分析
原來的斷點表status.bptable是以斷點id為鍵的數組，我們需要通過斷點id來快速刪除斷點，所以status.bptable表還是保留。
但是在鉤子函數中，我們並不關心斷點的id，相反我們關心斷點屬於哪個函數。只有當程式執行到有斷點的函數時，我們才需要處理line事件。所以，很自然地可以想到，我們應該新增一個以函數為鍵的斷點表。我們把這個新表定義如下：
status.funcbpt = {} -- 以函數為鍵的斷點表
那麼新表的值應該是什麼呢？因為一個函數中可能有多個斷點，而在line事件中我們又需要比較當前行是否是斷點行，所以我們把新表status.funcbpt的值也設計成一個表，該表的鍵是斷點行號，值為斷點id。因為斷點行號並不連續，所以status.funcbpt[func]表不是一個序列，為了快速獲取斷點個數，我們在表中額外加了一個特殊的num欄位保存該函數中的斷點個數。
這樣我們就可以在call事件中快速地判斷當前函數是否有斷點，在line事件中快速地判斷當前行是否是斷點行。
另外，之所以將斷點id作為status.funcbpt[func]表的值，則是為了保留從status.funcbpt訪問status.bptable中對應斷點的能力（status.bptable表中元素因為包含了func和line欄位，所以也可以訪問到status.funcbpt對應斷點）。
這麼說可能不直觀，我們來看個例子。
假設我們的bptable表中func函數添加了兩個斷點如下：
bptable[1] = {func = func, line = 10}
bptable[2] = {func = func, line = 20}
對應的在funcbpt表中的操作如下：
funcbpt[func] = {} -- 構造表
funcbpt[func][10] = 1 -- 函數func，行號10，斷點id為1
funcbpt[func].num = 1 -- 該函數第一個斷點
funcbpt[func][20] = 2 -- 函數func，行號20，斷點id為2
funcbpt[func].num = funcbpt[func].num + 1 -- 斷點個數+1
OK，理清楚了status.funcbpt的數據結構設計，實現起來就簡單了。
添加斷點
我們先從設置斷點函數入手修改程式碼。新增的程式碼已經用中括弧括起來了，有兩個部分。其中前面的部分先根據函數和行號檢查是否已經設置過同一個斷點了，如果是的話，直接返回之前設置的斷點id。
後面的部分，在斷點保存到s.bptable表之後，也要保存到我們新增的表s.funcbpt表中，行號line作為鍵，新斷點id作為值。如果設置的是該函數的第一個斷點，需要先進行表的初始化構造，所以操作稍有不同。
local function setbreakpoint(func, line)
local s = status
if type(func) ~= "function" or type(line) ~= "number" then
return nil
end
[[ 新增程式碼開始 ]]
-- 已經設置了相同的斷點
if s.funcbpt[func] and s.funcbpt[func][line] then
return s.funcbpt[func][line]
end
[[ 新增程式碼結束 ]]
s.bpid = s.bpid + 1
s.bpnum = s.bpnum + 1
s.bptable[s.bpid] = {func = func, line = line}
[[ 新增程式碼開始 ]]
if s.funcbpt[func] then -- 該函數已經有斷點了
s.funcbpt[func].num = s.funcbpt[func].num + 1
s.funcbpt[func][line] = s.bpid
else -- 該函數第一個斷點
s.funcbpt[func] = {}
s.funcbpt[func].num = 1
s.funcbpt[func][line] = s.bpid
end
[[ 新增程式碼結束 ]]
if s.bpnum == 1 then -- 全局第一個斷點
debug.sethook(hook, "c") -- 設置鉤子"call"事件
end
return s.bpid --> 返回斷點id
end
刪除斷點
相應地，在刪除斷點的時候，我們也需要把s.funcbpt表中對應的斷點刪除。首先根據斷點id，從s.bptable表中獲取到斷點的函數和行號，從而找到s.funcbpt表中對應的斷點。現將斷點個數減1，然後將對應斷點刪除（防止後續line事件找到該斷點）。如果該函數已經沒有斷點了，那麼將s.funcbpt[func]表本身也刪除（防止後續call事件以為該函數還有斷點）。
local function removebreakpoint(id)
local s = status
if s.bptable[id] == nil then
return
end
[[ 新增程式碼開始 ]]
local func = s.bptable[id].func
local line = s.bptable[id].line
s.funcbpt[func].num = s.funcbpt[func].num - 1
s.funcbpt[func][line] = nil
if s.funcbpt[func].num == 0 then
s.funcbpt[func] = nil
end
[[ 新增程式碼結束 ]]
s.bptable[id] = nil
s.bpnum = s.bpnum - 1
if s.bpnum == 0 then
debug.sethook() -- 移除鉤子
end
end
鉤子函數
然後來修改鉤子函數的處理，鉤子的函數的修改主要有兩處，分別是call事件和line事件。我們先來看call事件的修改：
local function hook (event, line)
local s = status
if event == "call" or event == "tail call" then
local func = debug.getinfo(2, "f").func
- for _, v in pairs(s.bptable) do
- -- found breakpoint in current function
- if v.func == func then
- if event == "call" then
- s.stackdepth = s.stackdepth + 1
- end
- s.stackinfos[s.stackdepth] =
- {func = func, hasbreak = true}
- debug.sethook(hook, "crl") -- 添加"line"事件
- return
- end
- end
- -- 沒有斷點
- if event == "call" then
+ if event == "call" then -- 對於尾調用,直接覆蓋
s.stackdepth = s.stackdepth + 1
end
- s.stackinfos[s.stackdepth] = {func = func, hasbreak = false}
- debug.sethook(hook, "cr") -- 去掉"line"事件
+ -- found breakpoint in current function
+ if s.funcbpt[func] then
+ s.stackinfos[s.stackdepth] = {func = func, hasbreak = true}
+ debug.sethook(hook, "crl") -- 添加"line"事件
+ else -- no breakpoints found
+ s.stackinfos[s.stackdepth] = {func = func, hasbreak = false}
+ debug.sethook(hook, "cr") -- 去掉"line"事件
+ end
elseif event == "return" or event == "tail return" then
主要的改動就是從原本的遍歷s.bptable表來查找是否有斷點，改成了直接通過檢查s.funcbpt[func]是否不為nil來判斷是否有斷點。這裡直接從遍歷一個表，優化成了一個查表操作。
第二處是line事件的修改，下面是修改前的程式碼：
-- 省略
elseif event == "line" then
for _, v in pairs(s.bptable) do
if v.func == s.stackinfos[s.stackdepth].func
and v.line == line then
if not s.funcinfos[v.func] then
s.funcinfos[v.func] = debug.getinfo(2, "nS")
end
local info = s.funcinfos[v.func]
local prompt = string.format("%s (%s)%s %s:%d\n",
info.what, info.namewhat, info.name, info.short_src, line)
io.write(prompt)
debug.debug()
end
end
end
-- 省略
下面是修改後的程式碼，除了增加了一些局部變數簡化程式碼之外，也是將原本的遍歷s.bptable表來判斷當前行是否是斷點行，改成了直接通過檢查s.funcbpt[curfunc][line]是否不為nil來判斷當前行是否是斷點行。這裡也將遍歷一個表的動作，優化成了一個查表操作。
elseif event == "line" then
local curfunc = s.stackinfos[s.stackdepth].func
local funcbp = s.funcbpt[curfunc]
assert(funcbp)
if funcbp[line] then
if not s.funcinfos[curfunc] then
s.funcinfos[curfunc] = debug.getinfo(2, "nS")
end
local info = s.funcinfos[curfunc]
local prompt = string.format("%s (%s)%s %s:%d\n",
info.what, info.namewhat, info.name, info.short_src, line)
io.write(prompt)
debug.debug()
end
end
複雜度分析
我們仍然假設程式碼執行的總行數為L，斷點數N=n*b，其中n為有斷點的函數個數，b為平均每個函數的斷點數，斷點所在函數平均行數為l，斷點所在函數平均調用次數為c，總的函數調用次數C。
完全沒優化前複雜度為O(L*N)，上一篇的事件處理優化後的複雜度為O(C*N+c*l*N)，而本篇的數據結構優化之後複雜度進一步縮小為O(C+c*l)。
測試多函數多斷點
先來測試一下修改之後斷點功能是否正常，編寫一個測試腳本如下。我們對foo函數和bar函數分別添加了兩個斷點，其中foo函數第一個斷點添加了兩次用於測試重複添加的情況。
local ldb = require "luadebug"
local setbp = ldb.setbreakpoint
local rmbp = ldb.removebreakpoint
pv = ldb.printvarvalue
sv = ldb.setvarvalue
ptb = ldb.printtraceback
local function foo ()
local a = 1
end
local function bar ()
local b = 1
end
local id1 = setbp(foo, 9)
assert(id1 == 1)
local id1 = setbp(foo, 9)
assert(id1 == 1)
local id2 = setbp(foo, 10)
local id3 = setbp(bar, 13)
local id4 = setbp(bar, 14)
foo()
bar()
rmbp(id1)
rmbp(id2)
rmbp(id3)
rmbp(id4)
foo()
bar()
運行腳本，4個斷點情況都能正常跑到。刪除斷點後再調用foo和bar函數，不再碰到斷點。
$ lua test.lua
Lua (local)foo test.lua:9
lua_debug> cont
Lua (local)foo test.lua:10
lua_debug> cont
Lua (local)bar test.lua:13
lua_debug> cont
Lua (local)bar test.lua:14
lua_debug> cont
$
性能比對
我們再來做個簡單的測試，看看我們優化的效果。編寫如下測試腳本，foo函數模擬較長的程式，然後在另一個函數上加個斷點（為了設置hook）。我們分別使用優化前的luadebug.lua和優化後的luadebug.lua進行測試。
local ldb = require "luadebug"
local setbp = ldb.setbreakpoint
local rmbp = ldb.removebreakpoint
local function foo ()
local a = 1
for i = 1, 10000000 do
a = a + 1
end
end
local function bar ()
end
local id1 = setbp(bar, 13)
foo()
優化前
使用優化前的實現，運行這個腳本用了40s
$ time lua test2.lua
lua test2.lua 39.54s user 0.16s system 99% cpu 39.957 total
優化後
使用優化後的實現，則只花了0.109s，相差了接近400倍，可見我們的優化效果還是很明顯的。
$ time lua test2.lua
lua test2.lua 0.10s user 0.00s system 97% cpu 0.109 total
