Use of rollback RCU with read-side modifications to RCU-protected data structures

• US 20060130061A1
• Filed: 12/09/2004
• Published: 06/15/2006
• Est. Priority Date: 12/09/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bauer, Robert T., McKenney, Paul E., Russell, Paul F.
• Granted Patent: US 8,176,489 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method, apparatus and program storage device for performing a return/rollback process for RCU-protected data structures is provided that includes checking a user-level state of a preempted thread having a RCU read-side critical section, and executing the critical section of the thread after preemption when the user-level state of the thread indicates execution, otherwise returning to a point of preemption, resuming execution of the thread and disabling checking the user-level state when the user-level state of the thread indicates return.

Claims

1. A program storage device, comprising:

program instructions executable by a processing device to perform operations for performing a return/rollback process for read copy update (RCU) protected data structures, the operations comprising;

determining a thread has been preempted and an exception signal has followed preemption allowing the process to resume;

checking a user-level state of the thread before resuming the process; and

restarting the RCU read-side critical section of the thread when user-level state indicates restart, else returning to a point of preemption, resuming execution and suspending checking of the user-level state when the user-level state indicates a rollback.

2. The process of claim 1, wherein determining the thread has been preempted comprises determining that the thread is in an extended quiescent state.

3. The process of claim 1, wherein determining a thread has been preempted and an exception signal has followed preemption allowing the process to resume comprises processing the signal while preventing the user-level from executing instructions.

4. The process of claim 1, wherein checking the thread user-level state comprises checking the thread user-level state to determine whether the thread holds a lock.

5. The process of claim 4, wherein restarting the RCU read-side critical section when the user-level state indicates restart comprises restarting the RCU read-side critical section when the thread does not hold a lock.

6. The process of claim 4, wherein returning to the point of preemption when the user-level state indicates rollback and suspending checking of the user-level state comprises returning to the point of preemption when the user-level state indicates the thread holds a lock and suspending checking of the user-level state.

7. The process of claim 1, wherein checking the thread user-level state comprises checking a value of a program counter at a point where preemption occurred.

8. The process of claim 1, wherein suspending checking the user-level state comprises setting a per-thread variable.

9. An apparatus for performing a rollback process for RCU-protected data structures, comprising:

a kernel including code for generating a signal enabling resumption of a thread after preemption from executing a critical section; and

an exception handler for checking a user-level state on the thread before resumption of the thread, and for restarting a critical section when the user-level state of the thread indicates restart, else for returning to a point of preemption and suspending checking the user-level state when the user-level state of the thread indicates returning to the point of preemption.

10. The apparatus of claim 9, wherein when the exception handler suspends checking by setting a per-thread variable.

11. The apparatus of claim 9, wherein the thread is a user-level thread.

12. The apparatus of claim 9, wherein the exception handler is positioned at the beginning of each RCU read-side critical section.

13. The apparatus of claim 9, wherein the signal indicating conditional resumption prevents the user-level from executing instructions.

14. The apparatus of claim 9, wherein the exception handler checks the user-level state to determine whether the thread holds a lock.

15. The apparatus of claim 14, wherein the exception handler restarts the critical section when the thread in the user-level state does not hold a lock.

16. The apparatus of claim 14, wherein the exception handler returns to the point of preemption and suspends checking when the user-level state indicates a thread does not hold a lock.

17. The apparatus of claim 9, wherein the handler checks a value of a program counter at a point where preemption occurred.

18. A method for performing a return/rollback process for RCU-protected data structures, comprising:

checking a user-level state of a preempted thread having a RCU read-side critical section; and

executing the critical section of the thread after preemption when the user-level state of the thread indicates execution, else returning to a point of preemption, resuming execution of the thread and disabling checking the user-level state when the user-level state of the thread indicates return.

19. A system for performing a return/rollback process for RCU-protected data structures, comprising:

means for determining a thread has been preempted and an exception signal has followed preemption allowing the thread to resume;

means for checking a user-level state of the thread; and

means for restarting the RCU read-side critical section of the thread when user-level state indicates restart, else returning to a point of preemption, resuming execution and suspending checking of the user-level state when the user-level state indicates a rollback.

20. An apparatus for performing a return/rollback process for RCU-protected data structures, comprising:

means for providing a kernel including code for generating a signal enabling resumption of a thread after preemption from executing a critical section; and

means for providing an exception handler for checking a user-level state on the thread before resumption, and for restarting a critical section when the user-level state of the thread indicates restart, else for returning to the point of preemption and suspending checking the user-level state when the user-level state of the thread indicates returning to the point of preemption.

21. A system for performing a return/rollback process for RCU-protected data structures, comprising:

means for checking a user-level state of a preempted thread having a RCU read-side critical section; and

means for executing the critical section of the thread after preemption when the user-level state of the thread indicates execution, else returning to a point of preemption, resuming execution of the thread and disabling checking the user-level state when the user-level state of the thread indicates return.