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