Fair high-throughput locking for expedited grace periods

• US 10,282,230 B2
• Filed: 10/03/2016
• Issued: 05/07/2019
• Est. Priority Date: 10/03/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Dudek, Jr., Edward J
• Assistant Examiner(s): Verderamo, III, Ralph A
• Application Number:
  US15/283,471
• Publication Number:
  US 20180095666A1
• Time in Patent Office: 946 Days
• Field of Search: None
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

An updater needing an expedited RCU grace period may initiate a leaf-to-root traversal of a funnel lock embodied as a hierarchical tree of nodes. For each accessed node, the updater may check an indicator to determine if another updater needing the same expedited grace period has visited the node. If true, the updater may add itself to a waitqueue of updaters waiting for the expedited RCU grace period. If false, the updater may set the indicator to indicate it has visited the node, and then continue to a next node. If the updater reaches the root node with no indication that any other updater needing the expedited RCU grace period has visited the nodes accessed by the updater, the updater may, while holding a mutex lock, start a new expedited RCU grace period and at the end thereof wake up other updaters waiting on the expedited RCU grace period.

Claims

1. A method for detecting expedited read-copy update (RCU) grace periods using funnel locking with waitqueues, said method comprising:

determining, by an RCU updater, a future expedited RCU grace period needed to guarantee that a full expedited RCU grace period has elapsed following a current expedited RCU grace period;

initiating, by said RCU updater, a leaf-to-root traversal of a funnel lock embodied as a hierarchical tree of nodes having a single top level root node, a plurality of bottom level leaf nodes, and zero or more intermediate level nodes;

for each node of said funnel lock accessed during said leaf-to-root traversal, checking an indicator to determine if another RCU updater needing said future expedited RCU grace period has visited said node;

if true, adding said RCU updater to a waitqueue of RCU updaters waiting for said future expedited RCU grace period;

if false, setting said indicator to indicate that said RCU updater needing said future expedited RCU grace period has visited said node, and continuing to a next node of said funnel lock;

if said RCU updater reaches said root node with no indication that any other RCU updater needing said future expedited RCU grace period has visited any of said nodes accessed by said RCU updater, then acquiring an expedited RCU grace period mutex lock that serializes expedited RCU grace period operations, starting a new expedited RCU grace period, waiting for said new expedited RCU grace period to elapse, releasing said expedited RCU grace period mutex lock, and initiating a wakeup operation that wakes up other RCU updaters waiting on waitqueues associated with said elapsed new expedited RCU grace period.

2. The method of claim 1, wherein said waitqueue is one of a set of per-node waitqueues maintained by said nodes.

3. The method of claim 2, wherein each of said nodes maintains an array of waitqueues that respectively queue RCU updaters waiting for different expedited RCU grace period.

4. The method of claim 3, wherein each array of waitqueues includes a first waitqueue associated with a current expedited RCU grace period, a second waitqueue associated with a previous expedited RCU grace period, and a third waitqueue associated with a next expedited RCU grace period.

5. The method of claim 1, wherein said indicator is one of a set of per-node indicators maintained by said nodes, each of said per-node indicators being protected by an indicator spinlock.

6. The method of claim 1, further including fastpath pre-processing that includes, prior to initiating said leaf-to-root traversal of said funnel lock, said RCU updater accessing said root node and performing said checking an indicator to determine if another RCU updater needing said future expedited RCU grace period has visited said root node, and if false, said RCU updater attempting acquisition of said expedited RCU grace period mutex lock, and if acquired, performing fastpath processing that includes starting said new expedited RCU grace period, waiting for said new expedited RCU grace period to elapse, releasing said expedited RCU grace period mutex lock, and initiating said wakeup operation that wakes up other RCU updaters waiting on waitqueues associated with said elapsed new expedited RCU grace period.

7. The method of claim 1, further including checking for said future expedited grace period each time said RCU updater accesses one of said nodes.

8. A system, comprising:

a plurality of CPUs;

a memory coupled to said CPUs, said memory including a computer readable storage medium tangibly embodying at least one program of instructions executable by said CPUs to perform operations for detecting expedited read-copy update (RCU) grace periods using funnel locking with waitqueues, said operations comprising;

determining, by an RCU updater, a future expedited RCU grace period needed to guarantee that a full expedited RCU grace period has elapsed following a current expedited RCU grace period;

initiating, by said RCU updater, a leaf-to-root traversal of a funnel lock embodied as a hierarchical tree of nodes having a single top level root node, a plurality of bottom level leaf nodes, and zero or more intermediate level nodes;

for each node of said funnel lock accessed during said leaf-to-root traversal, checking an indicator to determine if another RCU updater needing said future expedited RCU grace period has visited said node;

if true, adding said RCU updater to a waitqueue of RCU updaters waiting for said future expedited RCU grace period;

