MIPS: relocation: add relocation support

this patch i a port of following patch from u-boot with some additional
integration changes and fixes of original code:
| Subject: [PATCH] MIPS: Stop building position independent code
|
| U-Boot has up until now built with -fpic for the MIPS architecture,
| producing position independent code which uses indirection through a
| global offset table, making relocation fairly straightforward as it
| simply involves patching up GOT entries.
|
| Using -fpic does however have some downsides. The biggest of these is
| that generated code is bloated in various ways. For example, function
| calls are indirected through the GOT & the t9 register:
|
|   8f998064   lw     t9,-32668(gp)
|   0320f809   jalr   t9
|
| Without -fpic the call is simply:
|
|   0f803f01   jal    be00fc04 <puts>
|
| This is more compact & faster (due to the lack of the load & the
| dependency the jump has on its result). It is also easier to read &
| debug because the disassembly shows what function is being called,
| rather than just an offset from gp which would then have to be looked up
| in the ELF to discover the target function.
|
| Another disadvantage of -fpic is that each function begins with a
| sequence to calculate the value of the gp register, for example:
|
|   3c1c0004   lui    gp,0x4
|   279c3384   addiu  gp,gp,13188
|   0399e021   addu   gp,gp,t9
|
| Without using -fpic this sequence no longer appears at the start of each
| function, reducing code size considerably.
|
| This patch switches U-Boot from building with -fpic to building with
| -fno-pic, in order to gain the benefits described above. The cost of
| this is an extra step during the build process to extract relocation
| data from the ELF & write it into a new .rel section in a compact
| format, plus the added complexity of dealing with multiple types of
| relocation rather than the single type that applied to the GOT. The
| benefit is smaller, cleaner, more debuggable code. The relocate_code()
| function is reimplemented in C to handle the new relocation scheme,
| which also makes it easier to read & debug.
|
| Taking maltael_defconfig as an example the size of u-boot.bin built
| using the Codescape MIPS 2016.05-06 toolchain (gcc 4.9.2, binutils
| 2.24.90) shrinks from 254KiB to 224KiB.
|
| Signed-off-by: Paul Burton <paul.burton@imgtec.com>

Signed-off-by: Oleksij Rempel <linux@rempel-privat.de>
Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de>

10 files changed, 285 insertions, 7 deletions

diff --git a/arch/mips/Kconfig b/arch/mips/Kconfig
index a4070cfe32..080f955c38 100644
--- a/arch/mips/Kconfig
+++ b/arch/mips/Kconfig
@@ -32,6 +32,24 @@ config PHYS_ADDR_T_64BIT
 
 menu "Machine selection"
 
+config MIPS_RELOCATION_TABLE_SIZE
+	hex "Relocation table size"
+	range 0x100 0x10000
+	default "0x8000"
+	---help---
+	  A table of relocation data will be appended to the Barebox binary
+	  and parsed in relocate_code() to fix up all offsets in the relocated
+	  Barebox.
+
+	  This option allows the amount of space reserved for the table to be
+	  adjusted in a range from 256 up to 64k. The default is 32k and should
+	  be ok in most cases. Reduce this value to shrink the size of U-Boot
+	  binary.
+
+	  The build will fail and a valid size suggested if this is too small.
+
+	  If unsure, leave at the default value.
+
 config BUILTIN_DTB
 	bool "link a DTB into the barebox image"
 	depends on OFTREE
diff --git a/arch/mips/Makefile b/arch/mips/Makefile
index 5fbd51ceee..6f1a1ce617 100644
--- a/arch/mips/Makefile
+++ b/arch/mips/Makefile
@@ -59,7 +59,7 @@ CPPFLAGS += -DTEXT_BASE=$(CONFIG_TEXT_BASE)
 ifndef CONFIG_MODULES
 # Add cleanup flags
 CPPFLAGS += -fdata-sections -ffunction-sections
-LDFLAGS_barebox += -static --gc-sections
+LDFLAGS_barebox += -static --gc-sections --emit-relocs
 endif
 
 ifdef CONFIG_IMAGE_COMPRESSION
@@ -116,6 +116,13 @@ CFLAGS += $(cflags-y)
 
 lds-$(CONFIG_GENERIC_LINKER_SCRIPT)   := arch/mips/lib/barebox.lds
 
