Initial parsing of the provided initrd file

We expect a CPIO archive with the 'newc' format for the initrd. Parse
this archive from the given initrd address and fetch the address for
each ELF executable while also pairing which task correspond to which
ELF.

This commit leaves to do the actual parsing of the ELF file for each
task, while also leaving some string utilities to be refined.

Signed-off-by: Miquel Sabaté Solà <mikisabate@gmail.com>

11 files changed, 244 insertions, 11 deletions

diff --git a/.gitignore b/.gitignore
index dc7f65d..0fc4add 100644
--- a/.gitignore
+++ b/.gitignore
@@ -8,6 +8,7 @@ usr/initramfs.cpio
 
 test/*.o
 test/test_dt
+test/test_initrd
 
 # You can generate it with Bear: `$ bear -- make`.
 compile_commands.json
diff --git a/Makefile b/Makefile
index bda1158..0d8bc44 100644
--- a/Makefile
+++ b/Makefile
@@ -60,9 +60,9 @@ SRC    = $(filter-out kernel/fbos.ld.S, $(wildcard kernel/*.S kernel/*.c lib/*.c
 OBJ    = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SRC)))
 LINKER = kernel/fbos.ld
 KRNL   = fbos
-USR    = usr/bin/foo
+USR    = usr/bin/foo usr/bin/bar usr/bin/foobar
 INIT   = usr/initramfs.cpio
-TESTS  = test/test_dt
+TESTS  = test/test_dt test/test_initrd
 
 LDFLAGS += -T $(LINKER)
 
@@ -111,19 +111,21 @@ usr/bin/%: usr/src/%.o
 # Tests
 
 .PHONY: test
-test: host_lib $(TESTS)
+test: host_lib usr $(TESTS)
 	$(Q) ./test/test_dt
+	$(Q) ./test/test_initrd
 
 host_lib:
-	$(Q) $(HOSTCC) $(WARNINGS) -Iinclude/ -g -c lib/dt.c -o lib/dt.o
+	$(Q) mkdir -p test/lib
+	$(Q) $(HOSTCC) $(WARNINGS) -Iinclude/ -g -c lib/dt.c -o test/lib/dt.o
+	$(Q) $(HOSTCC) $(WARNINGS) -Iinclude/ -g -c kernel/initrd.c -o test/lib/initrd.o
 
 test/%.o: test/%.c
-	$(E) "	HOSTCC	" $(basename $@)
 	$(Q) $(HOSTCC) $(WARNINGS) -g -Iinclude/ -c $< -o $@
 
 test/%: test/%.o
-	$(E) "	HOSTLD	" $@
-	$(Q) $(HOSTCC) -Iinclude/ $< lib/dt.o -o $@
+	$(E) "	TEST	" $@
+	$(Q) $(HOSTCC) -Iinclude/ $< test/lib/*.o -o $@
 
 ##
 # Hacking
@@ -142,7 +144,7 @@ gdb:
 
 .PHONY: clean
 clean:
-	$(Q) rm -f $(OBJ) $(KRNL) $(LINKER) $(USR) usr/src/*.o $(INIT) test/*.o $(TESTS)
+	$(Q) rm -f $(OBJ) $(KRNL) $(LINKER) $(USR) usr/src/*.o $(INIT) test/*.o test/lib/*.o $(TESTS)
 
 .PHONY: lint
 lint:
diff --git a/include/fbos/init.h b/include/fbos/init.h
index eb72508..c4d0a85 100644
--- a/include/fbos/init.h
+++ b/include/fbos/init.h
@@ -5,7 +5,11 @@
 
 extern struct task_struct init_task;
 
+// Extract the executables from the initrd that is located at `base_addr` and
+// has the given `size`.
+void extract_initrd(const char *const base_addr, uint64_t size);
+
 // The entry point for the kernel.
-__noreturn __kernel void start_kernel(void *dtb);
+void start_kernel(void *dtb);
 
 #endif /* __FBOS_INIT_H */
diff --git a/include/fbos/sched.h b/include/fbos/sched.h
index 626f72f..5cfc2ba 100644
--- a/include/fbos/sched.h
+++ b/include/fbos/sched.h
@@ -1,6 +1,14 @@
 #ifndef __FBOS_SCHED_H_
 #define __FBOS_SCHED_H_
 
+enum task_id {
+	TASK_UNKNOWN = -1,
+	TASK_INIT = 0,
+	TASK_FOO = 1,
+	TASK_BAR = 2,
+	TASK_FOOBAR = 3,
+};
+
 struct task_struct {
 	void *stack;
 };
