Practical implementation of arbitrary-sized LL/SC variables

A computer-readable storage medium, comprising program instructions computer-executable to implement a load-linked, store-conditional (LL/SC) synchronization construct that emulates LL/SC synchronization primitives, the LL/SC construct comprising:

• a first functional sequence executable to implement a load-linked (LL) operation;
• a second functional sequence executable to implement a store-conditional (SC) operation;
• wherein the load-linked (LL) and store-conditional (SC) operations are executable to operate on an LL/SC variable of arbitrary-size without use of a synchronization primitive that atomically manipulates storage larger than a pointer;
• wherein the LL/SC variable includes an entry tag selective for a current one of two alternative pointers, the entry tag coding alternating from the current one to a non-current one of the two alternative pointers by operation of a particular instance of the synchronization construct;
• and
• wherein storage employed by the synchronization construct does not depend on a number of threads that will or might access the LL/SC variable.

A computer-implemented method comprising:

• using a computer to perform:
• instantiating a load-linked/store-conditional (LL/SC) variable in memory, wherein the instantiated LL/SC variable has an associated entry tag selective for a current one of two alternative pointers identifying different respective instances of a structure that encodes values corresponding to the LL/SC variable, the entry tag coding alternating from the current one to a non-current one of the two alternative pointers by operation of a particular instance of a single-target synchronization;
• emulating a load-linked (LL) operation on the LL/SC variable, in part by using a first single-target synchronization operation to ensure consistency of persistent thread local values read for the current one of the two alternative pointers and at least a version portion of the associated entry tag;
• and
• emulating a store-conditional (SC) operation on the LL/SC variable, in part by using a single-target synchronization operation to introduce into the non-current one of the two alternative pointers a pointer to a structure that encodes a value corresponding to SC operation and thereafter incrementing at least a version portion of the associated entry tag.

An apparatus, comprising:

• one or more processors;
• a memory shared amongst the one or more processors to allow concurrent access to an arbitrary-sized LL/SC variable instantiated therein by threads executable on respective ones of the processors;
• and
• a load-linked/store-conditional (LL/SC) synchronization construct including a computer readable encoding of an entry tag selective for a current one of two alternative pointers to different respective instances of a structure that encodes the arbitrary-sized LL/SC variable, the entry tag coding alternating from the current one to a non-current one of the two alternative pointers by operation of a particular instance of the synchronization construct;
• wherein in response to an SC operation targeting the arbitrary-sized LL/SC variable, an executing thread introduces into the non-current one of the two alternative pointers a pointer to a structure that encodes a store value of the SC operation and the non-current pointer is thereafter selected as current one of the two alternative pointers using a single-target synchronization targeting the associated entry tag.