update dyninst parsing to support shared and non-contiguous code - - - -
[dyninst.git] / dyninstAPI / src / codeRange.C
1 /*
2  * Copyright (c) 1996-2004 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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 // $Id: codeRange.C,v 1.14 2006/01/14 23:47:43 nater Exp $
43
44 #include <stdio.h>
45 #include "codeRange.h"
46
47 #include "dyninstAPI/src/symtab.h"
48 #include "dyninstAPI/src/baseTramp.h"
49 #include "dyninstAPI/src/miniTramp.h"
50 #include "dyninstAPI/src/mapped_object.h"
51 #include "dyninstAPI/src/function.h"
52 #include "dyninstAPI/src/instPoint.h"
53 #include "dyninstAPI/src/rpcMgr.h"
54
55 multiTramp *codeRange::is_multitramp() {
56     if (dynamic_cast<multiTramp *>(this))
57         return dynamic_cast<multiTramp *>(this);
58     else if (dynamic_cast<instArea *>(this))
59         return (dynamic_cast<instArea *>(this))->multi;
60     return NULL;
61 }
62
63 inferiorRPCinProgress * codeRange::is_inferior_rpc() {
64         return dynamic_cast< inferiorRPCinProgress * >( this );
65         }
66
67 // This is a special case... the multitramp is the thing in the
68 // codeRange tree, but people think of baseTramps.
69 // So this is dangerous to use, actually.
70 baseTrampInstance *codeRange::is_basetramp_multi() {
71    return dynamic_cast<baseTrampInstance *>(this);
72 }
73
74 miniTrampInstance *codeRange::is_minitramp() {
75    return dynamic_cast<miniTrampInstance *>(this);
76 }
77
78 bblInstance *codeRange::is_basicBlockInstance() {
79     return dynamic_cast<bblInstance *>(this);
80 }
81
82 int_basicBlock *codeRange::is_basicBlock() {
83     bblInstance *block = dynamic_cast<bblInstance *>(this);
84     if (block)
85         return block->block();
86     return NULL;
87 }
88
89 int_function *codeRange::is_function() {
90     bblInstance *block = dynamic_cast<bblInstance *>(this);
91     if (block)
92         return block->func();
93     return NULL;
94 }
95
96 image_func *codeRange::is_image_func() {
97    return dynamic_cast<image_func *>(this);
98 }
99
100 image_basicBlock *codeRange::is_image_basicBlock() {
101     return dynamic_cast<image_basicBlock *>(this);
102 }
103
104 replacedFunctionCall *codeRange::is_replaced_call() {
105     return dynamic_cast<replacedFunctionCall *>(this);
106 }
107
108 functionReplacement *codeRange::is_function_replacement() {
109     return dynamic_cast<functionReplacement *>(this);
110 }
111
112
113 image *codeRange::is_image() {
114    return dynamic_cast<image *>(this);
115 }
116
117 mapped_object *codeRange::is_mapped_object() {
118    return dynamic_cast<mapped_object *>(this);
119 }
120
121 void codeRangeTree::leftRotate(entry* pivot){
122         if(!pivot || (pivot == nil))
123                 return;
124         entry* y = pivot->right;
125         if(y == nil)
126                 return;
127         pivot->right = y->left;
128         if(y->left != nil)
129                 y->left->parent = pivot;
130         y->parent = pivot->parent;
131         if(!pivot->parent) {
132                 setData = y;
133         }
134         else if(pivot == pivot->parent->left)
135                 pivot->parent->left = y;
136         else
137                 pivot->parent->right = y;
138         y->left = pivot;
139         pivot->parent = y;
140 }
141
142
143 void codeRangeTree::rightRotate(entry* pivot){
144         if(!pivot || (pivot == nil))
145                 return;
146         entry* x = pivot->left;
147         if(x == nil)
148                 return;
149         pivot->left = x->right;
150         if(x->right != nil)
151                 x->right->parent = pivot;
152         x->parent = pivot->parent;
153         if(!pivot->parent) {
154                 setData = x;
155         }
156         else if(pivot == pivot->parent->left)
157                 pivot->parent->left = x;
158         else
159                 pivot->parent->right = x;
160         x->right = pivot;
161         pivot->parent = x;
162 }
163
164
165 void codeRangeTree::deleteFixup(entry* x){
166         while((x != setData) && 
167               (x->color == TREE_BLACK))
168         {
169                 if(x == x->parent->left){
170                         entry* w = x->parent->right;
171                         if(w->color == TREE_RED){
172                                 w->color = TREE_BLACK;
173                                 x->parent->color = TREE_RED;
174                                 leftRotate(x->parent);
175                                 w = x->parent->right;
176                         }
177                         if((w->left->color == TREE_BLACK) &&
178                            (w->right->color == TREE_BLACK)){
179                                 w->color = TREE_RED;
180                                 x = x->parent;
181                         }
182                         else{
183                                 if(w->right->color == TREE_BLACK){
184                                         w->left->color = TREE_BLACK;
185                                         w->color = TREE_RED;
186                                         rightRotate(w);
187                                         w = x->parent->right;
188                                 }
189                                 w->color = x->parent->color;
190                                 x->parent->color = TREE_BLACK;
191                                 w->right->color = TREE_BLACK;
192                                 leftRotate(x->parent);
193                                 x = setData;
194                         }
195                 }
196                 else{
197                         entry* w = x->parent->left;
198                         if(w->color == TREE_RED){
199                                 w->color = TREE_BLACK;
200                                 x->parent->color = TREE_RED;
201                                 rightRotate(x->parent);
202                                 w = x->parent->left;
203                         }
204                         if((w->right->color == TREE_BLACK) &&
205                            (w->left->color == TREE_BLACK)){
206                                 w->color = TREE_RED;
207                                 x = x->parent;
208                         }
209                         else{
210                                 if(w->left->color == TREE_BLACK){
211                                         w->right->color = TREE_BLACK;
212                                         w->color = TREE_RED;
213                                         leftRotate(w);
214                                         w = x->parent->left;
215                                 }
216                                 w->color = x->parent->color;
217                                 x->parent->color = TREE_BLACK;
218                                 w->left->color = TREE_BLACK;
219                                 rightRotate(x->parent);
220                                 x = setData;
221                         }
222                 }
223         }
224         x->color = TREE_BLACK;
225 }
226
227
228 codeRangeTree::entry *codeRangeTree::treeInsert(Address key, codeRange *value)
229 {
230         entry* y = NULL;
231         entry* x = setData;
232         while(x != nil){
233                 y = x;
234                 if (key < x->key) 
235                     x = x->left;
236                 else if(key > x->key)
237                     x = x->right;
238                 else
239                     return NULL;
240         }       
241         entry* z = new entry(key, value, nil);
242         z->parent = y;
243         if(!y) {
244                 setData = z;
245         }
246         else {
247         if (key < y->key)
248             y->left = z;
249                 else if (key > y->key)
250                         y->right = z;
251         }
252         setSize++;
253         return z;
254 }
255
256 /** finds the minimum value node when x is being deleted */
257
258 codeRangeTree::entry *codeRangeTree::treeSuccessor(entry* x) const{
259         if(!x || (x == nil))
260                 return NULL;
261         if(x->right != nil){
262                 entry* z = x->right;
263                 while(z->left != nil) z = z->left;
264                 return z;
265         }
266         entry* y = x->parent;
267         while(y && (x == y->right)){
268                 x = y;
269                 y = y->parent;
270         }
271         return y;
272 }
273
274
275 codeRangeTree::entry *codeRangeTree::find_internal(Address element) const{
276         entry* x = setData;
277         while(x != nil){
278             if (element < x->key) {
279                 x = x->left;
280             }
281             else if (element > x->key) {
282                 x = x->right;
283             }
284             else
285                 return x;
286         }       
287         return NULL;
288 }
289
290
291 void codeRangeTree::traverse(codeRange ** all, entry* node, int& n) const{
292         if(node == nil)
293                 return;
294         if(node->left != nil)
295                 traverse(all,node->left,n);
296         if(all)
297                 all[n++] = node->value;
298         if(node->right != nil)
299                 traverse(all,node->right,n);
300 }
301
302
303 void codeRangeTree::traverse(pdvector<codeRange *> &all, entry* node) const{
304         if(node == nil)
305                 return;
306         if(node->left != nil)
307                 traverse(all,node->left);
308         all.push_back(node->value);
309         if(node->right != nil)
310                 traverse(all,node->right);
311 }
312
313 //////////////////////////// PUBLIC FUNCTIONS ////////////////////////////////
314
315 void codeRangeTree::insert(codeRange *value) {
316         entry* x = treeInsert(value->get_address_cr(), value);
317         if(!x) {
318             // We're done.
319             return;
320         }
321         x->color = TREE_RED;
322         while((x != setData) && (x->parent->color == TREE_RED)){
323                 if(x->parent == x->parent->parent->left){
324                         entry* y = x->parent->parent->right;
325                         if(y->color == TREE_RED){
326                                 x->parent->color = TREE_BLACK;
327                                 y->color = TREE_BLACK;
328                                 x->parent->parent->color = TREE_RED;
329                                 x = x->parent->parent;
330                         }
331                         else{
332                                 if(x == x->parent->right){
333                                         x = x->parent;
334                                         leftRotate(x);
335                                 }
336                                 x->parent->color = TREE_BLACK;
337                                 x->parent->parent->color = TREE_RED;
338                                 rightRotate(x->parent->parent);
339                         }
340                 }
341                 else{
342                         entry* y = x->parent->parent->left;
343                         if(y->color == TREE_RED){
344                                 x->parent->color = TREE_BLACK;
345                                 y->color = TREE_BLACK;
346                                 x->parent->parent->color = TREE_RED;
347                                 x = x->parent->parent;
348                         }
349                         else{
350                                 if(x == x->parent->left){
351                                         x = x->parent;
352                                         rightRotate(x);
353                                 }
354                                 x->parent->color = TREE_BLACK;
355                                 x->parent->parent->color = TREE_RED;
356                                 leftRotate(x->parent->parent);
357                         }
358                 }
359         }
360         setData->color = TREE_BLACK;
361 }
362
363  void codeRangeTree::remove(Address key){
364         entry* z = find_internal(key);
365         if(!z)
366                 return;
367         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
368         entry* x=(y->left != nil) ? y->left : y->right;
369         x->parent = y->parent;
370         if(!y->parent) {
371                 setData = x;
372         }
373         else if(y == y->parent->left)
374                 y->parent->left = x;
375         else
376                 y->parent->right = x;
377         if(y != z) {
378                 z->value = y->value;
379         z->key = y->key;
380     }
381         if(y->color == TREE_BLACK)
382                 deleteFixup(x);
383         setSize--;
384         delete y;
385 }
386
387
388
389
390 void codeRangeTree::destroy(entry* node){
391         if(!node || (node == nil))
392                 return;
393         if(node->left != nil)
394                 destroy(node->left);
395         if(node->right != nil)
396                 destroy(node->right);
397         delete node;
398 }
399
400 bool codeRangeTree::find(Address key, codeRange *& value) const{
401     value = NULL;
402     if (!precessor(key, value))
403         return false;
404     // Check to see if the range works
405     if (!value->get_size_cr()) {
406         cerr << "Warning: size was 0..." << endl;
407     }
408     if (key >= (value->get_address_cr() + value->get_size_cr())) {
409         return false;
410     }
411     // We can also underflow
412     if (key < value->get_address_cr())
413         return false;
414     return true;
415 #if 0
416     fprintf(stderr, "codeRangeTree::find for 0x%x\n", key);
417     entry* x = find_internal(key);
418     fprintf(stderr, "find_internal returned %p\n", x);
419     if (!x) return false;
420     value = x->value;
421     assert(value->get_address_cr() <= key); // Otherwise it wouldn't have been returned.
422
423     if (key >= (value->get_address_cr() + value->get_size_cr())) {
424         fprintf(stderr, "... ret false\n");
425         return false;
426     }
427     fprintf(stderr, "... ret true\n");
428     return true;
429 #endif
430 }
431
432 bool codeRangeTree::precessor(Address key, codeRange * &value) const{
433     entry *x = setData;
434     entry *last = nil;
435     while (x != nil) {
436         assert(x != NULL);
437         if (x->key == key) {
438             value = x->value;
439             return true;
440         }
441         else if (key < x->key) {
442             x = x->left;
443         }
444         else { // key > x->key
445             last = x;
446             x = x->right;
447         }
448     }
449     if (x == nil) {
450         // Ran out of tree to search... get the parent
451         assert(last != NULL);
452         if (last != nil) {
453             value = last->value;
454             return true;
455         }
456         else return false;
457     }
458     // Should never hit here
459     assert(0);
460     return false;
461 }
462
463 bool codeRangeTree::successor(Address key, codeRange * &value) const{
464     entry *x = setData;
465     entry *last = nil;
466     while (x != nil) {
467         if (x->key == key) {
468             value = x->value;
469             return true;
470         }
471         else if (key > x->key) {
472             x = x->right;
473         }
474         else { // key < x->key
475             last = x;
476             x = x->left;
477         }
478     }
479     if (x == nil) {
480         // Ran out of tree to search... get the parent
481         if (last != nil) {
482             value = last->value;
483             return true;
484         }
485         else return false;
486     }
487     // Should never reach this point
488     assert(0);
489     return false;
490 }
491
492 codeRange ** codeRangeTree::elements(codeRange ** buffer) const{
493         if(setData == nil) return NULL;
494         if(!buffer) return NULL;
495         int tmp = 0;
496         traverse(buffer,setData,tmp);   
497         return buffer;
498 }
499
500 bool codeRangeTree::elements(pdvector<codeRange *> &buffer) const{
501         if(setData == nil) return false;
502         traverse(buffer,setData);       
503         return true;
504 }
505
506 void codeRangeTree::clear() {
507     if (setData == nil) return;
508     destroy(setData);
509     setData = nil;
510     setSize = 0;
511 }
512
513 #define PRINT_COMMA if (print_comma) fprintf(stderr, ", "); print_comma = true
514 void codeRange::print_range(Address addr) {
515    bool print_comma = false;
516    image *img_ptr = is_image();
517    mapped_object *mapped_ptr = is_mapped_object();
518         int_function *func_ptr = is_function();
519    functionReplacement *reloc_ptr = is_function_replacement();
520    multiTramp *multi_ptr = is_multitramp();
521    baseTrampInstance *base_ptr = NULL;
522         miniTrampInstance *mini_ptr = is_minitramp();
523    inferiorRPCinProgress *rpc_ptr = is_inferior_rpc();
524
525    /**
526     * The is_* functions above won't give us mulitple layers of objects
527     * (i.e the fact we have a function pointer, doesn't mean we have a 
528     * mapped_object pointer).  Build up more information from what we have
529     **/
530    if (mini_ptr && !base_ptr) 
531       base_ptr = mini_ptr->baseTI;
532    if (base_ptr && !multi_ptr)
533       multi_ptr = base_ptr->multiT;
534    if (multi_ptr && !func_ptr) 
535       func_ptr = multi_ptr->func();
536    if (multi_ptr && !base_ptr && addr) 
537       base_ptr = multi_ptr->getBaseTrampInstanceByAddr(addr);
538    if (reloc_ptr && !func_ptr)
539       func_ptr = reloc_ptr->source()->func();
540    if (func_ptr && !mapped_ptr)
541       mapped_ptr = func_ptr->obj();
542    if (mapped_ptr && !img_ptr)
543       img_ptr = mapped_ptr->parse_img();
544
545    fprintf(stderr, "[");
546
547    if (img_ptr) {
548       PRINT_COMMA;
549       fprintf(stderr, "img:%s", img_ptr->name().c_str());
550    }
551    if (mapped_ptr) {
552       PRINT_COMMA;
553       fprintf(stderr, "map_obj:%s", mapped_ptr->fullName().c_str());
554    }
555    if (func_ptr) {
556       PRINT_COMMA;
557       fprintf(stderr, "func:%s", func_ptr->prettyName().c_str());
558    }
559    if (reloc_ptr) {
560       PRINT_COMMA;
561       fprintf(stderr, "reloc:%lx", 
562               reloc_ptr->targetVersion());
563    }
564    if (multi_ptr) {
565       PRINT_COMMA;
566       fprintf(stderr, "multi:%lx->%lx+%u", multi_ptr->instAddr(), 
567               multi_ptr->get_address_cr(), multi_ptr->get_size_cr());
568    }
569    if (base_ptr) {
570       PRINT_COMMA;
571       fprintf(stderr, "base:%lx+%lx", multi_ptr->get_address_cr(),
572               multi_ptr->get_size_cr());
573    }
574    if (mini_ptr) {
575       PRINT_COMMA;
576       fprintf(stderr, "mini:%lx+%lx", multi_ptr->get_address_cr(),
577               multi_ptr->get_size_cr());
578    }
579    if (rpc_ptr) {
580       PRINT_COMMA;
581       fprintf(stderr, "rpc:%lx", rpc_ptr->get_address_cr());
582    }
583    if (!print_comma)
584    {
585       fprintf(stderr, "Nothing");
586    }
587    fprintf(stderr, "]\n");
588 }
589