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