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