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