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

• US 8,176,489 B2
• Filed: 12/09/2004
• Issued: 05/08/2012
• 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.
• Primary Examiner(s): To, Jennifer
• Assistant Examiner(s): Arcos, Caroline H
• Application Number:
  US11/009,220
• Publication Number:
  US 20060130061A1
• Time in Patent Office: 2,707 Days
• Field of Search: 718/100, 718/102, 718/104, 718/108, 714/38, 711/141, 711/147
• 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 stored thereon, executable by a processing device to perform operations for performing a return/rollback process for a read copy update (RCU) read-side critical section that references an RCU protected data structure, the operations comprising;

determining a thread executing an RCU read-side critical section has been preempted, wherein the determining comprises determining that the thread is in an extended quiescent state;

an exception handler checking a user-level state of the thread to determine whether the thread holds a lock before resuming the thread, wherein the lock for a resource is acquired in the critical section of the thread; and

rolling back the thread to a beginning of the RCU read-side critical section of the thread when the user-level state indicates restart in absence of the lock held by the thread, else when the user-level state indicates the thread holds the lock, returning to a point of preemption, resuming execution and suspending checking of the user-level state for the lock.

2. The program storage device of claim 1, wherein the operation of determining a thread has been preempted further comprising processing an exception signal while preventing the thread from executing instructions.

3. The program storage device of claim 1, wherein the operation of returning to the point of preemption when the user-level state indicates rollback and suspending checking of the user-level state further comprising returning to the point of preemption when the user-level state indicates the thread holds the lock and suspending checking of the user-level state.

4. The program storage device of claim 1, wherein the operation of checking the thread user-level state further comprising checking a value of a program counter at a point where preemption occurred.

5. The program storage device of claim 1, wherein the operation of suspending checking the user-level state further comprising setting a per-thread variable.

6. An apparatus for performing a return/rollback process for a read copy update (RCU) read side critical section that references RCU protected data structures, comprising:

a processor in communication with memory;

said processor to determine a thread executing an RCU read-side critical section has been preempted, comprising determining that the thread is in an extended quiescent state, and executing an exception handler for checking a user-level state on the thread to determine whether the thread holds a lock before resuming the thread, wherein the lock for a resource is acquired in the critical section of the thread; and

said processor to roll back the thread to a beginning of the RCU read-side critical section when the user-level state of the thread indicates restart in absence of a lock held by the thread, else when the user-level state indicates the thread holds the lock, returning to a point of preemption and suspending checking the user-level state for the lock.

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

8. The apparatus of claim 6, wherein the thread is a user-level thread.

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

10. The apparatus of claim 6, wherein the signal indicating conditional resumption prevents the thread from executing instructions.

11. The apparatus of claim 6, wherein the exception handler rolls back to the point of preemption and suspends checking when the user-level state indicates the thread does not hold the lock.

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

13. A method for performing a return/rollback process for a read copy update (RCU) read side critical section that references RCU protected data structures, comprising:

determining a thread executing an RCU read-side critical section has been preempted, wherein the determining comprises determining that the thread is in an extended quiescent state;

checking, by an exception handler, a user-level state of the thread preempted in the RCU read-side critical section to determine whether the thread holds a lock before resuming the thread, wherein the lock for a resource is acquired in the critical section of the thread; and

executing a roll back process to a beginning of the RCU read-side critical section of the thread after preemption when the user-level state of the thread indicates restart in absence of the lock held by the thread, else when the user-level state indicates the thread holds the lock, returning to a point of preemption, resuming execution of the thread and disabling checking the user-level state for the lock.

14. A computer program product for performing a return/rollback process for a read copy update (RCU) read side critical section that references RCU protected data structures, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

means for determining a thread executing an RCU read-side critical section has been preempted, comprising determining that the thread is in an extended quiescent state, and an exception signal has followed preemption allowing the thread to resume;

means for checking a user-level state of the thread for to determine whether the thread holds a lock before resuming the thread, wherein the lock for a resource is acquired in the critical section of the thread; and

means for rolling back the thread to a beginning of the RCU read-side critical section of the thread when the user-level state indicates restart in absence of the lock held by the thread, else when the user-level state indicates the thread holds the lock, returning to a point of preemption, resuming execution and suspending checking of the user-level state for the lock.

15. An apparatus for performing a return/rollback process for a read copy update (RCU) read-side critical section that references RCU protected data structures, comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

instruction for determining a thread executing a RCU read-side critical section has been preempted, wherein the determining comprises determining that the thread is in an extended quiescent state;

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

instructions for providing an exception handler for checking a user-level state of the thread for a lock before resumption, wherein the lock for a resource is acquired in the critical section of the thread, and for rolling back the thread at to a beginning of the RCU read-side the critical section when the user-level state of the thread indicates restart in absence of the lock held by the thread, else when the user-level state indicates the thread holds the lock, for returning to a point of preemption and suspending checking the user-level state for the lock.

16. A system for performing a return/rollback process for a read copy update (RCU) read-side critical section that references RCU protected data structures, comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

means for determining a thread executing an RCU read-side critical section has been preempted, wherein the determining comprises determining that the thread is in an extended quiescent state;

means for checking for a user-level state of the preempted thread to determine whether the thread holds a lock before resuming the thread, wherein the lock for a resource is acquired in the critical section of the thread; and

means for executing roll back of the critical section of the thread after preemption when the user-level state of the thread indicates restart in absence of the lock held by the thread, else when the user-level state indicates the threads holds the lock returning to a point of preemption, resuming execution of the thread and disabling checking the user-level state for the lock.