1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * elf.c - ELF access library 4 * 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> 8 */ 9 10 #include <sys/types.h> 11 #include <sys/stat.h> 12 #include <fcntl.h> 13 #include <stdio.h> 14 #include <stdlib.h> 15 #include <string.h> 16 #include <unistd.h> 17 #include <errno.h> 18 #include "builtin.h" 19 20 #include "elf.h" 21 #include "warn.h" 22 23 #define MAX_NAME_LEN 128 24 25 static inline u32 str_hash(const char *str) 26 { 27 return jhash(str, strlen(str), 0); 28 } 29 30 static void rb_add(struct rb_root *tree, struct rb_node *node, 31 int (*cmp)(struct rb_node *, const struct rb_node *)) 32 { 33 struct rb_node **link = &tree->rb_node; 34 struct rb_node *parent = NULL; 35 36 while (*link) { 37 parent = *link; 38 if (cmp(node, parent) < 0) 39 link = &parent->rb_left; 40 else 41 link = &parent->rb_right; 42 } 43 44 rb_link_node(node, parent, link); 45 rb_insert_color(node, tree); 46 } 47 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 *)) 50 { 51 struct rb_node *node = tree->rb_node; 52 struct rb_node *match = NULL; 53 54 while (node) { 55 int c = cmp(key, node); 56 if (c <= 0) { 57 if (!c) 58 match = node; 59 node = node->rb_left; 60 } else if (c > 0) { 61 node = node->rb_right; 62 } 63 } 64 65 return match; 66 } 67 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 *)) 70 { 71 node = rb_next(node); 72 if (node && cmp(key, node)) 73 node = NULL; 74 return node; 75 } 76 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))) 80 81 static int symbol_to_offset(struct rb_node *a, const struct rb_node *b) 82 { 83 struct symbol *sa = rb_entry(a, struct symbol, node); 84 struct symbol *sb = rb_entry(b, struct symbol, node); 85 86 if (sa->offset < sb->offset) 87 return -1; 88 if (sa->offset > sb->offset) 89 return 1; 90 91 if (sa->len < sb->len) 92 return -1; 93 if (sa->len > sb->len) 94 return 1; 95 96 sa->alias = sb; 97 98 return 0; 99 } 100 101 static int symbol_by_offset(const void *key, const struct rb_node *node) 102 { 103 const struct symbol *s = rb_entry(node, struct symbol, node); 104 const unsigned long *o = key; 105 106 if (*o < s->offset) 107 return -1; 108 if (*o > s->offset + s->len) 109 return 1; 110 111 return 0; 112 } 113 114 struct section *find_section_by_name(struct elf *elf, const char *name) 115 { 116 struct section *sec; 117 118 hash_for_each_possible(elf->section_name_hash, sec, name_hash, str_hash(name)) 119 if (!strcmp(sec->name, name)) 120 return sec; 121 122 return NULL; 123 } 124 125 static struct section *find_section_by_index(struct elf *elf, 126 unsigned int idx) 127 { 128 struct section *sec; 129 130 hash_for_each_possible(elf->section_hash, sec, hash, idx) 131 if (sec->idx == idx) 132 return sec; 133 134 return NULL; 135 } 136 137 static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx) 138 { 139 struct symbol *sym; 140 141 hash_for_each_possible(elf->symbol_hash, sym, hash, idx) 142 if (sym->idx == idx) 143 return sym; 144 145 return NULL; 146 } 147 148 struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset) 149 { 150 struct rb_node *node; 151 152 rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { 153 struct symbol *s = rb_entry(node, struct symbol, node); 154 155 if (s->offset == offset && s->type != STT_SECTION) 156 return s; 157 } 158 159 return NULL; 160 } 161 162 struct symbol *find_func_by_offset(struct section *sec, unsigned long offset) 163 { 164 struct rb_node *node; 165 166 rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { 167 struct symbol *s = rb_entry(node, struct symbol, node); 168 169 if (s->offset == offset && s->type == STT_FUNC) 170 return s; 171 } 172 173 return NULL; 174 } 175 176 struct symbol *find_symbol_containing(struct section *sec, unsigned long offset) 177 { 178 struct rb_node *node; 179 180 rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { 181 struct symbol *s = rb_entry(node, struct symbol, node); 182 183 if (s->type != STT_SECTION) 184 return s; 185 } 186 187 return NULL; 188 } 189 190 struct symbol *find_func_containing(struct section *sec, unsigned long offset) 191 { 192 struct rb_node *node; 193 194 rb_for_each(&sec->symbol_tree, node, &offset, symbol_by_offset) { 195 struct symbol *s = rb_entry(node, struct symbol, node); 196 197 if (s->type == STT_FUNC) 198 return s; 199 } 200 201 return NULL; 202 } 203 204 struct symbol *find_symbol_by_name(struct elf *elf, const char *name) 205 { 206 struct symbol *sym; 207 208 hash_for_each_possible(elf->symbol_name_hash, sym, name_hash, str_hash(name)) 209 if (!strcmp(sym->name, name)) 210 return sym; 211 212 return NULL; 213 } 214 215 struct rela *find_rela_by_dest_range(struct elf *elf, struct section *sec, 216 unsigned long offset, unsigned int len) 217 { 218 struct rela *rela, *r = NULL; 219 unsigned long o; 220 221 if (!sec->rela) 222 return NULL; 223 224 sec = sec->rela; 225 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) 230 continue; 231 232 if (rela->offset >= offset && rela->offset < offset + len) { 233 if (!r || rela->offset < r->offset) 234 r = rela; 235 } 236 } 237 if (r) 238 return r; 239 } 240 241 return NULL; 242 } 243 244 struct rela *find_rela_by_dest(struct elf *elf, struct section *sec, unsigned long offset) 245 { 246 return find_rela_by_dest_range(elf, sec, offset, 1); 247 } 248 249 static int read_sections(struct elf *elf) 250 { 251 Elf_Scn *s = NULL; 252 struct section *sec; 253 size_t shstrndx, sections_nr; 254 int i; 255 256 if (elf_getshdrnum(elf->elf, §ions_nr)) { 257 WARN_ELF("elf_getshdrnum"); 258 return -1; 259 } 260 261 if (elf_getshdrstrndx(elf->elf, &shstrndx)) { 262 WARN_ELF("elf_getshdrstrndx"); 263 return -1; 264 } 265 266 for (i = 0; i < sections_nr; i++) { 267 sec = malloc(sizeof(*sec)); 268 if (!sec) { 269 perror("malloc"); 270 return -1; 271 } 272 memset(sec, 0, sizeof(*sec)); 273 274 INIT_LIST_HEAD(&sec->symbol_list); 275 INIT_LIST_HEAD(&sec->rela_list); 276 277 s = elf_getscn(elf->elf, i); 278 if (!s) { 279 WARN_ELF("elf_getscn"); 280 return -1; 281 } 282 283 sec->idx = elf_ndxscn(s); 284 285 if (!gelf_getshdr(s, &sec->sh)) { 286 WARN_ELF("gelf_getshdr"); 287 return -1; 288 } 289 290 sec->name = elf_strptr(elf->elf, shstrndx, sec->sh.sh_name); 291 if (!sec->name) { 292 WARN_ELF("elf_strptr"); 293 return -1; 294 } 295 296 if (sec->sh.sh_size != 0) { 297 sec->data = elf_getdata(s, NULL); 298 if (!sec->data) { 299 WARN_ELF("elf_getdata"); 300 return -1; 301 } 302 if (sec->data->d_off != 0 || 303 sec->data->d_size != sec->sh.sh_size) { 304 WARN("unexpected data attributes for %s", 305 sec->name); 306 return -1; 307 } 308 } 309 sec->len = sec->sh.sh_size; 310 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)); 314 } 315 316 if (stats) 317 printf("nr_sections: %lu\n", (unsigned long)sections_nr); 318 319 /* sanity check, one more call to elf_nextscn() should return NULL */ 320 if (elf_nextscn(elf->elf, s)) { 321 WARN("section entry mismatch"); 322 return -1; 323 } 324 325 return 0; 326 } 327 328 static int read_symbols(struct elf *elf) 329 { 330 struct section *symtab, *sec; 331 struct symbol *sym, *pfunc; 332 struct list_head *entry; 333 struct rb_node *pnode; 334 int symbols_nr, i; 335 char *coldstr; 336 337 symtab = find_section_by_name(elf, ".symtab"); 338 if (!symtab) { 339 WARN("missing symbol table"); 340 return -1; 341 } 342 343 symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize; 344 345 for (i = 0; i < symbols_nr; i++) { 346 sym = malloc(sizeof(*sym)); 347 if (!sym) { 348 perror("malloc"); 349 return -1; 350 } 351 memset(sym, 0, sizeof(*sym)); 352 sym->alias = sym; 353 354 sym->idx = i; 355 356 if (!gelf_getsym(symtab->data, i, &sym->sym)) { 357 WARN_ELF("gelf_getsym"); 358 goto err; 359 } 360 361 sym->name = elf_strptr(elf->elf, symtab->sh.sh_link, 362 sym->sym.st_name); 363 if (!sym->name) { 364 WARN_ELF("elf_strptr"); 365 goto err; 366 } 367 368 sym->type = GELF_ST_TYPE(sym->sym.st_info); 369 sym->bind = GELF_ST_BIND(sym->sym.st_info); 370 371 if (sym->sym.st_shndx > SHN_UNDEF && 372 sym->sym.st_shndx < SHN_LORESERVE) { 373 sym->sec = find_section_by_index(elf, 374 sym->sym.st_shndx); 375 if (!sym->sec) { 376 WARN("couldn't find section for symbol %s", 377 sym->name); 378 goto err; 379 } 380 if (sym->type == STT_SECTION) { 381 sym->name = sym->sec->name; 382 sym->sec->sym = sym; 383 } 384 } else 385 sym->sec = find_section_by_index(elf, 0); 386 387 sym->offset = sym->sym.st_value; 388 sym->len = sym->sym.st_size; 389 390 rb_add(&sym->sec->symbol_tree, &sym->node, symbol_to_offset); 391 pnode = rb_prev(&sym->node); 392 if (pnode) 393 entry = &rb_entry(pnode, struct symbol, node)->list; 394 else 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)); 399 } 400 401 if (stats) 402 printf("nr_symbols: %lu\n", (unsigned long)symbols_nr); 403 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]; 408 size_t pnamelen; 409 if (sym->type != STT_FUNC) 410 continue; 411 sym->pfunc = sym->cfunc = sym; 412 coldstr = strstr(sym->name, ".cold"); 413 if (!coldstr) 414 continue; 415 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); 420 return -1; 421 } 422 423 strncpy(pname, sym->name, pnamelen); 424 pname[pnamelen] = '\0'; 425 pfunc = find_symbol_by_name(elf, pname); 426 427 if (!pfunc) { 428 WARN("%s(): can't find parent function", 429 sym->name); 430 return -1; 431 } 432 433 sym->pfunc = pfunc; 434 pfunc->cfunc = sym; 435 436 /* 437 * Unfortunately, -fnoreorder-functions puts the child 438 * inside the parent. Remove the overlap so we can 439 * have sane assumptions. 440 * 441 * Note that pfunc->len now no longer matches 442 * pfunc->sym.st_size. 443 */ 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; 448 } 449 } 450 } 451 452 return 0; 453 454 err: 455 free(sym); 456 return -1; 457 } 458 459 static int read_relas(struct elf *elf) 460 { 461 struct section *sec; 462 struct rela *rela; 463 int i; 464 unsigned int symndx; 465 unsigned long nr_rela, max_rela = 0, tot_rela = 0; 466 467 list_for_each_entry(sec, &elf->sections, list) { 468 if (sec->sh.sh_type != SHT_RELA) 469 continue; 470 471 sec->base = find_section_by_name(elf, sec->name + 5); 472 if (!sec->base) { 473 WARN("can't find base section for rela section %s", 474 sec->name); 475 return -1; 476 } 477 478 sec->base->rela = sec; 479 480 nr_rela = 0; 481 for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) { 482 rela = malloc(sizeof(*rela)); 483 if (!rela) { 484 perror("malloc"); 485 return -1; 486 } 487 memset(rela, 0, sizeof(*rela)); 488 489 if (!gelf_getrela(sec->data, i, &rela->rela)) { 490 WARN_ELF("gelf_getrela"); 491 return -1; 492 } 493 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); 499 rela->sec = sec; 500 if (!rela->sym) { 501 WARN("can't find rela entry symbol %d for %s", 502 symndx, sec->name); 503 return -1; 504 } 505 506 list_add_tail(&rela->list, &sec->rela_list); 507 hash_add(elf->rela_hash, &rela->hash, rela_hash(rela)); 508 nr_rela++; 509 } 510 max_rela = max(max_rela, nr_rela); 511 tot_rela += nr_rela; 512 } 513 514 if (stats) { 515 printf("max_rela: %lu\n", max_rela); 516 printf("tot_rela: %lu\n", tot_rela); 517 } 518 519 return 0; 520 } 521 522 struct elf *elf_read(const char *name, int flags) 523 { 524 struct elf *elf; 525 Elf_Cmd cmd; 526 527 elf_version(EV_CURRENT); 528 529 elf = malloc(sizeof(*elf)); 530 if (!elf) { 531 perror("malloc"); 532 return NULL; 533 } 534 memset(elf, 0, sizeof(*elf)); 535 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); 542 543 elf->fd = open(name, flags); 544 if (elf->fd == -1) { 545 fprintf(stderr, "objtool: Can't open '%s': %s\n", 546 name, strerror(errno)); 547 goto err; 548 } 549 550 if ((flags & O_ACCMODE) == O_RDONLY) 551 cmd = ELF_C_READ_MMAP; 552 else if ((flags & O_ACCMODE) == O_RDWR) 553 cmd = ELF_C_RDWR; 554 else /* O_WRONLY */ 555 cmd = ELF_C_WRITE; 556 557 elf->elf = elf_begin(elf->fd, cmd, NULL); 558 if (!elf->elf) { 559 WARN_ELF("elf_begin"); 560 goto err; 561 } 562 563 if (!gelf_getehdr(elf->elf, &elf->ehdr)) { 564 WARN_ELF("gelf_getehdr"); 565 goto err; 566 } 567 568 if (read_sections(elf)) 569 goto err; 570 571 if (read_symbols(elf)) 572 goto err; 573 574 if (read_relas(elf)) 575 goto err; 576 577 return elf; 578 579 err: 580 elf_close(elf); 581 return NULL; 582 } 583 584 struct section *elf_create_section(struct elf *elf, const char *name, 585 size_t entsize, int nr) 586 { 587 struct section *sec, *shstrtab; 588 size_t size = entsize * nr; 589 Elf_Scn *s; 590 Elf_Data *data; 591 592 sec = malloc(sizeof(*sec)); 593 if (!sec) { 594 perror("malloc"); 595 return NULL; 596 } 597 memset(sec, 0, sizeof(*sec)); 598 599 INIT_LIST_HEAD(&sec->symbol_list); 600 INIT_LIST_HEAD(&sec->rela_list); 601 602 s = elf_newscn(elf->elf); 603 if (!s) { 604 WARN_ELF("elf_newscn"); 605 return NULL; 606 } 607 608 sec->name = strdup(name); 609 if (!sec->name) { 610 perror("strdup"); 611 return NULL; 612 } 613 614 sec->idx = elf_ndxscn(s); 615 sec->len = size; 616 sec->changed = true; 617 618 sec->data = elf_newdata(s); 619 if (!sec->data) { 620 WARN_ELF("elf_newdata"); 621 return NULL; 622 } 623 624 sec->data->d_size = size; 625 sec->data->d_align = 1; 626 627 if (size) { 628 sec->data->d_buf = malloc(size); 629 if (!sec->data->d_buf) { 630 perror("malloc"); 631 return NULL; 632 } 633 memset(sec->data->d_buf, 0, size); 634 } 635 636 if (!gelf_getshdr(s, &sec->sh)) { 637 WARN_ELF("gelf_getshdr"); 638 return NULL; 639 } 640 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; 646 647 648 /* Add section name to .shstrtab (or .strtab for Clang) */ 649 shstrtab = find_section_by_name(elf, ".shstrtab"); 650 if (!shstrtab) 651 shstrtab = find_section_by_name(elf, ".strtab"); 652 if (!shstrtab) { 653 WARN("can't find .shstrtab or .strtab section"); 654 return NULL; 655 } 656 657 s = elf_getscn(elf->elf, shstrtab->idx); 658 if (!s) { 659 WARN_ELF("elf_getscn"); 660 return NULL; 661 } 662 663 data = elf_newdata(s); 664 if (!data) { 665 WARN_ELF("elf_newdata"); 666 return NULL; 667 } 668 669 data->d_buf = sec->name; 670 data->d_size = strlen(name) + 1; 671 data->d_align = 1; 672 673 sec->sh.sh_name = shstrtab->len; 674 675 shstrtab->len += strlen(name) + 1; 676 shstrtab->changed = true; 677 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)); 681 682 return sec; 683 } 684 685 struct section *elf_create_rela_section(struct elf *elf, struct section *base) 686 { 687 char *relaname; 688 struct section *sec; 689 690 relaname = malloc(strlen(base->name) + strlen(".rela") + 1); 691 if (!relaname) { 692 perror("malloc"); 693 return NULL; 694 } 695 strcpy(relaname, ".rela"); 696 strcat(relaname, base->name); 697 698 sec = elf_create_section(elf, relaname, sizeof(GElf_Rela), 0); 699 free(relaname); 700 if (!sec) 701 return NULL; 702 703 base->rela = sec; 704 sec->base = base; 705 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; 711 712 return sec; 713 } 714 715 int elf_rebuild_rela_section(struct section *sec) 716 { 717 struct rela *rela; 718 int nr, idx = 0, size; 719 GElf_Rela *relas; 720 721 nr = 0; 722 list_for_each_entry(rela, &sec->rela_list, list) 723 nr++; 724 725 size = nr * sizeof(*relas); 726 relas = malloc(size); 727 if (!relas) { 728 perror("malloc"); 729 return -1; 730 } 731 732 sec->data->d_buf = relas; 733 sec->data->d_size = size; 734 735 sec->sh.sh_size = size; 736 737 idx = 0; 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); 742 idx++; 743 } 744 745 return 0; 746 } 747 748 int elf_write(struct elf *elf) 749 { 750 struct section *sec; 751 Elf_Scn *s; 752 753 /* Update section headers for changed sections: */ 754 list_for_each_entry(sec, &elf->sections, list) { 755 if (sec->changed) { 756 s = elf_getscn(elf->elf, sec->idx); 757 if (!s) { 758 WARN_ELF("elf_getscn"); 759 return -1; 760 } 761 if (!gelf_update_shdr(s, &sec->sh)) { 762 WARN_ELF("gelf_update_shdr"); 763 return -1; 764 } 765 } 766 } 767 768 /* Make sure the new section header entries get updated properly. */ 769 elf_flagelf(elf->elf, ELF_C_SET, ELF_F_DIRTY); 770 771 /* Write all changes to the file. */ 772 if (elf_update(elf->elf, ELF_C_WRITE) < 0) { 773 WARN_ELF("elf_update"); 774 return -1; 775 } 776 777 return 0; 778 } 779 780 void elf_close(struct elf *elf) 781 { 782 struct section *sec, *tmpsec; 783 struct symbol *sym, *tmpsym; 784 struct rela *rela, *tmprela; 785 786 if (elf->elf) 787 elf_end(elf->elf); 788 789 if (elf->fd > 0) 790 close(elf->fd); 791 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); 796 free(sym); 797 } 798 list_for_each_entry_safe(rela, tmprela, &sec->rela_list, list) { 799 list_del(&rela->list); 800 hash_del(&rela->hash); 801 free(rela); 802 } 803 list_del(&sec->list); 804 free(sec); 805 } 806 807 free(elf); 808 } 809