USER-LEVEL READ-COPY UPDATE THAT DOES NOT REQUIRE DISABLING PREEMPTION OR SIGNAL HANDLING

• US 20100023946A1
• Filed: 07/28/2008
• Published: 01/28/2010
• Est. Priority Date: 07/28/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Granted Patent: US 8,020,160 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

A user-level read-copy update (RCU) technique. A user-level RCU subsystem executes within threads of a user-level multithreaded application. The multithreaded application may include reader threads that read RCU-protected data elements in a shared memory and updater threads that update such data elements. The reader and updater threads may be preemptible and comprise signal handlers that process signals. Reader registration and unregistration components in the RCU subsystem respectively register and unregister the reader threads for RCU critical section processing. These operations are performed while the reader threads remain preemptible and with their signal handlers being operational. A grace period detection component in the RCU subsystem considers a registration status of the reader threads and determines when it is safe to perform RCU second-phase update processing to remove stale versions of updated data elements that are being referenced by the reader threads, or take other RCU second-phase update processing actions.

Claims

1. A user-level read-copy update (RCU) method, comprising:

establishing a user-level RCU subsystem that executes within threads of a user-level multithreaded application;

said multithreaded application comprising one or more reader threads that read RCU-protected data elements in a shared memory;

said multithreaded application comprising one or more updater threads that update said RCU-protected data elements in said shared memory;

said reader threads and said updater threads being preemptible and comprising signal handlers that process signals;

implementing a reader registration component in said RCU subsystem that registers said reader threads for RCU critical section processing, said reader registration component performing reader registration while said reader threads remain preemptible and with their signal handlers being operational;

implementing a reader unregistration component in said RCU subsystem that unregisters said reader threads from RCU critical section processing, said reader unregistration component performing reader unregistration while said reader threads remain preemptible and their signal handlers are operational; and

implementing a grace period detection component in said RCU subsystem that considers a registration status of said reader threads and determines when it is safe to perform RCU second-phase update processing to remove stale versions of updated data elements that are being referenced by said reader threads, or take other RCU second-phase update processing actions.

2. The method of claim 1, wherein said reader registration component registers said reader threads by manipulating per-reader variables that each specify a per-reader grace period number and a per-reader state that determines whether or not said reader threads are in an RCU critical section.

3. The method of claim 2, wherein said grace period detection component maintains a global variable that specifies a global grace period number and a global reference state, and wherein consideration of said reader registration status comprises comparing said per-reader variables to said global variable and determining that it is safe to perform said RCU second-phase update processing if all of said per-reader variables indicate a per-reader state that is the same as said global reference state or if all of said per-reader variables specify a per-reader grace period that is not earlier than a current grace period specified by said global grace period number.

4. The method of claim 1, further including ensuring the integrity of said reader registration status when considered by said grace period detection component by either (1) said registration component, said unregistration component and said grace period detection component implementing memory barriers that coordinate their respective processing, or (2) said reader threads implementing a signal handler that reports said reader registration status to said grace period detection component, whereby, in either case, said grace period detection component does not determine it is safe to perform said RCU second-phase update processing until all of said reader threads are safe from such processing.

5. The method of claim 1, wherein said registration component refrains from registering said reader threads for RCU critical section processing if said reader threads are performing nested RCU read operations and said reader threads have already been registered for RCU critical section processing.

6. The method of claim 1, wherein said grace period detection component performs batched grace period detection processing.

7. A data processing system for implementing user-level read-copy update (RCU), comprising:

one or more processors;

a memory coupled to said one or more processors, said memory including a computer useable medium tangibly embodying at least one program of instructions executable by said processor to perform operations, comprising;

establishing a user-level RCU subsystem that executes within threads of a user-level multithreaded application;

said multithreaded application comprising one or more reader threads that read RCU-protected data elements in a shared memory;

said multithreaded application comprising one or more updater threads that update said RCU-protected data elements in said shared memory;

said reader threads and said updater threads being preemptible and comprising signal handlers that process signals;

implementing a reader registration component in said RCU subsystem that registers said reader threads for RCU critical section processing, said reader registration component performing reader registration while said reader threads remain preemptible and with their signal handlers being operational;

implementing a reader unregistration component in said RCU subsystem that unregisters said reader threads from RCU critical section processing, said reader unregistration component performing reader unregistration while said reader threads remain preemptible and their signal handlers are operational; and

implementing a grace period detection component in said RCU subsystem that considers a registration status of said reader threads and determines when it is safe to perform RCU second-phase update processing to remove stale versions of updated data elements that are being referenced by said reader threads, or take other RCU second-phase update processing actions.

8. The system of claim 7, wherein said reader registration component registers said reader threads by manipulating per-reader variables that each specify a per-reader grace period number and a per-reader state that determines whether or not said reader threads are in an RCU critical section.

9. The system of claim 8, wherein said grace period detection component maintains a global variable that specifies a global grace period number and a global reference state, and wherein consideration of said reader registration status comprises comparing said per-reader variables to said global variable and determining that it is safe to perform said RCU second-phase update processing if all of said per-reader variables indicate a per-reader state that is the same as said global reference state or if all of said per-reader variables specify a per-reader grace period that is not earlier than a current grace period specified by said global grace period number.

