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_libc.h"
26
27#include "dfsan/dfsan.h"
28
29using namespace __dfsan;
30
31typedef atomic_uint16_t atomic_dfsan_label;
32static const dfsan_label kInitializingLabel = -1;
33
34static const uptr kNumLabels = 1 << (sizeof(dfsan_label) * 8);
35
36static atomic_dfsan_label __dfsan_last_label;
37static dfsan_label_info __dfsan_label_info[kNumLabels];
38
39Flags __dfsan::flags_data;
40
41SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_retval_tls;
42SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_arg_tls[64];
43
44// On Linux/x86_64, memory is laid out as follows:
45//
46// +--------------------+ 0x800000000000 (top of memory)
47// | application memory |
48// +--------------------+ 0x700000008000 (kAppAddr)
49// |                    |
50// |       unused       |
51// |                    |
52// +--------------------+ 0x200200000000 (kUnusedAddr)
53// |    union table     |
54// +--------------------+ 0x200000000000 (kUnionTableAddr)
55// |   shadow memory    |
56// +--------------------+ 0x000000010000 (kShadowAddr)
57// | reserved by kernel |
58// +--------------------+ 0x000000000000
59//
60// To derive a shadow memory address from an application memory address,
61// bits 44-46 are cleared to bring the address into the range
62// [0x000000008000,0x100000000000).  Then the address is shifted left by 1 to
63// account for the double byte representation of shadow labels and move the
64// address into the shadow memory range.  See the function shadow_for below.
65
66typedef atomic_dfsan_label dfsan_union_table_t[kNumLabels][kNumLabels];
67
68static const uptr kShadowAddr = 0x10000;
69static const uptr kUnionTableAddr = 0x200000000000;
70static const uptr kUnusedAddr = kUnionTableAddr + sizeof(dfsan_union_table_t);
71static const uptr kAppAddr = 0x700000008000;
72
73static atomic_dfsan_label *union_table(dfsan_label l1, dfsan_label l2) {
74  return &(*(dfsan_union_table_t *) kUnionTableAddr)[l1][l2];
75}
76
77// Resolves the union of two unequal labels.  Nonequality is a precondition for
78// this function (the instrumentation pass inlines the equality test).
79extern "C" SANITIZER_INTERFACE_ATTRIBUTE
80dfsan_label __dfsan_union(dfsan_label l1, dfsan_label l2) {
81  DCHECK_NE(l1, l2);
82
83  if (l1 == 0)
84    return l2;
85  if (l2 == 0)
86    return l1;
87
88  if (l1 > l2)
89    Swap(l1, l2);
90
91  atomic_dfsan_label *table_ent = union_table(l1, l2);
92  // We need to deal with the case where two threads concurrently request
93  // a union of the same pair of labels.  If the table entry is uninitialized,
94  // (i.e. 0) use a compare-exchange to set the entry to kInitializingLabel
95  // (i.e. -1) to mark that we are initializing it.
96  dfsan_label label = 0;
97  if (atomic_compare_exchange_strong(table_ent, &label, kInitializingLabel,
98                                     memory_order_acquire)) {
99    // Check whether l2 subsumes l1.  We don't need to check whether l1
100    // subsumes l2 because we are guaranteed here that l1 < l2, and (at least
101    // in the cases we are interested in) a label may only subsume labels
102    // created earlier (i.e. with a lower numerical value).
103    if (__dfsan_label_info[l2].l1 == l1 ||
104        __dfsan_label_info[l2].l2 == l1) {
105      label = l2;
106    } else {
107      label =
108        atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1;
109      CHECK_NE(label, kInitializingLabel);
110      __dfsan_label_info[label].l1 = l1;
111      __dfsan_label_info[label].l2 = l2;
112    }
113    atomic_store(table_ent, label, memory_order_release);
114  } else if (label == kInitializingLabel) {
115    // Another thread is initializing the entry.  Wait until it is finished.
116    do {
117      internal_sched_yield();
118      label = atomic_load(table_ent, memory_order_acquire);
119    } while (label == kInitializingLabel);
120  }
121  return label;
122}
123
124extern "C" SANITIZER_INTERFACE_ATTRIBUTE
125dfsan_label __dfsan_union_load(const dfsan_label *ls, uptr n) {
126  dfsan_label label = ls[0];
127  for (uptr i = 1; i != n; ++i) {
128    dfsan_label next_label = ls[i];
129    if (label != next_label)
130      label = __dfsan_union(label, next_label);
131  }
132  return label;
133}
134
135extern "C" SANITIZER_INTERFACE_ATTRIBUTE
136void __dfsan_unimplemented(char *fname) {
137  if (flags().warn_unimplemented)
138    Report("WARNING: DataFlowSanitizer: call to uninstrumented function %s\n",
139           fname);
140}
141
142// Use '-mllvm -dfsan-debug-nonzero-labels' and break on this function
143// to try to figure out where labels are being introduced in a nominally
144// label-free program.
145extern "C" SANITIZER_INTERFACE_ATTRIBUTE void __dfsan_nonzero_label() {
146  if (flags().warn_nonzero_labels)
147    Report("WARNING: DataFlowSanitizer: saw nonzero label\n");
148}
149
150// Like __dfsan_union, but for use from the client or custom functions.  Hence
151// the equality comparison is done here before calling __dfsan_union.
152SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
153dfsan_union(dfsan_label l1, dfsan_label l2) {
154  if (l1 == l2)
155    return l1;
156  return __dfsan_union(l1, l2);
157}
158
159extern "C" SANITIZER_INTERFACE_ATTRIBUTE
160dfsan_label dfsan_create_label(const char *desc, void *userdata) {
161  dfsan_label label =
162    atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1;
163  CHECK_NE(label, kInitializingLabel);
164  __dfsan_label_info[label].l1 = __dfsan_label_info[label].l2 = 0;
165  __dfsan_label_info[label].desc = desc;
166  __dfsan_label_info[label].userdata = userdata;
167  return label;
168}
169
170extern "C" SANITIZER_INTERFACE_ATTRIBUTE
171void __dfsan_set_label(dfsan_label label, void *addr, uptr size) {
172  for (dfsan_label *labelp = shadow_for(addr); size != 0; --size, ++labelp)
173    *labelp = label;
174}
175
176SANITIZER_INTERFACE_ATTRIBUTE
177void dfsan_set_label(dfsan_label label, void *addr, uptr size) {
178  __dfsan_set_label(label, addr, size);
179}
180
181SANITIZER_INTERFACE_ATTRIBUTE
182void dfsan_add_label(dfsan_label label, void *addr, uptr size) {
183  for (dfsan_label *labelp = shadow_for(addr); size != 0; --size, ++labelp)
184    if (*labelp != label)
185      *labelp = __dfsan_union(*labelp, label);
186}
187
188// Unlike the other dfsan interface functions the behavior of this function
189// depends on the label of one of its arguments.  Hence it is implemented as a
190// custom function.
191extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
192__dfsw_dfsan_get_label(long data, dfsan_label data_label,
193                       dfsan_label *ret_label) {
194  *ret_label = 0;
195  return data_label;
196}
197
198SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
199dfsan_read_label(const void *addr, uptr size) {
200  if (size == 0)
201    return 0;
202  return __dfsan_union_load(shadow_for(addr), size);
203}
204
205SANITIZER_INTERFACE_ATTRIBUTE
206const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) {
207  return &__dfsan_label_info[label];
208}
209
210extern "C" SANITIZER_INTERFACE_ATTRIBUTE int
211dfsan_has_label(dfsan_label label, dfsan_label elem) {
212  if (label == elem)
213    return true;
214  const dfsan_label_info *info = dfsan_get_label_info(label);
215  if (info->l1 != 0) {
216    return dfsan_has_label(info->l1, elem) || dfsan_has_label(info->l2, elem);
217  } else {
218    return false;
219  }
220}
221
222extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
223dfsan_has_label_with_desc(dfsan_label label, const char *desc) {
224  const dfsan_label_info *info = dfsan_get_label_info(label);
225  if (info->l1 != 0) {
226    return dfsan_has_label_with_desc(info->l1, desc) ||
227           dfsan_has_label_with_desc(info->l2, desc);
228  } else {
229    return internal_strcmp(desc, info->desc) == 0;
230  }
231}
232
233extern "C" SANITIZER_INTERFACE_ATTRIBUTE uptr
234dfsan_get_label_count(void) {
235  dfsan_label max_label_allocated =
236      atomic_load(&__dfsan_last_label, memory_order_relaxed);
237
238  return static_cast<uptr>(max_label_allocated);
239}
240
241static void InitializeFlags(Flags &f, const char *env) {
242  f.warn_unimplemented = true;
243  f.warn_nonzero_labels = false;
244  f.strict_data_dependencies = true;
245
246  ParseFlag(env, &f.warn_unimplemented, "warn_unimplemented", "");
247  ParseFlag(env, &f.warn_nonzero_labels, "warn_nonzero_labels", "");
248  ParseFlag(env, &f.strict_data_dependencies, "strict_data_dependencies", "");
249}
250
251#ifdef DFSAN_NOLIBC
252extern "C" void dfsan_init() {
253#else
254static void dfsan_init(int argc, char **argv, char **envp) {
255#endif
256  MmapFixedNoReserve(kShadowAddr, kUnusedAddr - kShadowAddr);
257
258  // Protect the region of memory we don't use, to preserve the one-to-one
259  // mapping from application to shadow memory. But if ASLR is disabled, Linux
260  // will load our executable in the middle of our unused region. This mostly
261  // works so long as the program doesn't use too much memory. We support this
262  // case by disabling memory protection when ASLR is disabled.
263  uptr init_addr = (uptr)&dfsan_init;
264  if (!(init_addr >= kUnusedAddr && init_addr < kAppAddr))
265    Mprotect(kUnusedAddr, kAppAddr - kUnusedAddr);
266
267  InitializeFlags(flags(), GetEnv("DFSAN_OPTIONS"));
268
269  InitializeInterceptors();
270}
271
272#ifndef DFSAN_NOLIBC
273__attribute__((section(".preinit_array"), used))
274static void (*dfsan_init_ptr)(int, char **, char **) = dfsan_init;
275#endif
276