LRU with shared_ptr in multi-threaded environment

I run into a corner case while using a shared_ptr based "database" that doubles as an LRU.

Since C++17, the shared_ptr::use_count is imprecise, so I have trouble deciding on which elements can be safely removed from the LRU.

I cannot remove still-in-use elements, as that would break contracts in the rest of the code.

As far as I understand it locking a mutex is not enough, since only a mutex unlock will force a memory barrier. I could still read an outdated value even when holding the lock.

I could of course slap a memory barier after I lock a mutex inside the LRU, but I'm a bit worried about the performance impact.

Here is an outline of how the lru works:

template <k,v>
class DB{
  shared_ptr<V> emplace(k, args...) {
    lock guard();
    remove_elements_if_needed();
    insert_if_new(k, args...);
    refresh_lru(k);
    return ptr;
  }
};

Solution

General solution I'd propose is while under a lock, identify a candidate element to remove. Then attempt to remove it by doing this:

Create a weak_ptr instance to an element you think might be a good candidate to remove
Delete the item from the list as you normally would
Try to restore the item as a shared_ptr from the weak_ptr
If you promote the weak_ptr back to shared_ptr and it's still null, then you are done.
If the new shared_ptr is not null, then you know someone still has a reference to the item. Put the item back into your data structure exactly as you found it.

Something like this. Since I don't have your code yet, I'm winging it wrt to your implementation. But I'm guessing you have a collection of "nodes". Each node has a member that is the shared_ptr instance that you hand back to callers.

 bool remove_unused_element() {

      bool removed = false;

      for (node& n : lru) {
          weak_ptr<X> wp = n.item;
          n.item.reset();
          shared_ptr<X> sp = wp.lock();
          if (sp != nullptr){
              n.item = sp ; // restore this node, someone is still using it
          }
          else {
              lru.erase(n);
              removed = true;
              break;
          }
     }
     return removed;
}             
          
          
void remove_elements_if_needed() {
    bool result = true;
    while ((lru.size() > max_lru_size) && result) {
         result = remove_unused_element();
    }
}

All of the above code assumes you have acquired the mutex as you show in your pseudo code.