Concurrent Ruby: `ReentrantReadWriteLock` read-count overflow grants a write lock without exclusivity

Summary

Concurrent::ReentrantReadWriteLock can incorrectly grant a write lock after one thread acquires the read lock 32,768 times.

The lock stores a thread's local read and write hold counts in one integer. The low 15 bits are used for the read hold count, and bit 15 is used as WRITE_LOCK_HELD. After 32,768 reentrant read acquisitions, the local read count crosses into the write-lock bit. try_write_lock then treats the thread as already holding a write lock and returns true without setting the global RUNNING_WRITER bit.

This breaks the core mutual-exclusion guarantee: the caller is told it has a write lock, but other threads can still hold or acquire read locks at the same time.

Version

Software: concurrent-ruby Version: 1.3.6 Commit: 7a1b78941c081106c20a9ca0144ac73a48d254ab

Details

The implementation uses a shared counter to track global readers/writers and a per-thread local counter to support reentrancy:

READER_BITS    = 15
WRITER_BITS    = 14

WAITING_WRITER = 1 << READER_BITS
RUNNING_WRITER = 1 << (READER_BITS + WRITER_BITS)
MAX_READERS    = WAITING_WRITER - 1
MAX_WRITERS    = RUNNING_WRITER - MAX_READERS - 1

WRITE_LOCK_HELD = 1 << READER_BITS
READ_LOCK_MASK  = WRITE_LOCK_HELD - 1
WRITE_LOCK_MASK = MAX_WRITERS

When a thread already holds a lock, acquire_read_lock increments @HeldCount:

if (held = @HeldCount.value) > 0
  if held & READ_LOCK_MASK == 0
    @Counter.update { |c| c + 1 }
  end
  @HeldCount.value = held + 1
  return true
end

After 32,768 read acquisitions, the per-thread held count becomes 32768, which is equal to WRITE_LOCK_HELD. Then try_write_lock returns success through its "already have a write lock" branch:

def try_write_lock
  if (held = @HeldCount.value) >= WRITE_LOCK_HELD
    @HeldCount.value = held + WRITE_LOCK_HELD
    return true
  else
    # normal global writer acquisition path
  end
end

This branch does not set the global RUNNING_WRITER bit. Other threads therefore do not observe an active writer and can continue holding or acquiring read locks while the caller believes it owns the write lock.

PoC

#!/usr/bin/env ruby
# frozen_string_literal: true

require 'concurrent/atomic/reentrant_read_write_lock'
require 'concurrent/version'
require 'thread'

def wait_for_queue(queue, timeout_seconds)
  deadline = Process.clock_gettime(Process::CLOCK_MONOTONIC) + timeout_seconds
  loop do
    return queue.pop(true)
  rescue ThreadError
    return nil if Process.clock_gettime(Process::CLOCK_MONOTONIC) >= deadline

    sleep 0.001
  end
end

puts "ruby=#{RUBY_DESCRIPTION}"
puts "concurrent_ruby_version=#{Concurrent::VERSION}"
puts "poc=ReentrantReadWriteLock read-depth overflow grants write lock without exclusivity"

lock = Concurrent::ReentrantReadWriteLock.new
other_reader_ready = Queue.new
other_reader_stop = Queue.new

other_reader = Thread.new do
  lock.acquire_read_lock
  other_reader_ready << :held
  other_reader_stop.pop
end

wait_for_queue(other_reader_ready, 1)
puts "other_thread_holds_read_lock=true"

depth = Concurrent::ReentrantReadWriteLock::WRITE_LOCK_HELD
depth.times { lock.acquire_read_lock }

held_count = lock.instance_eval { @HeldCount.value }
counter_before = lock.instance_eval { @Counter.value }

puts "main_thread_read_acquisitions=#{depth}"
puts "main_thread_held_count=#{held_count}"
puts "counter_before_try_write=#{counter_before}"
puts "running_writer_bit_before=#{(counter_before & Concurrent::ReentrantReadWriteLock::RUNNING_WRITER) != 0}"

write_granted = lock.try_write_lock
counter_after = lock.instance_eval { @Counter.value }

puts "try_write_lock_returned=#{write_granted}"
puts "counter_after_try_write=#{counter_after}"
puts "running_writer_bit_after=#{(counter_after & Concurrent::ReentrantReadWriteLock::RUNNING_WRITER) != 0}"

third_reader_ready = Queue.new
third_reader = Thread.new do
  lock.acquire_read_lock
  third_reader_ready << :acquired
end

third_reader_acquired = wait_for_queue(third_reader_ready, 0.25) == :acquired
puts "new_reader_acquired_while_write_claimed=#{third_reader_acquired}"

if write_granted && third_reader_acquired && (counter_after & Concurrent::ReentrantReadWriteLock::RUNNING_WRITER).zero?
  puts 'result=REPRODUCED write lock granted without setting global writer state'
else
  puts 'result=NOT_REPRODUCED'
end

third_reader.kill
other_reader_stop << :stop
other_reader.kill