diff --git a/include/fbos/string.h b/include/fbos/string.h
index af7e2ef..ade77cc 100644
--- a/include/fbos/string.h
+++ b/include/fbos/string.h
@@ -5,5 +5,7 @@
 
 extern size_t strlen(const char *);
 extern int strcmp(const char *, const char *);
+extern int memcmp(const void *, const void *, size_t);
+extern void *memcpy(void *, const void *, size_t);
 
 #endif // __FBOS_STRING_H_
diff --git a/kernel/initrd.c b/kernel/initrd.c
new file mode 100644
index 0000000..c05e77d
--- /dev/null
+++ b/kernel/initrd.c
@@ -0,0 +1,135 @@
+#include <fbos/init.h>
+#include <fbos/sched.h>
+#include <fbos/printk.h>
+#include <fbos/string.h>
+
+#define BUFFER_SIZE 16
+
+#define CPIO_HEADER_FILESIZE 54
+#define CPIO_HEADER_NAMESIZE 94
+#define CPIO_HEADER_SIZE 110
+
+// TODO: move to assembly
+__kernel void *memcpy(void *dest, const void *src, size_t count)
+{
+	char *destc = dest;
+	const char *srcc = src;
+
+	for (uint64_t i = 0; i < count; i++) {
+		*destc++ = *srcc++;
+	}
+	return dest;
+}
+
+// TODO: this is required by GCC which must be doing some optimization
+// underneath. For now let's keep it simple (and wrong) by just calling memcpy.
+__kernel void *memmove(void *dest, const void *src, size_t count)
+{
+	return memcpy(dest, src, count);
+}
+
+__kernel uint64_t strtoul16(const char *str, size_t count)
+{
+	char c;
+	uint64_t ret = 0;
+	uint64_t aux = 0;
+
+	for (uint64_t i = 1; count > 0; i *= 16, count--) {
+		c = str[count - 1];
+		if (c >= 'A' && c <= 'F') {
+			aux = 10 + (uint64_t)(c - 'A');
+		} else if (c >= 'a' && c <= 'f') {
+			aux = 10 + (uint64_t)(c - 'a');
+		} else if (c < '0' || c > '9') {
+			die("Bad number\n");
+		} else {
+			aux = (uint64_t)c - '0';
+		}
+
+		ret += aux * i;
+	}
+	return ret;
+}
+
+__kernel int get_task_id_from_name(const char *const name)
+{
+	if (strcmp(name, "usr/bin/foo") == 0) {
+		return TASK_FOO;
+	} else if (strcmp(name, "usr/bin/bar") == 0) {
+		return TASK_BAR;
+	} else if (strcmp(name, "usr/bin/foobar") == 0) {
+		return TASK_FOOBAR;
+	}
+	return TASK_UNKNOWN;
+}
+
+__kernel void extract_elf(int task_id, const char *const addr, size_t size)
+{
+	__unused(task_id);
+	__unused(addr);
+	__unused(size);
+
+	// TODO
+}
+
+__kernel void extract_initrd(const char *const initrd_addr, uint64_t size)
+{
+	char buffer[BUFFER_SIZE];
+	uint64_t name_size, file_size, padding, base = 0;
+	int task_id;
+
+	// The `base` is the index from `initrd_addr` which points to the first byte
+	// of the header of the currently evaluated file inside of the CPIO archive.
+	while (base < size) {
+		// Only the "newc" format is supported, without checksums nor fancy
+		// stuff.
+		if (memcmp(&initrd_addr[base], "070701", 6) != 0) {
+			if (memcmp(&initrd_addr[base], "070702", 6) == 0 ||
+				memcmp(&initrd_addr[base], "070707", 6) == 0) {
+				die("Incorrect cpio format: stick to 'newc'");
+			} else {
+				die("No cpio magic number");
+			}
+		}
+
+		// We identify the task being extracted by looking at the file's path,
+		// so let's first get the size of it.
+		memcpy(buffer, &initrd_addr[base + CPIO_HEADER_NAMESIZE], 8);
+		buffer[8] = '\0';
+		name_size = strtoul16(buffer, 8);
+		if (name_size >= BUFFER_SIZE) {
+			die("Path too large for initrd executable");
+		}
+
+		// Right after the header (hence current header + its size) there is the
+		// actual file's path, which is exactly `name_size` long. Fetch it now
+		// to identify the task at hand.
+		memcpy(buffer, &initrd_addr[base + CPIO_HEADER_SIZE], name_size);
+		buffer[name_size] = '\0';
+		task_id = get_task_id_from_name(buffer);
+
+		// Note that this is not necessarily a bad CPIO archive, it might just
+		// be the end "TRAILER!!!" delimiter. Either way, just quit at this
+		// point.
+		if (task_id == TASK_UNKNOWN) {
+			break;
+		}
+
+		// Fetch the size of the executable, which is needed for `extract_elf`,
+		// as well as for advancing the `base` to the next file.
+		memcpy(buffer, &initrd_addr[base + CPIO_HEADER_FILESIZE], 8);
+		buffer[8] = '\0';
+		file_size = strtoul16(buffer, 8);
+
+		// Files are aligned in 4-byte boundaries after the header. That's why
+		// there might be some padding in between the header and the file.
+		padding = 4 - ((CPIO_HEADER_SIZE + name_size) & 3);
+
+		// And extract everything from the ELF file for the given task.
+		extract_elf(task_id, &initrd_addr[base + name_size + CPIO_HEADER_SIZE + padding],
+					file_size);
+
+		// Advance the base to the next file.
+		base += CPIO_HEADER_SIZE + name_size + padding + file_size;
+	}
+}
diff --git a/kernel/main.c b/kernel/main.c
index 11f2721..7eb2ef6 100644
--- a/kernel/main.c
+++ b/kernel/main.c
@@ -20,7 +20,8 @@ __noreturn __kernel void start_kernel(void *dtb)
 	printk("Welcome to FizzBuzz OS!\n");
 
 	struct initrd_addr addr = find_dt_initrd_addr(dtb);
