Read-copy-update (RCU) operations with reduced memory barrier usage

• US 7,353,346 B2
• Filed: 03/24/2006
• Issued: 04/01/2008
• Est. Priority Date: 03/24/2006
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E., Bhattacharya, Suparna
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): Flournoy; Horace L.
• Application Number:
  US11/388,364
• Publication Number:
  US 20070226431A1
• Time in Patent Office: 739 Days
• Field of Search: None
• US Class Current: 711/154
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/522 Barrier synchronisation
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Read-copy-update (RCU) is performed within real-time and other types of systems, such that memory barrier usage within RCU is reduced. A computerized system includes processors, memory, updaters, and readers. The updaters update contents of a section of the memory by using first and second sets of per-processor counters, first and second sets of per-processor need-memory-barrier bits, and a global flip-counter bit. The global flip-counter bit specifies which of the first or second set of the per-processor counters and the per-processor need-memory-barrier bits is a current set, and which is a last set. The readers read the contents of the section of the memory by using the first and second sets of per-processor counters, the first and second sets of per-processor need-memory-barrier bits, and the global flip-counter bit, in a way that significantly reduces the need for memory barriers during such read operations.

Claims

1. A method comprising:

to update contents of a section of memory,

copying a global flip-counter bit to a local flip-counter bit, the global flip-counter bit specifying which of a first set of per-processor counters and a second set of per-processor counters is a current set of per-processor counters and which is a last set of per-processor counters, the global flip-counter bit also specifying which of a first set of per-processor need-memory-barrier bits and a second set of per-processor need-memory-barrier bits is a current set of per-processor need-memory-barrier bits and which is a last set of per-processor need-memory-barrier bits;

where attempting to acquire a flip-counter-bit lock on the global-flip-counter bit is successful,

where the global flip-counter bit has not changed while acquiring the flip-counter-bit lock,

where all of the last set of per-processor counters are zero, such that none of a plurality of threads being executed by a plurality of processors corresponding to the last set of per-processor counters are currently executing a critical read operation on the section of memory,

where all of the last set of per-processor need-memory-barrier bits are zero, such that none of the processors needs to execute a memory barrier,

setting each of the current set of per-processor need-memory-barrier bits to one, using the local flip-counter bit;

inverting the global flip-counter bit; and

,

releasing the flip-counter-bit lock.

2. The method of claim 1, further comprising, executing a memory barrier before inverting the global flip-counter bit.

3. The method of claim 1, further comprising, to perform a critical read operation on the section of memory to read the contents of the section of memory, to acquire an effective read lock in performing the critical read operation,

incrementing a per-task read-lock-nesting counter corresponding to a task performing the critical read operation;

where the per-task read-lock-nesting counter is equal to one,

copying the global flip-counter bit to the local flip-counter bit;

incrementing the per-processor counter of the current set of per-processor counters that corresponds to a processor currently executing the task, using the local flip-counter bit; and

,

pointing a per-task flip-counter pointer corresponding to the task to the per-processor counter that was incremented.

4. The method of claim 3, wherein incrementing the per-processor counter of the current set of per-processor counters that corresponds to the processor currently executing the task comprises atomically incrementing the per-processor counter of the current set of per-processor counters that corresponds to the processor currently executing the task.

5. The method of claim 3, wherein incrementing per-processor counter of the current set of per-processor counters that corresponds to the processor currently executing the task comprises:

where the per-processor counter corresponding to the processor currently executing the task is equal to zero, non-atomically incrementing the per-processor counter corresponding to the processor currently executing the task; and

,

where the per-processor counter corresponding to the processor currently executing the task is greater than zero, atomically incrementing the per-processor counter corresponding to the processor currently executing the task.

6. The method of claim 3, further comprising, reading the contents of the section of memory.

7. The method of claim 3, further comprising, to release the effective read lock in performing the critical read operation,

decrementing the per-task read-lock-nesting counter corresponding to the task performing the critical read operation;

where the per-task read-lock-nesting counter is equal to zero,

decrementing the per-processor counter pointed to by the per-task flip-counter pointer;

where the per-processor counter within the last set of per-processor counters for the processor currently executing the task is equal to zero, and a corresponding per-processor need-memory-barrier bit is not equal to zero,

executing a memory barrier; and

,

clearing the corresponding per-processor need-memory-barrier bit.

8. The method of claim 7, wherein decrementing the per-processor counter pointed to by the per-task flip-counter pointer comprises atomically decrementing the per-processor counter pointed to by the per-task flip-counter pointer.

