start mld, add loading of object files, add fuzzing support

6 files changed, 740 insertions, 0 deletions

diff --git a/mld/Makefile b/mld/Makefile
new file mode 100644
index 0000000..fd907d9
--- /dev/null
+++ b/mld/Makefile
@@ -0,0 +1,7 @@
+include ../config.mk
+
+SRC=.
+BIN=../bin/mld
+OUT=mld
+
+include ../makefile.mk
diff --git a/mld/link.c b/mld/link.c
new file mode 100644
index 0000000..2593806
--- /dev/null
+++ b/mld/link.c
@@ -0,0 +1,62 @@
+#include <stdlib.h>
+#include <merror.h>
+#include <string.h>
+#include <sys/stat.h>
+
+#include "link.h"
+
+static int load_objects(struct linker *linker)
+{
+	linker->objects = malloc(sizeof(struct object) *
+			  linker->args->in_count);
+	linker->obj_len = 0;
+
+	if (linker->objects == NULL) {
+		ERROR("cannot alloc");
+		return M_ERROR;
+	}
+
+	for (int i = 0; i < linker->args->in_count; i++) {
+		char *path = linker->args->in_files[i];
+		struct object *obj = &linker->objects[linker->obj_len];
+
+		// check for duplicate
+		for (size_t j = 0; j < linker->obj_len; j++) {
+			const char *dupname = linker->objects[j].name;
+			struct stat st, st2;
+			if (stat(path, &st) || stat(dupname, &st2))
+				continue;
+			if (st.st_ino == st2.st_ino)
+				goto skip_obj;
+		}
+
+		// load obj file
+		linker->obj_len++;
+		if (object_load(obj, path))
+			return M_ERROR;
+skip_obj:
+	}
+
+	return M_SUCCESS;
+}
+
+static void linker_free(struct linker *linker)
+{
+	if (linker->objects != NULL) {
+		for (size_t i = 0; i < linker->obj_len; i++)
+			object_free(&linker->objects[i]);
+		free(linker->objects);
+	}
+}
+
+int link_files(struct linker_arguments args) {
+	struct linker linker;
+	linker.args = &args;
+	int res = M_SUCCESS;
+
+	if (res == M_SUCCESS)
+		res = load_objects(&linker);
+
+	linker_free(&linker);
+	return res;
+}
diff --git a/mld/link.h b/mld/link.h
new file mode 100644
index 0000000..ac97bbf
--- /dev/null
+++ b/mld/link.h
@@ -0,0 +1,151 @@
+/* Copyright (c) 2024 Freya Murphy */
+
+#ifndef __LINK_H__
+#define __LINK_H__
+
+#include <linux/limits.h>
+#include <mlimits.h>
+#include <mips.h>
+#include <merror.h>
+#include <stdint.h>
+#include <elf.h>
+#include <stdio.h>
+
+
+// when mapping porinters, we need to bounds check to
+// make sure its in the mapped object file
+//
+// this checks that
+// 1. the end is in the file
+// 2. the off and len doesnt integer overflow
+#define BOUND_CHK(obj, len, off) \
+	(off > UINT32_MAX - len || off + len > obj->mapped_size)
+
+
+// pre define
+struct linker;
+struct object;
+struct segment;
+
+///
+/// relocation table
+///
+
+struct relocation_table {
+	uint32_t type;
+	union {
+		void *raw;
+		Elf32_Rel  *rel;
+		Elf32_Rela *rela;
+	};
+	size_t len;
+	struct symbol_table *symtab;
+};
+
+///
+/// string table
+///
+
+struct string_table {
+	char *data;
+	size_t len;
+};
+
+///
+/// symbol table
+///
+
+struct symbol_table {
+	struct string_table *strtab;
+	Elf32_Sym *syms;
+	size_t len;
+};
+
+///
+/// segment
+///
+
+/* a loadable program segment */
+struct segment {
+	// phdr
+	Elf32_Phdr *phdr;
+	uint32_t phdr_idx;
+
+	// shdr
+	Elf32_Shdr *shdr;
+	uint32_t shdr_idx;
+
+	// segment data
+	char *name;
+	unsigned char *bytes;
+
+	// relocation table
+	struct relocation_table reltab;
+};
+
+int segment_load(struct object *object, struct segment *segment, size_t index);
+
+///
+/// object file
+///
+
+struct object {
+	// file
+	int fd;
+	char *mapped;
+	size_t mapped_size;
+
+	// ehdr
+	Elf32_Ehdr *ehdr;
+
+	// section header table
+	Elf32_Shdr *shdr;
+	size_t shdr_len;
+
+	// program table
+	Elf32_Phdr *phdr;
+	size_t phdr_len;
+
+	// object meta
+	const char *name;
+	size_t index;
+
+	// segments
+	size_t segment_len;
+	struct segment *segments;
+
+	// section header strtab
+	struct string_table *shstrtab;
+
+	// strtabs
+	struct string_table *strtabs;
+	// symtabs
+	struct symbol_table *symtabs;
+};
+
+int object_load(struct object *object, char *path);
+
+void object_free(struct object *object);
+
+///
+/// linker
+///
+
+struct linker {
+	size_t obj_len;
+	struct object *objects;
+
+	struct linker_arguments *args;
+};
+
+/* defines arguments to the linker */
+struct linker_arguments {
+	char **in_files;
+	int in_count;
+	char *out_file;
+};
+
+/* link object files */
+int link_files(struct linker_arguments args);
+
+#endif /* __LINK_H__ */
diff --git a/mld/main.c b/mld/main.c
new file mode 100644
index 0000000..3dd5b5c
--- /dev/null
+++ b/mld/main.c
@@ -0,0 +1,50 @@
+#include <stdio.h>
+#include <unistd.h>
+#include <merror.h>
+#include <string.h>
+
+#include "link.h"
+
+void help(void) {
+	printf("usage: mld [options] objfile...\n\n");
+	printf("options:\n");
+	printf("\t-h\t\tprints this help message\n");
+	printf("\t-o <output>\tselect a output file destination\n");
+}
+
+int main(int argc, char **argv) {
+
+	struct linker_arguments args = {
+		.in_files = NULL,
+		.in_count = 0,
+		.out_file = "a.out",
+	};
+
+	int c;
+
+	while ((c = getopt(argc, argv, "ho:")) != 1) {
+		switch(c) {
+		case 'h':
+			help();
+			return M_SUCCESS;
+		case 'o':
+			args.out_file = optarg;
+			break;
+		case '?':
+			return M_ERROR;
+		default:
+			goto next;
+		}
+	}
+
+next:
+	if (optind >= argc) {
+		ERROR("no object files passed");
+		return M_ERROR;
+	}
+
+	args.in_files = &argv[optind];
+	args.in_count = argc - optind;
+
+	return link_files(args);
+}
diff --git a/mld/obj.c b/mld/obj.c
new file mode 100644
index 0000000..9a83d31
--- /dev/null
+++ b/mld/obj.c
@@ -0,0 +1,335 @@
+#include <elf.h>
+#include <merror.h>
+#include <melf.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+#include "link.h"
+
+extern char *current_file;
+
+static int obj_assert_ehdr(const void *given, const void *assert, size_t size)
+{
+	if (memcmp(given, assert, size) == 0)
+		return M_SUCCESS;
+	ERROR("invalid elf file");
+	return M_ERROR;
+}
+
+/**
+ * Map the ehdr
+ */
+static int load_ehdr(struct object *object)
+{
+	uint32_t off = 0;
+	object->ehdr = (Elf32_Ehdr *) (object->mapped + off);
+
+	if (BOUND_CHK(object, sizeof(Elf32_Ehdr), off)) {
+		ERROR("cannot read ehdr");
+		return M_ERROR;
+	}
+
+	/**
+	 * Compare each "static" value in the ehdr and make sure it
+	 * is what it should be. If not throw and error and eventually
+	 * return.
+	 */
+
+	#define EHDR_ASSERT(name, size)                                   \
+			if (res == M_SUCCESS)                             \
+			  res |= obj_assert_ehdr(&MIPS_ELF_EHDR.e_##name, \
+			  &object->ehdr->e_##name, size)                  \
+
+	int res = 0;
+	EHDR_ASSERT(ident,     EI_NIDENT);
+	EHDR_ASSERT(type,      sizeof(Elf32_Half));
+	EHDR_ASSERT(machine,   sizeof(Elf32_Half));
+	EHDR_ASSERT(version,   sizeof(Elf32_Word));
+	EHDR_ASSERT(flags,     sizeof(Elf32_Word));
+	EHDR_ASSERT(ehsize,    sizeof(Elf32_Half));
+	EHDR_ASSERT(phentsize, sizeof(Elf32_Half));
+	EHDR_ASSERT(shentsize, sizeof(Elf32_Half));
+
+	#undef EHDR_ASSERT
+
+	if (res)
+		return M_ERROR;
+
+	return M_SUCCESS;
+}
+
+/**
+ * Map the shdr
+ */
+static int load_shdr(struct object *object)
+{
+	size_t shdr_len = B16(object->ehdr->e_shentsize) *
+		B16(object->ehdr->e_shnum);
+	size_t shdr_off = B32(object->ehdr->e_shoff);
+	object->shdr = (Elf32_Shdr *) (object->mapped + shdr_off);
+	object->shdr_len = B16(object->ehdr->e_shnum);
+
+	if (BOUND_CHK(object, shdr_len, shdr_off)) {
+		ERROR("cannot read shdr");
+		return M_ERROR;
+	}
+
+	return M_SUCCESS;
+}
+
+/**
+ * Map the phdr
+ */
+static int load_phdr(struct object *object)
+{
+	size_t phdr_len = B16(object->ehdr->e_phentsize) *
+		B16(object->ehdr->e_phnum);
+	size_t phdr_off = B32(object->ehdr->e_phoff);
+	object->phdr = (Elf32_Phdr *) (object->mapped + phdr_off);
+	object->phdr_len = B16(object->ehdr->e_phnum);
+
+	if (BOUND_CHK(object, phdr_len, phdr_off)) {
+		ERROR("cannot read phdr");
+		return M_ERROR;
+	}
+
+	return M_SUCCESS;
+}
+
+/**
+ * Load the strtabs
+ */
+static int load_strtabs(struct object *object)
+{
+	uint32_t max_entries = object->shdr_len;
+	struct string_table *strtabs = malloc(max_entries *
+					sizeof(struct string_table));
+
+	if (strtabs == NULL) {
+		PERROR("cannot alloc");
+		return M_ERROR;
+	}
+
+	for (size_t i = 0; i < object->shdr_len; i++) {
+		Elf32_Shdr *hdr = &object->shdr[i];
+		struct string_table *strtab = &strtabs[i];
+
+		if (B32(hdr->sh_type) != SHT_STRTAB) {
+			strtab->len = 0;
+			continue;
+		}
+
+		uint32_t off = B32(hdr->sh_offset);
+		uint32_t len = B32(hdr->sh_size);
+
+		strtab->len = len;
+		strtab->data = object->mapped + off;
+
+		if (len < 1) {
+			ERROR("invalid or empty strtab [%d]", i);
+			return M_ERROR;
+		}
+
+		if (BOUND_CHK(object, len, off)) {
+			ERROR("cannot map strtab [%d]", i);
+			return M_ERROR;
+		}
+
+		if (strtab->data[0] != '\0' ||
+			strtab->data[len - 1] != '\0') {
+			ERROR("strtab [%d] doesn't not have bounding null "
+				"values", i);
+			return M_ERROR;
+		}
+	}
+
+	object->strtabs = strtabs;
+	return M_SUCCESS;
+}
+
+/**
+ * Load the symtabs
+ */
+static int load_symtabs(struct object *object)
+{
+	uint32_t max_entries = object->shdr_len;
+	struct symbol_table *symtabs = malloc(max_entries *
+					sizeof(struct symbol_table));
+
+	if (symtabs == NULL) {
+		PERROR("cannot alloc");
+		return M_ERROR;
+	}
+
+	for (size_t i = 0; i < object->shdr_len; i++) {
+		Elf32_Shdr *hdr = &object->shdr[i];
+		struct symbol_table *symtab = &symtabs[i];
+
+		if (B32(hdr->sh_type) != SHT_SYMTAB) {
+			symtab->len = 0;
+			continue;
+		}
+
+		uint32_t off = B32(hdr->sh_offset);
+		uint32_t len = B32(hdr->sh_size);
+		uint32_t stridx = B32(hdr->sh_link);
+
+		if (stridx >= max_entries) {
+			ERROR("strtab index [%d] out of bounds", stridx);
+			return M_ERROR;
+		}
+
+		struct string_table *strtab = &object->strtabs[stridx];
+		if (strtab->len < 1) {
+			ERROR("strtab index [%d] empty or invalid", stridx);
+			return M_ERROR;
+		}
+
+		symtab->strtab = strtab;
+		symtab->len = len;
+		symtab->syms = (Elf32_Sym *) (object->mapped + off);
+
+		if (BOUND_CHK(object, len, off)) {
+			ERROR("cannot map symtab index [%d]", i);
+			return M_ERROR;
+		}
+	}
+
+	object->symtabs = symtabs;
+	return M_SUCCESS;
+}
+
+/**
+ * Load the shstrtab
+ */
+static int load_shstrtab(struct object *object)
+{
+	uint16_t idx = B16(object->ehdr->e_shstrndx);
+	if (idx >= object->shdr_len) {
+		ERROR("shstrndx [%d] out of bounds", idx);
+		return M_ERROR;
+	}
+
+	struct string_table *strtab = &object->strtabs[idx];
+	if (strtab->len < 1) {
+		ERROR("shstrndx is invalid or empty");
+		return M_ERROR;
+	}
+
+	object->shstrtab = strtab;
+	return M_SUCCESS;
+}
+
+/**
+ * Load the program segments
+ */
+static int load_segments(struct object *object)
+{
+	object->segment_len = B16(object->ehdr->e_phnum);
+	object->segments = malloc(sizeof(struct segment) *
+				object->segment_len);
+
+	if (object->segments == NULL) {
+		PERROR("cannot alloc");
+		return M_ERROR;
+	}
+
+	for (size_t i = 0; i < object->segment_len; i++) {
+		struct segment *seg = &object->segments[i];
+		if (segment_load(object, seg, i)) {
+			return M_ERROR;
+		}
+	}
+
+	return M_SUCCESS;
+}
+
+static int map_file(struct object *obj, char *path)
+{
+	obj->fd = open(path, O_RDONLY);
+	if (obj->fd == -1) {
+		PERROR("cannot read");
+		return M_ERROR;
+	}
+
+	struct stat st;
+	if (stat(path, &st)) {
+		PERROR("cannot stat");
+		return M_ERROR;
+	}
+
+	obj->mapped_size = st.st_size;
+	obj->mapped = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED,
+				obj->fd, 0);
+
+	if (obj->mapped == MAP_FAILED) {
+		PERROR("cannot map");
+		return M_ERROR;
+	}
+
+	return M_SUCCESS;
+}
+
+int object_load(struct object *object, char *path)
+{
+	current_file = path;
+
+	object->fd = 0;
+	object->segments = NULL;
+	object->symtabs = NULL;
+	object->strtabs = NULL;
+	object->mapped = NULL;
+	object->name = path;
+
+	/** load the file */
+	if (map_file(object, path))
+		return M_ERROR;
+
+	/* ehdr */
+	if (load_ehdr(object))
+		return M_ERROR;
+
+	/* shdr */
+	if (load_shdr(object))
+		return M_ERROR;
+
+	/* phdr */
+	if (load_phdr(object))
+		return M_ERROR;
+
+	/* strtabs */
+	if (load_strtabs(object))
+		return M_ERROR;
+
+	/* symtabs */
+	if (load_symtabs(object))
+		return M_ERROR;
+
+	/* shstrtab */
+	if (load_shstrtab(object))
+		return M_ERROR;
+
+	/* segments */
+	if (load_segments(object))
+		return M_ERROR;
+
+	return M_SUCCESS;
+}
+
+void object_free(struct object *obj)
+{
+	if (obj->symtabs != NULL)
+		free(obj->symtabs);
+	if (obj->strtabs != NULL)
+		free(obj->strtabs);
+	if (obj->segments != NULL)
+		free(obj->segments);
+	if (obj->fd > 0)
+		close(obj->fd);
+	if (obj->mapped != NULL && obj->mapped != MAP_FAILED)
+		munmap(obj->mapped, obj->mapped_size);
+}
diff --git a/mld/seg.c b/mld/seg.c
new file mode 100644
index 0000000..a720720
--- /dev/null
+++ b/mld/seg.c
@@ -0,0 +1,135 @@
+#include <merror.h>
+#include <melf.h>
+#include <elf.h>
+#include <sys/mman.h>
+
+#include "link.h"
+
+/**
+ * Read the phdr for this segment
+ */
+static int load_phdr(struct object *obj, struct segment *seg, size_t index)
+{
+	if (index >= obj->phdr_len) {
+		ERROR("phdr index [%d] out of bounds", index);
+		return M_ERROR;
+	}
+
+	seg->phdr = &obj->phdr[index];
+	seg->phdr_idx = index;
+	return M_SUCCESS;
+}
+
+/**
+ * Read the shdr for this segment
+ */
+static int load_shdr(struct object *obj, struct segment *seg, size_t index)
+{
+	bool found = false;
+
+	for (size_t i = 0; i < obj->shdr_len; i++) {
+		Elf32_Shdr *hdr = &obj->shdr[i];
+
+		// find shdr that matches  the offset in phdr
+		if (seg->phdr->p_offset != hdr->sh_offset)
+			continue;
+
+
+		// get name
+		uint32_t name = B32(hdr->sh_name);
+		if (name >= obj->shstrtab->len) {
+			ERROR("section name index [%d] out of bounds", name);
+			return M_ERROR;
+		}
+		seg->name = &obj->shstrtab->data[name];
+
+		// map bytes
+		uint32_t len = B32(hdr->sh_size);
+		uint32_t off = B32(hdr->sh_offset);
+		seg->bytes = (unsigned char *) (obj->mapped + off);
+
+		if (BOUND_CHK(obj, len, off)) {
+			ERROR("cannot map seg %s:%d", seg->name, index);
+			return M_ERROR;
+		}
+
+		found = true;
+		seg->shdr = hdr;
+		seg->shdr_idx = i;
+		break;
+	}
+
+	if (!found) {
+		ERROR("cannot find shdr for segment [%d]", index);
+		return M_ERROR;
+	}
+
+	return M_SUCCESS;
+}
+
+/**
+ * Read the relocation table for this segment (if one exists)
+ */
+static int load_reltab(struct object *obj, struct segment *seg)
+{
+	// default to none
+	seg->reltab.len = 0;
+
+	for (size_t i = 0; i < obj->shdr_len; i++) {
+		Elf32_Shdr *hdr = &obj->shdr[i];
+		uint32_t type = B32(hdr->sh_type);
+
+		if (type != SHT_REL && type != SHT_RELA)
+			continue;
+
+		if (B32(hdr->sh_info) != seg->shdr_idx)
+			continue;
+
+		uint32_t symtab_idx = B32(hdr->sh_link);
+		if (symtab_idx >= obj->shdr_len) {
+			ERROR("reltab [%d] symtab index [%d] out of bounds",
+				i, symtab_idx);
+			return M_ERROR;
+		}
+
+		struct symbol_table *symtab = &obj->symtabs[symtab_idx];
+		if (symtab->len < 1) {
+			ERROR("reltab [%d] symtab is empty or invalid", i);
+			return M_ERROR;
+		}
+
+		uint32_t len = B32(hdr->sh_size);
+		uint32_t off = B32(hdr->sh_offset);
+
+
+		seg->reltab.symtab = symtab;
+		seg->reltab.len = len;
+		seg->reltab.raw = obj->mapped + off;
+		seg->reltab.type = type;
+
+		if (BOUND_CHK(obj, len, off)) {
+			ERROR("cannot map reltab [%d] for %s",
+				i, seg->name);
+			return M_ERROR;
+		}
+
+		break;
+	}
+
+	return M_SUCCESS;
+}
+
+int segment_load(struct object *obj, struct segment *seg, size_t index)
+{
+
+	if (load_phdr(obj, seg, index))
+		return M_ERROR;
+
+	if (load_shdr(obj, seg, index))
+		return M_ERROR;
+
+	if (load_reltab(obj, seg))
+		return M_ERROR;
+
+	return M_SUCCESS;
+}