Practical implementation of arbitrary-sized LL/SC variables
View Patent ↗Many conventional lock-free data structures exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, “64-bit-clean” lock-free data structures, which cannot use such techniques, are needed. We present several 64-bit-clean lock-free implementations: including load-linked/store conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software (or more generally full-architectural-width pointer operations), our implementations also improve on existing techniques in that they are (or can be) space-adaptive and do not require a priori knowledge of the number of threads that will access them.
1. A computing system, comprising:
one or more processors configured for multithreaded operation;
a memory comprising program instructions executable by the one or more processors to implement:
emulation of load-linked, store-conditional (LL/SC) synchronization primitives that employ only pointer-sized single-target synchronization operations to coordinate access to pointer-referenced LL/SC variables, wherein the emulation is lock-free, population-oblivious and space-adaptive;
wherein to emulate LL/SC synchronization primitives, the program instructions are executable to implement:
instantiating an instance of an LL/SC variable in memory, 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 one of the pointer-sized single-target synchronization operations.
2. The computing system of claim 1 , wherein the two alternative pointers identify different respective instances of a structure that encodes values corresponding to the LL/SC variable.
3. The computing system of claim 2 , wherein the program instructions comprise:
a first functional sequence executable to implement a load-linked (LL) operation on the LL/SC variable, the first functional sequence including 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.
4. The computing system of claim 2 , wherein the program instructions further comprise:
a second functional sequence executable to implement a store-conditional (SC) operation on the LL/SC variable, the second functional sequence including a second single-target synchronization operation to introduce into the non-current one of the two alternative pointers a pointer to a structure that encodes a store value of the SC operation, the non-current pointer thereafter selectable as the current one of the two alternative pointers using a third single-target synchronization operation on at least a version portion of the associated entry tag.
5. The computing system of claim 4 ,
wherein selection of the previously non-current pointer as current results from incrementing or decrementing the version portion.
6. The computing system of claim 4 ,
wherein the second functional sequence includes an executable instance of the third single-target synchronization operation.
7. The computing system of claim 4 , wherein the program instructions are further executable to implement:
a helper sequence or thread executing the third single-target synchronization operation.
8. The computing system of claim 2 ,
wherein the entry tag includes a version portion; and
wherein certain values of the version portion are selective for a first of the two alternative pointers and other values of the version portion are selective for a second of the two alternative pointers.
9. The computing system of claim 8 , wherein the program instructions are further executable to implement:
updating the version portion, using a single-target synchronization operation, in correspondence with a successful execution of an SC operation on the corresponding LL/SC variable.
10. The computing system of claim 9 ,
wherein the updating includes incrementing the version portion.
11. The computing system of claim 8 ,
wherein the certain values include even values.
12. The computing system of claim 2 ,
wherein the entry tag includes a count portion; and
wherein the program instructions are further executable to implement:
updating the count portion, using the first single-target synchronization operation, in correspondence with a successful execution of an LL operation on the corresponding LL/SC variable.
13. The computing system of claim 12 ,
wherein the updating includes incrementing or decrementing the count portion.
14. The computing system of claim 2 ,
wherein the value encoding structure includes storage for a pointer to a previously current instance thereof.
15. The computing system of claim 2 ,
wherein the value encoding structure includes an exit tag.
16. The computing system of claim 1 ,
wherein the LL/SC variable is of arbitrary size.
17. The computing system of claim 1 , wherein the pointer-sized single-target synchronization operations include one or more of:
pointer-sized compare-and-swap (CAS) operations; and
pointer-sized load-linked (LL) and store-conditional (SC) operation pairs.
18. The computing system of claim 2 , wherein the program instructions further comprise:
a third functional sequence executable to implement an unlink operation on the LL/SC variable.
19. The computing system of claim 18 ,
wherein the entry tag includes a count portion; and
wherein the program instructions are further executable to implement:
updating the count portion, using a fourth single-target synchronization operation, in correspondence with at least some executions of the unlink operation.
20. The computing system of claim 19 ,
wherein the updating includes decrementing the count portion.
21. 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.
22. The storage medium of claim 21 ,
wherein the load-linked (LL) and store-conditional (SC) operations each employ pointer-size single-target synchronization primitives.
23. The storage medium of claim 22 , wherein the pointer-size single-target synchronization primitives include one or more pointer-size Compare-and-Swap (CAS) operations or pointer-sized load-linked (LL) and store-conditional (SC) operation pairs.
24. The storage medium of claim 21 , embodied as a computer program product encoded in at least one medium selected from the set of a disk, tape or other magnetic, optical, or electronic storage medium.
25. 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:
an encoding of an entry tag selective for a current one of two alternative pointers identifying different respective instances of a structure that encodes an associated 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; and
a first functional sequence executable to introduce into the non-current one of the two alternative pointers, a pointer to a structure that encodes a store value of an SC operation targeting the arbitrary-sized LL/SC variable, the non-current pointer thereafter selectable as the current one of the two alternative pointers by operation of a single-target synchronization on the associated entry tag.
26. The storage medium of claim 25 ,
wherein the associated entry tag includes both a version portion selective for a particular one of the two alternative pointers and a count portion indicative of a currently outstanding number of successful LL operations that have observed the currently selected one of the alternate two alternative pointers.
27. The storage medium of claim 25 ,
wherein the first functional sequence at least partially implements the SC operation.
28. The storage medium of claim 25 ,
wherein selection of the non-current pointer as current is performed by the first functional sequence.
29. The storage medium of claim 25 ,
wherein, for at least some executions, selection of the non-current pointer as current is performed by another thread in response to operation of the first functional sequence.
30. The storage medium of claim 25 , wherein the LL/SC synchronization construct further comprises:
exit tags associated with respective ones of the structure instances that encode the arbitrary-sized LL/SC variable.
31. The storage medium of claim 30 ,
wherein the exit tags encode, for their respective structures, a count of corresponding LL operations that have released the respective structure.
32. The storage medium of claim 30 ,
wherein exit tag encodings disambiguate an initial state from a state in which all successful LL operations have a corresponding successful release.
33. The storage medium of claim 25 , wherein the LL/SC synchronization construct further comprises:
a second functional sequence executable to load a value of the arbitrary-sized LL/SC variable into storage local to an executing thread and to atomically increment a link count corresponding thereto.
34. The storage medium of claim 33 , wherein the LL/SC synchronization construct further comprises:
a third functional sequence executable to unlink a previously executed LL operation and to atomically decrement a link count corresponding thereto.
35. The storage medium of claim 25 ,
wherein the LL/SC synchronization construct is embodied, in part, as a definition of the arbitrary-sized LL/SC variable instantiable in memory of a multiprocessor;
wherein the LL/SC synchronization construct is embodied, at least in part, in a nonblocking implementation of a concurrent shared object;
wherein the LL/SC synchronization construct is embodied, at least in part, in an execution environment or operating system; or
wherein the LL/SC synchronization construct is embodied as a software emulation of at least a load-linked operation and a store-conditional operation.
36. 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.
37. The method of claim 36 ,
wherein the instantiated LL/SC variable has an associated entry count.
38. The method of claim 36 ,
wherein the respective structure instances have associated exit tags.
39. The method of claim 36 , further comprising:
the computer coordinating reclamation of instances of the LL/SC value encoding structures, at least in part, by reconciling associated entry and exit counts.
40. 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.