oprofile 0.9.6
Copy in the rest of the oprofile 0.9.6 tree so we have a source
copy to match the prebuilt binaries that are checked into
external/.
Change-Id: Iaac327571d5d583594a4194973bf256569061048
diff --git a/opjitconv/jitsymbol.c b/opjitconv/jitsymbol.c
new file mode 100644
index 0000000..1aa6db1
--- /dev/null
+++ b/opjitconv/jitsymbol.c
@@ -0,0 +1,555 @@
+/**
+ * @file jitsymbol.c
+ * Handle symbols found in jitted code dump
+ *
+ * @remark Copyright 2007 OProfile authors
+ * @remark Read the file COPYING
+ *
+ * @author Jens Wilke
+ * @Modifications Maynard Johnson
+ * @Modifications Philippe Elie
+ * @Modifications Daniel Hansel
+ *
+ * Copyright IBM Corporation 2007
+ *
+ */
+
+#include "opjitconv.h"
+#include "opd_printf.h"
+#include "op_libiberty.h"
+#include "op_types.h"
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+#include <limits.h>
+
+typedef int (*compare_symbol)(void const *, void const *);
+
+
+/* count the entries in the jitentry_list */
+static u32 count_entries(void)
+{
+ struct jitentry const * entry;
+ u32 cnt = 0;
+ for (entry = jitentry_list; entry; entry = entry->next)
+ cnt++;
+ return cnt;
+}
+
+
+static void fill_entry_array(struct jitentry * entries[])
+{
+ int i = 0;
+ struct jitentry * entry;
+ for (entry = jitentry_list; entry; entry = entry->next)
+ entries[i++] = entry;
+}
+
+
+/* create an array pointing to the jitentry structures which is sorted
+ * according to the comparator rule given by parameter compar
+ */
+static struct jitentry ** create_sorted_array(compare_symbol compare)
+{
+ struct jitentry ** array =
+ xmalloc(sizeof(struct jitentry *) * entry_count);
+ fill_entry_array(array);
+ qsort(array, entry_count, sizeof(struct jitentry *), compare);
+ return array;
+}
+
+
+/* comparator method for qsort which sorts jitentries by symbol_name */
+static int cmp_symbolname(void const * a, void const * b)
+{
+ struct jitentry * a0 = *(struct jitentry **) a;
+ struct jitentry * b0 = *(struct jitentry **) b;
+ return strcmp(a0->symbol_name, b0->symbol_name);
+}
+
+
+/* comparator method for qsort which sorts jitentries by address */
+static int cmp_address(void const * a, void const * b)
+{
+ struct jitentry * a0 = *(struct jitentry **) a;
+ struct jitentry * b0 = *(struct jitentry **) b;
+ if (a0->vma < b0->vma)
+ return -1;
+ if (a0->vma == b0->vma)
+ return 0;
+ return 1;
+}
+
+
+/* resort address_ascending array */
+static void resort_address(void)
+{
+ u32 i;
+
+ qsort(entries_address_ascending, entry_count,
+ sizeof(struct jitentry *), cmp_address);
+
+ // lower entry_count if entries are invalidated
+ for (i = 0; i < entry_count; ++i) {
+ if (entries_address_ascending[i]->vma)
+ break;
+ }
+
+ if (i) {
+ entry_count -= i;
+ memmove(&entries_address_ascending[0],
+ &entries_address_ascending[i],
+ sizeof(struct jitentry *) * entry_count);
+ }
+}
+
+
+/* Copy address_ascending array to entries_symbols_ascending and resort it. */
+static void resort_symbol(void)
+{
+ memcpy(entries_symbols_ascending, entries_address_ascending,
+ sizeof(struct jitentry *) * entry_count);
+ qsort(entries_symbols_ascending, entry_count,
+ sizeof(struct jitentry *), cmp_symbolname);
+}
+
+/* allocate, populate and sort the jitentry arrays */
+void create_arrays(void)
+{
+ max_entry_count = entry_count = count_entries();
+ entries_symbols_ascending = create_sorted_array(cmp_symbolname);
+ entries_address_ascending = create_sorted_array(cmp_address);
+}
+
+
+/* add a new create jitentry to the array. mallocs new arrays if space is
+ * needed */
+static void insert_entry(struct jitentry * entry)
+{
+ if (entry_count == max_entry_count) {
+ if (max_entry_count < UINT32_MAX - 18)
+ max_entry_count += 18;
+ else if (max_entry_count < UINT32_MAX)
+ max_entry_count += 1;
+ else {
+ fprintf(stderr, "Amount of JIT dump file entries is too large.\n");
+ exit(EXIT_FAILURE);
+ }
+ entries_symbols_ascending = (struct jitentry **)
+ xrealloc(entries_symbols_ascending,
+ sizeof(struct jitentry *) * max_entry_count);
+ entries_address_ascending = (struct jitentry **)
+ xrealloc(entries_address_ascending,
+ sizeof(struct jitentry *) * max_entry_count);
+ }
+ entries_address_ascending[entry_count++] = entry;
+}
+
+
+/* add a suffix to the name to differenciate it */
+static char * replacement_name(char * s, int i)
+{
+ int cnt = 1;
+ int j = i;
+ char * res;
+
+ while ((j = j/10))
+ cnt++;
+ cnt += 2 + strlen(s);
+ res = xmalloc(cnt);
+ snprintf(res, cnt, "%s~%i", s, i);
+ return res;
+}
+
+
+/*
+ * Mark the entry so it is not included in the ELF file. We do this by
+ * writing a 0 address as magic vma and sorting
+ * it out later
+ */
+static void invalidate_entry(struct jitentry * e)
+{
+ verbprintf(debug, "invalidate_entry: addr=%llx, name=%s\n",
+ e->vma, e->symbol_name);
+ e->vma = 0;
+}
+
+
+/*
+ * Invalidate all symbols that are not alive at sampling start time.
+ */
+static void invalidate_earlybirds(unsigned long long start_time)
+{
+ u32 i;
+ int flag;
+ struct jitentry * a;
+
+ flag = 0;
+ for (i = 0; i < entry_count; i++) {
+ a = entries_address_ascending[i];
+ if (a->life_end < start_time) {
+ invalidate_entry(a);
+ flag = 1;
+ }
+ }
+ if (flag) {
+ resort_address();
+ resort_symbol();
+ }
+}
+
+
+/* select the symbol with the longest life time in the index range */
+static int select_one(int start_idx, int end_idx)
+{
+ int i;
+ int candidate = OP_JIT_CONV_FAIL;
+ unsigned long long lifetime = 0;
+ unsigned long long x;
+ struct jitentry const * e;
+
+ for (i = start_idx; i <= end_idx; i++) {
+ e = entries_address_ascending[i];
+ x = e->life_end - e->life_start;
+ if (candidate == -1 || x > lifetime) {
+ candidate = i;
+ lifetime = x;
+ }
+ }
+ return candidate;
+}
+
+
+/*
+ * We decided to keep one entry in favor of the other. Instead of dropping
+ * the overlapping entry we split or truncate it to not overlap any more.
+ *
+ * Looking on the address regions, we may have the following situation:
+ *
+ * split: |------------|
+ * keep: |---|
+ *
+ * The split entry may be splitted in a left part and a right part. E.g.:
+ *
+ * split0/1: |--| |---|
+ * keep: |---|
+ *
+ * However, both parts may or may not exist.
+ */
+static void split_entry(struct jitentry * split, struct jitentry const * keep)
+{
+ unsigned long long start_addr_keep = keep->vma;
+ unsigned long long end_addr_keep = keep->vma + keep->code_size;
+ unsigned long long end_addr_split = split->vma + split->code_size;
+ unsigned long long start_addr_split = split->vma;
+
+ // do we need a right part?
+ if (end_addr_split > end_addr_keep) {
+ struct jitentry * new_entry =
+ xcalloc(1, sizeof(struct jitentry));
+ char * s = NULL;
+
+ /* Check for max. length to avoid possible integer overflow. */
+ if (strlen(split->symbol_name) > SIZE_MAX - 3) {
+ fprintf(stderr, "Length of symbol name is too large.\n");
+ exit(EXIT_FAILURE);
+ } else {
+ s = xmalloc(strlen(split->symbol_name) + 3);
+ strcpy(s, split->symbol_name);
+ strcat(s, "#1");
+ }
+
+ new_entry->vma = end_addr_keep;
+ new_entry->code_size = end_addr_split - end_addr_keep;
+ new_entry->symbol_name = s;
+ new_entry->sym_name_malloced = 1;
+ new_entry->life_start = split->life_start;
+ new_entry->life_end = split->life_end;
+ // the right part does not have an associated code, because we
+ // don't know whether the split part begins at an opcode
+ new_entry->code = NULL;
+ verbprintf(debug, "split right (new) name=%s, start=%llx,"
+ " end=%llx\n", new_entry->symbol_name,
+ new_entry->vma,
+ new_entry->vma + new_entry->code_size);
+ insert_entry(new_entry);
+ }
+ // do we need a left part?
+ if (start_addr_split < start_addr_keep) {
+ char * s = NULL;
+
+ /* Check for max. length to avoid possible integer overflow. */
+ if (strlen(split->symbol_name) > SIZE_MAX - 3) {
+ fprintf(stderr, "Length of symbol name is too large.\n");
+ exit(EXIT_FAILURE);
+ } else {
+ s = xmalloc(strlen(split->symbol_name) + 3);
+ strcpy(s, split->symbol_name);
+ strcat(s, "#0");
+ }
+
+ split->code_size = start_addr_keep - start_addr_split;
+ if (split->sym_name_malloced)
+ free(split->symbol_name);
+ split->symbol_name = s;
+ split->sym_name_malloced = 1;
+ verbprintf(debug, "split left name=%s, start=%llx, end=%llx\n",
+ split->symbol_name, split->vma,
+ split->vma + split->code_size);
+ } else {
+ invalidate_entry(split);
+ }
+}
+
+
+/*
+ * Scans through the index range and splits/truncates entries that overlap
+ * with the one indexed by keep_idx. Returns the total lifetime of the symbols
+ * found to overlap.
+ * Returns ULONG_MAX on error.
+ */
+static unsigned long long eliminate_overlaps(int start_idx, int end_idx,
+ int keep_idx)
+{
+ unsigned long long retval;
+ struct jitentry const * keep = entries_address_ascending[keep_idx];
+ struct jitentry * e;
+ unsigned long long start_addr_keep = keep->vma;
+ unsigned long long end_addr_keep = keep->vma + keep->code_size;
+ unsigned long long start_addr_entry, end_addr_entry;
+ int i;
+ unsigned long long min_start = keep->life_start;
+ unsigned long long max_end = keep->life_end;
+
+ for (i = start_idx; i <= end_idx; i++) {
+ if (i == keep_idx)
+ continue;
+ e = entries_address_ascending[i];
+ start_addr_entry = e->vma;
+ end_addr_entry = e->vma + e->code_size;
+ if (debug) {
+ if (!(start_addr_entry <= end_addr_entry)) {
+ verbprintf(debug, "assert failed:"
+ " start_addr_entry <="
+ " end_addr_entry\n");
+ retval = ULONG_MAX;
+ goto out;
+ }
+ if (!(start_addr_keep <= end_addr_keep)) {
+ verbprintf(debug, "assert failed: "
+ "start_addr_keep <="
+ " end_addr_keep\n");
+ retval = ULONG_MAX;
+ goto out;
+ }
+ }
+ if (start_addr_entry < end_addr_keep &&
+ end_addr_entry > start_addr_keep) {
+ if (e->life_start < min_start)
+ min_start = e->life_start;
+ if (e->life_end > max_end)
+ max_end = e->life_end;
+ split_entry(e, keep);
+ }
+ }
+ retval = max_end - min_start;
+out:
+ return retval;
+}
+
+
+/*
+ * Within the index range (into the array entries_address_ascending), find the
+ * symbol with the maximal lifetime and split/truncate all symbols that overlap
+ * with it (i.e. that there won't be any overlaps anymore).
+ */
+static int handle_overlap_region(int start_idx, int end_idx)
+{
+ int rc = OP_JIT_CONV_OK;
+ int idx;
+ struct jitentry * e;
+ int cnt;
+ char * name;
+ int i, j;
+ unsigned long long totaltime;
+
+ if (debug) {
+ for (i = start_idx; i <= end_idx; i++) {
+ e = entries_address_ascending[i];
+ verbprintf(debug, "overlap idx=%i, name=%s, "
+ "start=%llx, end=%llx, life_start=%lli, "
+ "life_end=%lli, lifetime=%lli\n",
+ i, e->symbol_name, e->vma,
+ e->vma + e->code_size, e->life_start,
+ e->life_end, e->life_end - e->life_start);
+ }
+ }
+ idx = select_one(start_idx, end_idx);
+ totaltime = eliminate_overlaps(start_idx, end_idx, idx);
+ if (totaltime == ULONG_MAX) {
+ rc = OP_JIT_CONV_FAIL;
+ goto out;
+ }
+ e = entries_address_ascending[idx];
+
+ cnt = 1;
+ j = (e->life_end - e->life_start) * 100 / totaltime;
+ while ((j = j/10))
+ cnt++;
+
+ // Mark symbol name with a %% to indicate the overlap.
+ cnt += strlen(e->symbol_name) + 2 + 1;
+ name = xmalloc(cnt);
+ snprintf(name, cnt, "%s%%%llu", e->symbol_name,
+ (e->life_end - e->life_start) * 100 / totaltime);
+ if (e->sym_name_malloced)
+ free(e->symbol_name);
+ e->symbol_name = name;
+ e->sym_name_malloced = 1;
+ verbprintf(debug, "selected idx=%i, name=%s\n", idx, e->symbol_name);
+out:
+ return rc;
+}
+
+
+/*
+ * one scan through the symbols to find overlaps.
+ * return 1 if an overlap is found. this is repeated until no more overlap
+ * is there.
+ * Process: There may be more than two overlapping symbols with each other.
+ * The index range of symbols found to overlap are passed to
+ * handle_overlap_region.
+ */
+static int scan_overlaps(void)
+{
+ int i, j;
+ unsigned long long end_addr, end_addr2;
+ struct jitentry const * a;
+ int flag = 0;
+ // entry_count can be incremented by split_entry() during the loop,
+ // save the inital value as loop count
+ int loop_count = entry_count;
+
+ verbprintf(debug,"count=%i, scan overlaps...\n", entry_count);
+ i = 0;
+ end_addr = 0;
+ for (j = 1; j < loop_count; j++) {
+ /**
+ * Take a symbol [i] and look for the next symbol(s) [j] that are overlapping
+ * symbol [i]. If a symbol [j] is found that is not overlapping symbol [i] the
+ * symbols [i]..[j-1] are handled to be not overlapping anymore.
+ * See descriptions of handle_overlap_region() and eliminate_overlaps() for
+ * further details of this handling.
+ * E.g. possible cases to be handled could be:
+ *
+ * sym1 |-----------|
+ * sym2 |---|
+ *
+ * sym1 |--------|
+ * sym2 |--------|
+ *
+ * sym1 |--------|
+ * sym2 |-------|
+ * sym3 |---------|
+ *
+ * But in the following case
+ *
+ * sym1 |--------|
+ * sym2 |-------------|
+ * sym3 |----------|
+ *
+ * sym3 would not overlap with sym1. Therefore handle_overlap_regio() would
+ * only be called for sym1 up to sym2.
+ */
+ a = entries_address_ascending[j - 1];
+ end_addr2 = a->vma + a->code_size;
+ if (end_addr2 > end_addr)
+ end_addr = end_addr2;
+ a = entries_address_ascending[j];
+ if (end_addr <= a->vma) {
+ if (i != j - 1) {
+ if (handle_overlap_region(i, j - 1) ==
+ OP_JIT_CONV_FAIL) {
+ flag = OP_JIT_CONV_FAIL;
+ goto out;
+ }
+ flag = 1;
+ }
+ i = j;
+ }
+ }
+ if (i != j - 1) {
+ if (handle_overlap_region(i, j - 1) == OP_JIT_CONV_FAIL)
+ flag = OP_JIT_CONV_FAIL;
+ else
+ flag = 1;
+ }
+out:
+ return flag;
+}
+
+
+/* search for symbols that have overlapping address ranges and decide for
+ * one */
+int resolve_overlaps(unsigned long long start_time)
+{
+ int rc = OP_JIT_CONV_OK;
+ int cnt = 0;
+
+ invalidate_earlybirds(start_time);
+ while ((rc = scan_overlaps()) && rc != OP_JIT_CONV_FAIL) {
+ resort_address();
+ if (cnt == 0) {
+ verbprintf(debug, "WARNING: overlaps detected. "
+ "Removing overlapping JIT methods\n");
+ }
+ cnt++;
+ }
+ if (cnt > 0 && rc != OP_JIT_CONV_FAIL)
+ resort_symbol();
+ return rc;
+}
+
+
+/*
+ * scan through the sorted array and replace identical symbol names by unique
+ * ones by adding a counter value.
+ */
+void disambiguate_symbol_names(void)
+{
+ u32 j;
+ int cnt, rep_cnt;
+ struct jitentry * a;
+ struct jitentry * b;
+
+ rep_cnt = 0;
+ for (j = 1; j < entry_count; j++) {
+ a = entries_symbols_ascending[j - 1];
+ cnt = 1;
+ do {
+ b = entries_symbols_ascending[j];
+ if (strcmp(a->symbol_name, b->symbol_name) == 0) {
+ if (b->sym_name_malloced)
+ free(b->symbol_name);
+ b->symbol_name =
+ replacement_name(a->symbol_name, cnt);
+ b->sym_name_malloced = 1;
+ j++;
+ cnt++;
+ rep_cnt++;
+ } else {
+ break;
+ }
+ } while (j < entry_count);
+ }
+ /* recurse to avoid that the added suffix also creates a collision */
+ if (rep_cnt) {
+ qsort(entries_symbols_ascending, entry_count,
+ sizeof(struct jitentry *), cmp_symbolname);
+ disambiguate_symbol_names();
+ }
+}