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;
}