[dfsan] Add origin chain utils

[stephan.yichao.zhao]

Summary

This is a part of https://reviews.llvm.org/D95835.

The design is based on MSan origin chains.

An 4-byte origin is a hash of an origin chain. An origin chain is a
pair of a stack hash id and a hash to its previous origin chain. 0 means
no previous origin chains exist. We limit the length of a chain to be 16.
With origin_history_size <= 0, the limit is removed.

The number of an origin node reference count is also limited.
See 3.6.1 of this paper.

The change does not have any test cases yet. The following change
will be adding test cases when the APIs are used.

[stephan.yichao.zhao]

fixed lint warnings

[morehouse]

compiler-rt/lib/dfsan/dfsan.cpp

288

Which platforms are these? If non-Linux, we don't care for DFSan.

301

Where is this defined? Please include the file directly.

compiler-rt/lib/dfsan/dfsan_chained_origin_depot.cpp

24

How much of this file is the same as MSan? Can we move the implementation to sanitizer_common and share it with both?

compiler-rt/lib/dfsan/dfsan_chained_origin_depot.h

22

26

[stephan.yichao.zhao]

compiler-rt/lib/dfsan/dfsan_chained_origin_depot.cpp

24

Will move them into sanitizer_common in a child change.

[morehouse]

compiler-rt/lib/dfsan/dfsan_chained_origin_depot.cpp

24

I think I'd prefer to move it first, then review this patch. It would make it easier to see the differences.

[stephan.yichao.zhao]

compiler-rt/lib/dfsan/dfsan.cpp

288

In terms of this, this happens only on mips.
Removed the restriction, but still keep the comments for reference.

301

It is defined sanitizer_stacktrace.h. We include this file.

compiler-rt/lib/dfsan/dfsan_chained_origin_depot.cpp

24

See D96319.

compiler-rt/lib/dfsan/dfsan_chained_origin_depot.h

22

fixed in the child change D96319.

26

fixed in the child change D96319.

[stephan.yichao.zhao]

updated

[stephan.yichao.zhao]

wait for D96319.

[stephan.yichao.zhao]

updated after D96319.

[stephan.yichao.zhao]

update

[morehouse]

compiler-rt/lib/dfsan/dfsan.cpp

295

We should include dfsan_flags.h for this.

308

Tracking origins through signal handlers could help a lot in debugging obscure bugs.

If it is not possible to track, please add a comment explaining why.

compiler-rt/lib/dfsan/dfsan_origin.h

83

This will fail if origin_history_size is larger than 1 << kDepthBits.

114

126

Nit: Let's move this to the top of the public section above.

[stephan.yichao.zhao]

updated in terms of comments

compiler-rt/lib/dfsan/dfsan.cpp

295

We include dfsan_flags.h in dfsan.h where we defined flags() before moving it into dfsan_flags.h.

compiler-rt/lib/dfsan/dfsan_origin.h

83

changed this assert to a normal check.

114

Thank you,

126

It refers to the private kDepthBits. The compiler does not allow forward reference for some reason.

[morehouse]

compiler-rt/lib/dfsan/dfsan.cpp

295

I prefer direct includes so we don't need to touch this file if we later remove the include from dfsan.h.

[stephan.yichao.zhao]

added dfsan_flags.h

[uabelho]

compiler-rt/lib/dfsan/dfsan.cpp

305

This function seems to be unused, and currently make clang raise a warning:

