struct sync_completion

/////////////////////////////////////////////////////////////////////////////

sync_completion_t

:: Overview ::

sync_completion_t objects (henceforth, simply "completions") are lightweight

in-process events. Conceptually, a completion has an internal state of either

UNSIGNALED or SIGNALED. Threads in a process may alter this state, check the

state without blocking, or wait on the completion with an optional

timeout/deadline until it achieves the SIGNALED state. Completions are

currently implemented using Zircon futexes.

:: Initialization ::

Completions always start in the UNSIGNALED state. When used in C code, users

*must* explicitly initialize their completion's state using the

SYNC_COMPLETION_INIT preprocessor symbol. For example:

```

struct my_structure {

int32_t a_variable;

sync_completion_t a_completion;

};

void init_my_structure(struct my_structure* s) {

s->a_variable = 0;

s->a_completion = SYNC_COMPLETION_INIT;

}

```

When used in C++ code, no explicit initialization steps are required. The

completion's structure will contain a default constructor which properly

initializes the completion's UNSIGNALED state.

:: Operations ::

The permitted operations on a completion are as follows.

++ sync_completion_wait ++

Block a thread with an optional relative timeout until the completion

achieves the signaled state. If the completion is already in the SIGNALED

state, the waiting thread will not block.

++ sync_completion_wait_deadline ++

Block a thread with an optional absolute deadline timeout until the

completion achieves the signaled state. If the completion is already in the

SIGNALED state, the waiting thread will not block.

++ sync_completion_signal ++

Change the internal state of a completion to SIGNALED, releasing any threads

which are currently waiting on it.

++ sync_completion_reset ++

Change the internal state of a completion to UNSIGNALED. See also `Avoid

"Strobing" Signals` (below) for some hazards related to the use of the reset

operation.

++ sync_completion_signaled ++

Observe the internal state of a completion, and return true if it is

SIGNALED, and false otherwise.

:: No Spurious Wakeups ::

sync_completion_wait() will *only* return:

++ if the completion is signaled at some point by a call to

sync_completion_signal() (either before or after the call to

sync_completion_wait())

++ or if the timeout occurs (if using timeouts)

Implementation details:

In general, futex-based concurrency algorithms can cause futex wakeups on

memory locations that have been deallocated (for example, the standard

algorithm for a mutex_unlock can do that). This means that futex-based

concurrency algorithms must be robust against spurious wakeups, because a

futex memory location may have been previously used, deallocated, and then

recycled.

Completions guarantee that waiters will not suffer any spurious wakeups,

provided that the lifetime of the sync_completion_t instance is properly

respected. For example, pretend we have the following situation.

```

void thread_a() {

sync_completion_t C = SYNC_COMPLETION_INIT;

share_completion_with_thread_b(

&C

);

sync_completion_wait(

&C

, ZX_TIME_INFINITE);

}

void thread_b() {

sync_completion_t* C = obtain_completion_from_thread_a();

sync_completion_signal(C);

}

```

The call to sync_completion_wait is guaranteed to not wake up spuriously,

even if an unrelated zx_futex_wake operation targeting the same memory

location happens to occur during the interactions between thread_a and

thread_b. This behavior **depends** on making sure that the life-cycle of C

is properly obeyed. After thread_b does sync_completion_signal(C), it must

not perform any further operations on C. Having signaled C, thread_b has

caused thread_a to unblock and begin the process of deallocating C. Any

operations performed on C after this point are racing with the deallocation

of C and might result in a use-after-free situation. While it is possible

that thread_b may still be in the call to sync_completion_signal when

thread_a unwinds and deallocates the completion, no reads or writes from or to

the completion's state will be made after this point, and the code is safe

provided that this is the final completion operation.

:: Avoid "Strobing" Signals ::

Users should avoid the pattern of "strobing" a signal operation.

Specifically, calling sync_completion_signal(C) immediately followed by

sync_completion_reset(C) is not guaranteed to wake up a waiter, even if the

user could prove that the waiter is waiting in the completion.

Implementation details:

The following is an example of a sequence which makes use of the strobe

pattern which can lead a missed event. It is based on specific details of

how sync_completion_t is implemented today, and should not be considered to

be the only way that a signal might end up getting missed, either now or in

the future. Again, user should always avoid this "strobing" pattern, it is

not guaranteed to wake a waiter.

```

global sync_completion_t C;

Thread A:

1) Wait on C with no timeout.

2) Declare victory

Thread B:

1) Wait until thread A is blocked on completion C by polling Thread A's state

via zx_object_get_info.

2) sync_completion_signal(C)

3) sync_completion_reset(C)

4) sync_completion_wait(C, timeout)

```

Step B.1 establishes the fact that (from thread B's perspective) thread A

managed to observe C in the UNSIGNALED state and join the internal futex wait

queue used to implement the completion_t. In the process, thread A sets the

completion_t's internal state to UNSIGNALED_WITH_WAITERS. The subsequent

signal/reset/wait operations (steps B.2-B.4), will release thread A from the

wait queue, but cycle the internal state of the completion_t through the

SIGNALED and UNSIGNALED states, and back again to the UNSIGNALED_WITH_WAITERS

state. If thread B manages to cycle the state all of the way back around to

UNSIGNALED_WITH_WAITERS before thread A manages to wake up, thread A will see

the state as UNSIGNALED_WITH_WAITERS and rejoin the wait queue thinking that

it had been woken by a spurious futex_wake.

Once again, as a general rule the signal/reset pattern shown here should not

be used with sync_completion_t objects. It is considered to be racy and can

result in undesired behavior, no matter what steps are taken establish that A

is waiting before the signal/reset operations take place.

:: Memory Ordering Semantics ::

When a thread transitions the state of a completion from UNSIGNALED to

SIGNALED by calling sync_completion_signal, the operation provides the same

guarantees as an atomic modification of the completion state with Release

semantics. These guarantees do _not_ hold if the completion is already in

the SIGNALED state when the thread calls sync_completion_signal.

When a thread returns from a sync_completion_wait operation with a status of

ZX_OK, the operation provides the same guarantees as having atomically

observed the completion state as being SIGNALED with Acquire semantics.

These guarantees do _not_ hold if the wait operation times out, or returns

any other error.

The effects of these guarantees are that write operations to shared memory

performed by a thread may not be reordered beyond a signal operation which

successfully transitions a completion from UNSIGNALED to SIGNALED performed

by the same thread. Likewise, successful wait operations performed by a

thread against a completion guarantee that subsequent read operations

performed by that thread may not be reordered before the wait operation.

Taken together, these guarantees make the following common pattern safe.

```

typedef struct {

uint32_t val;

sync_completion_t C;

} read_operation_t;

void thread_a() {

read_operation_t Op;

Op.C = SYNC_COMPLETION_INIT;

send_op_to_thread_b(

&Op

);

sync_completion_wait(

&Op

.C);

do_great_things_with_val(Op.val);

}

void thread_b() {

while (true) {

read_operation_t* Op = obtain_read_op();

Op->val = compute_a_value_only_thread_b_can_compute();

sync_completion_signal(

&Op

->C);

}

}

```

Thread A is guaranteed to see the results written by thread B into the shared

Op.val member. The modifications performed by thread B may not be reordered

past the signal operation, and read operations performed by thread A may not

be moved before the wait operation.