[sanitizer] Move MSan's chained_origin_depot to sanitizer_common

[stephan.yichao.zhao]

Summary

https://reviews.llvm.org/D95835 implements origin tracking for DFSan.
It reuses the chained origin depot of MSan.

This change moves the utility to sanitizer_common to share between
MSan and DFSan.

[morehouse]

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp

2

Looks like accidental line break here.

compiler-rt/lib/sanitizer_common/tests/sanitizer_chained_origin_depot_test.cpp

17

Please fix this lint

45

Do we need to somehow reset the origin depot between tests? If the Basic test runs before this one, will we still get true?

48

So we expect that when the Put fails it should return the existing origin ID. Let's document this in the ChainedOriginDepotPut function comment.

60

Should we test that Get with both new_id1 and new_id2 returns the current StackDepot ID and previous origin ID?

[stephan.yichao.zhao]

compiler-rt/lib/sanitizer_common/tests/sanitizer_chained_origin_depot_test.cpp

17

reordered them. but that gtest.h cannot be removed.

45

The underlying StackDepot is a global variable, and internally it allocates memory permanently, does not have a 'free' method.

This is a good point. I updated the test cases to use different numbers.

[stephan.yichao.zhao]

updated

[stephan.yichao.zhao]

compiler-rt/lib/sanitizer_common/tests/sanitizer_chained_origin_depot_test.cpp

17

for some reason, the local lint used by arc suggests this style different from the online one, and does not allow update if we reordered the headers.

[morehouse]

LGTM

[eugenis]

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp

102

This is a pretty large global variable that seems to be added to all sanitizers now, even those that do not need it, like hwasan.

[stephan.yichao.zhao]

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp

102

This is a good point...

The main goal of this change is about code reuse.

To address this issue, one possible fixes could be making the declaration here as extern attribute((weak));, and msan/dsan can define them separately.
Other sanitizers would not define it. Will this work for msan?

[eugenis]

I'd rather create a ChainedOriginDepot class, turn all the global functions into methods, turn the global variable into a member and then instantiate it in dfsan and msan separately.

[stephan.yichao.zhao]

changed origin chain to a class.

But we still keep the wrappers in msan_chained_origin_depot.h|cpp, because sanitizer_chained_origin_depot includes sanitizer_stackdepotbase and sanitizer_stackdepotbase includes sanitizer_internal_defs. sanitizer_internal_defs has types and functions conflicting with msan_interceptors

[eugenis]

LGTM

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.h

80

Please rename it to just "depot" or something like that - the current name makes it look like it could be an instance of class ChainOriginDepot.

[stephan.yichao.zhao]

renamed chainedOriginDepot to depot.

[vitalybuka]

This one breaks "check-memprof"

'RUN: at line 9';   env MEMPROF_OPTIONS=log_path=stderr  /usr/local/google/home/vitalybuka/src/llvm.git/out/z/projects/compiler-rt/test/memprof/X86_64LinuxConfig/TestCases/Output/test_malloc_load_store.c.tmp 2>&1 | FileCheck /usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/test/memprof/TestCases/test_malloc_load_store.c
--
Exit Code: 1

Command Output (stderr):
--
clang-13: warning: treating 'c' input as 'c++' when in C++ mode, this behavior is deprecated [-Wdeprecated]
/usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/test/memprof/TestCases/test_malloc_load_store.c:20:16: error: CHECK-NEXT: expected string not found in input
// CHECK-NEXT: #0 {{.*}} in malloc
               ^
<stdin>:37:2: note: scanning from here
 #0 0x44a71d in __interceptor_malloc /usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/lib/memprof/memprof_malloc_linux.cpp:127:3
 ^
<stdin>:37:20: note: possible intended match here
 #0 0x44a71d in __interceptor_malloc /usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/lib/memprof/memprof_malloc_linux.cpp:127:3
                   ^

Input file: <stdin>
Check file: /usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/test/memprof/TestCases/test_malloc_load_store.c

