Debian Codegraph @

tests/linux_kernel/helpers/test_radixtree.py

raw
1 # Copyright (c) Meta Platforms, Inc. and affiliates.
2 # SPDX-License-Identifier: LGPL-2.1-or-later
3
4 from drgn import NULL, Object
5 from drgn.helpers.linux.radixtree import radix_tree_for_each, radix_tree_lookup
6 from tests.linux_kernel import LinuxKernelTestCase, skip_unless_have_test_kmod
7
8
9 @skip_unless_have_test_kmod
10 class TestRadixTree(LinuxKernelTestCase):
11 def test_radix_tree_lookup_empty(self):
12 root = self.prog["drgn_test_radix_tree_empty"].address_of_()
13 self.assertIdentical(radix_tree_lookup(root, 0), NULL(self.prog, "void *"))
14 self.assertIdentical(radix_tree_lookup(root, 100000), NULL(self.prog, "void *"))
15
16 def test_radix_tree_for_each_empty(self):
17 root = self.prog["drgn_test_radix_tree_empty"].address_of_()
18 self.assertIdentical(list(radix_tree_for_each(root)), [])
19
20 def test_radix_tree_lookup_one(self):
21 root = self.prog["drgn_test_radix_tree_one"].address_of_()
22 self.assertIdentical(radix_tree_lookup(root, 0), NULL(self.prog, "void *"))
23 self.assertIdentical(radix_tree_lookup(root, 665), NULL(self.prog, "void *"))
24 self.assertIdentical(
25 radix_tree_lookup(root, 666), Object(self.prog, "void *", 0xDEADB00)
26 )
27 self.assertIdentical(radix_tree_lookup(root, 667), NULL(self.prog, "void *"))
28 self.assertIdentical(radix_tree_lookup(root, 100000), NULL(self.prog, "void *"))
29
30 def test_radix_tree_for_each_one(self):
31 root = self.prog["drgn_test_radix_tree_one"].address_of_()
32 self.assertIdentical(
33 list(radix_tree_for_each(root)),
34 [(666, Object(self.prog, "void *", 0xDEADB00))],
35 )
36
37 def test_radix_tree_lookup_one_at_zero(self):
38 root = self.prog["drgn_test_radix_tree_one_at_zero"].address_of_()
39 self.assertIdentical(
40 radix_tree_lookup(root, 0), Object(self.prog, "void *", 0x1234)
41 )
42 self.assertIdentical(radix_tree_lookup(root, 1), NULL(self.prog, "void *"))
43 self.assertIdentical(radix_tree_lookup(root, 100000), NULL(self.prog, "void *"))
44
45 def test_radix_tree_for_each_one_at_zero(self):
46 root = self.prog["drgn_test_radix_tree_one_at_zero"].address_of_()
47 self.assertIdentical(
48 list(radix_tree_for_each(root)), [(0, Object(self.prog, "void *", 0x1234))]
49 )
50
51 def test_radix_tree_lookup_sparse(self):
52 root = self.prog["drgn_test_radix_tree_sparse"].address_of_()
53 self.assertIdentical(radix_tree_lookup(root, 0), NULL(self.prog, "void *"))
54 self.assertIdentical(
55 radix_tree_lookup(root, 1), Object(self.prog, "void *", 0x1234)
56 )
57 self.assertIdentical(radix_tree_lookup(root, 2), NULL(self.prog, "void *"))
58 self.assertIdentical(
59 radix_tree_lookup(root, 0x40000000), NULL(self.prog, "void *")
60 )
61 self.assertIdentical(
62 radix_tree_lookup(root, 0x80000000), NULL(self.prog, "void *")
63 )
64 self.assertIdentical(
65 radix_tree_lookup(root, 0x80800000), NULL(self.prog, "void *")
66 )
67 self.assertIdentical(
68 radix_tree_lookup(root, 0x80808000), NULL(self.prog, "void *")
69 )
70 self.assertIdentical(
71 radix_tree_lookup(root, 0x80808080), Object(self.prog, "void *", 0x5678)
72 )
73 self.assertIdentical(
74 radix_tree_lookup(root, 0xFFFFFFFE), NULL(self.prog, "void *")
75 )
76 self.assertIdentical(
77 radix_tree_lookup(root, 0xFFFFFFFF), Object(self.prog, "void *", 0x9ABC)
78 )
79
80 def test_radix_tree_for_each_sparse(self):
81 root = self.prog["drgn_test_radix_tree_sparse"].address_of_()
82 self.assertIdentical(
83 list(radix_tree_for_each(root)),
84 [
85 (1, Object(self.prog, "void *", 0x1234)),
86 (0x80808080, Object(self.prog, "void *", 0x5678)),
87 (0xFFFFFFFF, Object(self.prog, "void *", 0x9ABC)),
88 ],
89 )
90
91 def test_radix_tree_lookup_multi_index(self):
92 try:
93 root = self.prog["drgn_test_radix_tree_multi_order"].address_of_()
94 except KeyError:
95 # Radix tree multi-order support only exists between Linux kernel
96 # commits e61452365372 ("radix_tree: add support for multi-order
97 # entries") (in v4.6) and 3a08cd52c37c ("radix tree: Remove
98 # multiorder support") (in v4.20), and only if
99 # CONFIG_RADIX_TREE_MULTIORDER=y.
100 self.skipTest("kernel does not have multi-order radix trees")
101 self.assertIdentical(
102 radix_tree_lookup(root, 0x80807FFF), NULL(self.prog, "void *")
103 )
104 for index in range(0x80808000, 0x80808200):
105 with self.subTest(index=index):
106 self.assertIdentical(
107 radix_tree_lookup(root, index), Object(self.prog, "void *", 0x1234)
108 )
109 self.assertIdentical(
110 radix_tree_lookup(root, 0x80808200), NULL(self.prog, "void *")
111 )
112
113 def test_radix_tree_for_each_multi_index(self):
114 try:
115 root = self.prog["drgn_test_radix_tree_multi_order"].address_of_()
116 except KeyError:
117 # See test_radix_tree_lookup_multi_index().
118 self.skipTest("kernel does not have multi-order radix trees")
119 self.assertIdentical(
120 list(radix_tree_for_each(root)),
121 [(0x80808000, Object(self.prog, "void *", 0x1234))],
122 )