Memory leak fixes and stopped tracking topped locations.
[dyninst.git] / dyninstAPI / src / function.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 // $Id: function.C,v 1.10 2005/03/02 19:44:45 bernat Exp
32
33 #include "function.h"
34 #include "instPoint.h"
35 #include "debug.h"
36 #include "dynProcess.h"
37
38 #include "mapped_object.h"
39 #include "mapped_module.h"
40 #include "InstructionDecoder.h"
41 #include "MemoryEmulator/memEmulator.h"
42 #include "Relocation/Transformers/Movement-analysis.h"
43
44 #include "PatchMgr.h" // Scope
45
46 #include "Parsing.h"
47
48 #include "binaryEdit.h"
49
50 using namespace Dyninst;
51 using namespace Dyninst::ParseAPI;
52 using namespace Dyninst::PatchAPI;
53 using namespace Dyninst::Relocation;
54 using namespace Dyninst::PatchAPI;
55
56 int func_instance_count = 0;
57
58 func_instance::func_instance(parse_func *f,
59                              Address baseAddr,
60                              mapped_module *mod) :
61   PatchFunction(f, mod->obj()),
62   ptrAddr_(f->getPtrOffset() ? f->getPtrOffset() + baseAddr : 0),
63   mod_(mod),
64   prevBlocksAbruptEnds_(0),
65   handlerFaultAddr_(0),
66   handlerFaultAddrAddr_(0)
67 #if defined(os_windows)
68   , callingConv(unknown_call)
69   , paramSize(0)
70 #endif
71    , wrapperSym_(NULL)
72 {
73   assert(f);
74 #if defined(ROUGH_MEMORY_PROFILE)
75   func_instance_count++;
76   if ((func_instance_count % 1000) == 0)
77     fprintf(stderr, "func_instance_count: %d (%d)\n",
78             func_instance_count, func_instance_count*sizeof(func_instance));
79 #endif
80
81     parsing_printf("%s: creating new proc-specific function at 0x%lx\n",
82                    symTabName().c_str(), addr_);
83 #if defined(cap_stack_mods)
84     _hasStackMod = false ;
85     _processedOffsetVector = false;
86     _hasDebugSymbols = false;
87     _seeded = false;
88     _randomizeStackFrame = false;
89     _hasCanary = false;
90     _modifications = new std::set<StackMod*>();
91     _offVec = new OffsetVector();
92     _tmpObjects = new set<tmpObject, less_tmpObject>();
93     _tMap = new TMap();
94     _accessMap = new std::map<Address, Accesses*>();
95     assert(_modifications && _offVec && _tMap && _accessMap);
96 #endif
97 }
98
99 unsigned func_instance::footprint() {
100     unsigned totalSize = 0;
101     vector<FuncExtent*> exts = ifunc()->extents();
102     for (unsigned i=0; i < exts.size(); i++) {
103         totalSize += (exts[i]->end() - exts[i]->start());
104     }
105     return totalSize;
106 }
107
108 func_instance::func_instance(const func_instance *parFunc,
109                              mapped_module *childMod) :
110   PatchFunction(parFunc->ifunc(), childMod->obj()),
111   ptrAddr_(parFunc->ptrAddr_),
112   mod_(childMod),
113   prevBlocksAbruptEnds_(0),
114   handlerFaultAddr_(0),
115   handlerFaultAddrAddr_(0)
116 #if defined(os_windows)
117   , callingConv(parFunc->callingConv)
118   , paramSize(parFunc->paramSize)
119 #endif
120    , wrapperSym_(NULL)
121 {
122    assert(ifunc());
123    // According to contract /w/ the mapped_object
124    // all blocks have already been constructed.
125    // Do we duplicate the parent or wait? I'm
126    // tempted to wait, just because of the common
127    // fork/exec case.
128 #if defined(cap_stack_mods)
129    _hasStackMod = false ;
130    _processedOffsetVector = false;
131    _hasDebugSymbols = false;
132    _seeded = false;
133    _randomizeStackFrame = false;
134    _hasCanary = false;
135    _modifications = new std::set<StackMod*>();
136    _offVec = new OffsetVector();
137    _tmpObjects = new set<tmpObject, less_tmpObject>();
138    _tMap = new TMap();
139    _accessMap = new std::map<Address, Accesses*>();
140    assert(_modifications && _offVec && _tMap && _accessMap);
141 #endif
142 }
143
144 func_instance::~func_instance() { 
145    // We don't delete blocks, since they're shared between functions
146    // We _do_ delete context instPoints, though
147    // Except that should get taken care of normally since the
148    // structures are static. 
149    for (unsigned i = 0; i < parallelRegions_.size(); i++)
150       delete parallelRegions_[i];
151    if (wrapperSym_ != NULL) {
152       delete wrapperSym_;
153    }
154 }
155
156 // the original entry block is gone, we choose a new entry block from the
157 // function, whichever non-dead block we can find that has no intraprocedural 
158 // incoming edges.  If there's no obvious block to choose, we stick with the
159 // default block
160 block_instance * func_instance::setNewEntry(block_instance *def,
161                                             std::set<block_instance*> &deadBlocks)
162 {
163     block_instance *newEntry = NULL;
164     assert(!all_blocks_.empty());
165
166     // choose block with no intraprocedural incoming edges
167     PatchFunction::Blockset::iterator bIter;
168     for (bIter = all_blocks_.begin(); 
169          bIter != all_blocks_.end(); 
170          bIter++) 
171     {
172         block_instance *block = static_cast<block_instance*>(*bIter);
173         if (deadBlocks.find(block) == deadBlocks.end()) {
174             ParseAPI::Intraproc epred;
175             const Block::edgelist & ib_ins = block->llb()->sources();
176             
177             if(std::distance(boost::make_filter_iterator(epred, ib_ins.begin(), ib_ins.end()), 
178                              boost::make_filter_iterator(epred, ib_ins.end(), ib_ins.end())) == 0)
179             {
180                 if (NULL != newEntry) {
181                     fprintf(stderr,"WARNING: multiple blocks in function %lx "
182                         "with overwritten entry point have no incoming edges: "
183                         "[%lx %lx) and [%lx %lx) %s[%d]\n",
184                         addr_, newEntry->llb()->start(),
185                         newEntry->llb()->start() + newEntry->llb()->end(),
186                         block->llb()->start(),
187                         block->llb()->start() + block->llb()->end(),
188                         FILE__,__LINE__);
189                 } else {
190                     newEntry = block;
191                 }
192             }
193         }
194     }
195     // if all blocks have incoming edges, choose the default block
196     if( ! newEntry ) {
197         newEntry = def;
198         mal_printf("Setting new entry block for func at 0x%lx to "
199                 "actively executing block [%lx %lx), as none of the function "
200                 "blocks lacks intraprocedural edges %s[%d]\n", addr_, 
201                 def->start(), def->end(), FILE__,__LINE__);
202     }
203
204     // set the new entry block
205     ifunc()->setEntryBlock(newEntry->llb());
206     addr_ = newEntry->start();
207
208     // debug output
209     if (newEntry->isShared()) {
210         mal_printf("New entry block chosen for func 0x%lx is shared\n",addr_);
211     }
212     mal_printf("Func has new entry block [%lx %lx)\n",addr_, 
213                newEntry->start(), newEntry->end());
214     return newEntry;
215 }
216
217 void func_instance::setHandlerFaultAddr(Address fa) {
218     handlerFaultAddr_ = fa;
219 }
220
221 // Sets the address in the structure at which the fault instruction's
222 // address is stored if "set" is true.  Accesses the fault address and
223 // translates it back to an original address if it corresponds to
224 // relocated code in the Dyninst heap
225 void func_instance::setHandlerFaultAddrAddr(Address faa, bool set) {
226   if (set) {
227     // save the faultAddrAddr
228     handlerFaultAddrAddr_ = faa;
229   }
230
231   // get the faultAddr
232   assert(proc()->proc());
233   assert(sizeof(Address) == proc()->getAddressWidth());
234   Address faultAddr=0;
235   if (!proc()->readDataSpace
236       ((void*)faa, proc()->getAddressWidth(), (void*)&faultAddr, true))
237     {
238       assert(0);
239     }
240
241   // translate the faultAddr back to an original address, and if
242   // that translation was necessary, save it to the faultAddrAddr in the
243   // CONTEXT struct
244   if (proc()->proc()->isRuntimeHeapAddr(faultAddr)) {
245
246     Address origAddr = faultAddr;
247     vector<func_instance *> tmps;
248     baseTramp *bti = NULL;
249     bool success = proc()->getAddrInfo(faultAddr, origAddr, tmps, bti);
250     assert(success);
251     assert( proc()->writeDataSpace((void*)faa,
252                                    sizeof(Address),
253                                    (void*)&origAddr) );
254   }
255 }
256
257 void func_instance::getReachableBlocks(const set<block_instance*> &exceptBlocks,
258                                       const list<block_instance*> &seedBlocks,
259                                       set<block_instance*> &reachBlocks)//output
260 {
261     list<parse_block*> imgSeeds;
262     for (list<block_instance*>::const_iterator sit = seedBlocks.begin();
263          sit != seedBlocks.end();
264          sit++)
265     {
266         imgSeeds.push_back((*sit)->llb());
267     }
268     set<parse_block*> imgExcept;
269     for (set<block_instance*>::const_iterator eit = exceptBlocks.begin();
270          eit != exceptBlocks.end();
271          eit++)
272     {
273         imgExcept.insert((*eit)->llb());
274     }
275
276     // image-level function does the work
277     set<parse_block*> imgReach;
278     ifunc()->getReachableBlocks(imgExcept,imgSeeds,imgReach);
279
280     for (set<parse_block*>::iterator rit = imgReach.begin();
281          rit != imgReach.end();
282          rit++)
283     {
284         reachBlocks.insert( obj()->findBlock(*rit) );
285     }
286 }
287
288 void print_func_vector_by_pretty_name(std::string prefix,
289                                       pdvector<func_instance *>*funcs) {
290     unsigned int i;
291     func_instance *func;
292     for(i=0;i<funcs->size();i++) {
293       func = ((*funcs)[i]);
294       cerr << prefix << func->prettyName() << endl;
295     }
296 }
297
298 mapped_object *func_instance::obj() const { return mod()->obj(); }
299 AddressSpace *func_instance::proc() const { return obj()->proc(); }
300
301 const func_instance::BlockSet &func_instance::unresolvedCF() {
302    if (ifunc()->getPrevBlocksUnresolvedCF() != ifunc()->num_blocks()) {
303        ifunc()->setPrevBlocksUnresolvedCF(ifunc()->num_blocks());
304        // A block has unresolved control flow if it has an indirect
305        // out-edge.
306        blocks(); // force initialization of all_blocks_
307        for (PatchFunction::Blockset::const_iterator iter = all_blocks_.begin(); 
308             iter != all_blocks_.end(); ++iter) 
309        {
310           block_instance* iblk = SCAST_BI(*iter);
311           if (iblk->llb()->unresolvedCF()) {
312              unresolvedCF_.insert(iblk);
313          }
314       }
315    }
316    return unresolvedCF_;
317 }
318
319 const func_instance::BlockSet &func_instance::abruptEnds() {
320     if (prevBlocksAbruptEnds_ != ifunc()->num_blocks()) {
321        prevBlocksAbruptEnds_ = blocks().size();
322         for (PatchFunction::Blockset::const_iterator iter = all_blocks_.begin(); 
323              iter != all_blocks_.end(); ++iter) 
324         {
325             block_instance* iblk = SCAST_BI(*iter);
326             if (iblk->llb()->abruptEnd()) {
327                 abruptEnds_.insert(iblk);
328             }
329         }
330     }
331     return abruptEnds_;
332 }
333
334 void func_instance::removeAbruptEnd(const block_instance *block)
335 {
336     if (abruptEnds_.empty()) {
337         return;
338     }
339
340     BlockSet::iterator bit = abruptEnds_.find(const_cast<block_instance*>(block));
341     if (abruptEnds_.end() != bit) {
342         abruptEnds_.erase(bit);
343     }
344 }
345
346
347 block_instance *func_instance::entryBlock() {
348   return SCAST_BI(entry());
349 }
350
351 unsigned func_instance::getNumDynamicCalls()
352 {
353    unsigned count=0;
354    for (PatchFunction::Blockset::const_iterator iter = callBlocks().begin(); 
355         iter != callBlocks().end(); ++iter) 
356    {
357       block_instance* iblk = SCAST_BI(*iter);
358       if (iblk->containsDynamicCall()) {
359          count++;
360       }
361    }
362    return count;
363 }
364
365
366 // warning: doesn't (and can't) force initialization of lazily-built 
367 // data structures because this function is declared to be constant
368 void func_instance::debugPrint() const {
369     fprintf(stderr, "Function debug dump (%p):\n", this);
370     fprintf(stderr, "  Symbol table names:\n");
371     for (auto i = symtab_names_begin(); 
372          i != symtab_names_end(); ++i) {
373       fprintf(stderr, "    %s\n", i->c_str());
374     }
375     fprintf(stderr, "  Demangled names:\n");
376     for (auto j = pretty_names_begin(); 
377          j != pretty_names_end(); ++j) {
378       fprintf(stderr, "    %s\n", j->c_str());
379     }
380     fprintf(stderr, "  Typed names:\n");
381     for (auto k = typed_names_begin(); 
382          k != typed_names_end(); ++k) {
383       fprintf(stderr, "    %s\n", k->c_str());
384     }
385     fprintf(stderr, "  Address: 0x%lx\n", addr());
386     fprintf(stderr, "  Internal pointer: %p\n", ifunc());
387     fprintf(stderr, "  Object: %s (%p), module: %s (%p)\n",
388             obj()->fileName().c_str(),
389             obj(),
390             mod()->fileName().c_str(),
391             mod());
392     for (Blockset::const_iterator
393          cb = all_blocks_.begin();
394          cb != all_blocks_.end();
395          cb++)
396     {
397         block_instance* orig = SCAST_BI(*cb);
398         fprintf(stderr, "  Block start 0x%lx, end 0x%lx\n", orig->start(),
399                 orig->end());
400     }
401 }
402
403 // Add to internal
404 // Add to mapped_object if a "new" name (true return from internal)
405 void func_instance::addSymTabName(const std::string name, bool isPrimary) {
406     if (ifunc()->addSymTabName(name, isPrimary))
407        obj()->addFunctionName(this, name, obj()->allFunctionsByMangledName);
408 }
409
410 void func_instance::addPrettyName(const std::string name, bool isPrimary) {
411     if (ifunc()->addPrettyName(name, isPrimary))
412        obj()->addFunctionName(this, name, obj()->allFunctionsByPrettyName);
413 }
414
415 // Dig down to the low-level block of b, find the low-level functions
416 // that share it, and map up to int-level functions and add them
417 // to the funcs list.
418 bool func_instance::getSharingFuncs(block_instance *b,
419                                    std::set<func_instance *> & funcs)
420 {
421     bool ret = false;
422
423     vector<Function *> lfuncs;
424     b->llb()->getFuncs(lfuncs);
425     vector<Function *>::iterator fit = lfuncs.begin();
426     for( ; fit != lfuncs.end(); ++fit) {
427       parse_func *ll_func = SCAST_PF(*fit);
428         func_instance *hl_func = obj()->findFunction(ll_func);
429         assert(hl_func);
430
431         if (hl_func == this) continue;
432
433         if (funcs.find(hl_func) == funcs.end()) ret = true;
434         funcs.insert(hl_func);
435     }
436
437     return ret;
438 }
439
440 // Find sharing functions via checking all basic blocks. We might be
441 // able to check only exit points; but we definitely need to check _all_
442 // exits so for now we're checking everything.
443
444 bool func_instance::getSharingFuncs(std::set<func_instance *> &funcs) {
445     bool ret = false;
446
447     // Create the block list.
448     PatchFunction::Blockset::const_iterator bIter;
449     for (bIter = blocks().begin();
450          bIter != blocks().end();
451          bIter++) {
452       block_instance* iblk = SCAST_BI(*bIter);
453        if (getSharingFuncs(iblk,funcs))
454           ret = true;
455     }
456
457     return ret;
458 }
459
460 bool func_instance::getOverlappingFuncs(block_instance *block,
461                                        std::set<func_instance *> &funcs)
462 {
463         ParseAPI::Block *llB = block->llb();
464         std::set<ParseAPI::Block *> overlappingBlocks;
465         for (Address i = llB->start(); i < llB->end(); ++i) {
466                 llB->obj()->findBlocks(llB->region(), i, overlappingBlocks);
467         }
468         // We now have all of the overlapping ParseAPI blocks. Get the set of
469         // ParseAPI::Functions containing each and up-map to func_instances
470         for (std::set<ParseAPI::Block *>::iterator iter = overlappingBlocks.begin();
471                 iter != overlappingBlocks.end(); ++iter) {
472                 std::vector<ParseAPI::Function *> llFuncs;
473                 (*iter)->getFuncs(llFuncs);
474                 for (std::vector<ParseAPI::Function *>::iterator iter2 = llFuncs.begin();
475                      iter2 != llFuncs.end(); ++iter2)  {
476                    funcs.insert(obj()->findFunction(*iter2));
477                 }
478         }
479         return (funcs.size() > 1);
480 }
481
482 bool func_instance::getOverlappingFuncs(std::set<func_instance *> &funcs)
483 {
484     bool ret = false;
485
486     // Create the block list.
487     PatchFunction::Blockset::const_iterator bIter;
488     for (bIter = blocks().begin();
489          bIter != blocks().end();
490          bIter++) {
491       block_instance* iblk = SCAST_BI(*bIter);
492        if (getOverlappingFuncs(iblk,funcs))
493           ret = true;
494     }
495
496     return ret;
497 }
498
499 std::string func_instance::get_name() const
500 {
501    return symTabName();
502 }
503
504 Offset func_instance::addrToOffset(const Address a) const {
505    return a - (addr() - ifunc()->getOffset());
506 }
507
508 const pdvector< int_parRegion* > &func_instance::parRegions()
509 {
510   if (parallelRegions_.size() > 0)
511     return parallelRegions_;
512
513   for (unsigned int i = 0; i < ifunc()->parRegions().size(); i++)
514     {
515       image_parRegion * imPR = ifunc()->parRegions()[i];
516       //int_parRegion * iPR = new int_parRegion(imPR, baseAddr, this);
517       int_parRegion * iPR = new int_parRegion(imPR, addr_, this);
518       parallelRegions_.push_back(iPR);
519     }
520   return parallelRegions_;
521 }
522
523 bool func_instance::consistency() const {
524    // 1) Check for 1:1 block relationship in
525    //    the block list and block map
526    // 2) Check that all instPoints are in the
527    //    correct block.
528
529    auto img_blocks = ifunc()->blocks();
530    assert(ifunc()->num_blocks() == all_blocks_.size());
531    for (auto iter = img_blocks.begin();
532         iter != img_blocks.end(); ++iter) {
533       parse_block *img_block = SCAST_PB(*iter);
534       block_instance *b_inst = obj()->findBlock(img_block);
535       assert(b_inst->llb() == img_block);
536    }
537
538    return true;
539 }
540
541 void func_instance::triggerModified() {
542     // KEVINTODO: is there anything to do here? 
543 }
544
545 Address func_instance::get_address() const { assert(0); return 0; }
546 unsigned func_instance::get_size() const { assert(0); return 0; }
547
548
549 bool func_instance::isInstrumentable() {
550 #if defined(os_freebsd)
551   // FreeBSD system call wrappers are using an indirect jump to an error
552   // handling function; this confuses our parsing and we conclude they
553   // are uninstrumentable. They're not. It's fine. 
554   
555   std::string wrapper_prefix = "__sys_";
556   for(auto i = symtab_names_begin(); i != symtab_names_end(); ++i) 
557   {
558     if (i->compare(0, 6, wrapper_prefix) == 0) {
559       return true;
560     }
561   }
562 #endif
563
564   Dyninst::PatchAPI::Instrumenter* inst = proc()->mgr()->instrumenter();
565   if (inst) return inst->isInstrumentable(this);
566   cerr << "Error: no instrumenter for " << symTabName() << endl;
567   return false;
568 }
569
570 block_instance *func_instance::getBlockByEntry(const Address addr) {
571    block_instance *block = obj()->findBlockByEntry(addr);
572    if (block) {
573       blocks(); // force initialization of all_blocks_
574       if (all_blocks_.find(block) != all_blocks_.end()) {
575          return block;
576       }
577    }
578    return NULL;
579 }
580
581
582 // get all blocks that have an instruction starting at addr, or if 
583 // there are none, return all blocks containing addr
584 bool func_instance::getBlocks(const Address addr, set<block_instance*> &blks) {
585    set<block_instance*> objblks;
586    obj()->findBlocksByAddr(addr, objblks);
587    blocks(); // ensure that all_blocks_ is filled in 
588    std::vector<std::set<block_instance *>::iterator> to_erase; 
589    for (set<block_instance*>::iterator bit = objblks.begin(); bit != objblks.end(); bit++) {
590       // Make sure it's one of ours
591       if (all_blocks_.find(*bit) == all_blocks_.end()) {
592          to_erase.push_back(bit);
593       }
594    }
595    for (unsigned i = 0; i < to_erase.size(); ++i) {
596       objblks.erase(to_erase[i]);
597    }
598
599    if (objblks.size() > 1) { 
600       // only add blocks that have an instruction at "addr"
601       for (set<block_instance*>::iterator bit = objblks.begin(); bit != objblks.end(); bit++) {
602          if ((*bit)->getInsn(addr)) {
603             blks.insert(*bit);
604          }
605       }
606    }
607    // if there are no blocks containing an instruction that starts at addr, 
608    // but there are blocks that contain addr, add those to blks
609    if (blks.empty() && !objblks.empty()) {
610       std::copy(objblks.begin(), objblks.end(), std::inserter(blks, blks.end()));
611    }
612    return ! blks.empty();
613 }
614
615 block_instance *func_instance::getBlock(const Address addr) {
616    std::set<block_instance *> blks;
617    getBlocks(addr, blks);
618    for (std::set<block_instance *>::iterator iter = blks.begin(); iter != blks.end(); ++iter) {
619       if ((*iter)->getInsn(addr)) return *iter;
620    }
621    return NULL;
622 }
623
624 using namespace SymtabAPI;
625
626 bool func_instance::addSymbolsForCopy() {
627    // Not implemented for dynamic mode
628    if (proc()->proc()) return false;
629    // And not implemented for same-module
630
631    // Get the old symbol
632    Symbol *oldsym = getRelocSymbol();
633
634    // Get the new symbol
635    Symbol *wrapperSym = getWrapperSymbol();
636    if (!wrapperSym) {
637       return false;
638    }
639    // Now we split. If this is a static binary, we want to point all the relocations
640    // in this function at the new symbol. If it's a dynamic binary, we can just relocate
641    // the daylights out of it.
642    if (obj()->isStaticExec()) {
643       proc()->edit()->addDyninstSymbol(wrapperSym_);
644       if (!updateRelocationsToSym(oldsym, wrapperSym)) return false;
645    }
646    else {
647       // I think we just add this to the dynamic symbol table...
648       wrapperSym->setDynamic(true);
649       proc()->edit()->addDyninstSymbol(wrapperSym_);
650    }
651
652    return true;
653 }
654
655 bool func_instance::updateRelocationsToSym(Symbol *oldsym, Symbol *newsym) {
656    for (Blockset::const_iterator iter = blocks().begin();
657         iter != blocks().end(); ++iter) {
658       obj()->parse_img()->getObject()->updateRelocations((*iter)->start(), (*iter)->last(), oldsym, newsym);
659    }
660    return true;
661 }
662
663 Symbol *func_instance::getWrapperSymbol() {
664    // Is created during relocation, which should have
665    // already happened.
666    return wrapperSym_;
667 }
668
669 Symbol *func_instance::getRelocSymbol() {
670    // there should be only one...
671    // HIGHLANDER!
672
673    // find the Symbol corresponding to the func_instance
674    std::vector<Symbol *> syms;
675    ifunc()->func()->getSymbols(syms);
676
677    if (syms.size() == 0) {
678       char msg[256];
679       sprintf(msg, "%s[%d]:  internal error:  cannot find symbol %s"
680               , __FILE__, __LINE__, name().c_str());
681       showErrorCallback(80, msg);
682       assert(0);
683    }
684
685    // try to find a dynamic symbol
686    // (take first static symbol if none are found)
687    Symbol *referring = syms[0];
688    for (unsigned k=0; k<syms.size(); k++) {
689       if (syms[k]->isInDynSymtab()) {
690          referring = syms[k];
691          break;
692       }
693    }
694    return referring;
695 }
696
697 void func_instance::createWrapperSymbol(Address entry, std::string name) {
698    if (wrapperSym_) {
699       // Just update the address
700       wrapperSym_->setOffset(entry);
701       return;
702    }
703    // Otherwise we need to create a new symbol
704    wrapperSym_ = new Symbol(name,
705                             Symbol::ST_FUNCTION,
706                             Symbol::SL_GLOBAL,
707                             Symbol::SV_DEFAULT,
708                             entry,
709                             NULL, // This is module - I probably want this?
710                             NULL, // Region - again, find it?
711                             0, // size - zero okay?
712                             false, // Definitely not dynamic ("Static binaries don't have dynamic symbols - Dan")
713                             false); // Definitely not absolute
714
715 }
716
717 /* PatchAPI stuffs */
718
719 instPoint *func_instance::funcEntryPoint(bool create) {
720    // Lookup the cached points
721    instPoint *p = IPCONV(proc()->mgr()->findPoint(Location::Function(this), Point::FuncEntry, create));
722    return p;
723 }
724
725 instPoint *func_instance::funcExitPoint(block_instance* b, bool create) {
726    instPoint *p = IPCONV(proc()->mgr()->findPoint(Location::ExitSite(this, b), Point::FuncExit, create));
727    return p;
728 }
729
730 void func_instance::funcExitPoints(Points* pts) {
731   std::vector<Point*> points;
732   proc()->mgr()->findPoints(Scope(this), Point::FuncExit, back_inserter(points));
733   for (std::vector<Point*>::iterator pi = points.begin(); pi != points.end(); pi++) {
734     instPoint* p = IPCONV(*pi);
735     pts->push_back(p);
736     assert(p->block());
737   }
738 }
739
740 instPoint *func_instance::preCallPoint(block_instance* b, bool create) {
741    instPoint *p = IPCONV(proc()->mgr()->findPoint(Location::CallSite(this, b), Point::PreCall, create));
742   return p;
743 }
744
745 instPoint *func_instance::postCallPoint(block_instance* b, bool create) {
746    instPoint *p = IPCONV(proc()->mgr()->findPoint(Location::CallSite(this, b), Point::PostCall, create));
747    return p;
748 }
749
750 void func_instance::callPoints(Points* pts) {
751   std::vector<Point*> points;
752   proc()->mgr()->findPoints(Scope(this), Point::PreCall|Point::PostCall, back_inserter(points));
753   for (std::vector<Point*>::iterator pi = points.begin(); pi != points.end(); pi++) {
754      instPoint* p = static_cast<instPoint*>(*pi);
755      pts->push_back(p);
756   }
757 }
758
759 instPoint *func_instance::blockEntryPoint(block_instance* b, bool create) {
760    instPoint *p = IPCONV(proc()->mgr()->findPoint(Location::BlockInstance(this, b), Point::BlockEntry, create));
761    return p;
762 }
763
764 instPoint *func_instance::blockExitPoint(block_instance* b, bool create) {
765    instPoint *p = IPCONV(proc()->mgr()->findPoint(Location::BlockInstance(this, b), Point::BlockExit, create));
766    return p;
767 }
768
769 instPoint *func_instance::preInsnPoint(block_instance* b, Address a,
770                                        InstructionAPI::Instruction::Ptr ptr,
771                                        bool trusted, bool create) {
772    Location loc = Location::InstructionInstance(this, b, a, ptr, trusted);
773
774    instPoint *p = IPCONV(proc()->mgr()->findPoint(loc, Point::PreInsn, create));
775    return p;
776 }
777
778 instPoint *func_instance::postInsnPoint(block_instance* b, Address a,
779                                         InstructionAPI::Instruction::Ptr ptr,
780                                         bool trusted, bool create) {
781    Location loc = Location::InstructionInstance(this, b, a, ptr, trusted);
782
783    instPoint *p = IPCONV(proc()->mgr()->findPoint(loc, Point::PostInsn, create));
784    return p;
785 }
786
787 void func_instance::blockInsnPoints(block_instance* b, Points* pts) {
788   std::vector<Point*> points;
789   proc()->mgr()->findPoints(Scope(this, b), Point::PreInsn|Point::PostInsn, back_inserter(points));
790   assert(points.size() > 0);
791   for (std::vector<Point*>::iterator i = points.begin(); i != points.end(); i++) {
792     instPoint* pt = static_cast<instPoint*>(*i);
793     pts->push_back(pt);
794   }
795 }
796
797 instPoint* func_instance::edgePoint(edge_instance* e, bool create) {
798    instPoint *p = IPCONV(proc()->mgr()->findPoint(Location::EdgeInstance(this, e), Point::EdgeDuring, create));
799    return p;
800 }
801
802 void func_instance::edgePoints(Points* pts) {
803    std::vector<Point *> points;
804    proc()->mgr()->findPoints(Scope(this), Point::EdgeDuring, back_inserter(points));
805    for (std::vector<Point*>::iterator i = points.begin(); i != points.end(); i++) {
806       instPoint* pt = static_cast<instPoint*>(*i);
807       pts->push_back(pt);
808    }
809 }
810
811
812 void func_instance::removeBlock(block_instance *block) {
813     // Put things here that go away from the perspective of this function
814     BlockSet::iterator bit = unresolvedCF_.find(block);
815     if (bit != unresolvedCF_.end()) {
816         unresolvedCF_.erase(bit);
817         size_t prev = ifunc()->getPrevBlocksUnresolvedCF();
818         if (prev > 0) {
819            ifunc()->setPrevBlocksUnresolvedCF(prev - 1);
820         }
821     }
822     bit = abruptEnds_.find(block);
823     if (bit != abruptEnds_.end()) {
824         abruptEnds_.erase(block);
825         if (prevBlocksAbruptEnds_ > 0) {
826            prevBlocksAbruptEnds_ --;
827         }
828     }
829 }
830
831 void func_instance::destroy(func_instance *f) {
832    // Put things here that go away when we destroy this function
833    delete f;
834 }
835
836 void func_instance::split_block_cb(block_instance *b1, block_instance *b2)
837 {
838
839     BlockSet::iterator bit = unresolvedCF_.find(b1);
840     if (bit != unresolvedCF_.end()) {
841         unresolvedCF_.erase(*bit);
842         unresolvedCF_.insert(b2);
843     }
844     bit = abruptEnds_.find(b1);
845     if (bit != abruptEnds_.end()) {
846         abruptEnds_.erase(*bit);
847         abruptEnds_.insert(b2);
848     }
849 }
850
851 void func_instance::add_block_cb(block_instance * /*block*/)
852 {
853 #if 0 // KEVINTODO: eliminate this?  as presently constituted, 
854       // these if cases will never execute anyway, at least not 
855       // when we intend them to
856     if (block->llb()->unresolvedCF()) {
857        size_t prev = ifunc()->getPrevBlocksUnresolvedCF();
858        if (ifunc()->blocks().size() == prev) {
859           unresolvedCF_.insert(block);
860           ifunc()->setPrevBlocksUnresolvedCF(prev+1);
861        }
862     }
863     if (block->llb()->abruptEnd() && 
864         prevBlocksAbruptEnds_ == ifunc()->blocks().size())
865     {
866         abruptEnds_.insert(block);
867         prevBlocksAbruptEnds_ ++;
868     }
869 #endif
870 }
871
872 void func_instance::markModified() {
873    proc()->addModifiedFunction(this);
874 }
875
876 // get caller blocks that aren't in deadBlocks
877 bool func_instance::getLiveCallerBlocks
878 (const std::set<block_instance*> &deadBlocks, 
879  const std::list<func_instance*> &deadFuncs, 
880  std::map<Address,vector<block_instance*> > & stubs)  // output: block + target addr
881 {
882    using namespace ParseAPI;
883
884    const PatchBlock::edgelist &callEdges = entryBlock()->sources();
885    PatchBlock::edgelist::const_iterator eit = callEdges.begin();
886    for( ; eit != callEdges.end(); ++eit) {
887       if (CALL == (*eit)->type()) {// includes tail calls
888           block_instance *cbbi = static_cast<block_instance*>((*eit)->src());
889           if (deadBlocks.end() != deadBlocks.find(cbbi)) {
890              continue; 
891           }
892
893           // don't use stub if it only appears in dead functions 
894           std::set<func_instance*> bfuncs;
895           cbbi->getFuncs(std::inserter(bfuncs,bfuncs.end()));
896           bool allSrcFuncsDead = true;
897           for (std::set<func_instance*>::iterator bfit = bfuncs.begin();
898                bfit != bfuncs.end(); 
899                bfit++) 
900           {
901              bool isSrcFuncDead = false;
902              for (std::list<func_instance*>::const_iterator dfit = deadFuncs.begin();
903                   dfit != deadFuncs.end();
904                   dfit++)
905              {
906                 if (*bfit == *dfit) {
907                    isSrcFuncDead = true;
908                    break;
909                 }
910              }
911              if (!isSrcFuncDead) {
912                 allSrcFuncsDead = false;
913                 break;
914              }
915           }
916           if (allSrcFuncsDead) {
917              continue; 
918           }
919           // add stub
920           stubs[addr()].push_back(cbbi);
921       }
922    }
923    return stubs.end() != stubs.find(addr()) && !stubs[addr()].empty();
924 }
925
926 #if defined(cap_stack_mods)
927 // Stack modifications
928 void func_instance::addMod(StackMod* mod, TMap* tMap)
929 {
930     _modifications->insert(mod);
931
932     // Update the transformation mapping
933     createTMap_internal(mod, tMap);
934 }
935
936 void func_instance::removeMod(StackMod* mod)
937 {
938     _modifications->erase(mod);
939 }
940
941 void func_instance::printMods() const
942 {
943     stackmods_printf("Modifications for %s\n", prettyName().c_str());
944     for (auto modIter = _modifications->begin(); modIter != _modifications->end(); ++modIter) {
945         StackMod* mod = *modIter;
946         stackmods_printf("\t %s\n", mod->format().c_str());
947     }
948 }
949
950 Accesses* func_instance::getAccesses(Address addr)
951 {
952     if (!_processedOffsetVector) {
953         createOffsetVector();
954     }
955     auto found = _accessMap->find(addr);
956     if (found != _accessMap->end()) {
957         return found->second;
958     } else {
959         return NULL;
960     }
961 }
962
963 bool func_instance::createOffsetVector()
964 {
965     if (_processedOffsetVector) {
966         return _validOffsetVector;
967     }
968
969     bool ret = true;
970
971     stackmods_printf("createOffsetVector for %s\n", prettyName().c_str());
972
973     // 2-tiered approach:
974     //      1. If symbols (DWARF, PDB), use this
975     //          Need to get BPatch_localVar info from the BPatch_function
976     //      2. Derive from instructions (even with symbols, check for consistency)
977
978     // Use symbols to update the offset vector
979     if (!createOffsetVector_Symbols()) {
980         ret = false;
981     }
982
983     // Use binary analysis to update offset vector
984     stackmods_printf("\t using analysis:\n");
985     ParseAPI::Function* func = ifunc();
986     const ParseAPI::Function::blocklist& blocks = func->blocks();
987     for (auto blockIter = blocks.begin(); blockIter != blocks.end(); ++blockIter) {
988         if (!ret) break;
989         ParseAPI::Block* block = *blockIter;
990         ParseAPI::Block::Insns insns;
991         block->getInsns(insns);
992
993         for (auto insnIter = insns.begin(); insnIter != insns.end(); ++insnIter) {
994             Address addr = (*insnIter).first;
995             InstructionAPI::Instruction::Ptr insn = (*insnIter).second;
996             if (!createOffsetVector_Analysis(func, block, insn, addr)) {
997                 ret = false;
998                 break;
999             }
1000         }
1001     }
1002
1003     // Populate offset vector
1004     for (auto iter = _tmpObjects->begin(); iter != _tmpObjects->end(); ++iter) {
1005         if (!addToOffsetVector((*iter).offset(), (*iter).size(), (*iter).type(), false, (*iter).valid())) {
1006             stackmods_printf("INVALID: addToOffsetVector failed (5)\n");
1007             ret = false;
1008         }
1009     }
1010
1011     _processedOffsetVector = true;
1012     if (ret) {
1013         _validOffsetVector = true;
1014         stackmods_printf("Function %s has FINE OFFSET VECTOR\n", prettyName().c_str());
1015     } else {
1016         _validOffsetVector = false;
1017         stackmods_printf("Function %s has INCONSISTENT OFFSET VECTOR (FUNCTION WILL BE SKIPPED)\n",  prettyName().c_str());
1018     }
1019
1020     delete _tmpObjects;
1021     _tmpObjects = NULL;
1022
1023     return ret;
1024 }
1025
1026 static int randomNumGenerator (int i) { return std::rand()%i; }
1027
1028 static bool matchRanges(ValidPCRange* a, ValidPCRange* b)
1029 {
1030     auto aIter = a->begin();
1031     auto bIter = b->begin();
1032
1033     while ( (aIter != a->end()) && (bIter != b->end())) {
1034         if ( ((*aIter).first == (*bIter).first) && ((*aIter).second.first == (*aIter).second.first)) {
1035             aIter++;
1036             bIter++;
1037         } else {
1038             return false;
1039         }
1040     }
1041     return true;
1042 }
1043
1044 bool func_instance::randomize(TMap* tMap, bool seeded, int seed)
1045 {
1046     if (seeded) {
1047         _seeded = true;
1048         _seed = seed;
1049     }
1050
1051     if (_seeded) {
1052         stackmods_printf("randomize: using seed %d\n", _seed);
1053         srand(_seed);
1054     } else {
1055         stackmods_printf("randomize: using NULL seed\n");
1056         srand(unsigned(time(NULL)));
1057     }
1058
1059     // Grab the locals
1060     // Find the lowest in offVec that's not a StackAccess::REGHEIGHT
1061     bool foundBottom = false;
1062
1063     IntervalTree<OffsetVector::K,OffsetVector::V> stack = _offVec->stack();
1064
1065     if (stack.empty()) {
1066         stackmods_printf("\t no stack variables to randomize\n");
1067         return false;
1068     }
1069
1070     StackAnalysis::Height curLB = stack.lowest();
1071     IntervalTree<StackAnalysis::Height, int> localsRanges;
1072     map<int, vector<StackLocation*> > locals;
1073
1074     Architecture arch = ifunc()->isrc()->getArch();
1075     int raLoc;
1076     if (arch == Arch_x86_64) {
1077         raLoc = -8;
1078     } else if (arch == Arch_x86) {
1079         raLoc = -4;
1080     } else {
1081         assert(0);
1082     }
1083     StackLocation* curLoc;
1084     int counter = -1;
1085     for (auto iter = stack.begin(); iter != stack.end(); ) {
1086         curLoc = (*iter).second.second;
1087         while ( /* Stop at the end */
1088                 (iter != stack.end()) &&
1089                 /* Stop at/above the RA (i.e., in the caller) */
1090                 (curLoc->off() < raLoc) &&
1091                 (curLoc->off()+curLoc->size() < raLoc) &&
1092                 /* Skip non-debug */
1093                 ((curLoc->type() != StackAccess::DEBUGINFO_LOCAL) && (curLoc->type() != StackAccess::DEBUGINFO_PARAM))) {
1094             ++iter;
1095             if (iter == stack.end()) {
1096                 break;
1097             }
1098             curLoc = (*iter).second.second;
1099
1100             // Start a new range
1101             curLB = curLoc->off();
1102         }
1103
1104         // Want to always create *contiguous* ranges
1105         curLB = curLoc->off()-1;
1106
1107         // Bail if we've reached the end of the stack objects, or gone above the RA
1108         if ( (iter == stack.end()) || (curLoc->off() >= raLoc) ) {
1109             break;
1110         }
1111
1112         if ((curLoc->type() != StackAccess::DEBUGINFO_LOCAL) && (curLoc->type() != StackAccess::DEBUGINFO_PARAM)) {
1113             break;
1114         }
1115
1116         if (!foundBottom) {
1117             foundBottom = true;
1118         }
1119
1120         StackAnalysis::Height lb, ub;
1121         int tmp;
1122         if (localsRanges.find(curLB, lb, ub, tmp) && matchRanges(locals.at(counter).back()->valid(), curLoc->valid())) {
1123             // If there already exists a range for the current LB, update
1124             localsRanges.update(lb, max(ub, curLoc->off() + curLoc->size()));
1125             stackmods_printf("%s in range %d\n", curLoc->format().c_str(), counter);
1126             locals.at(counter).push_back(curLoc);
1127         } else {
1128             // Otherwise, start a new range
1129             counter++;
1130             curLB = curLoc->off();
1131             localsRanges.insert(curLoc->off(), curLoc->off() + curLoc->size(), counter);
1132             stackmods_printf("%s in range %d\n", curLoc->format().c_str(), counter);
1133             vector<StackLocation*> nextvec;
1134             locals.insert(make_pair(counter, nextvec));
1135             locals.at(counter).push_back(curLoc);
1136         }
1137         ++iter;
1138     }
1139
1140     if (locals.size() == 0) {
1141         stackmods_printf("\t no locals to randomize\n");
1142         return false;
1143     }
1144
1145     bool randomizedRange = false;
1146
1147     stackmods_printf("Found locals ranges:\n");
1148     for (auto iter = localsRanges.begin(); iter != localsRanges.end(); ++iter) {
1149         stackmods_printf("\t %d: [%ld, %ld)\n", (*iter).second.second, (*iter).first.height(), (*iter).second.first.height());
1150         vector<StackLocation*> vec = locals.at((*iter).second.second);
1151         for (auto viter = vec.begin(); viter != vec.end(); ++viter) {
1152             stackmods_printf("\t\t %s\n", (*viter)->format().c_str());
1153         }
1154         if (vec.size() == 1) {
1155             stackmods_printf("\t skipping range %d: [%ld, %ld), only one local\n", (*iter).second.second, (*iter).first.height(), (*iter).second.first.height());
1156             continue;
1157         }
1158
1159         randomizedRange = true;
1160         std::random_shuffle(vec.begin(), vec.end(), randomNumGenerator);
1161         StackAnalysis::Height nextLoc = (*iter).first.height();
1162
1163         for (auto viter = vec.begin(); viter != vec.end(); ++viter) {
1164             StackLocation* cur = *viter;
1165             Move* tmp = new Move(cur->off().height(), cur->off().height()+cur->size(), nextLoc.height());
1166             addMod(tmp, tMap);
1167             nextLoc += cur->size();
1168         }
1169     }
1170
1171     if (randomizedRange) {
1172         stackmods_printf("\t After randomize:\n");
1173         printMods();
1174     }
1175
1176     _randomizeStackFrame = true;
1177
1178     return randomizedRange;
1179 }
1180
1181 bool func_instance::createOffsetVector_Symbols()
1182 {
1183     bool ret = true;
1184
1185     if (_vars.size() == 0 && _params.size() == 0) {
1186         // No DWARF or no locals
1187         // Is there another way to check for DWARF?
1188         stackmods_printf("\t No symbols\n");
1189         return ret;
1190     }
1191
1192     stackmods_printf("\t using symbols:\n");
1193     _hasDebugSymbols = true;
1194
1195     // Calculate base pointer height for locals; the frame offset is relative to this
1196     int width;
1197     Architecture arch = ifunc()->isrc()->getArch();
1198     if (arch == Arch_x86) { width = 4; }
1199     else if (arch == Arch_x86_64) { width = 8; }
1200     else { assert(0); }
1201     int base = -width;
1202     if (!ifunc()->hasNoStackFrame()) {
1203         base -= width; // account for BP save
1204     }
1205     MachRegister bp = MachRegister::getFramePointer(arch);
1206
1207     for (auto vIter = _vars.begin(); vIter != _vars.end(); ++vIter) {
1208         SymtabAPI::localVar* var = *vIter;
1209         vector<VariableLocation> locs = var->getLocationLists();
1210         if (locs.empty()) {
1211             continue;
1212         }
1213
1214         ValidPCRange* valid = new ValidPCRange();
1215
1216         bool found = false;
1217         long offset = 0;
1218         for (auto locIter = locs.begin(); locIter != locs.end(); ++locIter) {
1219             VariableLocation curLoc = *locIter;
1220             if (curLoc.mr_reg == MachRegister::getFramePointer(arch)) {
1221                 found = true;
1222                 valid->insert(curLoc.lowPC, curLoc.hiPC+1, 0);
1223                 offset = curLoc.frameOffsetAbs;
1224             }
1225         }
1226
1227         if (!found || !offset) {
1228             continue;
1229         }
1230
1231         stackmods_printf("\t\t\t Found %s (type %s) @ %ld, size = %d\n", var->getName().c_str(), var->getType()->getName().c_str(), offset, var->getType()->getSize());
1232         for (auto locIter = locs.begin(); locIter != locs.end(); ++locIter) {
1233             VariableLocation curLoc = *locIter;
1234             if (curLoc.mr_reg == MachRegister::getFramePointer(arch)) {
1235                 stackmods_printf("\t\t\t\t Range = [0x%lx, 0x%lx)\n", curLoc.lowPC, curLoc.hiPC);
1236             } else {
1237                 stackmods_printf("\t\t\t\t SKIPPED Range = [0x%lx, 0x%lx)\n", curLoc.lowPC, curLoc.hiPC);
1238             }
1239         }
1240
1241         StackAccess::StackAccessType sat = StackAccess::DEBUGINFO_LOCAL;
1242         if (var->getType()->getSize() == 0) {
1243             _tmpObjects->insert(tmpObject(offset, 4, sat, valid));
1244         } else {
1245             _tmpObjects->insert(tmpObject(offset, var->getType()->getSize(), sat, valid));
1246         }
1247     }
1248
1249     for (auto vIter = _params.begin(); vIter != _params.end(); ++vIter) {
1250         SymtabAPI::localVar* var = *vIter;
1251         vector<VariableLocation> locs = var->getLocationLists();
1252         if (locs.empty()) {
1253             continue;
1254         }
1255
1256         ValidPCRange* valid = new ValidPCRange();
1257
1258         bool found = false;
1259         long offset = 0;
1260         for (auto locIter = locs.begin(); locIter != locs.end(); ++locIter) {
1261             VariableLocation curLoc = *locIter;
1262             if (curLoc.mr_reg == MachRegister::getFramePointer(arch)) {
1263                 found = true;
1264                 valid->insert(curLoc.lowPC, curLoc.hiPC+1, 0);
1265                 offset = curLoc.frameOffsetAbs;
1266             }
1267         }
1268
1269         if (!found || !offset) {
1270             continue;
1271         }
1272
1273         stackmods_printf("\t\t\t Found %s (type %s) @ %ld, size = %d\n", var->getName().c_str(), var->getType()->getName().c_str(), offset, var->getType()->getSize());
1274
1275         for (auto locIter = locs.begin(); locIter != locs.end(); ++locIter) {
1276             VariableLocation curLoc = *locIter;
1277             if (curLoc.mr_reg == MachRegister::getFramePointer(arch)) {
1278                 stackmods_printf("\t\t\t\t Range = [0x%lx, 0x%lx)\n", curLoc.lowPC, curLoc.hiPC);
1279             } else {
1280                 stackmods_printf("\t\t\t\t SKIPPED Range = [0x%lx, 0x%lx)\n", curLoc.lowPC, curLoc.hiPC);
1281             }
1282         }
1283
1284         StackAccess::StackAccessType sat = StackAccess::DEBUGINFO_PARAM;
1285         if (var->getType()->getSize() == 0) {
1286             _tmpObjects->insert(tmpObject(offset, 4, sat, valid));
1287         } else {
1288             _tmpObjects->insert(tmpObject(offset, var->getType()->getSize(), sat, valid));
1289         }
1290     }
1291
1292     return ret;
1293 }
1294
1295
1296 bool func_instance::createOffsetVector_Analysis(ParseAPI::Function* func,
1297         ParseAPI::Block* block,
1298         InstructionAPI::Instruction::Ptr insn,
1299         Address addr)
1300 {
1301     bool ret = true;
1302
1303     stackmods_printf("\t Processing %lx: %s\n", addr, insn->format().c_str());
1304
1305     int accessSize = getAccessSize(insn);
1306     Accesses* accesses = new Accesses();
1307     assert(accesses);
1308     if (::getAccesses(func, block, addr, insn, accesses)) {
1309         _accessMap->insert(make_pair(addr, accesses));
1310
1311         for (auto accessIter = accesses->begin(); accessIter != accesses->end(); ++accessIter) {
1312             StackAccess* access = (*accessIter).second;
1313
1314             stackmods_printf("\t\t Processing %s, size %d\n", access->format().c_str(), accessSize);
1315
1316             if (access->disp()) {
1317                 if (access->skipReg()) {
1318                     stackmods_printf("\t\t\t Skipping (1).\n");
1319                     _offVec->addSkip(access->reg(), access->regHeight(), block->start(), addr);
1320                     // Skip
1321                     if (!addToOffsetVector(access->regHeight(), 1, StackAccess::REGHEIGHT, true, NULL, access->reg())) {
1322                         stackmods_printf("\t\t\t INVALID: addToOffsetVector failed (1)\n");
1323                         return false;
1324                     }
1325                 } else {
1326                     if (!addToOffsetVector(access->regHeight(), 1, StackAccess::REGHEIGHT, true, NULL, access->reg())) {
1327                         stackmods_printf("\t\t\t INVALID: addToOffsetVector failed (2)\n");
1328                         return false;
1329                     }
1330                 }
1331                 _tmpObjects->insert(tmpObject(access->readHeight().height(), accessSize, access->type()));
1332             } else {
1333                 if (access->skipReg()) {
1334                     _offVec->addSkip(access->reg(), access->regHeight(), block->start(), addr);
1335                     stackmods_printf("\t\t\t Skipping (2).\n");
1336                     if (!addToOffsetVector(access->regHeight(), 1, StackAccess::REGHEIGHT, true, NULL, access->reg())) {
1337                         stackmods_printf("\t\t\t INVALID: addToOffsetVector failed (3)\n");
1338                         return false;
1339                     }
1340                 } else {
1341                     if (!addToOffsetVector(access->regHeight(), 1, StackAccess::REGHEIGHT, true, NULL, access->reg())) {
1342                         stackmods_printf("\t\t\t INVALID: addToOffsetVector failed (4)\n");
1343                         return false;
1344                     }
1345                 }
1346                 _tmpObjects->insert(tmpObject(access->readHeight().height(), accessSize, access->type()));
1347             }
1348         }
1349     } else {
1350         stackmods_printf("\t\t\t INVALID: getAccesses failed\n");
1351         // Once we've found a bad access, stop looking!
1352         return false;
1353     }
1354
1355     return ret;
1356 }
1357
1358 bool func_instance::addToOffsetVector(StackAnalysis::Height off, int size, StackAccess::StackAccessType type, bool isRegisterHeight, ValidPCRange* valid, MachRegister reg)
1359 {
1360     bool ret = true;
1361
1362     bool skip_misunderstood = false;
1363
1364     if (isRegisterHeight) {
1365         StackLocation* existingLoc = NULL;
1366         if (_offVec->find(off, reg, existingLoc)) {
1367             if (existingLoc->isRegisterHeight() && existingLoc->reg() == reg) {
1368                 return ret;
1369             } else {
1370                 stackmods_printf("\t\t\t loc %s is not a match\n", existingLoc->format().c_str());
1371             }
1372         }
1373
1374         stackmods_printf("\t\t\t addToOffsetVector: added %s %d\n", StackAccess::printStackAccessType(type).c_str(), off.height());
1375         StackLocation* tmp = new StackLocation(off, type, reg);
1376         _offVec->insert(off, off+size, tmp, isRegisterHeight);
1377         return ret;
1378     }
1379
1380     if (size == 0) {
1381         stackmods_printf("\t\t\t addToOffsetVector: trying to add non-StackAccess::REGHEIGHT of size 0. Skipping.\n");
1382         return ret;
1383     }
1384
1385     bool found = false;
1386     stackmods_printf("\t\t\t Adding %ld, size %d, type %s\n", off.height(), size, StackAccess::printStackAccessType(type).c_str());
1387
1388     // If the access is inside the expected space for the return address, declare INCONSISTENT
1389     Architecture arch = ifunc()->isrc()->getArch();
1390     int raLoc;
1391     if (arch == Arch_x86_64) {
1392         raLoc = -8;
1393     } else if (arch == Arch_x86) {
1394         raLoc = -4;
1395     } else {
1396         assert(0);
1397     }
1398
1399     if ( ( (raLoc <= off.height()) && (off.height() < 0) ) ||
1400          ( (raLoc <  off.height() + size) && (off.height() + size <= 0) ) ||
1401          ( (off.height() < raLoc) && (off.height() + size > 0)) ) {
1402         stackmods_printf("\t\t\t\t This stack access interferes with the RA. We may be confused. Skipping.\n");
1403         if (isDebugType(type)) {
1404             // Silently skip; doesn't hurt--if there's an actual access, the others will catch it.
1405             // Okay to skip here because getAccesses won't return this one because it came from the DWARF.
1406             type = StackAccess::MISUNDERSTOOD;
1407         } else {
1408             return false;
1409         }
1410     }
1411
1412     StackAnalysis::Height lb, ub;
1413     StackLocation* existing;
1414     if (_offVec->find(off, lb, ub, existing)) {
1415         found = true;
1416         stackmods_printf("\t\t\t\t Found existing offset range %s\n", existing->format().c_str());
1417         if (lb == off) {
1418             int existingSize = existing->size();
1419             stackmods_printf("\t\t\t\t\t Existing has same lb.\n");
1420             if (size == existingSize) {
1421                 stackmods_printf("\t\t\t\t\t Existing has same size. Skip adding.\n");
1422                 // Merge intervals
1423                 if (isDebugType(type)) {
1424                     for (auto vIter = valid->begin(); vIter != valid->end(); ++vIter) {
1425                         existing->valid()->insert((*vIter).first, (*vIter).second.first, (*vIter).second.second);
1426                     }
1427                 }
1428             } else if (size < existingSize) {
1429                 stackmods_printf("\t\t\t\t\t Existing has larger size. Skip adding.\n");
1430             } else {
1431                 stackmods_printf("\t\t\t\t\t Existing has smaller size. Checking whether to update.\n");
1432                 bool skip = false;
1433
1434                 // Iterate through update offsets to make sure no conflict that overlaps or is contained in the region
1435                 for (int i = 0; i < size; i++) {
1436
1437                     StackAnalysis::Height lb2, ub2;
1438                     StackLocation* existing2;
1439                     // Is there an existing range at the potential update size?
1440                     if (_offVec->find(off+i, lb2, ub2, existing2)) {
1441
1442                         // If we find a different range at the potential update size, skip!
1443                         if (existing2 != existing) {
1444                             stackmods_printf("\t\t\t\t\t\t\t\t WARNING: updating size would conflict with different existing range.\n");
1445                             skip = true;
1446
1447                             if (skip_misunderstood) {
1448                                 ret = false;
1449                                 break;
1450                             } else {
1451                                 // We know the new one overlaps with existing
1452                                 existing->setType(StackAccess::MISUNDERSTOOD);
1453
1454                                 // But, it also overlaps with existing2
1455                                 existing2->setType(StackAccess::MISUNDERSTOOD);
1456
1457                                 StackLocation* tmp = new StackLocation(off, size, StackAccess::MISUNDERSTOOD, isRegisterHeight, valid);
1458                                 assert(tmp);
1459                                 _offVec->insert(off, off+size, tmp, isRegisterHeight);
1460                             }
1461                         }
1462                     }
1463                 }
1464
1465                 // Safe to update existing to a new larger size!
1466                 if (!skip) {
1467                     stackmods_printf("\t\t\t\t\t\t Updating size to %d. Added\n", size);
1468                     existing->setSize(size);
1469                     _offVec->update(existing->off(), existing->off() + existing->size());
1470                 }
1471             }
1472         } else if (lb < off && off < ub) {
1473             stackmods_printf("\t\t\t\t Found overlapping offset range (lb < off < ub): %s\n", existing->format().c_str());
1474
1475             int existingUpperBound = existing->off().height() + existing->size();
1476             int newUpperBound = off.height() + size;
1477
1478             if (existingUpperBound == newUpperBound) {
1479                 stackmods_printf("\t\t\t\t\t Existing and new upper bounds are the same. Skip adding.\n");
1480             } else if (existingUpperBound > newUpperBound) {
1481                 stackmods_printf("\t\t\t\t\t Existing upper bound is greater than what we're adding. Skip adding.\n");
1482             } else {
1483                 stackmods_printf("\t\t\t\t\t WARNING: conflict because existing upper bound is less than what we're adding.\n");
1484
1485                 // Goal: figure out what other range(s) we're in conflict with
1486                 if (skip_misunderstood) {
1487                     ret = false;
1488                 } else {
1489                     for (int i = 0; i < size; i++) {
1490                         StackAnalysis::Height lb2, ub2;
1491                         StackLocation* existing2;
1492                         if (_offVec->find(off+i, lb2, ub2, existing2)) {
1493                             if (existing2 != existing) {
1494                                 stackmods_printf("\t\t\t\t\t\t Range overlaps with another existing range %s\n", existing2->format().c_str());
1495                                 existing2->setType(StackAccess::MISUNDERSTOOD);
1496                             }
1497                         }
1498                     }
1499
1500                     // We know we're in conflict with the existing range, since lb != off
1501                     existing->setType(StackAccess::MISUNDERSTOOD);
1502
1503                     // Add new range as misunderstood
1504                     StackLocation* tmp = new StackLocation(off, size, StackAccess::MISUNDERSTOOD, isRegisterHeight, valid);
1505                     assert(tmp);
1506                     _offVec->insert(off, off+size, tmp, isRegisterHeight);
1507                 }
1508             }
1509         } else if (off == ub) {
1510             // Not a match! Adjacent ranges. Continue searching.
1511             found = false;
1512         } else {
1513             assert(0);
1514         }
1515     }
1516
1517     if (!found) {
1518             stackmods_printf("\t\t\t\t ... created new\n");
1519             StackLocation* tmp = new StackLocation(off, size, type, isRegisterHeight, valid);
1520             assert(tmp);
1521             _offVec->insert(off, off+size, tmp, isRegisterHeight);
1522     }
1523
1524     return ret;
1525 }
1526
1527 void func_instance::createTMap_internal(StackMod* mod, StackLocation* loc, TMap* tMap)
1528 {
1529     StackAnalysis::Height off = loc->off();
1530     StackAnalysis::Height size = loc->size();
1531     switch(mod->type()) {
1532         case(StackMod::INSERT): {
1533                           /* Model:
1534                            * o < d: o' = o + (c-d)
1535                            */
1536
1537                           Insert* insertMod = dynamic_cast<Insert*>(mod);
1538                           StackAnalysis::Height c(insertMod->low());
1539                           StackAnalysis::Height d(insertMod->high());
1540
1541                           if (!loc->isRegisterHeight()) {
1542                               if (off < d || off == d) {
1543                                   stackmods_printf("\t\t Processing interaction with %s\n", loc->format().c_str());
1544                                   int delta = c.height() - d.height();
1545                                 tMap->update(loc, delta);
1546                               }
1547                           } else {
1548                               if (off < d || off == d) {
1549                                   stackmods_printf("\t\t Processing interaction with %s\n", loc->format().c_str());
1550                                   int delta = c.height() - d.height();
1551                                   tMap->update(loc, delta);
1552                               }
1553                           }
1554                           break;
1555                       }
1556         case(StackMod::REMOVE): {
1557                           /* Model:
1558                            * O' = O - [c,d)
1559                            * o < d: o' = o - (c-d)
1560                            */
1561
1562                           Remove* removeMod = dynamic_cast<Remove*>(mod);
1563                           StackAnalysis::Height c(removeMod->low());
1564                           StackAnalysis::Height d(removeMod->high());
1565
1566                           // Remove existing element
1567                           if ((c == off || c < off) &&
1568                                   (off < c + (d-c))) {
1569                               stackmods_printf("\t\t Processing interaction with %s\n", loc->format().c_str());
1570                               StackLocation* tmp = new StackLocation();
1571                               tMap->insert(make_pair(loc, tmp));
1572                               stackmods_printf("\t\t Adding to tMap %s -> %s\n", loc->format().c_str(), tmp->format().c_str());
1573                           }
1574
1575                           // Shift other elements
1576                           if (off < d) {
1577                               stackmods_printf("\t\t Processing interaction with %s\n", loc->format().c_str());
1578                               int delta = d.height() - c.height();
1579                               tMap->update(loc, delta);
1580                           }
1581
1582
1583                           break;
1584                       }
1585         case(StackMod::MOVE): {
1586                         /* Model:
1587                          * o in [c,d): o' = o + (m-c)
1588                          */
1589
1590                         Move* moveMod = dynamic_cast<Move*>(mod);
1591                         StackAnalysis::Height c(moveMod->srcLow());
1592                         int size = moveMod->size();
1593
1594                         // Future: could check the DWARF and use the vailD PC range if we have one
1595                         ValidPCRange* valid = NULL;
1596                         StackLocation* found = NULL;
1597                         _offVec->find(c, found);
1598                         if (found) {
1599                             valid = found->valid();
1600                         }
1601
1602                         StackAnalysis::Height m(moveMod->destLow());
1603
1604                         if (    (c == off || c < off) &&
1605                                 (off < c+size) ) {
1606                             stackmods_printf("\t\t Processing interaction with %s\n", loc->format().c_str());
1607                             // This does not go through the updateTMap because it's a fixed change
1608                             StackLocation* src;
1609                             StackLocation* tmp;
1610                             if (loc->isRegisterHeight()) {
1611                                 src = new StackLocation(loc->off(), loc->type(), loc->reg(), valid);
1612                                 tmp = new StackLocation(off + (m-c), loc->type(), loc->reg(), valid);
1613                             } else {
1614                                 src = loc;
1615                                 tmp = new StackLocation(off + (m-c), size-(off.height()-c.height()), loc->type(), false, loc->valid());
1616                             }
1617                             auto res = tMap->insert(make_pair(src, tmp));
1618                             stackmods_printf("\t\t\t Adding to tMap: %s -> %s\n", loc->format().c_str(), tmp->format().c_str());
1619                             if (res.second) {
1620                                 stackmods_printf("\t\t\t\t Added.\n");
1621                             } else {
1622                                 stackmods_printf("\t\t\t\t Not added. Found  %s -> %s already existed\n", res.first->first->format().c_str(), res.first->second->format().c_str());
1623                             }
1624                             // Update size
1625                             loc->setSize(size - (off.height() - c.height()));
1626                         }
1627                         break;
1628                     }
1629         default:
1630                     assert(0 && "unknown modification type");
1631     }
1632 }
1633
1634 void func_instance::createTMap_internal(StackMod* mod, TMap* tMap)
1635 {
1636
1637     stackmods_printf("\t Processing %s\n", mod->format().c_str());
1638
1639     // Handle insert/add side effects
1640     if (mod->type() == StackMod::INSERT) {
1641         Insert* insertMod = dynamic_cast<Insert*>(mod);
1642         StackAnalysis::Height c(insertMod->low());
1643         StackAnalysis::Height d(insertMod->high());
1644         StackLocation* tmpSrc = new StackLocation();
1645         StackLocation* tmpDest = new StackLocation(c, (d-c).height(), StackAccess::UNKNOWN, false);
1646         tMap->insert(make_pair(tmpSrc, tmpDest));
1647         stackmods_printf("\t\t\t Adding to tMap: %s -> %s\n", tmpSrc->format().c_str(), tmpDest->format().c_str());
1648     }
1649
1650     if (!_offVec->stack().empty()) {
1651         IntervalTree<OffsetVector::K,OffsetVector::V> stack = _offVec->stack();
1652         for (auto offIter = stack.begin(); offIter != stack.end(); ++offIter) {
1653             StackLocation* loc = (*offIter).second.second;
1654             createTMap_internal(mod, loc, tMap);
1655         }
1656     }
1657     if (!_offVec->definedRegs().empty()) {
1658         std::map<MachRegister,IntervalTree<OffsetVector::K,OffsetVector::V> > definedRegs = _offVec->definedRegs();
1659         for (auto offIter = definedRegs.begin(); offIter != definedRegs.end(); ++offIter) {
1660             for (auto iter2 = (*offIter).second.begin(); iter2 != (*offIter).second.end(); ++iter2) {
1661                 createTMap_internal(mod, (*iter2).second.second, tMap);
1662             }
1663         }
1664     }
1665 }
1666
1667 AnnotationClass <StackAnalysis::Intervals> Stack_Anno(std::string("Stack_Anno"));
1668 void func_instance::freeStackMod() {
1669     // Free stack analysis intervals
1670     StackAnalysis::Intervals *tmp = NULL;
1671     ifunc()->getAnnotation(tmp, Stack_Anno);
1672     ifunc()->removeAnnotation(Stack_Anno);
1673     if (tmp != NULL) {
1674         delete tmp;
1675     }
1676 }
1677 #endif