Realm
A distributed, event-based tasking library
Loading...
Searching...
No Matches
event_impl.h
Go to the documentation of this file.
1/*
2 * Copyright 2025 Stanford University, NVIDIA Corporation
3 * SPDX-License-Identifier: Apache-2.0
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18// Event/UserEvent implementations for Realm
19
20#ifndef REALM_EVENT_IMPL_H
21#define REALM_EVENT_IMPL_H
22
23#include "realm/event.h"
24#include "realm/id.h"
25#include "realm/nodeset.h"
26#include "realm/faults.h"
27
28#include "realm/network.h"
29#include <realm/activemsg.h>
30
31#include "realm/lists.h"
32#include "realm/threads.h"
33#include "realm/logging.h"
34#include "realm/redop.h"
35#include "realm/bgwork.h"
36#include "realm/dynamic_table.h"
37
38#include <vector>
39#include <map>
40#include <memory>
41#include <deque>
42#include <optional>
43
44namespace Realm {
45
46 class GenEventImpl;
47
48 extern Logger log_poison; // defined in event_impl.cc
49 class ProcessorImpl; // defined in proc_impl.h
50
52 public:
53 virtual ~EventWaiter(void) {}
54 virtual void event_triggered(bool poisoned, TimeLimit work_until) = 0;
55 virtual void print(std::ostream &os) const = 0;
56 virtual Event get_finish_event(void) const = 0;
57
63 };
64
65 // triggering events can often result in recursive expansion of work -
66 // this widget flattens the call stack and defers excessive triggers
67 // to avoid stalling the initial triggerer longer than they want
85
86 // parent class of GenEventImpl and BarrierImpl
87 class EventImpl {
88 public:
89 typedef unsigned gen_t;
90
91 EventImpl(void);
92 virtual ~EventImpl(void);
93
94 // test whether an event has triggered without waiting
95 virtual bool has_triggered(gen_t needed_gen, bool &poisoned) = 0;
96
97 virtual void subscribe(gen_t subscribe_gen) = 0;
98
99 // causes calling thread to block until event has occurred
100 // void wait(Event::gen_t needed_gen);
101
102 virtual void external_wait(gen_t needed_gen, bool &poisoned) = 0;
103 virtual bool external_timedwait(gen_t needed_gen, bool &poisoned,
104 long long max_ns) = 0;
105
106 // helper to create the Event for an arbitrary generation
108
109 virtual bool add_waiter(gen_t needed_gen,
110 EventWaiter *waiter /*, bool pre_subscribed = false*/) = 0;
111
112 static bool add_waiter(Event needed, EventWaiter *waiter);
113
114 // use this sparingly - it has to hunt through waiter lists while
115 // holding locks
116 virtual bool remove_waiter(gen_t needed_gen, EventWaiter *waiter) = 0;
117
118 static bool detect_event_chain(Event search_from, Event target, int max_depth,
119 bool print_chain);
120
121 public:
125 };
126
127 class GenEventImpl;
128
130 public:
136
139
140 bool is_active(void) const;
141
142 void prepare_merger(Event _finish_event, bool _ignore_faults,
143 std::optional<size_t> expected_events = std::optional<size_t>(),
144 FaultPropagation _fault_propagation = FaultPropagation::EARLY);
145
146 void add_precondition(Event wait_for);
147
148 void arm_merger(void);
149
151 public:
152 MergeEventPrecondition(void) = default;
155 virtual ~MergeEventPrecondition(void) = default;
156
157 public:
159
160 virtual void event_triggered(bool poisoned, TimeLimit work_until);
161 virtual void print(std::ostream &os) const;
162 virtual Event get_finish_event(void) const;
163 };
164
165 // as an alternative to add_precondition, get_next_precondition can
166 // be used to get a precondition that can manually be added to a waiter
167 // list
169
170 // number of preconditions a merge can have before the merger has to
171 // heap-allocate overflow storage
172 static constexpr size_t MAX_INLINE_PRECONDITIONS = 6;
173
174 protected:
175 void precondition_triggered(bool poisoned, TimeLimit work_until,
176 MergeEventPrecondition *precondition = nullptr);
177
179
188
190 // storage for preconditions beyond MAX_INLINE_PRECONDITIONS - once handed
191 // out, a precondition's address is registered on another event's waiter
192 // list, so this container must never relocate its elements: std::deque
193 // does not invalidate references on growth (std::vector would)
194 // the deque itself is heap-allocated lazily on the first overflow and
195 // released when the merge completes - a default-constructed std::deque is
196 // not free (libstdc++ eagerly allocates its map and one 512-byte node),
197 // and since GenEventImpls are materialized in bulk by DynamicTable leaves
198 // that cost was paid for every event slot on every node even though very
199 // few events ever merge more than MAX_INLINE_PRECONDITIONS inputs
200 std::unique_ptr<std::deque<MergeEventPrecondition>> overflow_preconditions;
202 };
203
205 public:
206 virtual ~EventCommunicator() = default;
207
208 virtual void trigger(Event event, NodeID owner, bool poisoned);
209
210 virtual void update(Event event, NodeSet to_update,
211 span<EventImpl::gen_t> poisoned_generations);
212
213 virtual void update(Event event, NodeID to_update,
214 span<EventImpl::gen_t> poisoned_generations);
215
216 virtual void subscribe(Event event, NodeID owner,
217 EventImpl::gen_t previous_subscribe_gen);
218 };
219
220 class GenEventImpl : public EventImpl {
221 public:
223
225 GenEventImpl(EventTriggerNotifier *_event_triggerer, EventCommunicator *_event_comm);
227
228 void init(ID _me, unsigned _init_owner);
229
230 static GenEventImpl *
231 create_genevent(void); // TODO: remove this once we get rid of get_runtime()
232
234
235 static ID make_id(const GenEventImpl &dummy, int owner, ID::IDType index)
236 {
237 return ID::make_event(owner, index, 0);
238 }
239
240 // get the Event (id+generation) for the current (i.e. untriggered) generation
241 Event current_event(void) const;
242
243 // test whether an event has triggered without waiting
244 virtual bool has_triggered(gen_t needed_gen, bool &poisoned);
245
246 virtual void subscribe(gen_t subscribe_gen);
247 void handle_remote_subscription(NodeID sender, gen_t subscribe_gen,
248 gen_t previous_subscribe_gen);
249
250 virtual void external_wait(gen_t needed_gen, bool &poisoned);
251 virtual bool external_timedwait(gen_t needed_gen, bool &poisoned, long long max_ns);
252
253 virtual bool add_waiter(gen_t needed_gen, EventWaiter *waiter);
254
255 // use this sparingly - it has to hunt through waiter lists while
256 // holding locks
257 virtual bool remove_waiter(gen_t needed_gen, EventWaiter *waiter);
258
259 // creates an event that won't trigger until all input events have
260 static Event merge_events(span<const Event> wait_for, bool ignore_faults);
263 Event ev6 = Event::NO_EVENT);
264 static Event ignorefaults(Event wait_for);
265
266 // record that the event has triggered and notify anybody who cares
267 bool trigger(gen_t gen_triggered, int trigger_node, bool poisoned,
268 TimeLimit work_until);
269
270 // helper for triggering with an Event (which must be backed by a GenEventImpl)
271 static void trigger(Event e, bool poisoned);
272 static void trigger(Event e, bool poisoned, TimeLimit work_until);
273
274 // process an update message from the owner
275 void process_update(gen_t current_gen, const gen_t *new_poisoned_generations,
276 int new_poisoned_count, TimeLimit work_until);
277
278 // Set the operation that will trigger this event's generation. On success the
279 // event takes ownership of the caller's reference to 'op' and releases it when
280 // 'gen' triggers, whether or not this node owns the event (see trigger()).
281 // Returns false if 'gen' has already been observed to trigger, in which case the
282 // caller keeps its reference.
284 // Get the operation that will trigger this event's generation.
285 // The returned operation's reference is incremented and must be removed by the
286 // caller.
288
289 // initializes the GenEventImpls in a DynamicTable leaf - every event shares the
290 // runtime's single EventTriggerNotifier and EventCommunicator, neither of
291 // which is owned by the events
295
296 GenEventImplAllocator(void) = default;
297
302
303 // the leaf's element array has already default-constructed the event, so
304 // just hand it the shared notifier and communicator and initialize it
305 // rather than destroying and rebuilding it
306 void construct(GenEventImpl *storage, ID id, unsigned owner) const
307 {
308 storage->event_triggerer = triggerer;
309 storage->event_comm = communicator;
310 storage->init(id, owner);
311 }
312 };
313
314 public: // protected:
315 // these state variables are monotonic, so can be checked without a lock for
316 // early-out conditions
320
321 bool is_generation_poisoned(gen_t gen) const; // helper function - linear search
322
323 // this is only manipulated when the event is "idle"
325
326 // used for merge_events and delayed UserEvent triggers
328
330 // not owned - the runtime holds a single stateless EventCommunicator that all
331 // events share (it is reached through a pointer only so that tests can
332 // substitute a mock), so an event must never heap-allocate one of its own:
333 // GenEventImpls are materialized in bulk by DynamicTable leaves and any
334 // per-event allocation is multiplied by millions of event slots on large runs
336
337 // everything below here protected by this mutex
339
340 // The operation that will trigger generation 'current_trigger_op_gen' - the event
341 // holds a reference to it (see set_trigger_op). For a remote event our view of
342 // 'generation' can lag the owner's, so the generation is tracked explicitly.
345
346 // the flags below are grouped here so that they pack into the word above
347 // instead of each occupying its own padded 8 bytes - every byte of a
348 // GenEventImpl is multiplied by millions of event slots on large runs
349 // tracks whether lagging_view holds any local triggers - written under the
350 // mutex, but also read without it as an early-out in has_triggered()
351 bool has_local_triggers = false;
352 // external waiters on this node are notified via a condition variable
354 // these resolve a race condition between the early trigger of a
355 // poisoned merge and the last precondition
357
358 // local waiters for the "current" generation (the one after 'generation') -
359 // waiters for later generations live in the lazily-allocated lagging-view
360 // state below
362
363 // external waiters block on a kernel mutex/condvar pair (a kernel mutex is
364 // needed for timedwait) - the pair is allocated by the first external wait
365 // on the event and then kept for the life of the event: very few events are
366 // ever waited on from outside a Realm thread, and embedding the pair cost
367 // 136 bytes and two pthread initializations for every event
376 // allocated (under 'mutex') before has_external_waiters is first set, so any
377 // path that sees the flag can rely on the pair existing
378 std::unique_ptr<ExternalWaiterSync> external_waiter_sync;
379 // returns the pair, allocating it on first use - caller must hold 'mutex'
381
382 // remote waiters are kept in a bitmask for the current generation - this is
383 // only maintained on the owner, who never has to worry about more than one
384 // generation
386
387 // we'll set an upper bound on how many times any given event can be poisoned - this
388 // keeps update messages from growing without bound
389 static const int POISONED_GENERATION_LIMIT = 16;
390
391 // note - we don't bother sorting the list below - the overhead of a binary search
392 // dominates for short lists
393 // we also can't use an STL vector because reallocation prevents us from reading the
394 // list without the lock - instead we'll allocate the max size if/when we need
395 // any space
397
398 // state that only a non-owner needs, and only while it is dealing with
399 // generations beyond its current view of the event: waiters for generations
400 // past the next one, and the outcomes of generations this node triggered
401 // itself before the owner has confirmed them. Owner-side events never touch
402 // it and non-owners only need it briefly, so it is allocated on first use and
403 // released as soon as both maps are empty again - embedding the two maps cost
404 // 96 bytes per event under libstdc++ and, under MSVC's STL, two heap
405 // allocations per event for their sentinel nodes
407 // local waiters for "future" generations (i.e. ones ahead of what we've
408 // heard about from the owner), by generation
409 std::map<gen_t, EventWaiter::EventWaiterList> future_local_waiters;
410 // local triggerings - if we've triggered/poisoned generations ourselves, we
411 // need to give consistent answers for them until our view of the
412 // distributed event catches up - the value is whether the generation was
413 // poisoned
414 std::map<gen_t, bool> local_triggers;
415 };
416 // protected by 'mutex' - released whenever both maps become empty
417 std::unique_ptr<LaggingViewState> lagging_view;
418 // caller must hold 'mutex' - allocates the state on first use
420 // caller must hold 'mutex' - releases the state if both maps are empty
422 // caller must hold 'mutex' - reports whether this node triggered 'gen' itself
423 // and, if so, whether it was poisoned
424 bool find_local_trigger(gen_t gen, bool &poisoned) const;
425
426 friend class EventMerger;
427 };
428}; // namespace Realm
429
430#include "realm/event_impl.inl"
431
432#endif // ifndef REALM_EVENT_IMPL_H
BackgroundWorkItem(const std::string &_name)
Definition threads.h:428
Definition event_impl.h:204
virtual void trigger(Event event, NodeID owner, bool poisoned)
virtual void update(Event event, NodeID to_update, span< EventImpl::gen_t > poisoned_generations)
virtual void subscribe(Event event, NodeID owner, EventImpl::gen_t previous_subscribe_gen)
virtual ~EventCommunicator()=default
virtual void update(Event event, NodeSet to_update, span< EventImpl::gen_t > poisoned_generations)
virtual bool remove_waiter(gen_t needed_gen, EventWaiter *waiter)=0
NodeID owner
Definition event_impl.h:124
virtual bool has_triggered(gen_t needed_gen, bool &poisoned)=0
Event make_event(gen_t gen) const
virtual void external_wait(gen_t needed_gen, bool &poisoned)=0
virtual bool external_timedwait(gen_t needed_gen, bool &poisoned, long long max_ns)=0
unsigned gen_t
Definition event_impl.h:89
virtual void subscribe(gen_t subscribe_gen)=0
static bool detect_event_chain(Event search_from, Event target, int max_depth, bool print_chain)
ProcessorImpl * owning_processor
Definition event_impl.h:123
static bool add_waiter(Event needed, EventWaiter *waiter)
ID me
Definition event_impl.h:122
virtual bool add_waiter(gen_t needed_gen, EventWaiter *waiter)=0
virtual ~EventImpl(void)
virtual void event_triggered(bool poisoned, TimeLimit work_until)
EventMerger * merger
Definition event_impl.h:158
MergeEventPrecondition(const MergeEventPrecondition &)=delete
MergeEventPrecondition(MergeEventPrecondition &&)=delete
virtual ~MergeEventPrecondition(void)=default
virtual Event get_finish_event(void) const
virtual void print(std::ostream &os) const
static constexpr size_t MAX_INLINE_PRECONDITIONS
Definition event_impl.h:172
FaultPropagation
Definition event_impl.h:132
@ AFTER_PRECONDITIONS
Definition event_impl.h:134
@ EARLY
Definition event_impl.h:133
GenEventImpl * event_impl
Definition event_impl.h:180
bool ignore_faults
Definition event_impl.h:183
void arm_merger(void)
atomic< int > faults_observed
Definition event_impl.h:187
MergeEventPrecondition * get_next_precondition(void)
EventImpl::gen_t finish_gen
Definition event_impl.h:181
bool recycle_preconditions
Definition event_impl.h:185
void add_precondition(Event wait_for)
unsigned precondition_offset
Definition event_impl.h:182
std::unique_ptr< std::deque< MergeEventPrecondition > > overflow_preconditions
Definition event_impl.h:200
EventMerger(GenEventImpl *_event_impl)
EventWaiter::EventWaiterList free_preconditions
Definition event_impl.h:201
atomic< int > count_needed
Definition event_impl.h:186
MergeEventPrecondition inline_preconditions[MAX_INLINE_PRECONDITIONS]
Definition event_impl.h:189
void prepare_merger(Event _finish_event, bool _ignore_faults, std::optional< size_t > expected_events=std::optional< size_t >(), FaultPropagation _fault_propagation=FaultPropagation::EARLY)
FaultPropagation fault_propagation
Definition event_impl.h:184
void precondition_triggered(bool poisoned, TimeLimit work_until, MergeEventPrecondition *precondition=nullptr)
bool is_active(void) const
Definition event_impl.h:68
Mutex mutex
Definition event_impl.h:78
virtual bool do_work(TimeLimit work_until)
EventWaiter::EventWaiterList delayed_poisoned
Definition event_impl.h:80
void trigger_event_waiters(EventWaiter::EventWaiterList &to_trigger, bool poisoned, TimeLimit trigger_until)
static EventWaiter::EventWaiterList * nested_poisoned
Definition event_impl.h:83
EventWaiter::EventWaiterList delayed_normal
Definition event_impl.h:79
static EventWaiter::EventWaiterList * nested_normal
Definition event_impl.h:82
Definition event_impl.h:51
virtual ~EventWaiter(void)
Definition event_impl.h:53
REALM_PMTA_DEFN(EventWaiter, IntrusiveListLink< EventWaiter >, ew_list_link)
IntrusiveListLink< EventWaiter > ew_list_link
Definition event_impl.h:58
virtual Event get_finish_event(void) const =0
IntrusiveList< EventWaiter, REALM_PMTA_USE(EventWaiter, ew_list_link), DummyLock > EventWaiterList
Definition event_impl.h:62
virtual void event_triggered(bool poisoned, TimeLimit work_until)=0
virtual void print(std::ostream &os) const =0
Definition event.h:50
static const Event NO_EVENT
The value should be usued to initialize an event handle. NO_EVENT is always in has triggered state .
Definition event.h:71
Definition event_impl.h:220
Operation * current_trigger_op
Definition event_impl.h:343
gen_t current_trigger_op_gen
Definition event_impl.h:344
bool is_generation_poisoned(gen_t gen) const
static void trigger(Event e, bool poisoned, TimeLimit work_until)
atomic< gen_t > gen_subscribed
Definition event_impl.h:318
std::unique_ptr< LaggingViewState > lagging_view
Definition event_impl.h:417
static Event merge_events(span< const Event > wait_for, bool ignore_faults)
virtual bool add_waiter(gen_t needed_gen, EventWaiter *waiter)
bool set_trigger_op(gen_t gen, Operation *op)
void init(ID _me, unsigned _init_owner)
gen_t * poisoned_generations
Definition event_impl.h:396
NodeSet remote_waiters
Definition event_impl.h:385
static Event ignorefaults(Event wait_for)
static const ID::ID_Types ID_TYPE
Definition event_impl.h:222
Operation * get_trigger_op(gen_t gen)
bool trigger(gen_t gen_triggered, int trigger_node, bool poisoned, TimeLimit work_until)
void handle_remote_subscription(NodeID sender, gen_t subscribe_gen, gen_t previous_subscribe_gen)
friend class EventMerger
Definition event_impl.h:426
bool free_list_insertion_delayed
Definition event_impl.h:356
virtual bool remove_waiter(gen_t needed_gen, EventWaiter *waiter)
GenEventImpl(EventTriggerNotifier *_event_triggerer, EventCommunicator *_event_comm)
static void trigger(Event e, bool poisoned)
static Event merge_events(Event ev1, Event ev2, Event ev3=Event::NO_EVENT, Event ev4=Event::NO_EVENT, Event ev5=Event::NO_EVENT, Event ev6=Event::NO_EVENT)
virtual void subscribe(gen_t subscribe_gen)
EventCommunicator * event_comm
Definition event_impl.h:335
EventTriggerNotifier * event_triggerer
Definition event_impl.h:329
EventWaiter::EventWaiterList current_local_waiters
Definition event_impl.h:361
bool has_external_waiters
Definition event_impl.h:353
Event current_event(void) const
static GenEventImpl * create_genevent(void)
EventMerger merger
Definition event_impl.h:327
virtual bool has_triggered(gen_t needed_gen, bool &poisoned)
LaggingViewState & get_lagging_view(void)
atomic< int > num_poisoned_generations
Definition event_impl.h:319
static const int POISONED_GENERATION_LIMIT
Definition event_impl.h:389
bool has_local_triggers
Definition event_impl.h:351
static ID make_id(const GenEventImpl &dummy, int owner, ID::IDType index)
Definition event_impl.h:235
virtual bool external_timedwait(gen_t needed_gen, bool &poisoned, long long max_ns)
void process_update(gen_t current_gen, const gen_t *new_poisoned_generations, int new_poisoned_count, TimeLimit work_until)
Mutex mutex
Definition event_impl.h:338
bool find_local_trigger(gen_t gen, bool &poisoned) const
virtual void external_wait(gen_t needed_gen, bool &poisoned)
GenEventImpl * next_free
Definition event_impl.h:324
atomic< gen_t > generation
Definition event_impl.h:317
std::unique_ptr< ExternalWaiterSync > external_waiter_sync
Definition event_impl.h:378
void release_lagging_view_if_empty(void)
ExternalWaiterSync & get_external_waiter_sync(void)
static GenEventImpl * create_genevent(RuntimeImpl *runtime_impl)
Definition id.h:30
static ID make_event(unsigned creator_node, unsigned gen_event_idx, unsigned generation)
ID_Types
Definition id.h:250
@ ID_EVENT
Definition id.h:253
::realm_id_t IDType
Definition id.h:32
Definition lists.h:66
Definition mutex.h:273
KernelCondVar CondVar
Definition mutex.h:278
Definition logging.h:52
Definition nodeset.h:117
Definition operation.h:32
Definition proc_impl.h:51
Definition runtime_impl.h:271
Definition timers.h:129
Definition atomics.h:31
Definition utils.h:84
#define REALM_PMTA_USE(structtype, name)
Definition lists.h:42
Definition activemsg.h:42
Logger log_poison
UnfairMutex Mutex
Definition mutex.h:68
int NodeID
Definition nodeset.h:40
Definition event_impl.h:368
KernelMutex mutex
Definition event_impl.h:373
KernelMutex::CondVar condvar
Definition event_impl.h:374
ExternalWaiterSync(void)
Definition event_impl.h:369
void construct(GenEventImpl *storage, ID id, unsigned owner) const
Definition event_impl.h:306
EventCommunicator * communicator
Definition event_impl.h:294
GenEventImplAllocator(EventTriggerNotifier *t, EventCommunicator *c)
Definition event_impl.h:298
EventTriggerNotifier * triggerer
Definition event_impl.h:293
Definition event_impl.h:406
std::map< gen_t, bool > local_triggers
Definition event_impl.h:414
std::map< gen_t, EventWaiter::EventWaiterList > future_local_waiters
Definition event_impl.h:409