Asynchronous grace-period primitives for user-space applications

• US 9,250,979 B2
• Filed: 04/24/2012
• Issued: 02/02/2016
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Nguyen, Van
• Assistant Examiner(s): ALFRED, MELISSA A
• Application Number:
  US13/454,443
• Publication Number:
  US 20120331238A1
• Time in Patent Office: 1,379 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A technique for implementing user-level read-copy update (RCU) with support for asynchronous grace periods. In an example embodiment, a user-level RCU subsystem is established that executes within threads of a user-level multithreaded application. The multithreaded application may comprise one or more reader threads that read RCU-protected data elements in a shared memory. The multithreaded application may further comprise one or more updater threads that perform updates to the RCU-protected data elements in the shared memory and register callbacks to be executed following a grace period in order to free stale data resulting from the updates. The RCU subsystem may implement two or more helper threads (helpers) that are created or selected as needed to track grace periods and execute the callbacks on behalf of the updaters instead of the updaters performing such work themselves.

Claims

1. A user-level read-copy update (RCU) method that supports asynchronous grace periods, 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 perform updates to said RCU-protected data elements in said shared memory and register callbacks to be executed following a grace period in order to free stale data resulting from said updates;

said RCU subsystem comprising two or more helper threads (helpers) that are created or selected as needed to track grace periods and execute said callbacks on behalf of said updaters instead of said updaters performing such work themselves;

wherein said RCU subsystem comprises a grace period detection/callback processing component that is implemented by said two or more helper threads on behalf of said updaters; and

wherein said grace period detection/callback processing component processes callbacks while they are pending, then either (1) polls for a specified time period to await new callbacks if a real-time updater is being serviced, or (2) sleeps to await awakening if a non-real-time updater is being serviced.

2. A method in accordance with claim 1, wherein said two or more helper threads include a default helper and one or more of a per-thread helper, a per-CPU helper or a per-node helper.

3. A method in accordance with claim 2, wherein a single one of said two or more helper threads is assigned to operate as said default helper and as at least one of said per-thread helper, said per-CPU helper or said per-node helper.

4. A method in accordance with claim 1, wherein said two or more helper threads each have an associated helper thread data structure whose fields include a callback list header field, a flags field, a lock field, a condition field, a callback list length field, a helper thread identifier field and a list head field.

5. A method in accordance with claim 4, wherein said RCU subsystem comprises a register callback component that enqueues a callback on said callback list of one of said helper thread data structures and wakes up said data structure'"'"'s associated helper thread.

6. A method in accordance with claim 1 wherein said RCU subsystem comprises a set of helper thread functions for creating, ending, waking, querying and assigning said two or more helper threads.

7. A user-level read-copy update (RCU) method that supports asynchronous grace periods, 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 perform updates to said RCU-protected data elements in said shared memory and register callbacks to be executed following a grace period in order to free stale data resulting from said updates;

said RCU subsystem comprising plural helper threads (helpers) that are separate from said updaters and which track grace periods and execute said callbacks on behalf of said updaters;

said helper threads comprising a default helper and one or more of a per-thread helper, a per-CPU helper or a per-node helper;

wherein said RCU subsystem comprises a grace period detection/callback processing component that is implemented by said two or more helper threads on behalf of said updaters; and

wherein said grace period detection/callback processing component processes callbacks while they are pending, then either (1) polls for a specified time period to await new callbacks if a real-time updater is being serviced, or (2) sleeps to await awakening if a non-real-time updater is being serviced.