if false, setting said indicator to indicate that said RCU updater needing said future expedited RCU grace period has visited said node, and continuing to a next node of said funnel lock;

if said RCU updater reaches said root node with no indication that any other RCU updater needing said future expedited RCU grace period has visited any of said nodes accessed by said RCU updater, then acquiring an expedited RCU grace period mutex lock that serializes expedited RCU grace period operations, starting a new expedited RCU grace period, waiting for said new expedited RCU grace period to elapse, releasing said expedited RCU grace period mutex lock, and initiating a wakeup operation that wakes up other RCU updaters waiting on waitqueues associated with said elapsed new expedited RCU grace period.

9. The system of claim 8, wherein said waitqueue is one of a set of per-node waitqueues maintained by said nodes.

10. The system of claim 9, wherein each of said nodes maintains an array of waitqueues that respectively queue RCU updaters waiting for different expedited RCU grace period.

11. The system of claim 10, wherein each array of waitqueues includes a first waitqueue associated with a current expedited RCU grace period, a second waitqueue associated with a previous expedited RCU grace period, and a third waitqueue associated with a next expedited RCU grace period.

12. The system of claim 8, wherein said indicator is one of a set of per-node indicators maintained by said nodes, each of said per-node indicators being protected by an indicator spinlock.

13. The system of claim 8, further including fastpath pre-processing that includes, prior to initiating said leaf-to-root traversal of said funnel lock, said RCU updater accessing said root node and performing said checking an indicator to determine if another RCU updater needing said future expedited RCU grace period has visited said root node, and if false, said RCU updater attempting acquisition of said expedited RCU grace period mutex lock, and if acquired, performing fastpath processing that includes starting said new expedited RCU grace period, waiting for said new expedited RCU grace period to elapse, releasing said expedited RCU grace period mutex lock, and initiating said wakeup operation that wakes up other RCU updaters waiting on waitqueues associated with said elapsed new expedited RCU grace period.

14. The system of claim 8, further including checking for said future expedited grace period each time said RCU updater accesses one of said nodes.

15. A computer program product, comprising:

one or more computer readable data storage media;

program instructions stored on said one or more computer readable data storage media for programming a data processing platform having a plurality of CPUs to perform operations for detecting expedited read-copy update (RCU) grace periods using funnel locking with waitqueues, said operations comprising;

determining, by an RCU updater, a future expedited RCU grace period needed to guarantee that a full expedited RCU grace period has elapsed following a current expedited RCU grace period;

initiating, by said RCU updater, a leaf-to-root traversal of a funnel lock embodied as a hierarchical tree of nodes having a single top level root node, a plurality of bottom level leaf nodes, and zero or more intermediate level nodes;

for each node of said funnel lock accessed during said leaf-to-root traversal, checking an indicator to determine if another RCU updater needing said future expedited RCU grace period has visited said node;

if true, adding said RCU updater to a waitqueue of RCU updaters waiting for said future expedited RCU grace period;

if false, setting said indicator to indicate that said RCU updater needing said future expedited RCU grace period has visited said node, and continuing to a next node of said funnel lock;

if said RCU updater reaches said root node with no indication that any other RCU updater needing said future expedited RCU grace period has visited any of said nodes accessed by said RCU updater, then acquiring an expedited RCU grace period mutex lock that serializes expedited RCU grace period operations, starting a new expedited RCU grace period, waiting for said new expedited RCU grace period to elapse, releasing said expedited RCU grace period mutex lock, and initiating a wakeup operation that wakes up other RCU updaters waiting on waitqueues associated with said elapsed new expedited RCU grace period.

16. The computer program product of claim 15, wherein said waitqueue is one of a set of per-node waitqueues maintained by said nodes.

17. The computer program product of claim 16, wherein each of said nodes maintains an array of waitqueues that respectively queue RCU updaters waiting for different expedited RCU grace period.

18. The computer program product of claim 17, wherein each array of waitqueues includes a first waitqueue associated with a current expedited RCU grace period, a second waitqueue associated with a previous expedited RCU grace period, and a third waitqueue associated with a next expedited RCU grace period.

19. The computer program product of claim 15, wherein said indicator is one of a set of per-node indicators maintained by said nodes, each of said per-node indicators being protected by an indicator spinlock.

20. The computer program product of claim 15, further including fastpath pre-processing that includes, prior to initiating said leaf-to-root traversal of said funnel lock, said RCU updater accessing said root node and performing said checking an indicator to determine if another RCU updater needing said future expedited RCU grace period has visited said root node, and if false, said RCU updater attempting acquisition of said expedited RCU grace period mutex lock, and if acquired, performing fastpath processing that includes starting said new expedited RCU grace period, waiting for said new expedited RCU grace period to elapse, releasing said expedited RCU grace period mutex lock, and initiating said wakeup operation that wakes up other RCU updaters waiting on waitqueues associated with said elapsed new expedited RCU grace period.