Hardware Extensions for Memory Reclamation for Concurrent Data Structures
First Claim
1. A method, comprising:
- performing, by a plurality of computing nodes;
beginning execution of a multithreaded application that comprises one or more accesses to a concurrent data structure that is accessible to multiple threads of the multithreaded application;
issuing, by a thread or process executing on a processor core of one of the plurality of computing nodes, an instruction to store a pointer to a location in a shared memory at which an element of the concurrent data structure resides to the hazard table; and
in response to said issuing;
storing an entry for the pointer to a hazard lookaside buffer component that is locally accessible to the processor core, wherein the hazard lookaside buffer component is configured to store information about pointers that have been or are going to be dereferenced by software executing on the processor core and about which information has not yet been written to the hazard table, and wherein said storing the pointer to the hazard lookaside buffer does not require the thread or process to issue a memory barrier instruction following the issuing of the instruction.
1 Assignment
0 Petitions
Accused Products
Abstract
A hardware-assisted mechanism may improve the performance of memory reclamation operations that employ hazard pointers. The mechanism includes hazard lookaside buffers (HLBs), each implemented in hardware and locally accessible to one or more processor cores, and two new instructions. A special store instruction may write entries to local HLBs for pointers that have been or will be dereferenced but were not yet written to a shared hazard table (which requires memory barriers). Each entry may include a hazard pointer and a table address. A special test instruction may signal each HLB to determine whether it contains a particular pointer and, if so, to return a response. If the pointer does not reside in any HLB, the memory reclamation operation may search the hazard table for the pointer. If the pointer is found in an HLB or in the hazard table, the pointed-to memory location or memory block is not reclaimed.
-
Citations
20 Claims
-
1. A method, comprising:
performing, by a plurality of computing nodes; beginning execution of a multithreaded application that comprises one or more accesses to a concurrent data structure that is accessible to multiple threads of the multithreaded application; issuing, by a thread or process executing on a processor core of one of the plurality of computing nodes, an instruction to store a pointer to a location in a shared memory at which an element of the concurrent data structure resides to the hazard table; and in response to said issuing; storing an entry for the pointer to a hazard lookaside buffer component that is locally accessible to the processor core, wherein the hazard lookaside buffer component is configured to store information about pointers that have been or are going to be dereferenced by software executing on the processor core and about which information has not yet been written to the hazard table, and wherein said storing the pointer to the hazard lookaside buffer does not require the thread or process to issue a memory barrier instruction following the issuing of the instruction. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
10. A system, comprising:
-
a plurality of processor cores; a plurality of hazard lookaside buffer components; a bus interface; a shared memory that is accessible by each of the plurality of processor cores over the bus interface; and a hazard table that is maintained in the shared memory, wherein the hazard table is configured to store information about potentially hazardous pointers, wherein a potentially hazardous pointer identifies memory that cannot be safely reclaimed; wherein each of the plurality of processor cores is associated with one of the plurality of hazard lookaside buffer components that is locally accessible to the processor core; and wherein each of the hazard lookaside buffer components is configured to store information about potentially hazardous pointers that have been or are going to be dereferenced by software executing on the processor core to which it is locally accessible and about which information has not yet been written to the hazard table. - View Dependent Claims (11, 12, 13, 14)
-
-
15. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more processor cores cause the one or more processor codes to implement a multithreaded application;
wherein the multithreaded application comprises a testing instruction that is invoked by an operation to determine whether or not a given shared memory location or block of shared memory can be recycled, wherein the testing instruction is configured to; determine whether or not a pointer to the given shared memory location or block of shared memory resides in any of a plurality of buffer components that store information about potentially hazardous pointers, each of which is locally accessible to one or more threads executing on one of the one or more processor cores, wherein a potentially hazardous pointer identifies memory that cannot be safely recycled; and determine, in response to receiving an indication from one of the plurality of buffer components that a pointer to the given shared memory location or block of shared memory resides in the one of the plurality of buffer components, that the given shared memory location or block of shared memory cannot be recycled. - View Dependent Claims (16, 17, 18, 19, 20)
Specification