#include <string.h>
#include <unistd.h>
#include <errno.h>
+#include <linux/interval_tree_generic.h>
#include <objtool/builtin.h>
#include <objtool/elf.h>
__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;
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;
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;
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;
/*
* 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)
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;
{
struct list_head *entry;
struct rb_node *pnode;
+ struct symbol *iter;
+ INIT_LIST_HEAD(&sym->reloc_list);
INIT_LIST_HEAD(&sym->pv_target);
sym->alias = 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;
* 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)
reloc->sym = sym;
reloc->addend = addend;
+ list_add_tail(&reloc->sym_reloc_entry, &sym->reloc_list);
list_add_tail(&reloc->list, &sec->reloc->reloc_list);
elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
*/
static void elf_dirty_reloc_sym(struct elf *elf, struct symbol *sym)
{
- struct section *sec;
-
- list_for_each_entry(sec, &elf->sections, list) {
- struct reloc *reloc;
-
- if (sec->changed)
- continue;
+ struct reloc *reloc;
- list_for_each_entry(reloc, &sec->reloc_list, list) {
- if (reloc->sym == sym) {
- sec->changed = true;
- break;
- }
- }
- }
+ list_for_each_entry(reloc, &sym->reloc_list, sym_reloc_entry)
+ reloc->sec->changed = true;
}
/*
/* end-of-list */
if (!symtab_data) {
+ /*
+ * Over-allocate to avoid O(n^2) symbol creation
+ * behaviour. The down side is that libelf doesn't
+ * like this; see elf_truncate_section() for the fixup.
+ */
+ int num = max(1U, sym->idx/3);
void *buf;
if (idx) {
if (t)
shndx_data = elf_newdata(t);
- buf = calloc(1, entsize);
+ buf = calloc(num, entsize);
if (!buf) {
WARN("malloc");
return -1;
}
symtab_data->d_buf = buf;
- symtab_data->d_size = entsize;
+ symtab_data->d_size = num * entsize;
symtab_data->d_align = 1;
symtab_data->d_type = ELF_T_SYM;
- symtab->sh.sh_size += entsize;
symtab->changed = true;
+ symtab->truncate = true;
if (t) {
- shndx_data->d_buf = &sym->sec->idx;
- shndx_data->d_size = sizeof(Elf32_Word);
+ buf = calloc(num, sizeof(Elf32_Word));
+ if (!buf) {
+ WARN("malloc");
+ return -1;
+ }
+
+ shndx_data->d_buf = buf;
+ shndx_data->d_size = num * sizeof(Elf32_Word);
shndx_data->d_align = sizeof(Elf32_Word);
shndx_data->d_type = ELF_T_WORD;
- symtab_shndx->sh.sh_size += sizeof(Elf32_Word);
symtab_shndx->changed = true;
+ symtab_shndx->truncate = true;
}
break;
}
static struct symbol *
-elf_create_section_symbol(struct elf *elf, struct section *sec)
+__elf_create_symbol(struct elf *elf, struct symbol *sym)
{
struct section *symtab, *symtab_shndx;
Elf32_Word first_non_local, new_idx;
- struct symbol *sym, *old;
+ struct symbol *old;
symtab = find_section_by_name(elf, ".symtab");
if (symtab) {
return NULL;
}
- sym = calloc(1, sizeof(*sym));
- if (!sym) {
- perror("malloc");
- return NULL;
- }
-
- sym->name = sec->name;
- sym->sec = sec;
+ new_idx = symtab->sh.sh_size / symtab->sh.sh_entsize;
- // st_name 0
- sym->sym.st_info = GELF_ST_INFO(STB_LOCAL, STT_SECTION);
- // st_other 0
- // st_value 0
- // st_size 0
+ if (GELF_ST_BIND(sym->sym.st_info) != STB_LOCAL)
+ goto non_local;
/*
* Move the first global symbol, as per sh_info, into a new, higher
* symbol index. This fees up a spot for a new local symbol.
*/
first_non_local = symtab->sh.sh_info;
- new_idx = symtab->sh.sh_size / symtab->sh.sh_entsize;
old = find_symbol_by_index(elf, first_non_local);
if (old) {
old->idx = new_idx;
new_idx = first_non_local;
}
+ /*
+ * Either way, we will add a LOCAL symbol.
+ */
+ symtab->sh.sh_info += 1;
+
+non_local:
sym->idx = new_idx;
if (elf_update_symbol(elf, symtab, symtab_shndx, sym)) {
WARN("elf_update_symbol");
return NULL;
}
- /*
- * Either way, we added a LOCAL symbol.
- */
- symtab->sh.sh_info += 1;
+ symtab->sh.sh_size += symtab->sh.sh_entsize;
+ symtab->changed = true;
- elf_add_symbol(elf, sym);
+ if (symtab_shndx) {
+ symtab_shndx->sh.sh_size += sizeof(Elf32_Word);
+ symtab_shndx->changed = true;
+ }
+
+ return sym;
+}
+
+static struct symbol *
+elf_create_section_symbol(struct elf *elf, struct section *sec)
+{
+ struct symbol *sym = calloc(1, sizeof(*sym));
+
+ if (!sym) {
+ perror("malloc");
+ return NULL;
+ }
+
+ sym->name = sec->name;
+ sym->sec = sec;
+
+ // st_name 0
+ sym->sym.st_info = GELF_ST_INFO(STB_LOCAL, STT_SECTION);
+ // st_other 0
+ // st_value 0
+ // st_size 0
+
+ sym = __elf_create_symbol(elf, sym);
+ if (sym)
+ elf_add_symbol(elf, sym);
+
+ return sym;
+}
+
+static int elf_add_string(struct elf *elf, struct section *strtab, char *str);
+
+struct symbol *
+elf_create_prefix_symbol(struct elf *elf, struct symbol *orig, long size)
+{
+ struct symbol *sym = calloc(1, sizeof(*sym));
+ size_t namelen = strlen(orig->name) + sizeof("__pfx_");
+ char *name = malloc(namelen);
+
+ if (!sym || !name) {
+ perror("malloc");
+ return NULL;
+ }
+
+ snprintf(name, namelen, "__pfx_%s", orig->name);
+
+ sym->name = name;
+ sym->sec = orig->sec;
+
+ sym->sym.st_name = elf_add_string(elf, NULL, name);
+ sym->sym.st_info = orig->sym.st_info;
+ sym->sym.st_value = orig->sym.st_value - size;
+ sym->sym.st_size = size;
+
+ sym = __elf_create_symbol(elf, sym);
+ if (sym)
+ elf_add_symbol(elf, sym);
return sym;
}
static int read_relocs(struct elf *elf)
{
+ unsigned long nr_reloc, max_reloc = 0, tot_reloc = 0;
struct section *sec;
struct reloc *reloc;
- int i;
unsigned int symndx;
- unsigned long nr_reloc, max_reloc = 0, tot_reloc = 0;
+ struct symbol *sym;
+ int i;
if (!elf_alloc_hash(reloc, elf->text_size / 16))
return -1;
reloc->sec = sec;
reloc->idx = i;
- reloc->sym = find_symbol_by_index(elf, symndx);
+ reloc->sym = sym = find_symbol_by_index(elf, symndx);
if (!reloc->sym) {
WARN("can't find reloc entry symbol %d for %s",
symndx, sec->name);
return -1;
}
+ list_add_tail(&reloc->sym_reloc_entry, &sym->reloc_list);
list_add_tail(&reloc->list, &sec->reloc_list);
elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
return 0;
}
+/*
+ * When Elf_Scn::sh_size is smaller than the combined Elf_Data::d_size
+ * do you:
+ *
+ * A) adhere to the section header and truncate the data, or
+ * B) ignore the section header and write out all the data you've got?
+ *
+ * Yes, libelf sucks and we need to manually truncate if we over-allocate data.
+ */
+static int elf_truncate_section(struct elf *elf, struct section *sec)
+{
+ u64 size = sec->sh.sh_size;
+ bool truncated = false;
+ Elf_Data *data = NULL;
+ Elf_Scn *s;
+
+ s = elf_getscn(elf->elf, sec->idx);
+ if (!s) {
+ WARN_ELF("elf_getscn");
+ return -1;
+ }
+
+ for (;;) {
+ /* get next data descriptor for the relevant section */
+ data = elf_getdata(s, data);
+
+ if (!data) {
+ if (size) {
+ WARN("end of section data but non-zero size left\n");
+ return -1;
+ }
+ return 0;
+ }
+
+ if (truncated) {
+ /* when we remove symbols */
+ WARN("truncated; but more data\n");
+ return -1;
+ }
+
+ if (!data->d_size) {
+ WARN("zero size data");
+ return -1;
+ }
+
+ if (data->d_size > size) {
+ truncated = true;
+ data->d_size = size;
+ }
+
+ size -= data->d_size;
+ }
+}
+
int elf_write(struct elf *elf)
{
struct section *sec;
/* Update changed relocation sections and section headers: */
list_for_each_entry(sec, &elf->sections, list) {
+ if (sec->truncate)
+ elf_truncate_section(elf, sec);
+
if (sec->changed) {
s = elf_getscn(elf->elf, sec->idx);
if (!s) {
git.samba.org / sfrench / cifs-2.6.git / blobdiff