| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <20190325184522.260535-4-swboyd@chromium.org>
Date: Mon, 25 Mar 2019 11:45:21 -0700
From: Stephen Boyd <swboyd@...omium.org>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: linux-kernel@...r.kernel.org,
Masahiro Yamada <yamada.masahiro@...ionext.com>,
Douglas Anderson <dianders@...omium.org>,
Nikolay Borisov <n.borisov.lkml@...il.com>,
Kieran Bingham <kbingham@...nel.org>,
Jan Kiszka <jan.kiszka@...mens.com>,
Jackie Liu <liuyun01@...inos.cn>
Subject: [PATCH 3/4] scripts/gdb: Add rb tree iterating utilities
Implement gdb functions for rb_first(), rb_last(), rb_next(), and
rb_prev(). These can be useful to iterate through the kernel's red-black
trees.
Cc: Douglas Anderson <dianders@...omium.org>
Cc: Nikolay Borisov <n.borisov.lkml@...il.com>
Cc: Kieran Bingham <kbingham@...nel.org>
Cc: Jan Kiszka <jan.kiszka@...mens.com>
Cc: Jackie Liu <liuyun01@...inos.cn>
Signed-off-by: Stephen Boyd <swboyd@...omium.org>
---
scripts/gdb/linux/rbtree.py | 169 ++++++++++++++++++++++++++++++++++++
scripts/gdb/vmlinux-gdb.py | 1 +
2 files changed, 170 insertions(+)
create mode 100644 scripts/gdb/linux/rbtree.py
diff --git a/scripts/gdb/linux/rbtree.py b/scripts/gdb/linux/rbtree.py
new file mode 100644
index 000000000000..fd7b0b961ca1
--- /dev/null
+++ b/scripts/gdb/linux/rbtree.py
@@ -0,0 +1,169 @@
+# SPDX-License-Identifier: GPL-2.0
+#
+# Copyright 2019 Google LLC.
+
+import gdb
+
+from linux import utils
+
+rb_root_type = utils.CachedType("struct rb_root")
+rb_node_type = utils.CachedType("struct rb_node")
+
+
+def rb_first(root):
+ if root.type == rb_root_type.get_type():
+ node = node.address.cast(rb_root_type.get_type().pointer())
+ elif root.type != rb_root_type.get_type().pointer():
+ raise gdb.GdbError("Must be struct rb_root not {}"
+ .format(root.type))
+
+ node = root['rb_node']
+ if node is 0:
+ return None
+
+ while node['rb_left']:
+ node = node['rb_left']
+
+ return node
+
+def rb_last(root):
+ if root.type == rb_root_type.get_type():
+ node = node.address.cast(rb_root_type.get_type().pointer())
+ elif root.type != rb_root_type.get_type().pointer():
+ raise gdb.GdbError("Must be struct rb_root not {}"
+ .format(root.type))
+
+ node = root['rb_node']
+ if node is 0:
+ return None
+
+ while node['rb_right']:
+ node = node['rb_right']
+
+ return node
+
+def rb_parent(node):
+ parent = gdb.Value(node['__rb_parent_color'] & ~3)
+ return parent.cast(rb_node_type.get_type().pointer())
+
+def rb_empty_node(node):
+ return node['__rb_parent_color'] == node.address
+
+def rb_next(node):
+ if node.type == rb_node_type.get_type():
+ node = node.address.cast(rb_node_type.get_type().pointer())
+ elif node.type != rb_node_type.get_type().pointer():
+ raise gdb.GdbError("Must be struct rb_node not {}"
+ .format(node.type))
+
+ if rb_empty_node(node):
+ return None
+
+ if node['rb_right']:
+ node = node['rb_right']
+ while node['rb_left']:
+ node = node['rb_left']
+ return node
+
+ parent = rb_parent(node)
+ while parent and node == parent['rb_right']:
+ node = parent
+ parent = rb_parent(node)
+
+ return parent
+
+def rb_prev(node):
+ if node.type == rb_node_type.get_type():
+ node = node.address.cast(rb_node_type.get_type().pointer())
+ elif node.type != rb_node_type.get_type().pointer():
+ raise gdb.GdbError("Must be struct rb_node not {}"
+ .format(node.type))
+
+ if rb_empty_node(node):
+ return None
+
+ if node['rb_left']:
+ node = node['rb_left']
+ while node['rb_right']:
+ node = node['rb_right']
+ return node.dereference()
+
+ parent = rb_parent(node)
+ while parent and node == parent['rb_left'].dereference():
+ node = parent
+ parent = rb_parent(node)
+
+ return parent
+
+
+class LxRbFirst(gdb.Function):
+ """Lookup and return a node from an RBTree
+
+$lx_rb_first(root): Return the node at the given index.
+If index is omitted, the root node is dereferenced and returned."""
+
+ def __init__(self):
+ super(LxRbFirst, self).__init__("lx_rb_first")
+
+ def invoke(self, root):
+ result = rb_first(root)
+ if result is None:
+ raise gdb.GdbError("No entry in tree")
+
+ return result
+
+LxRbFirst()
+
+class LxRbLast(gdb.Function):
+ """Lookup and return a node from an RBTree.
+
+$lx_rb_last(root): Return the node at the given index.
+If index is omitted, the root node is dereferenced and returned."""
+
+ def __init__(self):
+ super(LxRbLast, self).__init__("lx_rb_last")
+
+ def invoke(self, root):
+ result = rb_last(root)
+ if result is None:
+ raise gdb.GdbError("No entry in tree")
+
+ return result
+
+LxRbLast()
+
+class LxRbNext(gdb.Function):
+ """Lookup and return a node from an RBTree.
+
+$lx_rb_next(node): Return the node at the given index.
+If index is omitted, the root node is dereferenced and returned."""
+
+ def __init__(self):
+ super(LxRbNext, self).__init__("lx_rb_next")
+
+ def invoke(self, node):
+ result = rb_next(node)
+ if result is None:
+ raise gdb.GdbError("No entry in tree")
+
+ return result
+
+LxRbNext()
+
+class LxRbPrev(gdb.Function):
+ """Lookup and return a node from an RBTree.
+
+$lx_rb_prev(node): Return the node at the given index.
+If index is omitted, the root node is dereferenced and returned."""
+
+ def __init__(self):
+ super(LxRbPrev, self).__init__("lx_rb_prev")
+
+ def invoke(self, node):
+ result = rb_prev(node)
+ if result is None:
+ raise gdb.GdbError("No entry in tree")
+
+ return result
+
+LxRbPrev()
diff --git a/scripts/gdb/vmlinux-gdb.py b/scripts/gdb/vmlinux-gdb.py
index be0efb5dda5b..89e4aa4f8966 100644
--- a/scripts/gdb/vmlinux-gdb.py
+++ b/scripts/gdb/vmlinux-gdb.py
@@ -30,5 +30,6 @@ else:
import linux.config
import linux.cpus
import linux.lists
+ import linux.rbtree
import linux.proc
import linux.constants
--
Sent by a computer through tubes
Powered by blists - more mailing lists