Funnel locking for normal RCU grace period requests

• US 10,613,913 B1
• Filed: 10/06/2018
• Issued: 04/07/2020
• Est. Priority Date: 10/06/2018
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Portka, Gary J
• Application Number:
  US16/153,731
• Publication Number:
  US 20200110642A1
• Time in Patent Office: 549 Days
• Field of Search: 710200, 711155, 711159
• CPC Class Codes: G06F 12/0877 Cache access modes
• CPC Class Codes: G06F 13/1605 based on arbitration arbitration in handling access to a common bus or bus system G06F13/36
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 9/468 Specific access rights for resources, e.g. using capability register
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

A funnel locking technique for normal read-copy update (RCU) grace period requests. Based on a calculated future normal RCU grace period, a traversal is initiated of a funnel lock embodied as a hierarchical tree of nodes. The funnel-lock traversal starts at an initial node whose lock is held throughout the funnel-lock traversal. For each node accessed during the funnel-lock traversal that is not the initial node, a lock on the node is held while accessing that node. For each accessed node, the funnel-lock traversal is terminated if the future normal RCU grace period has already been requested at that node, if the node believes that the future normal RCU grace period as already started, or if the node is not the initial node and believes that any normal RCU grace period is underway. Otherwise, a request for the future normal RCU grace period is recorded at the node.

Claims

1. A computer-implemented method, comprising:

calculating a future normal RCU grace period based on the status of a current RCU grace period;

initiating a traversal of a funnel lock embodied as a hierarchical tree of nodes having a single top level root node, one or more bottom level leaf nodes, and zero or more intermediate level nodes;

the funnel-lock traversal starting at an initial node whose node lock is held throughout the funnel-lock traversal;

for each node accessed during the funnel-lock traversal that is not the initial node, holding a node lock on the node while accessing that node;

for each node accessed during the funnel-lock traversal, checking future normal RCU grace period request information maintained by the node to determine whether a first condition exists wherein the future normal RCU grace period has already been requested at that node, and responsive to the first condition being determined to exist, terminating the funnel-lock traversal;

for each node accessed during the funnel-lock traversal, checking current normal RCU grace period information maintained by the node to determine whether a second condition exists wherein the future normal RCU grace period as already started, and responsive to the second condition being determined to exist, terminating the funnel-lock traversal;

for each node accessed during the funnel-lock traversal that is not the initial node, checking the current normal RCU grace period information maintained by the node to determine whether a third condition exists wherein any normal RCU grace period is currently underway, and responsive to the third condition being determined to exist, terminating the funnel-lock traversal; and

for each node accessed during the funnel-lock traversal wherein neither the first condition, the second condition, nor the third condition are determined to exist, updating the future normal RCU grace period request information maintained by the node to record a request for the future normal RCU grace period.

2. The method of claim 1, wherein the funnel-lock traversal starts at a non-root node of the hierarchical tree of nodes.

3. The method of claim 1, wherein the funnel-lock traversal starts the root node of the hierarchical tree of nodes.

4. The method of claim 1, wherein the node lock of each node that is not the initial node is released in response to terminating the funnel-lock traversal at that node, but wherein the node lock of the initial node is held in response to terminating the funnel-lock traversal.

5. The method of claim 1, wherein state is set to start a normal RCU grace period in response to accessing the root node and determining that a normal RCU grace period is not in progress and a grace period kernel thread has been started.

6. The method of claim 1, wherein the future RCU grace period is calculated as being one normal RCU grace period following the current RCU grace period in response to:

the node lock of the root node being held and the current normal RCU grace period information maintained by the root node indicating there is no normal RCU grace period currently in progress;

or

the node lock of a non-root node being held and the current normal RCU grace period information maintained by the non-root node indicating there is no normal RCU grace period currently in progress, and a non-locking check of current normal RCU grace period information maintained by a global RCU state structure confirming there is no normal RCU grace period in progress.

7. The method of claim 6, wherein the future RCU future RCU grace period is calculated as being two normal RCU grace periods following the current RCU grace period in response to:

either the node lock of the root node or a non-root node being held, and the current normal RCU grace period information maintained by the root node or the non-root node indicating there is a normal RCU grace period currently in progress;

or

the node lock of a non-root node being held, the current normal RCU grace period information maintained by the non-root node indicating there is no normal RCU grace period currently in progress, but a non-locking check of current normal RCU grace period information maintained by a global RCU state structure indicating there is in fact a normal RCU grace period in progress.

8. A system, comprising:

a plurality of processors;

a computer readable storage medium;

program instructions stored on the computer readable storage medium for execution by one or more of the processors to perform funnel-locking operations for normal read-copy update (RCU) grace period requests, the operations comprising;

calculating a future normal RCU grace period based on the status of a current RCU grace period;

initiating a traversal of a funnel lock embodied as a hierarchical tree of nodes having a single top level root node, one or more bottom level leaf nodes, and zero or more intermediate level nodes;

the funnel-lock traversal starting at an initial node whose node lock is held throughout the funnel-lock traversal;

for each node accessed during the funnel-lock traversal that is not the initial node, holding a node lock on the node while accessing that node;

for each node accessed during the funnel-lock traversal, checking future normal RCU grace period request information maintained by the node to determine whether a first condition exists wherein the future normal RCU grace period has already been requested at that node, and responsive to the first condition being determined to exist, terminating the funnel-lock traversal;

for each node accessed during the funnel-lock traversal, checking current normal RCU grace period information maintained by the node to determine whether a second condition exists wherein the future normal RCU grace period as already started, and responsive to the second condition being determined to exist, terminating the funnel-lock traversal;

