Lock-free implementation of dynamic-sized shared data structure

A computer program product encoded in one or more computer readable storage media and including a dynamically-sizable implementation of a data structure, comprising:

• a representation of the dynamically-sizable data structure instantiable as separately reclaimable blocks of storage sharable, at least in part, by plural threads of a multithreaded computation;
• a first instruction sequence executable by one or more of the threads to:
• access the data structure;
• successfully post a guard on a value that encodes a pointer, wherein the value references storage in the data structure, wherein said successfully posting comprises:
• determining that storage referenced by the pointer remains in the data structure;
• and
• in response to determining that storage referenced by the pointer remains in the data structure, posting a guard on the value that encodes the pointer;
• and
• dereference the pointer in response to said successful posting;
• a second instruction sequence executable by one or more of the threads to qualify for deallocation, a respective one of the storage blocks referenced by the value;
• and
• a third instruction sequence executable by one or more of the threads to return storage referenced by the deallocation qualified value.

A computer program product encoded in one or more computer readable storage media and comprising:

• an instruction sequence that includes one or more instructions, wherein the one or more instructions are configured to:
• provide a dynamically-sizable shared data structure, wherein the shared data structure includes separately reclaimable blocks of storage sharable, at least in part, by a plurality of threads of a multithreaded computation;
• in one of the plurality of threads of the multithreaded computation, successfully post a guard on a value that encodes a pointer read from the shared data structure;
• in response to said successfully posting, dereference the pointer;
• free storage referenced by the value, wherein said freeing comprises:
• determining that storage referenced by the pointer is not in the shared data structure;
• determining that no guard successfully posted on the value remains successfully posted on the value;
• and
• in response to determining that storage referenced by the pointer is not in the shared data structure and no guard successfully posted on the value remains successfully posted on the value, Qualify the storage referenced by the value for deallocation.

An apparatus for supporting dynamic-sizing of a shared data structure, the apparatus comprising:

• means for representing the shared data structure as separately reclaimable blocks of storage sharable, at least in part, by a plurality of threads of a multithreaded computation;
• means for, in one of the plurality of threads of the multithreaded computation, successfully posting a guard on a value that encodes a pointer read from the shared data structure;
• means for, in response to said successfully posting, dereferencing the pointer;
• means for freeing storage referenced by the value, wherein said freeing comprises:
• determining that storage referenced by the pointer is not in the shared data structure;
• determining that no guard successfully posted on the value remains successfully posted on the value;
• and
• qualifying for deallocation, the storage referenced by the value.