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