[PATCH 1/2] scripts/sorttable: Build orc fast lookup table via sorttable tool

[Huaixin Chang <changhuaixin@linux.alibaba.com>]

Since orc tables are already sorted by sorttable tool, let us move
building of fast lookup table into sorttable tool too. This saves us
6380us from boot time under Intel(R) Xeon(R) CPU E5-2682 v4 @ 2.50GHz
with 64 cores.

Signed-off-by: Huaixin Chang <changhuaixin@linux.alibaba.com>
Signed-off-by: Shile Zhang <shile.zhang@linux.alibaba.com>
---
 scripts/sorttable.h | 99 +++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 92 insertions(+), 7 deletions(-)

diff --git a/scripts/sorttable.h b/scripts/sorttable.h
index a2baa2fefb13..a36c76c17be4 100644
--- a/scripts/sorttable.h
+++ b/scripts/sorttable.h
@@ -93,12 +93,50 @@
 char g_err[ERRSTR_MAXSZ];
 int *g_orc_ip_table;
 struct orc_entry *g_orc_table;
+static unsigned long orc_ip_table_offset;
 
 pthread_t orc_sort_thread;
 
+struct orc_sort_param {
+	size_t		lookup_table_size;
+	unsigned int	*orc_lookup_table;
+	unsigned long	start_ip;
+	size_t		text_size;
+	unsigned int	orc_num_entries;
+};
+
 static inline unsigned long orc_ip(const int *ip)
 {
-	return (unsigned long)ip + *ip;
+	return (unsigned long)ip + *ip + orc_ip_table_offset;
+}
+
+static struct orc_entry *__orc_find(int *ip_table, struct orc_entry *u_table,
+				    unsigned int num_entries, unsigned long ip)
+{
+	int *first = ip_table;
+	int *last = ip_table + num_entries - 1;
+	int *mid = first, *found = first;
+
+	if (!num_entries)
+		return NULL;
+
+	/*
+	 * Do a binary range search to find the rightmost duplicate of a given
+	 * starting address.  Some entries are section terminators which are
+	 * "weak" entries for ensuring there are no gaps.  They should be
+	 * ignored when they conflict with a real entry.
+	 */
+	while (first <= last) {
+		mid = first + ((last - first) / 2);
+
+		if (orc_ip(mid) <= ip) {
+			found = mid;
+			first = mid + 1;
+		} else
+			last = mid - 1;
+	}
+
+	return u_table + (found - ip_table);
 }
 
 static int orc_sort_cmp(const void *_a, const void *_b)
@@ -130,18 +168,24 @@ static void *sort_orctable(void *arg)
 	int *idxs = NULL;
 	int *tmp_orc_ip_table = NULL;
 	struct orc_entry *tmp_orc_table = NULL;
-	unsigned int *orc_ip_size = (unsigned int *)arg;
-	unsigned int num_entries = *orc_ip_size / sizeof(int);
+	struct orc_sort_param *param = (struct orc_sort_param *)arg;
+	unsigned int num_entries = param->orc_num_entries;
+	unsigned int orc_ip_size = num_entries * sizeof(int);
 	unsigned int orc_size = num_entries * sizeof(struct orc_entry);
+	unsigned int lookup_num_blocks = param->lookup_table_size / sizeof(int);
+	unsigned int *orc_lookup = param->orc_lookup_table;
+	unsigned long lookup_start_ip = param->start_ip;
+	unsigned long lookup_stop_ip = param->start_ip + param->text_size;
+	struct orc_entry *orc;
 
-	idxs = (int *)malloc(*orc_ip_size);
+	idxs = (int *)malloc(orc_ip_size);
 	if (!idxs) {
 		snprintf(g_err, ERRSTR_MAXSZ, "malloc idxs: %s",
 			 strerror(errno));
 		pthread_exit(g_err);
 	}
 
