1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// Configurable packed watchpoint table shared by the host and GPU runtimes.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef CSAN_WATCH_H
15#define CSAN_WATCH_H
16
17#include "csan_defs.h"
18#include "sanitizer_common/sanitizer_internal_defs.h"
19
20#if !defined(__has_builtin) || !__has_builtin(__scoped_atomic_load_n)
21#define CSAN_DEFINED_SCOPED_ATOMICS
22#define __scoped_atomic_load_n(P, Order, Scope) __atomic_load_n(P, Order)
23#define __scoped_atomic_store_n(P, V, Order, Scope) \
24 __atomic_store_n(P, V, Order)
25#define __scoped_atomic_compare_exchange_n(P, E, V, Weak, Success, Failure, \
26 Scope) \
27 __atomic_compare_exchange_n(P, E, V, Weak, Success, Failure)
28#define __scoped_atomic_exchange_n(P, V, Order, Scope) \
29 __atomic_exchange_n(P, V, Order)
30#endif
31
32namespace __csan {
33
34using __sanitizer::u32;
35using __sanitizer::u64;
36using __sanitizer::uptr;
37
38template <u32 MaxAccessSize, u32 CheckAdjacentSlots> class WatchpointTable {
39 static_assert(MaxAccessSize && !(MaxAccessSize & (MaxAccessSize - 1)),
40 "maximum access size must be a power of two");
41
42public:
43 static constexpr u32 SizeBits = __builtin_popcount(MaxAccessSize - 1) + 1;
44 static constexpr u32 AddressBits = 64 - 2 - SizeBits;
45 static constexpr u64 AddressMask = (1ull << AddressBits) - 1;
46 static constexpr u32 OverflowEntries = 2 * CheckAdjacentSlots;
47
48private:
49 // Armed watchpoint (u64):
50 // [63] is_write
51 // [62] consumed = 0
52 // [61:AddressBits] access size
53 // [AddressBits-1:0] address key
54 //
55 // Consumed watchpoint (u64):
56 // [63] peer is_write
57 // [62] consumed = 1
58 // [61:AddressBits] peer access size
59 // [AddressBits-1:0] peer PC
60 static constexpr u64 Invalid = 0;
61 static constexpr u64 ConsumedMask = 1ull << 62;
62 static constexpr u64 WriteMask = 1ull << 63;
63 static constexpr u64 SizeMask = ((1ull << SizeBits) - 1) << AddressBits;
64 static constexpr u32 NumSlots = 1 + 2 * CheckAdjacentSlots;
65
66 u64 *Table;
67
68 static constexpr u64 Encode(u64 Address, u32 Size, bool IsWrite) {
69 return (IsWrite ? WriteMask : 0) | (static_cast<u64>(Size) << AddressBits) |
70 (Address & AddressMask);
71 }
72
73 static constexpr bool Decode(u64 Value, u64 &Address, u32 &Size,
74 bool &IsWrite) {
75 if (Value == Invalid || (Value & ConsumedMask))
76 return false;
77 IsWrite = Value & WriteMask;
78 Size = (Value & SizeMask) >> AddressBits;
79 Address = Value & AddressMask;
80 return true;
81 }
82
83 static constexpr bool Overlaps(u64 A, u32 ASize, u64 B, u32 BSize) {
84 return A < B + BSize && B < A + ASize;
85 }
86
87public:
88 constexpr WatchpointTable(u64 *Table) : Table(Table) {}
89
90 static constexpr u32 EncodeSize(u32 Size) {
91 return Size < MaxAccessSize ? Size : MaxAccessSize;
92 }
93
94 u64 *Find(u64 Key, u32 Size, bool ExpectWrite, u32 Slot, u64 &Encoded) const {
95 for (u32 I = 0; I < NumSlots; ++I) {
96 u64 *Watchpoint = &Table[Slot + I];
97 Encoded = __scoped_atomic_load_n(Watchpoint, __ATOMIC_RELAXED,
98 __MEMORY_SCOPE_DEVICE);
99
100 u64 Address;
101 u32 WatchSize;
102 bool IsWrite;
103 if (!Decode(Value: Encoded, Address, Size&: WatchSize, IsWrite))
104 continue;
105 if (ExpectWrite && !IsWrite)
106 continue;
107 if (Overlaps(A: Address, ASize: WatchSize, B: Key, BSize: Size))
108 return Watchpoint;
109 }
110 return nullptr;
111 }
112
113 u64 *Insert(u64 Key, u32 Size, bool IsWrite, u32 Slot) const {
114 const u64 Encoded = Encode(Address: Key, Size, IsWrite);
115 for (u32 I = 0; I < NumSlots; ++I) {
116 u32 Index = Slot + ((I + CheckAdjacentSlots) % NumSlots);
117 u64 *Watchpoint = &Table[Index];
118 u64 Expected = Invalid;
119 if (__scoped_atomic_compare_exchange_n(
120 Watchpoint, &Expected, Encoded, false, __ATOMIC_RELAXED,
121 __ATOMIC_RELAXED, __MEMORY_SCOPE_DEVICE))
122 return Watchpoint;
123 }
124 return nullptr;
125 }
126
127 bool TryConsume(u64 *Watchpoint, u64 Encoded, uptr PC, bool IsWrite,
128 u32 Size) const {
129 u64 Consumed = ConsumedMask | (IsWrite ? WriteMask : 0) |
130 (static_cast<u64>(EncodeSize(Size)) << AddressBits) |
131 (PC & AddressMask);
132 return __scoped_atomic_compare_exchange_n(
133 Watchpoint, &Encoded, Consumed, false, __ATOMIC_RELAXED,
134 __ATOMIC_RELAXED, __MEMORY_SCOPE_DEVICE);
135 }
136
137 bool Consume(u64 *Watchpoint, void *&Peer, int &PeerAccess,
138 u32 &PeerSize) const {
139 u64 Old = __scoped_atomic_exchange_n(
140 Watchpoint, ConsumedMask, __ATOMIC_RELAXED, __MEMORY_SCOPE_DEVICE);
141 Peer = reinterpret_cast<void *>(static_cast<uptr>(Old & AddressMask));
142 PeerAccess = (Old & WriteMask) ? CSAN_ACCESS_WRITE : 0;
143 PeerSize = (Old & SizeMask) >> AddressBits;
144 return !(Old & ConsumedMask);
145 }
146
147 void Remove(u64 *Watchpoint) const {
148 __scoped_atomic_store_n(Watchpoint, Invalid, __ATOMIC_RELAXED,
149 __MEMORY_SCOPE_DEVICE);
150 }
151};
152
153} // namespace __csan
154
155#ifdef CSAN_DEFINED_SCOPED_ATOMICS
156#undef __scoped_atomic_load_n
157#undef __scoped_atomic_store_n
158#undef __scoped_atomic_compare_exchange_n
159#undef __scoped_atomic_exchange_n
160#undef CSAN_DEFINED_SCOPED_ATOMICS
161#endif
162
163#endif // CSAN_WATCH_H
164