US 10,866,890 B2 · Method and apparatus for implementing lock-free data structures

Abstract

An instruction set architecture of a data processing system includes one or more persistent atomic instructions that provide failure-safe atomicity. When issued, a sequence of operations associated with the persistent atomic instruction are performed and first data, associated with a first address in a persistent memory of the data processing system, is written to a point of persistence in the data processing system. Access to data associated with the first address is controlled such that the first data is not available to other execution threads of the data processing system until completion of writing the first data to the point of persistence. The point of persistence may be the persistent memory itself or a persist buffer. The persist buffer may be a volatile or non-volatile buffer. One or more monitors may control access to data at memory addresses dependent upon a designated state of exclusivity.

Claims21

Dependent claims

A method comprising:

responsive to a persistent atomic instruction issued by a first execution thread in a data processing system, the persistent atomic instruction associated with a first address in a persistent memory of the data processing system:
performing a sequence of actions associated with the persistent atomic instruction;
and
writing first data to a point of persistence in the data processing system, where the point of persistence comprises a persist buffer and the first data is produced by the sequence of actions or is associated with the persistent atomic instruction;
controlling accesses associated with the first address in the persistent memory such that the first data is not available to other execution threads of the data processing system until completion of writing the first data to the point of persistence in the data processing system;
and
copying contents of the persist buffer to the persistent memory, where the copying is not synchronized with the completion of the persistent atomic instruction.

4 more elements

A method comprising:

executing, responsive to a persistent atomic instruction issued by a first execution thread in a data processing system, a first store operation associated with first data and a first address in a persistent memory of the data processing system, where a monitor of the data processing system controls access to data associated with the address in the persistent memory dependent upon a first monitor state, in which access to the first data is open to any execution thread operating in the data processing system, and a second monitor state, in which access to the data is exclusive to a designated execution thread;
responsive the first store operation, performing a sequence of actions comprising:
setting the monitor state to the second state;
putting a line of a cache of the data processing system into an exclusive state of a coherence protocol;
updating the cache line with the first data;
writing the first data to a point of persistence in the apparatus;
and
setting the monitor state to the first monitor state following completion of writing the first data to a point of persistence in the apparatus,
where the point of persistent is in the persistent memory or in a persist buffer of the data processing system.

6 more elements

An apparatus comprising:

a processing device comprising a processing core and a data cache;
a persistent memory accessible by the processing device;
and
a monitor configured to control access to data associated with a data address in the persistent memory dependent upon a first monitor state, in which access to the data is open to any execution thread operating on the processing device, and a second monitor state, in which access to the data is exclusive to a designated execution thread;
where, responsive to a persistent atomic instruction issued by the processing core, the apparatus is configured for:
generating a first store operation to store first data at a first address in the persistent memory;
setting the monitor state to the second state;
putting a line of the cache in an exclusive state;
updating the cache line with the first data;
writing the first data to a point of persistence in the apparatus;
and
setting the monitor state to the first monitor state following completion of writing the first data to a point of persistence in the apparatus,
where the point of persistent comprises the persistent memory or a persist buffer of the data processing system.

10 more elements

Dependencies are inferred from the claim text.

Method and apparatus for implementing lock-free data structures

Life of this patent

Method and apparatus for implementing lock-free data structures

Life of this patent

Abstract

Claims21