dyninstAPI: Limit cerr messages to debug mode
[dyninst.git] / dyninstAPI / src / addressSpace.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #include "addressSpace.h"
32 #include "codeRange.h"
33 #include "dynProcess.h"
34 #include "function.h"
35 #include "binaryEdit.h"
36 #include "baseTramp.h"
37
38 #include "instPoint.h"
39 #include "debug.h"
40
41 // Two-level codeRange structure
42 #include "mapped_object.h"
43 #include "mapped_module.h"
44 #include "InstructionDecoder.h"
45 #include "Instruction.h"
46
47 #include "common/h/DynAST.h"
48 #include "Relocation/CodeMover.h"
49 #include "Relocation/Springboard.h"
50 #include "Relocation/Transformers/Include.h"
51 #include "Relocation/CodeTracker.h"
52
53 #include "MemoryEmulator/memEmulator.h"
54 #include "parseAPI/h/CodeObject.h"
55 #include <boost/tuple/tuple.hpp>
56
57 #include "PatchMgr.h"
58 #include "Patching.h"
59 #include "Relocation/DynAddrSpace.h"
60 #include "Relocation/DynPointMaker.h"
61 #include "Relocation/DynObject.h"
62 #include "Relocation/DynInstrumenter.h"
63
64 #include <boost/bind.hpp>
65
66 // Implementations of non-virtual functions in the address space
67 // class.
68
69 using namespace Dyninst;
70
71 using PatchAPI::DynObject;
72 using PatchAPI::DynAddrSpace;
73 using PatchAPI::PatchMgr;
74 using PatchAPI::Patcher;
75 using PatchAPI::DynInstrumenter;
76 using PatchAPI::DynRemoveSnipCommand;
77
78 AddressSpace::AddressSpace () :
79     trapMapping(this),
80     new_func_cb(NULL),
81     new_instp_cb(NULL),
82     heapInitialized_(false),
83     useTraps_(true),
84     trampGuardBase_(NULL),
85     up_ptr_(NULL),
86     costAddr_(0),
87     installedSpringboards_(new Relocation::InstalledSpringboards()),
88     memEmulator_(NULL),
89     emulateMem_(false),
90     emulatePC_(false),
91     delayRelocation_(false),
92     patcher_(NULL)
93 {
94 #if 0
95    // Disabled for now; used by defensive mode
96    if ( getenv("DYNINST_EMULATE_MEMORY") ) {
97        printf("emulating memory & pc\n");
98        memEmulator_ = new MemoryEmulator(this);
99        emulateMem_ = true;
100        emulatePC_ = true;
101    }
102 #endif
103 }
104
105 AddressSpace::~AddressSpace() {
106     if (memEmulator_)
107       delete memEmulator_;
108     if (mgr_)
109        static_cast<DynAddrSpace*>(mgr_->as())->removeAddrSpace(this);
110 }
111
112 PCProcess *AddressSpace::proc() {
113     return dynamic_cast<PCProcess *>(this);
114 }
115
116 BinaryEdit *AddressSpace::edit() {
117     return dynamic_cast<BinaryEdit *>(this);
118 }
119 Address AddressSpace::getTOCoffsetInfo(func_instance *func) {
120   // Symtab has this information on a per-Function basis. It's
121   // kinda nontrivial to get a Function object out of a 
122   // func_instance; instead we use its entry address which
123   // is what all the TOC data structures are written in terms of
124   // anyway
125
126   bool toc64 = false;
127   bool toc32 = false;
128 #if defined(cap_toc_64)
129   toc64 = true;
130 #endif
131 #if defined(cap_toc_32)
132   toc32 = true;
133 #endif
134   if (getAddressWidth() == 8 && !toc64) return 0;
135   if (getAddressWidth() == 4 && !toc32) return 0;
136
137   Offset baseTOC = func->obj()->parse_img()->getObject()->getTOCoffset(func->function()->addr());
138   return baseTOC + func->obj()->dataBase();
139 }
140
141 // Fork constructor - and so we can assume a parent "process"
142 // rather than "address space"
143 //
144 // Actually, for the sake of abstraction, use an AddressSpace instead of process
145 void AddressSpace::copyAddressSpace(AddressSpace *parent) {
146     deleteAddressSpace();
147
148     // This is only defined for process->process copy
149     // until someone can give a good reason for copying
150     // anything else...
151
152     assert(proc());
153
154     mapped_object *par_aout = parent->getAOut();
155     mapped_object *child_aout = new mapped_object(par_aout, proc());
156     initPatchAPI();
157     addMappedObject(child_aout);
158
159     // Mapped objects first
160     for (unsigned i = 0; i < parent->mapped_objects.size(); i++) {
161         mapped_object *par_obj = parent->mapped_objects[i];
162         if (parent->getAOut() != par_obj) {
163           mapped_object *child_obj = new mapped_object(par_obj, proc());
164           assert(child_obj);
165           addMappedObject(child_obj);
166         }
167         // This clones funcs, which then clone instPoints, which then 
168         // clone baseTramps, which then clones miniTramps.
169     }
170
171
172     // Clone the tramp guard base
173     if (parent->trampGuardBase_) 
174       trampGuardBase_ = new int_variable(parent->trampGuardBase_, getAOut()->getDefaultModule());
175     else
176       trampGuardBase_ = NULL;
177
178     /////////////////////////
179     // Inferior heap
180     /////////////////////////
181
182     heap_ = inferiorHeap(parent->heap_);
183     heapInitialized_ = parent->heapInitialized_;
184
185     /////////////////////////
186     // Trap mappings
187     /////////////////////////
188     trapMapping.copyTrapMappings(& (parent->trapMapping));
189
190     /////////////////////////
191     // Overly complex code tracking system
192     /////////////////////////
193     for (CodeTrackers::iterator iter = parent->relocatedCode_.begin();
194          iter != parent->relocatedCode_.end(); ++iter) {
195        // Efficiency; this avoids a spurious copy of the entire
196        // CodeTracker. 
197
198        relocatedCode_.push_back(Relocation::CodeTracker::fork(*iter, this));
199     }
200     
201     // Let's assume we're not forking _in the middle of instrumentation_
202     // (good Lord), and so leave modifiedFunctions_ alone.
203     /*
204     for (CallModMap::iterator iter = parent->callModifications_.begin(); 
205          iter != parent->callModifications_.end(); ++iter) {
206        // Need to forward map the lot
207        block_instance *newB = findBlock(iter->first->llb());
208        for (std::map<func_instance *, func_instance *>::iterator iter2 = iter->second.begin();
209             iter2 != iter->second.end(); ++iter2) {
210           func_instance *context = (iter2->first == NULL) ? NULL : findFunction(iter2->first->ifunc());
211           func_instance *target = (iter2->second == NULL) ? NULL : findFunction(iter2->second->ifunc());
212           callModifications_[newB][context] = target;
213        }
214     }
215     */
216
217     assert(parent->mgr());
218     PatchAPI::CallModMap& cmm = parent->mgr()->instrumenter()->callModMap();
219     for (PatchAPI::CallModMap::iterator iter = cmm.begin(); iter != cmm.end(); ++iter) {
220        // Need to forward map the lot
221       block_instance *newB = findBlock(SCAST_BI(iter->first)->llb());
222       for (std::map<PatchFunction*, PatchFunction*>::iterator iter2 = iter->second.begin();
223             iter2 != iter->second.end(); ++iter2) {
224         func_instance *context = (SCAST_FI(iter2->first) == NULL) ? NULL : findFunction(SCAST_FI(iter2->first)->ifunc());
225         func_instance *target = (SCAST_FI(iter2->second) == NULL) ? NULL : findFunction(SCAST_FI(iter2->second)->ifunc());
226         cmm[newB][context] = target;
227        }
228     }
229
230     PatchAPI::FuncModMap& frm = parent->mgr()->instrumenter()->funcRepMap();
231     for (PatchAPI::FuncModMap::iterator iter = frm.begin(); iter != frm.end(); ++iter) {
232       func_instance *from = findFunction(SCAST_FI(iter->first)->ifunc());
233       func_instance *to = findFunction(SCAST_FI(iter->second)->ifunc());
234       frm[from] = to;
235     }
236
237     PatchAPI::FuncWrapMap& fwm = parent->mgr()->instrumenter()->funcWrapMap();
238     for (PatchAPI::FuncWrapMap::iterator iter = fwm.begin(); iter != fwm.end(); ++iter) {
239       func_instance *from = findFunction(SCAST_FI(iter->first)->ifunc());
240       func_instance *to = findFunction(SCAST_FI(iter->second.first)->ifunc());
241       fwm[from] = std::make_pair(to, iter->second.second);
242     }
243
244     if (memEmulator_) assert(0 && "FIXME!");
245     emulateMem_ = parent->emulateMem_;
246     emulatePC_ = parent->emulatePC_;
247 }
248
249 void AddressSpace::deleteAddressSpace() {
250    // Methodically clear everything we have - it all went away
251    // We have the following member variables:
252
253    // bool heapInitialized_
254    // inferiorHeap heap_
255
256    heapInitialized_ = false;
257    heap_.clear();
258    for (unsigned i = 0; i < mapped_objects.size(); i++) 
259       delete mapped_objects[i];
260
261    mapped_objects.clear();
262
263    runtime_lib.clear();
264
265    trampGuardBase_ = NULL;
266    trampGuardAST_ = AstNodePtr();
267
268    // up_ptr_ is untouched
269    costAddr_ = 0;
270    for (CodeTrackers::iterator iter = relocatedCode_.begin(); 
271         iter != relocatedCode_.end(); ++iter) {
272       delete *iter;
273    }
274    relocatedCode_.clear();
275    modifiedFunctions_.clear();
276    forwardDefensiveMap_.clear();
277    reverseDefensiveMap_.clear();
278    instrumentationInstances_.clear();
279
280    if (memEmulator_) delete memEmulator_;
281    memEmulator_ = NULL;
282 }
283
284
285
286 // Returns the named symbol from the image or a shared object
287 bool AddressSpace::getSymbolInfo( const std::string &name, int_symbol &ret ) 
288 {
289    for (unsigned i = 0; i < mapped_objects.size(); i++) {
290       if (mapped_objects[i]->getSymbolInfo( name, ret ))
291          return true;
292    }
293    return false;
294 }
295
296 bool heapItemLessByAddr(const heapItem *a, const heapItem *b)
297 {
298    if (a->addr < b->addr) {
299       return true;
300    }
301    return false;
302 }
303
304 //////////////////////////////////////////////////////////////////////////////
305 // Memory allocation routines
306 //////////////////////////////////////////////////////////////////////////////
307
308
309 void AddressSpace::inferiorFreeCompact() {
310    pdvector<heapItem *> &freeList = heap_.heapFree;
311    unsigned i, nbuf = freeList.size();
312
313    /* sort buffers by address */
314 #if defined (cap_use_pdvector)
315     std::sort(freeList.begin(), freeList.end(), ptr_fun(heapItemCmpByAddr));
316 #else
317     std::sort(freeList.begin(), freeList.end(), ptr_fun(heapItemLessByAddr));
318 #endif
319
320
321    /* combine adjacent buffers */
322    bool needToCompact = false;
323    for (i = 1; i < freeList.size(); i++) {
324       heapItem *h1 = freeList[i-1];
325       heapItem *h2 = freeList[i];
326       assert(h1->length != 0);
327       if (h1->addr + h1->length > h2->addr) {
328          fprintf(stderr, "Error: heap 1 (%p) (0x%p to 0x%p) overlaps heap 2 (%p) (0x%p to 0x%p)\n",
329                  h1,
330                  (void *)h1->addr, (void *)(h1->addr + h1->length),
331                  h2,
332                  (void *)h2->addr, (void *)(h2->addr + h2->length));
333       }
334       assert(h1->addr + h1->length <= h2->addr);
335       if (h1->addr + h1->length == h2->addr
336           && h1->type == h2->type) {
337          h2->addr = h1->addr;
338          h2->length = h1->length + h2->length;
339          h1->length = 0;
340          nbuf--;
341          needToCompact = true;
342       }
343    }
344
345    /* remove any absorbed (empty) buffers */ 
346    if (needToCompact) {
347       pdvector<heapItem *> cleanList;
348       unsigned end = freeList.size();
349       for (i = 0; i < end; i++) {
350          heapItem *h1 = freeList[i];
351          if (h1->length != 0) {
352             cleanList.push_back(h1);
353          } else {
354             delete h1;
355          }
356       }
357       assert(cleanList.size() == nbuf);
358       for (i = 0; i < nbuf; i++) {
359          freeList[i] = cleanList[i];
360       }
361       freeList.resize(nbuf);
362       assert(freeList.size() == nbuf);
363    }
364 }
365     
366 int AddressSpace::findFreeIndex(unsigned size, int type, Address lo, Address hi) {
367    // type is a bitmask: match on any bit in the mask
368    pdvector<heapItem *> &freeList = heap_.heapFree;
369     
370    int best = -1;
371    for (unsigned i = 0; i < freeList.size(); i++) {
372       heapItem *h = freeList[i];
373       // check if free block matches allocation constraints
374       // Split out to facilitate debugging
375       infmalloc_printf("%s[%d]: comparing heap %d: 0x%lx-0x%lx/%d to desired %d bytes in 0x%lx-0x%lx/%d\n",
376                        FILE__, __LINE__, 
377                        i,
378                        h->addr, 
379                        h->addr + h->length,
380                        h->type,
381                        size,
382                        lo, 
383                        hi,
384                        type);
385       if (h->addr >= lo &&
386           (h->addr + size - 1) <= hi &&
387           h->length >= size &&
388           h->type & type) {
389          if (best == -1)
390             best = i;
391          // check for better match
392          if (h->length < freeList[best]->length) best = i;
393       }
394    }
395    infmalloc_printf("%s[%d]: returning match %d\n", FILE__, __LINE__, best);
396    return best;
397 }
398
399 void AddressSpace::addHeap(heapItem *h) {
400    heap_.bufferPool.push_back(h);
401    heapItem *h2 = new heapItem(h);
402    h2->status = HEAPfree;
403    heap_.heapFree.push_back(h2);
404     
405    /* When we add an item to heapFree, make sure it remains in sorted order */
406    std::sort(heap_.heapFree.begin(), heap_.heapFree.end(), ptr_fun(heapItemLessByAddr));
407
408    heap_.totalFreeMemAvailable += h2->length;
409
410    if (h->dynamic) {
411       addAllocatedRegion(h->addr, h->length);
412    }
413 }
414
415 void AddressSpace::initializeHeap() {
416    // (re)initialize everything 
417    heap_.heapActive.clear();
418    heap_.heapFree.resize(0);
419    heap_.disabledList.resize(0);
420    heap_.disabledListTotalMem = 0;
421    heap_.freed = 0;
422    heap_.totalFreeMemAvailable = 0;
423
424    heapInitialized_ = true;
425 }
426
427 /* returns true if memory was allocated for a variable starting at address
428    "block", otherwise returns false
429 */
430 bool AddressSpace::isInferiorAllocated(Address block) {
431    return (heap_.heapActive.find(block) != heap_.heapActive.end());
432 }
433
434 Address AddressSpace::inferiorMallocInternal(unsigned size,
435                                              Address lo,
436                                              Address hi,
437                                              inferiorHeapType type) {
438    infmalloc_printf("%s[%d]: inferiorMallocInternal, %d bytes, type %d, between 0x%lx - 0x%lx\n",
439                     FILE__, __LINE__, size, type, lo, hi);
440    int freeIndex = findFreeIndex(size, type, lo, hi);
441    if (freeIndex == -1) return 0; // Failure is often an option
442
443
444    // adjust active and free lists
445    assert(freeIndex != -1);
446    heapItem *h = heap_.heapFree[freeIndex];
447    assert(h);
448     
449    // remove allocated buffer from free list
450    if (h->length != size) {
451       // size mismatch: put remainder of block on free list
452       heapItem *rem = new heapItem(h);
453       rem->addr += size;
454       rem->length -= size;
455       heap_.heapFree[freeIndex] = rem;
456    } else {
457       // size match: remove entire block from free list
458       unsigned last = heap_.heapFree.size();
459       heap_.heapFree[freeIndex] = heap_.heapFree[last-1];
460       heap_.heapFree.resize(last-1);
461    }
462
463    /* When we update an item in heapFree, make sure it remains in sorted order */
464    std::sort(heap_.heapFree.begin(), heap_.heapFree.end(), ptr_fun(heapItemLessByAddr));
465
466    // add allocated block to active list
467    h->length = size;
468    h->status = HEAPallocated;
469    heap_.heapActive[h->addr] = h;
470    // bookkeeping
471    heap_.totalFreeMemAvailable -= size;
472    assert(h->addr);
473     
474    return(h->addr);
475 }
476
477 void AddressSpace::inferiorFreeInternal(Address block) {
478    // find block on active list
479    infmalloc_printf("%s[%d]: inferiorFree for block at 0x%lx\n", FILE__, __LINE__, block);
480
481    auto iter = heap_.heapActive.find(block);
482    if (iter == heap_.heapActive.end()) return;
483    heapItem *h = iter->second;
484    assert(h);
485
486    // Remove from the active list
487    heap_.heapActive.erase(iter);
488     
489    // Add to the free list
490    h->status = HEAPfree;
491    heap_.heapFree.push_back(h);
492
493    /* When we add an item to heapFree, make sure it remains in sorted order */
494    std::sort(heap_.heapFree.begin(), heap_.heapFree.end(), ptr_fun(heapItemLessByAddr));
495
496    heap_.totalFreeMemAvailable += h->length;
497    heap_.freed += h->length;
498    infmalloc_printf("%s[%d]: Freed block from 0x%lx - 0x%lx, %d bytes, type %d\n",
499                     FILE__, __LINE__,
500                     h->addr,
501                     h->addr + h->length,
502                     h->length,
503                     h->type);
504 }
505
506 void AddressSpace::inferiorMallocAlign(unsigned &size) {
507    // Align to the process word
508    unsigned alignment = (getAddressWidth() - 1);
509    size = (size + alignment) & ~alignment;
510 }
511     
512 bool AddressSpace::inferiorReallocInternal(Address block, unsigned newSize) {
513   //#if defined (cap_dynamic_heap)
514    // This is why it's not a reference...
515    inferiorMallocAlign(newSize);
516    //#endif
517     
518    infmalloc_printf("%s[%d]: inferiorRealloc for block 0x%lx, new size %d\n",
519                     FILE__, __LINE__, block, newSize);
520
521    auto iter = heap_.heapActive.find(block);
522    if (iter == heap_.heapActive.end()) {
523       // We can do this if we're at process teardown.
524       infmalloc_printf("%s[%d]: inferiorRealloc unable to find block, returning\n", FILE__, __LINE__);
525       return false;
526    }
527    heapItem *h = iter->second;
528    assert(h);
529    infmalloc_printf("%s[%d]: inferiorRealloc found block with addr 0x%lx, length %d\n",
530                     FILE__, __LINE__, h->addr, h->length);
531
532    if (h->length == newSize)
533       return true;
534    else if (h->length > newSize) {
535       // Shrink the block
536       return inferiorShrinkBlock(h, block, newSize);
537    }
538    else {
539       // See if we can grow this block
540       return inferiorExpandBlock(h, block, newSize);
541    }
542 }
543
544 bool AddressSpace::inferiorShrinkBlock(heapItem *h, 
545                                        Address block, 
546                                        unsigned newSize) {
547
548    // We make a new "free" block that is the end of this one.
549    Address freeStart = block + newSize;
550    Address succAddr = h->addr + h->length;
551    int shrink = h->length - newSize;
552     
553    assert(shrink > 0);
554     
555    h->length = newSize;
556     
557    // New speedy way. Find the block that is the successor of the
558    // active block; if it exists, simply enlarge it "downwards". Otherwise,
559    // make a new block. 
560    heapItem *succ = NULL;
561    for (unsigned i = 0; i < heap_.heapFree.size(); i++) {
562       heapItem *tmp = heap_.heapFree[i];
563       assert(tmp);
564       if (tmp->addr == succAddr) {
565          succ = tmp;
566          break;
567       }
568    }
569    if (succ != NULL) {
570       infmalloc_printf("%s[%d]: enlarging existing block; old 0x%lx - 0x%lx (%d), new 0x%lx - 0x%lx (%d)\n",
571                        FILE__, __LINE__,
572                        succ->addr,
573                        succ->addr + succ->length,
574                        succ->addr,
575                        succ->addr - shrink,
576                        succ->addr + succ->length,
577                        succ->length + shrink);
578
579
580       succ->addr -= shrink;
581       succ->length += shrink;
582    }
583    else {
584       // Must make a new block to represent the free memory
585       infmalloc_printf("%s[%d]: inferiorRealloc: creating new block 0x%lx to 0x%lx (%d), type %d\n",
586                        FILE__, __LINE__, 
587                        freeStart, 
588                        freeStart + shrink,
589                        shrink,
590                        h->type);
591
592       heapItem *freeEnd = new heapItem(freeStart,
593                                        shrink,
594                                        h->type,
595                                        h->dynamic,
596                                        HEAPfree);
597       heap_.heapFree.push_back(freeEnd);
598
599       /* When we add an item to heapFree, make sure it remains sorted */
600       std::sort(heap_.heapFree.begin(), heap_.heapFree.end(), ptr_fun(heapItemLessByAddr));
601    }
602
603    heap_.totalFreeMemAvailable += shrink;
604    heap_.freed += shrink;
605
606    return true;
607 }    
608
609 bool AddressSpace::inferiorExpandBlock(heapItem *h, 
610                                        Address, 
611                                        unsigned newSize) {
612    // We attempt to find a free block that immediately succeeds
613    // this one. If we find such a block we expand this block into
614    // the next; if this is possible we return true. Otherwise
615    // we return false.
616
617    Address succAddr = h->addr + h->length;
618    int expand = newSize - h->length;
619    assert(expand > 0);
620     
621    // New speedy way. Find the block that is the successor of the
622    // active block; if it exists, simply enlarge it "downwards". Otherwise,
623    // make a new block. 
624    heapItem *succ = NULL;
625    for (unsigned i = 0; i < heap_.heapFree.size(); i++) {
626       heapItem *tmp = heap_.heapFree[i];
627       assert(tmp);
628       if (tmp->addr == succAddr) {
629          succ = tmp;
630          break;
631       }
632    }
633    if (succ != NULL) {
634       if (succ->length < (unsigned) expand) {
635          // Can't fit
636          return false;
637       }
638       Address newFreeBase = succAddr + expand;
639       int newFreeLen = succ->length - expand;
640       succ->addr = newFreeBase;
641       succ->length = newFreeLen;
642
643       // If we've enlarged to exactly the end of the successor (succ->length == 0),
644       // remove succ
645       if (0x0 == succ->length) {
646           pdvector<heapItem *> cleanList;
647           unsigned end = heap_.heapFree.size();
648           for (unsigned i = 0; i < end; i++) {
649               heapItem * h1 = heap_.heapFree[i];
650               if (h1->length != 0) {
651                   cleanList.push_back(h1);
652               } else {
653                   delete h1;
654               }
655           }
656           end--;
657           for (unsigned i = 0; i < end; i++) {
658               heap_.heapFree[i] = cleanList[i];  
659           }
660           // Remove the last (now unused) element of the freeList
661           heap_.heapFree.pop_back();
662       }
663    }
664    else {
665       return false;
666    }
667
668    heap_.totalFreeMemAvailable -= expand;
669   
670    return true;
671 }    
672
673 /////////////////////////////////////////
674 // Function lookup...
675 /////////////////////////////////////////
676
677 bool AddressSpace::findFuncsByAll(const std::string &funcname,
678                                   pdvector<func_instance *> &res,
679                                   const std::string &libname) { // = "", btw
680     
681    unsigned starting_entries = res.size(); // We'll return true if we find something
682    for (unsigned i = 0; i < mapped_objects.size(); i++) {
683       if (libname == "" ||
684           mapped_objects[i]->fileName() == libname.c_str() ||
685           mapped_objects[i]->fullName() == libname.c_str()) {
686          const pdvector<func_instance *> *pretty = mapped_objects[i]->findFuncVectorByPretty(funcname);
687          if (pretty) {
688             // We stop at first match...
689             for (unsigned pm = 0; pm < pretty->size(); pm++) {
690                res.push_back((*pretty)[pm]);
691             }
692          }
693          else {
694             const pdvector<func_instance *> *mangled = mapped_objects[i]->findFuncVectorByMangled(funcname);
695             if (mangled) {
696                for (unsigned mm = 0; mm < mangled->size(); mm++) {
697                   res.push_back((*mangled)[mm]);
698                }
699             }
700          }
701       }
702    }
703
704    return (res.size() != starting_entries);
705 }
706
707
708 bool AddressSpace::findFuncsByPretty(const std::string &funcname,
709                                      pdvector<func_instance *> &res,
710                                      const std::string &libname) { // = "", btw
711
712    unsigned starting_entries = res.size(); // We'll return true if we find something
713
714    for (unsigned i = 0; i < mapped_objects.size(); i++) {
715       if (libname == "" ||
716           mapped_objects[i]->fileName() == libname.c_str() ||
717           mapped_objects[i]->fullName() == libname.c_str()) {
718          const pdvector<func_instance *> *pretty = mapped_objects[i]->findFuncVectorByPretty(funcname);
719          if (pretty) {
720             // We stop at first match...
721             for (unsigned pm = 0; pm < pretty->size(); pm++) {
722                res.push_back((*pretty)[pm]);
723             }
724          }
725       }
726    }
727    return res.size() != starting_entries;
728 }
729
730
731 bool AddressSpace::findFuncsByMangled(const std::string &funcname,
732                                       pdvector<func_instance *> &res,
733                                       const std::string &libname) { // = "", btw
734    unsigned starting_entries = res.size(); // We'll return true if we find something
735
736    for (unsigned i = 0; i < mapped_objects.size(); i++) {
737       if (libname == "" ||
738           mapped_objects[i]->fileName() == libname.c_str() ||
739           mapped_objects[i]->fullName() == libname.c_str()) {
740          const pdvector<func_instance *> *mangled = 
741             mapped_objects[i]->findFuncVectorByMangled(funcname);
742          if (mangled) {
743             for (unsigned mm = 0; mm < mangled->size(); mm++) {
744                res.push_back((*mangled)[mm]);
745             }
746          }
747       }
748    }
749    return res.size() != starting_entries;
750 }
751
752 func_instance *AddressSpace::findOnlyOneFunction(const string &name,
753                                                  const string &lib,
754                                                  bool /*search_rt_lib*/) 
755 {
756    assert(mapped_objects.size());
757
758    pdvector<func_instance *> allFuncs;
759
760    if (!findFuncsByAll(name.c_str(), allFuncs, lib.c_str()))
761       return NULL;
762
763    if (allFuncs.size() > 1) 
764    {
765       //cerr << "Warning: multiple matches for " << name << ", returning first" << endl;
766    }
767
768    return allFuncs[0];
769 }
770
771 /////////////////////////////////////////
772 // Variable lookup...
773 /////////////////////////////////////////
774
775 bool AddressSpace::findVarsByAll(const std::string &varname,
776                                  pdvector<int_variable *> &res,
777                                  const std::string &libname) { // = "", btw
778    unsigned starting_entries = res.size(); // We'll return true if we find something
779     
780    for (unsigned i = 0; i < mapped_objects.size(); i++) {
781       if (libname == "" ||
782           mapped_objects[i]->fileName() == libname.c_str() ||
783           mapped_objects[i]->fullName() == libname.c_str()) {
784          const pdvector<int_variable *> *pretty = mapped_objects[i]->findVarVectorByPretty(varname);
785          if (pretty) {
786             // We stop at first match...
787             for (unsigned pm = 0; pm < pretty->size(); pm++) {
788                res.push_back((*pretty)[pm]);
789             }
790          }
791          else {
792             const pdvector<int_variable *> *mangled = mapped_objects[i]->findVarVectorByMangled(varname);
793             if (mangled) {
794                for (unsigned mm = 0; mm < mangled->size(); mm++) {
795                   res.push_back((*mangled)[mm]);
796                }
797             }
798          }
799       }
800    }
801
802    return res.size() != starting_entries;
803 }
804
805
806
807 // Get me a pointer to the instruction: the return is a local
808 // (mutator-side) store for the mutatee. This may duck into the local
809 // copy for images, or a relocated function's self copy.
810 // TODO: is this really worth it? Or should we just use ptrace?
811
812 void *AddressSpace::getPtrToInstruction(const Address addr) const {
813    mapped_object *obj = findObject(addr);
814    if (obj) return obj->getPtrToInstruction(addr);
815
816    fprintf(stderr,"[%s:%d] failed to find matching range for address %lx\n",
817            FILE__,__LINE__,addr);
818    assert(0);
819    return NULL;
820 }
821
822 bool AddressSpace::isCode(const Address addr) const {
823    mapped_object *obj = findObject(addr);
824    if (!obj) return false;
825
826    Address objStart = obj->codeAbs();
827    Address objEnd;
828    if (BPatch_defensiveMode == obj->hybridMode()) {
829       objEnd = obj->memoryEnd();
830    } else {
831       objEnd = objStart + obj->imageSize();
832    }
833
834    return (addr >= objStart && addr <= objEnd);
835
836 }
837 bool AddressSpace::isData(const Address addr) const {
838    mapped_object *obj = findObject(addr);
839    if (!obj) return false;
840    
841    Address dataStart = obj->dataAbs();
842    if (addr >= dataStart &&
843        addr < (dataStart + obj->dataSize())) return true;
844    return false;
845 }
846
847 bool AddressSpace::isValidAddress(const Address addr) const {
848    mapped_object *obj = findObject(addr);
849    if (!obj) return false;
850    
851    if (obj->isCode(addr) || obj->isData(addr)) return true;
852    return false;
853 }
854
855 mapped_object *AddressSpace::findObject(Address addr) const {
856    for (unsigned i=0; i<mapped_objects.size(); i++)
857    {
858       Address objStart = mapped_objects[i]->codeAbs();
859       Address objEnd; // calculate objEnd
860       if (BPatch_defensiveMode == mapped_objects[i]->hybridMode()) {
861          objEnd = mapped_objects[i]->memoryEnd();
862       } else {
863          objEnd = objStart + mapped_objects[i]->imageSize();
864       }
865
866       if (addr >= objStart && addr < objEnd)
867       {
868          return mapped_objects[i];
869       }
870    }
871    return NULL;
872 }
873
874 mapped_object *AddressSpace::findObject(const ParseAPI::CodeObject *co) const {
875    mapped_object *obj = 
876       findObject(static_cast<ParseAPI::SymtabCodeSource*>(co->cs())->
877                  getSymtabObject()->file());
878    return obj;
879 }
880
881 func_instance *AddressSpace::findFunction(parse_func *ifunc) {
882    assert(ifunc);
883
884    return findObject(ifunc->obj())->findFunction(ifunc);
885 }
886
887 block_instance *AddressSpace::findBlock(parse_block *iblk) {
888    assert(iblk);
889
890    return findObject(iblk->obj())->findBlock(iblk);
891 }
892
893 edge_instance *AddressSpace::findEdge(ParseAPI::Edge *iedge) {
894    assert(iedge);
895    return findObject(iedge->src()->obj())->findEdge(iedge);
896 }
897
898 // findModule: returns the module associated with mod_name 
899 // this routine checks both the a.out image and any shared object
900 // images for this resource
901 mapped_module *AddressSpace::findModule(const std::string &mod_name, bool wildcard)
902 {
903    // KLUDGE: first search any shared libraries for the module name 
904    //  (there is only one module in each shared library, and that 
905    //  is the library name)
906    for(u_int j=0; j < mapped_objects.size(); j++){
907       mapped_module *mod = mapped_objects[j]->findModule(mod_name.c_str(), wildcard);
908       if (mod) {
909          return (mod);
910       }
911    }
912
913    return NULL;
914 }
915
916 // findObject: returns the object associated with obj_name 
917 // This just iterates over the mapped object vector
918 mapped_object *AddressSpace::findObject(std::string obj_name, bool wildcard) const
919 {
920    // Update: check by full name first because we may have non-unique fileNames. 
921    for(u_int j=0; j < mapped_objects.size(); j++){
922       if (mapped_objects[j]->fullName() == obj_name ||
923           (wildcard &&
924            wildcardEquiv(obj_name, mapped_objects[j]->fullName())))
925          return mapped_objects[j];
926    }
927
928    // get rid of the directory in the path
929    std::string orig_name = obj_name;
930    std::string::size_type dir = obj_name.rfind('/');
931    if (dir != std::string::npos) {
932       // +1, as that finds the slash and we don't want it. 
933       obj_name = obj_name.substr(dir+1);
934    } else {
935            dir = obj_name.rfind('\\');
936            if (dir != std::string::npos){
937                  obj_name = obj_name.substr(dir+1);
938            }
939    }
940
941    for(u_int j=0; j < mapped_objects.size(); j++){
942       if (mapped_objects[j]->fileName() == obj_name ||
943           (wildcard &&
944            wildcardEquiv(obj_name, mapped_objects[j]->fileName())))
945          return mapped_objects[j];
946    }
947 #if 0
948    cerr << "Warning: failed to find mapped_object matching " << obj_name
949         << " (originally " << orig_name << ")"
950         << " with wildcard " << (wildcard ? "<on>" : "<off>") << endl;
951    for (unsigned int i = 0; i < mapped_objects.size(); ++i) {
952       cerr << "\t" << mapped_objects[i]->fileName() << " / " << mapped_objects[i]->fullName() << endl;
953    }
954 #endif
955    return NULL;
956 }
957
958 // findObject: returns the object associated with obj_name 
959 // This just iterates over the mapped object vector
960 mapped_object *AddressSpace::findObject(fileDescriptor desc) const
961 {
962    for(u_int j=0; j < mapped_objects.size(); j++){
963       if (desc == mapped_objects[j]->getFileDesc()) 
964          return mapped_objects[j];
965    }
966    return NULL;
967 }
968
969 // getAllFunctions: returns a vector of all functions defined in the
970 // a.out and in the shared objects
971
972 void AddressSpace::getAllFunctions(pdvector<func_instance *> &funcs) {
973    for (unsigned i = 0; i < mapped_objects.size(); i++) {
974       mapped_objects[i]->getAllFunctions(funcs);
975    }
976 }
977       
978 // getAllModules: returns a vector of all modules defined in the
979 // a.out and in the shared objects
980
981 void AddressSpace::getAllModules(pdvector<mapped_module *> &mods){
982    for (unsigned i = 0; i < mapped_objects.size(); i++) {
983       const pdvector<mapped_module *> &obj_mods = mapped_objects[i]->getModules();
984       for (unsigned j = 0; j < obj_mods.size(); j++) {
985          mods.push_back(obj_mods[j]);
986       }
987    }
988 }
989
990 //Acts like findTargetFuncByAddr, but also finds the function if addr
991 // is an indirect jump to a function.
992 //I know this is an odd function, but darn I need it.
993 func_instance *AddressSpace::findJumpTargetFuncByAddr(Address addr) {
994
995    Address addr2 = 0;
996    func_instance *f = findOneFuncByAddr(addr);
997    if (f)
998       return f;
999
1000    if (!findObject(addr)) return NULL;
1001
1002    using namespace Dyninst::InstructionAPI;
1003    InstructionDecoder decoder((const unsigned char*)getPtrToInstruction(addr),
1004                               InstructionDecoder::maxInstructionLength,
1005                               getArch());
1006    Instruction::Ptr curInsn = decoder.decode();
1007     
1008    Expression::Ptr target = curInsn->getControlFlowTarget();
1009    RegisterAST thePC = RegisterAST::makePC(getArch());
1010    target->bind(&thePC, Result(u32, addr));
1011    Result cft = target->eval();
1012    if(cft.defined)
1013    {
1014       switch(cft.type)
1015       {
1016          case u32:
1017             addr2 = cft.val.u32val;
1018             break;
1019          case s32:
1020             addr2 = cft.val.s32val;
1021             break;
1022          default:
1023             assert(!"Not implemented for non-32 bit CFTs yet!");
1024             break;
1025       }
1026    }
1027    return findOneFuncByAddr(addr2);
1028 }
1029
1030 AstNodePtr AddressSpace::trampGuardAST() {
1031    if (!trampGuardBase_) {
1032       // Don't have it yet....
1033       return AstNodePtr();
1034    }
1035
1036    if (trampGuardAST_) return trampGuardAST_;
1037
1038    trampGuardAST_ = AstNode::operandNode(AstNode::variableAddr, trampGuardBase_->ivar());
1039    return trampGuardAST_;
1040 }
1041
1042
1043 trampTrapMappings::trampTrapMappings(AddressSpace *a) :
1044    needs_updating(false),
1045    as(a),
1046    trapTableUsed(NULL),
1047    trapTableVersion(NULL),
1048    trapTable(NULL),
1049    trapTableSorted(NULL),
1050    table_version(0),
1051    table_used(0),
1052    table_allocated(0),
1053    table_mutatee_size(0),
1054    current_table(0x0),
1055    table_header(0x0),
1056    blockFlushes(false)
1057 {
1058 }
1059
1060 void trampTrapMappings::copyTrapMappings(trampTrapMappings *parent)
1061 {
1062    needs_updating = parent->needs_updating;
1063    trapTableUsed = NULL;
1064    trapTableVersion = NULL;
1065    trapTable = NULL;
1066    trapTableSorted = NULL;
1067    table_version = parent->table_version;
1068    table_used = parent->table_used;
1069    table_allocated = parent->table_allocated;
1070    table_mutatee_size = parent->table_mutatee_size;
1071    current_table = parent->current_table;
1072    mapping = parent->mapping;
1073 }
1074
1075 void trampTrapMappings::clearTrapMappings()
1076 {
1077    needs_updating = false;
1078    trapTableUsed = NULL;
1079    trapTableVersion = NULL;
1080    trapTable = NULL;
1081    trapTableSorted = NULL;
1082    table_version = 0;
1083    table_used = 0;
1084    table_allocated = 0;
1085    table_mutatee_size = 0;
1086    current_table = 0;
1087    mapping.clear();
1088 }
1089
1090 void trampTrapMappings::addTrapMapping(Address from, Address to, 
1091                                        bool write_to_mutatee)
1092 {
1093 #if defined(arch_x86) || defined(arch_x86_64)
1094    //x86 traps occur at +1 addr
1095    from++;
1096 #endif
1097    tramp_mapping_t m;
1098    bool existing_trap = (mapping.count(from) != 0);
1099    m.from_addr = from;
1100    m.to_addr = to;
1101    m.written = false;
1102    m.cur_index = existing_trap ? mapping[from].cur_index : INDEX_INVALID;
1103    m.mutatee_side = write_to_mutatee;
1104    mapping[from] = m;
1105 #if defined(cap_mutatee_traps)
1106    updated_mappings.insert(& mapping[from]);
1107    if (write_to_mutatee && !existing_trap) {
1108       table_mutatee_size++;
1109    }
1110    needs_updating = true;
1111 #endif
1112 #if defined(arch_x86) || defined(arch_x86_64)
1113    from--;
1114 #endif
1115 }
1116
1117 bool trampTrapMappings::definesTrapMapping(Address from)
1118 {
1119    return mapping.count(from) != 0;
1120 }
1121
1122 Address trampTrapMappings::getTrapMapping(Address from)
1123 {
1124    if (!mapping.count(from))
1125       return 0;
1126    return mapping[from].to_addr;
1127 }
1128
1129 bool trampTrapMappings::needsUpdating()
1130 {
1131    return needs_updating;
1132 }
1133
1134 bool trampTrapMappings::empty() {
1135    return mapping.empty();
1136 }
1137
1138
1139 AddressSpace *trampTrapMappings::proc() const {
1140    return as;
1141 }
1142
1143 bool mapping_sort(const trampTrapMappings::tramp_mapping_t *lhs,
1144                   const trampTrapMappings::tramp_mapping_t *rhs)
1145 {
1146    return lhs->from_addr < rhs->from_addr;
1147 }
1148
1149 #if defined(cap_32_64)
1150 void trampTrapMappings::writeToBuffer(unsigned char *buffer, unsigned long val,
1151                                       unsigned addr_width)
1152 {
1153    //Deal with the case when mutatee word size != mutator word size
1154    if (addr_width != sizeof(Address)) {
1155       //Currently only support 64-bit mutators with 32-bit mutatees
1156       assert(addr_width == 4);
1157       assert(sizeof(Address) == 8);
1158       *((uint32_t *) buffer) = (uint32_t) val;
1159       return;
1160    }
1161    *((unsigned long *) buffer) = val;
1162 }
1163 #else
1164 void trampTrapMappings::writeToBuffer(unsigned char *buffer, unsigned long val,
1165                                       unsigned)
1166 {
1167    *((unsigned long *)(void*) buffer) = val;
1168 }
1169 #endif
1170
1171
1172 void trampTrapMappings::writeTrampVariable(const int_variable *var, 
1173                                            unsigned long val)
1174 {
1175    unsigned char buffer[16];
1176    unsigned aw = proc()->getAddressWidth();
1177
1178    writeToBuffer(buffer, val, aw);
1179    bool result = proc()->writeDataSpace((void *) var->getAddress(), aw, buffer);
1180    assert(result);
1181 }
1182                   
1183 void trampTrapMappings::arrange_mapping(tramp_mapping_t &m, bool should_sort,
1184                                         std::vector<tramp_mapping_t*> &mappings_to_add,
1185                                         std::vector<tramp_mapping_t*> &mappings_to_update)
1186 {
1187    if (!m.mutatee_side || (m.written && !should_sort))
1188       return;
1189    m.written = true;
1190    if (should_sort || m.cur_index == INDEX_INVALID)
1191       mappings_to_add.push_back(&m);
1192    else if (m.cur_index != INDEX_INVALID)
1193       mappings_to_update.push_back(&m);
1194 }
1195
1196 void trampTrapMappings::flush() {
1197    if (!needs_updating || blockFlushes)
1198       return;
1199
1200    set<mapped_object *> &rtlib = proc()->runtime_lib;
1201
1202    //We'll sort addresses in the binary rewritter (when writting only happens
1203    // once and we may do frequent lookups)
1204    //If we're using the dynamic instrumentor and creating a new table we might
1205    // as well sort it.
1206    //If we're just adding a few entries to the table which already fit, then
1207    // we'll just append them to the end of the table.
1208    //
1209    //If we're sorting, then everytime we update we'll generate a whole new table
1210    //If we're not sorting, then each update will just append to the end of the
1211    // table.
1212    bool should_sort = (dynamic_cast<PCProcess *>(proc()) == NULL ||
1213                        table_mutatee_size > table_allocated);
1214
1215    if (should_sort) {
1216       table_used = 0; //We're rebuilding the table, nothing's used.
1217    }
1218
1219    /**
1220     * Fill in the mappings_to_add and mappings_to_update vectors.
1221     * As an optimization, we keep a list of the mappings that have
1222     * changed in updated_mappings.  If we're not completly regenerating
1223     * the table we'll get our trap list out of updated_mappings, 
1224     * otherwise we'll get our change list out of the entire dyn_hash_map.
1225     **/
1226    std::vector<tramp_mapping_t*> mappings_to_add;
1227    std::vector<tramp_mapping_t*> mappings_to_update;
1228    if (should_sort) {
1229       dyn_hash_map<Address, tramp_mapping_t>::iterator i;
1230       for (i = mapping.begin(); i != mapping.end(); i++) {
1231          arrange_mapping((*i).second, should_sort, 
1232                          mappings_to_add, mappings_to_update);
1233       }
1234    } 
1235    else {
1236       std::set<tramp_mapping_t *>::iterator i;
1237       for (i = updated_mappings.begin(); i != updated_mappings.end(); i++) {
1238          arrange_mapping(**i, should_sort, 
1239                          mappings_to_add, mappings_to_update);
1240       }
1241    }
1242    updated_mappings.clear();
1243
1244    assert(mappings_to_add.size() + table_used == table_mutatee_size);
1245
1246    for (unsigned k=0; k<mappings_to_add.size(); k++)
1247    {
1248       mappings_to_add[k]->written = true;
1249    }
1250
1251    //Sort the mappings (if needed) 
1252    if (should_sort) 
1253       std::sort(mappings_to_add.begin(), mappings_to_add.end(), mapping_sort);
1254
1255    // Assign the cur_index field of each entry in the new mappings we're adding
1256    for (unsigned j=0; j<mappings_to_add.size(); j++) {
1257       mappings_to_add[j]->cur_index = table_used + j;
1258    }
1259    
1260    //Each table entry has two pointers.
1261    unsigned entry_size = proc()->getAddressWidth() * 2;
1262
1263    Address write_addr = 0x0;
1264
1265    allocateTable();
1266
1267    //Add any new entries to the table
1268    unsigned char *buffer = NULL;
1269    if (mappings_to_add.size()) {
1270       //Create a buffer containing the new entries we're going to write.
1271       unsigned long bytes_to_add = mappings_to_add.size() * entry_size;
1272       buffer = (unsigned char *) malloc(bytes_to_add);
1273       assert(buffer);
1274       
1275       unsigned char *cur = buffer;
1276       std::vector<tramp_mapping_t*>::iterator j;
1277       for (j = mappings_to_add.begin(); j != mappings_to_add.end(); j++) {
1278          tramp_mapping_t &tm = **j;
1279          writeToBuffer(cur, tm.from_addr, proc()->getAddressWidth());
1280          cur += proc()->getAddressWidth();
1281          writeToBuffer(cur, tm.to_addr, proc()->getAddressWidth());
1282          cur += proc()->getAddressWidth();
1283       }
1284       assert(cur == buffer + bytes_to_add);
1285       
1286       //Write the new entries into the process
1287       write_addr = current_table + (table_used * entry_size);
1288       bool result = proc()->writeDataSpace((void *) write_addr, bytes_to_add, 
1289                                            buffer);
1290       assert(result);
1291       free(buffer);
1292       buffer = NULL;
1293
1294       table_used += mappings_to_add.size();
1295    }
1296
1297    //Now we get to update existing entries that have been modified.
1298    if (mappings_to_update.size()) {
1299       assert(!should_sort);
1300       unsigned aw = proc()->getAddressWidth();
1301       buffer = (unsigned char *) malloc(aw);
1302       assert(buffer);
1303
1304       //For each entry, use its cur_index field to figure out where in the
1305       // process it is, and write it.
1306       //We only need to update the to_addr, since this is an update of an
1307       // existing from_addr
1308       std::vector<tramp_mapping_t*>::iterator j;
1309       for (j = mappings_to_update.begin(); j != mappings_to_update.end(); j++) {
1310          tramp_mapping_t &tm = **j;
1311          writeToBuffer(buffer, tm.to_addr, aw);
1312
1313          Address write_addr = current_table + (tm.cur_index * entry_size) + aw;
1314          bool result = proc()->writeDataSpace((void *) write_addr, aw, buffer);
1315          assert(result);
1316       }
1317       
1318       free(buffer);
1319       buffer = NULL;
1320    }
1321
1322    //This function just keeps going... Now we need to take all of those 
1323    // mutatee side variables and update them.
1324    if (dynamic_cast<PCProcess *>(proc())) 
1325    {
1326       if (!trapTable) {
1327          //Lookup all variables that are in the rtlib
1328          set<mapped_object *>::iterator rtlib_it;
1329          for(rtlib_it = rtlib.begin(); rtlib_it != rtlib.end(); ++rtlib_it) {
1330             if( !trapTableUsed ) trapTableUsed = (*rtlib_it)->getVariable("dyninstTrapTableUsed");
1331             if( !trapTableVersion ) trapTableVersion = (*rtlib_it)->getVariable("dyninstTrapTableVersion");
1332             if( !trapTable ) trapTable = (*rtlib_it)->getVariable("dyninstTrapTable");
1333             if( !trapTableSorted ) trapTableSorted = (*rtlib_it)->getVariable("dyninstTrapTableIsSorted");
1334          }
1335          
1336          if (!trapTableUsed) {
1337             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");
1338          }
1339          assert(trapTableUsed);
1340          assert(trapTableVersion);
1341          assert(trapTable);
1342          assert(trapTableSorted);
1343       }
1344    
1345       writeTrampVariable(trapTableUsed, table_used);
1346       writeTrampVariable(trapTableVersion, ++table_version);
1347       writeTrampVariable(trapTable, (unsigned long) current_table);
1348       writeTrampVariable(trapTableSorted, should_sort ? 1 : 0);
1349    }
1350
1351    needs_updating = false;
1352 }
1353
1354 void trampTrapMappings::allocateTable()
1355 {
1356    unsigned entry_size = proc()->getAddressWidth() * 2;
1357
1358    if (dynamic_cast<PCProcess *>(proc()))
1359    {
1360       //Dynamic rewriting
1361
1362       //Allocate the space for the tramp mapping table, or make sure that enough
1363       // space already exists.
1364       if (table_mutatee_size > table_allocated) {
1365          //Free old table
1366          if (current_table) {
1367             proc()->inferiorFree(current_table);
1368          }
1369          
1370          //Calculate size of new table
1371          table_allocated = (unsigned long) (table_mutatee_size * 1.5);
1372          if (table_allocated < MIN_TRAP_TABLE_SIZE)
1373             table_allocated = MIN_TRAP_TABLE_SIZE;
1374          
1375          //allocate
1376          current_table = proc()->inferiorMalloc(table_allocated * entry_size);
1377          assert(current_table);
1378       }
1379       return;
1380    }
1381
1382    //Static rewriting
1383    BinaryEdit *binedit = dynamic_cast<BinaryEdit *>(proc());
1384    assert(!current_table);
1385    assert(binedit);
1386    
1387    table_allocated = (unsigned long) table_mutatee_size;
1388    table_header = proc()->inferiorMalloc(table_allocated * entry_size + 
1389                                          sizeof(trap_mapping_header));
1390    trap_mapping_header header;
1391    header.signature = TRAP_HEADER_SIG;
1392    header.num_entries = table_mutatee_size;
1393    header.pos = -1;
1394    header.low_entry = 0;
1395    header.high_entry = 0;
1396
1397    bool result = proc()->writeDataSpace((void *) table_header, 
1398                                         sizeof(trap_mapping_header),
1399                                         &header);
1400    assert(result);   
1401    current_table = table_header + sizeof(trap_mapping_header);
1402
1403    SymtabAPI::Symtab *symtab = 
1404       binedit->getMappedObject()->parse_img()->getObject();
1405    if( !symtab->isStaticBinary() ) {
1406        symtab->addSysVDynamic(DT_DYNINST, table_header);
1407        symtab->addLibraryPrereq(proc()->dyninstRT_name);
1408       symtab->addSysVDynamic(DT_DYNINST, table_header);
1409       symtab->addLibraryPrereq(proc()->dyninstRT_name);
1410 #if defined (os_windows)
1411       symtab->addTrapHeader_win((Address)table_header);
1412 #endif
1413    }
1414 }
1415
1416 bool AddressSpace::findFuncsByAddr(Address addr, std::set<func_instance*> &funcs, bool includeReloc)
1417 {
1418    if (includeReloc) {
1419       RelocInfo ri;
1420       if (getRelocInfo(addr, ri)) {
1421
1422          if (proc() && BPatch_defensiveMode == proc()->getHybridMode()) {
1423             // check that the block & function still exist
1424             mapped_object *obj = findObject(ri.orig);
1425             if (!obj) {
1426                return false;
1427             }
1428             std::set<block_instance*> blocks;
1429             if (!obj->findBlocksByAddr(ri.orig, blocks)) {
1430                return false; // block no longer exists
1431             }
1432          }
1433          if (ri.func) {
1434             // We cloned for some reason. Nifty.
1435             funcs.insert(ri.func);
1436          }
1437          else {
1438             // We copied a block sans function context, so...
1439             // grab everyone
1440             ri.block->getFuncs(std::inserter(funcs, funcs.end()));
1441          }
1442          return true;
1443       }
1444    }
1445    mapped_object *obj = findObject(addr);
1446    if (!obj) return false;
1447    return obj->findFuncsByAddr(addr, funcs);
1448 }
1449
1450 bool AddressSpace::findBlocksByAddr(Address addr, std::set<block_instance *> &blocks, bool includeReloc) {
1451    if (includeReloc) {
1452       RelocInfo ri;
1453       if (getRelocInfo(addr, ri)) {
1454          blocks.insert(ri.block);
1455          return true;
1456       }
1457    }
1458
1459    mapped_object *obj = findObject(addr);
1460    if (!obj) return false;
1461    bool ret = obj->findBlocksByAddr(addr, blocks);
1462    if (ret || !includeReloc)
1463       return ret;
1464    return false;
1465 }
1466
1467 func_instance *AddressSpace::findFuncByEntry(const block_instance *block) {
1468    mapped_object *obj = findObject(block->start());
1469    if (!obj) return NULL;
1470    return obj->findFuncByEntry(block);
1471 }
1472
1473 block_instance *AddressSpace::findBlockByEntry(Address a) {
1474    mapped_object *obj = findObject(a);
1475    if (!obj) return NULL;
1476    return obj->findBlockByEntry(a);
1477 }
1478
1479 func_instance *AddressSpace::findOneFuncByAddr(Address addr) {
1480    std::set<func_instance *> funcs;
1481    if (!findFuncsByAddr(addr, funcs)) return NULL;
1482    if (funcs.empty()) return NULL;
1483    if (funcs.size() == 1) return *(funcs.begin());
1484    // Arbitrarily pick one...
1485    Address last = 0;
1486    func_instance *ret = NULL;
1487    for (std::set<func_instance *>::iterator iter = funcs.begin();
1488         iter != funcs.end(); ++iter) {
1489       if (ret == NULL ||
1490           ((*iter)->entryBlock()->start() > last)) {
1491          ret = *iter;
1492          last = (*iter)->entryBlock()->start();
1493       }
1494    }
1495    return ret;
1496 }
1497
1498 func_instance *AddressSpace::findFuncByEntry(Address addr) {
1499    std::set<func_instance *> funcs;
1500    if (!findFuncsByAddr(addr, funcs)) return NULL;
1501    if (funcs.empty()) return NULL;
1502
1503    for (std::set<func_instance *>::iterator iter = funcs.begin();
1504         iter != funcs.end(); ++iter) {
1505       if ((*iter)->entryBlock()->start() == addr) {
1506          return *iter;
1507       }
1508    }
1509    return NULL;
1510 }
1511
1512
1513 bool AddressSpace::canUseTraps()
1514 {
1515 #if !defined(cap_mutatee_traps)
1516    return false;
1517 #else
1518    return useTraps_;
1519 #endif
1520 }
1521
1522 void AddressSpace::setUseTraps(bool usetraps)
1523 {
1524    useTraps_ = usetraps;
1525 }
1526
1527 bool AddressSpace::needsPIC(int_variable *v)
1528 {
1529    return needsPIC(v->mod()->proc());
1530 }
1531
1532 bool AddressSpace::needsPIC(func_instance *f)
1533 {
1534    return needsPIC(f->proc());
1535 }
1536
1537 bool AddressSpace::needsPIC(AddressSpace *s)
1538 {
1539    if (proc())
1540       return false; //Never PIC for dynamic
1541    if (this != s)
1542       return true; //Use PIC cross module
1543    return s->needsPIC(); //Use target module
1544 }
1545
1546 bool AddressSpace::sameRegion(Address addr1, Address addr2)
1547 {
1548    mapped_object *mobj = findObject(addr1);
1549    if (!mobj || mobj != findObject(addr2)) {
1550       return false;
1551    }
1552    Address baseAddr = mobj->codeBase();
1553
1554    SymtabAPI::Region *reg1 = 
1555       mobj->parse_img()->getObject()->findEnclosingRegion( addr1 - baseAddr );
1556
1557    if (!reg1 || reg1 != mobj->parse_img()->getObject()->
1558        findEnclosingRegion( addr2 - baseAddr )) {
1559       return false;
1560    }
1561    return true;
1562 }
1563 ////////////////////////////////////////////////////////////////////////////////////////
1564
1565 void AddressSpace::modifyCall(block_instance *block, func_instance *newFunc, func_instance *context) {
1566    // Just register it for later code generation
1567    //callModifications_[block][context] = newFunc;
1568    mgr()->instrumenter()->modifyCall(block, newFunc, context);
1569    if (context) addModifiedFunction(context);
1570    else addModifiedBlock(block);
1571 }
1572
1573 void AddressSpace::replaceFunction(func_instance *oldfunc, func_instance *newfunc) {
1574    mgr()->instrumenter()->replaceFunction(oldfunc, newfunc);
1575    addModifiedFunction(oldfunc);
1576 }
1577
1578 bool AddressSpace::wrapFunction(func_instance *original, 
1579                                 func_instance *wrapper,
1580                                 SymtabAPI::Symbol *clone) {
1581    if (!original) return false;
1582    if (!wrapper) return false;
1583    if (!clone) return false;
1584
1585    if (original->proc() != this) {
1586       return original->proc()->wrapFunction(original, wrapper, clone);
1587    }
1588    assert(original->proc() == this);
1589
1590
1591    // 1) Replace original with wrapper via entry point jumps;
1592    //    this is handled in the instrumenter. 
1593    // 2) Create a copy of original with the new provided name. 
1594    // 3) (binary editing): update the various Symtab tables
1595    //      with the new name.
1596    //    (process) replace any PLT stubs to the clone with intermodule
1597    //      branches to this copy. 
1598
1599    // TODO: once we have PatchAPI updated a bit, break this into
1600    // steps 1-3. For now, keep it together. 
1601    mgr()->instrumenter()->wrapFunction(original, wrapper, clone->getMangledName());
1602    addModifiedFunction(original);
1603
1604    wrappedFunctionWorklist_[original] = clone;
1605
1606    return true;
1607 }
1608
1609 void AddressSpace::wrapFunctionPostPatch(func_instance *func, Dyninst::SymtabAPI::Symbol *clone) {
1610    if (edit()) {
1611       func->addSymbolsForCopy();
1612    }
1613    else {
1614       Address newAddr = func->getWrapperSymbol()->getOffset();
1615       // We have copied the original function and given it the address
1616       // newAddr. We now need to update any references calling the clone
1617       // symbol and point them at newAddr. Effectively, we're acting as
1618       // a proactive loader. 
1619       
1620       for (unsigned i = 0; i < mapped_objects.size(); ++i) {
1621          // Need original to get intermodule working right. 
1622          mapped_objects[i]->replacePLTStub(clone, func, newAddr);
1623       }
1624    }
1625 }
1626
1627 void AddressSpace::removeCall(block_instance *block, func_instance *context) {
1628   mgr()->instrumenter()->removeCall(block, context);
1629   if (context) addModifiedFunction(context);
1630   else addModifiedBlock(block);
1631 }
1632
1633 void AddressSpace::revertCall(block_instance *block, func_instance *context) {
1634   /*
1635    if (callModifications_.find(block) != callModifications_.end()) {
1636       callModifications_[block].erase(context);
1637    }
1638   */
1639   mgr()->instrumenter()->revertModifiedCall(block, context);
1640   if (context) addModifiedFunction(context);
1641   else addModifiedBlock(block);
1642 }
1643
1644 void AddressSpace::revertReplacedFunction(func_instance *oldfunc) {
1645   //functionReplacements_.erase(oldfunc);
1646   mgr()->instrumenter()->revertReplacedFunction(oldfunc);
1647   addModifiedFunction(oldfunc);
1648 }
1649
1650 void AddressSpace::revertWrapFunction(func_instance *wrappedfunc) {
1651    // Undo the instrumentation component
1652    mgr()->instrumenter()->revertWrappedFunction(wrappedfunc);
1653    addModifiedFunction(wrappedfunc);
1654    wrappedFunctionWorklist_.erase(wrappedfunc);
1655 }
1656
1657 const func_instance *AddressSpace::isFunctionReplacement(func_instance *func) const
1658 {
1659     PatchAPI::FuncModMap repFuncs = mgr_->instrumenter()->funcRepMap();
1660     PatchAPI::FuncModMap::const_iterator frit = repFuncs.begin();
1661     for (; frit != repFuncs.end(); frit++) {
1662         if (func == frit->second) {
1663             return static_cast<const func_instance*>(frit->first);
1664         }
1665     }
1666     return NULL;
1667 }
1668
1669
1670 using namespace Dyninst;
1671 using namespace Relocation;
1672
1673 bool AddressSpace::delayRelocation() const {
1674    return delayRelocation_;
1675 }
1676
1677 bool AddressSpace::relocate() {
1678    if (delayRelocation()) return true;
1679    
1680    relocation_cerr << "ADDRSPACE::Relocate called; modified functions reports "
1681                    << modifiedFunctions_.size() << " objects to relocate." << endl;
1682   if (!mapped_objects.size()) {
1683     relocation_cerr << "WARNING: No mapped_object in this addressSpace!\n";
1684     return false;
1685   }
1686
1687   bool ret = true;
1688   for (std::map<mapped_object *, FuncSet>::iterator iter = modifiedFunctions_.begin();
1689        iter != modifiedFunctions_.end(); ++iter) {
1690      FuncSet &modFuncs = iter->second;
1691
1692      bool repeat = false;
1693
1694      do { // add overlapping functions in a fixpoint calculation
1695         repeat = false;
1696         unsigned int num = modFuncs.size();
1697         FuncSet overlappingFuncs;
1698         for (FuncSet::iterator iter2 = modFuncs.begin(); iter2 != modFuncs.end(); ++iter2) {
1699            block_instance *entry = (*iter2)->entryBlock();
1700            entry->getFuncs(std::inserter(overlappingFuncs,overlappingFuncs.begin()));
1701         }
1702         modFuncs.insert(overlappingFuncs.begin(), overlappingFuncs.end());
1703         if (num < modFuncs.size()) {
1704            repeat = true;
1705         }
1706      } while (repeat);
1707      
1708      addModifiedRegion(iter->first);
1709      
1710      Address middle = (iter->first->codeAbs() + (iter->first->imageSize() / 2));
1711      
1712      if (!relocateInt(iter->second.begin(), iter->second.end(), middle)) {
1713         ret = false;
1714      }
1715      
1716   }
1717
1718   updateMemEmulator();
1719
1720   modifiedFunctions_.clear();
1721
1722   for (std::map<func_instance *, Dyninst::SymtabAPI::Symbol *>::iterator foo = wrappedFunctionWorklist_.begin();
1723        foo != wrappedFunctionWorklist_.end(); ++foo) {
1724       wrapFunctionPostPatch(foo->first, foo->second);
1725   }
1726   wrappedFunctionWorklist_.clear();
1727
1728   return ret;
1729 }
1730
1731 // iter is some sort of functions
1732 bool AddressSpace::relocateInt(FuncSet::const_iterator begin, FuncSet::const_iterator end, Address nearTo) {
1733
1734   if (begin == end) {
1735     return true;
1736   }
1737
1738   // Create a CodeMover covering these functions
1739   //cerr << "Creating a CodeMover" << endl;
1740
1741   relocatedCode_.push_back(new CodeTracker());
1742   CodeMover::Ptr cm = CodeMover::create(relocatedCode_.back());
1743   if (!cm->addFunctions(begin, end)) return false;
1744
1745   SpringboardBuilder::Ptr spb = SpringboardBuilder::createFunc(begin, end, this);
1746
1747   relocation_cerr << "Debugging CodeMover (pre-transform)" << endl;
1748   relocation_cerr << cm->format() << endl;
1749   transform(cm);
1750
1751   relocation_cerr << "Debugging CodeMover" << endl;
1752   relocation_cerr << cm->format() << endl;
1753
1754   relocation_cerr << "  Entering code generation loop" << endl;
1755   Address baseAddr = generateCode(cm, nearTo);
1756   if (!baseAddr) {
1757     relocation_cerr << "  ERROR: generateCode returned baseAddr of " << baseAddr << ", exiting" << endl;
1758     return false;
1759   }
1760
1761   if (dyn_debug_reloc || dyn_debug_write) {
1762       using namespace InstructionAPI;
1763       // Print out the buffer we just created
1764       cerr << "DUMPING RELOCATION BUFFER" << endl;
1765
1766       Address base = baseAddr;
1767       InstructionDecoder deco
1768         (cm->ptr(),cm->size(),getArch());
1769       Instruction::Ptr insn = deco.decode();
1770       while(insn) {
1771          cerr << "\t" << hex << base << ": " << insn->format(base) << dec << endl;
1772         base += insn->size();
1773         insn = deco.decode();
1774       }
1775       cerr << dec;
1776       cerr << endl;
1777  //     cerr << cm->format() << endl;
1778
1779   }
1780
1781
1782   // Copy it in
1783   relocation_cerr << "  Writing " << cm->size() << " bytes of data into program at "
1784                   << std::hex << baseAddr << std::dec << endl;
1785   if (!writeTextSpace((void *)baseAddr,
1786                       cm->size(),
1787                       cm->ptr()))
1788     return false;
1789
1790   // Now handle patching; AKA linking
1791   relocation_cerr << "  Patching in jumps to generated code" << endl;
1792
1793   if (!patchCode(cm, spb)) {
1794       relocation_cerr << "Error: patching in jumps failed, ret false!" << endl;
1795     return false;
1796   }
1797
1798   // Build the address mapping index
1799   relocatedCode_.back()->createIndices();
1800     
1801   // Kevin's stuff
1802   cm->extractDefensivePads(this);
1803
1804   if (proc()) {
1805       // adjust PC if active frame is in a modified function, this 
1806       // forces the instrumented version of the code to execute right 
1807       // away and is needed for code overwrites
1808       
1809       vector<PCThread *> threads;
1810       proc()->getThreads(threads);
1811
1812       vector<PCThread *>::const_iterator titer;
1813       for (titer = threads.begin();
1814            titer != threads.end(); 
1815            titer++) 
1816       {
1817           // translate thread's active PC to orig addr
1818           Frame tframe = (*titer)->getActiveFrame();
1819           Address curAddr = tframe.getPC();
1820
1821           Address orig = 0;
1822           block_instance *block = NULL;
1823           func_instance *func = NULL;
1824           unsigned offset = 0;
1825
1826           // Fill in the above
1827           // First, check in instrumentation
1828           RelocInfo ri;
1829           if (getRelocInfo(curAddr, ri)) {
1830              orig = ri.orig;
1831              block = ri.block;
1832              func = ri.func;
1833              // HACK: if we're in the middle of an emulation block, add that
1834              // offset to where we transfer to. 
1835              TrackerElement *te = NULL;
1836              for (CodeTrackers::const_iterator iter = relocatedCode_.begin();
1837                   iter != relocatedCode_.end(); ++iter) {
1838                 te = (*iter)->findByReloc(curAddr);
1839                 if (te) break;
1840              }
1841              
1842              if (te && te->type() == TrackerElement::emulated) {
1843                 offset = curAddr - te->reloc();
1844                 assert(offset < te->size());
1845              }
1846           } else {
1847              // In original code; do a slow and painful lookup. 
1848              orig = curAddr;
1849              mapped_object *obj = findObject(curAddr);
1850              if (!obj) break;
1851              block = obj->findOneBlockByAddr(curAddr);
1852              func = tframe.getFunc();
1853              offset = 0;
1854           }             
1855                         if (!block || !func) continue;
1856
1857           list<Address> relocPCs;
1858           getRelocAddrs(orig, block, func, relocPCs, true);
1859           mal_printf("Found %d matches for address 0x%lx\n", relocPCs.size(), orig);
1860           if (!relocPCs.empty()) {
1861              (*titer)->changePC(relocPCs.back() + offset);
1862              mal_printf("Pulling active frame PC into newest relocation "
1863                         "orig[%lx], cur[%lx], new[%lx (0x%lx + 0x%lx)]\n", orig, 
1864                         tframe.getPC(), relocPCs.back() + offset, relocPCs.back(), offset);
1865              break;
1866           }
1867       }
1868   }
1869   
1870   return true;
1871 }
1872
1873 bool AddressSpace::transform(CodeMover::Ptr cm) {
1874
1875    if (0 && proc() && BPatch_defensiveMode != proc()->getHybridMode()) {
1876        adhocMovementTransformer a(this);
1877        cm->transform(a);
1878    }
1879    else {
1880        PCSensitiveTransformer pc(this, cm->priorityMap());
1881         cm->transform(pc);
1882    }
1883
1884 #if defined(cap_mem_emulation)
1885    if (emulateMem_) {
1886       MemEmulatorTransformer m;
1887       cm->transform(m);
1888   }
1889 #endif
1890
1891   // Add instrumentation
1892   relocation_cerr << "Inst transformer" << endl;
1893   Instrumenter i;
1894   cm->transform(i);
1895
1896    Modification mod(mgr()->instrumenter()->callModMap(),
1897                     mgr()->instrumenter()->funcRepMap(),
1898                     mgr()->instrumenter()->funcWrapMap());
1899    cm->transform(mod);
1900
1901   return true;
1902
1903 }
1904
1905 Address AddressSpace::generateCode(CodeMover::Ptr cm, Address nearTo) {
1906   // And now we start the relocation process.
1907   // This is at heart an iterative process, using the following
1908   // algorithm
1909   // size = code size estimate
1910   // done = false
1911   // While (!done), do
1912   //   addr = inferiorMalloc(size)
1913   //   cm.relocate(addr)
1914   //   if ((cm.size <= size) || (inferiorRealloc(addr, cm.size)))
1915   //     done = true
1916   //   else
1917   //     size = cm.size
1918   //     inferiorFree(addr)
1919   // In effect, we keep trying until we get a code generation that fits
1920   // in the space we have allocated.
1921
1922   Address baseAddr = 0;
1923
1924   codeGen genTemplate;
1925   genTemplate.setAddrSpace(this);
1926   // Set the code emitter?
1927   
1928   if (!cm->initialize(genTemplate)) {
1929     return 0;
1930   }
1931
1932   while (1) {
1933      relocation_cerr << "   Attempting to allocate " << cm->size() << "bytes" << endl;
1934     unsigned size = cm->size();
1935     if (!size) {
1936         // This can happen if the only thing being moved are control flow instructions
1937         // (or other things that are _only_ patches)
1938         // inferiorMalloc horks if we hand it zero, so make sure it's non-zero.
1939         size = 1;
1940     }
1941     baseAddr = inferiorMalloc(size, anyHeap, nearTo);
1942     
1943     
1944     relocation_cerr << "   Calling CodeMover::relocate" << endl;
1945     if (!cm->relocate(baseAddr)) {
1946        // Whoa
1947        relocation_cerr << "   ERROR: CodeMover failed relocation!" << endl;
1948        return 0;
1949     }
1950     
1951     // Either attempt to expand or shrink...
1952     relocation_cerr << "   Calling inferiorRealloc to fit new size " << cm->size() 
1953                     << ", current base addr is " 
1954                     << std::hex << baseAddr << std::dec << endl;
1955     if (!inferiorRealloc(baseAddr, cm->size())) {
1956       relocation_cerr << "   ... inferiorRealloc failed, trying again" << endl;
1957       inferiorFree(baseAddr);
1958       continue;
1959     }
1960     else {
1961       relocation_cerr << "   ... inferiorRealloc succeeded, finished" << endl;
1962       break;
1963     }
1964   }
1965   
1966   if (!cm->finalize()) {
1967      return 0;
1968   }
1969
1970   //addrMap.debug();
1971
1972   return baseAddr;
1973 }
1974
1975 bool AddressSpace::patchCode(CodeMover::Ptr cm,
1976                              SpringboardBuilder::Ptr spb) {
1977    SpringboardMap &p = cm->sBoardMap(this);
1978   
1979   // A SpringboardMap has three priority sets: Required, Suggested, and
1980   // NotRequired. We care about:
1981   // Required: all
1982   // Suggested: function entries
1983   // NotRequired: none
1984
1985   std::list<codeGen> patches;
1986
1987   if (!spb->generate(patches, p)) {
1988       springboard_cerr << "Failed springboard generation, ret false" << endl;
1989     return false;
1990   }
1991
1992   springboard_cerr << "Installing " << patches.size() << " springboards!" << endl;
1993   for (std::list<codeGen>::iterator iter = patches.begin();
1994        iter != patches.end(); ++iter) 
1995   {
1996       springboard_cerr << "Writing springboard @ " << hex << iter->startAddr() << endl;
1997       if (!writeTextSpace((void *)iter->startAddr(),
1998           iter->used(),
1999           iter->start_ptr())) 
2000       {
2001         springboard_cerr << "\t FAILED to write springboard @ " << hex << iter->startAddr() << endl;
2002          // HACK: code modification will make this happen...
2003          return false;
2004       }
2005
2006     mapped_object *obj = findObject(iter->startAddr());
2007     if (obj && runtime_lib.end() == runtime_lib.find(obj)) {
2008         Address objBase = obj->codeBase();
2009         SymtabAPI::Region * reg = obj->parse_img()->getObject()->
2010             findEnclosingRegion(iter->startAddr() - objBase);
2011         if (memEmulator_)
2012            memEmulator_->addSpringboard(reg, 
2013                                         iter->startAddr() - objBase - reg->getMemOffset(),
2014                                         iter->used());
2015     }
2016   }
2017
2018   return true;
2019 };
2020
2021 void AddressSpace::causeTemplateInstantiations() {
2022 }
2023
2024 void AddressSpace::getRelocAddrs(Address orig, 
2025                                  block_instance *block,
2026                                  func_instance *func,
2027                                  std::list<Address> &relocs,
2028                                  bool getInstrumentationAddrs) const {
2029   springboard_cerr << "getRelocAddrs for orig addr " << hex << orig << " /w/ block start " << block->start() << dec << endl;
2030   for (CodeTrackers::const_iterator iter = relocatedCode_.begin();
2031        iter != relocatedCode_.end(); ++iter) {
2032     Relocation::CodeTracker::RelocatedElements reloc;
2033     //springboard_cerr << "\t Checking CodeTracker " << hex << *iter << dec << endl;
2034     if ((*iter)->origToReloc(orig, block, func, reloc)) {
2035       // Pick instrumentation if it's there, otherwise use the reloc instruction
2036        //springboard_cerr << "\t\t ... match" << endl;
2037        if (!reloc.instrumentation.empty() && getInstrumentationAddrs) {
2038           for (std::map<instPoint *, Address>::iterator iter2 = reloc.instrumentation.begin();
2039                iter2 != reloc.instrumentation.end(); ++iter2) {
2040              relocs.push_back(iter2->second);
2041           }
2042       }
2043       else {
2044         assert(reloc.instruction);
2045         relocs.push_back(reloc.instruction);
2046       }
2047     }
2048   }
2049 }      
2050
2051 bool AddressSpace::getAddrInfo(Address relocAddr,
2052                                Address &origAddr,
2053                                vector<func_instance *> &origFuncs,
2054                                baseTramp *&baseT) 
2055 {
2056    CodeTracker::RelocInfo ri;
2057    if (getRelocInfo(relocAddr, ri)) {
2058       origAddr = ri.orig;
2059       baseT = ri.bt;
2060       if (ri.func)
2061          origFuncs.push_back(ri.func);
2062       else {
2063          // We copied a block sans function context, so...
2064          // grab everyone
2065          ri.block->getFuncs(std::back_inserter(origFuncs));
2066       }
2067       return true;
2068    }      
2069    
2070    std::set<func_instance *> tmpFuncs;
2071    if (findFuncsByAddr(relocAddr, tmpFuncs)) {
2072       origAddr = relocAddr;
2073       origFuncs.insert(origFuncs.end(), tmpFuncs.begin(), tmpFuncs.end());
2074
2075       baseT = NULL;
2076       return true;
2077    }
2078       
2079    return false;
2080 }
2081
2082 // KEVINTODO: not clearing out entries when deleting code, and extremely slow in defensive mode, over 300 codetrackers for Yoda
2083 bool AddressSpace::getRelocInfo(Address relocAddr,
2084                                 RelocInfo &ri) {
2085   bool ret = false;
2086   // address is relocated (or bad), check relocation maps
2087   for (CodeTrackers::const_iterator iter = relocatedCode_.begin();
2088        iter != relocatedCode_.end(); ++iter) {
2089      if ((*iter)->relocToOrig(relocAddr, ri)) {
2090         assert(!ret);
2091         ret = true;
2092      }
2093   }
2094   return ret;
2095 }
2096
2097 bool AddressSpace::inEmulatedCode(Address addr) {
2098   // address is relocated (or bad), check relocation maps
2099   for (CodeTrackers::const_iterator iter = relocatedCode_.begin();
2100        iter != relocatedCode_.end(); ++iter)  {
2101      TrackerElement *te = (*iter)->findByReloc(addr);
2102      if (te) {
2103         if (te->type() == TrackerElement::emulated ||
2104             te->type() == TrackerElement::instrumentation) {
2105            return true;
2106         }
2107      }
2108   }
2109   return false;
2110 }
2111
2112 void AddressSpace::addModifiedFunction(func_instance *func) {
2113   assert(func->obj());
2114
2115   modifiedFunctions_[func->obj()].insert(func);
2116 }
2117
2118 void AddressSpace::addModifiedBlock(block_instance *block) {
2119    // TODO someday this will decouple from functions. Until
2120    // then...
2121    std::list<func_instance *> tmp;
2122    block->getFuncs(std::back_inserter(tmp));
2123    for (std::list<func_instance *>::iterator iter = tmp.begin();
2124         iter != tmp.end(); ++iter) {
2125       addModifiedFunction(*iter);
2126    }
2127 }
2128
2129
2130 void AddressSpace::addDefensivePad(block_instance *callBlock, func_instance *callFunc,
2131                                    Address padStart, unsigned size) {
2132   // We want to register these in terms of a block_instance that the pad ends, but 
2133   // the CFG can change out from under us; therefore, for lookup we use an instPoint
2134   // as they are invariant. 
2135    instPoint *point = instPoint::preCall(callFunc, callBlock);
2136    if (!point) {
2137       mal_printf("Error: no preCall point for %s\n",
2138                  callBlock->long_format().c_str());
2139       return;
2140    }
2141
2142    mal_printf("Adding pad for callBlock [%lx %lx), pad at 0%lx\n", 
2143               callBlock->start(), callBlock->end(), padStart);
2144
2145    forwardDefensiveMap_[callBlock->last()][callFunc].insert(std::make_pair(padStart, size));
2146    std::pair<func_instance*,Address> padContext;
2147    padContext.first = callFunc;
2148    padContext.second = callBlock->last();
2149    reverseDefensiveMap_.insert(padStart, padStart+size, padContext);
2150 }
2151
2152 void AddressSpace::getPreviousInstrumentationInstances(baseTramp *bt,
2153                                                        std::set<Address>::iterator &b,
2154                                                        std::set<Address>::iterator &e) {
2155   b = instrumentationInstances_[bt].begin();
2156   e = instrumentationInstances_[bt].end();
2157   return;
2158 }
2159
2160 void AddressSpace::addInstrumentationInstance(baseTramp *bt,
2161                                               Address a) {
2162   instrumentationInstances_[bt].insert(a);
2163 }
2164
2165 void AddressSpace::addAllocatedRegion(Address start, unsigned size) {
2166    if (memEmulator_) memEmulator_->addAllocatedRegion(start, size);
2167 }
2168
2169 void AddressSpace::addModifiedRegion(mapped_object *obj) {
2170    if (memEmulator_) memEmulator_->addRegion(obj);
2171    return;
2172 }
2173
2174 void AddressSpace::updateMemEmulator() {
2175    if (memEmulator_) memEmulator_->update();
2176 }
2177
2178 MemoryEmulator * AddressSpace::getMemEm() {
2179     return memEmulator_;
2180 }
2181
2182 void updateSrcListAndVisited(ParseAPI::Edge* e,
2183                              std::list<ParseAPI::Edge*>& srcList,
2184                              std::set<ParseAPI::Edge*>& visited)                             
2185 {
2186   if (visited.find(e) == visited.end()) {
2187     srcList.push_back(e);
2188     visited.insert(e);
2189   }
2190 }
2191                              
2192 // create stub edge set which is: all edges such that: 
2193 //     e->trg() in owBlocks and e->src() not in delBlocks, 
2194 //     in which case, choose stub from among e->src()->sources()
2195 std::map<func_instance*,vector<edgeStub> > 
2196 AddressSpace::getStubs(const std::list<block_instance *> &owBlocks,
2197                        const std::set<block_instance*> &delBlocks,
2198                        const std::list<func_instance*> &deadFuncs)
2199 {
2200     std::map<func_instance*,vector<edgeStub> > stubs;
2201     std::set<ParseAPI::Edge*> stubEdges;
2202     std::set<ParseAPI::Edge*> visited;
2203
2204     for (list<block_instance*>::const_iterator bit = owBlocks.begin();
2205          bit != owBlocks.end(); 
2206          bit++) 
2207     {
2208         // if the overwritten block is in a dead func, we won't find a stub
2209         bool inDeadFunc = false;
2210         set<func_instance*> bFuncs;
2211         (*bit)->getFuncs(std::inserter(bFuncs,bFuncs.end()));
2212         for (list<func_instance*>::const_iterator dfit = deadFuncs.begin();
2213              dfit != deadFuncs.end(); dfit++) 
2214         {
2215            if (bFuncs.end() != bFuncs.find(*dfit)) {
2216               inDeadFunc = true;
2217               break;
2218            }
2219         }
2220         if (inDeadFunc) {
2221            mal_printf("block [%lx %lx) is in a dead function, will not reparse\n", 
2222                       (*bit)->start(), (*bit)->end());
2223            continue;
2224         }
2225
2226         using namespace ParseAPI;
2227         bool foundStub = false;
2228         parse_block *curImgBlock = (*bit)->llb();
2229         Address base = (*bit)->start() - curImgBlock->firstInsnOffset();
2230         const Block::edgelist & sourceEdges = curImgBlock->sources();
2231
2232         // search for stubs in all functions containing the overwritten block
2233         for (set<func_instance*>::iterator fit = bFuncs.begin();
2234              !foundStub && fit != bFuncs.end();
2235              fit++)
2236         {
2237             // build "srcList" worklist
2238             SingleContext epred_((*fit)->ifunc(),true,true);
2239             //Intraproc epred(&epred_);
2240             std::list<ParseAPI::Edge*> srcList;
2241             std::for_each(boost::make_filter_iterator(epred_, sourceEdges.begin(), sourceEdges.end()),
2242                           boost::make_filter_iterator(epred_, sourceEdges.end(), sourceEdges.end()),
2243                           boost::bind(updateSrcListAndVisited,
2244                                       _1,
2245                                       boost::ref(srcList),
2246                                       boost::ref(visited)));
2247
2248
2249             // find all stub blocks for this edge
2250             for (list<ParseAPI::Edge*>::iterator eit = srcList.begin(); eit != srcList.end(); eit++) {
2251                 parse_block *isrc = (parse_block*)((*eit)->src());
2252                 block_instance *src = (*fit)->obj()->findBlockByEntry(base + isrc->start());
2253                 assert(src);
2254
2255                 if ( delBlocks.end() == delBlocks.find(src) ) {
2256                    if (stubEdges.find(*eit) == stubEdges.end()) {
2257                       edgeStub st(src, (*eit)->trg()->start() + base, (*eit)->type());
2258                       stubs[*fit].push_back(st);
2259                       foundStub = true;
2260                    }
2261                 } 
2262                 else {
2263                    const Block::edgelist &srcSrcs = isrc->sources();
2264                    std::for_each(boost::make_filter_iterator(epred_, srcSrcs.begin(), srcSrcs.end()),
2265                                  boost::make_filter_iterator(epred_, srcSrcs.end(), srcSrcs.end()),
2266                                  boost::bind(updateSrcListAndVisited,
2267                                              _1,
2268                                              boost::ref(srcList),
2269                                              boost::ref(visited)));
2270                    
2271
2272                 }
2273             }
2274         }
2275     }
2276     return stubs;
2277 }
2278
2279 /* PatchAPI Stuffs */
2280 void AddressSpace::initPatchAPI() {
2281    DynAddrSpace* addr_space = DynAddrSpace::create();
2282    assert(addr_space);
2283    
2284    mgr_ = PatchMgr::create(addr_space,
2285                            new DynInstrumenter,
2286                            new DynPointMaker);
2287    
2288    patcher_ = Patcher::create(mgr_);
2289    
2290    assert(mgr());
2291    mgr()->instrumenter()->callModMap().clear();
2292    mgr()->instrumenter()->funcRepMap().clear();
2293    mgr()->instrumenter()->funcWrapMap().clear();
2294 }
2295
2296 bool AddressSpace::patch(AddressSpace* as) {
2297    return as->patcher()->commit();
2298 }
2299
2300 void AddressSpace::addMappedObject(mapped_object* obj) {
2301   mapped_objects.push_back(obj);
2302   dynamic_cast<DynAddrSpace*>(mgr_->as())->loadLibrary(obj);
2303 }
2304
2305
2306 bool uninstrument(Dyninst::PatchAPI::Instance::Ptr inst) {
2307    instPoint *point = IPCONV(inst->point());
2308    bool ret = point->remove(inst);
2309    if (!ret) return false;
2310    point->markModified();
2311    return true;
2312
2313 }