-	tmp_orc_ip_table = (int *)malloc(*orc_ip_size);
+	tmp_orc_ip_table = (int *)malloc(orc_ip_size);
 	if (!tmp_orc_ip_table) {
 		snprintf(g_err, ERRSTR_MAXSZ, "malloc tmp_orc_ip_table: %s",
 			 strerror(errno));
@@ -173,6 +217,31 @@ static void *sort_orctable(void *arg)
 		g_orc_table[i] = tmp_orc_table[idxs[i]];
 	}
 
+#define LOOKUP_BLOCK_ORDER	8
+#define LOOKUP_BLOCK_SIZE	(1 << LOOKUP_BLOCK_ORDER)
+
+	for (i = 0; i < lookup_num_blocks-1; i++) {
+		orc = __orc_find(g_orc_ip_table, g_orc_table,
+				 num_entries,
+				 lookup_start_ip + (LOOKUP_BLOCK_SIZE * i));
+		if (!orc) {
+			snprintf(g_err, ERRSTR_MAXSZ,
+					"Corrupt .orc_unwind table\n");
+			pthread_exit(g_err);
+		}
+
+		orc_lookup[i] = orc - g_orc_table;
+	}
+
+	/* Initialize the ending block: */
+	orc = __orc_find(g_orc_ip_table, g_orc_table, num_entries,
+			 lookup_stop_ip);
+	if (!orc) {
+		snprintf(g_err, ERRSTR_MAXSZ, "Corrupt .orc_unwind table\n");
+		pthread_exit(g_err);
+	}
+	orc_lookup[lookup_num_blocks-1] = orc - g_orc_table;
+
 	free(idxs);
 	free(tmp_orc_ip_table);
 	free(tmp_orc_table);
@@ -221,6 +290,8 @@ static int do_sort(Elf_Ehdr *ehdr,
 	unsigned int orc_ip_size = 0;
 	unsigned int orc_size = 0;
 	unsigned int orc_num_entries = 0;
+	unsigned long orc_ip_addr = 0;
+	struct orc_sort_param param;
 #endif
 
 	shstrndx = r2(&ehdr->e_shstrndx);
@@ -259,17 +330,27 @@ static int do_sort(Elf_Ehdr *ehdr,
 			orc_ip_size = s->sh_size;
 			g_orc_ip_table = (int *)((void *)ehdr +
 						   s->sh_offset);
+			orc_ip_addr = s->sh_addr;
 		}
 		if (!strcmp(secstrings + idx, ".orc_unwind")) {
 			orc_size = s->sh_size;
 			g_orc_table = (struct orc_entry *)((void *)ehdr +
 							     s->sh_offset);
 		}
+		if (!strcmp(secstrings + idx, ".orc_lookup")) {
+			param.lookup_table_size = s->sh_size;
+			param.orc_lookup_table = (unsigned int *)
+				((void *)ehdr + s->sh_offset);
+		}
+		if (!strcmp(secstrings + idx, ".text")) {
+			param.text_size = s->sh_size;
+			param.start_ip = s->sh_addr;
+		}
 #endif
 	} /* for loop */
 
 #if defined(SORTTABLE_64) && defined(UNWINDER_ORC_ENABLED)
-	if (!g_orc_ip_table || !g_orc_table) {
+	if (!g_orc_ip_table || !g_orc_table || !param.orc_lookup_table) {
 		fprintf(stderr,
 			"incomplete ORC unwind tables in file: %s\n", fname);
 		goto out;
@@ -285,9 +366,13 @@ static int do_sort(Elf_Ehdr *ehdr,
 		goto out;
 	}
 
+	/* Make orc_ip return virtual address at execution. */
+	orc_ip_table_offset = orc_ip_addr - (unsigned long)g_orc_ip_table;
+
 	/* create thread to sort ORC unwind tables concurrently */
+	param.orc_num_entries = orc_num_entries;
 	if (pthread_create(&orc_sort_thread, NULL,
-			   sort_orctable, &orc_ip_size)) {
+			   sort_orctable, &param)) {
 		fprintf(stderr,
 			"pthread_create orc_sort_thread failed '%s': %s\n",
 			strerror(errno), fname);
-- 
2.14.4.44.g2045bb6