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 <sys/mman.h>
13 #include <fcntl.h>
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17 #include <unistd.h>
18 #include <errno.h>
19 #include <objtool/builtin.h>
20 
21 #include <objtool/elf.h>
22 #include <objtool/warn.h>
23 
24 #define MAX_NAME_LEN 128
25 
str_hash(const char * str)26 static inline u32 str_hash(const char *str)
27 {
28 	return jhash(str, strlen(str), 0);
29 }
30 
31 #define __elf_table(name)	(elf->name##_hash)
32 #define __elf_bits(name)	(elf->name##_bits)
33 
34 #define elf_hash_add(name, node, key) \
35 	hlist_add_head(node, &__elf_table(name)[hash_min(key, __elf_bits(name))])
36 
37 #define elf_hash_for_each_possible(name, obj, member, key) \
38 	hlist_for_each_entry(obj, &__elf_table(name)[hash_min(key, __elf_bits(name))], member)
39 
40 #define elf_alloc_hash(name, size) \
41 ({ \
42 	__elf_bits(name) = max(10, ilog2(size)); \
43 	__elf_table(name) = mmap(NULL, sizeof(struct hlist_head) << __elf_bits(name), \
44 				 PROT_READ|PROT_WRITE, \
45 				 MAP_PRIVATE|MAP_ANON, -1, 0); \
46 	if (__elf_table(name) == (void *)-1L) { \
47 		WARN("mmap fail " #name); \
48 		__elf_table(name) = NULL; \
49 	} \
50 	__elf_table(name); \
51 })
52 
symbol_to_offset(struct rb_node * a,const struct rb_node * b)53 static bool symbol_to_offset(struct rb_node *a, const struct rb_node *b)
54 {
55 	struct symbol *sa = rb_entry(a, struct symbol, node);
56 	struct symbol *sb = rb_entry(b, struct symbol, node);
57 
58 	if (sa->offset < sb->offset)
59 		return true;
60 	if (sa->offset > sb->offset)
61 		return false;
62 
63 	if (sa->len < sb->len)
64 		return true;
65 	if (sa->len > sb->len)
66 		return false;
67 
68 	sa->alias = sb;
69 
70 	return false;
71 }
72 
symbol_by_offset(const void * key,const struct rb_node * node)73 static int symbol_by_offset(const void *key, const struct rb_node *node)
74 {
75 	const struct symbol *s = rb_entry(node, struct symbol, node);
76 	const unsigned long *o = key;
77 
78 	if (*o < s->offset)
79 		return -1;
80 	if (*o >= s->offset + s->len)
81 		return 1;
82 
83 	return 0;
84 }
85 
86 struct symbol_hole {
87 	unsigned long key;
88 	const struct symbol *sym;
89 };
90 
91 /*
92  * Find !section symbol where @offset is after it.
93  */
symbol_hole_by_offset(const void * key,const struct rb_node * node)94 static int symbol_hole_by_offset(const void *key, const struct rb_node *node)
95 {
96 	const struct symbol *s = rb_entry(node, struct symbol, node);
97 	struct symbol_hole *sh = (void *)key;
98 
99 	if (sh->key < s->offset)
100 		return -1;
101 
102 	if (sh->key >= s->offset + s->len) {
103 		if (s->type != STT_SECTION)
104 			sh->sym = s;
105 		return 1;
106 	}
107 
108 	return 0;
109 }
110 
find_section_by_name(const struct elf * elf,const char * name)111 struct section *find_section_by_name(const struct elf *elf, const char *name)
112 {
113 	struct section *sec;
114 
115 	elf_hash_for_each_possible(section_name, sec, name_hash, str_hash(name)) {
116 		if (!strcmp(sec->name, name))
117 			return sec;
118 	}
119 
120 	return NULL;
121 }
122 
find_section_by_index(struct elf * elf,unsigned int idx)123 static struct section *find_section_by_index(struct elf *elf,
124 					     unsigned int idx)
125 {
126 	struct section *sec;
127 
128 	elf_hash_for_each_possible(section, sec, hash, idx) {
129 		if (sec->idx == idx)
130 			return sec;
131 	}
132 
133 	return NULL;
134 }
135 
find_symbol_by_index(struct elf * elf,unsigned int idx)136 static struct symbol *find_symbol_by_index(struct elf *elf, unsigned int idx)
137 {
138 	struct symbol *sym;
139 
140 	elf_hash_for_each_possible(symbol, sym, hash, idx) {
141 		if (sym->idx == idx)
142 			return sym;
143 	}
144 
145 	return NULL;
146 }
147 
find_symbol_by_offset(struct section * sec,unsigned long offset)148 struct symbol *find_symbol_by_offset(struct section *sec, unsigned long offset)
149 {
150 	struct rb_node *node;
151 
152 	rb_for_each(node, &offset, &sec->symbol_tree, 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 
find_func_by_offset(struct section * sec,unsigned long offset)162 struct symbol *find_func_by_offset(struct section *sec, unsigned long offset)
163 {
164 	struct rb_node *node;
165 
166 	rb_for_each(node, &offset, &sec->symbol_tree, 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 
find_symbol_containing(const struct section * sec,unsigned long offset)176 struct symbol *find_symbol_containing(const struct section *sec, unsigned long offset)
177 {
178 	struct rb_node *node;
179 
180 	rb_for_each(node, &offset, &sec->symbol_tree, 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 /*
191  * Returns size of hole starting at @offset.
192  */
find_symbol_hole_containing(const struct section * sec,unsigned long offset)193 int find_symbol_hole_containing(const struct section *sec, unsigned long offset)
194 {
195 	struct symbol_hole hole = {
196 		.key = offset,
197 		.sym = NULL,
198 	};
199 	struct rb_node *n;
200 	struct symbol *s;
201 
202 	/*
203 	 * Find the rightmost symbol for which @offset is after it.
204 	 */
205 	n = rb_find(&hole, &sec->symbol_tree, symbol_hole_by_offset);
206 
207 	/* found a symbol that contains @offset */
208 	if (n)
209 		return 0; /* not a hole */
210 
211 	/* didn't find a symbol for which @offset is after it */
212 	if (!hole.sym)
213 		return 0; /* not a hole */
214 
215 	/* @offset >= sym->offset + sym->len, find symbol after it */
216 	n = rb_next(&hole.sym->node);
217 	if (!n)
218 		return -1; /* until end of address space */
219 
220 	/* hole until start of next symbol */
221 	s = rb_entry(n, struct symbol, node);
222 	return s->offset - offset;
223 }
224 
find_func_containing(struct section * sec,unsigned long offset)225 struct symbol *find_func_containing(struct section *sec, unsigned long offset)
226 {
227 	struct rb_node *node;
228 
229 	rb_for_each(node, &offset, &sec->symbol_tree, symbol_by_offset) {
230 		struct symbol *s = rb_entry(node, struct symbol, node);
231 
232 		if (s->type == STT_FUNC)
233 			return s;
234 	}
235 
236 	return NULL;
237 }
238 
find_symbol_by_name(const struct elf * elf,const char * name)239 struct symbol *find_symbol_by_name(const struct elf *elf, const char *name)
240 {
241 	struct symbol *sym;
242 
243 	elf_hash_for_each_possible(symbol_name, sym, name_hash, str_hash(name)) {
244 		if (!strcmp(sym->name, name))
245 			return sym;
246 	}
247 
248 	return NULL;
249 }
250 
find_reloc_by_dest_range(const struct elf * elf,struct section * sec,unsigned long offset,unsigned int len)251 struct reloc *find_reloc_by_dest_range(const struct elf *elf, struct section *sec,
252 				     unsigned long offset, unsigned int len)
253 {
254 	struct reloc *reloc, *r = NULL;
255 	unsigned long o;
256 
257 	if (!sec->reloc)
258 		return NULL;
259 
260 	sec = sec->reloc;
261 
262 	for_offset_range(o, offset, offset + len) {
263 		elf_hash_for_each_possible(reloc, reloc, hash,
264 					   sec_offset_hash(sec, o)) {
265 			if (reloc->sec != sec)
266 				continue;
267 
268 			if (reloc->offset >= offset && reloc->offset < offset + len) {
269 				if (!r || reloc->offset < r->offset)
270 					r = reloc;
271 			}
272 		}
273 		if (r)
274 			return r;
275 	}
276 
277 	return NULL;
278 }
279 
find_reloc_by_dest(const struct elf * elf,struct section * sec,unsigned long offset)280 struct reloc *find_reloc_by_dest(const struct elf *elf, struct section *sec, unsigned long offset)
281 {
282 	return find_reloc_by_dest_range(elf, sec, offset, 1);
283 }
284 
read_sections(struct elf * elf)285 static int read_sections(struct elf *elf)
286 {
287 	Elf_Scn *s = NULL;
288 	struct section *sec;
289 	size_t shstrndx, sections_nr;
290 	int i;
291 
292 	if (elf_getshdrnum(elf->elf, &sections_nr)) {
293 		WARN_ELF("elf_getshdrnum");
294 		return -1;
295 	}
296 
297 	if (elf_getshdrstrndx(elf->elf, &shstrndx)) {
298 		WARN_ELF("elf_getshdrstrndx");
299 		return -1;
300 	}
301 
302 	if (!elf_alloc_hash(section, sections_nr) ||
303 	    !elf_alloc_hash(section_name, sections_nr))
304 		return -1;
305 
306 	for (i = 0; i < sections_nr; i++) {
307 		sec = malloc(sizeof(*sec));
308 		if (!sec) {
309 			perror("malloc");
310 			return -1;
311 		}
312 		memset(sec, 0, sizeof(*sec));
313 
314 		INIT_LIST_HEAD(&sec->symbol_list);
315 		INIT_LIST_HEAD(&sec->reloc_list);
316 
317 		s = elf_getscn(elf->elf, i);
318 		if (!s) {
319 			WARN_ELF("elf_getscn");
320 			return -1;
321 		}
322 
323 		sec->idx = elf_ndxscn(s);
324 
325 		if (!gelf_getshdr(s, &sec->sh)) {
326 			WARN_ELF("gelf_getshdr");
327 			return -1;
328 		}
329 
330 		sec->name = elf_strptr(elf->elf, shstrndx, sec->sh.sh_name);
331 		if (!sec->name) {
332 			WARN_ELF("elf_strptr");
333 			return -1;
334 		}
335 
336 		if (sec->sh.sh_size != 0) {
337 			sec->data = elf_getdata(s, NULL);
338 			if (!sec->data) {
339 				WARN_ELF("elf_getdata");
340 				return -1;
341 			}
342 			if (sec->data->d_off != 0 ||
343 			    sec->data->d_size != sec->sh.sh_size) {
344 				WARN("unexpected data attributes for %s",
345 				     sec->name);
346 				return -1;
347 			}
348 		}
349 
350 		if (sec->sh.sh_flags & SHF_EXECINSTR)
351 			elf->text_size += sec->sh.sh_size;
352 
353 		list_add_tail(&sec->list, &elf->sections);
354 		elf_hash_add(section, &sec->hash, sec->idx);
355 		elf_hash_add(section_name, &sec->name_hash, str_hash(sec->name));
356 	}
357 
358 	if (opts.stats) {
359 		printf("nr_sections: %lu\n", (unsigned long)sections_nr);
360 		printf("section_bits: %d\n", elf->section_bits);
361 	}
362 
363 	/* sanity check, one more call to elf_nextscn() should return NULL */
364 	if (elf_nextscn(elf->elf, s)) {
365 		WARN("section entry mismatch");
366 		return -1;
367 	}
368 
369 	return 0;
370 }
371 
elf_add_symbol(struct elf * elf,struct symbol * sym)372 static void elf_add_symbol(struct elf *elf, struct symbol *sym)
373 {
374 	struct list_head *entry;
375 	struct rb_node *pnode;
376 
377 	INIT_LIST_HEAD(&sym->pv_target);
378 	sym->alias = sym;
379 
380 	sym->type = GELF_ST_TYPE(sym->sym.st_info);
381 	sym->bind = GELF_ST_BIND(sym->sym.st_info);
382 
383 	if (sym->type == STT_FILE)
384 		elf->num_files++;
385 
386 	sym->offset = sym->sym.st_value;
387 	sym->len = sym->sym.st_size;
388 
389 	rb_add(&sym->node, &sym->sec->symbol_tree, symbol_to_offset);
390 	pnode = rb_prev(&sym->node);
391 	if (pnode)
392 		entry = &rb_entry(pnode, struct symbol, node)->list;
393 	else
394 		entry = &sym->sec->symbol_list;
395 	list_add(&sym->list, entry);
396 	elf_hash_add(symbol, &sym->hash, sym->idx);
397 	elf_hash_add(symbol_name, &sym->name_hash, str_hash(sym->name));
398 
399 	/*
400 	 * Don't store empty STT_NOTYPE symbols in the rbtree.  They
401 	 * can exist within a function, confusing the sorting.
402 	 */
403 	if (!sym->len)
404 		rb_erase(&sym->node, &sym->sec->symbol_tree);
405 }
406 
read_symbols(struct elf * elf)407 static int read_symbols(struct elf *elf)
408 {
409 	struct section *symtab, *symtab_shndx, *sec;
410 	struct symbol *sym, *pfunc;
411 	int symbols_nr, i;
412 	char *coldstr;
413 	Elf_Data *shndx_data = NULL;
414 	Elf32_Word shndx;
415 
416 	symtab = find_section_by_name(elf, ".symtab");
417 	if (symtab) {
418 		symtab_shndx = find_section_by_name(elf, ".symtab_shndx");
419 		if (symtab_shndx)
420 			shndx_data = symtab_shndx->data;
421 
422 		symbols_nr = symtab->sh.sh_size / symtab->sh.sh_entsize;
423 	} else {
424 		/*
425 		 * A missing symbol table is actually possible if it's an empty
426 		 * .o file. This can happen for thunk_64.o. Make sure to at
427 		 * least allocate the symbol hash tables so we can do symbol
428 		 * lookups without crashing.
429 		 */
430 		symbols_nr = 0;
431 	}
432 
433 	if (!elf_alloc_hash(symbol, symbols_nr) ||
434 	    !elf_alloc_hash(symbol_name, symbols_nr))
435 		return -1;
436 
437 	for (i = 0; i < symbols_nr; i++) {
438 		sym = malloc(sizeof(*sym));
439 		if (!sym) {
440 			perror("malloc");
441 			return -1;
442 		}
443 		memset(sym, 0, sizeof(*sym));
444 
445 		sym->idx = i;
446 
447 		if (!gelf_getsymshndx(symtab->data, shndx_data, i, &sym->sym,
448 				      &shndx)) {
449 			WARN_ELF("gelf_getsymshndx");
450 			goto err;
451 		}
452 
453 		sym->name = elf_strptr(elf->elf, symtab->sh.sh_link,
454 				       sym->sym.st_name);
455 		if (!sym->name) {
456 			WARN_ELF("elf_strptr");
457 			goto err;
458 		}
459 
460 		if ((sym->sym.st_shndx > SHN_UNDEF &&
461 		     sym->sym.st_shndx < SHN_LORESERVE) ||
462 		    (shndx_data && sym->sym.st_shndx == SHN_XINDEX)) {
463 			if (sym->sym.st_shndx != SHN_XINDEX)
464 				shndx = sym->sym.st_shndx;
465 
466 			sym->sec = find_section_by_index(elf, shndx);
467 			if (!sym->sec) {
468 				WARN("couldn't find section for symbol %s",
469 				     sym->name);
470 				goto err;
471 			}
472 			if (GELF_ST_TYPE(sym->sym.st_info) == STT_SECTION) {
473 				sym->name = sym->sec->name;
474 				sym->sec->sym = sym;
475 			}
476 		} else
477 			sym->sec = find_section_by_index(elf, 0);
478 
479 		elf_add_symbol(elf, sym);
480 	}
481 
482 	if (opts.stats) {
483 		printf("nr_symbols: %lu\n", (unsigned long)symbols_nr);
484 		printf("symbol_bits: %d\n", elf->symbol_bits);
485 	}
486 
487 	/* Create parent/child links for any cold subfunctions */
488 	list_for_each_entry(sec, &elf->sections, list) {
489 		list_for_each_entry(sym, &sec->symbol_list, list) {
490 			char pname[MAX_NAME_LEN + 1];
491 			size_t pnamelen;
492 			if (sym->type != STT_FUNC)
493 				continue;
494 
495 			if (sym->pfunc == NULL)
496 				sym->pfunc = sym;
497 
498 			if (sym->cfunc == NULL)
499 				sym->cfunc = sym;
500 
501 			coldstr = strstr(sym->name, ".cold");
502 			if (!coldstr)
503 				continue;
504 
505 			pnamelen = coldstr - sym->name;
506 			if (pnamelen > MAX_NAME_LEN) {
507 				WARN("%s(): parent function name exceeds maximum length of %d characters",
508 				     sym->name, MAX_NAME_LEN);
509 				return -1;
510 			}
511 
512 			strncpy(pname, sym->name, pnamelen);
513 			pname[pnamelen] = '\0';
514 			pfunc = find_symbol_by_name(elf, pname);
515 
516 			if (!pfunc) {
517 				WARN("%s(): can't find parent function",
518 				     sym->name);
519 				return -1;
520 			}
521 
522 			sym->pfunc = pfunc;
523 			pfunc->cfunc = sym;
524 
525 			/*
526 			 * Unfortunately, -fnoreorder-functions puts the child
527 			 * inside the parent.  Remove the overlap so we can
528 			 * have sane assumptions.
529 			 *
530 			 * Note that pfunc->len now no longer matches
531 			 * pfunc->sym.st_size.
532 			 */
533 			if (sym->sec == pfunc->sec &&
534 			    sym->offset >= pfunc->offset &&
535 			    sym->offset + sym->len == pfunc->offset + pfunc->len) {
536 				pfunc->len -= sym->len;
537 			}
538 		}
539 	}
540 
541 	return 0;
542 
543 err:
544 	free(sym);
545 	return -1;
546 }
547 
548 static struct section *elf_create_reloc_section(struct elf *elf,
549 						struct section *base,
550 						int reltype);
551 
elf_add_reloc(struct elf * elf,struct section * sec,unsigned long offset,unsigned int type,struct symbol * sym,s64 addend)552 int elf_add_reloc(struct elf *elf, struct section *sec, unsigned long offset,
553 		  unsigned int type, struct symbol *sym, s64 addend)
554 {
555 	struct reloc *reloc;
556 
557 	if (!sec->reloc && !elf_create_reloc_section(elf, sec, SHT_RELA))
558 		return -1;
559 
560 	reloc = malloc(sizeof(*reloc));
561 	if (!reloc) {
562 		perror("malloc");
563 		return -1;
564 	}
565 	memset(reloc, 0, sizeof(*reloc));
566 
567 	reloc->sec = sec->reloc;
568 	reloc->offset = offset;
569 	reloc->type = type;
570 	reloc->sym = sym;
571 	reloc->addend = addend;
572 
573 	list_add_tail(&reloc->list, &sec->reloc->reloc_list);
574 	elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
575 
576 	sec->reloc->sh.sh_size += sec->reloc->sh.sh_entsize;
577 	sec->reloc->changed = true;
578 
579 	return 0;
580 }
581 
582 /*
583  * Ensure that any reloc section containing references to @sym is marked
584  * changed such that it will get re-generated in elf_rebuild_reloc_sections()
585  * with the new symbol index.
586  */
elf_dirty_reloc_sym(struct elf * elf,struct symbol * sym)587 static void elf_dirty_reloc_sym(struct elf *elf, struct symbol *sym)
588 {
589 	struct section *sec;
590 
591 	list_for_each_entry(sec, &elf->sections, list) {
592 		struct reloc *reloc;
593 
594 		if (sec->changed)
595 			continue;
596 
597 		list_for_each_entry(reloc, &sec->reloc_list, list) {
598 			if (reloc->sym == sym) {
599 				sec->changed = true;
600 				break;
601 			}
602 		}
603 	}
604 }
605 
606 /*
607  * The libelf API is terrible; gelf_update_sym*() takes a data block relative
608  * index value, *NOT* the symbol index. As such, iterate the data blocks and
609  * adjust index until it fits.
610  *
611  * If no data block is found, allow adding a new data block provided the index
612  * is only one past the end.
613  */
elf_update_symbol(struct elf * elf,struct section * symtab,struct section * symtab_shndx,struct symbol * sym)614 static int elf_update_symbol(struct elf *elf, struct section *symtab,
615 			     struct section *symtab_shndx, struct symbol *sym)
616 {
617 	Elf32_Word shndx = sym->sec ? sym->sec->idx : SHN_UNDEF;
618 	Elf_Data *symtab_data = NULL, *shndx_data = NULL;
619 	Elf64_Xword entsize = symtab->sh.sh_entsize;
620 	int max_idx, idx = sym->idx;
621 	Elf_Scn *s, *t = NULL;
622 	bool is_special_shndx = sym->sym.st_shndx >= SHN_LORESERVE &&
623 				sym->sym.st_shndx != SHN_XINDEX;
624 
625 	if (is_special_shndx)
626 		shndx = sym->sym.st_shndx;
627 
628 	s = elf_getscn(elf->elf, symtab->idx);
629 	if (!s) {
630 		WARN_ELF("elf_getscn");
631 		return -1;
632 	}
633 
634 	if (symtab_shndx) {
635 		t = elf_getscn(elf->elf, symtab_shndx->idx);
636 		if (!t) {
637 			WARN_ELF("elf_getscn");
638 			return -1;
639 		}
640 	}
641 
642 	for (;;) {
643 		/* get next data descriptor for the relevant sections */
644 		symtab_data = elf_getdata(s, symtab_data);
645 		if (t)
646 			shndx_data = elf_getdata(t, shndx_data);
647 
648 		/* end-of-list */
649 		if (!symtab_data) {
650 			void *buf;
651 
652 			if (idx) {
653 				/* we don't do holes in symbol tables */
654 				WARN("index out of range");
655 				return -1;
656 			}
657 
658 			/* if @idx == 0, it's the next contiguous entry, create it */
659 			symtab_data = elf_newdata(s);
660 			if (t)
661 				shndx_data = elf_newdata(t);
662 
663 			buf = calloc(1, entsize);
664 			if (!buf) {
665 				WARN("malloc");
666 				return -1;
667 			}
668 
669 			symtab_data->d_buf = buf;
670 			symtab_data->d_size = entsize;
671 			symtab_data->d_align = 1;
672 			symtab_data->d_type = ELF_T_SYM;
673 
674 			symtab->sh.sh_size += entsize;
675 			symtab->changed = true;
676 
677 			if (t) {
678 				shndx_data->d_buf = &sym->sec->idx;
679 				shndx_data->d_size = sizeof(Elf32_Word);
680 				shndx_data->d_align = sizeof(Elf32_Word);
681 				shndx_data->d_type = ELF_T_WORD;
682 
683 				symtab_shndx->sh.sh_size += sizeof(Elf32_Word);
684 				symtab_shndx->changed = true;
685 			}
686 
687 			break;
688 		}
689 
690 		/* empty blocks should not happen */
691 		if (!symtab_data->d_size) {
692 			WARN("zero size data");
693 			return -1;
694 		}
695 
696 		/* is this the right block? */
697 		max_idx = symtab_data->d_size / entsize;
698 		if (idx < max_idx)
699 			break;
700 
701 		/* adjust index and try again */
702 		idx -= max_idx;
703 	}
704 
705 	/* something went side-ways */
706 	if (idx < 0) {
707 		WARN("negative index");
708 		return -1;
709 	}
710 
711 	/* setup extended section index magic and write the symbol */
712 	if ((shndx >= SHN_UNDEF && shndx < SHN_LORESERVE) || is_special_shndx) {
713 		sym->sym.st_shndx = shndx;
714 		if (!shndx_data)
715 			shndx = 0;
716 	} else {
717 		sym->sym.st_shndx = SHN_XINDEX;
718 		if (!shndx_data) {
719 			WARN("no .symtab_shndx");
720 			return -1;
721 		}
722 	}
723 
724 	if (!gelf_update_symshndx(symtab_data, shndx_data, idx, &sym->sym, shndx)) {
725 		WARN_ELF("gelf_update_symshndx");
726 		return -1;
727 	}
728 
729 	return 0;
730 }
731 
732 static struct symbol *
elf_create_section_symbol(struct elf * elf,struct section * sec)733 elf_create_section_symbol(struct elf *elf, struct section *sec)
734 {
735 	struct section *symtab, *symtab_shndx;
736 	Elf32_Word first_non_local, new_idx;
737 	struct symbol *sym, *old;
738 
739 	symtab = find_section_by_name(elf, ".symtab");
740 	if (symtab) {
741 		symtab_shndx = find_section_by_name(elf, ".symtab_shndx");
742 	} else {
743 		WARN("no .symtab");
744 		return NULL;
745 	}
746 
747 	sym = calloc(1, sizeof(*sym));
748 	if (!sym) {
749 		perror("malloc");
750 		return NULL;
751 	}
752 
753 	sym->name = sec->name;
754 	sym->sec = sec;
755 
756 	// st_name 0
757 	sym->sym.st_info = GELF_ST_INFO(STB_LOCAL, STT_SECTION);
758 	// st_other 0
759 	// st_value 0
760 	// st_size 0
761 
762 	/*
763 	 * Move the first global symbol, as per sh_info, into a new, higher
764 	 * symbol index. This fees up a spot for a new local symbol.
765 	 */
766 	first_non_local = symtab->sh.sh_info;
767 	new_idx = symtab->sh.sh_size / symtab->sh.sh_entsize;
768 	old = find_symbol_by_index(elf, first_non_local);
769 	if (old) {
770 		old->idx = new_idx;
771 
772 		hlist_del(&old->hash);
773 		elf_hash_add(symbol, &old->hash, old->idx);
774 
775 		elf_dirty_reloc_sym(elf, old);
776 
777 		if (elf_update_symbol(elf, symtab, symtab_shndx, old)) {
778 			WARN("elf_update_symbol move");
779 			return NULL;
780 		}
781 
782 		new_idx = first_non_local;
783 	}
784 
785 	sym->idx = new_idx;
786 	if (elf_update_symbol(elf, symtab, symtab_shndx, sym)) {
787 		WARN("elf_update_symbol");
788 		return NULL;
789 	}
790 
791 	/*
792 	 * Either way, we added a LOCAL symbol.
793 	 */
794 	symtab->sh.sh_info += 1;
795 
796 	elf_add_symbol(elf, sym);
797 
798 	return sym;
799 }
800 
elf_add_reloc_to_insn(struct elf * elf,struct section * sec,unsigned long offset,unsigned int type,struct section * insn_sec,unsigned long insn_off)801 int elf_add_reloc_to_insn(struct elf *elf, struct section *sec,
802 			  unsigned long offset, unsigned int type,
803 			  struct section *insn_sec, unsigned long insn_off)
804 {
805 	struct symbol *sym = insn_sec->sym;
806 	int addend = insn_off;
807 
808 	if (!sym) {
809 		/*
810 		 * Due to how weak functions work, we must use section based
811 		 * relocations. Symbol based relocations would result in the
812 		 * weak and non-weak function annotations being overlaid on the
813 		 * non-weak function after linking.
814 		 */
815 		sym = elf_create_section_symbol(elf, insn_sec);
816 		if (!sym)
817 			return -1;
818 
819 		insn_sec->sym = sym;
820 	}
821 
822 	return elf_add_reloc(elf, sec, offset, type, sym, addend);
823 }
824 
read_rel_reloc(struct section * sec,int i,struct reloc * reloc,unsigned int * symndx)825 static int read_rel_reloc(struct section *sec, int i, struct reloc *reloc, unsigned int *symndx)
826 {
827 	if (!gelf_getrel(sec->data, i, &reloc->rel)) {
828 		WARN_ELF("gelf_getrel");
829 		return -1;
830 	}
831 	reloc->type = GELF_R_TYPE(reloc->rel.r_info);
832 	reloc->addend = 0;
833 	reloc->offset = reloc->rel.r_offset;
834 	*symndx = GELF_R_SYM(reloc->rel.r_info);
835 	return 0;
836 }
837 
read_rela_reloc(struct section * sec,int i,struct reloc * reloc,unsigned int * symndx)838 static int read_rela_reloc(struct section *sec, int i, struct reloc *reloc, unsigned int *symndx)
839 {
840 	if (!gelf_getrela(sec->data, i, &reloc->rela)) {
841 		WARN_ELF("gelf_getrela");
842 		return -1;
843 	}
844 	reloc->type = GELF_R_TYPE(reloc->rela.r_info);
845 	reloc->addend = reloc->rela.r_addend;
846 	reloc->offset = reloc->rela.r_offset;
847 	*symndx = GELF_R_SYM(reloc->rela.r_info);
848 	return 0;
849 }
850 
read_relocs(struct elf * elf)851 static int read_relocs(struct elf *elf)
852 {
853 	struct section *sec;
854 	struct reloc *reloc;
855 	int i;
856 	unsigned int symndx;
857 	unsigned long nr_reloc, max_reloc = 0, tot_reloc = 0;
858 
859 	if (!elf_alloc_hash(reloc, elf->text_size / 16))
860 		return -1;
861 
862 	list_for_each_entry(sec, &elf->sections, list) {
863 		if ((sec->sh.sh_type != SHT_RELA) &&
864 		    (sec->sh.sh_type != SHT_REL))
865 			continue;
866 
867 		sec->base = find_section_by_index(elf, sec->sh.sh_info);
868 		if (!sec->base) {
869 			WARN("can't find base section for reloc section %s",
870 			     sec->name);
871 			return -1;
872 		}
873 
874 		sec->base->reloc = sec;
875 
876 		nr_reloc = 0;
877 		for (i = 0; i < sec->sh.sh_size / sec->sh.sh_entsize; i++) {
878 			reloc = malloc(sizeof(*reloc));
879 			if (!reloc) {
880 				perror("malloc");
881 				return -1;
882 			}
883 			memset(reloc, 0, sizeof(*reloc));
884 			switch (sec->sh.sh_type) {
885 			case SHT_REL:
886 				if (read_rel_reloc(sec, i, reloc, &symndx))
887 					return -1;
888 				break;
889 			case SHT_RELA:
890 				if (read_rela_reloc(sec, i, reloc, &symndx))
891 					return -1;
892 				break;
893 			default: return -1;
894 			}
895 
896 			reloc->sec = sec;
897 			reloc->idx = i;
898 			reloc->sym = find_symbol_by_index(elf, symndx);
899 			if (!reloc->sym) {
900 				WARN("can't find reloc entry symbol %d for %s",
901 				     symndx, sec->name);
902 				return -1;
903 			}
904 
905 			list_add_tail(&reloc->list, &sec->reloc_list);
906 			elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
907 
908 			nr_reloc++;
909 		}
910 		max_reloc = max(max_reloc, nr_reloc);
911 		tot_reloc += nr_reloc;
912 	}
913 
914 	if (opts.stats) {
915 		printf("max_reloc: %lu\n", max_reloc);
916 		printf("tot_reloc: %lu\n", tot_reloc);
917 		printf("reloc_bits: %d\n", elf->reloc_bits);
918 	}
919 
920 	return 0;
921 }
922 
elf_open_read(const char * name,int flags)923 struct elf *elf_open_read(const char *name, int flags)
924 {
925 	struct elf *elf;
926 	Elf_Cmd cmd;
927 
928 	elf_version(EV_CURRENT);
929 
930 	elf = malloc(sizeof(*elf));
931 	if (!elf) {
932 		perror("malloc");
933 		return NULL;
934 	}
935 	memset(elf, 0, offsetof(struct elf, sections));
936 
937 	INIT_LIST_HEAD(&elf->sections);
938 
939 	elf->fd = open(name, flags);
940 	if (elf->fd == -1) {
941 		fprintf(stderr, "objtool: Can't open '%s': %s\n",
942 			name, strerror(errno));
943 		goto err;
944 	}
945 
946 	if ((flags & O_ACCMODE) == O_RDONLY)
947 		cmd = ELF_C_READ_MMAP;
948 	else if ((flags & O_ACCMODE) == O_RDWR)
949 		cmd = ELF_C_RDWR;
950 	else /* O_WRONLY */
951 		cmd = ELF_C_WRITE;
952 
953 	elf->elf = elf_begin(elf->fd, cmd, NULL);
954 	if (!elf->elf) {
955 		WARN_ELF("elf_begin");
956 		goto err;
957 	}
958 
959 	if (!gelf_getehdr(elf->elf, &elf->ehdr)) {
960 		WARN_ELF("gelf_getehdr");
961 		goto err;
962 	}
963 
964 	if (read_sections(elf))
965 		goto err;
966 
967 	if (read_symbols(elf))
968 		goto err;
969 
970 	if (read_relocs(elf))
971 		goto err;
972 
973 	return elf;
974 
975 err:
976 	elf_close(elf);
977 	return NULL;
978 }
979 
elf_add_string(struct elf * elf,struct section * strtab,char * str)980 static int elf_add_string(struct elf *elf, struct section *strtab, char *str)
981 {
982 	Elf_Data *data;
983 	Elf_Scn *s;
984 	int len;
985 
986 	if (!strtab)
987 		strtab = find_section_by_name(elf, ".strtab");
988 	if (!strtab) {
989 		WARN("can't find .strtab section");
990 		return -1;
991 	}
992 
993 	s = elf_getscn(elf->elf, strtab->idx);
994 	if (!s) {
995 		WARN_ELF("elf_getscn");
996 		return -1;
997 	}
998 
999 	data = elf_newdata(s);
1000 	if (!data) {
1001 		WARN_ELF("elf_newdata");
1002 		return -1;
1003 	}
1004 
1005 	data->d_buf = str;
1006 	data->d_size = strlen(str) + 1;
1007 	data->d_align = 1;
1008 
1009 	len = strtab->sh.sh_size;
1010 	strtab->sh.sh_size += data->d_size;
1011 	strtab->changed = true;
1012 
1013 	return len;
1014 }
1015 
elf_create_section(struct elf * elf,const char * name,unsigned int sh_flags,size_t entsize,int nr)1016 struct section *elf_create_section(struct elf *elf, const char *name,
1017 				   unsigned int sh_flags, size_t entsize, int nr)
1018 {
1019 	struct section *sec, *shstrtab;
1020 	size_t size = entsize * nr;
1021 	Elf_Scn *s;
1022 
1023 	sec = malloc(sizeof(*sec));
1024 	if (!sec) {
1025 		perror("malloc");
1026 		return NULL;
1027 	}
1028 	memset(sec, 0, sizeof(*sec));
1029 
1030 	INIT_LIST_HEAD(&sec->symbol_list);
1031 	INIT_LIST_HEAD(&sec->reloc_list);
1032 
1033 	s = elf_newscn(elf->elf);
1034 	if (!s) {
1035 		WARN_ELF("elf_newscn");
1036 		return NULL;
1037 	}
1038 
1039 	sec->name = strdup(name);
1040 	if (!sec->name) {
1041 		perror("strdup");
1042 		return NULL;
1043 	}
1044 
1045 	sec->idx = elf_ndxscn(s);
1046 	sec->changed = true;
1047 
1048 	sec->data = elf_newdata(s);
1049 	if (!sec->data) {
1050 		WARN_ELF("elf_newdata");
1051 		return NULL;
1052 	}
1053 
1054 	sec->data->d_size = size;
1055 	sec->data->d_align = 1;
1056 
1057 	if (size) {
1058 		sec->data->d_buf = malloc(size);
1059 		if (!sec->data->d_buf) {
1060 			perror("malloc");
1061 			return NULL;
1062 		}
1063 		memset(sec->data->d_buf, 0, size);
1064 	}
1065 
1066 	if (!gelf_getshdr(s, &sec->sh)) {
1067 		WARN_ELF("gelf_getshdr");
1068 		return NULL;
1069 	}
1070 
1071 	sec->sh.sh_size = size;
1072 	sec->sh.sh_entsize = entsize;
1073 	sec->sh.sh_type = SHT_PROGBITS;
1074 	sec->sh.sh_addralign = 1;
1075 	sec->sh.sh_flags = SHF_ALLOC | sh_flags;
1076 
1077 	/* Add section name to .shstrtab (or .strtab for Clang) */
1078 	shstrtab = find_section_by_name(elf, ".shstrtab");
1079 	if (!shstrtab)
1080 		shstrtab = find_section_by_name(elf, ".strtab");
1081 	if (!shstrtab) {
1082 		WARN("can't find .shstrtab or .strtab section");
1083 		return NULL;
1084 	}
1085 	sec->sh.sh_name = elf_add_string(elf, shstrtab, sec->name);
1086 	if (sec->sh.sh_name == -1)
1087 		return NULL;
1088 
1089 	list_add_tail(&sec->list, &elf->sections);
1090 	elf_hash_add(section, &sec->hash, sec->idx);
1091 	elf_hash_add(section_name, &sec->name_hash, str_hash(sec->name));
1092 
1093 	elf->changed = true;
1094 
1095 	return sec;
1096 }
1097 
elf_create_rel_reloc_section(struct elf * elf,struct section * base)1098 static struct section *elf_create_rel_reloc_section(struct elf *elf, struct section *base)
1099 {
1100 	char *relocname;
1101 	struct section *sec;
1102 
1103 	relocname = malloc(strlen(base->name) + strlen(".rel") + 1);
1104 	if (!relocname) {
1105 		perror("malloc");
1106 		return NULL;
1107 	}
1108 	strcpy(relocname, ".rel");
1109 	strcat(relocname, base->name);
1110 
1111 	sec = elf_create_section(elf, relocname, 0, sizeof(GElf_Rel), 0);
1112 	free(relocname);
1113 	if (!sec)
1114 		return NULL;
1115 
1116 	base->reloc = sec;
1117 	sec->base = base;
1118 
1119 	sec->sh.sh_type = SHT_REL;
1120 	sec->sh.sh_addralign = 8;
1121 	sec->sh.sh_link = find_section_by_name(elf, ".symtab")->idx;
1122 	sec->sh.sh_info = base->idx;
1123 	sec->sh.sh_flags = SHF_INFO_LINK;
1124 
1125 	return sec;
1126 }
1127 
elf_create_rela_reloc_section(struct elf * elf,struct section * base)1128 static struct section *elf_create_rela_reloc_section(struct elf *elf, struct section *base)
1129 {
1130 	char *relocname;
1131 	struct section *sec;
1132 
1133 	relocname = malloc(strlen(base->name) + strlen(".rela") + 1);
1134 	if (!relocname) {
1135 		perror("malloc");
1136 		return NULL;
1137 	}
1138 	strcpy(relocname, ".rela");
1139 	strcat(relocname, base->name);
1140 
1141 	sec = elf_create_section(elf, relocname, 0, sizeof(GElf_Rela), 0);
1142 	free(relocname);
1143 	if (!sec)
1144 		return NULL;
1145 
1146 	base->reloc = sec;
1147 	sec->base = base;
1148 
1149 	sec->sh.sh_type = SHT_RELA;
1150 	sec->sh.sh_addralign = 8;
1151 	sec->sh.sh_link = find_section_by_name(elf, ".symtab")->idx;
1152 	sec->sh.sh_info = base->idx;
1153 	sec->sh.sh_flags = SHF_INFO_LINK;
1154 
1155 	return sec;
1156 }
1157 
elf_create_reloc_section(struct elf * elf,struct section * base,int reltype)1158 static struct section *elf_create_reloc_section(struct elf *elf,
1159 					 struct section *base,
1160 					 int reltype)
1161 {
1162 	switch (reltype) {
1163 	case SHT_REL:  return elf_create_rel_reloc_section(elf, base);
1164 	case SHT_RELA: return elf_create_rela_reloc_section(elf, base);
1165 	default:       return NULL;
1166 	}
1167 }
1168 
elf_rebuild_rel_reloc_section(struct section * sec)1169 static int elf_rebuild_rel_reloc_section(struct section *sec)
1170 {
1171 	struct reloc *reloc;
1172 	int idx = 0;
1173 	void *buf;
1174 
1175 	/* Allocate a buffer for relocations */
1176 	buf = malloc(sec->sh.sh_size);
1177 	if (!buf) {
1178 		perror("malloc");
1179 		return -1;
1180 	}
1181 
1182 	sec->data->d_buf = buf;
1183 	sec->data->d_size = sec->sh.sh_size;
1184 	sec->data->d_type = ELF_T_REL;
1185 
1186 	idx = 0;
1187 	list_for_each_entry(reloc, &sec->reloc_list, list) {
1188 		reloc->rel.r_offset = reloc->offset;
1189 		reloc->rel.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
1190 		if (!gelf_update_rel(sec->data, idx, &reloc->rel)) {
1191 			WARN_ELF("gelf_update_rel");
1192 			return -1;
1193 		}
1194 		idx++;
1195 	}
1196 
1197 	return 0;
1198 }
1199 
elf_rebuild_rela_reloc_section(struct section * sec)1200 static int elf_rebuild_rela_reloc_section(struct section *sec)
1201 {
1202 	struct reloc *reloc;
1203 	int idx = 0;
1204 	void *buf;
1205 
1206 	/* Allocate a buffer for relocations with addends */
1207 	buf = malloc(sec->sh.sh_size);
1208 	if (!buf) {
1209 		perror("malloc");
1210 		return -1;
1211 	}
1212 
1213 	sec->data->d_buf = buf;
1214 	sec->data->d_size = sec->sh.sh_size;
1215 	sec->data->d_type = ELF_T_RELA;
1216 
1217 	idx = 0;
1218 	list_for_each_entry(reloc, &sec->reloc_list, list) {
1219 		reloc->rela.r_offset = reloc->offset;
1220 		reloc->rela.r_addend = reloc->addend;
1221 		reloc->rela.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
1222 		if (!gelf_update_rela(sec->data, idx, &reloc->rela)) {
1223 			WARN_ELF("gelf_update_rela");
1224 			return -1;
1225 		}
1226 		idx++;
1227 	}
1228 
1229 	return 0;
1230 }
1231 
elf_rebuild_reloc_section(struct elf * elf,struct section * sec)1232 static int elf_rebuild_reloc_section(struct elf *elf, struct section *sec)
1233 {
1234 	switch (sec->sh.sh_type) {
1235 	case SHT_REL:  return elf_rebuild_rel_reloc_section(sec);
1236 	case SHT_RELA: return elf_rebuild_rela_reloc_section(sec);
1237 	default:       return -1;
1238 	}
1239 }
1240 
elf_write_insn(struct elf * elf,struct section * sec,unsigned long offset,unsigned int len,const char * insn)1241 int elf_write_insn(struct elf *elf, struct section *sec,
1242 		   unsigned long offset, unsigned int len,
1243 		   const char *insn)
1244 {
1245 	Elf_Data *data = sec->data;
1246 
1247 	if (data->d_type != ELF_T_BYTE || data->d_off) {
1248 		WARN("write to unexpected data for section: %s", sec->name);
1249 		return -1;
1250 	}
1251 
1252 	memcpy(data->d_buf + offset, insn, len);
1253 	elf_flagdata(data, ELF_C_SET, ELF_F_DIRTY);
1254 
1255 	elf->changed = true;
1256 
1257 	return 0;
1258 }
1259 
elf_write_reloc(struct elf * elf,struct reloc * reloc)1260 int elf_write_reloc(struct elf *elf, struct reloc *reloc)
1261 {
1262 	struct section *sec = reloc->sec;
1263 
1264 	if (sec->sh.sh_type == SHT_REL) {
1265 		reloc->rel.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
1266 		reloc->rel.r_offset = reloc->offset;
1267 
1268 		if (!gelf_update_rel(sec->data, reloc->idx, &reloc->rel)) {
1269 			WARN_ELF("gelf_update_rel");
1270 			return -1;
1271 		}
1272 	} else {
1273 		reloc->rela.r_info = GELF_R_INFO(reloc->sym->idx, reloc->type);
1274 		reloc->rela.r_addend = reloc->addend;
1275 		reloc->rela.r_offset = reloc->offset;
1276 
1277 		if (!gelf_update_rela(sec->data, reloc->idx, &reloc->rela)) {
1278 			WARN_ELF("gelf_update_rela");
1279 			return -1;
1280 		}
1281 	}
1282 
1283 	elf->changed = true;
1284 
1285 	return 0;
1286 }
1287 
elf_write(struct elf * elf)1288 int elf_write(struct elf *elf)
1289 {
1290 	struct section *sec;
1291 	Elf_Scn *s;
1292 
1293 	if (opts.dryrun)
1294 		return 0;
1295 
1296 	/* Update changed relocation sections and section headers: */
1297 	list_for_each_entry(sec, &elf->sections, list) {
1298 		if (sec->changed) {
1299 			s = elf_getscn(elf->elf, sec->idx);
1300 			if (!s) {
1301 				WARN_ELF("elf_getscn");
1302 				return -1;
1303 			}
1304 			if (!gelf_update_shdr(s, &sec->sh)) {
1305 				WARN_ELF("gelf_update_shdr");
1306 				return -1;
1307 			}
1308 
1309 			if (sec->base &&
1310 			    elf_rebuild_reloc_section(elf, sec)) {
1311 				WARN("elf_rebuild_reloc_section");
1312 				return -1;
1313 			}
1314 
1315 			sec->changed = false;
1316 			elf->changed = true;
1317 		}
1318 	}
1319 
1320 	/* Make sure the new section header entries get updated properly. */
1321 	elf_flagelf(elf->elf, ELF_C_SET, ELF_F_DIRTY);
1322 
1323 	/* Write all changes to the file. */
1324 	if (elf_update(elf->elf, ELF_C_WRITE) < 0) {
1325 		WARN_ELF("elf_update");
1326 		return -1;
1327 	}
1328 
1329 	elf->changed = false;
1330 
1331 	return 0;
1332 }
1333 
elf_close(struct elf * elf)1334 void elf_close(struct elf *elf)
1335 {
1336 	struct section *sec, *tmpsec;
1337 	struct symbol *sym, *tmpsym;
1338 	struct reloc *reloc, *tmpreloc;
1339 
1340 	if (elf->elf)
1341 		elf_end(elf->elf);
1342 
1343 	if (elf->fd > 0)
1344 		close(elf->fd);
1345 
1346 	list_for_each_entry_safe(sec, tmpsec, &elf->sections, list) {
1347 		list_for_each_entry_safe(sym, tmpsym, &sec->symbol_list, list) {
1348 			list_del(&sym->list);
1349 			hash_del(&sym->hash);
1350 			free(sym);
1351 		}
1352 		list_for_each_entry_safe(reloc, tmpreloc, &sec->reloc_list, list) {
1353 			list_del(&reloc->list);
1354 			hash_del(&reloc->hash);
1355 			free(reloc);
1356 		}
1357 		list_del(&sec->list);
1358 		free(sec);
1359 	}
1360 
1361 	free(elf);
1362 }
1363