Скачать или смотреть Using a Malicious User-Level RCU to Torture RCU-Based Algorithms

Presenter(s): Paul McKenney
URL: http://www.linux.org.au/conf/2009/pro...

Read-Copy Update (RCU) is a synchronization mechanism that was added to the Linux kernel during the 2.5 development effort. Loosely speaking, RCU can be thought of as a replacement for reader-writer locking, but where the read-side primitives are extremely lightweight. Indeed, for the non-CONFIG_PREEMPT case, the read-side primitives are no-ops, invisible even to the compiler. The RCU free lunch ends on the update side, however, as RCU updaters must maintain multiple versions of objects until all pre-existing RCU read-side critical sections complete. RCU is therefore most applicable to read-mostly data structures.Because RCU updates can be expensive, Linux-kernel implementations make heavy use of batching techniques that work to amortize the RCU update overhead over all RCU updaters within a given several-millisecond time period. As a result, the latency of RCU updates is normally many milliseconds, which make it difficult to detect some forms of RCU abuse by testing. (It also makes certain types of RCU implementation errors difficult to detect via testing, which is one reason that rcutorture.c exists.) An example of difficult-to-test RCU abuse follows: rcu_read_lock(); p = rcu_dereference(global_ptr); do_something_with(p); rcu_read_unlock(); do_something_else_with(p); /* BUG!!!! */The above code fragment is buggy because a pointer to an RCU-protected data structure is used outside of the RCU read-side critical section. The problem is that an RCU updater would be within its rights to free up the structure pointed to by p immediately after the rcu_read_unlock(), resulting in a use-after-free bug in do_something_else_with(). However, because RCU updates extend for many milliseconds, the chances of this bug being caught by testing are slim indeed -- and are in fact zero for a non-CONFIG_PREEMPT kernel. What is required is an RCU implementation with much faster grace periods so as to be able to more likely to catch such bugs.One candidate is the QRCU patch, which in absence of readers boasts sub-microsecond grace-period latencies. Unfortunately, like SRCU, QRCU's API is incompatible with that of Classic RCU due to the fact that qrcu_read_lock() returns an index that must be passed into qrcu_read_unlock(). Furthermore, catching this type of bug requires the updater to run concurrently with the readers, greatly slowing the QRCU updates. Finally, changes that would speed up the QRCU update would require the updater to spin, which would be unhealthy, particularly in a non-CONFIG_PREEMPT kernel. Safe, sane, and reliable detection of this sort of error is best done at user level.This talk describes a simple (17 semicolons, 131 lines including a pair of GPL comment headers) user-level implementation of the standard RCU API that boasts the sub-microsecond grace periods required to track down this type of bug. In addition, this implementation has efficient and scalable read-side primitives, and tolerates threads blocking indefinitely outside of RCU read-side critical sections. Finally, this implementation does not require disabling of either preemption nor interrupts, nor does it require code in signal handlers. This presents the possibility of its use in arbitrary user-level applications and libraries.

http://lca2009.linux.org.au - http://www.linux.org.au
CC BY-SA - http://creativecommons.org/licenses/b...