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