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 30using namespace __dfsan; 31 32typedef atomic_uint16_t atomic_dfsan_label; 33static const dfsan_label kInitializingLabel = -1; 34 35static const uptr kNumLabels = 1 << (sizeof(dfsan_label) * 8); 36 37static atomic_dfsan_label __dfsan_last_label; 38static dfsan_label_info __dfsan_label_info[kNumLabels]; 39 40Flags __dfsan::flags_data; 41 42SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_retval_tls; 43SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_arg_tls[64]; 44 45SANITIZER_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 117typedef atomic_dfsan_label dfsan_union_table_t[kNumLabels][kNumLabels]; 118 119#ifdef DFSAN_RUNTIME_VMA 120// Runtime detected VMA size. 121int __dfsan::vmaSize; 122#endif 123 124static uptr UnusedAddr() { 125 return MappingArchImpl<MAPPING_UNION_TABLE_ADDR>() 126 + sizeof(dfsan_union_table_t); 127} 128 129static 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. 134static 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). 143extern "C" SANITIZER_INTERFACE_ATTRIBUTE 144dfsan_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 188extern "C" SANITIZER_INTERFACE_ATTRIBUTE 189dfsan_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 199extern "C" SANITIZER_INTERFACE_ATTRIBUTE 200void __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. 209extern "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. 216extern "C" SANITIZER_INTERFACE_ATTRIBUTE void 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. 225SANITIZER_INTERFACE_ATTRIBUTE dfsan_label 226dfsan_union(dfsan_label l1, dfsan_label l2) { 227 if (l1 == l2) 228 return l1; 229 return __dfsan_union(l1, l2); 230} 231 232extern "C" SANITIZER_INTERFACE_ATTRIBUTE 233dfsan_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 243extern "C" SANITIZER_INTERFACE_ATTRIBUTE 244void __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 261SANITIZER_INTERFACE_ATTRIBUTE 262void dfsan_set_label(dfsan_label label, void *addr, uptr size) { 263 __dfsan_set_label(label, addr, size); 264} 265 266SANITIZER_INTERFACE_ATTRIBUTE 267void 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. 276extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_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 283SANITIZER_INTERFACE_ATTRIBUTE dfsan_label 284dfsan_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 290extern "C" SANITIZER_INTERFACE_ATTRIBUTE 291const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) { 292 return &__dfsan_label_info[label]; 293} 294 295extern "C" SANITIZER_INTERFACE_ATTRIBUTE int 296dfsan_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 307extern "C" SANITIZER_INTERFACE_ATTRIBUTE dfsan_label 308dfsan_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 318extern "C" SANITIZER_INTERFACE_ATTRIBUTE uptr 319dfsan_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 326extern "C" SANITIZER_INTERFACE_ATTRIBUTE void 327dfsan_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 344void Flags::SetDefaults() { 345#define DFSAN_FLAG(Type, Name, DefaultValue, Description) Name = DefaultValue; 346#include "dfsan_flags.inc" 347#undef DFSAN_FLAG 348} 349 350static 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 357static 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 370static 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 385static 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 401static 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)) 429static void (*dfsan_init_ptr)(int, char **, char **) = dfsan_init; 430#endif 431