-dump-input=help explains the following input dump.

Input was:
<<<<<<
           .
           .
           .
          32: Stack for id 1090519041:
          33:  #0 0x44a71d in __interceptor_malloc /usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/lib/memprof/memprof_malloc_linux.cpp:127:3
          34:  #1 0x7fb446b078b0 in _dl_exception_create_format elf/dl-exception.c:146:21
          35: 
          36: Stack for id 1342177281:
          37:  #0 0x44a71d in __interceptor_malloc /usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/lib/memprof/memprof_malloc_linux.cpp:127:3
next:20'0      X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
next:20'1                        ?                                                                                                                                    possible intended match
          38:  #1 0x46a58d in main /usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/test/memprof/TestCases/test_malloc_load_store.c:27:19
next:20'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
          39:  #2 0x7fb4465b5d09 in __libc_start_main csu/../csu/libc-start.c:308:16
next:20'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
          40: 
next:20'0     ~
          41: Stack for id 1686110209:
next:20'0     ~~~~~~~~~~~~~~~~~~~~~~~~
          42:  #0 0x44a71d in __interceptor_malloc /usr/local/google/home/vitalybuka/src/llvm.git/llvm-project/compiler-rt/lib/memprof/memprof_malloc_linux.cpp:127:3
next:20'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           .
           .
           .
>>>>>>

--

********************
********************
Failed Tests (1):
  MemProfiler-x86_64-linux :: TestCases/test_malloc_load_store.c

[stephan.yichao.zhao]

I cannot reproduce this error by ninja check-memprof from my sandbox.

This change, although related to StackDepot, does not use the one in compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp. It creates a new instance of StackDepotBase used by only Msan.

[stephan.yichao.zhao]

Fixed by https://github.com/llvm/llvm-project/commit/f2133f2e318d8ce87e9972d288485d9bc49fef5c. Thank you. @vitalybuka

compiler-rt/lib/msan/msan_chained_origin_depot.h

-//===-- msan_chained_origin_depot.h --------------------------*- C++ -*-===//
+//===-- msan_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 MemorySanitizer.
+//
 // A storage for chained origins.
 //===----------------------------------------------------------------------===//
+
 #ifndef MSAN_CHAINED_ORIGIN_DEPOT_H
 #define MSAN_CHAINED_ORIGIN_DEPOT_H
 
 #include "sanitizer_common/sanitizer_common.h"
 
 namespace __msan {
 
+// Gets the statistic of the origin chain storage.
 StackDepotStats *ChainedOriginDepotGetStats();
+
+// Stores a chain with StackDepot ID here_id and previous chain ID prev_id.
+// If successful, returns true and the new chain id new_id.
+// If the same element already exists, returns false and sets new_id to the
+// existing ID.
 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id);
-// Retrieves a stored stack trace by the id.
+
+// Retrieves the stored StackDepot ID for the given origin ID.
 u32 ChainedOriginDepotGet(u32 id, u32 *other);
 
 void ChainedOriginDepotLockAll();
 void ChainedOriginDepotUnlockAll();
 
 }  // namespace __msan
 
 #endif  // MSAN_CHAINED_ORIGIN_DEPOT_H

compiler-rt/lib/msan/msan_chained_origin_depot.cpp

-//===-- msan_chained_origin_depot.cpp ----------------------------------===//
+//===-- msan_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 MemorySanitizer.
+//
 // A storage for chained origins.
 //===----------------------------------------------------------------------===//
 
 #include "msan_chained_origin_depot.h"
 
