31  * ck_ec implements 32- and 64- bit event counts. Event counts let us
32  * easily integrate OS-level blocking (e.g., futexes) in lock-free
44  * available if CK supports 64-bit atomic operations. Currently,
46  * x86-64, on compilers that support GCC extended inline assembly;
53  *    - Make changes to some shared data structure, without involving
55  *    - After each change, call ck_ec_inc on the event count. The call
56  *	acts as a write-write barrier, and wakes up any consumer blocked
61  *    - Snapshot ck_ec_value of the event count. The call acts as a
63  *    - Read and process the shared data structure.
64  *    - Wait for new changes by calling ck_ec_wait with the snapshot value.
89  * When compiled as C11 or later, this header defines type-generic
91  * type-generic API.
118  *  counter.  This read acts as a read (acquire) barrier.
124  *  counter by one. This writes acts as a write barrier. Wakes up
127  * `value ck_ec_add(ec, mode, value)`: increments the event counter by
128  *  `value`, and returns the event counter's previous value. This
129  *  write acts as a write barrier. Wakes up any waiting thread.
137  *  success, and -1 if ops->gettime failed (without touching errno).
140  *  counter's value differs from `value`, or, if `deadline` is
141  *  provided and non-NULL, until the current time is after that
142  *  deadline. Use a deadline with tv_sec = 0 for a non-blocking
143  *  execution. Returns 0 if the event counter has changed, and -1 on
147  * until the event counter's value differs from `value`, or until
148  * `pred` returns non-zero, or, if `deadline` is provided and
149  * non-NULL, until the current time is after that deadline. Use a
150  * deadline with tv_sec = 0 for a non-blocking execution. Returns 0 if
151  * the event counter has changed, `pred`'s return value if non-zero,
152  * and -1 on timeout. This function acts as a read (acquire) barrier.
157  * `pred` returns a non-zero value, that value is immediately returned
166  * count, with a single flag bit to denote the need to wake up waiting
170  * [x86-TSO](https://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf), and
171  * to non-atomic read-modify-write instructions (e.g., `inc mem`);
172  * these non-atomic RMW let us write to the same memory locations with
173  * atomic and non-atomic instructions, without suffering from process
176  * The reason we can mix atomic and non-atomic writes to the `counter`
177  * word is that every non-atomic write obviates the need for the
178  * atomically flipped flag bit: we only use non-atomic writes to
181  * We only require the non-atomic RMW counter update to prevent
186  * non-atomic writes. The key is instead x86-TSO's guarantee that a
191  * x86-TSO's constraint on reads suffices to guarantee that the
192  * producer will never forget about a counter update. If the last
196  * case, the value of the counter (modulo flag) is correct.
198  * When the producer forwards the counter's value from its store
201  * woken up because the flag bit was silently cleared.
203  * In reality, the store queue in x86-TSO stands for in-flight
204  * instructions in the chip's out-of-order backend. In the vast
207  * the `counter` word for ~100 iterations after flipping its flag bit:
208  * if the counter hasn't changed after that many iterations, it is
209  * very likely that the producer's next counter update will observe
217  * particularly the pre-emption timer, are why single-producer updates
218  * must happen in a single non-atomic read-modify-write instruction.
220  * have to consider the worst-case execution time for that
222  * instructions, which an unlucky pre-emption could delay for
232  * flag will definitely be observed at the next counter update.
235  * bit ints, so we must treat the 64 bit counter's low 32 bits as an
240  * the store queue (the out-of-order execution backend).
243  * or otherwise pre-empted? Migration must already incur a barrier, so
245  * pre-emption, that requires storing the architectural state, which
247  * all when pre-emption happens.
268  * GCC inline assembly lets us exploit non-atomic read-modify-write
269  * instructions on x86/x86_64 for a fast single-producer mode.
289  * ck_ec_ops define system-specific functions to get the current time,
297 	/* Populates out with the current time. Returns non-zero on failure. */
302 	 * deadline is non-NULL, stops waiting once that deadline is
309 	 * Same as wait32, but for a 64 bit counter. Only used if
319 	/* Wakes up all threads waiting on address. */
323 	 * Same as wake32, but for a 64 bit counter. Only used if
394 	uint32_t counter;  member
403 	 * works on x86-64 (i.e., little endian), so the futex int
406 	uint64_t counter;  member
412 #define CK_EC_INITIALIZER { .counter = 0 }
438  * Returns the counter value in the event count. The value is at most
447  * Returns the counter value in the event count. The value is at most
480  * Increments the counter value in the event count by one, and wakes
481  * up any waiter.
499  * Increments the counter value in the event count by delta, wakes
500  * up any waiter, and returns the previous counter value.
523  * Returns 0 on success, and -1 if clock_gettime failed, in which
531  * Waits until the counter value in the event count differs from
532  * old_value, or, if deadline is non-NULL, until CLOCK_MONOTONIC is
535  * Returns 0 on success, and -1 on timeout.
561  * Waits until the counter value in the event count differs from
562  * old_value, pred returns non-zero, or, if deadline is non-NULL,
565  * Returns 0 on success, -1 on timeout, and the return value of pred
566  * if it returns non-zero.
604 	ec->counter = value & ~(1UL << 31);  in ck_ec32_init()
610 	uint32_t ret = ck_pr_load_32(&ec->counter) & ~(1UL << 31);  in ck_ec32_value()
618 	return ck_pr_load_32(&ec->counter) & (1UL << 31);  in ck_ec32_has_waiters()
644 	 *  -------------------------------------------  in ck_ec32_inc()
660 			 : "+m"(ec->counter), "=@ccle"(flagged)	 \  in ck_ec32_inc()
665 			 : "+m"(ec->counter), "=r"(flagged)		\  in ck_ec32_inc()
669 	if (mode->single_producer == true) {  in ck_ec32_inc()
679 		ck_ec32_wake(ec, mode->ops);  in ck_ec32_inc()
696 		ck_ec32_wake(ec, mode->ops);  in ck_ec32_add_epilogue()
709 	old = ck_pr_faa_32(&ec->counter, delta);  in ck_ec32_add_mp()
723 	 * is a no-op.  in ck_ec32_add_sp()
732 			 : "+m"(ec->counter), "+r"(old)  in ck_ec32_add_sp()
743 	if (mode->single_producer == true) {  in ck_ec32_add()
759 	return ck_ec_deadline_impl(new_deadline, mode->ops, timeout);  in ck_ec_deadline()
777 	return ck_ec32_wait_slow(ec, mode->ops, old_value, deadline);  in ck_ec32_wait()
801 	return ck_ec32_wait_pred_slow(ec, mode->ops, old_value,  in ck_ec32_wait_pred()
808 	ec->counter = value << 1;  in ck_ec64_init()
814 	uint64_t ret = ck_pr_load_64(&ec->counter) >> 1;  in ck_ec64_value()
822 	return ck_pr_load_64(&ec->counter) & 1;  in ck_ec64_has_waiters()
842 		ck_ec64_wake(ec, mode->ops);  in ck_ec_add64_epilogue()
855 	return ck_ec_add64_epilogue(ec, mode, ck_pr_faa_64(&ec->counter, inc));  in ck_ec64_add_mp()
859 /* Single-producer specialisation. */
869 	 * is a no-op.  in ck_ec64_add_sp()
878 			 : "+m"(ec->counter), "+r"(old)  in ck_ec64_add_sp()
885  * Dispatch on mode->single_producer in this FORCE_INLINE function:
894 	if (mode->single_producer == true) {  in ck_ec64_add()
916 	return ck_ec64_wait_slow(ec, mode->ops, old_value, deadline);  in ck_ec64_wait()
941 	return ck_ec64_wait_pred_slow(ec, mode->ops, old_value,  in ck_ec64_wait_pred()