diff options
| -rw-r--r-- | scripts/gdb/linux/radixtree.py | 66 |
1 files changed, 40 insertions, 26 deletions
diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py index bc2954e45c32..8ce9936dfa50 100644 --- a/scripts/gdb/linux/radixtree.py +++ b/scripts/gdb/linux/radixtree.py @@ -27,6 +27,24 @@ def entry_to_node(node): indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INTERNAL_NODE return indirect_ptr.cast(radix_tree_node_type.get_type().pointer()) +def is_node(entry): + # Like xa_is_node(): internal entries below 4096 are sibling, retry + # or zero entries rather than pointers to a struct xa_node. + ulong_type = utils.get_ulong_type() + return is_internal_node(entry) and entry.cast(ulong_type) > 4096 + +def is_sibling(entry): + # Like xa_is_sibling(): a multi-index entry occupies several slots, + # and all but the first hold a sibling entry that encodes the offset + # of the first one. + ulong_type = utils.get_ulong_type() + return is_internal_node(entry) and entry.cast(ulong_type) < \ + xa_mk_internal(constants.LX_RADIX_TREE_MAP_SIZE - 1) + +def sibling_offset(entry): + ulong_type = utils.get_ulong_type() + return int(entry.cast(ulong_type)) >> 2 + def node_maxindex(node): return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1 @@ -40,39 +58,35 @@ def resolve_root(root): def lookup(root, index): root = resolve_root(root) - node = root['xa_head'] - if node == 0: - return None + entry = root['xa_head'] - if not (is_internal_node(node)): - if (index > 0): + if is_node(entry): + node = entry_to_node(entry) + if index > node_maxindex(node): return None - return node - node = entry_to_node(node) - maxindex = node_maxindex(node) - - if (index > maxindex): - return None - - shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT - - while True: - offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK - slot = node['slots'][offset] + # Walk down the tree like xas_load() does. + while True: + offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK + entry = node['slots'][offset] - if slot == 0: - return None + while is_sibling(entry): + entry = node['slots'][sibling_offset(entry)] + if node['shift'] and is_node(entry): + # xas_descend() turns this into a retry entry. + return None - node = slot.cast(node.type.pointer()).dereference() - if node == 0: - return None + if not is_node(entry) or node['shift'] == 0: + break + node = entry_to_node(entry) + elif index > 0: + return None - shift -= constants.LX_RADIX_TREE_MAP_SHIFT - if (shift <= 0): - break + # Empty slots and retry or zero entries hold no data. + if entry == 0 or is_internal_node(entry): + return None - return node + return entry def descend(parent, index): offset = (index >> int(parent["shift"])) & constants.LX_RADIX_TREE_MAP_MASK |