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