12:25:59 /repo/bbiswjenk/fem2s10-eiffel176/workspace/llvm/llvm-master-clang/compiler-rt/lib/dfsan/dfsan.cpp:307:12: error: unused function 'ChainOrigin' [-Werror,-Wunused-function]
12:25:59 static u32 ChainOrigin(u32 id, StackTrace *stack, bool from_init = false) {
12:25:59 ^
12:25:59 1 error generated.

[stephan.yichao.zhao]

compiler-rt/lib/dfsan/dfsan.cpp

305

Thank you for reporting this. The next change (https://reviews.llvm.org/D96564) will be fixing this. But I submitted a fix to comment this out for now: https://github.com/llvm/llvm-project/commit/a7538fee3a0256a8891e746823f7b0f0ade84e62

compiler-rt/lib/dfsan/CMakeLists.txt

 include_directories(..)
 
 # Runtime library sources and build flags.
 set(DFSAN_RTL_SOURCES
   dfsan.cpp
+  dfsan_chained_origin_depot.cpp
   dfsan_custom.cpp
   dfsan_interceptors.cpp
   dfsan_thread.cpp
   )
 
 set(DFSAN_RTL_HEADERS
   dfsan.h
+  dfsan_chained_origin_depot.h
   dfsan_flags.inc
+  dfsan_flags.h
   dfsan_platform.h
   dfsan_thread.h
   )
 
 set(DFSAN_COMMON_CFLAGS ${SANITIZER_COMMON_CFLAGS})
 append_rtti_flag(OFF DFSAN_COMMON_CFLAGS)
 # Prevent clang from generating libc calls.
 append_list_if(COMPILER_RT_HAS_FFREESTANDING_FLAG -ffreestanding DFSAN_COMMON_CFLAGS)

compiler-rt/lib/dfsan/dfsan.h

 //
 // Private DFSan header.
 //===----------------------------------------------------------------------===//
 
 #ifndef DFSAN_H
 #define DFSAN_H
 
 #include "sanitizer_common/sanitizer_internal_defs.h"
+
+#include "dfsan_flags.h"
 #include "dfsan_platform.h"
 
 using __sanitizer::uptr;
 using __sanitizer::u16;
 
 // Copy declarations from public sanitizer/dfsan_interface.h header here.
 typedef u16 dfsan_label;
 

 inline dfsan_label *shadow_for(void *ptr) {
   return (dfsan_label *) ((((uptr) ptr) & ShadowMask()) << 1);
 }
 
 inline const dfsan_label *shadow_for(const void *ptr) {
   return shadow_for(const_cast<void *>(ptr));
 }
 
-struct Flags {
-#define DFSAN_FLAG(Type, Name, DefaultValue, Description) Type Name;
-#include "dfsan_flags.inc"
-#undef DFSAN_FLAG
-
-  void SetDefaults();
-};
-
-extern Flags flags_data;
-inline Flags &flags() {
-  return flags_data;
-}
-
 }  // namespace __dfsan
 
 #endif  // DFSAN_H

compiler-rt/lib/dfsan/dfsan.cpp

 //
 // The public interface is defined in include/sanitizer/dfsan_interface.h whose
 // functions are prefixed dfsan_ while the compiler interface functions are
 // prefixed __dfsan_.
 //===----------------------------------------------------------------------===//
 
 #include "dfsan/dfsan.h"
 
+#include "dfsan/dfsan_chained_origin_depot.h"
+#include "dfsan/dfsan_flags.h"
+#include "dfsan/dfsan_origin.h"
 #include "dfsan/dfsan_thread.h"
 #include "sanitizer_common/sanitizer_atomic.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_file.h"
 #include "sanitizer_common/sanitizer_flag_parser.h"
 #include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_internal_defs.h"
 #include "sanitizer_common/sanitizer_libc.h"
dfsan_label label =
       atomic_fetch_add(&__dfsan_last_label, 1, memory_order_relaxed) + 1;
   dfsan_check_label(label);
   __dfsan_label_info[label].l1 = __dfsan_label_info[label].l2 = 0;
   __dfsan_label_info[label].desc = desc;
   __dfsan_label_info[label].userdata = userdata;
   return label;
 }
 