-#include "sanitizer_common/sanitizer_stackdepotbase.h"
+#include "sanitizer_common/sanitizer_chained_origin_depot.h"
 
 namespace __msan {
 
-struct ChainedOriginDepotDesc {
-  u32 here_id;
-  u32 prev_id;
-};
-
-struct ChainedOriginDepotNode {
-  ChainedOriginDepotNode *link;
-  u32 id;
-  u32 here_id;
-  u32 prev_id;
-
-  typedef ChainedOriginDepotDesc args_type;
-
-  bool eq(u32 hash, const args_type &args) const {
-    return here_id == args.here_id && prev_id == args.prev_id;
-  }
-
-  static uptr storage_size(const args_type &args) {
-    return sizeof(ChainedOriginDepotNode);
-  }
-
-  /* This is murmur2 hash for the 64->32 bit case.
-     It does not behave all that well because the keys have a very biased
-     distribution (I've seen 7-element buckets with the table only 14% full).
-
-     here_id is built of
-     * (1 bits) Reserved, zero.
-     * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
-     * (23 bits) Sequential number (each part has each own sequence).
-
-     prev_id has either the same distribution as here_id (but with 3:8:21)
-     split, or one of two reserved values (-1) or (-2). Either case can
-     dominate depending on the workload.
-  */
-  static u32 hash(const args_type &args) {
-    const u32 m = 0x5bd1e995;
-    const u32 seed = 0x9747b28c;
-    const u32 r = 24;
-    u32 h = seed;
-    u32 k = args.here_id;
-    k *= m;
-    k ^= k >> r;
-    k *= m;
-    h *= m;
-    h ^= k;
-
-    k = args.prev_id;
-    k *= m;
-    k ^= k >> r;
-    k *= m;
-    h *= m;
-    h ^= k;
-
-    h ^= h >> 13;
-    h *= m;
-    h ^= h >> 15;
-    return h;
-  }
-  static bool is_valid(const args_type &args) { return true; }
-  void store(const args_type &args, u32 other_hash) {
-    here_id = args.here_id;
-    prev_id = args.prev_id;
-  }
-
-  args_type load() const {
-    args_type ret = {here_id, prev_id};
-    return ret;
-  }
-
-  struct Handle {
-    ChainedOriginDepotNode *node_;
-    Handle() : node_(nullptr) {}
-    explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
-    bool valid() { return node_; }
-    u32 id() { return node_->id; }
-    int here_id() { return node_->here_id; }
-    int prev_id() { return node_->prev_id; }
-  };
-
-  Handle get_handle() { return Handle(this); }
-
-  typedef Handle handle_type;
-};
-
-static StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
+static ChainedOriginDepot chainedOriginDepot;
 
 StackDepotStats *ChainedOriginDepotGetStats() {
   return chainedOriginDepot.GetStats();
 }
 
 bool ChainedOriginDepotPut(u32 here_id, u32 prev_id, u32 *new_id) {
-  ChainedOriginDepotDesc desc = {here_id, prev_id};
-  bool inserted;
-  ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
-  *new_id = h.valid() ? h.id() : 0;
-  return inserted;
+  return chainedOriginDepot.Put(here_id, prev_id, new_id);
 }
 
-// Retrieves a stored stack trace by the id.
 u32 ChainedOriginDepotGet(u32 id, u32 *other) {
-  ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
-  *other = desc.prev_id;
-  return desc.here_id;
+  return chainedOriginDepot.Get(id, other);
 }
 
 void ChainedOriginDepotLockAll() {
   chainedOriginDepot.LockAll();
 }
 
 void ChainedOriginDepotUnlockAll() {
   chainedOriginDepot.UnlockAll();
 }
 
 } // namespace __msan

