Understanding memory reclamation in this lock-free structure

1

I found a very nice paper on intro to lock-free programming: https://erdani.org/publications/cuj-2004-10.pdf

In this paper, just before reaching to conclusions, in the code snippet forUpdate; we never clean up the counter, so this isn't a correct solution to the memory reclamation problem, right?

void Update(const K &k, const V &v)
{
    Data old;
    Data fresh;
    old.second = 1;
    fresh.first = 0;
    fresh.second = 1;
    Map<K, V> *last = 0;
    do
    {
        old.first = data_.first;
        if (last != old.first)
        {
            delete fresh.first;
            fresh.first =
                new Map<K, V>(old.first);
            fresh.first->insert(make_pair(k, v));
            last = old.first;
        }
    } while (!CAS(&data_, old, fresh));
    delete old.first; // whew
}
2

From the paper it seems perhaps it's cleaned by Lookup, this part stands out:

Neat, huh? Not that much. Update is now locked:
it will need to wait for all Lookups to finish before it has a chance to update the map. Gone
with the wind are all the nice properties of lockfree data structures. In particular, it is very easy
to starve Update to death: just look up the map
at a high-enough rate—and the reference count will
never go down to one.

In Lookup I do see:

do {
  old = data_;
  fresh = old;
  --fresh.second;
 }

Seems --fresh.second; does it but honestly I'm not 100% sure but if fresh.second is the counter in transit and data_.second is the counter then stands to reason imo.

3

hey, thanks a lot for taking a look! By "we never clean up the counter", I meant to ask if we ever destroy the counter (data_.second) or it's a leak?

4

It's in the map so I would think no for the leak but instead you need to have logic at some point to destroy the map which doesn't appear to be in the paper that I saw. If that makes sense (might not and that's ok)?