+// For platforms which support slow unwinder only, we need to restrict the store
+// context size to 1, basically only storing the current pc, because the slow
+// unwinder which is based on libunwind is not async signal safe and causes
+// random freezes in forking applications as well as in signal handlers.
+// DFSan supports only Linux. So we do not restrict the store context size.
+#define GET_STORE_STACK_TRACE_PC_BP(pc, bp) \
+  BufferedStackTrace stack;                 \
+  stack.Unwind(pc, bp, nullptr, true, flags().store_context_size);
+
+#define PRINT_CALLER_STACK_TRACE        \
+  {                                     \
+    GET_CALLER_PC_BP_SP;                \
+    (void)sp;                           \
+    GET_STORE_STACK_TRACE_PC_BP(pc, bp) \
+    stack.Print();                      \
+  }
+
+static u32 ChainOrigin(u32 id, StackTrace *stack, bool from_init = false) {
+  // StackDepot is not async signal safe. Do not create new chains in a signal
+  // handler.
+  DFsanThread *t = GetCurrentThread();
+  if (t && t->InSignalHandler())
+    return id;
+
+  // As an optimization the origin of an application byte is updated only when
+  // its shadow is non-zero. Because we are only interested in the origins of
+  // taint labels, it does not matter what origin a zero label has. This reduces
+  // memory write cost. MSan does similar optimization. The following invariant
+  // may not hold because of some bugs. We check the invariant to help debug.
+  if (!from_init && id == 0 && flags().check_origin_invariant) {
+    Printf("  DFSan found invalid origin invariant\n");
+    PRINT_CALLER_STACK_TRACE
+  }
+
+  Origin o = Origin::FromRawId(id);
+  stack->tag = StackTrace::TAG_UNKNOWN;
+  Origin chained = Origin::CreateChainedOrigin(o, stack);
+  return chained.raw_id();
+}
+
 static void WriteShadowIfDifferent(dfsan_label label, uptr shadow_addr,
                                    uptr size) {
   dfsan_label *labelp = (dfsan_label *)shadow_addr;
   for (; size != 0; --size, ++labelp) {
     // Don't write the label if it is already the value we need it to be.
     // In a program where most addresses are not labeled, it is common that
     // a page of shadow memory is entirely zeroed.  The Linux copy-on-write
     // implementation will share all of the zeroed pages, making a copy of a

compiler-rt/lib/dfsan/dfsan_chained_origin_depot.h

+//===-- dfsan_chained_origin_depot.h ----------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of DataFlowSanitizer.
+//
+// A storage for chained origins.
+//===----------------------------------------------------------------------===//
+
+#ifndef DFSAN_CHAINED_ORIGIN_DEPOT_H
+#define DFSAN_CHAINED_ORIGIN_DEPOT_H
+
+#include "sanitizer_common/sanitizer_chained_origin_depot.h"
+#include "sanitizer_common/sanitizer_common.h"
+
+namespace __dfsan {
+
+ChainedOriginDepot* GetChainedOriginDepot();
+
+}  // namespace __dfsan
+
+#endif  // DFSAN_CHAINED_ORIGIN_DEPOT_H

compiler-rt/lib/dfsan/dfsan_chained_origin_depot.cpp

+//===-- dfsan_chained_origin_depot.cpp ------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of DataFlowSanitizer.
+//
+// A storage for chained origins.
+//===----------------------------------------------------------------------===//
+
+#include "dfsan_chained_origin_depot.h"
+
+namespace __dfsan {
+
+static ChainedOriginDepot chainedOriginDepot;
+
+ChainedOriginDepot* GetChainedOriginDepot() { return &chainedOriginDepot; }
+
+}  // namespace __dfsan

compiler-rt/lib/dfsan/dfsan_flags.h

+//===-- dfsan_flags.h -------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of DataFlowSanitizer.
+//
+// DFSan flags.
+//===----------------------------------------------------------------------===//
+
+#ifndef DFSAN_FLAGS_H
+#define DFSAN_FLAGS_H
+
+namespace __dfsan {
+
+struct Flags {
+#define DFSAN_FLAG(Type, Name, DefaultValue, Description) Type Name;
+#include "dfsan_flags.inc"
+#undef DFSAN_FLAG
+
+  void SetDefaults();
+};
+
+extern Flags flags_data;
+inline Flags &flags() { return flags_data; }
+
+}  // namespace __dfsan
+
+#endif  // DFSAN_FLAGS_H

compiler-rt/lib/dfsan/dfsan_flags.inc

DFSAN_FLAG(
     bool, strict_data_dependencies, true,
     "Whether to propagate labels only when there is an obvious data dependency"
     "(e.g., when comparing strings, ignore the fact that the output of the"
     "comparison might be data-dependent on the content of the strings). This"
     "applies only to the custom functions defined in 'custom.c'.")
 DFSAN_FLAG(const char *, dump_labels_at_exit, "", "The path of the file where "
                                                   "to dump the labels when the "
                                                   "program terminates.")
+DFSAN_FLAG(
+     int, origin_history_size, Origin::kMaxDepth,
+    "The limit of origin chain length. Non-positive values mean unlimited.")
+DFSAN_FLAG(
+     int, origin_history_per_stack_limit, 20000,
+    "The limit of origin node's references count. "
+    "Non-positive values mean unlimited.")
+DFSAN_FLAG(int, store_context_size, 20,
+           "The depth limit of origin tracking stack traces.")
+DFSAN_FLAG(bool, check_origin_invariant, false,
+           "Whether to check if the origin invariant holds.")

compiler-rt/lib/dfsan/dfsan_origin.h

+//===-- dfsan_origin.h ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of DataFlowSanitizer.
+//
+// Origin id utils.
+//===----------------------------------------------------------------------===//
+
+#ifndef DFSAN_ORIGIN_H
+#define DFSAN_ORIGIN_H
+
+#include "dfsan_chained_origin_depot.h"
+#include "dfsan_flags.h"
+#include "sanitizer_common/sanitizer_stackdepot.h"
+
+namespace __dfsan {
+
+// Origin handling.
+//
+// Origin is a 32-bit identifier that is attached to any taint value in the
+// program and describes how this memory came to be tainted.
+//
+// Chained origin id is like:
+// zzzz xxxx xxxx xxxx
+//
+// Chained origin id describes an event of storing a taint value to
+// memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of
+// (stack_id, prev_id) -> id, where
+//  * stack_id describes the event.
+//    StackDepot keeps a mapping between those and corresponding stack traces.
+//  * prev_id is another origin id that describes the earlier part of the
+//    taint value history. 0 prev_id indicates the start of a chain.
+// Following a chain of prev_id provides the full recorded history of a taint
+// value.
+//
+// This, effectively, defines a forest where nodes are points in value history
+// marked with origin ids, and edges are events that are marked with stack_id.
+//
+// The "zzzz" bits of chained origin id are used to store the length of the
+// origin chain.
+
+class Origin {
+ public:
+  static bool isValidId(u32 id) { return id != 0; }
+
+  u32 raw_id() const { return raw_id_; }
+
+  bool isChainedOrigin() const { return Origin::isValidId(raw_id_); }
+
+  u32 getChainedId() const {
+    CHECK(Origin::isValidId(raw_id_));
+    return raw_id_ & kChainedIdMask;
+  }
+
+  // Returns the next origin in the chain and the current stack trace.
+  //
+  // It scans a partition of StackDepot linearly, and is used only by origin
+  // tracking report.
+  Origin getNextChainedOrigin(StackTrace *stack) const {
+    CHECK(Origin::isValidId(raw_id_));
+    u32 prev_id;
+    u32 stack_id = GetChainedOriginDepot()->Get(getChainedId(), &prev_id);
+    if (stack)
+      *stack = StackDepotGet(stack_id);
+    return Origin(prev_id);
+  }
+
+  static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) {
+    int depth = prev.isChainedOrigin() ? prev.depth() : -1;
+    // depth is the length of the chain minus 1.
+    // origin_history_size of 0 means unlimited depth.
+    if (flags().origin_history_size > 0) {
+      ++depth;
+      if (depth >= flags().origin_history_size || depth > kMaxDepth)
+        return prev;
+    }
+
+    StackDepotHandle h = StackDepotPut_WithHandle(*stack);
+    if (!h.valid())
+      return prev;
+
+    if (flags().origin_history_per_stack_limit > 0) {
+      int use_count = h.use_count();
+      if (use_count > flags().origin_history_per_stack_limit)
+        return prev;
+    }
+
+    u32 chained_id;
+    bool inserted =
+        GetChainedOriginDepot()->Put(h.id(), prev.raw_id(), &chained_id);
+    CHECK((chained_id & kChainedIdMask) == chained_id);
+
+    if (inserted && flags().origin_history_per_stack_limit > 0)
+      h.inc_use_count_unsafe();
+
+    return Origin((depth << kDepthShift) | chained_id);
+  }
+
+  static Origin FromRawId(u32 id) { return Origin(id); }
+
+ private:
+  static const int kDepthBits = 4;
+  static const int kDepthShift = 32 - kDepthBits;
+
+  static const u32 kChainedIdMask = ((u32)-1) >> kDepthBits;
+
+  u32 raw_id_;
+
+  explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
+
+  int depth() const {
+    CHECK(isChainedOrigin());
+    return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1);
+  }
+
+ public:
+  static const int kMaxDepth = (1 << kDepthBits) - 1;
+};
+
+}  // namespace __dfsan
+
+#endif  // DFSAN_ORIGIN_H