[PATCH v2 0/2] ARM: Use udiv/sdiv for __aeabi_{u}idiv library functions

[PATCH v2 0/2] ARM: Use udiv/sdiv for __aeabi_{u}idiv library functions

[Stephen Boyd]

This is a respin of a patch series from about a year ago[1]. I realized
that we already had most of the code in recordmcount to figure out
where we make calls to particular functions, so recording where
we make calls to the integer division functions should be easy enough
to add support for using the same design. Looking back on the thread
it seems like Mans was thinking along the same lines, although it wasn't
obvious to me back then or even over the last few days when I wrote this.

This series copies and reworks recordmcount to record the locations of the
calls to the library integer division functions on ARM builds, and puts those
locations into a table that we use to patch instructions at boot. The first
patch adds the recorduidiv program, and the second patch implements the
runtime patching for modules and kernel code. The module part hooks into
the relocation patching code we already have.

The discussion surrounding adding ARMv7VE so that this patchset isn't
as necessary is still on going, so I'm just sending out these patches for
now. Assuming we can come to a conclusion on how to implement ARMv7VE
I'll finish up those patches.

Comments/feedback appreciated.

Changes from v1:
 * Add suport for PJ4 udiv/sdiv mrc opcodes
 * Create a new program for recording uidiv instead of modifying recordmcount

[1] http://lkml.kernel.org/r/1383951632-6090-1-git-send-email-sboyd@codeaurora.org

Cc: Nicolas Pitre <nico@fluxnic.net>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Måns Rullgård <mans@mansr.com>
Cc: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
Cc: Michal Marek <mmarek@suse.com>
Cc: Russell King - ARM Linux <linux@arm.linux.org.uk>

Stephen Boyd (2):
  scripts: Add a recorduidiv program
  ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

 arch/arm/Kconfig               |  14 +
 arch/arm/include/asm/cputype.h |   8 +-
 arch/arm/include/asm/setup.h   |   3 +
 arch/arm/kernel/module.c       |  40 +++
 arch/arm/kernel/setup.c        |  68 ++++
 arch/arm/kernel/vmlinux.lds.S  |  13 +
 scripts/Makefile               |   1 +
 scripts/Makefile.build         |  17 +-
 scripts/recorduidiv.c          | 745 +++++++++++++++++++++++++++++++++++++++++
 9 files changed, 906 insertions(+), 3 deletions(-)
 create mode 100644 scripts/recorduidiv.c

-- 
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum,
a Linux Foundation Collaborative Project

[PATCH v2 1/2] scripts: Add a recorduidiv program

[Stephen Boyd]

The ARM compiler inserts calls to __aeabi_uidiv() and
__aeabi_idiv() when it needs to perform division on signed and
unsigned integers. If a processor has support for the udiv and
sdiv division instructions the calls to these support routines
can be replaced with those instructions. Therefore, record the
location of calls to these library functions into two sections
(one for udiv and one for sdiv) similar to how we trace calls to
mcount. When the kernel boots up it will check to see if the
processor supports the instructions and then patch the call sites
with the instruction.

Cc: Nicolas Pitre <nico@fluxnic.net>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Måns Rullgård <mans@mansr.com>
Cc: Michal Marek <mmarek@suse.com>
Signed-off-by: Stephen Boyd <sboyd@codeaurora.org>
---
 scripts/Makefile       |   1 +
 scripts/Makefile.build |  17 +-
 scripts/recorduidiv.c  | 745 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 761 insertions(+), 2 deletions(-)
 create mode 100644 scripts/recorduidiv.c

diff --git a/scripts/Makefile b/scripts/Makefile
index fd0d53d4a234..26b9ebd8be31 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -15,6 +15,7 @@ hostprogs-$(CONFIG_KALLSYMS)     += kallsyms
 hostprogs-$(CONFIG_LOGO)         += pnmtologo
 hostprogs-$(CONFIG_VT)           += conmakehash
 hostprogs-$(BUILD_C_RECORDMCOUNT) += recordmcount
+hostprogs-$(CONFIG_ARM_PATCH_UIDIV) += recorduidiv
 hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable
 hostprogs-$(CONFIG_ASN1)	 += asn1_compiler
 hostprogs-$(CONFIG_MODULE_SIG)	 += sign-file
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index 01df30af4d4a..142e5db29d3b 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -241,12 +241,25 @@ cmd_record_mcount =						\
 	fi;
 endif
 
+ifdef CONFIG_ARM_PATCH_UIDIV
+# Due to recursion, we must skip empty.o.
+# The empty.o file is created in the make process in order to determine
+#  the target endianness and word size. It is made before all other C
+#  files, including recorduidiv.
+cmd_record_uidiv =					\
+	if [ $(@) != "scripts/mod/empty.o" ]; then	\
+		$(objtree)/scripts/recorduidiv "$(@)";	\
+	fi;
+recorduidiv_source := $(srctree)/scripts/recorduidiv.c
+endif
+
 define rule_cc_o_c
 	$(call echo-cmd,checksrc) $(cmd_checksrc)			  \
 	$(call echo-cmd,cc_o_c) $(cmd_cc_o_c);				  \
 	$(cmd_modversions)						  \
 	$(call echo-cmd,record_mcount)					  \
 	$(cmd_record_mcount)						  \
+	$(call echo-cmd,record_uidiv) $(cmd_record_uidiv)		  \
 	scripts/basic/fixdep $(depfile) $@ '$(call make-cmd,cc_o_c)' >    \
 	                                              $(dot-target).tmp;  \
 	rm -f $(depfile);						  \
@@ -254,13 +267,13 @@ define rule_cc_o_c
 endef
 
 # Built-in and composite module parts
