lib/dfsan/dfsan.cc

   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
  29 using namespace __dfsan;
  30
  31 typedef atomic_uint16_t atomic_dfsan_label;
  32 static const dfsan_label kInitializingLabel = -1;
  33
  34 static const uptr kNumLabels = 1 << (sizeof(dfsan_label) * 8);
  35
  36 static atomic_dfsan_label __dfsan_last_label;
  37 static dfsan_label_info __dfsan_label_info[kNumLabels];
  38
  39 Flags __dfsan::flags_data;
  40
  41 SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_retval_tls;
  42 SANITIZER_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
  66 typedef atomic_dfsan_label dfsan_union_table_t[kNumLabels][kNumLabels];
  67
  68 static const uptr kShadowAddr = 0x10000;
  69 static const uptr kUnionTableAddr = 0x200000000000;
  70 static const uptr kUnusedAddr = kUnionTableAddr + sizeof(dfsan_union_table_t);
  71 static const uptr kAppAddr = 0x700000008000;
  72
  73 static 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).
  79 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
  80 dfsan_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
 124 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 125 dfsan_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
 135 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 136 void __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.
 145 extern "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.
 152 SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
 153 dfsan_union(dfsan_label l1, dfsan_label l2) {
 154   if (l1 == l2)
 155     return l1;
 156   return __dfsan_union(l1, l2);
 157 }
 158
 159 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 160 dfsan_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
 170 extern "C" SANITIZER_INTERFACE_ATTRIBUTE
 171 void __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
 176 SANITIZER_INTERFACE_ATTRIBUTE
 177 void dfsan_set_label(dfsan_label label, void *addr, uptr size) {
 178   __dfsan_set_label(label, addr, size);
 179 }
 180
 181 SANITIZER_INTERFACE_ATTRIBUTE
 182 void 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.
 191 extern "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
 198 SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
 199 dfsan_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
 205 SANITIZER_INTERFACE_ATTRIBUTE
 206 const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) {
 207   return &__dfsan_label_info[label];
 208 }
 209
 210 extern "C" SANITIZER_INTERFACE_ATTRIBUTE int
 211 dfsan_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
 222 extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_label
 223 dfsan_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
 233 extern "C" SANITIZER_INTERFACE_ATTRIBUTE uptr
 234 dfsan_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
 241 static 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
 252 extern "C" void dfsan_init() {
 253 #else
 254 static 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))
 274 static void (*dfsan_init_ptr)(int, char **, char **) = dfsan_init;
 275 #endif