dfsan.cc revision eee71ae5c1f4ce71612fac359463a54bc867abd6
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/dfsan_interface.h" 23#include "sanitizer_common/sanitizer_atomic.h" 24#include "sanitizer_common/sanitizer_common.h" 25#include "sanitizer_common/sanitizer_libc.h" 26 27typedef atomic_uint16_t atomic_dfsan_label; 28static const dfsan_label kInitializingLabel = -1; 29 30static const uptr kNumLabels = 1 << (sizeof(dfsan_label) * 8); 31 32static atomic_dfsan_label __dfsan_last_label; 33static dfsan_label_info __dfsan_label_info[kNumLabels]; 34 35SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_retval_tls; 36SANITIZER_INTERFACE_ATTRIBUTE THREADLOCAL dfsan_label __dfsan_arg_tls[64]; 37 38// On Linux/x86_64, memory is laid out as follows: 39// 40// +--------------------+ 0x800000000000 (top of memory) 41// | application memory | 42// +--------------------+ 0x700000008000 (kAppAddr) 43// | | 44// | unused | 45// | | 46// +--------------------+ 0x200200000000 (kUnusedAddr) 47// | union table | 48// +--------------------+ 0x200000000000 (kUnionTableAddr) 49// | shadow memory | 50// +--------------------+ 0x000000010000 (kShadowAddr) 51// | reserved by kernel | 52// +--------------------+ 0x000000000000 53// 54// To derive a shadow memory address from an application memory address, 55// bits 44-46 are cleared to bring the address into the range 56// [0x000000008000,0x100000000000). Then the address is shifted left by 1 to 57// account for the double byte representation of shadow labels and move the 58// address into the shadow memory range. See the function shadow_for below. 59 60typedef atomic_dfsan_label dfsan_union_table_t[kNumLabels][kNumLabels]; 61 62static const uptr kShadowAddr = 0x10000; 63static const uptr kUnionTableAddr = 0x200000000000; 64static const uptr kUnusedAddr = kUnionTableAddr + sizeof(dfsan_union_table_t); 65static const uptr kAppAddr = 0x700000008000; 66 67static atomic_dfsan_label *union_table(dfsan_label l1, dfsan_label l2) { 68 return &(*(dfsan_union_table_t *) kUnionTableAddr)[l1][l2]; 69} 70 71static dfsan_label *shadow_for(void *ptr) { 72 return (dfsan_label *) ((((uintptr_t) ptr) & ~0x700000000000) << 1); 73} 74 75// Resolves the union of two unequal labels. Nonequality is a precondition for 76// this function (the instrumentation pass inlines the equality test). 77extern "C" SANITIZER_INTERFACE_ATTRIBUTE 78dfsan_label __dfsan_union(dfsan_label l1, dfsan_label l2) { 79 DCHECK_NE(l1, l2); 80 81 if (l1 == 0) 82 return l2; 83 if (l2 == 0) 84 return l1; 85 86 if (l1 > l2) 87 Swap(l1, l2); 88 89 atomic_dfsan_label *table_ent = union_table(l1, l2); 90 // We need to deal with the case where two threads concurrently request 91 // a union of the same pair of labels. If the table entry is uninitialized, 92 // (i.e. 0) use a compare-exchange to set the entry to kInitializingLabel 93 // (i.e. -1) to mark that we are initializing it. 94 dfsan_label label = 0; 95 if (atomic_compare_exchange_strong(table_ent, &label, kInitializingLabel, 96 memory_order_acquire)) { 97 // Check whether l2 subsumes l1. We don't need to check whether l1 98 // subsumes l2 because we are guaranteed here that l1 < l2, and (at least 99 // in the cases we are interested in) a label may only subsume labels 100 // created earlier (i.e. with a lower numerical value). 101 if (__dfsan_label_info[l2].l1 == l1 || 102 __dfsan_label_info[l2].l2 == l1) { 103 label = l2; 104 } else { 105 label = 106 atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1; 107 CHECK_NE(label, kInitializingLabel); 108 __dfsan_label_info[label].l1 = l1; 109 __dfsan_label_info[label].l2 = l2; 110 } 111 atomic_store(table_ent, label, memory_order_release); 112 } else if (label == kInitializingLabel) { 113 // Another thread is initializing the entry. Wait until it is finished. 114 do { 115 internal_sched_yield(); 116 label = atomic_load(table_ent, memory_order_acquire); 117 } while (label == kInitializingLabel); 118 } 119 return label; 120} 121 122extern "C" SANITIZER_INTERFACE_ATTRIBUTE 123dfsan_label __dfsan_union_load(dfsan_label *ls, size_t n) { 124 dfsan_label label = ls[0]; 125 for (size_t i = 1; i != n; ++i) { 126 dfsan_label next_label = ls[i]; 127 if (label != next_label) 128 label = __dfsan_union(label, next_label); 129 } 130 return label; 131} 132 133extern "C" SANITIZER_INTERFACE_ATTRIBUTE 134void *__dfsan_memcpy(void *dest, const void *src, size_t n) { 135 dfsan_label *sdest = shadow_for(dest), *ssrc = shadow_for((void *)src); 136 internal_memcpy((void *)sdest, (void *)ssrc, n * sizeof(dfsan_label)); 137 return internal_memcpy(dest, src, n); 138} 139 140SANITIZER_INTERFACE_ATTRIBUTE 141dfsan_label dfsan_create_label(const char *desc, void *userdata) { 142 dfsan_label label = 143 atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1; 144 CHECK_NE(label, kInitializingLabel); 145 __dfsan_label_info[label].l1 = __dfsan_label_info[label].l2 = 0; 146 __dfsan_label_info[label].desc = desc; 147 __dfsan_label_info[label].userdata = userdata; 148 __dfsan_retval_tls = 0; // Ensures return value is unlabelled in the caller. 149 return label; 150} 151 152SANITIZER_INTERFACE_ATTRIBUTE 153void dfsan_set_label(dfsan_label label, void *addr, size_t size) { 154 for (dfsan_label *labelp = shadow_for(addr); size != 0; --size, ++labelp) 155 *labelp = label; 156} 157 158SANITIZER_INTERFACE_ATTRIBUTE 159void dfsan_add_label(dfsan_label label, void *addr, size_t size) { 160 for (dfsan_label *labelp = shadow_for(addr); size != 0; --size, ++labelp) 161 if (*labelp != label) 162 *labelp = __dfsan_union(*labelp, label); 163} 164 165SANITIZER_INTERFACE_ATTRIBUTE dfsan_label dfsan_get_label(long data) { 166 // The label for 'data' is implicitly passed by the instrumentation pass in 167 // the first element of __dfsan_arg_tls. So we can just return it. 168 __dfsan_retval_tls = 0; // Ensures return value is unlabelled in the caller. 169 return __dfsan_arg_tls[0]; 170} 171 172SANITIZER_INTERFACE_ATTRIBUTE 173const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label) { 174 __dfsan_retval_tls = 0; // Ensures return value is unlabelled in the caller. 175 return &__dfsan_label_info[label]; 176} 177 178int dfsan_has_label(dfsan_label label, dfsan_label elem) { 179 __dfsan_retval_tls = 0; // Ensures return value is unlabelled in the caller. 180 if (label == elem) 181 return true; 182 const dfsan_label_info *info = dfsan_get_label_info(label); 183 if (info->l1 != 0) { 184 return dfsan_has_label(info->l1, elem) || dfsan_has_label(info->l2, elem); 185 } else { 186 return false; 187 } 188} 189 190dfsan_label dfsan_has_label_with_desc(dfsan_label label, const char *desc) { 191 __dfsan_retval_tls = 0; // Ensures return value is unlabelled in the caller. 192 const dfsan_label_info *info = dfsan_get_label_info(label); 193 if (info->l1 != 0) { 194 return dfsan_has_label_with_desc(info->l1, desc) || 195 dfsan_has_label_with_desc(info->l2, desc); 196 } else { 197 return internal_strcmp(desc, info->desc) == 0; 198 } 199} 200 201#ifdef DFSAN_NOLIBC 202extern "C" void dfsan_init() { 203#else 204static void dfsan_init(int argc, char **argv, char **envp) { 205#endif 206 MmapFixedNoReserve(kShadowAddr, kUnusedAddr - kShadowAddr); 207 208 // Protect the region of memory we don't use, to preserve the one-to-one 209 // mapping from application to shadow memory. But if ASLR is disabled, Linux 210 // will load our executable in the middle of our unused region. This mostly 211 // works so long as the program doesn't use too much memory. We support this 212 // case by disabling memory protection when ASLR is disabled. 213 uptr init_addr = (uptr)&dfsan_init; 214 if (!(init_addr >= kUnusedAddr && init_addr < kAppAddr)) 215 Mprotect(kUnusedAddr, kAppAddr - kUnusedAddr); 216} 217 218#ifndef DFSAN_NOLIBC 219__attribute__((section(".preinit_array"), used)) 220static void (*dfsan_init_ptr)(int, char **, char **) = dfsan_init; 221#endif 222