-$(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
+$(obj)/%.o: $(src)/%.c $(recordmcount_source) $(recorduidiv_source) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 
 # Single-part modules are special since we need to mark them in $(MODVERDIR)
 
-$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
+$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) $(recorduidiv_source) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 	@{ echo $(@:.o=.ko); echo $@; } > $(MODVERDIR)/$(@F:.o=.mod)
diff --git a/scripts/recorduidiv.c b/scripts/recorduidiv.c
new file mode 100644
index 000000000000..a2af5c46cb6d
--- /dev/null
+++ b/scripts/recorduidiv.c
@@ -0,0 +1,745 @@
+/*
+ * recorduidiv.c: construct a table of the locations of calls to '__aeabi_uidiv'
+ * and '__aeabi_idiv' so that the kernel can replace them with idiv and sdiv
+ * instructions.
+ *
+ * Copyright 2009 John F. Reiser <jreiser@BitWagon.com>.  All rights reserved.
+ * Licensed under the GNU General Public License, version 2 (GPLv2).
+ *
+ * Restructured to fit Linux format, as well as other updates:
+ *  Copyright 2010 Steven Rostedt <srostedt@redhat.com>, Red Hat Inc.
+ *
+ * Copyright (c) 2015 The Linux Foundation. All rights reserved.
+ */
+
+/*
+ * Strategy: alter the .o file in-place.
+ *
+ * Append a new STRTAB that has the new section names, followed by a new array
+ * ElfXX_Shdr[] that has the new section headers, followed by the section
+ * contents for __udiv_loc and __idiv_loc and their relocations. The old
+ * shstrtab strings, and the old ElfXX_Shdr[] array, remain as "garbage"
+ * (commonly, a couple kilobytes.) Subsequent processing by /bin/ld (or the
+ * kernel module loader) will ignore the garbage regions, because they are not
+ * designated by the new .e_shoff nor the new ElfXX_Shdr[].  [In order to
+ * remove the garbage, then use "ld -r" to create a new file that omits the
+ * garbage.]
+ */
+
+#include <sys/types.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <elf.h>
+#include <fcntl.h>
+#include <setjmp.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+# define _align			3u
+# define _size			4
+
+#ifndef R_ARM_CALL
+#define R_ARM_CALL		28
+#endif
+
+#ifndef R_ARM_JUMP24
+#define R_ARM_JUMP24		29
+#endif
+
+static int fd_map;	/* File descriptor for file being modified. */
+static int mmap_failed; /* Boolean flag. */
+static void *ehdr_curr; /* current ElfXX_Ehdr *  for resource cleanup */
+static struct stat sb;	/* Remember .st_size, etc. */
+static jmp_buf jmpenv;	/* setjmp/longjmp per-file error escape */
+
+/* setjmp() return values */
+enum {
+	SJ_SETJMP = 0,  /* hardwired first return */
+	SJ_FAIL,
+	SJ_SUCCEED
+};
+
+/* Per-file resource cleanup when multiple files. */
+static void
+cleanup(void)
+{
+	if (!mmap_failed)
+		munmap(ehdr_curr, sb.st_size);
+	else
+		free(ehdr_curr);
+	close(fd_map);
+}
+
+static void __attribute__((noreturn))
+fail_file(void)
+{
+	cleanup();
+	longjmp(jmpenv, SJ_FAIL);
+}
+
+static void __attribute__((noreturn))
+succeed_file(void)
+{
+	cleanup();
+	longjmp(jmpenv, SJ_SUCCEED);
+}
+
+/* ulseek, uread, ...:  Check return value for errors. */
+
+static off_t
+ulseek(int const fd, off_t const offset, int const whence)
+{
+	off_t const w = lseek(fd, offset, whence);
+	if (w == (off_t)-1) {
+		perror("lseek");
+		fail_file();
+	}
+	return w;
+}
+
+static size_t
+uread(int const fd, void *const buf, size_t const count)
+{
+	size_t const n = read(fd, buf, count);
+	if (n != count) {
+		perror("read");
+		fail_file();
+	}
+	return n;
+}
+
+static size_t
+uwrite(int const fd, void const *const buf, size_t const count)
+{
+	size_t const n = write(fd, buf, count);
+	if (n != count) {
+		perror("write");
+		fail_file();
+	}
+	return n;
+}
+
+static void *
+umalloc(size_t size)
+{
+	void *const addr = malloc(size);
+	if (addr == 0) {
+		fprintf(stderr, "malloc failed: %zu bytes\n", size);
+		fail_file();
+	}
+	return addr;
+}
+
+/*
+ * Get the whole file as a programming convenience in order to avoid
+ * malloc+lseek+read+free of many pieces.  If successful, then mmap
+ * avoids copying unused pieces; else just read the whole file.
+ * Open for both read and write; new info will be appended to the file.
+ * Use MAP_PRIVATE so that a few changes to the in-memory ElfXX_Ehdr
+ * do not propagate to the file until an explicit overwrite at the last.
+ * This preserves most aspects of consistency (all except .st_size)
+ * for simultaneous readers of the file while we are appending to it.
+ * However, multiple writers still are bad.  We choose not to use
+ * locking because it is expensive and the use case of kernel build
+ * makes multiple writers unlikely.
+ */
+static void *mmap_file(char const *fname)
+{
+	void *addr;
+
+	fd_map = open(fname, O_RDWR);
+	if (fd_map < 0 || fstat(fd_map, &sb) < 0) {
+		perror(fname);
+		fail_file();
+	}
+	if (!S_ISREG(sb.st_mode)) {
+		fprintf(stderr, "not a regular file: %s\n", fname);
+		fail_file();
+	}
+	addr = mmap(0, sb.st_size, PROT_READ|PROT_WRITE, MAP_PRIVATE,
+		    fd_map, 0);
+	mmap_failed = 0;
+	if (addr == MAP_FAILED) {
+		mmap_failed = 1;
+		addr = umalloc(sb.st_size);
+		uread(fd_map, addr, sb.st_size);
+	}
+	return addr;
+}
+
+/* w8rev, w8nat, ...: Handle endianness. */
+
+static uint64_t w8rev(uint64_t const x)
+{
+	return   ((0xff & (x >> (0 * 8))) << (7 * 8))
+	       | ((0xff & (x >> (1 * 8))) << (6 * 8))
+	       | ((0xff & (x >> (2 * 8))) << (5 * 8))
+	       | ((0xff & (x >> (3 * 8))) << (4 * 8))
+	       | ((0xff & (x >> (4 * 8))) << (3 * 8))
+	       | ((0xff & (x >> (5 * 8))) << (2 * 8))
+	       | ((0xff & (x >> (6 * 8))) << (1 * 8))
+	       | ((0xff & (x >> (7 * 8))) << (0 * 8));
+}
+
+static uint32_t w4rev(uint32_t const x)
+{
+	return   ((0xff & (x >> (0 * 8))) << (3 * 8))
+	       | ((0xff & (x >> (1 * 8))) << (2 * 8))
+	       | ((0xff & (x >> (2 * 8))) << (1 * 8))
+	       | ((0xff & (x >> (3 * 8))) << (0 * 8));
+}
+
+static uint32_t w2rev(uint16_t const x)
+{
+	return   ((0xff & (x >> (0 * 8))) << (1 * 8))
+	       | ((0xff & (x >> (1 * 8))) << (0 * 8));
+}
+
+static uint64_t w8nat(uint64_t const x)
+{
+	return x;
+}
+
+static uint32_t w4nat(uint32_t const x)
+{
+	return x;
+}
+
+static uint32_t w2nat(uint16_t const x)
+{
+	return x;
+}
+
+static uint64_t (*w8)(uint64_t);
+static uint32_t (*w)(uint32_t);
+static uint32_t (*w2)(uint16_t);
+
+/* Names of the sections that could contain calls to __aeabi_{u}idiv() */
+static int is_valid_section_name(char const *const txtname)
+{
+	return strcmp(".text",           txtname) == 0 ||
+		strcmp(".ref.text",      txtname) == 0 ||
+		strcmp(".sched.text",    txtname) == 0 ||
+		strcmp(".spinlock.text", txtname) == 0 ||
+		strcmp(".irqentry.text", txtname) == 0 ||
+		strcmp(".kprobes.text",  txtname) == 0 ||
+		strcmp(".text.unlikely", txtname) == 0 ||
+		strcmp(".init.text",     txtname) == 0;
+}
+
+static uint32_t Elf32_r_sym(Elf32_Rel const *rp)
+{
+	return ELF32_R_SYM(w(rp->r_info));
+}
+
+static void append_section(uint32_t const *const mloc0,
+			   uint32_t const *const mlocp,
+			   Elf32_Rel const *const mrel0,
+			   Elf32_Rel const *const mrelp,
+			   char const *name,
+			   unsigned int const rel_entsize,
+			   unsigned int const symsec_sh_link,
+			   uint32_t *name_offp,
+			   uint32_t *tp,
+			   unsigned *shnump
+		)
+{
+	Elf32_Shdr mcsec;
+	uint32_t name_off = *name_offp;
+	uint32_t t = *tp;
+	uint32_t loc_diff = (void *)mlocp - (void *)mloc0;
+	uint32_t rel_diff = (void *)mrelp - (void *)mrel0;
+	unsigned shnum = *shnump;
+
+	mcsec.sh_name = w((sizeof(Elf32_Rela) == rel_entsize) + strlen(".rel")
+		+ name_off);
+	mcsec.sh_type = w(SHT_PROGBITS);
+	mcsec.sh_flags = w(SHF_ALLOC);
+	mcsec.sh_addr = 0;
+	mcsec.sh_offset = w(t);
+	mcsec.sh_size = w(loc_diff);
+	mcsec.sh_link = 0;
+	mcsec.sh_info = 0;
+	mcsec.sh_addralign = w(_size);
+	mcsec.sh_entsize = w(_size);
+	uwrite(fd_map, &mcsec, sizeof(mcsec));
+	t += loc_diff;
+
+	mcsec.sh_name = w(name_off);
+	mcsec.sh_type = (sizeof(Elf32_Rela) == rel_entsize)
+		? w(SHT_RELA)
+		: w(SHT_REL);
+	mcsec.sh_flags = 0;
+	mcsec.sh_addr = 0;
+	mcsec.sh_offset = w(t);
+	mcsec.sh_size   = w(rel_diff);
+	mcsec.sh_link = w(symsec_sh_link);
+	mcsec.sh_info = w(shnum);
+	mcsec.sh_addralign = w(_size);
+	mcsec.sh_entsize = w(rel_entsize);
+	uwrite(fd_map, &mcsec, sizeof(mcsec));
+	t += rel_diff;
+
+	shnum += 2;
+	name_off += strlen(name) + 1;
+
+	*tp = t;
+	*shnump = shnum;
+	*name_offp = name_off;
+}
+
+/*
+ * Append the new shstrtab, Elf32_Shdr[], __{udiv,idiv}_loc and their
+ * relocations.
+ */
+static void append_func(Elf32_Ehdr *const ehdr,
+			Elf32_Shdr *const shstr,
+			uint32_t const *const mloc0_u,
+			uint32_t const *const mlocp_u,
+			Elf32_Rel const *const mrel0_u,
+			Elf32_Rel const *const mrelp_u,
+			uint32_t const *const mloc0_i,
+			uint32_t const *const mlocp_i,
+			Elf32_Rel const *const mrel0_i,
+			Elf32_Rel const *const mrelp_i,
+			unsigned int const rel_entsize,
+			unsigned int const symsec_sh_link)
+{
+	/* Begin constructing output file */
+	char const *udiv_name = (sizeof(Elf32_Rela) == rel_entsize)
+		? ".rela__udiv_loc"
+		:  ".rel__udiv_loc";
+	char const *idiv_name = (sizeof(Elf32_Rela) == rel_entsize)
+		? ".rela__idiv_loc"
+		:  ".rel__idiv_loc";
+	unsigned old_shnum = w2(ehdr->e_shnum);
+	uint32_t const old_shoff = w(ehdr->e_shoff);
+	uint32_t const old_shstr_sh_size   = w(shstr->sh_size);
+	uint32_t const old_shstr_sh_offset = w(shstr->sh_offset);
+	uint32_t new_e_shoff;
+	uint32_t t = w(shstr->sh_size);
+	uint32_t name_off = old_shstr_sh_size;
+	int udiv = 0, idiv = 0;
+	int num_sections;
+
+	if (mlocp_u != mloc0_u) {
+		t += 1 + strlen(udiv_name);
+		udiv = 1;
+	}
+	if (mlocp_i != mloc0_i) {
+		t += 1 + strlen(idiv_name);
+		idiv = 1;
+	}
+	num_sections = (udiv * 2) + (idiv * 2);
+
+	shstr->sh_size = w(t);
+	shstr->sh_offset = w(sb.st_size);
+	t += sb.st_size;
+	t += (_align & -t);  /* word-byte align */
+	new_e_shoff = t;
+
+	/* body for new shstrtab */
+	ulseek(fd_map, sb.st_size, SEEK_SET);
+	uwrite(fd_map, old_shstr_sh_offset + (void *)ehdr, name_off);
+	if (udiv)
+		uwrite(fd_map, udiv_name, 1 + strlen(udiv_name));
+	if (idiv)
+		uwrite(fd_map, idiv_name, 1 + strlen(idiv_name));
+
+	/* old(modified) Elf32_Shdr table, word-byte aligned */
+	ulseek(fd_map, t, SEEK_SET);
+	t += sizeof(Elf32_Shdr) * old_shnum;
+	uwrite(fd_map, old_shoff + (void *)ehdr,
+	       sizeof(Elf32_Shdr) * old_shnum);
+
+	t += num_sections * sizeof(Elf32_Shdr);
+
+	/* new sections __udiv_loc and .rel__udiv_loc */
+	if (udiv)
+		append_section(mloc0_u, mlocp_u, mrel0_u, mrelp_u, udiv_name,
+			       rel_entsize, symsec_sh_link, &name_off, &t,
+			       &old_shnum);
+
+	/* new sections __idiv_loc and .rel__idiv_loc */
+	if (idiv)
+		append_section(mloc0_i, mlocp_i, mrel0_i, mrelp_i, idiv_name,
+			       rel_entsize, symsec_sh_link, &name_off, &t,
+			       &old_shnum);
+
+	if (udiv) {
+		uwrite(fd_map, mloc0_u, (void *)mlocp_u - (void *)mloc0_u);
+		uwrite(fd_map, mrel0_u, (void *)mrelp_u - (void *)mrel0_u);
+	}
+	if (idiv) {
+		uwrite(fd_map, mloc0_i, (void *)mlocp_i - (void *)mloc0_i);
+		uwrite(fd_map, mrel0_i, (void *)mrelp_i - (void *)mrel0_i);
+	}
+
+	ehdr->e_shoff = w(new_e_shoff);
+	ehdr->e_shnum = w2(num_sections + w2(ehdr->e_shnum));
+	ulseek(fd_map, 0, SEEK_SET);
+	uwrite(fd_map, ehdr, sizeof(*ehdr));
+}
+
+static unsigned get_sym(Elf32_Sym const *const sym0,
+			      Elf32_Rel const *relp,
+			      char const *const str0, const char *find)
+{
+	unsigned sym = 0;
+	Elf32_Sym const *const symp = &sym0[Elf32_r_sym(relp)];
+	char const *symname = &str0[w(symp->st_name)];
+
+	if (strcmp(find, symname) == 0)
+		sym = Elf32_r_sym(relp);
+
+	return sym;
+}
+
+static void get_sym_str_and_relp(Elf32_Shdr const *const relhdr,
+				 Elf32_Ehdr const *const ehdr,
+				 Elf32_Sym const **sym0,
+				 char const **str0,
+				 Elf32_Rel const **relp)
+{
+	Elf32_Shdr *const shdr0 = (Elf32_Shdr *)(w(ehdr->e_shoff)
+		+ (void *)ehdr);
+	unsigned const symsec_sh_link = w(relhdr->sh_link);
+	Elf32_Shdr const *const symsec = &shdr0[symsec_sh_link];
+	Elf32_Shdr const *const strsec = &shdr0[w(symsec->sh_link)];
+	Elf32_Rel const *const rel0 = (Elf32_Rel const *)(w(relhdr->sh_offset)
+		+ (void *)ehdr);
+
+	*sym0 = (Elf32_Sym const *)(w(symsec->sh_offset)
+				  + (void *)ehdr);
+
+	*str0 = (char const *)(w(strsec->sh_offset)
+			       + (void *)ehdr);
+
+	*relp = rel0;
+}
+
+static void add_relocation(Elf32_Rel const *relp, uint32_t *mloc0, uint32_t **mlocpp,
+			   uint32_t const recval, unsigned const recsym,
+			   Elf32_Rel **const mrelpp, unsigned offbase,
+			   unsigned rel_entsize)
+{
+	uint32_t *mlocp = *mlocpp;
+	Elf32_Rel *mrelp = *mrelpp;
+	uint32_t const addend = w(w(relp->r_offset) - recval);
+	mrelp->r_offset = w(offbase + ((void *)mlocp - (void *)mloc0));
+	mrelp->r_info = w(ELF32_R_INFO(recsym, R_ARM_ABS32));
+	if (rel_entsize == sizeof(Elf32_Rela)) {
+		((Elf32_Rela *)mrelp)->r_addend = addend;
+		*mlocp++ = 0;
+	} else
+		*mlocp++ = addend;
+
+	*mlocpp = mlocp;
+	*mrelpp = (Elf32_Rel *)(rel_entsize + (void *)mrelp);
+}
+
+/*
+ * Look at the relocations in order to find the calls to __aeabi_{u}idiv.
+ * Accumulate the section offsets that are found, and their relocation info,
+ * onto the end of the existing arrays.
+ */
+static void sift_relocations(uint32_t **mlocpp_u, uint32_t *mloc_base_u,
+			     Elf32_Rel **const mrelpp_u,
+			     uint32_t **mlocpp_i,
+			     uint32_t *mloc_base_i,
+			     Elf32_Rel **const mrelpp_i,
+			     Elf32_Shdr const *const relhdr,
+			     Elf32_Ehdr const *const ehdr,
+			     unsigned const recsym, uint32_t const recval)
+{
+	uint32_t *mlocp_u = *mlocpp_u;
+	unsigned const offbase_u = (void *)mlocp_u - (void *)mloc_base_u;
+	uint32_t *const mloc0_u = mlocp_u;
+	Elf32_Rel *mrelp_u = *mrelpp_u;
+	uint32_t *mlocp_i = *mlocpp_i;
+	unsigned const offbase_i = (void *)mlocp_i - (void *)mloc_base_i;
+	uint32_t *const mloc0_i = mlocp_i;
+	Elf32_Rel *mrelp_i = *mrelpp_i;
+	Elf32_Sym const *sym0;
+	char const *str0;
+	Elf32_Rel const *relp;
+	unsigned rel_entsize = w(relhdr->sh_entsize);
+	unsigned const nrel = w(relhdr->sh_size) / rel_entsize;
+	unsigned udiv_sym = 0, idiv_sym = 0;
+	unsigned t;
+
+	get_sym_str_and_relp(relhdr, ehdr, &sym0, &str0, &relp);
+
+	for (t = nrel; t; --t) {
+		if (!udiv_sym)
+			udiv_sym = get_sym(sym0, relp, str0,
+					       "__aeabi_uidiv");
+		if (!idiv_sym)
+			idiv_sym = get_sym(sym0, relp, str0,
+						 "__aeabi_idiv");
+
+		switch (relp->r_info & 0xff) {
+		case R_ARM_PC24:
+		case R_ARM_CALL:
+		case R_ARM_JUMP24:
+			if (udiv_sym == Elf32_r_sym(relp)) {
+				add_relocation(relp, mloc0_u, &mlocp_u, recval,
+					       recsym, &mrelp_u, offbase_u,
+					       rel_entsize);
+			} else if (idiv_sym == Elf32_r_sym(relp)) {
+				add_relocation(relp, mloc0_i, &mlocp_i, recval,
+					       recsym, &mrelp_i, offbase_i,
+					       rel_entsize);
+			}
+		}
+
+		relp = (Elf32_Rel const *)(rel_entsize + (void *)relp);
+	}
+	*mrelpp_i = mrelp_i;
+	*mrelpp_u = mrelp_u;
+	*mlocpp_i = mlocp_i;
+	*mlocpp_u = mlocp_u;
+}
+
+/*
+ * Find a symbol in the given section, to be used as the base for relocating
+ * the table of offsets of calls.  A local or global symbol suffices,
+ * but avoid a Weak symbol because it may be overridden; the change in value
+ * would invalidate the relocations of the offsets of the calls.
+ * Often the found symbol will be the unnamed local symbol generated by
+ * GNU 'as' for the start of each section.  For example:
+ *    Num:    Value  Size Type    Bind   Vis      Ndx Name
+ *      2: 00000000     0 SECTION LOCAL  DEFAULT    1
+ */
+static unsigned find_secsym_ndx(unsigned const txtndx,
+				char const *const txtname,
+				uint32_t *const recvalp,
+				Elf32_Shdr const *const symhdr,
+				Elf32_Ehdr const *const ehdr)
+{
+	Elf32_Sym const *const sym0 = (Elf32_Sym const *)(w(symhdr->sh_offset)
+		+ (void *)ehdr);
+	unsigned const nsym = w(symhdr->sh_size) / w(symhdr->sh_entsize);
+	Elf32_Sym const *symp;
+	unsigned t;
+
+	for (symp = sym0, t = nsym; t; --t, ++symp) {
+		unsigned int const st_bind = ELF32_ST_BIND(symp->st_info);
+
+		if (txtndx == w2(symp->st_shndx)
+			/* avoid STB_WEAK */
+		    && (STB_LOCAL == st_bind || STB_GLOBAL == st_bind)) {
+			/* function symbols on ARM have quirks, avoid them */
+			if (ELF32_ST_TYPE(symp->st_info) == STT_FUNC)
+				continue;
+
+			*recvalp = w(symp->st_value);
+			return symp - sym0;
+		}
+	}
+	fprintf(stderr, "Cannot find symbol for section %d: %s.\n",
+		txtndx, txtname);
+	fail_file();
+}
+
+
+/* Evade ISO C restriction: no declaration after statement in has_rel. */
+static char const *
+__has_rel(Elf32_Shdr const *const relhdr,  /* is SHT_REL or SHT_RELA */
+	  Elf32_Shdr const *const shdr0,
+	  char const *const shstrtab,
+	  char const *const fname)
+{
+	/* .sh_info depends on .sh_type == SHT_REL[,A] */
+	Elf32_Shdr const *const txthdr = &shdr0[w(relhdr->sh_info)];
+	char const *const txtname = &shstrtab[w(txthdr->sh_name)];
+
+	if (strcmp("__idiv_loc", txtname) == 0 ||
+	    strcmp("__udiv_loc", txtname) == 0)
+		succeed_file();
+	if (w(txthdr->sh_type) != SHT_PROGBITS ||
+	    !(w(txthdr->sh_flags) & SHF_EXECINSTR))
+		return NULL;
+	return txtname;
+}
+
+static char const *has_rel(Elf32_Shdr const *const relhdr,
+				  Elf32_Shdr const *const shdr0,
+				  char const *const shstrtab,
+				  char const *const fname)
+{
+	if (w(relhdr->sh_type) != SHT_REL && w(relhdr->sh_type) != SHT_RELA)
+		return NULL;
+	return __has_rel(relhdr, shdr0, shstrtab, fname);
+}
+
+
+static unsigned tot_relsize(Elf32_Shdr const *const shdr0,
+			    unsigned nhdr,
+			    const char *const shstrtab,
+			    const char *const fname)
+{
+	unsigned totrelsz = 0;
+	Elf32_Shdr const *shdrp = shdr0;
+	char const *txtname;
+
+	for (; nhdr; --nhdr, ++shdrp) {
+		txtname = has_rel(shdrp, shdr0, shstrtab, fname);
+		if (txtname && is_valid_section_name(txtname))
+			totrelsz += w(shdrp->sh_size);
+	}
+	return totrelsz;
+}
+
+
+/* Overall supervision for Elf32 ET_REL file. */
+static void
+do_func(Elf32_Ehdr *const ehdr, char const *const fname)
+{
+	Elf32_Shdr *const shdr0 = (Elf32_Shdr *)(w(ehdr->e_shoff)
+		+ (void *)ehdr);
+	unsigned const nhdr = w2(ehdr->e_shnum);
+	Elf32_Shdr *const shstr = &shdr0[w2(ehdr->e_shstrndx)];
+	char const *const shstrtab = (char const *)(w(shstr->sh_offset)
+		+ (void *)ehdr);
+
+	Elf32_Shdr const *relhdr;
+	unsigned k;
+
+	/* Upper bound on space: assume all relevant relocs are valid. */
+	unsigned const totrelsz = tot_relsize(shdr0, nhdr, shstrtab, fname);
+	Elf32_Rel *const mrel0_u = umalloc(totrelsz);
+	Elf32_Rel *      mrelp_u = mrel0_u;
+
+	/* 2*sizeof(address) <= sizeof(Elf32_Rel) */
+	uint32_t *const mloc0_u = umalloc(totrelsz>>1);
+	uint32_t *      mlocp_u = mloc0_u;
+
+	Elf32_Rel *const mrel0_i = umalloc(totrelsz);
+	Elf32_Rel *      mrelp_i = mrel0_i;
+
+	/* 2*sizeof(address) <= sizeof(Elf32_Rel) */
+	uint32_t *const mloc0_i = umalloc(totrelsz>>1);
+	uint32_t *      mlocp_i = mloc0_i;
+
+	unsigned rel_entsize = 0;
+	unsigned symsec_sh_link = 0;
+
+	for (relhdr = shdr0, k = nhdr; k; --k, ++relhdr) {
+		char const *const txtname = has_rel(relhdr, shdr0, shstrtab,
+						    fname);
+		if (txtname && is_valid_section_name(txtname)) {
+			uint32_t recval = 0;
+			unsigned const recsym = find_secsym_ndx(
+				w(relhdr->sh_info), txtname, &recval,
+				&shdr0[symsec_sh_link = w(relhdr->sh_link)],
+				ehdr);
+
+			rel_entsize = w(relhdr->sh_entsize);
+			sift_relocations(&mlocp_u, mloc0_u, &mrelp_u,
+					&mlocp_i, mloc0_i, &mrelp_i,
+					relhdr, ehdr, recsym, recval);
+		}
+	}
+	if (mloc0_u != mlocp_u || mloc0_i != mlocp_i) {
+		append_func(ehdr, shstr, mloc0_u, mlocp_u, mrel0_u, mrelp_u,
+			    mloc0_i, mlocp_i, mrel0_i, mrelp_i,
+			    rel_entsize, symsec_sh_link);
+	}
+	free(mrel0_u);
+	free(mloc0_u);
+	free(mrel0_i);
+	free(mloc0_i);
+}
+
+static void
+do_file(char const *const fname)
+{
+	Elf32_Ehdr *const ehdr = mmap_file(fname);
+
+	ehdr_curr = ehdr;
+	w = w4nat;
+	w2 = w2nat;
+	w8 = w8nat;
+	switch (ehdr->e_ident[EI_DATA]) {
+		static unsigned int const endian = 1;
+	default:
+		fprintf(stderr, "unrecognized ELF data encoding %d: %s\n",
+			ehdr->e_ident[EI_DATA], fname);
+		fail_file();
+		break;
+	case ELFDATA2LSB:
+		if (*(unsigned char const *)&endian != 1) {
+			/* main() is big endian, file.o is little endian. */
+			w = w4rev;
+			w2 = w2rev;
+			w8 = w8rev;
+		}
+		break;
+	case ELFDATA2MSB:
+		if (*(unsigned char const *)&endian != 0) {
+			/* main() is little endian, file.o is big endian. */
+			w = w4rev;
+			w2 = w2rev;
+			w8 = w8rev;
+		}
+		break;
+	}  /* end switch */
+	if (memcmp(ELFMAG, ehdr->e_ident, SELFMAG) != 0
+	||  w2(ehdr->e_type) != ET_REL
+	||  ehdr->e_ident[EI_VERSION] != EV_CURRENT) {
+		fprintf(stderr, "unrecognized ET_REL file %s\n", fname);
+		fail_file();
+	}
+
+	if (w2(ehdr->e_ehsize) != sizeof(Elf32_Ehdr)
+	||  w2(ehdr->e_shentsize) != sizeof(Elf32_Shdr)) {
+		fprintf(stderr,
+			"unrecognized ET_REL file: %s\n", fname);
+		fail_file();
+	}
+	do_func(ehdr, fname);
+
+	cleanup();
+}
+
+int
+main(int argc, char *argv[])
+{
+	int n_error = 0;  /* gcc-4.3.0 false positive complaint */
+	int i;
+
+	if (argc < 2) {
+		fprintf(stderr, "usage: recorduidiv file.o...\n");
+		return 0;
+	}
+
+	/* Process each file in turn, allowing deep failure. */
+	for (i = 1; i < argc; i++) {
+		char *file = argv[i];
+		int const sjval = setjmp(jmpenv);
+
+		switch (sjval) {
+		default:
+			fprintf(stderr, "internal error: %s\n", file);
+			exit(1);
+			break;
+		case SJ_SETJMP:    /* normal sequence */
+			/* Avoid problems if early cleanup() */
+			fd_map = -1;
+			ehdr_curr = NULL;
+			mmap_failed = 1;
+			do_file(file);
+			break;
+		case SJ_FAIL:    /* error in do_file or below */
+			++n_error;
+			break;
+		case SJ_SUCCEED:    /* premature success */
+			/* do nothing */
+			break;
+		}  /* end switch */
+	}
+	return !!n_error;
+}
-- 
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum,
a Linux Foundation Collaborative Project

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Russell King - ARM Linux]

