1//===-- sanitizer_coverage.cc ---------------------------------------------===//
2//
3// This file is distributed under the University of Illinois Open Source
4// License. See LICENSE.TXT for details.
5//
6//===----------------------------------------------------------------------===//
7//
8// Sanitizer Coverage.
9// This file implements run-time support for a poor man's coverage tool.
10//
11// Compiler instrumentation:
12// For every interesting basic block the compiler injects the following code:
13// if (*Guard) {
14//    __sanitizer_cov();
15//    *Guard = 1;
16// }
17// It's fine to call __sanitizer_cov more than once for a given block.
18//
19// Run-time:
20//  - __sanitizer_cov(): record that we've executed the PC (GET_CALLER_PC).
21//  - __sanitizer_cov_dump: dump the coverage data to disk.
22//  For every module of the current process that has coverage data
23//  this will create a file module_name.PID.sancov. The file format is simple:
24//  it's just a sorted sequence of 4-byte offsets in the module.
25//
26// Eventually, this coverage implementation should be obsoleted by a more
27// powerful general purpose Clang/LLVM coverage instrumentation.
28// Consider this implementation as prototype.
29//
30// FIXME: support (or at least test with) dlclose.
31//===----------------------------------------------------------------------===//
32
33#include "sanitizer_allocator_internal.h"
34#include "sanitizer_common.h"
35#include "sanitizer_libc.h"
36#include "sanitizer_mutex.h"
37#include "sanitizer_procmaps.h"
38#include "sanitizer_stacktrace.h"
39#include "sanitizer_symbolizer.h"
40#include "sanitizer_flags.h"
41
42atomic_uint32_t dump_once_guard;  // Ensure that CovDump runs only once.
43
44// pc_array is the array containing the covered PCs.
45// To make the pc_array thread- and async-signal-safe it has to be large enough.
46// 128M counters "ought to be enough for anybody" (4M on 32-bit).
47
48// With coverage_direct=1 in ASAN_OPTIONS, pc_array memory is mapped to a file.
49// In this mode, __sanitizer_cov_dump does nothing, and CovUpdateMapping()
50// dump current memory layout to another file.
51
52static bool cov_sandboxed = false;
53static int cov_fd = kInvalidFd;
54static unsigned int cov_max_block_size = 0;
55
56namespace __sanitizer {
57
58class CoverageData {
59 public:
60  void Init();
61  void BeforeFork();
62  void AfterFork(int child_pid);
63  void Extend(uptr npcs);
64  void Add(uptr pc);
65  void IndirCall(uptr caller, uptr callee, uptr callee_cache[],
66                 uptr cache_size);
67  void DumpCallerCalleePairs();
68
69  uptr *data();
70  uptr size();
71
72 private:
73  // Maximal size pc array may ever grow.
74  // We MmapNoReserve this space to ensure that the array is contiguous.
75  static const uptr kPcArrayMaxSize = FIRST_32_SECOND_64(1 << 22, 1 << 27);
76  // The amount file mapping for the pc array is grown by.
77  static const uptr kPcArrayMmapSize = 64 * 1024;
78
79  // pc_array is allocated with MmapNoReserveOrDie and so it uses only as
80  // much RAM as it really needs.
81  uptr *pc_array;
82  // Index of the first available pc_array slot.
83  atomic_uintptr_t pc_array_index;
84  // Array size.
85  atomic_uintptr_t pc_array_size;
86  // Current file mapped size of the pc array.
87  uptr pc_array_mapped_size;
88  // Descriptor of the file mapped pc array.
89  int pc_fd;
90
91  // Caller-Callee (cc) array, size and current index.
92  static const uptr kCcArrayMaxSize = FIRST_32_SECOND_64(1 << 18, 1 << 24);
93  uptr **cc_array;
94  atomic_uintptr_t cc_array_index;
95  atomic_uintptr_t cc_array_size;
96
97
98  StaticSpinMutex mu;
99
100  void DirectOpen();
101  void ReInit();
102};
103
104static CoverageData coverage_data;
105
106void CoverageData::DirectOpen() {
107  InternalScopedString path(1024);
108  internal_snprintf((char *)path.data(), path.size(), "%s/%zd.sancov.raw",
109                    common_flags()->coverage_dir, internal_getpid());
110  pc_fd = OpenFile(path.data(), true);
111  if (internal_iserror(pc_fd)) {
112    Report(" Coverage: failed to open %s for writing\n", path.data());
113    Die();
114  }
115
116  pc_array_mapped_size = 0;
117  CovUpdateMapping();
118}
119
120void CoverageData::Init() {
121  pc_array = reinterpret_cast<uptr *>(
122      MmapNoReserveOrDie(sizeof(uptr) * kPcArrayMaxSize, "CovInit"));
123  pc_fd = kInvalidFd;
124  if (common_flags()->coverage_direct) {
125    atomic_store(&pc_array_size, 0, memory_order_relaxed);
126    atomic_store(&pc_array_index, 0, memory_order_relaxed);
127  } else {
128    atomic_store(&pc_array_size, kPcArrayMaxSize, memory_order_relaxed);
129    atomic_store(&pc_array_index, 0, memory_order_relaxed);
130  }
131
132  cc_array = reinterpret_cast<uptr **>(MmapNoReserveOrDie(
133      sizeof(uptr *) * kCcArrayMaxSize, "CovInit::cc_array"));
134  atomic_store(&cc_array_size, kCcArrayMaxSize, memory_order_relaxed);
135  atomic_store(&cc_array_index, 0, memory_order_relaxed);
136}
137
138void CoverageData::ReInit() {
139  internal_munmap(pc_array, sizeof(uptr) * kPcArrayMaxSize);
140  if (pc_fd != kInvalidFd) internal_close(pc_fd);
141  if (common_flags()->coverage_direct) {
142    // In memory-mapped mode we must extend the new file to the known array
143    // size.
144    uptr size = atomic_load(&pc_array_size, memory_order_relaxed);
145    Init();
146    if (size) Extend(size);
147  } else {
148    Init();
149  }
150}
151
152void CoverageData::BeforeFork() {
153  mu.Lock();
154}
155
156void CoverageData::AfterFork(int child_pid) {
157  // We are single-threaded so it's OK to release the lock early.
158  mu.Unlock();
159  if (child_pid == 0) ReInit();
160}
161
162// Extend coverage PC array to fit additional npcs elements.
163void CoverageData::Extend(uptr npcs) {
164  if (!common_flags()->coverage_direct) return;
165  SpinMutexLock l(&mu);
166
167  if (pc_fd == kInvalidFd) DirectOpen();
168  CHECK_NE(pc_fd, kInvalidFd);
169
170  uptr size = atomic_load(&pc_array_size, memory_order_relaxed);
171  size += npcs * sizeof(uptr);
172
173  if (size > pc_array_mapped_size) {
174    uptr new_mapped_size = pc_array_mapped_size;
175    while (size > new_mapped_size) new_mapped_size += kPcArrayMmapSize;
176
177    // Extend the file and map the new space at the end of pc_array.
178    uptr res = internal_ftruncate(pc_fd, new_mapped_size);
179    int err;
180    if (internal_iserror(res, &err)) {
181      Printf("failed to extend raw coverage file: %d\n", err);
182      Die();
183    }
184    void *p = MapWritableFileToMemory(pc_array + pc_array_mapped_size,
185                                      new_mapped_size - pc_array_mapped_size,
186                                      pc_fd, pc_array_mapped_size);
187    CHECK_EQ(p, pc_array + pc_array_mapped_size);
188    pc_array_mapped_size = new_mapped_size;
189  }
190
191  atomic_store(&pc_array_size, size, memory_order_release);
192}
193
194// Simply add the pc into the vector under lock. If the function is called more
195// than once for a given PC it will be inserted multiple times, which is fine.
196void CoverageData::Add(uptr pc) {
197  if (!pc_array) return;
198  uptr idx = atomic_fetch_add(&pc_array_index, 1, memory_order_relaxed);
199  CHECK_LT(idx * sizeof(uptr),
200           atomic_load(&pc_array_size, memory_order_acquire));
201  pc_array[idx] = pc;
202}
203
204// Registers a pair caller=>callee.
205// When a given caller is seen for the first time, the callee_cache is added
206// to the global array cc_array, callee_cache[0] is set to caller and
207// callee_cache[1] is set to cache_size.
208// Then we are trying to add callee to callee_cache [2,cache_size) if it is
209// not there yet.
210// If the cache is full we drop the callee (may want to fix this later).
211void CoverageData::IndirCall(uptr caller, uptr callee, uptr callee_cache[],
212                             uptr cache_size) {
213  if (!cc_array) return;
214  atomic_uintptr_t *atomic_callee_cache =
215      reinterpret_cast<atomic_uintptr_t *>(callee_cache);
216  uptr zero = 0;
217  if (atomic_compare_exchange_strong(&atomic_callee_cache[0], &zero, caller,
218                                     memory_order_seq_cst)) {
219    uptr idx = atomic_fetch_add(&cc_array_index, 1, memory_order_relaxed);
220    CHECK_LT(idx * sizeof(uptr),
221             atomic_load(&cc_array_size, memory_order_acquire));
222    callee_cache[1] = cache_size;
223    cc_array[idx] = callee_cache;
224  }
225  CHECK_EQ(atomic_load(&atomic_callee_cache[0], memory_order_relaxed), caller);
226  for (uptr i = 2; i < cache_size; i++) {
227    uptr was = 0;
228    if (atomic_compare_exchange_strong(&atomic_callee_cache[i], &was, callee,
229                                       memory_order_seq_cst))
230      return;
231    if (was == callee)  // Already have this callee.
232      return;
233  }
234}
235
236uptr *CoverageData::data() {
237  return pc_array;
238}
239
240uptr CoverageData::size() {
241  return atomic_load(&pc_array_index, memory_order_relaxed);
242}
243
244// Block layout for packed file format: header, followed by module name (no
245// trailing zero), followed by data blob.
246struct CovHeader {
247  int pid;
248  unsigned int module_name_length;
249  unsigned int data_length;
250};
251
252static void CovWritePacked(int pid, const char *module, const void *blob,
253                           unsigned int blob_size) {
254  if (cov_fd < 0) return;
255  unsigned module_name_length = internal_strlen(module);
256  CovHeader header = {pid, module_name_length, blob_size};
257
258  if (cov_max_block_size == 0) {
259    // Writing to a file. Just go ahead.
260    internal_write(cov_fd, &header, sizeof(header));
261    internal_write(cov_fd, module, module_name_length);
262    internal_write(cov_fd, blob, blob_size);
263  } else {
264    // Writing to a socket. We want to split the data into appropriately sized
265    // blocks.
266    InternalScopedBuffer<char> block(cov_max_block_size);
267    CHECK_EQ((uptr)block.data(), (uptr)(CovHeader *)block.data());
268    uptr header_size_with_module = sizeof(header) + module_name_length;
269    CHECK_LT(header_size_with_module, cov_max_block_size);
270    unsigned int max_payload_size =
271        cov_max_block_size - header_size_with_module;
272    char *block_pos = block.data();
273    internal_memcpy(block_pos, &header, sizeof(header));
274    block_pos += sizeof(header);
275    internal_memcpy(block_pos, module, module_name_length);
276    block_pos += module_name_length;
277    char *block_data_begin = block_pos;
278    char *blob_pos = (char *)blob;
279    while (blob_size > 0) {
280      unsigned int payload_size = Min(blob_size, max_payload_size);
281      blob_size -= payload_size;
282      internal_memcpy(block_data_begin, blob_pos, payload_size);
283      blob_pos += payload_size;
284      ((CovHeader *)block.data())->data_length = payload_size;
285      internal_write(cov_fd, block.data(),
286                     header_size_with_module + payload_size);
287    }
288  }
289}
290
291// If packed = false: <name>.<pid>.<sancov> (name = module name).
292// If packed = true and name == 0: <pid>.<sancov>.<packed>.
293// If packed = true and name != 0: <name>.<sancov>.<packed> (name is
294// user-supplied).
295static int CovOpenFile(bool packed, const char* name) {
296  InternalScopedBuffer<char> path(1024);
297  if (!packed) {
298    CHECK(name);
299    internal_snprintf((char *)path.data(), path.size(), "%s/%s.%zd.sancov",
300                      common_flags()->coverage_dir, name, internal_getpid());
301  } else {
302    if (!name)
303      internal_snprintf((char *)path.data(), path.size(),
304                        "%s/%zd.sancov.packed", common_flags()->coverage_dir,
305                        internal_getpid());
306    else
307      internal_snprintf((char *)path.data(), path.size(), "%s/%s.sancov.packed",
308                        common_flags()->coverage_dir, name);
309  }
310  uptr fd = OpenFile(path.data(), true);
311  if (internal_iserror(fd)) {
312    Report(" SanitizerCoverage: failed to open %s for writing\n", path.data());
313    return -1;
314  }
315  return fd;
316}
317
318// This function dumps the caller=>callee pairs into a file as a sequence of
319// lines like "module_name offset".
320void CoverageData::DumpCallerCalleePairs() {
321  uptr max_idx = atomic_load(&cc_array_index, memory_order_relaxed);
322  if (!max_idx) return;
323  auto sym = Symbolizer::GetOrInit();
324  if (!sym)
325    return;
326  InternalScopedString out(32 << 20);
327  uptr total = 0;
328  for (uptr i = 0; i < max_idx; i++) {
329    uptr *cc_cache = cc_array[i];
330    CHECK(cc_cache);
331    uptr caller = cc_cache[0];
332    uptr n_callees = cc_cache[1];
333    const char *caller_module_name = "<unknown>";
334    uptr caller_module_address = 0;
335    sym->GetModuleNameAndOffsetForPC(caller, &caller_module_name,
336                                     &caller_module_address);
337    for (uptr j = 2; j < n_callees; j++) {
338      uptr callee = cc_cache[j];
339      if (!callee) break;
340      total++;
341      const char *callee_module_name = "<unknown>";
342      uptr callee_module_address = 0;
343      sym->GetModuleNameAndOffsetForPC(callee, &callee_module_name,
344                                       &callee_module_address);
345      out.append("%s 0x%zx\n%s 0x%zx\n", caller_module_name,
346                 caller_module_address, callee_module_name,
347                 callee_module_address);
348    }
349  }
350  int fd = CovOpenFile(false, "caller-callee");
351  if (fd < 0) return;
352  internal_write(fd, out.data(), out.length());
353  internal_close(fd);
354  VReport(1, " CovDump: %zd caller-callee pairs written\n", total);
355}
356
357// Dump the coverage on disk.
358static void CovDump() {
359  if (!common_flags()->coverage || common_flags()->coverage_direct) return;
360#if !SANITIZER_WINDOWS
361  if (atomic_fetch_add(&dump_once_guard, 1, memory_order_relaxed))
362    return;
363  uptr size = coverage_data.size();
364  InternalMmapVector<u32> offsets(size);
365  uptr *vb = coverage_data.data();
366  uptr *ve = vb + size;
367  SortArray(vb, size);
368  MemoryMappingLayout proc_maps(/*cache_enabled*/true);
369  uptr mb, me, off, prot;
370  InternalScopedBuffer<char> module(4096);
371  InternalScopedBuffer<char> path(4096 * 2);
372  for (int i = 0;
373       proc_maps.Next(&mb, &me, &off, module.data(), module.size(), &prot);
374       i++) {
375    if ((prot & MemoryMappingLayout::kProtectionExecute) == 0)
376      continue;
377    while (vb < ve && *vb < mb) vb++;
378    if (vb >= ve) break;
379    if (*vb < me) {
380      offsets.clear();
381      const uptr *old_vb = vb;
382      CHECK_LE(off, *vb);
383      for (; vb < ve && *vb < me; vb++) {
384        uptr diff = *vb - (i ? mb : 0) + off;
385        CHECK_LE(diff, 0xffffffffU);
386        offsets.push_back(static_cast<u32>(diff));
387      }
388      const char *module_name = StripModuleName(module.data());
389      if (cov_sandboxed) {
390        if (cov_fd >= 0) {
391          CovWritePacked(internal_getpid(), module_name, offsets.data(),
392                         offsets.size() * sizeof(u32));
393          VReport(1, " CovDump: %zd PCs written to packed file\n", vb - old_vb);
394        }
395      } else {
396        // One file per module per process.
397        internal_snprintf((char *)path.data(), path.size(), "%s/%s.%zd.sancov",
398                          common_flags()->coverage_dir, module_name,
399                          internal_getpid());
400        int fd = CovOpenFile(false /* packed */, module_name);
401        if (fd > 0) {
402          internal_write(fd, offsets.data(), offsets.size() * sizeof(u32));
403          internal_close(fd);
404          VReport(1, " CovDump: %s: %zd PCs written\n", path.data(),
405                  vb - old_vb);
406        }
407      }
408    }
409  }
410  if (cov_fd >= 0)
411    internal_close(cov_fd);
412  coverage_data.DumpCallerCalleePairs();
413#endif  // !SANITIZER_WINDOWS
414}
415
416void CovPrepareForSandboxing(__sanitizer_sandbox_arguments *args) {
417  if (!args) return;
418  if (!common_flags()->coverage) return;
419  cov_sandboxed = args->coverage_sandboxed;
420  if (!cov_sandboxed) return;
421  cov_fd = args->coverage_fd;
422  cov_max_block_size = args->coverage_max_block_size;
423  if (cov_fd < 0)
424    // Pre-open the file now. The sandbox won't allow us to do it later.
425    cov_fd = CovOpenFile(true /* packed */, 0);
426}
427
428int MaybeOpenCovFile(const char *name) {
429  CHECK(name);
430  if (!common_flags()->coverage) return -1;
431  return CovOpenFile(true /* packed */, name);
432}
433
434void CovBeforeFork() {
435  coverage_data.BeforeFork();
436}
437
438void CovAfterFork(int child_pid) {
439  coverage_data.AfterFork(child_pid);
440}
441
442}  // namespace __sanitizer
443
444extern "C" {
445SANITIZER_INTERFACE_ATTRIBUTE void __sanitizer_cov() {
446  coverage_data.Add(StackTrace::GetPreviousInstructionPc(GET_CALLER_PC()));
447}
448SANITIZER_INTERFACE_ATTRIBUTE void
449__sanitizer_cov_indir_call16(uptr callee, uptr callee_cache16[]) {
450  coverage_data.IndirCall(StackTrace::GetPreviousInstructionPc(GET_CALLER_PC()),
451                          callee, callee_cache16, 16);
452}
453SANITIZER_INTERFACE_ATTRIBUTE void __sanitizer_cov_dump() { CovDump(); }
454SANITIZER_INTERFACE_ATTRIBUTE void __sanitizer_cov_init() {
455  coverage_data.Init();
456}
457SANITIZER_INTERFACE_ATTRIBUTE void __sanitizer_cov_module_init(uptr npcs) {
458  if (!common_flags()->coverage || !common_flags()->coverage_direct) return;
459  if (SANITIZER_ANDROID) {
460    // dlopen/dlclose interceptors do not work on Android, so we rely on
461    // Extend() calls to update .sancov.map.
462    CovUpdateMapping(GET_CALLER_PC());
463  }
464  coverage_data.Extend(npcs);
465}
466SANITIZER_INTERFACE_ATTRIBUTE
467sptr __sanitizer_maybe_open_cov_file(const char *name) {
468  return MaybeOpenCovFile(name);
469}
470}  // extern "C"
471