Resolving RCU-scheduler deadlocks

• US 9,003,420 B2
• Filed: 05/18/2012
• Issued: 04/07/2015
• Est. Priority Date: 05/18/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Zhe, Mengyao
• Assistant Examiner(s): Zhao, Bing
• Application Number:
  US13/475,003
• Publication Number:
  US 20130311995A1
• Time in Patent Office: 1,054 Days
• Field of Search: None
• US Class Current: 718/107
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A technique for resolving deadlocks between an RCU subsystem and an operating system scheduler. An RCU reader manipulates a counter when entering and exiting an RCU read-side critical section. At the entry, the counter is incremented. At the exit, the counter is manipulated differently depending on the counter value. A first counter manipulation path is taken when the counter indicates a task-context RCU reader is exiting an outermost RCU read-side critical section. This path includes condition-based processing that may result in invocation of the operating system scheduler. The first path further includes a deadlock protection operation that manipulates the counter to prevent an intervening RCU reader from taking the same path. The second manipulation path is taken when the counter value indicates a task-context RCU reader is exiting a non-outermost RCU read-side critical section, or an RCU reader is nested within the first path. This path bypasses the condition-based processing.

Claims

1. A system, comprising:

one or more processors;

a memory coupled to said processors, said memory including a computer useable storage medium tangibly embodying at least one program of instructions executable by said processors to implement a read-copy update (RCU) subsystem and to perform operations for resolving deadlocks between said RCU subsystem and an operating system scheduler, comprising;

providing an RCU registration component that allows an RCU reader to manipulate an rcu_read_lock_nesting counter when said RCU reader enters an RCU read-side critical section;

providing an RCU unregistration component that allows an RCU reader to manipulate said rcu_read_lock_nesting counter when said RCU reader leaves an RCU read-side critical section;

said unregistration component providing first and second rcu_read_lock_nesting manipulation paths that are dependent on a current value of said rcu_read_lock_nesting counter;

said first rcu_read_lock_nesting manipulation path being taken when said current value of said rcu_read_lock_nesting counter is indicative of a task-context RCU reader exiting an outermost RCU read-side critical section;

said first rcu_read_lock_nesting manipulation path including condition-based read-side helper processing that may result in invocation of said operating system scheduler;

said first rcu_read_lock_nesting manipulation path further including a deadlock protection operation that manipulates said rcu_read_lock_nesting counter to prevent any intervening RCU reader from taking said first rcu_read_lock_nesting manipulation path while a task-context RCU reader is within that path;

said second rcu_read_lock_nesting manipulation path being taken when said current value of said rcu_read_lock_nesting counter is indicative of a task-context RCU reader exiting a non-outermost RCU read-side critical section or an RCU reader being nested within said first rcu_read_lock_nesting manipulation path;

said second rcu_read_lock_nesting manipulation path bypassing said condition-based read-side helper processing

said RCU unregistration component allowing an RCU reader to manipulate said rcu_read_lock_nesting counter by either decrementing it or setting it to a value, depending on which manipulation path is taken by said RCU reader; and

said first manipulation path comprising setting said rcu_read_lock_nesting counter to a deadlock protection value and said second manipulation path comprises decrementing said rcu_read_lock_nesting counter.

2. The system of claim 1, wherein said RCU registration component allows an RCU reader to manipulate said rcu_read_lock_nesting counter by incrementing it.

3. The system of claim 1, wherein said first manipulation path is taken when said rcu_read_lock_nesting counter has a first count value that is indicative of said task-context RCU reader exiting all RCU read-side critical section processing, and comprises setting said rcu_read_lock_nesting counter to an arbitrary second count value representing said deadlock protection value, performing said read-side helper processing, and setting said rcu_read_lock_nesting counter to a third count value that is indicative of said task-context RCU reader being outside of an RCU read-side critical section.

4. The system of claim 3, wherein said arbitrary second count value is a large negative number.

5. The system of claim 3, wherein said second manipulation path is taken when said rcu_read_lock_nesting counter has any value other than said first count value, and comprises decrementing said rcu_read_lock_nesting counter and bypassing said read-side helper processing.

6. A computer program product, comprising:

one or more non-transitory machine-useable storage media;

program instructions provided by said one or more media for programming a processing platform to implement a read-copy update (RCU) subsystem and to perform operations for resolving deadlocks between said RCU subsystem and an operating system scheduler, comprising;

providing an RCU registration component that allows an RCU reader to manipulate an rcu_read_lock_nesting counter when said RCU reader enters an RCU read-side critical section;

providing an RCU unregistration component that allows an RCU reader to manipulate said rcu_read_lock_nesting counter when said RCU reader leaves an RCU read-side critical section;

said unregistration component providing first and second rcu_read_lock_nesting manipulation paths that are dependent on a current value of said rcu_read_lock_nesting counter;

said first rcu_read_lock_nesting manipulation path being taken when said current value of said rcu_read_lock_nesting counter is indicative of a task-context RCU reader exiting an outermost RCU read-side critical section;

said first rcu_read_lock_nesting manipulation path including condition-based read-side helper processing that may result in invocation of said operating system scheduler;

said first rcu_read_lock_nesting manipulation path further including a deadlock protection operation that temporarily manipulates said rcu_read_lock_nesting counter to prevent any intervening RCU reader from taking said first rcu_read_lock_nesting manipulation path while a task-context RCU reader is within that path;

said second rcu_read_lock_nesting manipulation path being taken when said current value of said rcu_read_lock_nesting counter is indicative of a task-context RCU reader exiting a non-outermost RCU read-side critical section or an RCU reader being nested within said first rcu_read_lock_nesting manipulation path;

said second rcu_read_lock_nesting manipulation path bypassing said condition-based read-side helper processing;

said RCU unregistration component allowing an RCU reader to manipulate said rcu_read_lock_nesting counter by either decrementing it or setting it to a value, depending on which manipulation path is taken by said RCU reader; and

said first manipulation path comprising setting said rcu_read_lock_nesting counter to a deadlock protection value and said second manipulation path of said unregistration component comprises decrementing said rcu_read_lock_nesting counter.

7. The computer program product of claim 6, wherein said RCU registration component allows an RCU reader to manipulate said rcu_read_lock_nesting counter by incrementing it.

8. The computer program product of claim 6, wherein said first manipulation path is taken when said rcu_read_lock_nesting counter has a first count value that is indicative of said task-context RCU reader exiting all RCU read-side critical section processing, and comprises setting said rcu_read_lock_nesting counter to an arbitrary second count value representing said deadlock protection value, performing said read-side helper processing, and setting said rcu_read_lock_nesting counter to a third count value that is indicative of said task-context RCU reader being outside of an RCU read-side critical section.

9. The computer program product of claim 8, wherein said arbitrary second count value is a large negative number.

10. The computer program product of claim 8, wherein said second manipulation path is taken when said rcu_read_lock_nesting counter has any value other than said first count value, and comprises decrementing said rcu_read_lock_nesting counter and bypassing said read-side helper processing.