Hardware extensions for memory reclamation for concurrent data structures

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.