diff options
| -rw-r--r-- | include/merror.h | 1 | ||||
| -rw-r--r-- | makefile.mk | 5 | ||||
| -rw-r--r-- | masm/asm.c | 9 | ||||
| -rw-r--r-- | masm/lex.c | 2 | ||||
| -rw-r--r-- | masm/parse.c | 24 | ||||
| -rw-r--r-- | masm/reltab.c | 4 | ||||
| -rw-r--r-- | masm/sectab.c | 8 | ||||
| -rw-r--r-- | masm/strtab.c | 2 | ||||
| -rw-r--r-- | masm/symtab.c | 4 | ||||
| -rw-r--r-- | mld/link.c | 652 | ||||
| -rw-r--r-- | mld/link.h | 117 | ||||
| -rw-r--r-- | mld/obj.c | 8 | ||||
| -rw-r--r-- | mld/seg.c | 23 | ||||
| -rw-r--r-- | mld/segtab.c | 147 | ||||
| -rw-r--r-- | mld/strtab.c | 56 | ||||
| -rw-r--r-- | mld/symtab.c | 60 | ||||
| -rw-r--r-- | test/Makefile | 17 | ||||
| -rw-r--r-- | test/mld/test.o | bin | 5442 -> 5442 bytes | |||
| -rw-r--r-- | test/msim/test | bin | 0 -> 5395 bytes |
19 files changed, 1092 insertions, 47 deletions
diff --git a/include/merror.h b/include/merror.h index 7be6fc7..de47ed8 100644 --- a/include/merror.h +++ b/include/merror.h @@ -3,6 +3,7 @@ #define __MERROR_H__ #include <errno.h> +#include <string.h> /* Error codes */ diff --git a/makefile.mk b/makefile.mk index 2d66744..8135205 100644 --- a/makefile.mk +++ b/makefile.mk @@ -13,7 +13,7 @@ H_SRC = $(shell find $(SRC) $(INCLUDE) -type f -name "*.h") C_SRC = $(shell find $(SRC) -type f -name "*.c") C_OBJ = $(patsubst %.c,$(BIN)/%.o,$(C_SRC)) -.PHONY: clean build run +.PHONY: clean build run test build: $(BIN)/$(OUT) @@ -27,7 +27,8 @@ run: build test: make -C ../test $(OUT) mkdir -p ../fuzz - afl-fuzz -i ../test/$(OUT) -o ../fuzz -- $(BIN)/$(OUT) @@ + rm -fr ../fuzz/$(OUT) + afl-fuzz -i ../test/$(OUT) -o ../fuzz -M $(OUT) -- $(BIN)/$(OUT) @@ $(C_OBJ): $(BIN)/%.o : %.c @mkdir -p $(@D) @@ -315,7 +315,7 @@ static int assemble_phdr(struct assembler *assembler, Elf32_Phdr **res, Elf32_Phdr *phdr = malloc(sizeof(Elf32_Phdr) * assembler->sectab.len); if (phdr == NULL) { - ERROR("cannot alloc"); + PERROR("cannot alloc"); return M_ERROR;; } @@ -354,6 +354,11 @@ static int assemble_shdr(struct assembler *assembler, Elf32_Shdr **res, Elf32_Shdr *shdr = malloc(sizeof(Elf32_Shdr) * max_entries); + if (shdr == NULL) { + PERROR("cannot alloc"); + return M_ERROR; + } + size_t str_off; uint32_t count = 0; @@ -593,7 +598,7 @@ static int write_file(struct assembler *assembler, Elf32_Ehdr *ehdr, if (out == NULL) { - ERROR("cannot write '%s'", path); + PERROR("cannot write '%s'", path); return M_ERROR; } @@ -309,7 +309,7 @@ int lexer_init(const char *path, struct lexer *lexer) { FILE *file = fopen(path, "r"); if (file == NULL) { - ERROR("cannot read '%s'", path); + PERROR("cannot read '%s'", path); return M_ERROR; } lexer->file = file; diff --git a/masm/parse.c b/masm/parse.c index 6c817d4..2e404ad 100644 --- a/masm/parse.c +++ b/masm/parse.c @@ -1,6 +1,5 @@ #include <mlimits.h> #include <merror.h> -#include <netinet/in.h> #include <stdint.h> #include <stdio.h> #include <string.h> @@ -10,6 +9,9 @@ #include "lex.h" #include "mips.h" +#define B16(x) (x) +#define B32(x) (x) + static int next_token(struct parser *parser, struct token *tok) { if (parser->peek.type != TOK_EOF) { @@ -475,7 +477,7 @@ off: if (assert_token(parser, TOK_NUMBER, &token)) return M_ERROR; - fi->data.offset = htons(token.number); + fi->data.immd = B16(token.number); if (peek_token(parser, &token)) return M_ERROR; @@ -618,7 +620,7 @@ static int parse_instruction_i(struct parser *parser, if (token.number >= MAX16) return M_ERROR; - ins->data.immd = htons(token.number); + ins->data.immd = B16(token.number); return M_SUCCESS; } @@ -634,12 +636,12 @@ static int parse_instruction_offset(struct parser *parser, case MAX26: if (get_offset_26(parser, &n, ref)) return M_ERROR; - ins->data.offs26 = htonl(n); + ins->data.offs26 = B32(n); break; case MAX16: if (get_offset(parser, &n, ref)) return M_ERROR; - ins->data.offset = htons(n); + ins->data.offset = B16(n); break; default: return M_ERROR; @@ -682,7 +684,7 @@ static int parse_instruction_branch_equal(struct parser *parser, int32_t off; if (get_offset(parser, &off, ref)) return M_ERROR; - ins->data.offset = htons(off); + ins->data.offset = B16(off); return M_SUCCESS; } @@ -703,7 +705,7 @@ static int parse_instruction_branch(struct parser *parser, if (get_offset(parser, &n, ref)) return M_ERROR; - ins->data.offset = htons(n); + ins->data.offset = B16(n); return M_SUCCESS; } @@ -742,7 +744,7 @@ static int parse_instruction_sli(struct parser *parser, if (assert_token(parser, TOK_NUMBER, &token) || token.number > MAX16) return M_ERROR; - ins->data.immd = htons(token.number); + ins->data.immd = B16(token.number); return M_SUCCESS; } @@ -818,7 +820,7 @@ static int parse_pseudo_li(struct parser *parser, struct ins_expr *expr) expr->ins[0] = mips_instructions[MIPS_INS_ORI]; expr->ins[0].data.rt = reg; expr->ins[0].data.rs = MIPS_REG_ZERO; - expr->ins[0].data.immd = htons(immd); + expr->ins[0].data.immd = B16(immd); expr->ref[0].type = R_MIPS_NONE; return M_SUCCESS; @@ -859,11 +861,11 @@ static int parse_pseudo_la(struct parser *parser, struct ins_expr *expr) expr->ins_len = 2; expr->ins[0] = mips_instructions[MIPS_INS_LUI]; expr->ins[0].data.rt = reg; - expr->ins[0].data.immd = htons(hi); + expr->ins[0].data.immd = B16(hi); expr->ins[1] = mips_instructions[MIPS_INS_ORI]; expr->ins[1].data.rt = reg; expr->ins[1].data.rs = MIPS_REG_ZERO; - expr->ins[1].data.immd = htons(lo); + expr->ins[1].data.immd = B16(lo); return M_SUCCESS; } diff --git a/masm/reltab.c b/masm/reltab.c index 482ed44..afbd5e7 100644 --- a/masm/reltab.c +++ b/masm/reltab.c @@ -13,7 +13,7 @@ int reltab_init(struct relocation_table *reltab) reltab->data = malloc(sizeof(Elf32_Rela) * RELTAB_INIT_LEN); if (reltab->data == NULL) { - ERROR("cannot alloc"); + PERROR("cannot alloc"); return M_ERROR; } @@ -33,7 +33,7 @@ int reltab_push(struct relocation_table *reltab, const Elf32_Rela rel) * reltab->size); if (reltab->data == NULL) { - ERROR("cannot realloc"); + PERROR("cannot realloc"); return M_ERROR; } } diff --git a/masm/sectab.c b/masm/sectab.c index d07399f..caf34dd 100644 --- a/masm/sectab.c +++ b/masm/sectab.c @@ -16,7 +16,7 @@ int sectab_init(struct section_table *sectab) sectab->sections = malloc(sizeof(struct section) * SECTBL_INIT_LEN); if (sectab->sections == NULL) { - ERROR("cannot alloc"); + PERROR("cannot alloc"); return M_ERROR; } @@ -59,7 +59,7 @@ int sectab_alloc(struct section_table *sectab, struct section **res, sizeof(struct section) * sectab->size); if (sectab->sections == NULL) { - ERROR("cannot realloc"); + PERROR("cannot realloc"); return M_ERROR; } } @@ -94,7 +94,7 @@ int sectab_alloc(struct section_table *sectab, struct section **res, } if (sec->entries == NULL) { - ERROR("cannot alloc"); + PERROR("cannot alloc"); return M_ERROR; } @@ -127,7 +127,7 @@ int sec_push(struct section *section, struct section_entry entry) sizeof(struct section_entry) * section->size); if (new == NULL) { - ERROR("cannot realloc"); + PERROR("cannot realloc"); return M_ERROR; } diff --git a/masm/strtab.c b/masm/strtab.c index 57d3d0e..404ea73 100644 --- a/masm/strtab.c +++ b/masm/strtab.c @@ -41,7 +41,7 @@ int strtab_init(struct str_table *strtab) strtab->size = 1; strtab->ptr = malloc(1); if (strtab->ptr == NULL) { - ERROR("cannot alloc"); + PERROR("cannot alloc"); return M_ERROR; } *strtab->ptr = '\0'; diff --git a/masm/symtab.c b/masm/symtab.c index c6f9aac..652bd42 100644 --- a/masm/symtab.c +++ b/masm/symtab.c @@ -18,7 +18,7 @@ int symtab_init(struct symbol_table *symtab) symtab->sections = malloc(sizeof(ssize_t) * SYMTBL_INIT_LEN); if (symtab->symbols == NULL || symtab->sections == NULL) { - ERROR("cannot alloc"); + PERROR("cannot alloc"); return M_ERROR; } @@ -44,7 +44,7 @@ int symtab_push(struct symbol_table *symtab, Elf32_Sym sym, ssize_t sec_idx) symtab->sections = realloc(symtab->sections, sizeof(ssize_t) * symtab->size); if (symtab->symbols == NULL || symtab->sections == NULL) { - ERROR("cannot realloc"); + PERROR("cannot realloc"); return M_ERROR; } } @@ -1,9 +1,17 @@ +#include <elf.h> +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> #include <stdlib.h> #include <merror.h> #include <string.h> #include <sys/stat.h> +#include <melf.h> #include "link.h" +#include "mips.h" + +#define SEC_ALIGN 0x1000 static int load_objects(struct linker *linker) { @@ -12,7 +20,7 @@ static int load_objects(struct linker *linker) linker->obj_len = 0; if (linker->objects == NULL) { - ERROR("cannot alloc"); + PERROR("cannot alloc"); return M_ERROR; } @@ -40,6 +48,627 @@ skip_obj: return M_SUCCESS; } +/** + * Relocates all segments with the given name + * (since they need to be next to eachother) + */ +static int relocate_segment_name(struct linker *linker, const char *name) +{ + for (size_t i = 0; i < linker->obj_len; i++) { + struct object *obj = &linker->objects[i]; + for (size_t j = 0; j < obj->segment_len; j++) { + struct segment *seg = &obj->segments[j]; + + // check if the segment has already been relocated + if (seg->new_vaddr != 0) + continue; + + // make sure the segments name matches what + // we are looking for + if (strcmp(seg->name, name) != 0) + continue; + + if (ADDR_CHK(linker->off, seg->size, UINT32_MAX)) { + ERROR("linker offset overflow"); + return M_ERROR; + } + + // is the segment a TEXT type or DATA type?? + if (B32(seg->phdr->p_flags) & PF_X) { + // TEXT + if (ADDR_CHK(linker->text_vaddr, seg->size, + DATA_VADDR_MIN)) { + ERROR("linker text vaddr overflow"); + return M_ERROR; + } + + seg->new_off = linker->off; + seg->new_vaddr = linker->text_vaddr; + linker->off += seg->size; + linker->text_vaddr += seg->size; + } else { + // DATA + if (ADDR_CHK(linker->data_vaddr, seg->size, + UINT32_MAX)) { + ERROR("linker data vaddr overflow"); + return M_ERROR; + } + + seg->new_off = linker->off; + seg->new_vaddr = linker->data_vaddr; + linker->off += seg->size; + linker->data_vaddr += seg->size; + } + + // if this is an existing segment, append this + // part + struct segment_table_entry *ent; + if (segtab_get(&linker->segments, &ent, name) == + M_SUCCESS) { + if (segtab_ent_push(ent, seg)) + return M_ERROR; + } else { + // else create a new segment + if (segtab_push(&linker->segments, NULL, seg)) + return M_ERROR; + } + } + } + + return M_SUCCESS; +} + +static int relocate_segments(struct linker *linker) +{ + for (size_t i = 0; i < linker->obj_len; i++) { + struct object *obj = &linker->objects[i]; + for (size_t j = 0; j < obj->segment_len; j++) { + struct segment *seg = &obj->segments[j]; + + // check if the segment has already been relocated + if (seg->new_vaddr != 0) + continue; + if(relocate_segment_name(linker, seg->name)) + return M_ERROR; + } + } + + return M_SUCCESS; +} + +static int relocate_symbol(struct linker *linker, struct object *obj, + struct symbol_table *symtab, const Elf32_Sym *sym) +{ + size_t shndx = B16(sym->st_shndx); + if (shndx == 0) + return M_SUCCESS; // ignore this symbol + + // find the given section + const char *name = symtab->strtab->data + B32(sym->st_name); + + if (shndx >= obj->shdr_len) { + ERROR("shdr entry [%d] name out of bounds", shndx); + return M_ERROR; + } + + if (B32(sym->st_name) >= symtab->strtab->len) { + ERROR("symbol name out of bounds"); + return M_ERROR; + } + + Elf32_Shdr const *shdr = &obj->shdr[shndx]; + struct segment *sec = NULL; + for (size_t i = 0; i < obj->phdr_len; i++) { + Elf32_Phdr *temp = &obj->phdr[i]; + if (shdr->sh_offset == temp->p_offset) { + sec = &obj->segments[i]; + break; + } + } + + if (sec == NULL) { + ERROR("could not locate segment for symbol '%s'", name); + return M_ERROR; + } + + struct segment_table_entry *ent = NULL; + if (segtab_get(&linker->segments, &ent, sec->name)) { + ERROR("could not locate segment for symbol '%s'", name); + return M_ERROR; + } + + // segments start at shindx 1 + ptrdiff_t new_shndx = (ent - linker->segments.entries) + 1; + + size_t str_off = 0; + if (strtab_push(linker->symtab.strtab, name, &str_off)) + return M_ERROR; + + int32_t off = sec->new_vaddr + B32(sym->st_value); + Elf32_Sym new = *sym; + new.st_name = B32(str_off); + new.st_value = B32(off); + new.st_shndx = B16(new_shndx); + new.st_size = 0; + + if (symtab_get(&linker->symtab, NULL, name) == M_SUCCESS) { + ERROR("cannot link doubly defiend symbol '%s'", name); + return M_ERROR; + } + + if (symtab_push(&linker->symtab, &new)) + return M_ERROR; + + return M_SUCCESS; +} + +static int relocate_symbols(struct linker *linker) +{ + for (size_t i = 0; i < linker->obj_len; i++) { + struct object *obj = &linker->objects[i]; + for (size_t j = 0; j < obj->shdr_len; j++) { + struct symbol_table *symtab = &obj->symtabs[j]; + if (symtab->len < 1) + continue; + + for (size_t k = 0; k < symtab->len; k++) { + const Elf32_Sym *sym = &symtab->syms[k]; + if (relocate_symbol(linker, obj, symtab, sym)) + return M_ERROR; + } + } + } + return M_SUCCESS; +} + +static int assemble_phdr(struct linker *linker) +{ + Elf32_Phdr *phdr = malloc(sizeof(Elf32_Phdr) * linker->segments.len); + + if (phdr == NULL) { + PERROR("cannot alloc"); + return M_ERROR; + } + + for (uint32_t i = 0; i < linker->segments.len; i++) { + Elf32_Phdr *hdr = &phdr[i]; + struct segment_table_entry *ent = &linker->segments.entries[i]; + size_t size = segtab_ent_size(ent); + hdr->p_type = B32(PT_LOAD); + hdr->p_flags = B32( + (ent->parts[0]->execute << 0) | + (ent->parts[0]->write << 1) | + (ent->parts[0]->read << 2)); + hdr->p_offset = B32(ent->off); + hdr->p_vaddr = B32(ent->vaddr); + hdr->p_paddr = B32(ent->vaddr); + hdr->p_filesz = B32(size); + hdr->p_memsz = B32(size); + hdr->p_align = B32(SEC_ALIGN); + } + + linker->phdr = phdr; + linker->phdr_len = linker->segments.len; + return M_SUCCESS; +} + +static int assemble_shdr(struct linker *linker) +{ + uint32_t max_entries = 0; + max_entries += 1; // null + max_entries += 1; // symtab + max_entries += 1; // strtab + max_entries += 1; // shstrtab + max_entries += linker->segments.len; // segments + + Elf32_Shdr *shdr = malloc(sizeof(Elf32_Shdr) * max_entries); + if (shdr == NULL) { + PERROR("cannot alloc"); + return M_ERROR; + } + linker->shdr = shdr; + + size_t str_off; + uint32_t count = 0; + + // null + shdr[count++] = (Elf32_Shdr) {0}; + + // segments + for (uint32_t i = 0; i < linker->segments.len; i++) { + struct segment_table_entry *ent = &linker->segments.entries[i]; + if (strtab_push(&linker->shstrtab, ent->name, &str_off)) + return M_ERROR; + + shdr[count++] = (Elf32_Shdr) { + .sh_name = B32(str_off), + .sh_type = B32(SHT_PROGBITS), + .sh_flags = B32( + (ent->parts[0]->write << 0) | + (ent->parts[0]->execute << 2) | + SHF_ALLOC), + .sh_addr = B32(ent->vaddr), + .sh_offset = B32(ent->off), + .sh_size = B32(segtab_ent_size(ent)), + .sh_link = 0, + .sh_info = 0, + .sh_addralign = B32(ent->parts[0]->align), + .sh_entsize = 0, + }; + } + + // symbol table + if (strtab_push(&linker->shstrtab, ".symtab", &str_off)) + return M_ERROR; + + linker->symtab_shidx = count; + shdr[count++] = (Elf32_Shdr) { + .sh_name = B32(str_off), + .sh_type = B32(SHT_SYMTAB), + .sh_flags = 0, + .sh_addr = 0, + .sh_offset = 0, + .sh_size = 0, + .sh_link = 0, + .sh_info = 0, + .sh_addralign = B32(1), + .sh_entsize = B32(sizeof(Elf32_Sym)), + }; + + // string table + if (strtab_push(&linker->shstrtab, ".strtab", &str_off)) + return M_ERROR; + + linker->strtab_shidx = count; + shdr[count++] = (Elf32_Shdr) { + .sh_name = B32(str_off), + .sh_type = B32(SHT_STRTAB), + .sh_flags = B32(SHF_STRINGS), + .sh_addr = 0, + .sh_offset = 0, + .sh_size = 0, + .sh_link = 0, + .sh_info = 0, + .sh_addralign = B32(1), + .sh_entsize = 0, + }; + + // shstring table + if (strtab_push(&linker->shstrtab, ".shstrtab", &str_off)) + return M_ERROR; + + linker->shstrtab_shidx = count; + shdr[count++] = (Elf32_Shdr) { + .sh_name = B32(str_off), + .sh_type = B32(SHT_STRTAB), + .sh_flags = B32(SHF_STRINGS), + .sh_addr = 0, + .sh_offset = 0, + .sh_size = 0, + .sh_link = 0, + .sh_info = 0, + .sh_addralign = B32(1), + .sh_entsize = 0, + }; + + linker->shdr_len = count; + return M_SUCCESS; +} + +static int relocate_instruction_rela(struct linker *linker, + struct segment *seg, + Elf32_Rela *rel) +{ + /// get start of the segment part in bytes and the byte offset + /// of this relocation in that segment part + uint32_t off = B32(rel->r_offset); + if (off > seg->size) { + ERROR("relocation in segment '%s' out of bounds", seg->name); + return M_ERROR; + } + + if (B32(rel->r_info) == 0) { + WARNING("skiping empty relocation entry"); + return M_SUCCESS; + } + + /// read the relocation entry + uint8_t idx = B32(rel->r_info) >> 8; + uint8_t typ = B32(rel->r_info) & 0xFF; + int32_t add = B32(rel->r_addend); + + /// read the symbol from the relocation + struct symbol_table *symtab = seg->reltab.symtab; + if (idx >= symtab->len) { + ERROR("relocation in segment '%s', symbol index [%d] out of " + "bounds", seg->name, idx); + return M_ERROR; + } + Elf32_Sym *sym = &symtab->syms[idx]; + const char *symname = symtab->strtab->data + B32(sym->st_name); + + + /// get the section header that the symbol is related to + Elf32_Shdr *shdr = NULL; + if (B16(sym->st_shndx) >= seg->obj->shdr_len) { + ERROR("shndx index [%d] out of bounds", B16(sym->st_shndx)); + return M_ERROR; + } + shdr = &seg->obj->shdr[B16(sym->st_shndx)]; + + /// get the segment that the symbol is in + struct segment_table_entry *ent; + const char *segname = seg->obj->shstrtab->data + B32(shdr->sh_name); + if (segtab_get(&linker->segments, &ent, segname)) { + ERROR("could not locate segment for relocation"); + return M_ERROR; + } + + uint32_t sym_vaddr = B32(sym->st_value) + ent->vaddr; + uint32_t *ins_raw = (uint32_t *) &seg->bytes[off]; + + union mips_instruction_data ins; + ins.raw = B32(*ins_raw); + + uint32_t ins_vaddr = seg->new_vaddr + off; + + uint32_t vaddr_abs = sym_vaddr + add; + int32_t vaddr_rel = (vaddr_abs - ins_vaddr - 4) >> 2; + bool warn = false; + + switch (typ) { + case R_MIPS_16: + // 16bit absolute + if (vaddr_abs > UINT16_MAX) + warn = true; + ins.immd = (uint16_t)vaddr_abs; + break; + case R_MIPS_PC16: + // 16bit relative shifted + if (vaddr_rel > INT16_MAX || vaddr_rel < INT16_MIN) + warn = true; + ins.offset = vaddr_rel; + break; + case R_MIPS_26: + // 26bit absolute shifted + if (vaddr_abs >= (1 << 25)) + warn = true; + ins.target = (vaddr_abs & 0x0FFFFFFF) >> 2; + break; + case R_MIPS_PC26_S2: + // 26bit relative shifted + if (vaddr_rel >= (1 << 24) || -vaddr_rel > (1 << 24)) + warn = true; + ins.offs26 = vaddr_rel; + break; + case R_MIPS_LO16: + // lo 16bit absolute + ins.immd = (uint16_t)(vaddr_abs & 0xFFFF); + break; + case R_MIPS_HI16: + // hi 16bit absolute + ins.immd = (uint16_t)(vaddr_abs >> 16); + break; + default: + ERROR("do not know how do handle relocation type [%d]", typ); + return M_ERROR; + } + + *ins_raw = B32(ins.raw); + + if (warn) + WARNING("truncating relocation for symbol '%s'", symname); + + return M_SUCCESS; + +} + +static int relocate_instruction_rel(struct linker *linker, + struct segment *seg, + Elf32_Rel *rel) +{ + Elf32_Rela temp; + temp.r_info = rel->r_info; + temp.r_offset = rel->r_offset; + temp.r_addend = 0; + + return relocate_instruction_rela(linker, seg, &temp); +} + +static int relocate_segment_instructions(struct linker *linker, + struct segment *seg) +{ + for (uint32_t i = 0; i < seg->reltab.len; i++) { + int res = M_SUCCESS; + if (seg->reltab.type == SHT_RELA) + res = relocate_instruction_rela(linker, seg, + &seg->reltab.rela[i]); + else if (seg->reltab.type == SHT_REL) + res = relocate_instruction_rel(linker, seg, + &seg->reltab.rel[i]); + else { + ERROR("unknown reltab type"); + return M_ERROR; + } + if (res) + return M_ERROR; + } + return M_SUCCESS; +} + +static int relocate_instructions(struct linker *linker) +{ + for (uint32_t i = 0; i < linker->segments.len; i++) { + struct segment_table_entry *ent = &linker->segments.entries[i]; + for (uint32_t j = 0; j < ent->len; j++) { + struct segment *seg = ent->parts[j]; + if (relocate_segment_instructions(linker, seg)) + return M_ERROR; + } + } + return M_SUCCESS; +} + +static void update_offsets(struct linker *linker) +{ + uint32_t ptr = 0; + + // we must now correct offsets and sizes in side the ehdr, phdr, + // and shdr + ptr += sizeof(Elf32_Ehdr); + + // phdr + linker->ehdr.e_phoff = B32(ptr); + ptr += linker->phdr_len * sizeof(Elf32_Phdr); + + // section padding + { + uint32_t mod = ptr % SEC_ALIGN; + if (mod != 0) + linker->secalign = (SEC_ALIGN - mod); + else + linker->secalign = 0; + ptr += linker->secalign; + } + + // sections + for (uint32_t i = 0; i < linker->segments.len; i++) { + struct segment_table_entry *ent = &linker->segments.entries[i]; + uint32_t idx = i + 1; + uint32_t size = segtab_ent_size(ent); + linker->phdr[i].p_offset = B32(ptr); + linker->shdr[idx].sh_offset = linker->phdr[i].p_offset; + ptr += size; + } + + // symtab + Elf32_Shdr *symtab = &linker->shdr[linker->symtab_shidx]; + symtab->sh_offset = B32(ptr); + symtab->sh_link = B32(linker->strtab_shidx); + symtab->sh_size = B32(linker->symtab.len * sizeof(Elf32_Sym)); + ptr += B32(symtab->sh_size); + + // strtab + Elf32_Shdr *strtab = &linker->shdr[linker->strtab_shidx]; + strtab->sh_offset = B32(ptr); + strtab->sh_size = B32(linker->strtab.len); + ptr += linker->strtab.len; + + // shstrtab + Elf32_Shdr *shstrtab = &linker->shdr[linker->shstrtab_shidx]; + shstrtab->sh_offset = B32(ptr); + shstrtab->sh_size = B32(linker->shstrtab.len); + ptr += linker->shstrtab.len; + + // shdr + linker->ehdr.e_shoff = B32(ptr); +} + +static int write_file(struct linker *linker) +{ + extern char *current_file; + current_file = linker->args->out_file; + + FILE *out = fopen(linker->args->out_file, "w"); + if (out == NULL) { + PERROR("cannot write"); + return M_ERROR; + } + + int res = 0; + + // ehdr + res |= fwrite(&linker->ehdr, sizeof(Elf32_Ehdr), 1, out); + + // phdr + res |= fwrite(linker->phdr, sizeof(Elf32_Phdr), linker->phdr_len, out); + + // section padding + for (uint32_t i = 0; i < linker->secalign; i++) { + uint8_t zero = 0; + res |= fwrite(&zero, 1, 1, out); + } + + // sections + for (uint32_t i = 0; i < linker->segments.len; i++) { + struct segment_table_entry *ent = &linker->segments.entries[i]; + for (uint32_t j = 0; j < ent->len; j++) { + struct segment *seg = ent->parts[j]; + res |= fwrite(seg->bytes, 1, seg->size, out); + } + } + + // sym tbl + res |= fwrite(linker->symtab.syms, sizeof(Elf32_Sym), linker->symtab.len, out); + + // str tbl + res |= fwrite(linker->strtab.data, 1, linker->strtab.len, out); + + // shstr tbl + res |= fwrite(linker->shstrtab.data, 1, linker->shstrtab.len, out); + + // shdr + res |= fwrite(linker->shdr, sizeof(Elf32_Shdr), linker->shdr_len, out); + + if (res < 0) { + ERROR("cannot write data"); + return M_ERROR; + } + + fclose(out); + + return M_SUCCESS; +} + +static int link_executable(struct linker *linker) +{ + Elf32_Ehdr *ehdr = &linker->ehdr; + *ehdr = MIPS_ELF_EHDR; + + if (assemble_phdr(linker)) + return M_ERROR; + + if (assemble_shdr(linker)) + return M_ERROR; + + ehdr->e_type = B16(ET_EXEC); + ehdr->e_phnum = B16(linker->phdr_len); + ehdr->e_shnum = B16(linker->shdr_len); + ehdr->e_shstrndx = B16(linker->shstrtab_shidx); + + update_offsets(linker); + + if (write_file(linker)) + return M_ERROR; + + return M_SUCCESS; +} + +static int linker_init(struct linker *linker, struct linker_arguments *args) +{ + linker->args = args; + linker->off = 0; + linker->text_vaddr = TEXT_VADDR_MIN; + linker->data_vaddr = DATA_VADDR_MIN; + linker->objects = NULL; + linker->segments.size = 0; + linker->symtab.syms = NULL; + linker->shstrtab.data = NULL; + linker->strtab.data = NULL; + linker->shdr = NULL; + linker->phdr = NULL; + if (segtab_init(&linker->segments)) + return M_ERROR; + if (strtab_init(&linker->shstrtab)) + return M_ERROR; + if (strtab_init(&linker->strtab)) + return M_ERROR; + if (symtab_init(&linker->symtab)) + return M_ERROR; + linker->symtab.strtab = &linker->strtab; + return M_SUCCESS; +} + static void linker_free(struct linker *linker) { if (linker->objects != NULL) { @@ -47,15 +676,32 @@ static void linker_free(struct linker *linker) object_free(&linker->objects[i]); free(linker->objects); } + if (linker->shdr != NULL) + free(linker->shdr); + if (linker->phdr != NULL) + free(linker->phdr); + segtab_free(&linker->segments); + strtab_free(&linker->shstrtab); + strtab_free(&linker->strtab); + symtab_free(&linker->symtab); } int link_files(struct linker_arguments args) { struct linker linker; - linker.args = &args; - int res = M_SUCCESS; + int res = M_SUCCESS; + if (res == M_SUCCESS) + res = linker_init(&linker, &args); if (res == M_SUCCESS) res = load_objects(&linker); + if (res == M_SUCCESS) + res = relocate_segments(&linker); + if (res == M_SUCCESS) + res = relocate_symbols(&linker); + if (res == M_SUCCESS) + res = relocate_instructions(&linker); + if (res == M_SUCCESS) + res = link_executable(&linker); linker_free(&linker); return res; @@ -9,7 +9,6 @@ #include <merror.h> #include <stdint.h> #include <elf.h> -#include <stdio.h> // when mapping porinters, we need to bounds check to @@ -21,6 +20,15 @@ #define BOUND_CHK(obj, len, off) \ (off > UINT32_MAX - len || off + len > obj->mapped_size) +// when relocating segments, we need to bounds check to +// make sure it wont overflow the addresses past the 32bit +// ELF file +#define ADDR_CHK(lnk_f, seg_f, max) \ + ((lnk_f) > max - (seg_f) || (lnk_f) + (seg_f) > max) + +// start addresses for each tyoe of segment +#define TEXT_VADDR_MIN 0x00400000 +#define DATA_VADDR_MIN 0x10000000 // pre define struct linker; @@ -51,6 +59,12 @@ struct string_table { size_t len; }; +int strtab_init(struct string_table *strtab); +void strtab_free(struct string_table *strtab); + +int strtab_push(struct string_table *strtab, const char *str, size_t *res); +int strtab_get(struct string_table *strtab, const char *str, size_t *res); + /// /// symbol table /// @@ -59,14 +73,42 @@ struct symbol_table { struct string_table *strtab; Elf32_Sym *syms; size_t len; + size_t size; }; +int symtab_init(struct symbol_table *symtab); +void symtab_free(struct symbol_table *symtab); + +int symtab_push(struct symbol_table *symtab, const Elf32_Sym *sym); +int symtab_get(struct symbol_table *symtab, Elf32_Sym **sym, const char *name); + /// /// segment /// /* a loadable program segment */ struct segment { + // segment data + char *name; + unsigned char *bytes; + + // current loc + uint32_t off; + uint32_t vaddr; + + // new loc + uint32_t new_off; + uint32_t new_vaddr; + + // meta + bool read; + bool write; + bool execute; + uint32_t align; + + // size + uint32_t size; + // phdr Elf32_Phdr *phdr; uint32_t phdr_idx; @@ -75,9 +117,8 @@ struct segment { Elf32_Shdr *shdr; uint32_t shdr_idx; - // segment data - char *name; - unsigned char *bytes; + // object im related to + struct object *obj; // relocation table struct relocation_table reltab; @@ -86,6 +127,46 @@ struct segment { int segment_load(struct object *object, struct segment *segment, size_t index); /// +/// segment table +/// + +struct segment_table_entry { + char *name; + uint32_t len; + uint32_t size; + uint32_t off; + uint32_t vaddr; + // weak segment pointers. we do not own these!!! + struct segment **parts; +}; + +int segtab_ent_init(struct segment_table_entry *ent); +void segtab_ent_free(struct segment_table_entry *ent); + +int segtab_ent_push(struct segment_table_entry *ent, struct segment *seg); +uint32_t segtab_ent_size(struct segment_table_entry *ent); + +// holds each segment by name +// and all the segment parts from each of the +// object files +struct segment_table { + uint32_t len; + uint32_t size; + struct segment_table_entry *entries; +}; + +int segtab_init(struct segment_table *segtab); +void segtab_free(struct segment_table *segtab); + +/* create a new entry with <seg> as its first segment part */ +int segtab_push(struct segment_table *segtab, struct segment_table_entry **ent, + struct segment *seg); + +/* find a segment table entry with a given name */ +int segtab_get(struct segment_table *segtab, struct segment_table_entry **ent, + const char *name); + +/// /// object file /// @@ -136,6 +217,34 @@ struct linker { struct object *objects; struct linker_arguments *args; + + // current pointers to relocate + // sections + uint32_t off; + uint32_t text_vaddr; + uint32_t data_vaddr; + + // elf tables + struct string_table shstrtab; + struct string_table strtab; + struct symbol_table symtab; + + // output elf + Elf32_Ehdr ehdr; + Elf32_Phdr *phdr; + uint32_t phdr_len; + Elf32_Shdr *shdr; + uint32_t shdr_len; + + uint32_t symtab_shidx; + uint32_t strtab_shidx; + uint32_t shstrtab_shidx; + + // section alignment after phdr bytes + uint32_t secalign; + + // all segments + struct segment_table segments; }; /* defines arguments to the linker */ @@ -171,6 +171,7 @@ static int load_symtabs(struct object *object) if (B32(hdr->sh_type) != SHT_SYMTAB) { symtab->len = 0; + symtab->size = 0; continue; } @@ -190,7 +191,8 @@ static int load_symtabs(struct object *object) } symtab->strtab = strtab; - symtab->len = len; + symtab->len = len / sizeof(Elf32_Sym); + symtab->size = len / sizeof(Elf32_Sym); symtab->syms = (Elf32_Sym *) (object->mapped + off); if (BOUND_CHK(object, len, off)) { @@ -263,8 +265,8 @@ static int map_file(struct object *obj, char *path) } obj->mapped_size = st.st_size; - obj->mapped = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, - obj->fd, 0); + obj->mapped = mmap(NULL, st.st_size, PROT_READ | PROT_WRITE, + MAP_PRIVATE, obj->fd, 0); if (obj->mapped == MAP_FAILED) { PERROR("cannot map"); @@ -82,6 +82,13 @@ static int load_reltab(struct object *obj, struct segment *seg) if (type != SHT_REL && type != SHT_RELA) continue; + if ((type == SHT_REL && B32(hdr->sh_entsize) != + sizeof(Elf32_Rel)) || (type == SHT_RELA && + B32(hdr->sh_entsize) != sizeof(Elf32_Rela))) { + ERROR("reltab [%d] has invalid entry size", i); + return M_ERROR; + } + if (B32(hdr->sh_info) != seg->shdr_idx) continue; @@ -101,9 +108,8 @@ static int load_reltab(struct object *obj, struct segment *seg) uint32_t len = B32(hdr->sh_size); uint32_t off = B32(hdr->sh_offset); - seg->reltab.symtab = symtab; - seg->reltab.len = len; + seg->reltab.len = len / B32(hdr->sh_entsize); seg->reltab.raw = obj->mapped + off; seg->reltab.type = type; @@ -131,5 +137,18 @@ int segment_load(struct object *obj, struct segment *seg, size_t index) if (load_reltab(obj, seg)) return M_ERROR; + seg->off = B32(seg->phdr->p_offset); + seg->vaddr = B32(seg->phdr->p_vaddr); + seg->size = B32(seg->phdr->p_filesz); + seg->new_off = 0; + seg->new_vaddr = 0; + + seg->read = B32(seg->phdr->p_flags) & PF_R; + seg->write = B32(seg->phdr->p_flags) & PF_W; + seg->execute = B32(seg->phdr->p_flags) & PF_X; + seg->align = B32(seg->phdr->p_align); + + seg->obj = obj; + return M_SUCCESS; } diff --git a/mld/segtab.c b/mld/segtab.c new file mode 100644 index 0000000..22356d5 --- /dev/null +++ b/mld/segtab.c @@ -0,0 +1,147 @@ +#include <stdlib.h> +#include <merror.h> + +#include "link.h" + +#define SEGTAB_INIT_SIZE 8 + +int segtab_init(struct segment_table *segtab) +{ + segtab->len = 0; + segtab->size = SEGTAB_INIT_SIZE; + segtab->entries = malloc(sizeof(struct segment_table_entry) * + SEGTAB_INIT_SIZE); + + if (segtab->entries == NULL) { + PERROR("cannot alloc"); + return M_ERROR; + } + + return M_SUCCESS; +} + +void segtab_free(struct segment_table *segtab) +{ + for (uint32_t i = 0; i < segtab->len; i++) { + segtab_ent_free(&segtab->entries[i]); + } + free(segtab->entries); +} + +/* create a new entry with <seg> as its first segment part */ +int segtab_push(struct segment_table *segtab, struct segment_table_entry **res, + struct segment *seg) +{ + if (segtab->len >= segtab->size) { + uint32_t size = segtab->size * 2; + void *new = realloc(segtab->entries, + sizeof(struct segment_table_entry) * size); + if (new == NULL) { + PERROR("cannot relloc"); + return M_ERROR; + } + segtab->size = size; + segtab->entries = new; + } + + struct segment_table_entry ent; + if (segtab_ent_init(&ent)) + return M_ERROR; + ent.name = seg->name; + ent.vaddr = seg->vaddr; + ent.off = seg->off; + + if (segtab_ent_push(&ent, seg)) { + segtab_ent_free(&ent); + return M_ERROR; + } + + segtab->entries[segtab->len] = ent; + + if (res != NULL) + *res = &segtab->entries[segtab->len]; + + segtab->len++; + + return M_SUCCESS; +} + +/* find a segment table entry with a given name */ +int segtab_get(struct segment_table *segtab, struct segment_table_entry **ent, + const char *name) +{ + for (uint32_t i = 0; i < segtab->len; i++) { + const char *segname = segtab->entries[i].name; + if (strcmp(name, segname) != 0) + continue; + + *ent = &segtab->entries[i]; + return M_SUCCESS; + } + + return M_ERROR; +} + +int segtab_ent_init(struct segment_table_entry *ent) +{ + ent->len = 0; + ent->size = SEGTAB_INIT_SIZE; + ent->parts = malloc(sizeof(struct segment *) * + SEGTAB_INIT_SIZE); + + if (ent->parts == NULL) { + PERROR("cannot alloc"); + return M_ERROR; + } + + return M_SUCCESS; +} + +void segtab_ent_free(struct segment_table_entry *ent) +{ + free(ent->parts); +} + +int segtab_ent_push(struct segment_table_entry *ent, struct segment *seg) +{ + if (ent->len >= ent->size) { + uint32_t size = ent->size * 2; + void *new = realloc(ent->parts, + sizeof(struct segment *) * size); + if (new == NULL) { + PERROR("cannot relloc"); + return M_ERROR; + } + ent->size = size; + ent->parts = new; + } + + if (ent->len > 0) { + struct segment *first = ent->parts[0]; + if (first->align != seg->align) { + ERROR("segment '%s' doest not have matching alignment", + ent->name); + } + if (first->read != seg->read || + first->write != seg->write || + first->execute != seg->execute) { + ERROR("segment '%s' doest not have matching RWX", + ent->name); + } + } else { + ent->off = seg->new_off; + ent->vaddr = seg->new_vaddr; + } + + ent->parts[ent->len++] = seg; + return M_SUCCESS; +} + +uint32_t segtab_ent_size(struct segment_table_entry *ent) +{ + uint32_t size = 0; + for (uint32_t i = 0; i < ent->len; i++) { + size += ent->parts[i]->size; + } + return size; +} diff --git a/mld/strtab.c b/mld/strtab.c new file mode 100644 index 0000000..c31889b --- /dev/null +++ b/mld/strtab.c @@ -0,0 +1,56 @@ +#include <merror.h> +#include <stdlib.h> + +#include "link.h" + +int strtab_init(struct string_table *strtab) +{ + strtab->len = 1; + strtab->data = malloc(1); + + if (strtab->data == NULL) { + PERROR("cannot alloc"); + return M_ERROR; + } + + strtab->data[0] = '\0'; + return M_SUCCESS; +} + +void strtab_free(struct string_table *strtab) +{ + free(strtab->data); +} + +int strtab_push(struct string_table *strtab, const char *str, size_t *res) +{ + if (strtab_get(strtab, str, res) == M_SUCCESS) + return M_SUCCESS; + + size_t len = strlen(str); + char *new = realloc(strtab->data, strtab->len + len + 1); + if (new == NULL) { + PERROR("cannot realloc"); + return M_ERROR; + } + strtab->data = new; + memcpy(strtab->data + strtab->len, str, len + 1); + + if (res != NULL) + *res = strtab->len; + strtab->len += len + 1; + + return M_SUCCESS; +} + +int strtab_get(struct string_table *strtab, const char *str, size_t *res) +{ + for (size_t i = 0; i < strtab->len; i++) { + if (strcmp(strtab->data + i, str) == 0) { + if (res != NULL) + *res = i; + return M_SUCCESS; + } + } + return M_ERROR; +} diff --git a/mld/symtab.c b/mld/symtab.c new file mode 100644 index 0000000..eca6dbe --- /dev/null +++ b/mld/symtab.c @@ -0,0 +1,60 @@ +#include <elf.h> +#include <merror.h> +#include <stdlib.h> +#include <melf.h> + +#include "link.h" + +#define SYMTAB_INIT_LEN 8 + +int symtab_init(struct symbol_table *symtab) +{ + symtab->len = 1; + symtab->size = SYMTAB_INIT_LEN; + symtab->syms = malloc(sizeof(Elf32_Sym) * SYMTAB_INIT_LEN); + + if (symtab->syms == NULL) { + PERROR("cannot alloc"); + return M_ERROR; + } + + symtab->syms[0] = (Elf32_Sym){0}; + + return M_SUCCESS; +} + +void symtab_free(struct symbol_table *symtab) +{ + free(symtab->syms); +} + +int symtab_push(struct symbol_table *symtab, const Elf32_Sym *sym) +{ + if (symtab->len >= symtab->size) { + size_t size = symtab->size *= 2; + void *new = realloc(symtab->syms, sizeof(Elf32_Sym) * size); + if (new == NULL) { + PERROR("cannot realloc"); + return M_ERROR; + } + symtab->size = size; + symtab->syms = new; + } + + symtab->syms[symtab->len++] = *sym; + return M_SUCCESS; +} + +int symtab_get(struct symbol_table *symtab, Elf32_Sym **res, const char *name) +{ + for (size_t i = 0; i < symtab->len; i++) { + Elf32_Sym *sym = &symtab->syms[i]; + const char *symname = symtab->strtab->data + B32(sym->st_name); + if (strcmp(name, symname) == 0) { + if (res != NULL) + *res = sym; + return M_SUCCESS; + } + } + return M_ERROR; +} diff --git a/test/Makefile b/test/Makefile index 1a97dd6..64f902d 100644 --- a/test/Makefile +++ b/test/Makefile @@ -3,18 +3,15 @@ LD=afl-cc BIN=../bin -none: +.PHONY: masm mld msim -clean: - rm -fr $(BIN) - -masm: clean - make -C ../masm build CC=$(CC) LD=$(LD) +masm: + make -C ../masm clean build CC=$(CC) LD=$(LD) $(BIN)/masm/masm -o ./mld/test.o ./masm/test.asm -mld: clean - make -C ../mld build CC=$(CC) LD=$(LD) +mld: + make -C ../mld clean build CC=$(CC) LD=$(LD) $(BIN)/mld/mld -o ./msim/test ./mld/test.o -msim: clean - make -C ../msim build CC=$(CC) LD=$(LD) +msim: + make -C ../msim clean build CC=$(CC) LD=$(LD) diff --git a/test/mld/test.o b/test/mld/test.o Binary files differindex 9281a13..c0a5e03 100644 --- a/test/mld/test.o +++ b/test/mld/test.o diff --git a/test/msim/test b/test/msim/test Binary files differnew file mode 100644 index 0000000..f81c617 --- /dev/null +++ b/test/msim/test |