International Business Machines Corporation

Sequent Computer Systems, Inc.

Globalfoundries Inc.

Other

Globalfoundries U.S. 2 LLC

Paul Edward McKenney

Dipankar Das Sarma

Joshua A Triplett

Orran Yaakov Krieger

Brent A Kingsbury

Phillip E Krueger

Maged M Michael

Suparna Bhattacharya

John D Slingwine

Ramakrishnan Rajamony

Ronald Lynn Rockhold

Maneesh Soni

Benedict Joseph Jackson

Corene Casper

Paul F Russell

Stuart A Friedberg

Dharmendra S Modha

Julian Satran

Boas Betzler

Michal Ostrowski

Michael C Wong

Jonathan Appavoo

Sorav Bansal

Brent William Yardley

Luke Matthew Browning

Thomas Stanley Mathews

Claudia Andrea Salzberg

John K Whetzel

Manuel Mayr

James Bernard Moody

Raghupathi Malige

Albert Andre Asselin

Stephen F Correl

Vaddagiri Srivatsa

Jeffrey Michael Franke

Pradeep Satyanarayana

Torez Smith

Kenneth Frank Dove

Kevin A Closson

Debora Velarde

Theodore Y Tso

Craig N Butler

Akimasa Fleshler

Swaminathan Sivasubramanian

John G Stultz

William L Irwin, Iii

Jean-Marie Christian Sulmont

Chandrasekhar Pulmarasetti

Rene Vandenbroeck

Peter H Reynolds

Keith Mannthey

Lawrence Roy

Robert T Bauer

Jonathan Walpole

Gautham R Shenoy

An augmented sleepable read-copy update implementation (PREEMPT_SRCU) combines elements of a tree-based sleepable read-copy update environment (Tree-SRCU) with elements of a preemptible read-copy update environment (Preemptible-RCU). The elements of Tree-SRCU may be used to manage PREEMPT_SRCU grace periods and handle PREEMPT_SRCU callbacks. The elements of Preemptible-RCU may be used to drive existing PREEMPT_SRCU grace periods to completion.

Replacing preemptible RCU with an augmented SRCU implementation

A technique for determining when it is safe to use scheduler lock-acquiring wakeups to defer quiescent states in real-time preemptible read-copy update (RCU). A determination may be made whether a deferred quiescent-state reporting request that defers the reporting of an RCU quiescent state on behalf of a target computer task is warranted. If so, it may be determined whether a previous deferred quiescent-state reporting request on behalf of the target computer task remains pending. A request may be issued for deferred quiescent-state report processing that reports a deferred quiescent state. The request for deferred quiescent-state report processing may be issued in a manner selected according to a result of the determining whether a previous deferred quiescent-state reporting request remains pending.

Determining when it is safe to use scheduler lock-acquiring wakeups to defer quiescent states in real-time preemptible read-copy update

A funnel locking technique improves scalability of callback handling while mediating grace-period-start requests in a sleepable read-copy update (SRCU) environment. Per-CPU data structures maintain lists of SRCU callbacks. A management data structure maintains a current-grace-period record tracking a current SRCU grace period and a future-grace-period record tracking a future SRCU grace period needed by the callbacks. A combining tree mediates grace-period-start requests concurrently vying for an opportunity to update the future-grace-period record. The grace-period-start requests are issued on behalf of the callbacks to a combining tree leaf level and propagate toward a combining tree root node. The future-grace-period record is updated in response to grace-period-start requests reaching the root node. The current-grace-period record is updated to start a new SRCU grace period in response to grace-period-start requests reaching the root node if the future SRCU grace period has not completed and there is no SRCU grace period in progress.

Funnel locking for sleepable read-copy update

A technique includes monitoring for a quiescent state by checking first quiescent state criteria that are indicative of a CPU having no task running inside an RCU read-side critical section that could be affected by destructive-to-reader actions. If the quiescent state has been reached, a check may be made for the existence of a condition that is indicative of a requirement to satisfy one or more additional quiescent state criteria before reporting the quiescent state on behalf of the CPU. If the condition is detected, reporting of the quiescent state may be deferred until the one or more additional quiescent state criteria are satisfied. The quiescent state may then be reported if it is useful and safe to do so.

Consolidating read-copy update types having different definitions of a quiescent state

A technique for using expedited RCU grace periods to avoid avoiding out-of-memory conditions for offloaded RCU callbacks. In an example embodiment, one or more processors in a computer system may be designated as no-callbacks (No-CBs) processors that do not perform read-copy update (RCU) callback processing. One or more RCU callback offload kernel threads (rcuo kthreads) may be spawned to perform RCU callback management for RCU callbacks generated by workloads running on the No-CBs processors. The rcuo kthreads may run on processors that are not No-CBs processors. The rcuo kthreads may perform RCU grace period waiting as part of their RCU callback management. The RCU grace period waiting may include selectively invoking either an RCU expedited grace period or waiting for a normal RCU grace period to elapse.

