summaryrefslogtreecommitdiff
path: root/tools/objtool/elf.c
diff options
context:
space:
mode:
Diffstat (limited to 'tools/objtool/elf.c')
-rw-r--r--tools/objtool/elf.c281
1 files changed, 202 insertions, 79 deletions
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index edba4745f25a..09ddc8f1def3 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -15,17 +15,107 @@
#include <string.h>
#include <unistd.h>
#include <errno.h>
+#include "builtin.h"
#include "elf.h"
#include "warn.h"
#define MAX_NAME_LEN 128
+static inline u32 str_hash(const char *str)
+{
+ return jhash(str, strlen(str), 0);
+}
+
+static void rb_add(struct rb_root *tree, struct rb_node *node,
+ int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+ struct rb_node **link = &tree->rb_node;
+ struct rb_node *parent = NULL;
+
+ while (*link) {
+ parent = *link;
+ if (cmp(node, parent) < 0)
+ link = &parent->rb_left;
+ else
+ link = &parent->rb_right;
+ }
+
+ rb_link_node(node, parent, link);
+ rb_insert_color(node, tree);
+}
+
+static struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ struct rb_node *node = tree->rb_node;
+ struct rb_node *match = NULL;
+
+ while (node) {
+ int c = cmp(key, node);
+ if (c <= 0) {
+ if (!c)
+ match = node;
+ node = node->rb_left;
+ } else if (c > 0) {
+ node = node->rb_right;
+ }
+ }
+
+ return match;
+}
+
+static struct rb_node *rb_next_match(struct rb_node *node, const void *key,
+ int (*cmp)(const void *key, const struct rb_node *))
+{
+ node = rb_next(node);
+ if (node && cmp(key, node))
+ node = NULL;
+ return node;
+}
+
+#define rb_for_each(tree, node, key, cmp) \
+ for ((node) = rb_find_first((tree), (key), (cmp)); \
+ (node); (node) = rb_next_match((node), (key), (cmp)))
+
+static int symbol_to_offset(struct rb_node *a, const struct rb_node *b)
+{
+ struct symbol *sa = rb_entry(a, struct symbol, node);
+ struct symbol *sb = rb_entry(b, struct symbol, node);
+
+ if (sa->offset < sb->offset)
+ return -1;
+ if (sa->offset > sb->offset)
+ return 1;
+
+ if (sa->len < sb->len)
+ return -1;
+ if (sa->len > sb->len)
+ return 1;
+
+ sa->alias = sb;
+
+ return 0;
+}
+
+static int symbol_by_offset(const void *key, const struct rb_node *node)
+{
+ const struct symbol *s = rb_entry(node, struct symbol, node);
+ const unsigned long *o = key;
+
+ if (*o < s->offset)
+ return -1;
+ if (*o > s->offset + s->len)
+ return 1;
+
+ return 0;
+}
+
struct section *find_section_by_name(struct elf *elf, const char *name)
{
struct section *sec;
- list_for_each_entry(sec, &elf->sections, list)
+ hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
if (!strcmp(sec->name, name))
return sec;
@@ -37,7 +127,7 @@ static struct section *find_section_by_index(struct elf *elf,
{
struct section *sec;
- list_for_each_entry(sec, &elf->sections, list)
+ hash_for_each_possible(elf->section_hash, sec, hash, idx)
if (sec->idx == idx)
return sec;
@@ -46,88 +136,116 @@ static struct section *find_section_by_index(struct elf *elf,
static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
{
- struct section *sec;
struct symbol *sym;
- list_for_each_entry(sec, &elf->sections, list)
- hash_for_each_possible(sec->symbol_hash, sym, hash, idx)
- if (sym->idx == idx)
- return sym;
+ hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
+ if (sym->idx == idx)
+ return sym;
return NULL;
}
struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
{
- struct symbol *sym;
+ struct rb_node *node;
- list_for_each_entry(sym, &sec->symbol_list, list)
- if (sym->type != STT_SECTION &&
- sym->offset == offset)
- return sym;
+ rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+ struct symbol *s = rb_entry(node, struct symbol, node);
+
+ if (s->offset == offset && s->type != STT_SECTION)
+ return s;
+ }
return NULL;
}
-struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
+struct symbol *find_func_by_offset(struct section *sec, unsigned long offset)
{
- struct section *sec;
- struct symbol *sym;
+ struct rb_node *node;
- list_for_each_entry(sec, &elf->sections, list)
- list_for_each_entry(sym, &sec->symbol_list, list)
- if (!strcmp(sym->name, name))
- return sym;
+ rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+ struct symbol *s = rb_entry(node, struct symbol, node);
+
+ if (s->offset == offset && s->type == STT_FUNC)
+ return s;
+ }
return NULL;
}
struct symbol *find_symbol_containing(struct section *sec, unsigned long offset)
{
- struct symbol *sym;
+ struct rb_node *node;
- list_for_each_entry(sym, &sec->symbol_list, list)
- if (sym->type != STT_SECTION &&
- offset >= sym->offset && offset < sym->offset + sym->len)
- return sym;
+ rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+ struct symbol *s = rb_entry(node, struct symbol, node);
+
+ if (s->type != STT_SECTION)
+ return s;
+ }
return NULL;
}
-struct rela *find_rela_by_dest_range(struct section *sec, unsigned long offset,
- unsigned int len)
+struct symbol *find_func_containing(struct section *sec, unsigned long offset)
{
- struct rela *rela;
- unsigned long o;
+ struct rb_node *node;
- if (!sec->rela)
- return NULL;
+ rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) {
+ struct symbol *s = rb_entry(node, struct symbol, node);
- for (o = offset; o < offset + len; o++)
- hash_for_each_possible(sec->rela->rela_hash, rela, hash, o)
- if (rela->offset == o)
- return rela;
+ if (s->type == STT_FUNC)
+ return s;
+ }
return NULL;
}
-struct rela *find_rela_by_dest(struct section *sec, unsigned long offset)
+struct symbol *find_symbol_by_name(struct elf *elf, const char *name)
{
- return find_rela_by_dest_range(sec, offset, 1);
+ struct symbol *sym;
+
+ hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
+ if (!strcmp(sym->name, name))
+ return sym;
+
+ return NULL;
}
-struct symbol *find_containing_func(struct section *sec, unsigned long offset)
+struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec,
+ unsigned long offset, unsigned int len)
{
- struct symbol *func;
+ struct rela *rela, *r = NULL;
+ unsigned long o;
+
+ if (!sec->rela)
+ return NULL;
- list_for_each_entry(func, &sec->symbol_list, list)
- if (func->type == STT_FUNC && offset >= func->offset &&
- offset < func->offset + func->len)
- return func;
+ sec = sec->rela;
+
+ for_offset_range(o, offset, offset + len) {
+ hash_for_each_possible(elf->rela_hash, rela, hash,
+ sec_offset_hash(sec, o)) {
+ if (rela->sec != sec)
+ continue;
+
+ if (rela->offset >= offset && rela->offset < offset + len) {
+ if (!r || rela->offset < r->offset)
+ r = rela;
+ }
+ }
+ if (r)
+ return r;
+ }
return NULL;
}
+struct rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset)
+{
+ return find_rela_by_dest_range(elf, sec, offset, 1);
+}
+
static int read_sections(struct elf *elf)
{
Elf_Scn *s = NULL;
@@ -155,10 +273,6 @@ static int read_sections(struct elf *elf)
INIT_LIST_HEAD(&sec->symbol_list);
INIT_LIST_HEAD(&sec->rela_list);
- hash_init(sec->rela_hash);
- hash_init(sec->symbol_hash);
-
- list_add_tail(&sec->list, &elf->sections);
s = elf_getscn(elf->elf, i);
if (!s) {
@@ -193,8 +307,15 @@ static int read_sections(struct elf *elf)
}
}
sec->len = sec->sh.sh_size;
+
+ list_add_tail(&sec->list, &elf->sections);
+ hash_add(elf->section_hash, &sec->hash, sec->idx);
+ hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
}
+ if (stats)
+ printf("nr_sections: %lu\n", (unsigned long)sections_nr);
+
/* sanity check, one more call to elf_nextscn() should return NULL */
if (elf_nextscn(elf->elf, s)) {
WARN("section entry mismatch");
@@ -207,8 +328,9 @@ static int read_sections(struct elf *elf)
static int read_symbols(struct elf *elf)
{
struct section *symtab, *sec;
- struct symbol *sym, *pfunc, *alias;
- struct list_head *entry, *tmp;
+ struct symbol *sym, *pfunc;
+ struct list_head *entry;
+ struct rb_node *pnode;
int symbols_nr, i;
char *coldstr;
@@ -227,7 +349,7 @@ static int read_symbols(struct elf *elf)
return -1;
}
memset(sym, 0, sizeof(*sym));
- alias = sym;
+ sym->alias = sym;
sym->idx = i;
@@ -265,33 +387,20 @@ static int read_symbols(struct elf *elf)
sym->offset = sym->sym.st_value;
sym->len = sym->sym.st_size;
- /* sorted insert into a per-section list */
- entry = &sym->sec->symbol_list;
- list_for_each_prev(tmp, &sym->sec->symbol_list) {
- struct symbol *s;
-
- s = list_entry(tmp, struct symbol, list);
-
- if (sym->offset > s->offset) {
- entry = tmp;
- break;
- }
-
- if (sym->offset == s->offset) {
- if (sym->len && sym->len == s->len && alias == sym)
- alias = s;
-
- if (sym->len >= s->len) {
- entry = tmp;
- break;
- }
- }
- }
- sym->alias = alias;
+ rb_add(&sym->sec->symbol_tree, &sym->node, symbol_to_offset);
+ pnode = rb_prev(&sym->node);
+ if (pnode)
+ entry = &rb_entry(pnode, struct symbol, node)->list;
+ else
+ entry = &sym->sec->symbol_list;
list_add(&sym->list, entry);
- hash_add(sym->sec->symbol_hash, &sym->hash, sym->idx);
+ hash_add(elf->symbol_hash, &sym->hash, sym->idx);
+ hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
}
+ if (stats)
+ printf("nr_symbols: %lu\n", (unsigned long)symbols_nr);
+
/* Create parent/child links for any cold subfunctions */
list_for_each_entry(sec, &elf->sections, list) {
list_for_each_entry(sym, &sec->symbol_list, list) {
@@ -353,6 +462,7 @@ static int read_relas(struct elf *elf)
struct rela *rela;
int i;
unsigned int symndx;
+ unsigned long nr_rela, max_rela = 0, tot_rela = 0;
list_for_each_entry(sec, &elf->sections, list) {
if (sec->sh.sh_type != SHT_RELA)
@@ -367,6 +477,7 @@ static int read_relas(struct elf *elf)
sec->base->rela = sec;
+ nr_rela = 0;
for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) {
rela = malloc(sizeof(*rela));
if (!rela) {
@@ -393,9 +504,16 @@ static int read_relas(struct elf *elf)
}
list_add_tail(&rela->list, &sec->rela_list);
- hash_add(sec->rela_hash, &rela->hash, rela->offset);
-
+ hash_add(elf->rela_hash, &rela->hash, rela_hash(rela));
+ nr_rela++;
}
+ max_rela = max(max_rela, nr_rela);
+ tot_rela += nr_rela;
+ }
+
+ if (stats) {
+ printf("max_rela: %lu\n", max_rela);
+ printf("tot_rela: %lu\n", tot_rela);
}
return 0;
@@ -415,6 +533,11 @@ struct elf *elf_read(const char *name, int flags)
}
memset(elf, 0, sizeof(*elf));
+ hash_init(elf->symbol_hash);
+ hash_init(elf->symbol_name_hash);
+ hash_init(elf->section_hash);
+ hash_init(elf->section_name_hash);
+ hash_init(elf->rela_hash);
INIT_LIST_HEAD(&elf->sections);
elf->fd = open(name, flags);
@@ -475,10 +598,6 @@ struct section *elf_create_section(struct elf *elf, const char *name,
INIT_LIST_HEAD(&sec->symbol_list);
INIT_LIST_HEAD(&sec->rela_list);
- hash_init(sec->rela_hash);
- hash_init(sec->symbol_hash);
-
- list_add_tail(&sec->list, &elf->sections);
s = elf_newscn(elf->elf);
if (!s) {
@@ -556,6 +675,10 @@ struct section *elf_create_section(struct elf *elf, const char *name,
shstrtab->len += strlen(name) + 1;
shstrtab->changed = true;
+ list_add_tail(&sec->list, &elf->sections);
+ hash_add(elf->section_hash, &sec->hash, sec->idx);
+ hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
+
return sec;
}