On Wed, Nov 25, 2015 at 01:51:03PM -0800, Stephen Boyd wrote:
> The ARM compiler inserts calls to __aeabi_uidiv() and
> __aeabi_idiv() when it needs to perform division on signed and
> unsigned integers. If a processor has support for the udiv and
> sdiv division instructions the calls to these support routines
> can be replaced with those instructions. Therefore, record the
> location of calls to these library functions into two sections
> (one for udiv and one for sdiv) similar to how we trace calls to
> mcount. When the kernel boots up it will check to see if the
> processor supports the instructions and then patch the call sites
> with the instruction.

Do we have any resolution on these programs which modify the object
files in-place, rather than breaking any hard-links which may be
present (eg, as a result of using ccache in hard-link mode) ?

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Michal Marek]

On 2015-11-26 00:47, Russell King - ARM Linux wrote:
> On Wed, Nov 25, 2015 at 01:51:03PM -0800, Stephen Boyd wrote:
>> The ARM compiler inserts calls to __aeabi_uidiv() and
>> __aeabi_idiv() when it needs to perform division on signed and
>> unsigned integers. If a processor has support for the udiv and
>> sdiv division instructions the calls to these support routines
>> can be replaced with those instructions. Therefore, record the
>> location of calls to these library functions into two sections
>> (one for udiv and one for sdiv) similar to how we trace calls to
>> mcount. When the kernel boots up it will check to see if the
>> processor supports the instructions and then patch the call sites
>> with the instruction.
> 
> Do we have any resolution on these programs which modify the object
> files in-place, rather than breaking any hard-links which may be
> present (eg, as a result of using ccache in hard-link mode) ?

Good point, but I do not think anybody is using CCACHE_HARDLINK with the
kernel. As the manpage says, it is going to confuse make, so the time
saved by ccache would be offset by make trying to recompile all *.c
files each time.

Michal

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Russell King - ARM Linux]

On Mon, Nov 30, 2015 at 04:11:16PM +0100, Michal Marek wrote:
> On 2015-11-26 00:47, Russell King - ARM Linux wrote:
> > On Wed, Nov 25, 2015 at 01:51:03PM -0800, Stephen Boyd wrote:
> >> The ARM compiler inserts calls to __aeabi_uidiv() and
> >> __aeabi_idiv() when it needs to perform division on signed and
> >> unsigned integers. If a processor has support for the udiv and
> >> sdiv division instructions the calls to these support routines
> >> can be replaced with those instructions. Therefore, record the
> >> location of calls to these library functions into two sections
> >> (one for udiv and one for sdiv) similar to how we trace calls to
> >> mcount. When the kernel boots up it will check to see if the
> >> processor supports the instructions and then patch the call sites
> >> with the instruction.
> > 
> > Do we have any resolution on these programs which modify the object
> > files in-place, rather than breaking any hard-links which may be
> > present (eg, as a result of using ccache in hard-link mode) ?
> 
> Good point, but I do not think anybody is using CCACHE_HARDLINK with the
> kernel.

That's wrong then, because I've been using it for a very long time with
my nightly builds. :)  Therefore, there is somebody!

> As the manpage says, it is going to confuse make, so the time
> saved by ccache would be offset by make trying to recompile all *.c
> files each time.

>From what I've noticed, it makes a big difference when running nightly
builds.  My nightly builds use O= and always build into an empty target
tree, so there are no old objects back-dated to confuse make.

Even if there were, make would spot that the object is older than the
source, and try to re-make the target again, at which point ccache
would re-hardlink the object after looking up the hashed preprocessed
source.

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Michal Marek]

On 2015-11-30 16:32, Russell King - ARM Linux wrote:
> On Mon, Nov 30, 2015 at 04:11:16PM +0100, Michal Marek wrote:
>> On 2015-11-26 00:47, Russell King - ARM Linux wrote:
>>> On Wed, Nov 25, 2015 at 01:51:03PM -0800, Stephen Boyd wrote:
>>>> The ARM compiler inserts calls to __aeabi_uidiv() and
>>>> __aeabi_idiv() when it needs to perform division on signed and
>>>> unsigned integers. If a processor has support for the udiv and
>>>> sdiv division instructions the calls to these support routines
>>>> can be replaced with those instructions. Therefore, record the
>>>> location of calls to these library functions into two sections
>>>> (one for udiv and one for sdiv) similar to how we trace calls to
>>>> mcount. When the kernel boots up it will check to see if the
>>>> processor supports the instructions and then patch the call sites
>>>> with the instruction.
>>>
>>> Do we have any resolution on these programs which modify the object
>>> files in-place, rather than breaking any hard-links which may be
>>> present (eg, as a result of using ccache in hard-link mode) ?
>>
>> Good point, but I do not think anybody is using CCACHE_HARDLINK with the
>> kernel.
> 
> That's wrong then, because I've been using it for a very long time with
> my nightly builds. :)  Therefore, there is somebody!

OK.


>> As the manpage says, it is going to confuse make, so the time
>> saved by ccache would be offset by make trying to recompile all *.c
>> files each time.
> 
> From what I've noticed, it makes a big difference when running nightly
> builds.  My nightly builds use O= and always build into an empty target
> tree, so there are no old objects back-dated to confuse make.
> 
> Even if there were, make would spot that the object is older than the
> source, and try to re-make the target again, at which point ccache
> would re-hardlink the object after looking up the hashed preprocessed
> source.

That's what I meant. If you do a second make in a freshly built tree, it
will recompile all the files again. It will all be cache hits, but each
of the will be lot slower than comparing two timestamps. But in
throwaway build trees you do not care, I haven't considered that...

