@@ -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, ¶m)) {
fprintf(stderr,
"pthread_create orc_sort_thread failed '%s': %s\n",
strerror(errno), fname);