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>
18 #include <objtool/builtin.h>
20 #include <objtool/elf.h>
21 #include <objtool/warn.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 static int read_sections(struct elf *elf)
218 size_t shstrndx, sections_nr;
221 if (elf_getshdrnum(elf->elf, §ions_nr)) {
222 WARN_ELF("elf_getshdrnum");
226 if (elf_getshdrstrndx(elf->elf, &shstrndx)) {
227 WARN_ELF("elf_getshdrstrndx");
231 for (i = 0; i < sections_nr; i++) {
232 sec = malloc(sizeof(*sec));
237 memset(sec, 0, sizeof(*sec));
239 INIT_LIST_HEAD(&sec->symbol_list);
240 INIT_LIST_HEAD(&sec->reloc_list);
242 s = elf_getscn(elf->elf, i);
244 WARN_ELF("elf_getscn");
248 sec->idx = elf_ndxscn(s);
250 if (!gelf_getshdr(s, &sec->sh)) {
251 WARN_ELF("gelf_getshdr");
255 sec->name = elf_strptr(elf->elf, shstrndx, sec->sh.sh_name);
257 WARN_ELF("elf_strptr");
261 if (sec->sh.sh_size != 0) {
262 sec->data = elf_getdata(s, NULL);
264 WARN_ELF("elf_getdata");
267 if (sec->data->d_off != 0 ||
268 sec->data->d_size != sec->sh.sh_size) {
269 WARN("unexpected data attributes for %s",
274 sec->len = sec->sh.sh_size;
276 list_add_tail(&sec->list, &elf->sections);
277 elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
278 elf_hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
282 printf("nr_sections: %lu\n", (unsigned long)sections_nr);
284 /* sanity check, one more call to elf_nextscn() should return NULL */
285 if (elf_nextscn(elf->elf, s)) {
286 WARN("section entry mismatch");
293 static void elf_add_symbol(struct elf *elf, struct symbol *sym)
295 struct list_head *entry;
296 struct rb_node *pnode;
298 sym->type = GELF_ST_TYPE(sym->sym.st_info);
299 sym->bind = GELF_ST_BIND(sym->sym.st_info);
301 sym->offset = sym->sym.st_value;
302 sym->len = sym->sym.st_size;
304 rb_add(&sym->node, &sym->sec->symbol_tree, symbol_to_offset);
305 pnode = rb_prev(&sym->node);
307 entry = &rb_entry(pnode, struct symbol, node)->list;
309 entry = &sym->sec->symbol_list;
310 list_add(&sym->list, entry);
311 elf_hash_add(elf->symbol_hash, &sym->hash, sym->idx);
312 elf_hash_add(elf->symbol_name_hash, &sym->name_hash, str_hash(sym->name));
315 * Don't store empty STT_NOTYPE symbols in the rbtree. They
316 * can exist within a function, confusing the sorting.
319 rb_erase(&sym->node, &sym->sec->symbol_tree);
322 static int read_symbols(struct elf *elf)
324 struct section *symtab, *symtab_shndx, *sec;
325 struct symbol *sym, *pfunc;
328 Elf_Data *shndx_data = NULL;
331 symtab = find_section_by_name(elf, ".symtab");
334 * A missing symbol table is actually possible if it's an empty
335 * .o file. This can happen for thunk_64.o.
340 symtab_shndx = find_section_by_name(elf, ".symtab_shndx");
342 shndx_data = symtab_shndx->data;
344 symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize;
346 for (i = 0; i < symbols_nr; i++) {
347 sym = malloc(sizeof(*sym));
352 memset(sym, 0, sizeof(*sym));
357 if (!gelf_getsymshndx(symtab->data, shndx_data, i, &sym->sym,
359 WARN_ELF("gelf_getsymshndx");
363 sym->name = elf_strptr(elf->elf, symtab->sh.sh_link,
366 WARN_ELF("elf_strptr");
370 if ((sym->sym.st_shndx > SHN_UNDEF &&
371 sym->sym.st_shndx < SHN_LORESERVE) ||
372 (shndx_data && sym->sym.st_shndx == SHN_XINDEX)) {
373 if (sym->sym.st_shndx != SHN_XINDEX)
374 shndx = sym->sym.st_shndx;
376 sym->sec = find_section_by_index(elf, shndx);
378 WARN("couldn't find section for symbol %s",
382 if (GELF_ST_TYPE(sym->sym.st_info) == STT_SECTION) {
383 sym->name = sym->sec->name;
387 sym->sec = find_section_by_index(elf, 0);
389 elf_add_symbol(elf, sym);
393 printf("nr_symbols: %lu\n", (unsigned long)symbols_nr);
395 /* Create parent/child links for any cold subfunctions */
396 list_for_each_entry(sec, &elf->sections, list) {
397 list_for_each_entry(sym, &sec->symbol_list, list) {
398 char pname[MAX_NAME_LEN + 1];
400 if (sym->type != STT_FUNC)
403 if (sym->pfunc == NULL)
406 if (sym->cfunc == NULL)
409 coldstr = strstr(sym->name, ".cold");
413 pnamelen = coldstr - sym->name;
414 if (pnamelen > MAX_NAME_LEN) {
415 WARN("%s(): parent function name exceeds maximum length of %d characters",
416 sym->name, MAX_NAME_LEN);
420 strncpy(pname, sym->name, pnamelen);
421 pname[pnamelen] = '\0';
422 pfunc = find_symbol_by_name(elf, pname);
425 WARN("%s(): can't find parent function",
434 * Unfortunately, -fnoreorder-functions puts the child
435 * inside the parent. Remove the overlap so we can
436 * have sane assumptions.
438 * Note that pfunc->len now no longer matches
439 * pfunc->sym.st_size.
441 if (sym->sec == pfunc->sec &&
442 sym->offset >= pfunc->offset &&
443 sym->offset + sym->len == pfunc->offset + pfunc->len) {
444 pfunc->len -= sym->len;
456 static struct section *elf_create_reloc_section(struct elf *elf,
457 struct section *base,
460 int elf_add_reloc(struct elf *elf, struct section *sec, unsigned long offset,
461 unsigned int type, struct symbol *sym, int addend)
465 if (!sec->reloc && !elf_create_reloc_section(elf, sec, SHT_RELA))
468 reloc = malloc(sizeof(*reloc));
473 memset(reloc, 0, sizeof(*reloc));
475 reloc->sec = sec->reloc;
476 reloc->offset = offset;
479 reloc->addend = addend;
481 list_add_tail(&reloc->list, &sec->reloc->reloc_list);
482 elf_hash_add(elf->reloc_hash, &reloc->hash, reloc_hash(reloc));
484 sec->reloc->changed = true;
489 int elf_add_reloc_to_insn(struct elf *elf, struct section *sec,
490 unsigned long offset, unsigned int type,
491 struct section *insn_sec, unsigned long insn_off)
502 * The Clang assembler strips section symbols, so we have to
503 * reference the function symbol instead:
505 sym = find_symbol_containing(insn_sec, insn_off);
508 * Hack alert. This happens when we need to reference
509 * the NOP pad insn immediately after the function.
511 sym = find_symbol_containing(insn_sec, insn_off - 1);
515 WARN("can't find symbol containing %s+0x%lx", insn_sec->name, insn_off);
519 addend = insn_off - sym->offset;
522 return elf_add_reloc(elf, sec, offset, type, sym, addend);
525 static int read_rel_reloc(struct section *sec, int i, struct reloc *reloc, unsigned int *symndx)
527 if (!gelf_getrel(sec->data, i, &reloc->rel)) {
528 WARN_ELF("gelf_getrel");
531 reloc->type = GELF_R_TYPE(reloc->rel.r_info);
533 reloc->offset = reloc->rel.r_offset;
534 *symndx = GELF_R_SYM(reloc->rel.r_info);
538 static int read_rela_reloc(struct section *sec, int i, struct reloc *reloc, unsigned int *symndx)
540 if (!gelf_getrela(sec->data, i, &reloc->rela)) {
541 WARN_ELF("gelf_getrela");
544 reloc->type = GELF_R_TYPE(reloc->rela.r_info);
545 reloc->addend = reloc->rela.r_addend;
546 reloc->offset = reloc->rela.r_offset;
547 *symndx = GELF_R_SYM(reloc->rela.r_info);
551 static int read_relocs(struct elf *elf)
557 unsigned long nr_reloc, max_reloc = 0, tot_reloc = 0;
559 list_for_each_entry(sec, &elf->sections, list) {
560 if ((sec->sh.sh_type != SHT_RELA) &&
561 (sec->sh.sh_type != SHT_REL))
564 sec->base = find_section_by_index(elf, sec->sh.sh_info);
566 WARN("can't find base section for reloc section %s",
571 sec->base->reloc = sec;
574 for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) {
575 reloc = malloc(sizeof(*reloc));
580 memset(reloc, 0, sizeof(*reloc));
581 switch (sec->sh.sh_type) {
583 if (read_rel_reloc(sec, i, reloc, &symndx))
587 if (read_rela_reloc(sec, i, reloc, &symndx))
595 reloc->sym = find_symbol_by_index(elf, symndx);
597 WARN("can't find reloc entry symbol %d for %s",
602 list_add_tail(&reloc->list, &sec->reloc_list);
603 elf_hash_add(elf->reloc_hash, &reloc->hash, reloc_hash(reloc));
607 max_reloc = max(max_reloc, nr_reloc);
608 tot_reloc += nr_reloc;
612 printf("max_reloc: %lu\n", max_reloc);
613 printf("tot_reloc: %lu\n", tot_reloc);
619 struct elf *elf_open_read(const char *name, int flags)
624 elf_version(EV_CURRENT);
626 elf = malloc(sizeof(*elf));
631 memset(elf, 0, offsetof(struct elf, sections));
633 INIT_LIST_HEAD(&elf->sections);
635 elf_hash_init(elf->symbol_hash);
636 elf_hash_init(elf->symbol_name_hash);
637 elf_hash_init(elf->section_hash);
638 elf_hash_init(elf->section_name_hash);
639 elf_hash_init(elf->reloc_hash);
641 elf->fd = open(name, flags);
643 fprintf(stderr, "objtool: Can't open '%s': %s\n",
644 name, strerror(errno));
648 if ((flags & O_ACCMODE) == O_RDONLY)
649 cmd = ELF_C_READ_MMAP;
650 else if ((flags & O_ACCMODE) == O_RDWR)
655 elf->elf = elf_begin(elf->fd, cmd, NULL);
657 WARN_ELF("elf_begin");
661 if (!gelf_getehdr(elf->elf, &elf->ehdr)) {
662 WARN_ELF("gelf_getehdr");
666 if (read_sections(elf))
669 if (read_symbols(elf))
672 if (read_relocs(elf))
682 static int elf_add_string(struct elf *elf, struct section *strtab, char *str)
689 strtab = find_section_by_name(elf, ".strtab");
691 WARN("can't find .strtab section");
695 s = elf_getscn(elf->elf, strtab->idx);
697 WARN_ELF("elf_getscn");
701 data = elf_newdata(s);
703 WARN_ELF("elf_newdata");
708 data->d_size = strlen(str) + 1;
712 strtab->len += data->d_size;
713 strtab->changed = true;
718 struct symbol *elf_create_undef_symbol(struct elf *elf, const char *name)
720 struct section *symtab;
725 sym = malloc(sizeof(*sym));
730 memset(sym, 0, sizeof(*sym));
732 sym->name = strdup(name);
734 sym->sym.st_name = elf_add_string(elf, NULL, sym->name);
735 if (sym->sym.st_name == -1)
738 sym->sym.st_info = GELF_ST_INFO(STB_GLOBAL, STT_NOTYPE);
744 symtab = find_section_by_name(elf, ".symtab");
746 WARN("can't find .symtab");
750 s = elf_getscn(elf->elf, symtab->idx);
752 WARN_ELF("elf_getscn");
756 data = elf_newdata(s);
758 WARN_ELF("elf_newdata");
762 data->d_buf = &sym->sym;
763 data->d_size = sizeof(sym->sym);
766 sym->idx = symtab->len / sizeof(sym->sym);
768 symtab->len += data->d_size;
769 symtab->changed = true;
771 sym->sec = find_section_by_index(elf, 0);
773 elf_add_symbol(elf, sym);
778 struct section *elf_create_section(struct elf *elf, const char *name,
779 unsigned int sh_flags, size_t entsize, int nr)
781 struct section *sec, *shstrtab;
782 size_t size = entsize * nr;
785 sec = malloc(sizeof(*sec));
790 memset(sec, 0, sizeof(*sec));
792 INIT_LIST_HEAD(&sec->symbol_list);
793 INIT_LIST_HEAD(&sec->reloc_list);
795 s = elf_newscn(elf->elf);
797 WARN_ELF("elf_newscn");
801 sec->name = strdup(name);
807 sec->idx = elf_ndxscn(s);
811 sec->data = elf_newdata(s);
813 WARN_ELF("elf_newdata");
817 sec->data->d_size = size;
818 sec->data->d_align = 1;
821 sec->data->d_buf = malloc(size);
822 if (!sec->data->d_buf) {
826 memset(sec->data->d_buf, 0, size);
829 if (!gelf_getshdr(s, &sec->sh)) {
830 WARN_ELF("gelf_getshdr");
834 sec->sh.sh_size = size;
835 sec->sh.sh_entsize = entsize;
836 sec->sh.sh_type = SHT_PROGBITS;
837 sec->sh.sh_addralign = 1;
838 sec->sh.sh_flags = SHF_ALLOC | sh_flags;
840 /* Add section name to .shstrtab (or .strtab for Clang) */
841 shstrtab = find_section_by_name(elf, ".shstrtab");
843 shstrtab = find_section_by_name(elf, ".strtab");
845 WARN("can't find .shstrtab or .strtab section");
848 sec->sh.sh_name = elf_add_string(elf, shstrtab, sec->name);
849 if (sec->sh.sh_name == -1)
852 list_add_tail(&sec->list, &elf->sections);
853 elf_hash_add(elf->section_hash, &sec->hash, sec->idx);
854 elf_hash_add(elf->section_name_hash, &sec->name_hash, str_hash(sec->name));
861 static struct section *elf_create_rel_reloc_section(struct elf *elf, struct section *base)
866 relocname = malloc(strlen(base->name) + strlen(".rel") + 1);
871 strcpy(relocname, ".rel");
872 strcat(relocname, base->name);
874 sec = elf_create_section(elf, relocname, 0, sizeof(GElf_Rel), 0);
882 sec->sh.sh_type = SHT_REL;
883 sec->sh.sh_addralign = 8;
884 sec->sh.sh_link = find_section_by_name(elf, ".symtab")->idx;
885 sec->sh.sh_info = base->idx;
886 sec->sh.sh_flags = SHF_INFO_LINK;
891 static struct section *elf_create_rela_reloc_section(struct elf *elf, struct section *base)
896 relocname = malloc(strlen(base->name) + strlen(".rela") + 1);
901 strcpy(relocname, ".rela");
902 strcat(relocname, base->name);
904 sec = elf_create_section(elf, relocname, 0, sizeof(GElf_Rela), 0);
912 sec->sh.sh_type = SHT_RELA;
913 sec->sh.sh_addralign = 8;
914 sec->sh.sh_link = find_section_by_name(elf, ".symtab")->idx;
915 sec->sh.sh_info = base->idx;
916 sec->sh.sh_flags = SHF_INFO_LINK;
921 static struct section *elf_create_reloc_section(struct elf *elf,
922 struct section *base,
926 case SHT_REL: return elf_create_rel_reloc_section(elf, base);
927 case SHT_RELA: return elf_create_rela_reloc_section(elf, base);
928 default: return NULL;
932 static int elf_rebuild_rel_reloc_section(struct section *sec, int nr)
938 /* Allocate a buffer for relocations */
939 size = nr * sizeof(GElf_Rel);
946 sec->data->d_buf = buf;
947 sec->data->d_size = size;
948 sec->data->d_type = ELF_T_REL;
950 sec->sh.sh_size = size;
953 list_for_each_entry(reloc, &sec->reloc_list, list) {
954 reloc->rel.r_offset = reloc->offset;
955 reloc->rel.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
956 gelf_update_rel(sec->data, idx, &reloc->rel);
963 static int elf_rebuild_rela_reloc_section(struct section *sec, int nr)
969 /* Allocate a buffer for relocations with addends */
970 size = nr * sizeof(GElf_Rela);
977 sec->data->d_buf = buf;
978 sec->data->d_size = size;
979 sec->data->d_type = ELF_T_RELA;
981 sec->sh.sh_size = size;
984 list_for_each_entry(reloc, &sec->reloc_list, list) {
985 reloc->rela.r_offset = reloc->offset;
986 reloc->rela.r_addend = reloc->addend;
987 reloc->rela.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
988 gelf_update_rela(sec->data, idx, &reloc->rela);
995 static int elf_rebuild_reloc_section(struct elf *elf, struct section *sec)
1001 list_for_each_entry(reloc, &sec->reloc_list, list)
1004 switch (sec->sh.sh_type) {
1005 case SHT_REL: return elf_rebuild_rel_reloc_section(sec, nr);
1006 case SHT_RELA: return elf_rebuild_rela_reloc_section(sec, nr);
1011 int elf_write_insn(struct elf *elf, struct section *sec,
1012 unsigned long offset, unsigned int len,
1015 Elf_Data *data = sec->data;
1017 if (data->d_type != ELF_T_BYTE || data->d_off) {
1018 WARN("write to unexpected data for section: %s", sec->name);
1022 memcpy(data->d_buf + offset, insn, len);
1023 elf_flagdata(data, ELF_C_SET, ELF_F_DIRTY);
1025 elf->changed = true;
1030 int elf_write_reloc(struct elf *elf, struct reloc *reloc)
1032 struct section *sec = reloc->sec;
1034 if (sec->sh.sh_type == SHT_REL) {
1035 reloc->rel.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
1036 reloc->rel.r_offset = reloc->offset;
1038 if (!gelf_update_rel(sec->data, reloc->idx, &reloc->rel)) {
1039 WARN_ELF("gelf_update_rel");
1043 reloc->rela.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
1044 reloc->rela.r_addend = reloc->addend;
1045 reloc->rela.r_offset = reloc->offset;
1047 if (!gelf_update_rela(sec->data, reloc->idx, &reloc->rela)) {
1048 WARN_ELF("gelf_update_rela");
1053 elf->changed = true;
1058 int elf_write(struct elf *elf)
1060 struct section *sec;
1063 /* Update changed relocation sections and section headers: */
1064 list_for_each_entry(sec, &elf->sections, list) {
1067 elf_rebuild_reloc_section(elf, sec)) {
1068 WARN("elf_rebuild_reloc_section");
1072 s = elf_getscn(elf->elf, sec->idx);
1074 WARN_ELF("elf_getscn");
1077 if (!gelf_update_shdr(s, &sec->sh)) {
1078 WARN_ELF("gelf_update_shdr");
1082 sec->changed = false;
1083 elf->changed = true;
1087 /* Make sure the new section header entries get updated properly. */
1088 elf_flagelf(elf->elf, ELF_C_SET, ELF_F_DIRTY);
1090 /* Write all changes to the file. */
1091 if (elf_update(elf->elf, ELF_C_WRITE) < 0) {
1092 WARN_ELF("elf_update");
1096 elf->changed = false;
1101 void elf_close(struct elf *elf)
1103 struct section *sec, *tmpsec;
1104 struct symbol *sym, *tmpsym;
1105 struct reloc *reloc, *tmpreloc;
1113 list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
1114 list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) {
1115 list_del(&sym->list);
1116 hash_del(&sym->hash);
1119 list_for_each_entry_safe(reloc, tmpreloc, &sec->reloc_list, list) {
1120 list_del(&reloc->list);
1121 hash_del(&reloc->hash);
1124 list_del(&sec->list);