Michal

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Michal Marek]

On 2015-11-30 16:40, Michal Marek wrote:
> On 2015-11-30 16:32, Russell King - ARM Linux wrote:
>> On Mon, Nov 30, 2015 at 04:11:16PM +0100, Michal Marek wrote:
>>> On 2015-11-26 00:47, Russell King - ARM Linux wrote:
>>>> Do we have any resolution on these programs which modify the object
>>>> files in-place, rather than breaking any hard-links which may be
>>>> present (eg, as a result of using ccache in hard-link mode) ?
>>>
>>> Good point, but I do not think anybody is using CCACHE_HARDLINK with the
>>> kernel.
>>
>> That's wrong then, because I've been using it for a very long time with
>> my nightly builds. :)  Therefore, there is somebody!
> 
> OK.

So, both recordmcount and the new recordudiv program are idempotent.
They check if the to-be-added section is already present and do nothing.
So the result is correct even with CCACHE_HARDLINK, just the
intermediate file might be incorrect. If this still is considered an
issue, I suggest clearing CCACHE_HARDLINK when using any of these
postprocessors, so as not to penalize other use cases.

The perl recordmcount does not modify the file in place.

Michal

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Russell King - ARM Linux]

On Tue, Dec 01, 2015 at 05:07:05PM +0100, Michal Marek wrote:
> On 2015-11-30 16:40, Michal Marek wrote:
> > On 2015-11-30 16:32, Russell King - ARM Linux wrote:
> >> On Mon, Nov 30, 2015 at 04:11:16PM +0100, Michal Marek wrote:
> >>> On 2015-11-26 00:47, Russell King - ARM Linux wrote:
> >>>> Do we have any resolution on these programs which modify the object
> >>>> files in-place, rather than breaking any hard-links which may be
> >>>> present (eg, as a result of using ccache in hard-link mode) ?
> >>>
> >>> Good point, but I do not think anybody is using CCACHE_HARDLINK with the
> >>> kernel.
> >>
> >> That's wrong then, because I've been using it for a very long time with
> >> my nightly builds. :)  Therefore, there is somebody!
> > 
> > OK.
> 
> So, both recordmcount and the new recordudiv program are idempotent.
> They check if the to-be-added section is already present and do nothing.

They hardly "do nothing", as the (eg) recordmcount plasters the build
log with warnings.  A solution to that would be to make recordmcount
silent if the section is already present.

> So the result is correct even with CCACHE_HARDLINK, just the
> intermediate file might be incorrect. If this still is considered an
> issue, I suggest clearing CCACHE_HARDLINK when using any of these
> postprocessors, so as not to penalize other use cases.

Another solution would be to have the top level make file unset the
CCACHE_HARDLINK environment variable if any of the options which enable
in-place editing of object files is enabled.  Looking at the ccache
code, the environment variable has to be deleted from the environment
to turn off the option - and I'm not sure whether make can delete
environment variables.  It certainly can override them, but I see
nothing in the info pages which suggests that environment variables
can be deleted by a makefile.

However, doing it outside of the kernel build system is likely error
prone especially as the kernel configuration options change and/or
their effect changes.

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Michal Marek]

On 2015-12-01 17:19, Russell King - ARM Linux wrote:
> On Tue, Dec 01, 2015 at 05:07:05PM +0100, Michal Marek wrote:
>> So, both recordmcount and the new recordudiv program are idempotent.
>> They check if the to-be-added section is already present and do nothing.
> 
> They hardly "do nothing", as the (eg) recordmcount plasters the build
> log with warnings.  A solution to that would be to make recordmcount
> silent if the section is already present.

Right, there is a warning. The recorduidiv program exits silently.


>> So the result is correct even with CCACHE_HARDLINK, just the
>> intermediate file might be incorrect. If this still is considered an
>> issue, I suggest clearing CCACHE_HARDLINK when using any of these
>> postprocessors, so as not to penalize other use cases.
> 
> Another solution would be to have the top level make file unset the
> CCACHE_HARDLINK environment variable if any of the options which enable
> in-place editing of object files is enabled.

This is what I meant, sorry for not being clear.


> Looking at the ccache
> code, the environment variable has to be deleted from the environment
> to turn off the option - and I'm not sure whether make can delete
> environment variables.  It certainly can override them, but I see
> nothing in the info pages which suggests that environment variables
> can be deleted by a makefile.

unexport CCACHE_HARDLINK

will do the trick.

Michal

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Steven Rostedt]

On Tue, 1 Dec 2015 16:19:44 +0000
Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:
 
> They hardly "do nothing", as the (eg) recordmcount plasters the build
> log with warnings.  A solution to that would be to make recordmcount
> silent if the section is already present.

Note, that warning found plenty of bugs when modifications of the build
system was being done and broke recordmcount.c. I really don't want to
silent it.

But for some reason, your build is causing lots of warnings and not for
others. Perhaps we can add a "SILENT_RECORDMCOUNT" environment variable
and have it set when something like CCACHE_HARDLINK or whatever is
causing it to trigger when we don't care.

-- Steve

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Russell King - ARM Linux]

On Tue, Dec 01, 2015 at 11:49:29AM -0500, Steven Rostedt wrote:
> On Tue, 1 Dec 2015 16:19:44 +0000
> Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:
>  
> > They hardly "do nothing", as the (eg) recordmcount plasters the build
> > log with warnings.  A solution to that would be to make recordmcount
> > silent if the section is already present.
> 
> Note, that warning found plenty of bugs when modifications of the build
> system was being done and broke recordmcount.c. I really don't want to
> silent it.
> 
> But for some reason, your build is causing lots of warnings and not for
> others. Perhaps we can add a "SILENT_RECORDMCOUNT" environment variable
> and have it set when something like CCACHE_HARDLINK or whatever is
> causing it to trigger when we don't care.

The case is:

Build 1 runs with CCACHE_HARDLINK enabled.
- Each object ccache creates will be stored in ccache, and hard linked
  into the throw-away object tree.
- recordmcount modifies in-place the object in the object tree, which
  also modifies the object in the ccache repository.

The throw-away object tree is thrown away, and a new tree is created,
and the build re-run.  It doesn't matter what CCACHE options are used,
the effect will now be the same:
- Each "hit" ccache object from the previous build will be linked or
  copied to the new throw-away object tree.
- recordmcount will be re-run on the object, which now contains the
  results of the previous recordmcount in-place modification.  This
  causes recordmcount to issue a warning.

There's two solutions to this: one is to disable CCACHE_HARDLINK for
all kernel builds which use in-place object modification.  The other
solution is to avoid in-place object modification, instead doing a
read-write-rename.

I think I ought to ask another question though, before we decide what
to do.  With recordmcount doing in-place object modification, what
happens if a SIGINT or similar is received half way through the
modification of an object?  I would hope that make would delete the
object and not leave it around.

Another suggestion - maybe recordmcount, which fstat()s the file,
should check the st_nlink before modifying the file, and error out
with a helpful error message telling people not to use hardlinks,
which would stop nasty surprises (and make it a rule that this should
be implemented as a general principle for good build behaviour) - iow,
something like this (untested):

 scripts/recordmcount.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/scripts/recordmcount.c b/scripts/recordmcount.c
index 698768bdc581..bb7589fd7392 100644
--- a/scripts/recordmcount.c
+++ b/scripts/recordmcount.c
@@ -203,6 +203,10 @@ static void *mmap_file(char const *fname)
 		fprintf(stderr, "not a regular file: %s\n", fname);
 		fail_file();
 	}
+	if (sb.st_nlink != 1) {
+		fprintf(stderr, "file is hard linked: %s\n", fname);
+		fail_file();
+	}
 	addr = mmap(0, sb.st_size, PROT_READ|PROT_WRITE, MAP_PRIVATE,
 		    fd_map, 0);
 	mmap_failed = 0;


-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Steven Rostedt]

On Tue, 1 Dec 2015 17:10:14 +0000
Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:

> Another suggestion - maybe recordmcount, which fstat()s the file,
> should check the st_nlink before modifying the file, and error out
> with a helpful error message telling people not to use hardlinks,
> which would stop nasty surprises (and make it a rule that this should
> be implemented as a general principle for good build behaviour) - iow,

Actually I like this solution the best.

> something like this (untested):

Can you test it to see if it gives you the error, otherwise I need to
set up a CCACHE_HARDLINK environment :-)

I guess another solution is to do a copy instead of modifying in place
if it detects the multiple hard link?

-- Steve


> 
>  scripts/recordmcount.c | 4 ++++
>  1 file changed, 4 insertions(+)
> 
> diff --git a/scripts/recordmcount.c b/scripts/recordmcount.c
> index 698768bdc581..bb7589fd7392 100644
> --- a/scripts/recordmcount.c
> +++ b/scripts/recordmcount.c
> @@ -203,6 +203,10 @@ static void *mmap_file(char const *fname)
>  		fprintf(stderr, "not a regular file: %s\n", fname);
>  		fail_file();
>  	}
> +	if (sb.st_nlink != 1) {
> +		fprintf(stderr, "file is hard linked: %s\n", fname);
> +		fail_file();
> +	}
>  	addr = mmap(0, sb.st_size, PROT_READ|PROT_WRITE, MAP_PRIVATE,
>  		    fd_map, 0);
>  	mmap_failed = 0;
> 
> 

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Russell King - ARM Linux]

On Tue, Dec 01, 2015 at 12:22:12PM -0500, Steven Rostedt wrote:
> On Tue, 1 Dec 2015 17:10:14 +0000
> Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:
> 
> > Another suggestion - maybe recordmcount, which fstat()s the file,
> > should check the st_nlink before modifying the file, and error out
> > with a helpful error message telling people not to use hardlinks,
> > which would stop nasty surprises (and make it a rule that this should
> > be implemented as a general principle for good build behaviour) - iow,
> 
> Actually I like this solution the best.
> 
> > something like this (untested):
> 
> Can you test it to see if it gives you the error, otherwise I need to
> set up a CCACHE_HARDLINK environment :-)

It does indeed:

  CC      init/do_mounts_initrd.o
file is hard linked: init/do_mounts_initrd.o
/home/rmk/git/linux-rmk/scripts/Makefile.build:258: recipe for target 'init/do_mounts_initrd.o' failed
make[2]: *** [init/do_mounts_initrd.o] Error 1

> I guess another solution is to do a copy instead of modifying in place
> if it detects the multiple hard link?

That would be the "transparent" solution.  If you think it's worth
persuing, I'll have a go at fixing recordmcount to do that.

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Michal Marek]

Dne 1.12.2015 v 19:16 Russell King - ARM Linux napsal(a):
> On Tue, Dec 01, 2015 at 12:22:12PM -0500, Steven Rostedt wrote:
>> I guess another solution is to do a copy instead of modifying in place
>> if it detects the multiple hard link?
> 
> That would be the "transparent" solution.  If you think it's worth
> persuing, I'll have a go at fixing recordmcount to do that.

But in terms of number of file copies, it would on par with disabling
CCACHE_HARDLINK from within the Makefile.

Michal

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Russell King - ARM Linux]

On Tue, Dec 01, 2015 at 06:16:43PM +0000, Russell King - ARM Linux wrote:
> On Tue, Dec 01, 2015 at 12:22:12PM -0500, Steven Rostedt wrote:
> > I guess another solution is to do a copy instead of modifying in place
> > if it detects the multiple hard link?
> 
> That would be the "transparent" solution.  If you think it's worth
> persuing, I'll have a go at fixing recordmcount to do that.

Well, copying the file is easy - I've tested this and the linker
appears happy with the result:

 scripts/recordmcount.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/scripts/recordmcount.c b/scripts/recordmcount.c
index 698768bdc581..91705ef30402 100644
--- a/scripts/recordmcount.c
+++ b/scripts/recordmcount.c
@@ -211,6 +211,20 @@ static void *mmap_file(char const *fname)
 		addr = umalloc(sb.st_size);
 		uread(fd_map, addr, sb.st_size);
 	}
+	if (sb.st_nlink != 1) {
+		/* file is hard-linked, break the hard link */
+		close(fd_map);
+		if (unlink(fname) < 0) {
+			perror(fname);
+			fail_file();
+		}
+		fd_map = open(fname, O_RDWR | O_CREAT, sb.st_mode);
+		if (fd_map < 0) {
+			perror(fname);
+			fail_file();
+		}
+		uwrite(fd_map, addr, sb.st_size);
+	}
 	return addr;
 }
 

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH v2 1/2] scripts: Add a recorduidiv program

[Steven Rostedt]

On Wed, 2 Dec 2015 10:23:39 +0000
Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:

> On Tue, Dec 01, 2015 at 06:16:43PM +0000, Russell King - ARM Linux wrote:
> > On Tue, Dec 01, 2015 at 12:22:12PM -0500, Steven Rostedt wrote:  
> > > I guess another solution is to do a copy instead of modifying in place
> > > if it detects the multiple hard link?  
> > 
> > That would be the "transparent" solution.  If you think it's worth
> > persuing, I'll have a go at fixing recordmcount to do that.  
> 
> Well, copying the file is easy - I've tested this and the linker
> appears happy with the result:

Want to make this into a proper patch and I'll start running it through
my tests?

-- Steve

