cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

rbtree.py (4347B)

      1# SPDX-License-Identifier: GPL-2.0
      2#
      3# Copyright 2019 Google LLC.
      4
      5import gdb
      6
      7from linux import utils
      8
      9rb_root_type = utils.CachedType("struct rb_root")
     10rb_node_type = utils.CachedType("struct rb_node")
     11
     12
     13def rb_first(root):
     14    if root.type == rb_root_type.get_type():
     15        node = root.address.cast(rb_root_type.get_type().pointer())
     16    elif root.type != rb_root_type.get_type().pointer():
     17        raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
     18
     19    node = root['rb_node']
     20    if node == 0:
     21        return None
     22
     23    while node['rb_left']:
     24        node = node['rb_left']
     25
     26    return node
     27
     28
     29def rb_last(root):
     30    if root.type == rb_root_type.get_type():
     31        node = root.address.cast(rb_root_type.get_type().pointer())
     32    elif root.type != rb_root_type.get_type().pointer():
     33        raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
     34
     35    node = root['rb_node']
     36    if node == 0:
     37        return None
     38
     39    while node['rb_right']:
     40        node = node['rb_right']
     41
     42    return node
     43
     44
     45def rb_parent(node):
     46    parent = gdb.Value(node['__rb_parent_color'] & ~3)
     47    return parent.cast(rb_node_type.get_type().pointer())
     48
     49
     50def rb_empty_node(node):
     51    return node['__rb_parent_color'] == node.address
     52
     53
     54def rb_next(node):
     55    if node.type == rb_node_type.get_type():
     56        node = node.address.cast(rb_node_type.get_type().pointer())
     57    elif node.type != rb_node_type.get_type().pointer():
     58        raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
     59
     60    if rb_empty_node(node):
     61        return None
     62
     63    if node['rb_right']:
     64        node = node['rb_right']
     65        while node['rb_left']:
     66            node = node['rb_left']
     67        return node
     68
     69    parent = rb_parent(node)
     70    while parent and node == parent['rb_right']:
     71            node = parent
     72            parent = rb_parent(node)
     73
     74    return parent
     75
     76
     77def rb_prev(node):
     78    if node.type == rb_node_type.get_type():
     79        node = node.address.cast(rb_node_type.get_type().pointer())
     80    elif node.type != rb_node_type.get_type().pointer():
     81        raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
     82
     83    if rb_empty_node(node):
     84        return None
     85
     86    if node['rb_left']:
     87        node = node['rb_left']
     88        while node['rb_right']:
     89            node = node['rb_right']
     90        return node.dereference()
     91
     92    parent = rb_parent(node)
     93    while parent and node == parent['rb_left'].dereference():
     94            node = parent
     95            parent = rb_parent(node)
     96
     97    return parent
     98
     99
    100class LxRbFirst(gdb.Function):
    101    """Lookup and return a node from an RBTree
    102
    103$lx_rb_first(root): Return the node at the given index.
    104If index is omitted, the root node is dereferenced and returned."""
    105
    106    def __init__(self):
    107        super(LxRbFirst, self).__init__("lx_rb_first")
    108
    109    def invoke(self, root):
    110        result = rb_first(root)
    111        if result is None:
    112            raise gdb.GdbError("No entry in tree")
    113
    114        return result
    115
    116
    117LxRbFirst()
    118
    119
    120class LxRbLast(gdb.Function):
    121    """Lookup and return a node from an RBTree.
    122
    123$lx_rb_last(root): Return the node at the given index.
    124If index is omitted, the root node is dereferenced and returned."""
    125
    126    def __init__(self):
    127        super(LxRbLast, self).__init__("lx_rb_last")
    128
    129    def invoke(self, root):
    130        result = rb_last(root)
    131        if result is None:
    132            raise gdb.GdbError("No entry in tree")
    133
    134        return result
    135
    136
    137LxRbLast()
    138
    139
    140class LxRbNext(gdb.Function):
    141    """Lookup and return a node from an RBTree.
    142
    143$lx_rb_next(node): Return the node at the given index.
    144If index is omitted, the root node is dereferenced and returned."""
    145
    146    def __init__(self):
    147        super(LxRbNext, self).__init__("lx_rb_next")
    148
    149    def invoke(self, node):
    150        result = rb_next(node)
    151        if result is None:
    152            raise gdb.GdbError("No entry in tree")
    153
    154        return result
    155
    156
    157LxRbNext()
    158
    159
    160class LxRbPrev(gdb.Function):
    161    """Lookup and return a node from an RBTree.
    162
    163$lx_rb_prev(node): Return the node at the given index.
    164If index is omitted, the root node is dereferenced and returned."""
    165
    166    def __init__(self):
    167        super(LxRbPrev, self).__init__("lx_rb_prev")
    168
    169    def invoke(self, node):
    170        result = rb_prev(node)
    171        if result is None:
    172            raise gdb.GdbError("No entry in tree")
    173
    174        return result
    175
    176
    177LxRbPrev()