Read-copy update implementation for non-cache-coherent systems

• US 9,189,413 B2
• Filed: 06/20/2011
• Issued: 11/17/2015
• Est. Priority Date: 06/20/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Doan, Han
• Application Number:
  US13/164,423
• Publication Number:
  US 20120324170A1
• Time in Patent Office: 1,611 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means

Abstract

A technique for implementing read-copy update in a shared-memory computing system having two or more processors operatively coupled to a shared memory and to associated incoherent caches that cache copies of data stored in the memory. According to example embodiments disclosed herein, cacheline information for data that has been rendered obsolete due to a data update being performed by one of the processors is recorded. The recorded cacheline information is communicated to one or more of the other processors. The one or more other processors use the communicated cacheline information to flush the obsolete data from all incoherent caches that may be caching such data.

Claims

1. A system, comprising:

two or more processors;

a memory coupled to said two or more processors;

incoherent caches associated with said two or more processors for caching copies of data stored in said memory without hardware-implemented cache coherency support;

said memory including a computer useable medium tangibly embodying at least one program of instructions executable by each of said two or more processors to perform read-copy update operations, said operations comprising;

recording cacheline information identifying cachelines containing data that has been rendered obsolete in an incoherent cache associated with one processor of said two or more processors due to a data update being performed by said one processor of said two or more processors;

said recording comprising said one processor of said two or more processors storing said cacheline information in a local cache record data structure associated with said one processor of said two or more processors;

communicating said recorded cacheline information to different processors of said two or more processors;

said communicating comprising either said different processors reading said local cache record data structure or said one processor of said two or more processor merging said cacheline information from said local cache record data structure into a global cache record data structure that stores cacheline information merged from two or more local cache record data structures associated with different processors, said cacheline information being merged either directly into said global cache record data structure or through a hierarchy comprising one or more levels of intermediate cache record data structures; and

using said communicated cacheline information to identify cachelines that contain said obsolete data in incoherent caches associated with said different processors and flush said obsolete data from said identified cachelines.

2. The system of claim 1, wherein said recording comprises an updater determining a memory address extent of said obsolete data in said memory during said data update to identify said cachelines that hold said obsolete data, and storing said cacheline information during said update in a local cache record data structure associated with a processor that is performing said recording.

3. The system of claim 1, wherein said recording comprises an updater determining a memory address extent of said obsolete data in said memory during said data update to identify said cachelines that hold said obsolete data, and storing said cacheline information following said update in a local cache record data structure associated with a processor that is performing said recording.

4. The system of claim 1, wherein a compression storage technique is used to record said cacheline information.

5. The system of claim 1, wherein said flushing comprise using said cacheline information stored in said local cache record data structure or said global cache record data structure to identify and flush said obsolete data from said incoherent caches.

6. The system of claim 1, wherein said communicating and said flushing are respectively performed during first and second grace period phases by each of said two or more processors or by one or more proxy processors of said two or more processors that perform said operations on behalf of said different processors.

7. A computer program product, comprising:

one or more non-transitory machine-useable storage media;

program instructions provided by said one or more non-transitory machine-useable storage media for programming a data processing system to perform read-copy update operations, said data processing system having two or more processors operatively coupled to a shared memory and to associated incoherent caches that cache copies of data stored in said memory without hardware-implemented cache coherency support, said read-copy update operations comprising;

recording cacheline information for identifying cachelines containing data that has been rendered obsolete in an incoherent cache associated with one processor of said two or more processors due to a data update being performed by said one processor of said two or more processors;

said recording comprising said one processor of said two or more processors storing said cacheline information in a local cache record data structure associated with said one processor of said two or more processors;

communicating said recorded cacheline information to different processors of said two or more processors;

said communicating comprising either said different processors reading said local cache record data structure or said one processor of said two or more processors merging said cacheline information from said local cache record data structure into a global cache record data structure that stores cacheline information merged from two or more local cache record data structures associated with different processors, said cacheline information being merged either directly into said global cache record data structure or through a hierarchy comprising one or more levels of intermediate cache record data structures; and

using said communicated cacheline information to identify cachelines that contain said obsolete data in incoherent caches associated with said different processors and flush said obsolete data from said identified cachelines.

8. The computer program product of claim 7, wherein said recording comprises an updater determining a memory address extent of said obsolete data in said memory during said data update to identify said cachelines that hold said obsolete data, and storing said cacheline information during said update in a local cache record data structure associated with a processor that is performing said recording.

9. The computer program product of claim 7, wherein said recording comprises an updater determining a memory address extent of said obsolete data in said memory during said data update to identify said cachelines that hold said obsolete data, and storing said cacheline information following said update in a local cache record data structure associated with a processor that is performing said recording.

10. The computer program product of claim 7, wherein a compression storage technique is used to record said cacheline information.

11. The computer program product of claim 7, wherein said flushing comprises using said cacheline information stored in said local cache record data structure or said global cache record data structure to identify and flush said obsolete data from said incoherent caches.

12. The computer program product of claim 7, wherein said communicating and said flushing are respectively performed during first and second grace period phases by each of said two or more processors or by one or more proxy processors of said two or more processors that perform said operations on behalf of said different processors.