-	__unused(addr); // TODO
+
+	extract_initrd((char *)addr.start, addr.end - addr.start);
 
 	// TODO: reenable stuff
 
diff --git a/kernel/string.S b/kernel/string.S
index afd5985..4fb1ccc 100644
--- a/kernel/string.S
+++ b/kernel/string.S
@@ -35,12 +35,38 @@ strcmp:
 1:
 	lbu t0, 0(a0)
 	lbu t1, 0(a1)
-	bne t0, t1, 2f
 	addi a0, a0, 1
 	addi a1, a1, 1
+	bne t0, t1, 2f
 	bnez t0, 1b
 	li a0, 0
 	ret
 2:
 	sub a0, t0, t1
 	ret
+
+/*
+ * Defined in include/fbos/string.h
+ *
+ *     int memcmp(const void *ptr1, const void *ptr2, size_t n)
+ *
+ * Returns (a0): comparison result as in stdlib.
+ * Parameter (a0, a1): strings to compare.
+ * Clobbers: t0, t1.
+ */
+.global memcmp
+.type memcmp, @function
+memcmp:
+1:
+	lbu t0, 0(a0)
+	lbu t1, 0(a1)
+	bne t0, t1, 2f
+	addi a0, a0, 1
+	addi a1, a1, 1
+	addi a2, a2, -1
+	bnez a2, 1b
+	li a0, 0
+	ret
+2:
+	sub a0, t0, t1
+	ret
diff --git a/test/test_initrd.c b/test/test_initrd.c
new file mode 100644
index 0000000..3662eaa
--- /dev/null
+++ b/test/test_initrd.c
@@ -0,0 +1,28 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include <fbos/init.h>
+
+int main(void)
+{
+	FILE *fh = fopen("./usr/initramfs.cpio", "rb");
+	assert(fh);
+
+	fseek(fh, 0, SEEK_END);
+	long fsize = ftell(fh);
+	rewind(fh);
+
+	char *contents = malloc((unsigned long)fsize + 1);
+	fread(contents, (unsigned long)fsize, 1, fh);
+	fclose(fh);
+
+	contents[fsize] = 0;
+
+	extract_initrd(contents, (uint64_t)fsize);
+	free(contents);
+
+	// TODO
+
+	exit(0);
+}
diff --git a/usr/src/bar.S b/usr/src/bar.S
new file mode 100644
index 0000000..09c68e3
--- /dev/null
+++ b/usr/src/bar.S
@@ -0,0 +1,13 @@
+.global _start
+.text
+
+_start:
+	li a0, 1
+	la a1, bar
+	ecall
+.Loop:
+	j .Loop
+
+.section .rodata
+bar:
+	.string "bar\n"
diff --git a/usr/src/foobar.S b/usr/src/foobar.S
new file mode 100644
index 0000000..49c9e1d
--- /dev/null
+++ b/usr/src/foobar.S
@@ -0,0 +1,13 @@
+.global _start
+.text
+
+_start:
+	li a0, 1
+	la a1, foobar
+	ecall
+.Loop:
+	j .Loop
+
+.section .rodata
+foobar:
+	.string "foobar\n"