Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / reloc-func.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31  
32 // $Id: reloc-func.C,v 1.41 2008/09/08 16:44:05 bernat Exp $
33
34
35
36 #include "common/h/Types.h"
37 #include "function.h"
38 #include "process.h"
39 #include "debug.h"
40 #include "codeRange.h"
41 #include "dyninstAPI/src/instPoint.h"
42 #include "dyninstAPI/src/multiTramp.h"
43 #if defined(cap_instruction_api)
44 #include "dyninstAPI/src/arch.h"
45 #include "instructionAPI/h/InstructionDecoder.h"
46 #include "instructionAPI/h/Instruction.h"
47 #else
48 #include "dyninstAPI/src/InstrucIter.h"
49 #endif
50 #include "dyninstAPI/src/mapped_object.h"
51 #include "dyninstAPI/src/patch.h"
52 class int_basicBlock;
53 class instruction;
54
55 // We'll also try to limit this to relocation-capable platforms
56 // in the Makefile. Just in case, though....
57 #if defined(cap_relocation)
58 #include "reloc-func.h"
59
60
61
62 // And happy fun time. Relocate a function: make a physical copy somewhere else
63 // in the address space that will execute as the original function did. 
64 // This creates a somewhat inefficient new version; relocation is done
65 // for correctness, not efficiency.
66
67 // Input: a list of things to change when we relocate the function.
68
69 // TODO: which version do we relocate? ;)
70
71 // 29.Nov.05 Okay, so things just got a little trickier. When relocating
72 // a function, co-owner functions (those that share blocks with this function)
73 // must also be relocated if we will overwrite any of the shared blocks.
74
75 bool int_function::relocationGenerate(pdvector<funcMod *> &mods,
76                                       int sourceVersion /* = 0 */,
77                                       pdvector< int_function *> &needReloc)
78 {
79     bool ret;
80
81     reloc_printf("%s[%d]: RELOCATION GENERATE FOR %s\n",
82                  FILE__, __LINE__, prettyName().c_str());
83
84 #if defined(os_aix)
85     // Once we've relocated once, we're good... there's a new function version
86     // near the heap. The code will blithely relocate a bazillion times, too. 
87     if (version() > 0)
88         return true;
89 #endif
90
91     // process this function (with mods)
92     ret = relocationGenerateInt(mods,sourceVersion,needReloc);
93
94     // process all functions in needReloc list -- functions that have
95     // been previously processed or actually relocated (installed and
96     // linked) must be skipped!
97
98     reloc_printf("%s[%d] after internal relocation generation, %d also need work\n",
99                  FILE__, __LINE__, needReloc.size());
100
101     for(unsigned i = 0; i < needReloc.size(); i++)
102     {
103         // if the function has previously been relocated (any stage,
104         // not just installed and linked), skip.
105       if(needReloc[i]->linkedVersion_ > 0) {
106         reloc_printf("Skipping dependant relocation of %s: function already relocated\n",
107                      needReloc[i]->prettyName().c_str());
108         needReloc[i] = needReloc.back();
109         needReloc.pop_back();
110         i--; // reprocess  
111       }
112 #if 0
113         else
114         {
115             reloc_printf("Forcing dependant relocation of %p\n",
116                          needReloc[i]);
117             // always version 0?
118             if (!needReloc[i]->relocationGenerateInt(needReloc[i]->enlargeMods(),
119                                                      0,needReloc))
120                 ret = false;
121         }
122 #endif
123     }
124
125     reloc_printf("%s[%d]: RELOCATION GENERATE FOR %s, returning %s, %d in needReloc\n",
126                  FILE__, __LINE__, prettyName().c_str(), ret ? "true" : "false", needReloc.size());
127
128
129     return ret;
130 }
131
132 Address int_function::allocRelocation(unsigned size_required)
133 {
134    // AIX: we try to target the data heap, since it's near instrumentation; 
135    // we can do big branches at the start of a function, but not within. 
136    // So amusingly, function relocation probably won't _enlarge_ the function,
137    // just pick it up and move it nearer instrumentation. Bring the mountain 
138    // to Mohammed, I guess.
139 #if defined(os_aix)
140    // Also, fork() instrumentation needs to go in data.
141    return proc()->inferiorMalloc(size_required, dataHeap);
142 #elif defined(arch_x86_64)
143    return proc()->inferiorMalloc(size_required, anyHeap, getAddress());
144 #else
145    // We're expandin'
146    return proc()->inferiorMalloc(size_required);
147 #endif
148 }
149
150 #if defined(cap_fixpoint_gen)
151 bool int_function::relocBlocks(Address baseInMutatee, 
152                                pdvector<bblInstance *> &newInstances)
153 {
154    pdvector<Address> addrs; //Parallel array to newInstances for storing current 
155                             // addresses of basic blocks as we compute them
156
157    Address curAddr = baseInMutatee;
158    for (unsigned i=0; i<newInstances.size(); i++) {
159      bblInstance *bbl = newInstances[i];
160      reloc_printf("Initial address of block 0x%lx set to 0x%lx\n", 
161                   bbl->block()->origInstance()->firstInsnAddr(),
162                   curAddr);
163      addrs.push_back(curAddr);
164      if (i < (newInstances.size() - 1))
165          curAddr += newInstances[i]->sizeRequired(newInstances[i+1]);
166      else
167          curAddr += newInstances[i]->sizeRequired(NULL);
168    }
169
170    for (;;) {
171       reloc_printf("Computing address for all blocks\n");
172       for (unsigned i=0; i<newInstances.size(); i++) {
173          bblInstance *bbl = newInstances[i];
174          bbl->setStartAddr(addrs[i]);
175       }
176
177       for (unsigned i=0; i<newInstances.size(); i++) {
178          bblInstance *bbl = newInstances[i];
179          reloc_printf("Fixpoint set block 0x%lx to 0x%lx (+%lu), generating...\n", 
180                       bbl->block()->origInstance()->firstInsnAddr(),
181                       addrs[i],
182                       addrs[i] - baseInMutatee);
183          if (i < (newInstances.size() - 1))
184              bbl->generate(newInstances[i+1]);
185          else
186              bbl->generate(NULL);
187          assert(!bbl->generatedBlock().hasPCRels());
188          reloc_printf("Block 0x%lx generation done.  Used %lu bytes\n",
189                       bbl->block()->origInstance()->firstInsnAddr(),
190                       bbl->generatedBlock().used());
191       }
192          
193       bool changeDetected = false;
194       for (unsigned i=0; i<newInstances.size(); i++) {
195          bblInstance *bbl = newInstances[i];
196
197          if (i+1 == newInstances.size()) {
198             //Size changes in the last block don't actually concern us
199             continue;
200          }
201
202          Address newBlockEndAddr = addrs[i] + bbl->getSize();
203          
204          if (newBlockEndAddr > addrs[i+1])
205          {
206             //Uh-Oh.  Rare, but possible.  We'd previously shrunk this block, but 
207             // the change in addresses (likely from previous blocks shrinking) caused 
208             // us to have to grow the block again.  This is likely if the block is 
209             // referencing an external object that isn't being relocated, and we were
210             // shrunk too far away from that object.
211             //We'll set the minSize of this block, so that we'll stop trying to shrink 
212             // this one.  If we didn't do this, the fixpoint could threoritically 
213             // infinite loop, as we could get into a scenario where we keep shrinking
214             // then growing this block.
215             bbl->minSize() = bbl->getSize();
216          }
217          if (newBlockEndAddr != addrs[i+1]) {
218             changeDetected = true;
219             reloc_printf("Fixpoint found block 0x%lx to be of size %u."
220                          "\n\tMoving block from %lx (+%lu) to %lx (+%lu).\n", 
221                          bbl->block()->origInstance()->firstInsnAddr(),
222                          bbl->getSize(),
223                          addrs[i+1],
224                          addrs[i+1] - baseInMutatee,
225                          newBlockEndAddr,
226                          newBlockEndAddr - baseInMutatee);
227             addrs[i+1] = newBlockEndAddr;
228          }
229       }
230       
231       if (!changeDetected) {
232          reloc_printf("Fixpoint concluded\n");
233          break;
234       }
235    }
236
237    return true;
238 }
239 #else
240 bool int_function::relocBlocks(Address baseInMutatee, 
241                                pdvector<bblInstance *> &newInstances)
242 {
243    Address currAddr = baseInMutatee;
244    // Inefficiency, part 1: we pin each block at a particular address
245    // so that we can one-pass generate and get jumps done correctly.
246    for (unsigned i = 0; i < newInstances.size(); i++) {
247       reloc_printf("Pinning block %d to 0x%lx\n", i, currAddr);
248       newInstances[i]->setStartAddr(currAddr);
249       if (i < (newInstances.size() - 1))
250           currAddr += newInstances[i]->sizeRequired(newInstances[i+1]);
251       else
252           currAddr += newInstances[i]->sizeRequired(NULL);
253    }
254
255    // Okay, so we have a set of "new" basicBlocks. Now go through and
256    // generate code for each; we can do branches appropriately, since
257    // we know where the targets will be.
258    // This builds the codeGen member of the bblInstance
259    bool success = true;
260    for (unsigned i = 0; i < newInstances.size(); i++) {
261       reloc_printf("... relocating block %d\n", blockList[i]->id());
262       // Hand in the physical successor block
263       if (i < (newInstances.size() - 1))
264           success &= newInstances[i]->generate(newInstances[i+1]);
265       else
266           success &= newInstances[i]->generate(NULL);
267       if (!success) break;
268    }
269    return true;
270 }
271 #endif
272
273 bool int_function::relocationGenerateInt(pdvector<funcMod *> &mods, 
274                                       int sourceVersion,
275                                       pdvector<int_function *> &needReloc) {
276     unsigned i;
277
278     if(!canBeRelocated()) {
279         return false;
280     }
281    
282     // If we call this function, we *probably* want to relocate whether
283     // or not we need to actually modify anything. 
284     //if (mods.size() == 0)
285     //    return true;
286
287     assert(sourceVersion <= version_);
288     if (generatedVersion_ > version_) {
289         // Odd case... we generated, but never installed or
290         // linked. Nuke the "dangling" version.
291         relocationInvalidate();
292     }
293
294     generatedVersion_++;
295
296
297     reloc_printf("Relocating function %s, version %d, 0x%lx, size: 0x%lx\n",
298                  symTabName().c_str(), sourceVersion,
299                  getAddress(), getSize_NP());
300
301     // Make sure the blocklist is created.
302     blocks(); 
303
304     // Make the basic block instances; they're placeholders for now.
305     pdvector<bblInstance *> newInstances;
306     for (i = 0; i < blockList.size(); i++) {
307         reloc_printf("Block %d, creating instance...\n", i);
308         bblInstance *newInstance = new bblInstance(blockList[i], generatedVersion_);
309         assert(newInstance);
310         newInstances.push_back(newInstance);
311         blockList[i]->instances_.push_back(newInstance);
312     }
313     assert(newInstances.size() == blockList.size());
314
315     // Whip through them and let people play with the sizes.
316     // We can also keep a tally of how much space we'll need while
317     // we're at it...
318     unsigned size_required = 0;
319     for (i = 0; i < newInstances.size(); i++) {
320         reloc_printf("Calling newInst:relocationSetup(%d)\n",
321                      sourceVersion);
322         newInstances[i]->relocationSetup(blockList[i]->instVer(sourceVersion),
323                                          mods);
324         if (i < (newInstances.size() - 1))
325             size_required += newInstances[i]->sizeRequired(newInstances[i+1]);
326         else
327             size_required += newInstances[i]->sizeRequired(NULL);
328
329         reloc_printf("After block %d, %d bytes required\n",
330                      i, size_required);
331     }
332
333     Address baseInMutatee = allocRelocation(size_required);
334     if (!baseInMutatee) return false;
335     reloc_printf("... new version at 0x%lx in mutatee\n", baseInMutatee);
336
337     bool success = relocBlocks(baseInMutatee, newInstances);
338     if (!success) {
339         relocationInvalidate();
340         return false;
341     }
342
343     // We use basicBlocks as labels.
344     // TODO Since there is only one entry block to any function and the
345     // image_function knows what it is, maybe it should be available at
346     // this level so we didn't have to do all this.
347     for (i = 0; i < blockList.size(); i++) {
348         if (!blockList[i]->needsJumpToNewVersion()) continue;
349         functionReplacement *funcRep = new functionReplacement(blockList[i], 
350                                                              blockList[i],
351                                                              sourceVersion,
352                                                              generatedVersion_);
353         if (funcRep->generateFuncRepJump(needReloc)) {            
354             blockList[i]->instVer(generatedVersion_)->jumpToBlock() = funcRep;
355         }
356         else {
357             // Try using traps...
358             // Fix this later; we might over-relocate things that we bled into
359             // before we decided a jump was bad news.
360             //needReloc.clear();
361             if (funcRep->generateFuncRepTrap(needReloc)) {
362                 blockList[i]->instVer(generatedVersion_)->jumpToBlock() = funcRep; 
363             }
364             else {
365                 relocationInvalidate();
366                 return false;
367             }
368         }
369     }
370     
371     return success;
372 }
373
374 bool int_function::relocationInstall() {
375
376     // Okay, we now have a new copy of the function. Go through 
377     // the version to be replaced, and replace each basic block
378     // with a "jump to new basic block" combo.
379     // If we overlap a bbl (which we probably will), oops.
380     unsigned i;
381
382     reloc_printf("%s[%d]: RELOCATION INSTALL FOR %s\n",
383                  FILE__, __LINE__, prettyName().c_str());
384
385     if (installedVersion_ == generatedVersion_) {
386         reloc_printf("%s[%d]: installedVersion_ %d == generatedVersion_ %d, returning\n",
387                 FILE__, __LINE__, installedVersion_, generatedVersion_);
388         return true; // Nothing to do here...
389     }
390
391     bool success = true;
392     for (i = 0; i < blockList.size(); i++) {
393         success &= blockList[i]->instVer(generatedVersion_)->install();
394         if (!success) break;
395         
396         // Add all the basicBlocks to the process data range...
397         proc()->addOrigRange(blockList[i]->instVer(generatedVersion_));
398         addBBLInstance(blockList[i]->instVer(generatedVersion_));
399     }
400     if (!success) {
401         fprintf(stderr, "Warning: installation of relocated function failed\n");
402         return false;
403     }
404
405     installedVersion_ = generatedVersion_;
406     version_ = installedVersion_;
407
408     return success;
409 }
410
411 bool int_function::relocationCheck(pdvector<Address> &checkPCs) {
412     unsigned i;
413
414     assert(generatedVersion_ == installedVersion_);
415
416     for (i = 0; i < blockList.size(); i++) {
417         if (!blockList[i]->instVer(installedVersion_)->check(checkPCs))
418             return false;
419     }
420     return true;
421 }
422         
423
424 bool int_function::relocationLink(pdvector<codeRange *> &overwritten_objs) {
425
426     unsigned i;
427
428     if (linkedVersion_ == installedVersion_) {
429         assert(linkedVersion_ == version_);
430         return true; // We're already done...
431     }
432
433     // If the assert fails, then we linked but did not
434     // update the global function version. That's _BAD_.
435
436     bool success = true;
437     for (i = 0; i < blockList.size(); i++) {
438         success &= blockList[i]->instVer(installedVersion_)->link(overwritten_objs);
439         if (!success)
440             break;
441     }
442     if (!success) {
443         // Uh oh...
444         fprintf(stderr, "ERROR: linking relocated function failed!\n");
445         assert(0);
446     }
447
448     linkedVersion_ = installedVersion_;
449     assert(linkedVersion_ == version_);
450
451     return true;
452 }
453
454 bool int_function::relocationInvalidate() {
455     unsigned i;
456     // The increase pattern goes like so:
457     // generatedVersion_++;
458     // installedVersion_++;
459     // version_++; -- so that instpoints will be updated
460     // linkedVersion_++;
461     reloc_printf("%s[%d]: relocationInvalidate for %s: linkedVersion %d, installedVersion %d, generatedVersion %d, version %d\n",
462                  FILE__, __LINE__, symTabName().c_str(), 
463                  linkedVersion_,
464                  installedVersion_,
465                  generatedVersion_,
466                  version_);
467
468     assert(generatedVersion_ >= installedVersion_);
469     assert(installedVersion_ >= version_);
470     assert(version_ >= linkedVersion_);
471
472     if (generatedVersion_ == linkedVersion_) {
473         reloc_printf("%s[%d]: nothing to do, returning\n",
474                      FILE__, __LINE__);
475         return true;
476     }
477
478     while (installedVersion_ > linkedVersion_) {
479         reloc_printf("******* Removing installed version %d\n",
480                      installedVersion_);
481         for (i = 0; i < blockList.size(); i++) {
482             reloc_printf("%s[%d]: Removing installed version %d of block %d\n",
483                          FILE__, __LINE__, installedVersion_, i);
484             bblInstance *instance = blockList[i]->instVer(installedVersion_);
485             assert(instance);
486             proc()->removeOrigRange(instance);
487             deleteBBLInstance(instance);
488             // Nuke any attached multiTramps...
489             multiTramp *multi = proc()->findMultiTrampByAddr(instance->firstInsnAddr());
490             if (multi)
491                 delete multi;
492         }
493         installedVersion_--;
494     }
495     
496     while (generatedVersion_ > installedVersion_) {
497         reloc_printf("******* Removing generated version %d\n",
498                      generatedVersion_);
499         proc()->inferiorFree(blockList[0]->instVer(generatedVersion_)->firstInsnAddr());
500         for (i = 0; i < blockList.size(); i++) {
501             reloc_printf("%s[%d]: Removing generated version %d of block %d\n",
502                          FILE__, __LINE__, generatedVersion_, i);
503             blockList[i]->removeVersion(generatedVersion_);
504         }
505         generatedVersion_--;
506     }
507     version_ = linkedVersion_;
508
509     reloc_printf("%s[%d]: version %d, linked %d, installed %d, generated %d\n",
510                  FILE__, __LINE__, version_, linkedVersion_, installedVersion_, generatedVersion_);
511     for (i = 0; i < blockList.size(); i++) {
512         reloc_printf("%s[%d]: block %d has %d versions\n",
513                      FILE__, __LINE__, i, blockList[i]->instances().size());
514     }
515
516     for (i = 0; i < entryPoints_.size(); i++)
517         entryPoints_[i]->updateInstances();
518     for (i = 0; i < exitPoints_.size(); i++)
519         exitPoints_[i]->updateInstances();
520     for (i = 0; i < callPoints_.size(); i++)
521         callPoints_[i]->updateInstances();
522     for (i = 0; i < arbitraryPoints_.size(); i++)
523         arbitraryPoints_[i]->updateInstances();
524
525     return true;
526 }
527
528 bool int_function::expandForInstrumentation() {
529     unsigned i;
530     // Take the most recent version of the function, check the instPoints
531     // registered. If one needs more room, create an expansion record.
532     // When we're done, relocate the function (most recent version only).
533
534     // Oh, only do that if there's instrumentation added at the point?
535     reloc_printf("Function expandForInstrumentation, version %d\n",
536                  version_);
537     // Right now I'm basing everything off version 0; that is, if we
538     // relocate multiple times, we will have discarded versions instead
539     // of a long chain. 
540
541     if (!canBeRelocated()) {
542         return false;
543     }
544
545     for (i = 0; i < blockList.size(); i++) {
546         bblInstance *bblI = blockList[i]->origInstance();
547         assert(bblI->block() == blockList[i]);
548         // Simplification: check if there's a multiTramp at the block.
549         // If there isn't, then we don't care.
550         multiTramp *multi = proc()->findMultiTrampByAddr(bblI->firstInsnAddr());
551         if (!multi) continue;
552         if (bblI->getSize() < multi->sizeDesired()) {
553             reloc_printf("Enlarging basic block %d; currently %d, %d bytes required; start addr 0x%lx\n",
554                          i, bblI->getSize(), multi->sizeDesired(), bblI->firstInsnAddr());
555             pdvector<bblInstance::reloc_info_t::relocInsn *> whocares;
556             bool found = false;
557             // Check to see if there's already a request for it...
558             for (unsigned j = 0; j < enlargeMods_.size(); j++) {
559                 if (enlargeMods_[j]->update(bblI->block(), 
560                                             whocares,
561                                             multi->sizeDesired())) {
562                     found = true;
563                     break;
564                 }
565             }
566             if (!found) {
567                 // Didn't find it...
568                 enlargeBlock *mod = new enlargeBlock(bblI->block(), multi->maxSizeRequired());
569                 enlargeMods_.push_back(mod);
570             }
571         }
572     }
573     return true;
574 }
575
576 // Return the absolute maximum size required to relocate this
577 // block somewhere else. If this looks very familiar, well, 
578 // _it is_. We should unify the instruction and relocatedInstruction
579 // classes.
580 // This is a bit inefficient, since we rapidly use and delete
581 // relocatedInstructions... ah, well :)
582 unsigned bblInstance::sizeRequired(bblInstance *nextBBL) {
583     assert(getMaxSize());
584
585     unsigned jumpToFallthrough = 0;
586     if (nextBBL &&
587         getFallthroughBBL() &&
588         (nextBBL != getFallthroughBBL())) {
589         jumpToFallthrough = instruction::maxJumpSize(proc()->getAddressWidth());
590     }
591
592     return getMaxSize() + jumpToFallthrough;
593 }
594
595 bool bblInstance::reset()
596 {
597   return true;
598 }
599
600 // Make a copy of the basic block (from the original provided),
601 // applying the modifications stated in the vector of funcMod
602 // objects.
603 bool bblInstance::relocationSetup(bblInstance *orig, pdvector<funcMod *> &mods) {
604    unsigned i;
605    origInstance() = orig;
606    assert(origInstance());
607    // First, build the insns vector
608
609    for (i = 0; i < relocs().size(); i++) {
610      delete relocs()[i];
611    }
612
613    relocs().clear();
614
615    // Keep a running count of how big things are...
616    maxSize() = 0;
617    minSize() = 0;
618 #if defined(cap_instruction_api)
619    using namespace Dyninst::InstructionAPI;
620    InstructionDecoder d;
621    d.setMode(orig->proc()->getAddressWidth() == 8);
622    unsigned char* buffer = reinterpret_cast<unsigned char*>(orig->proc()->getPtrToInstruction(orig->firstInsnAddr()));
623    
624    size_t offset = 0;
625    while(offset < orig->getSize())
626    {
627      Instruction::Ptr tmp = d.decode(buffer + offset);
628      
629      reloc_info_t::relocInsn *reloc = new reloc_info_t::relocInsn;
630
631      reloc->origAddr = orig->firstInsnAddr() + offset;
632      reloc->relocAddr = 0;
633      reloc->origInsn = new instruction;
634      reloc->origPtr = buffer + offset;
635      reloc->origInsn->setInstruction((const unsigned char*)reloc->origPtr, reloc->origAddr);
636      reloc->relocTarget = 0;
637      reloc->relocSize = 0;
638
639      relocs().push_back(reloc);
640
641      maxSize() += reloc->origInsn->spaceToRelocate();
642      offset += tmp->size();
643    }
644    
645   
646 #else
647    InstrucIter insnIter(orig);
648    while (insnIter.hasMore()) {
649      instruction *insnPtr = insnIter.getInsnPtr();
650      assert(insnPtr);
651      reloc_info_t::relocInsn *reloc = new reloc_info_t::relocInsn;
652
653      reloc->origAddr = *insnIter;
654      reloc->relocAddr = 0;
655      reloc->origInsn = insnPtr;
656      reloc->origPtr = insnPtr->ptr();
657      reloc->relocTarget = 0;
658      reloc->relocSize = 0;
659
660      relocs().push_back(reloc);
661
662      maxSize() += insnPtr->spaceToRelocate();
663      insnIter++;
664    }
665 #endif //defined(cap_instruction_api)
666
667    // Apply any hanging-around relocations from our previous instance
668    for (i = 0; i < orig->appliedMods().size(); i++) {
669       if (orig->appliedMods()[i]->modifyBBL(block_, relocs(), *this)) {
670          appliedMods().push_back(orig->appliedMods()[i]);
671       }
672     }
673
674     // So now we have a rough size and a list of insns. See if any of
675     // those mods want to play.
676     for (i = 0; i < mods.size(); i++) {
677         if (mods[i]->modifyBBL(block_, relocs(), *this)) {
678             // Store for possible further relocations.
679             appliedMods().push_back(mods[i]);
680         }
681     }
682
683     return true;
684 }
685
686 void bblInstance::setStartAddr(Address addr) {
687   firstInsnAddr_ = addr;
688 }
689
690 bool bblInstance::generate(bblInstance *nextBBL) {
691     assert(firstInsnAddr_);
692     assert(relocs().size());
693     assert(maxSize());
694     assert(block_);
695     assert(origInstance());
696     unsigned i;
697
698     unsigned fallthroughJumpSizeNeeded = 0;
699     if (nextBBL &&
700         getFallthroughBBL() &&
701         (nextBBL != getFallthroughBBL())) {
702         fallthroughJumpSizeNeeded = instruction::maxJumpSize(proc()->getAddressWidth());
703     }
704     
705
706     generatedBlock().allocate(maxSize() + fallthroughJumpSizeNeeded);
707     generatedBlock().setAddrSpace(proc());
708     generatedBlock().setAddr(firstInsnAddr_);
709     generatedBlock().setFunction(func());
710
711     Address origAddr = origInstance()->firstInsnAddr();
712     for (i = 0; i < relocs().size(); i++) {
713       Address currAddr = generatedBlock().currAddr(firstInsnAddr_);
714       relocs()[i]->relocAddr = currAddr;
715       patchTarget *fallthroughOverride = NULL;
716       patchTarget *targetOverride = NULL;
717       if (i == (relocs().size()-1)) {
718           targetOverride = getTargetBBL();
719       }
720       reloc_printf("... generating insn %d, orig addr 0x%lx, new addr 0x%lx, " 
721                    "fallthrough 0x%lx, target 0x%lx\n",
722                    i, origAddr, currAddr, 
723                    fallthroughOverride ? fallthroughOverride->get_address() : 0, 
724                    targetOverride ? targetOverride->get_address() : 0);
725       unsigned usedBefore = generatedBlock().used();
726
727       // Added 4APR08 to handle de-overlapping blocks; our fallthrough may
728       // not be the contextual successor...
729       bblInstance *fallthrough = getFallthroughBBL();
730       
731       if ((nextBBL != NULL) &&
732           (fallthrough != NULL) &&
733           (fallthrough != nextBBL)) {
734           reloc_printf("%s[%d]: Handling case where fallthrough is not next block; func %s, block at 0x%lx, fallthrough at 0x%lx, next block at 0x%lx\n",
735                        FILE__, __LINE__,
736                        func()->prettyName().c_str(),
737                        block()->origInstance()->firstInsnAddr(),
738                        fallthrough->origInstance()->firstInsnAddr(),
739                        nextBBL->origInstance()->firstInsnAddr());
740           fallthroughOverride = fallthrough;
741       }
742
743       relocs()[i]->origInsn->generate(generatedBlock(),
744                                       proc(),
745                                       origAddr,
746                                       currAddr,
747                                       fallthroughOverride,
748                                       targetOverride); // targetOverride
749       
750       relocs()[i]->relocTarget = targetOverride ? targetOverride->get_address() : 0;
751       
752       // And set the remaining bbl variables correctly
753       // This may be overwritten multiple times, but will end
754       // correct.
755       lastInsnAddr_ = currAddr;
756       
757       relocs()[i]->relocSize = generatedBlock().used() - usedBefore;
758       
759       origAddr += relocs()[i]->origInsn->size();
760     }
761
762
763 #if !defined(cap_fixpoint_gen)
764     //Fill out unused space at end of block with NOPs
765     generatedBlock().fillRemaining(codeGen::cgNOP);
766     blockEndAddr_ = firstInsnAddr_ + maxSize();
767 #else
768     //No unused space.  Only expand if we're under the minimum size
769     // (which only happens if the block is being expanded.
770     unsigned space_used = generatedBlock().used();
771     if (space_used < minSize())
772        generatedBlock().fill(minSize() - space_used, codeGen::cgNOP);
773     blockEndAddr_ = firstInsnAddr_ + generatedBlock().used();
774 #endif
775
776     relocs().back()->relocSize = blockEndAddr_ - lastInsnAddr_;
777     
778     // Post conditions
779     assert(firstInsnAddr_);
780     assert(lastInsnAddr_);
781     assert(blockEndAddr_);
782     
783     return true;
784 }
785
786 bool bblInstance::install() {
787     assert(firstInsnAddr_);
788     assert(generatedBlock() != NULL);
789     assert(maxSize());
790
791     reloc_printf("%s[%d]: Writing from 0x%lx 0x%lx to 0x%lx 0x%lx\n",
792                  FILE__, __LINE__,
793                  generatedBlock().start_ptr(), 
794                  (long) generatedBlock().start_ptr() + generatedBlock().used(),
795                  firstInsnAddr_,
796                  firstInsnAddr_ + generatedBlock().used());
797     
798     bool success = proc()->writeTextSpace((void *)firstInsnAddr_,
799                                           generatedBlock().used(),
800                                           generatedBlock().start_ptr());
801     if (success) {
802         return true;
803     }
804     else 
805         return false;
806 }
807
808 bool bblInstance::check(pdvector<Address> &checkPCs) {
809     if (!getJumpToBlock()) return true;
810     return jumpToBlock()->checkFuncRep(checkPCs);
811 }
812
813 bool bblInstance::link(pdvector<codeRange *> &overwrittenObjs) {
814     if (!getJumpToBlock()) return true;
815     return jumpToBlock()->linkFuncRep(overwrittenObjs);
816 }
817
818 bool enlargeBlock::modifyBBL(int_basicBlock *block,
819                              pdvector<bblInstance::reloc_info_t::relocInsn *> &,
820                              bblInstance &bbl)
821 {
822    if (block == targetBlock_) {
823       if (targetSize_ == (unsigned) -1) {
824          return true;
825       }
826       
827       if (bbl.maxSize() < targetSize_) {
828          bbl.maxSize() = targetSize_;
829       }
830       if (bbl.minSize() < targetSize_) {
831          bbl.minSize() = targetSize_;
832       }
833       
834       return true;
835    }
836    return false;
837 }
838
839 bool enlargeBlock::update(int_basicBlock *block,
840                           pdvector<bblInstance::reloc_info_t::relocInsn *> &,
841                           unsigned size) {
842     if (block == targetBlock_) {
843         if (size == (unsigned) -1) {
844             // Nothing we can do about it, we're just fudging...
845             return true;
846         }
847         targetSize_ = (targetSize_ > size) ? targetSize_ : size;
848         return true;
849     }
850     return false;
851 }
852
853
854 #endif // cap_relocation
855
856 functionReplacement::functionReplacement(int_basicBlock *sourceBlock,
857                                          int_basicBlock *targetBlock,
858                                          unsigned sourceVersion /* =0 */,
859                                          unsigned targetVersion /* =0 */) :
860     sourceBlock_(sourceBlock),
861     targetBlock_(targetBlock),
862     sourceVersion_(sourceVersion),
863     targetVersion_(targetVersion),
864     overwritesMultipleBlocks_(false),
865     usesTrap_(false)
866 {}
867     
868 Address functionReplacement::get_address() const {
869     assert(sourceBlock_);
870     return sourceBlock_->instVer(sourceVersion_)->firstInsnAddr();
871 }
872
873 unsigned functionReplacement::get_size() const {
874     if (jumpToRelocated != NULL)
875         return jumpToRelocated.used();
876     else
877         return 0;
878 }
879
880 // Will potentially append to needReloc (indicating that
881 // other functions must be relocated)
882 bool functionReplacement::generateFuncRepJump(pdvector<int_function *> &needReloc)
883 {
884     
885     assert(sourceBlock_);
886     assert(targetBlock_);
887     assert(jumpToRelocated == NULL);
888
889 #if !defined(cap_relocation)
890     assert(sourceVersion_ == 0);
891     assert(targetVersion_ == 0);
892 #endif
893
894     usesTrap_ = false;
895
896     // TODO: if check modules and do ToC if not the same one.
897
898     bblInstance *sourceInst = sourceBlock_->instVer(sourceVersion_);
899     assert(sourceInst);
900     bblInstance *targetInst = targetBlock_->instVer(targetVersion_);
901     assert(targetInst);
902
903     unsigned addr_width = proc()->getAddressWidth();
904     jumpToRelocated.allocate(instruction::maxInterFunctionJumpSize(addr_width));
905     jumpToRelocated.setAddrSpace(proc());
906     reloc_printf("******* generating interFunctionJump from 0x%lx (%d) to 0x%lx (%d)\n",
907                  sourceInst->firstInsnAddr(),
908                  sourceVersion_,
909                  targetInst->firstInsnAddr(),
910                  targetVersion_);
911
912     instruction::generateInterFunctionBranch(jumpToRelocated,
913                                              sourceInst->firstInsnAddr(),
914                                              targetInst->firstInsnAddr());
915
916     // Determine whether relocation of this function will force relocation
917     // of any other functions:
918     // If the inter-function jump will overwrite any shared blocks,
919     // the "co-owner" functions that are associated with those blocks
920     // must be relocated before the jump can be written.
921     //
922
923
924     if(sourceBlock_->hasSharedBase())
925     {
926         reloc_printf("%s[%d]: odd case, function with shared entry block\n",
927                      FILE__, __LINE__);
928
929         // if this entry block is shared...
930         sourceBlock_->func()->getSharingFuncs(sourceBlock_,
931                                               needReloc);
932     }
933
934     if (jumpToRelocated.used() > sourceInst->getSize()) {
935         // Okay, things are going to get ugly. There are two things we
936         // can't do:
937         // 1) Overwrite another entry point
938         // 2) Overwrite a different function
939         // So start seeing where this jump is going to run into...
940         
941         // FIXME there seems to be something fundamentally unsound about
942         // going ahead and installing instrumentation over the top of
943         // other functions! 
944         //
945         // And so, now, we don't.  Return false in this case, and in the
946         // case where we would normally write into unclaimed space.
947         //
948         unsigned overflow = jumpToRelocated.used() - sourceInst->getSize();
949         Address currAddr = sourceInst->endAddr();
950
951         while (overflow > 0) {
952             bblInstance *curInst = sourceBlock_->func()->findBlockInstanceByAddr(currAddr);
953             reloc_printf("%s[%d]: jump overflowed into block %p at 0x%lx\n", 
954                          FILE__, __LINE__, curInst, currAddr);
955             if (curInst) {
956                 // Okay, we've got another block in this function. Check
957                 // to see if it's shared.
958                 if (curInst->block()->hasSharedBase()) {
959                     reloc_printf("%s[%d]: block is shared, checking if it is an entry function\n",
960                                  FILE__, __LINE__);
961                   // This can get painful. If we're the entry block for another
962                   // function (e.g., __write_nocancel on Linux), we _really_ don't
963                   // want to be writing a jump here. So, check to see if the
964                   // internal block is an entry for a function that is _not_ us.
965                   image_func *possibleEntry = curInst->block()->llb()->getEntryFunc();
966
967                   if (possibleEntry && possibleEntry != sourceBlock_->func()->ifunc()) {
968                     // Yeah, this ain't gonna work
969                       reloc_printf("%s[%d]: Found function %s that shares with this block at 0x%lx, returning failure\n",
970                                    FILE__, __LINE__, possibleEntry->prettyName().c_str(), currAddr);
971                     return false;
972                   }
973
974                   // add functions to needReloc list
975                   curInst->block()->func()->getSharingFuncs(curInst->block(),
976                                                             needReloc);
977                 } 
978
979                 if (curInst->block()->needsJumpToNewVersion()) {
980                     reloc_printf("%s[%d]: Block needs jump to new version, failing\n",
981                                  FILE__, __LINE__);
982                     // Ooopsie... we're going to stop on another block
983                     // that jumps over. This we cannot do.
984                     return false;
985                 }
986
987                 // Otherwise keep going
988                 // Inefficient...
989                 currAddr = curInst->endAddr();
990                 if (curInst->getSize() > overflow)
991                     overflow = 0;
992                 else
993                     overflow -= curInst->getSize();
994             }
995             else {
996                 // Ummm... see if anyone else claimed this space.
997
998                 // NTS: we want any basic block that matches this address range
999                 // as part of any image in the proc(). hmmmm.... this means
1000                 // that the process needs to have knowledge of all
1001                 // int_basicBlocks.
1002                 int_basicBlock *block =
1003                         sourceBlock_->proc()->findBasicBlockByAddr(currAddr);
1004
1005                 if(block)
1006                 {
1007                     // Consistency check...
1008                     assert(block->func() != sourceBlock_->func());
1009                     return false;
1010                 }
1011                 else {
1012                     // Ummm... empty space.  Let's not try to write here.
1013                     return false;
1014                 }
1015             }
1016         }
1017         overwritesMultipleBlocks_ = true;
1018     }
1019
1020     return true;
1021 }
1022
1023 // Will potentially append to needReloc (indicating that
1024 // other functions must be relocated)
1025 bool functionReplacement::generateFuncRepTrap(pdvector<int_function *> &needReloc)
1026 {
1027     assert(sourceBlock_);
1028     assert(targetBlock_);
1029
1030     if (!proc()->canUseTraps())
1031         return false;
1032
1033     jumpToRelocated.invalidate();
1034
1035     assert(usesTrap_ == false);
1036
1037     usesTrap_ = true;
1038
1039 #if !defined(cap_relocation)
1040     assert(sourceVersion_ == 0);
1041     assert(targetVersion_ == 0);
1042 #endif
1043
1044     // TODO: if check modules and do ToC if not the same one.
1045
1046     bblInstance *sourceInst = sourceBlock_->instVer(sourceVersion_);
1047     assert(sourceInst);
1048     bblInstance *targetInst = targetBlock_->instVer(targetVersion_);
1049     assert(targetInst);
1050
1051     unsigned addr_width = proc()->getAddressWidth();
1052     jumpToRelocated.allocate(instruction::maxInterFunctionJumpSize(addr_width));
1053     reloc_printf("******* generating interFunctionTrap from 0x%lx (%d) to 0x%lx (%d)\n",
1054                  sourceInst->firstInsnAddr(),
1055                  sourceVersion_,
1056                  targetInst->firstInsnAddr(),
1057                  targetVersion_);
1058
1059     instruction::generateTrap(jumpToRelocated);
1060
1061     // Determine whether relocation of this function will force relocation
1062     // of any other functions:
1063     // If the inter-function jump will overwrite any shared blocks,
1064     // the "co-owner" functions that are associated with those blocks
1065     // must be relocated before the jump can be written.
1066     //
1067
1068
1069     if(sourceBlock_->hasSharedBase())
1070     {
1071         // if this entry block is shared...
1072         sourceBlock_->func()->getSharingFuncs(sourceBlock_,
1073                                               needReloc);
1074     }
1075
1076     return true;
1077 }
1078
1079 AddressSpace *functionReplacement::proc() const {
1080     assert(sourceBlock_);
1081     return sourceBlock_->proc();
1082 }
1083
1084 bool functionReplacement::installFuncRep() {
1085     // Nothing to do here unless we go to a springboard model.
1086
1087
1088     return true;
1089 }
1090
1091 // TODO: jumps that overwrite multiple basic blocks...
1092 bool functionReplacement::checkFuncRep(pdvector<Address> &checkPCs) {
1093     unsigned i;
1094
1095     Address start = get_address();
1096     Address end = get_address() + get_size();
1097     for (i = 0; i < checkPCs.size(); i++) {
1098         if ((checkPCs[i] > start) &&
1099             (checkPCs[i] < end))
1100             return false;
1101     }
1102     return true;
1103 }
1104
1105 bool functionReplacement::linkFuncRep(pdvector<codeRange *> &/*overwrittenObjs*/) {
1106     if (sourceBlock_->proc()->writeTextSpace((void *)get_address(),
1107                                              jumpToRelocated.used(),
1108                                              jumpToRelocated.start_ptr())) {
1109         sourceBlock_->proc()->addFuncReplacement(this); 
1110
1111         if (usesTrap_) {
1112             bblInstance *sourceInst = sourceBlock_->instVer(sourceVersion_);
1113             assert(sourceInst);
1114             bblInstance *targetInst = targetBlock_->instVer(targetVersion_);
1115             assert(targetInst);
1116
1117             AddressSpace *as = sourceBlock_->proc();
1118             as->trapMapping.addTrapMapping(sourceInst->firstInsnAddr(),
1119                                            targetInst->firstInsnAddr(),
1120                                            true);
1121         }       
1122
1123         return true;
1124     }
1125     else
1126         return false;
1127 }
1128
1129
1130 // If we're an entry block, we need a jump (to catch the
1131 // entry point). Also true if we are the target of an indirect jump.
1132
1133 bool int_basicBlock::needsJumpToNewVersion() {
1134     if (isEntryBlock())
1135         return true;
1136     
1137     assert(ib_);
1138     pdvector<int_basicBlock *> sources;
1139     getSources(sources);
1140     for (unsigned i = 0; i < sources.size(); i++) {
1141         if (getSourceEdgeType(sources[i]) == ET_INDIR)
1142             return true;
1143     }
1144     return false;
1145 }
1146     
1147