• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- dfsan.cc ----------------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file is a part of DataFlowSanitizer.
11 //
12 // DataFlowSanitizer runtime.  This file defines the public interface to
13 // DataFlowSanitizer as well as the definition of certain runtime functions
14 // called automatically by the compiler (specifically the instrumentation pass
15 // in llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp).
16 //
17 // The public interface is defined in include/sanitizer/dfsan_interface.h whose
18 // functions are prefixed dfsan_ while the compiler interface functions are
19 // prefixed __dfsan_.
20 //===----------------------------------------------------------------------===//
21 
22 #include "sanitizer_common/sanitizer_atomic.h"
23 #include "sanitizer_common/sanitizer_common.h"
24 #include "sanitizer_common/sanitizer_flags.h"
25 #include "sanitizer_common/sanitizer_flag_parser.h"
26 #include "sanitizer_common/sanitizer_libc.h"
27 
28 #include "dfsan/dfsan.h"
29 
30 using namespace __dfsan;
31 
32 typedef atomic_uint16_t atomic_dfsan_label;
33 static const dfsan_label kInitializingLabel = -1;
34 
35 static const uptr kNumLabels = 1 << (sizeof(dfsan_label) * 8);
36 
37 static atomic_dfsan_label __dfsan_last_label;
38 static dfsan_label_info __dfsan_label_info[kNumLabels];
39 
40 Flags __dfsan::flags_data;
41 
42 SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_retval_tls;
43 SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_arg_tls[64];
44 
45 SANITIZER_INTERFACE_ATTRIBUTE uptr __dfsan_shadow_ptr_mask;
46 
47 // On Linux/x86_64, memory is laid out as follows:
48 //
49 // +--------------------+ 0x800000000000 (top of memory)
50 // | application memory |
51 // +--------------------+ 0x700000008000 (kAppAddr)
52 // |                    |
53 // |       unused       |
54 // |                    |
55 // +--------------------+ 0x200200000000 (kUnusedAddr)
56 // |    union table     |
57 // +--------------------+ 0x200000000000 (kUnionTableAddr)
58 // |   shadow memory    |
59 // +--------------------+ 0x000000010000 (kShadowAddr)
60 // | reserved by kernel |
61 // +--------------------+ 0x000000000000
62 //
63 // To derive a shadow memory address from an application memory address,
64 // bits 44-46 are cleared to bring the address into the range
65 // [0x000000008000,0x100000000000).  Then the address is shifted left by 1 to
66 // account for the double byte representation of shadow labels and move the
67 // address into the shadow memory range.  See the function shadow_for below.
68 
69 // On Linux/MIPS64, memory is laid out as follows:
70 //
71 // +--------------------+ 0x10000000000 (top of memory)
72 // | application memory |
73 // +--------------------+ 0xF000008000 (kAppAddr)
74 // |                    |
75 // |       unused       |
76 // |                    |
77 // +--------------------+ 0x2200000000 (kUnusedAddr)
78 // |    union table     |
79 // +--------------------+ 0x2000000000 (kUnionTableAddr)
80 // |   shadow memory    |
81 // +--------------------+ 0x0000010000 (kShadowAddr)
82 // | reserved by kernel |
83 // +--------------------+ 0x0000000000
84 
85 // On Linux/AArch64 (39-bit VMA), memory is laid out as follow:
86 //
87 // +--------------------+ 0x8000000000 (top of memory)
88 // | application memory |
89 // +--------------------+ 0x7000008000 (kAppAddr)
90 // |                    |
91 // |       unused       |
92 // |                    |
93 // +--------------------+ 0x1200000000 (kUnusedAddr)
94 // |    union table     |
95 // +--------------------+ 0x1000000000 (kUnionTableAddr)
96 // |   shadow memory    |
97 // +--------------------+ 0x0000010000 (kShadowAddr)
98 // | reserved by kernel |
99 // +--------------------+ 0x0000000000
100 
101 // On Linux/AArch64 (42-bit VMA), memory is laid out as follow:
102 //
103 // +--------------------+ 0x40000000000 (top of memory)
104 // | application memory |
105 // +--------------------+ 0x3ff00008000 (kAppAddr)
106 // |                    |
107 // |       unused       |
108 // |                    |
109 // +--------------------+ 0x1200000000 (kUnusedAddr)
110 // |    union table     |
111 // +--------------------+ 0x8000000000 (kUnionTableAddr)
112 // |   shadow memory    |
113 // +--------------------+ 0x0000010000 (kShadowAddr)
114 // | reserved by kernel |
115 // +--------------------+ 0x0000000000
116 
117 typedef atomic_dfsan_label dfsan_union_table_t[kNumLabels][kNumLabels];
118 
119 #ifdef DFSAN_RUNTIME_VMA
120 // Runtime detected VMA size.
121 int __dfsan::vmaSize;
122 #endif
123 
UnusedAddr()124 static uptr UnusedAddr() {
125   return MappingArchImpl<MAPPING_UNION_TABLE_ADDR>()
126          + sizeof(dfsan_union_table_t);
127 }
128 
union_table(dfsan_label l1,dfsan_label l2)129 static atomic_dfsan_label *union_table(dfsan_label l1, dfsan_label l2) {
130   return &(*(dfsan_union_table_t *) UnionTableAddr())[l1][l2];
131 }
132 
133 // Checks we do not run out of labels.
dfsan_check_label(dfsan_label label)134 static void dfsan_check_label(dfsan_label label) {
135   if (label == kInitializingLabel) {
136     Report("FATAL: DataFlowSanitizer: out of labels\n");
137     Die();
138   }
139 }
140 
141 // Resolves the union of two unequal labels.  Nonequality is a precondition for
142 // this function (the instrumentation pass inlines the equality test).
143 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
__dfsan_union(dfsan_label l1,dfsan_label l2)144 dfsan_label __dfsan_union(dfsan_label l1, dfsan_label l2) {
145   DCHECK_NE(l1, l2);
146 
147   if (l1 == 0)
148     return l2;
149   if (l2 == 0)
150     return l1;
151 
152   if (l1 > l2)
153     Swap(l1, l2);
154 
155   atomic_dfsan_label *table_ent = union_table(l1, l2);
156   // We need to deal with the case where two threads concurrently request
157   // a union of the same pair of labels.  If the table entry is uninitialized,
158   // (i.e. 0) use a compare-exchange to set the entry to kInitializingLabel
159   // (i.e. -1) to mark that we are initializing it.
160   dfsan_label label = 0;
161   if (atomic_compare_exchange_strong(table_ent, &label, kInitializingLabel,
162                                      memory_order_acquire)) {
163     // Check whether l2 subsumes l1.  We don't need to check whether l1
164     // subsumes l2 because we are guaranteed here that l1 < l2, and (at least
165     // in the cases we are interested in) a label may only subsume labels
166     // created earlier (i.e. with a lower numerical value).
167     if (__dfsan_label_info[l2].l1 == l1 ||
168         __dfsan_label_info[l2].l2 == l1) {
169       label = l2;
170     } else {
171       label =
172         atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1;
173       dfsan_check_label(label);
174       __dfsan_label_info[label].l1 = l1;
175       __dfsan_label_info[label].l2 = l2;
176     }
177     atomic_store(table_ent, label, memory_order_release);
178   } else if (label == kInitializingLabel) {
179     // Another thread is initializing the entry.  Wait until it is finished.
180     do {
181       internal_sched_yield();
182       label = atomic_load(table_ent, memory_order_acquire);
183     } while (label == kInitializingLabel);
184   }
185   return label;
186 }
187 
188 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
__dfsan_union_load(const dfsan_label * ls,uptr n)189 dfsan_label __dfsan_union_load(const dfsan_label *ls, uptr n) {
190   dfsan_label label = ls[0];
191   for (uptr i = 1; i != n; ++i) {
192     dfsan_label next_label = ls[i];
193     if (label != next_label)
194       label = __dfsan_union(label, next_label);
195   }
196   return label;
197 }
198 
199 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
__dfsan_unimplemented(char * fname)200 void __dfsan_unimplemented(char *fname) {
201   if (flags().warn_unimplemented)
202     Report("WARNING: DataFlowSanitizer: call to uninstrumented function %s\n",
203            fname);
204 }
205 
206 // Use '-mllvm -dfsan-debug-nonzero-labels' and break on this function
207 // to try to figure out where labels are being introduced in a nominally
208 // label-free program.
__dfsan_nonzero_label()209 extern "C" SANITIZER_INTERFACE_ATTRIBUTE void __dfsan_nonzero_label() {
210   if (flags().warn_nonzero_labels)
211     Report("WARNING: DataFlowSanitizer: saw nonzero label\n");
212 }
213 
214 // Indirect call to an uninstrumented vararg function. We don't have a way of
215 // handling these at the moment.
216 extern "C" SANITIZER_INTERFACE_ATTRIBUTE void
__dfsan_vararg_wrapper(const char * fname)217 __dfsan_vararg_wrapper(const char *fname) {
218   Report("FATAL: DataFlowSanitizer: unsupported indirect call to vararg "
219          "function %s\n", fname);
220   Die();
221 }
222 
223 // Like __dfsan_union, but for use from the client or custom functions.  Hence
224 // the equality comparison is done here before calling __dfsan_union.
225 SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
dfsan_union(dfsan_label l1,dfsan_label l2)226 dfsan_union(dfsan_label l1, dfsan_label l2) {
227   if (l1 == l2)
228     return l1;
229   return __dfsan_union(l1, l2);
230 }
231 
232 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
dfsan_create_label(const char * desc,void * userdata)233 dfsan_label dfsan_create_label(const char *desc, void *userdata) {
234   dfsan_label label =
235     atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1;
236   dfsan_check_label(label);
237   __dfsan_label_info[label].l1 = __dfsan_label_info[label].l2 = 0;
238   __dfsan_label_info[label].desc = desc;
239   __dfsan_label_info[label].userdata = userdata;
240   return label;
241 }
242 
243 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
__dfsan_set_label(dfsan_label label,void * addr,uptr size)244 void __dfsan_set_label(dfsan_label label, void *addr, uptr size) {
245   for (dfsan_label *labelp = shadow_for(addr); size != 0; --size, ++labelp) {
246     // Don't write the label if it is already the value we need it to be.
247     // In a program where most addresses are not labeled, it is common that
248     // a page of shadow memory is entirely zeroed.  The Linux copy-on-write
249     // implementation will share all of the zeroed pages, making a copy of a
250     // page when any value is written.  The un-sharing will happen even if
251     // the value written does not change the value in memory.  Avoiding the
252     // write when both |label| and |*labelp| are zero dramatically reduces
253     // the amount of real memory used by large programs.
254     if (label == *labelp)
255       continue;
256 
257     *labelp = label;
258   }
259 }
260 
261 SANITIZER_INTERFACE_ATTRIBUTE
dfsan_set_label(dfsan_label label,void * addr,uptr size)262 void dfsan_set_label(dfsan_label label, void *addr, uptr size) {
263   __dfsan_set_label(label, addr, size);
264 }
265 
266 SANITIZER_INTERFACE_ATTRIBUTE
dfsan_add_label(dfsan_label label,void * addr,uptr size)267 void dfsan_add_label(dfsan_label label, void *addr, uptr size) {
268   for (dfsan_label *labelp = shadow_for(addr); size != 0; --size, ++labelp)
269     if (*labelp != label)
270       *labelp = __dfsan_union(*labelp, label);
271 }
272 
273 // Unlike the other dfsan interface functions the behavior of this function
274 // depends on the label of one of its arguments.  Hence it is implemented as a
275 // custom function.
276 extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
__dfsw_dfsan_get_label(long data,dfsan_label data_label,dfsan_label * ret_label)277 __dfsw_dfsan_get_label(long data, dfsan_label data_label,
278                        dfsan_label *ret_label) {
279   *ret_label = 0;
280   return data_label;
281 }
282 
283 SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
dfsan_read_label(const void * addr,uptr size)284 dfsan_read_label(const void *addr, uptr size) {
285   if (size == 0)
286     return 0;
287   return __dfsan_union_load(shadow_for(addr), size);
288 }
289 
290 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
dfsan_get_label_info(dfsan_label label)291 const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) {
292   return &__dfsan_label_info[label];
293 }
294 
295 extern "C" SANITIZER_INTERFACE_ATTRIBUTE int
dfsan_has_label(dfsan_label label,dfsan_label elem)296 dfsan_has_label(dfsan_label label, dfsan_label elem) {
297   if (label == elem)
298     return true;
299   const dfsan_label_info *info = dfsan_get_label_info(label);
300   if (info->l1 != 0) {
301     return dfsan_has_label(info->l1, elem) || dfsan_has_label(info->l2, elem);
302   } else {
303     return false;
304   }
305 }
306 
307 extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
dfsan_has_label_with_desc(dfsan_label label,const char * desc)308 dfsan_has_label_with_desc(dfsan_label label, const char *desc) {
309   const dfsan_label_info *info = dfsan_get_label_info(label);
310   if (info->l1 != 0) {
311     return dfsan_has_label_with_desc(info->l1, desc) ||
312            dfsan_has_label_with_desc(info->l2, desc);
313   } else {
314     return internal_strcmp(desc, info->desc) == 0;
315   }
316 }
317 
318 extern "C" SANITIZER_INTERFACE_ATTRIBUTE uptr
dfsan_get_label_count(void)319 dfsan_get_label_count(void) {
320   dfsan_label max_label_allocated =
321       atomic_load(&__dfsan_last_label, memory_order_relaxed);
322 
323   return static_cast<uptr>(max_label_allocated);
324 }
325 
326 extern "C" SANITIZER_INTERFACE_ATTRIBUTE void
dfsan_dump_labels(int fd)327 dfsan_dump_labels(int fd) {
328   dfsan_label last_label =
329       atomic_load(&__dfsan_last_label, memory_order_relaxed);
330 
331   for (uptr l = 1; l <= last_label; ++l) {
332     char buf[64];
333     internal_snprintf(buf, sizeof(buf), "%u %u %u ", l,
334                       __dfsan_label_info[l].l1, __dfsan_label_info[l].l2);
335     WriteToFile(fd, buf, internal_strlen(buf));
336     if (__dfsan_label_info[l].l1 == 0 && __dfsan_label_info[l].desc) {
337       WriteToFile(fd, __dfsan_label_info[l].desc,
338                   internal_strlen(__dfsan_label_info[l].desc));
339     }
340     WriteToFile(fd, "\n", 1);
341   }
342 }
343 
SetDefaults()344 void Flags::SetDefaults() {
345 #define DFSAN_FLAG(Type, Name, DefaultValue, Description) Name = DefaultValue;
346 #include "dfsan_flags.inc"
347 #undef DFSAN_FLAG
348 }
349 
RegisterDfsanFlags(FlagParser * parser,Flags * f)350 static void RegisterDfsanFlags(FlagParser *parser, Flags *f) {
351 #define DFSAN_FLAG(Type, Name, DefaultValue, Description) \
352   RegisterFlag(parser, #Name, Description, &f->Name);
353 #include "dfsan_flags.inc"
354 #undef DFSAN_FLAG
355 }
356 
InitializeFlags()357 static void InitializeFlags() {
358   SetCommonFlagsDefaults();
359   flags().SetDefaults();
360 
361   FlagParser parser;
362   RegisterCommonFlags(&parser);
363   RegisterDfsanFlags(&parser, &flags());
364   parser.ParseString(GetEnv("DFSAN_OPTIONS"));
365   InitializeCommonFlags();
366   if (Verbosity()) ReportUnrecognizedFlags();
367   if (common_flags()->help) parser.PrintFlagDescriptions();
368 }
369 
InitializePlatformEarly()370 static void InitializePlatformEarly() {
371   AvoidCVE_2016_2143();
372 #ifdef DFSAN_RUNTIME_VMA
373   __dfsan::vmaSize =
374     (MostSignificantSetBitIndex(GET_CURRENT_FRAME()) + 1);
375   if (__dfsan::vmaSize == 39 || __dfsan::vmaSize == 42) {
376     __dfsan_shadow_ptr_mask = ShadowMask();
377   } else {
378     Printf("FATAL: DataFlowSanitizer: unsupported VMA range\n");
379     Printf("FATAL: Found %d - Supported 39 and 42\n", __dfsan::vmaSize);
380     Die();
381   }
382 #endif
383 }
384 
dfsan_fini()385 static void dfsan_fini() {
386   if (internal_strcmp(flags().dump_labels_at_exit, "") != 0) {
387     fd_t fd = OpenFile(flags().dump_labels_at_exit, WrOnly);
388     if (fd == kInvalidFd) {
389       Report("WARNING: DataFlowSanitizer: unable to open output file %s\n",
390              flags().dump_labels_at_exit);
391       return;
392     }
393 
394     Report("INFO: DataFlowSanitizer: dumping labels to %s\n",
395            flags().dump_labels_at_exit);
396     dfsan_dump_labels(fd);
397     CloseFile(fd);
398   }
399 }
400 
dfsan_init(int argc,char ** argv,char ** envp)401 static void dfsan_init(int argc, char **argv, char **envp) {
402   InitializeFlags();
403 
404   InitializePlatformEarly();
405 
406   MmapFixedNoReserve(ShadowAddr(), UnusedAddr() - ShadowAddr());
407 
408   // Protect the region of memory we don't use, to preserve the one-to-one
409   // mapping from application to shadow memory. But if ASLR is disabled, Linux
410   // will load our executable in the middle of our unused region. This mostly
411   // works so long as the program doesn't use too much memory. We support this
412   // case by disabling memory protection when ASLR is disabled.
413   uptr init_addr = (uptr)&dfsan_init;
414   if (!(init_addr >= UnusedAddr() && init_addr < AppAddr()))
415     MmapFixedNoAccess(UnusedAddr(), AppAddr() - UnusedAddr());
416 
417   InitializeInterceptors();
418 
419   // Register the fini callback to run when the program terminates successfully
420   // or it is killed by the runtime.
421   Atexit(dfsan_fini);
422   AddDieCallback(dfsan_fini);
423 
424   __dfsan_label_info[kInitializingLabel].desc = "<init label>";
425 }
426 
427 #if SANITIZER_CAN_USE_PREINIT_ARRAY
428 __attribute__((section(".preinit_array"), used))
429 static void (*dfsan_init_ptr)(int, char **, char **) = dfsan_init;
430 #endif
431