TOCTOU race in getAndSet causes data loss with shared backends

[djmetzle]

Problem

Backend::getAndSet() has a Time-of-Check-Time-of-Use (TOCTOU) race condition. It performs a non-atomic get() then set(), so concurrent callers that both observe a miss will each compute and write different values. The last writer wins, silently orphaning data written by earlier callers under the first value.

Matryoshka/library/iFixit/Matryoshka/Backend.php

Lines 132 to 145 in ab81f01

	public function getAndSet($key, callable $callback, int $expiration = 0,
	$reset = false) {
	$value = $reset ? self::MISS : $this->get($key);
	if ($value === self::MISS) {
	$value = $callback();
	if ($value !== self::MISS) {
	$this->set($key, $value, $expiration);
	}
	}
	return $value;
	}

This is benign for single-process backends (Ephemeral) but is a real bug for shared-memory backends like APCu, where multiple PHP-FPM workers share the same cache.

Slack thread with more details, and another one leading to the creation of this issue

Impact on Scope

Scope::getScopePrefix() uses getAndSet to lazily initialize a random scope prefix:

Matryoshka/library/iFixit/Matryoshka/Scope.php

Lines 24 to 35 in ab81f01

	public function getScopePrefix(bool $reset = false) {
	if ($this->scopePrefix === null || $reset) {
	$scopeValue = $this->backend->getAndSet($this->getScopeKey(),
	function() {
	return substr(md5(microtime() . $this->scopeName), 0, 16);
	}, 0, $reset);
	$this->scopePrefix = "{$scopeValue}-";
	}
	return $this->scopePrefix;
	}

The race:

Worker A: get("scope-foo") → MISS
Worker B: get("scope-foo") → MISS
Worker A: callback() → "aaa...", set("scope-foo", "aaa...")
Worker A: set("aaa...-mykey", data)
Worker B: callback() → "bbb...", set("scope-foo", "bbb...")   ← overwrites A's prefix
Worker A: get("scope-foo") → "bbb..."                         ← prefix changed
Worker A: get("bbb...-mykey") → MISS                          ← data orphaned under "aaa..."

Any worker that wrote cache entries between A's set and B's set has orphaned those entries. The scope prefix is also cached in $this->scopePrefix (an instance variable), so within a single request the stale prefix persists even after it's been overwritten in the backend — causing all subsequent reads to miss for the rest of that request.

Options

1. Use add() instead of set() in getAndSet

First writer wins. After add(), re-get() to learn the winning value.

public function getAndSet($key, callable $callback, int $expiration = 0, $reset = false) {
    $value = $reset ? self::MISS : $this->get($key);
    if ($value === self::MISS) {
        $value = $callback();
        if ($value !== self::MISS) {
            if (!$this->add($key, $value, $expiration)) {
                $value = $this->get($key);
            }
        }
    }
    return $value;
}

Pro: Simple, uses an existing primitive, correct for the scope-initialization use case.
Con: Changes semantics — today getAndSet with $reset=false still overwrites on concurrent miss. Callers relying on last-writer-wins (if any exist) would break. The $reset=true path still needs set() (intentional overwrite), so the two paths would diverge.

2. Add a separate getOrAdd method

Keep getAndSet as-is, add a new method that uses add() for atomic initialization. Update Scope to call getOrAdd.

Pro: No behavior change to existing API. Explicit opt-in.
Con: More API surface.

3. Fix only in Scope

Have Scope::getScopePrefix() call add() + get() directly instead of going through getAndSet.

Pro: Minimal change, fixes the concrete bug.
Con: Doesn't fix the general footgun — other callers of getAndSet on shared backends have the same problem.

Ambiguities

• Is getAndSet intended to be atomic? The docstring doesn't say, but the name and usage pattern (lazy cache population) strongly implies it. If it's explicitly non-atomic, that should be documented as a caveat for shared backends.
• $reset=true semantics with add(): Option 1 would need to keep using set() for the reset path (intentional overwrite). This is correct but means getAndSet uses two different write primitives depending on $reset.
• Scope::$scopePrefix instance caching: Even after fixing the backend race, the instance variable $this->scopePrefix means a Scope object caches the prefix for its lifetime. If another worker calls deleteScope(), this instance won't see the new prefix until getScopePrefix($reset=true) is called. This may be intentional (scope invalidation is eventually consistent within a request) but is worth clarifying.