Using expedited RCU grace periods to avoid out-of-memory conditions for offloaded RCU callbacks

In an SRCU environment, per-processor data structures each maintain a list of SRCU callbacks enqueued by SRCU updaters. An SRCU management data structure maintains a current-grace-period counter that tracks a current SRCU grace period, and a future-grace-period counter that tracks a farthest-in-the-future SRCU grace period needed by the SRCU callbacks enqueued by the SRCU updaters. A combining tree is used to mediate a plurality of grace-period-start requests concurrently vying for an opportunity to update the future-grace-period record on behalf of SRCU callbacks. The current-grace-period counter is prevented from wrapping during some or all of the grace-period-start request processing. In an embodiment, the counter wrapping is prevented by performing some or all of the grace-period start-request processing within an SRCU read-side critical section.

Prevent counter wrap during update-side grace-period-request processing in tree-SRCU implementations

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.

Funnel locking for normal RCU grace period requests

A technique for enabling a real-time CPU-bound in-kernel workload to run an infinite loop while keeping read-copy update (RCU) grace periods finite. In an embodiment, a per-CPU indicator may be set to indicate that a CPU running the CPU-bound in-kernel workload has not reported an RCU quiescent state within a first defined time. An RCU grace period operation may be invoked from within the workload that causes an RCU quiescent state to be reported on behalf of the CPU if the per-CPU indicator is set. If the RCU quiescent state is not reported within a second defined time that is longer than the first defined time and sufficiently long to indicate an error condition requiring CPU rescheduling, the CPU may be rescheduled.

Enabling real-time CPU-bound in-kernel workloads to run infinite loops while keeping RCU grace periods finite

A technique for atomically moving a linked data element may include providing an atomic-move wrapper around the data element, along with an existence header whose status may be permanent, outgoing or incoming to indicate whether the data element is not in transition, or if in transition is either outgoing or incoming. The existence header may reference an existence group having a state field that changes state using a single store operation. A first state may indicate that the data element exists if its existence header is outgoing, and does not exist if its existence header is incoming. A second state may indicate that the data element exists if its existence header is incoming, and does not exist if its existence header is outgoing. Following the state change, the existence group and any atomic-move wrapper containing an outgoing existence header and data element may be freed following an RCU grace period.

Atomically moving data elements between or within linked data structures having no support for atomic moves

A technique for short-circuiting normal read-copy update (RCU) grace period computations in the presence of expedited RCU grace periods. Both normal and expedited RCU grace period processing may be periodically performing to respectively report normal and expedited quiescent states on behalf of CPUs in a set of CPUs until all of the CPUs have respectively reported normal or expedited quiescent states so that the normal and expedited grace periods may be respectively ended. The expedited grace periods are of shorter duration than the normal grace periods. Responsive to a condition indicating that the normal RCU grace period processing can be short-circuited by the expedited RCU grace period processing, the expedited RCU grace period processing may report both expedited quiescent states and normal quiescent states on behalf of the same CPUs in the set of CPUs.

Using expedited grace periods to short-circuit normal grace-period computations

A technique for short-circuiting normal read-copy update (RCU) grace period computations in the presence of expedited RCU grace periods. The technique may include determining during normal RCU grace period processing whether at least one expedited RCU grace period elapsed during a normal RCU grace period. If so, the normal RCU grace period is ended. If not, the normal RCU grace period processing is continued. Expedited RCU grace periods may be implemented by expedited RCU grace period processing that periodically awakens a kernel thread that implements the normal RCU grace period processing. The expedited RCU grace period processing may conditionally throttle wakeups to the kernel thread based on CPU utilization.

Short-circuiting normal grace-period computations in the presence of expedited grace periods

An optimized skiplist iterator technique for RCU-protected skiplists. A skiplist iterator operation may attempt to validate a cached pointer hint that references a skiplist element of an RCU-protected skiplist, the skiplist element having an associated first key. If the pointer hint is validated, the pointer hint may be dereferenced to access the skiplist element. A pointer in the skiplist element may be dereferenced to advance to a next skiplist element of the RCU-protected skiplist, the next skiplist element having an associated second key that is larger than the first key. If the pointer hint is not validated, a value-based skiplist iterator operation may be performed that includes traversing the RCU-protected skiplist using the first key to find the next skiplist element having the second key. A new pointer hint that references the next skiplist element may be cached for use in a next invocation of the skiplist iterator operation.

Optimized iterators for RCU-protected skiplists

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.

Fair high-throughput locking for expedited grace periods

Growing community of inventors

Beaverton, OR, United States of America

Paul Edward McKenney