kmodsrc/ksplice.c

   1 /*  Copyright (C) 2008  Jeffrey Brian Arnold <jbarnold@mit.edu>
   2  *
   3  *  This program is free software; you can redistribute it and/or modify
   4  *  it under the terms of the GNU General Public License, version 2.
   5  *
   6  *  This program is distributed in the hope that it will be useful,
   7  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   8  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   9  *  GNU General Public License for more details.
  10  *
  11  *  You should have received a copy of the GNU General Public License
  12  *  along with this program; if not, write to the Free Software
  13  *  Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
  14  *  02110-1301, USA.
  15  */
  16
  17 #include <linux/module.h>
  18 #include <linux/errno.h>
  19 #include <linux/kallsyms.h>
  20 #include <linux/kthread.h>
  21 #include <linux/proc_fs.h>
  22 #include <linux/sched.h>
  23 #include <linux/stop_machine.h>
  24 #include <linux/time.h>
  25 #ifdef KSPLICE_STANDALONE
  26 /* linux/uaccess.h doesn't exist in kernels before 2.6.18 */
  27 #include <linux/version.h>
  28 #include <asm/uaccess.h>
  29 #include "ksplice.h"
  30 #include "ksplice-run-pre.h"
  31 #else
  32 #include <linux/uaccess.h>
  33 #include "ksplice.h"
  34 #include <asm/ksplice-run-pre.h>
  35 #endif
  36
  37 #ifdef KSPLICE_STANDALONE
  38
  39 /* Old kernels do not have kcalloc */
  40 #define kcalloc(n, size, flags) ksplice_kcalloc(n)
  41
  42 #ifndef task_thread_info
  43 #define task_thread_info(task) (task)->thread_info
  44 #endif /* task_thread_info */
  45
  46 #ifdef __ASM_X86_PROCESSOR_H
  47 #define KSPLICE_EIP(x) ((x)->thread.ip)
  48 #define KSPLICE_ESP(x) ((x)->thread.sp)
  49 #elif BITS_PER_LONG == 32
  50 #define KSPLICE_EIP(x) ((x)->thread.eip)
  51 #define KSPLICE_ESP(x) ((x)->thread.esp)
  52 #elif BITS_PER_LONG == 64
  53 #define KSPLICE_EIP(x) (KSTK_EIP(x))
  54 #define KSPLICE_ESP(x) ((x)->thread.rsp)
  55 #endif /* __ASM_X86_PROCESSOR_H */
  56
  57 static int bootstrapped = 0;
  58
  59 #ifdef CONFIG_KALLSYMS
  60 extern unsigned long kallsyms_addresses[], kallsyms_num_syms;
  61 extern u8 kallsyms_names[];
  62 #endif /* CONFIG_KALLSYMS */
  63
  64 /* defined by ksplice-create */
  65 extern struct ksplice_reloc ksplice_init_relocs;
  66
  67 #else /* KSPLICE_STANDALONE */
  68 #define KSPLICE_EIP(x) ((x)->thread.ip)
  69 #define KSPLICE_ESP(x) ((x)->thread.sp)
  70 #endif /* KSPLICE_STANDALONE */
  71
  72 static int debug;
  73 module_param(debug, int, 0600);
  74
  75 /* THIS_MODULE everywhere is wrong! */
  76
  77 void cleanup_ksplice_module(struct module_pack *pack)
  78 {
  79         remove_proc_entry(pack->name, &proc_root);
  80 }
  81
  82 int activate_primary(struct module_pack *pack)
  83 {
  84         int i, ret;
  85         struct proc_dir_entry *proc_entry;
  86
  87         pack->helper = 0;
  88
  89         if (process_ksplice_relocs(pack, pack->primary_relocs) != 0)
  90                 return -1;
  91
  92         if (resolve_patch_symbols(pack) != 0)
  93                 return -1;
  94
  95         proc_entry = create_proc_entry(pack->name, 0644, NULL);
  96         if (proc_entry == NULL) {
  97                 print_abort("primary module: could not create proc entry");
  98                 return -1;
  99         }
 100
 101         proc_entry->read_proc = procfile_read;
 102         proc_entry->write_proc = procfile_write;
 103         proc_entry->data = pack;
 104         proc_entry->owner = THIS_MODULE;
 105         proc_entry->mode = S_IFREG | S_IRUSR | S_IWUSR;
 106         proc_entry->uid = 0;
 107         proc_entry->gid = 0;
 108         proc_entry->size = 0;
 109
 110         for (i = 0; i < 5; i++) {
 111                 bust_spinlocks(1);
 112                 ret = stop_machine_run(__apply_patches, pack, NR_CPUS);
 113                 bust_spinlocks(0);
 114                 if (ret != -EAGAIN)
 115                         break;
 116                 set_current_state(TASK_INTERRUPTIBLE);
 117                 schedule_timeout(msecs_to_jiffies(1000));
 118         }
 119         if (pack->state != KSPLICE_APPLIED) {
 120                 remove_proc_entry(pack->name, &proc_root);
 121                 if (ret == -EAGAIN)
 122                         print_abort("stack check: to-be-replaced code is busy");
 123                 return -1;
 124         }
 125
 126         printk(KERN_INFO "ksplice: Update %s applied successfully\n",
 127                pack->name);
 128         return 0;
 129 }
 130
 131 int resolve_patch_symbols(struct module_pack *pack)
 132 {
 133         struct ksplice_patch *p;
 134         int ret;
 135         LIST_HEAD(vals);
 136
 137         for (p = pack->patches; p->oldstr; p++) {
 138                 p->saved = kmalloc(5, GFP_KERNEL);
 139                 if (p->saved == NULL) {
 140                         print_abort("out of memory");
 141                         return -ENOMEM;
 142                 }
 143
 144                 if (p->oldaddr != 0) {
 145                         ret = add_candidate_val(&vals, p->oldaddr);
 146                         if (ret < 0)
 147                                 return ret;
 148                 }
 149
 150                 ret = compute_address(pack, p->oldstr, &vals);
 151                 if (ret < 0)
 152                         return ret;
 153
 154                 if (!singular(&vals)) {
 155                         release_vals(&vals);
 156                         failed_to_find(p->oldstr);
 157                         return -1;
 158                 }
 159                 p->oldaddr =
 160                     list_entry(vals.next, struct candidate_val, list)->val;
 161                 release_vals(&vals);
 162         }
 163
 164         return 0;
 165 }
 166
 167 int procfile_read(char *buffer, char **buffer_location,
 168                   off_t offset, int buffer_length, int *eof, void *data)
 169 {
 170         return 0;
 171 }
 172
 173 int procfile_write(struct file *file, const char *buffer, unsigned long count,
 174                    void *data)
 175 {
 176         int i, ret;
 177         struct module_pack *pack = data;
 178         printk(KERN_INFO "ksplice: Preparing to reverse %s\n", pack->name);
 179
 180         if (pack->state != KSPLICE_APPLIED)
 181                 return count;
 182
 183         for (i = 0; i < 5; i++) {
 184                 bust_spinlocks(1);
 185                 ret = stop_machine_run(__reverse_patches, pack, NR_CPUS);
 186                 bust_spinlocks(0);
 187                 if (ret != -EAGAIN)
 188                         break;
 189                 set_current_state(TASK_INTERRUPTIBLE);
 190                 schedule_timeout(msecs_to_jiffies(1000));
 191         }
 192         if (ret == -EAGAIN)
 193                 print_abort("stack check: to-be-reversed code is busy");
 194         else if (ret == 0)
 195                 printk(KERN_INFO "ksplice: Update %s reversed successfully\n",
 196                        pack->name);
 197
 198         return count;
 199 }
 200
 201 int __apply_patches(void *packptr)
 202 {
 203         struct module_pack *pack = packptr;
 204         struct ksplice_patch *p;
 205         struct safety_record *rec;
 206
 207         list_for_each_entry(rec, pack->safety_records, list) {
 208                 for (p = pack->patches; p->oldstr; p++) {
 209                         if (p->oldaddr == rec->addr)
 210                                 rec->care = 1;
 211                 }
 212         }
 213
 214         if (check_each_task(pack) < 0)
 215                 return -EAGAIN;
 216
 217         if (!try_module_get(THIS_MODULE))
 218                 return -ENODEV;
 219
 220         pack->state = KSPLICE_APPLIED;
 221
 222         for (p = pack->patches; p->oldstr; p++) {
 223                 memcpy((void *)p->saved, (void *)p->oldaddr, 5);
 224                 *((u8 *) p->oldaddr) = 0xE9;
 225                 *((u32 *) (p->oldaddr + 1)) = p->repladdr - (p->oldaddr + 5);
 226         }
 227         return 0;
 228 }
 229
 230 int __reverse_patches(void *packptr)
 231 {
 232         struct module_pack *pack = packptr;
 233         struct ksplice_patch *p;
 234
 235         if (pack->state != KSPLICE_APPLIED)
 236                 return 0;
 237
 238         if (check_each_task(pack) < 0)
 239                 return -EAGAIN;
 240
 241         clear_list(pack->safety_records, struct safety_record, list);
 242         pack->state = KSPLICE_REVERSED;
 243         module_put(THIS_MODULE);
 244
 245         p = pack->patches;
 246         for (; p->oldstr; p++) {
 247                 memcpy((void *)p->oldaddr, (void *)p->saved, 5);
 248                 kfree(p->saved);
 249                 *((u8 *) p->repladdr) = 0xE9;
 250                 *((u32 *) (p->repladdr + 1)) = p->oldaddr - (p->repladdr + 5);
 251         }
 252
 253         return 0;
 254 }
 255
 256 int check_each_task(struct module_pack *pack)
 257 {
 258         struct task_struct *g, *p;
 259         int status = 0;
 260         read_lock(&tasklist_lock);
 261         do_each_thread(g, p) {
 262                 /* do_each_thread is a double loop! */
 263                 if (check_task(pack, p) < 0) {
 264                         if (debug == 1) {
 265                                 debug = 2;
 266                                 check_task(pack, p);
 267                                 debug = 1;
 268                         }
 269                         status = -EAGAIN;
 270                 }
 271         }
 272         while_each_thread(g, p);
 273         read_unlock(&tasklist_lock);
 274         return status;
 275 }
 276
 277 int check_task(struct module_pack *pack, struct task_struct *t)
 278 {
 279         int status, ret;
 280
 281         ksplice_debug(2, KERN_DEBUG "ksplice: stack check: pid %d (%s) eip "
 282                       "%08lx ", t->pid, t->comm, KSPLICE_EIP(t));
 283         status = check_address_for_conflict(pack, KSPLICE_EIP(t));
 284         ksplice_debug(2, ": ");
 285
 286         if (t == current) {
 287                 ret = check_stack(pack, task_thread_info(t),
 288                                   (long *)__builtin_frame_address(0));
 289                 if (status == 0)
 290                         status = ret;
 291         } else if (!task_curr(t)) {
 292                 ret = check_stack(pack, task_thread_info(t),
 293                                   (long *)KSPLICE_ESP(t));
 294                 if (status == 0)
 295                         status = ret;
 296         } else if (strcmp(t->comm, "kstopmachine") != 0) {
 297                 ksplice_debug(2, "unexpected running task!");
 298                 status = -ENODEV;
 299         }
 300         ksplice_debug(2, "\n");
 301         return status;
 302 }
 303
 304 /* Modified version of Linux's print_context_stack */
 305 int check_stack(struct module_pack *pack, struct thread_info *tinfo,
 306                 long *stack)
 307 {
 308         int status = 0;
 309         long addr;
 310
 311         while (valid_stack_ptr(tinfo, stack)) {
 312                 addr = *stack++;
 313                 if (__kernel_text_address(addr)) {
 314                         ksplice_debug(2, "%08lx ", addr);
 315                         if (check_address_for_conflict(pack, addr) < 0)
 316                                 status = -EAGAIN;
 317                 }
 318         }
 319         return status;
 320 }
 321
 322 int check_address_for_conflict(struct module_pack *pack, long addr)
 323 {
 324         struct ksplice_size *s = pack->primary_sizes;
 325         struct safety_record *rec;
 326
 327         /* It is safe for addr to point to the beginning of a patched
 328            function, because that location will be overwritten with a
 329            trampoline. */
 330         list_for_each_entry(rec, pack->safety_records, list) {
 331                 if (rec->care == 1 && addr > rec->addr
 332                     && addr < rec->addr + rec->size) {
 333                         ksplice_debug(2, "[<-- CONFLICT] ");
 334                         return -EAGAIN;
 335                 }
 336         }
 337         for (; s->name != NULL; s++) {
 338                 if (addr >= s->thismod_addr
 339                     && addr < s->thismod_addr + s->size) {
 340                         ksplice_debug(2, "[<-- CONFLICT] ");
 341                         return -EAGAIN;
 342                 }
 343         }
 344         return 0;
 345 }
 346
 347 /* Modified version of Linux's valid_stack_ptr */
 348 int valid_stack_ptr(struct thread_info *tinfo, void *p)
 349 {
 350         return p > (void *)tinfo
 351             && p <= (void *)tinfo + THREAD_SIZE - sizeof(long);
 352 }
 353
 354 int init_ksplice_module(struct module_pack *pack)
 355 {
 356         int ret = 0;
 357 #ifdef KSPLICE_STANDALONE
 358         if (process_ksplice_relocs(pack, &ksplice_init_relocs) != 0)
 359                 return -1;
 360         bootstrapped = 1;
 361 #endif
 362
 363         printk(KERN_INFO "ksplice_h: Preparing and checking %s\n", pack->name);
 364
 365         if (activate_helper(pack) != 0 || activate_primary(pack) != 0)
 366                 ret = -1;
 367
 368         clear_list(pack->reloc_namevals, struct reloc_nameval, list);
 369         clear_list(pack->reloc_addrmaps, struct reloc_addrmap, list);
 370         if (pack->state == KSPLICE_PREPARING)
 371                 clear_list(pack->safety_records, struct safety_record, list);
 372
 373         return ret;
 374 }
 375
 376 int activate_helper(struct module_pack *pack)
 377 {
 378         struct ksplice_size *s;
 379         int i, record_count = 0, ret;
 380         char *finished;
 381         int numfinished, oldfinished = 0;
 382         int restart_count = 0;
 383
 384         pack->helper = 1;
 385
 386         if (process_ksplice_relocs(pack, pack->helper_relocs) != 0)
 387                 return -1;
 388
 389         for (s = pack->helper_sizes; s->name != NULL; s++)
 390                 record_count++;
 391
 392         finished = kcalloc(record_count, 1, GFP_KERNEL);
 393         if (finished == NULL) {
 394                 print_abort("out of memory");
 395                 return -ENOMEM;
 396         }
 397
 398 start:
 399         for (s = pack->helper_sizes, i = 0; s->name != NULL; s++, i++) {
 400                 if (s->size == 0)
 401                         finished[i] = 1;
 402                 if (finished[i])
 403                         continue;
 404
 405                 ret = search_for_match(pack, s);
 406                 if (ret < 0) {
 407                         kfree(finished);
 408                         return ret;
 409                 } else if (ret > 0) {
 410                         finished[i] = 1;
 411                 }
 412         }
 413
 414         numfinished = 0;
 415         for (i = 0; i < record_count; i++) {
 416                 if (finished[i])
 417                         numfinished++;
 418         }
 419         if (numfinished == record_count) {
 420                 kfree(finished);
 421                 return 0;
 422         }
 423
 424         if (oldfinished == numfinished) {
 425                 print_abort("run-pre: could not match some sections");
 426                 kfree(finished);
 427                 return -1;
 428         }
 429         oldfinished = numfinished;
 430
 431         if (restart_count < 20) {
 432                 restart_count++;
 433                 goto start;
 434         }
 435         print_abort("run-pre: restart limit exceeded");
 436         kfree(finished);
 437         return -1;
 438 }
 439
 440 int search_for_match(struct module_pack *pack, struct ksplice_size *s)
 441 {
 442         int i, ret;
 443 #ifdef KSPLICE_STANDALONE
 444         int saved_debug;
 445 #endif
 446         long run_addr;
 447         LIST_HEAD(vals);
 448         struct candidate_val *v;
 449
 450         for (i = 0; i < s->num_sym_addrs; i++) {
 451                 ret = add_candidate_val(&vals, s->sym_addrs[i]);
 452                 if (ret < 0)
 453                         return ret;
 454         }
 455
 456         ret = compute_address(pack, s->name, &vals);
 457         if (ret < 0)
 458                 return ret;
 459
 460         ksplice_debug(3, KERN_DEBUG "ksplice_h: run-pre: starting sect search "
 461                       "for %s\n", s->name);
 462
 463         list_for_each_entry(v, &vals, list) {
 464                 run_addr = v->val;
 465
 466                 yield();
 467                 ret = try_addr(pack, s, run_addr, s->thismod_addr,
 468                                !singular(&vals));
 469                 if (ret != 0) {
 470                         /* we've encountered a match (> 0) or an error (< 0) */
 471                         release_vals(&vals);
 472                         return ret;
 473                 }
 474         }
 475         release_vals(&vals);
 476
 477 #ifdef KSPLICE_STANDALONE
 478         saved_debug = debug;
 479         debug = 0;
 480         brute_search_all_mods(pack, s);
 481         debug = saved_debug;
 482 #endif
 483         return 0;
 484 }
 485
 486 int try_addr(struct module_pack *pack, struct ksplice_size *s, long run_addr,
 487              long pre_addr, int create_nameval)
 488 {
 489         struct safety_record *tmp;
 490         struct reloc_nameval *nv;
 491
 492         if (run_pre_cmp(pack, run_addr, pre_addr, s->size, 0) != 0) {
 493                 set_temp_myst_relocs(pack, NOVAL);
 494                 ksplice_debug(1, KERN_DEBUG "ksplice_h: run-pre: sect %s does "
 495                               "not match ", s->name);
 496                 ksplice_debug(1, "(r_a=%08lx p_a=%08lx s=%ld)\n",
 497                               run_addr, pre_addr, s->size);
 498                 ksplice_debug(1, "ksplice_h: run-pre: ");
 499                 if (debug >= 1)
 500                         run_pre_cmp(pack, run_addr, pre_addr, s->size, 1);
 501                 ksplice_debug(1, "\n");
 502         } else {
 503                 set_temp_myst_relocs(pack, VAL);
 504
 505                 ksplice_debug(3, KERN_DEBUG "ksplice_h: run-pre: found sect "
 506                               "%s=%08lx\n", s->name, run_addr);
 507
 508                 tmp = kmalloc(sizeof(*tmp), GFP_KERNEL);
 509                 if (tmp == NULL) {
 510                         print_abort("out of memory");
 511                         return -ENOMEM;
 512                 }
 513                 tmp->addr = run_addr;
 514                 tmp->size = s->size;
 515                 tmp->care = 0;
 516                 list_add(&tmp->list, pack->safety_records);
 517
 518                 if (create_nameval) {
 519                         nv = find_nameval(pack, s->name, 1);
 520                         if (nv == NULL)
 521                                 return -ENOMEM;
 522                         nv->val = run_addr;
 523                         nv->status = VAL;
 524                 }
 525
 526                 return 1;
 527         }
 528         return 0;
 529 }
 530
 531 int handle_myst_reloc(long pre_addr, int *pre_o, long run_addr,
 532                       int *run_o, struct reloc_addrmap *map, int rerun)
 533 {
 534         int expected;
 535         int offset = (int)(pre_addr + *pre_o - map->addr);
 536         long run_reloc = 0;
 537         long run_reloc_addr;
 538         run_reloc_addr = run_addr + *run_o - offset;
 539         if (map->size == 4)
 540                 run_reloc = *(int *)run_reloc_addr;
 541         else if (map->size == 8)
 542                 run_reloc = *(long long *)run_reloc_addr;
 543         else
 544                 BUG();
 545
 546         if (debug >= 3 && !rerun) {
 547                 printk(KERN_DEBUG "ksplice_h: run-pre: reloc at r_a=%08lx "
 548                        "p_o=%08x: ", run_addr, *pre_o);
 549                 printk("%s=%08lx (A=%08lx *r=%08lx)\n",
 550                        map->nameval->name, map->nameval->val,
 551                        map->addend, run_reloc);
 552         }
 553
 554         if (!starts_with(map->nameval->name, ".rodata.str")) {
 555                 expected = run_reloc - map->addend;
 556                 if ((int)run_reloc == 0x77777777)
 557                         return 1;
 558                 if (map->pcrel)
 559                         expected += run_reloc_addr;
 560                 if (map->nameval->status == NOVAL) {
 561                         map->nameval->val = expected;
 562                         map->nameval->status = TEMP;
 563                 } else if (map->nameval->val != expected) {
 564                         if (rerun)
 565                                 return 1;
 566                         printk(KERN_DEBUG "ksplice_h: pre-run reloc: Expected "
 567                                "%s=%08x!\n", map->nameval->name, expected);
 568                         return 1;
 569                 }
 570         }
 571
 572         *pre_o += map->size - offset;
 573         *run_o += map->size - offset;
 574         return 0;
 575 }
 576
 577 int process_ksplice_relocs(struct module_pack *pack,
 578                            struct ksplice_reloc *relocs)
 579 {
 580         struct ksplice_reloc *r;
 581         for (r = relocs; r->sym_name != NULL; r++) {
 582                 if (process_reloc(pack, r) != 0)
 583                         return -1;
 584         }
 585         return 0;
 586 }
 587
 588 int process_reloc(struct module_pack *pack, struct ksplice_reloc *r)
 589 {
 590         int i, ret;
 591         long off, sym_addr;
 592         struct reloc_addrmap *map;
 593         const long blank_addr = r->blank_sect_addr + r->blank_offset;
 594         LIST_HEAD(vals);
 595 #ifdef KSPLICE_STANDALONE
 596         /* run_pre_reloc: will this reloc be used for run-pre matching? */
 597         const int run_pre_reloc = pack->helper && bootstrapped;
 598 #ifndef CONFIG_KALLSYMS
 599
 600         if (bootstrapped)
 601                 goto skip_using_system_map;
 602 #endif /* CONFIG_KALLSYMS */
 603 #endif /* KSPLICE_STANDALONE */
 604
 605         /* Some Fedora kernel releases have System.map files whose symbol
 606          * addresses disagree with the running kernel by a constant address
 607          * offset because of the CONFIG_PHYSICAL_START and CONFIG_PHYSICAL_ALIGN
 608          * values used to compile these kernels.  This constant address offset
 609          * is always a multiple of 0x100000.
 610          *
 611          * If we observe an offset that is NOT a multiple of 0x100000, then the
 612          * user provided us with an incorrect System.map file, and we should
 613          * abort.
 614          * If we observe an offset that is a multiple of 0x100000, then we can
 615          * adjust the System.map address values accordingly and proceed.
 616          */
 617         off = (long)printk - pack->map_printk;
 618         if (off & 0xfffff) {
 619                 print_abort("System.map does not match kernel");
 620                 return -1;
 621         }
 622         for (i = 0; i < r->num_sym_addrs; i++) {
 623                 ret = add_candidate_val(&vals, r->sym_addrs[i] + off);
 624                 if (ret < 0)
 625                         return ret;
 626         }
 627 #ifndef CONFIG_KALLSYMS
 628 skip_using_system_map:
 629 #endif
 630
 631         if ((r->size == 4 && *(int *)blank_addr != 0x77777777)
 632             || (r->size == 8 &&
 633                 *(long long *)blank_addr != 0x7777777777777777ll)) {
 634                 ksplice_debug(4, KERN_DEBUG "ksplice%s: reloc: skipped %s:%08lx"
 635                               " (altinstr)\n", (pack->helper ? "_h" : ""),
 636                               r->sym_name, r->blank_offset);
 637                 release_vals(&vals);
 638                 return 0;
 639         }
 640
 641         ret = compute_address(pack, r->sym_name, &vals);
 642         if (ret < 0)
 643                 return ret;
 644         if (!singular(&vals)) {
 645                 release_vals(&vals);
 646 #ifdef KSPLICE_STANDALONE
 647                 if (!run_pre_reloc) {
 648 #else
 649                 if (!pack->helper) {
 650 #endif
 651                         failed_to_find(r->sym_name);
 652                         return -1;
 653                 }
 654
 655                 ksplice_debug(4, KERN_DEBUG "ksplice: reloc: deferred %s:%08lx "
 656                               "to run-pre\n", r->sym_name, r->blank_offset);
 657
 658                 map = kmalloc(sizeof(*map), GFP_KERNEL);
 659                 if (map == NULL) {
 660                         print_abort("out of memory");
 661                         return -ENOMEM;
 662                 }
 663                 map->addr = blank_addr;
 664                 map->nameval = find_nameval(pack, r->sym_name, 1);
 665                 if (map->nameval == NULL)
 666                         return -ENOMEM;
 667                 map->addend = r->addend;
 668                 map->pcrel = r->pcrel;
 669                 map->size = r->size;
 670                 list_add(&map->list, pack->reloc_addrmaps);
 671                 return 0;
 672         }
 673         sym_addr = list_entry(vals.next, struct candidate_val, list)->val;
 674         release_vals(&vals);
 675
 676 #ifdef KSPLICE_STANDALONE
 677         if (r->pcrel && run_pre_reloc) {
 678 #else
 679         if (r->pcrel && pack->helper) {
 680 #endif
 681                 map = kmalloc(sizeof(*map), GFP_KERNEL);
 682                 if (map == NULL) {
 683                         print_abort("out of memory");
 684                         return -ENOMEM;
 685                 }
 686                 map->addr = blank_addr;
 687                 map->nameval = find_nameval(pack, "ksplice_zero", 1);
 688                 if (map->nameval == NULL)
 689                         return -ENOMEM;
 690                 map->nameval->val = 0;
 691                 map->nameval->status = VAL;
 692                 map->addend = sym_addr + r->addend;
 693                 map->size = r->size;
 694                 map->pcrel = r->pcrel;
 695                 list_add(&map->list, pack->reloc_addrmaps);
 696
 697         } else {
 698                 long val;
 699                 if (r->pcrel)
 700                         val = sym_addr + r->addend - blank_addr;
 701                 else
 702                         val = sym_addr + r->addend;
 703                 if (r->size == 4)
 704                         *(int *)blank_addr = val;
 705                 else if (r->size == 8)
 706                         *(long long *)blank_addr = val;
 707                 else
 708                         BUG();
 709         }
 710
 711         ksplice_debug(4, KERN_DEBUG "ksplice%s: reloc: %s:%08lx ",
 712                       (pack->helper ? "_h" : ""), r->sym_name, r->blank_offset);
 713         ksplice_debug(4, "(S=%08lx A=%08lx ", sym_addr, r->addend);
 714         if (r->size == 4)
 715                 ksplice_debug(4, "aft=%08x)\n", *(int *)blank_addr);
 716         else if (r->size == 8)
 717                 ksplice_debug(4, "aft=%016llx)\n", *(long long *)blank_addr);
 718         else
 719                 BUG();
 720         return 0;
 721 }
 722
 723 int compute_address(struct module_pack *pack, char *sym_name,
 724                     struct list_head *vals)
 725 {
 726         int i, ret;
 727         const char *prefix[] = { ".text.", ".bss.", ".data.", NULL };
 728 #ifdef KSPLICE_STANDALONE
 729         if (!bootstrapped)
 730                 return 0;
 731 #endif
 732
 733         if (!pack->helper) {
 734                 struct reloc_nameval *nv = find_nameval(pack, sym_name, 0);
 735                 if (nv != NULL && nv->status != NOVAL) {
 736                         release_vals(vals);
 737                         ret = add_candidate_val(vals, nv->val);
 738                         if (ret < 0)
 739                                 return ret;
 740                         ksplice_debug(1, KERN_DEBUG "ksplice: using detected "
 741                                       "sym %s=%08lx\n", sym_name, nv->val);
 742                         return 0;
 743                 }
 744         }
 745
 746         if (starts_with(sym_name, ".rodata"))
 747                 return 0;
 748
 749 #ifdef CONFIG_KALLSYMS
 750         ret = kernel_lookup(sym_name, vals);
 751         if (ret < 0)
 752                 return ret;
 753         ret = other_module_lookup(sym_name, vals, pack->name);
 754         if (ret < 0)
 755                 return ret;
 756 #endif
 757
 758         for (i = 0; prefix[i] != NULL; i++) {
 759                 if (starts_with(sym_name, prefix[i])) {
 760                         ret = compute_address(pack, sym_name +
 761                                               strlen(prefix[i]), vals);
 762                         if (ret < 0)
 763                                 return ret;
 764                 }
 765         }
 766         return 0;
 767 }
 768
 769 #ifdef KSPLICE_STANDALONE
 770 void brute_search_all_mods(struct module_pack *pack, struct ksplice_size *s)
 771 {
 772         struct module *m;
 773         list_for_each_entry(m, &(THIS_MODULE->list), list) {
 774                 if (!starts_with(m->name, pack->name)
 775                     && !ends_with(m->name, "_helper")) {
 776                         if (brute_search(pack, s, m->module_core, m->core_size)
 777                             == 0)
 778                                 return;
 779                         if (brute_search(pack, s, m->module_init, m->init_size)
 780                             == 0)
 781                                 return;
 782                 }
 783         }
 784 }
 785
 786 /* old kernels do not have kcalloc */
 787 void *ksplice_kcalloc(int size)
 788 {
 789         char *mem = kmalloc(size, GFP_KERNEL);
 790         if (mem)
 791                 memset(mem, 0, size);
 792         return mem;
 793 }
 794
 795 #ifdef CONFIG_KALLSYMS
 796 /* Modified version of Linux's kallsyms_lookup_name */
 797 int kernel_lookup(const char *name_wlabel, struct list_head *vals)
 798 {
 799         int ret;
 800         char namebuf[KSYM_NAME_LEN + 1];
 801         unsigned long i;
 802 #if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,10)
 803         unsigned long off;
 804 #endif /* LINUX_VERSION_CODE */
 805
 806         const char *name = dup_wolabel(name_wlabel);
 807         if (name == NULL)
 808                 return -ENOMEM;
 809
 810 /*  kallsyms compression was added by 5648d78927ca65e74aadc88a2b1d6431e55e78ec
 811  *  2.6.10 was the first release after this commit
 812  */
 813 #if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,10)
 814         for (i = 0, off = 0; i < kallsyms_num_syms; i++) {
 815                 off = ksplice_kallsyms_expand_symbol(off, namebuf);
 816
 817                 if (strcmp(namebuf, name) == 0) {
 818                         ret = add_candidate_val(vals, kallsyms_addresses[i]);
 819                         if (ret < 0)
 820                                 return ret;
 821                 }
 822         }
 823 #else /* LINUX_VERSION_CODE */
 824         char *knames;
 825
 826         for (i = 0, knames = kallsyms_names; i < kallsyms_num_syms; i++) {
 827                 unsigned prefix = *knames++;
 828
 829                 strlcpy(namebuf + prefix, knames, KSYM_NAME_LEN - prefix);
 830
 831                 if (strcmp(namebuf, name) == 0) {
 832                         ret = add_candidate_val(vals, kallsyms_addresses[i]);
 833                         if (ret < 0)
 834                                 return ret;
 835                 }
 836
 837                 knames += strlen(knames) + 1;
 838         }
 839 #endif /* LINUX_VERSION_CODE */
 840
 841         kfree(name);
 842         return 0;
 843 }
 844
 845 /*  kallsyms compression was added by 5648d78927ca65e74aadc88a2b1d6431e55e78ec
 846  *  2.6.10 was the first release after this commit
 847  */
 848 #if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,10)
 849 extern u8 kallsyms_token_table[];
 850 extern u16 kallsyms_token_index[];
 851 /* Modified version of Linux's kallsyms_expand_symbol */
 852 long ksplice_kallsyms_expand_symbol(unsigned long off, char *result)
 853 {
 854         long len, skipped_first = 0;
 855         const u8 *tptr, *data;
 856
 857         data = &kallsyms_names[off];
 858         len = *data;
 859         data++;
 860
 861         off += len + 1;
 862
 863         while (len) {
 864                 tptr = &kallsyms_token_table[kallsyms_token_index[*data]];
 865                 data++;
 866                 len--;
 867
 868                 while (*tptr) {
 869                         if (skipped_first) {
 870                                 *result = *tptr;
 871                                 result++;
 872                         } else
 873                                 skipped_first = 1;
 874                         tptr++;
 875                 }
 876         }
 877
 878         *result = '\0';
 879
 880         return off;
 881 }
 882 #endif /* LINUX_VERSION_CODE */
 883
 884 int other_module_lookup(const char *name_wlabel, struct list_head *vals,
 885                         const char *ksplice_name)
 886 {
 887         int ret;
 888         struct module *m;
 889         const char *name = dup_wolabel(name_wlabel);
 890         if (name == NULL)
 891                 return -ENOMEM;
 892
 893         list_for_each_entry(m, &(THIS_MODULE->list), list) {
 894                 if (!starts_with(m->name, ksplice_name)
 895                     && !ends_with(m->name, "_helper")) {
 896                         ret = ksplice_mod_find_sym(m, name, vals);
 897                         if (ret < 0)
 898                                 return ret;
 899                 }
 900         }
 901
 902         kfree(name);
 903         return 0;
 904 }
 905
 906 /* Modified version of Linux's mod_find_symname */
 907 int
 908 ksplice_mod_find_sym(struct module *m, const char *name, struct list_head *vals)
 909 {
 910         int i, ret;
 911         if (strlen(m->name) <= 1)
 912                 return 0;
 913
 914         for (i = 0; i < m->num_symtab; i++) {
 915                 const char *cursym_name = m->strtab + m->symtab[i].st_name;
 916                 if (strncmp(cursym_name, name, strlen(name)) != 0)
 917                         continue;
 918
 919                 cursym_name = dup_wolabel(cursym_name);
 920                 if (cursym_name == NULL)
 921                         return -ENOMEM;
 922                 if (strcmp(cursym_name, name) == 0 &&
 923                     m->symtab[i].st_value != 0) {
 924                         ret = add_candidate_val(vals, m->symtab[i].st_value);
 925                         if (ret < 0)
 926                                 return ret;
 927                 }
 928                 kfree(cursym_name);
 929         }
 930         return 0;
 931 }
 932 #endif /* CONFIG_KALLSYMS */
 933 #else /* KSPLICE_STANDALONE */
 934 EXPORT_SYMBOL_GPL(init_ksplice_module);
 935 EXPORT_SYMBOL_GPL(cleanup_ksplice_module);
 936
 937 struct accumulate_struct {
 938         const char *desired_name;
 939         struct list_head *vals;
 940 };
 941
 942 int init_module(void)
 943 {
 944         return 0;
 945 }
 946
 947 void cleanup_module(void)
 948 {
 949 }
 950
 951 int accumulate_matching_names(void *data, const char *sym_name, long sym_val)
 952 {
 953         int ret;
 954         struct accumulate_struct *acc = data;
 955
 956         if (strncmp(sym_name, acc->desired_name, strlen(acc->desired_name)) !=
 957             0)
 958                 return 0;
 959
 960         sym_name = dup_wolabel(sym_name);
 961         if (sym_name == NULL)
 962                 return -ENOMEM;
 963         /* TODO: possibly remove "&& sym_val != 0" */
 964         if (strcmp(sym_name, acc->desired_name) == 0 && sym_val != 0) {
 965                 ret = add_candidate_val(acc->vals, sym_val);
 966                 if (ret < 0)
 967                         return ret;
 968         }
 969         kfree(sym_name);
 970         return 0;
 971 }
 972
 973 int kernel_lookup(const char *name_wlabel, struct list_head *vals)
 974 {
 975         int ret;
 976         struct accumulate_struct acc = { dup_wolabel(name_wlabel), vals };
 977         if (acc.desired_name == NULL)
 978                 return -ENOMEM;
 979         ret = kallsyms_on_each_symbol(accumulate_matching_names, &acc);
 980         if (ret < 0)
 981                 return ret;
 982         kfree(acc.desired_name);
 983         return 0;
 984 }
 985
 986 int other_module_lookup(const char *name_wlabel, struct list_head *vals,
 987                         const char *ksplice_name)
 988 {
 989         int ret;
 990         struct accumulate_struct acc = { dup_wolabel(name_wlabel), vals };
 991         struct module *m;
 992
 993         if (acc.desired_name == NULL)
 994                 return -ENOMEM;
 995
 996         list_for_each_entry(m, &(THIS_MODULE->list), list) {
 997                 if (!starts_with(m->name, ksplice_name)
 998                     && !ends_with(m->name, "_helper")) {
 999                         ret = module_on_each_symbol(m,
1000                                                     accumulate_matching_names,
1001                                                     &acc);
1002                         if (ret < 0)
1003                                 return ret;
1004                 }
1005         }
1006
1007         kfree(acc.desired_name);
1008         return 0;
1009 }
1010 #endif /* KSPLICE_STANDALONE */
1011
1012 int add_candidate_val(struct list_head *vals, long val)
1013 {
1014         struct candidate_val *tmp, *new;
1015
1016         list_for_each_entry(tmp, vals, list) {
1017                 if (tmp->val == val)
1018                         return 0;
1019         }
1020         new = kmalloc(sizeof(*new), GFP_KERNEL);
1021         if (new == NULL) {
1022                 print_abort("out of memory");
1023                 return -ENOMEM;
1024         }
1025         new->val = val;
1026         list_add(&new->list, vals);
1027         return 0;
1028 }
1029
1030 void release_vals(struct list_head *vals)
1031 {
1032         clear_list(vals, struct candidate_val, list);
1033 }
1034
1035 struct reloc_nameval *find_nameval(struct module_pack *pack, char *name,
1036                                    int create)
1037 {
1038         struct reloc_nameval *nv, *new;
1039         char *newname;
1040         list_for_each_entry(nv, pack->reloc_namevals, list) {
1041                 newname = nv->name;
1042                 if (starts_with(newname, ".text."))
1043                         newname += 6;
1044                 if (strcmp(newname, name) == 0)
1045                         return nv;
1046         }
1047         if (!create)
1048                 return NULL;
1049
1050         new = kmalloc(sizeof(*new), GFP_KERNEL);
1051         if (new == NULL) {
1052                 print_abort("out of memory");
1053                 return NULL;
1054         }
1055         new->name = name;
1056         new->val = 0;
1057         new->status = NOVAL;
1058         list_add(&new->list, pack->reloc_namevals);
1059         return new;
1060 }
1061
1062 struct reloc_addrmap *find_addrmap(struct module_pack *pack, long addr)
1063 {
1064         struct reloc_addrmap *map;
1065         list_for_each_entry(map, pack->reloc_addrmaps, list) {
1066                 if (addr >= map->addr && addr < map->addr + map->size)
1067                         return map;
1068         }
1069         return NULL;
1070 }
1071
1072 void set_temp_myst_relocs(struct module_pack *pack, int status_val)
1073 {
1074         struct reloc_nameval *nv;
1075         list_for_each_entry(nv, pack->reloc_namevals, list) {
1076                 if (nv->status == TEMP)
1077                         nv->status = status_val;
1078         }
1079 }
1080
1081 int starts_with(const char *str, const char *prefix)
1082 {
1083         return strncmp(str, prefix, strlen(prefix)) == 0;
1084 }
1085
1086 int ends_with(const char *str, const char *suffix)
1087 {
1088         return strlen(str) >= strlen(suffix) &&
1089             strcmp(&str[strlen(str) - strlen(suffix)], suffix) == 0;
1090 }
1091
1092 int label_offset(const char *sym_name)
1093 {
1094         int i;
1095         for (i = 0;
1096              sym_name[i] != 0 && sym_name[i + 1] != 0 && sym_name[i + 2] != 0
1097              && sym_name[i + 3] != 0; i++) {
1098                 if (sym_name[i] == '_' && sym_name[i + 1] == '_'
1099                     && sym_name[i + 2] == '_' && sym_name[i + 3] == '_')
1100                         return i + 4;
1101         }
1102         return -1;
1103 }
1104
1105 const char *dup_wolabel(const char *sym_name)
1106 {
1107         int offset, entire_strlen, label_strlen, new_strlen;
1108         char *newstr;
1109
1110         offset = label_offset(sym_name);
1111         if (offset == -1)
1112                 label_strlen = 0;
1113         else
1114                 label_strlen = strlen(&sym_name[offset]) + strlen("____");
1115
1116         entire_strlen = strlen(sym_name);
1117         new_strlen = entire_strlen - label_strlen;
1118         newstr = kmalloc(new_strlen + 1, GFP_KERNEL);
1119         if (newstr == NULL) {
1120                 print_abort("out of memory");
1121                 return NULL;
1122         }
1123         memcpy(newstr, sym_name, new_strlen);
1124         newstr[new_strlen] = 0;
1125         return newstr;
1126 }
1127
1128 MODULE_LICENSE("GPL v2");
1129 MODULE_AUTHOR("Jeffrey Brian Arnold <jbarnold@mit.edu>");