1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * elf.c - ELF access library
5 * Adapted from kpatch (https://github.com/dynup/kpatch):
6 * Copyright (C) 2013-2015 Josh Poimboeuf <jpoimboe@redhat.com>
7 * Copyright (C) 2014 Seth Jennings <sjenning@redhat.com>
10 #include <sys/types.h>
23 #define MAX_NAME_LEN 128
25 static inline u32 str_hash(const char *str)
27 return jhash(str, strlen(str), 0);
30 static inline int elf_hash_bits(void)
32 return vmlinux ? ELF_HASH_BITS : 16;
35 #define elf_hash_add(hashtable, node, key) \
36 hlist_add_head(node, &hashtable[hash_min(key, elf_hash_bits())])
38 static void elf_hash_init(struct hlist_head *table)
40 __hash_init(table, 1U << elf_hash_bits());
43 #define elf_hash_for_each_possible(name, obj, member, key) \
44 hlist_for_each_entry(obj, &name[hash_min(key, elf_hash_bits())], member)
46 static bool symbol_to_offset(struct rb_node *a, const struct rb_node *b)
48 struct symbol *sa = rb_entry(a, struct symbol, node);
49 struct symbol *sb = rb_entry(b, struct symbol, node);
51 if (sa->offset < sb->offset)
53 if (sa->offset > sb->offset)
56 if (sa->len < sb->len)
58 if (sa->len > sb->len)
66 static int symbol_by_offset(const void *key, const struct rb_node *node)
68 const struct symbol *s = rb_entry(node, struct symbol, node);
69 const unsigned long *o = key;
73 if (*o >= s->offset + s->len)
79 struct section *find_section_by_name(const struct elf *elf, const char *name)
83 elf_hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name))
84 if (!strcmp(sec->name, name))
90 static struct section *find_section_by_index(struct elf *elf,
95 elf_hash_for_each_possible(elf->section_hash, sec, hash, idx)
102 static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
106 elf_hash_for_each_possible(elf->symbol_hash, sym, hash, idx)
113 struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
115 struct rb_node *node;
117 rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
118 struct symbol *s = rb_entry(node, struct symbol, node);
120 if (s->offset == offset && s->type != STT_SECTION)
127 struct symbol *find_func_by_offset(struct section *sec, unsigned long offset)
129 struct rb_node *node;
131 rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
132 struct symbol *s = rb_entry(node, struct symbol, node);
134 if (s->offset == offset && s->type == STT_FUNC)
141 struct symbol *find_symbol_containing(const struct section *sec, unsigned long offset)
143 struct rb_node *node;
145 rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
146 struct symbol *s = rb_entry(node, struct symbol, node);
148 if (s->type != STT_SECTION)
155 struct symbol *find_func_containing(struct section *sec, unsigned long offset)
157 struct rb_node *node;
159 rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
160 struct symbol *s = rb_entry(node, struct symbol, node);
162 if (s->type == STT_FUNC)
169 struct symbol *find_symbol_by_name(const struct elf *elf, const char *name)
173 elf_hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name))
174 if (!strcmp(sym->name, name))
180 struct reloc *find_reloc_by_dest_range(const struct elf *elf, struct section *sec,
181 unsigned long offset, unsigned int len)
183 struct reloc *reloc, *r = NULL;
191 for_offset_range(o, offset, offset + len) {
192 elf_hash_for_each_possible(elf->reloc_hash, reloc, hash,
193 sec_offset_hash(sec, o)) {
194 if (reloc->sec != sec)
197 if (reloc->offset >= offset && reloc->offset < offset + len) {
198 if (!r || reloc->offset < r->offset)
209 struct reloc *find_reloc_by_dest(const struct elf *elf, struct section *sec, unsigned long offset)
211 return find_reloc_by_dest_range(elf, sec, offset, 1);
214 void insn_to_reloc_sym_addend(struct section *sec, unsigned long offset,
218 reloc->sym = sec->sym;
219 reloc->addend = offset;
224 * The Clang assembler strips section symbols, so we have to reference
225 * the function symbol instead:
227 reloc->sym = find_symbol_containing(sec, offset);
230 * Hack alert. This happens when we need to reference the NOP
231 * pad insn immediately after the function.
233 reloc->sym = find_symbol_containing(sec, offset - 1);
237 reloc->addend = offset - reloc->sym->offset;
240 static int read_sections(struct elf *elf)
244 size_t shstrndx, sections_nr;
247 if (elf_getshdrnum(elf->elf, §ions_nr)) {
248 WARN_ELF("elf_getshdrnum");
252 if (elf_getshdrstrndx(elf->elf, &shstrndx)) {
253 WARN_ELF("elf_getshdrstrndx");
257 for (i = 0; i < sections_nr; i++) {
258 sec = malloc(sizeof(*sec));
263 memset(sec, 0, sizeof(*sec));
265 INIT_LIST_HEAD(&sec->symbol_list);
266 INIT_LIST_HEAD(&sec->reloc_list);
268 s = elf_getscn(elf->elf, i);
270 WARN_ELF("elf_getscn");
274 sec->idx = elf_ndxscn(s);
276 if (!gelf_getshdr(s, &sec->sh)) {
277 WARN_ELF("gelf_getshdr");
281 sec->name = elf_strptr(elf->elf, shstrndx, sec->sh.sh_name);
283 WARN_ELF("elf_strptr");
287 if (sec->sh.sh_size != 0) {
288 sec->data = elf_getdata(s, NULL);
290 WARN_ELF("elf_getdata");
293 if (sec->data->d_off != 0 ||
294 sec->data->d_size != sec->sh.sh_size) {
295 WARN("unexpected data attributes for %s",
300 sec->len = sec->sh.sh_size;
302 list_add_tail(&sec->list, &elf->sections);
303 elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
304 elf_hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
308 printf("nr_sections: %lu\n", (unsigned long)sections_nr);
310 /* sanity check, one more call to elf_nextscn() should return NULL */
311 if (elf_nextscn(elf->elf, s)) {
312 WARN("section entry mismatch");
319 static int read_symbols(struct elf *elf)
321 struct section *symtab, *symtab_shndx, *sec;
322 struct symbol *sym, *pfunc;
323 struct list_head *entry;
324 struct rb_node *pnode;
327 Elf_Data *shndx_data = NULL;
330 symtab = find_section_by_name(elf, ".symtab");
333 * A missing symbol table is actually possible if it's an empty
334 * .o file. This can happen for thunk_64.o.
339 symtab_shndx = find_section_by_name(elf, ".symtab_shndx");
341 shndx_data = symtab_shndx->data;
343 symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize;
345 for (i = 0; i < symbols_nr; i++) {
346 sym = malloc(sizeof(*sym));
351 memset(sym, 0, sizeof(*sym));
356 if (!gelf_getsymshndx(symtab->data, shndx_data, i, &sym->sym,
358 WARN_ELF("gelf_getsymshndx");
362 sym->name = elf_strptr(elf->elf, symtab->sh.sh_link,
365 WARN_ELF("elf_strptr");
369 sym->type = GELF_ST_TYPE(sym->sym.st_info);
370 sym->bind = GELF_ST_BIND(sym->sym.st_info);
372 if ((sym->sym.st_shndx > SHN_UNDEF &&
373 sym->sym.st_shndx < SHN_LORESERVE) ||
374 (shndx_data && sym->sym.st_shndx == SHN_XINDEX)) {
375 if (sym->sym.st_shndx != SHN_XINDEX)
376 shndx = sym->sym.st_shndx;
378 sym->sec = find_section_by_index(elf, shndx);
380 WARN("couldn't find section for symbol %s",
384 if (sym->type == STT_SECTION) {
385 sym->name = sym->sec->name;
389 sym->sec = find_section_by_index(elf, 0);
391 sym->offset = sym->sym.st_value;
392 sym->len = sym->sym.st_size;
394 rb_add(&sym->node, &sym->sec->symbol_tree, symbol_to_offset);
395 pnode = rb_prev(&sym->node);
397 entry = &rb_entry(pnode, struct symbol, node)->list;
399 entry = &sym->sec->symbol_list;
400 list_add(&sym->list, entry);
401 elf_hash_add(elf->symbol_hash, &sym->hash, sym->idx);
402 elf_hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
405 * Don't store empty STT_NOTYPE symbols in the rbtree. They
406 * can exist within a function, confusing the sorting.
409 rb_erase(&sym->node, &sym->sec->symbol_tree);
413 printf("nr_symbols: %lu\n", (unsigned long)symbols_nr);
415 /* Create parent/child links for any cold subfunctions */
416 list_for_each_entry(sec, &elf->sections, list) {
417 list_for_each_entry(sym, &sec->symbol_list, list) {
418 char pname[MAX_NAME_LEN + 1];
420 if (sym->type != STT_FUNC)
423 if (sym->pfunc == NULL)
426 if (sym->cfunc == NULL)
429 coldstr = strstr(sym->name, ".cold");
433 pnamelen = coldstr - sym->name;
434 if (pnamelen > MAX_NAME_LEN) {
435 WARN("%s(): parent function name exceeds maximum length of %d characters",
436 sym->name, MAX_NAME_LEN);
440 strncpy(pname, sym->name, pnamelen);
441 pname[pnamelen] = '\0';
442 pfunc = find_symbol_by_name(elf, pname);
445 WARN("%s(): can't find parent function",
454 * Unfortunately, -fnoreorder-functions puts the child
455 * inside the parent. Remove the overlap so we can
456 * have sane assumptions.
458 * Note that pfunc->len now no longer matches
459 * pfunc->sym.st_size.
461 if (sym->sec == pfunc->sec &&
462 sym->offset >= pfunc->offset &&
463 sym->offset + sym->len == pfunc->offset + pfunc->len) {
464 pfunc->len -= sym->len;
476 void elf_add_reloc(struct elf *elf, struct reloc *reloc)
478 struct section *sec = reloc->sec;
480 list_add_tail(&reloc->list, &sec->reloc_list);
481 elf_hash_add(elf->reloc_hash, &reloc->hash, reloc_hash(reloc));
484 static int read_rel_reloc(struct section *sec, int i, struct reloc *reloc, unsigned int *symndx)
486 if (!gelf_getrel(sec->data, i, &reloc->rel)) {
487 WARN_ELF("gelf_getrel");
490 reloc->type = GELF_R_TYPE(reloc->rel.r_info);
492 reloc->offset = reloc->rel.r_offset;
493 *symndx = GELF_R_SYM(reloc->rel.r_info);
497 static int read_rela_reloc(struct section *sec, int i, struct reloc *reloc, unsigned int *symndx)
499 if (!gelf_getrela(sec->data, i, &reloc->rela)) {
500 WARN_ELF("gelf_getrela");
503 reloc->type = GELF_R_TYPE(reloc->rela.r_info);
504 reloc->addend = reloc->rela.r_addend;
505 reloc->offset = reloc->rela.r_offset;
506 *symndx = GELF_R_SYM(reloc->rela.r_info);
510 static int read_relocs(struct elf *elf)
516 unsigned long nr_reloc, max_reloc = 0, tot_reloc = 0;
518 list_for_each_entry(sec, &elf->sections, list) {
519 if ((sec->sh.sh_type != SHT_RELA) &&
520 (sec->sh.sh_type != SHT_REL))
523 sec->base = find_section_by_index(elf, sec->sh.sh_info);
525 WARN("can't find base section for reloc section %s",
530 sec->base->reloc = sec;
533 for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) {
534 reloc = malloc(sizeof(*reloc));
539 memset(reloc, 0, sizeof(*reloc));
540 switch (sec->sh.sh_type) {
542 if (read_rel_reloc(sec, i, reloc, &symndx))
546 if (read_rela_reloc(sec, i, reloc, &symndx))
554 reloc->sym = find_symbol_by_index(elf, symndx);
556 WARN("can't find reloc entry symbol %d for %s",
561 elf_add_reloc(elf, reloc);
564 max_reloc = max(max_reloc, nr_reloc);
565 tot_reloc += nr_reloc;
569 printf("max_reloc: %lu\n", max_reloc);
570 printf("tot_reloc: %lu\n", tot_reloc);
576 struct elf *elf_open_read(const char *name, int flags)
581 elf_version(EV_CURRENT);
583 elf = malloc(sizeof(*elf));
588 memset(elf, 0, offsetof(struct elf, sections));
590 INIT_LIST_HEAD(&elf->sections);
592 elf_hash_init(elf->symbol_hash);
593 elf_hash_init(elf->symbol_name_hash);
594 elf_hash_init(elf->section_hash);
595 elf_hash_init(elf->section_name_hash);
596 elf_hash_init(elf->reloc_hash);
598 elf->fd = open(name, flags);
600 fprintf(stderr, "objtool: Can't open '%s': %s\n",
601 name, strerror(errno));
605 if ((flags & O_ACCMODE) == O_RDONLY)
606 cmd = ELF_C_READ_MMAP;
607 else if ((flags & O_ACCMODE) == O_RDWR)
612 elf->elf = elf_begin(elf->fd, cmd, NULL);
614 WARN_ELF("elf_begin");
618 if (!gelf_getehdr(elf->elf, &elf->ehdr)) {
619 WARN_ELF("gelf_getehdr");
623 if (read_sections(elf))
626 if (read_symbols(elf))
629 if (read_relocs(elf))
639 struct section *elf_create_section(struct elf *elf, const char *name,
640 unsigned int sh_flags, size_t entsize, int nr)
642 struct section *sec, *shstrtab;
643 size_t size = entsize * nr;
647 sec = malloc(sizeof(*sec));
652 memset(sec, 0, sizeof(*sec));
654 INIT_LIST_HEAD(&sec->symbol_list);
655 INIT_LIST_HEAD(&sec->reloc_list);
657 s = elf_newscn(elf->elf);
659 WARN_ELF("elf_newscn");
663 sec->name = strdup(name);
669 sec->idx = elf_ndxscn(s);
673 sec->data = elf_newdata(s);
675 WARN_ELF("elf_newdata");
679 sec->data->d_size = size;
680 sec->data->d_align = 1;
683 sec->data->d_buf = malloc(size);
684 if (!sec->data->d_buf) {
688 memset(sec->data->d_buf, 0, size);
691 if (!gelf_getshdr(s, &sec->sh)) {
692 WARN_ELF("gelf_getshdr");
696 sec->sh.sh_size = size;
697 sec->sh.sh_entsize = entsize;
698 sec->sh.sh_type = SHT_PROGBITS;
699 sec->sh.sh_addralign = 1;
700 sec->sh.sh_flags = SHF_ALLOC | sh_flags;
703 /* Add section name to .shstrtab (or .strtab for Clang) */
704 shstrtab = find_section_by_name(elf, ".shstrtab");
706 shstrtab = find_section_by_name(elf, ".strtab");
708 WARN("can't find .shstrtab or .strtab section");
712 s = elf_getscn(elf->elf, shstrtab->idx);
714 WARN_ELF("elf_getscn");
718 data = elf_newdata(s);
720 WARN_ELF("elf_newdata");
724 data->d_buf = sec->name;
725 data->d_size = strlen(name) + 1;
728 sec->sh.sh_name = shstrtab->len;
730 shstrtab->len += strlen(name) + 1;
731 shstrtab->changed = true;
733 list_add_tail(&sec->list, &elf->sections);
734 elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
735 elf_hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
742 static struct section *elf_create_rel_reloc_section(struct elf *elf, struct section *base)
747 relocname = malloc(strlen(base->name) + strlen(".rel") + 1);
752 strcpy(relocname, ".rel");
753 strcat(relocname, base->name);
755 sec = elf_create_section(elf, relocname, 0, sizeof(GElf_Rel), 0);
763 sec->sh.sh_type = SHT_REL;
764 sec->sh.sh_addralign = 8;
765 sec->sh.sh_link = find_section_by_name(elf, ".symtab")->idx;
766 sec->sh.sh_info = base->idx;
767 sec->sh.sh_flags = SHF_INFO_LINK;
772 static struct section *elf_create_rela_reloc_section(struct elf *elf, struct section *base)
777 relocname = malloc(strlen(base->name) + strlen(".rela") + 1);
782 strcpy(relocname, ".rela");
783 strcat(relocname, base->name);
785 sec = elf_create_section(elf, relocname, 0, sizeof(GElf_Rela), 0);
793 sec->sh.sh_type = SHT_RELA;
794 sec->sh.sh_addralign = 8;
795 sec->sh.sh_link = find_section_by_name(elf, ".symtab")->idx;
796 sec->sh.sh_info = base->idx;
797 sec->sh.sh_flags = SHF_INFO_LINK;
802 struct section *elf_create_reloc_section(struct elf *elf,
803 struct section *base,
807 case SHT_REL: return elf_create_rel_reloc_section(elf, base);
808 case SHT_RELA: return elf_create_rela_reloc_section(elf, base);
809 default: return NULL;
813 static int elf_rebuild_rel_reloc_section(struct section *sec, int nr)
819 /* Allocate a buffer for relocations */
820 size = nr * sizeof(*relocs);
821 relocs = malloc(size);
827 sec->data->d_buf = relocs;
828 sec->data->d_size = size;
830 sec->sh.sh_size = size;
833 list_for_each_entry(reloc, &sec->reloc_list, list) {
834 relocs[idx].r_offset = reloc->offset;
835 relocs[idx].r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
842 static int elf_rebuild_rela_reloc_section(struct section *sec, int nr)
848 /* Allocate a buffer for relocations with addends */
849 size = nr * sizeof(*relocs);
850 relocs = malloc(size);
856 sec->data->d_buf = relocs;
857 sec->data->d_size = size;
859 sec->sh.sh_size = size;
862 list_for_each_entry(reloc, &sec->reloc_list, list) {
863 relocs[idx].r_offset = reloc->offset;
864 relocs[idx].r_addend = reloc->addend;
865 relocs[idx].r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
872 int elf_rebuild_reloc_section(struct elf *elf, struct section *sec)
881 list_for_each_entry(reloc, &sec->reloc_list, list)
884 switch (sec->sh.sh_type) {
885 case SHT_REL: return elf_rebuild_rel_reloc_section(sec, nr);
886 case SHT_RELA: return elf_rebuild_rela_reloc_section(sec, nr);
891 int elf_write_insn(struct elf *elf, struct section *sec,
892 unsigned long offset, unsigned int len,
895 Elf_Data *data = sec->data;
897 if (data->d_type != ELF_T_BYTE || data->d_off) {
898 WARN("write to unexpected data for section: %s", sec->name);
902 memcpy(data->d_buf + offset, insn, len);
903 elf_flagdata(data, ELF_C_SET, ELF_F_DIRTY);
910 int elf_write_reloc(struct elf *elf, struct reloc *reloc)
912 struct section *sec = reloc->sec;
914 if (sec->sh.sh_type == SHT_REL) {
915 reloc->rel.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
916 reloc->rel.r_offset = reloc->offset;
918 if (!gelf_update_rel(sec->data, reloc->idx, &reloc->rel)) {
919 WARN_ELF("gelf_update_rel");
923 reloc->rela.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
924 reloc->rela.r_addend = reloc->addend;
925 reloc->rela.r_offset = reloc->offset;
927 if (!gelf_update_rela(sec->data, reloc->idx, &reloc->rela)) {
928 WARN_ELF("gelf_update_rela");
938 int elf_write(struct elf *elf)
943 /* Update section headers for changed sections: */
944 list_for_each_entry(sec, &elf->sections, list) {
946 s = elf_getscn(elf->elf, sec->idx);
948 WARN_ELF("elf_getscn");
951 if (!gelf_update_shdr(s, &sec->sh)) {
952 WARN_ELF("gelf_update_shdr");
956 sec->changed = false;
960 /* Make sure the new section header entries get updated properly. */
961 elf_flagelf(elf->elf, ELF_C_SET, ELF_F_DIRTY);
963 /* Write all changes to the file. */
964 if (elf_update(elf->elf, ELF_C_WRITE) < 0) {
965 WARN_ELF("elf_update");
969 elf->changed = false;
974 void elf_close(struct elf *elf)
976 struct section *sec, *tmpsec;
977 struct symbol *sym, *tmpsym;
978 struct reloc *reloc, *tmpreloc;
986 list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
987 list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) {
988 list_del(&sym->list);
989 hash_del(&sym->hash);
992 list_for_each_entry_safe(reloc, tmpreloc, &sec->reloc_list, list) {
993 list_del(&reloc->list);
994 hash_del(&reloc->hash);
997 list_del(&sec->list);