Adds a print operator to our code ranges
[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.13 2005/10/21 21:48:14 legendre 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 replacedFunctionCall *codeRange::is_replaced_call() {
101     return dynamic_cast<replacedFunctionCall *>(this);
102 }
103
104 functionReplacement *codeRange::is_function_replacement() {
105     return dynamic_cast<functionReplacement *>(this);
106 }
107
108
109 image *codeRange::is_image() {
110    return dynamic_cast<image *>(this);
111 }
112
113 mapped_object *codeRange::is_mapped_object() {
114    return dynamic_cast<mapped_object *>(this);
115 }
116
117 void codeRangeTree::leftRotate(entry* pivot){
118         if(!pivot || (pivot == nil))
119                 return;
120         entry* y = pivot->right;
121         if(y == nil)
122                 return;
123         pivot->right = y->left;
124         if(y->left != nil)
125                 y->left->parent = pivot;
126         y->parent = pivot->parent;
127         if(!pivot->parent) {
128                 setData = y;
129         }
130         else if(pivot == pivot->parent->left)
131                 pivot->parent->left = y;
132         else
133                 pivot->parent->right = y;
134         y->left = pivot;
135         pivot->parent = y;
136 }
137
138
139 void codeRangeTree::rightRotate(entry* pivot){
140         if(!pivot || (pivot == nil))
141                 return;
142         entry* x = pivot->left;
143         if(x == nil)
144                 return;
145         pivot->left = x->right;
146         if(x->right != nil)
147                 x->right->parent = pivot;
148         x->parent = pivot->parent;
149         if(!pivot->parent) {
150                 setData = x;
151         }
152         else if(pivot == pivot->parent->left)
153                 pivot->parent->left = x;
154         else
155                 pivot->parent->right = x;
156         x->right = pivot;
157         pivot->parent = x;
158 }
159
160
161 void codeRangeTree::deleteFixup(entry* x){
162         while((x != setData) && 
163               (x->color == TREE_BLACK))
164         {
165                 if(x == x->parent->left){
166                         entry* w = x->parent->right;
167                         if(w->color == TREE_RED){
168                                 w->color = TREE_BLACK;
169                                 x->parent->color = TREE_RED;
170                                 leftRotate(x->parent);
171                                 w = x->parent->right;
172                         }
173                         if((w->left->color == TREE_BLACK) &&
174                            (w->right->color == TREE_BLACK)){
175                                 w->color = TREE_RED;
176                                 x = x->parent;
177                         }
178                         else{
179                                 if(w->right->color == TREE_BLACK){
180                                         w->left->color = TREE_BLACK;
181                                         w->color = TREE_RED;
182                                         rightRotate(w);
183                                         w = x->parent->right;
184                                 }
185                                 w->color = x->parent->color;
186                                 x->parent->color = TREE_BLACK;
187                                 w->right->color = TREE_BLACK;
188                                 leftRotate(x->parent);
189                                 x = setData;
190                         }
191                 }
192                 else{
193                         entry* w = x->parent->left;
194                         if(w->color == TREE_RED){
195                                 w->color = TREE_BLACK;
196                                 x->parent->color = TREE_RED;
197                                 rightRotate(x->parent);
198                                 w = x->parent->left;
199                         }
200                         if((w->right->color == TREE_BLACK) &&
201                            (w->left->color == TREE_BLACK)){
202                                 w->color = TREE_RED;
203                                 x = x->parent;
204                         }
205                         else{
206                                 if(w->left->color == TREE_BLACK){
207                                         w->right->color = TREE_BLACK;
208                                         w->color = TREE_RED;
209                                         leftRotate(w);
210                                         w = x->parent->left;
211                                 }
212                                 w->color = x->parent->color;
213                                 x->parent->color = TREE_BLACK;
214                                 w->left->color = TREE_BLACK;
215                                 rightRotate(x->parent);
216                                 x = setData;
217                         }
218                 }
219         }
220         x->color = TREE_BLACK;
221 }
222
223
224 codeRangeTree::entry *codeRangeTree::treeInsert(Address key, codeRange *value)
225 {
226         entry* y = NULL;
227         entry* x = setData;
228         while(x != nil){
229                 y = x;
230                 if (key < x->key) 
231                     x = x->left;
232                 else if(key > x->key)
233                     x = x->right;
234                 else
235                     return NULL;
236         }       
237         entry* z = new entry(key, value, nil);
238         z->parent = y;
239         if(!y) {
240                 setData = z;
241         }
242         else {
243         if (key < y->key)
244             y->left = z;
245                 else if (key > y->key)
246                         y->right = z;
247         }
248         setSize++;
249         return z;
250 }
251
252 /** finds the minimum value node when x is being deleted */
253
254 codeRangeTree::entry *codeRangeTree::treeSuccessor(entry* x) const{
255         if(!x || (x == nil))
256                 return NULL;
257         if(x->right != nil){
258                 entry* z = x->right;
259                 while(z->left != nil) z = z->left;
260                 return z;
261         }
262         entry* y = x->parent;
263         while(y && (x == y->right)){
264                 x = y;
265                 y = y->parent;
266         }
267         return y;
268 }
269
270
271 codeRangeTree::entry *codeRangeTree::find_internal(Address element) const{
272         entry* x = setData;
273         while(x != nil){
274             if (element < x->key) {
275                 x = x->left;
276             }
277             else if (element > x->key) {
278                 x = x->right;
279             }
280             else
281                 return x;
282         }       
283         return NULL;
284 }
285
286
287 void codeRangeTree::traverse(codeRange ** all, entry* node, int& n) const{
288         if(node == nil)
289                 return;
290         if(node->left != nil)
291                 traverse(all,node->left,n);
292         if(all)
293                 all[n++] = node->value;
294         if(node->right != nil)
295                 traverse(all,node->right,n);
296 }
297
298
299 void codeRangeTree::traverse(pdvector<codeRange *> &all, entry* node) const{
300         if(node == nil)
301                 return;
302         if(node->left != nil)
303                 traverse(all,node->left);
304         all.push_back(node->value);
305         if(node->right != nil)
306                 traverse(all,node->right);
307 }
308
309 //////////////////////////// PUBLIC FUNCTIONS ////////////////////////////////
310
311 void codeRangeTree::insert(codeRange *value) {
312         entry* x = treeInsert(value->get_address_cr(), value);
313         if(!x) {
314             // We're done.
315             return;
316         }
317         x->color = TREE_RED;
318         while((x != setData) && (x->parent->color == TREE_RED)){
319                 if(x->parent == x->parent->parent->left){
320                         entry* y = x->parent->parent->right;
321                         if(y->color == TREE_RED){
322                                 x->parent->color = TREE_BLACK;
323                                 y->color = TREE_BLACK;
324                                 x->parent->parent->color = TREE_RED;
325                                 x = x->parent->parent;
326                         }
327                         else{
328                                 if(x == x->parent->right){
329                                         x = x->parent;
330                                         leftRotate(x);
331                                 }
332                                 x->parent->color = TREE_BLACK;
333                                 x->parent->parent->color = TREE_RED;
334                                 rightRotate(x->parent->parent);
335                         }
336                 }
337                 else{
338                         entry* y = x->parent->parent->left;
339                         if(y->color == TREE_RED){
340                                 x->parent->color = TREE_BLACK;
341                                 y->color = TREE_BLACK;
342                                 x->parent->parent->color = TREE_RED;
343                                 x = x->parent->parent;
344                         }
345                         else{
346                                 if(x == x->parent->left){
347                                         x = x->parent;
348                                         rightRotate(x);
349                                 }
350                                 x->parent->color = TREE_BLACK;
351                                 x->parent->parent->color = TREE_RED;
352                                 leftRotate(x->parent->parent);
353                         }
354                 }
355         }
356         setData->color = TREE_BLACK;
357 }
358
359  void codeRangeTree::remove(Address key){
360         entry* z = find_internal(key);
361         if(!z)
362                 return;
363         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
364         entry* x=(y->left != nil) ? y->left : y->right;
365         x->parent = y->parent;
366         if(!y->parent) {
367                 setData = x;
368         }
369         else if(y == y->parent->left)
370                 y->parent->left = x;
371         else
372                 y->parent->right = x;
373         if(y != z) {
374                 z->value = y->value;
375         z->key = y->key;
376     }
377         if(y->color == TREE_BLACK)
378                 deleteFixup(x);
379         setSize--;
380         delete y;
381 }
382
383
384
385
386 void codeRangeTree::destroy(entry* node){
387         if(!node || (node == nil))
388                 return;
389         if(node->left != nil)
390                 destroy(node->left);
391         if(node->right != nil)
392                 destroy(node->right);
393         delete node;
394 }
395
396 bool codeRangeTree::find(Address key, codeRange *& value) const{
397     value = NULL;
398     if (!precessor(key, value))
399         return false;
400     // Check to see if the range works
401     if (!value->get_size_cr()) {
402         cerr << "Warning: size was 0..." << endl;
403     }
404     if (key >= (value->get_address_cr() + value->get_size_cr())) {
405         return false;
406     }
407     // We can also underflow
408     if (key < value->get_address_cr())
409         return false;
410     return true;
411 #if 0
412     fprintf(stderr, "codeRangeTree::find for 0x%x\n", key);
413     entry* x = find_internal(key);
414     fprintf(stderr, "find_internal returned %p\n", x);
415     if (!x) return false;
416     value = x->value;
417     assert(value->get_address_cr() <= key); // Otherwise it wouldn't have been returned.
418
419     if (key >= (value->get_address_cr() + value->get_size_cr())) {
420         fprintf(stderr, "... ret false\n");
421         return false;
422     }
423     fprintf(stderr, "... ret true\n");
424     return true;
425 #endif
426 }
427
428 bool codeRangeTree::precessor(Address key, codeRange * &value) const{
429     entry *x = setData;
430     entry *last = nil;
431     while (x != nil) {
432         assert(x != NULL);
433         if (x->key == key) {
434             value = x->value;
435             return true;
436         }
437         else if (key < x->key) {
438             x = x->left;
439         }
440         else { // key > x->key
441             last = x;
442             x = x->right;
443         }
444     }
445     if (x == nil) {
446         // Ran out of tree to search... get the parent
447         assert(last != NULL);
448         if (last != nil) {
449             value = last->value;
450             return true;
451         }
452         else return false;
453     }
454     // Should never hit here
455     assert(0);
456     return false;
457 }
458
459 bool codeRangeTree::successor(Address key, codeRange * &value) const{
460     entry *x = setData;
461     entry *last = nil;
462     while (x != nil) {
463         if (x->key == key) {
464             value = x->value;
465             return true;
466         }
467         else if (key > x->key) {
468             x = x->right;
469         }
470         else { // key < x->key
471             last = x;
472             x = x->left;
473         }
474     }
475     if (x == nil) {
476         // Ran out of tree to search... get the parent
477         if (last != nil) {
478             value = last->value;
479             return true;
480         }
481         else return false;
482     }
483     // Should never reach this point
484     assert(0);
485     return false;
486 }
487
488 codeRange ** codeRangeTree::elements(codeRange ** buffer) const{
489         if(setData == nil) return NULL;
490         if(!buffer) return NULL;
491         int tmp = 0;
492         traverse(buffer,setData,tmp);   
493         return buffer;
494 }
495
496 bool codeRangeTree::elements(pdvector<codeRange *> &buffer) const{
497         if(setData == nil) return false;
498         traverse(buffer,setData);       
499         return true;
500 }
501
502 void codeRangeTree::clear() {
503     if (setData == nil) return;
504     destroy(setData);
505     setData = nil;
506     setSize = 0;
507 }
508
509 #define PRINT_COMMA if (print_comma) fprintf(stderr, ", "); print_comma = true
510 void codeRange::print_range(Address addr) {
511    bool print_comma = false;
512    image *img_ptr = is_image();
513    mapped_object *mapped_ptr = is_mapped_object();
514         int_function *func_ptr = is_function();
515    functionReplacement *reloc_ptr = is_function_replacement();
516    multiTramp *multi_ptr = is_multitramp();
517    baseTrampInstance *base_ptr = NULL;
518         miniTrampInstance *mini_ptr = is_minitramp();
519    inferiorRPCinProgress *rpc_ptr = is_inferior_rpc();
520
521    /**
522     * The is_* functions above won't give us mulitple layers of objects
523     * (i.e the fact we have a function pointer, doesn't mean we have a 
524     * mapped_object pointer).  Build up more information from what we have
525     **/
526    if (mini_ptr && !base_ptr) 
527       base_ptr = mini_ptr->baseTI;
528    if (base_ptr && !multi_ptr)
529       multi_ptr = base_ptr->multiT;
530    if (multi_ptr && !func_ptr) 
531       func_ptr = multi_ptr->func();
532    if (multi_ptr && !base_ptr && addr) 
533       base_ptr = multi_ptr->getBaseTrampInstanceByAddr(addr);
534    if (reloc_ptr && !func_ptr)
535       func_ptr = reloc_ptr->source()->func();
536    if (func_ptr && !mapped_ptr)
537       mapped_ptr = func_ptr->obj();
538    if (mapped_ptr && !img_ptr)
539       img_ptr = mapped_ptr->parse_img();
540
541    fprintf(stderr, "[");
542
543    if (img_ptr) {
544       PRINT_COMMA;
545       fprintf(stderr, "img:%s", img_ptr->name().c_str());
546    }
547    if (mapped_ptr) {
548       PRINT_COMMA;
549       fprintf(stderr, "map_obj:%s", mapped_ptr->fullName().c_str());
550    }
551    if (func_ptr) {
552       PRINT_COMMA;
553       fprintf(stderr, "func:%s", func_ptr->prettyName().c_str());
554    }
555    if (reloc_ptr) {
556       PRINT_COMMA;
557       fprintf(stderr, "reloc:%lx", 
558               reloc_ptr->targetVersion());
559    }
560    if (multi_ptr) {
561       PRINT_COMMA;
562       fprintf(stderr, "multi:%lx->%lx+%u", multi_ptr->instAddr(), 
563               multi_ptr->get_address_cr(), multi_ptr->get_size_cr());
564    }
565    if (base_ptr) {
566       PRINT_COMMA;
567       fprintf(stderr, "base:%lx+%lx", multi_ptr->get_address_cr(),
568               multi_ptr->get_size_cr());
569    }
570    if (mini_ptr) {
571       PRINT_COMMA;
572       fprintf(stderr, "mini:%lx+%lx", multi_ptr->get_address_cr(),
573               multi_ptr->get_size_cr());
574    }
575    if (rpc_ptr) {
576       PRINT_COMMA;
577       fprintf(stderr, "rpc:%lx", rpc_ptr->get_address_cr());
578    }
579    if (!print_comma)
580    {
581       fprintf(stderr, "Nothing");
582    }
583    fprintf(stderr, "]\n");
584 }
585