Handling CPU hotplug events in RCU without sleeplocks

• US 9,940,290 B2
• Filed: 10/19/2015
• Issued: 04/10/2018
• Est. Priority Date: 10/02/2015
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Phan, Dean
• Application Number:
  US14/886,518
• Publication Number:
  US 20170097917A1
• Time in Patent Office: 904 Days
• Field of Search: None
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 13/4081 Live connection to bus, e.g. hot-plugging current or voltage limitation during live insertion H02H9/004
• CPC Class Codes: G06F 13/4234 being a memory bus
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/068 Hybrid storage device
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Read-copy update (RCU) grace period initialization and CPU hotplugging are synchronized without a sleeplock. Periodic RCU grace period initialization includes, for each node of a combining tree, copying a first bitmask indicating online/offline status of a set of CPUs to a second bitmask indicating RCU quiescent state status of the CPUs. Periodic CPU hotplug operations include indicating CPU online/offline status to leaf nodes associated with the CPUs. This status is indicated without manipulating any bits in the first bitmask of the leaf nodes. Prior to each RCU grace period initialization, RCU grace period pre-initialization is performed at each leaf node. The RCU grace period pre-initialization includes (1) updating the first bitmask to account for the CPU hotplug operations, and (2) if this results in the first bitmask transitioning between fully cleared and not-fully cleared states, the state change is conditionally propagated to a higher level node.

Claims

1. A method, comprising:

providing a combining tree to track RCU grace periods and CPU hotplug activity, said combining tree comprising;

a root node at a root level of said combining tree and a set of lower level nodes in one or more lower levels of said combining tree, said lower level nodes including a set of two or more leaf nodes at a leaf level of said combining tree, and said lower level nodes optionally including zero or more intermediate nodes in zero or more intermediate levels of said combining tree;

each said leaf node being accessed by a set of assigned CPUs and referencing an assigned higher level node in said combining tree that is said root node if there are two levels in said combining tree or that is one of said intermediate nodes if there are more than two levels in said combining tree;

said root node being referenced by a set of assigned lower level nodes that are said leaf nodes if there are two levels in said combining tree or that are one or more levels of said intermediate nodes if there are more than two levels in said combining tree; and

each node in said combining tree having a first bitmask whose bits indicate online or offline status of said CPUs, and a second bitmask whose bits indicate RCU quiescent state status of said CPUs, each bitmask bit in said leaf nodes directly corresponding to one of said CPUs, and each bitmask bit in said higher level nodes directly corresponding to an assigned lower level node and indirectly corresponding to CPUs represented by said assigned lower level node;

periodically performing RCU grace period initialization in which, for each said node, said first bitmask is copied to said second bitmask;

periodically performing CPU hotplug operations that result in said CPUs coming online or going offline, said CPU hotplug operations indicating online or offline status of said CPUs to said associated leaf nodes to which said CPUs are assigned, said online or offline status being indicated without manipulating any bits in said first bitmask of said leaf nodes;

prior to each RCU grace period initialization, performing RCU grace period pre-initialization at each of said leaf nodes, said RCU grace period pre-initialization including (1) updating said first bitmask by setting or clearing bits to account for said leaf node'"'"'s assigned CPUs that have come online or gone offline as a result of said CPU hotplug operations, and (2) if said updating said first bitmask results in said first bitmask transitioning from a state in which at least one bit is set to a cleared state, or from a cleared state to a state in which at least one bit is set, conditionally propagating said state change to said leaf node'"'"'s assigned higher level node by setting or clearing a bit that corresponds to said leaf node in said higher level node'"'"'s first bitmask; and

synchronizing access to said leaf nodes by said RCU grace period pre-initialization and said CPU hotplug operations without using a sleeplock that prevents said RCU grace-period initialization from running concurrently with manipulations of said combining tree by said CPU hotplug operations.

2. The method of claim 1, wherein said synchronizing access to said leaf nodes by said RCU grace period pre-initialization and said CPU hotplug operations uses a spinlock associated with each of said leaf nodes.

3. The method of claim 1, wherein said CPU hotplug operations indicate online or offline status of said CPUs by manipulating CPU hotplug buffer bits provided in each of said leaf nodes that are not part of said first bitmask or said second bitmask, and wherein said RCU grace period initialization performs said updating of said first bitmask in said leaf nodes by merging said CPU hotplug buffer bits into said first bitmask.

4. The method of claim 3, wherein said CPU hotplug buffer bits are part of a single CPU hotplug buffer bitmask in each of said leaf nodes that continuously indicates CPU hotplug state of CPUs assigned to said leaf nodes.

5. The method of claim 3, wherein said CPU hotplug buffer bits are part of first and second CPU hotplug buffer bitmasks in each of said leaf nodes that are cleared when said first bitmask is updated, said first CPU hotplug buffer bitmask being an online-indicating bitmask and said second CPU hotplug buffer bitmask being an offline-indicating bitmask.

6. The method of claim 5, wherein said CPU hotplug operations manipulate said CPU hotplug buffer bits when said CPUs goes offline by clearing said CPU hotplug buffer bits in said online-indicating bitmask if set, and otherwise setting said CPU hotplug buffer bits in said offline-indicating bitmask, and wherein said CPU hotplug operations manipulate said CPU hotplug buffer bits when said CPUs come online by clearing said CPU hotplug buffer bits in said offline-indicating bitmask if set, and otherwise setting said CPU hotplug buffer bits in said online-indicating bitmask.

7. The method of claim 1, wherein said RCU pre-initialization conditionally reports said state change to said leaf node'"'"'s assigned higher level node based on a condition that there are no blocked tasks associated with said leaf node that were preempted while in an RCU critical section.