Debian Codegraph @

tests/linux_kernel/helpers/test_mapletree.py

raw
1 # Copyright (c) Meta Platforms, Inc. and affiliates.
2 # SPDX-License-Identifier: LGPL-2.1-or-later
3
4 import unittest
5
6 from drgn import NULL, Object, sizeof
7 from drgn.helpers.linux.mapletree import mt_for_each, mtree_load
8 from drgn.helpers.linux.xarray import xa_is_zero
9 from tests import slow_test
10 from tests.linux_kernel import LinuxKernelTestCase, skip_unless_have_test_kmod
11
12
13 @skip_unless_have_test_kmod
14 class TestMapleTree(LinuxKernelTestCase):
15 @classmethod
16 def setUpClass(cls):
17 super().setUpClass()
18 if not cls.prog["drgn_test_have_maple_tree"]:
19 raise unittest.SkipTest("kernel does not have maple tree")
20
21 def maple_trees(self, name):
22 yield self.prog["drgn_test_maple_tree_" + name].address_of_(), False
23 yield self.prog["drgn_test_maple_tree_arange_" + name].address_of_(), True
24
25 def test_mtree_load_empty(self):
26 for mt, _ in self.maple_trees("empty"):
27 self.assertIdentical(mtree_load(mt, 0), NULL(self.prog, "void *"))
28 self.assertIdentical(mtree_load(mt, 666), NULL(self.prog, "void *"))
29
30 def test_mt_for_each_empty(self):
31 for mt, _ in self.maple_trees("empty"):
32 self.assertIdentical(list(mt_for_each(mt)), [])
33
34 def test_mtree_load_one(self):
35 for mt, _ in self.maple_trees("one"):
36 self.assertIdentical(mtree_load(mt, 0), NULL(self.prog, "void *"))
37 self.assertIdentical(mtree_load(mt, 665), NULL(self.prog, "void *"))
38 self.assertIdentical(
39 mtree_load(mt, 666), Object(self.prog, "void *", 0xDEADB00)
40 )
41 self.assertIdentical(mtree_load(mt, 667), NULL(self.prog, "void *"))
42 self.assertIdentical(mtree_load(mt, 2**32 - 1), NULL(self.prog, "void *"))
43 self.assertIdentical(mtree_load(mt, 2**64 - 1), NULL(self.prog, "void *"))
44
45 def test_mt_for_each_one(self):
46 for mt, _ in self.maple_trees("one"):
47 self.assertIdentical(
48 list(mt_for_each(mt)),
49 [(666, 666, Object(self.prog, "void *", 0xDEADB00))],
50 )
51
52 def test_mtree_load_one_range(self):
53 for mt, _ in self.maple_trees("one_range"):
54 self.assertIdentical(mtree_load(mt, 0), NULL(self.prog, "void *"))
55 self.assertIdentical(mtree_load(mt, 615), NULL(self.prog, "void *"))
56 self.assertIdentical(
57 mtree_load(mt, 616), Object(self.prog, "void *", 0xDEADB000)
58 )
59 self.assertIdentical(
60 mtree_load(mt, 660), Object(self.prog, "void *", 0xDEADB000)
61 )
62 self.assertIdentical(
63 mtree_load(mt, 666), Object(self.prog, "void *", 0xDEADB000)
64 )
65 self.assertIdentical(mtree_load(mt, 667), NULL(self.prog, "void *"))
66 self.assertIdentical(mtree_load(mt, 2**32 - 1), NULL(self.prog, "void *"))
67 self.assertIdentical(mtree_load(mt, 2**64 - 1), NULL(self.prog, "void *"))
68
69 def test_mt_for_each_one_range(self):
70 for mt, _ in self.maple_trees("one_range"):
71 self.assertIdentical(
72 list(mt_for_each(mt)),
73 [(616, 666, Object(self.prog, "void *", 0xDEADB000))],
74 )
75
76 def test_mtree_load_one_at_zero(self):
77 for mt, _ in self.maple_trees("one_at_zero"):
78 self.assertIdentical(mtree_load(mt, 0), Object(self.prog, "void *", 0x1234))
79 self.assertIdentical(mtree_load(mt, 1), NULL(self.prog, "void *"))
80 self.assertIdentical(mtree_load(mt, 2**32 - 1), NULL(self.prog, "void *"))
81 self.assertIdentical(mtree_load(mt, 2**64 - 1), NULL(self.prog, "void *"))
82
83 def test_mt_for_each_one_at_zero(self):
84 for mt, _ in self.maple_trees("one_at_zero"):
85 self.assertIdentical(
86 list(mt_for_each(mt)), [(0, 0, Object(self.prog, "void *", 0x1234))]
87 )
88
89 def test_mtree_load_one_range_at_zero(self):
90 for mt, _ in self.maple_trees("one_range_at_zero"):
91 self.assertIdentical(mtree_load(mt, 0), Object(self.prog, "void *", 0x5678))
92 self.assertIdentical(mtree_load(mt, 1), Object(self.prog, "void *", 0x5678))
93 self.assertIdentical(
94 mtree_load(mt, 0x1336), Object(self.prog, "void *", 0x5678)
95 )
96 self.assertIdentical(
97 mtree_load(mt, 0x1337), Object(self.prog, "void *", 0x5678)
98 )
99 self.assertIdentical(mtree_load(mt, 0x1338), NULL(self.prog, "void *"))
100 self.assertIdentical(mtree_load(mt, 2**32 - 1), NULL(self.prog, "void *"))
101 self.assertIdentical(mtree_load(mt, 2**64 - 1), NULL(self.prog, "void *"))
102
103 def test_mt_for_each_one_range_at_zero(self):
104 for mt, _ in self.maple_trees("one_range_at_zero"):
105 self.assertIdentical(
106 list(mt_for_each(mt)),
107 [(0, 0x1337, Object(self.prog, "void *", 0x5678))],
108 )
109
110 def test_mtree_load_zero_entry(self):
111 for mt, _ in self.maple_trees("zero_entry"):
112 self.assertIdentical(mtree_load(mt, 666), NULL(self.prog, "void *"))
113 self.assertTrue(xa_is_zero(mtree_load(mt, 666, advanced=True)))
114
115 def test_mtree_for_each_zero_entry(self):
116 for mt, _ in self.maple_trees("zero_entry"):
117 self.assertIdentical(list(mt_for_each(mt)), [])
118 entries = list(mt_for_each(mt, advanced=True))
119 self.assertEqual(len(entries), 1)
120 self.assertEqual(entries[0][:2], (666, 666))
121 self.assertTrue(xa_is_zero(entries[0][2]))
122
123 def test_mtree_load_zero_entry_at_zero(self):
124 for mt, _ in self.maple_trees("zero_entry_at_zero"):
125 self.assertIdentical(mtree_load(mt, 0), NULL(self.prog, "void *"))
126 self.assertTrue(xa_is_zero(mtree_load(mt, 0, advanced=True)))
127
128 def test_mtree_for_each_zero_entry_at_zero(self):
129 for mt, _ in self.maple_trees("zero_entry_at_zero"):
130 self.assertIdentical(list(mt_for_each(mt)), [])
131 entries = list(mt_for_each(mt, advanced=True))
132 self.assertEqual(len(entries), 1)
133 self.assertEqual(entries[0][:2], (0, 0))
134 self.assertTrue(xa_is_zero(entries[0][2]))
135
136 def test_mtree_load_dense(self):
137 for mt, _ in self.maple_trees("dense"):
138 for i in range(5):
139 with self.subTest(i=i):
140 self.assertIdentical(
141 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA000 | i)
142 )
143 self.assertIdentical(mtree_load(mt, 5), NULL(self.prog, "void *"))
144 self.assertIdentical(mtree_load(mt, 2**32 - 1), NULL(self.prog, "void *"))
145 self.assertIdentical(mtree_load(mt, 2**64 - 1), NULL(self.prog, "void *"))
146
147 def test_mt_for_each_dense(self):
148 for mt, _ in self.maple_trees("dense"):
149 self.assertIdentical(
150 list(mt_for_each(mt)),
151 [(i, i, Object(self.prog, "void *", 0xB0BA000 | i)) for i in range(5)],
152 )
153
154 def test_mtree_load_dense_ranges(self):
155 for mt, _ in self.maple_trees("dense_ranges"):
156 self.assertIdentical(
157 mtree_load(mt, 0), Object(self.prog, "void *", 0xB0BA000)
158 )
159 for i in range(1, 4):
160 self.assertIdentical(
161 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA001)
162 )
163 for i in range(4, 9):
164 self.assertIdentical(
165 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA002)
166 )
167 for i in range(9, 16):
168 self.assertIdentical(
169 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA003)
170 )
171 for i in range(16, 25):
172 self.assertIdentical(
173 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA004)
174 )
175 self.assertIdentical(mtree_load(mt, 25), NULL(self.prog, "void *"))
176 self.assertIdentical(mtree_load(mt, 2**32 - 1), NULL(self.prog, "void *"))
177 self.assertIdentical(mtree_load(mt, 2**64 - 1), NULL(self.prog, "void *"))
178
179 def test_mt_for_each_dense_ranges(self):
180 for mt, _ in self.maple_trees("dense_ranges"):
181 self.assertIdentical(
182 list(mt_for_each(mt)),
183 [
184 (
185 i**2,
186 (i + 1) ** 2 - 1,
187 Object(self.prog, "void *", 0xB0BA000 | i),
188 )
189 for i in range(5)
190 ],
191 )
192
193 def test_mtree_load_sparse(self):
194 for mt, _ in self.maple_trees("sparse"):
195 self.assertIdentical(mtree_load(mt, 0), NULL(self.prog, "void *"))
196 self.assertIdentical(
197 mtree_load(mt, 1), Object(self.prog, "void *", 0xB0BA000)
198 )
199 for i in range(2, 4):
200 self.assertIdentical(mtree_load(mt, i), NULL(self.prog, "void *"))
201 self.assertIdentical(
202 mtree_load(mt, 4), Object(self.prog, "void *", 0xB0BA001)
203 )
204 for i in range(5, 9):
205 self.assertIdentical(mtree_load(mt, i), NULL(self.prog, "void *"))
206 self.assertIdentical(mtree_load(mt, 26), NULL(self.prog, "void *"))
207 self.assertIdentical(mtree_load(mt, 2**32 - 1), NULL(self.prog, "void *"))
208 self.assertIdentical(mtree_load(mt, 2**64 - 1), NULL(self.prog, "void *"))
209
210 def test_mt_for_each_sparse(self):
211 for mt, _ in self.maple_trees("sparse"):
212 self.assertIdentical(
213 list(mt_for_each(mt)),
214 [
215 (
216 (i + 1) ** 2,
217 (i + 1) ** 2,
218 Object(self.prog, "void *", 0xB0BA000 | i),
219 )
220 for i in range(5)
221 ],
222 )
223
224 def test_mtree_load_sparse_ranges(self):
225 for mt, _ in self.maple_trees("sparse_ranges"):
226 self.assertIdentical(mtree_load(mt, 0), NULL(self.prog, "void *"))
227 for i in range(1, 5):
228 self.assertIdentical(
229 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA000)
230 )
231 for i in range(5, 9):
232 self.assertIdentical(mtree_load(mt, i), NULL(self.prog, "void *"))
233 for i in range(9, 17):
234 self.assertIdentical(
235 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA001)
236 )
237 for i in range(17, 25):
238 self.assertIdentical(mtree_load(mt, i), NULL(self.prog, "void *"))
239 for i in range(25, 37):
240 self.assertIdentical(
241 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA002)
242 )
243 for i in range(37, 49):
244 self.assertIdentical(mtree_load(mt, i), NULL(self.prog, "void *"))
245 for i in range(49, 65):
246 self.assertIdentical(
247 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA003)
248 )
249 for i in range(65, 81):
250 self.assertIdentical(mtree_load(mt, i), NULL(self.prog, "void *"))
251 for i in range(81, 101):
252 self.assertIdentical(
253 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA004)
254 )
255 self.assertIdentical(mtree_load(mt, 101), NULL(self.prog, "void *"))
256 self.assertIdentical(mtree_load(mt, 2**32 - 1), NULL(self.prog, "void *"))
257 self.assertIdentical(mtree_load(mt, 2**64 - 1), NULL(self.prog, "void *"))
258
259 def test_mt_for_each_sparse_ranges(self):
260 for mt, _ in self.maple_trees("sparse_ranges"):
261 self.assertIdentical(
262 list(mt_for_each(mt)),
263 [
264 (
265 (2 * i + 1) ** 2,
266 (2 * i + 2) ** 2,
267 Object(self.prog, "void *", 0xB0BA000 | i),
268 )
269 for i in range(5)
270 ],
271 )
272
273 @slow_test
274 def test_mtree_load_three_levels_dense_1(self):
275 maple_range64_slots = self.prog["drgn_test_maple_range64_slots"].value_()
276 ulong_max = (1 << (sizeof(self.prog.type("unsigned long")) * 8)) - 1
277 for mt, arange in self.maple_trees("three_levels_dense_1"):
278 node_slots = self.prog[
279 (
280 "drgn_test_maple_arange64_slots"
281 if arange
282 else "drgn_test_maple_range64_slots"
283 )
284 ].value_()
285 n = 2 * (node_slots - 1) * (maple_range64_slots - 1) + (
286 maple_range64_slots - 1
287 )
288 for i in range(n):
289 with self.subTest(i=i):
290 self.assertIdentical(
291 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA000 | i)
292 )
293 self.assertIdentical(mtree_load(mt, n), NULL(self.prog, "void *"))
294 self.assertIdentical(mtree_load(mt, n + 1), NULL(self.prog, "void *"))
295 self.assertIdentical(
296 mtree_load(mt, ulong_max - 1), NULL(self.prog, "void *")
297 )
298 self.assertIdentical(mtree_load(mt, ulong_max), NULL(self.prog, "void *"))
299
300 def test_mt_for_each_three_levels_dense_1(self):
301 maple_range64_slots = self.prog["drgn_test_maple_range64_slots"].value_()
302 for mt, arange in self.maple_trees("three_levels_dense_1"):
303 node_slots = self.prog[
304 (
305 "drgn_test_maple_arange64_slots"
306 if arange
307 else "drgn_test_maple_range64_slots"
308 )
309 ].value_()
310 n = 2 * (node_slots - 1) * (maple_range64_slots - 1) + (
311 maple_range64_slots - 1
312 )
313 self.assertIdentical(
314 list(mt_for_each(mt)),
315 [(i, i, Object(self.prog, "void *", 0xB0BA000 | i)) for i in range(n)],
316 )
317
318 @slow_test
319 def test_mtree_load_three_levels_dense_2(self):
320 maple_range64_slots = self.prog["drgn_test_maple_range64_slots"].value_()
321 ulong_max = (1 << (sizeof(self.prog.type("unsigned long")) * 8)) - 1
322 for mt, arange in self.maple_trees("three_levels_dense_2"):
323 node_slots = self.prog[
324 (
325 "drgn_test_maple_arange64_slots"
326 if arange
327 else "drgn_test_maple_range64_slots"
328 )
329 ].value_()
330 n = 2 * node_slots * maple_range64_slots
331 for i in range(n):
332 with self.subTest(i=i):
333 self.assertIdentical(
334 mtree_load(mt, i), Object(self.prog, "void *", 0xB0BA000 | i)
335 )
336 self.assertIdentical(mtree_load(mt, n), NULL(self.prog, "void *"))
337 self.assertIdentical(mtree_load(mt, n + 1), NULL(self.prog, "void *"))
338 self.assertIdentical(
339 mtree_load(mt, ulong_max - 1), NULL(self.prog, "void *")
340 )
341 self.assertIdentical(mtree_load(mt, ulong_max), NULL(self.prog, "void *"))
342
343 def test_mt_for_each_three_levels_dense_2(self):
344 maple_range64_slots = self.prog["drgn_test_maple_range64_slots"].value_()
345 for mt, arange in self.maple_trees("three_levels_dense_2"):
346 node_slots = self.prog[
347 (
348 "drgn_test_maple_arange64_slots"
349 if arange
350 else "drgn_test_maple_range64_slots"
351 )
352 ].value_()
353 n = 2 * node_slots * maple_range64_slots
354 self.assertIdentical(
355 list(mt_for_each(mt)),
356 [(i, i, Object(self.prog, "void *", 0xB0BA000 | i)) for i in range(n)],
357 )
358
359 @slow_test
360 def test_mtree_load_three_levels_ranges_1(self):
361 maple_range64_slots = self.prog["drgn_test_maple_range64_slots"].value_()
362 ulong_max = (1 << (sizeof(self.prog.type("unsigned long")) * 8)) - 1
363 for mt, arange in self.maple_trees("three_levels_ranges_1"):
364 node_slots = self.prog[
365 (
366 "drgn_test_maple_arange64_slots"
367 if arange
368 else "drgn_test_maple_range64_slots"
369 )
370 ].value_()
371 n = 2 * (node_slots - 1) * (maple_range64_slots - 1) + (
372 maple_range64_slots - 1
373 )
374 for i in range(n):
375 with self.subTest(i=i):
376 self.assertIdentical(
377 mtree_load(mt, 2 * i),
378 Object(self.prog, "void *", 0xB0BA000 | i),
379 )
380 self.assertIdentical(
381 mtree_load(mt, 2 * i + 1),
382 Object(self.prog, "void *", 0xB0BA000 | i),
383 )
384 self.assertIdentical(
385 mtree_load(mt, 2 * n), Object(self.prog, "void *", 0xB0BA000 | n)
386 )
387 self.assertIdentical(
388 mtree_load(mt, 2 * n + 1), Object(self.prog, "void *", 0xB0BA000 | n)
389 )
390 self.assertIdentical(
391 mtree_load(mt, ulong_max - 1),
392 Object(self.prog, "void *", 0xB0BA000 | n),
393 )
394 self.assertIdentical(
395 mtree_load(mt, ulong_max), Object(self.prog, "void *", 0xB0BA000 | n)
396 )
397
398 def test_mt_for_each_three_levels_ranges_1(self):
399 maple_range64_slots = self.prog["drgn_test_maple_range64_slots"].value_()
400 ulong_max = (1 << (sizeof(self.prog.type("unsigned long")) * 8)) - 1
401 for mt, arange in self.maple_trees("three_levels_ranges_1"):
402 node_slots = self.prog[
403 (
404 "drgn_test_maple_arange64_slots"
405 if arange
406 else "drgn_test_maple_range64_slots"
407 )
408 ].value_()
409 n = 2 * (node_slots - 1) * (maple_range64_slots - 1) + (
410 maple_range64_slots - 1
411 )
412 self.assertIdentical(
413 list(mt_for_each(mt)),
414 [
415 (2 * i, 2 * i + 1, Object(self.prog, "void *", 0xB0BA000 | i))
416 for i in range(n)
417 ]
418 + [(2 * n, ulong_max, Object(self.prog, "void *", 0xB0BA000 | n))],
419 )
420
421 @slow_test
422 def test_mtree_load_three_levels_ranges_2(self):
423 maple_range64_slots = self.prog["drgn_test_maple_range64_slots"].value_()
424 ulong_max = (1 << (sizeof(self.prog.type("unsigned long")) * 8)) - 1
425 for mt, arange in self.maple_trees("three_levels_ranges_2"):
426 node_slots = self.prog[
427 (
428 "drgn_test_maple_arange64_slots"
429 if arange
430 else "drgn_test_maple_range64_slots"
431 )
432 ].value_()
433 n = 2 * node_slots * maple_range64_slots
434 for i in range(n):
435 with self.subTest(i=i):
436 self.assertIdentical(
437 mtree_load(mt, 2 * i),
438 Object(self.prog, "void *", 0xB0BA000 | i),
439 )
440 self.assertIdentical(
441 mtree_load(mt, 2 * i + 1),
442 Object(self.prog, "void *", 0xB0BA000 | i),
443 )
444 self.assertIdentical(
445 mtree_load(mt, 2 * n), Object(self.prog, "void *", 0xB0BA000 | n)
446 )
447 self.assertIdentical(
448 mtree_load(mt, 2 * n + 1), Object(self.prog, "void *", 0xB0BA000 | n)
449 )
450 self.assertIdentical(
451 mtree_load(mt, ulong_max - 1),
452 Object(self.prog, "void *", 0xB0BA000 | n),
453 )
454 self.assertIdentical(
455 mtree_load(mt, ulong_max), Object(self.prog, "void *", 0xB0BA000 | n)
456 )
457
458 def test_mt_for_each_three_levels_ranges_2(self):
459 maple_range64_slots = self.prog["drgn_test_maple_range64_slots"].value_()
460 ulong_max = (1 << (sizeof(self.prog.type("unsigned long")) * 8)) - 1
461 for mt, arange in self.maple_trees("three_levels_ranges_2"):
462 node_slots = self.prog[
463 (
464 "drgn_test_maple_arange64_slots"
465 if arange
466 else "drgn_test_maple_range64_slots"
467 )
468 ].value_()
469 n = 2 * node_slots * maple_range64_slots
470 self.assertIdentical(
471 list(mt_for_each(mt)),
472 [
473 (2 * i, 2 * i + 1, Object(self.prog, "void *", 0xB0BA000 | i))
474 for i in range(n)
475 ]
476 + [(2 * n, ulong_max, Object(self.prog, "void *", 0xB0BA000 | n))],
477 )