Function relocation on x86 - - - - - - - - - - - - - - - - - - - - - - -
[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.11 2005/08/25 22:45:23 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
54 multiTramp *codeRange::is_multitramp() {
55     if (dynamic_cast<multiTramp *>(this))
56         return dynamic_cast<multiTramp *>(this);
57     else if (dynamic_cast<instArea *>(this))
58         return (dynamic_cast<instArea *>(this))->multi;
59     return NULL;
60 }
61
62 // This is a special case... the multitramp is the thing in the
63 // codeRange tree, but people think of baseTramps.
64 // So this is dangerous to use, actually.
65 baseTrampInstance *codeRange::is_basetramp_multi() {
66    return dynamic_cast<baseTrampInstance *>(this);
67 }
68
69 miniTrampInstance *codeRange::is_minitramp() {
70    return dynamic_cast<miniTrampInstance *>(this);
71 }
72
73 bblInstance *codeRange::is_basicBlockInstance() {
74     return dynamic_cast<bblInstance *>(this);
75 }
76
77 int_basicBlock *codeRange::is_basicBlock() {
78     bblInstance *block = dynamic_cast<bblInstance *>(this);
79     if (block)
80         return block->block();
81     return NULL;
82 }
83
84 int_function *codeRange::is_function() {
85     bblInstance *block = dynamic_cast<bblInstance *>(this);
86     if (block)
87         return block->func();
88     return NULL;
89 }
90
91 image_func *codeRange::is_image_func() {
92    return dynamic_cast<image_func *>(this);
93 }
94
95 replacedFunctionCall *codeRange::is_replaced_call() {
96     return dynamic_cast<replacedFunctionCall *>(this);
97 }
98
99 functionReplacement *codeRange::is_function_replacement() {
100     return dynamic_cast<functionReplacement *>(this);
101 }
102
103
104 image *codeRange::is_image() {
105    return dynamic_cast<image *>(this);
106 }
107
108 mapped_object *codeRange::is_mapped_object() {
109    return dynamic_cast<mapped_object *>(this);
110 }
111
112 void codeRangeTree::leftRotate(entry* pivot){
113         if(!pivot || (pivot == nil))
114                 return;
115         entry* y = pivot->right;
116         if(y == nil)
117                 return;
118         pivot->right = y->left;
119         if(y->left != nil)
120                 y->left->parent = pivot;
121         y->parent = pivot->parent;
122         if(!pivot->parent) {
123                 setData = y;
124         }
125         else if(pivot == pivot->parent->left)
126                 pivot->parent->left = y;
127         else
128                 pivot->parent->right = y;
129         y->left = pivot;
130         pivot->parent = y;
131 }
132
133
134 void codeRangeTree::rightRotate(entry* pivot){
135         if(!pivot || (pivot == nil))
136                 return;
137         entry* x = pivot->left;
138         if(x == nil)
139                 return;
140         pivot->left = x->right;
141         if(x->right != nil)
142                 x->right->parent = pivot;
143         x->parent = pivot->parent;
144         if(!pivot->parent) {
145                 setData = x;
146         }
147         else if(pivot == pivot->parent->left)
148                 pivot->parent->left = x;
149         else
150                 pivot->parent->right = x;
151         x->right = pivot;
152         pivot->parent = x;
153 }
154
155
156 void codeRangeTree::deleteFixup(entry* x){
157         while((x != setData) && 
158               (x->color == TREE_BLACK))
159         {
160                 if(x == x->parent->left){
161                         entry* w = x->parent->right;
162                         if(w->color == TREE_RED){
163                                 w->color = TREE_BLACK;
164                                 x->parent->color = TREE_RED;
165                                 leftRotate(x->parent);
166                                 w = x->parent->right;
167                         }
168                         if((w->left->color == TREE_BLACK) &&
169                            (w->right->color == TREE_BLACK)){
170                                 w->color = TREE_RED;
171                                 x = x->parent;
172                         }
173                         else{
174                                 if(w->right->color == TREE_BLACK){
175                                         w->left->color = TREE_BLACK;
176                                         w->color = TREE_RED;
177                                         rightRotate(w);
178                                         w = x->parent->right;
179                                 }
180                                 w->color = x->parent->color;
181                                 x->parent->color = TREE_BLACK;
182                                 w->right->color = TREE_BLACK;
183                                 leftRotate(x->parent);
184                                 x = setData;
185                         }
186                 }
187                 else{
188                         entry* w = x->parent->left;
189                         if(w->color == TREE_RED){
190                                 w->color = TREE_BLACK;
191                                 x->parent->color = TREE_RED;
192                                 rightRotate(x->parent);
193                                 w = x->parent->left;
194                         }
195                         if((w->right->color == TREE_BLACK) &&
196                            (w->left->color == TREE_BLACK)){
197                                 w->color = TREE_RED;
198                                 x = x->parent;
199                         }
200                         else{
201                                 if(w->left->color == TREE_BLACK){
202                                         w->right->color = TREE_BLACK;
203                                         w->color = TREE_RED;
204                                         leftRotate(w);
205                                         w = x->parent->left;
206                                 }
207                                 w->color = x->parent->color;
208                                 x->parent->color = TREE_BLACK;
209                                 w->left->color = TREE_BLACK;
210                                 rightRotate(x->parent);
211                                 x = setData;
212                         }
213                 }
214         }
215         x->color = TREE_BLACK;
216 }
217
218
219 codeRangeTree::entry *codeRangeTree::treeInsert(Address key, codeRange *value)
220 {
221         entry* y = NULL;
222         entry* x = setData;
223         while(x != nil){
224                 y = x;
225                 if (key < x->key) 
226                     x = x->left;
227                 else if(key > x->key)
228                     x = x->right;
229                 else
230                     return NULL;
231         }       
232         entry* z = new entry(key, value, nil);
233         z->parent = y;
234         if(!y) {
235                 setData = z;
236         }
237         else {
238         if (key < y->key)
239             y->left = z;
240                 else if (key > y->key)
241                         y->right = z;
242         }
243         setSize++;
244         return z;
245 }
246
247 /** finds the minimum value node when x is being deleted */
248
249 codeRangeTree::entry *codeRangeTree::treeSuccessor(entry* x) const{
250         if(!x || (x == nil))
251                 return NULL;
252         if(x->right != nil){
253                 entry* z = x->right;
254                 while(z->left != nil) z = z->left;
255                 return z;
256         }
257         entry* y = x->parent;
258         while(y && (x == y->right)){
259                 x = y;
260                 y = y->parent;
261         }
262         return y;
263 }
264
265
266 codeRangeTree::entry *codeRangeTree::find_internal(Address element) const{
267         entry* x = setData;
268         while(x != nil){
269             if (element < x->key) {
270                 x = x->left;
271             }
272             else if (element > x->key) {
273                 x = x->right;
274             }
275             else
276                 return x;
277         }       
278         return NULL;
279 }
280
281
282 void codeRangeTree::traverse(codeRange ** all, entry* node, int& n) const{
283         if(node == nil)
284                 return;
285         if(node->left != nil)
286                 traverse(all,node->left,n);
287         if(all)
288                 all[n++] = node->value;
289         if(node->right != nil)
290                 traverse(all,node->right,n);
291 }
292
293
294 void codeRangeTree::traverse(pdvector<codeRange *> &all, entry* node) const{
295         if(node == nil)
296                 return;
297         if(node->left != nil)
298                 traverse(all,node->left);
299         all.push_back(node->value);
300         if(node->right != nil)
301                 traverse(all,node->right);
302 }
303
304 //////////////////////////// PUBLIC FUNCTIONS ////////////////////////////////
305
306 void codeRangeTree::insert(codeRange *value) {
307         entry* x = treeInsert(value->get_address_cr(), value);
308         if(!x) {
309             // We're done.
310             return;
311         }
312         x->color = TREE_RED;
313         while((x != setData) && (x->parent->color == TREE_RED)){
314                 if(x->parent == x->parent->parent->left){
315                         entry* y = x->parent->parent->right;
316                         if(y->color == TREE_RED){
317                                 x->parent->color = TREE_BLACK;
318                                 y->color = TREE_BLACK;
319                                 x->parent->parent->color = TREE_RED;
320                                 x = x->parent->parent;
321                         }
322                         else{
323                                 if(x == x->parent->right){
324                                         x = x->parent;
325                                         leftRotate(x);
326                                 }
327                                 x->parent->color = TREE_BLACK;
328                                 x->parent->parent->color = TREE_RED;
329                                 rightRotate(x->parent->parent);
330                         }
331                 }
332                 else{
333                         entry* y = x->parent->parent->left;
334                         if(y->color == TREE_RED){
335                                 x->parent->color = TREE_BLACK;
336                                 y->color = TREE_BLACK;
337                                 x->parent->parent->color = TREE_RED;
338                                 x = x->parent->parent;
339                         }
340                         else{
341                                 if(x == x->parent->left){
342                                         x = x->parent;
343                                         rightRotate(x);
344                                 }
345                                 x->parent->color = TREE_BLACK;
346                                 x->parent->parent->color = TREE_RED;
347                                 leftRotate(x->parent->parent);
348                         }
349                 }
350         }
351         setData->color = TREE_BLACK;
352 }
353
354  void codeRangeTree::remove(Address key){
355         entry* z = find_internal(key);
356         if(!z)
357                 return;
358         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
359         entry* x=(y->left != nil) ? y->left : y->right;
360         x->parent = y->parent;
361         if(!y->parent) {
362                 setData = x;
363         }
364         else if(y == y->parent->left)
365                 y->parent->left = x;
366         else
367                 y->parent->right = x;
368         if(y != z) {
369                 z->value = y->value;
370         z->key = y->key;
371     }
372         if(y->color == TREE_BLACK)
373                 deleteFixup(x);
374         setSize--;
375         delete y;
376 }
377
378
379
380
381 void codeRangeTree::destroy(entry* node){
382         if(!node || (node == nil))
383                 return;
384         if(node->left != nil)
385                 destroy(node->left);
386         if(node->right != nil)
387                 destroy(node->right);
388         delete node;
389 }
390
391 bool codeRangeTree::find(Address key, codeRange *& value) const{
392     value = NULL;
393     if (!precessor(key, value))
394         return false;
395     // Check to see if the range works
396     if (!value->get_size_cr()) {
397         cerr << "Warning: size was 0..." << endl;
398     }
399     if (key >= (value->get_address_cr() + value->get_size_cr())) {
400         return false;
401     }
402     // We can also underflow
403     if (key < value->get_address_cr())
404         return false;
405     return true;
406 #if 0
407     fprintf(stderr, "codeRangeTree::find for 0x%x\n", key);
408     entry* x = find_internal(key);
409     fprintf(stderr, "find_internal returned %p\n", x);
410     if (!x) return false;
411     value = x->value;
412     assert(value->get_address_cr() <= key); // Otherwise it wouldn't have been returned.
413
414     if (key >= (value->get_address_cr() + value->get_size_cr())) {
415         fprintf(stderr, "... ret false\n");
416         return false;
417     }
418     fprintf(stderr, "... ret true\n");
419     return true;
420 #endif
421 }
422
423 bool codeRangeTree::precessor(Address key, codeRange * &value) const{
424     entry *x = setData;
425     entry *last = nil;
426     while (x != nil) {
427         assert(x != NULL);
428         if (x->key == key) {
429             value = x->value;
430             return true;
431         }
432         else if (key < x->key) {
433             x = x->left;
434         }
435         else { // key > x->key
436             last = x;
437             x = x->right;
438         }
439     }
440     if (x == nil) {
441         // Ran out of tree to search... get the parent
442         assert(last != NULL);
443         if (last != nil) {
444             value = last->value;
445             return true;
446         }
447         else return false;
448     }
449     // Should never hit here
450     assert(0);
451     return false;
452 }
453
454 bool codeRangeTree::successor(Address key, codeRange * &value) const{
455     entry *x = setData;
456     entry *last = nil;
457     while (x != nil) {
458         if (x->key == key) {
459             value = x->value;
460             return true;
461         }
462         else if (key > x->key) {
463             x = x->right;
464         }
465         else { // key < x->key
466             last = x;
467             x = x->left;
468         }
469     }
470     if (x == nil) {
471         // Ran out of tree to search... get the parent
472         if (last != nil) {
473             value = last->value;
474             return true;
475         }
476         else return false;
477     }
478     // Should never reach this point
479     assert(0);
480     return false;
481 }
482
483 codeRange ** codeRangeTree::elements(codeRange ** buffer) const{
484         if(setData == nil) return NULL;
485         if(!buffer) return NULL;
486         int tmp = 0;
487         traverse(buffer,setData,tmp);   
488         return buffer;
489 }
490
491 bool codeRangeTree::elements(pdvector<codeRange *> &buffer) const{
492         if(setData == nil) return false;
493         traverse(buffer,setData);       
494         return true;
495 }
496
497 void codeRangeTree::clear() {
498     if (setData == nil) return;
499     destroy(setData);
500     setData = nil;
501     setSize = 0;
502 }