sysperfana/perfinvestigator/com.nokia.carbide.cpp.pi/src/com/nokia/carbide/cpp/internal/pi/resolvers/CachedFunctionResolver.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/sysperfana/perfinvestigator/com.nokia.carbide.cpp.pi/src/com/nokia/carbide/cpp/internal/pi/resolvers/CachedFunctionResolver.java Thu Feb 11 15:32:31 2010 +0200
@@ -0,0 +1,475 @@
+/*
+ * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies).
+ * All rights reserved.
+ * This component and the accompanying materials are made available
+ * under the terms of the License "Eclipse Public License v1.0"
+ * which accompanies this distribution, and is available
+ * at the URL "http://www.eclipse.org/legal/epl-v10.html".
+ *
+ * Initial Contributors:
+ * Nokia Corporation - initial contribution.
+ *
+ * Contributors:
+ *
+ * Description:
+ *
+ */
+
+package com.nokia.carbide.cpp.internal.pi.resolvers;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Hashtable;
+
+import com.nokia.carbide.cpp.internal.pi.model.Binary;
+import com.nokia.carbide.cpp.internal.pi.model.Function;
+import com.nokia.carbide.cpp.internal.pi.model.FunctionResolver;
+
+
+// re-implement SymbolFileParser for supporting
+// cached resolver with ROFS symbols
+
+public abstract class CachedFunctionResolver implements FunctionResolver {
+
+ protected SymbolFileDllItem[] dllList = null;
+
+ // cache
+ private int cacheSize = 0;
+ private long cacheAddressTable[] = new long[cacheSize];
+ private long mostPopularCache[] = new long[cacheSize];
+ private SymbolFileFunctionItem[] cacheOrderTable = new SymbolFileFunctionItem[cacheSize];
+ private SymbolFileFunctionItem[] mostPopularCacheTable = new SymbolFileFunctionItem[cacheSize];
+ //private int mostPopularHitCount[] = new int[cacheSize];
+ private int mostPopularTableIndex = 0;
+ private int cacheIndex = 0;
+ //private int cacheFoundPopular = 0;
+ //private int cacheFound = 0;
+ //private int cacheNotFound = 0;
+
+ // whether the resolver has enough information to resolve anything
+ protected boolean ableToResolve = false;
+
+ private Hashtable<String,Function> knownFunctions = new Hashtable<String,Function>();
+ private Hashtable<String,Binary> knownBinaries = new Hashtable<String,Binary>();
+
+ protected static class SymbolFileFunctionItem
+ {
+ public String name;
+ public long address;
+ public long length;
+ public SymbolFileDllItem dll;
+
+ public SymbolFileFunctionItem(String name, long address, long length, SymbolFileDllItem dll)
+ {
+ this.name = name;
+ this.length = length;
+ this.address = address;
+ this.dll = dll;
+ }
+ }
+
+ protected static class SymbolFileDllItem
+ {
+ public String name;
+ public long start;
+ public long end;
+ public ArrayList<SymbolFileFunctionItem> data;
+ public boolean uninitialised;
+
+ public SymbolFileDllItem()
+ {
+ start = 0;
+ end = 0;
+ name = null;
+ data = new ArrayList<SymbolFileFunctionItem>();
+ uninitialised = true;
+ }
+ }
+
+ // must implement some way to form a DLL list e.g. read rom/rofs symbol file, read obyfile
+ public abstract void parseAndProcessSymbolFile(java.io.File symbolFile);
+
+ public void addAllToDllList(Collection<SymbolFileDllItem> list) {
+
+ // if the dll array is empty, create an array based on the input list
+ if (dllList == null) {
+ dllList = new SymbolFileDllItem[list.size()];
+ dllList = list.toArray(dllList);
+ } else {
+ // add the input list to the existing dll array
+ SymbolFileDllItem[] oldList = dllList;
+ Object[] objects = list.toArray();
+
+ dllList = new SymbolFileDllItem[dllList.length + list.size()];
+
+ int i = 0;
+ for (int j = 0; j < oldList.length; j++)
+ dllList[i++] = oldList[j];
+
+ for (int j = 0; j < list.size(); j++)
+ dllList[i++] = (SymbolFileDllItem) objects[j];
+ }
+
+ // sort the dll list
+ Arrays.sort(dllList, new Comparator<Object>() {
+
+ public int compare(Object arg0, Object arg1)
+ {
+ return (int) (((SymbolFileDllItem)arg0).start - ((SymbolFileDllItem)arg1).start);
+ }
+ });
+ }
+
+ public void clearDllList()
+ {
+ dllList = null;
+ }
+
+ public CachedFunctionResolver()
+ {
+ this.clearDllList();
+ this.initializeCache(250);
+ }
+
+ public Binary findBinaryForAddress(long address) {
+ SymbolFileDllItem item = this.getDllItemForAddress(address);
+ if (item != null)
+ {
+ Binary b = this.knownBinaries.get(item.name);
+
+ if (b == null) {
+ b = new Binary(item.name);
+ b.length = (int)(item.end-item.start);
+ b.offsetToCodeStart = 0;
+ b.startAddress = item.start;
+ this.knownBinaries.put(item.name, b);
+ }
+ return b;
+ }
+ else
+ return null;
+// {
+// String bName = "Binary at 0x"+Long.toHexString(address)+" not found;
+//
+// Binary b = this.knownBinaries.get(bName);
+//
+// if (b == null) {
+// b = new Binary(bName);
+// b.length = 0;
+// b.offsetToCodeStart = 0;
+// b.startAddress = address;
+// this.knownBinaries.put(bName, b);
+// }
+// return b;
+// }
+ }
+
+ public String findBinaryNameForAddress(long address) {
+ SymbolFileDllItem foundDllItem = this.getDllItemForAddress(address);
+ if (foundDllItem != null)
+ return foundDllItem.name;
+ else
+ return Messages.getString("CachedFunctionResolver.dllForAddress")+Long.toHexString(address)+Messages.getString("CachedFunctionResolver.notFound"); //$NON-NLS-1$ //$NON-NLS-2$
+ }
+
+ public Function findFunctionForAddress(long address) {
+ SymbolFileFunctionItem item = this.getFunctionItemForAddress(address);
+
+ if (item != null)
+ {
+ String search = item.name + item.dll.name;
+ Function f = this.knownFunctions.get(search);
+
+ if (f == null) {
+ f = new Function(item.name,new Long(item.address),item.dll.name);
+ f.offsetFromBinaryStart = item.address-item.dll.start;
+ f.length = item.length;
+ this.knownFunctions.put(search, f);
+ }
+ return f;
+ }
+ else
+ {
+ //System.out.println(Long.toHexString(address));
+ SymbolFileDllItem dllItem = this.getDllItemForAddress(address);
+
+ if (dllItem != null)
+ {
+ String fName = Messages.getString("CachedFunctionResolver.functionNotFound1")+Long.toHexString(address)+Messages.getString("CachedFunctionResolver.functionNotFound2"); //$NON-NLS-1$ //$NON-NLS-2$
+
+ Function f = this.knownFunctions.get(fName);
+
+ if (f == null ) {
+ f = new Function(fName, new Long(dllItem.start), dllItem.name);
+ f.offsetFromBinaryStart = address-dllItem.start;
+ f.length = 0;
+ this.knownFunctions.put(fName, f);
+ }
+
+ return f;
+ }
+ else
+ return null;
+// {
+// String fName = Messages.getString("CachedFunctionResolver.functionNotFound1")+Long.toHexString(address)+Messages.getString("CachedFunctionResolver.functionNotFound2"); //$NON-NLS-1$ //$NON-NLS-2$
+//
+// Function f = this.knownFunctions.get(fName);
+//
+// if (f == null ) {
+// f = new Function(fName, new Long(address),
+// "Binary at 0x" +
+// Long.toHexString(address)+" not found");
+// f.offsetFromBinaryStart = 0;
+// this.knownFunctions.put(fName, f);
+// }
+//
+// return f;
+// }
+ }
+ }
+
+ public String findFunctionNameForAddress(long address) {
+ SymbolFileFunctionItem item = this.getFunctionItemForAddress(address);
+ if (item != null)
+ {
+ return item.name;
+ }
+ else
+ {
+ return Messages.getString("CachedFunctionResolver.functionForAddress")+Long.toHexString(address)+Messages.getString("CachedFunctionResolver.notFound"); //$NON-NLS-1$ //$NON-NLS-2$
+ }
+ }
+
+ public String getResolverName() {
+ return Messages.getString("CachedFunctionResolver.symbol"); //$NON-NLS-1$
+ }
+
+ public String getResolverString() {
+ return Messages.getString("CachedFunctionResolver.symbolFile"); //$NON-NLS-1$
+ }
+
+ public SymbolFileDllItem getDllItemForAddress(long address)
+ {
+ if (dllList == null)
+ return null;
+
+ for (int i=0; i < this.dllList.length; i++)
+ {
+ SymbolFileDllItem dllItem = this.dllList[i];
+ if (address >= dllItem.start && address < dllItem.end)
+ {
+ return dllItem;
+ }
+ }
+ return null;
+ }
+
+ private void initializeCache(int size)
+ {
+ cacheSize = size;
+
+ cacheAddressTable = new long[cacheSize];
+ mostPopularCache = new long[cacheSize];
+ cacheOrderTable = new SymbolFileFunctionItem[cacheSize];
+ mostPopularCacheTable = new SymbolFileFunctionItem[cacheSize];
+// mostPopularHitCount = new int[cacheSize];
+ mostPopularTableIndex = 0;
+
+ for (int i=0;i<cacheSize;i++)
+ {
+ cacheAddressTable[i] = 0;
+ mostPopularCache[i] = 0;
+
+ cacheOrderTable[i] = null;
+ mostPopularCacheTable[i] = null;
+
+// mostPopularHitCount[i] = 0;
+ }
+ }
+
+ private SymbolFileFunctionItem getFunctionItemForAddress(long address)
+ {
+ SymbolFileFunctionItem cached = findFromCache(address);
+ if (cached != null) return cached;
+
+ SymbolFileDllItem foundDllItem = null;
+
+ if (this.dllList != null)
+ for (int i=0; i < this.dllList.length; i++)
+ {
+ SymbolFileDllItem dllItem = this.dllList[i];
+ if (address >= dllItem.start && address < dllItem.end)
+ {
+ foundDllItem = dllItem;
+ break;
+ }
+ }
+
+ if (foundDllItem != null)
+ {
+ int listSize = foundDllItem.data.size();
+ SymbolFileFunctionItem functionItem;
+
+ for (int i = 0; i + 1 < listSize; i++)
+ {
+ functionItem = (SymbolFileFunctionItem)foundDllItem.data.get(i);
+
+ if (address >= functionItem.address && address < functionItem.address+functionItem.length)
+ {
+ addToCache(functionItem,address);
+ return functionItem;
+ }
+ }
+
+ // if last item is an entry for a static function area, ignore it
+ functionItem = (SymbolFileFunctionItem)foundDllItem.data.get(listSize - 1);
+
+ if (!functionItem.name.startsWith(Messages.getString("CachedFunctionResolver.possibleStaticFunction1"))) { //$NON-NLS-1$
+ addToCache(functionItem,address);
+ return functionItem;
+ }
+ }
+
+ return null;
+ }
+
+ private SymbolFileFunctionItem findFromCache(long address)
+ {
+ SymbolFileFunctionItem item = null;
+
+ item = findFromMostPopular(address);
+ if (item!=null) return item;
+
+ for (int i=0;i<cacheSize;i++)
+ {
+ if (cacheAddressTable[i] == address)
+ {
+ item = cacheOrderTable[i];
+ //System.out.println("Found from cache,adding to most popular");
+// cacheFound++;
+ addToMostPopular(item,address);
+ break;
+ }
+ }
+// cacheNotFound++;
+ //if (item == null) System.out.println("Not found from the cache!!");
+ return item;
+ }
+
+ private void addToCache(SymbolFileFunctionItem item,long address)
+ {
+ if (cacheSize == 0) return;
+ cacheOrderTable[cacheIndex] = item;
+ cacheAddressTable[cacheIndex] = address;
+
+ cacheIndex++;
+ if (cacheIndex == cacheSize) cacheIndex = 0;
+ }
+
+ /* internal test function : comment out so code coverage looks
+ * good quantitatively
+ public void printMostPopularFromCache(int amountToPrint)
+ {
+ if (amountToPrint > cacheSize) amountToPrint = cacheSize;
+ System.out.println(Messages.getString("CachedFunctionResolver.mostPopularFromCache")); //$NON-NLS-1$
+
+ for (int i=0;i<amountToPrint;i++)
+ {
+ SymbolFileFunctionItem item = mostPopularCacheTable[i];
+ if (item!=null) System.out.println(item.name+Messages.getString("CachedFunctionResolver.hits")+mostPopularHitCount[i]); //$NON-NLS-1$
+ else break;
+ }
+ System.out.println(Messages.getString("CachedFunctionResolver.stats")); //$NON-NLS-1$
+ int all = cacheFound+cacheFoundPopular+cacheNotFound;
+ System.out.println(Messages.getString("CachedFunctionResolver.foundFromMostPopularCache")+(cacheFoundPopular*100f/all)+Messages.getString("CachedFunctionResolver.percentageSign")); //$NON-NLS-1$ //$NON-NLS-2$
+ System.out.println(Messages.getString("CachedFunctionResolver.foundFromCache")+(cacheFound*100f/all)+Messages.getString("CachedFunctionResolver.percentageSign")); //$NON-NLS-1$ //$NON-NLS-2$
+ System.out.println(Messages.getString("CachedFunctionResolver.notFoundFromCache")+(cacheNotFound*100f/all)+Messages.getString("CachedFunctionResolver.percentageSign")); //$NON-NLS-1$ //$NON-NLS-2$
+
+ System.out.println(Messages.getString("CachedFunctionResolver.end")); //$NON-NLS-1$
+ }
+ *
+ */
+
+ private SymbolFileFunctionItem findFromMostPopular(long address)
+ {
+ SymbolFileFunctionItem item = null;
+
+ int i = 0;
+
+ // until there are a few entries in mostPopularCache[], it's faster not using a binary search
+ if (mostPopularCache[4] == 0) {
+ for (;i<cacheSize && mostPopularCache[i] > address;i++)
+ ;
+ } else {
+ // use a binary search to find the item
+ int lowerBound = 0;
+ int upperBound = cacheSize - 1;
+ while (lowerBound <= upperBound) {
+ i = (lowerBound + upperBound)/2;
+ if (mostPopularCache[i] == address) {
+ item = mostPopularCacheTable[i];
+ break;
+ } else if (address > mostPopularCache[i])
+ upperBound = i - 1;
+ else
+ lowerBound = i + 1;
+ }
+
+// // check binary search
+// int j = 0;
+// for (;j<cacheSize && mostPopularCache[j] > address;j++)
+// ;
+// if (j != i && mostPopularCache[j] > address)
+// System.out.println("binary search failed");
+ }
+
+ if (mostPopularCache[i] == address)
+ {
+ item = mostPopularCacheTable[i];
+// mostPopularHitCount[i]++;
+// cacheFoundPopular++;
+ }
+
+ return item;
+ }
+
+ private void addToMostPopular(SymbolFileFunctionItem item, long address)
+ {
+ // most popular cache is full, delete 20%
+ if (mostPopularTableIndex == cacheSize)
+ {
+ for (int i=(8*(cacheSize/10));i<cacheSize;i++)
+ {
+ mostPopularCache[i] = 0;
+ mostPopularCacheTable[i] = null;
+// mostPopularHitCount[i] = 0;
+ }
+ mostPopularTableIndex = 8*(cacheSize/10);
+ //System.out.println("Clearing most popular ");
+ }
+
+ // add the new item in descending address order, so that we can bail out during search
+ int i = 0;
+
+ for ( ; i < mostPopularTableIndex && mostPopularCache[i] > address; i++)
+ ;
+
+ for (int j = mostPopularTableIndex; j > i; j--)
+ {
+ mostPopularCacheTable[j] = mostPopularCacheTable[j-1];
+ mostPopularCache[j] = mostPopularCache[j-1];
+// mostPopularHitCount[j] = mostPopularHitCount[j-1];
+ }
+
+ mostPopularCache[i] = address;
+ mostPopularCacheTable[i] = item;
+// mostPopularHitCount[i] = 2;
+ mostPopularTableIndex++;
+ }
+
+ public boolean canResolve() {
+ return this.ableToResolve;
+ }
+}