ruby-concurrency / ruby-concurrency/concurrent-ruby

Deadlock race when calling ScheduledTask#reschedule

Open
#1,099 9 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Ruby
Stars
5.8k
Forks
420
Avg merge
20h 45m
Merged PRs (30d)
4

Description

I believe I've found a deadlock in ScheduledTask / TimerSet, which appears to be present in both old (1.2.3) and current (1.3.6) concurrent-ruby.

If one creates a ScheduledTask, and calls reschedule() on it from the main thread on it right as the TimerSet background thread wakes up to run the #process_tasks loop, a deadlock can occur.

Thread 1: ScheduledTask#reschedule is called explicitly:

  1. locks ScheduledTask.synchronize (scheduled_task.rb:265)
  2. calls ns_reschedule, which in turn calls TimerSet#remove_task
  3. which tries to lock TimerSet.synchronize (timer_set.rb:117)

Thread 2: TimerSet#process_tasks runs auto in the background:

  1. Calls task = synchronize { @queue.pop } (timer_set.rb:167)
  2. This locks TImerSet.synchronize
  3. @queue.pop tries to pop the soonest work item, which results in invoking ScheduledTask#schedule_time to sort/compare queue items
  4. which tries to lock ScheduledTask.synchronize before accessing @time (scheduled_task.rb:207)

Below I show two threads which are deadlocked in this fashion, showing the issue, and where each thread grabs each lock. One thread is a puma request thread, which ends up calling ScheduledTask#reschedule.

# put_metric_data request #2 (TID-dh2ik puma srv tp 005)
#
# Lock Conditions: 
# - TimerSet: trying to lock
# - ScheduledTask: locked
#
[171733] Thread: TID-dh2ik puma srv tp 005
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/synchronization/mutex_lockable_object.rb:48:in 'synchronize'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/synchronization/mutex_lockable_object.rb:48:in 'synchronize'
#### <---- TRY TO LOCK TimerSet.synchronize ####
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/timer_set.rb:116:in 'remove_task' 
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/scheduled_task.rb:328:in 'ns_reschedule'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/scheduled_task.rb:265:in 'block in reschedule' 
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/synchronization/mutex_lockable_object.rb:46:in 'synchronize'
#### <---- LOCK ScheduledTask.synchronize ####
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/scheduled_task.rb:265:in 'reschedule'
# SNIP, long puma/rails request backtrace which doesn't use concurrent


# concurrent-ruby scheduled_task (TID-4jpio worker-1)
#
# Lock Conditions: 
# - TimerSet: locked
# - ScheduledTask: trying to lock
#
[171733] Thread: TID-4jpio worker-1
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/synchronization/mutex_lockable_object.rb:48:in 'synchronize'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/synchronization/mutex_lockable_object.rb:48:in 'synchronize'
#### <---- TRY TO LOCK ScheduledTask.synchronize ####
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/scheduled_task.rb:207:in 'schedule_time'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/scheduled_task.rb:214:in '<=>'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb:120:in 'ordered?'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb:133:in 'sink'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/collection/ruby_non_concurrent_priority_queue.rb:70:in 'pop'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/timer_set.rb:164:in 'block (2 levels) in process_tasks'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/synchronization/mutex_lockable_object.rb:48:in 'block in synchronize'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/synchronization/mutex_lockable_object.rb:48:in 'synchronize'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/synchronization/mutex_lockable_object.rb:48:in 'synchronize'
#### <---- LOCK TimerSet.synchronize ####
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/timer_set.rb:164:in 'block in process_tasks' 
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/timer_set.rb:144:in 'loop'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/timer_set.rb:144:in 'process_tasks'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/ruby_thread_pool_executor.rb:359:in 'run_task'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/ruby_thread_pool_executor.rb:350:in 'block (3 levels) in create_worker'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/ruby_thread_pool_executor.rb:341:in 'loop'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/ruby_thread_pool_executor.rb:341:in 'block (2 levels) in create_worker'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/ruby_thread_pool_executor.rb:340:in 'catch'
concurrent-ruby-1.2.3/lib/concurrent-ruby/concurrent/executor/ruby_thread_pool_executor.rb:340:in 'block in create_worker'

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with lib/concurrent-ruby/concurrent/scheduled_task.rb, especially reschedule, ns_reschedule, and schedule_time, then inspect lib/concurrent-ruby/concurrent/executor/timer_set.rb and its process_tasks and remove_task paths. Reproduce the lock-ordering race described in the issue and use the cited priority queue stack to observe it. Done means the reschedule and timer-processing paths no longer deadlock.

Written by the indexing model from the issue text.

Assessment

Tech stack
ruby
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.