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 void rb_add(struct rb_root
*tree
, struct rb_node
*node
,
31 int (*cmp
)(struct rb_node
*, const struct rb_node
*))
33 struct rb_node
**link
= &tree
->rb_node
;
34 struct rb_node
*parent
= NULL
;
38 if (cmp(node
, parent
) < 0)
39 link
= &parent
->rb_left
;
41 link
= &parent
->rb_right
;
44 rb_link_node(node
, parent
, link
);
45 rb_insert_color(node
, tree
);
48 static struct rb_node
*rb_find_first(struct rb_root
*tree
, const void *key
,
49 int (*cmp
)(const void *key
, const struct rb_node
*))
51 struct rb_node
*node
= tree
->rb_node
;
52 struct rb_node
*match
= NULL
;
55 int c
= cmp(key
, node
);
61 node
= node
->rb_right
;
68 static struct rb_node
*rb_next_match(struct rb_node
*node
, const void *key
,
69 int (*cmp
)(const void *key
, const struct rb_node
*))
72 if (node
&& cmp(key
, node
))
77 #define rb_for_each(tree, node, key, cmp) \
78 for ((node) = rb_find_first((tree), (key), (cmp)); \
79 (node); (node) = rb_next_match((node), (key), (cmp)))
81 static int symbol_to_offset(struct rb_node
*a
, const struct rb_node
*b
)
83 struct symbol
*sa
= rb_entry(a
, struct symbol
, node
);
84 struct symbol
*sb
= rb_entry(b
, struct symbol
, node
);
86 if (sa
->offset
< sb
->offset
)
88 if (sa
->offset
> sb
->offset
)
91 if (sa
->len
< sb
->len
)
93 if (sa
->len
> sb
->len
)
101 static int symbol_by_offset(const void *key
, const struct rb_node
*node
)
103 const struct symbol
*s
= rb_entry(node
, struct symbol
, node
);
104 const unsigned long *o
= key
;
108 if (*o
>= s
->offset
+ s
->len
)
114 struct section
*find_section_by_name(struct elf
*elf
, const char *name
)
118 hash_for_each_possible(elf
->section_name_hash
, sec
, name_hash
, str_hash(name
))
119 if (!strcmp(sec
->name
, name
))
125 static struct section
*find_section_by_index(struct elf
*elf
,
130 hash_for_each_possible(elf
->section_hash
, sec
, hash
, idx
)
137 static struct symbol
*find_symbol_by_index(struct elf
*elf
, unsigned int idx
)
141 hash_for_each_possible(elf
->symbol_hash
, sym
, hash
, idx
)
148 struct symbol
*find_symbol_by_offset(struct section
*sec
, unsigned long offset
)
150 struct rb_node
*node
;
152 rb_for_each(&sec
->symbol_tree
, node
, &offset
, symbol_by_offset
) {
153 struct symbol
*s
= rb_entry(node
, struct symbol
, node
);
155 if (s
->offset
== offset
&& s
->type
!= STT_SECTION
)
162 struct symbol
*find_func_by_offset(struct section
*sec
, unsigned long offset
)
164 struct rb_node
*node
;
166 rb_for_each(&sec
->symbol_tree
, node
, &offset
, symbol_by_offset
) {
167 struct symbol
*s
= rb_entry(node
, struct symbol
, node
);
169 if (s
->offset
== offset
&& s
->type
== STT_FUNC
)
176 struct symbol
*find_symbol_containing(struct section
*sec
, unsigned long offset
)
178 struct rb_node
*node
;
180 rb_for_each(&sec
->symbol_tree
, node
, &offset
, symbol_by_offset
) {
181 struct symbol
*s
= rb_entry(node
, struct symbol
, node
);
183 if (s
->type
!= STT_SECTION
)
190 struct symbol
*find_func_containing(struct section
*sec
, unsigned long offset
)
192 struct rb_node
*node
;
194 rb_for_each(&sec
->symbol_tree
, node
, &offset
, symbol_by_offset
) {
195 struct symbol
*s
= rb_entry(node
, struct symbol
, node
);
197 if (s
->type
== STT_FUNC
)
204 struct symbol
*find_symbol_by_name(struct elf
*elf
, const char *name
)
208 hash_for_each_possible(elf
->symbol_name_hash
, sym
, name_hash
, str_hash(name
))
209 if (!strcmp(sym
->name
, name
))
215 struct rela
*find_rela_by_dest_range(struct elf
*elf
, struct section
*sec
,
216 unsigned long offset
, unsigned int len
)
218 struct rela
*rela
, *r
= NULL
;
226 for_offset_range(o
, offset
, offset
+ len
) {
227 hash_for_each_possible(elf
->rela_hash
, rela
, hash
,
228 sec_offset_hash(sec
, o
)) {
229 if (rela
->sec
!= sec
)
232 if (rela
->offset
>= offset
&& rela
->offset
< offset
+ len
) {
233 if (!r
|| rela
->offset
< r
->offset
)
244 struct rela
*find_rela_by_dest(struct elf
*elf
, struct section
*sec
, unsigned long offset
)
246 return find_rela_by_dest_range(elf
, sec
, offset
, 1);
249 static int read_sections(struct elf
*elf
)
253 size_t shstrndx
, sections_nr
;
256 if (elf_getshdrnum(elf
->elf
, §ions_nr
)) {
257 WARN_ELF("elf_getshdrnum");
261 if (elf_getshdrstrndx(elf
->elf
, &shstrndx
)) {
262 WARN_ELF("elf_getshdrstrndx");
266 for (i
= 0; i
< sections_nr
; i
++) {
267 sec
= malloc(sizeof(*sec
));
272 memset(sec
, 0, sizeof(*sec
));
274 INIT_LIST_HEAD(&sec
->symbol_list
);
275 INIT_LIST_HEAD(&sec
->rela_list
);
277 s
= elf_getscn(elf
->elf
, i
);
279 WARN_ELF("elf_getscn");
283 sec
->idx
= elf_ndxscn(s
);
285 if (!gelf_getshdr(s
, &sec
->sh
)) {
286 WARN_ELF("gelf_getshdr");
290 sec
->name
= elf_strptr(elf
->elf
, shstrndx
, sec
->sh
.sh_name
);
292 WARN_ELF("elf_strptr");
296 if (sec
->sh
.sh_size
!= 0) {
297 sec
->data
= elf_getdata(s
, NULL
);
299 WARN_ELF("elf_getdata");
302 if (sec
->data
->d_off
!= 0 ||
303 sec
->data
->d_size
!= sec
->sh
.sh_size
) {
304 WARN("unexpected data attributes for %s",
309 sec
->len
= sec
->sh
.sh_size
;
311 list_add_tail(&sec
->list
, &elf
->sections
);
312 hash_add(elf
->section_hash
, &sec
->hash
, sec
->idx
);
313 hash_add(elf
->section_name_hash
, &sec
->name_hash
, str_hash(sec
->name
));
317 printf("nr_sections: %lu\n", (unsigned long)sections_nr
);
319 /* sanity check, one more call to elf_nextscn() should return NULL */
320 if (elf_nextscn(elf
->elf
, s
)) {
321 WARN("section entry mismatch");
328 static int read_symbols(struct elf
*elf
)
330 struct section
*symtab
, *sec
;
331 struct symbol
*sym
, *pfunc
;
332 struct list_head
*entry
;
333 struct rb_node
*pnode
;
337 symtab
= find_section_by_name(elf
, ".symtab");
339 WARN("missing symbol table");
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_getsym(symtab
->data
, i
, &sym
->sym
)) {
357 WARN_ELF("gelf_getsym");
361 sym
->name
= elf_strptr(elf
->elf
, symtab
->sh
.sh_link
,
364 WARN_ELF("elf_strptr");
368 sym
->type
= GELF_ST_TYPE(sym
->sym
.st_info
);
369 sym
->bind
= GELF_ST_BIND(sym
->sym
.st_info
);
371 if (sym
->sym
.st_shndx
> SHN_UNDEF
&&
372 sym
->sym
.st_shndx
< SHN_LORESERVE
) {
373 sym
->sec
= find_section_by_index(elf
,
376 WARN("couldn't find section for symbol %s",
380 if (sym
->type
== STT_SECTION
) {
381 sym
->name
= sym
->sec
->name
;
385 sym
->sec
= find_section_by_index(elf
, 0);
387 sym
->offset
= sym
->sym
.st_value
;
388 sym
->len
= sym
->sym
.st_size
;
390 rb_add(&sym
->sec
->symbol_tree
, &sym
->node
, symbol_to_offset
);
391 pnode
= rb_prev(&sym
->node
);
393 entry
= &rb_entry(pnode
, struct symbol
, node
)->list
;
395 entry
= &sym
->sec
->symbol_list
;
396 list_add(&sym
->list
, entry
);
397 hash_add(elf
->symbol_hash
, &sym
->hash
, sym
->idx
);
398 hash_add(elf
->symbol_name_hash
, &sym
->name_hash
, str_hash(sym
->name
));
402 printf("nr_symbols: %lu\n", (unsigned long)symbols_nr
);
404 /* Create parent/child links for any cold subfunctions */
405 list_for_each_entry(sec
, &elf
->sections
, list
) {
406 list_for_each_entry(sym
, &sec
->symbol_list
, list
) {
407 char pname
[MAX_NAME_LEN
+ 1];
409 if (sym
->type
!= STT_FUNC
)
411 sym
->pfunc
= sym
->cfunc
= sym
;
412 coldstr
= strstr(sym
->name
, ".cold");
416 pnamelen
= coldstr
- sym
->name
;
417 if (pnamelen
> MAX_NAME_LEN
) {
418 WARN("%s(): parent function name exceeds maximum length of %d characters",
419 sym
->name
, MAX_NAME_LEN
);
423 strncpy(pname
, sym
->name
, pnamelen
);
424 pname
[pnamelen
] = '\0';
425 pfunc
= find_symbol_by_name(elf
, pname
);
428 WARN("%s(): can't find parent function",
437 * Unfortunately, -fnoreorder-functions puts the child
438 * inside the parent. Remove the overlap so we can
439 * have sane assumptions.
441 * Note that pfunc->len now no longer matches
442 * pfunc->sym.st_size.
444 if (sym
->sec
== pfunc
->sec
&&
445 sym
->offset
>= pfunc
->offset
&&
446 sym
->offset
+ sym
->len
== pfunc
->offset
+ pfunc
->len
) {
447 pfunc
->len
-= sym
->len
;
459 static int read_relas(struct elf
*elf
)
465 unsigned long nr_rela
, max_rela
= 0, tot_rela
= 0;
467 list_for_each_entry(sec
, &elf
->sections
, list
) {
468 if (sec
->sh
.sh_type
!= SHT_RELA
)
471 sec
->base
= find_section_by_name(elf
, sec
->name
+ 5);
473 WARN("can't find base section for rela section %s",
478 sec
->base
->rela
= sec
;
481 for (i
= 0; i
< sec
->sh
.sh_size
/ sec
->sh
.sh_entsize
; i
++) {
482 rela
= malloc(sizeof(*rela
));
487 memset(rela
, 0, sizeof(*rela
));
489 if (!gelf_getrela(sec
->data
, i
, &rela
->rela
)) {
490 WARN_ELF("gelf_getrela");
494 rela
->type
= GELF_R_TYPE(rela
->rela
.r_info
);
495 rela
->addend
= rela
->rela
.r_addend
;
496 rela
->offset
= rela
->rela
.r_offset
;
497 symndx
= GELF_R_SYM(rela
->rela
.r_info
);
498 rela
->sym
= find_symbol_by_index(elf
, symndx
);
501 WARN("can't find rela entry symbol %d for %s",
506 list_add_tail(&rela
->list
, &sec
->rela_list
);
507 hash_add(elf
->rela_hash
, &rela
->hash
, rela_hash(rela
));
510 max_rela
= max(max_rela
, nr_rela
);
515 printf("max_rela: %lu\n", max_rela
);
516 printf("tot_rela: %lu\n", tot_rela
);
522 struct elf
*elf_read(const char *name
, int flags
)
527 elf_version(EV_CURRENT
);
529 elf
= malloc(sizeof(*elf
));
534 memset(elf
, 0, sizeof(*elf
));
536 hash_init(elf
->symbol_hash
);
537 hash_init(elf
->symbol_name_hash
);
538 hash_init(elf
->section_hash
);
539 hash_init(elf
->section_name_hash
);
540 hash_init(elf
->rela_hash
);
541 INIT_LIST_HEAD(&elf
->sections
);
543 elf
->fd
= open(name
, flags
);
545 fprintf(stderr
, "objtool: Can't open '%s': %s\n",
546 name
, strerror(errno
));
550 if ((flags
& O_ACCMODE
) == O_RDONLY
)
551 cmd
= ELF_C_READ_MMAP
;
552 else if ((flags
& O_ACCMODE
) == O_RDWR
)
557 elf
->elf
= elf_begin(elf
->fd
, cmd
, NULL
);
559 WARN_ELF("elf_begin");
563 if (!gelf_getehdr(elf
->elf
, &elf
->ehdr
)) {
564 WARN_ELF("gelf_getehdr");
568 if (read_sections(elf
))
571 if (read_symbols(elf
))
584 struct section
*elf_create_section(struct elf
*elf
, const char *name
,
585 size_t entsize
, int nr
)
587 struct section
*sec
, *shstrtab
;
588 size_t size
= entsize
* nr
;
592 sec
= malloc(sizeof(*sec
));
597 memset(sec
, 0, sizeof(*sec
));
599 INIT_LIST_HEAD(&sec
->symbol_list
);
600 INIT_LIST_HEAD(&sec
->rela_list
);
602 s
= elf_newscn(elf
->elf
);
604 WARN_ELF("elf_newscn");
608 sec
->name
= strdup(name
);
614 sec
->idx
= elf_ndxscn(s
);
618 sec
->data
= elf_newdata(s
);
620 WARN_ELF("elf_newdata");
624 sec
->data
->d_size
= size
;
625 sec
->data
->d_align
= 1;
628 sec
->data
->d_buf
= malloc(size
);
629 if (!sec
->data
->d_buf
) {
633 memset(sec
->data
->d_buf
, 0, size
);
636 if (!gelf_getshdr(s
, &sec
->sh
)) {
637 WARN_ELF("gelf_getshdr");
641 sec
->sh
.sh_size
= size
;
642 sec
->sh
.sh_entsize
= entsize
;
643 sec
->sh
.sh_type
= SHT_PROGBITS
;
644 sec
->sh
.sh_addralign
= 1;
645 sec
->sh
.sh_flags
= SHF_ALLOC
;
648 /* Add section name to .shstrtab (or .strtab for Clang) */
649 shstrtab
= find_section_by_name(elf
, ".shstrtab");
651 shstrtab
= find_section_by_name(elf
, ".strtab");
653 WARN("can't find .shstrtab or .strtab section");
657 s
= elf_getscn(elf
->elf
, shstrtab
->idx
);
659 WARN_ELF("elf_getscn");
663 data
= elf_newdata(s
);
665 WARN_ELF("elf_newdata");
669 data
->d_buf
= sec
->name
;
670 data
->d_size
= strlen(name
) + 1;
673 sec
->sh
.sh_name
= shstrtab
->len
;
675 shstrtab
->len
+= strlen(name
) + 1;
676 shstrtab
->changed
= true;
678 list_add_tail(&sec
->list
, &elf
->sections
);
679 hash_add(elf
->section_hash
, &sec
->hash
, sec
->idx
);
680 hash_add(elf
->section_name_hash
, &sec
->name_hash
, str_hash(sec
->name
));
685 struct section
*elf_create_rela_section(struct elf
*elf
, struct section
*base
)
690 relaname
= malloc(strlen(base
->name
) + strlen(".rela") + 1);
695 strcpy(relaname
, ".rela");
696 strcat(relaname
, base
->name
);
698 sec
= elf_create_section(elf
, relaname
, sizeof(GElf_Rela
), 0);
706 sec
->sh
.sh_type
= SHT_RELA
;
707 sec
->sh
.sh_addralign
= 8;
708 sec
->sh
.sh_link
= find_section_by_name(elf
, ".symtab")->idx
;
709 sec
->sh
.sh_info
= base
->idx
;
710 sec
->sh
.sh_flags
= SHF_INFO_LINK
;
715 int elf_rebuild_rela_section(struct section
*sec
)
718 int nr
, idx
= 0, size
;
722 list_for_each_entry(rela
, &sec
->rela_list
, list
)
725 size
= nr
* sizeof(*relas
);
726 relas
= malloc(size
);
732 sec
->data
->d_buf
= relas
;
733 sec
->data
->d_size
= size
;
735 sec
->sh
.sh_size
= size
;
738 list_for_each_entry(rela
, &sec
->rela_list
, list
) {
739 relas
[idx
].r_offset
= rela
->offset
;
740 relas
[idx
].r_addend
= rela
->addend
;
741 relas
[idx
].r_info
= GELF_R_INFO(rela
->sym
->idx
, rela
->type
);
748 int elf_write(struct elf
*elf
)
753 /* Update section headers for changed sections: */
754 list_for_each_entry(sec
, &elf
->sections
, list
) {
756 s
= elf_getscn(elf
->elf
, sec
->idx
);
758 WARN_ELF("elf_getscn");
761 if (!gelf_update_shdr(s
, &sec
->sh
)) {
762 WARN_ELF("gelf_update_shdr");
768 /* Make sure the new section header entries get updated properly. */
769 elf_flagelf(elf
->elf
, ELF_C_SET
, ELF_F_DIRTY
);
771 /* Write all changes to the file. */
772 if (elf_update(elf
->elf
, ELF_C_WRITE
) < 0) {
773 WARN_ELF("elf_update");
780 void elf_close(struct elf
*elf
)
782 struct section
*sec
, *tmpsec
;
783 struct symbol
*sym
, *tmpsym
;
784 struct rela
*rela
, *tmprela
;
792 list_for_each_entry_safe(sec
, tmpsec
, &elf
->sections
, list
) {
793 list_for_each_entry_safe(sym
, tmpsym
, &sec
->symbol_list
, list
) {
794 list_del(&sym
->list
);
795 hash_del(&sym
->hash
);
798 list_for_each_entry_safe(rela
, tmprela
, &sec
->rela_list
, list
) {
799 list_del(&rela
->list
);
800 hash_del(&rela
->hash
);
803 list_del(&sec
->list
);