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 MAX(a, b)       ((a) > (b) ? (a) : (b))
  30 #define ALIGN(x, a)     (((x) + (long) (a) - 1) & ~((long) (a) - 1))
  31
  32 struct obj {
  33         char *mem;
  34         Elf32_Ehdr *ehdr;
  35         Elf32_Shdr *shdr;
  36         Elf32_Sym *syms;
  37         int nsyms;
  38         char *symstr;
  39         char *shstr;
  40 };
  41
  42 struct secmap {
  43         Elf32_Shdr *o_shdr;
  44         struct obj *obj;
  45         unsigned long vaddr;
  46         unsigned long faddr;
  47 };
  48
  49 struct bss_sym {
  50         Elf32_Sym *sym;
  51         int off;
  52 };
  53
  54 struct got_sym {
  55         Elf32_Sym *sym;
  56         struct obj *obj;
  57 };
  58
  59 struct outelf {
  60         Elf32_Ehdr ehdr;
  61         Elf32_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 Elf32_Sym *obj_find(struct obj *obj, char *name)
  85 {
  86         int i;
  87         for (i = 0; i < obj->nsyms; i++) {
  88                 Elf32_Sym *sym = &obj->syms[i];
  89                 if (ELF32_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] = ELFCLASS32;
 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_386;
 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(Elf32_Shdr);
 131 }
 132
 133 static struct secmap *outelf_mapping(struct outelf *oe, Elf32_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, Elf32_Sym **sym_sym)
 144 {
 145         int i;
 146         for (i = 0; i < oe->nobjs; i++) {
 147                 struct obj *obj = &oe->objs[i];
 148                 Elf32_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, Elf32_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 void die(char *msg)
 168 {
 169         write(1, msg, strlen(msg));
 170         exit(1);
 171 }
 172
 173 static void warn_undef(char *name)
 174 {
 175         char msg[128];
 176         strcpy(msg, name);
 177         strcpy(msg + strlen(msg), " undefined\n");
 178         die(msg);
 179 }
 180
 181 static unsigned long symval(struct outelf *oe, struct obj *obj, Elf32_Sym *sym)
 182 {
 183         struct secmap *sec;
 184         char *name = obj ? obj->symstr + sym->st_name : NULL;
 185         int s_idx, s_off;
 186         switch (ELF32_ST_TYPE(sym->st_info)) {
 187         case STT_SECTION:
 188                 if ((sec = outelf_mapping(oe, &obj->shdr[sym->st_shndx])))
 189                         return sec->vaddr;
 190                 break;
 191         case STT_NOTYPE:
 192         case STT_OBJECT:
 193         case STT_FUNC:
 194                 if (name && *name && sym->st_shndx == SHN_UNDEF)
 195                         if (outelf_find(oe, name, &obj, &sym))
 196                                 warn_undef(name);
 197                 if (sym->st_shndx == SHN_COMMON)
 198                         return bss_addr(oe, sym);
 199                 s_idx = sym->st_shndx;
 200                 s_off = sym->st_value;
 201                 sec = outelf_mapping(oe, &obj->shdr[s_idx]);
 202                 if ((sec = outelf_mapping(oe, &obj->shdr[s_idx])))
 203                         return sec->vaddr + s_off;
 204         }
 205         return 0;
 206 }
 207
 208 static unsigned long outelf_addr(struct outelf *oe, char *name)
 209 {
 210         struct obj *obj;
 211         Elf32_Sym *sym;
 212         if (outelf_find(oe, name, &obj, &sym))
 213                 die("unknown symbol!\n");
 214         return symval(oe, obj, sym);
 215 }
 216
 217 static void outelf_reloc_sec(struct outelf *oe, int o_idx, int s_idx)
 218 {
 219         struct obj *obj = &oe->objs[o_idx];
 220         Elf32_Shdr *rel_shdr = &obj->shdr[s_idx];
 221         Elf32_Rel *rels = (void *) obj->mem + obj->shdr[s_idx].sh_offset;
 222         Elf32_Shdr *other_shdr = &obj->shdr[rel_shdr->sh_info];
 223         void *other = (void *) obj->mem + other_shdr->sh_offset;
 224         int nrels = rel_shdr->sh_size / sizeof(*rels);
 225         unsigned long addr;
 226         int i;
 227         for (i = 0; i < nrels; i++) {
 228                 Elf32_Rela *rel = &rels[i];
 229                 int sym_idx = ELF32_R_SYM(rel->r_info);
 230                 Elf32_Sym *sym = &obj->syms[sym_idx];
 231                 unsigned long val = symval(oe, obj, sym);
 232                 unsigned long *dst = other + rel->r_offset;
 233                 switch (ELF32_R_TYPE(rel->r_info)) {
 234                 case R_386_NONE:
 235                         break;
 236                 case R_386_16:
 237                         *(unsigned short *) dst += val;
 238                         break;
 239                 case R_386_32:
 240                         *dst += val;
 241                         break;
 242                 case R_386_PC32:
 243                 case R_386_PLT32:
 244                         addr = outelf_mapping(oe, other_shdr)->vaddr +
 245                                 rel->r_offset;
 246                         *dst += val - addr;
 247                         break;
 248                 default:
 249                         die("unknown relocation type\n");
 250                 }
 251         }
 252 }
 253
 254 static void outelf_reloc(struct outelf *oe)
 255 {
 256         int i, j;
 257         for (i = 0; i < oe->nobjs; i++) {
 258                 struct obj *obj = &oe->objs[i];
 259                 for (j = 0; j < obj->ehdr->e_shnum; j++)
 260                         if (obj->shdr[j].sh_type == SHT_REL)
 261                                 outelf_reloc_sec(oe, i, j);
 262         }
 263 }
 264
 265 static void alloc_bss(struct outelf *oe, Elf32_Sym *sym)
 266 {
 267         int n = oe->nbss_syms++;
 268         int off = ALIGN(oe->bss_len, MAX(sym->st_value, 4));
 269         oe->bss_syms[n].sym = sym;
 270         oe->bss_syms[n].off = off + sym->st_size;
 271         oe->bss_len += off + sym->st_size;
 272 }
 273
 274 static void outelf_bss(struct outelf *oe)
 275 {
 276         int i, j;
 277         for (i = 0; i < oe->nobjs; i++) {
 278                 struct obj *obj = &oe->objs[i];
 279                 for (j = 0; j < obj->nsyms; j++)
 280                         if (obj->syms[j].st_shndx == SHN_COMMON)
 281                                 alloc_bss(oe, &obj->syms[j]);
 282         }
 283 }
 284
 285 static int outelf_putgot(struct outelf *oe, char *buf)
 286 {
 287         unsigned long *got = (void *) buf;
 288         int len = 4 * oe->ngot_syms;
 289         int i;
 290         for (i = 0; i < oe->ngot_syms; i++)
 291                 got[i] = symval(oe, oe->got_syms[i].obj,
 292                                 oe->got_syms[i].sym);
 293         memset(buf + len, 0, GOT_PAD);
 294         return len + GOT_PAD;
 295 }
 296
 297 #define SEC_CODE(s)     ((s)->sh_flags & SHF_EXECINSTR)
 298 #define SEC_BSS(s)      ((s)->sh_type == SHT_NOBITS)
 299 #define SEC_DATA(s)     (!SEC_CODE(s) && !SEC_BSS(s))
 300
 301 static void outelf_write(struct outelf *oe, int fd)
 302 {
 303         int i;
 304         char buf[1 << 14];
 305         int got_len;
 306         oe->ehdr.e_entry = outelf_addr(oe, "_start");
 307         got_len = outelf_putgot(oe, buf);
 308
 309         oe->ehdr.e_phnum = oe->nph;
 310         oe->ehdr.e_phoff = sizeof(oe->ehdr);
 311         lseek(fd, 0, SEEK_SET);
 312         write(fd, &oe->ehdr, sizeof(oe->ehdr));
 313         write(fd, &oe->phdr, oe->nph * sizeof(oe->phdr[0]));
 314         for (i = 0; i < oe->nsecs; i++) {
 315                 struct secmap *sec = &oe->secs[i];
 316                 char *buf = sec->obj->mem + sec->o_shdr->sh_offset;
 317                 int len = sec->o_shdr->sh_size;
 318                 if (SEC_BSS(sec->o_shdr))
 319                         continue;
 320                 lseek(fd, sec->faddr, SEEK_SET);
 321                 write(fd, buf, len);
 322         }
 323         lseek(fd, oe->got_faddr, SEEK_SET);
 324         write(fd, buf, got_len);
 325 }
 326
 327 static void outelf_add(struct outelf *oe, char *mem)
 328 {
 329         Elf32_Ehdr *ehdr = (void *) mem;
 330         Elf32_Shdr *shdr = (void *) (mem + ehdr->e_shoff);
 331         struct obj *obj;
 332         int i;
 333         if (ehdr->e_type != ET_REL)
 334                 return;
 335         if (oe->nobjs >= MAXOBJS)
 336                 die("ld: MAXOBJS reached!\n");
 337         obj = &oe->objs[oe->nobjs++];
 338         obj_init(obj, mem);
 339         for (i = 0; i < ehdr->e_shnum; i++) {
 340                 struct secmap *sec;
 341                 if (!(shdr[i].sh_flags & 0x7))
 342                         continue;
 343                 if (oe->nsecs >= MAXSECS)
 344                         die("ld: MAXSECS reached\n");
 345                 sec = &oe->secs[oe->nsecs++];
 346                 sec->o_shdr = &shdr[i];
 347                 sec->obj = obj;
 348         }
 349 }
 350
 351 static void outelf_link(struct outelf *oe)
 352 {
 353         int i;
 354         Elf32_Phdr *code_phdr = &oe->phdr[oe->nph++];
 355         Elf32_Phdr *bss_phdr = &oe->phdr[oe->nph++];
 356         Elf32_Phdr *data_phdr = &oe->phdr[oe->nph++];
 357         unsigned long faddr = sizeof(oe->ehdr) + MAXPHDRS * sizeof(oe->phdr[0]);
 358         unsigned long vaddr = SRCADDR + faddr % PAGE_SIZE;
 359         int len = 0;
 360         for (i = 0; i < oe->nsecs; i++) {
 361                 struct secmap *sec = &oe->secs[i];
 362                 int alignment = MAX(sec->o_shdr->sh_addralign, 4);
 363                 if (!SEC_CODE(sec->o_shdr))
 364                         continue;
 365                 len = ALIGN(vaddr + len, alignment) - vaddr;
 366                 sec->vaddr = vaddr + len;
 367                 sec->faddr = faddr + len;
 368                 len += sec->o_shdr->sh_size;
 369         }
 370         code_phdr->p_type = PT_LOAD;
 371         code_phdr->p_flags = PF_R | PF_W | PF_X;
 372         code_phdr->p_vaddr = vaddr;
 373         code_phdr->p_paddr = vaddr;
 374         code_phdr->p_offset = faddr;
 375         code_phdr->p_filesz = len;
 376         code_phdr->p_memsz = len;
 377         code_phdr->p_align = PAGE_SIZE;
 378
 379         faddr += len;
 380         vaddr = BSSADDR + faddr % PAGE_SIZE;
 381         len = 0;
 382         outelf_bss(oe);
 383         oe->bss_vaddr = vaddr + len;
 384         len += oe->bss_len;
 385         for (i = 0; i < oe->nsecs; i++) {
 386                 struct secmap *sec = &oe->secs[i];
 387                 int alignment = MAX(sec->o_shdr->sh_addralign, 4);
 388                 if (!SEC_BSS(sec->o_shdr))
 389                         continue;
 390                 len = ALIGN(vaddr + len, alignment) - vaddr;
 391                 sec->vaddr = vaddr + len;
 392                 sec->faddr = faddr;
 393                 len += sec->o_shdr->sh_size;
 394         }
 395         bss_phdr->p_type = PT_LOAD;
 396         bss_phdr->p_flags = PF_R | PF_W;
 397         bss_phdr->p_vaddr = vaddr;
 398         bss_phdr->p_paddr = vaddr;
 399         bss_phdr->p_offset = faddr;
 400         bss_phdr->p_filesz = 0;
 401         bss_phdr->p_memsz = len;
 402         bss_phdr->p_align = PAGE_SIZE;
 403
 404         faddr = ALIGN(faddr, 4);
 405         vaddr = DATADDR + faddr % PAGE_SIZE;
 406         len = 0;
 407         for (i = 0; i < oe->nsecs; i++) {
 408                 struct secmap *sec = &oe->secs[i];
 409                 if (!SEC_DATA(sec->o_shdr))
 410                         continue;
 411                 sec->vaddr = vaddr + len;
 412                 sec->faddr = faddr + len;
 413                 len += sec->o_shdr->sh_size;
 414         }
 415         len = ALIGN(len, 4);
 416         oe->got_faddr = faddr + len;
 417         oe->got_vaddr = vaddr + len;
 418         outelf_reloc(oe);
 419         len += oe->ngot_syms * 4 + GOT_PAD;
 420
 421         data_phdr->p_type = PT_LOAD;
 422         data_phdr->p_flags = PF_R | PF_W | PF_X;
 423         data_phdr->p_align = PAGE_SIZE;
 424         data_phdr->p_vaddr = vaddr;
 425         data_phdr->p_paddr = vaddr;
 426         data_phdr->p_filesz = len;
 427         data_phdr->p_memsz = len;
 428         data_phdr->p_offset = faddr;
 429 }
 430
 431 struct arhdr {
 432         char ar_name[16];
 433         char ar_date[12];
 434         char ar_uid[6];
 435         char ar_gid[6];
 436         char ar_mode[8];
 437         char ar_size[10];
 438         char ar_fmag[2];
 439 };
 440
 441 static int get_be32(unsigned char *s)
 442 {
 443         return s[3] | (s[2] << 8) | (s[1] << 16) | (s[0] << 32);
 444 }
 445
 446 static int sym_undef(struct outelf *oe, char *name)
 447 {
 448         int i, j;
 449         int undef = 0;
 450         for (i = 0; i < oe->nobjs; i++) {
 451                 struct obj *obj = &oe->objs[i];
 452                 for (j = 0; j < obj->nsyms; j++) {
 453                         Elf32_Sym *sym = &obj->syms[j];
 454                         if (ELF32_ST_BIND(sym->st_info) == STB_LOCAL)
 455                                 continue;
 456                         if (strcmp(name, obj->symstr + sym->st_name))
 457                                 continue;
 458                         if (sym->st_shndx != SHN_UNDEF)
 459                                 return 0;
 460                         undef = 1;
 461                 }
 462         }
 463         return undef;
 464 }
 465
 466 static int outelf_ar_link(struct outelf *oe, char *ar, int base)
 467 {
 468         char *ar_index;
 469         char *ar_name;
 470         int nsyms = get_be32((void *) ar);
 471         int added = 0;
 472         int i;
 473         ar_index = ar + 4;
 474         ar_name = ar_index + nsyms * 4;
 475         for (i = 0; i < nsyms; i++) {
 476                 int off = get_be32((void *) ar_index + i * 4) +
 477                                 sizeof(struct arhdr);
 478                 if (sym_undef(oe, ar_name)) {
 479                         outelf_add(oe, ar - base + off);
 480                         added++;
 481                 }
 482                 ar_name = strchr(ar_name, '\0') + 1;
 483         }
 484         return added;
 485 }
 486
 487 static void link_archive(struct outelf *oe, char *ar)
 488 {
 489         char *beg = ar;
 490
 491         /* skip magic */
 492         ar += 8;
 493         for(;;) {
 494                 struct arhdr *hdr = (void *) ar;
 495                 int size;
 496                 ar += sizeof(*hdr);
 497                 hdr->ar_size[sizeof(hdr->ar_size) - 1] = '\0';
 498                 size = atoi(hdr->ar_size);
 499                 size = (size + 1) & ~1;
 500                 if (!strncmp(hdr->ar_name, "/ ", 2)) {
 501                         while (outelf_ar_link(oe, ar, ar - beg))
 502                                 ;
 503                         return;
 504                 }
 505                 if (!strncmp(hdr->ar_name, "// ", 3))
 506                         outelf_add(oe, ar);
 507                 ar += size;
 508         }
 509 }
 510
 511 static long filesize(int fd)
 512 {
 513         struct stat stat;
 514         fstat(fd, &stat);
 515         return stat.st_size;
 516 }
 517
 518 static char *fileread(char *path)
 519 {
 520         int fd = open(path, O_RDONLY);
 521         int size = filesize(fd);
 522         char *buf = malloc(size);
 523         read(fd, buf, size);
 524         close(fd);
 525         return buf;
 526 }
 527
 528 static int is_ar(char *path)
 529 {
 530         int len = strlen(path);
 531         return len > 2 && path[len - 2] == '.' && path[len - 1] == 'a';
 532 }
 533
 534 int main(int argc, char **argv)
 535 {
 536         char out[1 << 10] = "a.out";
 537         char *buf;
 538         struct outelf oe;
 539         char *mem[MAXFILES];
 540         int nmem = 0;
 541         int fd;
 542         int i = 0;
 543         if (argc < 2)
 544                 die("no object given\n");
 545         outelf_init(&oe);
 546
 547         while (++i < argc) {
 548                 if (!strcmp("-o", argv[i])) {
 549                         strcpy(out, argv[++i]);
 550                         continue;
 551                 }
 552                 if (!strcmp("-g", argv[i]))
 553                         continue;
 554                 buf = fileread(argv[i]);
 555                 mem[nmem++] = buf;
 556                 if (!buf)
 557                         die("cannot open object\n");
 558                 if (is_ar(argv[i]))
 559                         link_archive(&oe, buf);
 560                 else
 561                         outelf_add(&oe, buf);
 562         }
 563         outelf_link(&oe);
 564         fd = open(out, O_WRONLY | O_TRUNC | O_CREAT, 0700);
 565         outelf_write(&oe, fd);
 566         close(fd);
 567         for (i = 0; i < nmem; i++)
 568                 free(mem[i]);
 569         return 0;
 570 }