Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / addressSpace.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 #include "addressSpace.h"
33 #include "codeRange.h"
34 #include "process.h"
35 #include "binaryEdit.h"
36
37 #include "miniTramp.h"
38 #include "baseTramp.h"
39 #include "multiTramp.h" // multiTramp and instArea
40 #include "instPoint.h"
41
42 // Two-level codeRange structure
43 #include "mapped_object.h"
44 #include "mapped_module.h"
45 #if defined(cap_instruction_api)
46 #include "InstructionDecoder.h"
47 #include "Instruction.h"
48
49 #else
50 #include "InstrucIter.h"
51 #endif //defined(cap_instruction_api)
52
53 // Implementations of non-virtual functions in the address space
54 // class.
55
56 AddressSpace::AddressSpace () :
57     trapMapping(this),
58     runtime_lib(NULL),
59     useTraps_(true),
60     multiTrampsById_(intHash),
61     trampGuardBase_(NULL),
62     up_ptr_(NULL),
63     costAddr_(0)
64 {}
65
66 AddressSpace::~AddressSpace() {}
67
68 process *AddressSpace::proc() {
69     return dynamic_cast<process *>(this);
70 }
71
72 BinaryEdit *AddressSpace::edit() {
73     return dynamic_cast<BinaryEdit *>(this);
74 }
75
76 // Fork constructor - and so we can assume a parent "process"
77 // rather than "address space"
78 void AddressSpace::copyAddressSpace(process *parent) {
79     deleteAddressSpace();
80
81     // This is only defined for process->process copy
82     // until someone can give a good reason for copying
83     // anything else...
84
85     assert(proc());
86
87     // Mapped objects first
88     for (unsigned i = 0; i < parent->mapped_objects.size(); i++) {
89         mapped_object *par_obj = parent->mapped_objects[i];
90         mapped_object *child_obj = new mapped_object(par_obj, proc());
91         assert(child_obj);
92         
93         mapped_objects.push_back(child_obj);
94         addOrigRange(child_obj);
95         
96         // This clones funcs, which then clone instPoints, which then 
97         // clone baseTramps, which then clones miniTramps.
98     }
99     // Clone the tramp guard base
100     trampGuardBase_ = new int_variable(parent->trampGuardBase_, getAOut()->getDefaultModule());
101     
102
103     /////////////////////////
104     // Inferior heap
105     /////////////////////////
106
107     heap_ = inferiorHeap(parent->heap_);
108     heapInitialized_ = parent->heapInitialized_;
109
110     /////////////////////////
111     // Instrumentation (multiTramps on down)
112     /////////////////////////
113
114     pdvector<codeRange *> ranges;
115     parent->modifiedRanges_.elements(ranges);
116
117     for (unsigned i = 0; i < ranges.size(); i++) {
118         instArea *area = dynamic_cast<instArea *>(ranges[i]);
119         replacedFunctionCall *rfc = dynamic_cast<replacedFunctionCall *>(ranges[i]);
120         // Not used yet
121         //functionReplacement *fr = dynamic_cast<functionReplacement *>(ranges[i]);
122         
123        if (area) {
124             // Create a new multiTramp and add it
125             multiTramp *pMulti = area->multi;
126             multiTramp *cMulti = new multiTramp(pMulti, proc());
127             addMultiTramp(cMulti);
128         }
129         else if (rfc) {
130             replacedFunctionCall *cRFC = new replacedFunctionCall((*rfc));
131             addReplacedCall(cRFC);
132         }
133 #if 0
134 // Apparently this was never implemented... it probably should be, though.
135         else if (fr) {
136             functionReplacement *cFR = new functionReplacement(cFR);
137             addFuncReplacement(cFR);
138         }
139 #endif
140     }
141     // That will also create all baseTramps, miniTramps, ...
142
143     /////////////////////////
144     // Trap mappings
145     /////////////////////////
146     trapMapping.copyTrapMappings(& (parent->trapMapping));
147 }
148
149 void AddressSpace::deleteAddressSpace() {
150     // Methodically clear everything we have - it all went away
151     // We have the following member variables:
152
153     // bool heapInitialized_
154     // inferiorHeap heap_
155     // codeRangeTree textRanges_
156     // codeRangeTree modifiedCodeRanges_
157     // dictionary_hash multiTrampsById_
158
159     heapInitialized_ = false;
160     heap_.clear();
161
162     // We can just clear the originalCodeRanges structure - everything else
163     // is deleted elsewhere, and we won't leak.
164     textRanges_.clear();
165
166     // Delete only the wrapper objects
167     pdvector<codeRange *> ranges;
168     dataRanges_.elements(ranges);
169     for (unsigned i = 0; i < ranges.size(); i++) {
170         delete ranges[i];
171     }
172     ranges.clear();
173     dataRanges_.clear();
174
175     // Modified code ranges we have to take care of. 
176     modifiedRanges_.elements(ranges);
177     modifiedRanges_.clear();
178
179     for (unsigned i = 0; i < ranges.size(); i++) {
180         // This is either a:
181         // instArea
182         // replacedFunctionCall
183         // replacedFunction
184
185         // Either way, we can nuke 'em.
186         delete ranges[i];
187     }
188
189     multiTrampsById_.clear();
190
191     for (unsigned i = 0; i < mapped_objects.size(); i++) 
192         delete mapped_objects[i];
193
194     mapped_objects.clear();
195
196     trampGuardBase_ = NULL;
197
198     // up_ptr_ is untouched
199     costAddr_ = 0;
200 }
201
202
203 // findRangeByAddr: finds the object (see below) that corresponds with
204 // a given absolute address. This includes:
205 //   Functions (non-relocated)
206 //   Base tramps
207 //   Mini tramps
208 //   Relocated functions
209 //
210 // The process class keeps a tree of objects occupying the address space.
211 // This top-level tree includes trampolines, relocated functions, and the
212 // application and shared objects. The search starts at the top of this tree.
213 // If the address resolves to a base tramp, mini tramp, or relocated function,
214 // that is returned. If the address resolves within the range of an shared
215 // object, the search recurses into the object (the offset into the object
216 // is calculated and the function lookup works from the offset). If the offset
217 // is within the a.out, we look up the function assuming the address given is
218 // the offset. 
219
220 // This function gives only "original" code - that is, code that either existed
221 // in the binary or that we added to unallocated space. If you're looking for places
222 // where things were overwritten (jumps to instrumentation, etc.) look at
223 // modifiedRanges_.
224
225 void AddressSpace::addOrigRange(codeRange *range) {
226     textRanges_.insert(range);
227     if (range->is_mapped_object()) {
228         // Hack... add data range
229         mappedObjData *data = new mappedObjData(range->is_mapped_object());
230         dataRanges_.insert(data);
231     }
232 }
233
234 void AddressSpace::addModifiedRange(codeRange *range) {
235     modifiedRanges_.insert(range);
236 }
237
238 void AddressSpace::removeOrigRange(codeRange *range) {
239     codeRange *tmp = NULL;
240     
241     if (!textRanges_.find(range->get_address(), tmp))
242         return;
243
244     assert (range == tmp);
245
246     textRanges_.remove(range->get_address());
247 }
248
249 void AddressSpace::removeModifiedRange(codeRange *range) {
250     codeRange *tmp = NULL;
251     
252     if (!modifiedRanges_.find(range->get_address(), tmp))
253         return;
254
255     assert (range == tmp);
256
257     modifiedRanges_.remove(range->get_address());
258
259     instArea *area = dynamic_cast<instArea *>(range);
260     if (area) {
261       // We have just removed a multiTramp. If the dictionary
262       // entry is the same as the instArea pointer, remove it
263       // from the dictionary as well so we can't accidentally
264       // access it that way.
265
266       // If the pointers aren't equal, squawk because that shouldn't
267       // happen.
268       
269        if (area->multi) {
270           if (multiTrampsById_[area->multi->id()] == area->multi)
271              multiTrampsById_[area->multi->id()] = NULL;
272           else {
273              fprintf(stderr, "%s[%u]: Warning: odd case in removing instArea\n",
274                      FILE__, __LINE__);
275           }
276       }
277     }
278 }
279
280 codeRange *AddressSpace::findOrigByAddr(Address addr) {
281     codeRange *range = NULL;
282     
283     if (!textRanges_.find(addr, range)) {
284         return NULL;
285     }
286     
287     assert(range);
288     
289     bool in_range = (addr >= range->get_address() &&
290                      addr <= (range->get_address() + range->get_size()));
291     assert(in_range); // Supposed to return NULL if this is the case
292     
293     // The top level tree doesn't go into mapped_objects, which is not
294     // what we want; so if we're in a mapped_object, poke inside.
295     // However, if we're in a function (int_function), minitramp,
296     // basetramp, ... return that right away.
297     
298     mapped_object *mobj = range->is_mapped_object();
299     if (mobj) {
300         codeRange *obj_range = mobj->findCodeRangeByAddress(addr);
301         if (obj_range) range = obj_range;
302     }
303     
304     return range;
305 }
306
307 codeRange *AddressSpace::findModByAddr(Address addr) {
308     codeRange *range = NULL;
309     
310     if (!modifiedRanges_.find(addr, range)) {
311         return NULL;
312     }
313     
314     assert(range);
315     
316     bool in_range = (addr >= range->get_address() &&
317                      addr <= (range->get_address() + range->get_size()));
318     assert(in_range); // Supposed to return NULL if this is the case
319
320     return range;
321 }
322
323 // Returns the named symbol from the image or a shared object
324 bool AddressSpace::getSymbolInfo( const std::string &name, int_symbol &ret ) 
325 {
326   for (unsigned i = 0; i < mapped_objects.size(); i++) {
327       if (mapped_objects[i]->getSymbolInfo( name, ret ))
328           return true;
329   }
330   return false;
331 }
332
333
334 bool AddressSpace::getOrigRanges(pdvector<codeRange *> &ranges) {
335     textRanges_.elements(ranges);
336     return true;
337 }
338
339 bool AddressSpace::getModifiedRanges(pdvector<codeRange *> &ranges) {
340     modifiedRanges_.elements(ranges);
341     return true;
342 }
343
344 multiTramp *AddressSpace::findMultiTrampByAddr(Address addr) {    
345     codeRange *range = findModByAddr(addr);
346     if (range) {
347         instArea *area = dynamic_cast<instArea *>(range);
348         
349         if (area)
350             return area->multi;
351     }
352     range = findOrigByAddr(addr);
353
354     multiTramp *multi = dynamic_cast<multiTramp *>(range);
355     return multi;
356 }
357
358 multiTramp *AddressSpace::findMultiTrampById(unsigned int id) {
359     multiTramp *multi = NULL;
360     multiTrampsById_.find(id, multi);
361
362     return multi;
363 }
364
365 // Check to see if we're replacing an earlier multiTramp,
366 // add to the unmodifiedAreas list
367 void AddressSpace::addMultiTramp(multiTramp *multi) {
368     assert(multi);
369     assert(multi->instAddr());
370
371     // Actually... we haven't copied it yet, so don't add anything. 
372     //addOrigRange(multi);
373
374     codeRange *range = findModByAddr(multi->instAddr());
375     if (range) {
376         // We're overriding. Keep the instArea but update pointer.
377         instArea *area = dynamic_cast<instArea *>(range);
378         // It could be something else, which should have been
379         // caught already
380         if (!area) {
381             // Oops, someone already here... and multiTramps have
382             // the lowest priority.
383             return;
384         }
385         area->multi = multi;
386     }
387     else {
388         instArea *area = new instArea(multi);
389
390         modifiedRanges_.insert(area);
391     }
392
393     multiTrampsById_[multi->id()] = multi;
394 }
395
396 void AddressSpace::removeMultiTramp(multiTramp *multi) {
397     if (!multi) return;
398
399     assert(multi->instAddr());
400
401     removeOrigRange(multi);
402
403     // For multiTramps we also have the "wrapper" that
404     // represents the jump to the multiTramp. If that's
405     // still associated with this one, then nuke it
406     // as well. If not, ignore.
407
408     instArea *jump = dynamic_cast<instArea *>(findModByAddr(multi->instAddr()));
409
410     if (jump && jump->multi == multi) {
411         removeModifiedRange(jump);
412         delete jump;
413     }
414 }
415
416 functionReplacement *AddressSpace::findFuncReplacement(Address addr) {
417     codeRange *range = findModByAddr(addr);
418     if (!range) return NULL;
419     
420     functionReplacement *rep = dynamic_cast<functionReplacement *>(range);
421     return rep;
422 }
423
424 void AddressSpace::addFuncReplacement(functionReplacement *rep) {
425     assert(rep);
426     Address currAddr = rep->get_address();
427
428     while (currAddr < (rep->get_address() + rep->get_size())) {
429         codeRange *range = findModByAddr(currAddr);
430
431         if (range) removeModifiedRange(range);
432         currAddr += 1;
433     }
434
435     addModifiedRange(rep);
436 }
437
438 void AddressSpace::removeFuncReplacement(functionReplacement *rep) {
439     removeModifiedRange(rep);
440 }
441
442 replacedFunctionCall *AddressSpace::findReplacedCall(Address addr) {
443     codeRange *range = findModByAddr(addr);
444     if (!range) return NULL;
445     
446     replacedFunctionCall *rep = dynamic_cast<replacedFunctionCall *>(range);
447     return rep;
448 }
449
450 void AddressSpace::addReplacedCall(replacedFunctionCall *repcall) {
451     codeRange *range = findModByAddr(repcall->get_address());
452     if (range) {
453         // Can't replace instrumentation right now...
454         assert(dynamic_cast<replacedFunctionCall *>(range));
455         removeModifiedRange(range);
456         delete range;
457     }
458     assert(repcall);
459     addModifiedRange(repcall);
460 }
461
462 void AddressSpace::removeReplacedCall(replacedFunctionCall *repcall) {
463     removeModifiedRange(repcall);
464 }
465
466 bool heapItemLessByAddr(const heapItem *a, const heapItem *b)
467 {
468    if (a->addr < b->addr) {
469       return true;
470    }
471    return false;
472 }
473
474 //////////////////////////////////////////////////////////////////////////////
475 // Memory allocation routines
476 //////////////////////////////////////////////////////////////////////////////
477
478
479 void AddressSpace::inferiorFreeCompact() {
480    pdvector<heapItem *> &freeList = heap_.heapFree;
481    unsigned i, nbuf = freeList.size();
482
483    /* sort buffers by address */
484 #if defined (cap_use_pdvector)
485    VECTOR_SORT(freeList, heapItemCmpByAddr);
486 #else
487    VECTOR_SORT(freeList, heapItemLessByAddr);
488 #endif
489
490
491   /* combine adjacent buffers */
492   bool needToCompact = false;
493   for (i = 1; i < freeList.size(); i++) {
494       heapItem *h1 = freeList[i-1];
495       heapItem *h2 = freeList[i];
496       assert(h1->length != 0);
497       if (h1->addr + h1->length > h2->addr) {
498           fprintf(stderr, "Error: heap 1 (%p) (0x%p to 0x%p) overlaps heap 2 (%p) (0x%p to 0x%p)\n",
499                   h1,
500                   (void *)h1->addr, (void *)(h1->addr + h1->length),
501                   h2,
502                   (void *)h2->addr, (void *)(h2->addr + h2->length));
503       }
504       assert(h1->addr + h1->length <= h2->addr);
505       if (h1->addr + h1->length == h2->addr
506           && h1->type == h2->type) {
507           h2->addr = h1->addr;
508           h2->length = h1->length + h2->length;
509           h1->length = 0;
510           nbuf--;
511           needToCompact = true;
512       }
513   }
514
515   /* remove any absorbed (empty) buffers */ 
516   if (needToCompact) {
517     pdvector<heapItem *> cleanList;
518     unsigned end = freeList.size();
519     for (i = 0; i < end; i++) {
520       heapItem *h1 = freeList[i];
521       if (h1->length != 0) {
522         cleanList.push_back(h1);
523       } else {
524         delete h1;
525       }
526     }
527     assert(cleanList.size() == nbuf);
528     for (i = 0; i < nbuf; i++) {
529       freeList[i] = cleanList[i];
530     }
531     freeList.resize(nbuf);
532     assert(freeList.size() == nbuf);
533   }
534 }
535     
536 int AddressSpace::findFreeIndex(unsigned size, int type, Address lo, Address hi) {
537     // type is a bitmask: match on any bit in the mask
538     pdvector<heapItem *> &freeList = heap_.heapFree;
539     
540     int best = -1;
541     for (unsigned i = 0; i < freeList.size(); i++) {
542         heapItem *h = freeList[i];
543         // check if free block matches allocation constraints
544         // Split out to facilitate debugging
545         infmalloc_printf("%s[%d]: comparing heap %d: 0x%lx-0x%lx/%d to desired %d bytes in 0x%lx-0x%lx/%d\n",
546                          FILE__, __LINE__, 
547                          i,
548                          h->addr, 
549                          h->addr + h->length,
550                          h->type,
551                          size,
552                          lo, 
553                          hi,
554                          type);
555         if (h->addr >= lo &&
556             (h->addr + size - 1) <= hi &&
557             h->length >= size &&
558             h->type & type) {
559             if (best == -1)
560                 best = i;
561             // check for better match
562             if (h->length < freeList[best]->length) best = i;
563         }
564     }
565     infmalloc_printf("%s[%d]: returning match %d\n", FILE__, __LINE__, best);
566     return best;
567 }
568
569 void AddressSpace::addHeap(heapItem *h) {
570     heap_.bufferPool.push_back(h);
571     heapItem *h2 = new heapItem(h);
572     h2->status = HEAPfree;
573     heap_.heapFree.push_back(h2);
574     heap_.totalFreeMemAvailable += h2->length;
575 }
576
577 void AddressSpace::initializeHeap() {
578     // (re)initialize everything 
579     heap_.heapActive.clear();
580     heap_.heapFree.resize(0);
581     heap_.disabledList.resize(0);
582     heap_.disabledListTotalMem = 0;
583     heap_.freed = 0;
584     heap_.totalFreeMemAvailable = 0;
585
586     heapInitialized_ = true;
587 }
588
589 /* returns true if memory was allocated for a variable starting at address
590    "block", otherwise returns false
591 */
592 bool AddressSpace::isInferiorAllocated(Address block) {
593     heapItem *h = NULL;  
594     return heap_.heapActive.find(block, h);
595 }
596
597 Address AddressSpace::inferiorMallocInternal(unsigned size,
598                                              Address lo,
599                                              Address hi,
600                                              inferiorHeapType type) {
601     infmalloc_printf("%s[%d]: inferiorMallocInternal, %d bytes, type %d, between 0x%lx - 0x%lx\n",
602                      FILE__, __LINE__, size, type, lo, hi);
603     int freeIndex = findFreeIndex(size, type, lo, hi);
604     if (freeIndex == -1) return 0; // Failure is often an option
605
606
607     // adjust active and free lists
608     assert(freeIndex != -1);
609     heapItem *h = heap_.heapFree[freeIndex];
610     assert(h);
611     
612     // remove allocated buffer from free list
613     if (h->length != size) {
614         // size mismatch: put remainder of block on free list
615         heapItem *rem = new heapItem(h);
616         rem->addr += size;
617         rem->length -= size;
618         heap_.heapFree[freeIndex] = rem;
619     } else {
620         // size match: remove entire block from free list
621         unsigned last = heap_.heapFree.size();
622         heap_.heapFree[freeIndex] = heap_.heapFree[last-1];
623         heap_.heapFree.resize(last-1);
624     }
625     // add allocated block to active list
626     h->length = size;
627     h->status = HEAPallocated;
628     heap_.heapActive[h->addr] = h;
629     // bookkeeping
630     heap_.totalFreeMemAvailable -= size;
631     assert(h->addr);
632     
633     return(h->addr);
634 }
635
636 void AddressSpace::inferiorFreeInternal(Address block) {
637     // find block on active list
638     infmalloc_printf("%s[%d]: inferiorFree for block at 0x%lx\n", FILE__, __LINE__, block);
639     heapItem *h = NULL;  
640     if (!heap_.heapActive.find(block, h)) {
641         // We can do this if we're at process teardown.
642         return;
643     }
644     assert(h);
645     
646     // Remove from the active list
647     heap_.heapActive.undef(block);
648     
649     // Add to the free list
650     h->status = HEAPfree;
651     heap_.heapFree.push_back(h);
652     heap_.totalFreeMemAvailable += h->length;
653     heap_.freed += h->length;
654     infmalloc_printf("%s[%d]: Freed block from 0x%lx - 0x%lx, %d bytes, type %d\n",
655                      FILE__, __LINE__,
656                      h->addr,
657                      h->addr + h->length,
658                      h->length,
659                      h->type);
660 }
661
662 void AddressSpace::inferiorMallocAlign(unsigned &size) {
663     // Align to the process word
664
665 #if !defined(arch_ia64)
666     unsigned alignment = (getAddressWidth() - 1);
667 #else
668     unsigned alignment = (128 - 1);
669 #endif
670
671     size = (size + alignment) & ~alignment;
672 }
673     
674 bool AddressSpace::inferiorReallocInternal(Address block, unsigned newSize) {
675 #if defined (cap_dynamic_heap)
676     // This is why it's not a reference...
677     inferiorMallocAlign(newSize);
678 #endif
679     
680     infmalloc_printf("%s[%d]: inferiorRealloc for block 0x%lx, new size %d\n",
681                      FILE__, __LINE__, block, newSize);
682
683     // find block on active list
684     heapItem *h = NULL;  
685     if (!heap_.heapActive.find(block, h)) {
686         // We can do this if we're at process teardown.
687         infmalloc_printf("%s[%d]: inferiorRealloc unable to find block, returning\n", FILE__, __LINE__);
688         return false;
689     }
690     assert(h);
691     infmalloc_printf("%s[%d]: inferiorRealloc found block with addr 0x%lx, length %d\n",
692                      FILE__, __LINE__, h->addr, h->length);
693     
694     if (h->length < newSize) {
695         return false; // Cannot make bigger...
696     }
697     if (h->length == newSize)
698         return true;
699
700     // We make a new "free" block that is the end of this one.
701     Address freeStart = block + newSize;
702     Address succAddr = h->addr + h->length;
703     int shrink = h->length - newSize;
704     
705     assert(shrink > 0);
706     
707     h->length = newSize;
708     
709     // New speedy way. Find the block that is the successor of the
710     // active block; if it exists, simply enlarge it "downwards". Otherwise,
711     // make a new block. 
712     heapItem *succ = NULL;
713     for (unsigned i = 0; i < heap_.heapFree.size(); i++) {
714         heapItem *tmp = heap_.heapFree[i];
715         assert(tmp);
716         if (tmp->addr == succAddr) {
717             succ = tmp;
718             break;
719         }
720     }
721     if (succ != NULL) {
722         infmalloc_printf("%s[%d]: enlarging existing block; old 0x%lx - 0x%lx (%d), new 0x%lx - 0x%lx (%d)\n",
723                          FILE__, __LINE__,
724                          succ->addr,
725                          succ->addr + succ->length,
726                          succ->addr,
727                          succ->addr - shrink,
728                          succ->addr + succ->length,
729                          succ->length + shrink);
730
731
732         succ->addr -= shrink;
733         succ->length += shrink;
734     }
735     else {
736         // Must make a new block to represent the free memory
737         infmalloc_printf("%s[%d]: inferiorRealloc: creating new block 0x%lx to 0x%lx (%d), type %d\n",
738                          FILE__, __LINE__, 
739                          freeStart, 
740                          freeStart + shrink,
741                          shrink,
742                          h->type);
743
744         heapItem *freeEnd = new heapItem(freeStart,
745                                          shrink,
746                                          h->type,
747                                          h->dynamic,
748                                          HEAPfree);
749         heap_.heapFree.push_back(freeEnd);
750     }
751
752     heap_.totalFreeMemAvailable += shrink;
753     heap_.freed += shrink;
754
755     
756     return true;
757 }    
758
759 /////////////////////////////////////////
760 // Function lookup...
761 /////////////////////////////////////////
762
763 bool AddressSpace::findFuncsByAll(const std::string &funcname,
764                              pdvector<int_function *> &res,
765                              const std::string &libname) { // = "", btw
766     
767     unsigned starting_entries = res.size(); // We'll return true if we find something
768     for (unsigned i = 0; i < mapped_objects.size(); i++) {
769         if (libname == "" ||
770             mapped_objects[i]->fileName() == libname.c_str() ||
771             mapped_objects[i]->fullName() == libname.c_str()) {
772             const pdvector<int_function *> *pretty = mapped_objects[i]->findFuncVectorByPretty(funcname);
773             if (pretty) {
774                 // We stop at first match...
775                 for (unsigned pm = 0; pm < pretty->size(); pm++) {
776                     res.push_back((*pretty)[pm]);
777                 }
778             }
779             else {
780                 const pdvector<int_function *> *mangled = mapped_objects[i]->findFuncVectorByMangled(funcname);
781                 if (mangled) {
782                     for (unsigned mm = 0; mm < mangled->size(); mm++) {
783                         res.push_back((*mangled)[mm]);
784                     }
785                 }
786             }
787         }
788     }
789
790     return (res.size() != starting_entries);
791 }
792
793
794 bool AddressSpace::findFuncsByPretty(const std::string &funcname,
795                              pdvector<int_function *> &res,
796                              const std::string &libname) { // = "", btw
797
798     unsigned starting_entries = res.size(); // We'll return true if we find something
799
800     for (unsigned i = 0; i < mapped_objects.size(); i++) {
801         if (libname == "" ||
802             mapped_objects[i]->fileName() == libname.c_str() ||
803             mapped_objects[i]->fullName() == libname.c_str()) {
804             const pdvector<int_function *> *pretty = mapped_objects[i]->findFuncVectorByPretty(funcname);
805             if (pretty) {
806                 // We stop at first match...
807                 for (unsigned pm = 0; pm < pretty->size(); pm++) {
808                     res.push_back((*pretty)[pm]);
809                 }
810             }
811         }
812     }
813     return res.size() != starting_entries;
814 }
815
816
817 bool AddressSpace::findFuncsByMangled(const std::string &funcname,
818                                  pdvector<int_function *> &res,
819                                  const std::string &libname) { // = "", btw
820     unsigned starting_entries = res.size(); // We'll return true if we find something
821
822     for (unsigned i = 0; i < mapped_objects.size(); i++) {
823         if (libname == "" ||
824             mapped_objects[i]->fileName() == libname.c_str() ||
825             mapped_objects[i]->fullName() == libname.c_str()) {
826             const pdvector<int_function *> *mangled = 
827                mapped_objects[i]->findFuncVectorByMangled(funcname);
828             if (mangled) {
829                 for (unsigned mm = 0; mm < mangled->size(); mm++) {
830                    res.push_back((*mangled)[mm]);
831                 }
832             }
833         }
834     }
835     return res.size() != starting_entries;
836 }
837
838 int_function *AddressSpace::findOnlyOneFunction(const string &name,
839                                                 const string &lib,
840                                                 bool /*search_rt_lib*/) 
841 {
842     assert(mapped_objects.size());
843
844     pdvector<int_function *> allFuncs;
845
846     if (!findFuncsByAll(name.c_str(), allFuncs, lib.c_str()))
847         return NULL;
848
849     if (allFuncs.size() > 1) 
850     {
851         //cerr << "Warning: multiple matches for " << name << ", returning first" << endl;
852     }
853
854     return allFuncs[0];
855 }
856
857 /////////////////////////////////////////
858 // Variable lookup...
859 /////////////////////////////////////////
860
861 bool AddressSpace::findVarsByAll(const std::string &varname,
862                             pdvector<int_variable *> &res,
863                             const std::string &libname) { // = "", btw
864     unsigned starting_entries = res.size(); // We'll return true if we find something
865     
866     for (unsigned i = 0; i < mapped_objects.size(); i++) {
867         if (libname == "" ||
868             mapped_objects[i]->fileName() == libname.c_str() ||
869             mapped_objects[i]->fullName() == libname.c_str()) {
870             const pdvector<int_variable *> *pretty = mapped_objects[i]->findVarVectorByPretty(varname);
871             if (pretty) {
872                 // We stop at first match...
873                 for (unsigned pm = 0; pm < pretty->size(); pm++) {
874                     res.push_back((*pretty)[pm]);
875                 }
876             }
877             else {
878                 const pdvector<int_variable *> *mangled = mapped_objects[i]->findVarVectorByMangled(varname);
879                 if (mangled) {
880                     for (unsigned mm = 0; mm < mangled->size(); mm++) {
881                         res.push_back((*mangled)[mm]);
882                     }
883                 }
884             }
885         }
886     }
887
888     return res.size() != starting_entries;
889 }
890
891
892
893 // Get me a pointer to the instruction: the return is a local
894 // (mutator-side) store for the mutatee. This may duck into the local
895 // copy for images, or a relocated function's self copy.
896 // TODO: is this really worth it? Or should we just use ptrace?
897
898 void *AddressSpace::getPtrToInstruction(Address addr) const {
899     codeRange *range;
900
901     if (textRanges_.find(addr, range)) {
902         return range->getPtrToInstruction(addr);
903     }
904     else if (dataRanges_.find(addr, range)) {
905         mappedObjData *data = dynamic_cast<mappedObjData *>(range);
906         assert(data);
907         return data->obj->getPtrToData(addr);
908     }
909     assert(0);
910     return NULL;
911 }
912
913 bool AddressSpace::isExecutableAddress(const Address &addr) const {
914     codeRange *dontcare;
915     if (textRanges_.find(addr, dontcare))
916         return true;
917     else
918         return false;
919 }
920
921 bool AddressSpace::isValidAddress(const Address& addr) const{
922     // "Is this part of the process address space?"
923     codeRange *dontcare;
924     if (textRanges_.find(addr, dontcare))
925         return true;
926     if (dataRanges_.find(addr, dontcare))
927         return true;
928     return false;
929 }        
930
931 mapped_object *AddressSpace::findObject(Address addr) {
932     for (unsigned i=0; i<mapped_objects.size(); i++)
933     {
934         if (addr >= mapped_objects[i]->codeAbs() &&
935             addr < mapped_objects[i]->codeAbs() + mapped_objects[i]->imageSize())
936         {
937             return mapped_objects[i];
938         }
939     }
940     return NULL;
941 }
942
943 int_function *AddressSpace::findFuncByAddr(Address addr) {
944     codeRange *range = findOrigByAddr(addr);
945     if (!range) return NULL;
946     
947     int_function *func_ptr = range->is_function();
948     multiTramp *multi = range->is_multitramp();
949     miniTrampInstance *mti = range->is_minitramp();
950
951     if(func_ptr) {
952        return func_ptr;
953     }
954     else if (multi) {
955         return multi->func();
956     }
957     else if (mti) {
958         return mti->baseTI->multiT->func();
959     }
960     else {
961         return NULL;
962     }
963 }
964
965 int_basicBlock *AddressSpace::findBasicBlockByAddr(Address addr) {
966     codeRange *range = findOrigByAddr(addr);
967     if (!range) return NULL;
968
969     int_basicBlock *b = range->is_basicBlock();
970     int_function *f = range->is_function();
971     multiTramp *mt = range->is_multitramp();
972     miniTrampInstance *mti = range->is_minitramp();
973
974     if(b) {
975         return b;
976     }
977     else if(f) {
978         return f->findBlockByAddr(addr);
979     }
980     else if(mt) {
981         return mt->func()->findBlockByAddr(addr);
982     }
983     else if(mti) {
984         return mti->baseTI->multiT->func()->findBlockByAddr(addr);
985     }
986     else
987         return NULL;
988 }
989
990 int_function *AddressSpace::findFuncByInternalFunc(image_func *ifunc) {
991     assert(ifunc);
992   
993     // Now we have to look up our specialized version
994     // Can't do module lookup because of DEFAULT_MODULE...
995     pdvector<int_function *> possibles;
996     if (!findFuncsByMangled(ifunc->symTabName().c_str(),
997                             possibles))
998         return NULL;
999
1000     assert(possibles.size());
1001   
1002     for (unsigned i = 0; i < possibles.size(); i++) {
1003         if (possibles[i]->ifunc() == ifunc) {
1004             return possibles[i];
1005         }
1006     }
1007     return NULL;
1008 }
1009
1010 // findModule: returns the module associated with mod_name 
1011 // this routine checks both the a.out image and any shared object
1012 // images for this resource
1013 mapped_module *AddressSpace::findModule(const std::string &mod_name, bool wildcard)
1014 {
1015     // KLUDGE: first search any shared libraries for the module name 
1016     //  (there is only one module in each shared library, and that 
1017     //  is the library name)
1018     for(u_int j=0; j < mapped_objects.size(); j++){
1019         mapped_module *mod = mapped_objects[j]->findModule(mod_name.c_str(), wildcard);
1020         if (mod) {
1021             return (mod);
1022         }
1023     }
1024     return NULL;
1025 }
1026
1027 // findObject: returns the object associated with obj_name 
1028 // This just iterates over the mapped object vector
1029 mapped_object *AddressSpace::findObject(const std::string &obj_name, bool wildcard)
1030 {
1031     for(u_int j=0; j < mapped_objects.size(); j++){
1032         if (mapped_objects[j]->fileName() == obj_name.c_str() ||
1033             mapped_objects[j]->fullName() == obj_name.c_str() ||
1034            (wildcard &&
1035              (wildcardEquiv(obj_name, mapped_objects[j]->fileName()) ||
1036               wildcardEquiv(obj_name, mapped_objects[j]->fullName()))))
1037             return mapped_objects[j];
1038     }
1039     return NULL;
1040 }
1041
1042 // findObject: returns the object associated with obj_name 
1043 // This just iterates over the mapped object vector
1044 mapped_object *AddressSpace::findObject(fileDescriptor desc)
1045 {
1046     for(u_int j=0; j < mapped_objects.size(); j++){
1047        if (desc == mapped_objects[j]->getFileDesc()) 
1048             return mapped_objects[j];
1049     }
1050     return NULL;
1051 }
1052
1053 // getAllFunctions: returns a vector of all functions defined in the
1054 // a.out and in the shared objects
1055
1056 void AddressSpace::getAllFunctions(pdvector<int_function *> &funcs) {
1057     for (unsigned i = 0; i < mapped_objects.size(); i++) {
1058         mapped_objects[i]->getAllFunctions(funcs);
1059     }
1060 }
1061       
1062 // getAllModules: returns a vector of all modules defined in the
1063 // a.out and in the shared objects
1064
1065 void AddressSpace::getAllModules(pdvector<mapped_module *> &mods){
1066     for (unsigned i = 0; i < mapped_objects.size(); i++) {
1067         const pdvector<mapped_module *> &obj_mods = mapped_objects[i]->getModules();
1068         for (unsigned j = 0; j < obj_mods.size(); j++) {
1069             mods.push_back(obj_mods[j]);
1070         }
1071     }
1072 }
1073
1074 //Acts like findTargetFuncByAddr, but also finds the function if addr
1075 // is an indirect jump to a function.
1076 //I know this is an odd function, but darn I need it.
1077 int_function *AddressSpace::findJumpTargetFuncByAddr(Address addr) {
1078
1079     Address addr2 = 0;
1080     int_function *f = findFuncByAddr(addr);
1081     if (f)
1082         return f;
1083
1084     codeRange *range = findOrigByAddr(addr);
1085     if (!range->is_mapped_object()) 
1086         return NULL;
1087 #if defined(cap_instruction_api)
1088     using namespace Dyninst::InstructionAPI;
1089     InstructionDecoder decoder;
1090     decoder.setMode(getAddressWidth() == 8);
1091     Instruction::Ptr curInsn = decoder.decode((const unsigned char*)getPtrToInstruction(addr));
1092     
1093     Expression::Ptr target = curInsn->getControlFlowTarget();
1094     RegisterAST thePC = RegisterAST::makePC();
1095     target->bind(&thePC, Result(u32, addr));
1096     Result cft = target->eval();
1097     if(cft.defined)
1098     {
1099       switch(cft.type)
1100       {
1101       case u32:
1102         addr2 = cft.val.u32val;
1103         break;
1104       case s32:
1105         addr2 = cft.val.s32val;
1106         break;
1107       default:
1108         assert(!"Not implemented for non-32 bit CFTs yet!");
1109         break;
1110       }
1111     }
1112 #else
1113     InstrucIter ii(addr, this);
1114     if (ii.isAJumpInstruction())
1115         addr2 = ii.getBranchTargetAddress();
1116 #endif //defined(cap_instruction_api)
1117     return findFuncByAddr(addr2);
1118 }
1119
1120 AstNodePtr AddressSpace::trampGuardAST() {
1121     if (!trampGuardBase_) {
1122         // Don't have it yet....
1123         return AstNodePtr();
1124     }
1125
1126     if (trampGuardAST_) return trampGuardAST_;
1127
1128     trampGuardAST_ = AstNode::operandNode(AstNode::variableAddr, trampGuardBase_->ivar());
1129     return trampGuardAST_;
1130 }
1131
1132 // Add it at the bottom...
1133 void AddressSpace::deleteGeneratedCode(generatedCodeObject *delInst)
1134 {
1135     delete delInst;
1136 }
1137
1138 trampTrapMappings::trampTrapMappings(AddressSpace *a) :
1139    needs_updating(false),
1140    as(a),
1141    trapTableUsed(NULL),
1142    trapTableVersion(NULL),
1143    trapTable(NULL),
1144    trapTableSorted(NULL),
1145    table_version(0),
1146    table_used(0),
1147    table_allocated(0),
1148    table_mutatee_size(0),
1149    current_table(0x0),
1150    table_header(0x0),
1151    blockFlushes(false)
1152 {
1153 }
1154
1155 void trampTrapMappings::copyTrapMappings(trampTrapMappings *parent)
1156 {
1157   needs_updating = parent->needs_updating;
1158   trapTableUsed = NULL;
1159   trapTableVersion = NULL;
1160   trapTable = NULL;
1161   trapTableSorted = NULL;
1162   table_version = parent->table_version;
1163   table_used = parent->table_used;
1164   table_allocated = parent->table_allocated;
1165   table_mutatee_size = parent->table_mutatee_size;
1166   current_table = parent->current_table;
1167   mapping = parent->mapping;
1168 }
1169
1170 void trampTrapMappings::clearTrapMappings()
1171 {
1172   needs_updating = false;
1173   trapTableUsed = NULL;
1174   trapTableVersion = NULL;
1175   trapTable = NULL;
1176   trapTableSorted = NULL;
1177   table_version = 0;
1178   table_used = 0;
1179   table_allocated = 0;
1180   table_mutatee_size = 0;
1181   current_table = 0;
1182   mapping.clear();
1183 }
1184
1185 void trampTrapMappings::addTrapMapping(Address from, Address to, 
1186                                        bool write_to_mutatee)
1187 {
1188 #if defined(arch_x86) || defined(arch_x86_64)
1189    //x86 traps occur at +1 addr
1190    from++;
1191 #endif
1192    tramp_mapping_t m;
1193    bool existing_trap = (mapping.count(from) != 0);
1194    m.from_addr = from;
1195    m.to_addr = to;
1196    m.written = false;
1197    m.cur_index = existing_trap ? mapping[from].cur_index : INDEX_INVALID;
1198    m.mutatee_side = write_to_mutatee;
1199    mapping[from] = m;
1200 #if defined(cap_mutatee_traps)
1201    updated_mappings.insert(& mapping[from]);
1202    if (write_to_mutatee && !existing_trap) {
1203       table_mutatee_size++;
1204    }
1205    needs_updating = true;
1206 #endif
1207 }
1208
1209 bool trampTrapMappings::definesTrapMapping(Address from)
1210 {
1211    return mapping.count(from) != 0;
1212 }
1213
1214 Address trampTrapMappings::getTrapMapping(Address from)
1215 {
1216    if (!mapping.count(from))
1217       return 0;
1218    return mapping[from].to_addr;
1219 }
1220
1221 bool trampTrapMappings::needsUpdating()
1222 {
1223    return needs_updating;
1224 }
1225
1226 bool trampTrapMappings::empty() {
1227     return mapping.empty();
1228 }
1229
1230
1231 AddressSpace *trampTrapMappings::proc() const {
1232    return as;
1233 }
1234
1235 bool mapping_sort(const trampTrapMappings::tramp_mapping_t *lhs,
1236                   const trampTrapMappings::tramp_mapping_t *rhs)
1237 {
1238    return lhs->from_addr < rhs->from_addr;
1239 }
1240
1241 #if defined(cap_32_64)
1242 void trampTrapMappings::writeToBuffer(unsigned char *buffer, unsigned long val,
1243                                       unsigned addr_width)
1244 {
1245    //Deal with the case when mutatee word size != mutator word size
1246    if (addr_width != sizeof(Address)) {
1247       //Currently only support 64-bit mutators with 32-bit mutatees
1248       assert(addr_width == 4);
1249       assert(sizeof(Address) == 8);
1250       *((uint32_t *) buffer) = (uint32_t) val;
1251       return;
1252    }
1253    *((unsigned long *) buffer) = val;
1254 }
1255 #else
1256 void trampTrapMappings::writeToBuffer(unsigned char *buffer, unsigned long val,
1257                                       unsigned)
1258 {
1259    *((unsigned long *)(void*) buffer) = val;
1260 }
1261 #endif
1262
1263
1264 void trampTrapMappings::writeTrampVariable(const int_variable *var, 
1265                                            unsigned long val)
1266 {
1267    unsigned char buffer[16];
1268    unsigned aw = proc()->getAddressWidth();
1269
1270    writeToBuffer(buffer, val, aw);
1271    bool result = proc()->writeDataSpace((void *) var->getAddress(), aw, buffer);
1272    assert(result);
1273 }
1274                   
1275 void trampTrapMappings::arrange_mapping(tramp_mapping_t &m, bool should_sort,
1276                                         std::vector<tramp_mapping_t*> &mappings_to_add,
1277                                         std::vector<tramp_mapping_t*> &mappings_to_update)
1278 {
1279    if (!m.mutatee_side || (m.written && !should_sort))
1280       return;
1281    m.written = true;
1282    if (should_sort || m.cur_index == INDEX_INVALID)
1283       mappings_to_add.push_back(&m);
1284    else if (m.cur_index != INDEX_INVALID)
1285       mappings_to_update.push_back(&m);
1286 }
1287
1288 void trampTrapMappings::flush() {
1289    if (!needs_updating || blockFlushes)
1290       return;
1291
1292    mapped_object *rtlib = proc()->runtime_lib;
1293
1294    //We'll sort addresses in the binary rewritter (when writting only happens
1295    // once and we may do frequent lookups)
1296    //If we're using the dynamic instrumentor and creating a new table we might
1297    // as well sort it.
1298    //If we're just adding a few entries to the table which already fit, then
1299    // we'll just append them to the end of the table.
1300    //
1301    //If we're sorting, then everytime we update we'll generate a whole new table
1302    //If we're not sorting, then each update will just append to the end of the
1303    // table.
1304    bool should_sort = (dynamic_cast<process *>(proc()) == NULL ||
1305                        table_mutatee_size > table_allocated);
1306
1307    if (should_sort) {
1308       table_used = 0; //We're rebuilding the table, nothing's used.
1309    }
1310
1311    /**
1312     * Fill in the mappings_to_add and mappings_to_update vectors.
1313     * As an optimization, we keep a list of the mappings that have
1314     * changed in updated_mappings.  If we're not completly regenerating
1315     * the table we'll get our trap list out of updated_mappings, 
1316     * otherwise we'll get our change list out of the entire dyn_hash_map.
1317     **/
1318    std::vector<tramp_mapping_t*> mappings_to_add;
1319    std::vector<tramp_mapping_t*> mappings_to_update;
1320    if (should_sort) {
1321       dyn_hash_map<Address, tramp_mapping_t>::iterator i;
1322       for (i = mapping.begin(); i != mapping.end(); i++) {
1323          arrange_mapping((*i).second, should_sort, 
1324                          mappings_to_add, mappings_to_update);
1325       }
1326    } 
1327    else {
1328       std::set<tramp_mapping_t *>::iterator i;
1329       for (i = updated_mappings.begin(); i != updated_mappings.end(); i++) {
1330          arrange_mapping(**i, should_sort, 
1331                          mappings_to_add, mappings_to_update);
1332       }
1333    }
1334    updated_mappings.clear();
1335
1336    assert(mappings_to_add.size() + table_used == table_mutatee_size);
1337
1338    for (unsigned k=0; k<mappings_to_add.size(); k++)
1339    {
1340       mappings_to_add[k]->written = true;
1341    }
1342
1343    //Sort the mappings (if needed) 
1344    if (should_sort) 
1345       std::sort(mappings_to_add.begin(), mappings_to_add.end(), mapping_sort);
1346
1347    // Assign the cur_index field of each entry in the new mappings we're adding
1348    for (unsigned j=0; j<mappings_to_add.size(); j++) {
1349       mappings_to_add[j]->cur_index = table_used + j;
1350    }
1351    
1352    //Each table entry has two pointers.
1353    unsigned entry_size = proc()->getAddressWidth() * 2;
1354
1355    Address write_addr = 0x0;
1356
1357    allocateTable();
1358
1359    //Add any new entries to the table
1360    unsigned char *buffer = NULL;
1361    if (mappings_to_add.size()) {
1362       //Create a buffer containing the new entries we're going to write.
1363       unsigned long bytes_to_add = mappings_to_add.size() * entry_size;
1364       buffer = (unsigned char *) malloc(bytes_to_add);
1365       assert(buffer);
1366       
1367       unsigned char *cur = buffer;
1368       std::vector<tramp_mapping_t*>::iterator j;
1369       for (j = mappings_to_add.begin(); j != mappings_to_add.end(); j++) {
1370          tramp_mapping_t &tm = **j;
1371          writeToBuffer(cur, tm.from_addr, proc()->getAddressWidth());
1372          cur += proc()->getAddressWidth();
1373          writeToBuffer(cur, tm.to_addr, proc()->getAddressWidth());
1374          cur += proc()->getAddressWidth();
1375       }
1376       assert(cur == buffer + bytes_to_add);
1377       
1378       //Write the new entries into the process
1379       write_addr = current_table + (table_used * entry_size);
1380       bool result = proc()->writeDataSpace((void *) write_addr, bytes_to_add, 
1381                                            buffer);
1382       assert(result);
1383       free(buffer);
1384       buffer = NULL;
1385
1386       table_used += mappings_to_add.size();
1387    }
1388
1389    //Now we get to update existing entries that have been modified.
1390    if (mappings_to_update.size()) {
1391       assert(!should_sort);
1392       unsigned aw = proc()->getAddressWidth();
1393       buffer = (unsigned char *) malloc(aw);
1394       assert(buffer);
1395
1396       //For each entry, use its cur_index field to figure out where in the
1397       // process it is, and write it.
1398       //We only need to update the to_addr, since this is an update of an
1399       // existing from_addr
1400       std::vector<tramp_mapping_t*>::iterator j;
1401       for (j = mappings_to_update.begin(); j != mappings_to_update.end(); j++) {
1402          tramp_mapping_t &tm = **j;
1403          writeToBuffer(buffer, tm.to_addr, aw);
1404
1405          Address write_addr = current_table + (tm.cur_index * entry_size) + aw;
1406          bool result = proc()->writeDataSpace((void *) write_addr, aw, buffer);
1407          assert(result);
1408       }
1409       
1410       free(buffer);
1411       buffer = NULL;
1412    }
1413
1414    //This function just keeps going... Now we need to take all of those 
1415    // mutatee side variables and update them.
1416    if (dynamic_cast<process *>(proc())) 
1417    {
1418       if (!trapTable) {
1419          //Lookup all variables that are in the rtlib
1420          assert(rtlib);
1421          trapTableUsed = rtlib->getVariable("dyninstTrapTableUsed");
1422          trapTableVersion = rtlib->getVariable("dyninstTrapTableVersion");
1423          trapTable = rtlib->getVariable("dyninstTrapTable");
1424          trapTableSorted = rtlib->getVariable("dyninstTrapTableIsSorted");
1425          
1426          if (!trapTableUsed) {
1427             fprintf(stderr, "Dyninst is about to crash with an assert.  Either your dyninstAPI_RT library is stripped, or you're using an older version of dyninstAPI_RT with a newer version of dyninst.  Check your DYNINSTAPI_RT_LIB enviroment variable.\n");
1428          }
1429          assert(trapTableUsed);
1430          assert(trapTableVersion);
1431          assert(trapTable);
1432          assert(trapTableSorted);
1433       }
1434    
1435       writeTrampVariable(trapTableUsed, table_used);
1436       writeTrampVariable(trapTableVersion, ++table_version);
1437       writeTrampVariable(trapTable, (unsigned long) current_table);
1438       writeTrampVariable(trapTableSorted, should_sort ? 1 : 0);
1439    }
1440
1441    needs_updating = false;
1442 }
1443
1444 void trampTrapMappings::allocateTable()
1445 {
1446    unsigned entry_size = proc()->getAddressWidth() * 2;
1447
1448    if (dynamic_cast<process *>(proc()))
1449    {
1450       //Dynamic rewriting
1451
1452       //Allocate the space for the tramp mapping table, or make sure that enough
1453       // space already exists.
1454       if (table_mutatee_size > table_allocated) {
1455          //Free old table
1456          if (current_table) {
1457             proc()->inferiorFree(current_table);
1458          }
1459          
1460          //Calculate size of new table
1461          table_allocated = (unsigned long) (table_mutatee_size * 1.5);
1462          if (table_allocated < MIN_TRAP_TABLE_SIZE)
1463             table_allocated = MIN_TRAP_TABLE_SIZE;
1464          
1465          //allocate
1466          current_table = proc()->inferiorMalloc(table_allocated * entry_size);
1467          assert(current_table);
1468       }
1469       return;
1470    }
1471
1472    //Static rewriting
1473    BinaryEdit *binedit = dynamic_cast<BinaryEdit *>(proc());
1474    assert(!current_table);
1475    assert(binedit);
1476    
1477    table_allocated = (unsigned long) table_mutatee_size;
1478    table_header = proc()->inferiorMalloc(table_allocated * entry_size + 
1479                                          sizeof(trap_mapping_header));
1480    trap_mapping_header header;
1481    header.signature = TRAP_HEADER_SIG;
1482    header.num_entries = table_mutatee_size;
1483    header.pos = -1;
1484    header.low_entry = 0;
1485    header.high_entry = 0;
1486
1487    bool result = proc()->writeDataSpace((void *) table_header, 
1488                                         sizeof(trap_mapping_header),
1489                                         &header);
1490    assert(result);   
1491    current_table = table_header + sizeof(trap_mapping_header);
1492
1493    Symtab *symtab = binedit->getMappedObject()->parse_img()->getObject();
1494    symtab->addSysVDynamic(DT_DYNINST, table_header);
1495
1496    std::string rt_lib_name = proc()->runtime_lib->fileName();
1497    symtab->addLibraryPrereq(rt_lib_name);
1498 }
1499
1500 bool AddressSpace::findFuncsByAddr(Address addr, std::vector<int_function *> &funcs)
1501 {
1502    codeRange *range = findOrigByAddr(addr);
1503    if (!range)
1504       return false;
1505
1506    bblInstance *bblInst = NULL;
1507    int_basicBlock *int_block = NULL;
1508    int_function *int_func = NULL;
1509    image_basicBlock *img_block = NULL;
1510
1511    bblInst = range->is_basicBlockInstance();
1512    if (bblInst) {
1513       int_block = bblInst->block();
1514       if (int_block->origInstance() != bblInst) {
1515          //If we're not the original instance of a block, then this
1516          // is a relocated copy.  Since we un-share when relocating
1517          // we only have one function to return.
1518          int_func = int_block->func();
1519          funcs.push_back(int_func);
1520          return true;
1521       }
1522    }
1523
1524    if (!int_block)
1525       int_block = range->is_basicBlock();
1526    if (int_block) 
1527    {
1528       //int_basicBlocks are unique to a function and don't contain
1529       // sharing information.  Move down to the image_basicBlock and
1530       // use that in the next if statement to look up sharing.
1531       img_block = int_block->llb();
1532    }
1533
1534    if (!img_block) 
1535       img_block = range->is_image_basicBlock();
1536    if (img_block)
1537    {
1538       //Get the multiple functions from the image block, convert to
1539       // int_functions and return them.
1540       const set<image_func *> & img_funcs = img_block->getFuncs();
1541       assert(img_funcs.size());
1542       set<image_func *>::const_iterator fit = img_funcs.begin();
1543       for( ; fit != img_funcs.end(); ++fit) {
1544          int_func = findFuncByInternalFunc(*fit);
1545          funcs.push_back(int_func);
1546       }
1547       return true;
1548    }
1549
1550    assert(!range->is_function());
1551    return false;
1552    
1553 }
1554
1555 bool AddressSpace::canUseTraps()
1556 {
1557    BinaryEdit *binEdit = dynamic_cast<BinaryEdit *>(this);
1558    if (binEdit && binEdit->getMappedObject()->parse_img()->getObject()->isStaticBinary())
1559         return false;
1560    
1561    return useTraps_;
1562 }
1563
1564 void AddressSpace::setUseTraps(bool usetraps)
1565 {
1566    useTraps_ = usetraps;
1567 }
1568
1569 bool AddressSpace::needsPIC(int_variable *v)
1570 {
1571    return needsPIC(v->mod()->proc());
1572 }
1573
1574 bool AddressSpace::needsPIC(int_function *f)
1575 {
1576    return needsPIC(f->proc());
1577 }
1578
1579 bool AddressSpace::needsPIC(AddressSpace *s)
1580 {
1581    if (proc())
1582       return false; //Never PIC for dynamic
1583    if (this != s)
1584       return true; //Use PIC cross module
1585    return s->needsPIC(); //Use target module
1586 }