Patent ID: 7533221

Claim:
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: a shared freelist data structure accessible by a plurality of threads executing on the one or more processors, the shared freelist indicating a pool of nodes that may be allocated by the plurality of threads; and coordination of accesses to the shared freelist using only pointer-sized single-target synchronizations; wherein the program instructions are further executable to implement CONTRACT, GET, and PUT sequences; wherein in response to execution of a GET sequence, the one or more processors are configured to cause a node to be removed from the shared freelist for use by at least one of the plurality of threads; wherein in response to execution of a PUT sequence, the one or more processors are configured to cause a node previously removed from the shared freelist by execution of a GET sequence to be reintroduced into the shared freelist; wherein in response to execution of a CONTRACT sequence, the one or more processors are configured to remove one or more nodes from the shared freelist and to cause storage associated with the removed one or more nodes to be freed to a general allocation pool; wherein the program instructions are further executable to implement an entry tag coding selective for a current one of two alternative pointers to an end node at one end of the shared freelist and including a pinning thread count, the entry tag coding alternating from the current one to a non-current one of the alternative pointers by operation of a particular one of the pointer-sized single-target synchronizations; wherein operations on the shared freelist are performed in a lock-free manner; and wherein memory consumption of the freelist at a given time is proportional to both freelist size and a number of threads currently accessing the shared freelist.