CC @sctice-ifixit

[sctice-ifixit]

I think I prefer (2) Add a separate getOrAdd method as a way to minimize collateral damage. I also think getAndSet implies set semantics, and that's usually fine.

[djmetzle]

@sctice-ifixit im a bit concerned about prioritizing:

[..] a way to minimize collateral damage

Trivially, i think we want/need at least option 3, yet it:

Con: Doesn't fix the general footgun — other callers of getAndSet on shared backends have the same problem.

Any thoughts on the mentioned ambiguities?

[sctice-ifixit]

I don't understand the concerns. (3) is covered by (2), and I'm not worried about the general footgun. I think it's generally fine for the last writer to win, and getOrAdd() gives us an easy tool to reach for where we find that it matters.

[djmetzle]

Okay. I think the first commit on #43 addresses the proximal issue.

[sctice-ifixit]

Okay. I think the first commit on #43 addresses the proximal issue.

What's the objection to adding getOrAdd() and using that in Scope? It's more API surface, but it seems like a useful addition.

[djmetzle]

That's fine, option 2 it is. Ill get a PR open.

[djmetzle]

@sctice-ifixit @sterlinghirsh the more ive sat and puzzled this problem, the more "last writer wins" makes less sense to me. Effectively, for the scope prefix anyhow, that is how the Scope prefix init currently works. And that is problematic (creating many orphaned scopes, before the all readers converge).

The "worst case" scenario would be a "thundering herd" using a scope, and pumping large objects/keys into the cache fast enough to cause continuous evictions. Or if a backend starts rejecting adds/sets when it is full. Or if that backend flushes itself completely (very awkward behavior, but something similar to this is mentioned in the APCu docs).

[sterlinghirsh]

I was thinking about this too. I had the idea of a guarded key, where the atomic action is at the front of the revalidation process, before generating the value. e.g. Before generating the value for scope-key, we first ADD 'lock--scope-key'. If we get the lock we generate and set as normal. If we don't get a lock, we repeat (GET / ADD lock) every 10ms or so. Then DELETE lock--scope-key at the end.

That would mean other threads won't waste their time generating values that won't be recorded. For just a scope key I think it makes very little difference, since the work is mostly getting the system time and md5ing it. Doing that work multiple times and throwing away all but the first to complete is simpler and doesn't require a sleep/retry loop. For more expensive caches that e.g. rely on external APIs, maybe deduplicating makes more sense.

GET (MISS) -> GENERATE -> ADD (FAIL) -> GET (HIT)

GET (MISS) -> ADD LOCK (SUCCESS) -> GENERATE -> SET -> DELETE LOCK
or
GET (MISS) -> ADD LOCK (FAIL) -> REPEAT until HIT or LOCK SUCCESS

I'm still not sure whether it's broadly true that scope keys want to be guarded like this. In the case you mentioned I see your reasoning, especially because the value doesn't change frequently. When the underlying data does change frequently, last-writer-wins makes more sense to me.

[sctice-ifixit]

I think we should unblock and proceed here. I think we've minimized the scope (hah) of the change, and it's reasonably motivated (reduce orphaned cache entries). We're still probably reducing rework because although every worker will generate its own scope key, only one will win, and everyone will use the same key, which means they'll all use that same key for the other values that they generate based on top of the scope key.

[danielbeardsley]

I like option 1 as it's the simplest and feels like a complete solution. I briefly felt it was a little dangerous though now I can't really pin down a situation where it would cause problems.

• Clients using generational caching (cache key changes) won't care because the new ID is only available once the new data is in place
• Clients using getAndSet tend to do the cache delete (if ever) after they've made the modification to the underlying data

Can anyone think of a situation where Option 1 could actually cause a problem?