| 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 |
) |