Update copyright to LGPL on all files
[dyninst.git] / codeCoverage / src / FunctionCoverage.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #include <stdio.h>
33 #include <unistd.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include <iostream>
37 #include <fstream>
38 #include <limits.h>
39 #include <pthread.h>
40 #include <tcl.h>
41 #include <tk.h>
42
43 #include "common/h/Vector.h"
44 #include "common/src/Dictionary.C"
45 #include "BPatch_Set.h"
46
47 #include "common/h/Types.h"
48 #include "common/h/String.h"
49
50 #include <CCcommon.h>
51 #include <CodeCoverage.h>
52 #include <FunctionCoverage.h>
53
54 FileLineCoverage::FileLineCoverage(const char* fName) :
55         owner(NULL),fileName(fName),lineCount(0),executionPercentage(0.0)
56 {}
57
58 FileLineCoverage::~FileLineCoverage()
59 {}
60
61 void FileLineCoverage::initializeLines(BPatch_Set<unsigned short>& lines){
62         unExecutedLines |= lines;
63         lineCount = lines.size();
64 }
65
66 FileLineCoverage*
67 FileLineCoverage::findFile(FileLineCoverage** files,int count,const char* fName){
68
69         if(!files || !count || !fName)
70                 return NULL;
71
72         if(count == 1){
73                 if(!strcmp(fName,files[0]->fileName))
74                         return files[0];
75                 return NULL;
76         }
77
78         int low = 0;
79         int high = count-1;
80         int mid = 0;
81         FileLineCoverage* ret = NULL;
82         do{
83                 mid = (low+high)/2;
84                 int check = strcmp(fName,files[mid]->fileName);
85                 if(check < 0)
86                         high = mid - 1;
87                 else if(check > 0)
88                         low = mid + 1;
89                 else{
90                         ret = files[mid];
91                         break;
92                 }
93         }while(low <= high);
94
95         return ret;
96 }
97
98 void FileLineCoverage::setOwner(FunctionCoverage* fc){
99         owner = fc;
100 }
101
102 /** constructor */
103 FunctionCoverage::FunctionCoverage() 
104                 : bpFunction(NULL),appThread(NULL),appImage(NULL),cfg(NULL),
105                   instrumentationCount(0),instrumentedBlock(NULL),
106                   blockVariable(NULL),instrumentationCode(NULL),
107                   executionCounts(NULL),functionName(NULL),
108                   id(-1),isPrecise(true),
109                   sourceFileLinesCount(0),
110                   sourceFileLines(NULL)
111 {
112         pthread_mutex_init(&updateLock,NULL);
113 }
114
115 /** constructor */
116 FunctionCoverage::FunctionCoverage(BPatch_function* f,BPatch_thread* t,
117                                    BPatch_image* i,
118                                    const char* funcN) 
119                 : bpFunction(f),appThread(t),appImage(i),cfg(NULL),
120                   instrumentationCount(0),instrumentedBlock(NULL),
121                   blockVariable(NULL),instrumentationCode(NULL),
122                   executionCounts(NULL),id(-1),isPrecise(true),
123                   sourceFileLinesCount(0),
124                   sourceFileLines(NULL)
125 {
126         functionName = funcN;
127         pthread_mutex_init(&updateLock,NULL);
128 }
129
130 /** method to set identifier of the object It is unique among
131   * objects of this class
132   */
133 void FunctionCoverage::setId(int i){
134         id = i;
135 }
136
137 /** method to create control flow graph of the function
138   * represented by this object
139   */
140 int FunctionCoverage::createCFG(){
141         cfg = bpFunction->getCFG();
142         if(!cfg)
143                 return errorPrint(Error_CFGCreate);
144
145         cfg->getAllBasicBlocks(allBlocks);
146
147         BPatch_Vector<BPatch_basicBlock*> enB; 
148         cfg->getEntryBasicBlock(enB);
149         for(unsigned int i=0;i<enB.size();i++)
150                 entryBlock += enB[i];
151
152         BPatch_Vector<BPatch_basicBlock*> exB; 
153         cfg->getExitBasicBlock(exB);
154         for(unsigned int i=0;i<exB.size();i++)
155                 exitBlock += exB[i];
156
157
158         /** source line infomation is created */
159         cfg->createSourceBlocks();
160
161         return Error_OK;
162 }
163
164 /** this method inserts break point to the beginning of the
165   * function and also an assigment which assigns the identifier of the
166   * function to the variable given as an argument
167   */
168 BPatchSnippetHandle* 
169 FunctionCoverage::insertBreakPointatEntry(BPatch_variableExpr* v)
170 {
171         BPatch_Vector<BPatch_snippet*> codeList;
172         BPatch_breakPointExpr *bp = new BPatch_breakPointExpr();
173         BPatch_arithExpr *whichbp = new BPatch_arithExpr(BPatch_assign,
174                                                        *v,BPatch_constExpr(id));
175         codeList.push_back(whichbp);
176         codeList.push_back(bp);
177
178         BPatch_Vector<BPatch_point*>* breakPoints = NULL;
179         breakPoints = bpFunction->findPoint(BPatch_entry);
180
181         BPatchSnippetHandle* ret = NULL;
182         if(breakPoints){
183                 ret = appThread->insertSnippet(BPatch_sequence(codeList),
184                                          *breakPoints,
185                                          BPatch_callBefore,BPatch_lastSnippet);
186                 delete breakPoints;
187         }
188         delete bp;
189         delete whichbp;
190         return ret;
191 }
192
193 /** Method to instrument selected basic blocks. For each basic block
194   * that is instrumented a variable is assigned and the instrumentation code
195   * increments this variable at the beginning of the basic block
196   * If the basic block is one of the entry point or exit points 
197   * already existing point are used for instrumentation.
198   */
199 int FunctionCoverage::instrumentPoints(){
200
201         cout << "information: " << functionName
202              << " is being instrumented..." << endl;
203
204         /** for each basic block */
205         for(int i=0;i<instrumentationCount;i++){
206                 BPatch_basicBlock* bb = instrumentedBlock[i];
207
208                 /** create the code to increment its variable */
209                 BPatch_arithExpr increment(
210                         BPatch_assign,*(blockVariable[i]),
211                         BPatch_arithExpr(BPatch_plus,*(blockVariable[i]),
212                                          BPatch_constExpr(1)));
213
214                 BPatch_Vector<BPatch_point*>* bpp = NULL;
215
216                 BPatch_callWhen callWhen = BPatch_callBefore;
217
218                 /** find the instrumentation point or create one arbitrary */
219                 if(entryBlock.contains(bb))
220                         bpp = bpFunction->findPoint(BPatch_entry);
221                 else if(exitBlock.contains(bb)){
222                         bpp = bpFunction->findPoint(BPatch_exit);
223                         callWhen = BPatch_callAfter;
224                 }
225                 else {
226                         bpp = new BPatch_Vector<BPatch_point*>;
227                         BPatch_point *p = NULL, *q = NULL; 
228                         void *startAddress=NULL,*endAddress=NULL;
229
230                         bb->getAddressRange(startAddress,endAddress);
231
232                         /** create the instrumentation point (arbitrary) */
233                         p = appImage->createInstPointAtAddr(startAddress,&q,
234                                                             bpFunction);
235
236                         if(p)
237                                 bpp->push_back(p);
238                         else if(q)
239                                 /** if can not be created but overlaps with other 
240                                   * use the overlapping one
241                                   */
242                                 bpp->push_back(q);
243                         else{
244                                 delete bpp;
245                                 isPrecise = false;
246                                 continue;
247                         }
248                 }
249
250                 /** insert the instrumentation code */
251                 if(bpp)
252                 instrumentationCode[i] = 
253                                 appThread->insertSnippet(increment,*bpp,
254                                                          callWhen,
255                                                          BPatch_lastSnippet);
256                 if(!instrumentationCode[i])
257                         isPrecise = false;
258                 delete bpp;
259         }
260         if(!isPrecise)
261                 cout << "\tinformation: " << functionName << " results may"
262                      << " not be precise..." << endl;
263         return Error_OK;
264 }
265
266 /** method that selects the basic blocks to be instrumented
267   * After selecting the basic blocks to be instrumented it initializes
268   * some data strucutes to store the variables, executions counts, etc.
269   * The basic blocks with single instructions are not instrumented
270   */
271 int FunctionCoverage::selectInstrumentationPoints(){
272
273         BPatch_Set<BPatch_basicBlock*> tobeInstrumented;
274
275         int errorCode = Error_OK;
276
277         /** create control flow graph */
278         errorCode = createCFG();
279         if(errorCode < Error_OK)
280                 return errorCode;
281
282         /** if needed fill in the dominator information */
283         fillDominatorInfo();
284
285         BPatch_basicBlock** elements = 
286                         new BPatch_basicBlock*[allBlocks.size()];
287         allBlocks.elements(elements);
288
289         executionCounts = new int[allBlocks.size()];
290
291         for(unsigned i=0;i<allBlocks.size();i++){
292                 BPatch_basicBlock* bb = elements[i];
293                 executionCounts[i] = 0;
294
295                 void *startAddress=NULL,*endAddress=NULL;
296                 bb->getAddressRange(startAddress,endAddress);
297
298                 /** if the basic block does not need to be instrumented
299                   * or even though it is needed it has only single instruction
300                   * then do not select
301                   */
302                 if(!validateBasicBlock(bb))
303                         continue;
304                 else if(!((char*)endAddress-(char*)startAddress)){
305                         isPrecise = false;
306                         continue;
307                 }
308
309                 /** otherwise selct to be instrumented */
310                 tobeInstrumented += bb;
311         }
312
313         instrumentationCount = tobeInstrumented.size();
314
315         /** if there is no possible selection for this method return */
316         if(!instrumentationCount)
317                 return Error_OK;
318
319         /** create the necessary data structures to store info about 
320           * executions of basic blocks
321           */
322         instrumentedBlock = new BPatch_basicBlock*[instrumentationCount];
323         blockVariable = new BPatch_variableExpr*[instrumentationCount];
324         instrumentationCode = new BPatchSnippetHandle*[instrumentationCount];
325
326         /** initialize the data strucutes created */
327         tobeInstrumented.elements(elements);
328         for(int i=0;i<instrumentationCount;i++){
329                 instrumentedBlock[i] = elements[i];
330                 instrumentationCode[i] = NULL;
331                 int tmpV = 0;
332                 blockVariable[i] = 
333                         appThread->malloc(*appImage->findType("int"));
334                 blockVariable[i]->writeValue((void*)&tmpV);
335         }
336
337         delete[] elements;
338
339         return Error_OK;
340 }
341
342 /** method to fill dominator information if needed */
343 void FunctionCoverage::fillDominatorInfo(){
344 }
345
346 /** method to decide whether it is necessary a basic block will
347   * be instrumented or not 
348   */ 
349 bool FunctionCoverage::validateBasicBlock(BPatch_basicBlock* bb){
350         if(bb)
351                 return true;
352         return false;
353 }
354
355 /** method that prints the error codes of this class */
356 int FunctionCoverage::errorPrint(int code,char* text){
357         cerr << "Error(" << code << ") : ";
358
359         switch(code){
360                 case Error_CFGCreate:
361                         cerr << "Control flow graph for the function can not be created. ";
362                         break;
363                 default: cerr << "Unrecognized error!!!!";
364         }
365
366         if(text)
367                 cerr << endl << "\t[ " << text << " ]";
368
369         cerr << endl;
370
371         return code;
372 }
373
374 /** destructor of the class */
375 FunctionCoverage::~FunctionCoverage() {
376         delete cfg;
377         delete[] instrumentedBlock;
378         delete[] blockVariable;
379         delete[] instrumentationCode;
380         delete[] executionCounts;
381         pthread_mutex_destroy(&updateLock);
382 }
383
384 /** method to print the coverage results of the function it represents 
385   * into a binary file generated by concatenation of the given suffix
386   * to the executable name
387   */
388 int FunctionCoverage::printCoverageInformation(std::ofstream& cf)
389 {
390         unsigned tmp_u;
391         unsigned short tmp_s;
392
393         for(int j=0;j<sourceFileLinesCount;j++){
394                 tmp_u = strlen(functionName);
395                 cf.write((char*)&tmp_u,sizeof(unsigned));
396                 cf.write(functionName,tmp_u);
397
398                 tmp_u = strlen(sourceFileLines[j]->fileName);
399                 cf.write((char*)&tmp_u,sizeof(unsigned));
400                 cf.write(sourceFileLines[j]->fileName,tmp_u);
401
402                 unsigned short* lelements = NULL;
403
404                 tmp_u = sourceFileLines[j]->executedLines.size();
405                 cf.write((char*)&tmp_u,sizeof(unsigned));
406
407                 if(tmp_u){
408                         lelements = new unsigned short[tmp_u];
409                         sourceFileLines[j]->executedLines.elements(lelements);
410                         for(unsigned int i=0;i<tmp_u;i++){
411                                 tmp_s = lelements[i];
412                                 cf.write((char*)&tmp_s,sizeof(unsigned short));
413                         }
414                         delete[] lelements;
415                 }
416
417                 pthread_mutex_lock(&updateLock);
418                 tmp_u = sourceFileLines[j]->unExecutedLines.size();
419                 cf.write((char*)&tmp_u,sizeof(unsigned));
420
421                 if(tmp_u){
422                         lelements = new unsigned short[tmp_u];
423                         sourceFileLines[j]->unExecutedLines.elements(lelements);
424                         for(unsigned int i=0;i<tmp_u;i++){
425                                 tmp_s = lelements[i];
426                                 cf.write((char*)&tmp_s,sizeof(unsigned short));
427                         }
428                         delete[] lelements;
429                 }
430                 pthread_mutex_unlock(&updateLock);
431         }
432
433         return Error_OK;
434 }
435
436 /** method that updates execution count for a basic block */
437 int FunctionCoverage::updateExecutionCounts(BPatch_basicBlock* bb,int ec){
438         if(bb && ec)
439                 return Error_OK;
440         return Error_OK;
441 }
442
443 /** method to update execution counts of the basic blocks */
444 int FunctionCoverage::updateExecutionCounts(){
445
446         /** for each instrumented basic block */
447         for(int i=0;i<instrumentationCount;i++){
448                 if(!instrumentedBlock[i])
449                         continue;
450                 BPatch_basicBlock* bb = instrumentedBlock[i];
451                 BPatch_variableExpr* bv = blockVariable[i];
452
453                 /** read the execution count */
454                 int ec = 0;
455                 if(bv) bv->readValue((void*)&ec);
456                 if(!ec)
457                         continue;
458
459                 /** using the basic block and execution count
460                   * update necessary basic block execution counts.
461                   */
462                 updateExecutionCounts(bb,ec);
463
464                 /** delete the instrumentation code for the basic block
465                   * since it does not produce any useful information
466                   * after it has been executed once
467                   */
468                 
469                 if(instrumentationCode[i]){
470                         CodeCoverage::globalObject->totalDeletions++;
471                         appThread->deleteSnippet(instrumentationCode[i]);
472                 }
473
474                 instrumentedBlock[i] = NULL;
475         }
476
477         for(int i=0;i<sourceFileLinesCount;i++)
478                 if(sourceFileLines[i]->lineCount){
479                         pthread_mutex_lock(&updateLock);
480
481                         sourceFileLines[i]->executionPercentage =  sourceFileLines[i]->executedLines.size();
482                         sourceFileLines[i]->executionPercentage /= sourceFileLines[i]->lineCount;
483                         sourceFileLines[i]->executionPercentage *= 100;
484
485                         pthread_mutex_unlock(&updateLock);
486                 }
487
488         return Error_OK;
489 }
490
491 int FunctionCoverage::updateLinesCovered(BPatch_sourceBlock* sb)
492 {
493         if(sb){
494                 pthread_mutex_lock(&updateLock);
495
496                 const char* fName = sb->getSourceFile();
497                 FileLineCoverage* flc = 
498                         FileLineCoverage::findFile(sourceFileLines,sourceFileLinesCount,fName);
499                 if(flc){
500                         BPatch_Vector<unsigned short> lines;
501                         sb->getSourceLines(lines);
502                         for(unsigned int j=0;j<lines.size();j++){
503                                 if(!flc->executedLines.contains(lines[j]))
504                                         CodeCoverage::globalObject->totalCoveredLines++;
505                                 flc->executedLines += lines[j];
506                                 flc->unExecutedLines.remove(lines[j]);
507                         }
508                 }
509
510                 pthread_mutex_unlock(&updateLock);
511         }
512         return Error_OK;
513 }
514
515 void FunctionCoverage::addSourceFile(FileLineCoverage* flc){
516         if( flc == NULL ) { return; }
517         
518         sourceFileLines = (FileLineCoverage**)(sourceFileLinesCount ?
519                         realloc(sourceFileLines,
520                                 (sourceFileLinesCount+1)*sizeof(FileLineCoverage*)) :
521                         malloc(sizeof(FileLineCoverage*)));
522
523         int location = sourceFileLinesCount;
524
525         for(;location>0;location--){
526                 if(strcmp(sourceFileLines[location-1]->fileName,flc->fileName) <= 0)
527                         break;
528                 sourceFileLines[location] = sourceFileLines[location-1] ;
529         }
530         
531         sourceFileLines[location] = flc;
532         sourceFileLinesCount++;
533 }