Add new trampTrapMapping object to track traps in mutatees
[dyninst.git] / dyninstAPI / src / addressSpace.C
1 /*
2  * Copyright (c) 1996-2004 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 // $Id: addressSpace.C,v 1.15 2008/01/31 18:01:48 legendre Exp $
43
44 #include "addressSpace.h"
45 #include "codeRange.h"
46 #include "process.h"
47 #include "binaryEdit.h"
48
49 #include "miniTramp.h"
50 #include "baseTramp.h"
51 #include "multiTramp.h" // multiTramp and instArea
52 #include "instPoint.h"
53
54 // Two-level codeRange structure
55 #include "mapped_object.h"
56
57 #include "InstrucIter.h"
58
59 // Implementations of non-virtual functions in the address space
60 // class.
61
62 AddressSpace::AddressSpace() :
63     trapMapping(this),
64     multiTrampsById_(intHash),
65     trampGuardBase_(0),
66     up_ptr_(NULL),
67     costAddr_(0)
68 {}
69
70 AddressSpace::~AddressSpace() {}
71
72 process *AddressSpace::proc() {
73     return dynamic_cast<process *>(this);
74 }
75
76 BinaryEdit *AddressSpace::edit() {
77     return dynamic_cast<BinaryEdit *>(this);
78 }
79
80 // Fork constructor - and so we can assume a parent "process"
81 // rather than "address space"
82 void AddressSpace::copyAddressSpace(process *parent) {
83     deleteAddressSpace();
84
85     // This is only defined for process->process copy
86     // until someone can give a good reason for copying
87     // anything else...
88
89     assert(proc());
90
91     // Mapped objects first
92     for (unsigned i = 0; i < parent->mapped_objects.size(); i++) {
93         mapped_object *par_obj = parent->mapped_objects[i];
94         mapped_object *child_obj = new mapped_object(par_obj, proc());
95         assert(child_obj);
96         
97         mapped_objects.push_back(child_obj);
98         addOrigRange(child_obj);
99         
100         // This clones funcs, which then clone instPoints, which then 
101         // clone baseTramps, which then clones miniTramps.
102     }
103     
104
105     /////////////////////////
106     // Inferior heap
107     /////////////////////////
108
109     heap_ = inferiorHeap(parent->heap_);
110     heapInitialized_ = parent->heapInitialized_;
111
112     /////////////////////////
113     // Instrumentation (multiTramps on down)
114     /////////////////////////
115
116     pdvector<codeRange *> ranges;
117     parent->modifiedRanges_.elements(ranges);
118
119     for (unsigned i = 0; i < ranges.size(); i++) {
120         instArea *area = dynamic_cast<instArea *>(ranges[i]);
121         replacedFunctionCall *rfc = dynamic_cast<replacedFunctionCall *>(ranges[i]);
122         // Not used yet
123         //functionReplacement *fr = dynamic_cast<functionReplacement *>(ranges[i]);
124         
125        if (area) {
126             // Create a new multiTramp and add it
127             multiTramp *pMulti = area->multi;
128             multiTramp *cMulti = new multiTramp(pMulti, proc());
129             addMultiTramp(cMulti);
130         }
131         else if (rfc) {
132             replacedFunctionCall *cRFC = new replacedFunctionCall((*rfc));
133             addReplacedCall(cRFC);
134         }
135 #if 0
136 // Apparently this was never implemented... it probably should be, though.
137         else if (fr) {
138             functionReplacement *cFR = new functionReplacement(cFR);
139             addFuncReplacement(cFR);
140         }
141 #endif
142     }
143     // That will also create all baseTramps, miniTramps, ...
144
145     /////////////////////////
146     // Trap mappings
147     /////////////////////////
148     trapMapping.copyTrapMappings(& (parent->trapMapping));
149 }
150
151 void AddressSpace::deleteAddressSpace() {
152     // Methodically clear everything we have - it all went away
153     // We have the following member variables:
154
155     // bool heapInitialized_
156     // inferiorHeap heap_
157     // codeRangeTree textRanges_
158     // codeRangeTree modifiedCodeRanges_
159     // dictionary_hash multiTrampsById_
160
161     heapInitialized_ = false;
162     heap_.clear();
163
164     // We can just clear the originalCodeRanges structure - everything else
165     // is deleted elsewhere, and we won't leak.
166     textRanges_.clear();
167
168     // Delete only the wrapper objects
169     pdvector<codeRange *> ranges;
170     dataRanges_.elements(ranges);
171     for (unsigned i = 0; i < ranges.size(); i++) {
172         delete ranges[i];
173     }
174     ranges.clear();
175     dataRanges_.clear();
176
177     // Modified code ranges we have to take care of. 
178     modifiedRanges_.elements(ranges);
179     modifiedRanges_.clear();
180
181     for (unsigned i = 0; i < ranges.size(); i++) {
182         // This is either a:
183         // instArea
184         // replacedFunctionCall
185         // replacedFunction
186
187         // Either way, we can nuke 'em.
188         delete ranges[i];
189     }
190
191     multiTrampsById_.clear();
192
193     for (unsigned i = 0; i < mapped_objects.size(); i++) 
194         delete mapped_objects[i];
195
196     mapped_objects.clear();
197
198     trampGuardBase_ = 0;
199
200     // up_ptr_ is untouched
201     costAddr_ = 0;
202 }
203
204
205 // findRangeByAddr: finds the object (see below) that corresponds with
206 // a given absolute address. This includes:
207 //   Functions (non-relocated)
208 //   Base tramps
209 //   Mini tramps
210 //   Relocated functions
211 //
212 // The process class keeps a tree of objects occupying the address space.
213 // This top-level tree includes trampolines, relocated functions, and the
214 // application and shared objects. The search starts at the top of this tree.
215 // If the address resolves to a base tramp, mini tramp, or relocated function,
216 // that is returned. If the address resolves within the range of an shared
217 // object, the search recurses into the object (the offset into the object
218 // is calculated and the function lookup works from the offset). If the offset
219 // is within the a.out, we look up the function assuming the address given is
220 // the offset. 
221
222 // This function gives only "original" code - that is, code that either existed
223 // in the binary or that we added to unallocated space. If you're looking for places
224 // where things were overwritten (jumps to instrumentation, etc.) look at
225 // modifiedRanges_.
226
227 void AddressSpace::addOrigRange(codeRange *range) {
228     textRanges_.insert(range);
229     if (range->is_mapped_object()) {
230         // Hack... add data range
231         mappedObjData *data = new mappedObjData(range->is_mapped_object());
232         dataRanges_.insert(data);
233     }
234 }
235
236 void AddressSpace::addModifiedRange(codeRange *range) {
237     modifiedRanges_.insert(range);
238 }
239
240 void AddressSpace::removeOrigRange(codeRange *range) {
241     codeRange *tmp = NULL;
242     
243     if (!textRanges_.find(range->get_address(), tmp))
244         return;
245
246     assert (range == tmp);
247
248     textRanges_.remove(range->get_address());
249 }
250
251 void AddressSpace::removeModifiedRange(codeRange *range) {
252     codeRange *tmp = NULL;
253     
254     if (!modifiedRanges_.find(range->get_address(), tmp))
255         return;
256
257     assert (range == tmp);
258
259     modifiedRanges_.remove(range->get_address());
260
261     instArea *area = dynamic_cast<instArea *>(range);
262     if (area) {
263       // We have just removed a multiTramp. If the dictionary
264       // entry is the same as the instArea pointer, remove it
265       // from the dictionary as well so we can't accidentally
266       // access it that way.
267
268       // If the pointers aren't equal, squawk because that shouldn't
269       // happen.
270       
271       if (area->multi) {
272         if (multiTrampsById_[area->multi->id()] == area->multi)
273           multiTrampsById_[area->multi->id()] = NULL;
274         else {
275           fprintf(stderr, "%s[%u]: Warning: odd case in removing instArea\n",
276                   FILE__, __LINE__);
277         }
278         
279       }
280     }
281 }
282
283 codeRange *AddressSpace::findOrigByAddr(Address addr) {
284     codeRange *range = NULL;
285     
286     if (!textRanges_.find(addr, range)) {
287         return NULL;
288     }
289     
290     assert(range);
291     
292     bool in_range = (addr >= range->get_address() &&
293                      addr <= (range->get_address() + range->get_size()));
294     assert(in_range); // Supposed to return NULL if this is the case
295     
296     // The top level tree doesn't go into mapped_objects, which is not
297     // what we want; so if we're in a mapped_object, poke inside.
298     // However, if we're in a function (int_function), minitramp,
299     // basetramp, ... return that right away.
300     
301     mapped_object *mobj = range->is_mapped_object();
302     if (mobj) {
303         codeRange *obj_range = mobj->findCodeRangeByAddress(addr);
304         if (obj_range) range = obj_range;
305     }
306     
307     return range;
308 }
309
310 codeRange *AddressSpace::findModByAddr(Address addr) {
311     codeRange *range = NULL;
312     
313     if (!modifiedRanges_.find(addr, range)) {
314         return NULL;
315     }
316     
317     assert(range);
318     
319     bool in_range = (addr >= range->get_address() &&
320                      addr <= (range->get_address() + range->get_size()));
321     assert(in_range); // Supposed to return NULL if this is the case
322
323     return range;
324 }
325
326 // Returns the named symbol from the image or a shared object
327 bool AddressSpace::getSymbolInfo( const pdstring &name, Symbol &ret ) 
328 {
329   for (unsigned i = 0; i < mapped_objects.size(); i++) {
330     bool sflag;
331     sflag = mapped_objects[i]->getSymbolInfo( name, ret );
332     
333     if( sflag ) {
334       return true;
335     }
336   }
337   return false;
338 }
339
340
341
342 bool AddressSpace::getOrigRanges(pdvector<codeRange *> &ranges) {
343     textRanges_.elements(ranges);
344     return true;
345 }
346
347 bool AddressSpace::getModifiedRanges(pdvector<codeRange *> &ranges) {
348     modifiedRanges_.elements(ranges);
349     return true;
350 }
351
352 multiTramp *AddressSpace::findMultiTrampByAddr(Address addr) {    
353     codeRange *range = findModByAddr(addr);
354     if (range) {
355         instArea *area = dynamic_cast<instArea *>(range);
356         
357         if (area)
358             return area->multi;
359     }
360     range = findOrigByAddr(addr);
361
362     multiTramp *multi = dynamic_cast<multiTramp *>(range);
363     return multi;
364 }
365
366 multiTramp *AddressSpace::findMultiTrampById(unsigned int id) {
367     multiTramp *multi = NULL;
368     multiTrampsById_.find(id, multi);
369
370     return multi;
371 }
372
373 // Check to see if we're replacing an earlier multiTramp,
374 // add to the unmodifiedAreas list
375 void AddressSpace::addMultiTramp(multiTramp *multi) {
376     assert(multi);
377     assert(multi->instAddr());
378
379     if (multi->id() == 11286) {
380       fprintf(stderr, "Replacing multiTramp with id %d: new %p\n",
381               11286, multi);
382     }
383
384     // Actually... we haven't copied it yet, so don't add anything. 
385     //addOrigRange(multi);
386
387     codeRange *range = findModByAddr(multi->instAddr());
388     if (range) {
389         // We're overriding. Keep the instArea but update pointer.
390         instArea *area = dynamic_cast<instArea *>(range);
391         // It could be something else, which should have been
392         // caught already
393         if (!area) {
394             // Oops, someone already here... and multiTramps have
395             // the lowest priority.
396             return;
397         }
398         area->multi = multi;
399     }
400     else {
401         instArea *area = new instArea(multi);
402
403         modifiedRanges_.insert(area);
404     }
405
406     multiTrampsById_[multi->id()] = multi;
407 }
408
409 void AddressSpace::removeMultiTramp(multiTramp *multi) {
410     if (!multi) return;
411
412     assert(multi->instAddr());
413
414     removeOrigRange(multi);
415
416     // For multiTramps we also have the "wrapper" that
417     // represents the jump to the multiTramp. If that's
418     // still associated with this one, then nuke it
419     // as well. If not, ignore.
420
421     instArea *jump = dynamic_cast<instArea *>(findModByAddr(multi->instAddr()));
422
423     if (jump && jump->multi == multi) {
424         removeModifiedRange(jump);
425         delete jump;
426     }
427 }
428
429 functionReplacement *AddressSpace::findFuncReplacement(Address addr) {
430     codeRange *range = findModByAddr(addr);
431     if (!range) return NULL;
432     
433     functionReplacement *rep = dynamic_cast<functionReplacement *>(range);
434     return rep;
435 }
436
437 void AddressSpace::addFuncReplacement(functionReplacement *rep) {
438     assert(rep);
439     Address currAddr = rep->get_address();
440
441     while (currAddr < (rep->get_address() + rep->get_size())) {
442         codeRange *range = findModByAddr(currAddr);
443
444         if (range) removeModifiedRange(range);
445         currAddr += 1;
446     }
447
448     addModifiedRange(rep);
449 }
450
451 void AddressSpace::removeFuncReplacement(functionReplacement *rep) {
452     removeModifiedRange(rep);
453 }
454
455 replacedFunctionCall *AddressSpace::findReplacedCall(Address addr) {
456     codeRange *range = findModByAddr(addr);
457     if (!range) return NULL;
458     
459     replacedFunctionCall *rep = dynamic_cast<replacedFunctionCall *>(range);
460     return rep;
461 }
462
463 void AddressSpace::addReplacedCall(replacedFunctionCall *repcall) {
464     codeRange *range = findModByAddr(repcall->get_address());
465     if (range) {
466         // Can't replace instrumentation right now...
467         assert(dynamic_cast<replacedFunctionCall *>(range));
468         removeModifiedRange(range);
469         delete range;
470     }
471     assert(repcall);
472     addModifiedRange(repcall);
473 }
474
475 void AddressSpace::removeReplacedCall(replacedFunctionCall *repcall) {
476     removeModifiedRange(repcall);
477 }
478
479 //////////////////////////////////////////////////////////////////////////////
480 // Memory allocation routines
481 //////////////////////////////////////////////////////////////////////////////
482
483
484 void AddressSpace::inferiorFreeCompact() {
485   pdvector<heapItem *> &freeList = heap_.heapFree;
486   unsigned i, nbuf = freeList.size();
487
488   /* sort buffers by address */
489   VECTOR_SORT(freeList, heapItemCmpByAddr);
490
491   /* combine adjacent buffers */
492   bool needToCompact = false;
493   for (i = 1; i < freeList.size(); i++) {
494       heapItem *h1 = freeList[i-1];
495       heapItem *h2 = freeList[i];
496       assert(h1->length != 0);
497       if (h1->addr + h1->length > h2->addr) {
498           fprintf(stderr, "Error: heap 1 (%p) (0x%p to 0x%p) overlaps heap 2 (%p) (0x%p to 0x%p)\n",
499                   h1,
500                   (void *)h1->addr, (void *)(h1->addr + h1->length),
501                   h2,
502                   (void *)h2->addr, (void *)(h2->addr + h2->length));
503       }
504       assert(h1->addr + h1->length <= h2->addr);
505       if (h1->addr + h1->length == h2->addr
506           && h1->type == h2->type) {
507           h2->addr = h1->addr;
508           h2->length = h1->length + h2->length;
509           h1->length = 0;
510           nbuf--;
511           needToCompact = true;
512       }
513   }
514
515   /* remove any absorbed (empty) buffers */ 
516   if (needToCompact) {
517     pdvector<heapItem *> cleanList;
518     unsigned end = freeList.size();
519     for (i = 0; i < end; i++) {
520       heapItem *h1 = freeList[i];
521       if (h1->length != 0) {
522         cleanList.push_back(h1);
523       } else {
524         delete h1;
525       }
526     }
527     assert(cleanList.size() == nbuf);
528     for (i = 0; i < nbuf; i++) {
529       freeList[i] = cleanList[i];
530     }
531     freeList.resize(nbuf);
532     assert(freeList.size() == nbuf);
533   }
534 }
535     
536 int AddressSpace::findFreeIndex(unsigned size, int type, Address lo, Address hi) {
537     // type is a bitmask: match on any bit in the mask
538     pdvector<heapItem *> &freeList = heap_.heapFree;
539     
540     int best = -1;
541     for (unsigned i = 0; i < freeList.size(); i++) {
542         heapItem *h = freeList[i];
543         // check if free block matches allocation constraints
544         // Split out to facilitate debugging
545         infmalloc_printf("%s[%d]: comparing heap %d: 0x%lx-0x%lx/%d to desired %d bytes in 0x%lx-0x%lx/%d\n",
546                          FILE__, __LINE__, 
547                          i,
548                          h->addr, 
549                          h->addr + h->length,
550                          h->type,
551                          size,
552                          lo, 
553                          hi,
554                          type);
555         if (h->addr >= lo &&
556             (h->addr + size - 1) <= hi &&
557             h->length >= size &&
558             h->type & type) {
559             if (best == -1)
560                 best = i;
561             // check for better match
562             if (h->length < freeList[best]->length) best = i;
563         }
564     }
565     infmalloc_printf("%s[%d]: returning match %d\n", FILE__, __LINE__, best);
566     return best;
567 }
568
569 void AddressSpace::addHeap(heapItem *h) {
570     heap_.bufferPool.push_back(h);
571     heapItem *h2 = new heapItem(h);
572     h2->status = HEAPfree;
573     heap_.heapFree.push_back(h2);
574     heap_.totalFreeMemAvailable += h2->length;
575 }
576
577 void AddressSpace::initializeHeap() {
578     // (re)initialize everything 
579     heap_.heapActive.clear();
580     heap_.heapFree.resize(0);
581     heap_.disabledList.resize(0);
582     heap_.disabledListTotalMem = 0;
583     heap_.freed = 0;
584     heap_.totalFreeMemAvailable = 0;
585
586     heapInitialized_ = true;
587 }
588
589 /* returns true if memory was allocated for a variable starting at address
590    "block", otherwise returns false
591 */
592 bool AddressSpace::isInferiorAllocated(Address block) {
593     heapItem *h = NULL;  
594     return heap_.heapActive.find(block, h);
595 }
596
597 Address AddressSpace::inferiorMallocInternal(unsigned size,
598                                              Address lo,
599                                              Address hi,
600                                              inferiorHeapType type) {
601     infmalloc_printf("%s[%d]: inferiorMallocInternal, %d bytes, type %d, between 0x%lx - 0x%lx\n",
602                      FILE__, __LINE__, size, type, lo, hi);
603     int freeIndex = findFreeIndex(size, type, lo, hi);
604     if (freeIndex == -1) return 0; // Failure is often an option
605
606
607     // adjust active and free lists
608     assert(freeIndex != -1);
609     heapItem *h = heap_.heapFree[freeIndex];
610     assert(h);
611     
612     // remove allocated buffer from free list
613     if (h->length != size) {
614         // size mismatch: put remainder of block on free list
615         heapItem *rem = new heapItem(h);
616         rem->addr += size;
617         rem->length -= size;
618         heap_.heapFree[freeIndex] = rem;
619     } else {
620         // size match: remove entire block from free list
621         unsigned last = heap_.heapFree.size();
622         heap_.heapFree[freeIndex] = heap_.heapFree[last-1];
623         heap_.heapFree.resize(last-1);
624     }
625     // add allocated block to active list
626     h->length = size;
627     h->status = HEAPallocated;
628     heap_.heapActive[h->addr] = h;
629     // bookkeeping
630     heap_.totalFreeMemAvailable -= size;
631     assert(h->addr);
632     
633     return(h->addr);
634 }
635
636 void AddressSpace::inferiorFree(Address block) {
637     // find block on active list
638     infmalloc_printf("%s[%d]: inferiorFree for block at 0x%lx\n", FILE__, __LINE__, block);
639     heapItem *h = NULL;  
640     if (!heap_.heapActive.find(block, h)) {
641         // We can do this if we're at process teardown.
642         return;
643     }
644     assert(h);
645     
646     // Remove from the active list
647     heap_.heapActive.undef(block);
648     
649     // Add to the free list
650     h->status = HEAPfree;
651     heap_.heapFree.push_back(h);
652     heap_.totalFreeMemAvailable += h->length;
653     heap_.freed += h->length;
654     infmalloc_printf("%s[%d]: Freed block from 0x%lx - 0x%lx, %d bytes, type %d\n",
655                      FILE__, __LINE__,
656                      h->addr,
657                      h->addr + h->length,
658                      h->length,
659                      h->type);
660 }
661
662 void AddressSpace::inferiorMallocAlign(unsigned &size) {
663     // Align to the process word
664
665 #if !defined(arch_ia64)
666     unsigned alignment = (getAddressWidth() - 1);
667 #else
668     unsigned alignment = (128 - 1);
669 #endif
670
671     size = (size + alignment) & ~alignment;
672 }
673     
674 bool AddressSpace::inferiorRealloc(Address block, unsigned newSize) {
675 #if defined (cap_dynamic_heap)
676     // This is why it's not a reference...
677     inferiorMallocAlign(newSize);
678 #endif
679     
680     infmalloc_printf("%s[%d]: inferiorRealloc for block 0x%lx, new size %d\n",
681                      FILE__, __LINE__, block, newSize);
682
683     // find block on active list
684     heapItem *h = NULL;  
685     if (!heap_.heapActive.find(block, h)) {
686         // We can do this if we're at process teardown.
687         infmalloc_printf("%s[%d]: inferiorRealloc unable to find block, returning\n", FILE__, __LINE__);
688         return false;
689     }
690     assert(h);
691     infmalloc_printf("%s[%d]: inferiorRealloc found block with addr 0x%lx, length %d\n",
692                      FILE__, __LINE__, h->addr, h->length);
693     
694     if (h->length < newSize) {
695         return false; // Cannot make bigger...
696     }
697     if (h->length == newSize)
698         return true;
699
700     // We make a new "free" block that is the end of this one.
701     Address freeStart = block + newSize;
702     Address succAddr = h->addr + h->length;
703     int shrink = h->length - newSize;
704     
705     assert(shrink > 0);
706     
707     h->length = newSize;
708     
709
710 #if 0
711     // Old slow way
712     
713     
714     
715     // And run a compact; otherwise we'll end up with hugely fragmented memory.
716     // This is also quite expensive...
717     inferiorFreeCompact();
718
719 #endif
720
721     // New speedy way. Find the block that is the successor of the
722     // active block; if it exists, simply enlarge it "downwards". Otherwise,
723     // make a new block. 
724     heapItem *succ = NULL;
725     for (unsigned i = 0; i < heap_.heapFree.size(); i++) {
726         heapItem *tmp = heap_.heapFree[i];
727         assert(tmp);
728         if (tmp->addr == succAddr) {
729             succ = tmp;
730             break;
731         }
732     }
733     if (succ != NULL) {
734         infmalloc_printf("%s[%d]: enlarging existing block; old 0x%lx - 0x%lx (%d), new 0x%lx - 0x%lx (%d)\n",
735                          FILE__, __LINE__,
736                          succ->addr,
737                          succ->addr + succ->length,
738                          succ->addr,
739                          succ->addr - shrink,
740                          succ->addr + succ->length,
741                          succ->length + shrink);
742
743
744         succ->addr -= shrink;
745         succ->length += shrink;
746     }
747     else {
748         // Must make a new block to represent the free memory
749         infmalloc_printf("%s[%d]: inferiorRealloc: creating new block 0x%lx to 0x%lx (%d), type %d\n",
750                          FILE__, __LINE__, 
751                          freeStart, 
752                          freeStart + shrink,
753                          shrink,
754                          h->type);
755
756         heapItem *freeEnd = new heapItem(freeStart,
757                                          shrink,
758                                          h->type,
759                                          h->dynamic,
760                                          HEAPfree);
761         heap_.heapFree.push_back(freeEnd);
762     }
763
764     heap_.totalFreeMemAvailable += shrink;
765     heap_.freed += shrink;
766
767     
768     return true;
769 }    
770
771 /////////////////////////////////////////
772 // Function lookup...
773 /////////////////////////////////////////
774
775 bool AddressSpace::findFuncsByAll(const pdstring &funcname,
776                              pdvector<int_function *> &res,
777                              const pdstring &libname) { // = "", btw
778     
779     unsigned starting_entries = res.size(); // We'll return true if we find something
780     for (unsigned i = 0; i < mapped_objects.size(); i++) {
781         if (libname == "" ||
782             mapped_objects[i]->fileName() == libname.c_str() ||
783             mapped_objects[i]->fullName() == libname.c_str()) {
784             const pdvector<int_function *> *pretty = mapped_objects[i]->findFuncVectorByPretty(funcname);
785             if (pretty) {
786                 // We stop at first match...
787                 for (unsigned pm = 0; pm < pretty->size(); pm++) {
788                     res.push_back((*pretty)[pm]);
789                 }
790             }
791             else {
792                 const pdvector<int_function *> *mangled = mapped_objects[i]->findFuncVectorByMangled(funcname);
793                 if (mangled) {
794                     for (unsigned mm = 0; mm < mangled->size(); mm++) {
795                         res.push_back((*mangled)[mm]);
796                     }
797                 }
798             }
799         }
800     }
801     return (res.size() != starting_entries);
802 }
803
804
805 bool AddressSpace::findFuncsByPretty(const pdstring &funcname,
806                              pdvector<int_function *> &res,
807                              const pdstring &libname) { // = "", btw
808
809     unsigned starting_entries = res.size(); // We'll return true if we find something
810
811     for (unsigned i = 0; i < mapped_objects.size(); i++) {
812         if (libname == "" ||
813             mapped_objects[i]->fileName() == libname.c_str() ||
814             mapped_objects[i]->fullName() == libname.c_str()) {
815             const pdvector<int_function *> *pretty = mapped_objects[i]->findFuncVectorByPretty(funcname);
816             if (pretty) {
817                 // We stop at first match...
818                 for (unsigned pm = 0; pm < pretty->size(); pm++) {
819                     res.push_back((*pretty)[pm]);
820                 }
821             }
822         }
823     }
824     return res.size() != starting_entries;
825 }
826
827
828 bool AddressSpace::findFuncsByMangled(const pdstring &funcname,
829                                  pdvector<int_function *> &res,
830                                  const pdstring &libname) { // = "", btw
831     unsigned starting_entries = res.size(); // We'll return true if we find something
832
833     for (unsigned i = 0; i < mapped_objects.size(); i++) {
834         if (libname == "" ||
835             mapped_objects[i]->fileName() == libname.c_str() ||
836             mapped_objects[i]->fullName() == libname.c_str()) {
837             const pdvector<int_function *> *mangled = 
838                mapped_objects[i]->findFuncVectorByMangled(funcname);
839             if (mangled) {
840                 for (unsigned mm = 0; mm < mangled->size(); mm++) {
841                    res.push_back((*mangled)[mm]);
842                 }
843             }
844         }
845     }
846     return res.size() != starting_entries;
847 }
848
849 int_function *AddressSpace::findOnlyOneFunction(const string &name,
850                                            const string &lib) 
851 {
852     assert(mapped_objects.size());
853
854     pdvector<int_function *> allFuncs;
855     if (!findFuncsByAll(name.c_str(), allFuncs, lib.c_str()))
856         return NULL;
857     if (allFuncs.size() > 1) {
858         cerr << "Warning: multiple matches for " << name << ", returning first" << endl;
859     }
860     return allFuncs[0];
861 }
862
863 /////////////////////////////////////////
864 // Variable lookup...
865 /////////////////////////////////////////
866
867 bool AddressSpace::findVarsByAll(const pdstring &varname,
868                             pdvector<int_variable *> &res,
869                             const pdstring &libname) { // = "", btw
870     unsigned starting_entries = res.size(); // We'll return true if we find something
871     
872     for (unsigned i = 0; i < mapped_objects.size(); i++) {
873         if (libname == "" ||
874             mapped_objects[i]->fileName() == libname.c_str() ||
875             mapped_objects[i]->fullName() == libname.c_str()) {
876             const pdvector<int_variable *> *pretty = mapped_objects[i]->findVarVectorByPretty(varname);
877             if (pretty) {
878                 // We stop at first match...
879                 for (unsigned pm = 0; pm < pretty->size(); pm++) {
880                     res.push_back((*pretty)[pm]);
881                 }
882             }
883             else {
884                 const pdvector<int_variable *> *mangled = mapped_objects[i]->findVarVectorByMangled(varname);
885                 if (mangled) {
886                     for (unsigned mm = 0; mm < mangled->size(); mm++) {
887                         res.push_back((*mangled)[mm]);
888                     }
889                 }
890             }
891         }
892     }
893
894     return res.size() != starting_entries;
895 }
896
897
898
899 // Get me a pointer to the instruction: the return is a local
900 // (mutator-side) store for the mutatee. This may duck into the local
901 // copy for images, or a relocated function's self copy.
902 // TODO: is this really worth it? Or should we just use ptrace?
903
904 void *AddressSpace::getPtrToInstruction(Address addr) const {
905     codeRange *range;
906
907     if (textRanges_.find(addr, range)) {
908         return range->getPtrToInstruction(addr);
909     }
910     else if (dataRanges_.find(addr, range)) {
911         mappedObjData *data = dynamic_cast<mappedObjData *>(range);
912         assert(data);
913         return data->obj->getPtrToData(addr);
914     }
915     return NULL;
916 }
917
918 bool AddressSpace::isValidAddress(const Address& addr) const{
919     // "Is this part of the process address space?"
920     codeRange *dontcare;
921     if (textRanges_.find(addr, dontcare))
922         return true;
923     if (dataRanges_.find(addr, dontcare))
924         return true;
925     fprintf(stderr, "Warning: address 0x%p not valid!\n",
926             (void *)addr);
927     return false;
928 }        
929
930 mapped_object *AddressSpace::findObject(Address addr) {
931     for (unsigned i=0; i<mapped_objects.size(); i++)
932     {
933         if (addr >= mapped_objects[i]->codeAbs() &&
934             addr < mapped_objects[i]->codeAbs() + mapped_objects[i]->imageSize())
935         {
936             return mapped_objects[i];
937         }
938     }
939     return NULL;
940 }
941
942 int_function *AddressSpace::findFuncByAddr(Address addr) {
943     codeRange *range = findOrigByAddr(addr);
944     if (!range) return NULL;
945     
946     int_function *func_ptr = range->is_function();
947     multiTramp *multi = range->is_multitramp();
948     miniTrampInstance *mti = range->is_minitramp();
949
950     if(func_ptr) {
951        return func_ptr;
952     }
953     else if (multi) {
954         return multi->func();
955     }
956     else if (mti) {
957         return mti->baseTI->multiT->func();
958     }
959     else {
960         return NULL;
961     }
962 }
963
964 int_basicBlock *AddressSpace::findBasicBlockByAddr(Address addr) {
965     codeRange *range = findOrigByAddr(addr);
966     if (!range) return NULL;
967
968     int_basicBlock *b = range->is_basicBlock();
969     int_function *f = range->is_function();
970     multiTramp *mt = range->is_multitramp();
971     miniTrampInstance *mti = range->is_minitramp();
972
973     if(b) {
974         return b;
975     }
976     else if(f) {
977         return f->findBlockByAddr(addr);
978     }
979     else if(mt) {
980         return mt->func()->findBlockByAddr(addr);
981     }
982     else if(mti) {
983         return mti->baseTI->multiT->func()->findBlockByAddr(addr);
984     }
985     else
986         return NULL;
987 }
988
989 int_function *AddressSpace::findFuncByInternalFunc(image_func *ifunc) {
990     assert(ifunc);
991   
992     // Now we have to look up our specialized version
993     // Can't do module lookup because of DEFAULT_MODULE...
994     pdvector<int_function *> possibles;
995     if (!findFuncsByMangled(ifunc->symTabName().c_str(),
996                             possibles))
997         return NULL;
998
999     assert(possibles.size());
1000   
1001     for (unsigned i = 0; i < possibles.size(); i++) {
1002         if (possibles[i]->ifunc() == ifunc) {
1003             return possibles[i];
1004         }
1005     }
1006     return NULL;
1007 }
1008
1009 // findModule: returns the module associated with mod_name 
1010 // this routine checks both the a.out image and any shared object
1011 // images for this resource
1012 mapped_module *AddressSpace::findModule(const pdstring &mod_name, bool wildcard)
1013 {
1014     // KLUDGE: first search any shared libraries for the module name 
1015     //  (there is only one module in each shared library, and that 
1016     //  is the library name)
1017     for(u_int j=0; j < mapped_objects.size(); j++){
1018         mapped_module *mod = mapped_objects[j]->findModule(mod_name.c_str(), wildcard);
1019         if (mod) {
1020             return (mod);
1021         }
1022     }
1023     return NULL;
1024 }
1025
1026 // findObject: returns the object associated with obj_name 
1027 // This just iterates over the mapped object vector
1028 mapped_object *AddressSpace::findObject(const pdstring &obj_name, bool wildcard)
1029 {
1030     for(u_int j=0; j < mapped_objects.size(); j++){
1031         if (mapped_objects[j]->fileName() == obj_name.c_str() ||
1032             mapped_objects[j]->fullName() == obj_name.c_str() ||
1033             (wildcard &&
1034              (obj_name.wildcardEquiv(mapped_objects[j]->fileName().c_str()) ||
1035               obj_name.wildcardEquiv(mapped_objects[j]->fullName().c_str()))))
1036             return mapped_objects[j];
1037     }
1038     return NULL;
1039 }
1040
1041 // findObject: returns the object associated with obj_name 
1042 // This just iterates over the mapped object vector
1043 mapped_object *AddressSpace::findObject(fileDescriptor desc)
1044 {
1045     for(u_int j=0; j < mapped_objects.size(); j++){
1046        if (desc == mapped_objects[j]->getFileDesc()) 
1047             return mapped_objects[j];
1048     }
1049     return NULL;
1050 }
1051
1052 // getAllFunctions: returns a vector of all functions defined in the
1053 // a.out and in the shared objects
1054
1055 void AddressSpace::getAllFunctions(pdvector<int_function *> &funcs) {
1056     for (unsigned i = 0; i < mapped_objects.size(); i++) {
1057         mapped_objects[i]->getAllFunctions(funcs);
1058     }
1059 }
1060       
1061 // getAllModules: returns a vector of all modules defined in the
1062 // a.out and in the shared objects
1063
1064 void AddressSpace::getAllModules(pdvector<mapped_module *> &mods){
1065     for (unsigned i = 0; i < mapped_objects.size(); i++) {
1066         const pdvector<mapped_module *> &obj_mods = mapped_objects[i]->getModules();
1067         for (unsigned j = 0; j < obj_mods.size(); j++) {
1068             mods.push_back(obj_mods[j]);
1069         }
1070     }
1071 }
1072
1073 //Acts like findTargetFuncByAddr, but also finds the function if addr
1074 // is an indirect jump to a function.
1075 //I know this is an odd function, but darn I need it.
1076 int_function *AddressSpace::findJumpTargetFuncByAddr(Address addr) {
1077     Address addr2 = 0;
1078     int_function *f = findFuncByAddr(addr);
1079     if (f)
1080         return f;
1081
1082     codeRange *range = findOrigByAddr(addr);
1083     if (!range->is_mapped_object()) 
1084         return NULL;
1085     
1086     InstrucIter ii(addr, this);
1087     if (ii.isAJumpInstruction())
1088         addr2 = ii.getBranchTargetAddress();
1089
1090     return findFuncByAddr(addr2);
1091 }
1092
1093 AstNodePtr AddressSpace::trampGuardAST() {
1094     if (!trampGuardBase_) {
1095         // Don't have it yet....
1096         return AstNodePtr();
1097     }
1098     if (trampGuardAST_) return trampGuardAST_;
1099
1100     trampGuardAST_ = AstNode::operandNode(AstNode::DataAddr, 
1101                                           (void *)trampGuardBase_);
1102
1103     return trampGuardAST_;
1104 }
1105
1106 // Add it at the bottom...
1107 void AddressSpace::deleteGeneratedCode(generatedCodeObject *delInst)
1108 {
1109 #if 0
1110     fprintf(stderr, "Deleting generated code %p, which is a:\n",
1111             delInst);
1112     if (dynamic_cast<multiTramp *>(delInst)) {
1113         fprintf(stderr, "   multiTramp\n");
1114     }
1115     else if (dynamic_cast<baseTrampInstance *>(delInst)) {
1116         fprintf(stderr, "   baseTramp\n");
1117     } 
1118     else if (dynamic_cast<miniTrampInstance *>(delInst)) {
1119         fprintf(stderr, "   miniTramp\n");
1120     }
1121     else {
1122         fprintf(stderr, "   unknown\n");
1123     }
1124 #endif    
1125
1126     delete delInst;
1127 }
1128
1129 trampTrapMappings::trampTrapMappings(AddressSpace *a) :
1130    needs_updating(false),
1131    as(a),
1132    trapTableUsed(NULL),
1133    trapTableVersion(NULL),
1134    trapTable(NULL),
1135    trapTableSorted(NULL),
1136    table_version(0),
1137    table_used(0),
1138    table_allocated(0),
1139    table_mutatee_size(0),
1140    current_table(0x0)
1141 {
1142 }
1143
1144 void trampTrapMappings::copyTrapMappings(trampTrapMappings *parent)
1145 {
1146   needs_updating = parent->needs_updating;
1147   trapTableUsed = NULL;
1148   trapTableVersion = NULL;
1149   trapTable = NULL;
1150   trapTableSorted = NULL;
1151   table_version = parent->table_version;
1152   table_used = parent->table_used;
1153   table_allocated = parent->table_allocated;
1154   table_mutatee_size = parent->table_mutatee_size;
1155   current_table = parent->current_table;
1156   mapping = parent->mapping;
1157 }
1158
1159 void trampTrapMappings::clearTrapMappings()
1160 {
1161   needs_updating = false;
1162   trapTableUsed = NULL;
1163   trapTableVersion = NULL;
1164   trapTable = NULL;
1165   trapTableSorted = NULL;
1166   table_version = 0;
1167   table_used = 0;
1168   table_allocated = 0;
1169   table_mutatee_size = 0;
1170   current_table = 0;
1171   mapping.clear();
1172 }
1173
1174 void trampTrapMappings::addTrapMapping(Address from, Address to, 
1175                                        bool write_to_mutatee)
1176 {
1177 #if defined(arch_x86) || defined(arch_x86_64)
1178    //x86 traps occur at +1 addr
1179    from++;
1180 #endif
1181    tramp_mapping_t m;
1182    bool existing_trap = (mapping.count(from) != 0);
1183    m.from_addr = from;
1184    m.to_addr = to;
1185    m.written = false;
1186    m.cur_index = existing_trap ? mapping[from].cur_index : INDEX_INVALID;
1187    m.mutatee_side = write_to_mutatee;
1188    mapping[from] = m;
1189 #if defined(cap_mutatee_traps)
1190    if (write_to_mutatee && !existing_trap) {
1191       table_mutatee_size++;
1192    }
1193    needs_updating = true;
1194 #endif
1195 }
1196
1197 bool trampTrapMappings::definesTrapMapping(Address from)
1198 {
1199    return mapping.count(from) != 0;
1200 }
1201
1202 Address trampTrapMappings::getTrapMapping(Address from)
1203 {
1204    if (!mapping.count(from))
1205       return 0;
1206    return mapping[from].to_addr;
1207 }
1208
1209 bool trampTrapMappings::needsUpdating()
1210 {
1211    return needs_updating;
1212 }
1213
1214 AddressSpace *trampTrapMappings::proc() const {
1215    return as;
1216 }
1217
1218 bool mapping_sort(const trampTrapMappings::tramp_mapping_t *lhs,
1219                   const trampTrapMappings::tramp_mapping_t *rhs)
1220 {
1221    return lhs->from_addr < rhs->from_addr;
1222 }
1223
1224 #if defined(cap_32_64)
1225 void trampTrapMappings::writeToBuffer(unsigned char *buffer, unsigned long val,
1226                                       unsigned addr_width)
1227 {
1228    //Deal with the case when mutatee word size != mutator word size
1229    if (addr_width != sizeof(Address)) {
1230       //Currently only support 64-bit mutators with 32-bit mutatees
1231       assert(addr_width == 4);
1232       assert(sizeof(Address) == 8);
1233       *((uint32_t *) buffer) = (uint32_t) val;
1234       return;
1235    }
1236    *((unsigned long *) buffer) = val;
1237 }
1238 #else
1239 void trampTrapMappings::writeToBuffer(unsigned char *buffer, unsigned long val,
1240                                       unsigned)
1241 {
1242    *((unsigned long *) buffer) = val;
1243 }
1244 #endif
1245
1246
1247 void trampTrapMappings::writeTrampVariable(const int_variable *var, 
1248                                            unsigned long val)
1249 {
1250    unsigned char buffer[16];
1251    unsigned aw = proc()->getAddressWidth();
1252
1253    writeToBuffer(buffer, val, aw);
1254    bool result = proc()->writeDataSpace((void *) var->getAddress(), aw, buffer);
1255    assert(result);
1256 }
1257                   
1258 void trampTrapMappings::flush() {
1259    if (!needs_updating)
1260       return;
1261
1262    process *p = dynamic_cast<process *>(proc());
1263    mapped_object *rtlib;
1264    if (p) {
1265       rtlib = p->runtime_lib;
1266    }
1267    else {
1268       //Binary rewritter needs RT library loaded before this will work.
1269       // Set rtlib when this becomes possible.
1270       assert(0);
1271    }
1272
1273    //We'll sort addresses in the binary rewritter (when writting only happens
1274    // once and we may do frequent lookups)
1275    //If we're using the dynamic instrumentor and creating a new table we might
1276    // as well sort it.
1277    //If we're just adding a few entries to the table which already fit, then
1278    // we'll just append them to the end of the table.
1279    //
1280    //If we're sorting, then everytime we update we'll generate a whole new table
1281   //If we're not sorting, then each update will just append to the end of the
1282    // table.
1283    bool should_sort = (dynamic_cast<process *>(proc()) == NULL ||
1284                        table_mutatee_size > table_allocated);
1285
1286    if (should_sort) {
1287       table_used = 0; //We're rebuilding the table, nothing's used.
1288    }
1289
1290    std::vector<tramp_mapping_t*> mappings_to_add;
1291    std::vector<tramp_mapping_t*> mappings_to_update;
1292    hash_map<Address, tramp_mapping_t>::iterator i;
1293    for (i = mapping.begin(); i != mapping.end(); i++) {
1294       tramp_mapping_t &m = (*i).second;
1295       if (!m.mutatee_side || (m.written && !should_sort))
1296          continue;
1297       m.written = true;
1298       if (should_sort || m.cur_index == INDEX_INVALID)
1299          mappings_to_add.push_back(&m);
1300       else if (m.cur_index != INDEX_INVALID)
1301          mappings_to_update.push_back(&m);
1302    }
1303    assert(mappings_to_add.size() + table_used == table_mutatee_size);
1304
1305    for (unsigned k=0; k<mappings_to_add.size(); k++)
1306    {
1307        mappings_to_add[k]->written = true;
1308    }
1309
1310    //Sort the mappings (if needed) 
1311    if (should_sort) 
1312       std::sort(mappings_to_add.begin(), mappings_to_add.end(), mapping_sort);
1313
1314    // Assign the cur_index field of each entry in the new mappings we're adding
1315    for (unsigned j=0; j<mappings_to_add.size(); j++) {
1316       mappings_to_add[j]->cur_index = table_used + j;
1317    }
1318    
1319    //Each table entry has two pointers.
1320    unsigned entry_size = proc()->getAddressWidth() * 2;
1321
1322    //Allocate the space for the tramp mapping table, or make sure that enough
1323    // space already exists.
1324    Address write_addr = 0x0;
1325    if (table_mutatee_size > table_allocated) {
1326       //Free old table
1327       if (current_table) {
1328          proc()->inferiorFree(current_table);
1329       }
1330       
1331       //Calculate size of new table
1332       table_allocated = (unsigned long) (table_mutatee_size * 1.5);
1333       if (table_allocated < MIN_TRAP_TABLE_SIZE)
1334          table_allocated = MIN_TRAP_TABLE_SIZE;
1335       
1336       //allocate
1337       current_table = proc()->inferiorMalloc(table_allocated * entry_size);
1338       assert(current_table);
1339    }
1340
1341    //Add any new entries to the table
1342    unsigned char *buffer = NULL;
1343    if (mappings_to_add.size()) {
1344       //Create a buffer containing the new entries we're going to write.
1345       unsigned long bytes_to_add = mappings_to_add.size() * entry_size;
1346       buffer = (unsigned char *) malloc(bytes_to_add);
1347       assert(buffer);
1348       
1349       unsigned char *cur = buffer;
1350       std::vector<tramp_mapping_t*>::iterator j;
1351       for (j = mappings_to_add.begin(); j != mappings_to_add.end(); j++) {
1352          tramp_mapping_t &tm = **j;
1353          writeToBuffer(cur, tm.from_addr, proc()->getAddressWidth());
1354          cur += proc()->getAddressWidth();
1355          writeToBuffer(cur, tm.to_addr, proc()->getAddressWidth());
1356          cur += proc()->getAddressWidth();
1357       }
1358       assert(cur == buffer + bytes_to_add);
1359       
1360       //Write the new entries into the process
1361       write_addr = current_table + (table_used * entry_size);
1362       bool result = proc()->writeDataSpace((void *) write_addr, bytes_to_add, 
1363                                            buffer);
1364       assert(result);
1365       free(buffer);
1366       buffer = NULL;
1367
1368       table_used += mappings_to_add.size();
1369    }
1370
1371    //Now we get to update existing entries that have been modified.
1372    if (mappings_to_update.size()) {
1373       assert(!should_sort);
1374       unsigned aw = proc()->getAddressWidth();
1375       buffer = (unsigned char *) malloc(aw);
1376       assert(buffer);
1377
1378       //For each entry, use its cur_index field to figure out where in the
1379       // process it is, and write it.
1380       //We only need to update the to_addr, since this is an update of an
1381       // existing from_addr
1382       std::vector<tramp_mapping_t*>::iterator j;
1383       for (j = mappings_to_update.begin(); j != mappings_to_update.end(); j++) {
1384          tramp_mapping_t &tm = **j;
1385          writeToBuffer(buffer, tm.to_addr, aw);
1386
1387          Address write_addr = current_table + (tm.cur_index * entry_size) + aw;
1388          bool result = proc()->writeDataSpace((void *) write_addr, aw, buffer);
1389          assert(result);
1390       }
1391       
1392       free(buffer);
1393       buffer = NULL;
1394    }
1395
1396    //This function just keeps going... Now we need to take all of those 
1397    // mutatee side variables and update them.
1398    if (!trapTable) {
1399       //Lookup all variables that are in the rtlib
1400       assert(rtlib);
1401       trapTableUsed = rtlib->getVariable("dyninstTrapTableUsed");
1402       trapTableVersion = rtlib->getVariable("dyninstTrapTableVersion");
1403       trapTable = rtlib->getVariable("dyninstTrapTable");
1404       trapTableSorted = rtlib->getVariable("dyninstTrapTableIsSorted");
1405
1406       assert(trapTableUsed);
1407       assert(trapTableVersion);
1408       assert(trapTable);
1409       assert(trapTableSorted);
1410    }
1411    
1412    writeTrampVariable(trapTableUsed, table_used);
1413    writeTrampVariable(trapTableVersion, ++table_version);
1414    writeTrampVariable(trapTable, (unsigned long) current_table);
1415    writeTrampVariable(trapTableSorted, should_sort ? 1 : 0);
1416
1417    needs_updating = false;
1418 }
1419