1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
#!/usr/bin/env tarantool
local tap = require('tap')
local test = tap.test("lj-494-table-chain-infinite-loop")
test:plan(1)
-- Test file to demonstrate Lua table hash chain bugs discussed in
-- https://github.com/LuaJIT/LuaJIT/issues/494
-- Credit: prepared by Peter Cawley here with minor edits:
-- https://gist.github.com/corsix/1fc9b13a2dd5f3659417b62dd54d4500
--- Plumbing
local ffi = require("ffi")
ffi.cdef("char* strstr(const char*, const char*)")
local strstr = ffi.C.strstr
local cast = ffi.cast
local str_hash_offset = cast("uint32_t*", strstr("*", ""))[-2] == 1 and 3 or 2
function str_hash(s)
return cast("uint32_t*", strstr(s, "")) - str_hash_offset
end
local table_new = require("table.new")
--- Prepare some objects
local victims = {}
local orig_hash = {}
for c in ("abcdef"):gmatch"." do
v = c .. "{09add58a-13a4-44e0-a52c-d44d0f9b2b95}"
victims[c] = v
orig_hash[c] = str_hash(v)[0]
end
collectgarbage()
do --- Basic version of the problem
for k, v in pairs(victims) do
str_hash(v)[0] = 0
end
t = table_new(0, 8)
-- Make chain a -> b -> c -> d, all with a as primary
t[victims.a] = true
t[victims.d] = true
t[victims.c] = true
t[victims.b] = true
-- Change c's primary to b, and d's primary to c
t[victims.d] = nil
t[victims.c] = nil
str_hash(victims.c)[0] = 5
str_hash(victims.d)[0] = 6
t[victims.c] = true
t[victims.d] = true
-- Insert something with b as primary
str_hash(victims.e)[0] = 5
t[victims.e] = true
-- Check for consistency
for c in ("abcde"):gmatch"." do
assert(t[victims[c]], c)
end
end
collectgarbage()
do --- Just `mn != freenode` can lead to infinite loops
for k, v in pairs(victims) do
str_hash(v)[0] = 0
end
t = table_new(0, 8)
-- Make chain a -> b -> c -> d, all with a as primary
t[victims.a] = true
t[victims.d] = true
t[victims.c] = true
t[victims.b] = true
-- Change c's primary to b, and d's primary to d
t[victims.d] = nil
t[victims.c] = nil
str_hash(victims.c)[0] = 5
str_hash(victims.d)[0] = 7
t[victims.c] = true
t[victims.d] = true
-- Insert something with b as primary
str_hash(victims.e)[0] = 5
t[victims.e] = true
-- Insert something with d as primary (infinite lookup loop)
str_hash(victims.f)[0] = 7
t[victims.f] = true
end
collectgarbage()
do --- Just `mn != nn` can lead to infinite loops
for k, v in pairs(victims) do
str_hash(v)[0] = 0
end
t = table_new(0, 8)
-- Make chain a -> b -> c -> d -> e, all with a as primary
t[victims.a] = true
t[victims.e] = true
t[victims.d] = true
t[victims.c] = true
t[victims.b] = true
-- Change c's primary to b, d's primary to d, and e's primary to d
t[victims.e] = nil
t[victims.d] = nil
t[victims.c] = nil
str_hash(victims.c)[0] = 4
str_hash(victims.d)[0] = 6
str_hash(victims.e)[0] = 6
t[victims.c] = true
t[victims.d] = true
t[victims.e] = true
-- Insert something with b as primary (infinite rechaining loop)
str_hash(victims.f)[0] = 4
t[victims.f] = true
end
for i = 0, 10 do --- Non-strings can need rechaining too
collectgarbage()
k = tonumber((("0x%xp-1074"):format(i)))
str_hash(victims.a)[0] = 0
str_hash(victims.b)[0] = 0
t = table_new(0, 4)
-- a -> b, both with a as primary
t[victims.a] = true
t[victims.b] = true
-- Change b's primary to b
t[victims.b] = nil
str_hash(victims.b)[0] = 3
t[victims.b] = true
-- Might get a -> b -> k, with k's primary as b
t[k] = true
-- Change b's primary to a
t[victims.b] = nil
str_hash(victims.b)[0] = 0
t[victims.b] = true
-- Insert something with b as primary
str_hash(victims.c)[0] = 3
t[victims.c] = true
-- Check for consistency
assert(t[k], i)
end
for i = 0, 10 do --- Non-strings can be moved to freenode
collectgarbage()
k = false
str_hash(victims.a)[0] = 0
str_hash(victims.b)[0] = 0
t = table_new(0, 4)
-- a -> k -> b, all with a as primary
t[victims.a] = true
t[victims.b] = true
t[k] = true
-- Change b's primary to k
t[victims.b] = nil
str_hash(victims.b)[0] = 2
t[victims.b] = true
-- Insert a non-string with primary of k
t[tonumber((("0x%xp-1074"):format(i)))] = true
-- Check for consistency
assert(t[victims.b], i)
end
collectgarbage()
do --- Do not forget to advance freenode in the not-string case
t = table_new(0, 4)
-- Chain of colliding numbers
t[0x0p-1074] = true
t[0x4p-1074] = true
t[0x8p-1074] = true
-- Steal middle node of the chain to be a main node (infinite walking loop)
t[0x2p-1074] = true
end
collectgarbage()
--- Restore interpreter invariants, just in case
for c, v in pairs(victims) do
str_hash(v)[0] = orig_hash[c]
end
test:ok(true, "table keys collisions are resolved properly (no assertions failed)")
os.exit(test:check() and 0 or 1)
|
