ARGOBOTS  8bef54a19d7b3e50f977f85716578b627bf37d9c
abti_waitlist.h
Go to the documentation of this file.
1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil ; -*- */
2 /*
3  * See COPYRIGHT in top-level directory.
4  */
5 
6 #ifndef ABTI_WAITLIST_H_INCLUDED
7 #define ABTI_WAITLIST_H_INCLUDED
8 
9 #include "abt_config.h"
10 
11 static inline void ABTI_waitlist_init(ABTI_waitlist *p_waitlist)
12 {
13 #ifndef ABT_CONFIG_ACTIVE_WAIT_POLICY
14  ABTD_futex_multiple_init(&p_waitlist->futex);
15 #endif
16  p_waitlist->p_head = NULL;
17  p_waitlist->p_tail = NULL;
18 }
19 
20 static inline void
22  ABTD_spinlock *p_lock,
23  ABT_sync_event_type sync_event_type, void *p_sync)
24 {
26  ABTI_ythread *p_ythread = NULL;
27  ABTI_xstream *p_local_xstream = ABTI_local_get_xstream_or_null(*pp_local);
28  if (!ABTI_IS_EXT_THREAD_ENABLED || p_local_xstream) {
29  p_ythread = ABTI_thread_get_ythread_or_null(p_local_xstream->p_thread);
30  }
31  if (!p_ythread) {
32  /* External thread or non-yieldable thread. */
33  ABTI_thread thread;
34  thread.type = ABTI_THREAD_TYPE_EXT;
35  /* use state for synchronization */
37  /* Add thread to the list. */
38  thread.p_next = NULL;
39  if (p_waitlist->p_head == NULL) {
40  p_waitlist->p_head = &thread;
41  } else {
42  p_waitlist->p_tail->p_next = &thread;
43  }
44  p_waitlist->p_tail = &thread;
45 
46  /* Non-yieldable thread is waiting here. */
47 #ifdef ABT_CONFIG_ACTIVE_WAIT_POLICY
48  ABTD_spinlock_release(p_lock);
49  while (ABTD_atomic_acquire_load_int(&thread.state) !=
51  ;
52 #else
53  while (1) {
54  /* While taking a lock check if this thread is not ready. This is
55  * necessary to sleep while ready; otherwise deadlock. */
56  if (ABTD_atomic_relaxed_load_int(&thread.state) ==
58  ABTD_spinlock_release(p_lock);
59  break;
60  }
61  ABTD_futex_wait_and_unlock(&p_waitlist->futex, p_lock);
62 
63  /* Quick check. */
64  if (ABTD_atomic_acquire_load_int(&thread.state) ==
66  break;
67 
68  /* Take a lock again. */
69  ABTD_spinlock_acquire(p_lock);
70  }
71 #endif
72  } else {
73  /* Add p_thread to the list. */
74  p_ythread->thread.p_next = NULL;
75  if (p_waitlist->p_head == NULL) {
76  p_waitlist->p_head = &p_ythread->thread;
77  } else {
78  p_waitlist->p_tail->p_next = &p_ythread->thread;
79  }
80  p_waitlist->p_tail = &p_ythread->thread;
81 
82  /* Suspend the current ULT */
83  ABTI_ythread_set_blocked(p_ythread);
84  ABTD_spinlock_release(p_lock);
85  ABTI_ythread_suspend(&p_local_xstream, p_ythread,
87  /* Resumed. */
88  *pp_local = ABTI_xstream_get_local(p_local_xstream);
89  }
90 }
91 
92 /* Return ABT_TRUE if timed out. */
94  ABTI_local **pp_local, ABTI_waitlist *p_waitlist, ABTD_spinlock *p_lock,
95  double target_time, ABT_sync_event_type sync_event_type, void *p_sync)
96 {
98  ABTI_ythread *p_ythread = NULL;
99  ABTI_xstream *p_local_xstream = ABTI_local_get_xstream_or_null(*pp_local);
100  if (!ABTI_IS_EXT_THREAD_ENABLED || p_local_xstream)
101  p_ythread = ABTI_thread_get_ythread_or_null(p_local_xstream->p_thread);
102 
103  /* Always use a dummy thread. */
104  ABTI_thread thread;
105  thread.type = ABTI_THREAD_TYPE_EXT;
106  /* use state for synchronization */
108 
109  /* Add p_thread to the list. This implementation is tricky since this
110  * updates p_prev as well for removal on timeout while the other functions
111  * (e.g., wait, broadcast, signal) do not update it. */
112  thread.p_next = NULL;
113  if (p_waitlist->p_head == NULL) {
114  p_waitlist->p_head = &thread;
115  thread.p_prev = NULL;
116  } else {
117  p_waitlist->p_tail->p_next = &thread;
118  thread.p_prev = p_waitlist->p_tail;
119  }
120  p_waitlist->p_tail = &thread;
121 
122  /* Waiting here. */
123  if (p_ythread) {
124  /* When an underlying entity is yieldable. */
125  ABTD_spinlock_release(p_lock);
126  while (ABTD_atomic_acquire_load_int(&thread.state) !=
128  double cur_time = ABTI_get_wtime();
129  if (cur_time >= target_time) {
130  ABTD_spinlock_acquire(p_lock);
131  goto timeout;
132  }
133  ABTI_ythread_yield(&p_local_xstream, p_ythread, sync_event_type,
134  p_sync);
135  *pp_local = ABTI_xstream_get_local(p_local_xstream);
136  }
137  } else {
138  /* When an underlying entity is non-yieldable. */
139 #ifdef ABT_CONFIG_ACTIVE_WAIT_POLICY
140  ABTD_spinlock_release(p_lock);
141  while (ABTD_atomic_acquire_load_int(&thread.state) !=
143  double cur_time = ABTI_get_wtime();
144  if (cur_time >= target_time) {
145  ABTD_spinlock_acquire(p_lock);
146  goto timeout;
147  }
148  }
149 #else
150  while (1) {
151  double cur_time = ABTI_get_wtime();
152  if (cur_time >= target_time) {
153  goto timeout;
154  }
155  /* While taking a lock check if this thread is not ready. This is
156  * necessary to sleep while ready; otherwise deadlock. */
157  if (ABTD_atomic_relaxed_load_int(&thread.state) ==
159  ABTD_spinlock_release(p_lock);
160  break;
161  }
162  ABTD_futex_timedwait_and_unlock(&p_waitlist->futex, p_lock,
163  target_time - cur_time);
164  /* Quick check. */
165  if (ABTD_atomic_acquire_load_int(&thread.state) ==
167  break;
168  /* Take a lock again. */
169  ABTD_spinlock_acquire(p_lock);
170  }
171 #endif
172  }
173  /* Singled */
174  return ABT_FALSE;
175 timeout:
176  /* Timeout. Remove this thread if not signaled even after taking a lock. */
178  ABT_bool is_timedout =
180  ? ABT_TRUE
181  : ABT_FALSE;
182  if (is_timedout) {
183  /* This thread is still in the list. */
184  if (p_waitlist->p_head == &thread) {
185  /* thread is a head. */
186  /* Note that thread->p_prev cannot be used to check whether
187  * thread is a head or not because signal and broadcast do
188  * not modify thread->p_prev. */
189  p_waitlist->p_head = thread.p_next;
190  if (!thread.p_next) {
191  /* This thread is p_tail */
192  ABTI_ASSERT(p_waitlist->p_tail == &thread);
193  p_waitlist->p_tail = NULL;
194  }
195  } else {
196  /* thread is not a head and thus p_prev exists. */
197  ABTI_ASSERT(thread.p_prev);
198  thread.p_prev->p_next = thread.p_next;
199  if (thread.p_next && thread.type == ABTI_THREAD_TYPE_EXT) {
200  /* Only a dummy external thread created by this function
201  * checks p_prev. Note that a real external thread is
202  * also dummy, so updating p_prev is allowed. */
203  thread.p_next->p_prev = thread.p_prev;
204  } else {
205  /* This thread is p_tail */
206  ABTI_ASSERT(p_waitlist->p_tail == &thread);
207  p_waitlist->p_tail = thread.p_prev;
208  }
209  }
210  /* We do not need to modify thread->p_prev and p_next since this
211  * dummy thread is no longer used. */
212  }
213  ABTD_spinlock_release(p_lock);
214  return is_timedout;
215 }
216 
217 static inline void ABTI_waitlist_signal(ABTI_local *p_local,
218  ABTI_waitlist *p_waitlist)
219 {
220  ABTI_thread *p_thread = p_waitlist->p_head;
221  if (p_thread) {
222  ABTI_thread *p_next = p_thread->p_next;
223  p_thread->p_next = NULL;
224 
225  ABTI_ythread *p_ythread = ABTI_thread_get_ythread_or_null(p_thread);
226  if (p_ythread) {
227  ABTI_ythread_set_ready(p_local, p_ythread);
228  } else {
229  /* When p_thread is an external thread or a tasklet */
232 #ifndef ABT_CONFIG_ACTIVE_WAIT_POLICY
233  /* There's no way to selectively wake up threads. Let's just
234  * wake up all the threads. They will sleep again since their
235  * states are not marked as READY. */
236  ABTD_futex_broadcast(&p_waitlist->futex);
237 #endif
238  }
239  /* After updating p_thread->state, p_thread can be updated and
240  * freed. */
241  p_waitlist->p_head = p_next;
242  if (!p_next)
243  p_waitlist->p_tail = NULL;
244  }
245 }
246 
247 static inline void ABTI_waitlist_broadcast(ABTI_local *p_local,
248  ABTI_waitlist *p_waitlist)
249 {
250  ABTI_thread *p_thread = p_waitlist->p_head;
251  if (p_thread) {
252  ABT_bool wakeup_nonyieldable = ABT_FALSE;
253  do {
254  ABTI_thread *p_next = p_thread->p_next;
255  p_thread->p_next = NULL;
256 
257  ABTI_ythread *p_ythread = ABTI_thread_get_ythread_or_null(p_thread);
258  if (p_ythread) {
259  ABTI_ythread_set_ready(p_local, p_ythread);
260  } else {
261  /* When p_thread is an external thread or a tasklet */
262  wakeup_nonyieldable = ABT_TRUE;
265  }
266  /* After updating p_thread->state, p_thread can be updated and
267  * freed. */
268  p_thread = p_next;
269  } while (p_thread);
270  p_waitlist->p_head = NULL;
271  p_waitlist->p_tail = NULL;
272 #ifndef ABT_CONFIG_ACTIVE_WAIT_POLICY
273  if (wakeup_nonyieldable) {
274  ABTD_futex_broadcast(&p_waitlist->futex);
275  }
276 #else
277  /* Do nothing. */
278  (void)wakeup_nonyieldable;
279 #endif
280  }
281 }
282 
284 {
285  return p_waitlist->p_head ? ABT_FALSE : ABT_TRUE;
286 }
287 
288 #endif /* ABTI_WAITLIST_H_INCLUDED */
ABTI_waitlist::futex
ABTD_futex_multiple futex
Definition: abti.h:179
ABT_bool
int ABT_bool
Boolean type.
Definition: abt.h:1001
ABTI_waitlist_wait_timedout_and_unlock
static ABT_bool ABTI_waitlist_wait_timedout_and_unlock(ABTI_local **pp_local, ABTI_waitlist *p_waitlist, ABTD_spinlock *p_lock, double target_time, ABT_sync_event_type sync_event_type, void *p_sync)
Definition: abti_waitlist.h:93
ABT_THREAD_STATE_READY
@ ABT_THREAD_STATE_READY
Definition: abt.h:417
ABTI_waitlist_broadcast
static void ABTI_waitlist_broadcast(ABTI_local *p_local, ABTI_waitlist *p_waitlist)
Definition: abti_waitlist.h:247
ABTI_thread::type
ABTI_thread_type type
Definition: abti.h:393
ABTD_futex_multiple_init
static void ABTD_futex_multiple_init(ABTD_futex_multiple *p_futex)
Definition: abtd_futex.h:79
ABTI_thread::p_next
ABTI_thread * p_next
Definition: abti.h:391
ABTI_waitlist::p_tail
ABTI_thread * p_tail
Definition: abti.h:182
ABTI_thread
Definition: abti.h:389
ABTI_xstream
Definition: abti.h:282
ABTI_THREAD_TYPE_EXT
#define ABTI_THREAD_TYPE_EXT
Definition: abti.h:95
ABTD_spinlock
Definition: abtd_spinlock.h:9
ABTI_waitlist
Definition: abti.h:177
ABTI_waitlist_is_empty
static ABT_bool ABTI_waitlist_is_empty(ABTI_waitlist *p_waitlist)
Definition: abti_waitlist.h:283
ABT_sync_event_type
ABT_sync_event_type
Type of synchronization event.
Definition: abt.h:660
ABT_THREAD_STATE_BLOCKED
@ ABT_THREAD_STATE_BLOCKED
Definition: abt.h:421
ABTD_atomic_relaxed_load_int
static int ABTD_atomic_relaxed_load_int(const ABTD_atomic_int *ptr)
Definition: abtd_atomic.h:763
ABTI_thread_get_ythread_or_null
static ABTI_ythread * ABTI_thread_get_ythread_or_null(ABTI_thread *p_thread)
Definition: abti_thread.h:59
ABTI_thread::state
ABTD_atomic_int state
Definition: abti.h:399
ABTD_spinlock_acquire
static void ABTD_spinlock_acquire(ABTD_spinlock *p_lock)
Definition: abtd_spinlock.h:28
ABTD_atomic_relaxed_store_int
static void ABTD_atomic_relaxed_store_int(ABTD_atomic_int *ptr, int val)
Definition: abtd_atomic.h:996
abt_config.h
ABTI_ASSERT
#define ABTI_ASSERT(cond)
Definition: abti_error.h:12
ABTD_futex_wait_and_unlock
void ABTD_futex_wait_and_unlock(ABTD_futex_multiple *p_futex, ABTD_spinlock *p_lock)
Definition: abtd_futex.c:87
ABTD_atomic_acquire_load_int
static int ABTD_atomic_acquire_load_int(const ABTD_atomic_int *ptr)
Definition: abtd_atomic.h:878
ABTI_ythread_set_blocked
void ABTI_ythread_set_blocked(ABTI_ythread *p_ythread)
Definition: ythread.c:23
ABTI_local_get_xstream_or_null
static ABTI_xstream * ABTI_local_get_xstream_or_null(ABTI_local *p_local)
Definition: abti_local.h:77
ABTI_IS_EXT_THREAD_ENABLED
#define ABTI_IS_EXT_THREAD_ENABLED
Definition: abti.h:28
ABT_SYNC_EVENT_TYPE_EVENTUAL
@ ABT_SYNC_EVENT_TYPE_EVENTUAL
Definition: abt.h:678
ABTI_xstream_get_local
static ABTI_local * ABTI_xstream_get_local(ABTI_xstream *p_xstream)
Definition: abti_stream.h:68
ABT_TRUE
#define ABT_TRUE
True constant for ABT_bool.
Definition: abt.h:748
ABTI_waitlist::p_head
ABTI_thread * p_head
Definition: abti.h:181
ABT_FALSE
#define ABT_FALSE
False constant for ABT_bool.
Definition: abt.h:750
ABTI_ythread
Definition: abti.h:424
ABTI_ythread_set_ready
void ABTI_ythread_set_ready(ABTI_local *p_local, ABTI_ythread *p_ythread)
Definition: ythread.c:65
ABTI_ythread_suspend
void ABTI_ythread_suspend(ABTI_xstream **pp_local_xstream, ABTI_ythread *p_ythread, ABT_sync_event_type sync_event_type, void *p_sync)
Definition: ythread.c:45
ABTD_spinlock_release
static void ABTD_spinlock_release(ABTD_spinlock *p_lock)
Definition: abtd_spinlock.h:42
ABTI_ythread::thread
ABTI_thread thread
Definition: abti.h:425
ABTI_thread::p_prev
ABTI_thread * p_prev
Definition: abti.h:390
ABTI_local
struct ABTI_local ABTI_local
Definition: abti.h:124
ABTD_futex_timedwait_and_unlock
void ABTD_futex_timedwait_and_unlock(ABTD_futex_multiple *p_futex, ABTD_spinlock *p_lock, double wait_time_sec)
Definition: abtd_futex.c:117
ABTI_ythread_yield
static void ABTI_ythread_yield(ABTI_xstream **pp_local_xstream, ABTI_ythread *p_ythread, ABT_sync_event_type sync_event_type, void *p_sync)
Definition: abti_ythread.h:372
ABTD_futex_broadcast
void ABTD_futex_broadcast(ABTD_futex_multiple *p_futex)
Definition: abtd_futex.c:174
ABTI_waitlist_init
static void ABTI_waitlist_init(ABTI_waitlist *p_waitlist)
Definition: abti_waitlist.h:11
ABTD_spinlock_is_locked
static ABT_bool ABTD_spinlock_is_locked(const ABTD_spinlock *p_lock)
Definition: abtd_spinlock.h:18
ABTI_waitlist_signal
static void ABTI_waitlist_signal(ABTI_local *p_local, ABTI_waitlist *p_waitlist)
Definition: abti_waitlist.h:217
ABTI_waitlist_wait_and_unlock
static void ABTI_waitlist_wait_and_unlock(ABTI_local **pp_local, ABTI_waitlist *p_waitlist, ABTD_spinlock *p_lock, ABT_sync_event_type sync_event_type, void *p_sync)
Definition: abti_waitlist.h:21
ABTD_atomic_release_store_int
static void ABTD_atomic_release_store_int(ABTD_atomic_int *ptr, int val)
Definition: abtd_atomic.h:1065
ABTI_get_wtime
static double ABTI_get_wtime(void)
Definition: abti_timer.h:11