compiler-rt/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_COVERAGE_SOURCES
   sancov_flags.cpp
   sanitizer_coverage_fuchsia.cpp
   sanitizer_coverage_libcdep_new.cpp
   sanitizer_coverage_win_sections.cpp
   )
 
 set(SANITIZER_SYMBOLIZER_SOURCES
   sanitizer_allocator_report.cpp
+  sanitizer_chained_origin_depot.cpp
   sanitizer_stackdepot.cpp
   sanitizer_stacktrace.cpp
   sanitizer_stacktrace_libcdep.cpp
   sanitizer_stacktrace_printer.cpp
   sanitizer_stacktrace_sparc.cpp
   sanitizer_symbolizer.cpp
   sanitizer_symbolizer_libbacktrace.cpp
   sanitizer_symbolizer_libcdep.cpp
set(SANITIZER_IMPL_HEADERS
   sanitizer_atomic.h
   sanitizer_atomic_clang.h
   sanitizer_atomic_clang_mips.h
   sanitizer_atomic_clang_other.h
   sanitizer_atomic_clang_x86.h
   sanitizer_atomic_msvc.h
   sanitizer_bitvector.h
   sanitizer_bvgraph.h
+  sanitizer_chained_origin_depot.h
   sanitizer_common.h
   sanitizer_common_interceptors.inc
   sanitizer_common_interceptors_format.inc
   sanitizer_common_interceptors_ioctl.inc
   sanitizer_common_interface.inc
   sanitizer_common_interface_posix.inc
   sanitizer_common_syscalls.inc
   sanitizer_coverage_interface.inc

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.h

+//===-- sanitizer_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
+//
+//===----------------------------------------------------------------------===//
+//
+// A storage for chained origins.
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_CHAINED_ORIGIN_DEPOT_H
+#define SANITIZER_CHAINED_ORIGIN_DEPOT_H
+
+#include "sanitizer_common.h"
+#include "sanitizer_stackdepotbase.h"
+
+namespace __sanitizer {
+
+class ChainedOriginDepot {
+ public:
+  ChainedOriginDepot();
+
+  // Gets the statistic of the origin chain storage.
+  StackDepotStats *GetStats();
+
+  // Stores a chain with StackDepot ID here_id and previous chain ID prev_id.
+  // If successful, returns true and the new chain id new_id.
+  // If the same element already exists, returns false and sets new_id to the
+  // existing ID.
+  bool Put(u32 here_id, u32 prev_id, u32 *new_id);
+
+  // Retrieves the stored StackDepot ID for the given origin ID.
+  u32 Get(u32 id, u32 *other);
+
+  void LockAll();
+  void UnlockAll();
+
+ private:
+  struct ChainedOriginDepotDesc {
+    u32 here_id;
+    u32 prev_id;
+  };
+
+  struct ChainedOriginDepotNode {
+    ChainedOriginDepotNode *link;
+    u32 id;
+    u32 here_id;
+    u32 prev_id;
+
+    typedef ChainedOriginDepotDesc args_type;
+
+    bool eq(u32 hash, const args_type &args) const;
+
+    static uptr storage_size(const args_type &args);
+
+    static u32 hash(const args_type &args);
+
+    static bool is_valid(const args_type &args);
+
+    void store(const args_type &args, u32 other_hash);
+
+    args_type load() const;
+
+    struct Handle {
+      ChainedOriginDepotNode *node_;
+      Handle() : node_(nullptr) {}
+      explicit Handle(ChainedOriginDepotNode *node) : node_(node) {}
+      bool valid() { return node_; }
+      u32 id() { return node_->id; }
+      int here_id() { return node_->here_id; }
+      int prev_id() { return node_->prev_id; }
+    };
+
+    Handle get_handle();
+
+    typedef Handle handle_type;
+  };
+
+  StackDepotBase<ChainedOriginDepotNode, 4, 20> chainedOriginDepot;
+
+  ChainedOriginDepot(const ChainedOriginDepot &) = delete;
+  void operator=(const ChainedOriginDepot &) = delete;
+};
+
+}  // namespace __sanitizer
+
+#endif  // SANITIZER_CHAINED_ORIGIN_DEPOT_H

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp

+//===-- sanitizer_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
+//
+//===----------------------------------------------------------------------===//
+//
+// A storage for chained origins.
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_chained_origin_depot.h"
+
+namespace __sanitizer {
+
+bool ChainedOriginDepot::ChainedOriginDepotNode::eq(
+    u32 hash, const args_type &args) const {
+  return here_id == args.here_id && prev_id == args.prev_id;
+}
+
+uptr ChainedOriginDepot::ChainedOriginDepotNode::storage_size(
+    const args_type &args) {
+  return sizeof(ChainedOriginDepotNode);
+}
+
+/* This is murmur2 hash for the 64->32 bit case.
+   It does not behave all that well because the keys have a very biased
+   distribution (I've seen 7-element buckets with the table only 14% full).
+
+   here_id is built of
+   * (1 bits) Reserved, zero.
+   * (8 bits) Part id = bits 13..20 of the hash value of here_id's key.
+   * (23 bits) Sequential number (each part has each own sequence).
+
+   prev_id has either the same distribution as here_id (but with 3:8:21)
+   split, or one of two reserved values (-1) or (-2). Either case can
+   dominate depending on the workload.
+*/
+u32 ChainedOriginDepot::ChainedOriginDepotNode::hash(const args_type &args) {
+  const u32 m = 0x5bd1e995;
+  const u32 seed = 0x9747b28c;
+  const u32 r = 24;
+  u32 h = seed;
+  u32 k = args.here_id;
+  k *= m;
+  k ^= k >> r;
+  k *= m;
+  h *= m;
+  h ^= k;
+
+  k = args.prev_id;
+  k *= m;
+  k ^= k >> r;
+  k *= m;
+  h *= m;
+  h ^= k;
+
+  h ^= h >> 13;
+  h *= m;
+  h ^= h >> 15;
+  return h;
+}
+
+bool ChainedOriginDepot::ChainedOriginDepotNode::is_valid(
+    const args_type &args) {
+  return true;
+}
+
+void ChainedOriginDepot::ChainedOriginDepotNode::store(const args_type &args,
+                                                       u32 other_hash) {
+  here_id = args.here_id;
+  prev_id = args.prev_id;
+}
+
+ChainedOriginDepot::ChainedOriginDepotNode::args_type
+ChainedOriginDepot::ChainedOriginDepotNode::load() const {
+  args_type ret = {here_id, prev_id};
+  return ret;
+}
+
+ChainedOriginDepot::ChainedOriginDepotNode::Handle
+ChainedOriginDepot::ChainedOriginDepotNode::get_handle() {
+  return Handle(this);
+}
+
+ChainedOriginDepot::ChainedOriginDepot() {}
+
+StackDepotStats *ChainedOriginDepot::GetStats() {
+  return chainedOriginDepot.GetStats();
+}
+
+bool ChainedOriginDepot::Put(u32 here_id, u32 prev_id, u32 *new_id) {
+  ChainedOriginDepotDesc desc = {here_id, prev_id};
+  bool inserted;
+  ChainedOriginDepotNode::Handle h = chainedOriginDepot.Put(desc, &inserted);
+  *new_id = h.valid() ? h.id() : 0;
+  return inserted;
+}
+
+u32 ChainedOriginDepot::Get(u32 id, u32 *other) {
+  ChainedOriginDepotDesc desc = chainedOriginDepot.Get(id);
+  *other = desc.prev_id;
+  return desc.here_id;
+}
+
+void ChainedOriginDepot::LockAll() { chainedOriginDepot.LockAll(); }
+
+void ChainedOriginDepot::UnlockAll() { chainedOriginDepot.UnlockAll(); }
+
+}  // namespace __sanitizer

compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt

 include(CompilerRTCompile)
 
 clang_compiler_add_cxx_check()
 
 # FIXME: use SANITIZER_COMMON_SUPPORTED_ARCH here
 filter_available_targets(SANITIZER_UNITTEST_SUPPORTED_ARCH x86_64 i386 mips64 mips64el riscv64)
 if(APPLE)
   darwin_filter_host_archs(SANITIZER_UNITTEST_SUPPORTED_ARCH SANITIZER_UNITTEST_SUPPORTED_ARCH)
 endif()
 
 set(SANITIZER_UNITTESTS
   sanitizer_allocator_test.cpp
   sanitizer_atomic_test.cpp
   sanitizer_bitvector_test.cpp
   sanitizer_bvgraph_test.cpp
+  sanitizer_chained_origin_depot_test.cpp
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_format_interceptor_test.cpp
   sanitizer_ioctl_test.cpp
   sanitizer_libc_test.cpp
   sanitizer_linux_test.cpp
   sanitizer_list_test.cpp

compiler-rt/lib/sanitizer_common/tests/sanitizer_chained_origin_depot_test.cpp

+//===-- sanitizer_chained_origin_depot_test.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 Sanitizer runtime.
+// Tests for sanitizer_chained_origin_depot.h.
+//
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_common/sanitizer_chained_origin_depot.h"
+
+#include "gtest/gtest.h"
+#include "sanitizer_common/sanitizer_internal_defs.h"
+#include "sanitizer_common/sanitizer_libc.h"
+
+namespace __sanitizer {
+
+static ChainedOriginDepot chainedOriginDepot;
+
+TEST(SanitizerCommon, ChainedOriginDepotBasic) {
+  u32 new_id;
+  EXPECT_TRUE(chainedOriginDepot.Put(1, 2, &new_id));
+  u32 prev_id;
+  EXPECT_EQ(chainedOriginDepot.Get(new_id, &prev_id), 1U);
+  EXPECT_EQ(prev_id, 2U);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotAbsent) {
+  u32 prev_id;
+  EXPECT_EQ(0U, chainedOriginDepot.Get(99, &prev_id));
+  EXPECT_EQ(0U, prev_id);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotZeroId) {
+  u32 prev_id;
+  EXPECT_EQ(0U, chainedOriginDepot.Get(0, &prev_id));
+  EXPECT_EQ(0U, prev_id);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotSame) {
+  u32 new_id1;
+  EXPECT_TRUE(chainedOriginDepot.Put(11, 12, &new_id1));
+  u32 new_id2;
+  EXPECT_FALSE(chainedOriginDepot.Put(11, 12, &new_id2));
+  EXPECT_EQ(new_id1, new_id2);
+
+  u32 prev_id;
+  EXPECT_EQ(chainedOriginDepot.Get(new_id1, &prev_id), 11U);
+  EXPECT_EQ(prev_id, 12U);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotDifferent) {
+  u32 new_id1;
+  EXPECT_TRUE(chainedOriginDepot.Put(21, 22, &new_id1));
+  u32 new_id2;
+  EXPECT_TRUE(chainedOriginDepot.Put(21, 23, &new_id2));
+  EXPECT_NE(new_id1, new_id2);
+
+  u32 prev_id;
+  EXPECT_EQ(chainedOriginDepot.Get(new_id1, &prev_id), 21U);
+  EXPECT_EQ(prev_id, 22U);
+  EXPECT_EQ(chainedOriginDepot.Get(new_id2, &prev_id), 21U);
+  EXPECT_EQ(prev_id, 23U);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotStats) {
+  StackDepotStats stats0 = *chainedOriginDepot.GetStats();
+
+  u32 new_id;
+  EXPECT_TRUE(chainedOriginDepot.Put(33, 34, &new_id));
+  StackDepotStats stats1 = *chainedOriginDepot.GetStats();
+  EXPECT_EQ(stats1.n_uniq_ids, stats0.n_uniq_ids + 1);
+  EXPECT_GT(stats1.allocated, stats0.allocated);
+
+  EXPECT_FALSE(chainedOriginDepot.Put(33, 34, &new_id));
+  StackDepotStats stats2 = *chainedOriginDepot.GetStats();
+  EXPECT_EQ(stats2.n_uniq_ids, stats1.n_uniq_ids);
+  EXPECT_EQ(stats2.allocated, stats1.allocated);
+
+  EXPECT_TRUE(chainedOriginDepot.Put(35, 36, &new_id));
+  StackDepotStats stats3 = *chainedOriginDepot.GetStats();
+  EXPECT_EQ(stats3.n_uniq_ids, stats2.n_uniq_ids + 1);
+  EXPECT_GT(stats3.allocated, stats2.allocated);
+}
+
+}  // namespace __sanitizer