SYSTEMS AND METHODS FOR CONTROLLING ACCESS TO A SHARED DATA STRUCTURE WITH READER-WRITER LOCKS USING MULTIPLE SUB-LOCKS

• US 20150248367A1
• Filed: 07/31/2012
• Published: 09/03/2015
• Est. Priority Date: 07/31/2012
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Tucek, Joseph
• Granted Patent: US 9,690,737 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means
• CPC Class Codes: G06F 13/4027 using bus bridges G06F13/4022 takes precedence
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 2212/621 Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A computer system for controlling access to a shared data structure includes a shared memory coupled to first and second processing units that stores a multi-lock to control access to a shared data structure. The multi-lock includes a first sub-lock associated with the first processing unit and a second sub-lock associated with the second processing unit The system also includes a data access control engine to receive a request to read from the data structure from the first processing unit and, as a result, determine whether a privately modifiable copy the first sub-lock exists in a first cache dedicated to the first processing unit, acquire a read portion of the first sub-lock and not communicate the acquisition across a coherence bus if a privately modifiable copy of the first sub-lock exists in the first cache, and if a privately modifiable copy of the first sub-lock does not exist in the first cache, load the first sub-lock into the first cache if no copy is in the first cache, shootdown other copies of the first sub-lock, and acquire the read portion of the first sub-lock.

Claims

1. A computer system for controlling access to a shared data structure, comprising:

a first processing unit coupled to a first cache dedicated to the first processing unit;

a second processing unit coupled to a second cache dedicated to the second processing unit;

a shared memory coupled to the first and second processing units that stores a multi-lock to control access to a data structure shared by the first and second processing units, the multi-lock comprising a first sub-lock associated with the first processing unit and a second sub-lock associated with the second processing unit, the sub-locks comprising a read portion and a write portion;

a coherence bus that couples the first and second caches and carries coherency information between the first and second caches; and

a data access control engine to receive a request to read from the data structure from the first processing unit and, as a result;

determine whether a privately modifiable copy the first sub-lock exists in the first cache;

acquire the read portion of the first sub-lock and not communicate the acquisition across the coherence bus if a privately modifiable copy of the first sub-lock exists in the first cache; and

if a privately modifiable copy of the first sub-lock does not exist in the first cache, load the first sub-lock into the first cache if no copy is in the first cache, shootdown other copies of the first sub-lock, and acquire the read portion of the first sub-lock.

2. The computer system of claim 1 wherein the coherence bus carries coherency information that implements a MESI cache coherence protocol.

3. The computer system of claim 2 wherein a copy of the first sub-lock is privately modifiable if a cache line that stores the first sub-lock in the first cache is in a modified or exclusive state.

4. The computer system of claim 2 wherein a copy of the first sub-lock is not privately modifiable if a cache line that stores the first sub-lock in the first cache is in a shared or invalid state or there is no cache line that stores the first sub-lock in the first cache, and wherein if the cache line that stores the first sub-lock in the first cache is in the shared state, a shootdown is issued to the second cache over the coherence bus and the read portion of the first sub-lock is acquired.

5. The computer system of claim 2 wherein the data access control engine is further configured to receive a request to write to the shared data structure from the first processing unit and, as a result, for each sub-lock of the multi-lock:

acquire the write portion of the sub-lock if the read portion indicates there are no processing units that have acquired the read portion of the sub-lock and a cache line storing the sub-lock in the first cache is in a modified or exclusive state;

acquire the write portion of the sub-lock and issue a shootdown to caches other than the first cache if the read portion indicates that there are no processing units that have acquired the read portion of the sub-lock and a cache line storing the sub-lock in the first cache is in a shared state; and

if a privately modifiable copy of the sub-lock does not exist in the first cache, load the sub-lock into the first cache if no copy is in the first cache, acquire the write portion of the sub-lock, and issue a shootdown to caches other than the first cache if the read portion indicates that there are no processing units that have acquired the read portion of the sub-lock.

6. The computer system of claim 1 wherein a shootdown is issued to the second cache over the coherence bus when the first sub-lock is loaded into the first cache from the shared memory.

7. A method for controlling access to a shared data structure, comprising:

storing a multi-lock to control access to the data structure, the multi-lock comprising a first sub-lock associated with a first processing unit and a second sub-lock associated with a second processing unit, each sub-lock comprising a read portion and a write portion;

receiving a request to read from the data structure from the first processing unit;

determining whether a privately modifiable copy of the first sub-lock exists in a first cache dedicated to the first processing unit;

acquiring the read portion of the first sub-lock and not communicating the acquisition across a coherence bus between the first cache and a second cache dedicated to the second processing unit if a privately modifiable copy of the first sub-lock exists in the first cache; and

loading the first sub-lock into the first cache if no copy is in the first cache and acquiring the read portion of the first sub-lock if a privately modifiable copy of the first sub-lock does not exist in the first cache.

8. The method of claim 7 wherein the coherence bus carries coherency information that implements a MESI cache coherence protocol.

9. The method of claim 8 wherein a copy of the first sub-lock is privately modifiable if a cache line that stores the first sub-lock in the first cache is in a modified or exclusive state.

10. The method of claim 8 wherein a copy of the first sub-lock is not privately modifiable if a cache line that stores the first sub-lock in the first cache is in a shared or invalid state or there is no cache line that stores the first sub-lock in the first cache, and wherein if the cache line that stores the first sub-lock in the first cache is in the shared state, the method further comprises issuing a shootdown to the second cache over the coherence bus and acquiring the read portion of the first sub-lock.

11. The method of claim 8 further comprising receiving a request to write to the data structure from the first processing unit and, as a result, for each sub-lock of the multi-lock:

acquiring the write portion of the sub-lock if the read portion indicates there are no processing units that have acquired the read portion of the sub-lock and a cache line storing the sub-lock in the first cache is in a modified or exclusive state;

acquiring the write portion of the sub-lock and issuing a shootdown to caches other than the first cache if the read portion indicates that there are no processing units that have acquired the read portion of the sub-lock and a cache line storing the sub-lock in the first cache is in a shared state; and

if a privately modifiable copy of the sub-lock does not exist in the first cache, loading the sub-lock into the first cache if no copy is in the first cache, acquiring the write portion of the sub-lock, and issuing a shootdown to caches other than the first cache if the read portion indicates that there are no processing units that have acquired the read portion of the sub-lock.

12. The method of claim 7 further comprising issuing a shootdown to the second cache over the coherence bus when the first sub-lock is loaded into the first cache from the shared memory.

13. A non-transitory computer-readable storage device storing software that, when executed by a processor including a coherence bus, causes the processor to:

store a multi-lock to control access to a data structure, the multi-lock comprising a first sub-lock associated with a first processing unit and a second sub-lock associated with a second processing unit, each sub-lock comprising a read portion and a write portion;

receive a request to read from the data structure from the first processing unit;

determine whether a privately modifiable copy of the first sub-lock exists in a first cache dedicated to the first processing unit;

acquire the read portion of the first sub-lock and not communicate the acquisition to a second cache dedicated to the second processing unit if a privately modifiable copy of the first sub-lock exists in the first cache; and

load the first sub-lock into the first cache if no copy is in the first cache and acquire the read portion of the first sub-lock if a privately modifiable copy of the first sub-lock does not exist in the first cache.

14. The non-transitory computer-readable storage device of claim 13 wherein the coherence bus carries coherency information that implements a MESI cache coherence protocol.

15. The non-transitory computer-readable storage device of claim 14 wherein the processor receives a request to write to the data structure from the first processing unit and, as a result_:

for each sub-lock of the multi-lock;

acquires the write portion of the sub-lock if the read portion indicates there are no processing units that have acquired the read portion of the sub-lock and a cache line storing the sub-lock in the first cache is in a modified or exclusive state;

acquires the write portion of the sub-lock and issues a shootdown to caches other than the first cache if the read portion indicates that there are no processing units that have acquired the read portion of the sub-lock and a cache line storing the sub-lock in the first cache is in a shared state; and

if a privately modifiable copy of the sub-lock does not exist in the first cache, loads the sub-lock into the first cache if no copy is in the first cache, acquires the write portion of the sub-lock, and issues a shootdown to caches other than the first cache if the read portion indicates that there are no processing units that have acquired the read portion of the sub-lock.