9. The method of claim 7, wherein decrementing the per-processor counter pointed to by the per-task flip-counter pointer comprises:

where the per-processor counter pointed to by the per-task flip-counter pointer is equal to one, non-atomically decrementing the per-processor counter pointed to by the per-task flip-counter pointer; and

,

where the per-processor counter pointed to by the per-task flip-counter pointer is greater than one, atomically decrementing the per-processor counter pointed to by the per-task flip-counter pointer.

10. The method of claim 1, further comprising:

where a per-processor counter of the last set of per-processor counters corresponding to a given processor is equal to zero, and a per-processor need-memory-barrier bit of the last set of per-processor need-memory-barrier bits corresponding to the given processor is equal to one,

executing a memory barrier; and

,

clearing the per-processor need-memory-barrier bit of the last set of per-processor need-memory-barrier bits corresponding to the given processor.

11. A method comprising:

to update contents of a section of memory,

copying a global flip-counter bit to a local flip-counter bit, the global flip-counter bit specifying which of a first set of per-processor counters and a second set of per-processor counters is a current set of per-processor counters and which is a last set of per-processor counters, the global flip-counter-bit also specifying which of a first set of per-processor need-memory-barrier bits and a second set of per-processor need-memory-barrier bits is a current set of per-processor need-memory-barrier bits and which is a last set of per-processor need-memory-barrier bits;

where attempting to acquire a flip-counter-bit lock on the global-flip-counter bit is successful,

where the global flip-counter bit has not changed while acquiring the flip-counter-bit lock,

where any of the last set of per-processor need-memory-barrier bits is equal to zero,

where a sum of all of the last set of per-processor counters is equal to zero,

incrementing each of the last set of per-processor need-memory-barrier bits, using the local flip-counter bit;

where all of the last set of per-processor need-memory-barrier bits are equal to two,

setting each of the current set of per-processor need-memory-barrier bits to zero, using the local flip-counter bit,

inverting the global flip-counter bit; and

,

releasing the flip-counter-bit lock.

12. The method of claim 11, further comprising, executing a memory barrier before incrementing each of the last set of per-processor need-memory-barrier bits.

13. The method of claim 11, further comprising, executing a memory barrier before inverting the global flip-counter bit.

14. The method of claim 11, further comprising, to perform a critical read operation on the section of memory to read the contents of the section of memory, to acquire an effective read lock in performing the critical read operation,

incrementing a per-task read-lock-nesting counter corresponding to a task performing the critical read operation;

where the per-task read-lock-nesting counter is equal to one,

copying the global flip-counter bit to the local flip-counter bit;

incrementing the per-processor counter of the current set of per-processor counters that corresponds to a processor currently executing the task, using the local flip-counter bit; and

,

setting a per-task flip-counter bit corresponding to the task equal to the local flip-counter bit.

15. The method of claim 14, further comprising:

prior to incrementing the per-task read-lock-nesting counter corresponding to the task performing the critical read operation, disabling preemption and/or interrupts; and

,

after setting the per-task flip-counter bit corresponding to the task equal to the local flip-counter bit, enabling preemption and/or interrupts.

16. The method of claim 14, further comprising, to release the effective read lock in performing the critical read operation,

decrementing the per-task read-lock-nesting counter corresponding to the task performing the critical read operation;

where the per-task read-lock-nesting counter is equal to zero,

decrementing the per-processor counter within a set of per-processor counters specified by the per-task flip-counter bit and corresponding to the processor currently executing the task;

copying the global flip-counter bit to the local flip-counter bit;

where the per-processor need-memory-barrier bit within the last set of per-processor need-memory-barrier bits and corresponding to the processor currently executing the task is equal to one,

executing a memory barrier; and

,

incrementing the per-processor need-memory-barrier bit within the last set of per-processor need-memory-barrier bits and corresponding to the processor currently executing the task.

17. The method of claim 16, further comprising:

prior to decrementing the per-task read-lock-nesting counter corresponding to the task performing the critical read operation, disabling preemption and/or interrupts; and

,

after incrementing the per-processor need-memory-barrier bit within the last set of per-processor need-memory-barrier bits and corresponding to the processor currently executing the task, enabling preemption and/or interrupts.

18. The method of claim 11, further comprising:

where a per-processor need-memory-barrier bit of the last set of per-processor need-memory-barrier bits corresponding to a given processor is equal to one,

executing a memory barrier; and

,

incrementing the per-processor need-memory-barrier bit of the last set of per-processor need-memory-barrier bits corresponding to the given processor.