Atomic Updates of Versioned Data Structures

Apparatus, comprising:

• circuitry, configured to facilitate reading from a shared memory;
• and
• a processor, configured to:
• atomically copy a shared current-version number from the shared memory to a local current-version number,
• subsequently to atomically copying the shared current-version number, using the circuitry, copy data from a portion of the shared memory that is referenced by the local current-version number,
• subsequently to copying the data, compare at least part of the local current-version number with another number in the shared memory that indicates a version of the data, and
• in response to the at least part of the local current-version number being equal to the other number, return the copy of the data.

A system, comprising:

• a shared memory;
• and
• one or more processors, configured to:
• allocate, in the shared memory, a current-version number and a cyclic array, and
• subsequently to allocating the current-version number and the cyclic array:
• by executing a first execution thread, write a series of versions of data to the shared memory, by, for each version of the versions:
• writing the version to a first element of the cyclic array that follows a second element of the cyclic array referenced by the current-version number, and
• subsequently to writing the version, atomically updating the current-version number to reference the first element of the cyclic array, and
• while the first execution thread is executed:
• by executing a second execution thread, read the current-version number, and
• subsequently to reading the current-version number, read one of the versions stored in an element of the cyclic array that is referenced by the current-version number.

A method, comprising:

• computing a local current-version number by incrementing a shared current-version number that is stored in a shared memory;
• subsequently to computing the local current-version number, atomically writing at least part of the local current-version number to a portion of the shared memory that is referenced by the local current-version number;
• subsequently to atomically writing the at least part of the local current-version number, storing data in the shared memory in association with the at least part of the local current-version number;
• and
• subsequently to storing the data, atomically overwriting the shared current-version number with the local current-version number.

A method, comprising:

• atomically copying a shared current-version number from a shared memory to a local current-version number;
• subsequently to atomically copying the shared current-version number, copying data from a portion of the shared memory that is referenced by the local current-version number;
• subsequently to copying the data, comparing at least part of the local current-version number with another number in the shared memory that indicates a version of the data;
• and
• in response to the at least part of the local current-version number being equal to the other number, returning the copy of the data.

A method, comprising:

• allocating, in a shared memory, a current-version number and a cyclic array;
• and
• subsequently to allocating the current-version number and the cyclic array:
• writing, by a first execution thread, a series of versions of data to the shared memory, by, for each version of the versions:
• writing the version to a first element of the cyclic array that follows a second element of the cyclic array referenced by the current-version number, and
• subsequently to writing the version, atomically updating the current-version number to reference the first element of the cyclic array, and
• while the first execution thread is writing the series of versions of the data:
• reading, by a second execution thread, the current-version number, and
• subsequently to reading the current-version number, reading one of the versions stored in an element of the cyclic array that is referenced by the current-version number.