ld.c

   1 /*
   2  * ld - a small static linker
   3  *
   4  * Copyright (C) 2010 Ali Gholami Rudi
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License, as published by the
   8  * Free Software Foundation.
   9  */
  10 #include <elf.h>
  11 #include <fcntl.h>
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <sys/stat.h>
  15 #include <string.h>
  16 #include <unistd.h>
  17
  18 #define SRCADDR         0x4000000ul
  19 #define DATADDR         0x6000000ul
  20 #define BSSADDR         0x8000000ul
  21 #define MAXSECS         (1 << 10)
  22 #define MAXOBJS         (1 << 7)
  23 #define MAXSYMS         (1 << 12)
  24 #define PAGE_SIZE       (1 << 12)
  25 #define GOT_PAD         16
  26 #define MAXFILES        (1 << 10)
  27
  28 #define ALIGN(x,a)              __ALIGN_MASK(x,(typeof(x))(a)-1)
  29 #define __ALIGN_MASK(x,mask)    (((x)+(mask))&~(mask))
  30
  31 struct obj {
  32         char *mem;
  33         Elf64_Ehdr *ehdr;
  34         Elf64_Shdr *shdr;
  35         Elf64_Sym *syms;
  36         int nsyms;
  37         char *symstr;
  38         char *shstr;
  39 };
  40
  41 struct secmap {
  42         Elf64_Shdr *o_shdr;
  43         struct obj *obj;
  44         unsigned long vaddr;
  45         unsigned long faddr;
  46 };
  47
  48 struct bss_sym {
  49         Elf64_Sym *sym;
  50         int off;
  51 };
  52
  53 struct got_sym {
  54         Elf64_Sym *sym;
  55         struct obj *obj;
  56 };
  57
  58 struct outelf {
  59         Elf64_Ehdr ehdr;
  60         Elf64_Phdr phdr[MAXSECS];
  61         int nph;
  62         struct secmap secs[MAXSECS];
  63         int nsecs;
  64         struct obj objs[MAXOBJS];
  65         int nobjs;
  66
  67         unsigned long code_addr;
  68         unsigned long phdr_faddr;
  69
  70         /* bss section */
  71         struct bss_sym bss_syms[MAXSYMS];
  72         int nbss_syms;
  73         unsigned long bss_vaddr;
  74         int bss_len;
  75
  76         /* got/plt section */
  77         struct got_sym got_syms[MAXSYMS];
  78         int ngot_syms;
  79         unsigned long got_vaddr;
  80         unsigned long got_faddr;
  81 };
  82
  83 static Elf64_Sym *obj_find(struct obj *obj, char *name)
  84 {
  85         int i;
  86         for (i = 0; i < obj->nsyms; i++) {
  87                 Elf64_Sym *sym = &obj->syms[i];
  88                 if (ELF64_ST_BIND(sym->st_info) == STB_LOCAL ||
  89                                 sym->st_shndx == SHN_UNDEF)
  90                         continue;
  91                 if (!strcmp(name, obj->symstr + sym->st_name))
  92                         return sym;
  93         }
  94         return NULL;
  95 }
  96
  97 static void obj_init(struct obj *obj, char *mem)
  98 {
  99         int i;
 100         obj->mem = mem;
 101         obj->ehdr = (void *) mem;
 102         obj->shdr = (void *) (mem + obj->ehdr->e_shoff);
 103         obj->shstr = mem + obj->shdr[obj->ehdr->e_shstrndx].sh_offset;
 104         for (i = 0; i < obj->ehdr->e_shnum; i++) {
 105                 if (obj->shdr[i].sh_type != SHT_SYMTAB)
 106                         continue;
 107                 obj->symstr = mem + obj->shdr[obj->shdr[i].sh_link].sh_offset;
 108                 obj->syms = (void *) (mem + obj->shdr[i].sh_offset);
 109                 obj->nsyms = obj->shdr[i].sh_size / sizeof(*obj->syms);
 110         }
 111 }
 112
 113 static void outelf_init(struct outelf *oe)
 114 {
 115         memset(oe, 0, sizeof(*oe));
 116         oe->ehdr.e_ident[0] = 0x7f;
 117         oe->ehdr.e_ident[1] = 'E';
 118         oe->ehdr.e_ident[2] = 'L';
 119         oe->ehdr.e_ident[3] = 'F';
 120         oe->ehdr.e_ident[4] = ELFCLASS64;
 121         oe->ehdr.e_ident[5] = ELFDATA2LSB;
 122         oe->ehdr.e_ident[6] = EV_CURRENT;
 123         oe->ehdr.e_type = ET_EXEC;
 124         oe->ehdr.e_machine = EM_X86_64;
 125         oe->ehdr.e_version = EV_CURRENT;
 126         oe->ehdr.e_shstrndx = SHN_UNDEF;
 127         oe->ehdr.e_ehsize = sizeof(oe->ehdr);
 128         oe->ehdr.e_phentsize = sizeof(oe->phdr[0]);
 129         oe->ehdr.e_shentsize = sizeof(Elf64_Shdr);
 130 }
 131
 132 static struct secmap *outelf_mapping(struct outelf *oe, Elf64_Shdr *shdr)
 133 {
 134         int i;
 135         for (i = 0; i < oe->nsecs; i++)
 136                 if (oe->secs[i].o_shdr == shdr)
 137                         return &oe->secs[i];
 138         return NULL;
 139 }
 140
 141 static int outelf_find(struct outelf *oe, char *name,
 142                         struct obj **sym_obj, Elf64_Sym **sym_sym)
 143 {
 144         int i;
 145         for (i = 0; i < oe->nobjs; i++) {
 146                 struct obj *obj = &oe->objs[i];
 147                 Elf64_Sym *sym;
 148                 if ((sym = obj_find(obj, name))) {
 149                         *sym_obj = obj;
 150                         *sym_sym = sym;
 151                         return 0;
 152                 }
 153         }
 154         return 1;
 155 }
 156
 157 static unsigned long bss_addr(struct outelf *oe, Elf64_Sym *sym)
 158 {
 159         int i;
 160         for (i = 0; i < oe->nbss_syms; i++)
 161                 if (oe->bss_syms[i].sym == sym)
 162                         return oe->bss_vaddr + oe->bss_syms[i].off;
 163         return 0;
 164 }
 165
 166 static unsigned long symval(struct outelf *oe, struct obj *obj, Elf64_Sym *sym)
 167 {
 168         struct secmap *sec;
 169         char *name = obj ? obj->symstr + sym->st_name : NULL;
 170         int s_idx, s_off;
 171         switch (ELF64_ST_TYPE(sym->st_info)) {
 172         case STT_SECTION:
 173                 if ((sec = outelf_mapping(oe, &obj->shdr[sym->st_shndx])))
 174                         return sec->vaddr;
 175                 break;
 176         case STT_NOTYPE:
 177         case STT_OBJECT:
 178         case STT_FUNC:
 179                 if (name && *name && sym->st_shndx == SHN_UNDEF)
 180                         outelf_find(oe, name, &obj, &sym);
 181                 if (sym->st_shndx == SHN_COMMON)
 182                         return bss_addr(oe, sym);
 183                 s_idx = sym->st_shndx;
 184                 s_off = sym->st_value;
 185                 sec = outelf_mapping(oe, &obj->shdr[s_idx]);
 186                 if ((sec = outelf_mapping(oe, &obj->shdr[s_idx])))
 187                         return sec->vaddr + s_off;
 188         }
 189         return 0;
 190 }
 191
 192 static void die(char *msg)
 193 {
 194         write(1, msg, strlen(msg));
 195         exit(1);
 196 }
 197
 198 static unsigned long outelf_addr(struct outelf *oe, char *name)
 199 {
 200         struct obj *obj;
 201         Elf64_Sym *sym;
 202         if (outelf_find(oe, name, &obj, &sym))
 203                 die("unknown symbol!\n");
 204         return symval(oe, obj, sym);
 205 }
 206
 207 static int got_offset(struct outelf *oe, struct obj *obj, Elf64_Sym *sym)
 208 {
 209         char *name = obj->symstr + sym->st_name;
 210         int n;
 211         int i;
 212         if (name && *name && sym->st_shndx == SHN_UNDEF)
 213                 outelf_find(oe, name, &obj, &sym);
 214         for (i = 0; i < oe->ngot_syms; i++)
 215                 if (oe->got_syms[i].sym == sym)
 216                         return i * 8;
 217         n = oe->ngot_syms++;
 218         oe->got_syms[n].sym = sym;
 219         oe->got_syms[n].obj = obj;
 220         return n * 8;
 221 }
 222
 223 static void outelf_reloc_sec(struct outelf *oe, int o_idx, int s_idx)
 224 {
 225         struct obj *obj = &oe->objs[o_idx];
 226         Elf64_Shdr *rel_shdr = &obj->shdr[s_idx];
 227         Elf64_Rela *rel = (void *) obj->mem + obj->shdr[s_idx].sh_offset;
 228         Elf64_Shdr *other_shdr = &obj->shdr[rel_shdr->sh_info];
 229         void *other = (void *) obj->mem + other_shdr->sh_offset;
 230         int nrel = rel_shdr->sh_size / sizeof(*rel);
 231         unsigned long addr;
 232         int i;
 233         for (i = 0; i < nrel; i++) {
 234                 int sym_idx = ELF64_R_SYM(rel[i].r_info);
 235                 Elf64_Sym *sym = &obj->syms[sym_idx];
 236                 unsigned long val = symval(oe, obj, sym) + rel[i].r_addend;
 237                 unsigned long *dst = other + rel[i].r_offset;
 238                 switch (ELF64_R_TYPE(rel[i].r_info)) {
 239                 case R_X86_64_NONE:
 240                         break;
 241                 case R_X86_64_32:
 242                 case R_X86_64_32S:
 243                         *(unsigned int *) dst = val;
 244                         break;
 245                 case R_X86_64_64:
 246                         *dst = val;
 247                         break;
 248                 case R_X86_64_PC32:
 249                 case R_X86_64_PLT32:
 250                         addr = outelf_mapping(oe, other_shdr)->vaddr +
 251                                 rel[i].r_offset;
 252                         *(unsigned int *) dst += val - addr;
 253                         break;
 254                 case R_X86_64_GOTPCREL:
 255                         addr = outelf_mapping(oe, other_shdr)->vaddr +
 256                                 rel[i].r_offset;
 257                         val = got_offset(oe, obj, sym) +
 258                                 oe->got_vaddr + rel[i].r_addend;
 259                         *(unsigned int *) dst += val - addr;
 260                         break;
 261                 default:
 262                         die("unknown relocation type\n");
 263                 }
 264         }
 265 }
 266
 267 static void outelf_reloc(struct outelf *oe)
 268 {
 269         int i, j;
 270         for (i = 0; i < oe->nobjs; i++) {
 271                 struct obj *obj = &oe->objs[i];
 272                 for (j = 0; j < obj->ehdr->e_shnum; j++)
 273                         if (obj->shdr[j].sh_type == SHT_RELA)
 274                                 outelf_reloc_sec(oe, i, j);
 275         }
 276 }
 277
 278 static void alloc_bss(struct outelf *oe, Elf64_Sym *sym)
 279 {
 280         int n = oe->nbss_syms++;
 281         int off = ALIGN(oe->bss_len, sym->st_value);
 282         oe->bss_syms[n].sym = sym;
 283         oe->bss_syms[n].off = off + sym->st_size;
 284         oe->bss_len += off + sym->st_size;
 285 }
 286
 287 static void outelf_bss(struct outelf *oe)
 288 {
 289         int i, j;
 290         for (i = 0; i < oe->nobjs; i++) {
 291                 struct obj *obj = &oe->objs[i];
 292                 for (j = 0; j < obj->nsyms; j++)
 293                         if (obj->syms[j].st_shndx == SHN_COMMON)
 294                                 alloc_bss(oe, &obj->syms[j]);
 295         }
 296 }
 297
 298 static int outelf_putgot(struct outelf *oe, char *buf)
 299 {
 300         unsigned long *got = (void *) buf;
 301         int len = 8 * oe->ngot_syms;
 302         int i;
 303         for (i = 0; i < oe->ngot_syms; i++)
 304                 got[i] = symval(oe, oe->got_syms[i].obj,
 305                                 oe->got_syms[i].sym);
 306         memset(buf + len, 0, GOT_PAD);
 307         return len + GOT_PAD;
 308 }
 309
 310 #define SEC_CODE(s)     ((s)->sh_flags & SHF_EXECINSTR)
 311 #define SEC_BSS(s)      ((s)->sh_type == SHT_NOBITS)
 312 #define SEC_DATA(s)     (!SEC_CODE(s) && !SEC_BSS(s))
 313
 314 static void outelf_write(struct outelf *oe, int fd)
 315 {
 316         int i;
 317         char buf[1 << 14];
 318         int got_len;
 319         oe->ehdr.e_entry = outelf_addr(oe, "_start");
 320         got_len = outelf_putgot(oe, buf);
 321
 322         oe->ehdr.e_phnum = oe->nph;
 323         oe->ehdr.e_phoff = oe->phdr_faddr;
 324         write(fd, &oe->ehdr, sizeof(oe->ehdr));
 325         for (i = 0; i < oe->nsecs; i++) {
 326                 struct secmap *sec = &oe->secs[i];
 327                 char *buf = sec->obj->mem + sec->o_shdr->sh_offset;
 328                 int len = sec->o_shdr->sh_size;
 329                 if (SEC_BSS(sec->o_shdr))
 330                         continue;
 331                 lseek(fd, sec->faddr, SEEK_SET);
 332                 write(fd, buf, len);
 333         }
 334         lseek(fd, oe->got_faddr, SEEK_SET);
 335         write(fd, buf, got_len);
 336         lseek(fd, oe->phdr_faddr, SEEK_SET);
 337         write(fd, &oe->phdr, oe->nph * sizeof(oe->phdr[0]));
 338 }
 339
 340 static void outelf_add(struct outelf *oe, char *mem)
 341 {
 342         Elf64_Ehdr *ehdr = (void *) mem;
 343         Elf64_Shdr *shdr = (void *) (mem + ehdr->e_shoff);
 344         struct obj *obj;
 345         int i;
 346         if (ehdr->e_type != ET_REL)
 347                 return;
 348         obj = &oe->objs[oe->nobjs++];
 349         obj_init(obj, mem);
 350         for (i = 0; i < ehdr->e_shnum; i++) {
 351                 struct secmap *sec;
 352                 if (!(shdr[i].sh_flags & 0x7))
 353                         continue;
 354                 sec = &oe->secs[oe->nsecs++];
 355                 sec->o_shdr = &shdr[i];
 356                 sec->obj = obj;
 357         }
 358 }
 359
 360 static void outelf_link(struct outelf *oe)
 361 {
 362         int i;
 363         Elf64_Phdr *code_phdr = &oe->phdr[oe->nph++];
 364         Elf64_Phdr *bss_phdr = &oe->phdr[oe->nph++];
 365         Elf64_Phdr *data_phdr = &oe->phdr[oe->nph++];
 366         unsigned long vaddr = SRCADDR + sizeof(oe->ehdr);
 367         unsigned long faddr = sizeof(oe->ehdr);
 368         int len = 0;
 369         for (i = 0; i < oe->nsecs; i++) {
 370                 struct secmap *sec = &oe->secs[i];
 371                 if (!SEC_CODE(sec->o_shdr))
 372                         continue;
 373                 sec->vaddr = vaddr + len;
 374                 sec->faddr = faddr + len;
 375                 len += sec->o_shdr->sh_size;
 376         }
 377         code_phdr->p_type = PT_LOAD;
 378         code_phdr->p_flags = PF_R | PF_W | PF_X;
 379         code_phdr->p_vaddr = vaddr;
 380         code_phdr->p_paddr = vaddr;
 381         code_phdr->p_offset = faddr;
 382         code_phdr->p_filesz = len;
 383         code_phdr->p_memsz = len;
 384         code_phdr->p_align = PAGE_SIZE;
 385
 386         faddr += len;
 387         vaddr = BSSADDR + faddr % PAGE_SIZE;
 388         len = 0;
 389         outelf_bss(oe);
 390         oe->bss_vaddr = vaddr + len;
 391         len += oe->bss_len;
 392         for (i = 0; i < oe->nsecs; i++) {
 393                 struct secmap *sec = &oe->secs[i];
 394                 if (!SEC_BSS(sec->o_shdr))
 395                         continue;
 396                 sec->vaddr = vaddr + len;
 397                 sec->faddr = faddr;
 398                 len += sec->o_shdr->sh_size;
 399         }
 400         bss_phdr->p_type = PT_LOAD;
 401         bss_phdr->p_flags = PF_R | PF_W;
 402         bss_phdr->p_vaddr = vaddr;
 403         bss_phdr->p_paddr = vaddr;
 404         bss_phdr->p_offset = faddr;
 405         bss_phdr->p_filesz = 0;
 406         bss_phdr->p_memsz = len;
 407         bss_phdr->p_align = PAGE_SIZE;
 408
 409         vaddr = DATADDR + faddr % PAGE_SIZE;
 410         len = 0;
 411         for (i = 0; i < oe->nsecs; i++) {
 412                 struct secmap *sec = &oe->secs[i];
 413                 if (!SEC_DATA(sec->o_shdr))
 414                         continue;
 415                 sec->vaddr = vaddr + len;
 416                 sec->faddr = faddr + len;
 417                 len += sec->o_shdr->sh_size;
 418         }
 419         oe->got_faddr = faddr + len;
 420         oe->got_vaddr = vaddr + len;
 421         len += oe->ngot_syms * 8 + GOT_PAD;
 422         outelf_reloc(oe);
 423
 424         data_phdr->p_type = PT_LOAD;
 425         data_phdr->p_flags = PF_R | PF_W | PF_X;
 426         data_phdr->p_align = PAGE_SIZE;
 427         data_phdr->p_vaddr = vaddr;
 428         data_phdr->p_paddr = vaddr;
 429         data_phdr->p_filesz = len;
 430         data_phdr->p_memsz = len;
 431         data_phdr->p_offset = faddr;
 432
 433         oe->phdr_faddr = faddr + len;
 434 }
 435
 436 struct arhdr {
 437         char ar_name[16];
 438         char ar_date[12];
 439         char ar_uid[6];
 440         char ar_gid[6];
 441         char ar_mode[8];
 442         char ar_size[10];
 443         char ar_fmag[2];
 444 };
 445
 446 static int get_be32(unsigned char *s)
 447 {
 448         return s[3] | (s[2] << 8) | (s[1] << 16) | (s[0] << 32);
 449 }
 450
 451 static int sym_undef(struct outelf *oe, char *name)
 452 {
 453         int i, j;
 454         int undef = 0;
 455         for (i = 0; i < oe->nobjs; i++) {
 456                 struct obj *obj = &oe->objs[i];
 457                 for (j = 0; j < obj->nsyms; j++) {
 458                         Elf64_Sym *sym = &obj->syms[j];
 459                         if (ELF64_ST_BIND(sym->st_info) == STB_LOCAL)
 460                                 continue;
 461                         if (strcmp(name, obj->symstr + sym->st_name))
 462                                 continue;
 463                         if (sym->st_shndx != SHN_UNDEF)
 464                                 return 0;
 465                         undef = 1;
 466                 }
 467         }
 468         return undef;
 469 }
 470
 471 static int outelf_ar_link(struct outelf *oe, char *ar, int base)
 472 {
 473         char *ar_index;
 474         char *ar_name;
 475         int nsyms = get_be32((void *) ar);
 476         int added = 0;
 477         int i;
 478         ar_index = ar + 4;
 479         ar_name = ar_index + nsyms * 4;
 480         for (i = 0; i < nsyms; i++) {
 481                 int off = get_be32((void *) ar_index + i * 4) +
 482                                 sizeof(struct arhdr);
 483                 if (sym_undef(oe, ar_name)) {
 484                         outelf_add(oe, ar - base + off);
 485                         added++;
 486                 }
 487                 ar_name = strchr(ar_name, '\0') + 1;
 488         }
 489         return added;
 490 }
 491
 492 static void link_archive(struct outelf *oe, char *ar)
 493 {
 494         char *beg = ar;
 495
 496         /* skip magic */
 497         ar += 8;
 498         for(;;) {
 499                 struct arhdr *hdr = (void *) ar;
 500                 int size;
 501                 ar += sizeof(*hdr);
 502                 hdr->ar_size[sizeof(hdr->ar_size) - 1] = '\0';
 503                 size = atoi(hdr->ar_size);
 504                 size = (size + 1) & ~1;
 505                 if (!strncmp(hdr->ar_name, "/ ", 2)) {
 506                         while (outelf_ar_link(oe, ar, ar - beg))
 507                                 ;
 508                         return;
 509                 }
 510                 if (!strncmp(hdr->ar_name, "// ", 3))
 511                         outelf_add(oe, ar);
 512                 ar += size;
 513         }
 514 }
 515
 516 static long filesize(int fd)
 517 {
 518         struct stat stat;
 519         fstat(fd, &stat);
 520         return stat.st_size;
 521 }
 522
 523 static char *fileread(char *path)
 524 {
 525         int fd = open(path, O_RDONLY);
 526         int size = filesize(fd);
 527         char *buf = malloc(size);
 528         read(fd, buf, size);
 529         close(fd);
 530         return buf;
 531 }
 532
 533 static int is_ar(char *path)
 534 {
 535         int len = strlen(path);
 536         return len > 2 && path[len - 2] == '.' && path[len - 1] == 'a';
 537 }
 538
 539 int main(int argc, char **argv)
 540 {
 541         char out[1 << 10] = "a.out";
 542         char *buf;
 543         struct outelf oe;
 544         char *mem[MAXFILES];
 545         int nmem = 0;
 546         int fd;
 547         int i = 0;
 548         if (argc < 2)
 549                 die("no object given\n");
 550         outelf_init(&oe);
 551
 552         while (++i < argc) {
 553                 if (!strcmp("-o", argv[i])) {
 554                         strcpy(out, argv[++i]);
 555                         continue;
 556                 }
 557                 if (!strcmp("-g", argv[i]))
 558                         continue;
 559                 buf = fileread(argv[i]);
 560                 mem[nmem++] = buf;
 561                 if (!buf)
 562                         die("cannot open object\n");
 563                 if (is_ar(argv[i]))
 564                         link_archive(&oe, buf);
 565                 else
 566                         outelf_add(&oe, buf);
 567         }
 568         outelf_link(&oe);
 569         fd = open(out, O_WRONLY | O_TRUNC | O_CREAT, 0700);
 570         outelf_write(&oe, fd);
 571         close(fd);
 572         for (i = 0; i < nmem; i++)
 573                 free(mem[i]);
 574         return 0;
 575 }