Memory leak fixes and stopped tracking topped locations.
[dyninst.git] / dyninstAPI / src / StackMod / StackModChecker.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 #include "BPatch.h"
32 #include "BPatch_addressSpace.h"
33 #include "BPatch_flowGraph.h"
34 #include "BPatch_basicBlockLoop.h"
35 #include "BPatch_object.h"
36 #include "BPatch_point.h"
37
38 #if defined(arch_x86) || defined(arch_x86_64)
39 #include "inst-x86.h"
40 #elif defined(arch_power)
41 #include "inst-power.h"
42 #else
43 #error "Unknown architecture, expected x86, x86_64, or power"
44 #endif
45
46 #include "stackanalysis.h"
47
48 #include "debug.h"
49 #include "StackMod.h"
50 #include "StackModExpr.h"
51 #include "StackModChecker.h"
52
53
54 StackModChecker::~StackModChecker() {
55     // Free the height vectors in blockHeights
56     for (auto bhIter = blockHeights.begin(); bhIter != blockHeights.end();
57         bhIter++) {
58         delete bhIter->second;
59     }
60 }
61
62 /* Locate the libc-provided canary failure function __stack_chk_fail */
63 static BPatch_function* findCanaryFailureFunction(BPatch_image* image)
64 {
65     BPatch_function* failFunction = NULL;
66
67     /* Locate libc stack_chk_fail function for failure case */
68     std::vector<BPatch_object*> objects;
69     image->getObjects(objects);
70     if (!objects.size()) {
71         stackmods_printf("findCanaryFailureFunction: could not find any BPatch_objects\n");
72         return failFunction;
73     }
74
75     std::string name = "__stack_chk_fail";
76
77     for (auto iter = objects.begin(); iter != objects.end(); ++iter) {
78         BPatch_object* obj = *iter;
79
80         std::vector<BPatch_function*> funcs;
81         obj->findFunction(name, funcs, false);
82         if (funcs.size()) {
83             failFunction = funcs[0];
84             return failFunction;
85         }
86     }
87
88     return failFunction;
89 }
90
91 bool StackModChecker::addModsInternal(std::set<StackMod*> mods)
92 {
93     // Check architecture
94     Architecture arch = func->ifunc()->isrc()->getArch();
95     if ( (arch != Arch_x86) && (arch != Arch_x86_64)) {
96         stackmods_printf("Stack modifications only implemented for x86 and x86_64!\n");
97         return false;
98     }
99
100     if (!func->proc()->edit()) {
101         stackmods_printf("Stack modifications only implemented for binary rewriting mode\n");
102         return false;
103     }
104
105     if (func->hasRandomize()) {
106         stackmods_printf("RANDOMIZE has already been applied to this function; additional modifications not allowed\n");
107         return false;
108     }
109
110     stackmods_printf("addMods called with:\n");
111     for (auto iter = mods.begin(); iter != mods.end(); ++iter) {
112         stackmods_printf("\t %s\n", (*iter)->format().c_str());
113     }
114
115     if (!func->hasOffsetVector()) {
116         // Add DWARF information to the low-level function
117         BPatch_Vector<BPatch_localVar*>* params = bfunc->getParams();
118         for (auto iter = params->begin(); iter != params->end(); ++iter) {
119             BPatch_localVar* v = *iter;
120             if (v) {
121                 func->addParam(v->getSymtabVar());
122             }
123         }
124         BPatch_Vector<BPatch_localVar*>* vars  = bfunc->getVars();
125         for (auto iter = vars->begin(); iter != vars->end(); ++iter) {
126             BPatch_localVar* v = *iter;    
127             if (v) {
128                 func->addVar(v->getSymtabVar());
129             }
130         }
131
132         // Generate offset vector
133         // This only needs to happen once per function
134         func->createOffsetVector();
135     }
136
137     if (!func->hasValidOffsetVector()) {
138         // Function cannot be modified
139         stackmods_printf("Function %s cannot be modified, addMods returning false\n", getName().c_str());
140         func->freeStackMod();
141         return false;
142     }
143
144     // Create a local set to update
145     std::vector<StackMod*> allMods;
146
147     // Some modifications require a safety check to ensure that the stack only grows/shrinks once during the function
148     bool requiresCheckStackGrowth = false;
149
150     // Calculate any paired modification requirements (before alignment)
151     //      TODO: Good way to check if the user is doing this cleanup already?
152     //      Although canaries have 2 snippets, they don't require a second
153     //      modification to be added (but two snippets will be generated)
154     // Also check that modifications make sense
155     //      Only one canary modification per function
156     //      Randomize may not be used with any other modifications
157     for (auto iter = mods.begin(); iter != mods.end(); ++iter) {
158         StackMod* m = *iter;
159         StackMod::MType type = m->type();
160         stackmods_printf("Checking paired modifications for %s\n", m->format().c_str());
161
162         switch(type) {
163             case StackMod::INSERT:
164                 {
165                     // Add paired REMOVE at function exit
166                     Insert* insertMod = dynamic_cast<Insert*>(m);
167                     Remove* removeMod = new Remove(StackMod::CLEANUP, insertMod->low(), insertMod->high());
168                     stackmods_printf("\t Adding paired %s\n", removeMod->format().c_str());
169                     allMods.push_back(removeMod);
170
171                     // Will require a check for how the stack grows/shrinks
172                     requiresCheckStackGrowth = true;
173                     break;
174
175                 }
176             case StackMod::REMOVE:
177                 {
178                     // Add paired INSERT at function exit
179                     Remove* removeMod = dynamic_cast<Remove*>(m);
180                     Insert* insertMod = new Insert(StackMod::CLEANUP, removeMod->low(), removeMod->high());
181                     stackmods_printf("\t Adding paired %s\n", insertMod->format().c_str());
182                     allMods.push_back(insertMod);
183
184                     // Will require a check for how the stack grows/shrinks
185                     requiresCheckStackGrowth = true;
186                     break;
187
188                 }
189             case StackMod::MOVE:
190                 {
191                     // Will require a check for how the stack grows/shrinks
192                     requiresCheckStackGrowth = true;
193                     break;
194                 }
195             case StackMod::CANARY:
196                 {
197 #if !defined(os_linux)
198                     // Safety check: canaries are Linux-only
199                     func->freeStackMod();
200                     return false;
201 #endif
202
203                     // Some initialization now required
204                     Canary* canaryMod = dynamic_cast<Canary*>(m);
205                     if (arch == Arch_x86) {
206                         canaryMod->init(-8, -4);
207                     } else if (arch == Arch_x86_64) {
208                         canaryMod->init(-8 - AMD64_STACK_ALIGNMENT, -8);
209                     }
210
211                     // Safety check: Only one CANARY modification may be performed
212
213                     // Check remainder of mods
214                     auto remainderIter = iter;
215                     remainderIter++;
216                     for ( ; remainderIter != mods.end(); ++remainderIter) {
217                         if ((*remainderIter)->type() == StackMod::CANARY) {
218                             stackmods_printf("Found 2 CANARY modifications, not allowed\n");
219                             func->freeStackMod();
220                             return false;
221                         }
222                     }
223
224                     // Check existing modifications
225                     if (func->hasCanary()) {
226                         stackmods_printf("Found existing CANARY modification, not allowed\n");
227                         func->freeStackMod();
228                         return false;
229                     }
230                     break;
231                 }
232             case StackMod::RANDOMIZE:
233                 {
234                     // Randomize may not be performed with any other stack modifcations
235                     if (mods.size() != 1 || func->hasStackMod()) {
236                         stackmods_printf("Found RANDOMIZE with other modifications, not allowed\n");
237                         func->freeStackMod();
238                         return false;
239                     }
240                     break;
241                 }
242             default:
243                 {
244                     stackmods_printf("addMods called with unknown stack modification type, returning false\n");
245                     func->freeStackMod();
246                     return false;
247                 }
248         }
249     }
250
251     // The canary has to be the "middle" modification because the snippets are inserted together
252     for (auto iter = mods.rbegin(); iter != mods.rend(); ++iter) {
253         if ((*iter)->type() == StackMod::CANARY) {
254             allMods.push_back(*iter);
255             break;
256         }
257     }
258
259     // Add in original mods
260     for (auto iter = mods.rbegin(); iter != mods.rend(); ++iter) {
261         if ((*iter)->type() != StackMod::CANARY) {
262             allMods.push_back(*iter);
263         }
264     }
265
266     // Calculate any alignment requirements
267     for (auto iter = allMods.begin(); iter != allMods.end(); ++iter) {
268         if (!accumulateStackRanges(*iter)) {
269             func->freeStackMod();
270             return false;
271         }
272     }
273     int alignment = 1;
274     if (arch == Arch_x86_64) { alignment = AMD64_STACK_ALIGNMENT; }
275     if (!alignStackRanges(alignment, StackMod::NEW, allMods)) {
276         func->freeStackMod();
277         return false;
278     }
279     if (!alignStackRanges(alignment, StackMod::CLEANUP, allMods)) {
280         func->freeStackMod();
281         return false;
282     }
283
284     stackmods_printf("final set of modifications:\n");
285     for (auto iter = allMods.begin(); iter != allMods.end(); ++iter) {
286         stackmods_printf("\t %s\n", (*iter)->format().c_str());
287     }
288
289     // Perform stack analysis so we have the information ready
290     StackAnalysis sa(func->ifunc());
291
292     // Other safety checks:
293     //  - Does the stack grow/shrink more than once? For canaries, randomize this might be fine; 
294     //    for the others, this could lead to ambiguity about where the modifications should happen
295     if (requiresCheckStackGrowth) {
296         if (_unsafeStackGrowth || !checkStackGrowth(sa)) {
297             _unsafeStackGrowth = true;
298             stackmods_printf("Found that the stack grows and shrinks multiple times in this function; INSERT,REMOVE,MOVE disallowed\n");
299             func->freeStackMod();
300             return false;
301         } 
302     }
303
304     // Record the old Transformation mapping, in case we need to reset it
305     TMap* oldTMap = func->getTMap(); 
306     TMap* newTMap = new TMap(*oldTMap);
307
308     // Keep track of inserted snippets, in case we need to remove them...
309     std::vector<BPatchSnippetHandle*> snippets;
310     
311     // We may add an insert for the canary check; we need to then add this to allMods outside the loop
312     StackMod* canaryCheckInsert = NULL;
313
314     // Add modifications to the mod set and generate snippets...
315     bool cleanupAndReturn = false;
316     for (auto iter = allMods.begin(); iter != allMods.end(); ++iter) {
317         // Analysis time!
318         StackMod* m = *iter;
319         stackmods_printf("Generating snippet for %s\n", m->format().c_str());
320
321         StackMod::MType type = m->type();
322
323         switch(type) {
324             case StackMod::INSERT :
325                 {
326                     long dispFromRSP = 0;
327                     std::vector<BPatch_point*>* points;
328                     if (!findInsertOrRemovePoints(sa, m, points, dispFromRSP)) {
329                         stackmods_printf("\t findInsertOrRemovePoints failed\n");
330                         func->freeStackMod();
331                         return false;
332                     }
333                     
334                     Insert* insert = dynamic_cast<Insert*>(m);
335                     
336                     for (auto iter = points->begin(); iter != points->end(); ++iter) {
337                         BPatch_point* point = *iter;
338                         Address addr = (Address)(point->getAddress()); 
339                         BPatch_snippet* snip = new BPatch_stackInsertExpr(insert->size(), dispFromRSP);
340                         stackmods_printf("\t Generating INSERT of size %d at 0x%lx\n", insert->size(), addr);
341                         BPatchSnippetHandle* handle = bfunc->getAddSpace()->insertSnippet(*snip, *point, BPatch_callBefore, BPatch_lastSnippet);
342                         if (!handle) {
343                             stackmods_printf("\t\t insertSnippet failed\n");
344                             cleanupAndReturn = true;
345                             break;
346                         } else {
347                             snippets.push_back(handle);
348                         }
349                     }
350
351                     if (m->order() == StackMod::NEW) {
352                         func->addMod(m, newTMap);
353                     } else {
354                         // Cleanup operations don't get added to the TMap
355                     }
356
357                     break;
358                 }
359             case StackMod::REMOVE :
360                 {
361                     long dispFromRSP = 0;
362                     std::vector<BPatch_point*>* points;
363                     if (!findInsertOrRemovePoints(sa, m, points, dispFromRSP)) {
364                         stackmods_printf("\t findInsertOrRemovePoints failed\n");
365                         cleanupAndReturn = true;
366                         break;
367                     }
368
369                     Remove* remove = dynamic_cast<Remove*>(m);
370                     
371                     for (auto iter = points->begin(); iter != points->end(); ++iter) {
372                         BPatch_point* point = *iter;
373                         Address addr = (Address)(point->getAddress()); 
374                         BPatch_snippet* snip = new BPatch_stackRemoveExpr(remove->size());
375                         stackmods_printf("\t Generating REMOVE of size %d at 0x%lx\n", remove->size(), addr);
376                         BPatchSnippetHandle* handle = bfunc->getAddSpace()->insertSnippet(*snip, *point);
377                         if (!handle) {
378                             stackmods_printf("\t\t insertSnippet failed\n");
379                             cleanupAndReturn = true;
380                             break;
381                         } else {
382                             snippets.push_back(handle);
383                         }
384                     }
385                     
386                     if (m->order() == StackMod::NEW) {
387                         func->addMod(m, newTMap);
388                     } else {
389                         // Cleanup operations don't get added to the TMap
390                     }
391
392                     break;
393                 }
394             case StackMod::MOVE :
395                 {
396                     // Doesn't matter where this snippet is inserted, so pick entry
397                     BPatch_point* point = NULL;
398                     std::vector<BPatch_point*>* entryPoints = bfunc->findPoint(BPatch_entry);
399                     if (entryPoints && entryPoints->size()) {
400                         point = entryPoints->at(0);
401                     } else {
402                         cleanupAndReturn = true;
403                         break;
404                     }
405                     BPatch_snippet* snip = new BPatch_stackMoveExpr();
406                     stackmods_printf("\t Generating MOVE at function entry (0x%lx)\n", (Address)(point->getAddress()));
407                     BPatchSnippetHandle* handle = bfunc->getAddSpace()->insertSnippet(*snip, *point);
408                     if (!handle) {
409                         stackmods_printf("\t\t insertSnippet failed\n");
410                         cleanupAndReturn = true;
411                         break;
412                     }
413                     
414                     if (m->order() == StackMod::NEW) {
415                         func->addMod(m, newTMap);
416                     }
417
418                     break;
419                 }
420             case StackMod::CANARY :
421                 {
422                     std::vector<BPatch_point*> insertPoints;
423                     std::vector<BPatch_point*> checkPoints;
424                     if (!findCanaryPoints(&insertPoints, &checkPoints)) {
425                         cleanupAndReturn = true;
426                         break;
427                     }
428                     
429                     // If the insert and check point are the same, don't add the canary
430                     // This isn't a failure, it's just unnecessary
431                     if ( (insertPoints.size() == 1) && (checkPoints.size() == 1) &&
432                             ((Address)(insertPoints.at(0)->getAddress()) == ((Address)(checkPoints.at(0)->getAddress())))) {
433                         continue;
434                     }
435                     // Generate check snippets before insert snippets; set gets processed in LIFO order
436                     Canary* canaryMod = dynamic_cast<Canary*>(m);
437                     BPatch_function* failFunc = canaryMod->failFunc();
438                    
439                     // If a failure function wasn't provided, use __stack_chk_fail from libc
440                     if (!failFunc) {
441                         failFunc = findCanaryFailureFunction(bfunc->getAddSpace()->getImage());
442                     }
443                     
444                     // If no failure function has been found, fail
445                     if (!failFunc) {
446                         cleanupAndReturn = true;
447                         break;
448                     }
449                     for (auto iter = checkPoints.begin(); iter != checkPoints.end(); ++iter) {
450                         BPatch_point* point = *iter;
451                         Address addr = (Address)(point->getAddress());
452                    
453                         // We always insert a canary at entry
454                         // To insert a canary elsewhere, set to true and update canaryHeight
455                         bool canaryAfterPrologue = false;
456                         long canaryHeight = 0;
457                         if (canaryAfterPrologue) {
458                             // This is the old handling code for non-entry canaries; needs to be updated
459 #if 0
460                             ParseAPI::Function* pf = ParseAPI::convert(func);
461                             StackAnalysis sa(pf);
462
463                             ParseAPI::Block* pb = ParseAPI::convert(block);
464                             assert(pb);
465                             StackAnalysis::Height spHeight = sa.findSP(pb, addr);
466                             if (spHeight.isBottom()) {
467                                 assert(0 && "spHeight is bottom and prologue_canary; this shouldn't happen");
468                             }
469
470                             fprintf(stderr, "BPatch_canaryCheckExpr: prologue_canary, spHeight = %s (decimal)\n", spHeight.format().c_str());
471
472                             // Calculate the stack height of the canary
473                             size_t width = func->getModule()->getAddressWidth();
474                             canaryHeight = spHeight + width + width; // spHeight - RA - saved FP  
475 #endif
476                         }
477                         stackmods_printf("\t Generating CANARY CHECK at 0x%lx\n", addr);
478                         BPatch_snippet* snip = new BPatch_canaryCheckExpr(failFunc, canaryAfterPrologue, canaryHeight);
479                         BPatchSnippetHandle* handle = bfunc->getAddSpace()->insertSnippet(*snip, *point, BPatch_callAfter, BPatch_firstSnippet);
480                         if (!handle) {
481                             stackmods_printf("\t\t insertSnippet failed\n");
482                             cleanupAndReturn = true;
483                             break;
484                         } else {
485                             snippets.push_back(handle);
486                         }
487                     }
488
489                     for (auto iter = insertPoints.begin(); iter != insertPoints.end(); ++iter) {
490                         BPatch_point* point = *iter;
491                         Address addr = (Address)(point->getAddress());
492                         BPatch_snippet* snip = new BPatch_canaryExpr();
493                         stackmods_printf("\t Generating CANARY at 0x%lx\n", addr);
494                         BPatchSnippetHandle* handle = bfunc->getAddSpace()->insertSnippet(*snip, *point, BPatch_callBefore);
495                         if (!handle) {
496                             stackmods_printf("\t\t insertSnippet failed\n");
497                             cleanupAndReturn = true;
498                             break;
499                         } else {
500                             snippets.push_back(handle);
501                         }
502                     }
503
504                     // This modification needs to get added to allMods
505                     canaryCheckInsert = new Insert(canaryMod->low(), canaryMod->high());
506                     func->addMod(canaryCheckInsert, newTMap);
507                     func->setCanary(true);
508
509                     break;
510                 }
511             case StackMod::RANDOMIZE :
512                 {
513                     BPatch_snippet* snip = new BPatch_stackRandomizeExpr();
514                     // Doesn't matter where this snippet is inserted, so pick entry
515                     BPatch_point* point = NULL;
516                     std::vector<BPatch_point*>* entryPoints = bfunc->findPoint(BPatch_entry);
517                     if (entryPoints && entryPoints->size()) {
518                         point = entryPoints->at(0);
519                     } else {
520                         cleanupAndReturn = true;
521                         break;
522                     }
523                     stackmods_printf("\t Generating RANDOMIZE at function entry (0x%lx)\n", (Address)(point->getAddress()));
524                     BPatchSnippetHandle* handle = bfunc->getAddSpace()->insertSnippet(*snip, *point);
525                     if (!handle) {
526                         stackmods_printf("\t\t insertSnippet failed\n");
527                         cleanupAndReturn = true;
528                         break;
529                     } else {
530                         snippets.push_back(handle);
531                     }
532
533                     // Add modifications to support randomization
534                     Randomize* randomizeMod = dynamic_cast<Randomize*>(m);
535                     if (randomizeMod->isSeeded()) {
536                         if (!func->randomize(newTMap, true, randomizeMod->seed())) {
537                             stackmods_printf("Function %s notrandom\n", getName().c_str());
538                             cleanupAndReturn = true;
539                             break;
540                         }
541                     } else {
542                         if (!func->randomize(newTMap)) {
543                             stackmods_printf("Function %s notrandom\n", getName().c_str());
544                             cleanupAndReturn = true;
545                             break;
546                         }
547                     }
548                     stackmods_printf("Function %s randomized\n", getName().c_str());
549                     break;
550                 }
551             default:
552                 {
553                     // Shouldn't get here--this was checked earlier
554                     cleanupAndReturn = true;
555                     break;
556                 }
557         }
558     }
559
560     if (canaryCheckInsert) {
561         // This will be out-of-order in allMods, but the snippet insertion happened in the right order, so it's OK
562         allMods.push_back(canaryCheckInsert);
563     }
564
565     // Unsafety analysis
566     // TMap has been built as func_instance::addMod has been invoked for each modification; now, we just need to run the analysis
567     if (!cleanupAndReturn && !areModificationsSafe()) {
568         stackmods_printf("Modifications are not safe. Will not be added.\n");
569         cleanupAndReturn = true;
570     }
571
572     // addMods should be atomic, so if there was a failure, we need to revert all changes performed by these modifications
573     if (cleanupAndReturn) {
574         stackmods_printf("One or more modifications were not successfully added. All modifications from the current set will be removed.\n");
575         
576         // Remove snippets
577         for (auto iter = snippets.begin(); iter != snippets.end(); ++iter) {
578             BPatchSnippetHandle* handle = *iter;
579             if (!bfunc->getAddSpace()->deleteSnippet(handle)) {
580                 stackmods_printf("deleteSnippet failed; this is odd.\n");
581             }
582         }
583
584         // Remove mods from the modification set (reverse func->addMods)
585         for (auto iter = allMods.begin(); iter != allMods.end(); ++iter) {
586             func->removeMod(*iter);
587         }
588
589         // The original TMap remained unchanged, so no reveision is necessary
590
591         func->freeStackMod();
592         return false; 
593     }
594
595     // Update the TMap
596     func->replaceTMap(newTMap);
597
598     // Free old TMap
599     for (auto tmapIter = oldTMap->begin(); tmapIter != oldTMap->end();
600         tmapIter++) {
601         delete tmapIter->first;
602         delete tmapIter->second;
603     }
604     delete oldTMap;
605
606     // Free stack mod data structures (lots of memory)
607     func->freeStackMod();
608
609     func->setStackMod(true);
610     return true;
611 }
612
613 /* Get the name of the function we're checking */
614 std::string StackModChecker::getName() const {
615     return func->ifunc()->name();
616 }
617
618 /* Accumulate the effects of the current stack modification on the _stackRanges;
619  * this gets used to determine if additional modification need to be added to 
620  * preserve alignment requirements on the current platform.
621  */
622 bool StackModChecker::accumulateStackRanges(StackMod* m)
623 {
624     StackMod::MType curType = m->type();
625     
626     // Handle MOVE = INSERT + REMOVE
627     if (curType == StackMod::MOVE) {
628         Move* mod = dynamic_cast<Move*>(m);
629         StackMod* tmpInsert = new Insert(mod->destLow(), mod->destHigh());
630         if (!accumulateStackRanges(tmpInsert)) { return false; }
631         StackMod* tmpRemove = new Remove(mod->srcLow(), mod->srcHigh());
632         return accumulateStackRanges(tmpRemove);
633     }
634
635     // Handle CANARY = INSERT
636     if (curType == StackMod::CANARY) {
637         Canary* mod = dynamic_cast<Canary*>(m);
638         StackMod* tmpInsert = new Insert(mod->low(), mod->high());
639         return accumulateStackRanges(tmpInsert);
640     }
641
642     // RANDOMIZE has no effect on the stack ranges
643     if (curType == StackMod::RANDOMIZE) {
644         return true;
645     }
646
647     bool found = false;
648     int removeRangeAt = -1;
649     std::set<std::pair<int, pair<int, StackMod::MType> > > newRanges;
650
651     rangeIterator begin, end;
652     if (m->order() == StackMod::NEW) {
653         begin = _stackRanges.begin();
654         end = _stackRanges.end();
655     } else if (m->order() == StackMod::CLEANUP) {
656         begin = _stackRangesCleanup.begin();
657         end = _stackRangesCleanup.end();
658     }
659
660     int low, high;
661     if (curType == StackMod::INSERT) {
662         Insert* insertMod = dynamic_cast<Insert*>(m);
663         low = insertMod->low();
664         high = insertMod->high();
665     } else if (curType == StackMod::REMOVE) {
666         Remove* removeMod = dynamic_cast<Remove*>(m);
667         low = removeMod->low();
668         high = removeMod->high();
669     } else {
670         // Shouldn't reach here
671         return false;
672     }
673
674     for (auto rangeIter = begin; rangeIter != end; ++rangeIter) {
675         int start = (*rangeIter).first;
676         int end = (*rangeIter).second.first;
677         StackMod::MType type = (*rangeIter).second.second;
678
679         if (type == curType) {
680             if ( (start <= low) && (low <= end) ) {
681                 found = true;
682                 removeRangeAt = start; // This is inefficient...
683                 newRanges.insert(make_pair(start, make_pair(high, type)));
684                 break;
685             } else if ( (start <= high) && (high <= end) ) {
686                 found = true;
687                 removeRangeAt = start;
688                 newRanges.insert(make_pair(low, make_pair(end, type)));
689                 break;
690             }
691         } else {
692             // Cases:
693             // 1. m's range is contained inside existing range
694             //      separate existing range into two disjoint ranges with same type,
695             //      insert new range for m
696             if ( (start <= low) && (high <= end)) {
697                 found = true;
698                 removeRangeAt = start;
699                 if (!(start == low)) {
700                     newRanges.insert(make_pair(start, make_pair(low, type)));
701                 } 
702
703                 if (!(end == high)) {
704                     newRanges.insert(make_pair(high, make_pair(end, type)));
705                 }
706
707                 newRanges.insert(make_pair(low, make_pair(high, curType)));
708             }
709             // 2. m's range encloses an existing range
710             //      remove existing ranges
711             //      insert a new range for m
712             if ( (low < start) && (high > end) ) {
713                 found = true;
714                 removeRangeAt = start;
715                 newRanges.insert(make_pair(low, make_pair(high, curType)));
716             }
717             // 3. m's range overlaps with start
718             if ( (low < start) && (high > start) && (high < end) ) {
719                 found = true;
720                 removeRangeAt = start;
721                 newRanges.insert(make_pair(low, make_pair(high, curType)));
722                 newRanges.insert(make_pair(high, make_pair(end, type)));
723             }
724             // 4. m's range overlaps with end
725             if ( (low > start) && (low < end) && (high > end) ) {
726                 found = true;
727                 removeRangeAt = start;
728                 newRanges.insert(make_pair(start, make_pair(low, type)));
729                 newRanges.insert(make_pair(low, make_pair(high, curType)));
730             }
731         }
732     }
733     if (found) {
734         if (removeRangeAt != -1) {
735             if (m->order() == StackMod::NEW) {
736                 _stackRanges.erase(removeRangeAt);
737             } else if (m->order() == StackMod::CLEANUP) {
738                 _stackRangesCleanup.erase(removeRangeAt);
739             }
740         }
741         for (auto rangeIter = newRanges.begin(); rangeIter != newRanges.end(); ++rangeIter) {
742             if (m->order() == StackMod::NEW) {
743                 _stackRanges.insert(*rangeIter);
744             } else if (m->order() == StackMod::CLEANUP) {
745                 _stackRangesCleanup.insert(*rangeIter);
746             }
747         }
748     } else {
749         if (m->order() == StackMod::NEW) {
750             _stackRanges.insert(make_pair(low, make_pair(high, curType)));
751         } else if (m->order() == StackMod::CLEANUP) {
752             _stackRangesCleanup.insert(make_pair(low, make_pair(high, curType)));
753         }
754     }
755
756     return true;
757 }
758
759 /* Conform to alignment requirements of the current platform */
760 bool StackModChecker::alignStackRanges(int alignment, StackMod::MOrder order, std::vector<StackMod*>& mods)
761 {
762     rangeIterator begin, end;
763     if (order == StackMod::NEW) {
764         begin = _stackRanges.begin();
765         end = _stackRanges.end();
766     } else if (order == StackMod::CLEANUP) {
767         begin = _stackRangesCleanup.begin();
768         end = _stackRangesCleanup.end();
769     } else {
770         // Shouldn't reach here
771         return false;
772     }
773
774     for (rangeIterator rIter = begin; rIter != end; ) {
775         rangeIterator end = rIter;
776         findContiguousRange(rIter, end);
777
778         // Need to account for INSERTs vs. REMOVEs
779         int size = 0;
780         if (rIter == end) {
781             size = (*rIter).second.first - (*rIter).first;
782         } else {
783             for (auto iter = rIter; iter != end; ++iter) {
784                 int curSize = (*iter).second.first - (*iter).first;
785                 StackMod::MType type = (*iter).second.second;
786                 if (type == StackMod::INSERT) {
787                     size += curSize;
788                 } else if (type == StackMod::REMOVE) {
789                     size -= curSize;
790                 }
791             }
792         }
793             
794         // Fix alignment
795         std::div_t d = std::div(size, alignment);
796         if (d.rem) {
797             // Pad out to alignment requirements; for now, we'll pad above (WLOG) 
798             int fixup = alignment - d.rem;
799             if (order == StackMod::NEW) {
800                 mods.push_back(new Insert(StackMod::NEW, (*end).second.first - fixup, (*end).second.first));
801             } else if (order == StackMod::CLEANUP) {
802                 mods.insert(mods.begin(), new Remove(StackMod::CLEANUP, (*end).second.first - fixup, (*end).second.first));
803             }
804         }
805
806         rIter = ++end;
807     } 
808     return true;
809 }
810
811 void StackModChecker::findContiguousRange(rangeIterator iter, rangeIterator& end)
812 {
813     if (end == _stackRanges.end()) {
814         return;
815     }
816     end = iter;
817     rangeIterator next = iter;
818     next++;
819     if (next != _stackRanges.end()) {
820         if ((*end).second.first == (*next).first) {
821             findContiguousRange(next, end);
822         }
823     }
824 }
825
826 /* This function determines whether the stack frame grows and shrinks multiple
827  * times throughout the function.  Currently, we do not allow stack
828  * modifications (INSERT, REMOVE, MOVE) for functions where this occurs,
829  * because the stack offsets specified by the modifications may be valid for
830  * multiple address ranges in the function.  In the future, stack modifications
831  * could be extended to handle these functions.
832  */
833 bool StackModChecker::checkStackGrowth(StackAnalysis& sa)
834 {
835     bool ret = true;
836    
837     ParseAPI::Function* pf = func->ifunc();
838     ParseAPI::Function::blocklist blocks = pf->blocks();
839
840     // Record stack heights in each function
841     for (auto bIter = blocks.begin(); bIter != blocks.end(); ++bIter) {
842         processBlock(sa, *bIter);
843     }
844    
845     // Quick check: if the stack only changes in the entry and exit blocks(s), 
846     // assume its safe to modify 
847
848     // Accumulate exit blocks
849     ParseAPI::Function::const_blocklist exitBlocklist = pf->exitBlocks();
850     std::set<ParseAPI::Block*> exitBlocks;
851     for (auto iter = exitBlocklist.begin(); iter != exitBlocklist.end(); ++iter) {
852         exitBlocks.insert(*iter);
853     }
854
855     bool requiresFurtherCheck = false;
856     for (auto bIter = blocks.begin(); bIter != blocks.end(); ++bIter) {
857         ParseAPI::Block* block = *bIter;
858         if (block == pf->entry()) {
859             // Entry block
860             continue;
861         } else if (exitBlocks.find(block) != exitBlocks.end()) {
862             // Exit block
863             continue;
864         } else {
865             // Internal block
866             auto found = blockHeights.find(block);
867
868             if (found == blockHeights.end()) {
869                 return false;
870             }
871             std::vector<StackAnalysis::Height>* heights = found->second;
872             if (heights->size() == 1) {
873                 continue;
874             } else {
875                 requiresFurtherCheck = true;
876             }
877         }
878     } 
879
880     // If the stack changes in internal blocks, perform more comprehensive checks
881     if (requiresFurtherCheck) {
882         ret = checkAllPaths(sa);
883     }
884
885     return ret;
886 }
887
888 /* Cache all SP heights for each block in the function */
889 void StackModChecker::processBlock(StackAnalysis& sa, ParseAPI::Block* block)
890 {
891     std::vector<StackAnalysis::Height>* heightVec = new std::vector<StackAnalysis::Height>();
892     ParseAPI::Block::Insns insns;
893     block->getInsns(insns);
894     heightVec->push_back(sa.findSP(block, block->start()));
895     for (auto iter = insns.begin(); iter != insns.end(); ++iter) {
896         Offset off = (*iter).first;
897         InstructionAPI::Instruction::Ptr insn = (*iter).second;
898         StackAnalysis::Height curHeight = sa.findSP(block, off);
899         if (curHeight != heightVec->back()) {
900             heightVec->push_back(curHeight);
901         }
902     }
903
904     blockHeights.insert(make_pair(block, heightVec));
905 }
906
907 /* Check the stack growth for all paths in the function */
908 bool StackModChecker::checkAllPaths(StackAnalysis& sa)
909 {
910     ParseAPI::Function::const_blocklist exitBlocklist = func->ifunc()->exitBlocks();
911     std::set<ParseAPI::Block*> exitBlocks;
912     for (auto iter = exitBlocklist.begin(); iter != exitBlocklist.end(); ++iter) {
913         exitBlocks.insert(*iter);
914     }
915     std::set<ParseAPI::Block*> state;
916     std::vector<ParseAPI::Block*> path;
917     return checkAllPathsInternal(func->ifunc()->entry(), state, path, exitBlocks, sa);
918 }
919
920 /* Recursively build all control flow paths through the function;
921  * when the end of path is found (at an exit block), check for safe
922  * stack growth on that path. 
923  */
924 bool StackModChecker::checkAllPathsInternal(ParseAPI::Block* block, 
925                                             std::set<ParseAPI::Block*>& state,
926                                             std::vector<ParseAPI::Block*>& path,
927                                             std::set<ParseAPI::Block*>& exitBlocks,
928                                             StackAnalysis& sa)
929 {
930     bool ret = true;
931
932     // Record this block on the current path; use this to track cycles
933     auto stateFound = state.find(block);
934     if (stateFound == state.end()) {
935         state.insert(block);
936     } else {
937         // Found a cycle; return
938         return ret;
939     }
940
941     path.push_back(block);
942
943     if (exitBlocks.find(block) != exitBlocks.end()) {
944         // Found the end of a path
945         if (!checkPath(path)) {
946             ret = false;
947         }
948     } else {
949         // Recurse
950         for (auto iter = block->targets().begin(); iter != block->targets().end(); ++iter) {
951             ParseAPI::Edge* edge = *iter;
952             // Don't follow interprocedural edges; we're creating an intraprocedural path
953             if (edge->sinkEdge() || edge->interproc()) continue;
954             ParseAPI::Block* target = edge->trg();
955
956             if (!checkAllPathsInternal(target, state, path, exitBlocks, sa)) {
957                 ret = false;
958                 break;
959             }
960         }
961     }
962
963     // Clean up the state
964     state.erase(block);
965     path.pop_back();
966
967     return ret;
968 }
969
970 /* Check for unsafe stack growth on the current path */
971 bool StackModChecker::checkPath(std::vector<ParseAPI::Block*>& path)
972 {
973     bool foundShrink = false;
974
975     ParseAPI::Block* entryBlock = path.front();
976     auto found = blockHeights.find(entryBlock);
977     if (found == blockHeights.end()) {
978         return false;
979     }
980     std::vector<StackAnalysis::Height>* heights = found->second;
981
982     // Height at function entry
983     StackAnalysis::Height curHeight = heights->front(); 
984
985     for (auto iter = path.begin(); iter != path.end(); ++iter) {
986         ParseAPI::Block* curBlock = *iter;
987         found = blockHeights.find(curBlock);
988
989         if (found == blockHeights.end()) {
990             return false;
991         }
992         heights = found->second;
993
994         for (auto heightIter = heights->begin(); heightIter != heights->end(); ++heightIter) {
995             StackAnalysis::Height height = *heightIter;
996             if (height < curHeight) {
997                 // Stack grows
998                 if (foundShrink) {
999                     // Found grow after shrink; not safe
1000                     return false;
1001                 }
1002                 curHeight = height;
1003             } else if (height > curHeight) {
1004                 // Stack shrinks
1005                 foundShrink = true;
1006                 curHeight = height;
1007             }
1008         }
1009     }
1010
1011     return true;
1012 }
1013
1014 bool StackModChecker::findInsertOrRemovePoints(StackAnalysis& sa, StackMod* m, std::vector<BPatch_point*>*& points, long& dispFromRSP)
1015 {
1016     // Insert and Remove need to be applied when the stack height is at the location of stack memory to be modified;
1017     // for Insert and StackMod::CLEANUP operations, this is directly above the region in qusetion; 
1018     // otherwise, directly below
1019     int loc = 0;
1020     if (m->type() == StackMod::INSERT || m->order() == StackMod::CLEANUP) {
1021         if (m->type() == StackMod::INSERT) {
1022             loc = dynamic_cast<Insert*>(m)->high();
1023         } else if (m->type() == StackMod::REMOVE) {
1024             loc = dynamic_cast<Remove*>(m)->high();
1025         } else {
1026             // Shouldn't reach here
1027             return false;
1028         }
1029     } else if (m->type() == StackMod::REMOVE) {
1030         loc = dynamic_cast<Remove*>(m)->low();
1031     } else {
1032         // Shouldn't reach here
1033         return false;
1034     }
1035
1036     // Record some loop information for a safety check
1037     BPatch_flowGraph* cfg = bfunc->getCFG();
1038     BPatch_Vector<BPatch_basicBlockLoop*> loops;
1039     cfg->getLoops(loops);
1040
1041     if (m->order() == StackMod::NEW) {
1042         // Find the first insn(s) at this height
1043
1044         // Shortcut: is this height at function entry?
1045         ParseAPI::Block* entryBlock = func->ifunc()->entry();
1046         Address entryAddr = entryBlock->start();
1047         BPatch_point* point;
1048         if (checkInsn(entryBlock, entryAddr, loc, sa, point, dispFromRSP)) {
1049             // Yes! Return BPatch_entry
1050             std::vector<BPatch_point*>* entryPoints = bfunc->findPoint(BPatch_entry);
1051             if (entryPoints && entryPoints->size()) {
1052                 points = entryPoints;
1053                 return true;
1054             }
1055         }
1056
1057         points = new std::vector<BPatch_point*>();
1058
1059         // Normal path: work forward from entry
1060         std::vector<ParseAPI::Block*> worklist;
1061         worklist.push_back(entryBlock);
1062
1063         std::set<BPatch_point*> tmpPoints;
1064
1065         while (worklist.size()) {
1066             ParseAPI::Block* block = worklist.back();
1067             worklist.pop_back();
1068
1069             bool found = false;
1070             ParseAPI::Block::Insns insns;
1071             block->getInsns(insns);
1072             BPatch_point* point;
1073             for (auto iIter = insns.begin(); iIter != insns.end(); ++iIter) {
1074                 Address addr = (*iIter).first;
1075                 if (checkInsn(block, addr, loc, sa, point, dispFromRSP)) {
1076                     // If this insn is part of a loop, not safe
1077                     for (auto iter = loops.begin(); iter != loops.end(); ++iter) {
1078                         BPatch_basicBlockLoop* bbl = *iter;
1079                         if (bbl->containsAddress(addr)) {
1080                             // Corner case: is stack height at the last insn in the loop header the same?
1081                             //   stack analysis calculates before height, not after.
1082                             //   Future: try to move to loop header
1083                             // Not safe to insert here
1084                             // But, inserting at a later instruction would not meet the expectations of the user
1085                             return false;
1086                         }
1087                     }
1088
1089                     tmpPoints.insert(point);
1090                     found = true;
1091                 }
1092                 if (found) break;
1093             }
1094
1095             if (found) {
1096                 // If this block contains an insn at the right height, add it to the set and continue through the worklist
1097             } else {
1098                 // If this block does not contain an insn at the right height, push successors onto the worklist
1099                 ParseAPI::Block::edgelist edges = block->targets();
1100                 for (auto eIter = edges.begin(); eIter != edges.end(); ++eIter) {
1101                     ParseAPI::Edge* edge = *eIter;
1102                     if (edge->interproc()) {
1103                         // We shouldn't follow an interproc edge
1104                         // Also, this shouldn't be possible, I think
1105                         return false;
1106                     }
1107                     ParseAPI::Block* srcBlock = edge->src();
1108                     worklist.push_back(srcBlock);
1109                 }
1110             }
1111         }
1112
1113         // If we found a point for each path, return true
1114         // TODO: Is it possible not to have found the right point for each path?
1115         if (tmpPoints.size()) {
1116             for (auto iter = tmpPoints.begin(); iter != tmpPoints.end(); ++iter) {
1117                 points->push_back(*iter);
1118             }
1119             return true;
1120         }
1121     } else if (m->order() == StackMod::CLEANUP) {
1122         // Find the last insn at this height from each function return/tailcall
1123         std::vector<ParseAPI::Block*> worklist;
1124
1125         ParseAPI::Function::const_blocklist retBlocks = func->ifunc()->returnBlocks();
1126         // Accumulate returns
1127         for (auto iter = retBlocks.begin(); iter != retBlocks.end(); ++iter) {
1128             worklist.push_back(*iter);
1129         }
1130         // Accumulate tailcalls
1131         ParseAPI::Function::edgelist callEdges = func->ifunc()->callEdges();
1132         for (auto iter = callEdges.begin(); iter != callEdges.end(); ++iter) {
1133             ParseAPI::Edge* edge = *iter;
1134             if ( ( (edge->type() == ParseAPI::DIRECT) || (edge->type() == ParseAPI::INDIRECT)) &&
1135                     (edge->interproc())) {
1136                 ParseAPI::Block* block = edge->src();
1137                 worklist.push_back(block);
1138             }
1139         }
1140
1141         // Use a set to combine when we find the same point twice
1142         std::set<BPatch_point*> tmpPoints;
1143
1144         while (worklist.size()) {
1145             // Grab the next block from the worklist
1146             ParseAPI::Block* block = worklist.back();
1147             worklist.pop_back();
1148
1149             // Look for insn at the specified height
1150             bool found = false;
1151             ParseAPI::Block::Insns insns;
1152             block->getInsns(insns);
1153             BPatch_point* point;
1154             for (auto iIter = insns.rbegin(); iIter != insns.rend(); ++iIter) {
1155                 Address addr = (*iIter).first;
1156                 if (checkInsn(block, addr, loc, sa, point, dispFromRSP)) {
1157                     // If this insn is part of a loop, not safe
1158                     for (auto iter = loops.begin(); iter != loops.end(); ++iter) {
1159                         BPatch_basicBlockLoop* bbl = *iter;
1160                         if (bbl->containsAddress(addr)) {
1161                             // Corner case: is stack height at the last insn in the loop header the same?
1162                             //   stack analysis calculates before height, not after.
1163                             //   Future: try to move to loop header
1164                             // Not safe to insert here
1165                             // But, inserting at a later instruction would not meet the expectations of the user
1166                             return false;
1167                         }
1168                     }
1169
1170                     tmpPoints.insert(point);
1171                     found = true;
1172                 }
1173                 if (found) break;
1174             }
1175
1176             if (found) {
1177                 // If this block contains an insn at the right height, add it to the set and continue through the worklist
1178             } else {
1179                 // If this block does not contain an insn at the right height, push predecessors onto the worklist
1180                 ParseAPI::Block::edgelist edges = block->sources();
1181                 for (auto eIter = edges.begin(); eIter != edges.end(); ++eIter) {
1182                     ParseAPI::Edge* edge = *eIter;
1183                     if (edge->interproc()) {
1184                         // We shouldn't follow an interproc edge
1185                         // Also, this shouldn't be possible, I think
1186                         return false;
1187                     }
1188                     ParseAPI::Block* srcBlock = edge->src();
1189                     worklist.push_back(srcBlock);
1190                 }
1191             }
1192         }
1193
1194         // If we found a point for each path, return true
1195         // TODO: Is it possible not to have found the right point for each path?
1196         if (tmpPoints.size()) {
1197             for (auto iter = tmpPoints.begin(); iter != tmpPoints.end(); ++iter) {
1198                 points->push_back(*iter);
1199             }
1200             return true;
1201         }
1202     } else {
1203         // Shouldn't reach here
1204         return false;
1205     }
1206     
1207     return false;
1208 }
1209
1210 bool StackModChecker::checkInsn(ParseAPI::Block* block, Offset off, int loc, StackAnalysis& sa, BPatch_point*& point, long& dispFromRSP)
1211 {
1212     // Get the current stack height at loc
1213     StackAnalysis::Height h = sa.findSP(block, off);
1214
1215     if (!h.isBottom() || h.height() == loc || h.height() < loc) {
1216         // Height matches
1217
1218         // Find point
1219         std::vector<BPatch_point*> points;
1220         if (!bfunc->getAddSpace()->getImage()->findPoints(off, points)) return false;
1221
1222         if (h.height() < loc) {
1223             // The difference gets stored in dispFromRSP
1224             // This is because we're actually inserting below our target height
1225             dispFromRSP = loc - h.height();
1226         }
1227
1228         if (points.size() > 1) {
1229             for (auto iter = points.begin(); iter != points.end(); ++iter) {
1230                 BPatch_point* curPoint = *iter;
1231                 BPatch_function* curFunc = curPoint->getFunction();
1232                 if (curFunc == bfunc) {
1233                     point = curPoint; 
1234                     return true;
1235                 } else { 
1236                     continue;
1237                 }
1238             }
1239         } else {
1240             point = points[0];
1241             return true;
1242         }
1243     }
1244
1245     return false;
1246 }
1247
1248 bool StackModChecker::findCanaryPoints(std::vector<BPatch_point*>* insertPoints,
1249         std::vector<BPatch_point*>* checkPoints)
1250 {
1251     // Insert at function entry
1252     std::vector<BPatch_point*>* entryPoints = bfunc->findPoint(BPatch_entry);
1253     if (!entryPoints || !entryPoints->size()) return false;
1254     *insertPoints = *entryPoints;
1255
1256     // Build set of check points by finding all function returns and tailcalls
1257     // Non-returning calls ARE NOT check points
1258     std::set<Address> checkAddrs;
1259
1260     ParseAPI::Function::const_blocklist exitBlocks = func->ifunc()->exitBlocks();
1261     for (auto iter = exitBlocks.begin(); iter != exitBlocks.end(); iter++) {
1262         ParseAPI::Block::edgelist exitEdges = (*iter)->targets();
1263         for (auto eiter = exitEdges.begin(); eiter != exitEdges.end(); eiter++) {
1264             if ((*eiter)->interproc() && ((*eiter)->type() == ParseAPI::RET ||
1265                 (*eiter)->type() == ParseAPI::DIRECT ||
1266                 (*eiter)->type() == ParseAPI::INDIRECT)) {
1267                 checkAddrs.insert((*iter)->last());
1268             }
1269         }
1270     }
1271
1272     // Add points corresponding to this accumulated set of check addrs
1273     std::vector<BPatch_point*>* exitPoints = bfunc->findPoint(BPatch_exit);
1274     if (!exitPoints || !exitPoints->size()) return false;
1275     for (auto iter = exitPoints->begin(); iter != exitPoints->end(); ++iter) {
1276         Address ptAddr = (Address)((*iter)->getAddress());
1277         if (checkAddrs.find(ptAddr) != checkAddrs.end()) {
1278             checkPoints->push_back(*iter);
1279         }
1280     }
1281     return true;
1282 }
1283
1284 bool StackModChecker::areModificationsSafe()
1285 {
1286     ParseAPI::Function* pf = func->ifunc();
1287     ParseAPI::Function::blocklist blocks = pf->blocks();
1288
1289     for (auto bIter = blocks.begin(); bIter != blocks.end(); ++bIter) {
1290         ParseAPI::Block* block = *bIter;
1291         ParseAPI::Block::Insns insns;
1292         block->getInsns(insns);
1293         for (auto iIter = insns.begin(); iIter != insns.end(); ++iIter) {
1294             Offset off = (*iIter).first;
1295             InstructionAPI::InstructionPtr insn = (*iIter).second; 
1296             Accesses* accesses = func->getAccesses(off);
1297             for (auto aIter = accesses->begin(); aIter != accesses->end(); ++aIter) {
1298                 if (!isAccessSafe(insn, (*aIter).second)) {
1299                     return false;
1300                 } 
1301             }
1302         }
1303     }
1304
1305     return true;
1306 }
1307
1308 /* Check if a particular stack access in instruction insn is safe, given the current set of
1309  * stack modifications. Accesses are unsafe if a stack modification perturbs the access range, 
1310  * which can happen by:
1311  *  - inserting into the accessed range, 
1312  *  - removing any part of the accessed range, or 
1313  *  - moving a portion (but not the whole) accessed range.
1314  */
1315 bool StackModChecker::isAccessSafe(InstructionAPI::InstructionPtr insn, StackAccess* access)
1316 {
1317     OffsetVector* offVec = func->getOffsetVector();
1318     TMap* tMap = func->getTMap();
1319
1320     StackAnalysis::Height accessLow = access->readHeight();
1321         int accessSize = -1;
1322         StackLocation* curLoc = NULL;
1323         offVec->find(accessLow, curLoc);
1324         if (curLoc) {
1325             accessLow = curLoc->off();
1326             accessSize = curLoc->size();
1327         } else {
1328             stackmods_printf("\t could not find entry in offVec for this access to %ld, defaulting to getAccessSize\n", accessLow.height());
1329             accessSize = getAccessSize(insn);
1330         }
1331
1332         StackAnalysis::Height accessHigh = accessLow + accessSize;
1333
1334         // Is this access also being moved?
1335         StackAnalysis::Height newAccessLow = accessLow;
1336         StackAnalysis::Height newAccessHigh = accessHigh;
1337         StackLocation* dest = NULL;
1338         if (curLoc) {
1339             dest = tMap->findInMap(curLoc);
1340             if (dest && curLoc != dest) {
1341                 newAccessLow = dest->off();
1342                 newAccessHigh = newAccessLow + dest->size();
1343             } 
1344         }
1345         
1346         // For now, we re-iterate through the modifications; in the future, it would be better to use the tMap somehow
1347         std::set<StackMod*>* modifications = func->getMods();
1348
1349         for (auto modIter = modifications->begin(); modIter != modifications->end(); ++modIter) {
1350             StackMod* mod = *modIter;
1351
1352             switch(mod->type()) {
1353                 case(StackMod::INSERT): {
1354                                   Insert* insertMod = dynamic_cast<Insert*>(mod);
1355                                   StackAnalysis::Height c(insertMod->low());
1356                                   StackAnalysis::Height d(insertMod->high());
1357
1358                                   if ((newAccessLow < c && c < newAccessHigh) || (newAccessLow < d && d < newAccessHigh)) {
1359                                       stackmods_printf("\t Checking modification %s\n", mod->format().c_str());
1360                                       stackmods_printf("\t\t c = %d\n", (int)c.height());
1361                                       stackmods_printf("\t\t d = %d\n", (int)d.height());
1362                                       stackmods_printf("\t\t Insert inside the access range. Unsafe.\n");    
1363                                       return false;
1364                                   }
1365                                   break;
1366                               }
1367                 case(StackMod::REMOVE): {
1368                                   Remove* removeMod = dynamic_cast<Remove*>(mod);
1369                                   StackAnalysis::Height c(removeMod->low());
1370                                   StackAnalysis::Height d(removeMod->high());
1371                                   if ((newAccessLow < c && c < newAccessHigh) || (newAccessLow < d && d < newAccessHigh)) {
1372                                       stackmods_printf("\t Checking modification %s\n", mod->format().c_str());
1373                                       stackmods_printf("\t c = %d\n", (int)c.height());
1374                                       stackmods_printf("\t d = %d\n", (int)d.height());
1375                                       stackmods_printf("\t\t Remove inside the access range. Unsafe.\n");    
1376                                       return false;
1377                                   }
1378                                   break;
1379                               }
1380                 case(StackMod::MOVE): {
1381                                       Move* moveMod = dynamic_cast<Move*>(mod);
1382                                       StackAnalysis::Height c(moveMod->srcLow());
1383
1384                                       int size = moveMod->size();
1385                                       StackAnalysis::Height m(moveMod->destLow());
1386
1387                                       // Possibilities: Both of the above sets
1388                                       if ((accessLow < c && c < accessHigh) || (accessLow < c+size && c+size < accessHigh)) {
1389                                           stackmods_printf("\t Checking modification %s\n", mod->format().c_str());
1390                                           stackmods_printf("\t c = %d, size = %d\n", (int)c.height(), size);
1391                                           stackmods_printf("\t m = %d\n", (int)m.height());
1392                                           stackmods_printf("\t\t Move source inside the access range. Unsafe.\n");    
1393                                           return false;
1394                                       }
1395
1396                                       if ((newAccessLow < m && m < newAccessHigh) || 
1397                                               ( newAccessLow < m+size && 
1398                                                 m+size < newAccessHigh)) {
1399                                           stackmods_printf("\t Checking modification %s\n", mod->format().c_str());
1400                                           stackmods_printf("\t c = %d, size = %d\n", (int)c.height(), size);
1401                                           stackmods_printf("\t m = %d\n", (int)m.height());
1402                                           stackmods_printf("\t\t Move dest inside the access range. Unsafe.\n");    
1403                                           return false;
1404                                       }
1405                                       break;
1406                                   }
1407                 default: {
1408                             stackmods_printf("\t\t Unknown modification type.\n");
1409                             return false;
1410                          }
1411             }
1412         }
1413         
1414         return true;
1415 }
1416
1417
1418