P99
p99_futex_c11.h
Go to the documentation of this file.
1 /* This may look like nonsense, but it really is -*- mode: C; coding: utf-8 -*- */
2 /* */
3 /* Except for parts copied from previous work and as explicitly stated below, */
4 /* the author and copyright holder for this work is */
5 /* (C) copyright 2012, 2014 Jens Gustedt, INRIA, France */
6 /* */
7 /* This file is free software; it is part of the P99 project. */
8 /* */
9 /* Licensed under the Apache License, Version 2.0 (the "License"); */
10 /* you may not use this file except in compliance with the License. */
11 /* You may obtain a copy of the License at */
12 /* */
13 /* http://www.apache.org/licenses/LICENSE-2.0 */
14 /* */
15 /* Unless required by applicable law or agreed to in writing, software */
16 /* distributed under the License is distributed on an "AS IS" BASIS, */
17 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
18 /* See the License for the specific language governing permissions and */
19 /* limitations under the License. */
20 /* */
21 #ifndef P99_FUTEX_C11_H
22 #define P99_FUTEX_C11_H
23 
28 struct p99_futex_c11 {
31  unsigned p99_cnt;
34  unsigned p99_waiting;
37  unsigned p99_awaking;
39  mtx_t p99_mut;
42  cnd_t p99_cnd;
43 };
44 
45 #ifndef P00_DOXYGEN
46 
47 #ifndef P99_FUTEX_INITIALIZER
48 # define P99_FUTEX_INITIALIZER(INITIAL) { .p99_cnt = (INITIAL), }
49 #endif
50 
51 p99_inline
52 p99_futex* p99_futex_init(p99_futex* p00_fut, unsigned p00_ini) {
53  if (p00_fut) {
54  *p00_fut = (p99_futex)P99_FUTEX_INITIALIZER(p00_ini);
55  mtx_init(&p00_fut->p99_mut, mtx_plain);
56  cnd_init(&p00_fut->p99_cnd);
57  }
58  return p00_fut;
59 }
60 
61 p99_inline
62 void p99_futex_destroy(p99_futex* p00_fut) {
63  if (p00_fut) {
64  p00_fut->p99_cnt = UINT_MAX;
65  mtx_destroy(&p00_fut->p99_mut);
66  cnd_destroy(&p00_fut->p99_cnd);
67  }
68 }
69 
70 P99_WEAK(p99_futex_load)
71 unsigned p99_futex_load(p99_futex volatile* p00_fut) {
72  unsigned p00_ret = 0;
73  P99_MUTUAL_EXCLUDE(*(mtx_t*)&p00_fut->p99_mut) {
74  p00_ret = p00_fut->p99_cnt;
75  }
76  return p00_ret;
77 }
78 
79 /* Supposes that the lock on the mutex is already taken and that
80  * p00_wmin <= p00_wmax. Returns min(p00_win, p00_wok) where p00_wok
81  * is the number of threads that have been woken up. */
82 p99_inline
83 unsigned p00_futex_wakeup(p99_futex volatile* p00_fut,
84  unsigned p00_wmin, unsigned p00_wmax) {
85  assert(p00_wmin <= p00_wmax);
86  if (p00_wmax && p00_fut->p99_waiting) {
87  if (p00_wmax > p00_fut->p99_waiting) p00_wmax = p00_fut->p99_waiting;
88  if (p00_wmax > 1u) cnd_broadcast((cnd_t*)&p00_fut->p99_cnd);
89  else cnd_signal((cnd_t*)&p00_fut->p99_cnd);
90  p00_fut->p99_waiting -= p00_wmax;
91  p00_fut->p99_awaking += p00_wmax;
92  return p00_wmin;
93  } else {
94  return 0;
95  }
96 }
97 
98 #define P00_FUTEX_WAKEUP(FUT, WMIN, WMAX) \
99  do { \
100  unsigned p00Wok = p00_futex_wakeup((FUT), WMIN, WMAX); \
101  WMIN -= p00Wok; \
102  WMAX -= p00Wok; \
103  } while(false)
104 
105 P99_WEAK(p99_futex_wakeup)
106 void p99_futex_wakeup(p99_futex volatile* p00_fut,
107  unsigned p00_wmin, unsigned p00_wmax) {
108  if (p00_wmax < p00_wmin) p00_wmax = p00_wmin;
109  if (p00_wmax) do {
110  unsigned p00_wok = 0;
111  P99_MUTUAL_EXCLUDE(*(mtx_t*)&p00_fut->p99_mut) {
112  p00_wok = p00_futex_wakeup(p00_fut, p00_wmin, p00_wmax);
113  }
114  p00_wmax -= p00_wok;
115  p00_wmin -= p00_wok;
116  } while (p00_wmin);
117 }
118 
119 p99_inline
120 void p00_futex_wait(p99_futex volatile* p00_fut) {
121  ++p00_fut->p99_waiting;
122  /* This loop captures spurious wakeups as they may happen for
123  cnd_wait. */
124  do {
125  cnd_wait((cnd_t*)&p00_fut->p99_cnd, (mtx_t*)&p00_fut->p99_mut);
126  } while (!p00_fut->p99_awaking);
127  --p00_fut->p99_awaking;
128 }
129 
130 P99_WEAK(p99_futex_wait)
131 void p99_futex_wait(p99_futex volatile* p00_fut) {
132  P99_MUTUAL_EXCLUDE(*(mtx_t*)&p00_fut->p99_mut)
133  p00_futex_wait(p00_fut);
134 }
135 
136 P99_WEAK(p99_futex_add)
137 unsigned p99_futex_add(p99_futex volatile* p00_fut, unsigned p00_hmuch,
138  unsigned p00_cstart, unsigned p00_clen,
139  unsigned p00_wmin, unsigned p00_wmax) {
140  unsigned p00_ret = 0;
141  if (p00_wmax < p00_wmin) p00_wmax = p00_wmin;
142  P99_MUTUAL_EXCLUDE(*(mtx_t*)&p00_fut->p99_mut) {
143  p00_ret = p00_fut->p99_cnt;
144  register unsigned const p00_des = p00_ret + p00_hmuch;
145  p00_fut->p99_cnt = p00_des;
146  if (p00_clen && P99_IN_RANGE(p00_des, p00_cstart, p00_clen)) {
147  P00_FUTEX_WAKEUP(p00_fut, p00_wmin, p00_wmax);
148  } else {
149  p00_wmin = 0;
150  }
151  }
152  /* If we haven't woken enough threads, we have to re-acquire the
153  mutex and loop until enough threads will enter the futex wait. */
154  if (p00_wmin) p99_futex_wakeup(p00_fut, p00_wmin, p00_wmax);
155  return p00_ret;
156 }
157 
158 P99_WEAK(p99_futex_exchange)
159 unsigned p99_futex_exchange(p99_futex volatile* p00_fut, unsigned p00_desired,
160  unsigned p00_cstart, unsigned p00_clen,
161  unsigned p00_wmin, unsigned p00_wmax) {
162  volatile unsigned p00_act = 0;
163  if (p00_wmax < p00_wmin) p00_wmax = p00_wmin;
164  P99_MUTUAL_EXCLUDE(*(mtx_t*)&p00_fut->p99_mut) {
165  p00_act = p00_fut->p99_cnt;
166  p00_fut->p99_cnt = p00_desired;
167  if (p00_clen && P99_IN_RANGE(p00_desired, p00_cstart, p00_clen)) {
168  P00_FUTEX_WAKEUP(p00_fut, p00_wmin, p00_wmax);
169  } else {
170  p00_wmin = 0;
171  }
172  }
173  /* If we haven't woken enough threads, we have to re-acquire the
174  mutex and loop until enough threads will enter the futex wait. */
175  if (p00_wmin) p99_futex_wakeup(p00_fut, p00_wmin, p00_wmax);
176  return p00_act;
177 }
178 
179 #ifndef P99_FUTEX_COMPARE_EXCHANGE
180 P00_DOCUMENT_IDENTIFIER_ARGUMENT(P99_FUTEX_COMPARE_EXCHANGE, 1)
181 # define P99_FUTEX_COMPARE_EXCHANGE(FUTEX, ACT, EXPECTED, DESIRED, WAKEMIN, WAKEMAX) \
182 do { \
183  p99_futex volatile*const p00Mfut = (FUTEX); \
184  unsigned volatile p00Mwmin = 0; \
185  unsigned volatile p00Mwmax = 0; \
186  P99_MUTUAL_EXCLUDE(*(mtx_t*)&p00Mfut->p99_mut) { \
187  for (;;) { \
188  register unsigned const ACT = p00Mfut->p99_cnt; \
189  P99_UNUSED(ACT); /* Don't warn if ACT is unused. */ \
190  if (P99_LIKELY(EXPECTED)) { \
191  p00Mfut->p99_cnt = (DESIRED); \
192  p00Mwmin = (WAKEMIN); \
193  p00Mwmax = (WAKEMAX); \
194  if (p00Mwmax < p00Mwmin) p00Mwmax = p00Mwmin; \
195  P00_FUTEX_WAKEUP(p00Mfut, p00Mwmin, p00Mwmax); \
196  break; \
197  } \
198  p00_futex_wait(p00Mfut); \
199  } \
200  } \
201  /* If we haven't woken enough threads, we have to re-acquire the \
202  mutex and loop until enough threads will enter the futex wait. */ \
203  if (p00Mwmin) p99_futex_wakeup(p00Mfut, p00Mwmin, p00Mwmax); \
204  } while (false)
205 #endif
206 
207 #endif /* P00_DOXYGEN */
208 #endif
p99_futex_c11::p99_cnd
cnd_t p99_cnd
A conditional variable to wait and signal changes to the value.
Definition: p99_futex_c11.h:42
p99_futex_c11::p99_cnt
unsigned p99_cnt
An unsigned that makes up the counter itself.
Definition: p99_futex_c11.h:31
p99_futex::p99_futex_destroy
void p99_futex_destroy(p99_futex *p00_c)
Destroy an p99_futex object.
p99_futex
A counter similar to a conditional variable that allows atomic increment and decrement and to wait fo...
Definition: p99_futex.h:163
p99_futex_c11::p99_waiting
unsigned p99_waiting
Holds the number of waiters on the condition.
Definition: p99_futex_c11.h:34
P99_IN_RANGE
#define P99_IN_RANGE(R, S, L)
check if R is in the range [S, S + L)
Definition: p99_generic.h:1499
p99_futex::p99_futex_exchange
unsigned p99_futex_exchange(p99_futex volatile *p00_fut, unsigned p00_desired, unsigned p00_cstart, unsigned p00_clen, unsigned p00_wmin, unsigned p00_wmax)
Unconditionally and atomically set the futex p00_fut to value p00_desired.
p99_inline
#define p99_inline
Try to force a function always to be inlined.
Definition: p99_compiler.h:496
mtx_plain
@ mtx_plain
passed to ::mtx_init to create a mutex object that supports neither timeout nor test and return
Definition: p99_threads_posix.h:157
p99_futex::P99_FUTEX_COMPARE_EXCHANGE
#define P99_FUTEX_COMPARE_EXCHANGE(FUTEX, ACT, EXPECTED, DESIRED, WAKEMIN, WAKEMAX)
a catch all macro to operate on p99_futex
Definition: p99_futex.h:563
P99_WEAK
#define P99_WEAK(...)
Declare a symbol to be weak such that it can be provided several times without error.
Definition: p99_compiler.h:561
p99_futex_c11
The structure that is used in the fallback implementation of p99_futex on non-linux systems.
Definition: p99_futex_c11.h:28
p99_futex::p99_futex_load
unsigned p99_futex_load(p99_futex volatile *p00_fut)
Obtain the value of futex p00_fut atomically.
p99_futex::p99_futex_wakeup
void p99_futex_wakeup(p99_futex volatile *p00_fut, unsigned p00_wmin, unsigned p00_wmax)
Wake up threads that are waiting for a futex.
p99_futex::p99_futex_wait
void p99_futex_wait(p99_futex volatile *p00_fut)
Unconditionally wait for futex p00_fut.
p99_futex_c11::p99_awaking
unsigned p99_awaking
Holds the number of waiters on the condition that are to be woken up.
Definition: p99_futex_c11.h:37
p99_futex::p99_futex_add
unsigned p99_futex_add(p99_futex volatile *p00_fut, unsigned p00_hmuch, unsigned p00_cstart, unsigned p00_clen, unsigned p00_wmin, unsigned p00_wmax)
increment the counter of p00_fut atomically by p00_hmuch.
P99_MUTUAL_EXCLUDE
#define P99_MUTUAL_EXCLUDE(MUT)
Protect the following block or statement with mtx_t MUT.
Definition: p99_threads.h:308
p99_futex::p99_futex_init
p99_futex * p99_futex_init(p99_futex *p00_c, unsigned p00_ini)
Initialize an p99_futex object.
p99_futex_c11::p99_mut
mtx_t p99_mut
A mutex that locks the access to the data structure.
Definition: p99_futex_c11.h:39
Generated by   doxygen 1.8.17