summaryrefslogtreecommitdiff
path: root/tools/objtool
diff options
context:
space:
mode:
authorPeter Zijlstra <peterz@infradead.org>2022-09-15 14:11:12 +0300
committerPeter Zijlstra <peterz@infradead.org>2022-10-17 17:41:08 +0300
commit5da6aea375cde499fdfac3cde4f26df4a840eb9f (patch)
tree0d5cca27775ab8e05b47ad22ded471647ddafa43 /tools/objtool
parent0c0a6d8934e2081df93ba0bfc0cf615cc9c06988 (diff)
downloadlinux-5da6aea375cde499fdfac3cde4f26df4a840eb9f.tar.xz
objtool: Fix find_{symbol,func}_containing()
The current find_{symbol,func}_containing() functions are broken in the face of overlapping symbols, exactly the case that is needed for a new ibt/endbr supression. Import interval_tree_generic.h into the tools tree and convert the symbol tree to an interval tree to support proper range stabs. Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> Link: https://lore.kernel.org/r/20220915111146.330203761@infradead.org
Diffstat (limited to 'tools/objtool')
-rw-r--r--tools/objtool/elf.c93
-rw-r--r--tools/objtool/include/objtool/elf.h3
2 files changed, 42 insertions, 54 deletions
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 7e24b09b1163..89b37cd4ab1d 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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)
diff --git a/tools/objtool/include/objtool/elf.h b/tools/objtool/include/objtool/elf.h
index baa808583c4f..d28533106b78 100644
--- a/tools/objtool/include/objtool/elf.h
+++ b/tools/objtool/include/objtool/elf.h
@@ -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;