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.
133  *		       const struct timespec *timeout)`:
134  *  computes a deadline `timeout` away from the current time. If
135  *  timeout is NULL, computes a deadline in the infinite future. The
137  *  success, and -1 if ops->gettime failed (without touching errno).
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
144  *  timeout. This function acts as a read (acquire) barrier.
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
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
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
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
229  * second will have elapsed since the flag flip, and the sleep timeout
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
403 	 * works on x86-64 (i.e., little endian), so the futex int
522  * Populates `new_deadline` with a deadline `timeout` in the future.
523  * Returns 0 on success, and -1 if clock_gettime failed, in which
528 			  const struct timespec *timeout);
532  * old_value, or, if deadline is non-NULL, until CLOCK_MONOTONIC is
535  * Returns 0 on success, and -1 on timeout.
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()
753 			const struct timespec *timeout);
757 				      const struct timespec *timeout)  in ck_ec_deadline()  argument
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()