for each node accessed during the funnel-lock traversal that is not the initial node, checking the current normal RCU grace period information maintained by the node to determine whether a third condition exists wherein any normal RCU grace period is currently underway, and responsive to the third condition being determined to exist, terminating the funnel-lock traversal; and

for each node accessed during the funnel-lock traversal wherein neither the first condition, the second condition, nor the third condition are determined to exist, updating the future normal RCU grace period request information maintained by the node to record a request for the future normal RCU grace period.

9. The system of claim 8, wherein the funnel-lock traversal starts at a non-root node of the hierarchical tree of nodes.

10. The system of claim 8, wherein the funnel-lock traversal starts the root node of the hierarchical tree of nodes.

11. The system of claim 8, wherein the node lock of each node that is not the initial node is released in response to terminating the funnel-lock traversal at that node, but wherein the node lock of the initial node is held in response to terminating the funnel-lock traversal.

12. The system of claim 8, wherein state is set to start a normal RCU grace period in response to accessing the root node and determining a normal RCU grace period is not in progress and a grace period kernel thread has been started.

13. The system of claim 8, wherein the future RCU grace period is calculated as being one normal RCU grace period following the current RCU grace period in response to:

the node lock of the root node being held and the current normal RCU grace period information maintained by the root node indicating there is no normal RCU grace period currently in progress;

or

the node lock of a non-root node being held and the current normal RCU grace period information maintained by the non-root node indicating there is no normal RCU grace period currently in progress, and a non-locking check of current normal RCU grace period information maintained by a global RCU state structure confirming there is no normal RCU grace period in progress.

14. The system of claim 13, wherein the future RCU future RCU grace period is calculated as being two normal RCU grace periods following the current RCU grace period in response to:

either the node lock of the root node or a non-root node being held, and the current normal RCU grace period information maintained by the root node or the non-root node indicating there is a normal RCU grace period currently in progress;

or

the node lock of a non-root node being held, the current normal RCU grace period information maintained by the non-root node indicating there is no normal RCU grace period currently in progress, but a non-locking check of current normal RCU grace period information maintained by a global RCU state structure indicating there is in fact a normal RCU grace period in progress.

15. A computer program product, comprising:

a computer readable storage medium;

program instructions stored on the computer readable storage medium for execution by a processor to perform funnel-locking operations for normal read-copy update (RCU) grace period requests, the operations comprising;

calculating a future normal RCU grace period based on the status of a current RCU grace period;

initiating a traversal of a funnel lock embodied as a hierarchical tree of nodes having a single top level root node, one or more bottom level leaf nodes, and zero or more intermediate level nodes;

the funnel-lock traversal starting at an initial node whose node lock is held throughout the funnel-lock traversal;

for each node accessed during the funnel-lock traversal that is not the initial node, holding a node lock on the node while accessing that node;

for each node accessed during the funnel-lock traversal, checking future normal RCU grace period request information maintained by the node to determine whether a first condition exists wherein the future normal RCU grace period has already been requested at that node, and responsive to the first condition being determined to exist, terminating the funnel-lock traversal;

for each node accessed during the funnel-lock traversal, checking current normal RCU grace period information maintained by the node to determine whether a second condition exists wherein the future normal RCU grace period as already started, and responsive to the second condition being determined to exist, terminating the funnel-lock traversal;

for each node accessed during the funnel-lock traversal that is not the initial node, checking the current normal RCU grace period information maintained by the node to determine whether a third condition exists wherein any normal RCU grace period is currently underway, and responsive to the third condition being determined to exist, terminating the funnel-lock traversal; and

for each node accessed during the funnel-lock traversal wherein neither the first condition, the second condition, nor the third condition are determined to exist, updating the future normal RCU grace period request information maintained by the node to record a request for the future normal RCU grace period.

16. The computer program product of claim 15, wherein the funnel-lock traversal starts at a non-root node of the hierarchical tree of nodes.

17. The computer program product of claim 15, wherein the funnel-lock traversal starts the root node of the hierarchical tree of nodes.

18. The computer program product of claim 15, wherein the node lock of each node that is not the initial node is released in response to terminating the funnel-lock traversal at that node, but wherein the node lock of the initial node is held in response to terminating the funnel-lock traversal.

19. The computer program product of claim 15, wherein state is set to start a normal RCU grace period in response to accessing the root node and determining a normal RCU grace period is not in progress and a grace period kernel thread has been started.

20. The system of claim 15, wherein the future RCU grace period is calculated as being one normal RCU grace period following the current RCU grace period in response to:

the node lock of the root node being held and the current normal RCU grace period information maintained by the root node indicating there is no normal RCU grace period currently in progress;

or

the node lock of a non-root node being held and the current normal RCU grace period information maintained by the non-root node indicating there is no normal RCU grace period currently in progress, and a non-locking check of current normal RCU grace period information maintained by a global RCU state structure confirming there is no normal RCU grace period in progress; and

wherein the future RCU future RCU grace period is calculated as being two normal RCU grace periods following the current RCU grace period in response to;

either the node lock of the root node or a non-root node being held, and the current normal RCU grace period information maintained by the root node or the non-root node indicating there is a normal RCU grace period currently in progress;

or

the node lock of a non-root node being held, the current normal RCU grace period information maintained by the non-root node indicating there is no normal RCU grace period currently in progress, but a non-locking check of current normal RCU grace period information maintained by a global RCU state structure indicating there is in fact a normal RCU grace period in progress.