new file mode 100644
@@ -0,0 +1,187 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+ Interval Trees
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
+
+ include/linux/interval_tree_generic.h
+*/
+
+#include <linux/rbtree_augmented.h>
+
+/*
+ * Template for implementing interval trees
+ *
+ * ITSTRUCT: struct type of the interval tree nodes
+ * ITRB: name of struct rb_node field within ITSTRUCT
+ * ITTYPE: type of the interval endpoints
+ * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
+ * ITSTART(n): start endpoint of ITSTRUCT node n
+ * ITLAST(n): last endpoint of ITSTRUCT node n
+ * ITSTATIC: 'static' or empty
+ * ITPREFIX: prefix to use for the inline tree definitions
+ *
+ * Note - before using this, please consider if generic version
+ * (interval_tree.h) would work for you...
+ */
+
+#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \
+ ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
+ \
+/* Callbacks for augmented rbtree insert and remove */ \
+ \
+RB_DECLARE_CALLBACKS_MAX(static, ITPREFIX ## _augment, \
+ ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITLAST) \
+ \
+/* Insert / remove interval nodes from the tree */ \
+ \
+ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
+ struct rb_root_cached *root) \
+{ \
+ struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \
+ ITTYPE start = ITSTART(node), last = ITLAST(node); \
+ ITSTRUCT *parent; \
+ bool leftmost = true; \
+ \
+ while (*link) { \
+ rb_parent = *link; \
+ parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \
+ if (parent->ITSUBTREE < last) \
+ parent->ITSUBTREE = last; \
+ if (start < ITSTART(parent)) \
+ link = &parent->ITRB.rb_left; \
+ else { \
+ link = &parent->ITRB.rb_right; \
+ leftmost = false; \
+ } \
+ } \
+ \
+ node->ITSUBTREE = last; \
+ rb_link_node(&node->ITRB, rb_parent, link); \
+ rb_insert_augmented_cached(&node->ITRB, root, \
+ leftmost, &ITPREFIX ## _augment); \
+} \
+ \
+ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, \
+ struct rb_root_cached *root) \
+{ \
+ rb_erase_augmented_cached(&node->ITRB, root, &ITPREFIX ## _augment); \
+} \
+ \
+/* \
+ * Iterate over intervals intersecting [start;last] \
+ * \
+ * Note that a node's interval intersects [start;last] iff: \
+ * Cond1: ITSTART(node) <= last \
+ * and \
+ * Cond2: start <= ITLAST(node) \
+ */ \
+ \
+static ITSTRUCT * \
+ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
+{ \
+ while (true) { \
+ /* \
+ * Loop invariant: start <= node->ITSUBTREE \
+ * (Cond2 is satisfied by one of the subtree nodes) \
+ */ \
+ if (node->ITRB.rb_left) { \
+ ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \
+ ITSTRUCT, ITRB); \
+ if (start <= left->ITSUBTREE) { \
+ /* \
+ * Some nodes in left subtree satisfy Cond2. \
+ * Iterate to find the leftmost such node N. \
+ * If it also satisfies Cond1, that's the \
+ * match we are looking for. Otherwise, there \
+ * is no matching interval as nodes to the \
+ * right of N can't satisfy Cond1 either. \
+ */ \
+ node = left; \
+ continue; \
+ } \
+ } \
+ if (ITSTART(node) <= last) { /* Cond1 */ \
+ if (start <= ITLAST(node)) /* Cond2 */ \
+ return node; /* node is leftmost match */ \
+ if (node->ITRB.rb_right) { \
+ node = rb_entry(node->ITRB.rb_right, \
+ ITSTRUCT, ITRB); \
+ if (start <= node->ITSUBTREE) \
+ continue; \
+ } \
+ } \
+ return NULL; /* No match */ \
+ } \
+} \
+ \
+ITSTATIC ITSTRUCT * \
+ITPREFIX ## _iter_first(struct rb_root_cached *root, \
+ ITTYPE start, ITTYPE last) \
+{ \
+ ITSTRUCT *node, *leftmost; \
+ \
+ if (!root->rb_root.rb_node) \
+ return NULL; \
+ \
+ /* \
+ * Fastpath range intersection/overlap between A: [a0, a1] and \
+ * B: [b0, b1] is given by: \
+ * \
+ * a0 <= b1 && b0 <= a1 \
+ * \
+ * ... where A holds the lock range and B holds the smallest \
+ * 'start' and largest 'last' in the tree. For the later, we \
+ * rely on the root node, which by augmented interval tree \
+ * property, holds the largest value in its last-in-subtree. \
+ * This allows mitigating some of the tree walk overhead for \
+ * for non-intersecting ranges, maintained and consulted in O(1). \
+ */ \
+ node = rb_entry(root->rb_root.rb_node, ITSTRUCT, ITRB); \
+ if (node->ITSUBTREE < start) \
+ return NULL; \
+ \
+ leftmost = rb_entry(root->rb_leftmost, ITSTRUCT, ITRB); \
+ if (ITSTART(leftmost) > last) \
+ return NULL; \
+ \
+ return ITPREFIX ## _subtree_search(node, start, last); \
+} \
+ \
+ITSTATIC ITSTRUCT * \
+ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
+{ \
+ struct rb_node *rb = node->ITRB.rb_right, *prev; \
+ \
+ while (true) { \
+ /* \
+ * Loop invariants: \
+ * Cond1: ITSTART(node) <= last \
+ * rb == node->ITRB.rb_right \
+ * \
+ * First, search right subtree if suitable \
+ */ \
+ if (rb) { \
+ ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \
+ if (start <= right->ITSUBTREE) \
+ return ITPREFIX ## _subtree_search(right, \
+ start, last); \
+ } \
+ \
+ /* Move up the tree until we come from a node's left child */ \
+ do { \
+ rb = rb_parent(&node->ITRB); \
+ if (!rb) \
+ return NULL; \
+ prev = &node->ITRB; \
+ node = rb_entry(rb, ITSTRUCT, ITRB); \
+ rb = node->ITRB.rb_right; \
+ } while (prev == rb); \
+ \
+ /* Check if the node intersects [start;last] */ \
+ if (last < ITSTART(node)) /* !Cond1 */ \
+ return NULL; \
+ else if (start <= ITLAST(node)) /* Cond2 */ \
+ return node; \
+ } \
+}
@@ -16,6 +16,7 @@
#include <string.h>
#include <unistd.h>
#include <errno.h>
+#include <linux/interval_tree_generic.h>
#include <objtool/builtin.h>
#include <objtool/elf.h>
@@ -50,38 +51,22 @@ static inline u32 str_hash(const char *str)
__elf_table(name); \
})
-static bool symbol_to_offset(struct rb_node *a, const struct rb_node *b)
+static inline unsigned long __sym_start(struct symbol *s)
{
- struct symbol *sa = rb_entry(a, struct symbol, node);
- struct symbol *sb = rb_entry(b, struct symbol, node);
-
- if (sa->offset < sb->offset)
- return true;
- if (sa->offset > sb->offset)
- return false;
-
- if (sa->len < sb->len)
- return true;
- if (sa->len > sb->len)
- return false;
-
- sa->alias = sb;
-
- return false;
+ return s->offset;
}
-static int symbol_by_offset(const void *key, const struct rb_node *node)
+static inline unsigned long __sym_last(struct symbol *s)
{
- const struct symbol *s = rb_entry(node, struct symbol, node);
- const unsigned long *o = key;
+ return s->offset + s->len - 1;
+}
- if (*o < s->offset)
- return -1;
- if (*o >= s->offset + s->len)
- return 1;
+INTERVAL_TREE_DEFINE(struct symbol, node, unsigned long, __subtree_last,
+ __sym_start, __sym_last, static, __sym)
- return 0;
-}
+#define __sym_for_each(_iter, _tree, _start, _end) \
+ for (_iter = __sym_iter_first((_tree), (_start), (_end)); \
+ _iter; _iter = __sym_iter_next(_iter, (_start), (_end)))
struct symbol_hole {
unsigned long key;
@@ -147,13 +132,12 @@ static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
{
- struct rb_node *node;
-
- rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
- struct symbol *s = rb_entry(node, struct symbol, node);
+ struct rb_root_cached *tree = (struct rb_root_cached *)&sec->symbol_tree;
+ struct symbol *iter;
- if (s->offset == offset && s->type != STT_SECTION)
- return s;
+ __sym_for_each(iter, tree, offset, offset) {
+ if (iter->offset == offset && iter->type != STT_SECTION)
+ return iter;
}
return NULL;
@@ -161,13 +145,12 @@ struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
struct symbol *find_func_by_offset(struct section *sec, unsigned long offset)
{
- struct rb_node *node;
+ struct rb_root_cached *tree = (struct rb_root_cached *)&sec->symbol_tree;
+ struct symbol *iter;
- rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
- struct symbol *s = rb_entry(node, struct symbol, node);
-
- if (s->offset == offset && s->type == STT_FUNC)
- return s;
+ __sym_for_each(iter, tree, offset, offset) {
+ if (iter->offset == offset && iter->type == STT_FUNC)
+ return iter;
}
return NULL;
@@ -175,13 +158,12 @@ struct symbol *find_func_by_offset(struct section *sec, unsigned long offset)
struct symbol *find_symbol_containing(const struct section *sec, unsigned long offset)
{
- struct rb_node *node;
-
- rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
- struct symbol *s = rb_entry(node, struct symbol, node);
+ struct rb_root_cached *tree = (struct rb_root_cached *)&sec->symbol_tree;
+ struct symbol *iter;
- if (s->type != STT_SECTION)
- return s;
+ __sym_for_each(iter, tree, offset, offset) {
+ if (iter->type != STT_SECTION)
+ return iter;
}
return NULL;
@@ -202,7 +184,7 @@ int find_symbol_hole_containing(const struct section *sec, unsigned long offset)
/*
* Find the rightmost symbol for which @offset is after it.
*/
- n = rb_find(&hole, &sec->symbol_tree, symbol_hole_by_offset);
+ n = rb_find(&hole, &sec->symbol_tree.rb_root, symbol_hole_by_offset);
/* found a symbol that contains @offset */
if (n)
@@ -224,13 +206,12 @@ int find_symbol_hole_containing(const struct section *sec, unsigned long offset)
struct symbol *find_func_containing(struct section *sec, unsigned long offset)
{
- struct rb_node *node;
-
- rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
- struct symbol *s = rb_entry(node, struct symbol, node);
+ struct rb_root_cached *tree = (struct rb_root_cached *)&sec->symbol_tree;
+ struct symbol *iter;
- if (s->type == STT_FUNC)
- return s;
+ __sym_for_each(iter, tree, offset, offset) {
+ if (iter->type == STT_FUNC)
+ return iter;
}
return NULL;
@@ -373,6 +354,7 @@ static void elf_add_symbol(struct elf *elf, struct symbol *sym)
{
struct list_head *entry;
struct rb_node *pnode;
+ struct symbol *iter;
INIT_LIST_HEAD(&sym->pv_target);
sym->alias = sym;
@@ -386,7 +368,12 @@ static void elf_add_symbol(struct elf *elf, struct symbol *sym)
sym->offset = sym->sym.st_value;
sym->len = sym->sym.st_size;
- rb_add(&sym->node, &sym->sec->symbol_tree, symbol_to_offset);
+ __sym_for_each(iter, &sym->sec->symbol_tree, sym->offset, sym->offset) {
+ if (iter->offset == sym->offset && iter->type == sym->type)
+ iter->alias = sym;
+ }
+
+ __sym_insert(sym, &sym->sec->symbol_tree);
pnode = rb_prev(&sym->node);
if (pnode)
entry = &rb_entry(pnode, struct symbol, node)->list;
@@ -401,7 +388,7 @@ static void elf_add_symbol(struct elf *elf, struct symbol *sym)
* can exist within a function, confusing the sorting.
*/
if (!sym->len)
- rb_erase(&sym->node, &sym->sec->symbol_tree);
+ __sym_remove(sym, &sym->sec->symbol_tree);
}
static int read_symbols(struct elf *elf)
@@ -30,7 +30,7 @@ struct section {
struct hlist_node hash;
struct hlist_node name_hash;
GElf_Shdr sh;
- struct rb_root symbol_tree;
+ struct rb_root_cached symbol_tree;
struct list_head symbol_list;
struct list_head reloc_list;
struct section *base, *reloc;
@@ -53,6 +53,7 @@ struct symbol {
unsigned char bind, type;
unsigned long offset;
unsigned int len;
+ unsigned long __subtree_last;
struct symbol *pfunc, *cfunc, *alias;
u8 uaccess_safe : 1;
u8 static_call_tramp : 1;