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 }