Implementing a shared array cache without locking

Question

I am trying to implement a shared cache for arrays. It must support two operations: set(owner, idx, value) and fetch(owner, idx) where idx is the index into the array and owner is an opaque handle to an owning object -- fetch(owner_1, idx) should return the value stored by set(owner_1, idx) only if the owner argument matches. The cache must be thread - safe but I do not want to rely on locking, i.e. mutexes. Failure in looking up cached values is fine - it is OK and expected that other threads will overwrite existing values in the shared cache, in which case fetch should just fail.

So the fetch operation has to read the cache slot's owner field to check against its argument, and if it matches return the cache slot's value field. The problem is, without locks, another thread could overwrite one of these fields during that operation. This approach tries to get around that by assigning a version field to each cache slot. It only increases. The fetch operation reads the version (atomically) at the start of the operation and at the end; if these are not the same, something changed during the read and the result is invalid, even if the owner field apparently matched.

The code below ensures that version is always incremented before value is updated, thus preventing fetch from returning a value from a different owner. (The functions g_atomic_... are provided by glib.) It "seems to work" - but can it be proven correct or incorrect?

struct _cache_slot
{
  void*        owner;
  gint         version;
  gdouble      value;
};

struct _cache_slot cache[SIZE];

int
point_cache_fetch(void *owner, gdouble* ret, gsize idx)
{
   struct _cache_slot *slot = &cache[idx];

   gint version_start  = g_atomic_int_get(&(slot->version));
   void* slot_owner    = g_atomic_pointer_get(&(slot->owner));
   gdouble value       = slot->value;
   gint version_finish = g_atomic_int_get(&(slot->version));

   if ((version_start == version_finish) && (slot_owner == owner))
   {
     *ret = value;
     return 1;
   }
   else
   {
     return 0;
   }
}

void
point_cache_store(void *owner, gsize idx, gdouble value)
{
   struct _cache_slot *slot = &cache[idx];

   g_atomic_pointer_set(&(slot->owner), NULL);
   slot->version++;
   g_atomic_pointer_set(&(slot->owner), owner);
   slot->value = value;
}

Answer 1

I do not believe this can be made thread-safe without a lock. Your solution fails for example when there are simultaneously two or more writers and one or more readers. More generally, race conditions are very difficult to foresee and you (or I) cannot predict or imagine them all. Why are you avoiding locks?

Answer 2

It's not clear from you're post whether owner is unique for each thread or if two threads can call the functions with the same value of owner. If two threads can call the functions with the same value for owner, your code is incorrect.

If one thread is executing point_catch_store() and another thread calls point_catch_fetch() while the first thread is between these two lines, you'll get the old value (from the previous owner of the entry), not the new one:

g_atomic_pointer_set(&(slot->owner), owner);
slot->value = value;

As far as I can tell, swapping those two lines would solve that problem.