10. The method of claim 7, further including ensuring the integrity of said reader registration status when considered by said grace period detection component by either (1) said registration component, said unregistration component and said grace period detection component implementing memory barriers that coordinate their respective processing, or (2) said reader threads implementing a signal handler that reports said reader registration status to said grace period detection component, whereby, in either case, said grace period detection component does not determine it is safe to perform said RCU second-phase update processing until all of said reader threads are safe from such processing.

11. The system of claim 7 wherein said registration component refrains from registering said reader threads for RCU critical section processing if said reader threads are performing nested RCU read operations and said reader threads have already been registered for RCU critical section processing.

12. The system of claim 7 wherein said grace period detection component performs batched grace period detection processing.

13. A computer program product, comprising:

one or more machine-readable media;

means provided by said one or more media for programming a data processing platform to implement user-level read-copy update (RCU), as by;

establishing a user-level RCU subsystem that executes within threads of a user-level multithreaded application;

said multithreaded application comprising one or more reader threads that read RCU-protected data elements in a shared memory;

said multithreaded application comprising one or more updater threads that update said RCU-protected data elements in said shared memory;

said reader threads and said updater threads being preemptible and comprising signal handlers that process signals;

implementing a reader registration component in said RCU subsystem that registers said reader threads for RCU critical section processing, said reader registration component performing reader registration while said reader threads remain preemptible and with their signal handlers being operational;

implementing a reader unregistration component in said RCU subsystem that unregisters said reader threads from RCU critical section processing, said reader unregistration component performing reader unregistration while said reader threads remain preemptible and their signal handlers are operational; and

implementing a grace period detection component in said RCU subsystem that considers a registration status of said reader threads and determines when it is safe to perform RCU second-phase update processing to remove stale versions of updated data elements that are being referenced by said reader threads, or take other RCU second-phase update processing actions.

14. The computer program product of claim 13, wherein said reader registration component registers said reader threads by manipulating per-reader variables that each specify a per-reader grace period number and a per-reader state that determines whether or not said reader threads are in an RCU critical section.

15. The computer program product of claim 14, wherein said grace period detection component maintains a global variable that specifies a global grace period number and a global reference state, and wherein consideration of said reader registration status comprises comparing said per-reader variables to said global variable and determining that it is safe to perform said RCU second-phase update processing if all of said per-reader variables indicate a per-reader state that is the same as said global reference state or if all of said per-reader variables specify a per-reader grace period that is not earlier than a current grace period specified by said global grace period number.

16. The computer program product of claim 13, further including ensuring the integrity of said reader registration status when considered by said grace period detection component by either (1) said registration component, said unregistration component and said grace period detection component implementing memory barriers that coordinate their respective processing, or (2) said reader threads implementing a signal handler that reports said reader registration status to said grace period detection component, whereby, in either case, said grace period detection component does not determine it is safe to perform said RCU second-phase update processing until all of said reader threads are safe from such processing.

17. The computer program product of claim 13, wherein said registration component refrains from registering said reader threads for RCU critical section processing if said reader threads are performing nested RCU read operations and said reader threads have already been registered for RCU critical section processing.

18. The computer program product of claim 13, wherein said grace period detection component performs batched grace period detection processing.

19. A user-level read-copy update (RCU) method, comprising:

establishing a global grace period variable in a shared memory that is shared with a user-level multithreaded application;

said global variable maintaining a global grace period number and a global reference state, and being writable on behalf of an updater thread in said multithreaded application that needs to update an RCU protected data element in said shared memory;

establishing a per-reader grace period variable for any reader thread in said multithreaded application that needs to access said RCU-protected data element in said shared memory;

when one of said reader threads (active reader) needs to enter an RCU-protected critical section to access one of said data elements, performing reader registration, as by;

setting said active reader'"'"'s per-reader variable to indicate a per-reader status that includes a per-reader grace period value and a per-reader state that indicate said active reader is in an RCU-protected critical section;

executing a memory barrier to ensure that setting of said active reader'"'"'s per-reader variable can be seen by other threads before said active reader commences critical section processing;

when said active reader needs to exit said RCU-protected critical section after accessing one of said data elements, performing reader unregistration, as by;

executing a memory barrier to ensure that said active reader'"'"'s critical section processing has completed before any further manipulation of said active reader'"'"'s per-reader variable value can be seen by other threads;

resetting said active reader'"'"'s per-reader variable to indicate a per-reader status that includes a current per-reader grace period value and a per-reader state that indicates said active reader is not in an RCU-protected critical section;

when said updater thread needs to free a stale data element due to a data element update, or take other RCU second-phase update processing actions, performing grace period detection processing, as by;

executing a memory barrier to ensure that said data element update is seen by other threads as occurring before said grace period detection processing;

setting said global variable to a value that indicates a new grace period and said global reference state;

executing a memory barrier to ensure that said setting of said global variable is seen by other threads as occurring before further grace period detection processing;

inspecting said per-reader variables to determine per-reader status by comparing said per-reader grace period value and per-reader state to said global grace period value and global reference state until it is determined that none of said reader threads are within an RCU-protected critical section that was entered during a previous grace period; and

executing a memory barrier to ensure that said stale data element is not freed until said inspecting is seen by other threads as being completed.

20. The method of claim 19, wherein said global reference state and per-reader state are respectively indicated using a low-order bit, a sign bit, or one or more other bits of said global variable and said per-reader variables.