18cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/** 28cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @file jitsymbol.c 38cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Handle symbols found in jitted code dump 48cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 58cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Copyright 2007 OProfile authors 68cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Read the file COPYING 78cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 88cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @author Jens Wilke 98cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @Modifications Maynard Johnson 108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @Modifications Philippe Elie 118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @Modifications Daniel Hansel 128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Copyright IBM Corporation 2007 148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "opjitconv.h" 188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "opd_printf.h" 198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "op_libiberty.h" 208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "op_types.h" 218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <stddef.h> 238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <stdlib.h> 248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <stdint.h> 258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <stdio.h> 268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <string.h> 278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <unistd.h> 288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <limits.h> 298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddtypedef int (*compare_symbol)(void const *, void const *); 318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* count the entries in the jitentry_list */ 348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic u32 count_entries(void) 358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry const * entry; 378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd u32 cnt = 0; 388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (entry = jitentry_list; entry; entry = entry->next) 398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt++; 408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return cnt; 418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic void fill_entry_array(struct jitentry * entries[]) 458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int i = 0; 478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * entry; 488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (entry = jitentry_list; entry; entry = entry->next) 498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd entries[i++] = entry; 508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* create an array pointing to the jitentry structures which is sorted 548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * according to the comparator rule given by parameter compar 558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic struct jitentry ** create_sorted_array(compare_symbol compare) 578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry ** array = 598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd xmalloc(sizeof(struct jitentry *) * entry_count); 608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd fill_entry_array(array); 618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd qsort(array, entry_count, sizeof(struct jitentry *), compare); 628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return array; 638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* comparator method for qsort which sorts jitentries by symbol_name */ 678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic int cmp_symbolname(void const * a, void const * b) 688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * a0 = *(struct jitentry **) a; 708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * b0 = *(struct jitentry **) b; 718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return strcmp(a0->symbol_name, b0->symbol_name); 728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* comparator method for qsort which sorts jitentries by address */ 768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic int cmp_address(void const * a, void const * b) 778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * a0 = *(struct jitentry **) a; 798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * b0 = *(struct jitentry **) b; 808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (a0->vma < b0->vma) 818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return -1; 828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (a0->vma == b0->vma) 838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return 0; 848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return 1; 858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* resort address_ascending array */ 898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic void resort_address(void) 908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd u32 i; 928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd qsort(entries_address_ascending, entry_count, 948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sizeof(struct jitentry *), cmp_address); 958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // lower entry_count if entries are invalidated 978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (i = 0; i < entry_count; ++i) { 988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (entries_address_ascending[i]->vma) 998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd break; 1008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 1018cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1028cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (i) { 1038cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd entry_count -= i; 1048cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd memmove(&entries_address_ascending[0], 1058cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd &entries_address_ascending[i], 1068cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sizeof(struct jitentry *) * entry_count); 1078cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 1088cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 1098cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* Copy address_ascending array to entries_symbols_ascending and resort it. */ 1128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic void resort_symbol(void) 1138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 1148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd memcpy(entries_symbols_ascending, entries_address_ascending, 1158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sizeof(struct jitentry *) * entry_count); 1168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd qsort(entries_symbols_ascending, entry_count, 1178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sizeof(struct jitentry *), cmp_symbolname); 1188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 1198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* allocate, populate and sort the jitentry arrays */ 1218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddvoid create_arrays(void) 1228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 1238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd max_entry_count = entry_count = count_entries(); 1248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd entries_symbols_ascending = create_sorted_array(cmp_symbolname); 1258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd entries_address_ascending = create_sorted_array(cmp_address); 1268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 1278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* add a new create jitentry to the array. mallocs new arrays if space is 1308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * needed */ 1318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic void insert_entry(struct jitentry * entry) 1328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 1338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (entry_count == max_entry_count) { 1348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (max_entry_count < UINT32_MAX - 18) 1358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd max_entry_count += 18; 1368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd else if (max_entry_count < UINT32_MAX) 1378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd max_entry_count += 1; 1388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd else { 1398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd fprintf(stderr, "Amount of JIT dump file entries is too large.\n"); 1408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd exit(EXIT_FAILURE); 1418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 1428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd entries_symbols_ascending = (struct jitentry **) 1438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd xrealloc(entries_symbols_ascending, 1448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sizeof(struct jitentry *) * max_entry_count); 1458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd entries_address_ascending = (struct jitentry **) 1468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd xrealloc(entries_address_ascending, 1478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sizeof(struct jitentry *) * max_entry_count); 1488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 1498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd entries_address_ascending[entry_count++] = entry; 1508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 1518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* add a suffix to the name to differenciate it */ 1548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic char * replacement_name(char * s, int i) 1558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 1568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int cnt = 1; 1578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int j = i; 1588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd char * res; 1598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd while ((j = j/10)) 1618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt++; 1628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt += 2 + strlen(s); 1638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd res = xmalloc(cnt); 1648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd snprintf(res, cnt, "%s~%i", s, i); 1658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return res; 1668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 1678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* 1708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Mark the entry so it is not included in the ELF file. We do this by 1718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * writing a 0 address as magic vma and sorting 1728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * it out later 1738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 1748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic void invalidate_entry(struct jitentry * e) 1758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 1768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug, "invalidate_entry: addr=%llx, name=%s\n", 1778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e->vma, e->symbol_name); 1788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e->vma = 0; 1798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 1808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* 1838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Invalidate all symbols that are not alive at sampling start time. 1848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 1858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic void invalidate_earlybirds(unsigned long long start_time) 1868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 1878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd u32 i; 1888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int flag; 1898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * a; 1908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd flag = 0; 1928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (i = 0; i < entry_count; i++) { 1938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd a = entries_address_ascending[i]; 1948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (a->life_end < start_time) { 1958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd invalidate_entry(a); 1968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd flag = 1; 1978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 1988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 1998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (flag) { 2008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd resort_address(); 2018cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd resort_symbol(); 2028cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 2038cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 2048cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2058cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2068cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* select the symbol with the longest life time in the index range */ 2078cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic int select_one(int start_idx, int end_idx) 2088cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 2098cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int i; 2108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int candidate = OP_JIT_CONV_FAIL; 2118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long lifetime = 0; 2128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long x; 2138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry const * e; 2148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (i = start_idx; i <= end_idx; i++) { 2168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e = entries_address_ascending[i]; 2178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd x = e->life_end - e->life_start; 2188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (candidate == -1 || x > lifetime) { 2198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd candidate = i; 2208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd lifetime = x; 2218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 2228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 2238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return candidate; 2248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 2258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* 2288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * We decided to keep one entry in favor of the other. Instead of dropping 2298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * the overlapping entry we split or truncate it to not overlap any more. 2308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 2318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Looking on the address regions, we may have the following situation: 2328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 2338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * split: |------------| 2348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * keep: |---| 2358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 2368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * The split entry may be splitted in a left part and a right part. E.g.: 2378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 2388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * split0/1: |--| |---| 2398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * keep: |---| 2408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 2418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * However, both parts may or may not exist. 2428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 2438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic void split_entry(struct jitentry * split, struct jitentry const * keep) 2448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 2458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long start_addr_keep = keep->vma; 2468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long end_addr_keep = keep->vma + keep->code_size; 2478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long end_addr_split = split->vma + split->code_size; 2488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long start_addr_split = split->vma; 2498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // do we need a right part? 2518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (end_addr_split > end_addr_keep) { 2528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * new_entry = 2538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd xcalloc(1, sizeof(struct jitentry)); 2548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd char * s = NULL; 2558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /* Check for max. length to avoid possible integer overflow. */ 2578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (strlen(split->symbol_name) > SIZE_MAX - 3) { 2588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd fprintf(stderr, "Length of symbol name is too large.\n"); 2598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd exit(EXIT_FAILURE); 2608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } else { 2618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd s = xmalloc(strlen(split->symbol_name) + 3); 2628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd strcpy(s, split->symbol_name); 2638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd strcat(s, "#1"); 2648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 2658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->vma = end_addr_keep; 2678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->code_size = end_addr_split - end_addr_keep; 2688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->symbol_name = s; 2698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->sym_name_malloced = 1; 2708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->life_start = split->life_start; 2718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->life_end = split->life_end; 2728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // the right part does not have an associated code, because we 2738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // don't know whether the split part begins at an opcode 2748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->code = NULL; 2758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug, "split right (new) name=%s, start=%llx," 2768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd " end=%llx\n", new_entry->symbol_name, 2778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->vma, 2788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd new_entry->vma + new_entry->code_size); 2798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd insert_entry(new_entry); 2808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 2818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // do we need a left part? 2828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (start_addr_split < start_addr_keep) { 2838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd char * s = NULL; 2848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /* Check for max. length to avoid possible integer overflow. */ 2868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (strlen(split->symbol_name) > SIZE_MAX - 3) { 2878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd fprintf(stderr, "Length of symbol name is too large.\n"); 2888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd exit(EXIT_FAILURE); 2898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } else { 2908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd s = xmalloc(strlen(split->symbol_name) + 3); 2918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd strcpy(s, split->symbol_name); 2928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd strcat(s, "#0"); 2938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 2948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 2958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd split->code_size = start_addr_keep - start_addr_split; 2968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (split->sym_name_malloced) 2978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd free(split->symbol_name); 2988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd split->symbol_name = s; 2998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd split->sym_name_malloced = 1; 3008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug, "split left name=%s, start=%llx, end=%llx\n", 3018cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd split->symbol_name, split->vma, 3028cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd split->vma + split->code_size); 3038cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } else { 3048cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd invalidate_entry(split); 3058cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3068cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 3078cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 3088cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 3098cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* 3108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Scans through the index range and splits/truncates entries that overlap 3118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * with the one indexed by keep_idx. Returns the total lifetime of the symbols 3128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * found to overlap. 3138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Returns ULONG_MAX on error. 3148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 3158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic unsigned long long eliminate_overlaps(int start_idx, int end_idx, 3168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int keep_idx) 3178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 3188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long retval; 3198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry const * keep = entries_address_ascending[keep_idx]; 3208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * e; 3218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long start_addr_keep = keep->vma; 3228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long end_addr_keep = keep->vma + keep->code_size; 3238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long start_addr_entry, end_addr_entry; 3248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int i; 3258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long min_start = keep->life_start; 3268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long max_end = keep->life_end; 3278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 3288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (i = start_idx; i <= end_idx; i++) { 3298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (i == keep_idx) 3308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd continue; 3318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e = entries_address_ascending[i]; 3328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd start_addr_entry = e->vma; 3338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd end_addr_entry = e->vma + e->code_size; 3348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (debug) { 3358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (!(start_addr_entry <= end_addr_entry)) { 3368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug, "assert failed:" 3378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd " start_addr_entry <=" 3388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd " end_addr_entry\n"); 3398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd retval = ULONG_MAX; 3408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd goto out; 3418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (!(start_addr_keep <= end_addr_keep)) { 3438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug, "assert failed: " 3448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd "start_addr_keep <=" 3458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd " end_addr_keep\n"); 3468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd retval = ULONG_MAX; 3478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd goto out; 3488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (start_addr_entry < end_addr_keep && 3518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd end_addr_entry > start_addr_keep) { 3528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (e->life_start < min_start) 3538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd min_start = e->life_start; 3548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (e->life_end > max_end) 3558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd max_end = e->life_end; 3568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd split_entry(e, keep); 3578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd retval = max_end - min_start; 3608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddout: 3618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return retval; 3628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 3638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 3648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 3658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* 3668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Within the index range (into the array entries_address_ascending), find the 3678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * symbol with the maximal lifetime and split/truncate all symbols that overlap 3688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * with it (i.e. that there won't be any overlaps anymore). 3698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 3708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic int handle_overlap_region(int start_idx, int end_idx) 3718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 3728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int rc = OP_JIT_CONV_OK; 3738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int idx; 3748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * e; 3758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int cnt; 3768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd char * name; 3778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int i, j; 3788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long totaltime; 3798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 3808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (debug) { 3818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (i = start_idx; i <= end_idx; i++) { 3828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e = entries_address_ascending[i]; 3838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug, "overlap idx=%i, name=%s, " 3848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd "start=%llx, end=%llx, life_start=%lli, " 3858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd "life_end=%lli, lifetime=%lli\n", 3868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd i, e->symbol_name, e->vma, 3878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e->vma + e->code_size, e->life_start, 3888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e->life_end, e->life_end - e->life_start); 3898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd idx = select_one(start_idx, end_idx); 3928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd totaltime = eliminate_overlaps(start_idx, end_idx, idx); 3938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (totaltime == ULONG_MAX) { 3948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd rc = OP_JIT_CONV_FAIL; 3958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd goto out; 3968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 3978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e = entries_address_ascending[idx]; 3988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 3998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt = 1; 4008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd j = (e->life_end - e->life_start) * 100 / totaltime; 4018cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd while ((j = j/10)) 4028cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt++; 4038cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 4048cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // Mark symbol name with a %% to indicate the overlap. 4058cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt += strlen(e->symbol_name) + 2 + 1; 4068cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd name = xmalloc(cnt); 4078cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd snprintf(name, cnt, "%s%%%llu", e->symbol_name, 4088cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd (e->life_end - e->life_start) * 100 / totaltime); 4098cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (e->sym_name_malloced) 4108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd free(e->symbol_name); 4118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e->symbol_name = name; 4128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd e->sym_name_malloced = 1; 4138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug, "selected idx=%i, name=%s\n", idx, e->symbol_name); 4148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddout: 4158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return rc; 4168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 4178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 4188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 4198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* 4208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * one scan through the symbols to find overlaps. 4218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * return 1 if an overlap is found. this is repeated until no more overlap 4228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * is there. 4238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Process: There may be more than two overlapping symbols with each other. 4248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * The index range of symbols found to overlap are passed to 4258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * handle_overlap_region. 4268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 4278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddstatic int scan_overlaps(void) 4288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 4298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int i, j; 4308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd unsigned long long end_addr, end_addr2; 4318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry const * a; 4328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int flag = 0; 4338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // entry_count can be incremented by split_entry() during the loop, 4348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd // save the inital value as loop count 4358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int loop_count = entry_count; 4368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 4378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug,"count=%i, scan overlaps...\n", entry_count); 4388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd i = 0; 4398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd end_addr = 0; 4408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (j = 1; j < loop_count; j++) { 4418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 4428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Take a symbol [i] and look for the next symbol(s) [j] that are overlapping 4438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * symbol [i]. If a symbol [j] is found that is not overlapping symbol [i] the 4448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * symbols [i]..[j-1] are handled to be not overlapping anymore. 4458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * See descriptions of handle_overlap_region() and eliminate_overlaps() for 4468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * further details of this handling. 4478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * E.g. possible cases to be handled could be: 4488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 4498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym1 |-----------| 4508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym2 |---| 4518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 4528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym1 |--------| 4538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym2 |--------| 4548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 4558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym1 |--------| 4568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym2 |-------| 4578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym3 |---------| 4588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 4598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * But in the following case 4608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 4618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym1 |--------| 4628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym2 |-------------| 4638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym3 |----------| 4648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 4658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sym3 would not overlap with sym1. Therefore handle_overlap_regio() would 4668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * only be called for sym1 up to sym2. 4678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 4688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd a = entries_address_ascending[j - 1]; 4698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd end_addr2 = a->vma + a->code_size; 4708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (end_addr2 > end_addr) 4718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd end_addr = end_addr2; 4728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd a = entries_address_ascending[j]; 4738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (end_addr <= a->vma) { 4748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (i != j - 1) { 4758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (handle_overlap_region(i, j - 1) == 4768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd OP_JIT_CONV_FAIL) { 4778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd flag = OP_JIT_CONV_FAIL; 4788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd goto out; 4798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 4808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd flag = 1; 4818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 4828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd i = j; 4838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 4848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 4858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (i != j - 1) { 4868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (handle_overlap_region(i, j - 1) == OP_JIT_CONV_FAIL) 4878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd flag = OP_JIT_CONV_FAIL; 4888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd else 4898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd flag = 1; 4908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 4918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddout: 4928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return flag; 4938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 4948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 4958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 4968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* search for symbols that have overlapping address ranges and decide for 4978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * one */ 4988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddint resolve_overlaps(unsigned long long start_time) 4998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 5008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int rc = OP_JIT_CONV_OK; 5018cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int cnt = 0; 5028cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 5038cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd invalidate_earlybirds(start_time); 5048cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd while ((rc = scan_overlaps()) && rc != OP_JIT_CONV_FAIL) { 5058cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd resort_address(); 5068cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (cnt == 0) { 5078cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd verbprintf(debug, "WARNING: overlaps detected. " 5088cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd "Removing overlapping JIT methods\n"); 5098cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 5108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt++; 5118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 5128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (cnt > 0 && rc != OP_JIT_CONV_FAIL) 5138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd resort_symbol(); 5148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return rc; 5158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 5168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 5178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 5188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* 5198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * scan through the sorted array and replace identical symbol names by unique 5208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * ones by adding a counter value. 5218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 5228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddvoid disambiguate_symbol_names(void) 5238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd{ 5248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd u32 j; 5258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd int cnt, rep_cnt; 5268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * a; 5278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd struct jitentry * b; 5288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 5298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd rep_cnt = 0; 5308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (j = 1; j < entry_count; j++) { 5318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd a = entries_symbols_ascending[j - 1]; 5328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt = 1; 5338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd do { 5348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd b = entries_symbols_ascending[j]; 5358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (strcmp(a->symbol_name, b->symbol_name) == 0) { 5368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (b->sym_name_malloced) 5378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd free(b->symbol_name); 5388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd b->symbol_name = 5398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd replacement_name(a->symbol_name, cnt); 5408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd b->sym_name_malloced = 1; 5418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd j++; 5428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd cnt++; 5438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd rep_cnt++; 5448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } else { 5458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd break; 5468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 5478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } while (j < entry_count); 5488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 5498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /* recurse to avoid that the added suffix also creates a collision */ 5508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (rep_cnt) { 5518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd qsort(entries_symbols_ascending, entry_count, 5528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sizeof(struct jitentry *), cmp_symbolname); 5538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd disambiguate_symbol_names(); 5548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 5558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd} 556