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

• Joey Adams: Shouldn't slot be declared as a pointer? As in, struct *slot = &cache[idx]; . That's how you're accessing it.
• Joey Adams: Err, struct _cache_slot *slot = &cache[idx].
• Joey Adams: Also, is it possible for two different threads to call store with the same owner object?
• gcbenison: @joey about slot not being a pointer - you're right; I am paraphrasing this code from elsewhere and made that mistake. Edited to fix
• Loki Astari: This is an error: struct slot = cache[idx]; Here you are making a copy of the cache content. Then you modify this copy in the function (you never touch the cache). Thus the cache is never updated. This means the code is non functional (do you actually have unit tests?).

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?

• William Morris: Looking at it again, note that version++ has three parts (read, modify, write) and so can be interrupted. One can imagine a scenario where version_finish < version_start. But maybe that is unrealistic in terms of the application logic.
• William Morris: Eg. thread A starts a store(), reads version 1 but is interrupted before setting 2; threads B and C store() setting version to 2 and then 3; thread D starts to fetch, reads version 3 and then is interrupted; threads E and F store() setting version to 4,5; thread A resumes and sets version to 2. Thread C resumes reads version 2. This is a convoluted example of course :-)

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.

• gcbenison: The reason for setting owner prior to setting value was to ensure that version is incremented before value is updated (because g_atomic_pointer_set() acts as a memory barrier). So I'm not sure if this change wouldn't introduce a new problem...
• stderr: @gcbenison: You're right. There still a problem after swapping those two lines. I had an idea for a solution, but while writing the solution I noticed that I had basically re-invented locking. :-/