jitsymbol.c

Go to the documentation of this file.

#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++) {
        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();
    }
}