> 
>  scripts/recordmcount.c | 14 ++++++++++++++
>  1 file changed, 14 insertions(+)
> 
> diff --git a/scripts/recordmcount.c b/scripts/recordmcount.c
> index 698768bdc581..91705ef30402 100644
> --- a/scripts/recordmcount.c
> +++ b/scripts/recordmcount.c
> @@ -211,6 +211,20 @@ static void *mmap_file(char const *fname)
>  		addr = umalloc(sb.st_size);
>  		uread(fd_map, addr, sb.st_size);
>  	}
> +	if (sb.st_nlink != 1) {
> +		/* file is hard-linked, break the hard link */
> +		close(fd_map);
> +		if (unlink(fname) < 0) {
> +			perror(fname);
> +			fail_file();
> +		}
> +		fd_map = open(fname, O_RDWR | O_CREAT, sb.st_mode);
> +		if (fd_map < 0) {
> +			perror(fname);
> +			fail_file();
> +		}
> +		uwrite(fd_map, addr, sb.st_size);
> +	}
>  	return addr;
>  }
>  
> 

Re: [PATCH] scripts: recordmcount: break hardlinks

[Steven Rostedt]

On Fri, 11 Dec 2015 12:09:03 +0000
Russell King <rmk+kernel@arm.linux.org.uk> wrote:

> recordmcount edits the file in-place, which can cause problems when
> using ccache in hardlink mode.  Arrange for recordmcount to break a
> hardlinked object.
> 
> Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
> ---
> Steven, sorry it took a while to get this out...

Should this be for stable, or is it fine to just add this to my 4.5
queue?

-- Steve

> 
>  scripts/recordmcount.c | 14 ++++++++++++++
>  1 file changed, 14 insertions(+)
> 
> diff --git a/scripts/recordmcount.c b/scripts/recordmcount.c
> index 698768bdc581..91705ef30402 100644
> --- a/scripts/recordmcount.c
> +++ b/scripts/recordmcount.c
> @@ -211,6 +211,20 @@ static void *mmap_file(char const *fname)
>  		addr = umalloc(sb.st_size);
>  		uread(fd_map, addr, sb.st_size);
>  	}
> +	if (sb.st_nlink != 1) {
> +		/* file is hard-linked, break the hard link */
> +		close(fd_map);
> +		if (unlink(fname) < 0) {
> +			perror(fname);
> +			fail_file();
> +		}
> +		fd_map = open(fname, O_RDWR | O_CREAT, sb.st_mode);
> +		if (fd_map < 0) {
> +			perror(fname);
> +			fail_file();
> +		}
> +		uwrite(fd_map, addr, sb.st_size);
> +	}
>  	return addr;
>  }
>  

Re: [PATCH] scripts: recordmcount: break hardlinks

[Russell King - ARM Linux]

On Fri, Dec 11, 2015 at 09:31:25AM -0500, Steven Rostedt wrote:
> On Fri, 11 Dec 2015 12:09:03 +0000
> Russell King <rmk+kernel@arm.linux.org.uk> wrote:
> 
> > recordmcount edits the file in-place, which can cause problems when
> > using ccache in hardlink mode.  Arrange for recordmcount to break a
> > hardlinked object.
> > 
> > Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
> > ---
> > Steven, sorry it took a while to get this out...
> 
> Should this be for stable, or is it fine to just add this to my 4.5
> queue?

I thought you wanted to test it first - although I've been running with
this for a while now, my nightly builds have masked out the mcount
warning, and I suspect it'll take a while for ccache to purge itself
of the modified objects.

If you're happy to add a stable tag to it, then please do so.

-- 
RMK's Patch system: http://www.arm.linux.org.uk/developer/patches/
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH] scripts: recordmcount: break hardlinks

[Steven Rostedt]

On Fri, 11 Dec 2015 14:45:41 +0000
Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:

> On Fri, Dec 11, 2015 at 09:31:25AM -0500, Steven Rostedt wrote:
> > On Fri, 11 Dec 2015 12:09:03 +0000
> > Russell King <rmk+kernel@arm.linux.org.uk> wrote:
> >   
> > > recordmcount edits the file in-place, which can cause problems when
> > > using ccache in hardlink mode.  Arrange for recordmcount to break a
> > > hardlinked object.
> > > 
> > > Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
> > > ---
> > > Steven, sorry it took a while to get this out...  
> > 
> > Should this be for stable, or is it fine to just add this to my 4.5
> > queue?  
> 
> I thought you wanted to test it first - although I've been running with

You're right. I forgot I said that ;-)


> this for a while now, my nightly builds have masked out the mcount
> warning, and I suspect it'll take a while for ccache to purge itself
> of the modified objects.
> 
> If you're happy to add a stable tag to it, then please do so.
> 

I'm fine with you taking it too, but let me go ahead and run it through
my tests now. I'll let you know the results. Takes several hours.

Thanks,

-- Steve

Re: [PATCH] scripts: recordmcount: break hardlinks

[Steven Rostedt]

On Fri, 11 Dec 2015 14:45:41 +0000
Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:

> On Fri, Dec 11, 2015 at 09:31:25AM -0500, Steven Rostedt wrote:
> > On Fri, 11 Dec 2015 12:09:03 +0000
> > Russell King <rmk+kernel@arm.linux.org.uk> wrote:
> >   
> > > recordmcount edits the file in-place, which can cause problems when
> > > using ccache in hardlink mode.  Arrange for recordmcount to break a
> > > hardlinked object.
> > > 
> > > Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
> > > ---
> > > Steven, sorry it took a while to get this out...  
> > 
> > Should this be for stable, or is it fine to just add this to my 4.5
> > queue?  
> 
> I thought you wanted to test it first - although I've been running with
> this for a while now, my nightly builds have masked out the mcount
> warning, and I suspect it'll take a while for ccache to purge itself
> of the modified objects.
> 
> If you're happy to add a stable tag to it, then please do so.
> 

I ran it through most my tests (it's still running and is at 20 of 33
tests). If there was anything wrong with this patch, I'm sure one of my
tests would have crashed by now.

Do you want to take it, or shall I?

If you want to take it, you can add my:

Reviewed-by: Steven Rostedt <rostedt@goodmis.org>

-- Steve

Re: [PATCH] scripts: recordmcount: break hardlinks

[Russell King - ARM Linux]

On Fri, Dec 11, 2015 at 01:10:29PM -0500, Steven Rostedt wrote:
> I ran it through most my tests (it's still running and is at 20 of 33
> tests). If there was anything wrong with this patch, I'm sure one of my
> tests would have crashed by now.

Thanks for testing.

> Do you want to take it, or shall I?

I'm easy - it probably makes more sense if take it.

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH] scripts: recordmcount: break hardlinks

[Steven Rostedt]

On Fri, 11 Dec 2015 18:33:27 +0000
Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:

> On Fri, Dec 11, 2015 at 01:10:29PM -0500, Steven Rostedt wrote:
> > I ran it through most my tests (it's still running and is at 20 of 33
> > tests). If there was anything wrong with this patch, I'm sure one of my
> > tests would have crashed by now.  
> 
> Thanks for testing.
> 
> > Do you want to take it, or shall I?  
> 
> I'm easy - it probably makes more sense if take it.
> 

Heh, you got me hanging in suspense. You missed a word. Is it:

 "makes more sense if *you* take it"

or

 "makes more sense if *I* take it"

??

Or you could be replying to my sentence of "take it" or "shall I" in
which it would be *you* take it.

/me confused

-- Steve

Re: [PATCH] scripts: recordmcount: break hardlinks

[Russell King - ARM Linux]

On Fri, Dec 11, 2015 at 01:51:15PM -0500, Steven Rostedt wrote:
> On Fri, 11 Dec 2015 18:33:27 +0000
> Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:
> 
> > On Fri, Dec 11, 2015 at 01:10:29PM -0500, Steven Rostedt wrote:
> > > I ran it through most my tests (it's still running and is at 20 of 33
> > > tests). If there was anything wrong with this patch, I'm sure one of my
> > > tests would have crashed by now.  
> > 
> > Thanks for testing.
> > 
> > > Do you want to take it, or shall I?  
> > 
> > I'm easy - it probably makes more sense if take it.
> > 
> 
> Heh, you got me hanging in suspense. You missed a word. Is it:
> 
>  "makes more sense if *you* take it"
> 
> or
> 
>  "makes more sense if *I* take it"
> 
> ??

Oops, sorry.  "makes more sense if *you* take it" was what I thought I
typed!

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH] scripts: recordmcount: break hardlinks

[Steven Rostedt]

On Fri, 11 Dec 2015 18:58:09 +0000
Russell King - ARM Linux <linux@arm.linux.org.uk> wrote:


> Oops, sorry.  "makes more sense if *you* take it" was what I thought I
> typed!
> 

OK, will do.

Thanks!

-- Steve

[PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Stephen Boyd]

The ARM compiler inserts calls to __aeabi_uidiv() and
__aeabi_idiv() when it needs to perform division on signed and
unsigned integers. If a processor has support for the udiv and
sdiv division instructions the calls to these support routines
can be replaced with those instructions. Now that recordmcount
records the locations of calls to these library functions in
two sections (one for udiv and one for sdiv), iterate over these
sections early at boot and patch the call sites with the
appropriate division instruction when we determine that the
processor supports the division instructions. Using the division
instructions should be faster and less power intensive than
running the support code.

Cc: Nicolas Pitre <nico@fluxnic.net>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Måns Rullgård <mans@mansr.com>
Cc: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
Signed-off-by: Stephen Boyd <sboyd@codeaurora.org>
---
 arch/arm/Kconfig               | 14 +++++++++
 arch/arm/include/asm/cputype.h |  8 ++++-
 arch/arm/include/asm/setup.h   |  3 ++
 arch/arm/kernel/module.c       | 40 +++++++++++++++++++++++++
 arch/arm/kernel/setup.c        | 68 ++++++++++++++++++++++++++++++++++++++++++
 arch/arm/kernel/vmlinux.lds.S  | 13 ++++++++
 6 files changed, 145 insertions(+), 1 deletion(-)

diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index 0365cbbc9179..aa8bc7da6331 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -1617,6 +1617,20 @@ config AEABI
 
 	  To use this you need GCC version 4.0.0 or later.
 
+config ARM_PATCH_UIDIV
+	bool "Runtime patch calls to __aeabi_{u}idiv() with udiv/sdiv"
+	depends on CPU_32v7 && !XIP_KERNEL && AEABI
+	help
+	  Some v7 CPUs have support for the udiv and sdiv instructions
+	  that can be used in place of calls to __aeabi_uidiv and __aeabi_idiv
+	  functions provided by the ARM runtime ABI.
+
+	  Enabling this option allows the kernel to modify itself to replace
+	  branches to these library functions with the udiv and sdiv
+	  instructions themselves. Typically this will be faster and less
+	  power intensive than running the library support code to do
+	  integer division.
+
 config OABI_COMPAT
 	bool "Allow old ABI binaries to run with this kernel (EXPERIMENTAL)"
 	depends on AEABI && !THUMB2_KERNEL
diff --git a/arch/arm/include/asm/cputype.h b/arch/arm/include/asm/cputype.h
index 85e374f873ac..48c77d422a0d 100644
--- a/arch/arm/include/asm/cputype.h
+++ b/arch/arm/include/asm/cputype.h
@@ -250,8 +250,14 @@ static inline int cpu_is_pj4(void)
 
 	return 0;
 }
+
+static inline bool __attribute_const__ cpu_is_pj4_nomp(void)
+{
+	return read_cpuid_part() == 0x56005810;
+}
 #else
-#define cpu_is_pj4()	0
+#define cpu_is_pj4()		0
+#define cpu_is_pj4_nomp()	0
 #endif
 
 static inline int __attribute_const__ cpuid_feature_extract_field(u32 features,
diff --git a/arch/arm/include/asm/setup.h b/arch/arm/include/asm/setup.h
index e0adb9f1bf94..a514552d5cbd 100644
--- a/arch/arm/include/asm/setup.h
+++ b/arch/arm/include/asm/setup.h
@@ -25,4 +25,7 @@ extern int arm_add_memory(u64 start, u64 size);
 extern void early_print(const char *str, ...);
 extern void dump_machine_table(void);
 
+extern void patch_udiv(void *addr, size_t size);
+extern void patch_sdiv(void *addr, size_t size);
+
 #endif
diff --git a/arch/arm/kernel/module.c b/arch/arm/kernel/module.c
index efdddcb97dd1..aa59e5cfe6a0 100644
--- a/arch/arm/kernel/module.c
+++ b/arch/arm/kernel/module.c
@@ -20,7 +20,9 @@
 #include <linux/string.h>
 #include <linux/gfp.h>
 
+#include <asm/hwcap.h>
 #include <asm/pgtable.h>
+#include <asm/setup.h>
 #include <asm/sections.h>
 #include <asm/smp_plat.h>
 #include <asm/unwind.h>
@@ -51,6 +53,38 @@ void *module_alloc(unsigned long size)
 }
 #endif
 
+#ifdef CONFIG_ARM_PATCH_UIDIV
+static int module_patch_aeabi_uidiv(unsigned long loc, const Elf32_Sym *sym)
+{
+	extern char __aeabi_uidiv[], __aeabi_idiv[];
+	unsigned long udiv_addr = (unsigned long)__aeabi_uidiv;
+	unsigned long sdiv_addr = (unsigned long)__aeabi_idiv;
+	unsigned int mask;
+
+	if (IS_ENABLED(CONFIG_THUMB2_KERNEL))
+		mask = HWCAP_IDIVT;
+	else
+		mask = HWCAP_IDIVA;
+
+	if (elf_hwcap & mask) {
+		if (sym->st_value == udiv_addr) {
+			patch_udiv(&loc, sizeof(loc));
+			return 1;
+		} else if (sym->st_value == sdiv_addr) {
+			patch_sdiv(&loc, sizeof(loc));
+			return 1;
+		}
+	}
+
+	return 0;
+}
+#else
+static int module_patch_aeabi_uidiv(unsigned long loc, const Elf32_Sym *sym)
+{
+	return 0;
+}
+#endif
+
 int
 apply_relocate(Elf32_Shdr *sechdrs, const char *strtab, unsigned int symindex,
 	       unsigned int relindex, struct module *module)
