Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef LulMainInt_h
8 : #define LulMainInt_h
9 :
10 : #include "PlatformMacros.h"
11 : #include "LulMain.h" // for TaggedUWord
12 :
13 : #include <vector>
14 :
15 : #include "mozilla/Assertions.h"
16 :
17 : // This file is provides internal interface inside LUL. If you are an
18 : // end-user of LUL, do not include it in your code. The end-user
19 : // interface is in LulMain.h.
20 :
21 :
22 : namespace lul {
23 :
24 : using std::vector;
25 :
26 : ////////////////////////////////////////////////////////////////
27 : // DW_REG_ constants //
28 : ////////////////////////////////////////////////////////////////
29 :
30 : // These are the Dwarf CFI register numbers, as (presumably) defined
31 : // in the ELF ABI supplements for each architecture.
32 :
33 : enum DW_REG_NUMBER {
34 : // No real register has this number. It's convenient to be able to
35 : // treat the CFA (Canonical Frame Address) as "just another
36 : // register", though.
37 : DW_REG_CFA = -1,
38 : #if defined(GP_ARCH_arm)
39 : // ARM registers
40 : DW_REG_ARM_R7 = 7,
41 : DW_REG_ARM_R11 = 11,
42 : DW_REG_ARM_R12 = 12,
43 : DW_REG_ARM_R13 = 13,
44 : DW_REG_ARM_R14 = 14,
45 : DW_REG_ARM_R15 = 15,
46 : #elif defined(GP_ARCH_amd64)
47 : // Because the X86 (32 bit) and AMD64 (64 bit) summarisers are
48 : // combined, a merged set of register constants is needed.
49 : DW_REG_INTEL_XBP = 6,
50 : DW_REG_INTEL_XSP = 7,
51 : DW_REG_INTEL_XIP = 16,
52 : #elif defined(GP_ARCH_x86)
53 : DW_REG_INTEL_XBP = 5,
54 : DW_REG_INTEL_XSP = 4,
55 : DW_REG_INTEL_XIP = 8,
56 : #else
57 : # error "Unknown arch"
58 : #endif
59 : };
60 :
61 :
62 : ////////////////////////////////////////////////////////////////
63 : // PfxExpr //
64 : ////////////////////////////////////////////////////////////////
65 :
66 : enum PfxExprOp {
67 : // meaning of mOperand effect on stack
68 : PX_Start, // bool start-with-CFA? start, with CFA on stack, or not
69 : PX_End, // none stop; result is at top of stack
70 : PX_SImm32, // int32 push signed int32
71 : PX_DwReg, // DW_REG_NUMBER push value of the specified reg
72 : PX_Deref, // none pop X ; push *X
73 : PX_Add, // none pop X ; pop Y ; push Y + X
74 : PX_Sub, // none pop X ; pop Y ; push Y - X
75 : PX_And, // none pop X ; pop Y ; push Y & X
76 : PX_Or, // none pop X ; pop Y ; push Y | X
77 : PX_CmpGES, // none pop X ; pop Y ; push (Y >=s X) ? 1 : 0
78 : PX_Shl // none pop X ; pop Y ; push Y << X
79 : };
80 :
81 : struct PfxInstr {
82 0 : PfxInstr(PfxExprOp opcode, int32_t operand)
83 0 : : mOpcode(opcode)
84 0 : , mOperand(operand)
85 0 : {}
86 0 : explicit PfxInstr(PfxExprOp opcode)
87 0 : : mOpcode(opcode)
88 0 : , mOperand(0)
89 0 : {}
90 : bool operator==(const PfxInstr& other) const {
91 : return mOpcode == other.mOpcode && mOperand == other.mOperand;
92 : }
93 : PfxExprOp mOpcode;
94 : int32_t mOperand;
95 : };
96 :
97 : static_assert(sizeof(PfxInstr) <= 8, "PfxInstr size changed unexpectedly");
98 :
99 : // Evaluate the prefix expression whose PfxInstrs start at aPfxInstrs[start].
100 : // In the case of any mishap (stack over/underflow, running off the end of
101 : // the instruction vector, obviously malformed sequences),
102 : // return an invalid TaggedUWord.
103 : // RUNS IN NO-MALLOC CONTEXT
104 : TaggedUWord EvaluatePfxExpr(int32_t start,
105 : const UnwindRegs* aOldRegs,
106 : TaggedUWord aCFA, const StackImage* aStackImg,
107 : const vector<PfxInstr>& aPfxInstrs);
108 :
109 :
110 : ////////////////////////////////////////////////////////////////
111 : // LExpr //
112 : ////////////////////////////////////////////////////////////////
113 :
114 : // An expression -- very primitive. Denotes either "register +
115 : // offset", a dereferenced version of the same, or a reference to a
116 : // prefix expression stored elsewhere. So as to allow convenient
117 : // handling of Dwarf-derived unwind info, the register may also denote
118 : // the CFA. A large number of these need to be stored, so we ensure
119 : // it fits into 8 bytes. See comment below on RuleSet to see how
120 : // expressions fit into the bigger picture.
121 :
122 : enum LExprHow {
123 : UNKNOWN=0, // This LExpr denotes no value.
124 : NODEREF, // Value is (mReg + mOffset).
125 : DEREF, // Value is *(mReg + mOffset).
126 : PFXEXPR // Value is EvaluatePfxExpr(secMap->mPfxInstrs[mOffset])
127 : };
128 :
129 0 : inline static const char* NameOf_LExprHow(LExprHow how) {
130 0 : switch (how) {
131 0 : case UNKNOWN: return "UNKNOWN";
132 0 : case NODEREF: return "NODEREF";
133 0 : case DEREF: return "DEREF";
134 0 : case PFXEXPR: return "PFXEXPR";
135 0 : default: return "LExpr-??";
136 : }
137 : }
138 :
139 :
140 : struct LExpr {
141 : // Denotes an expression with no value.
142 0 : LExpr()
143 0 : : mHow(UNKNOWN)
144 : , mReg(0)
145 0 : , mOffset(0)
146 0 : {}
147 :
148 : // Denotes any expressible expression.
149 0 : LExpr(LExprHow how, int16_t reg, int32_t offset)
150 0 : : mHow(how)
151 : , mReg(reg)
152 0 : , mOffset(offset)
153 : {
154 0 : switch (how) {
155 0 : case UNKNOWN: MOZ_ASSERT(reg == 0 && offset == 0); break;
156 0 : case NODEREF: break;
157 0 : case DEREF: break;
158 0 : case PFXEXPR: MOZ_ASSERT(reg == 0 && offset >= 0); break;
159 0 : default: MOZ_ASSERT(0, "LExpr::LExpr: invalid how");
160 : }
161 0 : }
162 :
163 : // Change the offset for an expression that references memory.
164 : LExpr add_delta(long delta)
165 : {
166 : MOZ_ASSERT(mHow == NODEREF);
167 : // If this is a non-debug build and the above assertion would have
168 : // failed, at least return LExpr() so that the machinery that uses
169 : // the resulting expression fails in a repeatable way.
170 : return (mHow == NODEREF) ? LExpr(mHow, mReg, mOffset+delta)
171 : : LExpr(); // Gone bad
172 : }
173 :
174 : // Dereference an expression that denotes a memory address.
175 : LExpr deref()
176 : {
177 : MOZ_ASSERT(mHow == NODEREF);
178 : // Same rationale as for add_delta().
179 : return (mHow == NODEREF) ? LExpr(DEREF, mReg, mOffset)
180 : : LExpr(); // Gone bad
181 : }
182 :
183 : // Print a rule for recovery of |aNewReg| whose recovered value
184 : // is this LExpr.
185 : string ShowRule(const char* aNewReg) const;
186 :
187 : // Evaluate this expression, producing a TaggedUWord. |aOldRegs|
188 : // holds register values that may be referred to by the expression.
189 : // |aCFA| holds the CFA value, if any, that applies. |aStackImg|
190 : // contains a chuck of stack that will be consulted if the expression
191 : // references memory. |aPfxInstrs| holds the vector of PfxInstrs
192 : // that will be consulted if this is a PFXEXPR.
193 : // RUNS IN NO-MALLOC CONTEXT
194 : TaggedUWord EvaluateExpr(const UnwindRegs* aOldRegs,
195 : TaggedUWord aCFA, const StackImage* aStackImg,
196 : const vector<PfxInstr>* aPfxInstrs) const;
197 :
198 : // Representation of expressions. If |mReg| is DW_REG_CFA (-1) then
199 : // it denotes the CFA. All other allowed values for |mReg| are
200 : // nonnegative and are DW_REG_ values.
201 : LExprHow mHow:8;
202 : int16_t mReg; // A DW_REG_ value
203 : int32_t mOffset; // 32-bit signed offset should be more than enough.
204 : };
205 :
206 : static_assert(sizeof(LExpr) <= 8, "LExpr size changed unexpectedly");
207 :
208 :
209 : ////////////////////////////////////////////////////////////////
210 : // RuleSet //
211 : ////////////////////////////////////////////////////////////////
212 :
213 : // This is platform-dependent. For some address range, describes how
214 : // to recover the CFA and then how to recover the registers for the
215 : // previous frame.
216 : //
217 : // The set of LExprs contained in a given RuleSet describe a DAG which
218 : // says how to compute the caller's registers ("new registers") from
219 : // the callee's registers ("old registers"). The DAG can contain a
220 : // single internal node, which is the value of the CFA for the callee.
221 : // It would be possible to construct a DAG that omits the CFA, but
222 : // including it makes the summarisers simpler, and the Dwarf CFI spec
223 : // has the CFA as a central concept.
224 : //
225 : // For this to make sense, |mCfaExpr| can't have
226 : // |mReg| == DW_REG_CFA since we have no previous value for the CFA.
227 : // All of the other |Expr| fields can -- and usually do -- specify
228 : // |mReg| == DW_REG_CFA.
229 : //
230 : // With that in place, the unwind algorithm proceeds as follows.
231 : //
232 : // (0) Initially: we have values for the old registers, and a memory
233 : // image.
234 : //
235 : // (1) Compute the CFA by evaluating |mCfaExpr|. Add the computed
236 : // value to the set of "old registers".
237 : //
238 : // (2) Compute values for the registers by evaluating all of the other
239 : // |Expr| fields in the RuleSet. These can depend on both the old
240 : // register values and the just-computed CFA.
241 : //
242 : // If we are unwinding without computing a CFA, perhaps because the
243 : // RuleSets are derived from EXIDX instead of Dwarf, then
244 : // |mCfaExpr.mHow| will be LExpr::UNKNOWN, so the computed value will
245 : // be invalid -- that is, TaggedUWord() -- and so any attempt to use
246 : // that will result in the same value. But that's OK because the
247 : // RuleSet would make no sense if depended on the CFA but specified no
248 : // way to compute it.
249 : //
250 : // A RuleSet is not allowed to cover zero address range. Having zero
251 : // length would break binary searching in SecMaps and PriMaps.
252 :
253 : class RuleSet {
254 : public:
255 : RuleSet();
256 : void Print(void(*aLog)(const char*)) const;
257 :
258 : // Find the LExpr* for a given DW_REG_ value in this class.
259 : LExpr* ExprForRegno(DW_REG_NUMBER aRegno);
260 :
261 : uintptr_t mAddr;
262 : uintptr_t mLen;
263 : // How to compute the CFA.
264 : LExpr mCfaExpr;
265 : // How to compute caller register values. These may reference the
266 : // value defined by |mCfaExpr|.
267 : #if defined(GP_ARCH_amd64) || defined(GP_ARCH_x86)
268 : LExpr mXipExpr; // return address
269 : LExpr mXspExpr;
270 : LExpr mXbpExpr;
271 : #elif defined(GP_ARCH_arm)
272 : LExpr mR15expr; // return address
273 : LExpr mR14expr;
274 : LExpr mR13expr;
275 : LExpr mR12expr;
276 : LExpr mR11expr;
277 : LExpr mR7expr;
278 : #else
279 : # error "Unknown arch"
280 : #endif
281 : };
282 :
283 : // Returns |true| for Dwarf register numbers which are members
284 : // of the set of registers that LUL unwinds on this target.
285 0 : static inline bool registerIsTracked(DW_REG_NUMBER reg) {
286 0 : switch (reg) {
287 : # if defined(GP_ARCH_amd64) || defined(GP_ARCH_x86)
288 : case DW_REG_INTEL_XBP: case DW_REG_INTEL_XSP: case DW_REG_INTEL_XIP:
289 0 : return true;
290 : # elif defined(GP_ARCH_arm)
291 : case DW_REG_ARM_R7: case DW_REG_ARM_R11: case DW_REG_ARM_R12:
292 : case DW_REG_ARM_R13: case DW_REG_ARM_R14: case DW_REG_ARM_R15:
293 : return true;
294 : # else
295 : # error "Unknown arch"
296 : # endif
297 : default:
298 0 : return false;
299 : }
300 : }
301 :
302 :
303 : ////////////////////////////////////////////////////////////////
304 : // SecMap //
305 : ////////////////////////////////////////////////////////////////
306 :
307 : // A SecMap may have zero address range, temporarily, whilst RuleSets
308 : // are being added to it. But adding a zero-range SecMap to a PriMap
309 : // will make it impossible to maintain the total order of the PriMap
310 : // entries, and so that can't be allowed to happen.
311 :
312 : class SecMap {
313 : public:
314 : // These summarise the contained mRuleSets, in that they give
315 : // exactly the lowest and highest addresses that any of the entries
316 : // in this SecMap cover. Hence invariants:
317 : //
318 : // mRuleSets is nonempty
319 : // <=> mSummaryMinAddr <= mSummaryMaxAddr
320 : // && mSummaryMinAddr == mRuleSets[0].mAddr
321 : // && mSummaryMaxAddr == mRuleSets[#rulesets-1].mAddr
322 : // + mRuleSets[#rulesets-1].mLen - 1;
323 : //
324 : // This requires that no RuleSet has zero length.
325 : //
326 : // mRuleSets is empty
327 : // <=> mSummaryMinAddr > mSummaryMaxAddr
328 : //
329 : // This doesn't constrain mSummaryMinAddr and mSummaryMaxAddr uniquely,
330 : // so let's use mSummaryMinAddr == 1 and mSummaryMaxAddr == 0 to denote
331 : // this case.
332 :
333 : explicit SecMap(void(*aLog)(const char*));
334 : ~SecMap();
335 :
336 : // Binary search mRuleSets to find one that brackets |ia|, or nullptr
337 : // if none is found. It's not allowable to do this until PrepareRuleSets
338 : // has been called first.
339 : RuleSet* FindRuleSet(uintptr_t ia);
340 :
341 : // Add a RuleSet to the collection. The rule is copied in. Calling
342 : // this makes the map non-searchable.
343 : void AddRuleSet(const RuleSet* rs);
344 :
345 : // Add a PfxInstr to the vector of such instrs, and return the index
346 : // in the vector. Calling this makes the map non-searchable.
347 : uint32_t AddPfxInstr(PfxInstr pfxi);
348 :
349 : // Returns the entire vector of PfxInstrs.
350 0 : const vector<PfxInstr>* GetPfxInstrs() { return &mPfxInstrs; }
351 :
352 : // Prepare the map for searching. Also, remove any rules for code
353 : // address ranges which don't fall inside [start, +len). |len| may
354 : // not be zero.
355 : void PrepareRuleSets(uintptr_t start, size_t len);
356 :
357 : bool IsEmpty();
358 :
359 0 : size_t Size() { return mRuleSets.size(); }
360 :
361 : size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
362 :
363 : // The min and max addresses of the addresses in the contained
364 : // RuleSets. See comment above for invariants.
365 : uintptr_t mSummaryMinAddr;
366 : uintptr_t mSummaryMaxAddr;
367 :
368 : private:
369 : // False whilst adding entries; true once it is safe to call FindRuleSet.
370 : // Transition (false->true) is caused by calling PrepareRuleSets().
371 : bool mUsable;
372 :
373 : // A vector of RuleSets, sorted, nonoverlapping (post Prepare()).
374 : vector<RuleSet> mRuleSets;
375 :
376 : // A vector of PfxInstrs, which are referred to by the RuleSets.
377 : // These are provided as a representation of Dwarf expressions
378 : // (DW_CFA_val_expression, DW_CFA_expression, DW_CFA_def_cfa_expression),
379 : // are relatively expensive to evaluate, and and are therefore
380 : // expected to be used only occasionally.
381 : //
382 : // The vector holds a bunch of separate PfxInstr programs, each one
383 : // starting with a PX_Start and terminated by a PX_End, all
384 : // concatenated together. When a RuleSet can't recover a value
385 : // using a self-contained LExpr, it uses a PFXEXPR whose mOffset is
386 : // the index in this vector of start of the necessary PfxInstr program.
387 : vector<PfxInstr> mPfxInstrs;
388 :
389 : // A logging sink, for debugging.
390 : void (*mLog)(const char*);
391 : };
392 :
393 : } // namespace lul
394 :
395 : #endif // ndef LulMainInt_h
|
