[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

16

Please fix this lint

44

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

47

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

59

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

16

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

44

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

16

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/CMakeLists.txt

 include_directories(..)
 
 # Runtime library sources and build flags.
 set(MSAN_RTL_SOURCES
   msan.cpp
   msan_allocator.cpp
-  msan_chained_origin_depot.cpp
   msan_interceptors.cpp
   msan_linux.cpp
   msan_report.cpp
   msan_thread.cpp
   msan_poisoning.cpp
   )
 
 set(MSAN_RTL_CXX_SOURCES
   msan_new_delete.cpp
   )
 
 set(MSAN_RTL_HEADERS
   msan.h
   msan_allocator.h
-  msan_chained_origin_depot.h
   msan_flags.h
   msan_flags.inc
   msan_interface_internal.h
   msan_origin.h
   msan_poisoning.h
   msan_report.h
   msan_thread.h)
 

compiler-rt/lib/msan/msan.cpp

 //===-- msan.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.
 //
 // MemorySanitizer runtime.
 //===----------------------------------------------------------------------===//
 
 #include "msan.h"
-#include "msan_chained_origin_depot.h"
+
 #include "msan_origin.h"
+#include "msan_poisoning.h"
 #include "msan_report.h"
 #include "msan_thread.h"
-#include "msan_poisoning.h"
 #include "sanitizer_common/sanitizer_atomic.h"
+#include "sanitizer_common/sanitizer_chained_origin_depot.h"
 #include "sanitizer_common/sanitizer_common.h"
-#include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_flag_parser.h"
+#include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_libc.h"
 #include "sanitizer_common/sanitizer_procmaps.h"
+#include "sanitizer_common/sanitizer_stackdepot.h"
 #include "sanitizer_common/sanitizer_stacktrace.h"
 #include "sanitizer_common/sanitizer_symbolizer.h"
-#include "sanitizer_common/sanitizer_stackdepot.h"
 #include "ubsan/ubsan_flags.h"
 #include "ubsan/ubsan_init.h"
 
 // ACHTUNG! No system header includes in this file.
 
 using namespace __sanitizer;
 
 // Globals.

compiler-rt/lib/msan/msan_interceptors.cpp

 // Interceptors for standard library functions.
 //
 // FIXME: move as many interceptors as possible into
 // sanitizer_common/sanitizer_common_interceptors.h
 //===----------------------------------------------------------------------===//
 
 #include "interception/interception.h"
 #include "msan.h"
-#include "msan_chained_origin_depot.h"
 #include "msan_origin.h"
+#include "msan_poisoning.h"
 #include "msan_report.h"
 #include "msan_thread.h"
-#include "msan_poisoning.h"
-#include "sanitizer_common/sanitizer_platform_limits_posix.h"
-#include "sanitizer_common/sanitizer_platform_limits_netbsd.h"
 #include "sanitizer_common/sanitizer_allocator.h"
 #include "sanitizer_common/sanitizer_allocator_interface.h"
 #include "sanitizer_common/sanitizer_allocator_internal.h"
 #include "sanitizer_common/sanitizer_atomic.h"
+#include "sanitizer_common/sanitizer_chained_origin_depot.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_errno.h"
-#include "sanitizer_common/sanitizer_stackdepot.h"
 #include "sanitizer_common/sanitizer_libc.h"
 #include "sanitizer_common/sanitizer_linux.h"
+#include "sanitizer_common/sanitizer_platform_limits_netbsd.h"
+#include "sanitizer_common/sanitizer_platform_limits_posix.h"
+#include "sanitizer_common/sanitizer_stackdepot.h"
 #include "sanitizer_common/sanitizer_tls_get_addr.h"
 #include "sanitizer_common/sanitizer_vector.h"
 
 #if SANITIZER_NETBSD
 #define fstat __fstat50
 #define gettimeofday __gettimeofday50
 #define getrusage __getrusage50
 #define tzset __tzset50

compiler-rt/lib/msan/msan_origin.h

 //===-- msan_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
 //
 //===----------------------------------------------------------------------===//
 //
 // Origin id utils.
 //===----------------------------------------------------------------------===//
 #ifndef MSAN_ORIGIN_H
 #define MSAN_ORIGIN_H
 
+#include "sanitizer_common/sanitizer_chained_origin_depot.h"
 #include "sanitizer_common/sanitizer_stackdepot.h"
-#include "msan_chained_origin_depot.h"
 
 namespace __msan {
 
 // Origin handling.
 //
 // Origin is a 32-bit identifier that is attached to any uninitialized value in
 // the program and describes, more or less exactly, how this memory came to be
 // uninitialized.
static Origin CreateHeapOrigin(StackTrace *stack) {
     CHECK((stack_id & kHeapIdMask) == stack_id);
     return Origin(stack_id);
   }
 
   static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) {
     int depth = prev.isChainedOrigin() ? prev.depth() : 0;
     // depth is the length of the chain minus 1.
     // origin_history_size of 0 means unlimited depth.
     if (flags()->origin_history_size > 0) {
       if (depth + 1 >= flags()->origin_history_size) {
         return prev;
       } else {
         ++depth;
         CHECK(depth < (1 << kDepthBits));
       }
     }
 
     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 = ChainedOriginDepotPut(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((1 << kHeapShift) | (depth << kDepthShift) | chained_id);
   }
 
   static Origin FromRawId(u32 id) {
     return Origin(id);
   }

compiler-rt/lib/msan/msan_report.cpp

 //===-- msan_report.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.
 //
 // Error reporting.
 //===----------------------------------------------------------------------===//
 
+#include "msan_report.h"
+
 #include "msan.h"
-#include "msan_chained_origin_depot.h"
 #include "msan_origin.h"
-#include "msan_report.h"
 #include "sanitizer_common/sanitizer_allocator_internal.h"
+#include "sanitizer_common/sanitizer_chained_origin_depot.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_mutex.h"
 #include "sanitizer_common/sanitizer_report_decorator.h"
 #include "sanitizer_common/sanitizer_stackdepot.h"
 #include "sanitizer_common/sanitizer_symbolizer.h"
 
 using namespace __sanitizer;

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

-//===-- msan_chained_origin_depot.h --------------------------*- C++ -*-===//
+//===-- 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 MSAN_CHAINED_ORIGIN_DEPOT_H
-#define MSAN_CHAINED_ORIGIN_DEPOT_H
 
-#include "sanitizer_common/sanitizer_common.h"
+#ifndef SANITIZER_CHAINED_ORIGIN_DEPOT_H
+#define SANITIZER_CHAINED_ORIGIN_DEPOT_H
 
-namespace __msan {
+#include "sanitizer_common.h"
 
+namespace __sanitizer {
+
+// 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.
 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
+}  // namespace __sanitizer
 
-#endif  // MSAN_CHAINED_ORIGIN_DEPOT_H
+#endif  // SANITIZER_CHAINED_ORIGIN_DEPOT_H

compiler-rt/lib/sanitizer_common/sanitizer_chained_origin_depot.cpp

-//===-- msan_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 "msan_chained_origin_depot.h"
+#include "sanitizer_chained_origin_depot.h"
 
-#include "sanitizer_common/sanitizer_stackdepotbase.h"
+#include "sanitizer_stackdepotbase.h"
 
-namespace __msan {
+namespace __sanitizer {
 
 struct ChainedOriginDepotDesc {
   u32 here_id;
   u32 prev_id;
 };
 
 struct ChainedOriginDepotNode {
   ChainedOriginDepotNode *link;
struct Handle {
     int prev_id() { return node_->prev_id; }
   };
 
   Handle get_handle() { return Handle(this); }
 
   typedef Handle handle_type;
 };
 
 static StackDepotBase<ChainedOriginDepotNode, 4, 20> 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;
 }
 
 // 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;
 }
 
-void ChainedOriginDepotLockAll() {
-  chainedOriginDepot.LockAll();
-}
+void ChainedOriginDepotLockAll() { chainedOriginDepot.LockAll(); }
 
-void ChainedOriginDepotUnlockAll() {
-  chainedOriginDepot.UnlockAll();
-}
+void ChainedOriginDepotUnlockAll() { chainedOriginDepot.UnlockAll(); }
 
-} // namespace __msan
+}  // 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 {
+
+TEST(SanitizerCommon, ChainedOriginDepotBasic) {
+  u32 new_id;
+  EXPECT_TRUE(ChainedOriginDepotPut(1, 2, &new_id));
+  u32 prev_id;
+  EXPECT_EQ(ChainedOriginDepotGet(new_id, &prev_id), 1U);
+  EXPECT_EQ(prev_id, 2U);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotAbsent) {
+  u32 prev_id;
+  EXPECT_EQ(0U, ChainedOriginDepotGet(99, &prev_id));
+  EXPECT_EQ(0U, prev_id);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotZeroId) {
+  u32 prev_id;
+  EXPECT_EQ(0U, ChainedOriginDepotGet(0, &prev_id));
+  EXPECT_EQ(0U, prev_id);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotSame) {
+  u32 new_id1;
+  EXPECT_TRUE(ChainedOriginDepotPut(1, 2, &new_id1));
+  u32 new_id2;
+  EXPECT_FALSE(ChainedOriginDepotPut(1, 2, &new_id2));
+  EXPECT_EQ(new_id1, new_id2);
+
+  u32 prev_id;
+  EXPECT_EQ(ChainedOriginDepotGet(new_id1, &prev_id), 1U);
+  EXPECT_EQ(prev_id, 2U);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotDifferent) {
+  u32 new_id1;
+  EXPECT_TRUE(ChainedOriginDepotPut(1, 2, &new_id1));
+  u32 new_id2;
+  EXPECT_TRUE(ChainedOriginDepotPut(1, 3, &new_id2));
+  EXPECT_NE(new_id1, new_id2);
+}
+
+TEST(SanitizerCommon, ChainedOriginDepotStats) {
+  StackDepotStats stats0 = *ChainedOriginDepotGetStats();
+
+  u32 new_id;
+  EXPECT_TRUE(ChainedOriginDepotPut(3, 4, &new_id));
+  StackDepotStats stats1 = *ChainedOriginDepotGetStats();
+  EXPECT_EQ(stats1.n_uniq_ids, stats0.n_uniq_ids + 1);
+  EXPECT_GT(stats1.allocated, stats0.allocated);
+
+  EXPECT_FALSE(ChainedOriginDepotPut(3, 4, &new_id));
+  StackDepotStats stats2 = *ChainedOriginDepotGetStats();
+  EXPECT_EQ(stats2.n_uniq_ids, stats1.n_uniq_ids);
+  EXPECT_EQ(stats2.allocated, stats1.allocated);
+
+  EXPECT_TRUE(ChainedOriginDepotPut(5, 6, &new_id));
+  StackDepotStats stats3 = *ChainedOriginDepotGetStats();
+  EXPECT_EQ(stats3.n_uniq_ids, stats2.n_uniq_ids + 1);
+  EXPECT_GT(stats3.allocated, stats2.allocated);
+}
+
+}  // namespace __sanitizer