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