How do Hazard Pointers safely reclaim memory in concurrent data structures without using locks?

Question

I've read this article by Maged Michael describing hazard pointers a couple times, and I don't quite get the trick here.

The example is a map, that does a copy-on-write - creating a new map copy of the current one, inserting a new key-value pair and swapping out the pointer to the current map with the new one.

So each thread keeps a thread local list of map pointers it wants to discard (retire) after doing a write/swapout. At the end of the update it does a scan of the list of retired pointers finds every one that has not been doled out to a read thread by the "Acquire" method, and deletes it.

I don't see how Acquire is doing anything. How does the initial map end up on the hazard pointer list? Maybe there is a bit of code missing. Even if it were bootstrapped into the hazard pointer list, how can we be sure Acquire isn't handing something out that is just about to get retired and deleted?

I took his code and tried to get it to run. It was full of errors. I think I fixed it up well enough, but I'm not sure if I replaced his CAS functions correctly with boost::atomic.

#pragma once

#include <iostream>

#include <unordered_map>
#include <vector>
#include <atomic>


typedef std::unordered_map<std::string, std::string> StringMap;


// Hazard pointer record
class HPRecType {

    //boost::atomic<int> active_;
    std::atomic_int active_;
    // Global header of the HP list
    static std::atomic<HPRecType *> pHead_;
    // The length of the list
    static std::atomic_int listLen_;
public:
    // Can be used by the thread
    // that acquired it
    void * pHazard_;
    HPRecType * pNext_;
    static HPRecType * Head() {
        return pHead_;
    }

    // Acquires one hazard pointer
    static HPRecType * Acquire() {
        int one = 1;
        // Try to reuse a retired HP record
        HPRecType * p = pHead_;
        for (; p; p = p->pNext_) {
            if (p->active_ || !p->active_.compare_exchange_strong(one, 0, std::memory_order_acquire))
                continue;
            // Got one!
            return p;
        }

        // Increment the list length
        int oldLen;
        do {
            oldLen = listLen_;

        } while (!listLen_.compare_exchange_strong(oldLen, oldLen +1, std::memory_order_acquire));

        // Allocate a new one
        p = new HPRecType;
        p->active_ = 1;
        p->pHazard_ = 0;
        // Push it to the front
        HPRecType * old;
        do {
            old = pHead_;
            p->pNext_ = old;
        } while (!pHead_.compare_exchange_strong(old, p, std::memory_order_acquire));
        return p;
    }

    // Releases a hazard pointer
    static void Release(HPRecType* p) {
        p->pHazard_ = 0;
        p->active_ = 0;
    }
};

// Per-thread private variable
//static boost::thread_specific_ptr<std::vector<StringMap*>> rlist;
static std::vector<StringMap*> *rlist;


class HazardPointerMap {
    std::atomic<StringMap *> pMap_;


private:
    static void Retire(StringMap * pOld) {
        // put it in the retired list
        rlist->push_back(pOld);
        if (rlist->size() >= 10) {
            Scan(HPRecType::Head());
        }
    }


    static void Scan(HPRecType * head) {
        // Stage 1: Scan hazard pointers list
        // collecting all non-null ptrs
        std::vector<void*> hp;
        while (head) {
            void * p = head->pHazard_;
            if (p) hp.push_back(p);
            head = head->pNext_;
        }
        // Stage 2: sort the hazard pointers
        sort(hp.begin(), hp.end(), std::less<void*>());
        // Stage 3: Search for'em!
        std::vector<StringMap *>::iterator i = rlist->begin();
        while (i != rlist->end()) {
            if (!binary_search(hp.begin(), hp.end(),  *i)) {
                // Aha!
                delete *i;
                i = rlist->erase(i);

                if (&*i != &rlist->back()) {
                    *i = rlist->back();
                }
                rlist->pop_back();
            } else {
                ++i;
            }
        }
    }

public:
    void Update(std::string&k, std::string&v){
        StringMap * pNew = 0;
        StringMap * pOld;
        do {
            pOld = pMap_;
            if (pNew) delete pNew;
            pNew = new StringMap(*pOld);
            (*pNew)[k] = v;
        } while (!pMap_.compare_exchange_strong(pOld, pNew, std::memory_order_acq_rel));
        Retire(pOld);
    }

    std::string Lookup(const std::string &k){
        HPRecType * pRec = HPRecType::Acquire();
        StringMap *ptr;
        do {
            ptr = pMap_;
            pRec->pHazard_ = ptr;
        } while (pMap_ != ptr);
        // Save Willy
        std::string result = ptr->at(k);
        // pRec can be released now
        // because it's not used anymore
        HPRecType::Release(pRec);
        return result;
    }

};

Answer 1

I don't see how Acquire is doing anything. How does the initial map end up on the hazard pointer list? Maybe there is a bit of code missing.

Acquire() does NOT bind any map to the hazard pointer list. It just gets a slot inside the list. A map is bound to pHazard of that slot in Lookup() after Acquire(). Pay attention to line pRec->pHazard_ = ptr; that follows.

V Lookup(const K&k){
   HPRecType * pRec = HPRecType::Acquire();
   Map<K, V> * ptr;
   do {
      ptr = pMap_;
      pRec->pHazard_ = ptr;    //<---- Bind the map to slot here
   } while (pMap_ != ptr);
   // Save Willy
   V result = (*ptr)[k];
   // pRec can be released now
   // because it's not used anymore
   HPRecType::Release(pRec);
   return result;
}

Even if it were bootstrapped into the hazard pointer list, how can we be sure Acquire isn't handing something out that is just about to get retired and deleted?

Don't need to be sure. From writer's point of view, after Acquire(), nothing effectively happens. There is no reader on pMap_ because _pHazard is not set yet by reader. Remember that writer checks _pHazard only to determine if there is any reader. So it's free for writer to think that "oh, there is no reader on this map" and go on to delete that map, as long as reader's pRec->pHazard_ = ptr; is not executed. Even if writer deletes the old map between line 2 and 3 that follows, the loop will guarantee that reader will not read from stale (deleted) map.

Line 1:    do {
Line 2:       ptr = pMap_;
Line 3:       pRec->pHazard_ = ptr;
Line 4:    } while (pMap_ != ptr);

Another thing worth mentioning is that active_ is only used among readers so that no more than one reader can get the same slot in singly linked list (the shared hazard pointer list). That may confuse you because pHazard is used in addition to it, both providing some kind of protection (among readers, or readers and writers). IMO, active_ can be removed and we can just check whether pHazard is NULL. The only problem is that the latter is a pointer which may be 64-bit, and there may not be a 64-bit CAS primitive on all platforms. That's why the author tries to avoid.