@@ -109,6 +143,9 @@ apply_relocate(Elf32_Shdr *sechdrs, const char *strtab, unsigned int symindex,
 				return -ENOEXEC;
 			}
 
+			if (module_patch_aeabi_uidiv(loc, sym))
+				break;
+
 			offset = __mem_to_opcode_arm(*(u32 *)loc);
 			offset = (offset & 0x00ffffff) << 2;
 			if (offset & 0x02000000)
@@ -195,6 +232,9 @@ apply_relocate(Elf32_Shdr *sechdrs, const char *strtab, unsigned int symindex,
 				return -ENOEXEC;
 			}
 
+			if (module_patch_aeabi_uidiv(loc, sym))
+				break;
+
 			upper = __mem_to_opcode_thumb16(*(u16 *)loc);
 			lower = __mem_to_opcode_thumb16(*(u16 *)(loc + 2));
 
diff --git a/arch/arm/kernel/setup.c b/arch/arm/kernel/setup.c
index 20edd349d379..39a46059d5e8 100644
--- a/arch/arm/kernel/setup.c
+++ b/arch/arm/kernel/setup.c
@@ -32,6 +32,7 @@
 #include <linux/compiler.h>
 #include <linux/sort.h>
 #include <linux/psci.h>
+#include <linux/module.h>
 
 #include <asm/unified.h>
 #include <asm/cp15.h>
@@ -375,6 +376,72 @@ void __init early_print(const char *str, ...)
 	printk("%s", buf);
 }
 
+#ifdef CONFIG_ARM_PATCH_UIDIV
+/* "sdiv r0, r0, r1" or "mrc p6, 1, r0, CR0, CR1, 4" if we're on pj4 w/o MP */
+static u32 __attribute_const__ sdiv_instruction(void)
+{
+	if (IS_ENABLED(CONFIG_THUMB2_KERNEL)) {
+		if (cpu_is_pj4_nomp())
+			return __opcode_to_mem_thumb32(0xee300691);
+		return __opcode_to_mem_thumb32(0xfb90f0f1);
+	}
+
+	if (cpu_is_pj4_nomp())
+		return __opcode_to_mem_arm(0xee300691);
+	return __opcode_to_mem_arm(0xe710f110);
+}
+
+/* "udiv r0, r0, r1" or "mrc p6, 1, r0, CR0, CR1, 0" if we're on pj4 w/o MP */
+static u32 __attribute_const__ udiv_instruction(void)
+{
+	if (IS_ENABLED(CONFIG_THUMB2_KERNEL)) {
+		if (cpu_is_pj4_nomp())
+			return __opcode_to_mem_thumb32(0xee300611);
+		return __opcode_to_mem_thumb32(0xfbb0f0f1);
+	}
+
+	if (cpu_is_pj4_nomp())
+		return __opcode_to_mem_arm(0xee300611);
+	return __opcode_to_mem_arm(0xe730f110);
+}
+
+static void __init_or_module patch(u32 **addr, size_t count, u32 insn)
+{
+	for (; count != 0; count -= 4)
+		**addr++ = insn;
+}
+
+void __init_or_module patch_udiv(void *addr, size_t size)
+{
+	patch(addr, size, udiv_instruction());
+}
+
+void __init_or_module patch_sdiv(void *addr, size_t size)
+{
+	return patch(addr, size, sdiv_instruction());
+}
+
+static void __init patch_aeabi_uidiv(void)
+{
+	extern char __start_udiv_loc[], __stop_udiv_loc[];
+	extern char __start_idiv_loc[], __stop_idiv_loc[];
+	unsigned int mask;
+
+	if (IS_ENABLED(CONFIG_THUMB2_KERNEL))
+		mask = HWCAP_IDIVT;
+	else
+		mask = HWCAP_IDIVA;
+
+	if (!(elf_hwcap & mask))
+		return;
+
+	patch_udiv(__start_udiv_loc, __stop_udiv_loc - __start_udiv_loc);
+	patch_sdiv(__start_idiv_loc, __stop_idiv_loc - __start_idiv_loc);
+}
+#else
+static void __init patch_aeabi_uidiv(void) { }
+#endif
+
 static void __init cpuid_init_hwcaps(void)
 {
 	int block;
@@ -642,6 +709,7 @@ static void __init setup_processor(void)
 	elf_hwcap = list->elf_hwcap;
 
 	cpuid_init_hwcaps();
+	patch_aeabi_uidiv();
 
 #ifndef CONFIG_ARM_THUMB
 	elf_hwcap &= ~(HWCAP_THUMB | HWCAP_IDIVT);
diff --git a/arch/arm/kernel/vmlinux.lds.S b/arch/arm/kernel/vmlinux.lds.S
index 8b60fde5ce48..bc87a2e04e6f 100644
--- a/arch/arm/kernel/vmlinux.lds.S
+++ b/arch/arm/kernel/vmlinux.lds.S
@@ -28,6 +28,18 @@
 	*(.hyp.idmap.text)						\
 	VMLINUX_SYMBOL(__hyp_idmap_text_end) = .;
 
+#ifdef CONFIG_ARM_PATCH_UIDIV
+#define UIDIV_REC	. = ALIGN(8);					\
+			VMLINUX_SYMBOL(__start_udiv_loc) = .;		\
+			*(__udiv_loc)					\
+			VMLINUX_SYMBOL(__stop_udiv_loc) = .;		\
+			VMLINUX_SYMBOL(__start_idiv_loc) = .;		\
+			*(__idiv_loc)					\
+			VMLINUX_SYMBOL(__stop_idiv_loc) = .;
+#else
+#define UIDIV_REC
+#endif
+
 #ifdef CONFIG_HOTPLUG_CPU
 #define ARM_CPU_DISCARD(x)
 #define ARM_CPU_KEEP(x)		x
@@ -210,6 +222,7 @@ SECTIONS
 	.init.data : {
 #ifndef CONFIG_XIP_KERNEL
 		INIT_DATA
+		UIDIV_REC
 #endif
 		INIT_SETUP(16)
 		INIT_CALLS
-- 
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum,
a Linux Foundation Collaborative Project

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Nicolas Pitre]

[-- Attachment #1: Type: text/plain, Size: 10386 bytes --]

On Wed, 25 Nov 2015, Stephen Boyd wrote:

> The ARM compiler inserts calls to __aeabi_uidiv() and
> __aeabi_idiv() when it needs to perform division on signed and
> unsigned integers. If a processor has support for the udiv and
> sdiv division instructions the calls to these support routines
> can be replaced with those instructions. Now that recordmcount
> records the locations of calls to these library functions in
> two sections (one for udiv and one for sdiv), iterate over these
> sections early at boot and patch the call sites with the
> appropriate division instruction when we determine that the
> processor supports the division instructions. Using the division
> instructions should be faster and less power intensive than
> running the support code.

A few remarks:

1) The code assumes unconditional branches to __aeabi_idiv and 
   __aeabi_uidiv. What if there are conditional branches? Also, tail 
   call optimizations will generate a straight b opcode rather than a bl 
   and patching those will obviously have catastrophic results.  I think 
   you should validate the presence of a bl before patching over it.

2) For those cases where a call to __aeabi_uidiv and __aeabi_idiv is not 
   patched due to (1), you could patch a uidiv/idiv plus "bx lr" 
   at those function entry points too.

3) In fact I was wondering if the overhead of the branch and back is 
   really significant compared to the non trivial cost of a idiv 
   instruction and all the complex infrastructure required to patch 
   those branches directly, and consequently if the performance 
   difference is actually worth it versus simply doing (2) alone.

4) Please add some printing to the boot log (debug level should be fine)  
   about the fact that you did modify n branch instances with a div 
   insn. That _could_ turn out to be a useful clue when debugging kernel 
   "strangeties".

