Make writeVariable work properly with the binary rewriter.
[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.21 2008/01/16 22:01:51 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 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(), 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         if (z->key != key)
368             return;
369
370         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
371         entry* x=(y->left != nil) ? y->left : y->right;
372         x->parent = y->parent;
373         if(!y->parent) {
374                 setData = x;
375         }
376         else if(y == y->parent->left)
377                 y->parent->left = x;
378         else
379                 y->parent->right = x;
380         if(y != z) {
381                 z->value = y->value;
382         z->key = y->key;
383     }
384         if(y->color == TREE_BLACK)
385                 deleteFixup(x);
386         setSize--;
387         delete y;
388 }
389
390
391
392
393 void codeRangeTree::destroy(entry* node){
394         if(!node || (node == nil))
395                 return;
396         if(node->left != nil)
397                 destroy(node->left);
398         if(node->right != nil)
399                 destroy(node->right);
400         delete node;
401 }
402
403 bool codeRangeTree::find(Address key, codeRange *& value) const{
404     value = NULL;
405     if (!precessor(key, value))
406         return false;
407     // Check to see if the range works
408     if (!value->get_size()) {
409         // XXX do we really need this warning?
410         //fprintf(stderr, "%s[%d]:  Warning:  size was 0...\n", FILE__, __LINE__);
411         if(key > value->get_address())
412             return false;
413     }
414     else if(key >= (value->get_address() + value->get_size())) {
415         return false;
416     }
417     // We can also underflow
418     if (key < value->get_address()) {
419       return false;
420     }
421     
422     return true;
423 #if 0
424     fprintf(stderr, "codeRangeTree::find for 0x%x\n", key);
425     entry* x = find_internal(key);
426     fprintf(stderr, "find_internal returned %p\n", x);
427     if (!x) return false;
428     value = x->value;
429     assert(value->get_address() <= key); // Otherwise it wouldn't have been returned.
430
431     if (key >= (value->get_address() + value->get_size())) {
432         fprintf(stderr, "... ret false\n");
433         return false;
434     }
435     fprintf(stderr, "... ret true\n");
436     return true;
437 #endif
438 }
439
440 bool codeRangeTree::precessor(Address key, codeRange * &value) const{
441     entry *x = setData;
442     entry *last = nil;
443     while (x != nil) {
444         assert(x != NULL);
445         if (x->key == key) {
446             value = x->value;
447             return true;
448         }
449         else if (key < x->key) {
450             x = x->left;
451         }
452         else { // key > x->key
453             last = x;
454             x = x->right;
455         }
456     }
457     if (x == nil) {
458         // Ran out of tree to search... get the parent
459         assert(last != NULL);
460         if (last != nil) {
461             value = last->value;
462             return true;
463         }
464         else return false;
465     }
466     // Should never hit here
467     assert(0);
468     return false;
469 }
470
471 bool codeRangeTree::successor(Address key, codeRange * &value) const{
472     entry *x = setData;
473     entry *last = nil;
474     while (x != nil) {
475         if (x->key == key) {
476             value = x->value;
477             return true;
478         }
479         else if (key > x->key) {
480             x = x->right;
481         }
482         else { // key < x->key
483             last = x;
484             x = x->left;
485         }
486     }
487     if (x == nil) {
488         // Ran out of tree to search... get the parent
489         if (last != nil) {
490             value = last->value;
491             return true;
492         }
493         else return false;
494     }
495     // Should never reach this point
496     assert(0);
497     return false;
498 }
499
500 codeRange ** codeRangeTree::elements(codeRange ** buffer) const{
501         if(setData == nil) return NULL;
502         if(!buffer) return NULL;
503         int tmp = 0;
504         traverse(buffer,setData,tmp);   
505         return buffer;
506 }
507
508 bool codeRangeTree::elements(pdvector<codeRange *> &buffer) const{
509         if(setData == nil) return false;
510         traverse(buffer,setData);       
511         return true;
512 }
513
514 void codeRangeTree::clear() {
515     if (setData == nil) return;
516     destroy(setData);
517     setData = nil;
518     setSize = 0;
519 }
520
521 #define PRINT_COMMA if (print_comma) fprintf(stderr, ", "); print_comma = true
522 void codeRange::print_range(Address addr) {
523    bool print_comma = false;
524    image *img_ptr = is_image();
525    mapped_object *mapped_ptr = is_mapped_object();
526         int_function *func_ptr = is_function();
527    functionReplacement *reloc_ptr = is_function_replacement();
528    multiTramp *multi_ptr = is_multitramp();
529    baseTrampInstance *base_ptr = NULL;
530         miniTrampInstance *mini_ptr = is_minitramp();
531    inferiorRPCinProgress *rpc_ptr = is_inferior_rpc();
532
533    /**
534     * The is_* functions above won't give us mulitple layers of objects
535     * (i.e the fact we have a function pointer, doesn't mean we have a 
536     * mapped_object pointer).  Build up more information from what we have
537     **/
538    if (mini_ptr && !base_ptr) 
539       base_ptr = mini_ptr->baseTI;
540    if (base_ptr && !multi_ptr)
541       multi_ptr = base_ptr->multiT;
542    if (multi_ptr && !func_ptr) 
543       func_ptr = multi_ptr->func();
544    if (multi_ptr && !base_ptr && addr) 
545       base_ptr = multi_ptr->getBaseTrampInstanceByAddr(addr);
546    if (reloc_ptr && !func_ptr)
547       func_ptr = reloc_ptr->source()->func();
548    if (func_ptr && !mapped_ptr)
549       mapped_ptr = func_ptr->obj();
550    if (mapped_ptr && !img_ptr)
551       img_ptr = mapped_ptr->parse_img();
552
553    fprintf(stderr, "[");
554
555    if (img_ptr) {
556       PRINT_COMMA;
557       fprintf(stderr, "img:%s", img_ptr->name().c_str());
558    }
559    if (mapped_ptr) {
560       PRINT_COMMA;
561       fprintf(stderr, "map_obj:%s", mapped_ptr->fullName().c_str());
562    }
563    if (func_ptr) {
564       PRINT_COMMA;
565       fprintf(stderr, "func:%s", func_ptr->prettyName().c_str());
566    }
567    if (reloc_ptr) {
568       PRINT_COMMA;
569       fprintf(stderr, "reloc:%x", 
570               reloc_ptr->targetVersion());
571    }
572    if (multi_ptr) {
573       PRINT_COMMA;
574       fprintf(stderr, "multi:%p->%p+%u", (void *)multi_ptr->instAddr(), 
575               (void *)multi_ptr->get_address(), multi_ptr->get_size());
576    }
577    if (base_ptr) {
578       PRINT_COMMA;
579       fprintf(stderr, "base:%p+%u", (void *)multi_ptr->get_address(),
580               multi_ptr->get_size());
581    }
582    if (mini_ptr) {
583       PRINT_COMMA;
584       fprintf(stderr, "mini:%p+%u", (void *)multi_ptr->get_address(),
585               multi_ptr->get_size());
586    }
587    if (rpc_ptr) {
588       PRINT_COMMA;
589       fprintf(stderr, "rpc:%lx", rpc_ptr->get_address());
590    }
591    if (!print_comma)
592    {
593       fprintf(stderr, "Nothing");
594    }
595    fprintf(stderr, "]\n");
596 }
597