1. Replace springboards prioriy "OffLimits" and "Required" with "FuncEntry" and ...
[dyninst.git] / dyninstAPI / src / Relocation / Springboard.h
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 // Build the branches from previous versions of moved code to the new versions.
32
33 #if !defined(_R_SPRINGBOARD_H_)
34 #define _R_SPRINGBOARD_H_
35 #include <map>
36 #include "common/src/IntervalTree.h"
37 #include "common/h/dyntypes.h"
38 #include "Transformers/Transformer.h" // Priority enum
39 #include "dyninstAPI/src/codegen.h"
40
41 class AddressSpace;
42
43 class func_instance;
44
45 namespace Dyninst {
46 namespace Relocation {
47
48 typedef enum {
49    MIN_PRIORITY,
50    RELOC_MIN_PRIORITY,
51    RelocNotRequired,
52    RelocSuggested,
53    RelocRequired,
54    RelocOffLimits,
55    RELOC_MAX_PRIORITY,
56    ORIG_MIN_PRIORITY,
57    NotRequired,
58    /* Currently we put suggested springboards at non-func-entry, 
59     * non-indirect-jump-target block entry.
60     * In case the jump table analysis under-approximate the jump targets (unlikely),
61     * the control flow will goes back to instrumentation at other blocks*/
62    Suggested,
63    /* Indirect jump target block is very important, 
64     * but is less important than func entry.
65     *
66     * Control flow can escape instrumentation by indirect jump (jump tables).
67     * So, we install springboards at all indirect jump targets.
68     * However, jump table analysis can overapproximate jump targets and
69     * the bogus jump targets can be function entries. So, we put indirect
70     * jump target as one priority lower than function entry
71     */
72    IndirBlockEntry,    
73    /* FuncEntry represents springboards at function entries.
74     * This is the highest priority because control flow enters
75     * instrumentation at function entry
76     */ 
77    FuncEntry,    
78    ORIG_MAX_PRIORITY,
79    MAX_PRIORITY } Priority;
80
81 struct SpringboardReq {
82    typedef std::map<func_instance *, Address> Destinations;
83
84    Address from;
85    Priority priority;
86    func_instance *func;
87    block_instance *block;
88    Destinations destinations;
89    bool checkConflicts;
90    bool includeRelocatedCopies;
91    bool fromRelocatedCode;
92    bool useTrap;
93    SpringboardReq(const Address from_, 
94                   const Address to_, 
95                   const Priority priority_, 
96                   func_instance *func_,
97                   block_instance *block_, 
98                   bool checkConflicts_, 
99                   bool includeRelocCopies_, 
100                   bool fromRelocCode_,
101                   bool useTrap_)
102    : from(from_), 
103       priority(priority_),
104       func(func_),
105       block(block_),
106       checkConflicts(checkConflicts_), 
107       includeRelocatedCopies(includeRelocCopies_),
108       fromRelocatedCode(fromRelocCode_),
109       useTrap(useTrap_) 
110    {
111       destinations[func_] = to_;
112    }
113 SpringboardReq() 
114 : from(0), priority(NotRequired),
115       func(NULL), 
116       block(NULL),
117       checkConflicts(false),
118       includeRelocatedCopies(false),
119       fromRelocatedCode(false),
120       useTrap(false) {};
121    void addReq (const Address from_, const Address to_,
122                 const Priority priority_, 
123                 func_instance *func_, block_instance *block_,
124                 bool checkConflicts_,
125                 bool includeRelocCopies_,
126                 bool fromRelocCode_, 
127                 bool useTrap_) 
128    {
129         // This mechanism handles overlapping functions, where
130         // we might see springboards from the same address to
131         // different targets. In this case only one can win,
132         // but we want to track the different bbls so that
133         // we can do the right thing with includeRelocatedCopies.
134         if (from == 0) {
135             // New version version
136             assert(destinations.empty()); 
137             from = from_;
138             func = func_;
139             block = block_;
140             priority = priority_;
141             destinations[func_] = to_;
142             checkConflicts = checkConflicts_;
143             includeRelocatedCopies = includeRelocCopies_;
144             fromRelocatedCode = fromRelocCode_;
145             useTrap = useTrap_;
146         }
147         else {
148             assert(from == from_);
149             destinations[func_] = to_;
150         }
151    }
152 };
153
154 class SpringboardBuilder;
155
156  class SpringboardMap {
157    friend class CodeMover;
158  public:
159
160    
161    typedef std::map<Address, SpringboardReq> SpringboardsAtPriority;
162    typedef std::map<Priority, SpringboardsAtPriority> Springboards;
163    typedef SpringboardsAtPriority::iterator iterator;
164    typedef SpringboardsAtPriority::const_iterator const_iterator;
165    typedef SpringboardsAtPriority::reverse_iterator reverse_iterator;
166
167    bool empty() const { 
168      return sBoardMap_.empty();
169    }
170
171    void addFromOrigCode(Address from, Address to, 
172                         Priority p, func_instance *func, block_instance *bbl) {
173 // This uses the default constructor if it isn't already there.
174       sBoardMap_[p][from].addReq(from, to, p, func, bbl, true, true, false, false);
175    }
176
177    void addFromRelocatedCode(Address from, Address to,
178                              Priority p) {
179       assert(p < RELOC_MAX_PRIORITY);
180       sBoardMap_[p][from] = SpringboardReq(from, to,
181                                            p,
182                                            NULL,
183                                            NULL,
184                                            true, 
185                                            false,
186                                            true, false);
187    };
188    
189    void addRaw(Address from, Address to, Priority p, 
190                func_instance *func, block_instance *bbl,
191                bool checkConflicts, bool includeRelocatedCopies, bool fromRelocatedCode,
192                bool useTrap) {
193       sBoardMap_[p][from] = SpringboardReq(from, to, p, func, bbl,
194                                            checkConflicts, includeRelocatedCopies,
195                                            fromRelocatedCode, useTrap);
196    }
197
198    iterator begin(Priority p) { return sBoardMap_[p].begin(); };
199    iterator end(Priority p) { return sBoardMap_[p].end(); };
200
201    reverse_iterator rbegin(Priority p) { return sBoardMap_[p].rbegin(); };
202    reverse_iterator rend(Priority p) { return sBoardMap_[p].rend(); };
203
204
205  private:
206    Springboards sBoardMap_;
207  };
208
209  // Persistent tracking of things that have already gotten springboards across multiple
210  // calls to AddressSpace::relocateInt() and thus across multiple SpringboardFoo,
211  // CodeTracker, CodeMover objects.
212
213 struct SpringboardInfo {
214     int val;
215     func_instance *func;
216     Priority priority;
217
218     SpringboardInfo(int v, func_instance* f) : val(v), func(f), priority(MIN_PRIORITY) {}
219     SpringboardInfo(int v, func_instance* f, Priority p) : val(v), func(f), priority(p) {}
220 };
221
222 class InstalledSpringboards
223 {
224  public:
225   typedef boost::shared_ptr<InstalledSpringboards> Ptr;
226   static const int Allocated;
227   static const int UnallocatedStart;
228  InstalledSpringboards() {}
229   
230   
231
232   template <typename BlockIter> 
233   bool addBlocks(func_instance* func, BlockIter begin, BlockIter end);
234   bool addFunc(func_instance* f);
235   bool conflict(Address start, Address end, bool inRelocatedCode, func_instance* func, Priority p);
236   bool conflictInRelocated(Address start, Address end);
237
238   void registerBranch(Address start, Address end, const SpringboardReq::Destinations &dest, bool inRelocatedCode, func_instance* func, Priority p);
239   void registerBranchInRelocated(Address start, Address end, func_instance* func, Priority p);
240   bool forceTrap(Address a) 
241   {
242     return relocTraps_.find(a) != relocTraps_.end();
243   }
244
245     
246   
247  private:
248   // tracks relocation addresses that need trap-based springboards
249   std::set<Address> relocTraps_; 
250   
251
252   // We don't really care about the payload; I just want an "easy to look up"
253   // range data structure. 
254   // Map this to an int because IntervalTree collapses similar ranges. Punks.
255   IntervalTree<Address, SpringboardInfo*> validRanges_;
256
257   // If we consume NOP-padding between functions to get room for a jump, that
258   // padding may not exist in the relocation buffer.  Remember such ranges so
259   // we can deal with that in reinstrumentation, if only to force a trap.
260   IntervalTree<Address, SpringboardInfo*> paddingRanges_;
261
262   // Like the previous, but for branches we put in relocated code. We
263   // assume anything marked as "in relocated code" is a valid thing to write
264   // to, since relocation size is >= original size. However, we still don't
265   // want overlapping branches. 
266   IntervalTree<Address, SpringboardInfo*> overwrittenRelocatedCode_;
267   void debugRanges();
268   
269 };
270  
271  
272
273 class SpringboardBuilder {
274   typedef enum {
275     Failed,
276     MultiNeeded,
277     Succeeded } generateResult_t;
278
279  public:
280   typedef boost::shared_ptr<SpringboardBuilder> Ptr;
281   typedef std::set<func_instance *> FuncSet;
282
283   static Ptr createFunc(FuncSet::const_iterator begin, FuncSet::const_iterator end, AddressSpace *addrSpace);
284
285   bool generate(std::list<codeGen> &springboards,
286                 SpringboardMap &input);
287
288  private:
289   SpringboardBuilder(AddressSpace *a);
290
291   bool generateInt(std::list<codeGen> &springboards,
292                    SpringboardMap &input,
293                    Priority p);
294
295   generateResult_t generateSpringboard(std::list<codeGen> &gens,
296                                        const SpringboardReq &p,
297                                        SpringboardMap &);
298
299   bool generateMultiSpringboard(std::list<codeGen> &input,
300                                 const SpringboardReq &p);
301
302   // Find all previous instrumentations and also overwrite 
303   // them. 
304   bool createRelocSpringboards(const SpringboardReq &r, bool useTrap, SpringboardMap &input);
305
306   bool generateReplacements(std::list<codeGen> &input,
307                             const SpringboardReq &p,
308                             bool useTrap);
309
310
311   void addMultiNeeded(const SpringboardReq &p);
312
313   void generateBranch(Address from, Address to, codeGen &input);
314   void generateTrap(Address from, Address to, codeGen &input);
315
316   bool conflict(Address start, Address end, bool inRelocatedCode, func_instance* func, Priority p) { return installed_springboards_->conflict(start, end, inRelocatedCode, func, p); }
317
318   void registerBranch(Address start, Address end, const SpringboardReq::Destinations &dest, bool inRelocatedCode, func_instance* func, Priority p)
319   {
320     return installed_springboards_->registerBranch(start, end, dest, inRelocatedCode, func, p);
321   }
322
323   bool isLegalShortBranch(Address from, Address to);
324   Address shortBranchBack(Address from);
325
326
327   AddressSpace *addrSpace_;
328
329   InstalledSpringboards::Ptr installed_springboards_;
330   
331   std::list<SpringboardReq> multis_;
332
333 };
334
335 };
336 };
337
338 #endif