1 | //===- LazyAtomicPointer.----------------------------------------*- C++ -*-===// |
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 | #ifndef LLVM_ADT_LAZYATOMICPOINTER_H |
10 | #define LLVM_ADT_LAZYATOMICPOINTER_H |
11 | |
12 | #include "llvm/ADT/STLFunctionalExtras.h" |
13 | #include "llvm/Support/Compiler.h" |
14 | #include <assert.h> |
15 | #include <atomic> |
16 | |
17 | namespace llvm { |
18 | |
19 | /// Atomic pointer that's lock-free, but that can coordinate concurrent writes |
20 | /// from a lazy generator. Should be reserved for cases where concurrent uses of |
21 | /// a generator for the same storage is unlikely. |
22 | /// |
23 | /// The laziness comes in with \a loadOrGenerate(), which lazily calls the |
24 | /// provided generator ONLY when the value is currently \c nullptr. With |
25 | /// concurrent calls, only one generator is called and the rest see that value. |
26 | /// |
27 | /// Most other APIs treat an in-flight \a loadOrGenerate() as if \c nullptr |
28 | /// were stored. APIs that are required to write a value will spin. |
29 | /// |
30 | /// The underlying storage is \a std::atomic<uintptr_t>. |
31 | /// |
32 | /// TODO: In C++20, use std::atomic<T>::wait() instead of spinning and call |
33 | /// std::atomic<T>::notify_all() in \a loadOrGenerate(). |
34 | template <class T> class LazyAtomicPointer { |
35 | static constexpr uintptr_t getNull() { return 0; } |
36 | static constexpr uintptr_t getBusy() { return -1ULL; } |
37 | |
38 | static T *makePointer(uintptr_t Value) { |
39 | assert(Value != getBusy()); |
40 | return Value ? reinterpret_cast<T *>(Value) : nullptr; |
41 | } |
42 | static uintptr_t makeRaw(T *Value) { |
43 | uintptr_t Raw = Value ? reinterpret_cast<uintptr_t>(Value) : getNull(); |
44 | assert(Raw != getBusy()); |
45 | return Raw; |
46 | } |
47 | |
48 | public: |
49 | /// Store a value. Waits for concurrent \a loadOrGenerate() calls. |
50 | void store(T *Value) { return (void)exchange(Value); } |
51 | |
52 | /// Set a value. Return the old value. Waits for concurrent \a |
53 | /// loadOrGenerate() calls. |
54 | T *exchange(T *Value) { |
55 | // Note: the call to compare_exchange_weak() fails "spuriously" if the |
56 | // current value is \a getBusy(), causing the loop to spin. |
57 | T *Old = nullptr; |
58 | while (!compare_exchange_weak(ExistingValue&: Old, NewValue: Value)) { |
59 | } |
60 | return Old; |
61 | } |
62 | |
63 | /// Compare-exchange. Returns \c false if there is a concurrent \a |
64 | /// loadOrGenerate() call, setting \p ExistingValue to \c nullptr. |
65 | bool compare_exchange_weak(T *&ExistingValue, T *NewValue) { |
66 | uintptr_t RawExistingValue = makeRaw(Value: ExistingValue); |
67 | if (Storage.compare_exchange_weak(RawExistingValue, makeRaw(Value: NewValue))) |
68 | return true; |
69 | |
70 | /// Report the existing value as "None" if busy. |
71 | if (RawExistingValue == getBusy()) |
72 | ExistingValue = nullptr; |
73 | else |
74 | ExistingValue = makePointer(Value: RawExistingValue); |
75 | return false; |
76 | } |
77 | |
78 | /// Compare-exchange. Keeps trying if there is a concurrent |
79 | /// \a loadOrGenerate() call. |
80 | bool compare_exchange_strong(T *&ExistingValue, T *NewValue) { |
81 | uintptr_t RawExistingValue = makeRaw(Value: ExistingValue); |
82 | const uintptr_t OriginalRawExistingValue = RawExistingValue; |
83 | if (Storage.compare_exchange_strong(RawExistingValue, makeRaw(Value: NewValue))) |
84 | return true; |
85 | |
86 | /// Keep trying as long as it's busy. |
87 | if (LLVM_UNLIKELY(RawExistingValue == getBusy())) { |
88 | while (RawExistingValue == getBusy()) { |
89 | RawExistingValue = OriginalRawExistingValue; |
90 | if (Storage.compare_exchange_weak(RawExistingValue, makeRaw(Value: NewValue))) |
91 | return true; |
92 | } |
93 | } |
94 | ExistingValue = makePointer(Value: RawExistingValue); |
95 | return false; |
96 | } |
97 | |
98 | /// Return the current stored value. Returns \a None if there is a concurrent |
99 | /// \a loadOrGenerate() in flight. |
100 | T *load() const { |
101 | uintptr_t RawValue = Storage.load(); |
102 | return RawValue == getBusy() ? nullptr : makePointer(Value: RawValue); |
103 | } |
104 | |
105 | /// Get the current value, or call \p Generator to generate a value. |
106 | /// Guarantees that only one thread's \p Generator will run. |
107 | /// |
108 | /// \pre \p Generator doesn't return \c nullptr. |
109 | T &loadOrGenerate(function_ref<T *()> Generator) { |
110 | // Return existing value, if already set. |
111 | uintptr_t Raw = Storage.load(); |
112 | if (Raw != getNull() && Raw != getBusy()) |
113 | return *makePointer(Value: Raw); |
114 | |
115 | // Try to mark as busy, then generate and store a new value. |
116 | if (LLVM_LIKELY(Raw == getNull() && |
117 | Storage.compare_exchange_strong(Raw, getBusy()))) { |
118 | Raw = makeRaw(Value: Generator()); |
119 | assert(Raw != getNull() && "Expected non-null from generator" ); |
120 | Storage.store(i: Raw); |
121 | return *makePointer(Value: Raw); |
122 | } |
123 | |
124 | // Contended with another generator. Wait for it to complete. |
125 | while (Raw == getBusy()) |
126 | Raw = Storage.load(); |
127 | assert(Raw != getNull() && "Expected non-null from competing generator" ); |
128 | return *makePointer(Value: Raw); |
129 | } |
130 | |
131 | explicit operator bool() const { return load(); } |
132 | operator T *() const { return load(); } |
133 | |
134 | T &operator*() const { |
135 | T *P = load(); |
136 | assert(P && "Unexpected null dereference" ); |
137 | return *P; |
138 | } |
139 | T *operator->() const { return &operator*(); } |
140 | |
141 | LazyAtomicPointer() : Storage(0) {} |
142 | LazyAtomicPointer(std::nullptr_t) : Storage(0) {} |
143 | LazyAtomicPointer(T *Value) : Storage(makeRaw(Value)) {} |
144 | LazyAtomicPointer(const LazyAtomicPointer &RHS) |
145 | : Storage(makeRaw(Value: RHS.load())) {} |
146 | |
147 | LazyAtomicPointer &operator=(std::nullptr_t) { |
148 | store(Value: nullptr); |
149 | return *this; |
150 | } |
151 | LazyAtomicPointer &operator=(T *RHS) { |
152 | store(Value: RHS); |
153 | return *this; |
154 | } |
155 | LazyAtomicPointer &operator=(const LazyAtomicPointer &RHS) { |
156 | store(Value: RHS.load()); |
157 | return *this; |
158 | } |
159 | |
160 | private: |
161 | std::atomic<uintptr_t> Storage; |
162 | }; |
163 | |
164 | } // end namespace llvm |
165 | |
166 | #endif // LLVM_ADT_LAZYATOMICPOINTER_H |
167 | |