Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make Waiters lock-free #382

Open
Tracked by #388
talex5 opened this issue Dec 5, 2022 · 3 comments
Open
Tracked by #388

Make Waiters lock-free #382

talex5 opened this issue Dec 5, 2022 · 3 comments
Labels
enhancement New feature or request

Comments

@talex5
Copy link
Collaborator

talex5 commented Dec 5, 2022

Waiters currently needs a mutex to protect the list of waiting fibers. This prevents us from using it in signal handlers or GC finalizers (see #374). We can't use Lf_queue here because we need to support cancellation (removing waiters from the middle of the queue).

https://arxiv.org/pdf/2111.12682.pdf ("A formally-verified framework for fair synchronization in Kotlin coroutines") could be a good solution, and will probably be faster too.

@talex5
Copy link
Collaborator Author

talex5 commented Feb 2, 2023

Instead of making it lock-free, I added a separate Cells module for lock-free users. Promise, Condition, Semaphore and 0-capacity Streams now use that.

The remaining uses are:

  • Switch (which could probably use Single_waiter instead).
  • Mutex (should be easy to update to Cells).
  • Streams with non-0-capacity (non-trivial, but should be possible to switch).

@talex5 talex5 added the enhancement New feature or request label Feb 6, 2023
@polytypic
Copy link
Contributor

polytypic commented Apr 13, 2023

Looking at the Mutex API, the protect argument of use_rw seems unnecessary.

-Mutex.use_rw ~protect:false mutex thunk
+Mutex.use_rw mutex thunk
-Mutex.use_rw ~protect:true mutex thunk
+Mutex.use_rw mutex (Cancel.protect thunk)

I guess the intention with the API is to force the user to think about cancellation.

The names, use_rw and use_ro chosen for the operations are not perhaps the most "comprehensive". It is quite possible to have a writing critical section that is still safe to cancel. What is needed is that state is consistent at the points where cancellation might happen.

For example, the common pattern using Condition.await

Mutex.lock mutex;
Fun.protect ~finally:(fun () -> Mutex.unlock mutex) begin fun () ->
  (* modify or examine state, never enter scheduler *)
  while (* some condition *) do
    (* await unlocks the mutex, so state needs to be consistent at this point *)
    Condition.await condition mutex
  done
  (* modify or examine state, never enter scheduler *)
end

should be safe as long as the Condition.await is the only point that enters the scheduler and might raise the cancellation exception.


As background information for others, I've been looking into the synchronization structures of Eio to see how one could implement them using compositional lock-free algorithms (using kcas).

@talex5
Copy link
Collaborator Author

talex5 commented Apr 14, 2023

Yes, it's trying to get users to think about two things:

  • Whether to poison the mutex if an unexpected exception occurs.
  • Whether to allow cancellation.

I'm not super happy about the names either, especially as it makes it sound like a RW lock.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

3 participants