1 /* 2 * Copyright (C) 2014 Linaro Ltd. <ard.biesheuvel@linaro.org> 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License version 2 as 6 * published by the Free Software Foundation. 7 */ 8 9 #include <linux/elf.h> 10 #include <linux/kernel.h> 11 #include <linux/module.h> 12 #include <linux/sort.h> 13 14 #include <asm/cache.h> 15 #include <asm/opcodes.h> 16 17 #define PLT_ENT_STRIDE L1_CACHE_BYTES 18 #define PLT_ENT_COUNT (PLT_ENT_STRIDE / sizeof(u32)) 19 #define PLT_ENT_SIZE (sizeof(struct plt_entries) / PLT_ENT_COUNT) 20 21 #ifdef CONFIG_THUMB2_KERNEL 22 #define PLT_ENT_LDR __opcode_to_mem_thumb32(0xf8dff000 | \ 23 (PLT_ENT_STRIDE - 4)) 24 #else 25 #define PLT_ENT_LDR __opcode_to_mem_arm(0xe59ff000 | \ 26 (PLT_ENT_STRIDE - 8)) 27 #endif 28 29 struct plt_entries { 30 u32 ldr[PLT_ENT_COUNT]; 31 u32 lit[PLT_ENT_COUNT]; 32 }; 33 34 u32 get_module_plt(struct module *mod, unsigned long loc, Elf32_Addr val) 35 { 36 struct plt_entries *plt = (struct plt_entries *)mod->arch.plt->sh_addr; 37 int idx = 0; 38 39 /* 40 * Look for an existing entry pointing to 'val'. Given that the 41 * relocations are sorted, this will be the last entry we allocated. 42 * (if one exists). 43 */ 44 if (mod->arch.plt_count > 0) { 45 plt += (mod->arch.plt_count - 1) / PLT_ENT_COUNT; 46 idx = (mod->arch.plt_count - 1) % PLT_ENT_COUNT; 47 48 if (plt->lit[idx] == val) 49 return (u32)&plt->ldr[idx]; 50 51 idx = (idx + 1) % PLT_ENT_COUNT; 52 if (!idx) 53 plt++; 54 } 55 56 mod->arch.plt_count++; 57 BUG_ON(mod->arch.plt_count * PLT_ENT_SIZE > mod->arch.plt->sh_size); 58 59 if (!idx) 60 /* Populate a new set of entries */ 61 *plt = (struct plt_entries){ 62 { [0 ... PLT_ENT_COUNT - 1] = PLT_ENT_LDR, }, 63 { val, } 64 }; 65 else 66 plt->lit[idx] = val; 67 68 return (u32)&plt->ldr[idx]; 69 } 70 71 #define cmp_3way(a,b) ((a) < (b) ? -1 : (a) > (b)) 72 73 static int cmp_rel(const void *a, const void *b) 74 { 75 const Elf32_Rel *x = a, *y = b; 76 int i; 77 78 /* sort by type and symbol index */ 79 i = cmp_3way(ELF32_R_TYPE(x->r_info), ELF32_R_TYPE(y->r_info)); 80 if (i == 0) 81 i = cmp_3way(ELF32_R_SYM(x->r_info), ELF32_R_SYM(y->r_info)); 82 return i; 83 } 84 85 static bool is_zero_addend_relocation(Elf32_Addr base, const Elf32_Rel *rel) 86 { 87 u32 *tval = (u32 *)(base + rel->r_offset); 88 89 /* 90 * Do a bitwise compare on the raw addend rather than fully decoding 91 * the offset and doing an arithmetic comparison. 92 * Note that a zero-addend jump/call relocation is encoded taking the 93 * PC bias into account, i.e., -8 for ARM and -4 for Thumb2. 94 */ 95 switch (ELF32_R_TYPE(rel->r_info)) { 96 u16 upper, lower; 97 98 case R_ARM_THM_CALL: 99 case R_ARM_THM_JUMP24: 100 upper = __mem_to_opcode_thumb16(((u16 *)tval)[0]); 101 lower = __mem_to_opcode_thumb16(((u16 *)tval)[1]); 102 103 return (upper & 0x7ff) == 0x7ff && (lower & 0x2fff) == 0x2ffe; 104 105 case R_ARM_CALL: 106 case R_ARM_PC24: 107 case R_ARM_JUMP24: 108 return (__mem_to_opcode_arm(*tval) & 0xffffff) == 0xfffffe; 109 } 110 BUG(); 111 } 112 113 static bool duplicate_rel(Elf32_Addr base, const Elf32_Rel *rel, int num) 114 { 115 const Elf32_Rel *prev; 116 117 /* 118 * Entries are sorted by type and symbol index. That means that, 119 * if a duplicate entry exists, it must be in the preceding 120 * slot. 121 */ 122 if (!num) 123 return false; 124 125 prev = rel + num - 1; 126 return cmp_rel(rel + num, prev) == 0 && 127 is_zero_addend_relocation(base, prev); 128 } 129 130 /* Count how many PLT entries we may need */ 131 static unsigned int count_plts(const Elf32_Sym *syms, Elf32_Addr base, 132 const Elf32_Rel *rel, int num) 133 { 134 unsigned int ret = 0; 135 const Elf32_Sym *s; 136 int i; 137 138 for (i = 0; i < num; i++) { 139 switch (ELF32_R_TYPE(rel[i].r_info)) { 140 case R_ARM_CALL: 141 case R_ARM_PC24: 142 case R_ARM_JUMP24: 143 case R_ARM_THM_CALL: 144 case R_ARM_THM_JUMP24: 145 /* 146 * We only have to consider branch targets that resolve 147 * to undefined symbols. This is not simply a heuristic, 148 * it is a fundamental limitation, since the PLT itself 149 * is part of the module, and needs to be within range 150 * as well, so modules can never grow beyond that limit. 151 */ 152 s = syms + ELF32_R_SYM(rel[i].r_info); 153 if (s->st_shndx != SHN_UNDEF) 154 break; 155 156 /* 157 * Jump relocations with non-zero addends against 158 * undefined symbols are supported by the ELF spec, but 159 * do not occur in practice (e.g., 'jump n bytes past 160 * the entry point of undefined function symbol f'). 161 * So we need to support them, but there is no need to 162 * take them into consideration when trying to optimize 163 * this code. So let's only check for duplicates when 164 * the addend is zero. 165 */ 166 if (!is_zero_addend_relocation(base, rel + i) || 167 !duplicate_rel(base, rel, i)) 168 ret++; 169 } 170 } 171 return ret; 172 } 173 174 int module_frob_arch_sections(Elf_Ehdr *ehdr, Elf_Shdr *sechdrs, 175 char *secstrings, struct module *mod) 176 { 177 unsigned long plts = 0; 178 Elf32_Shdr *s, *sechdrs_end = sechdrs + ehdr->e_shnum; 179 Elf32_Sym *syms = NULL; 180 181 /* 182 * To store the PLTs, we expand the .text section for core module code 183 * and for initialization code. 184 */ 185 for (s = sechdrs; s < sechdrs_end; ++s) { 186 if (strcmp(".plt", secstrings + s->sh_name) == 0) 187 mod->arch.plt = s; 188 else if (s->sh_type == SHT_SYMTAB) 189 syms = (Elf32_Sym *)s->sh_addr; 190 } 191 192 if (!mod->arch.plt) { 193 pr_err("%s: module PLT section missing\n", mod->name); 194 return -ENOEXEC; 195 } 196 if (!syms) { 197 pr_err("%s: module symtab section missing\n", mod->name); 198 return -ENOEXEC; 199 } 200 201 for (s = sechdrs + 1; s < sechdrs_end; ++s) { 202 Elf32_Rel *rels = (void *)ehdr + s->sh_offset; 203 int numrels = s->sh_size / sizeof(Elf32_Rel); 204 Elf32_Shdr *dstsec = sechdrs + s->sh_info; 205 206 if (s->sh_type != SHT_REL) 207 continue; 208 209 /* ignore relocations that operate on non-exec sections */ 210 if (!(dstsec->sh_flags & SHF_EXECINSTR)) 211 continue; 212 213 /* sort by type and symbol index */ 214 sort(rels, numrels, sizeof(Elf32_Rel), cmp_rel, NULL); 215 216 plts += count_plts(syms, dstsec->sh_addr, rels, numrels); 217 } 218 219 mod->arch.plt->sh_type = SHT_NOBITS; 220 mod->arch.plt->sh_flags = SHF_EXECINSTR | SHF_ALLOC; 221 mod->arch.plt->sh_addralign = L1_CACHE_BYTES; 222 mod->arch.plt->sh_size = round_up(plts * PLT_ENT_SIZE, 223 sizeof(struct plt_entries)); 224 mod->arch.plt_count = 0; 225 226 pr_debug("%s: plt=%x\n", __func__, mod->arch.plt->sh_size); 227 return 0; 228 } 229