Hardware extensions for memory reclamation for concurrent data structures

• US 9,785,548 B2
• Filed: 11/19/2015
• Issued: 10/10/2017
• Est. Priority Date: 11/19/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Kogan, Alex, Dice, David, Herlihy, Maurice P.
• Primary Examiner(s): Dudek, Jr., Edward
• Assistant Examiner(s): Verderamo, III, Ralph A
• Application Number:
  US14/946,625
• Publication Number:
  US 20170147487A1
• Time in Patent Office: 691 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

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.

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.

2. The method of claim 1, wherein said issuing is performed in response to the thread or process issuing an instruction that dereferences the pointer.

3. The method of claim 1, further comprising:

issuing, by the thread or process, another instruction that dereferences the pointer;

determining that an entry for the pointer is stored in the hazard lookaside buffer component that is locally accessible to the processor core; and

overwriting the entry for the pointer stored in the hazard lookaside buffer component that is locally accessible to the processor core.

4. The method of claim 1, further comprising:

determining that the hazard lookaside buffer component is full; and

in response to said determining, writing information about one or more pointers that have been dereferenced or are going to be dereferenced by software executing on the processor core to the hazard table.

5. The method of claim 1, further comprising:

performing, by the thread or process, a memory reclamation operation, wherein said performing comprises;

issuing an instruction for determining whether or not an entry for a given pointer resides in any one or more of a plurality of hazard lookaside buffer components, including the hazard lookaside buffer, each of which is locally accessible to a processor core of one of the plurality of computing nodes;

wherein the instruction is configured to initiate a search for the given pointer in the plurality of hazard lookaside buffer components.

6. The method of claim 5, further comprising:

executing the instruction for determining whether or not an entry for a given pointer resides in one or more of the plurality of hazard lookaside buffer components;

wherein said executing comprises broadcasting a bus transaction indicating that the plurality of hazard lookaside buffer components are to be searched for the given pointer; and

detecting, by the plurality of hazard lookaside buffer components, the bus transaction.

7. The method of claim 5, further comprising:

receiving a respective response from one or more of the plurality of hazard lookaside buffer components indicating that an entry for the given pointer resides in the hazard lookaside buffer component; and

refraining from reclaiming memory identified by the given pointer.

8. The method of claim 5, further comprising:

performing, in response to a failure to receiving a response from any one or more of the plurality of hazard lookaside buffer components indicating that an entry for the given pointer resides in the hazard lookaside buffer component, an operation to search for the given pointer in the hazard table;

determining that an entry for the given pointer resides in the hazard table; and

refraining from reclaiming memory identified by the given pointer.

9. The method of claim 5, further comprising:

performing, in response to a failure to receiving a response from any one or more of the plurality of hazard lookaside buffer components indicating that an entry for the given pointer resides in the hazard lookaside buffer component, an operation to search for the given pointer in the hazard table;

determining that no entry for the given pointer resides in the hazard table; and

reclaiming memory identified by the given pointer.

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.

11. The system of claim 10, wherein each of the hazard lookaside buffers is shared by, and is locally accessible to, two or more processor cores on the same integrated circuit device.

12. The system of claim 10, wherein each of the hazard lookaside buffers is locally accessible to only a single one of the plurality of processor cores or only to a single thread executing on one of the plurality of processor cores.

13. The system of claim 10,

wherein, during execution of an application on the plurality of processor cores, one of processor cores is configured to issue an instruction to store information about a potentially hazardous pointer to the hazard table;

and

wherein execution of the instruction causes an entry comprising information about the potentially hazardous pointer to be written to the hazard lookaside buffer component that is locally accessible to the one of the processor cores.

14. The system of claim 13,

wherein the system further comprises a plurality of store buffer components;

wherein each of the plurality of processor cores is associated with one of the plurality of store buffer components that is locally accessible to the processor core; and

wherein execution of the instruction further causes an entry comprising information about the potentially hazardous pointer to be written to the store buffer component that is locally accessible to the one of the processor cores.

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.

16. The non-transitory, computer-readable storage medium of claim 15,

wherein the testing instruction is further configured to:

determine, in response to failing to receive an indication from any of the plurality of buffer components that a pointer to the given shared memory location or block of shared memory resides in the buffer component, whether or not a pointer to the given shared memory location or block of shared memory resides in a shared hazard table that is accessible to a plurality of threads executing on the one or more processor cores; and

determine, in response to determining that a pointer to the given shared memory location or block of shared memory resides in the shared hazard table, that the given shared memory location or block of shared memory cannot be recycled.

17. The non-transitory, computer-readable storage medium of claim 16,

wherein the testing instruction is further configured to:

determine, in response to determining that no pointer to the given shared memory location or block of shared memory resides in the shared hazard table, that the given shared memory location or block of shared memory can be recycled.

18. The non-transitory, computer-readable storage medium of claim 15,

wherein the multithreaded application comprises:

an instruction that dereferences a pointer to the given shared memory location or block of shared memory; and

an instruction that is configured to store the pointer to one of the plurality of buffer components.

19. The non-transitory, computer-readable storage medium of claim 18,

wherein the testing instruction and the instruction that is configured to store the pointer to one of the plurality of buffer components are implemented in hardware as native instructions of the instruction set architecture of the one or more processor cores.

20. The non-transitory, computer-readable storage medium of claim 15,

wherein the multithreaded application comprises an instruction that atomically performs:

dereferencing a pointer to the given shared memory location or block of shared memory; and

storing the pointer to one of the plurality of buffer components; and

wherein the instruction is implemented in hardware as a native instruction of the instruction set architecture of the one or more processor cores.