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
17namespace 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().
34template <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
48public:
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
160private:
161 std::atomic<uintptr_t> Storage;
162};
163
164} // end namespace llvm
165
166#endif // LLVM_ADT_LAZYATOMICPOINTER_H
167

source code of llvm/include/llvm/ADT/LazyAtomicPointer.h