dyninstAPI/src/LineInformation.C

   1 #include <stdlib.h>
   2
   3 #include "dyninstAPI/src/LineInformation.h"
   4 #include "dyninstAPI/src/util.h"
   5
   6 typedef FileLineInformation::tuple tuple;
   7
   8 //this function implements binary search and returns the found element.
   9 //besides the found element it returns the next bigger line numbered one
  10 //The found element is the first same values element in the array in existence
  11 //of many same values elements.
  12 //in case it is not found it will RETURN NULL. if the next element
  13 //is not available it will assign NULL to the reference.
  14 //the next contains the entry with the first greater line number
  15 tuple* binarySearchLineFirst(tuple element,tuple* array,int howMany,tuple*& next)
  16 {
  17         int low = 0;
  18         int high = howMany-1;
  19         int mid;
  20         tuple* ret=NULL;
  21         do{
  22                 mid = (low+high)/2;
  23                 if(element.lineNo < array[mid].lineNo)
  24                         high = mid - 1;
  25                 else if(element.lineNo > array[mid].lineNo)
  26                         low = mid + 1;
  27                 else
  28                         break;
  29         }while(low <= high);
  30
  31         //if found then porepare to return and the next available
  32         if(element.lineNo == array[mid].lineNo){
  33                 int index = mid;
  34                 for(;(index >= 0)&&(array[index].lineNo == element.lineNo);index--);
  35                 ret = array+(index+1);
  36                 index = mid;
  37                 for(;(index < howMany)&&(array[index].lineNo == element.lineNo);index++);
  38                 if(index == howMany)
  39                         next = NULL;
  40                 else
  41                         next = array+index;
  42         }
  43         else if(low == howMany)
  44                 next = NULL;
  45         else
  46                 next = array+low;
  47
  48         return ret;
  49 }
  50 //this function implements binary search and returns the found element.
  51 //besides the found element it returns the previous smaller address entry
  52 //The found element is the first same values element in the array in existence
  53 //of many same values elements.
  54 //in case it is not found it will RETURN NULL. if the next element
  55 //is not available it will assign NULL to the reference.
  56 //the next contains the entry with the previous smaller address
  57 tuple* binarySearchAddrFirst(tuple element,tuple* array,int howMany,tuple*& next)
  58 {
  59         int low = 0;
  60         int high = howMany-1;
  61         int mid;
  62         tuple* ret=NULL;
  63         do{
  64                 mid = (low+high)/2;
  65                 if(element.codeAddress < array[mid].codeAddress)
  66                         high = mid - 1;
  67                 else if(element.codeAddress > array[mid].codeAddress)
  68                         low = mid + 1;
  69                 else
  70                         break;
  71         }while(low <= high);
  72
  73         ////if found then porepare to return and the next available
  74         if(element.codeAddress == array[mid].codeAddress){
  75                 int index = mid;
  76                 for(;(index>=0)&&(array[index].codeAddress == element.codeAddress);index--);
  77                 ret = array+(index+1);
  78                 if(index == -1)
  79                         next = NULL;
  80                 else{
  81                         Address addr = array[index].codeAddress;
  82                         for(;(index>=0) && (array[index].codeAddress == addr);index--);
  83                         next = array+(index+1);
  84                 }
  85         }
  86         else if(high == -1)
  87                 next = NULL;
  88         else{
  89                 Address addr = array[high].codeAddress;
  90                 for(;(high >=0) && (array[high].codeAddress == addr);high--);
  91                 next = array+(high+1);
  92         }
  93         return ret;
  94 }
  95
  96 //constructor
  97 FileLineInformation::FileLineInformation(string fileName)
  98         : sourceFileName(fileName),
  99           size(0),
 100           lineToAddr(NULL),
 101           addrToLine(NULL),
 102           functionCount(0),
 103           functionNameList(NULL),
 104           lineInformationList(NULL) {}
 105
 106 //destructor
 107 FileLineInformation::~FileLineInformation(){
 108         delete[] lineToAddr;
 109         delete[] addrToLine;
 110         for(int i=0;i<functionCount;i++){
 111                 delete lineInformationList[i];
 112                 delete functionNameList[i];
 113         }
 114         delete[] functionNameList;
 115         delete[] lineInformationList;
 116 }
 117
 118 //returns the function info structure
 119 FileLineInformation::FunctionInfo*
 120 FileLineInformation::findFunctionInfo(string functionName){
 121         for(int i=0;i<functionCount;i++)
 122                 if(functionName == *functionNameList[i])
 123                         return lineInformationList[i];
 124         return NULL;
 125 }
 126
 127 //inserts function wntry to the mapping from function name to its info
 128 void FileLineInformation::insertFunction(string functionName){
 129         FunctionInfo* fInfo = findFunctionInfo(functionName);
 130         if(!fInfo){
 131                 functionNameList = (string**)(functionCount ?
 132                         realloc(functionNameList,(functionCount+1)*sizeof(string*)) :
 133                         new string*[1]);
 134                 lineInformationList = (FunctionInfo**)(functionCount ?
 135                         realloc(lineInformationList,(functionCount+1)*sizeof(FunctionInfo*)) :
 136                         new FunctionInfo*[1]);
 137                 functionNameList[functionCount] = new string(functionName);
 138                 lineInformationList[functionCount] = new FunctionInfo;
 139                 functionCount++;
 140         }
 141 }
 142
 143 //returns true if the function has an entry in the mapping
 144 bool FileLineInformation::findFunction(string functionName){
 145         FunctionInfo* fInfo = findFunctionInfo(functionName);
 146         if(!fInfo) return false;
 147         return true;
 148 }
 149
 150
 151 //insert a mapping from line number to address and address to line number
 152 //to the corresponding structures and updates the records for the function
 153 //given
 154 void FileLineInformation::insertLineAddress(string functionName,
 155                                             unsigned short lineNo,
 156                                             Address codeAddress)
 157 {
 158
 159         FunctionInfo* fInfo = findFunctionInfo(functionName);
 160         if(!fInfo){
 161                 cerr << "FATAL ERROR : Something wrong \n";
 162                 return;
 163         }
 164
 165         lineToAddr = !lineToAddr ? ((tuple*)malloc(sizeof(tuple))) :
 166                      ((tuple*)realloc(lineToAddr,sizeof(tuple)*(size+1)));
 167         addrToLine = !addrToLine ? ((tuple*)malloc(sizeof(tuple))) :
 168                      ((tuple*)realloc(addrToLine,sizeof(tuple)*(size+1)));
 169
 170         //since the entries will come in oreder insertion sort is the best sort here
 171         //to keep the list sorted and using binary search to find the entries.
 172         //insertion sort comes here
 173
 174         short index1;
 175         for(index1=size-1;index1>=0;index1--)
 176                 if(lineToAddr[index1].lineNo > lineNo)
 177                         lineToAddr[index1+1] = lineToAddr[index1];
 178                 else break;
 179         index1++;
 180         lineToAddr[index1] = tuple(lineNo,codeAddress);
 181
 182         short index2;
 183         //insertion sort for code address
 184
 185         for(index2=size-1;index2>=0;index2--)
 186                 if(addrToLine[index2].codeAddress > codeAddress)
 187                         addrToLine[index2+1] = addrToLine[index2];
 188                 else break;
 189         index2++;
 190         addrToLine[index2] = tuple(lineNo,codeAddress);
 191
 192         size++;
 193
 194         if(!fInfo->validInfo){
 195                 fInfo->startLinePtr = (unsigned)index1;
 196                 fInfo->endLinePtr = (unsigned)index1;
 197                 fInfo->startAddrPtr = (unsigned)index2;
 198                 fInfo->endAddrPtr = (unsigned)index2;
 199                 fInfo->validInfo = true;
 200                 return;
 201         }
 202
 203         if(lineToAddr[fInfo->startLinePtr].lineNo > lineNo)
 204                 fInfo->startLinePtr = (unsigned)index1;
 205         if(lineToAddr[fInfo->endLinePtr].lineNo <= lineNo)
 206                 fInfo->endLinePtr = (unsigned)index1;
 207
 208         if(addrToLine[fInfo->startAddrPtr].codeAddress > codeAddress)
 209                 fInfo->startAddrPtr = (unsigned)index2;
 210         if(addrToLine[fInfo->endAddrPtr].codeAddress <= codeAddress)
 211                 fInfo->endAddrPtr = (unsigned)index2;
 212
 213 }
 214
 215 //returns true in case of success, false otherwise.
 216 //this method finds the line number corresponding to an address.
 217 //if name of the function is supplied and isFile is false
 218 //then function level search is being applied. Otherwise file level
 219 //search is applied. If there are more than 1 line found than
 220 //the maximum is being returned.
 221 bool FileLineInformation::getLineFromAddr(string name,unsigned short& lineNo,
 222                                           Address codeAddress,bool isFile,
 223                                           bool isExactMatch)
 224 {
 225         BPatch_Set<unsigned short> lines;
 226         if(!getLineFromAddr(name,lines,codeAddress,isFile,isExactMatch))
 227                 return false;
 228         lineNo = lines.maximum();
 229         return true;
 230 }
 231 //returns true in case of success, false otherwise.
 232 //this method finds the line numbers corresponding to an address.
 233 //if name of the function is supplied and isFile is false
 234 //then function level search is being applied. Otherwise file level
 235 //search is applied. All the line numbers corresponding to the address
 236 //is returned in a set of addresses.
 237 bool FileLineInformation::getLineFromAddr(string name,
 238                                           BPatch_Set<unsigned short>& lines,
 239                                           Address codeAddress,bool isFile,
 240                                           bool isExactMatch)
 241 {
 242         tuple* beginPtr;
 243         tuple* endPtr;
 244         int howMany;
 245
 246         if(!addrToLine)
 247                 return false;
 248         if(isFile){
 249                 beginPtr = addrToLine;
 250                 endPtr = (tuple*) (addrToLine+(size-1));
 251                 howMany = size;
 252         }
 253         else{
 254                 FunctionInfo* fInfo = findFunctionInfo(name);
 255                 if(!fInfo)
 256                         return false;
 257                 if(!fInfo->validInfo)
 258                         return false;
 259                 beginPtr = addrToLine+fInfo->startAddrPtr;
 260                 endPtr = addrToLine+fInfo->endAddrPtr;
 261                 howMany = fInfo->endAddrPtr-fInfo->startAddrPtr+1;
 262         }
 263
 264         if((codeAddress < beginPtr->codeAddress) || (endPtr->codeAddress < codeAddress))
 265                 return false;
 266
 267         tuple toSearch(0,codeAddress);
 268         tuple* next=NULL;
 269         tuple* ret = binarySearchAddrFirst(toSearch,beginPtr,howMany,next);
 270         if(!ret){
 271                 if(isExactMatch)
 272                         return false;
 273                 if(!next)
 274                         return false;
 275                 ret = next;
 276                 codeAddress = ret->codeAddress;
 277         }
 278         do{
 279                 lines += ret->lineNo;
 280                 ret++;
 281         }while((ret <= endPtr) && (ret->codeAddress == codeAddress));
 282
 283         return true;
 284 }
 285
 286 //method that retuns set of addresses corresponding to a given line number
 287 //the level of the search is file level if isFile flag is set.
 288 //If isFile level is not set, it seraches in the given function
 289 //in case of success it returns true otherwise false
 290 bool FileLineInformation::getAddrFromLine(string name,
 291                                           BPatch_Set<Address>& codeAddress,
 292                                           unsigned short lineNo,bool isFile,
 293                                           bool isExactMatch)
 294 {
 295         tuple* beginPtr;
 296         tuple* endPtr;
 297         int howMany;
 298
 299         if(!lineToAddr)
 300                 return false;
 301         if(isFile){
 302                 beginPtr = lineToAddr;
 303                 endPtr = (tuple*) (lineToAddr+(size-1));
 304                 howMany = size;
 305         }
 306         else{
 307                 FunctionInfo* fInfo = findFunctionInfo(name);
 308                 if(!fInfo)
 309                         return false;
 310                 if(!fInfo->validInfo)
 311                         return false;
 312                 beginPtr = lineToAddr+fInfo->startLinePtr;
 313                 endPtr = lineToAddr+fInfo->endLinePtr;
 314                 howMany = fInfo->endLinePtr-fInfo->startLinePtr+1;
 315         }
 316         if(!isFile &&
 317            (lineNo < beginPtr->lineNo) || (endPtr->lineNo < lineNo))
 318                 return false;
 319
 320         tuple toSearch(lineNo,0);
 321         tuple* next=NULL;
 322         tuple* ret = binarySearchLineFirst(toSearch,beginPtr,howMany,next);
 323         if(!ret){
 324                 if(isExactMatch)
 325                         return false;
 326                 if(!next)
 327                         return false;
 328                 ret = next;
 329                 lineNo = ret->lineNo;
 330         }
 331         do{
 332                 codeAddress += ret->codeAddress;
 333                 ret++;
 334         }while((ret <= endPtr) && (ret->lineNo == lineNo));
 335
 336         return true;
 337 }
 338
 339 //temporary function to print info about line information
 340 void FileLineInformation::print(){
 341         cerr << "LINE TO ADDRESS :\n";
 342         for(int j=0;j<size;j++)
 343                 cerr << dec << lineToAddr[j].lineNo << " ----> " << hex << lineToAddr[j].codeAddress << "\n";
 344         for(int i=0;i<functionCount;i++){
 345                 FunctionInfo* funcinfo = lineInformationList[i];
 346                 cerr << "FUNCTION LINE : " << *functionNameList[i] << " : " ;
 347                 if(!funcinfo->validInfo)
 348                         continue;
 349                 cerr << dec << lineToAddr[funcinfo->startLinePtr].lineNo ;
 350                 cerr << " --- " << dec << lineToAddr[funcinfo->endLinePtr].lineNo << "\n";
 351         }
 352
 353 }
 354
 355 //constructor whose argument is the name of the module name
 356 LineInformation::LineInformation(string mName)
 357                 : moduleName(mName),
 358                   sourceFileCount(0),
 359                   sourceFileList(NULL),
 360                   lineInformationList(NULL) {}
 361
 362
 363 //desctructor
 364 LineInformation::~LineInformation() {
 365         for(int i=0;i<sourceFileCount;i++){
 366                 delete sourceFileList[i];
 367                 delete lineInformationList[i];
 368         }
 369         delete[] sourceFileList;
 370         delete[] lineInformationList;
 371 }
 372
 373 //method to insert entries for the given file name and function name
 374 //it creates the necessary structures and inserts into the maps
 375 void LineInformation::insertSourceFileName(string functionName,string fileName)
 376 {
 377         FileLineInformation* fInfo = getFileLineInformation(fileName);
 378         if(!fInfo){
 379                 fInfo = new FileLineInformation(fileName);
 380                 sourceFileList = (string**)(sourceFileCount ?
 381                         realloc(sourceFileList,(sourceFileCount+1)*sizeof(string*)) :
 382                         new string*[1]);
 383                 lineInformationList = (FileLineInformation**)(sourceFileCount ?
 384                         realloc(lineInformationList,(sourceFileCount+1)*sizeof(FileLineInformation*)) :
 385                         new FileLineInformation*[1]);
 386                 sourceFileList[sourceFileCount] = new string(fileName);
 387                 lineInformationList[sourceFileCount] = fInfo;
 388                 sourceFileCount++;
 389         }
 390         fInfo->insertFunction(functionName);
 391 }
 392
 393 //inserts line to address and address to line mapping to the line info
 394 //object of the given filename. The records for function is also updated
 395 void LineInformation::insertLineAddress(string functionName,
 396                                         string fileName,
 397                                         unsigned short lineNo,
 398                                         Address codeAddress)
 399 {
 400         FileLineInformation* fInfo = getFileLineInformation(fileName);
 401         if(!fInfo) return;
 402         fInfo->insertLineAddress(functionName,lineNo,codeAddress);
 403 }
 404
 405 //returns line number corresponding to the the given address
 406 //if isFile is set the search is file level otherwsie function level.
 407 bool LineInformation::getLineFromAddr(string name,
 408                                       unsigned short& lineNo,
 409                                       Address codeAddress,
 410                                       bool isFile,
 411                                       bool isExactMatch)
 412 {
 413         FileLineInformation* fInfo = NULL;
 414         if(isFile)
 415                 fInfo = getFileLineInformation(name);
 416         else
 417                 fInfo = getFunctionLineInformation(name);
 418
 419         if(!fInfo) return false;
 420
 421         return fInfo->getLineFromAddr(name,lineNo,codeAddress,isFile,isExactMatch);
 422 }
 423
 424 //returns line number corresponding to the the given address
 425 //if isFile is set the search is file level otherwsie function level.
 426 bool LineInformation::getLineFromAddr(string name,
 427                                       BPatch_Set<unsigned short>& lines,
 428                                       Address codeAddress,
 429                                       bool isFile,
 430                                       bool isExactMatch)
 431 {
 432         FileLineInformation* fInfo = NULL;
 433         if(isFile)
 434                 fInfo = getFileLineInformation(name);
 435         else
 436                 fInfo = getFunctionLineInformation(name);
 437
 438         if(!fInfo) return false;
 439
 440         return fInfo->getLineFromAddr(name,lines,codeAddress,isFile,isExactMatch);
 441 }
 442
 443 //returns address corresponding to the the given line
 444 //if isFile is set the search is file level otherwsie function level.
 445 bool LineInformation::getAddrFromLine(string name,
 446                                       BPatch_Set<Address>& codeAddress,
 447                                       unsigned short lineNo,
 448                                       bool isFile,
 449                                       bool isExactMatch)
 450 {
 451         FileLineInformation* fInfo = NULL;
 452         if(isFile)
 453                 fInfo = getFileLineInformation(name);
 454         else
 455                 fInfo = getFunctionLineInformation(name);
 456
 457         if(!fInfo) return false;
 458
 459         return fInfo->getAddrFromLine(name,codeAddress,lineNo,isFile,isExactMatch);
 460 }
 461
 462 bool LineInformation::getAddrFromLine(BPatch_Set<Address>& codeAddress,
 463                                       unsigned short lineNo,
 464                                       bool isExactMatch)
 465 {
 466         FileLineInformation* fInfo = getFileLineInformation(moduleName);
 467         if(!fInfo){
 468 #ifdef DEBUG_LINE
 469                 cerr << "Module " << moduleName << " is not source file name\n";
 470 #endif
 471                 return false;
 472         }
 473         return fInfo->getAddrFromLine(moduleName,codeAddress,
 474                                       lineNo,true,isExactMatch);
 475 }
 476
 477 //returns the line information for the given filename
 478 FileLineInformation* LineInformation::getFileLineInformation(string fileName){
 479         for(int j=0;j<sourceFileCount;j++)
 480                 if(fileName == *sourceFileList[j])
 481                         return lineInformationList[j];
 482         for(int i=0;i<sourceFileCount;i++){
 483                 char* name = new char[sourceFileList[i]->length()+1];
 484                 strncpy(name,sourceFileList[i]->string_of(),
 485                         sourceFileList[i]->length());
 486                 name[sourceFileList[i]->length()] = '\0';
 487                 char* p = strrchr(name,'/');
 488                 if(!p) {
 489                         delete[] name;
 490                         continue;
 491                 }
 492                 p++;
 493                 string sname(p);
 494                 if(fileName == sname){
 495                         delete[] name;
 496                         return lineInformationList[i];
 497                 }
 498                 delete[] name;
 499         }
 500
 501         return NULL;
 502 }
 503
 504 //method retuns the file line information object which the function belongs to.
 505 //if there is no entry than it retuns NULL
 506 FileLineInformation*
 507 LineInformation::getFunctionLineInformation(string functionName){
 508         for(int i=0;i<sourceFileCount;i++)
 509                 if(lineInformationList[i]->findFunction(functionName))
 510                         return lineInformationList[i];
 511         return NULL;
 512 }
 513
 514 //method that returns true if function belongs to this object
 515 //false otherwise
 516 bool LineInformation::findFunction(string functionName){
 517         bool ret = false;
 518         for(int i=0;!ret && (i<sourceFileCount);i++)
 519                 ret = lineInformationList[i]->findFunction(functionName);
 520         return ret;
 521 }
 522
 523 //print the line information kept in the map
 524 void LineInformation::print(){
 525         cerr << "**********************************************\n";
 526         cerr << "MODULE : " << moduleName << "\n";
 527         cerr << "**********************************************\n";
 528         for(int i=0;i<sourceFileCount;i++){
 529                 cerr << "FILE : " << *sourceFileList[i] << "\n";
 530                 lineInformationList[i]->print();
 531         }
 532 }
 533