arch/arm/kernel/module-plts.c

   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 }