+cmd_barebox__ ?= $(LD) $(LDFLAGS) $(LDFLAGS_barebox) -o $@ \
+      -T $(barebox-lds)                         \
+      --start-group $(barebox-common) --end-group                  \
+      $(filter-out $(barebox-lds) $(barebox-common) FORCE ,$^);	\
+	$(objtree)/scripts/mips-relocs $@
+
+
 CLEAN_FILES    += arch/mips/lib/barebox.lds barebox.map barebox.S
 
 pbl := arch/mips/pbl
diff --git a/arch/mips/boot/main_entry-pbl.c b/arch/mips/boot/main_entry-pbl.c
index 28eaa8791f..60be645148 100644
--- a/arch/mips/boot/main_entry-pbl.c
+++ b/arch/mips/boot/main_entry-pbl.c
@@ -38,7 +38,7 @@ void __section(.text_entry) pbl_main_entry(void *fdt, void *fdt_end,
 {
 	u32 pg_start, pg_end, pg_len, fdt_len;
 	void *fdt_new;
-	void (*barebox)(void *fdt, u32 fdt_len);
+	void (*barebox)(void *fdt, u32 fdt_len, u32 ram_size);
 
 	puts_ll("pbl_main_entry()\n");
 
@@ -56,5 +56,5 @@ void __section(.text_entry) pbl_main_entry(void *fdt, void *fdt_end,
 	memcpy(fdt_new, fdt, fdt_len);
 
 	barebox = (void *)TEXT_BASE;
-	barebox(fdt_new, fdt_len);
+	barebox(fdt_new, fdt_len, ram_size);
 }
diff --git a/arch/mips/boot/start.S b/arch/mips/boot/start.S
index 6efe03e98d..c1cd2d9dd5 100644
--- a/arch/mips/boot/start.S
+++ b/arch/mips/boot/start.S
@@ -18,6 +18,7 @@ EXPORT(_start)
 	/* save dtb pointer */
 	move	s0, a0
 	move	s1, a1
+	move	s2, a2
 
 	/* disable watchpoints */
 	mtc0	zero, CP0_WATCHLO
@@ -32,7 +33,8 @@ EXPORT(_start)
 	/* restore dtb pointer */
 	move	a0, s0
 	move	a1, s1
-	la	v0, main_entry
+	move	a2, s2
+	la	v0, relocate_code
 	jal	v0
 	 nop
 
diff --git a/arch/mips/include/asm/relocs.h b/arch/mips/include/asm/relocs.h
new file mode 100644
index 0000000000..0987c4bb13
--- /dev/null
+++ b/arch/mips/include/asm/relocs.h
@@ -0,0 +1,23 @@
+/* SPDX-License-Identifier: GPL-2.0+ */
+/*
+ * MIPS Relocations
+ *
+ * Copyright (c) 2017 Imagination Technologies Ltd.
+ */
+
+#ifndef __ASM_MIPS_RELOCS_H__
+#define __ASM_MIPS_RELOCS_H__
+
+#define R_MIPS_NONE		0
+#define R_MIPS_32		2
+#define R_MIPS_26		4
+#define R_MIPS_HI16		5
+#define R_MIPS_LO16		6
+#define R_MIPS_PC16		10
+#define R_MIPS_64		18
+#define R_MIPS_HIGHER		28
+#define R_MIPS_HIGHEST		29
+#define R_MIPS_PC21_S2		60
+#define R_MIPS_PC26_S2		61
+
+#endif /* __ASM_MIPS_RELOCS_H__ */
diff --git a/arch/mips/include/asm/sections.h b/arch/mips/include/asm/sections.h
index 2b8c516038..8e004eaf34 100644
--- a/arch/mips/include/asm/sections.h
+++ b/arch/mips/include/asm/sections.h
@@ -1 +1,15 @@
+/* SPDX-License-Identifier: GPL-2.0+ */
+
+#ifndef __ASM_MIPS_SECTIONS_H
+#define __ASM_MIPS_SECTIONS_H
+
 #include <asm-generic/sections.h>
+
+/**
+ * __rel_start: Relocation data generated by the mips-relocs tool
+ *
+ * See arch/mips/lib/reloc.c for details on the format & use of this data.
+ */
+extern uint8_t __rel_start[];
+
+#endif
diff --git a/arch/mips/lib/Makefile b/arch/mips/lib/Makefile
index 7372e8dc27..4ba42e526e 100644
--- a/arch/mips/lib/Makefile
+++ b/arch/mips/lib/Makefile
@@ -4,6 +4,8 @@ obj-y += cpu-probe.o
 lwl-y += end.o
 obj-y += traps.o
 obj-y += genex.o
+obj-y  += reloc.o
+obj-y += sections.o 
 obj-y += shutdown.o
 obj-y += dma-default.o
 
diff --git a/arch/mips/lib/barebox.lds.S b/arch/mips/lib/barebox.lds.S
index 8ddf954517..58b0c5919d 100644
--- a/arch/mips/lib/barebox.lds.S
+++ b/arch/mips/lib/barebox.lds.S
@@ -13,6 +13,8 @@ SECTIONS
 	. = TEXT_BASE;
 
 	. = ALIGN(4);
+
+	.image_start : { *(.__image_start) }
 	.text      :
 	{
 		_stext = .;
@@ -79,9 +81,28 @@ SECTIONS
 	.dtb : { BAREBOX_DTB() }
 
 	_edata = .;
+	.image_end : { *(.__image_end) }
+
 	. = ALIGN(4);
-	__bss_start = .;
-	.bss : { *(.bss*) }
-	__bss_stop = .;
+	/*
+	 * .rel must come last so that the mips-relocs tool can shrink
+	 * the section size & the PT_LOAD program header filesz.
+	 */
+	.data.reloc : {
+		__rel_start = .;
+		BYTE(0x0)
+		. += (32 * 1024) - 1;
+	}
+
 	_end = .;
+
+	.bss __rel_start (OVERLAY) : {
+		__bss_start = .;
+		*(.sbss.*)
+		*(.bss.*)
+		*(COMMON)
+		. = ALIGN(4);
+		__bss_stop = .;
+	}
+
 }
diff --git a/arch/mips/lib/reloc.c b/arch/mips/lib/reloc.c
new file mode 100644
index 0000000000..9756d61666
--- /dev/null
+++ b/arch/mips/lib/reloc.c
@@ -0,0 +1,182 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * MIPS Relocation
+ *
+ * Copyright (c) 2017 Imagination Technologies Ltd.
+ *
+ * Relocation data, found in the .rel section, is generated by the mips-relocs
+ * tool & contains a record of all locations in the Barebox binary that need to
+ * be fixed up during relocation.
+ *
+ * The data is a sequence of unsigned integers, which are of somewhat arbitrary
+ * size. This is achieved by encoding integers as a sequence of bytes, each of
+ * which contains 7 bits of data with the most significant bit indicating
+ * whether any further bytes need to be read. The least significant bits of the
+ * integer are found in the first byte - ie. it somewhat resembles little
+ * endian.
+ *
+ * Each pair of two integers represents a relocation that must be applied. The
+ * first integer represents the type of relocation as a standard ELF relocation
+ * type (ie. R_MIPS_*). The second integer represents the offset at which to
+ * apply the relocation, relative to the previous relocation or for the first
+ * relocation the start of the relocated .text section.
+ *
+ * The end of the relocation data is indicated when type R_MIPS_NONE (0) is
+ * read, at which point no further integers should be read. That is, the
+ * terminating R_MIPS_NONE reloc includes no offset.
+ */
+
+#include <common.h>
+
+#include <asm/bitops.h>
+#include <asm/cache.h>
+#include <asm/cacheops.h>
+#include <asm/cpu.h>
+#include <asm/cpu-info.h>
+#include <asm/io.h>
+#include <asm/mipsregs.h>
+#include <asm/relocs.h>
+#include <asm/sections.h>
+#include <linux/sizes.h>
+#include <asm-generic/memory_layout.h>
+
+#define MAX_BSS_SIZE SZ_1M
+
+void main_entry(void *fdt, u32 fdt_size);
+void relocate_code(void *fdt, u32 fdt_size, u32 relocaddr);
+
+/**
+ * read_uint() - Read an unsigned integer from the buffer
+ * @buf: pointer to a pointer to the reloc buffer
+ *
+ * Read one whole unsigned integer from the relocation data pointed to by @buf,
+ * advancing @buf past the bytes encoding the integer.
+ *
+ * Returns: the integer read from @buf
+ */
+static unsigned long read_uint(uint8_t **buf)
+{
+	unsigned long val = 0;
+	unsigned int shift = 0;
+	uint8_t new;
+
+	do {
+		new = *(*buf)++;
+		val |= (new & 0x7f) << shift;
+		shift += 7;
+	} while (new & 0x80);
+
+	return val;
+}
+
+/**
+ * apply_reloc() - Apply a single relocation
+ * @type: the type of reloc (R_MIPS_*)
+ * @addr: the address that the reloc should be applied to
+ * @off: the relocation offset, ie. number of bytes we're moving Barebox by
+ *
+ * Apply a single relocation of type @type at @addr. This function is
+ * intentionally simple, and does the bare minimum needed to fixup the
+ * relocated Barebox - in particular, it does not check for overflows.
+ */
+static void apply_reloc(unsigned int type, void *addr, long off)
+{
+	uint32_t u32;
+
+	switch (type) {
+	case R_MIPS_26:
+		u32 = *(uint32_t *)addr;
+		u32 = (u32 & GENMASK(31, 26)) |
+		      ((u32 + (off >> 2)) & GENMASK(25, 0));
+		*(uint32_t *)addr = u32;
+		break;
+
+	case R_MIPS_32:
+		*(uint32_t *)addr += off;
+		break;
+
+	case R_MIPS_64:
+		*(uint64_t *)addr += off;
+		break;
+
+	case R_MIPS_HI16:
+		*(uint32_t *)addr += off >> 16;
+		break;
+
+	default:
+		panic("Unhandled reloc type %u\n", type);
+	}
+}
+
+/**
+ * relocate_code() - Relocate Barebox, generally from flash to DDR
+ * @start_addr_sp: new stack pointer
+ * @new_gd: pointer to relocated global data
+ * @relocaddr: the address to relocate to
+ *
+ * Relocate Barebox from its current location (generally in flash) to a new one
+ * (generally in DDR). This function will copy the Barebox binary & apply
+ * relocations as necessary, then jump to board_init_r in the new build of
+ * Barebox. As such, this function does not return.
+ */
+void relocate_code(void *fdt, u32 fdt_size, u32 ram_size)
+{
+	unsigned long addr, length, bss_len;
+	u32 relocaddr, new_stack;
+	uint8_t *buf, *bss_start;
+	unsigned int type;
+	long off;
+
+	length = barebox_image_size + MAX_BSS_SIZE;
+	relocaddr = ALIGN_DOWN(ram_size - barebox_image_size, SZ_64K);
+	relocaddr = KSEG0ADDR(relocaddr);
+	new_stack = relocaddr - MALLOC_SIZE - 16;
+
+	/*
+	 * Ensure that we're relocating by an offset which is a multiple of
+	 * 64KiB, ie. doesn't change the least significant 16 bits of any
+	 * addresses. This allows us to discard R_MIPS_LO16 relocs, saving
+	 * space in the Barebox binary & complexity in handling them.
+	 */
+	off = relocaddr - (unsigned long)__image_start;
+	if (off & 0xffff)
+		panic("Mis-aligned relocation\n");
+
+	/* Copy Barebox to RAM */
+	memcpy((void *)relocaddr, __image_start, length);
+
+	/* Now apply relocations to the copy in RAM */
+	buf = __rel_start;
+	addr = relocaddr;
+	while (true) {
+		type = read_uint(&buf);
+		if (type == R_MIPS_NONE)
+			break;
+
+		addr += read_uint(&buf) << 2;
+		apply_reloc(type, (void *)addr, off);
+	}
+
+	/* Ensure the icache is coherent */
+	flush_cache_all();
+
+	/* Clear the .bss section */
+	bss_start = (uint8_t *)((unsigned long)__bss_start + off);
+	bss_len = (unsigned long)&__bss_stop - (unsigned long)__bss_start;
+	memset(bss_start, 0, bss_len);
+
+	 __asm__ __volatile__ (
+			"move	$a0, %0\n"
+		"	move	$a1, %1\n"
+		"	move	$31, $0\n"
+		"	move	$sp, %2\n"
+		"	jr	%3\n"
+		: /* no outputs */
+		: "r"(fdt),
+		  "r"(fdt_size),
+		  "r"(new_stack),
+		  "r"((unsigned long)main_entry + off));
+
+	/* Since we jumped to the new Barebox above, we won't get here */
+	unreachable();
+}
diff --git a/arch/mips/lib/sections.c b/arch/mips/lib/sections.c
new file mode 100644
index 0000000000..66d559f94a
--- /dev/null
+++ b/arch/mips/lib/sections.c
@@ -0,0 +1,9 @@
+#include <common.h>
+#include <asm/sections.h>
+#include <linux/types.h>
+
+char _text[0] __attribute__((section("._text")));
+char __bss_start[0] __attribute__((section(".__bss_start")));
+char __bss_stop[0] __attribute__((section(".__bss_stop")));
+char __image_start[0] __attribute__((section(".__image_start")));
+char __image_end[0] __attribute__((section(".__image_end")));