> Cc: Nicolas Pitre <nico@fluxnic.net>
> Cc: Arnd Bergmann <arnd@arndb.de>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Måns Rullgård <mans@mansr.com>
> Cc: Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
> Signed-off-by: Stephen Boyd <sboyd@codeaurora.org>
> ---
>  arch/arm/Kconfig               | 14 +++++++++
>  arch/arm/include/asm/cputype.h |  8 ++++-
>  arch/arm/include/asm/setup.h   |  3 ++
>  arch/arm/kernel/module.c       | 40 +++++++++++++++++++++++++
>  arch/arm/kernel/setup.c        | 68 ++++++++++++++++++++++++++++++++++++++++++
>  arch/arm/kernel/vmlinux.lds.S  | 13 ++++++++
>  6 files changed, 145 insertions(+), 1 deletion(-)
> 
> diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
> index 0365cbbc9179..aa8bc7da6331 100644
> --- a/arch/arm/Kconfig
> +++ b/arch/arm/Kconfig
> @@ -1617,6 +1617,20 @@ config AEABI
>  
>  	  To use this you need GCC version 4.0.0 or later.
>  
> +config ARM_PATCH_UIDIV
> +	bool "Runtime patch calls to __aeabi_{u}idiv() with udiv/sdiv"
> +	depends on CPU_32v7 && !XIP_KERNEL && AEABI
> +	help
> +	  Some v7 CPUs have support for the udiv and sdiv instructions
> +	  that can be used in place of calls to __aeabi_uidiv and __aeabi_idiv
> +	  functions provided by the ARM runtime ABI.
> +
> +	  Enabling this option allows the kernel to modify itself to replace
> +	  branches to these library functions with the udiv and sdiv
> +	  instructions themselves. Typically this will be faster and less
> +	  power intensive than running the library support code to do
> +	  integer division.
> +
>  config OABI_COMPAT
>  	bool "Allow old ABI binaries to run with this kernel (EXPERIMENTAL)"
>  	depends on AEABI && !THUMB2_KERNEL
> diff --git a/arch/arm/include/asm/cputype.h b/arch/arm/include/asm/cputype.h
> index 85e374f873ac..48c77d422a0d 100644
> --- a/arch/arm/include/asm/cputype.h
> +++ b/arch/arm/include/asm/cputype.h
> @@ -250,8 +250,14 @@ static inline int cpu_is_pj4(void)
>  
>  	return 0;
>  }
> +
> +static inline bool __attribute_const__ cpu_is_pj4_nomp(void)
> +{
> +	return read_cpuid_part() == 0x56005810;
> +}
>  #else
> -#define cpu_is_pj4()	0
> +#define cpu_is_pj4()		0
> +#define cpu_is_pj4_nomp()	0
>  #endif
>  
>  static inline int __attribute_const__ cpuid_feature_extract_field(u32 features,
> diff --git a/arch/arm/include/asm/setup.h b/arch/arm/include/asm/setup.h
> index e0adb9f1bf94..a514552d5cbd 100644
> --- a/arch/arm/include/asm/setup.h
> +++ b/arch/arm/include/asm/setup.h
> @@ -25,4 +25,7 @@ extern int arm_add_memory(u64 start, u64 size);
>  extern void early_print(const char *str, ...);
>  extern void dump_machine_table(void);
>  
> +extern void patch_udiv(void *addr, size_t size);
> +extern void patch_sdiv(void *addr, size_t size);
> +
>  #endif
> diff --git a/arch/arm/kernel/module.c b/arch/arm/kernel/module.c
> index efdddcb97dd1..aa59e5cfe6a0 100644
> --- a/arch/arm/kernel/module.c
> +++ b/arch/arm/kernel/module.c
> @@ -20,7 +20,9 @@
>  #include <linux/string.h>
>  #include <linux/gfp.h>
>  
> +#include <asm/hwcap.h>
>  #include <asm/pgtable.h>
> +#include <asm/setup.h>
>  #include <asm/sections.h>
>  #include <asm/smp_plat.h>
>  #include <asm/unwind.h>
> @@ -51,6 +53,38 @@ void *module_alloc(unsigned long size)
>  }
>  #endif
>  
> +#ifdef CONFIG_ARM_PATCH_UIDIV
> +static int module_patch_aeabi_uidiv(unsigned long loc, const Elf32_Sym *sym)
> +{
> +	extern char __aeabi_uidiv[], __aeabi_idiv[];
> +	unsigned long udiv_addr = (unsigned long)__aeabi_uidiv;
> +	unsigned long sdiv_addr = (unsigned long)__aeabi_idiv;
> +	unsigned int mask;
> +
> +	if (IS_ENABLED(CONFIG_THUMB2_KERNEL))
> +		mask = HWCAP_IDIVT;
> +	else
> +		mask = HWCAP_IDIVA;
> +
> +	if (elf_hwcap & mask) {
> +		if (sym->st_value == udiv_addr) {
> +			patch_udiv(&loc, sizeof(loc));
> +			return 1;
> +		} else if (sym->st_value == sdiv_addr) {
> +			patch_sdiv(&loc, sizeof(loc));
> +			return 1;
> +		}
> +	}
> +
> +	return 0;
> +}
> +#else
> +static int module_patch_aeabi_uidiv(unsigned long loc, const Elf32_Sym *sym)
> +{
> +	return 0;
> +}
> +#endif
> +
>  int
>  apply_relocate(Elf32_Shdr *sechdrs, const char *strtab, unsigned int symindex,
>  	       unsigned int relindex, struct module *module)
> @@ -109,6 +143,9 @@ apply_relocate(Elf32_Shdr *sechdrs, const char *strtab, unsigned int symindex,
>  				return -ENOEXEC;
>  			}
>  
> +			if (module_patch_aeabi_uidiv(loc, sym))
> +				break;
> +
>  			offset = __mem_to_opcode_arm(*(u32 *)loc);
>  			offset = (offset & 0x00ffffff) << 2;
>  			if (offset & 0x02000000)
> @@ -195,6 +232,9 @@ apply_relocate(Elf32_Shdr *sechdrs, const char *strtab, unsigned int symindex,
>  				return -ENOEXEC;
>  			}
>  
> +			if (module_patch_aeabi_uidiv(loc, sym))
> +				break;
> +
>  			upper = __mem_to_opcode_thumb16(*(u16 *)loc);
>  			lower = __mem_to_opcode_thumb16(*(u16 *)(loc + 2));
>  
> diff --git a/arch/arm/kernel/setup.c b/arch/arm/kernel/setup.c
> index 20edd349d379..39a46059d5e8 100644
> --- a/arch/arm/kernel/setup.c
> +++ b/arch/arm/kernel/setup.c
> @@ -32,6 +32,7 @@
>  #include <linux/compiler.h>
>  #include <linux/sort.h>
>  #include <linux/psci.h>
> +#include <linux/module.h>
>  
>  #include <asm/unified.h>
>  #include <asm/cp15.h>
> @@ -375,6 +376,72 @@ void __init early_print(const char *str, ...)
>  	printk("%s", buf);
>  }
>  
> +#ifdef CONFIG_ARM_PATCH_UIDIV
> +/* "sdiv r0, r0, r1" or "mrc p6, 1, r0, CR0, CR1, 4" if we're on pj4 w/o MP */
> +static u32 __attribute_const__ sdiv_instruction(void)
> +{
> +	if (IS_ENABLED(CONFIG_THUMB2_KERNEL)) {
> +		if (cpu_is_pj4_nomp())
> +			return __opcode_to_mem_thumb32(0xee300691);
> +		return __opcode_to_mem_thumb32(0xfb90f0f1);
> +	}
> +
> +	if (cpu_is_pj4_nomp())
> +		return __opcode_to_mem_arm(0xee300691);
> +	return __opcode_to_mem_arm(0xe710f110);
> +}
> +
> +/* "udiv r0, r0, r1" or "mrc p6, 1, r0, CR0, CR1, 0" if we're on pj4 w/o MP */
> +static u32 __attribute_const__ udiv_instruction(void)
> +{
> +	if (IS_ENABLED(CONFIG_THUMB2_KERNEL)) {
> +		if (cpu_is_pj4_nomp())
> +			return __opcode_to_mem_thumb32(0xee300611);
> +		return __opcode_to_mem_thumb32(0xfbb0f0f1);
> +	}
> +
> +	if (cpu_is_pj4_nomp())
> +		return __opcode_to_mem_arm(0xee300611);
> +	return __opcode_to_mem_arm(0xe730f110);
> +}
> +
> +static void __init_or_module patch(u32 **addr, size_t count, u32 insn)
> +{
> +	for (; count != 0; count -= 4)
> +		**addr++ = insn;
> +}
> +
> +void __init_or_module patch_udiv(void *addr, size_t size)
> +{
> +	patch(addr, size, udiv_instruction());
> +}
> +
> +void __init_or_module patch_sdiv(void *addr, size_t size)
> +{
> +	return patch(addr, size, sdiv_instruction());
> +}
> +
> +static void __init patch_aeabi_uidiv(void)
> +{
> +	extern char __start_udiv_loc[], __stop_udiv_loc[];
> +	extern char __start_idiv_loc[], __stop_idiv_loc[];
> +	unsigned int mask;
> +
> +	if (IS_ENABLED(CONFIG_THUMB2_KERNEL))
> +		mask = HWCAP_IDIVT;
> +	else
> +		mask = HWCAP_IDIVA;
> +
> +	if (!(elf_hwcap & mask))
> +		return;
> +
> +	patch_udiv(__start_udiv_loc, __stop_udiv_loc - __start_udiv_loc);
> +	patch_sdiv(__start_idiv_loc, __stop_idiv_loc - __start_idiv_loc);
> +}
> +#else
> +static void __init patch_aeabi_uidiv(void) { }
> +#endif
> +
>  static void __init cpuid_init_hwcaps(void)
>  {
>  	int block;
> @@ -642,6 +709,7 @@ static void __init setup_processor(void)
>  	elf_hwcap = list->elf_hwcap;
>  
>  	cpuid_init_hwcaps();
> +	patch_aeabi_uidiv();
>  
>  #ifndef CONFIG_ARM_THUMB
>  	elf_hwcap &= ~(HWCAP_THUMB | HWCAP_IDIVT);
> diff --git a/arch/arm/kernel/vmlinux.lds.S b/arch/arm/kernel/vmlinux.lds.S
> index 8b60fde5ce48..bc87a2e04e6f 100644
> --- a/arch/arm/kernel/vmlinux.lds.S
> +++ b/arch/arm/kernel/vmlinux.lds.S
> @@ -28,6 +28,18 @@
>  	*(.hyp.idmap.text)						\
>  	VMLINUX_SYMBOL(__hyp_idmap_text_end) = .;
>  
> +#ifdef CONFIG_ARM_PATCH_UIDIV
> +#define UIDIV_REC	. = ALIGN(8);					\
> +			VMLINUX_SYMBOL(__start_udiv_loc) = .;		\
> +			*(__udiv_loc)					\
> +			VMLINUX_SYMBOL(__stop_udiv_loc) = .;		\
> +			VMLINUX_SYMBOL(__start_idiv_loc) = .;		\
> +			*(__idiv_loc)					\
> +			VMLINUX_SYMBOL(__stop_idiv_loc) = .;
> +#else
> +#define UIDIV_REC
> +#endif
> +
>  #ifdef CONFIG_HOTPLUG_CPU
>  #define ARM_CPU_DISCARD(x)
>  #define ARM_CPU_KEEP(x)		x
> @@ -210,6 +222,7 @@ SECTIONS
>  	.init.data : {
>  #ifndef CONFIG_XIP_KERNEL
>  		INIT_DATA
> +		UIDIV_REC
>  #endif
>  		INIT_SETUP(16)
>  		INIT_CALLS
> -- 
> The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum,
> a Linux Foundation Collaborative Project
> 
> 

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Russell King - ARM Linux]

On Wed, Nov 25, 2015 at 06:09:13PM -0500, Nicolas Pitre wrote:
> 3) In fact I was wondering if the overhead of the branch and back is 
>    really significant compared to the non trivial cost of a idiv 
>    instruction and all the complex infrastructure required to patch 
>    those branches directly, and consequently if the performance 
>    difference is actually worth it versus simply doing (2) alone.

I definitely agree with you on this, given that modern CPUs which
are going to be benefitting from idiv are modern CPUs with a branch
predictor (and if it's not predicting such unconditional calls and
returns it's not much use as a branch predictor!)

I think what we need to see is the performance of existing kernels,
vs patching the idiv instructions at every callsite, vs patching
the called function itself.

> > +#ifdef CONFIG_ARM_PATCH_UIDIV
> > +/* "sdiv r0, r0, r1" or "mrc p6, 1, r0, CR0, CR1, 4" if we're on pj4 w/o MP */
> > +static u32 __attribute_const__ sdiv_instruction(void)
> > +{
> > +	if (IS_ENABLED(CONFIG_THUMB2_KERNEL)) {
> > +		if (cpu_is_pj4_nomp())
> > +			return __opcode_to_mem_thumb32(0xee300691);
> > +		return __opcode_to_mem_thumb32(0xfb90f0f1);
> > +	}
> > +
> > +	if (cpu_is_pj4_nomp())
> > +		return __opcode_to_mem_arm(0xee300691);
> > +	return __opcode_to_mem_arm(0xe710f110);
> > +}
> > +
> > +/* "udiv r0, r0, r1" or "mrc p6, 1, r0, CR0, CR1, 0" if we're on pj4 w/o MP */
> > +static u32 __attribute_const__ udiv_instruction(void)
> > +{
> > +	if (IS_ENABLED(CONFIG_THUMB2_KERNEL)) {
> > +		if (cpu_is_pj4_nomp())
> > +			return __opcode_to_mem_thumb32(0xee300611);
> > +		return __opcode_to_mem_thumb32(0xfbb0f0f1);
> > +	}
> > +
> > +	if (cpu_is_pj4_nomp())
> > +		return __opcode_to_mem_arm(0xee300611);
> > +	return __opcode_to_mem_arm(0xe730f110);
> > +}

Any reason the above aren't marked with __init_or_module as well, as
the compiler can choose not to inline them?

> > +
> > +static void __init_or_module patch(u32 **addr, size_t count, u32 insn)
> > +{
> > +	for (; count != 0; count -= 4)
> > +		**addr++ = insn;
> > +}
> > +
> > +void __init_or_module patch_udiv(void *addr, size_t size)
> > +{
> > +	patch(addr, size, udiv_instruction());
> > +}
> > +
> > +void __init_or_module patch_sdiv(void *addr, size_t size)
> > +{
> > +	return patch(addr, size, sdiv_instruction());
> > +}
> > +
> > +static void __init patch_aeabi_uidiv(void)
> > +{
> > +	extern char __start_udiv_loc[], __stop_udiv_loc[];
> > +	extern char __start_idiv_loc[], __stop_idiv_loc[];
> > +	unsigned int mask;
> > +
> > +	if (IS_ENABLED(CONFIG_THUMB2_KERNEL))
> > +		mask = HWCAP_IDIVT;
> > +	else
> > +		mask = HWCAP_IDIVA;
> > +
> > +	if (!(elf_hwcap & mask))
> > +		return;
> > +
> > +	patch_udiv(__start_udiv_loc, __stop_udiv_loc - __start_udiv_loc);
> > +	patch_sdiv(__start_idiv_loc, __stop_idiv_loc - __start_idiv_loc);

I'm left really concerned about this.  We're modifying code with all
the caches on, and the above is not only missing any coherency of the
I/D paths, it's also missing any branch predictor maintanence.  So, if
we've executed any divisions at this point, the predictor could already
predicted one of these branches that's being modified.

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Måns Rullgård]

Nicolas Pitre <nico@fluxnic.net> writes:

> On Wed, 25 Nov 2015, Stephen Boyd wrote:
>
>> The ARM compiler inserts calls to __aeabi_uidiv() and
>> __aeabi_idiv() when it needs to perform division on signed and
>> unsigned integers. If a processor has support for the udiv and
>> sdiv division instructions the calls to these support routines
>> can be replaced with those instructions. Now that recordmcount
>> records the locations of calls to these library functions in
>> two sections (one for udiv and one for sdiv), iterate over these
>> sections early at boot and patch the call sites with the
>> appropriate division instruction when we determine that the
>> processor supports the division instructions. Using the division
>> instructions should be faster and less power intensive than
>> running the support code.
>
> A few remarks:
>
> 1) The code assumes unconditional branches to __aeabi_idiv and 
>    __aeabi_uidiv. What if there are conditional branches? Also, tail 
>    call optimizations will generate a straight b opcode rather than a bl 
>    and patching those will obviously have catastrophic results.  I think 
>    you should validate the presence of a bl before patching over it.

I did a quick check on a compiled kernel I had nearby, and there are no
conditional or tail calls to those functions, so although they should
obviously be checked for correctness, performance is unlikely to matter
for those.

However, there are almost half as many calls to __aeabi_{u}idivmod as to
the plain div functions, 129 vs 228 for signed and unsigned combined.
For best results, these functions should also be patched with the
hardware instructions.  Obviously the call sites for these can't be
patched.

> 2) For those cases where a call to __aeabi_uidiv and __aeabi_idiv is not 
>    patched due to (1), you could patch a uidiv/idiv plus "bx lr" 
>    at those function entry points too.
>
> 3) In fact I was wondering if the overhead of the branch and back is 
>    really significant compared to the non trivial cost of a idiv 
>    instruction and all the complex infrastructure required to patch 
>    those branches directly, and consequently if the performance 
>    difference is actually worth it versus simply doing (2) alone.

Depending on the operands, the div instruction can take as few as 3
cycles on a Cortex-A7.

-- 
Måns Rullgård
mans@mansr.com

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Nicolas Pitre]

[-- Attachment #1: Type: text/plain, Size: 3097 bytes --]

On Thu, 26 Nov 2015, Måns Rullgård wrote:

> Nicolas Pitre <nico@fluxnic.net> writes:
> 
> > On Wed, 25 Nov 2015, Stephen Boyd wrote:
> >
> >> The ARM compiler inserts calls to __aeabi_uidiv() and
> >> __aeabi_idiv() when it needs to perform division on signed and
> >> unsigned integers. If a processor has support for the udiv and
> >> sdiv division instructions the calls to these support routines
> >> can be replaced with those instructions. Now that recordmcount
> >> records the locations of calls to these library functions in
> >> two sections (one for udiv and one for sdiv), iterate over these
> >> sections early at boot and patch the call sites with the
> >> appropriate division instruction when we determine that the
> >> processor supports the division instructions. Using the division
> >> instructions should be faster and less power intensive than
> >> running the support code.
> >
> > A few remarks:
> >
> > 1) The code assumes unconditional branches to __aeabi_idiv and 
> >    __aeabi_uidiv. What if there are conditional branches? Also, tail 
> >    call optimizations will generate a straight b opcode rather than a bl 
> >    and patching those will obviously have catastrophic results.  I think 
> >    you should validate the presence of a bl before patching over it.
> 
> I did a quick check on a compiled kernel I had nearby, and there are no
> conditional or tail calls to those functions, so although they should
> obviously be checked for correctness, performance is unlikely to matter
> for those.

I'm more worried about correctness than performance.  This kind of 
patching should be done defensively.

> However, there are almost half as many calls to __aeabi_{u}idivmod as to
> the plain div functions, 129 vs 228 for signed and unsigned combined.
> For best results, these functions should also be patched with the
> hardware instructions.  Obviously the call sites for these can't be
> patched.

