Asynchronous grace-period primitives for user-space applications

• US 9,250,978 B2
• Filed: 06/27/2011
• Issued: 02/02/2016
• Est. Priority Date: 06/27/2011
• Status: Expired due to Fees

• 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/169,570
• Publication Number:
  US 20120331237A1
• Time in Patent Office: 1,681 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 system, 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 for implementing user-level read-copy update (RCU) with support for asynchronous grace periods, said 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 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 system 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 system in accordance with claim 2, wherein a single one of said one or more helper threads is assigned to operate as said default helper and at least one of said per-thread helper, said per-CPU helper or said per-node helper.

4. A system 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 system 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 system 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 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 data processing platform to perform operations for implementing user-level read-copy update (RCU) with support for asynchronous grace periods, said 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 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; and

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.

8. A computer program product in accordance with claim 7, 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.

9. A computer program product in accordance with claim 8, 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.

10. A computer program product in accordance with claim 7, 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.

11. A computer program product in accordance with claim 10, 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.

12. A computer program product in accordance with claim 7, wherein said RCU subsystem comprises a set of helper thread functions for creating, ending, waking, querying and assigning said two or more helper threads.