This commit enables arbitrary instrumentation points at the last instruction
[dyninst.git] / dyninstAPI / src / func-reloc.C
1 /*
2  * Copyright (c) 1996 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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 /*
43  * $Id: func-reloc.C,v 1.40 2003/03/13 17:00:14 jodom Exp $
44  */
45
46 #include "dyninstAPI/src/func-reloc.h"
47 #include "dyninstAPI/src/dyn_lwp.h"
48
49 extern bool isTrueCallInsn(const instruction insn);
50 extern bool isNearBranchInsn(const instruction insn);
51 extern void copyInstruction(instruction &newInsn, instruction &oldInsn,  
52                                                unsigned &codeOffset);
53
54 class LocalAlterationSet;
55 class LocalAlteration;
56
57 /****************************************************************************/
58 /****************************************************************************/
59
60 // update the target of relative branches (near jumps for x86) whose
61 // destination is outside the function
62
63 int pd_Function::fixRelocatedInstruction(bool setDisp, instruction *insn, 
64                                          Address origAddr, Address targetAddr) { 
65
66     int newDisp, disp, extra_bytes = 0;
67
68     // check for relative addressing       
69     if (isTrueCallInsn((const instruction) *insn) || 
70         isNearBranchInsn((const instruction) *insn)) {
71         
72         // get the original displacement
73         disp = get_disp(insn);
74
75         // calculate the new displacement 
76         newDisp = (origAddr + disp) - targetAddr;
77
78         // update displacement (if set_disp = true, extra_bytes should be 0).
79         // extra_bytes = # of extra bytes needed to update insn's displacement 
80         extra_bytes = set_disp(setDisp, insn, newDisp, true);
81
82 #ifdef DEBUG_FUNC_RELOC
83         cerr << "pd_Function::fixRelocatedInstruction:" << endl; 
84         cerr << " fixing displacement of insruction relocated" 
85              << " from " << hex << origAddr << endl; 
86         cerr << " to " << hex << targetAddr  
87              << " with setDisp " << setDisp << endl; 
88 #endif
89
90     }
91
92 #ifdef DEBUG_FUNC_RELOC 
93     cerr << " extra_bytes = " << extra_bytes << endl; 
94 #endif
95
96   return extra_bytes;
97 }
98
99 /****************************************************************************/
100 /****************************************************************************/
101
102 /* Platform independent */
103
104
105 // Fix displacement of relatvie branch or call instructions.
106 // Relative branches or calls with targets inside function will be updated by 
107 // patchOffset.
108 // Relative branches or calls with targets outside function will be updated by
109 // fixRelocatedInstruction
110
111 int pd_Function::relocateInstructionWithFunction(bool setDisp, 
112                                                  instruction *insn, 
113                                                  Address origAddr, 
114                                                  Address targetAddr, 
115                                                  Address oldFunctionAddr, 
116                                                  unsigned originalCodeSize) {
117
118   // check if insn is a relative branch with target inside function 
119   if (branchInsideRange(*insn, origAddr, oldFunctionAddr, \
120                           oldFunctionAddr + originalCodeSize)) {
121     return 0;
122   }
123   // check if insn is a relative call with target inside function 
124   if (trueCallInsideRange(*insn, origAddr, oldFunctionAddr, \
125                             oldFunctionAddr + size())) {
126     return 0;
127   }
128
129   return fixRelocatedInstruction(setDisp, insn, origAddr, targetAddr);
130 }
131
132 /****************************************************************************/
133 /****************************************************************************/
134
135 /* Platform independent */
136
137 // check insn is a branch with relative addressing and a target address 
138 // inside the function
139
140 bool pd_Function::branchInsideRange(instruction insn, Address branchAddress, 
141                                     Address firstAddress, Address lastAddress) {
142
143   int disp;
144   Address target;
145
146   // check if insn is a branch with relative addressing 
147   if (!isNearBranchInsn(insn)) return false;
148
149   // get the displacement of the target
150   disp = get_disp(&insn);
151
152   // get target of branch instruction
153 #if defined(i386_unknown_solaris2_5) || defined(i386_unknown_nt4_0) || defined(i386_unknown_linux2_0)
154   target = branchAddress + disp + insn.size();
155 #elif defined(sparc_sun_solaris2_4)
156   target = branchAddress + disp;
157 #endif
158
159   if (target < firstAddress) return false;
160   if (target >= lastAddress) return false;
161
162 #ifdef DEBUG_FUNC_RELOC 
163   cerr << "pd_Function::branchInsideRange:" << endl; 
164   cerr << " Instruction offset = " << branchAddress - firstAddress << endl; 
165   cerr << " function: " << hex << firstAddress << " to " 
166        << hex << lastAddress << endl;  
167   cerr << " branch target = " << hex << target - firstAddress << endl; 
168 #endif
169
170   return true;
171 }
172
173 /****************************************************************************/
174 /****************************************************************************/
175
176 /* Platform independent */
177
178 // check if insn is a call with relative addressing and a target address
179 // inside the function
180
181 bool pd_Function::trueCallInsideRange(instruction insn, Address callAddress, 
182                                       Address firstAddress, 
183                                       Address lastAddress) {
184
185   Address target;
186   int disp;
187   
188   // insn is a call instruction with relative addressing 
189   if (!isTrueCallInsn(insn)) return false;
190
191   // get the displacement of the target
192   disp = get_disp(&insn);
193    
194   // get target of call instruction
195 #if defined(i386_unknown_solaris2_5) || defined(i386_unknown_nt4_0) || defined(i386_unknown_linux2_0)
196   target = callAddress + disp + insn.size();
197 #elif defined(sparc_sun_solaris2_4)
198   target = callAddress + disp;
199 #endif
200
201   if (target < firstAddress) return false;
202   if (target >= lastAddress) return false;
203
204 #ifdef DEBUG_FUNC_RELOC 
205   cerr << "pd_Function::trueCallInsideRange:" << endl; 
206   cerr << " Instruction offset = " << callAddress - firstAddress << endl;
207   cerr << " function at: " << hex << firstAddress << " to "  << hex << lastAddress << endl;  
208
209   cerr << " call target = " << target - firstAddress << endl; 
210 #endif
211
212   return true;
213 }
214
215 /****************************************************************************/
216 /****************************************************************************/
217
218 /* Platform independent */
219
220 // if setDisp is true, update the displacement of the relative call or branch
221 // instructions if its target address is inside the function 
222 // Otherwise, calculate by how many bytes the insn needs to be expanded so
223 // that the branch or call target is within the instructions range
224
225 int pd_Function::patchOffset(bool setDisp, LocalAlterationSet *alteration_set, 
226                              instruction &insn, Address adr, 
227                              Address firstAddress, 
228                              unsigned originalCodeSize) {
229   
230   int disp, extra_offset, extra_bytes;
231   int lastAddress = firstAddress + originalCodeSize;
232   int insnSize = sizeOfMachineInsn(&insn);
233
234   // insn is a relative branch or call instruction with target inside function
235   if (!branchInsideRange(insn, adr, firstAddress, lastAddress) && 
236       !trueCallInsideRange(insn, adr, firstAddress, lastAddress)) return 0;
237
238   //  get the displacement of the instruction
239   disp = get_disp(&insn);
240  
241
242   // extra_offset: # of bytes that function expansion has further seperated 
243   // the address of the insn from its target address 
244   alteration_set->Collapse();
245   extra_offset = 
246          alteration_set->getShift((adr - firstAddress) + insnSize + disp) - 
247          alteration_set->getShift((adr - firstAddress)+ insnSize);
248
249   // (if set_disp = true, update the displacement, in which case 
250   // extra_bytes = 0).
251   // Otherwise extra_bytes = # of extra bytes needed to update insn's 
252   // displacement (which could be 0 as well) 
253   extra_bytes = set_disp(setDisp, &insn, disp + extra_offset, false);
254
255
256 #ifdef DEBUG_FUNC_RELOC 
257   cerr << "pd_Function::patchOffset" << endl;
258   cerr << " Instruction offset = " << adr - firstAddress << endl;
259   cerr << " function at: " << hex << firstAddress << " to " << hex << lastAddress << endl;   
260   cerr << " extra_bytes = " << extra_bytes << endl; 
261 #endif
262
263   return extra_bytes;
264 }
265
266
267 /****************************************************************************/
268 /****************************************************************************/
269
270 /* Plarform independent */
271
272 // return the # of bytes by which the function will be expanded, if it is
273 // relocated
274 int pd_Function::relocatedSizeChange(const image *owner, process *proc) {
275
276   instruction *oldInstructions = 0;
277   Address mutator, mutatee;
278   LocalAlterationSet normalized_alteration_set(this);
279
280   return findAlterations(owner, proc, oldInstructions, normalized_alteration_set, 
281                          mutator, mutatee);
282 }
283
284
285 /****************************************************************************/
286 /****************************************************************************/
287
288 /* Plarform independent */
289
290 // calculate the size and location of all alterations needed to relocate the 
291 // function. 
292 // normalized_alteration_set will contain the record of these changes
293 // Return the sum total of the sizes of the alterations
294
295 // oldInstructions: buffer of instruction objects
296 // mutatee: address of actual function to be relocated (located in the mutatee)
297 // mutator: address of copy of the above function  (located in the mutator)
298
299 int pd_Function::findAlterations(const image *owner, 
300                                  process *proc, 
301                                  instruction *&oldInstructions,
302                                  LocalAlterationSet &normalized_alteration_set,
303                                  Address &mutator, Address &mutatee) {
304
305 LocalAlterationSet temp_alteration_set(this);
306 Address baseAddress;
307 unsigned numberOfInstructions;
308 int totalSizeChange = 0;
309 bool relocate = true;
310 bool expanded = true;
311
312 #ifdef DEBUG_FUNC_RELOC
313     cerr << "pd_Function::findAlterations called " << endl;
314     cerr << " prettyName = " << prettyName().c_str() << endl;
315     cerr << " size() = " << size() << endl;
316     cerr << " this = " << *this << endl;
317 #endif
318
319   if (size() == 0) {
320     cerr << "WARN : attempting to relocate function " \
321          << prettyName().c_str() << " with size 0, unable to instrument" \
322          <<  endl;
323     return -1;
324   }
325
326   // get baseAddress if this is a shared object
327   baseAddress = 0;
328   if(!(proc->getBaseAddress(owner,baseAddress))){
329     baseAddress = 0;
330   }
331   // address of function (in mutatee) 
332   mutatee = baseAddress + getAddress(0);
333
334   // create a buffer of instruction objects 
335   if (!(loadCode(owner, proc, oldInstructions, numberOfInstructions, mutatee)))
336   {
337     return -1;  
338   }
339
340   // address of copy of function (in mutator)
341   mutator = addressOfMachineInsn(&oldInstructions[0]);
342
343 #ifdef DEBUG_FUNC_RELOC
344   cerr << " mutator = " << hex << mutator << endl;
345   cerr << " mutatee = " << hex << mutatee << endl;
346 #endif
347
348   // discover which instPoints need to be expaned  
349   expanded = expandInstPoints(owner, &temp_alteration_set, 
350                               normalized_alteration_set, 
351                               baseAddress, mutator, mutatee, 
352                               oldInstructions, 
353                               numberOfInstructions,
354                               proc); 
355
356   if (expanded) { 
357   // Check if the expansions discovered in expandInstPoints would require
358   // further expansion of the function (this occurs if the target of a 
359   // relative branch or call would be moved outside the range of the insn
360     relocate = updateAlterations(&temp_alteration_set, 
361                                  normalized_alteration_set, 
362                                  oldInstructions, baseAddress, 
363                                  mutatee, totalSizeChange); 
364   } else {
365     // Don't relocate
366     totalSizeChange = -1;
367   }
368
369   // Don't relocate
370   if (!relocate) totalSizeChange = -1;
371
372 #ifdef DEBUG_FUNC_RELOC
373     cerr << " totalSizeChange = " << totalSizeChange << endl;
374 #endif
375
376   return totalSizeChange;
377 }
378   
379   
380 /****************************************************************************/
381 /****************************************************************************/
382
383 /* Plarform independent */
384
385 // First expand the function, determining all LocalAlterations that need 
386 // to be applied, and then apply them, writing the rewritten function to
387 // the buffer relocatedCode
388
389 // newAdr: address in mutatee where function is to be relocated to
390 // reloc_info: info about relocated functions
391 // size_change: # bytes by which relocated function is larger than original
392
393 /* IMPORTANT: The function is not actually relocated in this method */
394
395 bool pd_Function::findAndApplyAlterations(const image *owner, 
396                                           instPoint *&location,
397                                           u_int &newAdr, 
398                                           process *proc, 
399                                           relocatedFuncInfo *&reloc_info, 
400                                           unsigned &size_change) {
401         
402   instruction *oldInstructions = 0, *newInstructions = 0;
403   Address mutator, mutatee;
404   int totalSizeChange = 0;
405   LocalAlterationSet normalized_alteration_set(this); 
406
407   // assumes delete NULL ptr safe....
408   oldInstructions = NULL;
409
410 #ifdef DEBUG_FUNC_RELOC
411     cerr << "pd_Function::findAndApplyAlterations called " << endl;
412     cerr << " prettyName = " << prettyName().c_str() << endl;
413     cerr << " size() = " << size() << endl;
414     cerr << " this = " << *this << endl;
415 #endif
416
417   // Find the alterations that need to be applied
418   totalSizeChange = findAlterations(owner, proc, oldInstructions,
419                                     normalized_alteration_set,
420                                     mutator, mutatee);  
421
422   if (totalSizeChange == -1) {
423
424     // Do not relocate function
425     delete []oldInstructions;
426     return false;
427   }
428
429
430 #ifdef DEBUG_FUNC_RELOC
431     cerr << " Allocate memory: " << size() + totalSizeChange << endl;
432 #endif
433
434     // Allocate the memory on the heap to which the function will be relocated
435     if(!reloc_info){  
436       Address ipAddr = 0;
437       proc->getBaseAddress(owner,ipAddr);
438       ipAddr += location->iPgetAddress();
439       u_int ret = proc->inferiorMalloc(size() + totalSizeChange, textHeap, ipAddr);
440       newAdr = ret;
441       if(!newAdr) {
442         delete []oldInstructions; 
443         return false;
444       }
445       reloc_info = new relocatedFuncInfo(proc,newAdr);
446       relocatedByProcess.push_back(reloc_info);
447     }
448
449     // Allocate the memory in paradyn to hold a copy of the rewritten function
450     relocatedCode = new unsigned char[size() + totalSizeChange];
451     if(!relocatedCode) {
452       cerr << "WARNING: Allocation of space for relocating function "
453            << prettyName() << " failed." << endl;
454        delete []oldInstructions;  
455        return false;
456     } 
457
458 #if defined(i386_unknown_solaris2_5) || defined(i386_unknown_nt4_0) || defined(i386_unknown_linux2_0)
459     // Upper bound on the number of instructions in the relocated function. 
460     // The original function has getNumInstructions instructions and so the
461     // relocated function has at least that many functions. At most, each byte
462     // added to the new function is an instruction, so the maximum number of 
463     // instructions in the new function is getNumInstructions + totalSizeChange
464     newInstructions = new instruction[getNumInstructions() + totalSizeChange];
465 #elif defined(sparc_sun_solaris2_4)
466     newInstructions = reinterpret_cast<instruction *> (relocatedCode);
467 #endif
468
469     // Apply the alterations needed for relocation. The expanded function 
470     // will be written to relocatedCode.
471     if (!(applyAlterations(normalized_alteration_set, mutator, mutatee, 
472                            newAdr, oldInstructions, size(), newInstructions) )) {
473       delete []oldInstructions;
474       return false;
475     }
476
477     // Fill reloc_info up with relocated (and altered by alterations) inst 
478     // points. Do AFTER all alterations are attached AND applied....
479     fillInRelocInstPoints(owner, proc, location, reloc_info, 
480                           mutatee, mutator, oldInstructions, newAdr, 
481                           newInstructions, normalized_alteration_set);
482     
483     size_change = totalSizeChange;  
484
485     delete []oldInstructions;
486     return true;
487 }
488
489 /****************************************************************************/
490 /****************************************************************************/
491
492 // Calulate which instPoints need to be expanded to allow for instrumentation  
493
494 // numberOfInstructions: # of insn's in function (as opposed to # of bytes)
495 // temp_alteration_set: record of the needed expansions 
496
497 bool pd_Function::expandInstPoints(const image *owner,
498                                LocalAlterationSet *temp_alteration_set, 
499                                LocalAlterationSet &normalized_alteration_set, 
500                                Address baseAddress, Address mutator,
501                                Address mutatee, instruction oldInstructions[], 
502                                unsigned num_instructions,
503                                process *proc) {
504
505   bool combined1, combined2, combined3, combined4, combined5;
506   bool attach1 = true, attach2 = true, attach3 = true, attach4 = true, attach5 = true;
507
508 #ifdef DEBUG_FUNC_RELOC
509     cerr << "pd_Function::expandInstPoints called "<< endl;
510     cerr << " baseAddress = " << hex << baseAddress << endl;
511     cerr << " mutator = " << hex << mutator << endl;
512     cerr << " mutatee = " << hex << mutatee << endl;
513     cerr << " numberOfInstructions = " << num_instructions << endl;
514 #endif
515
516   LocalAlterationSet tmp_alt_set1(this);
517   LocalAlterationSet tmp_alt_set2(this);
518   LocalAlterationSet tmp_alt_set3(this);
519   LocalAlterationSet tmp_alt_set4(this);
520
521   // Perform three passes looking for instPoints that need expansion
522
523   attach1 = PA_attachGeneralRewrites(owner, temp_alteration_set, baseAddress, 
524                            mutatee, oldInstructions, num_instructions, size());
525   attach2 = PA_attachOverlappingInstPoints(&tmp_alt_set1, baseAddress, 
526                            mutatee, oldInstructions, size());
527   attach3 = PA_attachBranchOverlaps(&tmp_alt_set2, baseAddress, mutator, 
528                            oldInstructions, num_instructions, size());
529 #if defined (sparc_sun_solaris2_4)
530   attach4 = PA_attachTailCalls(&tmp_alt_set3);
531   attach5 = PA_attachBasicBlockEndRewrites(&tmp_alt_set4, baseAddress, mutatee,
532                                            proc);
533 #endif
534
535   if (!attach1 || !attach2 || !attach3 || !attach4) {
536     return false;
537   }
538
539   // merge the LocalAlterations discovered in the above passes, placing
540   // them in normalized_alteration_set 
541
542   combined1 = combineAlterationSets(temp_alteration_set, &tmp_alt_set1);
543   combined2 = combineAlterationSets(temp_alteration_set, &tmp_alt_set2);
544   combined3 = combineAlterationSets(temp_alteration_set, &tmp_alt_set3);
545   combined4 = combineAlterationSets(temp_alteration_set, &tmp_alt_set4);
546   combined5 = combineAlterationSets(&normalized_alteration_set, temp_alteration_set);    
547
548   if (!combined1 || !combined2 || !combined3 || !combined4 || !combined5) {
549     return false;
550   }
551
552   return true;
553 }
554
555 /****************************************************************************/
556 /****************************************************************************/
557 /****************************************************************************/
558
559   /* Platform independent */
560
561 // Check if targetAddress (the target of a branch or call insn) 
562 // is in the footprint of an inst point. 
563
564 instPoint *pd_Function::find_overlap(pdvector<instPoint*> v, Address targetAddress) {
565
566 #ifdef DEBUG_FUNC_RELOC
567   cerr << " find_overlap:" 
568        << " of target address " << hex << targetAddress 
569        << " with an instrumentation point " << endl;
570 #endif
571     
572   for (unsigned u = 0; u < v.size(); u++) {
573     instPoint *i = v[u];
574      
575     if (targetAddress <= i->firstAddress()) {
576       return NULL;
577     }
578     if (targetAddress > i->firstAddress() && targetAddress < i->followingAddress()) {
579         return i;
580     }
581   }
582   return NULL;
583 }
584
585 /****************************************************************************/
586 /****************************************************************************/
587
588 /* Platform independent */
589
590 // Alterations needed to increase the range of relative branch and call 
591 // instructions, are located in this function. i.e. alterations may need
592 // to be applied if the target of a 2 byte jmp instruction is no longer 
593 // within 128 bytes of the insn, due to expanding other instPoints. To deal 
594 // with this, we expand the jmp instruciton into a 5 byte jump.
595
596 bool pd_Function::discoverAlterations(LocalAlterationSet *temp_alteration_set, 
597                                       LocalAlterationSet &norm_alt_set,
598                                       Address baseAddress, Address firstAddress, 
599                                       instruction code[], 
600                                       int codeSize) {
601
602   int oldOffset = 0, newOffset = 0, codeOffset = 0; 
603   int size_of_expansion1, size_of_expansion2;
604  
605   // set to true if a new LocalAlteration is discovered 
606   bool foundAlteration = false;  
607
608   LocalAlterationSet discover_alteration_set(this);
609
610 #ifdef DEBUG_FUNC_RELOC
611     cerr << "pd_Function::discoverAlterations called" <<endl;
612     cerr << " firstAddress = " << hex << firstAddress
613          << " codeSize = " << codeSize << endl;
614 #endif 
615
616   norm_alt_set.iterReset();  
617   norm_alt_set.Collapse(); 
618
619   // iterate over all instructions
620   while (oldOffset < codeSize) {
621
622 #ifdef DEBUG_FUNC_RELOC 
623       cerr << " oldOffset = " << oldOffset << endl;
624 #endif
625  
626     // # of bytes needed to expand instruction so that its target 
627     // is still within its range.
628     size_of_expansion1 = relocateInstructionWithFunction(
629                                      false, &code[codeOffset], 
630                                      baseAddress + firstAddress + oldOffset, 
631                                      baseAddress + firstAddress + newOffset, 
632                                      baseAddress + firstAddress, codeSize);
633
634     // if instruction needs to be expanded 
635     if (size_of_expansion1) {
636
637 #if defined(i386_unknown_solaris2_5) || defined(i386_unknown_nt4_0) || defined(i386_unknown_linux2_0)
638
639       // expansion was not already found
640       if (!alreadyExpanded(oldOffset, size_of_expansion1, &norm_alt_set)) {
641
642         // new LocalAlteration
643         ExpandInstruction *exp = new ExpandInstruction(this, oldOffset,       
644                                                        size_of_expansion1);
645         discover_alteration_set.AddAlteration(exp);
646         foundAlteration = true;
647
648 #ifdef DEBUG_FUNC_RELOC 
649           cerr << " ExpandInstruction alteration found " << endl;
650           cerr << "     offset: " << oldOffset << endl; 
651           cerr << "     size: " << size_of_expansion1 << endl;
652 #endif
653       }
654
655 #elif defined(sparc_sun_solaris2_4)
656         // Don't expand instruction on sparc. i.e. if the new branch target is 
657         // greater than 2^21 bytes away, don't relocate the function 
658         return false;
659 #endif
660
661     }
662
663     // # of bytes needed to expand instruction so that its target 
664     // is still within its range.
665     size_of_expansion2 = patchOffset(false, &norm_alt_set, 
666                                      code[codeOffset], 
667                                      firstAddress + oldOffset, 
668                                      firstAddress, codeSize);
669
670
671     // if instruction needs to be expanded      
672     if (size_of_expansion2) {
673       // insn target is either inside reange of function or outside range
674       // of function, not both
675       assert(!size_of_expansion1);
676
677 #if defined(i386_unknown_solaris2_5) || defined(i386_unknown_nt4_0) || defined(i386_unknown_linux2_0)
678
679       // expansion was not already found
680       if (!alreadyExpanded(oldOffset, size_of_expansion2, &norm_alt_set)) {
681
682         // new LocalAlteration
683         ExpandInstruction *exp = new ExpandInstruction(this, oldOffset, 
684                                                          size_of_expansion2);
685         discover_alteration_set.AddAlteration(exp);
686         foundAlteration = true;        
687
688 #ifdef DEBUG_FUNC_RELOC 
689           cerr << " ExpandInstruction alteration found " << endl;
690           cerr << "     offset: " << oldOffset << endl; 
691           cerr << "     size: " << size_of_expansion2 << endl;
692 #endif
693       }
694
695 #elif defined(sparc_sun_solaris2_4)
696         // Don't expand instruction on sparc. i.e. if the new branch target is 
697         // greater than 2^21 bytes away, don't relocate the function 
698         return false;
699 #endif
700
701     }
702
703     // next intsruction
704     oldOffset += sizeOfMachineInsn(&code[codeOffset]);
705     newOffset += sizeOfMachineInsn(&code[codeOffset]); 
706
707     codeOffset++;      
708   }
709
710   // If any new LocalAlterations were found, pass them out of this function 
711   // through temp_alteration_set
712   discover_alteration_set.Collapse();
713
714   if (foundAlteration) *temp_alteration_set = discover_alteration_set;
715
716   return true;
717 }
718 /****************************************************************************/
719 /****************************************************************************/
720
721     /* Platform independent */
722
723 // place an expanded copy of the original function in relocatedCode 
724
725 // mutatee: first address of function in mutatee
726 // mutator: first address of copy of function in mutator
727 // newAdr: address in mutatee where function is to be relocated to
728 // codeSize: size of original, unexpanded function
729 // oldInstructions: buffer of insn's corresponding to copy of function in mutator
730 // newInstructions: buffer of insn's corresponding to expanded function located
731 //          in temporary buffer in mutator
732
733 bool pd_Function::applyAlterations(LocalAlterationSet &norm_alt_set,
734                                    Address mutator, Address mutatee, 
735                                    Address newAdr, 
736                                    instruction oldInstructions[], 
737                                    unsigned codeSize, 
738                                    instruction newInstructions[]) {
739
740   // offset of current insn from beginning of original function  
741   Address oldOffset = 0;
742   // offset of current insn from beginning of expanded function
743   Address  newOffset = 0;
744   // next alteration
745   LocalAlteration *nextAlter = 0; 
746   // address at which next alteration begins 
747   Address nextAlterBegins;
748
749   // offset of current insn into buffer of instructon objects 
750   // (oldInstructions and newInstructions respectively)
751   int oldInsnOffset = 0, newInsnOffset = 0;
752
753   int newDisp = 0;
754
755   // offset into buffer for rerwitten function
756   unsigned codeOffset = 0;
757
758   Address oldAdr_before, oldAdr_after, newAdr_before, newAdr_after; 
759
760 #ifdef DEBUG_FUNC_RELOC
761     cerr << "pd_Function::applyAlterations called" <<endl;
762     cerr << " mutator = " << hex << mutator << endl;
763     cerr << " mutatee = " << hex << mutatee << endl;
764     cerr << " newAdr = " << hex << newAdr << endl;
765     cerr << " codeSize = " << codeSize << endl;
766 #endif 
767
768   norm_alt_set.iterReset();  
769   norm_alt_set.Collapse(); 
770
771   // iterate over all instructions in function....
772   while (oldOffset < codeSize) {
773
774     // next alteration
775     nextAlter = norm_alt_set.iterNext();
776   
777     if (nextAlter == NULL) {
778       // no more alterations 
779       nextAlterBegins = codeSize;
780     } else {
781         // offset at which next alteration begins
782         nextAlterBegins = nextAlter->getOffset();
783     }
784
785     // iterate over all instructions before the next alteration, 
786     while (oldOffset < nextAlterBegins) {
787
788 #ifdef DEBUG_FUNC_RELOC 
789       cerr << " oldOffset = " << oldOffset << endl;
790       cerr << " nextAlterBegins = " << nextAlterBegins << endl;
791 #endif
792          
793       // copy current instruction into temporary buffer in mutator
794       copyInstruction(newInstructions[newInsnOffset], oldInstructions[oldInsnOffset], 
795                                                           codeOffset);
796     
797       // mutatee + oldOffset = address in mutatee of current instruction
798       // newAdr + newOffset = address in mutatee where current instruction is
799       // to be relocated
800       // update relative branches and calls to locations outside the function 
801       relocateInstructionWithFunction(true,&newInstructions[newInsnOffset], 
802                                       mutatee + oldOffset, newAdr + newOffset,
803                                       mutatee, codeSize);
804
805       // mutatee + oldOffset = address in mutatee of current instruction
806       // newInstructions[newInsnOffset] = insn in temporary buffer to be patched up
807       // update relative branches and calls to locations inside the function
808       patchOffset(true, &norm_alt_set, newInstructions[newInsnOffset], 
809                   mutator + oldOffset, mutator, codeSize);
810
811       // next instruction
812       oldOffset += sizeOfMachineInsn(&oldInstructions[oldInsnOffset]);
813       newOffset += sizeOfMachineInsn(&oldInstructions[oldInsnOffset]);
814       oldInsnOffset++; 
815       newInsnOffset++;
816     }
817
818
819     if (oldOffset != nextAlterBegins) {
820       cerr << "ERORR: non-matching alterations."<< endl;
821       cerr << "  oldOffset = " << oldOffset << endl;
822       cerr << "  nextAlterBegins = " << nextAlterBegins << endl;
823     }
824
825     assert(oldOffset == nextAlterBegins);
826   
827     // next alteration to be applied
828     if (nextAlter != NULL) {
829
830       // branch or call instruction with relative addressing
831       if(isNearBranchInsn(oldInstructions[oldInsnOffset])  || 
832          isTrueCallInsn(oldInstructions[oldInsnOffset])) {
833         int oldDisp = get_disp(&oldInstructions[oldInsnOffset]);
834         int oldInsnSize = sizeOfMachineInsn(&oldInstructions[oldInsnOffset]);  
835
836         // mutator + oldOffset = address in mutator of current instruction
837         // mutator + codeSize = last address of copy of function in mutator
838         if ((branchInsideRange(oldInstructions[oldInsnOffset], mutator + oldOffset, 
839                                mutator, mutator + codeSize))   ||
840             (trueCallInsideRange(oldInstructions[oldInsnOffset], mutator + oldOffset, 
841                                  mutator, mutator + codeSize))) {
842
843           // updated disp for relative branch or call insn to target 
844           // inside function
845           newDisp = oldDisp + (norm_alt_set.getShift(oldOffset + oldInsnSize +
846                                oldDisp) - norm_alt_set.getShift(oldOffset + oldInsnSize));
847
848         } else {
849
850             // updated disp for relative branch or call insn to target 
851             // outside function
852 #if defined(i386_unknown_solaris2_5) || defined(i386_unknown_nt4_0) || defined(i386_unknown_linux2_0)
853             int origAddr = (mutatee + oldOffset + oldInsnSize + oldDisp);
854             int targetAddr = (newAdr + newOffset + oldInsnSize + 
855                     set_disp(false, &oldInstructions[oldInsnOffset], newDisp, true));
856 #elif defined(sparc_sun_solaris2_4)
857             int origAddr = (mutatee + oldOffset + oldDisp);
858             int targetAddr = (newAdr + newOffset + 
859                     set_disp(false, &oldInstructions[oldInsnOffset], newDisp, true));
860 #elif defined(ia64_unknown_linux2_4)
861             /* Hopefully, my guesses will never be used, since the IA-64 doesn't _do_
862                function relocation. */
863             int origAddr = (mutatee + oldOffset + oldDisp);
864             int targetAddr = (newAdr + newOffset + 
865                     set_disp(false, &oldInstructions[oldInsnOffset], newDisp, true));
866 #endif
867
868             newDisp = origAddr - targetAddr;
869         } 
870
871 #ifdef DEBUG_FUNC_RELOC 
872       cerr << " newDisp " << newDisp << " oldDisp " << oldDisp << endl;
873 #endif
874
875       }
876
877       // RewriteFootprint makes the appropriate alterations to the  
878       // function at the instruction specified by the instPoint. 
879       // Unfortunately RewriteFootprint may change the offset values, 
880       // so we have to make sure we fix any altered values
881       // 
882
883       // oldAdr_before: address of current insn in mutatee  
884       // oldAdr_after: address of next instruction to be dealt with
885       //                (in mutatee), after alteration has been applied
886
887       // newAdr_before: address where current insn will be relocated to   
888       // newAdr_after: address where next instruction will be relocated to 
889
890       // oldInstructions: buffer of old insn objects
891       // newInstructions: buffer of new insn objects being made
892       // oldInsnOffset: offset of instruction object (in oldInstructions) 
893       //                corresponding to current insn
894       // newInsnOffset: offset of instruction object (in newInstructions) 
895       //                corresponding to current insn
896
897       oldAdr_after = oldAdr_before = mutatee + oldOffset;
898       newAdr_after = newAdr_before = newAdr + newOffset;
899
900       nextAlter->RewriteFootprint(mutatee, oldAdr_after, 
901                                   newAdr, newAdr_after, 
902                                   oldInstructions, newInstructions, 
903                                   oldInsnOffset, newInsnOffset, newDisp, 
904                                   codeOffset, relocatedCode);
905
906       // update offsets by the # of bytes RewriteFootprint walked over
907       oldOffset += (oldAdr_after - oldAdr_before);
908       newOffset += (newAdr_after - newAdr_before);
909     }
910   } 
911   
912   return true;
913 }
914
915 /****************************************************************************/
916 /****************************************************************************/
917
918 /****************************************************************************/
919 /****************************************************************************/
920
921 /* Platform independent */
922
923 // Combine two LocalAlterationSets, making sure the LocalAlterations
924 // remain in order from smallest to largest offset.
925 bool combineAlterationSets(LocalAlterationSet *combined_alteration_set, 
926                           LocalAlterationSet *alteration_set) {
927
928   assert (combined_alteration_set != NULL);
929   assert (alteration_set != NULL);
930
931   LocalAlterationSet temp_alteration_set;
932   temp_alteration_set = *combined_alteration_set;
933   combined_alteration_set->Flush();
934
935 #ifdef DEBUG_FUNC_RELOC 
936   cerr << "pd_Function::combineAlterationSets " << endl;
937 #endif
938
939   alteration_set->iterReset();  
940   LocalAlteration *alteration = alteration_set->iterNext(); 
941   
942   temp_alteration_set.iterReset();
943   LocalAlteration *tempAlteration = temp_alteration_set.iterNext();
944  
945   // While there are still LocalAlterations
946   while (tempAlteration != NULL || alteration != NULL) { 
947
948     // if alteration is NULL or tempAlteration has the smaller offset
949     if ((alteration == NULL) || ((tempAlteration != NULL) && 
950          alteration->getOffset() > tempAlteration->getOffset())) {
951
952       // tempAlteration is the next LocalAlteration to be added (     
953       combined_alteration_set->AddAlteration(tempAlteration);
954       tempAlteration = temp_alteration_set.iterNext();     
955     } else {
956         if ((tempAlteration == NULL) || 
957              alteration->getOffset() < tempAlteration->getOffset()) { 
958
959           // alteration is the next LocalAlteration to be added
960           combined_alteration_set->AddAlteration(alteration);
961           alteration = alteration_set->iterNext();
962         } else {
963
964             assert (alteration->getOffset() == tempAlteration->getOffset());
965
966             // reconcile the conflict of overlapping LocalAlterations
967             alteration = fixOverlappingAlterations(alteration, tempAlteration);
968   
969             if (alteration == NULL) return false;
970             
971             combined_alteration_set->AddAlteration(alteration);
972   
973             alteration = alteration_set->iterNext();
974             tempAlteration = temp_alteration_set.iterNext();
975         }
976     }      
977   }
978   combined_alteration_set->iterReset();  
979   combined_alteration_set->Collapse(); 
980   return true;
981 }
982
983 /****************************************************************************/
984 /****************************************************************************/
985
986 // find out if previous LocalAlterations have expanded the function in such
987 // a way as to require new LocalAlterations to be added.
988
989 bool pd_Function::updateAlterations(LocalAlterationSet *temp_alteration_set,
990                                     LocalAlterationSet &normalized_alteration_set,
991                                     instruction *oldInstructions, 
992                                     Address baseAddress,
993                                     Address firstAddress,
994                                     int &totalSizeChange) { 
995
996   // false if discoverAlterations failed
997   bool relocate = true;
998   bool combined = true;
999   assert (temp_alteration_set != NULL);
1000
1001   temp_alteration_set->iterReset();
1002   LocalAlteration *iterator = temp_alteration_set->iterNext();
1003
1004 #ifdef DEBUG_FUNC_RELOC 
1005   cerr << " updateAlterations: " << endl;
1006   cerr << " address of process " << hex << baseAddress << endl;
1007   cerr << " address of function being relocated" << hex << firstAddress << endl;
1008   cerr << " bytes of expansion of function " << totalSizeChange << endl; 
1009 #endif
1010
1011   // while discoverAlterations discovers new LocalAlterations
1012   for (int i = 0; iterator != NULL && i < 2 ; i++) {
1013     
1014     // normalized_alteration_set already contains 
1015     // temp_alteration_set is already normalized the first time through
1016     if (i != 0) {   
1017       
1018       // merge normalized_alteration_set and temp_alteration_set
1019       combined = combineAlterationSets(&normalized_alteration_set, temp_alteration_set);
1020  
1021       if (!combined) return false;
1022     }
1023
1024     temp_alteration_set->Flush();
1025
1026     // find new alterations that have come about, due to the expansion 
1027     // of the function. e.g. ExpandInstruction LocalAlterations 
1028     relocate = discoverAlterations(temp_alteration_set, normalized_alteration_set, 
1029                                      baseAddress, firstAddress, oldInstructions, size());
1030  
1031     // Don't relocate the function
1032     if (!relocate) return false;
1033
1034     temp_alteration_set->iterReset();
1035
1036     // NULL if no new alterations were found
1037     iterator = temp_alteration_set->iterNext();
1038   }
1039
1040   totalSizeChange = normalized_alteration_set.sizeChange();  
1041
1042 #ifdef DEBUG_FUNC_RELOC 
1043   cerr << " Number of bytes of expansion = " << totalSizeChange << endl;  
1044 #endif
1045
1046   return true;
1047
1048
1049 /****************************************************************************/
1050 /****************************************************************************/
1051
1052 // Function relocation requires a version of process::convertPCsToFuncs 
1053 // in which null functions are not passed into ret. - Itai 
1054 pdvector<pd_Function *> process::pcsToFuncs(pdvector<Frame> stackWalk) {
1055     pdvector <pd_Function *> ret;
1056     unsigned i;
1057     pd_Function *fn;
1058     for(i=0;i<stackWalk.size();i++) {
1059         fn = (pd_Function *)findFuncByAddr(stackWalk[i].getPC());
1060         // no reason to add a null function to ret
1061         if (fn != 0) ret.push_back(fn);
1062     }
1063     return ret;
1064 }
1065
1066 /****************************************************************************/
1067 /****************************************************************************/
1068
1069 /* Platform independent */
1070
1071 // Relocate "this" function
1072
1073 bool pd_Function::relocateFunction(process *proc, 
1074                                    instPoint *&location,
1075                                    bool &deferred) {
1076
1077     relocatedFuncInfo *reloc_info = 0;
1078
1079     // silence compiler warnings
1080     assert(deferred || true);
1081
1082     // how many bytes the function was expanded by
1083     unsigned size_change;
1084
1085 #ifdef DEBUG_FUNC_RELOC 
1086     cerr << "pd_Function::relocateFunction " << endl;
1087     cerr << " prettyName = " << prettyName().c_str() << endl;
1088     cerr << " size() = " << size() << endl;
1089     cerr << " this = " << *this << endl;
1090 #endif
1091
1092 #ifdef BPATCH_LIBRARY
1093     if (BPatch::bpatch->autoRelocationOn() == false) {
1094       BPatch_reportError(BPatchSerious, 125,
1095                          "Function required relocation but auto-relocation disabled.\n");
1096       return false;
1097     }
1098 #endif
1099
1100
1101     // check if this process already has a relocation record for this 
1102     // function, meaning that the.function has already been relocated
1103     for(u_int j=0; j < relocatedByProcess.size(); j++){
1104         if((relocatedByProcess[j])->getProcess() == proc){        
1105             reloc_info = relocatedByProcess[j];
1106             
1107 #ifdef DEBUG_FUNC_RELOC
1108             cerr << "pd_Function::relocateFunction " << endl;
1109             cerr << " prettyName = " << prettyName().c_str() << endl;      
1110             cerr << " previously relocated." << endl; 
1111 #endif
1112         }
1113     }
1114
1115    
1116   /* Check if we are currently executing inside the function we want to */ 
1117   /* instrument. If so, don't relocate the function.                    */
1118   /* this code was copied from metricFocusNode::adjustManuallyTrigger() */
1119   /* in metric.C -itai                                                  */
1120
1121 #if defined(i386_unknown_nt4_0) || defined(i386_unknown_linux2_0)
1122     unsigned i;
1123     pd_Function *stack_func;
1124
1125     pdvector<pdvector<Frame> > stackWalks;
1126     if (!proc->walkStacks(stackWalks)) return false;
1127
1128     for (unsigned walk_iter = 0; walk_iter < stackWalks.size(); walk_iter++) {
1129       pdvector<pd_Function *> stack_funcs = proc->pcsToFuncs(stackWalks[walk_iter]);
1130       for(i=0;i<stack_funcs.size();i++) {
1131         stack_func = stack_funcs[i];
1132         
1133         if (i == 0 && (stackWalks[walk_iter][i].getPC() == this->getEffectiveAddress(proc))) {
1134           /* okay if we haven't really entered the function yet */
1135           continue;
1136         }
1137         
1138         if( stack_func == this ) {
1139           
1140 #ifdef DEBUG_FUNC_RELOC
1141           cerr << "pd_Function::relocateFunction" << endl;
1142           cerr << "currently in Function " << prettyName() << endl;
1143 #endif
1144           
1145           // Defer relocation and instrumentation for Paradyn only
1146           deferred = true;
1147           return false;
1148         }
1149       }
1150     }
1151 #endif
1152
1153     /* We are not currently executing in this function, 
1154        so proceed with the relocation */
1155     
1156     Address baseAddress = 0;
1157     if(!(proc->getBaseAddress(location->iPgetOwner(),baseAddress))){
1158       baseAddress = 0;
1159     }
1160     
1161     // original address of function (before relocation)
1162     u_int origAddress = baseAddress + getAddress(0);    
1163     
1164  
1165     // address to which function will be relocated.
1166     // memory is not allocated until total size change of function is known
1167     u_int ret = 0;
1168
1169     if (!reloc_info) {
1170       // findAndApplyAlterations expands and updates the function, 
1171       // storing the expanded function with relocated addresses in 
1172       // the buffer relocatedCode.
1173       if (findAndApplyAlterations(location->iPgetOwner(), location, ret, proc, 
1174                                   reloc_info, size_change)) {
1175
1176         // Copy the expanded and updated function into the mutatee's 
1177         // address space
1178         proc->writeDataSpace((caddr_t)ret, size() + size_change,
1179                              relocatedCode);
1180
1181
1182
1183
1184         // branch from original function to relocated function
1185 #if defined(sparc_sun_solaris2_4)
1186         extern void generateBranchOrCall(process* , Address , Address);
1187         generateBranchOrCall(proc, origAddress, ret);
1188 #else
1189         generateBranch(proc, origAddress, ret);
1190 #endif
1191         reloc_info->setInstalled();
1192
1193 #ifdef DEBUG_FUNC_RELOC
1194         cerr << "pd_Function::relocateFunction " << endl;
1195         cerr << " prettyName = " << prettyName().c_str() << endl;      
1196         cerr << " relocated from 0x" << hex << origAddress
1197              << " with size 0x" << size() << endl;
1198         cerr << " to 0x" << hex << ret 
1199              << " with size 0x" << size()+size_change << endl;
1200         cerr << " copy original code at " << &originalCode << endl;
1201         cerr << " copy relocated code at " << &relocatedCode << endl;
1202 #endif
1203
1204       } else {
1205
1206 #ifdef DEBUG_FUNC_RELOC
1207         cerr << "Warning: Unable to relocate function"
1208              << prettyName() << endl;
1209 #endif
1210           return false;
1211       }
1212
1213       return true;
1214     }
1215     return false;
1216 }
1217
1218 /****************************************************************************/
1219 /****************************************************************************/
1220
1221 // 32 bit addresses
1222 #ifndef MAX_ADDRESS
1223 #define MAX_ADDRESS 0xffffffff;
1224 #endif
1225
1226 // Fill up vector with instPoints and then sort it 
1227
1228 void pd_Function::sorted_ips_vector(pdvector<instPoint*>&fill_in) {
1229     unsigned int returns_idx, calls_idx;
1230     Address returns_ip_addr, calls_ip_addr;
1231
1232     // sorted vector of inst points starts with funcEntry_  ....
1233     fill_in.push_back(funcEntry_);
1234
1235     returns_idx = calls_idx = 0;
1236
1237     // step through funcReturns and calls, popping element off of each and
1238     // looking at insnAddress() to see which one to stick onto fill_in next...
1239     while (returns_idx < funcReturns.size() || calls_idx < calls.size()) {
1240         if (returns_idx < funcReturns.size()) {
1241             returns_ip_addr = funcReturns[returns_idx]->insnAddress();
1242         } else {
1243             returns_ip_addr = MAX_ADDRESS;
1244         }
1245         
1246         if (calls_idx < calls.size()) {
1247             calls_ip_addr = calls[calls_idx]->insnAddress();
1248         } else {
1249             calls_ip_addr = MAX_ADDRESS;
1250         }
1251
1252         // 2 inst points at same location????
1253         if (returns_ip_addr == calls_ip_addr) {
1254           cerr << "return = " << returns_ip_addr << ", "
1255                << "call = " << calls_ip_addr << endl;
1256         }
1257         assert(returns_ip_addr != calls_ip_addr);
1258
1259         // if next call inst point comes before next return inst point, add
1260         //  the call inst point....
1261         if (calls_ip_addr < returns_ip_addr) {
1262             fill_in.push_back(calls[calls_idx++]);
1263         } else {
1264             fill_in.push_back(funcReturns[returns_idx++]);
1265         }
1266     }
1267 }
1268