Current __aeabi_{u}idivmod implementations are simple wrappers around a 
call to __aeabi_{u}idiv so they'd get the benefit automatically 
regardless of the chosen approach.

> > 2) For those cases where a call to __aeabi_uidiv and __aeabi_idiv is not 
> >    patched due to (1), you could patch a uidiv/idiv plus "bx lr" 
> >    at those function entry points too.
> >
> > 3) In fact I was wondering if the overhead of the branch and back is 
> >    really significant compared to the non trivial cost of a idiv 
> >    instruction and all the complex infrastructure required to patch 
> >    those branches directly, and consequently if the performance 
> >    difference is actually worth it versus simply doing (2) alone.
> 
> Depending on the operands, the div instruction can take as few as 3
> cycles on a Cortex-A7.

Even the current software based implementation can produce a result with 
about 5 simple ALU instructions depending on the operands.

The average cycle count is more important than the easy-way-out case. 
And then how significant the two branches around it are compared to idiv 
alone from direct patching of every call to it.


Nicolas

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Måns Rullgård]

Nicolas Pitre <nico@fluxnic.net> writes:

> On Thu, 26 Nov 2015, Måns Rullgård wrote:
>
>> Nicolas Pitre <nico@fluxnic.net> writes:
>> 
>> > 3) In fact I was wondering if the overhead of the branch and back is 
>> >    really significant compared to the non trivial cost of a idiv 
>> >    instruction and all the complex infrastructure required to patch 
>> >    those branches directly, and consequently if the performance 
>> >    difference is actually worth it versus simply doing (2) alone.
>> 
>> Depending on the operands, the div instruction can take as few as 3
>> cycles on a Cortex-A7.
>
> Even the current software based implementation can produce a result with 
> about 5 simple ALU instructions depending on the operands.
>
> The average cycle count is more important than the easy-way-out case. 
> And then how significant the two branches around it are compared to idiv 
> alone from direct patching of every call to it.

If not calling the function saves an I-cache miss, the benefit can be
substantial.  No, I have no proof of this being a problem, but it's
something that could happen.

Of course, none of this is going to be as good as letting the compiler
generate div instructions directly.

-- 
Måns Rullgård
mans@mansr.com

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Russell King - ARM Linux]

On Thu, Nov 26, 2015 at 12:50:08AM +0000, Måns Rullgård wrote:
> If not calling the function saves an I-cache miss, the benefit can be
> substantial.  No, I have no proof of this being a problem, but it's
> something that could happen.

That's a simplistic view of modern CPUs.

As I've already said, modern CPUs which have branch prediction, but
they also have speculative instruction fetching and speculative data
prefetching - which the CPUs which have idiv support will have.

With such features, the branch predictor is able to learn that the
branch will be taken, and because of the speculative instruction
fetching, it can bring the cache line in so that it has the
instructions it needs with minimal or, if working correctly,
without stalling the CPU pipeline.

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Måns Rullgård]

Russell King - ARM Linux <linux@arm.linux.org.uk> writes:

> On Thu, Nov 26, 2015 at 12:50:08AM +0000, Måns Rullgård wrote:
>> If not calling the function saves an I-cache miss, the benefit can be
>> substantial.  No, I have no proof of this being a problem, but it's
>> something that could happen.
>
> That's a simplistic view of modern CPUs.
>
> As I've already said, modern CPUs which have branch prediction, but
> they also have speculative instruction fetching and speculative data
> prefetching - which the CPUs which have idiv support will have.
>
> With such features, the branch predictor is able to learn that the
> branch will be taken, and because of the speculative instruction
> fetching, it can bring the cache line in so that it has the
> instructions it needs with minimal or, if working correctly,
> without stalling the CPU pipeline.

It doesn't matter how many fancy features the CPU has.  Executing more
branches and using more cache lines puts additional pressure on those
resources, reducing overall performance.  Besides, the performance
counters readily show that the prediction is nothing near as perfect as
you seem to believe.

-- 
Måns Rullgård
mans@mansr.com

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Nicolas Pitre]

[-- Attachment #1: Type: text/plain, Size: 3426 bytes --]

On Thu, 26 Nov 2015, Måns Rullgård wrote:

> Russell King - ARM Linux <linux@arm.linux.org.uk> writes:
> 
> > On Thu, Nov 26, 2015 at 12:50:08AM +0000, Måns Rullgård wrote:
> >> If not calling the function saves an I-cache miss, the benefit can be
> >> substantial.  No, I have no proof of this being a problem, but it's
> >> something that could happen.
> >
> > That's a simplistic view of modern CPUs.
> >
> > As I've already said, modern CPUs which have branch prediction, but
> > they also have speculative instruction fetching and speculative data
> > prefetching - which the CPUs which have idiv support will have.
> >
> > With such features, the branch predictor is able to learn that the
> > branch will be taken, and because of the speculative instruction
> > fetching, it can bring the cache line in so that it has the
> > instructions it needs with minimal or, if working correctly,
> > without stalling the CPU pipeline.
> 
> It doesn't matter how many fancy features the CPU has.  Executing more
> branches and using more cache lines puts additional pressure on those
> resources, reducing overall performance.  Besides, the performance
> counters readily show that the prediction is nothing near as perfect as
> you seem to believe.

OK... Let's try to come up with actual numbers.

We know that letting gcc emit idiv by itself is the ultimate solution. 
And it is free of maintenance on our side besides passing the 
appropriate argument to gcc of course. So this is worth doing.

For the case where you have a set of target machines in your kernel that 
may or may not have idiv, then the first step should be to patch 
__aeabi_uidiv and __aeabi_idiv.  This is a pretty small and simple 
change that might turn out to be more than good enough. It is necessary 
anyway as the full patching solution does not cover all cases.

Then, IMHO, it would be a good idea to get performance numbers to 
compare that first step and the full patching solution. Of course the 
full patching will yield better performance. It has to. But if the 
difference is not significant enough, then it might not be worth 
introducing the implied complexity into mainline.  And it is not because 
the approach is bad. In fact I think this is a very cool hack. But it 
comes with a cost in maintenance and that cost has to be justified.

Just to have an idea, I produced the attached micro benchmark. I tested 
on a TC2 forced to a single Cortex-A15 core and I got those results:

Testing INLINE_DIV ...

real    0m7.182s
user    0m7.170s
sys     0m0.000s

Testing PATCHED_DIV ...

real    0m7.181s
user    0m7.170s
sys     0m0.000s

Testing OUTOFLINE_DIV ...

real    0m7.181s
user    0m7.170s
sys     0m0.005s

Testing LIBGCC_DIV ...

real    0m18.659s
user    0m18.635s
sys     0m0.000s

As you can see, whether the div is inline or out-of-line, whether 
arguments are moved into r0-r1 or not, makes no difference at all on a 
Cortex-A15.

Now forcing it onto a Cortex-A7 core:

Testing INLINE_DIV ...

real    0m8.917s
user    0m8.895s
sys     0m0.005s

Testing PATCHED_DIV ...

real    0m11.666s
user    0m11.645s
sys     0m0.000s

Testing OUTOFLINE_DIV ...

real    0m13.065s
user    0m13.025s
sys     0m0.000s

Testing LIBGCC_DIV ...

real    0m51.815s
user    0m51.750s
sys     0m0.005s

So on A cortex-A7 the various overheads become visible. How significant 
is it in practice with normal kernel usage? I don't know.


Nicolas

[-- Attachment #2: Type: text/plain, Size: 207 bytes --]

#!/bin/sh
set -e
for test in INLINE_DIV PATCHED_DIV OUTOFLINE_DIV LIBGCC_DIV; do
  gcc -o divtest_$test divtest.S -D$test
  echo "Testing $test ..."
  time ./divtest_$test
  echo
  rm -f divtest_$test
done


[-- Attachment #3: Type: text/plain, Size: 582 bytes --]

	.arm
	.arch_extension idiv

	.globl main
main:

	stmfd	sp!, {r4, r5, lr}

	mov	r4, #17
1:	mov	r5, #1

2:
#if defined(INLINE_DIV)

	udiv	r0, r4, r5

#elif defined(OUTOFLINE_DIV)

	mov	r0, r4
	mov	r1, r5
	bl	my_div

#elif defined(PATCHED_DIV)

	mov	r0, r4
	mov	r1, r5
	udiv	r0, r0, r1

#elif defined(LIBGCC_DIV)

	mov	r0, r4
	mov	r1, r5
	bl	__aeabi_uidiv

#else
#error "define INLINE_DIV, OUTOFLINE_DIV or LIBGCC_DIV"
#endif

	add	r5, r5, #1
	cmp	r4, r5
	bhs	2b
	adds	r4, r4, r4, lsl #1
	bpl	1b

	mov	r0, #0
	ldmfd	sp!, {r4, r5, pc}

	.space 1024

my_div:

	udiv	r0, r0, r1
	bx	lr

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Måns Rullgård]

Nicolas Pitre <nico@fluxnic.net> writes:

> On Thu, 26 Nov 2015, Måns Rullgård wrote:
>
>> Russell King - ARM Linux <linux@arm.linux.org.uk> writes:
>> 
>> > On Thu, Nov 26, 2015 at 12:50:08AM +0000, Måns Rullgård wrote:
>> >> If not calling the function saves an I-cache miss, the benefit can be
>> >> substantial.  No, I have no proof of this being a problem, but it's
>> >> something that could happen.
>> >
>> > That's a simplistic view of modern CPUs.
>> >
>> > As I've already said, modern CPUs which have branch prediction, but
>> > they also have speculative instruction fetching and speculative data
>> > prefetching - which the CPUs which have idiv support will have.
>> >
>> > With such features, the branch predictor is able to learn that the
>> > branch will be taken, and because of the speculative instruction
>> > fetching, it can bring the cache line in so that it has the
>> > instructions it needs with minimal or, if working correctly,
>> > without stalling the CPU pipeline.
>> 
>> It doesn't matter how many fancy features the CPU has.  Executing more
>> branches and using more cache lines puts additional pressure on those
>> resources, reducing overall performance.  Besides, the performance
>> counters readily show that the prediction is nothing near as perfect as
>> you seem to believe.
>
> OK... Let's try to come up with actual numbers.
>
> We know that letting gcc emit idiv by itself is the ultimate solution. 
> And it is free of maintenance on our side besides passing the 
> appropriate argument to gcc of course. So this is worth doing.
>
> For the case where you have a set of target machines in your kernel that 
> may or may not have idiv, then the first step should be to patch 
> __aeabi_uidiv and __aeabi_idiv.  This is a pretty small and simple 
> change that might turn out to be more than good enough. It is necessary 
> anyway as the full patching solution does not cover all cases.
>
> Then, IMHO, it would be a good idea to get performance numbers to 
> compare that first step and the full patching solution. Of course the 
> full patching will yield better performance. It has to. But if the 
> difference is not significant enough, then it might not be worth 
> introducing the implied complexity into mainline.  And it is not because 
> the approach is bad. In fact I think this is a very cool hack. But it 
> comes with a cost in maintenance and that cost has to be justified.
>
> Just to have an idea, I produced the attached micro benchmark. I tested 
> on a TC2 forced to a single Cortex-A15 core and I got those results:
>
> Testing INLINE_DIV ...
>
> real    0m7.182s
> user    0m7.170s
> sys     0m0.000s
>
> Testing PATCHED_DIV ...
>
> real    0m7.181s
> user    0m7.170s
> sys     0m0.000s
>
> Testing OUTOFLINE_DIV ...
>
> real    0m7.181s
> user    0m7.170s
> sys     0m0.005s
>
> Testing LIBGCC_DIV ...
>
> real    0m18.659s
> user    0m18.635s
> sys     0m0.000s
>
> As you can see, whether the div is inline or out-of-line, whether 
> arguments are moved into r0-r1 or not, makes no difference at all on a 
> Cortex-A15.
>
> Now forcing it onto a Cortex-A7 core:
>
> Testing INLINE_DIV ...
>
> real    0m8.917s
> user    0m8.895s
> sys     0m0.005s
>
> Testing PATCHED_DIV ...
>
> real    0m11.666s
> user    0m11.645s
> sys     0m0.000s
>
> Testing OUTOFLINE_DIV ...
>
> real    0m13.065s
> user    0m13.025s
> sys     0m0.000s
>
> Testing LIBGCC_DIV ...
>
> real    0m51.815s
> user    0m51.750s
> sys     0m0.005s
>
> So on A cortex-A7 the various overheads become visible. How significant 
> is it in practice with normal kernel usage? I don't know.

Bear in mind that in a trivial test like this, everything fits in L1
caches and branch prediction works perfectly.  It would be more
informative to measure the effect on a load that already has some cache
and branch prediction misses.

-- 
Måns Rullgård
mans@mansr.com

Re: [PATCH v2 2/2] ARM: Replace calls to __aeabi_{u}idiv with udiv/sdiv instructions

[Russell King - ARM Linux]

On Wed, Nov 25, 2015 at 01:51:04PM -0800, Stephen Boyd wrote:
> diff --git a/arch/arm/include/asm/cputype.h b/arch/arm/include/asm/cputype.h
> index 85e374f873ac..48c77d422a0d 100644
> --- a/arch/arm/include/asm/cputype.h
> +++ b/arch/arm/include/asm/cputype.h
> @@ -250,8 +250,14 @@ static inline int cpu_is_pj4(void)
>  
>  	return 0;
>  }
> +
> +static inline bool __attribute_const__ cpu_is_pj4_nomp(void)
> +{
> +	return read_cpuid_part() == 0x56005810;

One other thing here, we really ought to avoid adding more magic numbers
to this file.  We have the ARM processors nicely #defined, but not a lot
else.  Maybe its time that we continued with the nice definitions for
these part numbers?

-- 
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.