Patent Publication Number: US-8997110-B2

Title: Resolving RCU-scheduler deadlocks

Description:
This application is a continuation under 35 U.S.C. 120 of application Ser. No. 13/475,003, filed May 18, 2012, entitled “Resolving RCU-Scheduler Deadlocks.” 
    
    
     BACKGROUND 
     1. Field 
     The present disclosure relates to computer systems and methods in which data resources are shared among data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the disclosure concerns an implementation of a mutual exclusion mechanism known as “read-copy update” (also known as “RCU”) in an operating system kernel environment wherein RCU uses the operating system scheduler and the scheduler uses RCU. 
     2. Description of the Prior Art 
     By way of background, read-copy update (also known as “RCU”) is a mutual exclusion technique that permits shared data to be accessed for reading without the use of locks, writes to shared memory, memory barriers, atomic instructions, or other computationally expensive synchronization mechanisms, while still permitting the data to be updated (modify, delete, insert, etc.) concurrently. The technique is well suited to both uniprocessor and multiprocessor computing environments wherein the number of read operations (readers) accessing a shared data set is large in comparison to the number of update operations (updaters), and wherein the overhead cost of employing other mutual exclusion techniques (such as locks) for each read operation would be high. By way of example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where read-side lock acquisition would be quite burdensome. 
     The read-copy update technique implements data updates in two phases. In the first (initial update) phase, the actual data update is carried out in a manner that temporarily preserves two views of the data being updated. One view is the old (pre-update) data state that is maintained for the benefit of read operations that may have been referencing the data concurrently with the update. The other view is the new (post-update) data state that is seen by operations that access the data following the update. In the second (deferred update) phase, the old data state is removed following a “grace period” that is long enough to ensure that the first group of read operations will no longer maintain references to the pre-update data. The second-phase update operation typically comprises freeing a stale data element to reclaim its memory. In certain RCU implementations, the second-phase update operation may comprise something else, such as changing an operational state according to the first-phase update. 
       FIGS. 1A-1D  illustrate the use of read-copy update to modify a data element B in a group of data elements A, B and C. The data elements A, B, and C are arranged in a singly-linked list that is traversed in acyclic fashion, with each element containing a pointer to a next element in the list (or a NULL pointer for the last element) in addition to storing some item of data. A global pointer (not shown) is assumed to point to data element A, the first member of the list. Persons skilled in the art will appreciate that the data elements A, B and C can be implemented using any of a variety of conventional programming constructs, including but not limited to, data structures defined by C-language “struct” variables. Moreover, the list itself is a type of data structure. 
     It is assumed that the data element list of  FIGS. 1A-1D  is traversed (without locking) by multiple readers and occasionally updated by updaters that delete, insert or modify data elements in the list. In  FIG. 1A , the data element B is being referenced by a reader r1, as shown by the vertical arrow below the data element. In  FIG. 1B , an updater u1 wishes to update the linked list by modifying data element B. Instead of simply updating this data element without regard to the fact that r1 is referencing it (which might crash r1), u1 preserves B while generating an updated version thereof (shown in  FIG. 1C  as data element B′) and inserting it into the linked list. This is done by u1 acquiring an appropriate lock (to exclude other updaters), allocating new memory for B′, copying the contents of B to B′, modifying B′ as needed, updating the pointer from A to B so that it points to B′, and releasing the lock. In current versions of the Linux® kernel, pointer updates performed by updaters can be implemented using the rcu_assign_pointer( ) primitive. As an alternative to locking during the update operation, other techniques such as non-blocking synchronization or a designated update thread could be used to serialize data updates. All subsequent (post update) readers that traverse the linked list, such as the reader r2, will see the effect of the update operation by encountering B′ as they dereference B&#39;s pointer. On the other hand, the old reader r1 will be unaffected because the original version of B and its pointer to C are retained. Although r1 will now be reading stale data, there are many cases where this can be tolerated, such as when data elements track the state of components external to the computer system (e.g., network connectivity) and must tolerate old data because of communication delays. In current versions of the Linux® kernel, pointer dereferences performed by readers can be implemented using the rcu_dereference( ) primitive. 
     At some subsequent time following the update, r1 will have continued its traversal of the linked list and moved its reference off of B. In addition, there will be a time at which no other reader process is entitled to access B. It is at this point, representing an expiration of the grace period referred to above, that u1 can free B, as shown in  FIG. 1D . 
       FIGS. 2A-2C  illustrate the use of read-copy update to delete a data element B in a singly-linked list of data elements A, B and C. As shown in  FIG. 2A , a reader r1 is assumed be currently referencing B and an updater u1 wishes to delete B. As shown in  FIG. 2B , the updater u1 updates the pointer from A to B so that A now points to C. In this way, r1 is not disturbed but a subsequent reader r2 sees the effect of the deletion. As shown in  FIG. 2C , r1 will subsequently move its reference off of B, allowing B to be freed following the expiration of a grace period. 
     In the context of the read-copy update mechanism, a grace period represents the point at which all running tasks (e.g., processes, threads or other work) having access to a data element guarded by read-copy update have passed through a “quiescent state” in which they can no longer maintain references to the data element, assert locks thereon, or make any assumptions about data element state. By convention, for operating system kernel code paths, a context switch, an idle loop, and user mode execution all represent quiescent states for any given CPU running non-preemptible code (as can other operations that will not be listed here). The reason for this is that a non-preemptible kernel will always complete a particular operation (e.g., servicing a system call while running in process context) prior to a context switch. 
     In  FIG. 3 , four tasks 0, 1, 2, and 3 running on four separate CPUs are shown to pass periodically through quiescent states (represented by the double vertical bars). The grace period (shown by the dotted vertical lines) encompasses the time frame in which all four tasks that began before the start of the grace period have passed through one quiescent state. If the four tasks 0, 1, 2, and 3 were reader tasks traversing the linked lists of  FIGS. 1A-1D  or  FIGS. 2A-2C , none of these tasks having reference to the old data element B prior to the grace period could maintain a reference thereto following the grace period. All post grace period searches conducted by these tasks would bypass B by following the updated pointers created by the updater. 
     Grace periods may synchronous or asynchronous. According to the synchronous technique, an updater performs the first phase update operation, blocks (waits) until a grace period has completed, and then implements the second phase update operation, such as by removing stale data. According to the asynchronous technique, an updater performs the first phase update operation, specifies the second phase update operation as a callback, then resumes other processing with the knowledge that the callback will eventually be processed at the end of a grace period. Advantageously, callbacks requested by one or more updaters can be batched (e.g., on callback lists) and processed as a group at the end of an asynchronous grace period. This allows asynchronous grace period overhead to be amortized over plural deferred update operations. 
     In some RCU implementations designed for preemptible operating system kernels, asynchronous grace period processing is the norm but a synchronous expedited grace period, sometimes referred to as a “Big Hammer” grace period, is also available for updaters that need it. This expedited grace period forces a context switch (and thus a quiescent state) on each processor so that an updater can quickly perform its second-phase update operation. Existing callbacks associated with asynchronous grace periods are not affected. They must await the end of an asynchronous grace period before becoming ripe for processing. In other RCU implementations designed for preemptible operating system kernels, the RCU grace period mechanism includes the capability of priority boosting reader tasks that were preempted within their RCU read-side critical sections so that such tasks do not unduly delay the end of a grace period. 
     In the foregoing preemptible kernel-based RCU implementations, the RCU subsystem can invoke the operating system scheduler from the rcu_read_unlock( ) primitive, which is invoked by reader tasks when they exit their RCU read-side critical sections. The rcu_read_unlock( ) primitive is a companion to the rcu_read_lock( ) primitive, which is invoked by reader tasks when they enter their RCU read-side critical sections. Two scenarios in which the rcu_read_unlock( ) primitive will result in invocation of the operating system scheduler are (1) when RCU priority boosting is enabled and the reader task that invoked rcu_read_unlock( ) needs to be deboosted, and (2) when the reader task that invoked rcu_read_unlock( ) is the last reader holding up an RCU expedited grace period and the updater task that requested the expedited grace period needs to be awakened. These operations require the scheduler to acquire runqueue locks and priority inheritance locks. 
     However, some operating system schedulers, such as the scheduler in current versions of the Linux® kernel, can themselves implement RCU read-side critical sections. Applicant submits that there are scenarios in which such usage could cause deadlock problems if the scheduler invoked by a (non-scheduler) reader task itself invokes rcu_read_unlock( ) and attempts to obtain runqueue or priority-inheritance locks that it already holds. The present disclosure presents a solution that addresses this issue. 
     SUMMARY 
     A method, system and computer program product are provided for resolving deadlocks between an RCU subsystem and an operating system scheduler. According to an example embodiment, an RCU registration component of the RCU subsystem allows an RCU reader to manipulate an rcu_read_lock_nesting counter when the RCU reader enters an RCU read-side critical section. An RCU unregistration component of the RCU subsystem allows an RCU reader to manipulate the rcu_read_lock_nesting counter when the RCU reader leaves an RCU read-side critical section. The unregistration component provides first and second rcu_read_lock_nesting manipulation paths that are dependent on a current value of the rcu_read_lock_nesting counter. The first rcu_read_lock_nesting manipulation path is taken when the current value of the rcu_read_lock_nesting counter is indicative of a task-context RCU reader exiting an outermost RCU read-side critical section. It includes condition-based read-side helper processing that may result in invocation of the operating system scheduler. This path further includes a deadlock protection operation that temporarily manipulates the rcu_read_lock_nesting counter to prevent any intervening RCU reader from taking the first rcu_read_lock_nesting manipulation path while a task-context RCU reader is within that path. The second rcu_read_lock_nesting manipulation path is taken when the current value of the rcu_read_lock_nesting counter is indicative of a task-context RCU reader exiting a non-outermost RCU read-side critical section, or an RCU reader being nested within the first rcu_read_lock_nesting manipulation path (such as due to an interrupt handler interrupting the path to run the scheduler or an explicit call to the scheduler from within the path). This path bypasses the condition-based read-side helper processing. 
     According to an example embodiment, the RCU registration component allows an RCU reader to manipulate the rcu_read_lock_nesting counter by incrementing it. The RCU unregistration component allows an RCU reader to manipulate the rcu_read_lock_nesting counter by either decrementing it or setting it to a value, depending on which manipulation path is taken by the RCU reader. The first manipulation path may include setting the rcu_read_lock_nesting counter to a deadlock protection value, and the second manipulation path may include decrementing the rcu_read_lock_nesting counter. 
     More particularly, the first manipulation path may taken when the rcu_read_lock_nesting counter has a first count value that is indicative of the task-context RCU reader exiting all RCU read-side critical section processing, and may comprise setting the rcu_read_lock_nesting counter to an arbitrary second count value representing the deadlock protection value, performing the read-side helper processing, and setting the rcu_read_lock_nesting counter to a third count value that is indicative of the task-context RCU reader being outside of an RCU read-side critical section. The arbitrary second count value may be a large negative number. 
     The second manipulation path may be taken when the rcu_read_lock_nesting counter has any value other than the first count value, and may comprise decrementing the rcu_read_lock_nesting counter and bypassing the read-side helper processing. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The foregoing and other features and advantages will be apparent from the following more particular description of example embodiments, as illustrated in the accompanying Drawings, in which: 
         FIGS. 1A-1D  are diagrammatic representations of a linked list of data elements undergoing a data element replacement according to a conventional read-copy update mechanism; 
         FIGS. 2A-2C  are diagrammatic representations of a linked list of data elements undergoing a data element deletion according to a conventional read-copy update mechanism; 
         FIG. 3  is a flow diagram illustrating a grace period in which four processes pass through a quiescent state; 
         FIG. 4  is a functional block diagram showing a multiprocessor computer system that may be implemented in accordance with the present disclosure; 
         FIG. 5  is a functional block diagram showing an RCU subsystem that may be provided in the computer system of  FIG. 4 ; 
         FIG. 6  is a diagrammatic illustration of showing a set of reader task structures comprising fields used by the RCU subsystem; 
         FIG. 7  is a block diagram showing an operating system kernel in which the RCU subsystem may be invoked by task-context RCU readers and task scheduler-context RCU readers, and may itself invoke the scheduler; 
         FIG. 8  is a C language code listing showing conventional operations of a reader unregistration component of the RCU subsystem; 
         FIG. 9  is a C language code listing showing operations of an improved reader unregistration component of the RCU subsystem implemented in accordance with the present disclosure; 
         FIG. 10  is a flow diagram corresponding to  FIG. 9 ; and 
         FIG. 11  is a diagrammatic illustration showing example storage media that may be used to provide a computer program product in accordance with the present disclosure. 
     
    
    
     DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS 
     Turning now to the drawing  FIG. 4  et seq., wherein like reference numerals represent like elements in all of the several views,  FIG. 4  illustrates an example multiprocessor computer system  2  in which the subject matter disclosed herein may be implemented. By way of example only, the computer system  2  is shown as including multiple processors  4   1 ,  4   2  . . .  4   n , a system bus  6 , and a program memory  8 . There are also cache memories  10   1 ,  10   2  . . .  10   n  and cache controllers  12   1 ,  12   2  . . .  12   n  respectively associated with the processors  4   1 ,  4   2  . . .  4   n . A conventional memory controller  14  is associated with the memory  8 . 
     The computer system  2  may represent any of several different types of computing apparatus. Such computing apparatus may include, but are not limited to, general purpose computers, special purpose computers, portable computing devices, communication and/or media player devices, set-top devices, embedded systems, and other types of information handling machines. The term “processor” as used with reference to the processors  4   1 ,  4   2  . . .  4   n  encompasses any program execution unit capable of executing program instructions, including but not limited to a packaged integrated circuit device (such as a microprocessor), a processing core within a packaged integrated circuit device (such as a microprocessor core), or a hardware thread comprising one or more functional units within a processing core (such as an SMT thread). Each such execution unit may be referred to as a CPU (central processing unit). The processors  4   1 ,  4   2  . . .  4   n  may be situated within a single computing device or node (e.g., as part of a single-node SMP system) or they may be distributed over plural nodes (e.g., as part of a NUMA system, a cluster, or a cloud). The memory  8  may comprise any type of tangible storage medium capable of storing data in computer readable form for use in program execution, including but not limited to, any of various types of random access memory (RAM), various flavors of programmable read-only memory (PROM) (such as flash memory), and other types of primary storage (i.e., program memory). The cache memories  10   1 ,  10   2  . . .  10   n  may be implemented in several levels (e.g., as level 1, level 2 and level 3 caches) and the cache controllers  12   1 ,  12   2  . . .  12   n  may collectively represent the cache controller logic that supports each cache level. As illustrated, the memory controller  14  may reside separately from processors  4   1 ,  4   2  . . .  4   n , for example, as part of a discrete chipset. Alternatively, the memory controller  114  could be provided by plural memory controller instances that are respectively integrated with the processors  4   1 ,  4   2  . . .  4   n . 
     Each CPU embodied by a given processor  4  is operable to execute program instruction logic under the control of a software program stored in the memory  8  (or elsewhere). As part of this program execution logic, update operations (updaters)  18  may execute within a process, thread, or other execution context (hereinafter “task”) on any of the processors  4 . Each updater  18  runs periodically to perform updates on a set of shared data  16  that may be stored in the shared memory  8  (or elsewhere). In  FIG. 4 , reference numerals  18   1 ,  18   2  . . .  18   n  illustrate individual data updaters that respectively execute on the several processors  4   1 ,  4   2  . . .  4   n . As described in the “Background” section above, the updates performed by an RCU updater can include modifying elements of a linked list, inserting new elements into the list, deleting elements from the list, and other types of operations. To facilitate such updates, the processors  4  are programmed from instructions stored in the memory  8  (or elsewhere) to implement a read-copy update (RCU) subsystem  20  as part of their processor functions. In  FIG. 4 , reference numbers  20   1 ,  20   2  . . .  20   n  represent individual RCU instances that may periodically execute on the several processors  4   1 ,  4   2  . . .  4   n . Any given processor  4  may also execute a read operation (reader)  21 . Each reader  21  runs from program instructions stored in the memory  8  (or elsewhere) in order to periodically perform read operations on the set of shared data  16  stored in the shared memory  8  (or elsewhere). In  FIG. 4 , reference numerals  21   1 ,  21   2  . . .  21   n  illustrate individual reader instances that may respectively execute on the several processors  4   1 ,  4   2  . . .  4   n . Such read operations will typically be performed far more often than updates, this being one of the premises underlying the use of read-copy update. Moreover, it is possible for several of the readers  21  to maintain simultaneous references to one of the shared data elements  16  while an updater  18  updates the same data element. 
     During operation of the computer system  2 , an updater  18  will occasionally perform an update to one of the shared data elements  16 . In accordance the philosophy of RCU, a first-phase update is performed in a manner that temporarily preserves a pre-update view of the shared data element for the benefit of readers  21  that may be concurrently referencing the shared data element during the update operation. Following the first-phase update, the updater  18  may register a callback with the RCU subsystem  20  for the deferred destruction of the pre-update view following a grace period (second-phase update). As described in the “Background” section above, this is known as asynchronous grace period processing. Alternatively, the updater  18  may request a synchronous expedited grace period. 
     The grace period processing performed by the RCU subsystem  20  entails starting new grace periods and detecting the end of old grace periods so that the RCU subsystem  20  knows when it is safe to free stale data (or take other actions). Grace period processing may further entail the management of callback lists that accumulate callbacks until they are ripe for batch processing at the end of a given grace period. In addition, reader priority boosting may be performed on behalf of readers  21  that are blocking the end of a grace period. The foregoing grace period processing operations may be performed by periodically running RCU subsystem instances  20   1 ,  20   2  . . .  20   n  on the several processors  4   1 ,  4   2  . . .  4   n . 
     Turning now to  FIG. 5 , example components of the RCU subsystem  20  are shown. These components include an RCU reader API (Application Programming Interface)  22 , an RCU updater API  24 , an RCU grace period API  26 , and a set of grace period detection and callback processing functions  28 . As shown in  FIG. 6 , the RCU subsystem  20  also uses several fields in the task structure  30  of each reader  21 . As discussed in more detail below, these fields include an rcu_read_lock_nesting counter  30 A and an rcu_read_unlock_special flag ( 30 B). 
     The RCU reader API  22  comprises a reader registration component  22 A and a reader unregistration component  22 B. These components are respectively invoked by readers  21  as they enter and leave their RCU read-side critical sections, thereby allowing the RCU subsystem  20  to track reader operations and determine when readers are engaged in RCU-protected read-side critical section processing. In an example embodiment, the reader registration component  22 A and the reader unregistration component  22 B may be respectively implemented using the rcu_read_lock( ) and rcu_read_unlock( ) primitives found in existing read-copy update implementations, but with the rcu_read_unlock( ) primitive being modified to address the deadlock problem discussed in the “Background” section above. 
     When a reader  21  enters an RCU read-side critical section and invokes the reader registration component  22 A, the latter increments the rcu_read_lock_nesting counter  30 A (see  FIG. 6 ) in the reader&#39;s task structure. When the reader  21  leaves an RCU read-side critical section and invokes the reader unregistration component  22 B, the latter decrements the rcu_read_lock_nesting counter  30 A. The term “nesting” as used in the name of this counter refers to the fact that a given reader&#39;s RCU read-side critical sections can be nested or overlapping. In conventional implementations of the rcu_read_unlock( ) primitive, a counter value of zero is commonly used to indicate that a reader  21  is not performing any RCU read-side critical section processing. This counter value also triggers the conventional rcu_read_unlock( ) primitive to check whether special read-side helper processing (see below) is needed. As described in more detail below, a modified version of the rcu_read_unlock( ) primitive may be used to bypass this test for scheduler-based invocations of the RCU subsystem  20 . 
     The RCU updater API  24  may comprise a register callback component  24 A and an expedited grace period component  24 B. The register callback component is used by the updaters  18  to register a callback following a first-phase update to a shared data element  16 . In an example embodiment, this component may be implemented using the “call rcu( )” primitive found in existing read-copy update implementations. A call to the register callback component  24 A initiates processing that places the callback on an RCU callback list (not shown) associated with the processor  4  that runs the updater  18 . This starts an asynchronous grace period so that the callback can be processed after the grace period has ended as part of second-phase update processing to remove stale data (or take other actions). The expedited grace period component  24 B is used by the updaters  18  to request a synchronous expedited grace period following a first-phase update to a shared data element  16 . The updater  18  blocks while the expedited grace period is in progress, then performs second-phase update processing to free stale data (or take other actions). In an example embodiment, this component may be implemented using the “synchronize_rcu_expedited( )” primitive found in existing read-copy update implementations. 
     The RCU grace period API  26  may comprise a check callbacks component  26 A. This component may be run periodically (e.g., in response to a scheduler clock interrupt) in order to check for new callbacks, start a new grace period if one is needed, and request callback processing. In an example embodiment, this component may be implemented using the “rcu_preempt_check_callbacks( )” primitive found in existing read-copy update implementations. As discussed below, the check callbacks component  26 A also manipulates the rcu_read_unlock_special flag  30 B (see  FIG. 6 ) if necessary to advance a grace period. 
     The grace period detection and callback processing functions  28  may comprise various components conventionally found in existing read-copy update implementations, including but not limited to a quiescent state/grace period tracking component, a callback processor, a blocked reader handler, and a reader priority boosting component. Of particular relevance to the present disclosure is a read-side helper component  28 A that is implemented when a reader  21  is delaying the end of a grace period. In an example embodiment, this component may be implemented using the “rcu_read_unlock_special( )” primitive found in existing read-copy update implementations. Its operations may include advising the RCU subsystem  20  that a delayed reader  21  is exiting an RCU read-side critical section (and that a quiescent state has been reached if this is the last reader), removing the reader from one or more blocked task lists used to identify readers that are blocking the end of a grace period, and invoking the scheduler to unboost the reader&#39;s priority if it was previously boosted. 
     As described in the “Background” section above, the present disclosure describes a technique that addresses the problem of deadlock that may occur in modern operating systems whose schedulers make increasing use of RCU and wherein RCU makes increasing calls to the scheduler. Current versions of the Linux® kernel configured for kernel-level preemption are one example. As shown in  FIG. 7 , a preemptible operating system kernel  40  that implements the RCU subsystem  20  may operate in task context  40 A (e.g., due to a system call) and scheduler context  40 B (also referred to herein as “the scheduler”). The RCU subsystem  20  can be invoked from both task context  40 A and scheduler context  40 B in the event that either context needs to perform RCU read-side critical section processing as an RCU reader  21 . These respective invocations of the RCU subsystem  20  are shown by the arrows  42  and  44 , each of which represents a pair of calls to the reader registration component  22 A (e.g., rcu_read_lock( ) ) and the reader unregistration component  22 B (e.g., rcu_read_unlock( ) ) of  FIG. 5 . In addition, an RCU reader  21  operating in task context  40 A can invoke the scheduler  40 B from the reader unregistration component  22 B (e.g., rcu_read_unlock( ) ) via the read-side helper component  28 A of  FIG. 5  (e.g., rcu_read_unlock_special( ) ). This is shown by the arrow  46 . For example, the read-side helper component  28 A may need to deboost the current task (when RCU priority boosting is enabled) or to wake up the task if it requested an expedited RCU grace period and it is the last such task that was blocking the end of that grace period. 
     In current implementations of the Linux® kernel, the rcu_read_unlock( ) function that provides the reader unregistration component  22 B invokes a work function known as rcu_read_unlock( ). The rcu_read_unlock( ) function, in turn, conditionally invokes the rcu_read_unlock_special( ) function that provides the read-side helper component  28 A. The conditions that lead to the invocation of rcu_read_unlock_special( ) are determined from the two fields  30 A and  30 B in the reader&#39;s task structure  30  (see  FIG. 6 ). As previously stated, the first field  30 A is an rcu_read_lock_nesting counter that maintains a count of the number of times the reader  21  has recursively entered an RCU read-side critical section. In a conventional RCU implementation a counter value of zero signifies that the reader  21  is not within such a critical section. The second field  30 B is the rcu_read_unlock_special flag that is set by the check callbacks component ( 26 A) of  FIG. 5 . In current implementations of the Linux® kernel, the rcu_read_unlock_special( ) function that provides the read-side helper component  28 A is invoked when (1) the rcu_read_lock_nesting counter  30 A is zero (indicating that the reader  21  has completed all RCU read-side critical section processing) and (2) the rcu_read_unlock_special flag  30 B is set (indicating that additional actions are required on behalf of this reader). 
     Example C language source code for a conventional rcu_read_unlock( ) work function that performs the foregoing condition processing is shown in  FIG. 8 . Line  6  decrements and tests the rcu_read_lock_nesting counter  30 A for zero. If true, and following a memory ordering barrier( ) compiler directive in line  7 , a check is made in line  8  to determine the state of the rcu_read_unlock_special flag  30 B. If the rcu_read_unlock_special flag  30 B is set, the rcu_read_unlock_special( ) function is invoked in line  9 . 
     The operations performed by the rcu_read_unlock_special( ) function that provides the read-side helper component  28 A will not be described in detail, but, as mentioned above, may include deboosting the current task (when RCU priority boosting is enabled) or waking up the task that requested an expedited RCU grace period (when the current task is the last one executing). Referring back to  FIG. 7 , these operations can result in the RCU subsystem  20  invoking the task scheduler  40 B (see arrow  46 ) to acquire its runqueue locks and its priority inheritance locks. If the scheduler  40 B independently invokes rcu_read_unlock( ) while holding the runqueue and priority-inheritance locks, and if that invocation of rcu_read_unlock( ) reinvokes the scheduler in the same manner as the initial rcu_read_unlock( ) operation, there is the possibility of deadlock under certain scenarios. 
     Such scenarios can be avoided if the scheduler  40 B disables interrupts when acquiring its runqueue and priority-inheritance locks. As long as the scheduler&#39;s RCU read-side critical sections are completely contained in a given runqueue or priority-inheritance lock&#39;s critical section, then that RCU read-side critical section cannot be interrupted, blocked, or preempted. There can therefore be no reason for rcu_read_unlock( ) to reinvoke the scheduler. In particular, there can be no priority boosting during the scheduler&#39;s RCU read-side critical because there can be no preemption with interrupts disabled. Moreover, the scheduler&#39;s RCU read-side critical section cannot be the last RCU read-side critical section to end for an expedited grace period because interrupts are disabled and there can be no preemption by reschedule IPIs (interprocessor interrupts). 
     However, consider an implementation of rcu_read_unlock( ) in a hierarchical RCU implementation designed for systems with many processors. In current versions of the Linux® kernel, the hierarchical RCU kernel configuration option is known as CONFIG_TREE_PREEMPT_RCU. In this implementation it is possible for the following sequence of events to occur:
         1. Task 0 invokes rcu_read_lock( ), entering an RCU read-side critical section.   2. Task 0 is preempted, during which time it is subjected to priority boosting, which causes it to run again.   3. Task 0 completes its RCU read-side critical section, and therefore invokes the work function_rcu_read_unlock( ) through line  7  of  FIG. 8 , decrementing the-&gt;rcu_read_lock_nesting nesting count and finding the result to be zero.   4. The CPU on which Task 0 is running is interrupted, and the interrupt handler invokes the scheduler  40 B to wake up another task to run, causing the scheduler to acquire a runqueue lock and to enter an RCU read-side critical section.   5. When the interrupt handler exits its RCU read-side critical section, the interrupt handler will invoke_rcu_read_unlock( ). During this second invocation of _rcu_read_unlock( ), the interrupt handler might find the value of Task 0&#39;s per-task-&gt;rcu_read_unlock_special field (see line  8  of  FIG. 8 ) to be non-zero (e.g., due to Task 0 having been previously preempted within its RCU read-side critical section). The interrupt handler would therefore invoke the rcu_read_unlock_special( ) function to perform special processing. As previously discussed, this function may invoke the scheduler  40 B to attempt to unboost Task 0, which would require the scheduler to attempt to acquire the runqueue lock that it already holds, resulting in deadlock.       

     The problem in this situation is that the interrupt handler&#39;s RCU reader code path is nested within the task-level RCU reader&#39;s code path, and the interrupt handler&#39;s instance of the_rcu_read_unlock( ) primitive is seeing the state that is intended for the task-level _rcu_read_unlock( ). A proposed solution to this problem is to use separate first and second rcu_read_lock_nesting manipulation paths in the reader unregistration component  22 B that are dependent on different values of the rcu_read_lock_nesting counter  30 A (see  FIG. 6 ). The first rcu_read_lock_nesting manipulation path includes condition-based read-side helper processing that may result in invocation of the operating system scheduler  40 B. This path is taken when the current value of the rcu_read_lock_nesting counter is indicative of a task-context RCU reader  21  exiting an outermost RCU read-side critical section. It includes a deadlock-protection operation that temporarily manipulates the rcu_read_lock_nesting counter to prevent any intervening RCU reader  21  from taking the first rcu_read_lock_nesting manipulation path while the task-context RCU reader  21  is within that path. The second rcu_read_lock_nesting manipulation path bypasses the condition-based read-side helper processing. This path is taken when the rcu_read_lock_nesting counter is indicative of a task-context RCU reader exiting a non-outermost RCU read-side critical section, or when the current value of the rcu_read_lock_nesting counter is indicative of an RCU reader being nested within the first rcu_read_lock_nesting manipulation path, such as due to an interrupt handler interrupting the path to run the scheduler or an explicit call to the scheduler from within the path. 
     In an example embodiment, the RCU unregistration component allows an RCU reader to manipulate the rcu_read_lock_nesting counter by either decrementing it or setting it to a value, depending on which manipulation path of the reader unregistration component is taken. In particular, the first manipulation path includes setting the rcu_read_lock_nesting counter to a deadlock-protection value, and the second manipulation path includes decrementing the rcu_read_lock_nesting counter. Still more particularly, the first manipulation path may be taken when the rcu_read_lock_nesting counter has a first count value that is indicative of the task-context RCU reader exiting all RCU read-side critical section processing, and may comprise setting the rcu_read_lock_nesting counter to an arbitrary second count value representing the deadlock-protection value, performing read-side helper processing, and resetting the rcu_read_lock_nesting counter to a third count value that is indicative of the task-context RCU reader being outside of an RCU read-side critical section. The arbitrary second count value may be a large negative number. The second manipulation path of the unregistration component may be taken when the rcu_read_lock_nesting counter has any value other than the first count value, and may comprise decrementing the rcu_read_lock_nesting counter and bypassing the read-side helper processing. 
     Example C language code implementing this solution is shown in  FIG. 9 . This has roughly the same overhead as the conventional code of  FIG. 8 : the decrement and assignment operation of line  6  of  FIG. 8  has been replaced by the decrement operation of line  6  of  FIG. 9  (for the first rcu_read_lock_nesting manipulation pathway) or the two assignment operations at lines  9  and  15  of  FIG. 9  (for the second rcu_read_lock_nesting manipulation pathway). When a task-context reader  21  exits its outermost RCU read-side critical section and reaches line  5  of  FIG. 9 , it will find that the rcu_read_lock_nesting counter  30 A is equal to one. Execution will jump to line  7 , a memory-ordering barrier( ) compiler directive provided in line  8 , and the rcu_read_lock_nesting counter  30 A will be set to INT_MIN, which can be a large negative number, in line  9 . This represents the above-mentioned deadlock-protection value. Following another memory ordering barrier( ) compiler directive in line  11 , lines  12 - 13  will be implemented and rcu_read_unlock_special( ) will be invoked if necessary (i.e., according to the state of the rcu_read_unlock_special flag  30 B in the reader&#39;s task structure (see  FIG. 6 ). Once the invocation of rcu_read_unlock_special( ) by the task-context RCU reader  21  is no longer a possibility, another memory-ordering barrier( ) compiler directive is provided on line  14  and the rcu_read_lock_nesting counter  30 A is set to zero on line  15 . The foregoing processing represents the first rcu_read_lock_nesting manipulation path mentioned above. This path is taken by task-context readers  21  that are exiting their outermost RCU read-side critical sections. 
     Advantageously, if a nested scheduler-level RCU reader  21  is invoked while the task-context RCU reader  21  is within the first rcu_read_lock_nesting manipulation path, the scheduler-level RCU reader, upon reaching line  5  of  FIG. 9 , will find that the rcu_read_lock_nesting counter  30 A is not equal to 1. The rcu_read_lock_nesting counter  30 A will equal INT_MIN+1 due to the scheduler-level RCU reader  21  having previously invoked the reader registration component  22 A (which increments the rcu_read_lock_nesting counter). Line  6  will then decrement the rcu_read_lock_nesting counter  30 A (setting it to INT_MIN) but the code path of lines  7 - 15  that leads to rcu_read_unlock_special( ) and the deadlock problem described above, will be bypassed. The foregoing processing represents the second rcu_read_lock_nesting manipulation path mentioned above. This path is taken by any RCU reader that is nested within the first rcu_read_lock_nesting manipulation path. As previously mentioned, this could be an interrupt handler that interrupts the first path or an explicit call to the scheduler  40 B from within that path. This first rcu_read_lock_nesting manipulation path is also taken by task-context readers  21  that are not exiting an outermost RCU read-side critical section. 
     The flow diagram of  FIG. 10  illustrates the foregoing processing. In block  50 , the test represented by line  5  of  FIG. 9  is implemented. Block  52  represents the decrement of line  6  of  FIG. 9  and block  54  represents the assignment of line  9  of  FIG. 9 . In block  56 , the condition test represented by line  12  of  FIG. 9  is implemented. Block  58  represents the conditional invocation of rcu_read_unlock_special( ) set forth on line  13  of  FIG. 9 . Block  60  represents the operation of line  15  of  FIG. 9  in which the rcu_read_lock_nesting counter is set to zero. 
     Accordingly, a technique for has been disclosed for implementing read-copy update in a manner that resolves RCU-scheduler deadlocks in an operating system kernel. It will be appreciated that the foregoing concepts may be variously embodied in any of a data processing system, a machine implemented method, and a computer program product in which programming logic is provided by one or more machine-useable storage media for use in controlling a data processing system to perform the required functions. Example embodiments of a data processing system and machine implemented method were previously described in connection with  FIG. 4-10 . With respect to a computer program product, digitally encoded program instructions may be stored on one or more computer-readable data storage media for use in controlling a computer or other digital machine or device to perform the required functions. The program instructions may be embodied as machine language code that is ready for loading and execution by the machine apparatus, or the program instructions may comprise a higher level language that can be assembled, compiled or interpreted into machine language. Example languages include, but are not limited to C, C++, assembly, to name but a few. When implemented on a machine comprising a processor, the program instructions combine with the processor to provide a particular machine that operates analogously to specific logic circuits, which themselves could be used to implement the disclosed subject matter. 
     Example data storage media for storing such program instructions are shown by reference numerals  8  (memory) and  10  (cache) of the multiprocessor system  2  of  FIG. 4 . The system  2  may further include one or more secondary (or tertiary) storage devices (not shown) that could store the program instructions between system reboots. A further example of storage media that may be used to store the program instructions is shown by reference numeral  100  in  FIG. 11 . The storage media  100  are illustrated as being portable optical storage disks of the type that are conventionally used for commercial software sales, such as compact disk-read only memory (CD-ROM) disks, compact disk-read/write (CD-R/W) disks, and digital versatile disks (DVDs). Such storage media can store the program instructions either alone or in conjunction with an operating system or other software product that incorporates the required functionality. The storage media could also be provided by other portable storage media (such as floppy disks, flash memory sticks, etc.), or storage media combined with drive systems (e.g. disk drives). As is the case with the memory  8  and the cache  10  of  FIG. 4 , the storage media may be incorporated in data processing platforms that have integrated random access memory (RAM), read-only memory (ROM) or other semiconductor or solid state memory. More broadly, the storage media could comprise any electronic, magnetic, optical, infrared, semiconductor system or apparatus or device, or any other tangible entity representing a machine, manufacture or composition of matter that can contain, store, communicate, or transport the program instructions for use by or in connection with an instruction execution system, apparatus or device, such as a computer. For all of the above forms of storage media, when the program instructions are loaded into and executed by an instruction execution system, apparatus or device, the resultant programmed system, apparatus or device becomes a particular machine for practicing embodiments of the method(s) and system(s) described herein. 
     Although various example embodiments have been shown and described, it should be apparent that many variations and alternative embodiments could be implemented in accordance with the disclosure. It is understood, therefore, that the invention is not to be in any way limited except in accordance with the spirit of the appended claims and their equivalents.