1 /*

     2  * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). 

     3  * All rights reserved.

     4  * This component and the accompanying materials are made available

     5  * under the terms of the License "Eclipse Public License v1.0"

     6  * which accompanies this distribution, and is available

     7  * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8  *

     9  * Initial Contributors:

    10  * Nokia Corporation - initial contribution.

    11  *

    12  * Contributors:

    13  *

    14  * Description: 

    15  *

    16  */

    17 

    18 package com.nokia.carbide.cpp.pi.call;

    19 

    20 import java.util.ArrayList;

    21 import java.util.Enumeration;

    22 import java.util.Hashtable;

    23 import java.util.Vector;

    24 

    25 import com.nokia.carbide.cpp.internal.pi.analyser.NpiInstanceRepository;

    26 import com.nokia.carbide.cpp.internal.pi.model.Function;

    27 import com.nokia.carbide.cpp.internal.pi.model.FunctionResolver;

    28 import com.nokia.carbide.cpp.internal.pi.model.GenericSample;

    29 import com.nokia.carbide.cpp.internal.pi.model.GenericSampledTraceWithFunctions;

    30 import com.nokia.carbide.cpp.internal.pi.utils.QuickSortImpl;

    31 import com.nokia.carbide.cpp.internal.pi.utils.Sortable;

    32 import com.nokia.carbide.cpp.internal.pi.visual.GenericTraceGraph;

    33 

    34 

    35 public class GfcTrace extends GenericSampledTraceWithFunctions

    36 {

    37 	private static final long serialVersionUID = -8144591614894549185L;

    38 

    39 	private long previousSample;

    40 	  

    41 	private Hashtable parsedGfcTrace;

    42 	private Vector    completeGfcTrace;

    43 	private int firstSample;

    44 	private int lastSample;

    45 	

    46 	private transient CallVisualiser callVisualiser;

    47 

    48 	private transient boolean completeTrace   = true;

    49 	private transient boolean completeSamples = true;

    50 	private transient int samplingInterval;

    51 	

    52 	public static final int SORT_BY_TOTAL_LOAD = 1;

    53 	public static final int SORT_BY_CALLED_LOAD = 2;

    54 	public static final int SORT_BY_RECURSIVE_LOAD = 3;

    55 

    56 	public GfcTrace(int size)

    57 	{	

    58 	    this.completeGfcTrace = new Vector(size);

    59 	    this.samples = new Vector(size);

    60 	    previousSample = 0;  	

    61 	}

    62 	

    63 	public void addSample(GfcSample sample, Long[] element)

    64 	{

    65 	    this.samples.add(sample);

    66 	  	  

    67 	    long sampleNumber   = sample.sampleSynchTime;

    68 	      

    69 	    if (previousSample != 0)

    70 	    {

    71 	    	if (sampleNumber != previousSample + samplingInterval)

    72 	    		System.out.println(Messages.getString("GfcTrace.missingSample1") + previousSample + Messages.getString("GfcTrace.missingSample2") + sample); //$NON-NLS-1$ //$NON-NLS-2$

    73 	    }

    74 	    previousSample = sampleNumber;

    75 	

    76 	    if (this.firstSample == -1)

    77 	    	this.firstSample = (int)sampleNumber;

    78 	    else

    79 	    	this.lastSample  = (int)sampleNumber;

    80 	    /*

    81 	    System.out.print("\n\nSample: "+sample+" pc: "+programCounter+" lr: "+linkRegister);

    82 	    System.out.print("\nSample: "+sample+

    83 	                       "\npc: "+symbolParser.getFunctionForAddress(programCounter).functionName+

    84 	                       "\nlr: "+symbolParser.getFunctionForAddress(linkRegister).functionName);

    85 	    */

    86 	    this.completeGfcTrace.add(element);

    87 	}

    88   

    89 	public Hashtable parseEntries(int startSample, int endSample)

    90 	{

    91 	  	// code to avoid stack overflow in saving analysis,

    92 	  	// with parameters -20,-20 , the parsedGfcTrace field is cleared,

    93 	  	// and it is restored with values -10,-10

    94 	    if (startSample == -20 && endSample == -20)

    95 	    {

    96 	    	if (this.parsedGfcTrace == null)

    97 	    	{

    98 	    		return null;

    99 	    	}

   100 	    	else

   101 	    	{

   102 	    		this.parsedGfcTrace = null;

   103 	    		return new Hashtable();

   104 	    	}

   105 	    }

   106 	    else if (startSample == -10 && endSample == -10)

   107 	    {

   108 	    	this.parseEntries(this.firstSample, this.lastSample);

   109 	    	return null;

   110 	    }

   111 	

   112 		int samplingInterval = (Integer) NpiInstanceRepository.getInstance().activeUidGetPersistState("com.nokia.carbide.cpp.pi.address.samplingInterval"); //$NON-NLS-1$

   113 

   114     	if (startSample < 1)

   115     		startSample = 0;

   116 

   117     	this.firstSample = startSample / samplingInterval;

   118 	    this.lastSample  = endSample / samplingInterval;

   119 	    

   120 	    this.parsedGfcTrace = new Hashtable();

   121 	    

   122     	if (this.completeTrace) {

   123 	    	// adjust the sample search

   124 	    	if (startSample > this.completeGfcTrace.size())

   125 	    		startSample = this.completeGfcTrace.size();

   126 	    	if (endSample > this.completeGfcTrace.size())

   127 	    		endSample = this.completeGfcTrace.size();

   128 	    	

   129 	    	for (int i = startSample; i < endSample; i++) {

   130 	    		Long[] data = (Long[])this.completeGfcTrace.elementAt(i);

   131 	    		this.parseOneEntry(data[0], data[1], data[2]);

   132 	    	}

   133 	    } else if (endSample >= samplingInterval) {

   134 	    	// sample is incomplete, so find the sample nearest but after the start

   135 	    	int nearest = 0;

   136 	    	if (startSample >= samplingInterval) {

   137 	    		int last = 0;

   138 	    		int half = this.completeGfcTrace.size() / 2;

   139 	    		nearest = this.completeGfcTrace.size() - 1;

   140 	    		long time = ((Long[]) this.completeGfcTrace.get(nearest))[0];

   141 	    		

   142 	    		while (time != startSample && half > 0) {

   143 	    			if (time < startSample)

   144 	    				nearest = nearest + half;

   145 	    			else

   146 	    				nearest = nearest - half;

   147 	    			half /= 2;

   148 	    			time = ((Long[]) this.completeGfcTrace.get(nearest))[0];

   149 	    		}

   150 	    		

   151 	    		while (nearest > 0 && time > startSample) {

   152 	    			nearest--;

   153 	    			time = ((Long[]) this.completeGfcTrace.get(nearest))[0];

   154 	    		}

   155 	    		

   156 	    		while (nearest < this.completeGfcTrace.size() - 1 && time + samplingInterval < startSample) {

   157 	    			nearest++;

   158 	    			time = ((Long[]) this.completeGfcTrace.get(nearest))[0];

   159 	    		}

   160 	    	}

   161 	    	

   162 	    	// we're starting at the right spot, so collect data (don't worry that we get the first one twice - we only parse it once

   163 	    	Long[] data = (Long[])this.completeGfcTrace.get(nearest);

   164 		    for ( ; data[0].longValue() <= endSample && nearest < this.completeGfcTrace.size(); nearest++) {

   165 		        data = (Long[])this.completeGfcTrace.get(nearest);

   166 		        this.parseOneEntry(data[0], data[1], data[2]);

   167 		    }

   168 	    }

   169 

   170 	    countRecursiveLoad();

   171     

   172 	    return this.parsedGfcTrace;

   173 	}

   174 	

   175 	private class CallerCallee {

   176 		String  functionName;

   177 		Long    startAdress;

   178 		String  binaryName;

   179 		boolean symbolParsed;

   180 	}

   181   

   182   	private void parseOneEntry(long sample, long programCounter, long linkRegister)

   183   	{

   184 	  	GfcSample gSam = null;

   185  

   186 	  	if (this.completeSamples)

   187   	    {

   188 	  		// find it directly

   189 	  		if (sample <= this.getLastSampleNumber())

   190 	  			gSam = (GfcSample)this.samples.elementAt((int) (sample - 1));

   191   	    } else {

   192   	    	// find it the slow way

   193   		  	if (this.getLastSampleNumber() <= sample + 1 || this.getFirstSampleNumber() > sample)

   194   		  		return;

   195 

   196   		  	GenericSample[] samples = this.getSamplesForTime(sample);

   197 	  	    if ((samples != null) && (samples.length != 0))

   198 	  	    	gSam = (GfcSample)samples[0];

   199   	    }

   200   	    

   201   	    if (gSam == null) {

   202   	    	System.out.println(Messages.getString("GfcTrace.sampleNotFound") + sample);  	    	 //$NON-NLS-1$

   203   	    	return;

   204   	    }

   205   	    

   206   	    CallerCallee caller = new CallerCallee();

   207   	    CallerCallee callee = new CallerCallee();

   208 

   209 		if (  (gSam.callerFunctionSym == null || gSam.callerFunctionSym.functionName.endsWith(Messages.getString("GfcTrace.functionNotFound"))) //$NON-NLS-1$

   210 			&& gSam.callerFunctionItt != null) //$NON-NLS-1$

   211 		{

   212 			caller.functionName = gSam.callerFunctionItt.functionName;

   213     		caller.startAdress  = gSam.callerFunctionItt.startAddress;

   214 			caller.binaryName   = gSam.callerFunctionItt.functionBinary.binaryName;

   215 			caller.symbolParsed = false;

   216 		}

   217 		else

   218 		{

   219 			caller.functionName = gSam.callerFunctionSym.functionName;

   220 			caller.startAdress  = gSam.callerFunctionSym.startAddress;

   221 			caller.binaryName   = gSam.callerFunctionSym.functionBinary.binaryName;

   222 			caller.symbolParsed = Boolean.valueOf(true);

   223 		}

   224 		

   225 		if (   (gSam.currentFunctionSym == null || gSam.currentFunctionSym.functionName.endsWith(Messages.getString("GfcTrace.functionNotFound"))) //$NON-NLS-1$

   226 			&& gSam.currentFunctionItt != null) //$NON-NLS-1$

   227 		{

   228 			callee.functionName = gSam.currentFunctionItt.functionName;

   229     		callee.startAdress  = gSam.currentFunctionItt.startAddress;

   230 			callee.binaryName   = gSam.currentFunctionItt.functionBinary.binaryName;

   231 			callee.symbolParsed = Boolean.valueOf(false);

   232 		}

   233 		else

   234 		{

   235 			callee.functionName = gSam.currentFunctionSym.functionName;

   236     		callee.startAdress  = gSam.currentFunctionSym.startAddress;

   237 			callee.binaryName   = gSam.currentFunctionSym.functionBinary.binaryName;

   238 			callee.symbolParsed = Boolean.valueOf(true);

   239 		}

   240 

   241 		this.updateEntryLists(sample, programCounter, linkRegister, caller, callee);

   242   	}

   243 

   244   	private void updateEntryLists(long sample, long programCounter, long linkRegister, CallerCallee callerObj, CallerCallee calleeObj)

   245 	{

   246 	    String callerName          = callerObj.functionName;

   247 	    Long callerStart           = callerObj.startAdress;

   248 	    String callerDllName       = callerObj.binaryName;

   249 	    boolean callerSymbolParsed = callerObj.symbolParsed;

   250 	

   251 	    String calleeName           = calleeObj.functionName;

   252 	    Long calleeStart            = calleeObj.startAdress;

   253 	    String calleeDllName        = calleeObj.binaryName;

   254 	    boolean calleeSymbolParsed  = calleeObj.symbolParsed;

   255 	    

   256 	    GfcFunctionItem caller;

   257 	    GfcFunctionItem callee;

   258 	

   259 	    // is the callee in the list

   260 	    if (parsedGfcTrace.containsKey(calleeStart))

   261 	    {

   262 		    // the callee is in the list

   263 		    callee = (GfcFunctionItem)this.parsedGfcTrace.get(calleeStart);

   264 	    }

   265 	    else

   266 	    {

   267 		    // the callee is not in the list

   268 		    callee = new GfcFunctionItem(calleeName, calleeStart.longValue(), calleeDllName, calleeSymbolParsed);

   269 		    this.parsedGfcTrace.put(calleeStart, callee);

   270 	    }

   271 

   272 	    // is the caller in the list

   273 	    if (this.parsedGfcTrace.containsKey(callerStart))

   274 	    {

   275 	    	// the caller is in the list

   276 	    	caller = (GfcFunctionItem)this.parsedGfcTrace.get(callerStart);

   277 	    }

   278 	    else

   279 	    {

   280 	    	// no, we have to add the caller to the list as well

   281 	    	caller = new GfcFunctionItem(callerName, callerStart.longValue(), callerDllName, callerSymbolParsed);

   282 	    	this.parsedGfcTrace.put(callerStart, caller);

   283 	    }

   284 

   285 	    if (!caller.equals(callee))

   286 	    {

   287 	    	callee.addCaller(caller, new Integer((int)sample));

   288 	    	caller.addCallee(callee, new Integer((int)sample));

   289 	    }

   290 	}

   291   

   292 	public void countRecursiveLoad()

   293 	{

   294 		//if (exclude == null)

   295 		ArrayList exclude = new ArrayList();

   296 

   297 		GfcFunctionItem[] sorted = this.getEntriesSorted(SORT_BY_CALLED_LOAD);

   298 		

   299 		if (sorted.length == 0)

   300 			return;

   301 		

   302 		int index = sorted.length - 1;

   303 		int lastExclude = 0;

   304 

   305 		// add the load of this function to the accumulated load

   306 		for (int i = 0; i < sorted.length; i++)

   307 		{

   308 			GfcFunctionItem gfi = sorted[i];

   309 			gfi.addRecursiveLoad(gfi.countSamplesThatCallThisFunction());

   310 			gfi.setRecursiveLoad(0);

   311 		}

   312 

   313 		while (true)

   314 		{

   315 		    GfcFunctionItem item = sorted[index];

   316 		    item.storePercents(-1, -1, -1, this.firstSample, this.lastSample);

   317 		

   318 		    index--;

   319 		    if (index == -1)

   320 		    {

   321 		        index = sorted.length - 1;

   322 		        if (lastExclude == exclude.size())

   323 		        {

   324 		        	break;

   325 		        }

   326 		        else

   327 		        {

   328 		        	lastExclude = exclude.size();

   329 		        }

   330 		    }

   331 		

   332 		    if (!exclude.contains(item))

   333 		    {

   334 		        double load = item.countSamplesThatCallThisFunction();

   335 		

   336 		        GfcFunctionItem[] callers = item.getCallerList();

   337 		        Double[] percentages = item.getCallerPercentages();

   338 		

   339 		        for (int i = 0; i < callers.length; i++)

   340 		        {

   341 			        //System.out.println(item.name+" load:"+load+" Adding "+load*(percentages[i].doubleValue()/100)+" to"+callers[i].name);

   342 			        callers[i].addRecursiveLoad(load*(percentages[i].doubleValue()/100));

   343 			

   344 			        // there is some accumulated recursive load to distribute

   345 			        // between the callers

   346 			        if (item.getRecursiveLoad() > 0)

   347 			        {

   348 			            double recursiveLoadToShare = item.getRecursiveLoad()*(percentages[i].doubleValue()/100);

   349 			

   350 			            // add recursive load only if the caller is not the function itself

   351 			            if (!callers[i].equals(item))

   352 			            {

   353 			            	callers[i].addRecursiveLoad(recursiveLoadToShare);

   354 			            }

   355 			        }

   356 		        }

   357 		        // clear the recursive load

   358 		        item.setRecursiveLoad(0);

   359 		    }

   360 	

   361 		    // this function does not call any other functions so it can be added

   362 		    // to the excluded functions list

   363 		    if (item.getCalleeList().length == 0)

   364 		    {

   365 		        if (!exclude.contains(item))

   366 		        	exclude.add(item);

   367 		        //sorted.remove(item);

   368 		    }

   369 		    else

   370 		    {

   371 		        GfcFunctionItem[] callees = item.getCalleeList();

   372 		        int i;

   373 		        for (i = 0; i < callees.length; i++)

   374 		        {

   375 			        // break if any item is found that is not excluded

   376 			        if (!exclude.contains(callees[i]))

   377 			        	break;

   378 		        }

   379 		

   380 		        // there are only excluded items in this function's call list,

   381 		        // thus it can also be excluded

   382 		        if (i == callees.length)

   383 		        {

   384 			        if (!exclude.contains(item))

   385 			        	exclude.add(item);

   386 			        //sorted.remove(item);

   387 		        }

   388 		    }

   389 		}

   390 	}

   391   

   392 	public GfcFunctionItem[] getEntriesSorted(final int sortMethod)

   393 	{

   394 	  	class ItemSorter implements Sortable

   395 	  	{

   396 	  		GfcFunctionItem item;

   397 	  		

   398 	  		double itemTotal;

   399 	  		double itemCaller;

   400 	  		double itemRecursive;

   401 	        

   402 	        public ItemSorter(GfcFunctionItem item)

   403 	        {

   404 	        	this.item = item;

   405 	            // calculate and store the percentages for the items for the selected period

   406 	            itemTotal     = item.getAbsoluteTotalPercentage(firstSample, lastSample);

   407 	            itemCaller    = item.getAbsoluteCallerPercentage(firstSample, lastSample);

   408 	            itemRecursive = item.getRecursiveCallerPercentage(firstSample, lastSample);

   409 	            

   410 	            if (itemTotal == -1 || itemCaller == -1 || itemRecursive == -1)

   411 	            {

   412 	            	itemTotal     = getAbsoluteTraditionalPercentageFor(item);

   413 	            	itemCaller    = getAbsoluteCallerPercentageFor(item);

   414 	            	itemRecursive = getRecursiveCallerPrecentageFor(item);

   415 	            

   416 	            	item.storePercents(itemTotal, itemCaller, itemRecursive,

   417 	                               		firstSample, lastSample);

   418 	            }

   419 	        }

   420         

   421 	  		public long valueOf()

   422 	  		{

   423 	  	        if (sortMethod == GfcTrace.SORT_BY_TOTAL_LOAD)

   424 	  	        {

   425 	  	        	return (long)(1000 * itemTotal);

   426 	  	        }

   427 	  	        else if (sortMethod == GfcTrace.SORT_BY_CALLED_LOAD)

   428 	  	        {

   429 	  	        	return (long)(1000 * itemCaller);

   430 	  	        }

   431 	  	        else if (sortMethod == GfcTrace.SORT_BY_RECURSIVE_LOAD)

   432 	  	        {

   433 	  	        	return (long)(1000 * itemRecursive);

   434 	  	        }

   435 	  	        else

   436 	  	        {

   437 	  	        	return 0;

   438 	  	        }

   439 	  		}

   440 	  	}

   441   	

   442 		Enumeration elements = this.parsedGfcTrace.elements();

   443 	  	

   444 		Vector s = new Vector();

   445 		while (elements.hasMoreElements())

   446 		{

   447 	  		ItemSorter is = new ItemSorter((GfcFunctionItem)elements.nextElement());

   448 	  		s.add(is);

   449 	  	}

   450 	  	

   451 	  	QuickSortImpl.sortReversed(s);

   452   	

   453 	  	elements = s.elements();

   454 	  	this.parsedGfcTrace.clear();

   455 	  	

   456 	  	GfcFunctionItem[] f = new GfcFunctionItem[s.size()];

   457 	  	int i = 0;

   458 	  	while (elements.hasMoreElements())

   459 	  	{

   460 	  		ItemSorter is = (ItemSorter)elements.nextElement();

   461 	  		f[i++] = is.item;

   462 	  		this.parsedGfcTrace.put(new Long(is.item.address), is.item);

   463 	  	}

   464   	

   465 	  	return f;

   466 	}

   467   

   468   	public double getAbsoluteTraditionalPercentageFor(GfcFunctionItem gfi)

   469 	{

   470 	    double samples = gfi.countSamplesThatCallThisFunction();

   471 	    double total = this.lastSample - this.firstSample;

   472 	    return 100 * (samples / total);

   473 	}

   474 

   475   	public double getAbsoluteCallerPercentageFor(GfcFunctionItem gfi)

   476   	{

   477   		double samples = gfi.countSamplesWhereThisFunctionIsTheCaller();

   478   		double total = this.lastSample - this.firstSample;

   479   		return 100 * (samples / total);

   480   	}

   481 

   482   	public double getRecursiveCallerPrecentageFor(GfcFunctionItem gfi)

   483   	{

   484   		double samples = gfi.getAccumulatedLoad();

   485   		double total = this.lastSample - this.firstSample;

   486   		return 100 * (samples / total);

   487   	}

   488 

   489   	/*

   490   	 * Check if the function call sample set and trace are complete

   491   	 * (first sample is at time 1, sample N is at time N)

   492   	 */

   493   	public void setComplete()

   494   	{

   495   		Object intervalObject = NpiInstanceRepository.getInstance().activeUidGetPersistState("com.nokia.carbide.cpp.pi.address.samplingInterval"); //$NON-NLS-1$

   496 		int samplingInterval = intervalObject != null ? (Integer) intervalObject : -1; 

   497   		int size;

   498   		

   499   		this.completeTrace = true;

   500   		

   501   		size = this.completeGfcTrace.size();

   502   		for (int i = 0; i < size; i++) {

   503   			Long[] element = (Long[])this.completeGfcTrace.elementAt(i);

   504   			if (element[0].longValue() != (i + 1)*samplingInterval) {

   505   				this.completeTrace = false;

   506   				break;

   507   			}

   508   		}

   509 

   510   		this.completeSamples = true;

   511   		

   512   		size = this.samples.size();

   513   		for (int i = 0; i < size; i++) {

   514   			GfcSample element = (GfcSample)this.samples.elementAt(i);

   515   			if (element.sampleSynchTime != (i + 1)*samplingInterval) {

   516   				this.completeSamples = false;

   517   				break;

   518   			}

   519   		}

   520   	}

   521   	

   522   	// this method is not used

   523   	public GenericTraceGraph getTraceGraph()

   524   	{

   525   		return null;

   526   	}

   527 

   528   	// this method is not used

   529   	public GenericTraceGraph getTraceGraph(int graphNumber)

   530   	{

   531 		return null;

   532 	}

   533 	

   534 	public CallVisualiser getCallVisualiser()

   535 	{

   536 		return this.callVisualiser;

   537 	}

   538 	

   539 	public void setCallVisualiser(CallVisualiser callVisualiser)

   540 	{

   541 		this.callVisualiser = callVisualiser;

   542 	}

   543 	

   544 	public void setSamplingInterval(int samplingInterval) {

   545 		this.samplingInterval = samplingInterval;

   546 	}

   547 	

   548 	public void refineTrace(FunctionResolver resolver)

   549 	{

   550 		GfcSample.setAddressTraceSamples();

   551 		super.refineTrace(resolver);

   552 	}

   553 	

   554 	public Vector getCompleteGfcTrace()

   555 	{

   556 		return this.completeGfcTrace;

   557 	}

   558 

   559 	@Override

   560 	public void finalizeTrace()

   561 	{

   562 		for (int i = 0; i < samples.size(); i++) {

   563 			GfcSample sample = (GfcSample) samples.get(i);

   564 			

   565 			if (sample.currentFunctionItt == null && sample.currentFunctionSym == null) {

   566 				sample.currentFunctionItt = new Function(Messages.getString("GfcTrace.functionNotFound1") + Long.toHexString(sample.programCounter) + Messages.getString("GfcTrace.functionNotFound2"), //$NON-NLS-1$ //$NON-NLS-2$

   567 						new Long(sample.programCounter),

   568 						Messages.getString("GfcTrace.binaryNotFound1") +  Long.toHexString(sample.programCounter) + Messages.getString("GfcTrace.binaryNotFound2")); //$NON-NLS-1$ //$NON-NLS-2$

   569 			}

   570 			

   571 			if (sample.callerFunctionItt == null && sample.callerFunctionSym == null) {

   572 				sample.callerFunctionItt = new Function(Messages.getString("GfcTrace.functionNotFound1") + Long.toHexString(sample.linkRegister) + Messages.getString("GfcTrace.functionNotFound2"), //$NON-NLS-1$ //$NON-NLS-2$

   573 						new Long(sample.linkRegister),

   574 						Messages.getString("GfcTrace.binaryNotFound1") +  Long.toHexString(sample.linkRegister) + Messages.getString("GfcTrace.binaryNotFound2")); //$NON-NLS-1$ //$NON-NLS-2$

   575 			}

   576 		}

   577 	}

   578 }