File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/Alignment.h |
Warning: | line 85, column 47 The result of the left shift is undefined due to shifting by '255', which is greater or equal to the width of type 'uint64_t' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- DataFlowSanitizer.cpp - dynamic data flow analysis -----------------===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | /// \file | |||
10 | /// This file is a part of DataFlowSanitizer, a generalised dynamic data flow | |||
11 | /// analysis. | |||
12 | /// | |||
13 | /// Unlike other Sanitizer tools, this tool is not designed to detect a specific | |||
14 | /// class of bugs on its own. Instead, it provides a generic dynamic data flow | |||
15 | /// analysis framework to be used by clients to help detect application-specific | |||
16 | /// issues within their own code. | |||
17 | /// | |||
18 | /// The analysis is based on automatic propagation of data flow labels (also | |||
19 | /// known as taint labels) through a program as it performs computation. | |||
20 | /// | |||
21 | /// Each byte of application memory is backed by a shadow memory byte. The | |||
22 | /// shadow byte can represent up to 8 labels. On Linux/x86_64, memory is then | |||
23 | /// laid out as follows: | |||
24 | /// | |||
25 | /// +--------------------+ 0x800000000000 (top of memory) | |||
26 | /// | application 3 | | |||
27 | /// +--------------------+ 0x700000000000 | |||
28 | /// | invalid | | |||
29 | /// +--------------------+ 0x610000000000 | |||
30 | /// | origin 1 | | |||
31 | /// +--------------------+ 0x600000000000 | |||
32 | /// | application 2 | | |||
33 | /// +--------------------+ 0x510000000000 | |||
34 | /// | shadow 1 | | |||
35 | /// +--------------------+ 0x500000000000 | |||
36 | /// | invalid | | |||
37 | /// +--------------------+ 0x400000000000 | |||
38 | /// | origin 3 | | |||
39 | /// +--------------------+ 0x300000000000 | |||
40 | /// | shadow 3 | | |||
41 | /// +--------------------+ 0x200000000000 | |||
42 | /// | origin 2 | | |||
43 | /// +--------------------+ 0x110000000000 | |||
44 | /// | invalid | | |||
45 | /// +--------------------+ 0x100000000000 | |||
46 | /// | shadow 2 | | |||
47 | /// +--------------------+ 0x010000000000 | |||
48 | /// | application 1 | | |||
49 | /// +--------------------+ 0x000000000000 | |||
50 | /// | |||
51 | /// MEM_TO_SHADOW(mem) = mem ^ 0x500000000000 | |||
52 | /// SHADOW_TO_ORIGIN(shadow) = shadow + 0x100000000000 | |||
53 | /// | |||
54 | /// For more information, please refer to the design document: | |||
55 | /// http://clang.llvm.org/docs/DataFlowSanitizerDesign.html | |||
56 | // | |||
57 | //===----------------------------------------------------------------------===// | |||
58 | ||||
59 | #include "llvm/Transforms/Instrumentation/DataFlowSanitizer.h" | |||
60 | #include "llvm/ADT/DenseMap.h" | |||
61 | #include "llvm/ADT/DenseSet.h" | |||
62 | #include "llvm/ADT/DepthFirstIterator.h" | |||
63 | #include "llvm/ADT/None.h" | |||
64 | #include "llvm/ADT/SmallPtrSet.h" | |||
65 | #include "llvm/ADT/SmallVector.h" | |||
66 | #include "llvm/ADT/StringExtras.h" | |||
67 | #include "llvm/ADT/StringRef.h" | |||
68 | #include "llvm/ADT/Triple.h" | |||
69 | #include "llvm/ADT/iterator.h" | |||
70 | #include "llvm/Analysis/ValueTracking.h" | |||
71 | #include "llvm/IR/Argument.h" | |||
72 | #include "llvm/IR/Attributes.h" | |||
73 | #include "llvm/IR/BasicBlock.h" | |||
74 | #include "llvm/IR/Constant.h" | |||
75 | #include "llvm/IR/Constants.h" | |||
76 | #include "llvm/IR/DataLayout.h" | |||
77 | #include "llvm/IR/DerivedTypes.h" | |||
78 | #include "llvm/IR/Dominators.h" | |||
79 | #include "llvm/IR/Function.h" | |||
80 | #include "llvm/IR/GlobalAlias.h" | |||
81 | #include "llvm/IR/GlobalValue.h" | |||
82 | #include "llvm/IR/GlobalVariable.h" | |||
83 | #include "llvm/IR/IRBuilder.h" | |||
84 | #include "llvm/IR/InlineAsm.h" | |||
85 | #include "llvm/IR/InstVisitor.h" | |||
86 | #include "llvm/IR/InstrTypes.h" | |||
87 | #include "llvm/IR/Instruction.h" | |||
88 | #include "llvm/IR/Instructions.h" | |||
89 | #include "llvm/IR/IntrinsicInst.h" | |||
90 | #include "llvm/IR/LLVMContext.h" | |||
91 | #include "llvm/IR/MDBuilder.h" | |||
92 | #include "llvm/IR/Module.h" | |||
93 | #include "llvm/IR/PassManager.h" | |||
94 | #include "llvm/IR/Type.h" | |||
95 | #include "llvm/IR/User.h" | |||
96 | #include "llvm/IR/Value.h" | |||
97 | #include "llvm/InitializePasses.h" | |||
98 | #include "llvm/Pass.h" | |||
99 | #include "llvm/Support/Alignment.h" | |||
100 | #include "llvm/Support/Casting.h" | |||
101 | #include "llvm/Support/CommandLine.h" | |||
102 | #include "llvm/Support/ErrorHandling.h" | |||
103 | #include "llvm/Support/SpecialCaseList.h" | |||
104 | #include "llvm/Support/VirtualFileSystem.h" | |||
105 | #include "llvm/Transforms/Instrumentation.h" | |||
106 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||
107 | #include "llvm/Transforms/Utils/Local.h" | |||
108 | #include <algorithm> | |||
109 | #include <cassert> | |||
110 | #include <cstddef> | |||
111 | #include <cstdint> | |||
112 | #include <iterator> | |||
113 | #include <memory> | |||
114 | #include <set> | |||
115 | #include <string> | |||
116 | #include <utility> | |||
117 | #include <vector> | |||
118 | ||||
119 | using namespace llvm; | |||
120 | ||||
121 | // This must be consistent with ShadowWidthBits. | |||
122 | static const Align ShadowTLSAlignment = Align(2); | |||
123 | ||||
124 | static const Align MinOriginAlignment = Align(4); | |||
125 | ||||
126 | // The size of TLS variables. These constants must be kept in sync with the ones | |||
127 | // in dfsan.cpp. | |||
128 | static const unsigned ArgTLSSize = 800; | |||
129 | static const unsigned RetvalTLSSize = 800; | |||
130 | ||||
131 | // The -dfsan-preserve-alignment flag controls whether this pass assumes that | |||
132 | // alignment requirements provided by the input IR are correct. For example, | |||
133 | // if the input IR contains a load with alignment 8, this flag will cause | |||
134 | // the shadow load to have alignment 16. This flag is disabled by default as | |||
135 | // we have unfortunately encountered too much code (including Clang itself; | |||
136 | // see PR14291) which performs misaligned access. | |||
137 | static cl::opt<bool> ClPreserveAlignment( | |||
138 | "dfsan-preserve-alignment", | |||
139 | cl::desc("respect alignment requirements provided by input IR"), cl::Hidden, | |||
140 | cl::init(false)); | |||
141 | ||||
142 | // The ABI list files control how shadow parameters are passed. The pass treats | |||
143 | // every function labelled "uninstrumented" in the ABI list file as conforming | |||
144 | // to the "native" (i.e. unsanitized) ABI. Unless the ABI list contains | |||
145 | // additional annotations for those functions, a call to one of those functions | |||
146 | // will produce a warning message, as the labelling behaviour of the function is | |||
147 | // unknown. The other supported annotations are "functional" and "discard", | |||
148 | // which are described below under DataFlowSanitizer::WrapperKind. | |||
149 | static cl::list<std::string> ClABIListFiles( | |||
150 | "dfsan-abilist", | |||
151 | cl::desc("File listing native ABI functions and how the pass treats them"), | |||
152 | cl::Hidden); | |||
153 | ||||
154 | // Controls whether the pass uses IA_Args or IA_TLS as the ABI for instrumented | |||
155 | // functions (see DataFlowSanitizer::InstrumentedABI below). | |||
156 | static cl::opt<bool> | |||
157 | ClArgsABI("dfsan-args-abi", | |||
158 | cl::desc("Use the argument ABI rather than the TLS ABI"), | |||
159 | cl::Hidden); | |||
160 | ||||
161 | // Controls whether the pass includes or ignores the labels of pointers in load | |||
162 | // instructions. | |||
163 | static cl::opt<bool> ClCombinePointerLabelsOnLoad( | |||
164 | "dfsan-combine-pointer-labels-on-load", | |||
165 | cl::desc("Combine the label of the pointer with the label of the data when " | |||
166 | "loading from memory."), | |||
167 | cl::Hidden, cl::init(true)); | |||
168 | ||||
169 | // Controls whether the pass includes or ignores the labels of pointers in | |||
170 | // stores instructions. | |||
171 | static cl::opt<bool> ClCombinePointerLabelsOnStore( | |||
172 | "dfsan-combine-pointer-labels-on-store", | |||
173 | cl::desc("Combine the label of the pointer with the label of the data when " | |||
174 | "storing in memory."), | |||
175 | cl::Hidden, cl::init(false)); | |||
176 | ||||
177 | // Controls whether the pass propagates labels of offsets in GEP instructions. | |||
178 | static cl::opt<bool> ClCombineOffsetLabelsOnGEP( | |||
179 | "dfsan-combine-offset-labels-on-gep", | |||
180 | cl::desc( | |||
181 | "Combine the label of the offset with the label of the pointer when " | |||
182 | "doing pointer arithmetic."), | |||
183 | cl::Hidden, cl::init(true)); | |||
184 | ||||
185 | static cl::opt<bool> ClDebugNonzeroLabels( | |||
186 | "dfsan-debug-nonzero-labels", | |||
187 | cl::desc("Insert calls to __dfsan_nonzero_label on observing a parameter, " | |||
188 | "load or return with a nonzero label"), | |||
189 | cl::Hidden); | |||
190 | ||||
191 | // Experimental feature that inserts callbacks for certain data events. | |||
192 | // Currently callbacks are only inserted for loads, stores, memory transfers | |||
193 | // (i.e. memcpy and memmove), and comparisons. | |||
194 | // | |||
195 | // If this flag is set to true, the user must provide definitions for the | |||
196 | // following callback functions: | |||
197 | // void __dfsan_load_callback(dfsan_label Label, void* addr); | |||
198 | // void __dfsan_store_callback(dfsan_label Label, void* addr); | |||
199 | // void __dfsan_mem_transfer_callback(dfsan_label *Start, size_t Len); | |||
200 | // void __dfsan_cmp_callback(dfsan_label CombinedLabel); | |||
201 | static cl::opt<bool> ClEventCallbacks( | |||
202 | "dfsan-event-callbacks", | |||
203 | cl::desc("Insert calls to __dfsan_*_callback functions on data events."), | |||
204 | cl::Hidden, cl::init(false)); | |||
205 | ||||
206 | // Controls whether the pass tracks the control flow of select instructions. | |||
207 | static cl::opt<bool> ClTrackSelectControlFlow( | |||
208 | "dfsan-track-select-control-flow", | |||
209 | cl::desc("Propagate labels from condition values of select instructions " | |||
210 | "to results."), | |||
211 | cl::Hidden, cl::init(true)); | |||
212 | ||||
213 | // TODO: This default value follows MSan. DFSan may use a different value. | |||
214 | static cl::opt<int> ClInstrumentWithCallThreshold( | |||
215 | "dfsan-instrument-with-call-threshold", | |||
216 | cl::desc("If the function being instrumented requires more than " | |||
217 | "this number of origin stores, use callbacks instead of " | |||
218 | "inline checks (-1 means never use callbacks)."), | |||
219 | cl::Hidden, cl::init(3500)); | |||
220 | ||||
221 | // Controls how to track origins. | |||
222 | // * 0: do not track origins. | |||
223 | // * 1: track origins at memory store operations. | |||
224 | // * 2: track origins at memory load and store operations. | |||
225 | // TODO: track callsites. | |||
226 | static cl::opt<int> ClTrackOrigins("dfsan-track-origins", | |||
227 | cl::desc("Track origins of labels"), | |||
228 | cl::Hidden, cl::init(0)); | |||
229 | ||||
230 | static StringRef getGlobalTypeString(const GlobalValue &G) { | |||
231 | // Types of GlobalVariables are always pointer types. | |||
232 | Type *GType = G.getValueType(); | |||
233 | // For now we support excluding struct types only. | |||
234 | if (StructType *SGType = dyn_cast<StructType>(GType)) { | |||
235 | if (!SGType->isLiteral()) | |||
236 | return SGType->getName(); | |||
237 | } | |||
238 | return "<unknown type>"; | |||
239 | } | |||
240 | ||||
241 | namespace { | |||
242 | ||||
243 | // Memory map parameters used in application-to-shadow address calculation. | |||
244 | // Offset = (Addr & ~AndMask) ^ XorMask | |||
245 | // Shadow = ShadowBase + Offset | |||
246 | // Origin = (OriginBase + Offset) & ~3ULL | |||
247 | struct MemoryMapParams { | |||
248 | uint64_t AndMask; | |||
249 | uint64_t XorMask; | |||
250 | uint64_t ShadowBase; | |||
251 | uint64_t OriginBase; | |||
252 | }; | |||
253 | ||||
254 | } // end anonymous namespace | |||
255 | ||||
256 | // x86_64 Linux | |||
257 | // NOLINTNEXTLINE(readability-identifier-naming) | |||
258 | static const MemoryMapParams Linux_X86_64_MemoryMapParams = { | |||
259 | 0, // AndMask (not used) | |||
260 | 0x500000000000, // XorMask | |||
261 | 0, // ShadowBase (not used) | |||
262 | 0x100000000000, // OriginBase | |||
263 | }; | |||
264 | ||||
265 | namespace { | |||
266 | ||||
267 | class DFSanABIList { | |||
268 | std::unique_ptr<SpecialCaseList> SCL; | |||
269 | ||||
270 | public: | |||
271 | DFSanABIList() = default; | |||
272 | ||||
273 | void set(std::unique_ptr<SpecialCaseList> List) { SCL = std::move(List); } | |||
274 | ||||
275 | /// Returns whether either this function or its source file are listed in the | |||
276 | /// given category. | |||
277 | bool isIn(const Function &F, StringRef Category) const { | |||
278 | return isIn(*F.getParent(), Category) || | |||
279 | SCL->inSection("dataflow", "fun", F.getName(), Category); | |||
280 | } | |||
281 | ||||
282 | /// Returns whether this global alias is listed in the given category. | |||
283 | /// | |||
284 | /// If GA aliases a function, the alias's name is matched as a function name | |||
285 | /// would be. Similarly, aliases of globals are matched like globals. | |||
286 | bool isIn(const GlobalAlias &GA, StringRef Category) const { | |||
287 | if (isIn(*GA.getParent(), Category)) | |||
288 | return true; | |||
289 | ||||
290 | if (isa<FunctionType>(GA.getValueType())) | |||
291 | return SCL->inSection("dataflow", "fun", GA.getName(), Category); | |||
292 | ||||
293 | return SCL->inSection("dataflow", "global", GA.getName(), Category) || | |||
294 | SCL->inSection("dataflow", "type", getGlobalTypeString(GA), | |||
295 | Category); | |||
296 | } | |||
297 | ||||
298 | /// Returns whether this module is listed in the given category. | |||
299 | bool isIn(const Module &M, StringRef Category) const { | |||
300 | return SCL->inSection("dataflow", "src", M.getModuleIdentifier(), Category); | |||
301 | } | |||
302 | }; | |||
303 | ||||
304 | /// TransformedFunction is used to express the result of transforming one | |||
305 | /// function type into another. This struct is immutable. It holds metadata | |||
306 | /// useful for updating calls of the old function to the new type. | |||
307 | struct TransformedFunction { | |||
308 | TransformedFunction(FunctionType *OriginalType, FunctionType *TransformedType, | |||
309 | std::vector<unsigned> ArgumentIndexMapping) | |||
310 | : OriginalType(OriginalType), TransformedType(TransformedType), | |||
311 | ArgumentIndexMapping(ArgumentIndexMapping) {} | |||
312 | ||||
313 | // Disallow copies. | |||
314 | TransformedFunction(const TransformedFunction &) = delete; | |||
315 | TransformedFunction &operator=(const TransformedFunction &) = delete; | |||
316 | ||||
317 | // Allow moves. | |||
318 | TransformedFunction(TransformedFunction &&) = default; | |||
319 | TransformedFunction &operator=(TransformedFunction &&) = default; | |||
320 | ||||
321 | /// Type of the function before the transformation. | |||
322 | FunctionType *OriginalType; | |||
323 | ||||
324 | /// Type of the function after the transformation. | |||
325 | FunctionType *TransformedType; | |||
326 | ||||
327 | /// Transforming a function may change the position of arguments. This | |||
328 | /// member records the mapping from each argument's old position to its new | |||
329 | /// position. Argument positions are zero-indexed. If the transformation | |||
330 | /// from F to F' made the first argument of F into the third argument of F', | |||
331 | /// then ArgumentIndexMapping[0] will equal 2. | |||
332 | std::vector<unsigned> ArgumentIndexMapping; | |||
333 | }; | |||
334 | ||||
335 | /// Given function attributes from a call site for the original function, | |||
336 | /// return function attributes appropriate for a call to the transformed | |||
337 | /// function. | |||
338 | AttributeList | |||
339 | transformFunctionAttributes(const TransformedFunction &TransformedFunction, | |||
340 | LLVMContext &Ctx, AttributeList CallSiteAttrs) { | |||
341 | ||||
342 | // Construct a vector of AttributeSet for each function argument. | |||
343 | std::vector<llvm::AttributeSet> ArgumentAttributes( | |||
344 | TransformedFunction.TransformedType->getNumParams()); | |||
345 | ||||
346 | // Copy attributes from the parameter of the original function to the | |||
347 | // transformed version. 'ArgumentIndexMapping' holds the mapping from | |||
348 | // old argument position to new. | |||
349 | for (unsigned I = 0, IE = TransformedFunction.ArgumentIndexMapping.size(); | |||
350 | I < IE; ++I) { | |||
351 | unsigned TransformedIndex = TransformedFunction.ArgumentIndexMapping[I]; | |||
352 | ArgumentAttributes[TransformedIndex] = CallSiteAttrs.getParamAttributes(I); | |||
353 | } | |||
354 | ||||
355 | // Copy annotations on varargs arguments. | |||
356 | for (unsigned I = TransformedFunction.OriginalType->getNumParams(), | |||
357 | IE = CallSiteAttrs.getNumAttrSets(); | |||
358 | I < IE; ++I) { | |||
359 | ArgumentAttributes.push_back(CallSiteAttrs.getParamAttributes(I)); | |||
360 | } | |||
361 | ||||
362 | return AttributeList::get(Ctx, CallSiteAttrs.getFnAttributes(), | |||
363 | CallSiteAttrs.getRetAttributes(), | |||
364 | llvm::makeArrayRef(ArgumentAttributes)); | |||
365 | } | |||
366 | ||||
367 | class DataFlowSanitizer { | |||
368 | friend struct DFSanFunction; | |||
369 | friend class DFSanVisitor; | |||
370 | ||||
371 | enum { ShadowWidthBits = 8, ShadowWidthBytes = ShadowWidthBits / 8 }; | |||
372 | ||||
373 | enum { OriginWidthBits = 32, OriginWidthBytes = OriginWidthBits / 8 }; | |||
374 | ||||
375 | /// Which ABI should be used for instrumented functions? | |||
376 | enum InstrumentedABI { | |||
377 | /// Argument and return value labels are passed through additional | |||
378 | /// arguments and by modifying the return type. | |||
379 | IA_Args, | |||
380 | ||||
381 | /// Argument and return value labels are passed through TLS variables | |||
382 | /// __dfsan_arg_tls and __dfsan_retval_tls. | |||
383 | IA_TLS | |||
384 | }; | |||
385 | ||||
386 | /// How should calls to uninstrumented functions be handled? | |||
387 | enum WrapperKind { | |||
388 | /// This function is present in an uninstrumented form but we don't know | |||
389 | /// how it should be handled. Print a warning and call the function anyway. | |||
390 | /// Don't label the return value. | |||
391 | WK_Warning, | |||
392 | ||||
393 | /// This function does not write to (user-accessible) memory, and its return | |||
394 | /// value is unlabelled. | |||
395 | WK_Discard, | |||
396 | ||||
397 | /// This function does not write to (user-accessible) memory, and the label | |||
398 | /// of its return value is the union of the label of its arguments. | |||
399 | WK_Functional, | |||
400 | ||||
401 | /// Instead of calling the function, a custom wrapper __dfsw_F is called, | |||
402 | /// where F is the name of the function. This function may wrap the | |||
403 | /// original function or provide its own implementation. This is similar to | |||
404 | /// the IA_Args ABI, except that IA_Args uses a struct return type to | |||
405 | /// pass the return value shadow in a register, while WK_Custom uses an | |||
406 | /// extra pointer argument to return the shadow. This allows the wrapped | |||
407 | /// form of the function type to be expressed in C. | |||
408 | WK_Custom | |||
409 | }; | |||
410 | ||||
411 | Module *Mod; | |||
412 | LLVMContext *Ctx; | |||
413 | Type *Int8Ptr; | |||
414 | IntegerType *OriginTy; | |||
415 | PointerType *OriginPtrTy; | |||
416 | ConstantInt *ZeroOrigin; | |||
417 | /// The shadow type for all primitive types and vector types. | |||
418 | IntegerType *PrimitiveShadowTy; | |||
419 | PointerType *PrimitiveShadowPtrTy; | |||
420 | IntegerType *IntptrTy; | |||
421 | ConstantInt *ZeroPrimitiveShadow; | |||
422 | Constant *ArgTLS; | |||
423 | ArrayType *ArgOriginTLSTy; | |||
424 | Constant *ArgOriginTLS; | |||
425 | Constant *RetvalTLS; | |||
426 | Constant *RetvalOriginTLS; | |||
427 | FunctionType *DFSanUnionLoadFnTy; | |||
428 | FunctionType *DFSanLoadLabelAndOriginFnTy; | |||
429 | FunctionType *DFSanUnimplementedFnTy; | |||
430 | FunctionType *DFSanSetLabelFnTy; | |||
431 | FunctionType *DFSanNonzeroLabelFnTy; | |||
432 | FunctionType *DFSanVarargWrapperFnTy; | |||
433 | FunctionType *DFSanCmpCallbackFnTy; | |||
434 | FunctionType *DFSanLoadStoreCallbackFnTy; | |||
435 | FunctionType *DFSanMemTransferCallbackFnTy; | |||
436 | FunctionType *DFSanChainOriginFnTy; | |||
437 | FunctionType *DFSanChainOriginIfTaintedFnTy; | |||
438 | FunctionType *DFSanMemOriginTransferFnTy; | |||
439 | FunctionType *DFSanMaybeStoreOriginFnTy; | |||
440 | FunctionCallee DFSanUnionLoadFn; | |||
441 | FunctionCallee DFSanLoadLabelAndOriginFn; | |||
442 | FunctionCallee DFSanUnimplementedFn; | |||
443 | FunctionCallee DFSanSetLabelFn; | |||
444 | FunctionCallee DFSanNonzeroLabelFn; | |||
445 | FunctionCallee DFSanVarargWrapperFn; | |||
446 | FunctionCallee DFSanLoadCallbackFn; | |||
447 | FunctionCallee DFSanStoreCallbackFn; | |||
448 | FunctionCallee DFSanMemTransferCallbackFn; | |||
449 | FunctionCallee DFSanCmpCallbackFn; | |||
450 | FunctionCallee DFSanChainOriginFn; | |||
451 | FunctionCallee DFSanChainOriginIfTaintedFn; | |||
452 | FunctionCallee DFSanMemOriginTransferFn; | |||
453 | FunctionCallee DFSanMaybeStoreOriginFn; | |||
454 | SmallPtrSet<Value *, 16> DFSanRuntimeFunctions; | |||
455 | MDNode *ColdCallWeights; | |||
456 | MDNode *OriginStoreWeights; | |||
457 | DFSanABIList ABIList; | |||
458 | DenseMap<Value *, Function *> UnwrappedFnMap; | |||
459 | AttrBuilder ReadOnlyNoneAttrs; | |||
460 | ||||
461 | /// Memory map parameters used in calculation mapping application addresses | |||
462 | /// to shadow addresses and origin addresses. | |||
463 | const MemoryMapParams *MapParams; | |||
464 | ||||
465 | Value *getShadowOffset(Value *Addr, IRBuilder<> &IRB); | |||
466 | Value *getShadowAddress(Value *Addr, Instruction *Pos); | |||
467 | Value *getShadowAddress(Value *Addr, Instruction *Pos, Value *ShadowOffset); | |||
468 | std::pair<Value *, Value *> | |||
469 | getShadowOriginAddress(Value *Addr, Align InstAlignment, Instruction *Pos); | |||
470 | bool isInstrumented(const Function *F); | |||
471 | bool isInstrumented(const GlobalAlias *GA); | |||
472 | FunctionType *getArgsFunctionType(FunctionType *T); | |||
473 | FunctionType *getTrampolineFunctionType(FunctionType *T); | |||
474 | TransformedFunction getCustomFunctionType(FunctionType *T); | |||
475 | InstrumentedABI getInstrumentedABI(); | |||
476 | WrapperKind getWrapperKind(Function *F); | |||
477 | void addGlobalNameSuffix(GlobalValue *GV); | |||
478 | Function *buildWrapperFunction(Function *F, StringRef NewFName, | |||
479 | GlobalValue::LinkageTypes NewFLink, | |||
480 | FunctionType *NewFT); | |||
481 | Constant *getOrBuildTrampolineFunction(FunctionType *FT, StringRef FName); | |||
482 | void initializeCallbackFunctions(Module &M); | |||
483 | void initializeRuntimeFunctions(Module &M); | |||
484 | void injectMetadataGlobals(Module &M); | |||
485 | bool initializeModule(Module &M); | |||
486 | ||||
487 | /// Advances \p OriginAddr to point to the next 32-bit origin and then loads | |||
488 | /// from it. Returns the origin's loaded value. | |||
489 | Value *loadNextOrigin(Instruction *Pos, Align OriginAlign, | |||
490 | Value **OriginAddr); | |||
491 | ||||
492 | /// Returns whether the given load byte size is amenable to inlined | |||
493 | /// optimization patterns. | |||
494 | bool hasLoadSizeForFastPath(uint64_t Size); | |||
495 | ||||
496 | /// Returns whether the pass tracks origins. Supports only TLS ABI mode. | |||
497 | bool shouldTrackOrigins(); | |||
498 | ||||
499 | /// Returns whether the pass tracks labels for struct fields and array | |||
500 | /// indices. Supports only TLS ABI mode. | |||
501 | bool shouldTrackFieldsAndIndices(); | |||
502 | ||||
503 | /// Returns a zero constant with the shadow type of OrigTy. | |||
504 | /// | |||
505 | /// getZeroShadow({T1,T2,...}) = {getZeroShadow(T1),getZeroShadow(T2,...} | |||
506 | /// getZeroShadow([n x T]) = [n x getZeroShadow(T)] | |||
507 | /// getZeroShadow(other type) = i16(0) | |||
508 | /// | |||
509 | /// Note that a zero shadow is always i16(0) when shouldTrackFieldsAndIndices | |||
510 | /// returns false. | |||
511 | Constant *getZeroShadow(Type *OrigTy); | |||
512 | /// Returns a zero constant with the shadow type of V's type. | |||
513 | Constant *getZeroShadow(Value *V); | |||
514 | ||||
515 | /// Checks if V is a zero shadow. | |||
516 | bool isZeroShadow(Value *V); | |||
517 | ||||
518 | /// Returns the shadow type of OrigTy. | |||
519 | /// | |||
520 | /// getShadowTy({T1,T2,...}) = {getShadowTy(T1),getShadowTy(T2),...} | |||
521 | /// getShadowTy([n x T]) = [n x getShadowTy(T)] | |||
522 | /// getShadowTy(other type) = i16 | |||
523 | /// | |||
524 | /// Note that a shadow type is always i16 when shouldTrackFieldsAndIndices | |||
525 | /// returns false. | |||
526 | Type *getShadowTy(Type *OrigTy); | |||
527 | /// Returns the shadow type of of V's type. | |||
528 | Type *getShadowTy(Value *V); | |||
529 | ||||
530 | const uint64_t NumOfElementsInArgOrgTLS = ArgTLSSize / OriginWidthBytes; | |||
531 | ||||
532 | public: | |||
533 | DataFlowSanitizer(const std::vector<std::string> &ABIListFiles); | |||
534 | ||||
535 | bool runImpl(Module &M); | |||
536 | }; | |||
537 | ||||
538 | struct DFSanFunction { | |||
539 | DataFlowSanitizer &DFS; | |||
540 | Function *F; | |||
541 | DominatorTree DT; | |||
542 | DataFlowSanitizer::InstrumentedABI IA; | |||
543 | bool IsNativeABI; | |||
544 | AllocaInst *LabelReturnAlloca = nullptr; | |||
545 | AllocaInst *OriginReturnAlloca = nullptr; | |||
546 | DenseMap<Value *, Value *> ValShadowMap; | |||
547 | DenseMap<Value *, Value *> ValOriginMap; | |||
548 | DenseMap<AllocaInst *, AllocaInst *> AllocaShadowMap; | |||
549 | DenseMap<AllocaInst *, AllocaInst *> AllocaOriginMap; | |||
550 | ||||
551 | struct PHIFixupElement { | |||
552 | PHINode *Phi; | |||
553 | PHINode *ShadowPhi; | |||
554 | PHINode *OriginPhi; | |||
555 | }; | |||
556 | std::vector<PHIFixupElement> PHIFixups; | |||
557 | ||||
558 | DenseSet<Instruction *> SkipInsts; | |||
559 | std::vector<Value *> NonZeroChecks; | |||
560 | ||||
561 | struct CachedShadow { | |||
562 | BasicBlock *Block; // The block where Shadow is defined. | |||
563 | Value *Shadow; | |||
564 | }; | |||
565 | /// Maps a value to its latest shadow value in terms of domination tree. | |||
566 | DenseMap<std::pair<Value *, Value *>, CachedShadow> CachedShadows; | |||
567 | /// Maps a value to its latest collapsed shadow value it was converted to in | |||
568 | /// terms of domination tree. When ClDebugNonzeroLabels is on, this cache is | |||
569 | /// used at a post process where CFG blocks are split. So it does not cache | |||
570 | /// BasicBlock like CachedShadows, but uses domination between values. | |||
571 | DenseMap<Value *, Value *> CachedCollapsedShadows; | |||
572 | DenseMap<Value *, std::set<Value *>> ShadowElements; | |||
573 | ||||
574 | DFSanFunction(DataFlowSanitizer &DFS, Function *F, bool IsNativeABI) | |||
575 | : DFS(DFS), F(F), IA(DFS.getInstrumentedABI()), IsNativeABI(IsNativeABI) { | |||
576 | DT.recalculate(*F); | |||
577 | } | |||
578 | ||||
579 | /// Computes the shadow address for a given function argument. | |||
580 | /// | |||
581 | /// Shadow = ArgTLS+ArgOffset. | |||
582 | Value *getArgTLS(Type *T, unsigned ArgOffset, IRBuilder<> &IRB); | |||
583 | ||||
584 | /// Computes the shadow address for a return value. | |||
585 | Value *getRetvalTLS(Type *T, IRBuilder<> &IRB); | |||
586 | ||||
587 | /// Computes the origin address for a given function argument. | |||
588 | /// | |||
589 | /// Origin = ArgOriginTLS[ArgNo]. | |||
590 | Value *getArgOriginTLS(unsigned ArgNo, IRBuilder<> &IRB); | |||
591 | ||||
592 | /// Computes the origin address for a return value. | |||
593 | Value *getRetvalOriginTLS(); | |||
594 | ||||
595 | Value *getOrigin(Value *V); | |||
596 | void setOrigin(Instruction *I, Value *Origin); | |||
597 | /// Generates IR to compute the origin of the last operand with a taint label. | |||
598 | Value *combineOperandOrigins(Instruction *Inst); | |||
599 | /// Before the instruction Pos, generates IR to compute the last origin with a | |||
600 | /// taint label. Labels and origins are from vectors Shadows and Origins | |||
601 | /// correspondingly. The generated IR is like | |||
602 | /// Sn-1 != Zero ? On-1: ... S2 != Zero ? O2: S1 != Zero ? O1: O0 | |||
603 | /// When Zero is nullptr, it uses ZeroPrimitiveShadow. Otherwise it can be | |||
604 | /// zeros with other bitwidths. | |||
605 | Value *combineOrigins(const std::vector<Value *> &Shadows, | |||
606 | const std::vector<Value *> &Origins, Instruction *Pos, | |||
607 | ConstantInt *Zero = nullptr); | |||
608 | ||||
609 | Value *getShadow(Value *V); | |||
610 | void setShadow(Instruction *I, Value *Shadow); | |||
611 | /// Generates IR to compute the union of the two given shadows, inserting it | |||
612 | /// before Pos. The combined value is with primitive type. | |||
613 | Value *combineShadows(Value *V1, Value *V2, Instruction *Pos); | |||
614 | /// Combines the shadow values of V1 and V2, then converts the combined value | |||
615 | /// with primitive type into a shadow value with the original type T. | |||
616 | Value *combineShadowsThenConvert(Type *T, Value *V1, Value *V2, | |||
617 | Instruction *Pos); | |||
618 | Value *combineOperandShadows(Instruction *Inst); | |||
619 | ||||
620 | /// Generates IR to load shadow and origin corresponding to bytes [\p | |||
621 | /// Addr, \p Addr + \p Size), where addr has alignment \p | |||
622 | /// InstAlignment, and take the union of each of those shadows. The returned | |||
623 | /// shadow always has primitive type. | |||
624 | /// | |||
625 | /// When tracking loads is enabled, the returned origin is a chain at the | |||
626 | /// current stack if the returned shadow is tainted. | |||
627 | std::pair<Value *, Value *> loadShadowOrigin(Value *Addr, uint64_t Size, | |||
628 | Align InstAlignment, | |||
629 | Instruction *Pos); | |||
630 | ||||
631 | void storePrimitiveShadowOrigin(Value *Addr, uint64_t Size, | |||
632 | Align InstAlignment, Value *PrimitiveShadow, | |||
633 | Value *Origin, Instruction *Pos); | |||
634 | /// Applies PrimitiveShadow to all primitive subtypes of T, returning | |||
635 | /// the expanded shadow value. | |||
636 | /// | |||
637 | /// EFP({T1,T2, ...}, PS) = {EFP(T1,PS),EFP(T2,PS),...} | |||
638 | /// EFP([n x T], PS) = [n x EFP(T,PS)] | |||
639 | /// EFP(other types, PS) = PS | |||
640 | Value *expandFromPrimitiveShadow(Type *T, Value *PrimitiveShadow, | |||
641 | Instruction *Pos); | |||
642 | /// Collapses Shadow into a single primitive shadow value, unioning all | |||
643 | /// primitive shadow values in the process. Returns the final primitive | |||
644 | /// shadow value. | |||
645 | /// | |||
646 | /// CTP({V1,V2, ...}) = UNION(CFP(V1,PS),CFP(V2,PS),...) | |||
647 | /// CTP([V1,V2,...]) = UNION(CFP(V1,PS),CFP(V2,PS),...) | |||
648 | /// CTP(other types, PS) = PS | |||
649 | Value *collapseToPrimitiveShadow(Value *Shadow, Instruction *Pos); | |||
650 | ||||
651 | void storeZeroPrimitiveShadow(Value *Addr, uint64_t Size, Align ShadowAlign, | |||
652 | Instruction *Pos); | |||
653 | ||||
654 | Align getShadowAlign(Align InstAlignment); | |||
655 | ||||
656 | private: | |||
657 | /// Collapses the shadow with aggregate type into a single primitive shadow | |||
658 | /// value. | |||
659 | template <class AggregateType> | |||
660 | Value *collapseAggregateShadow(AggregateType *AT, Value *Shadow, | |||
661 | IRBuilder<> &IRB); | |||
662 | ||||
663 | Value *collapseToPrimitiveShadow(Value *Shadow, IRBuilder<> &IRB); | |||
664 | ||||
665 | /// Returns the shadow value of an argument A. | |||
666 | Value *getShadowForTLSArgument(Argument *A); | |||
667 | ||||
668 | /// The fast path of loading shadows. | |||
669 | std::pair<Value *, Value *> | |||
670 | loadShadowFast(Value *ShadowAddr, Value *OriginAddr, uint64_t Size, | |||
671 | Align ShadowAlign, Align OriginAlign, Value *FirstOrigin, | |||
672 | Instruction *Pos); | |||
673 | ||||
674 | Align getOriginAlign(Align InstAlignment); | |||
675 | ||||
676 | /// Because 4 contiguous bytes share one 4-byte origin, the most accurate load | |||
677 | /// is __dfsan_load_label_and_origin. This function returns the union of all | |||
678 | /// labels and the origin of the first taint label. However this is an | |||
679 | /// additional call with many instructions. To ensure common cases are fast, | |||
680 | /// checks if it is possible to load labels and origins without using the | |||
681 | /// callback function. | |||
682 | /// | |||
683 | /// When enabling tracking load instructions, we always use | |||
684 | /// __dfsan_load_label_and_origin to reduce code size. | |||
685 | bool useCallbackLoadLabelAndOrigin(uint64_t Size, Align InstAlignment); | |||
686 | ||||
687 | /// Returns a chain at the current stack with previous origin V. | |||
688 | Value *updateOrigin(Value *V, IRBuilder<> &IRB); | |||
689 | ||||
690 | /// Returns a chain at the current stack with previous origin V if Shadow is | |||
691 | /// tainted. | |||
692 | Value *updateOriginIfTainted(Value *Shadow, Value *Origin, IRBuilder<> &IRB); | |||
693 | ||||
694 | /// Creates an Intptr = Origin | Origin << 32 if Intptr's size is 64. Returns | |||
695 | /// Origin otherwise. | |||
696 | Value *originToIntptr(IRBuilder<> &IRB, Value *Origin); | |||
697 | ||||
698 | /// Stores Origin into the address range [StoreOriginAddr, StoreOriginAddr + | |||
699 | /// Size). | |||
700 | void paintOrigin(IRBuilder<> &IRB, Value *Origin, Value *StoreOriginAddr, | |||
701 | uint64_t StoreOriginSize, Align Alignment); | |||
702 | ||||
703 | /// Stores Origin in terms of its Shadow value. | |||
704 | /// * Do not write origins for zero shadows because we do not trace origins | |||
705 | /// for untainted sinks. | |||
706 | /// * Use __dfsan_maybe_store_origin if there are too many origin store | |||
707 | /// instrumentations. | |||
708 | void storeOrigin(Instruction *Pos, Value *Addr, uint64_t Size, Value *Shadow, | |||
709 | Value *Origin, Value *StoreOriginAddr, Align InstAlignment); | |||
710 | ||||
711 | /// Convert a scalar value to an i1 by comparing with 0. | |||
712 | Value *convertToBool(Value *V, IRBuilder<> &IRB, const Twine &Name = ""); | |||
713 | ||||
714 | bool shouldInstrumentWithCall(); | |||
715 | ||||
716 | /// Generates IR to load shadow and origin corresponding to bytes [\p | |||
717 | /// Addr, \p Addr + \p Size), where addr has alignment \p | |||
718 | /// InstAlignment, and take the union of each of those shadows. The returned | |||
719 | /// shadow always has primitive type. | |||
720 | std::pair<Value *, Value *> | |||
721 | loadShadowOriginSansLoadTracking(Value *Addr, uint64_t Size, | |||
722 | Align InstAlignment, Instruction *Pos); | |||
723 | int NumOriginStores = 0; | |||
724 | }; | |||
725 | ||||
726 | class DFSanVisitor : public InstVisitor<DFSanVisitor> { | |||
727 | public: | |||
728 | DFSanFunction &DFSF; | |||
729 | ||||
730 | DFSanVisitor(DFSanFunction &DFSF) : DFSF(DFSF) {} | |||
731 | ||||
732 | const DataLayout &getDataLayout() const { | |||
733 | return DFSF.F->getParent()->getDataLayout(); | |||
734 | } | |||
735 | ||||
736 | // Combines shadow values and origins for all of I's operands. | |||
737 | void visitInstOperands(Instruction &I); | |||
738 | ||||
739 | void visitUnaryOperator(UnaryOperator &UO); | |||
740 | void visitBinaryOperator(BinaryOperator &BO); | |||
741 | void visitBitCastInst(BitCastInst &BCI); | |||
742 | void visitCastInst(CastInst &CI); | |||
743 | void visitCmpInst(CmpInst &CI); | |||
744 | void visitLandingPadInst(LandingPadInst &LPI); | |||
745 | void visitGetElementPtrInst(GetElementPtrInst &GEPI); | |||
746 | void visitLoadInst(LoadInst &LI); | |||
747 | void visitStoreInst(StoreInst &SI); | |||
748 | void visitAtomicRMWInst(AtomicRMWInst &I); | |||
749 | void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I); | |||
750 | void visitReturnInst(ReturnInst &RI); | |||
751 | void visitCallBase(CallBase &CB); | |||
752 | void visitPHINode(PHINode &PN); | |||
753 | void visitExtractElementInst(ExtractElementInst &I); | |||
754 | void visitInsertElementInst(InsertElementInst &I); | |||
755 | void visitShuffleVectorInst(ShuffleVectorInst &I); | |||
756 | void visitExtractValueInst(ExtractValueInst &I); | |||
757 | void visitInsertValueInst(InsertValueInst &I); | |||
758 | void visitAllocaInst(AllocaInst &I); | |||
759 | void visitSelectInst(SelectInst &I); | |||
760 | void visitMemSetInst(MemSetInst &I); | |||
761 | void visitMemTransferInst(MemTransferInst &I); | |||
762 | ||||
763 | private: | |||
764 | void visitCASOrRMW(Align InstAlignment, Instruction &I); | |||
765 | ||||
766 | // Returns false when this is an invoke of a custom function. | |||
767 | bool visitWrappedCallBase(Function &F, CallBase &CB); | |||
768 | ||||
769 | // Combines origins for all of I's operands. | |||
770 | void visitInstOperandOrigins(Instruction &I); | |||
771 | ||||
772 | void addShadowArguments(Function &F, CallBase &CB, std::vector<Value *> &Args, | |||
773 | IRBuilder<> &IRB); | |||
774 | ||||
775 | void addOriginArguments(Function &F, CallBase &CB, std::vector<Value *> &Args, | |||
776 | IRBuilder<> &IRB); | |||
777 | }; | |||
778 | ||||
779 | } // end anonymous namespace | |||
780 | ||||
781 | DataFlowSanitizer::DataFlowSanitizer( | |||
782 | const std::vector<std::string> &ABIListFiles) { | |||
783 | std::vector<std::string> AllABIListFiles(std::move(ABIListFiles)); | |||
784 | llvm::append_range(AllABIListFiles, ClABIListFiles); | |||
785 | // FIXME: should we propagate vfs::FileSystem to this constructor? | |||
786 | ABIList.set( | |||
787 | SpecialCaseList::createOrDie(AllABIListFiles, *vfs::getRealFileSystem())); | |||
788 | } | |||
789 | ||||
790 | FunctionType *DataFlowSanitizer::getArgsFunctionType(FunctionType *T) { | |||
791 | SmallVector<Type *, 4> ArgTypes(T->param_begin(), T->param_end()); | |||
792 | ArgTypes.append(T->getNumParams(), PrimitiveShadowTy); | |||
793 | if (T->isVarArg()) | |||
794 | ArgTypes.push_back(PrimitiveShadowPtrTy); | |||
795 | Type *RetType = T->getReturnType(); | |||
796 | if (!RetType->isVoidTy()) | |||
797 | RetType = StructType::get(RetType, PrimitiveShadowTy); | |||
798 | return FunctionType::get(RetType, ArgTypes, T->isVarArg()); | |||
799 | } | |||
800 | ||||
801 | FunctionType *DataFlowSanitizer::getTrampolineFunctionType(FunctionType *T) { | |||
802 | assert(!T->isVarArg())((void)0); | |||
803 | SmallVector<Type *, 4> ArgTypes; | |||
804 | ArgTypes.push_back(T->getPointerTo()); | |||
805 | ArgTypes.append(T->param_begin(), T->param_end()); | |||
806 | ArgTypes.append(T->getNumParams(), PrimitiveShadowTy); | |||
807 | Type *RetType = T->getReturnType(); | |||
808 | if (!RetType->isVoidTy()) | |||
809 | ArgTypes.push_back(PrimitiveShadowPtrTy); | |||
810 | ||||
811 | if (shouldTrackOrigins()) { | |||
812 | ArgTypes.append(T->getNumParams(), OriginTy); | |||
813 | if (!RetType->isVoidTy()) | |||
814 | ArgTypes.push_back(OriginPtrTy); | |||
815 | } | |||
816 | ||||
817 | return FunctionType::get(T->getReturnType(), ArgTypes, false); | |||
818 | } | |||
819 | ||||
820 | TransformedFunction DataFlowSanitizer::getCustomFunctionType(FunctionType *T) { | |||
821 | SmallVector<Type *, 4> ArgTypes; | |||
822 | ||||
823 | // Some parameters of the custom function being constructed are | |||
824 | // parameters of T. Record the mapping from parameters of T to | |||
825 | // parameters of the custom function, so that parameter attributes | |||
826 | // at call sites can be updated. | |||
827 | std::vector<unsigned> ArgumentIndexMapping; | |||
828 | for (unsigned I = 0, E = T->getNumParams(); I != E; ++I) { | |||
829 | Type *ParamType = T->getParamType(I); | |||
830 | FunctionType *FT; | |||
831 | if (isa<PointerType>(ParamType) && | |||
832 | (FT = dyn_cast<FunctionType>(ParamType->getPointerElementType()))) { | |||
833 | ArgumentIndexMapping.push_back(ArgTypes.size()); | |||
834 | ArgTypes.push_back(getTrampolineFunctionType(FT)->getPointerTo()); | |||
835 | ArgTypes.push_back(Type::getInt8PtrTy(*Ctx)); | |||
836 | } else { | |||
837 | ArgumentIndexMapping.push_back(ArgTypes.size()); | |||
838 | ArgTypes.push_back(ParamType); | |||
839 | } | |||
840 | } | |||
841 | for (unsigned I = 0, E = T->getNumParams(); I != E; ++I) | |||
842 | ArgTypes.push_back(PrimitiveShadowTy); | |||
843 | if (T->isVarArg()) | |||
844 | ArgTypes.push_back(PrimitiveShadowPtrTy); | |||
845 | Type *RetType = T->getReturnType(); | |||
846 | if (!RetType->isVoidTy()) | |||
847 | ArgTypes.push_back(PrimitiveShadowPtrTy); | |||
848 | ||||
849 | if (shouldTrackOrigins()) { | |||
850 | for (unsigned I = 0, E = T->getNumParams(); I != E; ++I) | |||
851 | ArgTypes.push_back(OriginTy); | |||
852 | if (T->isVarArg()) | |||
853 | ArgTypes.push_back(OriginPtrTy); | |||
854 | if (!RetType->isVoidTy()) | |||
855 | ArgTypes.push_back(OriginPtrTy); | |||
856 | } | |||
857 | ||||
858 | return TransformedFunction( | |||
859 | T, FunctionType::get(T->getReturnType(), ArgTypes, T->isVarArg()), | |||
860 | ArgumentIndexMapping); | |||
861 | } | |||
862 | ||||
863 | bool DataFlowSanitizer::isZeroShadow(Value *V) { | |||
864 | if (!shouldTrackFieldsAndIndices()) | |||
865 | return ZeroPrimitiveShadow == V; | |||
866 | ||||
867 | Type *T = V->getType(); | |||
868 | if (!isa<ArrayType>(T) && !isa<StructType>(T)) { | |||
869 | if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) | |||
870 | return CI->isZero(); | |||
871 | return false; | |||
872 | } | |||
873 | ||||
874 | return isa<ConstantAggregateZero>(V); | |||
875 | } | |||
876 | ||||
877 | bool DataFlowSanitizer::hasLoadSizeForFastPath(uint64_t Size) { | |||
878 | uint64_t ShadowSize = Size * ShadowWidthBytes; | |||
879 | return ShadowSize % 8 == 0 || ShadowSize == 4; | |||
880 | } | |||
881 | ||||
882 | bool DataFlowSanitizer::shouldTrackOrigins() { | |||
883 | static const bool ShouldTrackOrigins = | |||
884 | ClTrackOrigins && getInstrumentedABI() == DataFlowSanitizer::IA_TLS; | |||
885 | return ShouldTrackOrigins; | |||
886 | } | |||
887 | ||||
888 | bool DataFlowSanitizer::shouldTrackFieldsAndIndices() { | |||
889 | return getInstrumentedABI() == DataFlowSanitizer::IA_TLS; | |||
890 | } | |||
891 | ||||
892 | Constant *DataFlowSanitizer::getZeroShadow(Type *OrigTy) { | |||
893 | if (!shouldTrackFieldsAndIndices()) | |||
894 | return ZeroPrimitiveShadow; | |||
895 | ||||
896 | if (!isa<ArrayType>(OrigTy) && !isa<StructType>(OrigTy)) | |||
897 | return ZeroPrimitiveShadow; | |||
898 | Type *ShadowTy = getShadowTy(OrigTy); | |||
899 | return ConstantAggregateZero::get(ShadowTy); | |||
900 | } | |||
901 | ||||
902 | Constant *DataFlowSanitizer::getZeroShadow(Value *V) { | |||
903 | return getZeroShadow(V->getType()); | |||
904 | } | |||
905 | ||||
906 | static Value *expandFromPrimitiveShadowRecursive( | |||
907 | Value *Shadow, SmallVector<unsigned, 4> &Indices, Type *SubShadowTy, | |||
908 | Value *PrimitiveShadow, IRBuilder<> &IRB) { | |||
909 | if (!isa<ArrayType>(SubShadowTy) && !isa<StructType>(SubShadowTy)) | |||
910 | return IRB.CreateInsertValue(Shadow, PrimitiveShadow, Indices); | |||
911 | ||||
912 | if (ArrayType *AT = dyn_cast<ArrayType>(SubShadowTy)) { | |||
913 | for (unsigned Idx = 0; Idx < AT->getNumElements(); Idx++) { | |||
914 | Indices.push_back(Idx); | |||
915 | Shadow = expandFromPrimitiveShadowRecursive( | |||
916 | Shadow, Indices, AT->getElementType(), PrimitiveShadow, IRB); | |||
917 | Indices.pop_back(); | |||
918 | } | |||
919 | return Shadow; | |||
920 | } | |||
921 | ||||
922 | if (StructType *ST = dyn_cast<StructType>(SubShadowTy)) { | |||
923 | for (unsigned Idx = 0; Idx < ST->getNumElements(); Idx++) { | |||
924 | Indices.push_back(Idx); | |||
925 | Shadow = expandFromPrimitiveShadowRecursive( | |||
926 | Shadow, Indices, ST->getElementType(Idx), PrimitiveShadow, IRB); | |||
927 | Indices.pop_back(); | |||
928 | } | |||
929 | return Shadow; | |||
930 | } | |||
931 | llvm_unreachable("Unexpected shadow type")__builtin_unreachable(); | |||
932 | } | |||
933 | ||||
934 | bool DFSanFunction::shouldInstrumentWithCall() { | |||
935 | return ClInstrumentWithCallThreshold >= 0 && | |||
936 | NumOriginStores >= ClInstrumentWithCallThreshold; | |||
937 | } | |||
938 | ||||
939 | Value *DFSanFunction::expandFromPrimitiveShadow(Type *T, Value *PrimitiveShadow, | |||
940 | Instruction *Pos) { | |||
941 | Type *ShadowTy = DFS.getShadowTy(T); | |||
942 | ||||
943 | if (!isa<ArrayType>(ShadowTy) && !isa<StructType>(ShadowTy)) | |||
944 | return PrimitiveShadow; | |||
945 | ||||
946 | if (DFS.isZeroShadow(PrimitiveShadow)) | |||
947 | return DFS.getZeroShadow(ShadowTy); | |||
948 | ||||
949 | IRBuilder<> IRB(Pos); | |||
950 | SmallVector<unsigned, 4> Indices; | |||
951 | Value *Shadow = UndefValue::get(ShadowTy); | |||
952 | Shadow = expandFromPrimitiveShadowRecursive(Shadow, Indices, ShadowTy, | |||
953 | PrimitiveShadow, IRB); | |||
954 | ||||
955 | // Caches the primitive shadow value that built the shadow value. | |||
956 | CachedCollapsedShadows[Shadow] = PrimitiveShadow; | |||
957 | return Shadow; | |||
958 | } | |||
959 | ||||
960 | template <class AggregateType> | |||
961 | Value *DFSanFunction::collapseAggregateShadow(AggregateType *AT, Value *Shadow, | |||
962 | IRBuilder<> &IRB) { | |||
963 | if (!AT->getNumElements()) | |||
964 | return DFS.ZeroPrimitiveShadow; | |||
965 | ||||
966 | Value *FirstItem = IRB.CreateExtractValue(Shadow, 0); | |||
967 | Value *Aggregator = collapseToPrimitiveShadow(FirstItem, IRB); | |||
968 | ||||
969 | for (unsigned Idx = 1; Idx < AT->getNumElements(); Idx++) { | |||
970 | Value *ShadowItem = IRB.CreateExtractValue(Shadow, Idx); | |||
971 | Value *ShadowInner = collapseToPrimitiveShadow(ShadowItem, IRB); | |||
972 | Aggregator = IRB.CreateOr(Aggregator, ShadowInner); | |||
973 | } | |||
974 | return Aggregator; | |||
975 | } | |||
976 | ||||
977 | Value *DFSanFunction::collapseToPrimitiveShadow(Value *Shadow, | |||
978 | IRBuilder<> &IRB) { | |||
979 | Type *ShadowTy = Shadow->getType(); | |||
980 | if (!isa<ArrayType>(ShadowTy) && !isa<StructType>(ShadowTy)) | |||
981 | return Shadow; | |||
982 | if (ArrayType *AT = dyn_cast<ArrayType>(ShadowTy)) | |||
983 | return collapseAggregateShadow<>(AT, Shadow, IRB); | |||
984 | if (StructType *ST = dyn_cast<StructType>(ShadowTy)) | |||
985 | return collapseAggregateShadow<>(ST, Shadow, IRB); | |||
986 | llvm_unreachable("Unexpected shadow type")__builtin_unreachable(); | |||
987 | } | |||
988 | ||||
989 | Value *DFSanFunction::collapseToPrimitiveShadow(Value *Shadow, | |||
990 | Instruction *Pos) { | |||
991 | Type *ShadowTy = Shadow->getType(); | |||
992 | if (!isa<ArrayType>(ShadowTy) && !isa<StructType>(ShadowTy)) | |||
993 | return Shadow; | |||
994 | ||||
995 | assert(DFS.shouldTrackFieldsAndIndices())((void)0); | |||
996 | ||||
997 | // Checks if the cached collapsed shadow value dominates Pos. | |||
998 | Value *&CS = CachedCollapsedShadows[Shadow]; | |||
999 | if (CS && DT.dominates(CS, Pos)) | |||
1000 | return CS; | |||
1001 | ||||
1002 | IRBuilder<> IRB(Pos); | |||
1003 | Value *PrimitiveShadow = collapseToPrimitiveShadow(Shadow, IRB); | |||
1004 | // Caches the converted primitive shadow value. | |||
1005 | CS = PrimitiveShadow; | |||
1006 | return PrimitiveShadow; | |||
1007 | } | |||
1008 | ||||
1009 | Type *DataFlowSanitizer::getShadowTy(Type *OrigTy) { | |||
1010 | if (!shouldTrackFieldsAndIndices()) | |||
1011 | return PrimitiveShadowTy; | |||
1012 | ||||
1013 | if (!OrigTy->isSized()) | |||
1014 | return PrimitiveShadowTy; | |||
1015 | if (isa<IntegerType>(OrigTy)) | |||
1016 | return PrimitiveShadowTy; | |||
1017 | if (isa<VectorType>(OrigTy)) | |||
1018 | return PrimitiveShadowTy; | |||
1019 | if (ArrayType *AT = dyn_cast<ArrayType>(OrigTy)) | |||
1020 | return ArrayType::get(getShadowTy(AT->getElementType()), | |||
1021 | AT->getNumElements()); | |||
1022 | if (StructType *ST = dyn_cast<StructType>(OrigTy)) { | |||
1023 | SmallVector<Type *, 4> Elements; | |||
1024 | for (unsigned I = 0, N = ST->getNumElements(); I < N; ++I) | |||
1025 | Elements.push_back(getShadowTy(ST->getElementType(I))); | |||
1026 | return StructType::get(*Ctx, Elements); | |||
1027 | } | |||
1028 | return PrimitiveShadowTy; | |||
1029 | } | |||
1030 | ||||
1031 | Type *DataFlowSanitizer::getShadowTy(Value *V) { | |||
1032 | return getShadowTy(V->getType()); | |||
1033 | } | |||
1034 | ||||
1035 | bool DataFlowSanitizer::initializeModule(Module &M) { | |||
1036 | Triple TargetTriple(M.getTargetTriple()); | |||
1037 | const DataLayout &DL = M.getDataLayout(); | |||
1038 | ||||
1039 | if (TargetTriple.getOS() != Triple::Linux) | |||
1040 | report_fatal_error("unsupported operating system"); | |||
1041 | if (TargetTriple.getArch() != Triple::x86_64) | |||
1042 | report_fatal_error("unsupported architecture"); | |||
1043 | MapParams = &Linux_X86_64_MemoryMapParams; | |||
1044 | ||||
1045 | Mod = &M; | |||
1046 | Ctx = &M.getContext(); | |||
1047 | Int8Ptr = Type::getInt8PtrTy(*Ctx); | |||
1048 | OriginTy = IntegerType::get(*Ctx, OriginWidthBits); | |||
1049 | OriginPtrTy = PointerType::getUnqual(OriginTy); | |||
1050 | PrimitiveShadowTy = IntegerType::get(*Ctx, ShadowWidthBits); | |||
1051 | PrimitiveShadowPtrTy = PointerType::getUnqual(PrimitiveShadowTy); | |||
1052 | IntptrTy = DL.getIntPtrType(*Ctx); | |||
1053 | ZeroPrimitiveShadow = ConstantInt::getSigned(PrimitiveShadowTy, 0); | |||
1054 | ZeroOrigin = ConstantInt::getSigned(OriginTy, 0); | |||
1055 | ||||
1056 | Type *DFSanUnionLoadArgs[2] = {PrimitiveShadowPtrTy, IntptrTy}; | |||
1057 | DFSanUnionLoadFnTy = FunctionType::get(PrimitiveShadowTy, DFSanUnionLoadArgs, | |||
1058 | /*isVarArg=*/false); | |||
1059 | Type *DFSanLoadLabelAndOriginArgs[2] = {Int8Ptr, IntptrTy}; | |||
1060 | DFSanLoadLabelAndOriginFnTy = | |||
1061 | FunctionType::get(IntegerType::get(*Ctx, 64), DFSanLoadLabelAndOriginArgs, | |||
1062 | /*isVarArg=*/false); | |||
1063 | DFSanUnimplementedFnTy = FunctionType::get( | |||
1064 | Type::getVoidTy(*Ctx), Type::getInt8PtrTy(*Ctx), /*isVarArg=*/false); | |||
1065 | Type *DFSanSetLabelArgs[4] = {PrimitiveShadowTy, OriginTy, | |||
1066 | Type::getInt8PtrTy(*Ctx), IntptrTy}; | |||
1067 | DFSanSetLabelFnTy = FunctionType::get(Type::getVoidTy(*Ctx), | |||
1068 | DFSanSetLabelArgs, /*isVarArg=*/false); | |||
1069 | DFSanNonzeroLabelFnTy = | |||
1070 | FunctionType::get(Type::getVoidTy(*Ctx), None, /*isVarArg=*/false); | |||
1071 | DFSanVarargWrapperFnTy = FunctionType::get( | |||
1072 | Type::getVoidTy(*Ctx), Type::getInt8PtrTy(*Ctx), /*isVarArg=*/false); | |||
1073 | DFSanCmpCallbackFnTy = | |||
1074 | FunctionType::get(Type::getVoidTy(*Ctx), PrimitiveShadowTy, | |||
1075 | /*isVarArg=*/false); | |||
1076 | DFSanChainOriginFnTy = | |||
1077 | FunctionType::get(OriginTy, OriginTy, /*isVarArg=*/false); | |||
1078 | Type *DFSanChainOriginIfTaintedArgs[2] = {PrimitiveShadowTy, OriginTy}; | |||
1079 | DFSanChainOriginIfTaintedFnTy = FunctionType::get( | |||
1080 | OriginTy, DFSanChainOriginIfTaintedArgs, /*isVarArg=*/false); | |||
1081 | Type *DFSanMaybeStoreOriginArgs[4] = {IntegerType::get(*Ctx, ShadowWidthBits), | |||
1082 | Int8Ptr, IntptrTy, OriginTy}; | |||
1083 | DFSanMaybeStoreOriginFnTy = FunctionType::get( | |||
1084 | Type::getVoidTy(*Ctx), DFSanMaybeStoreOriginArgs, /*isVarArg=*/false); | |||
1085 | Type *DFSanMemOriginTransferArgs[3] = {Int8Ptr, Int8Ptr, IntptrTy}; | |||
1086 | DFSanMemOriginTransferFnTy = FunctionType::get( | |||
1087 | Type::getVoidTy(*Ctx), DFSanMemOriginTransferArgs, /*isVarArg=*/false); | |||
1088 | Type *DFSanLoadStoreCallbackArgs[2] = {PrimitiveShadowTy, Int8Ptr}; | |||
1089 | DFSanLoadStoreCallbackFnTy = | |||
1090 | FunctionType::get(Type::getVoidTy(*Ctx), DFSanLoadStoreCallbackArgs, | |||
1091 | /*isVarArg=*/false); | |||
1092 | Type *DFSanMemTransferCallbackArgs[2] = {PrimitiveShadowPtrTy, IntptrTy}; | |||
1093 | DFSanMemTransferCallbackFnTy = | |||
1094 | FunctionType::get(Type::getVoidTy(*Ctx), DFSanMemTransferCallbackArgs, | |||
1095 | /*isVarArg=*/false); | |||
1096 | ||||
1097 | ColdCallWeights = MDBuilder(*Ctx).createBranchWeights(1, 1000); | |||
1098 | OriginStoreWeights = MDBuilder(*Ctx).createBranchWeights(1, 1000); | |||
1099 | return true; | |||
1100 | } | |||
1101 | ||||
1102 | bool DataFlowSanitizer::isInstrumented(const Function *F) { | |||
1103 | return !ABIList.isIn(*F, "uninstrumented"); | |||
1104 | } | |||
1105 | ||||
1106 | bool DataFlowSanitizer::isInstrumented(const GlobalAlias *GA) { | |||
1107 | return !ABIList.isIn(*GA, "uninstrumented"); | |||
1108 | } | |||
1109 | ||||
1110 | DataFlowSanitizer::InstrumentedABI DataFlowSanitizer::getInstrumentedABI() { | |||
1111 | return ClArgsABI ? IA_Args : IA_TLS; | |||
1112 | } | |||
1113 | ||||
1114 | DataFlowSanitizer::WrapperKind DataFlowSanitizer::getWrapperKind(Function *F) { | |||
1115 | if (ABIList.isIn(*F, "functional")) | |||
1116 | return WK_Functional; | |||
1117 | if (ABIList.isIn(*F, "discard")) | |||
1118 | return WK_Discard; | |||
1119 | if (ABIList.isIn(*F, "custom")) | |||
1120 | return WK_Custom; | |||
1121 | ||||
1122 | return WK_Warning; | |||
1123 | } | |||
1124 | ||||
1125 | void DataFlowSanitizer::addGlobalNameSuffix(GlobalValue *GV) { | |||
1126 | std::string GVName = std::string(GV->getName()), Suffix = ".dfsan"; | |||
1127 | GV->setName(GVName + Suffix); | |||
1128 | ||||
1129 | // Try to change the name of the function in module inline asm. We only do | |||
1130 | // this for specific asm directives, currently only ".symver", to try to avoid | |||
1131 | // corrupting asm which happens to contain the symbol name as a substring. | |||
1132 | // Note that the substitution for .symver assumes that the versioned symbol | |||
1133 | // also has an instrumented name. | |||
1134 | std::string Asm = GV->getParent()->getModuleInlineAsm(); | |||
1135 | std::string SearchStr = ".symver " + GVName + ","; | |||
1136 | size_t Pos = Asm.find(SearchStr); | |||
1137 | if (Pos != std::string::npos) { | |||
1138 | Asm.replace(Pos, SearchStr.size(), ".symver " + GVName + Suffix + ","); | |||
1139 | Pos = Asm.find("@"); | |||
1140 | ||||
1141 | if (Pos == std::string::npos) | |||
1142 | report_fatal_error("unsupported .symver: " + Asm); | |||
1143 | ||||
1144 | Asm.replace(Pos, 1, Suffix + "@"); | |||
1145 | GV->getParent()->setModuleInlineAsm(Asm); | |||
1146 | } | |||
1147 | } | |||
1148 | ||||
1149 | Function * | |||
1150 | DataFlowSanitizer::buildWrapperFunction(Function *F, StringRef NewFName, | |||
1151 | GlobalValue::LinkageTypes NewFLink, | |||
1152 | FunctionType *NewFT) { | |||
1153 | FunctionType *FT = F->getFunctionType(); | |||
1154 | Function *NewF = Function::Create(NewFT, NewFLink, F->getAddressSpace(), | |||
1155 | NewFName, F->getParent()); | |||
1156 | NewF->copyAttributesFrom(F); | |||
1157 | NewF->removeAttributes( | |||
1158 | AttributeList::ReturnIndex, | |||
1159 | AttributeFuncs::typeIncompatible(NewFT->getReturnType())); | |||
1160 | ||||
1161 | BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", NewF); | |||
1162 | if (F->isVarArg()) { | |||
1163 | NewF->removeAttributes(AttributeList::FunctionIndex, | |||
1164 | AttrBuilder().addAttribute("split-stack")); | |||
1165 | CallInst::Create(DFSanVarargWrapperFn, | |||
1166 | IRBuilder<>(BB).CreateGlobalStringPtr(F->getName()), "", | |||
1167 | BB); | |||
1168 | new UnreachableInst(*Ctx, BB); | |||
1169 | } else { | |||
1170 | auto ArgIt = pointer_iterator<Argument *>(NewF->arg_begin()); | |||
1171 | std::vector<Value *> Args(ArgIt, ArgIt + FT->getNumParams()); | |||
1172 | ||||
1173 | CallInst *CI = CallInst::Create(F, Args, "", BB); | |||
1174 | if (FT->getReturnType()->isVoidTy()) | |||
1175 | ReturnInst::Create(*Ctx, BB); | |||
1176 | else | |||
1177 | ReturnInst::Create(*Ctx, CI, BB); | |||
1178 | } | |||
1179 | ||||
1180 | return NewF; | |||
1181 | } | |||
1182 | ||||
1183 | Constant *DataFlowSanitizer::getOrBuildTrampolineFunction(FunctionType *FT, | |||
1184 | StringRef FName) { | |||
1185 | FunctionType *FTT = getTrampolineFunctionType(FT); | |||
1186 | FunctionCallee C = Mod->getOrInsertFunction(FName, FTT); | |||
1187 | Function *F = dyn_cast<Function>(C.getCallee()); | |||
1188 | if (F && F->isDeclaration()) { | |||
1189 | F->setLinkage(GlobalValue::LinkOnceODRLinkage); | |||
1190 | BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", F); | |||
1191 | std::vector<Value *> Args; | |||
1192 | Function::arg_iterator AI = F->arg_begin() + 1; | |||
1193 | for (unsigned N = FT->getNumParams(); N != 0; ++AI, --N) | |||
1194 | Args.push_back(&*AI); | |||
1195 | CallInst *CI = CallInst::Create(FT, &*F->arg_begin(), Args, "", BB); | |||
1196 | Type *RetType = FT->getReturnType(); | |||
1197 | ReturnInst *RI = RetType->isVoidTy() ? ReturnInst::Create(*Ctx, BB) | |||
1198 | : ReturnInst::Create(*Ctx, CI, BB); | |||
1199 | ||||
1200 | // F is called by a wrapped custom function with primitive shadows. So | |||
1201 | // its arguments and return value need conversion. | |||
1202 | DFSanFunction DFSF(*this, F, /*IsNativeABI=*/true); | |||
1203 | Function::arg_iterator ValAI = F->arg_begin(), ShadowAI = AI; | |||
1204 | ++ValAI; | |||
1205 | for (unsigned N = FT->getNumParams(); N != 0; ++ValAI, ++ShadowAI, --N) { | |||
1206 | Value *Shadow = | |||
1207 | DFSF.expandFromPrimitiveShadow(ValAI->getType(), &*ShadowAI, CI); | |||
1208 | DFSF.ValShadowMap[&*ValAI] = Shadow; | |||
1209 | } | |||
1210 | Function::arg_iterator RetShadowAI = ShadowAI; | |||
1211 | const bool ShouldTrackOrigins = shouldTrackOrigins(); | |||
1212 | if (ShouldTrackOrigins) { | |||
1213 | ValAI = F->arg_begin(); | |||
1214 | ++ValAI; | |||
1215 | Function::arg_iterator OriginAI = ShadowAI; | |||
1216 | if (!RetType->isVoidTy()) | |||
1217 | ++OriginAI; | |||
1218 | for (unsigned N = FT->getNumParams(); N != 0; ++ValAI, ++OriginAI, --N) { | |||
1219 | DFSF.ValOriginMap[&*ValAI] = &*OriginAI; | |||
1220 | } | |||
1221 | } | |||
1222 | DFSanVisitor(DFSF).visitCallInst(*CI); | |||
1223 | if (!RetType->isVoidTy()) { | |||
1224 | Value *PrimitiveShadow = DFSF.collapseToPrimitiveShadow( | |||
1225 | DFSF.getShadow(RI->getReturnValue()), RI); | |||
1226 | new StoreInst(PrimitiveShadow, &*RetShadowAI, RI); | |||
1227 | if (ShouldTrackOrigins) { | |||
1228 | Value *Origin = DFSF.getOrigin(RI->getReturnValue()); | |||
1229 | new StoreInst(Origin, &*std::prev(F->arg_end()), RI); | |||
1230 | } | |||
1231 | } | |||
1232 | } | |||
1233 | ||||
1234 | return cast<Constant>(C.getCallee()); | |||
1235 | } | |||
1236 | ||||
1237 | // Initialize DataFlowSanitizer runtime functions and declare them in the module | |||
1238 | void DataFlowSanitizer::initializeRuntimeFunctions(Module &M) { | |||
1239 | { | |||
1240 | AttributeList AL; | |||
1241 | AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, | |||
1242 | Attribute::NoUnwind); | |||
1243 | AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, | |||
1244 | Attribute::ReadOnly); | |||
1245 | AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, | |||
1246 | Attribute::ZExt); | |||
1247 | DFSanUnionLoadFn = | |||
1248 | Mod->getOrInsertFunction("__dfsan_union_load", DFSanUnionLoadFnTy, AL); | |||
1249 | } | |||
1250 | { | |||
1251 | AttributeList AL; | |||
1252 | AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, | |||
1253 | Attribute::NoUnwind); | |||
1254 | AL = AL.addAttribute(M.getContext(), AttributeList::FunctionIndex, | |||
1255 | Attribute::ReadOnly); | |||
1256 | AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, | |||
1257 | Attribute::ZExt); | |||
1258 | DFSanLoadLabelAndOriginFn = Mod->getOrInsertFunction( | |||
1259 | "__dfsan_load_label_and_origin", DFSanLoadLabelAndOriginFnTy, AL); | |||
1260 | } | |||
1261 | DFSanUnimplementedFn = | |||
1262 | Mod->getOrInsertFunction("__dfsan_unimplemented", DFSanUnimplementedFnTy); | |||
1263 | { | |||
1264 | AttributeList AL; | |||
1265 | AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); | |||
1266 | AL = AL.addParamAttribute(M.getContext(), 1, Attribute::ZExt); | |||
1267 | DFSanSetLabelFn = | |||
1268 | Mod->getOrInsertFunction("__dfsan_set_label", DFSanSetLabelFnTy, AL); | |||
1269 | } | |||
1270 | DFSanNonzeroLabelFn = | |||
1271 | Mod->getOrInsertFunction("__dfsan_nonzero_label", DFSanNonzeroLabelFnTy); | |||
1272 | DFSanVarargWrapperFn = Mod->getOrInsertFunction("__dfsan_vararg_wrapper", | |||
1273 | DFSanVarargWrapperFnTy); | |||
1274 | { | |||
1275 | AttributeList AL; | |||
1276 | AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); | |||
1277 | AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, | |||
1278 | Attribute::ZExt); | |||
1279 | DFSanChainOriginFn = Mod->getOrInsertFunction("__dfsan_chain_origin", | |||
1280 | DFSanChainOriginFnTy, AL); | |||
1281 | } | |||
1282 | { | |||
1283 | AttributeList AL; | |||
1284 | AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); | |||
1285 | AL = AL.addParamAttribute(M.getContext(), 1, Attribute::ZExt); | |||
1286 | AL = AL.addAttribute(M.getContext(), AttributeList::ReturnIndex, | |||
1287 | Attribute::ZExt); | |||
1288 | DFSanChainOriginIfTaintedFn = Mod->getOrInsertFunction( | |||
1289 | "__dfsan_chain_origin_if_tainted", DFSanChainOriginIfTaintedFnTy, AL); | |||
1290 | } | |||
1291 | DFSanMemOriginTransferFn = Mod->getOrInsertFunction( | |||
1292 | "__dfsan_mem_origin_transfer", DFSanMemOriginTransferFnTy); | |||
1293 | ||||
1294 | { | |||
1295 | AttributeList AL; | |||
1296 | AL = AL.addParamAttribute(M.getContext(), 0, Attribute::ZExt); | |||
1297 | AL = AL.addParamAttribute(M.getContext(), 3, Attribute::ZExt); | |||
1298 | DFSanMaybeStoreOriginFn = Mod->getOrInsertFunction( | |||
1299 | "__dfsan_maybe_store_origin", DFSanMaybeStoreOriginFnTy, AL); | |||
1300 | } | |||
1301 | ||||
1302 | DFSanRuntimeFunctions.insert( | |||
1303 | DFSanUnionLoadFn.getCallee()->stripPointerCasts()); | |||
1304 | DFSanRuntimeFunctions.insert( | |||
1305 | DFSanLoadLabelAndOriginFn.getCallee()->stripPointerCasts()); | |||
1306 | DFSanRuntimeFunctions.insert( | |||
1307 | DFSanUnimplementedFn.getCallee()->stripPointerCasts()); | |||
1308 | DFSanRuntimeFunctions.insert( | |||
1309 | DFSanSetLabelFn.getCallee()->stripPointerCasts()); | |||
1310 | DFSanRuntimeFunctions.insert( | |||
1311 | DFSanNonzeroLabelFn.getCallee()->stripPointerCasts()); | |||
1312 | DFSanRuntimeFunctions.insert( | |||
1313 | DFSanVarargWrapperFn.getCallee()->stripPointerCasts()); | |||
1314 | DFSanRuntimeFunctions.insert( | |||
1315 | DFSanLoadCallbackFn.getCallee()->stripPointerCasts()); | |||
1316 | DFSanRuntimeFunctions.insert( | |||
1317 | DFSanStoreCallbackFn.getCallee()->stripPointerCasts()); | |||
1318 | DFSanRuntimeFunctions.insert( | |||
1319 | DFSanMemTransferCallbackFn.getCallee()->stripPointerCasts()); | |||
1320 | DFSanRuntimeFunctions.insert( | |||
1321 | DFSanCmpCallbackFn.getCallee()->stripPointerCasts()); | |||
1322 | DFSanRuntimeFunctions.insert( | |||
1323 | DFSanChainOriginFn.getCallee()->stripPointerCasts()); | |||
1324 | DFSanRuntimeFunctions.insert( | |||
1325 | DFSanChainOriginIfTaintedFn.getCallee()->stripPointerCasts()); | |||
1326 | DFSanRuntimeFunctions.insert( | |||
1327 | DFSanMemOriginTransferFn.getCallee()->stripPointerCasts()); | |||
1328 | DFSanRuntimeFunctions.insert( | |||
1329 | DFSanMaybeStoreOriginFn.getCallee()->stripPointerCasts()); | |||
1330 | } | |||
1331 | ||||
1332 | // Initializes event callback functions and declare them in the module | |||
1333 | void DataFlowSanitizer::initializeCallbackFunctions(Module &M) { | |||
1334 | DFSanLoadCallbackFn = Mod->getOrInsertFunction("__dfsan_load_callback", | |||
1335 | DFSanLoadStoreCallbackFnTy); | |||
1336 | DFSanStoreCallbackFn = Mod->getOrInsertFunction("__dfsan_store_callback", | |||
1337 | DFSanLoadStoreCallbackFnTy); | |||
1338 | DFSanMemTransferCallbackFn = Mod->getOrInsertFunction( | |||
1339 | "__dfsan_mem_transfer_callback", DFSanMemTransferCallbackFnTy); | |||
1340 | DFSanCmpCallbackFn = | |||
1341 | Mod->getOrInsertFunction("__dfsan_cmp_callback", DFSanCmpCallbackFnTy); | |||
1342 | } | |||
1343 | ||||
1344 | void DataFlowSanitizer::injectMetadataGlobals(Module &M) { | |||
1345 | // These variables can be used: | |||
1346 | // - by the runtime (to discover what the shadow width was, during | |||
1347 | // compilation) | |||
1348 | // - in testing (to avoid hardcoding the shadow width and type but instead | |||
1349 | // extract them by pattern matching) | |||
1350 | Type *IntTy = Type::getInt32Ty(*Ctx); | |||
1351 | (void)Mod->getOrInsertGlobal("__dfsan_shadow_width_bits", IntTy, [&] { | |||
1352 | return new GlobalVariable( | |||
1353 | M, IntTy, /*isConstant=*/true, GlobalValue::WeakODRLinkage, | |||
1354 | ConstantInt::get(IntTy, ShadowWidthBits), "__dfsan_shadow_width_bits"); | |||
1355 | }); | |||
1356 | (void)Mod->getOrInsertGlobal("__dfsan_shadow_width_bytes", IntTy, [&] { | |||
1357 | return new GlobalVariable(M, IntTy, /*isConstant=*/true, | |||
1358 | GlobalValue::WeakODRLinkage, | |||
1359 | ConstantInt::get(IntTy, ShadowWidthBytes), | |||
1360 | "__dfsan_shadow_width_bytes"); | |||
1361 | }); | |||
1362 | } | |||
1363 | ||||
1364 | bool DataFlowSanitizer::runImpl(Module &M) { | |||
1365 | initializeModule(M); | |||
1366 | ||||
1367 | if (ABIList.isIn(M, "skip")) | |||
1368 | return false; | |||
1369 | ||||
1370 | const unsigned InitialGlobalSize = M.global_size(); | |||
1371 | const unsigned InitialModuleSize = M.size(); | |||
1372 | ||||
1373 | bool Changed = false; | |||
1374 | ||||
1375 | auto GetOrInsertGlobal = [this, &Changed](StringRef Name, | |||
1376 | Type *Ty) -> Constant * { | |||
1377 | Constant *C = Mod->getOrInsertGlobal(Name, Ty); | |||
1378 | if (GlobalVariable *G = dyn_cast<GlobalVariable>(C)) { | |||
1379 | Changed |= G->getThreadLocalMode() != GlobalVariable::InitialExecTLSModel; | |||
1380 | G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel); | |||
1381 | } | |||
1382 | return C; | |||
1383 | }; | |||
1384 | ||||
1385 | // These globals must be kept in sync with the ones in dfsan.cpp. | |||
1386 | ArgTLS = | |||
1387 | GetOrInsertGlobal("__dfsan_arg_tls", | |||
1388 | ArrayType::get(Type::getInt64Ty(*Ctx), ArgTLSSize / 8)); | |||
1389 | RetvalTLS = GetOrInsertGlobal( | |||
1390 | "__dfsan_retval_tls", | |||
1391 | ArrayType::get(Type::getInt64Ty(*Ctx), RetvalTLSSize / 8)); | |||
1392 | ArgOriginTLSTy = ArrayType::get(OriginTy, NumOfElementsInArgOrgTLS); | |||
1393 | ArgOriginTLS = GetOrInsertGlobal("__dfsan_arg_origin_tls", ArgOriginTLSTy); | |||
1394 | RetvalOriginTLS = GetOrInsertGlobal("__dfsan_retval_origin_tls", OriginTy); | |||
1395 | ||||
1396 | (void)Mod->getOrInsertGlobal("__dfsan_track_origins", OriginTy, [&] { | |||
1397 | Changed = true; | |||
1398 | return new GlobalVariable( | |||
1399 | M, OriginTy, true, GlobalValue::WeakODRLinkage, | |||
1400 | ConstantInt::getSigned(OriginTy, | |||
1401 | shouldTrackOrigins() ? ClTrackOrigins : 0), | |||
1402 | "__dfsan_track_origins"); | |||
1403 | }); | |||
1404 | ||||
1405 | injectMetadataGlobals(M); | |||
1406 | ||||
1407 | initializeCallbackFunctions(M); | |||
1408 | initializeRuntimeFunctions(M); | |||
1409 | ||||
1410 | std::vector<Function *> FnsToInstrument; | |||
1411 | SmallPtrSet<Function *, 2> FnsWithNativeABI; | |||
1412 | for (Function &F : M) | |||
1413 | if (!F.isIntrinsic() && !DFSanRuntimeFunctions.contains(&F)) | |||
1414 | FnsToInstrument.push_back(&F); | |||
1415 | ||||
1416 | // Give function aliases prefixes when necessary, and build wrappers where the | |||
1417 | // instrumentedness is inconsistent. | |||
1418 | for (Module::alias_iterator AI = M.alias_begin(), AE = M.alias_end(); | |||
1419 | AI != AE;) { | |||
1420 | GlobalAlias *GA = &*AI; | |||
1421 | ++AI; | |||
1422 | // Don't stop on weak. We assume people aren't playing games with the | |||
1423 | // instrumentedness of overridden weak aliases. | |||
1424 | auto *F = dyn_cast<Function>(GA->getBaseObject()); | |||
1425 | if (!F) | |||
1426 | continue; | |||
1427 | ||||
1428 | bool GAInst = isInstrumented(GA), FInst = isInstrumented(F); | |||
1429 | if (GAInst && FInst) { | |||
1430 | addGlobalNameSuffix(GA); | |||
1431 | } else if (GAInst != FInst) { | |||
1432 | // Non-instrumented alias of an instrumented function, or vice versa. | |||
1433 | // Replace the alias with a native-ABI wrapper of the aliasee. The pass | |||
1434 | // below will take care of instrumenting it. | |||
1435 | Function *NewF = | |||
1436 | buildWrapperFunction(F, "", GA->getLinkage(), F->getFunctionType()); | |||
1437 | GA->replaceAllUsesWith(ConstantExpr::getBitCast(NewF, GA->getType())); | |||
1438 | NewF->takeName(GA); | |||
1439 | GA->eraseFromParent(); | |||
1440 | FnsToInstrument.push_back(NewF); | |||
1441 | } | |||
1442 | } | |||
1443 | ||||
1444 | ReadOnlyNoneAttrs.addAttribute(Attribute::ReadOnly) | |||
1445 | .addAttribute(Attribute::ReadNone); | |||
1446 | ||||
1447 | // First, change the ABI of every function in the module. ABI-listed | |||
1448 | // functions keep their original ABI and get a wrapper function. | |||
1449 | for (std::vector<Function *>::iterator FI = FnsToInstrument.begin(), | |||
1450 | FE = FnsToInstrument.end(); | |||
1451 | FI != FE; ++FI) { | |||
1452 | Function &F = **FI; | |||
1453 | FunctionType *FT = F.getFunctionType(); | |||
1454 | ||||
1455 | bool IsZeroArgsVoidRet = (FT->getNumParams() == 0 && !FT->isVarArg() && | |||
1456 | FT->getReturnType()->isVoidTy()); | |||
1457 | ||||
1458 | if (isInstrumented(&F)) { | |||
1459 | // Instrumented functions get a '.dfsan' suffix. This allows us to more | |||
1460 | // easily identify cases of mismatching ABIs. This naming scheme is | |||
1461 | // mangling-compatible (see Itanium ABI), using a vendor-specific suffix. | |||
1462 | if (getInstrumentedABI() == IA_Args && !IsZeroArgsVoidRet) { | |||
1463 | FunctionType *NewFT = getArgsFunctionType(FT); | |||
1464 | Function *NewF = Function::Create(NewFT, F.getLinkage(), | |||
1465 | F.getAddressSpace(), "", &M); | |||
1466 | NewF->copyAttributesFrom(&F); | |||
1467 | NewF->removeAttributes( | |||
1468 | AttributeList::ReturnIndex, | |||
1469 | AttributeFuncs::typeIncompatible(NewFT->getReturnType())); | |||
1470 | for (Function::arg_iterator FArg = F.arg_begin(), | |||
1471 | NewFArg = NewF->arg_begin(), | |||
1472 | FArgEnd = F.arg_end(); | |||
1473 | FArg != FArgEnd; ++FArg, ++NewFArg) { | |||
1474 | FArg->replaceAllUsesWith(&*NewFArg); | |||
1475 | } | |||
1476 | NewF->getBasicBlockList().splice(NewF->begin(), F.getBasicBlockList()); | |||
1477 | ||||
1478 | for (Function::user_iterator UI = F.user_begin(), UE = F.user_end(); | |||
1479 | UI != UE;) { | |||
1480 | BlockAddress *BA = dyn_cast<BlockAddress>(*UI); | |||
1481 | ++UI; | |||
1482 | if (BA) { | |||
1483 | BA->replaceAllUsesWith( | |||
1484 | BlockAddress::get(NewF, BA->getBasicBlock())); | |||
1485 | delete BA; | |||
1486 | } | |||
1487 | } | |||
1488 | F.replaceAllUsesWith( | |||
1489 | ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT))); | |||
1490 | NewF->takeName(&F); | |||
1491 | F.eraseFromParent(); | |||
1492 | *FI = NewF; | |||
1493 | addGlobalNameSuffix(NewF); | |||
1494 | } else { | |||
1495 | addGlobalNameSuffix(&F); | |||
1496 | } | |||
1497 | } else if (!IsZeroArgsVoidRet || getWrapperKind(&F) == WK_Custom) { | |||
1498 | // Build a wrapper function for F. The wrapper simply calls F, and is | |||
1499 | // added to FnsToInstrument so that any instrumentation according to its | |||
1500 | // WrapperKind is done in the second pass below. | |||
1501 | FunctionType *NewFT = | |||
1502 | getInstrumentedABI() == IA_Args ? getArgsFunctionType(FT) : FT; | |||
1503 | ||||
1504 | // If the function being wrapped has local linkage, then preserve the | |||
1505 | // function's linkage in the wrapper function. | |||
1506 | GlobalValue::LinkageTypes WrapperLinkage = | |||
1507 | F.hasLocalLinkage() ? F.getLinkage() | |||
1508 | : GlobalValue::LinkOnceODRLinkage; | |||
1509 | ||||
1510 | Function *NewF = buildWrapperFunction( | |||
1511 | &F, | |||
1512 | (shouldTrackOrigins() ? std::string("dfso$") : std::string("dfsw$")) + | |||
1513 | std::string(F.getName()), | |||
1514 | WrapperLinkage, NewFT); | |||
1515 | if (getInstrumentedABI() == IA_TLS) | |||
1516 | NewF->removeAttributes(AttributeList::FunctionIndex, ReadOnlyNoneAttrs); | |||
1517 | ||||
1518 | Value *WrappedFnCst = | |||
1519 | ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT)); | |||
1520 | F.replaceAllUsesWith(WrappedFnCst); | |||
1521 | ||||
1522 | UnwrappedFnMap[WrappedFnCst] = &F; | |||
1523 | *FI = NewF; | |||
1524 | ||||
1525 | if (!F.isDeclaration()) { | |||
1526 | // This function is probably defining an interposition of an | |||
1527 | // uninstrumented function and hence needs to keep the original ABI. | |||
1528 | // But any functions it may call need to use the instrumented ABI, so | |||
1529 | // we instrument it in a mode which preserves the original ABI. | |||
1530 | FnsWithNativeABI.insert(&F); | |||
1531 | ||||
1532 | // This code needs to rebuild the iterators, as they may be invalidated | |||
1533 | // by the push_back, taking care that the new range does not include | |||
1534 | // any functions added by this code. | |||
1535 | size_t N = FI - FnsToInstrument.begin(), | |||
1536 | Count = FE - FnsToInstrument.begin(); | |||
1537 | FnsToInstrument.push_back(&F); | |||
1538 | FI = FnsToInstrument.begin() + N; | |||
1539 | FE = FnsToInstrument.begin() + Count; | |||
1540 | } | |||
1541 | // Hopefully, nobody will try to indirectly call a vararg | |||
1542 | // function... yet. | |||
1543 | } else if (FT->isVarArg()) { | |||
1544 | UnwrappedFnMap[&F] = &F; | |||
1545 | *FI = nullptr; | |||
1546 | } | |||
1547 | } | |||
1548 | ||||
1549 | for (Function *F : FnsToInstrument) { | |||
1550 | if (!F || F->isDeclaration()) | |||
1551 | continue; | |||
1552 | ||||
1553 | removeUnreachableBlocks(*F); | |||
1554 | ||||
1555 | DFSanFunction DFSF(*this, F, FnsWithNativeABI.count(F)); | |||
1556 | ||||
1557 | // DFSanVisitor may create new basic blocks, which confuses df_iterator. | |||
1558 | // Build a copy of the list before iterating over it. | |||
1559 | SmallVector<BasicBlock *, 4> BBList(depth_first(&F->getEntryBlock())); | |||
1560 | ||||
1561 | for (BasicBlock *BB : BBList) { | |||
1562 | Instruction *Inst = &BB->front(); | |||
1563 | while (true) { | |||
1564 | // DFSanVisitor may split the current basic block, changing the current | |||
1565 | // instruction's next pointer and moving the next instruction to the | |||
1566 | // tail block from which we should continue. | |||
1567 | Instruction *Next = Inst->getNextNode(); | |||
1568 | // DFSanVisitor may delete Inst, so keep track of whether it was a | |||
1569 | // terminator. | |||
1570 | bool IsTerminator = Inst->isTerminator(); | |||
1571 | if (!DFSF.SkipInsts.count(Inst)) | |||
1572 | DFSanVisitor(DFSF).visit(Inst); | |||
1573 | if (IsTerminator) | |||
1574 | break; | |||
1575 | Inst = Next; | |||
1576 | } | |||
1577 | } | |||
1578 | ||||
1579 | // We will not necessarily be able to compute the shadow for every phi node | |||
1580 | // until we have visited every block. Therefore, the code that handles phi | |||
1581 | // nodes adds them to the PHIFixups list so that they can be properly | |||
1582 | // handled here. | |||
1583 | for (DFSanFunction::PHIFixupElement &P : DFSF.PHIFixups) { | |||
1584 | for (unsigned Val = 0, N = P.Phi->getNumIncomingValues(); Val != N; | |||
1585 | ++Val) { | |||
1586 | P.ShadowPhi->setIncomingValue( | |||
1587 | Val, DFSF.getShadow(P.Phi->getIncomingValue(Val))); | |||
1588 | if (P.OriginPhi) | |||
1589 | P.OriginPhi->setIncomingValue( | |||
1590 | Val, DFSF.getOrigin(P.Phi->getIncomingValue(Val))); | |||
1591 | } | |||
1592 | } | |||
1593 | ||||
1594 | // -dfsan-debug-nonzero-labels will split the CFG in all kinds of crazy | |||
1595 | // places (i.e. instructions in basic blocks we haven't even begun visiting | |||
1596 | // yet). To make our life easier, do this work in a pass after the main | |||
1597 | // instrumentation. | |||
1598 | if (ClDebugNonzeroLabels) { | |||
1599 | for (Value *V : DFSF.NonZeroChecks) { | |||
1600 | Instruction *Pos; | |||
1601 | if (Instruction *I = dyn_cast<Instruction>(V)) | |||
1602 | Pos = I->getNextNode(); | |||
1603 | else | |||
1604 | Pos = &DFSF.F->getEntryBlock().front(); | |||
1605 | while (isa<PHINode>(Pos) || isa<AllocaInst>(Pos)) | |||
1606 | Pos = Pos->getNextNode(); | |||
1607 | IRBuilder<> IRB(Pos); | |||
1608 | Value *PrimitiveShadow = DFSF.collapseToPrimitiveShadow(V, Pos); | |||
1609 | Value *Ne = | |||
1610 | IRB.CreateICmpNE(PrimitiveShadow, DFSF.DFS.ZeroPrimitiveShadow); | |||
1611 | BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen( | |||
1612 | Ne, Pos, /*Unreachable=*/false, ColdCallWeights)); | |||
1613 | IRBuilder<> ThenIRB(BI); | |||
1614 | ThenIRB.CreateCall(DFSF.DFS.DFSanNonzeroLabelFn, {}); | |||
1615 | } | |||
1616 | } | |||
1617 | } | |||
1618 | ||||
1619 | return Changed || !FnsToInstrument.empty() || | |||
1620 | M.global_size() != InitialGlobalSize || M.size() != InitialModuleSize; | |||
1621 | } | |||
1622 | ||||
1623 | Value *DFSanFunction::getArgTLS(Type *T, unsigned ArgOffset, IRBuilder<> &IRB) { | |||
1624 | Value *Base = IRB.CreatePointerCast(DFS.ArgTLS, DFS.IntptrTy); | |||
1625 | if (ArgOffset) | |||
1626 | Base = IRB.CreateAdd(Base, ConstantInt::get(DFS.IntptrTy, ArgOffset)); | |||
1627 | return IRB.CreateIntToPtr(Base, PointerType::get(DFS.getShadowTy(T), 0), | |||
1628 | "_dfsarg"); | |||
1629 | } | |||
1630 | ||||
1631 | Value *DFSanFunction::getRetvalTLS(Type *T, IRBuilder<> &IRB) { | |||
1632 | return IRB.CreatePointerCast( | |||
1633 | DFS.RetvalTLS, PointerType::get(DFS.getShadowTy(T), 0), "_dfsret"); | |||
1634 | } | |||
1635 | ||||
1636 | Value *DFSanFunction::getRetvalOriginTLS() { return DFS.RetvalOriginTLS; } | |||
1637 | ||||
1638 | Value *DFSanFunction::getArgOriginTLS(unsigned ArgNo, IRBuilder<> &IRB) { | |||
1639 | return IRB.CreateConstGEP2_64(DFS.ArgOriginTLSTy, DFS.ArgOriginTLS, 0, ArgNo, | |||
1640 | "_dfsarg_o"); | |||
1641 | } | |||
1642 | ||||
1643 | Value *DFSanFunction::getOrigin(Value *V) { | |||
1644 | assert(DFS.shouldTrackOrigins())((void)0); | |||
1645 | if (!isa<Argument>(V) && !isa<Instruction>(V)) | |||
1646 | return DFS.ZeroOrigin; | |||
1647 | Value *&Origin = ValOriginMap[V]; | |||
1648 | if (!Origin) { | |||
1649 | if (Argument *A = dyn_cast<Argument>(V)) { | |||
1650 | if (IsNativeABI) | |||
1651 | return DFS.ZeroOrigin; | |||
1652 | switch (IA) { | |||
1653 | case DataFlowSanitizer::IA_TLS: { | |||
1654 | if (A->getArgNo() < DFS.NumOfElementsInArgOrgTLS) { | |||
1655 | Instruction *ArgOriginTLSPos = &*F->getEntryBlock().begin(); | |||
1656 | IRBuilder<> IRB(ArgOriginTLSPos); | |||
1657 | Value *ArgOriginPtr = getArgOriginTLS(A->getArgNo(), IRB); | |||
1658 | Origin = IRB.CreateLoad(DFS.OriginTy, ArgOriginPtr); | |||
1659 | } else { | |||
1660 | // Overflow | |||
1661 | Origin = DFS.ZeroOrigin; | |||
1662 | } | |||
1663 | break; | |||
1664 | } | |||
1665 | case DataFlowSanitizer::IA_Args: { | |||
1666 | Origin = DFS.ZeroOrigin; | |||
1667 | break; | |||
1668 | } | |||
1669 | } | |||
1670 | } else { | |||
1671 | Origin = DFS.ZeroOrigin; | |||
1672 | } | |||
1673 | } | |||
1674 | return Origin; | |||
1675 | } | |||
1676 | ||||
1677 | void DFSanFunction::setOrigin(Instruction *I, Value *Origin) { | |||
1678 | if (!DFS.shouldTrackOrigins()) | |||
1679 | return; | |||
1680 | assert(!ValOriginMap.count(I))((void)0); | |||
1681 | assert(Origin->getType() == DFS.OriginTy)((void)0); | |||
1682 | ValOriginMap[I] = Origin; | |||
1683 | } | |||
1684 | ||||
1685 | Value *DFSanFunction::getShadowForTLSArgument(Argument *A) { | |||
1686 | unsigned ArgOffset = 0; | |||
1687 | const DataLayout &DL = F->getParent()->getDataLayout(); | |||
1688 | for (auto &FArg : F->args()) { | |||
1689 | if (!FArg.getType()->isSized()) { | |||
1690 | if (A == &FArg) | |||
1691 | break; | |||
1692 | continue; | |||
1693 | } | |||
1694 | ||||
1695 | unsigned Size = DL.getTypeAllocSize(DFS.getShadowTy(&FArg)); | |||
1696 | if (A != &FArg) { | |||
1697 | ArgOffset += alignTo(Size, ShadowTLSAlignment); | |||
1698 | if (ArgOffset > ArgTLSSize) | |||
1699 | break; // ArgTLS overflows, uses a zero shadow. | |||
1700 | continue; | |||
1701 | } | |||
1702 | ||||
1703 | if (ArgOffset + Size > ArgTLSSize) | |||
1704 | break; // ArgTLS overflows, uses a zero shadow. | |||
1705 | ||||
1706 | Instruction *ArgTLSPos = &*F->getEntryBlock().begin(); | |||
1707 | IRBuilder<> IRB(ArgTLSPos); | |||
1708 | Value *ArgShadowPtr = getArgTLS(FArg.getType(), ArgOffset, IRB); | |||
1709 | return IRB.CreateAlignedLoad(DFS.getShadowTy(&FArg), ArgShadowPtr, | |||
1710 | ShadowTLSAlignment); | |||
1711 | } | |||
1712 | ||||
1713 | return DFS.getZeroShadow(A); | |||
1714 | } | |||
1715 | ||||
1716 | Value *DFSanFunction::getShadow(Value *V) { | |||
1717 | if (!isa<Argument>(V) && !isa<Instruction>(V)) | |||
1718 | return DFS.getZeroShadow(V); | |||
1719 | Value *&Shadow = ValShadowMap[V]; | |||
1720 | if (!Shadow) { | |||
1721 | if (Argument *A = dyn_cast<Argument>(V)) { | |||
1722 | if (IsNativeABI) | |||
1723 | return DFS.getZeroShadow(V); | |||
1724 | switch (IA) { | |||
1725 | case DataFlowSanitizer::IA_TLS: { | |||
1726 | Shadow = getShadowForTLSArgument(A); | |||
1727 | break; | |||
1728 | } | |||
1729 | case DataFlowSanitizer::IA_Args: { | |||
1730 | unsigned ArgIdx = A->getArgNo() + F->arg_size() / 2; | |||
1731 | Function::arg_iterator Arg = F->arg_begin(); | |||
1732 | std::advance(Arg, ArgIdx); | |||
1733 | Shadow = &*Arg; | |||
1734 | assert(Shadow->getType() == DFS.PrimitiveShadowTy)((void)0); | |||
1735 | break; | |||
1736 | } | |||
1737 | } | |||
1738 | NonZeroChecks.push_back(Shadow); | |||
1739 | } else { | |||
1740 | Shadow = DFS.getZeroShadow(V); | |||
1741 | } | |||
1742 | } | |||
1743 | return Shadow; | |||
1744 | } | |||
1745 | ||||
1746 | void DFSanFunction::setShadow(Instruction *I, Value *Shadow) { | |||
1747 | assert(!ValShadowMap.count(I))((void)0); | |||
1748 | assert(DFS.shouldTrackFieldsAndIndices() ||((void)0) | |||
1749 | Shadow->getType() == DFS.PrimitiveShadowTy)((void)0); | |||
1750 | ValShadowMap[I] = Shadow; | |||
1751 | } | |||
1752 | ||||
1753 | /// Compute the integer shadow offset that corresponds to a given | |||
1754 | /// application address. | |||
1755 | /// | |||
1756 | /// Offset = (Addr & ~AndMask) ^ XorMask | |||
1757 | Value *DataFlowSanitizer::getShadowOffset(Value *Addr, IRBuilder<> &IRB) { | |||
1758 | assert(Addr != RetvalTLS && "Reinstrumenting?")((void)0); | |||
1759 | Value *OffsetLong = IRB.CreatePointerCast(Addr, IntptrTy); | |||
1760 | ||||
1761 | uint64_t AndMask = MapParams->AndMask; | |||
1762 | if (AndMask) | |||
1763 | OffsetLong = | |||
1764 | IRB.CreateAnd(OffsetLong, ConstantInt::get(IntptrTy, ~AndMask)); | |||
1765 | ||||
1766 | uint64_t XorMask = MapParams->XorMask; | |||
1767 | if (XorMask) | |||
1768 | OffsetLong = IRB.CreateXor(OffsetLong, ConstantInt::get(IntptrTy, XorMask)); | |||
1769 | return OffsetLong; | |||
1770 | } | |||
1771 | ||||
1772 | std::pair<Value *, Value *> | |||
1773 | DataFlowSanitizer::getShadowOriginAddress(Value *Addr, Align InstAlignment, | |||
1774 | Instruction *Pos) { | |||
1775 | // Returns ((Addr & shadow_mask) + origin_base - shadow_base) & ~4UL | |||
1776 | IRBuilder<> IRB(Pos); | |||
1777 | Value *ShadowOffset = getShadowOffset(Addr, IRB); | |||
1778 | Value *ShadowLong = ShadowOffset; | |||
1779 | uint64_t ShadowBase = MapParams->ShadowBase; | |||
1780 | if (ShadowBase != 0) { | |||
1781 | ShadowLong = | |||
1782 | IRB.CreateAdd(ShadowLong, ConstantInt::get(IntptrTy, ShadowBase)); | |||
1783 | } | |||
1784 | IntegerType *ShadowTy = IntegerType::get(*Ctx, ShadowWidthBits); | |||
1785 | Value *ShadowPtr = | |||
1786 | IRB.CreateIntToPtr(ShadowLong, PointerType::get(ShadowTy, 0)); | |||
1787 | Value *OriginPtr = nullptr; | |||
1788 | if (shouldTrackOrigins()) { | |||
1789 | Value *OriginLong = ShadowOffset; | |||
1790 | uint64_t OriginBase = MapParams->OriginBase; | |||
1791 | if (OriginBase != 0) | |||
1792 | OriginLong = | |||
1793 | IRB.CreateAdd(OriginLong, ConstantInt::get(IntptrTy, OriginBase)); | |||
1794 | const Align Alignment = llvm::assumeAligned(InstAlignment.value()); | |||
1795 | // When alignment is >= 4, Addr must be aligned to 4, otherwise it is UB. | |||
1796 | // So Mask is unnecessary. | |||
1797 | if (Alignment < MinOriginAlignment) { | |||
1798 | uint64_t Mask = MinOriginAlignment.value() - 1; | |||
1799 | OriginLong = IRB.CreateAnd(OriginLong, ConstantInt::get(IntptrTy, ~Mask)); | |||
1800 | } | |||
1801 | OriginPtr = IRB.CreateIntToPtr(OriginLong, OriginPtrTy); | |||
1802 | } | |||
1803 | return std::make_pair(ShadowPtr, OriginPtr); | |||
1804 | } | |||
1805 | ||||
1806 | Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos, | |||
1807 | Value *ShadowOffset) { | |||
1808 | IRBuilder<> IRB(Pos); | |||
1809 | return IRB.CreateIntToPtr(ShadowOffset, PrimitiveShadowPtrTy); | |||
1810 | } | |||
1811 | ||||
1812 | Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos) { | |||
1813 | IRBuilder<> IRB(Pos); | |||
1814 | Value *ShadowOffset = getShadowOffset(Addr, IRB); | |||
1815 | return getShadowAddress(Addr, Pos, ShadowOffset); | |||
1816 | } | |||
1817 | ||||
1818 | Value *DFSanFunction::combineShadowsThenConvert(Type *T, Value *V1, Value *V2, | |||
1819 | Instruction *Pos) { | |||
1820 | Value *PrimitiveValue = combineShadows(V1, V2, Pos); | |||
1821 | return expandFromPrimitiveShadow(T, PrimitiveValue, Pos); | |||
1822 | } | |||
1823 | ||||
1824 | // Generates IR to compute the union of the two given shadows, inserting it | |||
1825 | // before Pos. The combined value is with primitive type. | |||
1826 | Value *DFSanFunction::combineShadows(Value *V1, Value *V2, Instruction *Pos) { | |||
1827 | if (DFS.isZeroShadow(V1)) | |||
1828 | return collapseToPrimitiveShadow(V2, Pos); | |||
1829 | if (DFS.isZeroShadow(V2)) | |||
1830 | return collapseToPrimitiveShadow(V1, Pos); | |||
1831 | if (V1 == V2) | |||
1832 | return collapseToPrimitiveShadow(V1, Pos); | |||
1833 | ||||
1834 | auto V1Elems = ShadowElements.find(V1); | |||
1835 | auto V2Elems = ShadowElements.find(V2); | |||
1836 | if (V1Elems != ShadowElements.end() && V2Elems != ShadowElements.end()) { | |||
1837 | if (std::includes(V1Elems->second.begin(), V1Elems->second.end(), | |||
1838 | V2Elems->second.begin(), V2Elems->second.end())) { | |||
1839 | return collapseToPrimitiveShadow(V1, Pos); | |||
1840 | } | |||
1841 | if (std::includes(V2Elems->second.begin(), V2Elems->second.end(), | |||
1842 | V1Elems->second.begin(), V1Elems->second.end())) { | |||
1843 | return collapseToPrimitiveShadow(V2, Pos); | |||
1844 | } | |||
1845 | } else if (V1Elems != ShadowElements.end()) { | |||
1846 | if (V1Elems->second.count(V2)) | |||
1847 | return collapseToPrimitiveShadow(V1, Pos); | |||
1848 | } else if (V2Elems != ShadowElements.end()) { | |||
1849 | if (V2Elems->second.count(V1)) | |||
1850 | return collapseToPrimitiveShadow(V2, Pos); | |||
1851 | } | |||
1852 | ||||
1853 | auto Key = std::make_pair(V1, V2); | |||
1854 | if (V1 > V2) | |||
1855 | std::swap(Key.first, Key.second); | |||
1856 | CachedShadow &CCS = CachedShadows[Key]; | |||
1857 | if (CCS.Block && DT.dominates(CCS.Block, Pos->getParent())) | |||
1858 | return CCS.Shadow; | |||
1859 | ||||
1860 | // Converts inputs shadows to shadows with primitive types. | |||
1861 | Value *PV1 = collapseToPrimitiveShadow(V1, Pos); | |||
1862 | Value *PV2 = collapseToPrimitiveShadow(V2, Pos); | |||
1863 | ||||
1864 | IRBuilder<> IRB(Pos); | |||
1865 | CCS.Block = Pos->getParent(); | |||
1866 | CCS.Shadow = IRB.CreateOr(PV1, PV2); | |||
1867 | ||||
1868 | std::set<Value *> UnionElems; | |||
1869 | if (V1Elems != ShadowElements.end()) { | |||
1870 | UnionElems = V1Elems->second; | |||
1871 | } else { | |||
1872 | UnionElems.insert(V1); | |||
1873 | } | |||
1874 | if (V2Elems != ShadowElements.end()) { | |||
1875 | UnionElems.insert(V2Elems->second.begin(), V2Elems->second.end()); | |||
1876 | } else { | |||
1877 | UnionElems.insert(V2); | |||
1878 | } | |||
1879 | ShadowElements[CCS.Shadow] = std::move(UnionElems); | |||
1880 | ||||
1881 | return CCS.Shadow; | |||
1882 | } | |||
1883 | ||||
1884 | // A convenience function which folds the shadows of each of the operands | |||
1885 | // of the provided instruction Inst, inserting the IR before Inst. Returns | |||
1886 | // the computed union Value. | |||
1887 | Value *DFSanFunction::combineOperandShadows(Instruction *Inst) { | |||
1888 | if (Inst->getNumOperands() == 0) | |||
1889 | return DFS.getZeroShadow(Inst); | |||
1890 | ||||
1891 | Value *Shadow = getShadow(Inst->getOperand(0)); | |||
1892 | for (unsigned I = 1, N = Inst->getNumOperands(); I < N; ++I) | |||
1893 | Shadow = combineShadows(Shadow, getShadow(Inst->getOperand(I)), Inst); | |||
1894 | ||||
1895 | return expandFromPrimitiveShadow(Inst->getType(), Shadow, Inst); | |||
1896 | } | |||
1897 | ||||
1898 | void DFSanVisitor::visitInstOperands(Instruction &I) { | |||
1899 | Value *CombinedShadow = DFSF.combineOperandShadows(&I); | |||
1900 | DFSF.setShadow(&I, CombinedShadow); | |||
1901 | visitInstOperandOrigins(I); | |||
1902 | } | |||
1903 | ||||
1904 | Value *DFSanFunction::combineOrigins(const std::vector<Value *> &Shadows, | |||
1905 | const std::vector<Value *> &Origins, | |||
1906 | Instruction *Pos, ConstantInt *Zero) { | |||
1907 | assert(Shadows.size() == Origins.size())((void)0); | |||
1908 | size_t Size = Origins.size(); | |||
1909 | if (Size == 0) | |||
1910 | return DFS.ZeroOrigin; | |||
1911 | Value *Origin = nullptr; | |||
1912 | if (!Zero) | |||
1913 | Zero = DFS.ZeroPrimitiveShadow; | |||
1914 | for (size_t I = 0; I != Size; ++I) { | |||
1915 | Value *OpOrigin = Origins[I]; | |||
1916 | Constant *ConstOpOrigin = dyn_cast<Constant>(OpOrigin); | |||
1917 | if (ConstOpOrigin && ConstOpOrigin->isNullValue()) | |||
1918 | continue; | |||
1919 | if (!Origin) { | |||
1920 | Origin = OpOrigin; | |||
1921 | continue; | |||
1922 | } | |||
1923 | Value *OpShadow = Shadows[I]; | |||
1924 | Value *PrimitiveShadow = collapseToPrimitiveShadow(OpShadow, Pos); | |||
1925 | IRBuilder<> IRB(Pos); | |||
1926 | Value *Cond = IRB.CreateICmpNE(PrimitiveShadow, Zero); | |||
1927 | Origin = IRB.CreateSelect(Cond, OpOrigin, Origin); | |||
1928 | } | |||
1929 | return Origin ? Origin : DFS.ZeroOrigin; | |||
1930 | } | |||
1931 | ||||
1932 | Value *DFSanFunction::combineOperandOrigins(Instruction *Inst) { | |||
1933 | size_t Size = Inst->getNumOperands(); | |||
1934 | std::vector<Value *> Shadows(Size); | |||
1935 | std::vector<Value *> Origins(Size); | |||
1936 | for (unsigned I = 0; I != Size; ++I) { | |||
1937 | Shadows[I] = getShadow(Inst->getOperand(I)); | |||
1938 | Origins[I] = getOrigin(Inst->getOperand(I)); | |||
1939 | } | |||
1940 | return combineOrigins(Shadows, Origins, Inst); | |||
1941 | } | |||
1942 | ||||
1943 | void DFSanVisitor::visitInstOperandOrigins(Instruction &I) { | |||
1944 | if (!DFSF.DFS.shouldTrackOrigins()) | |||
1945 | return; | |||
1946 | Value *CombinedOrigin = DFSF.combineOperandOrigins(&I); | |||
1947 | DFSF.setOrigin(&I, CombinedOrigin); | |||
1948 | } | |||
1949 | ||||
1950 | Align DFSanFunction::getShadowAlign(Align InstAlignment) { | |||
1951 | const Align Alignment = ClPreserveAlignment ? InstAlignment : Align(1); | |||
1952 | return Align(Alignment.value() * DFS.ShadowWidthBytes); | |||
1953 | } | |||
1954 | ||||
1955 | Align DFSanFunction::getOriginAlign(Align InstAlignment) { | |||
1956 | const Align Alignment = llvm::assumeAligned(InstAlignment.value()); | |||
1957 | return Align(std::max(MinOriginAlignment, Alignment)); | |||
1958 | } | |||
1959 | ||||
1960 | bool DFSanFunction::useCallbackLoadLabelAndOrigin(uint64_t Size, | |||
1961 | Align InstAlignment) { | |||
1962 | // When enabling tracking load instructions, we always use | |||
1963 | // __dfsan_load_label_and_origin to reduce code size. | |||
1964 | if (ClTrackOrigins == 2) | |||
1965 | return true; | |||
1966 | ||||
1967 | assert(Size != 0)((void)0); | |||
1968 | // * if Size == 1, it is sufficient to load its origin aligned at 4. | |||
1969 | // * if Size == 2, we assume most cases Addr % 2 == 0, so it is sufficient to | |||
1970 | // load its origin aligned at 4. If not, although origins may be lost, it | |||
1971 | // should not happen very often. | |||
1972 | // * if align >= 4, Addr must be aligned to 4, otherwise it is UB. When | |||
1973 | // Size % 4 == 0, it is more efficient to load origins without callbacks. | |||
1974 | // * Otherwise we use __dfsan_load_label_and_origin. | |||
1975 | // This should ensure that common cases run efficiently. | |||
1976 | if (Size <= 2) | |||
1977 | return false; | |||
1978 | ||||
1979 | const Align Alignment = llvm::assumeAligned(InstAlignment.value()); | |||
1980 | return Alignment < MinOriginAlignment || !DFS.hasLoadSizeForFastPath(Size); | |||
1981 | } | |||
1982 | ||||
1983 | Value *DataFlowSanitizer::loadNextOrigin(Instruction *Pos, Align OriginAlign, | |||
1984 | Value **OriginAddr) { | |||
1985 | IRBuilder<> IRB(Pos); | |||
1986 | *OriginAddr = | |||
1987 | IRB.CreateGEP(OriginTy, *OriginAddr, ConstantInt::get(IntptrTy, 1)); | |||
1988 | return IRB.CreateAlignedLoad(OriginTy, *OriginAddr, OriginAlign); | |||
1989 | } | |||
1990 | ||||
1991 | std::pair<Value *, Value *> DFSanFunction::loadShadowFast( | |||
1992 | Value *ShadowAddr, Value *OriginAddr, uint64_t Size, Align ShadowAlign, | |||
1993 | Align OriginAlign, Value *FirstOrigin, Instruction *Pos) { | |||
1994 | const bool ShouldTrackOrigins = DFS.shouldTrackOrigins(); | |||
1995 | const uint64_t ShadowSize = Size * DFS.ShadowWidthBytes; | |||
1996 | ||||
1997 | assert(Size >= 4 && "Not large enough load size for fast path!")((void)0); | |||
1998 | ||||
1999 | // Used for origin tracking. | |||
2000 | std::vector<Value *> Shadows; | |||
2001 | std::vector<Value *> Origins; | |||
2002 | ||||
2003 | // Load instructions in LLVM can have arbitrary byte sizes (e.g., 3, 12, 20) | |||
2004 | // but this function is only used in a subset of cases that make it possible | |||
2005 | // to optimize the instrumentation. | |||
2006 | // | |||
2007 | // Specifically, when the shadow size in bytes (i.e., loaded bytes x shadow | |||
2008 | // per byte) is either: | |||
2009 | // - a multiple of 8 (common) | |||
2010 | // - equal to 4 (only for load32) | |||
2011 | // | |||
2012 | // For the second case, we can fit the wide shadow in a 32-bit integer. In all | |||
2013 | // other cases, we use a 64-bit integer to hold the wide shadow. | |||
2014 | Type *WideShadowTy = | |||
2015 | ShadowSize == 4 ? Type::getInt32Ty(*DFS.Ctx) : Type::getInt64Ty(*DFS.Ctx); | |||
2016 | ||||
2017 | IRBuilder<> IRB(Pos); | |||
2018 | Value *WideAddr = IRB.CreateBitCast(ShadowAddr, WideShadowTy->getPointerTo()); | |||
2019 | Value *CombinedWideShadow = | |||
2020 | IRB.CreateAlignedLoad(WideShadowTy, WideAddr, ShadowAlign); | |||
2021 | ||||
2022 | unsigned WideShadowBitWidth = WideShadowTy->getIntegerBitWidth(); | |||
2023 | const uint64_t BytesPerWideShadow = WideShadowBitWidth / DFS.ShadowWidthBits; | |||
2024 | ||||
2025 | auto AppendWideShadowAndOrigin = [&](Value *WideShadow, Value *Origin) { | |||
2026 | if (BytesPerWideShadow > 4) { | |||
2027 | assert(BytesPerWideShadow == 8)((void)0); | |||
2028 | // The wide shadow relates to two origin pointers: one for the first four | |||
2029 | // application bytes, and one for the latest four. We use a left shift to | |||
2030 | // get just the shadow bytes that correspond to the first origin pointer, | |||
2031 | // and then the entire shadow for the second origin pointer (which will be | |||
2032 | // chosen by combineOrigins() iff the least-significant half of the wide | |||
2033 | // shadow was empty but the other half was not). | |||
2034 | Value *WideShadowLo = IRB.CreateShl( | |||
2035 | WideShadow, ConstantInt::get(WideShadowTy, WideShadowBitWidth / 2)); | |||
2036 | Shadows.push_back(WideShadow); | |||
2037 | Origins.push_back(DFS.loadNextOrigin(Pos, OriginAlign, &OriginAddr)); | |||
2038 | ||||
2039 | Shadows.push_back(WideShadowLo); | |||
2040 | Origins.push_back(Origin); | |||
2041 | } else { | |||
2042 | Shadows.push_back(WideShadow); | |||
2043 | Origins.push_back(Origin); | |||
2044 | } | |||
2045 | }; | |||
2046 | ||||
2047 | if (ShouldTrackOrigins) | |||
2048 | AppendWideShadowAndOrigin(CombinedWideShadow, FirstOrigin); | |||
2049 | ||||
2050 | // First OR all the WideShadows (i.e., 64bit or 32bit shadow chunks) linearly; | |||
2051 | // then OR individual shadows within the combined WideShadow by binary ORing. | |||
2052 | // This is fewer instructions than ORing shadows individually, since it | |||
2053 | // needs logN shift/or instructions (N being the bytes of the combined wide | |||
2054 | // shadow). | |||
2055 | for (uint64_t ByteOfs = BytesPerWideShadow; ByteOfs < Size; | |||
2056 | ByteOfs += BytesPerWideShadow) { | |||
2057 | WideAddr = IRB.CreateGEP(WideShadowTy, WideAddr, | |||
2058 | ConstantInt::get(DFS.IntptrTy, 1)); | |||
2059 | Value *NextWideShadow = | |||
2060 | IRB.CreateAlignedLoad(WideShadowTy, WideAddr, ShadowAlign); | |||
2061 | CombinedWideShadow = IRB.CreateOr(CombinedWideShadow, NextWideShadow); | |||
2062 | if (ShouldTrackOrigins) { | |||
2063 | Value *NextOrigin = DFS.loadNextOrigin(Pos, OriginAlign, &OriginAddr); | |||
2064 | AppendWideShadowAndOrigin(NextWideShadow, NextOrigin); | |||
2065 | } | |||
2066 | } | |||
2067 | for (unsigned Width = WideShadowBitWidth / 2; Width >= DFS.ShadowWidthBits; | |||
2068 | Width >>= 1) { | |||
2069 | Value *ShrShadow = IRB.CreateLShr(CombinedWideShadow, Width); | |||
2070 | CombinedWideShadow = IRB.CreateOr(CombinedWideShadow, ShrShadow); | |||
2071 | } | |||
2072 | return {IRB.CreateTrunc(CombinedWideShadow, DFS.PrimitiveShadowTy), | |||
2073 | ShouldTrackOrigins | |||
2074 | ? combineOrigins(Shadows, Origins, Pos, | |||
2075 | ConstantInt::getSigned(IRB.getInt64Ty(), 0)) | |||
2076 | : DFS.ZeroOrigin}; | |||
2077 | } | |||
2078 | ||||
2079 | std::pair<Value *, Value *> DFSanFunction::loadShadowOriginSansLoadTracking( | |||
2080 | Value *Addr, uint64_t Size, Align InstAlignment, Instruction *Pos) { | |||
2081 | const bool ShouldTrackOrigins = DFS.shouldTrackOrigins(); | |||
2082 | ||||
2083 | // Non-escaped loads. | |||
2084 | if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) { | |||
2085 | const auto SI = AllocaShadowMap.find(AI); | |||
2086 | if (SI != AllocaShadowMap.end()) { | |||
2087 | IRBuilder<> IRB(Pos); | |||
2088 | Value *ShadowLI = IRB.CreateLoad(DFS.PrimitiveShadowTy, SI->second); | |||
2089 | const auto OI = AllocaOriginMap.find(AI); | |||
2090 | assert(!ShouldTrackOrigins || OI != AllocaOriginMap.end())((void)0); | |||
2091 | return {ShadowLI, ShouldTrackOrigins | |||
2092 | ? IRB.CreateLoad(DFS.OriginTy, OI->second) | |||
2093 | : nullptr}; | |||
2094 | } | |||
2095 | } | |||
2096 | ||||
2097 | // Load from constant addresses. | |||
2098 | SmallVector<const Value *, 2> Objs; | |||
2099 | getUnderlyingObjects(Addr, Objs); | |||
2100 | bool AllConstants = true; | |||
2101 | for (const Value *Obj : Objs) { | |||
2102 | if (isa<Function>(Obj) || isa<BlockAddress>(Obj)) | |||
2103 | continue; | |||
2104 | if (isa<GlobalVariable>(Obj) && cast<GlobalVariable>(Obj)->isConstant()) | |||
2105 | continue; | |||
2106 | ||||
2107 | AllConstants = false; | |||
2108 | break; | |||
2109 | } | |||
2110 | if (AllConstants) | |||
2111 | return {DFS.ZeroPrimitiveShadow, | |||
2112 | ShouldTrackOrigins ? DFS.ZeroOrigin : nullptr}; | |||
2113 | ||||
2114 | if (Size == 0) | |||
2115 | return {DFS.ZeroPrimitiveShadow, | |||
2116 | ShouldTrackOrigins ? DFS.ZeroOrigin : nullptr}; | |||
2117 | ||||
2118 | // Use callback to load if this is not an optimizable case for origin | |||
2119 | // tracking. | |||
2120 | if (ShouldTrackOrigins && | |||
2121 | useCallbackLoadLabelAndOrigin(Size, InstAlignment)) { | |||
2122 | IRBuilder<> IRB(Pos); | |||
2123 | CallInst *Call = | |||
2124 | IRB.CreateCall(DFS.DFSanLoadLabelAndOriginFn, | |||
2125 | {IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()), | |||
2126 | ConstantInt::get(DFS.IntptrTy, Size)}); | |||
2127 | Call->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt); | |||
2128 | return {IRB.CreateTrunc(IRB.CreateLShr(Call, DFS.OriginWidthBits), | |||
2129 | DFS.PrimitiveShadowTy), | |||
2130 | IRB.CreateTrunc(Call, DFS.OriginTy)}; | |||
2131 | } | |||
2132 | ||||
2133 | // Other cases that support loading shadows or origins in a fast way. | |||
2134 | Value *ShadowAddr, *OriginAddr; | |||
2135 | std::tie(ShadowAddr, OriginAddr) = | |||
2136 | DFS.getShadowOriginAddress(Addr, InstAlignment, Pos); | |||
2137 | ||||
2138 | const Align ShadowAlign = getShadowAlign(InstAlignment); | |||
2139 | const Align OriginAlign = getOriginAlign(InstAlignment); | |||
2140 | Value *Origin = nullptr; | |||
2141 | if (ShouldTrackOrigins) { | |||
2142 | IRBuilder<> IRB(Pos); | |||
2143 | Origin = IRB.CreateAlignedLoad(DFS.OriginTy, OriginAddr, OriginAlign); | |||
2144 | } | |||
2145 | ||||
2146 | // When the byte size is small enough, we can load the shadow directly with | |||
2147 | // just a few instructions. | |||
2148 | switch (Size) { | |||
2149 | case 1: { | |||
2150 | LoadInst *LI = new LoadInst(DFS.PrimitiveShadowTy, ShadowAddr, "", Pos); | |||
2151 | LI->setAlignment(ShadowAlign); | |||
2152 | return {LI, Origin}; | |||
2153 | } | |||
2154 | case 2: { | |||
2155 | IRBuilder<> IRB(Pos); | |||
2156 | Value *ShadowAddr1 = IRB.CreateGEP(DFS.PrimitiveShadowTy, ShadowAddr, | |||
2157 | ConstantInt::get(DFS.IntptrTy, 1)); | |||
2158 | Value *Load = | |||
2159 | IRB.CreateAlignedLoad(DFS.PrimitiveShadowTy, ShadowAddr, ShadowAlign); | |||
2160 | Value *Load1 = | |||
2161 | IRB.CreateAlignedLoad(DFS.PrimitiveShadowTy, ShadowAddr1, ShadowAlign); | |||
2162 | return {combineShadows(Load, Load1, Pos), Origin}; | |||
2163 | } | |||
2164 | } | |||
2165 | bool HasSizeForFastPath = DFS.hasLoadSizeForFastPath(Size); | |||
2166 | ||||
2167 | if (HasSizeForFastPath) | |||
2168 | return loadShadowFast(ShadowAddr, OriginAddr, Size, ShadowAlign, | |||
2169 | OriginAlign, Origin, Pos); | |||
2170 | ||||
2171 | IRBuilder<> IRB(Pos); | |||
2172 | CallInst *FallbackCall = IRB.CreateCall( | |||
2173 | DFS.DFSanUnionLoadFn, {ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)}); | |||
2174 | FallbackCall->addAttribute(AttributeList::ReturnIndex, Attribute::ZExt); | |||
2175 | return {FallbackCall, Origin}; | |||
2176 | } | |||
2177 | ||||
2178 | std::pair<Value *, Value *> DFSanFunction::loadShadowOrigin(Value *Addr, | |||
2179 | uint64_t Size, | |||
2180 | Align InstAlignment, | |||
2181 | Instruction *Pos) { | |||
2182 | Value *PrimitiveShadow, *Origin; | |||
2183 | std::tie(PrimitiveShadow, Origin) = | |||
2184 | loadShadowOriginSansLoadTracking(Addr, Size, InstAlignment, Pos); | |||
2185 | if (DFS.shouldTrackOrigins()) { | |||
2186 | if (ClTrackOrigins == 2) { | |||
2187 | IRBuilder<> IRB(Pos); | |||
2188 | auto *ConstantShadow = dyn_cast<Constant>(PrimitiveShadow); | |||
2189 | if (!ConstantShadow || !ConstantShadow->isZeroValue()) | |||
2190 | Origin = updateOriginIfTainted(PrimitiveShadow, Origin, IRB); | |||
2191 | } | |||
2192 | } | |||
2193 | return {PrimitiveShadow, Origin}; | |||
2194 | } | |||
2195 | ||||
2196 | static AtomicOrdering addAcquireOrdering(AtomicOrdering AO) { | |||
2197 | switch (AO) { | |||
2198 | case AtomicOrdering::NotAtomic: | |||
2199 | return AtomicOrdering::NotAtomic; | |||
2200 | case AtomicOrdering::Unordered: | |||
2201 | case AtomicOrdering::Monotonic: | |||
2202 | case AtomicOrdering::Acquire: | |||
2203 | return AtomicOrdering::Acquire; | |||
2204 | case AtomicOrdering::Release: | |||
2205 | case AtomicOrdering::AcquireRelease: | |||
2206 | return AtomicOrdering::AcquireRelease; | |||
2207 | case AtomicOrdering::SequentiallyConsistent: | |||
2208 | return AtomicOrdering::SequentiallyConsistent; | |||
2209 | } | |||
2210 | llvm_unreachable("Unknown ordering")__builtin_unreachable(); | |||
2211 | } | |||
2212 | ||||
2213 | void DFSanVisitor::visitLoadInst(LoadInst &LI) { | |||
2214 | auto &DL = LI.getModule()->getDataLayout(); | |||
2215 | uint64_t Size = DL.getTypeStoreSize(LI.getType()); | |||
2216 | if (Size == 0) { | |||
2217 | DFSF.setShadow(&LI, DFSF.DFS.getZeroShadow(&LI)); | |||
2218 | DFSF.setOrigin(&LI, DFSF.DFS.ZeroOrigin); | |||
2219 | return; | |||
2220 | } | |||
2221 | ||||
2222 | // When an application load is atomic, increase atomic ordering between | |||
2223 | // atomic application loads and stores to ensure happen-before order; load | |||
2224 | // shadow data after application data; store zero shadow data before | |||
2225 | // application data. This ensure shadow loads return either labels of the | |||
2226 | // initial application data or zeros. | |||
2227 | if (LI.isAtomic()) | |||
2228 | LI.setOrdering(addAcquireOrdering(LI.getOrdering())); | |||
2229 | ||||
2230 | Instruction *Pos = LI.isAtomic() ? LI.getNextNode() : &LI; | |||
2231 | std::vector<Value *> Shadows; | |||
2232 | std::vector<Value *> Origins; | |||
2233 | Value *PrimitiveShadow, *Origin; | |||
2234 | std::tie(PrimitiveShadow, Origin) = | |||
2235 | DFSF.loadShadowOrigin(LI.getPointerOperand(), Size, LI.getAlign(), Pos); | |||
2236 | const bool ShouldTrackOrigins = DFSF.DFS.shouldTrackOrigins(); | |||
2237 | if (ShouldTrackOrigins) { | |||
2238 | Shadows.push_back(PrimitiveShadow); | |||
2239 | Origins.push_back(Origin); | |||
2240 | } | |||
2241 | if (ClCombinePointerLabelsOnLoad) { | |||
2242 | Value *PtrShadow = DFSF.getShadow(LI.getPointerOperand()); | |||
2243 | PrimitiveShadow = DFSF.combineShadows(PrimitiveShadow, PtrShadow, Pos); | |||
2244 | if (ShouldTrackOrigins) { | |||
2245 | Shadows.push_back(PtrShadow); | |||
2246 | Origins.push_back(DFSF.getOrigin(LI.getPointerOperand())); | |||
2247 | } | |||
2248 | } | |||
2249 | if (!DFSF.DFS.isZeroShadow(PrimitiveShadow)) | |||
2250 | DFSF.NonZeroChecks.push_back(PrimitiveShadow); | |||
2251 | ||||
2252 | Value *Shadow = | |||
2253 | DFSF.expandFromPrimitiveShadow(LI.getType(), PrimitiveShadow, Pos); | |||
2254 | DFSF.setShadow(&LI, Shadow); | |||
2255 | ||||
2256 | if (ShouldTrackOrigins) { | |||
2257 | DFSF.setOrigin(&LI, DFSF.combineOrigins(Shadows, Origins, Pos)); | |||
2258 | } | |||
2259 | ||||
2260 | if (ClEventCallbacks) { | |||
2261 | IRBuilder<> IRB(Pos); | |||
2262 | Value *Addr8 = IRB.CreateBitCast(LI.getPointerOperand(), DFSF.DFS.Int8Ptr); | |||
2263 | IRB.CreateCall(DFSF.DFS.DFSanLoadCallbackFn, {PrimitiveShadow, Addr8}); | |||
2264 | } | |||
2265 | } | |||
2266 | ||||
2267 | Value *DFSanFunction::updateOriginIfTainted(Value *Shadow, Value *Origin, | |||
2268 | IRBuilder<> &IRB) { | |||
2269 | assert(DFS.shouldTrackOrigins())((void)0); | |||
2270 | return IRB.CreateCall(DFS.DFSanChainOriginIfTaintedFn, {Shadow, Origin}); | |||
2271 | } | |||
2272 | ||||
2273 | Value *DFSanFunction::updateOrigin(Value *V, IRBuilder<> &IRB) { | |||
2274 | if (!DFS.shouldTrackOrigins()) | |||
2275 | return V; | |||
2276 | return IRB.CreateCall(DFS.DFSanChainOriginFn, V); | |||
2277 | } | |||
2278 | ||||
2279 | Value *DFSanFunction::originToIntptr(IRBuilder<> &IRB, Value *Origin) { | |||
2280 | const unsigned OriginSize = DataFlowSanitizer::OriginWidthBytes; | |||
2281 | const DataLayout &DL = F->getParent()->getDataLayout(); | |||
2282 | unsigned IntptrSize = DL.getTypeStoreSize(DFS.IntptrTy); | |||
2283 | if (IntptrSize == OriginSize) | |||
2284 | return Origin; | |||
2285 | assert(IntptrSize == OriginSize * 2)((void)0); | |||
2286 | Origin = IRB.CreateIntCast(Origin, DFS.IntptrTy, /* isSigned */ false); | |||
2287 | return IRB.CreateOr(Origin, IRB.CreateShl(Origin, OriginSize * 8)); | |||
2288 | } | |||
2289 | ||||
2290 | void DFSanFunction::paintOrigin(IRBuilder<> &IRB, Value *Origin, | |||
2291 | Value *StoreOriginAddr, | |||
2292 | uint64_t StoreOriginSize, Align Alignment) { | |||
2293 | const unsigned OriginSize = DataFlowSanitizer::OriginWidthBytes; | |||
2294 | const DataLayout &DL = F->getParent()->getDataLayout(); | |||
2295 | const Align IntptrAlignment = DL.getABITypeAlign(DFS.IntptrTy); | |||
2296 | unsigned IntptrSize = DL.getTypeStoreSize(DFS.IntptrTy); | |||
2297 | assert(IntptrAlignment >= MinOriginAlignment)((void)0); | |||
2298 | assert(IntptrSize >= OriginSize)((void)0); | |||
2299 | ||||
2300 | unsigned Ofs = 0; | |||
2301 | Align CurrentAlignment = Alignment; | |||
2302 | if (Alignment >= IntptrAlignment && IntptrSize > OriginSize) { | |||
2303 | Value *IntptrOrigin = originToIntptr(IRB, Origin); | |||
2304 | Value *IntptrStoreOriginPtr = IRB.CreatePointerCast( | |||
2305 | StoreOriginAddr, PointerType::get(DFS.IntptrTy, 0)); | |||
2306 | for (unsigned I = 0; I < StoreOriginSize / IntptrSize; ++I) { | |||
2307 | Value *Ptr = | |||
2308 | I ? IRB.CreateConstGEP1_32(DFS.IntptrTy, IntptrStoreOriginPtr, I) | |||
2309 | : IntptrStoreOriginPtr; | |||
2310 | IRB.CreateAlignedStore(IntptrOrigin, Ptr, CurrentAlignment); | |||
2311 | Ofs += IntptrSize / OriginSize; | |||
2312 | CurrentAlignment = IntptrAlignment; | |||
2313 | } | |||
2314 | } | |||
2315 | ||||
2316 | for (unsigned I = Ofs; I < (StoreOriginSize + OriginSize - 1) / OriginSize; | |||
2317 | ++I) { | |||
2318 | Value *GEP = I ? IRB.CreateConstGEP1_32(DFS.OriginTy, StoreOriginAddr, I) | |||
2319 | : StoreOriginAddr; | |||
2320 | IRB.CreateAlignedStore(Origin, GEP, CurrentAlignment); | |||
2321 | CurrentAlignment = MinOriginAlignment; | |||
2322 | } | |||
2323 | } | |||
2324 | ||||
2325 | Value *DFSanFunction::convertToBool(Value *V, IRBuilder<> &IRB, | |||
2326 | const Twine &Name) { | |||
2327 | Type *VTy = V->getType(); | |||
2328 | assert(VTy->isIntegerTy())((void)0); | |||
2329 | if (VTy->getIntegerBitWidth() == 1) | |||
2330 | // Just converting a bool to a bool, so do nothing. | |||
2331 | return V; | |||
2332 | return IRB.CreateICmpNE(V, ConstantInt::get(VTy, 0), Name); | |||
2333 | } | |||
2334 | ||||
2335 | void DFSanFunction::storeOrigin(Instruction *Pos, Value *Addr, uint64_t Size, | |||
2336 | Value *Shadow, Value *Origin, | |||
2337 | Value *StoreOriginAddr, Align InstAlignment) { | |||
2338 | // Do not write origins for zero shadows because we do not trace origins for | |||
2339 | // untainted sinks. | |||
2340 | const Align OriginAlignment = getOriginAlign(InstAlignment); | |||
2341 | Value *CollapsedShadow = collapseToPrimitiveShadow(Shadow, Pos); | |||
2342 | IRBuilder<> IRB(Pos); | |||
2343 | if (auto *ConstantShadow = dyn_cast<Constant>(CollapsedShadow)) { | |||
2344 | if (!ConstantShadow->isZeroValue()) | |||
2345 | paintOrigin(IRB, updateOrigin(Origin, IRB), StoreOriginAddr, Size, | |||
2346 | OriginAlignment); | |||
2347 | return; | |||
2348 | } | |||
2349 | ||||
2350 | if (shouldInstrumentWithCall()) { | |||
2351 | IRB.CreateCall(DFS.DFSanMaybeStoreOriginFn, | |||
2352 | {CollapsedShadow, | |||
2353 | IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()), | |||
2354 | ConstantInt::get(DFS.IntptrTy, Size), Origin}); | |||
2355 | } else { | |||
2356 | Value *Cmp = convertToBool(CollapsedShadow, IRB, "_dfscmp"); | |||
2357 | Instruction *CheckTerm = SplitBlockAndInsertIfThen( | |||
2358 | Cmp, &*IRB.GetInsertPoint(), false, DFS.OriginStoreWeights, &DT); | |||
2359 | IRBuilder<> IRBNew(CheckTerm); | |||
2360 | paintOrigin(IRBNew, updateOrigin(Origin, IRBNew), StoreOriginAddr, Size, | |||
2361 | OriginAlignment); | |||
2362 | ++NumOriginStores; | |||
2363 | } | |||
2364 | } | |||
2365 | ||||
2366 | void DFSanFunction::storeZeroPrimitiveShadow(Value *Addr, uint64_t Size, | |||
2367 | Align ShadowAlign, | |||
2368 | Instruction *Pos) { | |||
2369 | IRBuilder<> IRB(Pos); | |||
2370 | IntegerType *ShadowTy = | |||
2371 | IntegerType::get(*DFS.Ctx, Size * DFS.ShadowWidthBits); | |||
2372 | Value *ExtZeroShadow = ConstantInt::get(ShadowTy, 0); | |||
2373 | Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos); | |||
2374 | Value *ExtShadowAddr = | |||
2375 | IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowTy)); | |||
2376 | IRB.CreateAlignedStore(ExtZeroShadow, ExtShadowAddr, ShadowAlign); | |||
2377 | // Do not write origins for 0 shadows because we do not trace origins for | |||
2378 | // untainted sinks. | |||
2379 | } | |||
2380 | ||||
2381 | void DFSanFunction::storePrimitiveShadowOrigin(Value *Addr, uint64_t Size, | |||
2382 | Align InstAlignment, | |||
2383 | Value *PrimitiveShadow, | |||
2384 | Value *Origin, | |||
2385 | Instruction *Pos) { | |||
2386 | const bool ShouldTrackOrigins = DFS.shouldTrackOrigins() && Origin; | |||
2387 | ||||
2388 | if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) { | |||
2389 | const auto SI = AllocaShadowMap.find(AI); | |||
2390 | if (SI != AllocaShadowMap.end()) { | |||
2391 | IRBuilder<> IRB(Pos); | |||
2392 | IRB.CreateStore(PrimitiveShadow, SI->second); | |||
2393 | ||||
2394 | // Do not write origins for 0 shadows because we do not trace origins for | |||
2395 | // untainted sinks. | |||
2396 | if (ShouldTrackOrigins && !DFS.isZeroShadow(PrimitiveShadow)) { | |||
2397 | const auto OI = AllocaOriginMap.find(AI); | |||
2398 | assert(OI != AllocaOriginMap.end() && Origin)((void)0); | |||
2399 | IRB.CreateStore(Origin, OI->second); | |||
2400 | } | |||
2401 | return; | |||
2402 | } | |||
2403 | } | |||
2404 | ||||
2405 | const Align ShadowAlign = getShadowAlign(InstAlignment); | |||
2406 | if (DFS.isZeroShadow(PrimitiveShadow)) { | |||
2407 | storeZeroPrimitiveShadow(Addr, Size, ShadowAlign, Pos); | |||
2408 | return; | |||
2409 | } | |||
2410 | ||||
2411 | IRBuilder<> IRB(Pos); | |||
2412 | Value *ShadowAddr, *OriginAddr; | |||
2413 | std::tie(ShadowAddr, OriginAddr) = | |||
2414 | DFS.getShadowOriginAddress(Addr, InstAlignment, Pos); | |||
2415 | ||||
2416 | const unsigned ShadowVecSize = 8; | |||
2417 | assert(ShadowVecSize * DFS.ShadowWidthBits <= 128 &&((void)0) | |||
2418 | "Shadow vector is too large!")((void)0); | |||
2419 | ||||
2420 | uint64_t Offset = 0; | |||
2421 | uint64_t LeftSize = Size; | |||
2422 | if (LeftSize >= ShadowVecSize) { | |||
2423 | auto *ShadowVecTy = | |||
2424 | FixedVectorType::get(DFS.PrimitiveShadowTy, ShadowVecSize); | |||
2425 | Value *ShadowVec = UndefValue::get(ShadowVecTy); | |||
2426 | for (unsigned I = 0; I != ShadowVecSize; ++I) { | |||
2427 | ShadowVec = IRB.CreateInsertElement( | |||
2428 | ShadowVec, PrimitiveShadow, | |||
2429 | ConstantInt::get(Type::getInt32Ty(*DFS.Ctx), I)); | |||
2430 | } | |||
2431 | Value *ShadowVecAddr = | |||
2432 | IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowVecTy)); | |||
2433 | do { | |||
2434 | Value *CurShadowVecAddr = | |||
2435 | IRB.CreateConstGEP1_32(ShadowVecTy, ShadowVecAddr, Offset); | |||
2436 | IRB.CreateAlignedStore(ShadowVec, CurShadowVecAddr, ShadowAlign); | |||
2437 | LeftSize -= ShadowVecSize; | |||
2438 | ++Offset; | |||
2439 | } while (LeftSize >= ShadowVecSize); | |||
2440 | Offset *= ShadowVecSize; | |||
2441 | } | |||
2442 | while (LeftSize > 0) { | |||
2443 | Value *CurShadowAddr = | |||
2444 | IRB.CreateConstGEP1_32(DFS.PrimitiveShadowTy, ShadowAddr, Offset); | |||
2445 | IRB.CreateAlignedStore(PrimitiveShadow, CurShadowAddr, ShadowAlign); | |||
2446 | --LeftSize; | |||
2447 | ++Offset; | |||
2448 | } | |||
2449 | ||||
2450 | if (ShouldTrackOrigins) { | |||
2451 | storeOrigin(Pos, Addr, Size, PrimitiveShadow, Origin, OriginAddr, | |||
2452 | InstAlignment); | |||
2453 | } | |||
2454 | } | |||
2455 | ||||
2456 | static AtomicOrdering addReleaseOrdering(AtomicOrdering AO) { | |||
2457 | switch (AO) { | |||
2458 | case AtomicOrdering::NotAtomic: | |||
2459 | return AtomicOrdering::NotAtomic; | |||
2460 | case AtomicOrdering::Unordered: | |||
2461 | case AtomicOrdering::Monotonic: | |||
2462 | case AtomicOrdering::Release: | |||
2463 | return AtomicOrdering::Release; | |||
2464 | case AtomicOrdering::Acquire: | |||
2465 | case AtomicOrdering::AcquireRelease: | |||
2466 | return AtomicOrdering::AcquireRelease; | |||
2467 | case AtomicOrdering::SequentiallyConsistent: | |||
2468 | return AtomicOrdering::SequentiallyConsistent; | |||
2469 | } | |||
2470 | llvm_unreachable("Unknown ordering")__builtin_unreachable(); | |||
2471 | } | |||
2472 | ||||
2473 | void DFSanVisitor::visitStoreInst(StoreInst &SI) { | |||
2474 | auto &DL = SI.getModule()->getDataLayout(); | |||
2475 | Value *Val = SI.getValueOperand(); | |||
2476 | uint64_t Size = DL.getTypeStoreSize(Val->getType()); | |||
2477 | if (Size == 0) | |||
2478 | return; | |||
2479 | ||||
2480 | // When an application store is atomic, increase atomic ordering between | |||
2481 | // atomic application loads and stores to ensure happen-before order; load | |||
2482 | // shadow data after application data; store zero shadow data before | |||
2483 | // application data. This ensure shadow loads return either labels of the | |||
2484 | // initial application data or zeros. | |||
2485 | if (SI.isAtomic()) | |||
2486 | SI.setOrdering(addReleaseOrdering(SI.getOrdering())); | |||
2487 | ||||
2488 | const bool ShouldTrackOrigins = | |||
2489 | DFSF.DFS.shouldTrackOrigins() && !SI.isAtomic(); | |||
2490 | std::vector<Value *> Shadows; | |||
2491 | std::vector<Value *> Origins; | |||
2492 | ||||
2493 | Value *Shadow = | |||
2494 | SI.isAtomic() ? DFSF.DFS.getZeroShadow(Val) : DFSF.getShadow(Val); | |||
2495 | ||||
2496 | if (ShouldTrackOrigins) { | |||
2497 | Shadows.push_back(Shadow); | |||
2498 | Origins.push_back(DFSF.getOrigin(Val)); | |||
2499 | } | |||
2500 | ||||
2501 | Value *PrimitiveShadow; | |||
2502 | if (ClCombinePointerLabelsOnStore) { | |||
2503 | Value *PtrShadow = DFSF.getShadow(SI.getPointerOperand()); | |||
2504 | if (ShouldTrackOrigins) { | |||
2505 | Shadows.push_back(PtrShadow); | |||
2506 | Origins.push_back(DFSF.getOrigin(SI.getPointerOperand())); | |||
2507 | } | |||
2508 | PrimitiveShadow = DFSF.combineShadows(Shadow, PtrShadow, &SI); | |||
2509 | } else { | |||
2510 | PrimitiveShadow = DFSF.collapseToPrimitiveShadow(Shadow, &SI); | |||
2511 | } | |||
2512 | Value *Origin = nullptr; | |||
2513 | if (ShouldTrackOrigins) | |||
2514 | Origin = DFSF.combineOrigins(Shadows, Origins, &SI); | |||
2515 | DFSF.storePrimitiveShadowOrigin(SI.getPointerOperand(), Size, SI.getAlign(), | |||
2516 | PrimitiveShadow, Origin, &SI); | |||
2517 | if (ClEventCallbacks) { | |||
2518 | IRBuilder<> IRB(&SI); | |||
2519 | Value *Addr8 = IRB.CreateBitCast(SI.getPointerOperand(), DFSF.DFS.Int8Ptr); | |||
2520 | IRB.CreateCall(DFSF.DFS.DFSanStoreCallbackFn, {PrimitiveShadow, Addr8}); | |||
2521 | } | |||
2522 | } | |||
2523 | ||||
2524 | void DFSanVisitor::visitCASOrRMW(Align InstAlignment, Instruction &I) { | |||
2525 | assert(isa<AtomicRMWInst>(I) || isa<AtomicCmpXchgInst>(I))((void)0); | |||
2526 | ||||
2527 | Value *Val = I.getOperand(1); | |||
2528 | const auto &DL = I.getModule()->getDataLayout(); | |||
2529 | uint64_t Size = DL.getTypeStoreSize(Val->getType()); | |||
2530 | if (Size == 0) | |||
2531 | return; | |||
2532 | ||||
2533 | // Conservatively set data at stored addresses and return with zero shadow to | |||
2534 | // prevent shadow data races. | |||
2535 | IRBuilder<> IRB(&I); | |||
2536 | Value *Addr = I.getOperand(0); | |||
2537 | const Align ShadowAlign = DFSF.getShadowAlign(InstAlignment); | |||
2538 | DFSF.storeZeroPrimitiveShadow(Addr, Size, ShadowAlign, &I); | |||
2539 | DFSF.setShadow(&I, DFSF.DFS.getZeroShadow(&I)); | |||
2540 | DFSF.setOrigin(&I, DFSF.DFS.ZeroOrigin); | |||
2541 | } | |||
2542 | ||||
2543 | void DFSanVisitor::visitAtomicRMWInst(AtomicRMWInst &I) { | |||
2544 | visitCASOrRMW(I.getAlign(), I); | |||
2545 | // TODO: The ordering change follows MSan. It is possible not to change | |||
2546 | // ordering because we always set and use 0 shadows. | |||
2547 | I.setOrdering(addReleaseOrdering(I.getOrdering())); | |||
2548 | } | |||
2549 | ||||
2550 | void DFSanVisitor::visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { | |||
2551 | visitCASOrRMW(I.getAlign(), I); | |||
| ||||
2552 | // TODO: The ordering change follows MSan. It is possible not to change | |||
2553 | // ordering because we always set and use 0 shadows. | |||
2554 | I.setSuccessOrdering(addReleaseOrdering(I.getSuccessOrdering())); | |||
2555 | } | |||
2556 | ||||
2557 | void DFSanVisitor::visitUnaryOperator(UnaryOperator &UO) { | |||
2558 | visitInstOperands(UO); | |||
2559 | } | |||
2560 | ||||
2561 | void DFSanVisitor::visitBinaryOperator(BinaryOperator &BO) { | |||
2562 | visitInstOperands(BO); | |||
2563 | } | |||
2564 | ||||
2565 | void DFSanVisitor::visitBitCastInst(BitCastInst &BCI) { | |||
2566 | if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { | |||
2567 | // Special case: if this is the bitcast (there is exactly 1 allowed) between | |||
2568 | // a musttail call and a ret, don't instrument. New instructions are not | |||
2569 | // allowed after a musttail call. | |||
2570 | if (auto *CI = dyn_cast<CallInst>(BCI.getOperand(0))) | |||
2571 | if (CI->isMustTailCall()) | |||
2572 | return; | |||
2573 | } | |||
2574 | // TODO: handle musttail call returns for IA_Args. | |||
2575 | visitInstOperands(BCI); | |||
2576 | } | |||
2577 | ||||
2578 | void DFSanVisitor::visitCastInst(CastInst &CI) { visitInstOperands(CI); } | |||
2579 | ||||
2580 | void DFSanVisitor::visitCmpInst(CmpInst &CI) { | |||
2581 | visitInstOperands(CI); | |||
2582 | if (ClEventCallbacks) { | |||
2583 | IRBuilder<> IRB(&CI); | |||
2584 | Value *CombinedShadow = DFSF.getShadow(&CI); | |||
2585 | IRB.CreateCall(DFSF.DFS.DFSanCmpCallbackFn, CombinedShadow); | |||
2586 | } | |||
2587 | } | |||
2588 | ||||
2589 | void DFSanVisitor::visitLandingPadInst(LandingPadInst &LPI) { | |||
2590 | // We do not need to track data through LandingPadInst. | |||
2591 | // | |||
2592 | // For the C++ exceptions, if a value is thrown, this value will be stored | |||
2593 | // in a memory location provided by __cxa_allocate_exception(...) (on the | |||
2594 | // throw side) or __cxa_begin_catch(...) (on the catch side). | |||
2595 | // This memory will have a shadow, so with the loads and stores we will be | |||
2596 | // able to propagate labels on data thrown through exceptions, without any | |||
2597 | // special handling of the LandingPadInst. | |||
2598 | // | |||
2599 | // The second element in the pair result of the LandingPadInst is a | |||
2600 | // register value, but it is for a type ID and should never be tainted. | |||
2601 | DFSF.setShadow(&LPI, DFSF.DFS.getZeroShadow(&LPI)); | |||
2602 | DFSF.setOrigin(&LPI, DFSF.DFS.ZeroOrigin); | |||
2603 | } | |||
2604 | ||||
2605 | void DFSanVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) { | |||
2606 | if (ClCombineOffsetLabelsOnGEP) { | |||
2607 | visitInstOperands(GEPI); | |||
2608 | return; | |||
2609 | } | |||
2610 | ||||
2611 | // Only propagate shadow/origin of base pointer value but ignore those of | |||
2612 | // offset operands. | |||
2613 | Value *BasePointer = GEPI.getPointerOperand(); | |||
2614 | DFSF.setShadow(&GEPI, DFSF.getShadow(BasePointer)); | |||
2615 | if (DFSF.DFS.shouldTrackOrigins()) | |||
2616 | DFSF.setOrigin(&GEPI, DFSF.getOrigin(BasePointer)); | |||
2617 | } | |||
2618 | ||||
2619 | void DFSanVisitor::visitExtractElementInst(ExtractElementInst &I) { | |||
2620 | visitInstOperands(I); | |||
2621 | } | |||
2622 | ||||
2623 | void DFSanVisitor::visitInsertElementInst(InsertElementInst &I) { | |||
2624 | visitInstOperands(I); | |||
2625 | } | |||
2626 | ||||
2627 | void DFSanVisitor::visitShuffleVectorInst(ShuffleVectorInst &I) { | |||
2628 | visitInstOperands(I); | |||
2629 | } | |||
2630 | ||||
2631 | void DFSanVisitor::visitExtractValueInst(ExtractValueInst &I) { | |||
2632 | if (!DFSF.DFS.shouldTrackFieldsAndIndices()) { | |||
2633 | visitInstOperands(I); | |||
2634 | return; | |||
2635 | } | |||
2636 | ||||
2637 | IRBuilder<> IRB(&I); | |||
2638 | Value *Agg = I.getAggregateOperand(); | |||
2639 | Value *AggShadow = DFSF.getShadow(Agg); | |||
2640 | Value *ResShadow = IRB.CreateExtractValue(AggShadow, I.getIndices()); | |||
2641 | DFSF.setShadow(&I, ResShadow); | |||
2642 | visitInstOperandOrigins(I); | |||
2643 | } | |||
2644 | ||||
2645 | void DFSanVisitor::visitInsertValueInst(InsertValueInst &I) { | |||
2646 | if (!DFSF.DFS.shouldTrackFieldsAndIndices()) { | |||
2647 | visitInstOperands(I); | |||
2648 | return; | |||
2649 | } | |||
2650 | ||||
2651 | IRBuilder<> IRB(&I); | |||
2652 | Value *AggShadow = DFSF.getShadow(I.getAggregateOperand()); | |||
2653 | Value *InsShadow = DFSF.getShadow(I.getInsertedValueOperand()); | |||
2654 | Value *Res = IRB.CreateInsertValue(AggShadow, InsShadow, I.getIndices()); | |||
2655 | DFSF.setShadow(&I, Res); | |||
2656 | visitInstOperandOrigins(I); | |||
2657 | } | |||
2658 | ||||
2659 | void DFSanVisitor::visitAllocaInst(AllocaInst &I) { | |||
2660 | bool AllLoadsStores = true; | |||
2661 | for (User *U : I.users()) { | |||
2662 | if (isa<LoadInst>(U)) | |||
2663 | continue; | |||
2664 | ||||
2665 | if (StoreInst *SI = dyn_cast<StoreInst>(U)) { | |||
2666 | if (SI->getPointerOperand() == &I) | |||
2667 | continue; | |||
2668 | } | |||
2669 | ||||
2670 | AllLoadsStores = false; | |||
2671 | break; | |||
2672 | } | |||
2673 | if (AllLoadsStores) { | |||
2674 | IRBuilder<> IRB(&I); | |||
2675 | DFSF.AllocaShadowMap[&I] = IRB.CreateAlloca(DFSF.DFS.PrimitiveShadowTy); | |||
2676 | if (DFSF.DFS.shouldTrackOrigins()) { | |||
2677 | DFSF.AllocaOriginMap[&I] = | |||
2678 | IRB.CreateAlloca(DFSF.DFS.OriginTy, nullptr, "_dfsa"); | |||
2679 | } | |||
2680 | } | |||
2681 | DFSF.setShadow(&I, DFSF.DFS.ZeroPrimitiveShadow); | |||
2682 | DFSF.setOrigin(&I, DFSF.DFS.ZeroOrigin); | |||
2683 | } | |||
2684 | ||||
2685 | void DFSanVisitor::visitSelectInst(SelectInst &I) { | |||
2686 | Value *CondShadow = DFSF.getShadow(I.getCondition()); | |||
2687 | Value *TrueShadow = DFSF.getShadow(I.getTrueValue()); | |||
2688 | Value *FalseShadow = DFSF.getShadow(I.getFalseValue()); | |||
2689 | Value *ShadowSel = nullptr; | |||
2690 | const bool ShouldTrackOrigins = DFSF.DFS.shouldTrackOrigins(); | |||
2691 | std::vector<Value *> Shadows; | |||
2692 | std::vector<Value *> Origins; | |||
2693 | Value *TrueOrigin = | |||
2694 | ShouldTrackOrigins ? DFSF.getOrigin(I.getTrueValue()) : nullptr; | |||
2695 | Value *FalseOrigin = | |||
2696 | ShouldTrackOrigins ? DFSF.getOrigin(I.getFalseValue()) : nullptr; | |||
2697 | ||||
2698 | if (isa<VectorType>(I.getCondition()->getType())) { | |||
2699 | ShadowSel = DFSF.combineShadowsThenConvert(I.getType(), TrueShadow, | |||
2700 | FalseShadow, &I); | |||
2701 | if (ShouldTrackOrigins) { | |||
2702 | Shadows.push_back(TrueShadow); | |||
2703 | Shadows.push_back(FalseShadow); | |||
2704 | Origins.push_back(TrueOrigin); | |||
2705 | Origins.push_back(FalseOrigin); | |||
2706 | } | |||
2707 | } else { | |||
2708 | if (TrueShadow == FalseShadow) { | |||
2709 | ShadowSel = TrueShadow; | |||
2710 | if (ShouldTrackOrigins) { | |||
2711 | Shadows.push_back(TrueShadow); | |||
2712 | Origins.push_back(TrueOrigin); | |||
2713 | } | |||
2714 | } else { | |||
2715 | ShadowSel = | |||
2716 | SelectInst::Create(I.getCondition(), TrueShadow, FalseShadow, "", &I); | |||
2717 | if (ShouldTrackOrigins) { | |||
2718 | Shadows.push_back(ShadowSel); | |||
2719 | Origins.push_back(SelectInst::Create(I.getCondition(), TrueOrigin, | |||
2720 | FalseOrigin, "", &I)); | |||
2721 | } | |||
2722 | } | |||
2723 | } | |||
2724 | DFSF.setShadow(&I, ClTrackSelectControlFlow | |||
2725 | ? DFSF.combineShadowsThenConvert( | |||
2726 | I.getType(), CondShadow, ShadowSel, &I) | |||
2727 | : ShadowSel); | |||
2728 | if (ShouldTrackOrigins) { | |||
2729 | if (ClTrackSelectControlFlow) { | |||
2730 | Shadows.push_back(CondShadow); | |||
2731 | Origins.push_back(DFSF.getOrigin(I.getCondition())); | |||
2732 | } | |||
2733 | DFSF.setOrigin(&I, DFSF.combineOrigins(Shadows, Origins, &I)); | |||
2734 | } | |||
2735 | } | |||
2736 | ||||
2737 | void DFSanVisitor::visitMemSetInst(MemSetInst &I) { | |||
2738 | IRBuilder<> IRB(&I); | |||
2739 | Value *ValShadow = DFSF.getShadow(I.getValue()); | |||
2740 | Value *ValOrigin = DFSF.DFS.shouldTrackOrigins() | |||
2741 | ? DFSF.getOrigin(I.getValue()) | |||
2742 | : DFSF.DFS.ZeroOrigin; | |||
2743 | IRB.CreateCall( | |||
2744 | DFSF.DFS.DFSanSetLabelFn, | |||
2745 | {ValShadow, ValOrigin, | |||
2746 | IRB.CreateBitCast(I.getDest(), Type::getInt8PtrTy(*DFSF.DFS.Ctx)), | |||
2747 | IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy)}); | |||
2748 | } | |||
2749 | ||||
2750 | void DFSanVisitor::visitMemTransferInst(MemTransferInst &I) { | |||
2751 | IRBuilder<> IRB(&I); | |||
2752 | ||||
2753 | // CopyOrMoveOrigin transfers origins by refering to their shadows. So we | |||
2754 | // need to move origins before moving shadows. | |||
2755 | if (DFSF.DFS.shouldTrackOrigins()) { | |||
2756 | IRB.CreateCall( | |||
2757 | DFSF.DFS.DFSanMemOriginTransferFn, | |||
2758 | {IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()), | |||
2759 | IRB.CreatePointerCast(I.getArgOperand(1), IRB.getInt8PtrTy()), | |||
2760 | IRB.CreateIntCast(I.getArgOperand(2), DFSF.DFS.IntptrTy, false)}); | |||
2761 | } | |||
2762 | ||||
2763 | Value *RawDestShadow = DFSF.DFS.getShadowAddress(I.getDest(), &I); | |||
2764 | Value *SrcShadow = DFSF.DFS.getShadowAddress(I.getSource(), &I); | |||
2765 | Value *LenShadow = | |||
2766 | IRB.CreateMul(I.getLength(), ConstantInt::get(I.getLength()->getType(), | |||
2767 | DFSF.DFS.ShadowWidthBytes)); | |||
2768 | Type *Int8Ptr = Type::getInt8PtrTy(*DFSF.DFS.Ctx); | |||
2769 | Value *DestShadow = IRB.CreateBitCast(RawDestShadow, Int8Ptr); | |||
2770 | SrcShadow = IRB.CreateBitCast(SrcShadow, Int8Ptr); | |||
2771 | auto *MTI = cast<MemTransferInst>( | |||
2772 | IRB.CreateCall(I.getFunctionType(), I.getCalledOperand(), | |||
2773 | {DestShadow, SrcShadow, LenShadow, I.getVolatileCst()})); | |||
2774 | if (ClPreserveAlignment) { | |||
2775 | MTI->setDestAlignment(I.getDestAlign() * DFSF.DFS.ShadowWidthBytes); | |||
2776 | MTI->setSourceAlignment(I.getSourceAlign() * DFSF.DFS.ShadowWidthBytes); | |||
2777 | } else { | |||
2778 | MTI->setDestAlignment(Align(DFSF.DFS.ShadowWidthBytes)); | |||
2779 | MTI->setSourceAlignment(Align(DFSF.DFS.ShadowWidthBytes)); | |||
2780 | } | |||
2781 | if (ClEventCallbacks) { | |||
2782 | IRB.CreateCall(DFSF.DFS.DFSanMemTransferCallbackFn, | |||
2783 | {RawDestShadow, | |||
2784 | IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy)}); | |||
2785 | } | |||
2786 | } | |||
2787 | ||||
2788 | static bool isAMustTailRetVal(Value *RetVal) { | |||
2789 | // Tail call may have a bitcast between return. | |||
2790 | if (auto *I = dyn_cast<BitCastInst>(RetVal)) { | |||
2791 | RetVal = I->getOperand(0); | |||
2792 | } | |||
2793 | if (auto *I = dyn_cast<CallInst>(RetVal)) { | |||
2794 | return I->isMustTailCall(); | |||
2795 | } | |||
2796 | return false; | |||
2797 | } | |||
2798 | ||||
2799 | void DFSanVisitor::visitReturnInst(ReturnInst &RI) { | |||
2800 | if (!DFSF.IsNativeABI && RI.getReturnValue()) { | |||
2801 | switch (DFSF.IA) { | |||
2802 | case DataFlowSanitizer::IA_TLS: { | |||
2803 | // Don't emit the instrumentation for musttail call returns. | |||
2804 | if (isAMustTailRetVal(RI.getReturnValue())) | |||
2805 | return; | |||
2806 | ||||
2807 | Value *S = DFSF.getShadow(RI.getReturnValue()); | |||
2808 | IRBuilder<> IRB(&RI); | |||
2809 | Type *RT = DFSF.F->getFunctionType()->getReturnType(); | |||
2810 | unsigned Size = | |||
2811 | getDataLayout().getTypeAllocSize(DFSF.DFS.getShadowTy(RT)); | |||
2812 | if (Size <= RetvalTLSSize) { | |||
2813 | // If the size overflows, stores nothing. At callsite, oversized return | |||
2814 | // shadows are set to zero. | |||
2815 | IRB.CreateAlignedStore(S, DFSF.getRetvalTLS(RT, IRB), | |||
2816 | ShadowTLSAlignment); | |||
2817 | } | |||
2818 | if (DFSF.DFS.shouldTrackOrigins()) { | |||
2819 | Value *O = DFSF.getOrigin(RI.getReturnValue()); | |||
2820 | IRB.CreateStore(O, DFSF.getRetvalOriginTLS()); | |||
2821 | } | |||
2822 | break; | |||
2823 | } | |||
2824 | case DataFlowSanitizer::IA_Args: { | |||
2825 | // TODO: handle musttail call returns for IA_Args. | |||
2826 | ||||
2827 | IRBuilder<> IRB(&RI); | |||
2828 | Type *RT = DFSF.F->getFunctionType()->getReturnType(); | |||
2829 | Value *InsVal = | |||
2830 | IRB.CreateInsertValue(UndefValue::get(RT), RI.getReturnValue(), 0); | |||
2831 | Value *InsShadow = | |||
2832 | IRB.CreateInsertValue(InsVal, DFSF.getShadow(RI.getReturnValue()), 1); | |||
2833 | RI.setOperand(0, InsShadow); | |||
2834 | break; | |||
2835 | } | |||
2836 | } | |||
2837 | } | |||
2838 | } | |||
2839 | ||||
2840 | void DFSanVisitor::addShadowArguments(Function &F, CallBase &CB, | |||
2841 | std::vector<Value *> &Args, | |||
2842 | IRBuilder<> &IRB) { | |||
2843 | FunctionType *FT = F.getFunctionType(); | |||
2844 | ||||
2845 | auto *I = CB.arg_begin(); | |||
2846 | ||||
2847 | // Adds non-variable argument shadows. | |||
2848 | for (unsigned N = FT->getNumParams(); N != 0; ++I, --N) | |||
2849 | Args.push_back(DFSF.collapseToPrimitiveShadow(DFSF.getShadow(*I), &CB)); | |||
2850 | ||||
2851 | // Adds variable argument shadows. | |||
2852 | if (FT->isVarArg()) { | |||
2853 | auto *LabelVATy = ArrayType::get(DFSF.DFS.PrimitiveShadowTy, | |||
2854 | CB.arg_size() - FT->getNumParams()); | |||
2855 | auto *LabelVAAlloca = | |||
2856 | new AllocaInst(LabelVATy, getDataLayout().getAllocaAddrSpace(), | |||
2857 | "labelva", &DFSF.F->getEntryBlock().front()); | |||
2858 | ||||
2859 | for (unsigned N = 0; I != CB.arg_end(); ++I, ++N) { | |||
2860 | auto *LabelVAPtr = IRB.CreateStructGEP(LabelVATy, LabelVAAlloca, N); | |||
2861 | IRB.CreateStore(DFSF.collapseToPrimitiveShadow(DFSF.getShadow(*I), &CB), | |||
2862 | LabelVAPtr); | |||
2863 | } | |||
2864 | ||||
2865 | Args.push_back(IRB.CreateStructGEP(LabelVATy, LabelVAAlloca, 0)); | |||
2866 | } | |||
2867 | ||||
2868 | // Adds the return value shadow. | |||
2869 | if (!FT->getReturnType()->isVoidTy()) { | |||
2870 | if (!DFSF.LabelReturnAlloca) { | |||
2871 | DFSF.LabelReturnAlloca = new AllocaInst( | |||
2872 | DFSF.DFS.PrimitiveShadowTy, getDataLayout().getAllocaAddrSpace(), | |||
2873 | "labelreturn", &DFSF.F->getEntryBlock().front()); | |||
2874 | } | |||
2875 | Args.push_back(DFSF.LabelReturnAlloca); | |||
2876 | } | |||
2877 | } | |||
2878 | ||||
2879 | void DFSanVisitor::addOriginArguments(Function &F, CallBase &CB, | |||
2880 | std::vector<Value *> &Args, | |||
2881 | IRBuilder<> &IRB) { | |||
2882 | FunctionType *FT = F.getFunctionType(); | |||
2883 | ||||
2884 | auto *I = CB.arg_begin(); | |||
2885 | ||||
2886 | // Add non-variable argument origins. | |||
2887 | for (unsigned N = FT->getNumParams(); N != 0; ++I, --N) | |||
2888 | Args.push_back(DFSF.getOrigin(*I)); | |||
2889 | ||||
2890 | // Add variable argument origins. | |||
2891 | if (FT->isVarArg()) { | |||
2892 | auto *OriginVATy = | |||
2893 | ArrayType::get(DFSF.DFS.OriginTy, CB.arg_size() - FT->getNumParams()); | |||
2894 | auto *OriginVAAlloca = | |||
2895 | new AllocaInst(OriginVATy, getDataLayout().getAllocaAddrSpace(), | |||
2896 | "originva", &DFSF.F->getEntryBlock().front()); | |||
2897 | ||||
2898 | for (unsigned N = 0; I != CB.arg_end(); ++I, ++N) { | |||
2899 | auto *OriginVAPtr = IRB.CreateStructGEP(OriginVATy, OriginVAAlloca, N); | |||
2900 | IRB.CreateStore(DFSF.getOrigin(*I), OriginVAPtr); | |||
2901 | } | |||
2902 | ||||
2903 | Args.push_back(IRB.CreateStructGEP(OriginVATy, OriginVAAlloca, 0)); | |||
2904 | } | |||
2905 | ||||
2906 | // Add the return value origin. | |||
2907 | if (!FT->getReturnType()->isVoidTy()) { | |||
2908 | if (!DFSF.OriginReturnAlloca) { | |||
2909 | DFSF.OriginReturnAlloca = new AllocaInst( | |||
2910 | DFSF.DFS.OriginTy, getDataLayout().getAllocaAddrSpace(), | |||
2911 | "originreturn", &DFSF.F->getEntryBlock().front()); | |||
2912 | } | |||
2913 | Args.push_back(DFSF.OriginReturnAlloca); | |||
2914 | } | |||
2915 | } | |||
2916 | ||||
2917 | bool DFSanVisitor::visitWrappedCallBase(Function &F, CallBase &CB) { | |||
2918 | IRBuilder<> IRB(&CB); | |||
2919 | switch (DFSF.DFS.getWrapperKind(&F)) { | |||
2920 | case DataFlowSanitizer::WK_Warning: | |||
2921 | CB.setCalledFunction(&F); | |||
2922 | IRB.CreateCall(DFSF.DFS.DFSanUnimplementedFn, | |||
2923 | IRB.CreateGlobalStringPtr(F.getName())); | |||
2924 | DFSF.setShadow(&CB, DFSF.DFS.getZeroShadow(&CB)); | |||
2925 | DFSF.setOrigin(&CB, DFSF.DFS.ZeroOrigin); | |||
2926 | return true; | |||
2927 | case DataFlowSanitizer::WK_Discard: | |||
2928 | CB.setCalledFunction(&F); | |||
2929 | DFSF.setShadow(&CB, DFSF.DFS.getZeroShadow(&CB)); | |||
2930 | DFSF.setOrigin(&CB, DFSF.DFS.ZeroOrigin); | |||
2931 | return true; | |||
2932 | case DataFlowSanitizer::WK_Functional: | |||
2933 | CB.setCalledFunction(&F); | |||
2934 | visitInstOperands(CB); | |||
2935 | return true; | |||
2936 | case DataFlowSanitizer::WK_Custom: | |||
2937 | // Don't try to handle invokes of custom functions, it's too complicated. | |||
2938 | // Instead, invoke the dfsw$ wrapper, which will in turn call the __dfsw_ | |||
2939 | // wrapper. | |||
2940 | CallInst *CI = dyn_cast<CallInst>(&CB); | |||
2941 | if (!CI) | |||
2942 | return false; | |||
2943 | ||||
2944 | const bool ShouldTrackOrigins = DFSF.DFS.shouldTrackOrigins(); | |||
2945 | FunctionType *FT = F.getFunctionType(); | |||
2946 | TransformedFunction CustomFn = DFSF.DFS.getCustomFunctionType(FT); | |||
2947 | std::string CustomFName = ShouldTrackOrigins ? "__dfso_" : "__dfsw_"; | |||
2948 | CustomFName += F.getName(); | |||
2949 | FunctionCallee CustomF = DFSF.DFS.Mod->getOrInsertFunction( | |||
2950 | CustomFName, CustomFn.TransformedType); | |||
2951 | if (Function *CustomFn = dyn_cast<Function>(CustomF.getCallee())) { | |||
2952 | CustomFn->copyAttributesFrom(&F); | |||
2953 | ||||
2954 | // Custom functions returning non-void will write to the return label. | |||
2955 | if (!FT->getReturnType()->isVoidTy()) { | |||
2956 | CustomFn->removeAttributes(AttributeList::FunctionIndex, | |||
2957 | DFSF.DFS.ReadOnlyNoneAttrs); | |||
2958 | } | |||
2959 | } | |||
2960 | ||||
2961 | std::vector<Value *> Args; | |||
2962 | ||||
2963 | // Adds non-variable arguments. | |||
2964 | auto *I = CB.arg_begin(); | |||
2965 | for (unsigned N = FT->getNumParams(); N != 0; ++I, --N) { | |||
2966 | Type *T = (*I)->getType(); | |||
2967 | FunctionType *ParamFT; | |||
2968 | if (isa<PointerType>(T) && | |||
2969 | (ParamFT = dyn_cast<FunctionType>(T->getPointerElementType()))) { | |||
2970 | std::string TName = "dfst"; | |||
2971 | TName += utostr(FT->getNumParams() - N); | |||
2972 | TName += "$"; | |||
2973 | TName += F.getName(); | |||
2974 | Constant *Trampoline = | |||
2975 | DFSF.DFS.getOrBuildTrampolineFunction(ParamFT, TName); | |||
2976 | Args.push_back(Trampoline); | |||
2977 | Args.push_back( | |||
2978 | IRB.CreateBitCast(*I, Type::getInt8PtrTy(*DFSF.DFS.Ctx))); | |||
2979 | } else { | |||
2980 | Args.push_back(*I); | |||
2981 | } | |||
2982 | } | |||
2983 | ||||
2984 | // Adds shadow arguments. | |||
2985 | const unsigned ShadowArgStart = Args.size(); | |||
2986 | addShadowArguments(F, CB, Args, IRB); | |||
2987 | ||||
2988 | // Adds origin arguments. | |||
2989 | const unsigned OriginArgStart = Args.size(); | |||
2990 | if (ShouldTrackOrigins) | |||
2991 | addOriginArguments(F, CB, Args, IRB); | |||
2992 | ||||
2993 | // Adds variable arguments. | |||
2994 | append_range(Args, drop_begin(CB.args(), FT->getNumParams())); | |||
2995 | ||||
2996 | CallInst *CustomCI = IRB.CreateCall(CustomF, Args); | |||
2997 | CustomCI->setCallingConv(CI->getCallingConv()); | |||
2998 | CustomCI->setAttributes(transformFunctionAttributes( | |||
2999 | CustomFn, CI->getContext(), CI->getAttributes())); | |||
3000 | ||||
3001 | // Update the parameter attributes of the custom call instruction to | |||
3002 | // zero extend the shadow parameters. This is required for targets | |||
3003 | // which consider PrimitiveShadowTy an illegal type. | |||
3004 | for (unsigned N = 0; N < FT->getNumParams(); N++) { | |||
3005 | const unsigned ArgNo = ShadowArgStart + N; | |||
3006 | if (CustomCI->getArgOperand(ArgNo)->getType() == | |||
3007 | DFSF.DFS.PrimitiveShadowTy) | |||
3008 | CustomCI->addParamAttr(ArgNo, Attribute::ZExt); | |||
3009 | if (ShouldTrackOrigins) { | |||
3010 | const unsigned OriginArgNo = OriginArgStart + N; | |||
3011 | if (CustomCI->getArgOperand(OriginArgNo)->getType() == | |||
3012 | DFSF.DFS.OriginTy) | |||
3013 | CustomCI->addParamAttr(OriginArgNo, Attribute::ZExt); | |||
3014 | } | |||
3015 | } | |||
3016 | ||||
3017 | // Loads the return value shadow and origin. | |||
3018 | if (!FT->getReturnType()->isVoidTy()) { | |||
3019 | LoadInst *LabelLoad = | |||
3020 | IRB.CreateLoad(DFSF.DFS.PrimitiveShadowTy, DFSF.LabelReturnAlloca); | |||
3021 | DFSF.setShadow(CustomCI, DFSF.expandFromPrimitiveShadow( | |||
3022 | FT->getReturnType(), LabelLoad, &CB)); | |||
3023 | if (ShouldTrackOrigins) { | |||
3024 | LoadInst *OriginLoad = | |||
3025 | IRB.CreateLoad(DFSF.DFS.OriginTy, DFSF.OriginReturnAlloca); | |||
3026 | DFSF.setOrigin(CustomCI, OriginLoad); | |||
3027 | } | |||
3028 | } | |||
3029 | ||||
3030 | CI->replaceAllUsesWith(CustomCI); | |||
3031 | CI->eraseFromParent(); | |||
3032 | return true; | |||
3033 | } | |||
3034 | return false; | |||
3035 | } | |||
3036 | ||||
3037 | void DFSanVisitor::visitCallBase(CallBase &CB) { | |||
3038 | Function *F = CB.getCalledFunction(); | |||
3039 | if ((F && F->isIntrinsic()) || CB.isInlineAsm()) { | |||
3040 | visitInstOperands(CB); | |||
3041 | return; | |||
3042 | } | |||
3043 | ||||
3044 | // Calls to this function are synthesized in wrappers, and we shouldn't | |||
3045 | // instrument them. | |||
3046 | if (F == DFSF.DFS.DFSanVarargWrapperFn.getCallee()->stripPointerCasts()) | |||
3047 | return; | |||
3048 | ||||
3049 | DenseMap<Value *, Function *>::iterator UnwrappedFnIt = | |||
3050 | DFSF.DFS.UnwrappedFnMap.find(CB.getCalledOperand()); | |||
3051 | if (UnwrappedFnIt != DFSF.DFS.UnwrappedFnMap.end()) | |||
3052 | if (visitWrappedCallBase(*UnwrappedFnIt->second, CB)) | |||
3053 | return; | |||
3054 | ||||
3055 | IRBuilder<> IRB(&CB); | |||
3056 | ||||
3057 | const bool ShouldTrackOrigins = DFSF.DFS.shouldTrackOrigins(); | |||
3058 | FunctionType *FT = CB.getFunctionType(); | |||
3059 | if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { | |||
3060 | // Stores argument shadows. | |||
3061 | unsigned ArgOffset = 0; | |||
3062 | const DataLayout &DL = getDataLayout(); | |||
3063 | for (unsigned I = 0, N = FT->getNumParams(); I != N; ++I) { | |||
3064 | if (ShouldTrackOrigins) { | |||
3065 | // Ignore overflowed origins | |||
3066 | Value *ArgShadow = DFSF.getShadow(CB.getArgOperand(I)); | |||
3067 | if (I < DFSF.DFS.NumOfElementsInArgOrgTLS && | |||
3068 | !DFSF.DFS.isZeroShadow(ArgShadow)) | |||
3069 | IRB.CreateStore(DFSF.getOrigin(CB.getArgOperand(I)), | |||
3070 | DFSF.getArgOriginTLS(I, IRB)); | |||
3071 | } | |||
3072 | ||||
3073 | unsigned Size = | |||
3074 | DL.getTypeAllocSize(DFSF.DFS.getShadowTy(FT->getParamType(I))); | |||
3075 | // Stop storing if arguments' size overflows. Inside a function, arguments | |||
3076 | // after overflow have zero shadow values. | |||
3077 | if (ArgOffset + Size > ArgTLSSize) | |||
3078 | break; | |||
3079 | IRB.CreateAlignedStore( | |||
3080 | DFSF.getShadow(CB.getArgOperand(I)), | |||
3081 | DFSF.getArgTLS(FT->getParamType(I), ArgOffset, IRB), | |||
3082 | ShadowTLSAlignment); | |||
3083 | ArgOffset += alignTo(Size, ShadowTLSAlignment); | |||
3084 | } | |||
3085 | } | |||
3086 | ||||
3087 | Instruction *Next = nullptr; | |||
3088 | if (!CB.getType()->isVoidTy()) { | |||
3089 | if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { | |||
3090 | if (II->getNormalDest()->getSinglePredecessor()) { | |||
3091 | Next = &II->getNormalDest()->front(); | |||
3092 | } else { | |||
3093 | BasicBlock *NewBB = | |||
3094 | SplitEdge(II->getParent(), II->getNormalDest(), &DFSF.DT); | |||
3095 | Next = &NewBB->front(); | |||
3096 | } | |||
3097 | } else { | |||
3098 | assert(CB.getIterator() != CB.getParent()->end())((void)0); | |||
3099 | Next = CB.getNextNode(); | |||
3100 | } | |||
3101 | ||||
3102 | if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { | |||
3103 | // Don't emit the epilogue for musttail call returns. | |||
3104 | if (isa<CallInst>(CB) && cast<CallInst>(CB).isMustTailCall()) | |||
3105 | return; | |||
3106 | ||||
3107 | // Loads the return value shadow. | |||
3108 | IRBuilder<> NextIRB(Next); | |||
3109 | const DataLayout &DL = getDataLayout(); | |||
3110 | unsigned Size = DL.getTypeAllocSize(DFSF.DFS.getShadowTy(&CB)); | |||
3111 | if (Size > RetvalTLSSize) { | |||
3112 | // Set overflowed return shadow to be zero. | |||
3113 | DFSF.setShadow(&CB, DFSF.DFS.getZeroShadow(&CB)); | |||
3114 | } else { | |||
3115 | LoadInst *LI = NextIRB.CreateAlignedLoad( | |||
3116 | DFSF.DFS.getShadowTy(&CB), DFSF.getRetvalTLS(CB.getType(), NextIRB), | |||
3117 | ShadowTLSAlignment, "_dfsret"); | |||
3118 | DFSF.SkipInsts.insert(LI); | |||
3119 | DFSF.setShadow(&CB, LI); | |||
3120 | DFSF.NonZeroChecks.push_back(LI); | |||
3121 | } | |||
3122 | ||||
3123 | if (ShouldTrackOrigins) { | |||
3124 | LoadInst *LI = NextIRB.CreateLoad( | |||
3125 | DFSF.DFS.OriginTy, DFSF.getRetvalOriginTLS(), "_dfsret_o"); | |||
3126 | DFSF.SkipInsts.insert(LI); | |||
3127 | DFSF.setOrigin(&CB, LI); | |||
3128 | } | |||
3129 | } | |||
3130 | } | |||
3131 | ||||
3132 | // Do all instrumentation for IA_Args down here to defer tampering with the | |||
3133 | // CFG in a way that SplitEdge may be able to detect. | |||
3134 | if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_Args) { | |||
3135 | // TODO: handle musttail call returns for IA_Args. | |||
3136 | ||||
3137 | FunctionType *NewFT = DFSF.DFS.getArgsFunctionType(FT); | |||
3138 | Value *Func = | |||
3139 | IRB.CreateBitCast(CB.getCalledOperand(), PointerType::getUnqual(NewFT)); | |||
3140 | ||||
3141 | const unsigned NumParams = FT->getNumParams(); | |||
3142 | ||||
3143 | // Copy original arguments. | |||
3144 | auto *ArgIt = CB.arg_begin(), *ArgEnd = CB.arg_end(); | |||
3145 | std::vector<Value *> Args(NumParams); | |||
3146 | std::copy_n(ArgIt, NumParams, Args.begin()); | |||
3147 | ||||
3148 | // Add shadow arguments by transforming original arguments. | |||
3149 | std::generate_n(std::back_inserter(Args), NumParams, | |||
3150 | [&]() { return DFSF.getShadow(*ArgIt++); }); | |||
3151 | ||||
3152 | if (FT->isVarArg()) { | |||
3153 | unsigned VarArgSize = CB.arg_size() - NumParams; | |||
3154 | ArrayType *VarArgArrayTy = | |||
3155 | ArrayType::get(DFSF.DFS.PrimitiveShadowTy, VarArgSize); | |||
3156 | AllocaInst *VarArgShadow = | |||
3157 | new AllocaInst(VarArgArrayTy, getDataLayout().getAllocaAddrSpace(), | |||
3158 | "", &DFSF.F->getEntryBlock().front()); | |||
3159 | Args.push_back(IRB.CreateConstGEP2_32(VarArgArrayTy, VarArgShadow, 0, 0)); | |||
3160 | ||||
3161 | // Copy remaining var args. | |||
3162 | unsigned GepIndex = 0; | |||
3163 | std::for_each(ArgIt, ArgEnd, [&](Value *Arg) { | |||
3164 | IRB.CreateStore( | |||
3165 | DFSF.getShadow(Arg), | |||
3166 | IRB.CreateConstGEP2_32(VarArgArrayTy, VarArgShadow, 0, GepIndex++)); | |||
3167 | Args.push_back(Arg); | |||
3168 | }); | |||
3169 | } | |||
3170 | ||||
3171 | CallBase *NewCB; | |||
3172 | if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { | |||
3173 | NewCB = IRB.CreateInvoke(NewFT, Func, II->getNormalDest(), | |||
3174 | II->getUnwindDest(), Args); | |||
3175 | } else { | |||
3176 | NewCB = IRB.CreateCall(NewFT, Func, Args); | |||
3177 | } | |||
3178 | NewCB->setCallingConv(CB.getCallingConv()); | |||
3179 | NewCB->setAttributes(CB.getAttributes().removeAttributes( | |||
3180 | *DFSF.DFS.Ctx, AttributeList::ReturnIndex, | |||
3181 | AttributeFuncs::typeIncompatible(NewCB->getType()))); | |||
3182 | ||||
3183 | if (Next) { | |||
3184 | ExtractValueInst *ExVal = ExtractValueInst::Create(NewCB, 0, "", Next); | |||
3185 | DFSF.SkipInsts.insert(ExVal); | |||
3186 | ExtractValueInst *ExShadow = ExtractValueInst::Create(NewCB, 1, "", Next); | |||
3187 | DFSF.SkipInsts.insert(ExShadow); | |||
3188 | DFSF.setShadow(ExVal, ExShadow); | |||
3189 | DFSF.NonZeroChecks.push_back(ExShadow); | |||
3190 | ||||
3191 | CB.replaceAllUsesWith(ExVal); | |||
3192 | } | |||
3193 | ||||
3194 | CB.eraseFromParent(); | |||
3195 | } | |||
3196 | } | |||
3197 | ||||
3198 | void DFSanVisitor::visitPHINode(PHINode &PN) { | |||
3199 | Type *ShadowTy = DFSF.DFS.getShadowTy(&PN); | |||
3200 | PHINode *ShadowPN = | |||
3201 | PHINode::Create(ShadowTy, PN.getNumIncomingValues(), "", &PN); | |||
3202 | ||||
3203 | // Give the shadow phi node valid predecessors to fool SplitEdge into working. | |||
3204 | Value *UndefShadow = UndefValue::get(ShadowTy); | |||
3205 | for (BasicBlock *BB : PN.blocks()) | |||
3206 | ShadowPN->addIncoming(UndefShadow, BB); | |||
3207 | ||||
3208 | DFSF.setShadow(&PN, ShadowPN); | |||
3209 | ||||
3210 | PHINode *OriginPN = nullptr; | |||
3211 | if (DFSF.DFS.shouldTrackOrigins()) { | |||
3212 | OriginPN = | |||
3213 | PHINode::Create(DFSF.DFS.OriginTy, PN.getNumIncomingValues(), "", &PN); | |||
3214 | Value *UndefOrigin = UndefValue::get(DFSF.DFS.OriginTy); | |||
3215 | for (BasicBlock *BB : PN.blocks()) | |||
3216 | OriginPN->addIncoming(UndefOrigin, BB); | |||
3217 | DFSF.setOrigin(&PN, OriginPN); | |||
3218 | } | |||
3219 | ||||
3220 | DFSF.PHIFixups.push_back({&PN, ShadowPN, OriginPN}); | |||
3221 | } | |||
3222 | ||||
3223 | namespace { | |||
3224 | class DataFlowSanitizerLegacyPass : public ModulePass { | |||
3225 | private: | |||
3226 | std::vector<std::string> ABIListFiles; | |||
3227 | ||||
3228 | public: | |||
3229 | static char ID; | |||
3230 | ||||
3231 | DataFlowSanitizerLegacyPass( | |||
3232 | const std::vector<std::string> &ABIListFiles = std::vector<std::string>()) | |||
3233 | : ModulePass(ID), ABIListFiles(ABIListFiles) {} | |||
3234 | ||||
3235 | bool runOnModule(Module &M) override { | |||
3236 | return DataFlowSanitizer(ABIListFiles).runImpl(M); | |||
3237 | } | |||
3238 | }; | |||
3239 | } // namespace | |||
3240 | ||||
3241 | char DataFlowSanitizerLegacyPass::ID; | |||
3242 | ||||
3243 | INITIALIZE_PASS(DataFlowSanitizerLegacyPass, "dfsan",static void *initializeDataFlowSanitizerLegacyPassPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "DataFlowSanitizer: dynamic data flow analysis." , "dfsan", &DataFlowSanitizerLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<DataFlowSanitizerLegacyPass>), false, false ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeDataFlowSanitizerLegacyPassPassFlag; void llvm::initializeDataFlowSanitizerLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeDataFlowSanitizerLegacyPassPassFlag , initializeDataFlowSanitizerLegacyPassPassOnce, std::ref(Registry )); } | |||
3244 | "DataFlowSanitizer: dynamic data flow analysis.", false, false)static void *initializeDataFlowSanitizerLegacyPassPassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "DataFlowSanitizer: dynamic data flow analysis." , "dfsan", &DataFlowSanitizerLegacyPass::ID, PassInfo::NormalCtor_t (callDefaultCtor<DataFlowSanitizerLegacyPass>), false, false ); Registry.registerPass(*PI, true); return PI; } static llvm ::once_flag InitializeDataFlowSanitizerLegacyPassPassFlag; void llvm::initializeDataFlowSanitizerLegacyPassPass(PassRegistry &Registry) { llvm::call_once(InitializeDataFlowSanitizerLegacyPassPassFlag , initializeDataFlowSanitizerLegacyPassPassOnce, std::ref(Registry )); } | |||
3245 | ||||
3246 | ModulePass *llvm::createDataFlowSanitizerLegacyPassPass( | |||
3247 | const std::vector<std::string> &ABIListFiles) { | |||
3248 | return new DataFlowSanitizerLegacyPass(ABIListFiles); | |||
3249 | } | |||
3250 | ||||
3251 | PreservedAnalyses DataFlowSanitizerPass::run(Module &M, | |||
3252 | ModuleAnalysisManager &AM) { | |||
3253 | if (DataFlowSanitizer(ABIListFiles).runImpl(M)) { | |||
3254 | return PreservedAnalyses::none(); | |||
3255 | } | |||
3256 | return PreservedAnalyses::all(); | |||
3257 | } |
1 | //===-- llvm/Support/Alignment.h - Useful alignment functions ---*- C++ -*-===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // This file contains types to represent alignments. | |||
10 | // They are instrumented to guarantee some invariants are preserved and prevent | |||
11 | // invalid manipulations. | |||
12 | // | |||
13 | // - Align represents an alignment in bytes, it is always set and always a valid | |||
14 | // power of two, its minimum value is 1 which means no alignment requirements. | |||
15 | // | |||
16 | // - MaybeAlign is an optional type, it may be undefined or set. When it's set | |||
17 | // you can get the underlying Align type by using the getValue() method. | |||
18 | // | |||
19 | //===----------------------------------------------------------------------===// | |||
20 | ||||
21 | #ifndef LLVM_SUPPORT_ALIGNMENT_H_ | |||
22 | #define LLVM_SUPPORT_ALIGNMENT_H_ | |||
23 | ||||
24 | #include "llvm/ADT/Optional.h" | |||
25 | #include "llvm/Support/MathExtras.h" | |||
26 | #include <cassert> | |||
27 | #ifndef NDEBUG1 | |||
28 | #include <string> | |||
29 | #endif // NDEBUG | |||
30 | ||||
31 | namespace llvm { | |||
32 | ||||
33 | #define ALIGN_CHECK_ISPOSITIVE(decl) \ | |||
34 | assert(decl > 0 && (#decl " should be defined"))((void)0) | |||
35 | ||||
36 | /// This struct is a compact representation of a valid (non-zero power of two) | |||
37 | /// alignment. | |||
38 | /// It is suitable for use as static global constants. | |||
39 | struct Align { | |||
40 | private: | |||
41 | uint8_t ShiftValue = 0; /// The log2 of the required alignment. | |||
42 | /// ShiftValue is less than 64 by construction. | |||
43 | ||||
44 | friend struct MaybeAlign; | |||
45 | friend unsigned Log2(Align); | |||
46 | friend bool operator==(Align Lhs, Align Rhs); | |||
47 | friend bool operator!=(Align Lhs, Align Rhs); | |||
48 | friend bool operator<=(Align Lhs, Align Rhs); | |||
49 | friend bool operator>=(Align Lhs, Align Rhs); | |||
50 | friend bool operator<(Align Lhs, Align Rhs); | |||
51 | friend bool operator>(Align Lhs, Align Rhs); | |||
52 | friend unsigned encode(struct MaybeAlign A); | |||
53 | friend struct MaybeAlign decodeMaybeAlign(unsigned Value); | |||
54 | ||||
55 | /// A trivial type to allow construction of constexpr Align. | |||
56 | /// This is currently needed to workaround a bug in GCC 5.3 which prevents | |||
57 | /// definition of constexpr assign operators. | |||
58 | /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic | |||
59 | /// FIXME: Remove this, make all assign operators constexpr and introduce user | |||
60 | /// defined literals when we don't have to support GCC 5.3 anymore. | |||
61 | /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain | |||
62 | struct LogValue { | |||
63 | uint8_t Log; | |||
64 | }; | |||
65 | ||||
66 | public: | |||
67 | /// Default is byte-aligned. | |||
68 | constexpr Align() = default; | |||
69 | /// Do not perform checks in case of copy/move construct/assign, because the | |||
70 | /// checks have been performed when building `Other`. | |||
71 | constexpr Align(const Align &Other) = default; | |||
72 | constexpr Align(Align &&Other) = default; | |||
73 | Align &operator=(const Align &Other) = default; | |||
74 | Align &operator=(Align &&Other) = default; | |||
75 | ||||
76 | explicit Align(uint64_t Value) { | |||
77 | assert(Value > 0 && "Value must not be 0")((void)0); | |||
78 | assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2")((void)0); | |||
79 | ShiftValue = Log2_64(Value); | |||
80 | assert(ShiftValue < 64 && "Broken invariant")((void)0); | |||
81 | } | |||
82 | ||||
83 | /// This is a hole in the type system and should not be abused. | |||
84 | /// Needed to interact with C for instance. | |||
85 | uint64_t value() const { return uint64_t(1) << ShiftValue; } | |||
| ||||
86 | ||||
87 | /// Allow constructions of constexpr Align. | |||
88 | template <size_t kValue> constexpr static LogValue Constant() { | |||
89 | return LogValue{static_cast<uint8_t>(CTLog2<kValue>())}; | |||
90 | } | |||
91 | ||||
92 | /// Allow constructions of constexpr Align from types. | |||
93 | /// Compile time equivalent to Align(alignof(T)). | |||
94 | template <typename T> constexpr static LogValue Of() { | |||
95 | return Constant<std::alignment_of<T>::value>(); | |||
96 | } | |||
97 | ||||
98 | /// Constexpr constructor from LogValue type. | |||
99 | constexpr Align(LogValue CA) : ShiftValue(CA.Log) {} | |||
100 | }; | |||
101 | ||||
102 | /// Treats the value 0 as a 1, so Align is always at least 1. | |||
103 | inline Align assumeAligned(uint64_t Value) { | |||
104 | return Value ? Align(Value) : Align(); | |||
105 | } | |||
106 | ||||
107 | /// This struct is a compact representation of a valid (power of two) or | |||
108 | /// undefined (0) alignment. | |||
109 | struct MaybeAlign : public llvm::Optional<Align> { | |||
110 | private: | |||
111 | using UP = llvm::Optional<Align>; | |||
112 | ||||
113 | public: | |||
114 | /// Default is undefined. | |||
115 | MaybeAlign() = default; | |||
116 | /// Do not perform checks in case of copy/move construct/assign, because the | |||
117 | /// checks have been performed when building `Other`. | |||
118 | MaybeAlign(const MaybeAlign &Other) = default; | |||
119 | MaybeAlign &operator=(const MaybeAlign &Other) = default; | |||
120 | MaybeAlign(MaybeAlign &&Other) = default; | |||
121 | MaybeAlign &operator=(MaybeAlign &&Other) = default; | |||
122 | ||||
123 | /// Use llvm::Optional<Align> constructor. | |||
124 | using UP::UP; | |||
125 | ||||
126 | explicit MaybeAlign(uint64_t Value) { | |||
127 | assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&((void)0) | |||
128 | "Alignment is neither 0 nor a power of 2")((void)0); | |||
129 | if (Value) | |||
130 | emplace(Value); | |||
131 | } | |||
132 | ||||
133 | /// For convenience, returns a valid alignment or 1 if undefined. | |||
134 | Align valueOrOne() const { return hasValue() ? getValue() : Align(); } | |||
135 | }; | |||
136 | ||||
137 | /// Checks that SizeInBytes is a multiple of the alignment. | |||
138 | inline bool isAligned(Align Lhs, uint64_t SizeInBytes) { | |||
139 | return SizeInBytes % Lhs.value() == 0; | |||
140 | } | |||
141 | ||||
142 | /// Checks that Addr is a multiple of the alignment. | |||
143 | inline bool isAddrAligned(Align Lhs, const void *Addr) { | |||
144 | return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr)); | |||
145 | } | |||
146 | ||||
147 | /// Returns a multiple of A needed to store `Size` bytes. | |||
148 | inline uint64_t alignTo(uint64_t Size, Align A) { | |||
149 | const uint64_t Value = A.value(); | |||
150 | // The following line is equivalent to `(Size + Value - 1) / Value * Value`. | |||
151 | ||||
152 | // The division followed by a multiplication can be thought of as a right | |||
153 | // shift followed by a left shift which zeros out the extra bits produced in | |||
154 | // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out | |||
155 | // are just zero. | |||
156 | ||||
157 | // Most compilers can generate this code but the pattern may be missed when | |||
158 | // multiple functions gets inlined. | |||
159 | return (Size + Value - 1) & ~(Value - 1U); | |||
160 | } | |||
161 | ||||
162 | /// If non-zero \p Skew is specified, the return value will be a minimal integer | |||
163 | /// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for | |||
164 | /// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p | |||
165 | /// Skew mod \p A'. | |||
166 | /// | |||
167 | /// Examples: | |||
168 | /// \code | |||
169 | /// alignTo(5, Align(8), 7) = 7 | |||
170 | /// alignTo(17, Align(8), 1) = 17 | |||
171 | /// alignTo(~0LL, Align(8), 3) = 3 | |||
172 | /// \endcode | |||
173 | inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) { | |||
174 | const uint64_t Value = A.value(); | |||
175 | Skew %= Value; | |||
176 | return ((Size + Value - 1 - Skew) & ~(Value - 1U)) + Skew; | |||
177 | } | |||
178 | ||||
179 | /// Returns a multiple of A needed to store `Size` bytes. | |||
180 | /// Returns `Size` if current alignment is undefined. | |||
181 | inline uint64_t alignTo(uint64_t Size, MaybeAlign A) { | |||
182 | return A ? alignTo(Size, A.getValue()) : Size; | |||
183 | } | |||
184 | ||||
185 | /// Aligns `Addr` to `Alignment` bytes, rounding up. | |||
186 | inline uintptr_t alignAddr(const void *Addr, Align Alignment) { | |||
187 | uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr); | |||
188 | assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=((void)0) | |||
189 | ArithAddr &&((void)0) | |||
190 | "Overflow")((void)0); | |||
191 | return alignTo(ArithAddr, Alignment); | |||
192 | } | |||
193 | ||||
194 | /// Returns the offset to the next integer (mod 2**64) that is greater than | |||
195 | /// or equal to \p Value and is a multiple of \p Align. | |||
196 | inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) { | |||
197 | return alignTo(Value, Alignment) - Value; | |||
198 | } | |||
199 | ||||
200 | /// Returns the necessary adjustment for aligning `Addr` to `Alignment` | |||
201 | /// bytes, rounding up. | |||
202 | inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) { | |||
203 | return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment); | |||
204 | } | |||
205 | ||||
206 | /// Returns the log2 of the alignment. | |||
207 | inline unsigned Log2(Align A) { return A.ShiftValue; } | |||
208 | ||||
209 | /// Returns the alignment that satisfies both alignments. | |||
210 | /// Same semantic as MinAlign. | |||
211 | inline Align commonAlignment(Align A, Align B) { return std::min(A, B); } | |||
212 | ||||
213 | /// Returns the alignment that satisfies both alignments. | |||
214 | /// Same semantic as MinAlign. | |||
215 | inline Align commonAlignment(Align A, uint64_t Offset) { | |||
216 | return Align(MinAlign(A.value(), Offset)); | |||
217 | } | |||
218 | ||||
219 | /// Returns the alignment that satisfies both alignments. | |||
220 | /// Same semantic as MinAlign. | |||
221 | inline MaybeAlign commonAlignment(MaybeAlign A, MaybeAlign B) { | |||
222 | return A && B ? commonAlignment(*A, *B) : A ? A : B; | |||
223 | } | |||
224 | ||||
225 | /// Returns the alignment that satisfies both alignments. | |||
226 | /// Same semantic as MinAlign. | |||
227 | inline MaybeAlign commonAlignment(MaybeAlign A, uint64_t Offset) { | |||
228 | return MaybeAlign(MinAlign((*A).value(), Offset)); | |||
229 | } | |||
230 | ||||
231 | /// Returns a representation of the alignment that encodes undefined as 0. | |||
232 | inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; } | |||
233 | ||||
234 | /// Dual operation of the encode function above. | |||
235 | inline MaybeAlign decodeMaybeAlign(unsigned Value) { | |||
236 | if (Value == 0) | |||
237 | return MaybeAlign(); | |||
238 | Align Out; | |||
239 | Out.ShiftValue = Value - 1; | |||
240 | return Out; | |||
241 | } | |||
242 | ||||
243 | /// Returns a representation of the alignment, the encoded value is positive by | |||
244 | /// definition. | |||
245 | inline unsigned encode(Align A) { return encode(MaybeAlign(A)); } | |||
246 | ||||
247 | /// Comparisons between Align and scalars. Rhs must be positive. | |||
248 | inline bool operator==(Align Lhs, uint64_t Rhs) { | |||
249 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
250 | return Lhs.value() == Rhs; | |||
251 | } | |||
252 | inline bool operator!=(Align Lhs, uint64_t Rhs) { | |||
253 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
254 | return Lhs.value() != Rhs; | |||
255 | } | |||
256 | inline bool operator<=(Align Lhs, uint64_t Rhs) { | |||
257 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
258 | return Lhs.value() <= Rhs; | |||
259 | } | |||
260 | inline bool operator>=(Align Lhs, uint64_t Rhs) { | |||
261 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
262 | return Lhs.value() >= Rhs; | |||
263 | } | |||
264 | inline bool operator<(Align Lhs, uint64_t Rhs) { | |||
265 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
266 | return Lhs.value() < Rhs; | |||
267 | } | |||
268 | inline bool operator>(Align Lhs, uint64_t Rhs) { | |||
269 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
270 | return Lhs.value() > Rhs; | |||
271 | } | |||
272 | ||||
273 | /// Comparisons between MaybeAlign and scalars. | |||
274 | inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) { | |||
275 | return Lhs ? (*Lhs).value() == Rhs : Rhs == 0; | |||
276 | } | |||
277 | inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) { | |||
278 | return Lhs ? (*Lhs).value() != Rhs : Rhs != 0; | |||
279 | } | |||
280 | ||||
281 | /// Comparisons operators between Align. | |||
282 | inline bool operator==(Align Lhs, Align Rhs) { | |||
283 | return Lhs.ShiftValue == Rhs.ShiftValue; | |||
284 | } | |||
285 | inline bool operator!=(Align Lhs, Align Rhs) { | |||
286 | return Lhs.ShiftValue != Rhs.ShiftValue; | |||
287 | } | |||
288 | inline bool operator<=(Align Lhs, Align Rhs) { | |||
289 | return Lhs.ShiftValue <= Rhs.ShiftValue; | |||
290 | } | |||
291 | inline bool operator>=(Align Lhs, Align Rhs) { | |||
292 | return Lhs.ShiftValue >= Rhs.ShiftValue; | |||
293 | } | |||
294 | inline bool operator<(Align Lhs, Align Rhs) { | |||
295 | return Lhs.ShiftValue < Rhs.ShiftValue; | |||
296 | } | |||
297 | inline bool operator>(Align Lhs, Align Rhs) { | |||
298 | return Lhs.ShiftValue > Rhs.ShiftValue; | |||
299 | } | |||
300 | ||||
301 | // Don't allow relational comparisons with MaybeAlign. | |||
302 | bool operator<=(Align Lhs, MaybeAlign Rhs) = delete; | |||
303 | bool operator>=(Align Lhs, MaybeAlign Rhs) = delete; | |||
304 | bool operator<(Align Lhs, MaybeAlign Rhs) = delete; | |||
305 | bool operator>(Align Lhs, MaybeAlign Rhs) = delete; | |||
306 | ||||
307 | bool operator<=(MaybeAlign Lhs, Align Rhs) = delete; | |||
308 | bool operator>=(MaybeAlign Lhs, Align Rhs) = delete; | |||
309 | bool operator<(MaybeAlign Lhs, Align Rhs) = delete; | |||
310 | bool operator>(MaybeAlign Lhs, Align Rhs) = delete; | |||
311 | ||||
312 | bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
313 | bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
314 | bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
315 | bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
316 | ||||
317 | inline Align operator*(Align Lhs, uint64_t Rhs) { | |||
318 | assert(Rhs > 0 && "Rhs must be positive")((void)0); | |||
319 | return Align(Lhs.value() * Rhs); | |||
320 | } | |||
321 | ||||
322 | inline MaybeAlign operator*(MaybeAlign Lhs, uint64_t Rhs) { | |||
323 | assert(Rhs > 0 && "Rhs must be positive")((void)0); | |||
324 | return Lhs ? Lhs.getValue() * Rhs : MaybeAlign(); | |||
325 | } | |||
326 | ||||
327 | inline Align operator/(Align Lhs, uint64_t Divisor) { | |||
328 | assert(llvm::isPowerOf2_64(Divisor) &&((void)0) | |||
329 | "Divisor must be positive and a power of 2")((void)0); | |||
330 | assert(Lhs != 1 && "Can't halve byte alignment")((void)0); | |||
331 | return Align(Lhs.value() / Divisor); | |||
332 | } | |||
333 | ||||
334 | inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) { | |||
335 | assert(llvm::isPowerOf2_64(Divisor) &&((void)0) | |||
336 | "Divisor must be positive and a power of 2")((void)0); | |||
337 | return Lhs ? Lhs.getValue() / Divisor : MaybeAlign(); | |||
338 | } | |||
339 | ||||
340 | inline Align max(MaybeAlign Lhs, Align Rhs) { | |||
341 | return Lhs && *Lhs > Rhs ? *Lhs : Rhs; | |||
342 | } | |||
343 | ||||
344 | inline Align max(Align Lhs, MaybeAlign Rhs) { | |||
345 | return Rhs && *Rhs > Lhs ? *Rhs : Lhs; | |||
346 | } | |||
347 | ||||
348 | #ifndef NDEBUG1 | |||
349 | // For usage in LLVM_DEBUG macros. | |||
350 | inline std::string DebugStr(const Align &A) { | |||
351 | return std::to_string(A.value()); | |||
352 | } | |||
353 | // For usage in LLVM_DEBUG macros. | |||
354 | inline std::string DebugStr(const MaybeAlign &MA) { | |||
355 | if (MA) | |||
356 | return std::to_string(MA->value()); | |||
357 | return "None"; | |||
358 | } | |||
359 | #endif // NDEBUG | |||
360 | ||||
361 | #undef ALIGN_CHECK_ISPOSITIVE | |||
362 | ||||
363 | } // namespace llvm | |||
364 | ||||
365 | #endif // LLVM_SUPPORT_ALIGNMENT_H_ |