I think we want "release", although I'm not 100% sure. It's possible that the synchronization from the incref is sufficient even with relaxes stores

Maybe I've failed to capture exactly what you're concerned about, but I think the synchronization around keys and values provides what we need: https://gist.github.com/DinoV/fd83e80e5eb37ffa197dadd9791cca6e because reads to ma_keys and ma_values are fully sequential, and writes to them are done with release stores.

My concern is that the initialization of the fields within key or value may not be fully visible. I think it's probably okay, but only because our mutex implementation uses stronger orderings than conventional locks.

For example, let's say value is a PyLongObject:

In pseudo-code:

PyLongObject *value = ...;
value->ob_digit = 123456;  // (1) non-atomic store that I'm concerned about
...
Py_BEGIN_CRITICAL_SECTION(dict);  // (2) lock dict
PyDictKeyEntry *entries = DK_ENTRIES(dict->ma_keys);
entries[...]->me_value = value; // (3) relaxed store
Py_END_CRITICAL_SECTION();

My concern was that (1) would be reordered past (3). I think it's okay because the mutexes used by critical sections use sequential consistency for both locking and unlocking, so (1) can't be reordered past (2). The "conventional" ordering is "acquire" for lock and "release" for unlock, which would not be sufficient.

And I think we'll be forced to lock on both threads because _Py_TryXGetRef is going to fail on the value that's not yet shared across threads and we'll be forced into the locking code path.

After thinking about this a bit more, I think (3) really needs to be at least "release".

First, contrary to what I wrote above, the mutex locking isn't sufficient because a seq-cst operation on a variable is weaker than a seq-cst fence -- it doesn't ensure that the write in (1) is visible in this case.

I don't think we can rely on the _Py_TryXGetRef failing either. The object might have a non-zero shared refcount for a number of reasons.

Here's a simplified model. If you change the relevant "memory_order_release" to "memory_order_relaxed" it will fail:
https://github.com/colesbury/c11-model-checker/blob/cpython-models/test/dict_value.c