Some comments below, mostly about formatting.

I'd prefer we focus the thread-safety changes on dict and not OrderedDict for now. OrderedDict is both a bit of a mess in general and harder to do locking in a way that doesn't lead to re-acquiring the lock for the same object.

This will help make it easier to assert in the dictionary API that we have the proper locking in place

I'm a bit skeptical about these sorts of asserts in dict (or list). I expect there to be at least a few places internally where we want to call the unlocked APIs because we know it's safe for other reasons.

For example, the LRU caches uses _PyDict_SetItem_KnownHash, but we will want to do the locking on the lru_cache_object and not the internal dict, and can use the unlocked ("lock_held") variant.

Really these changes are from a focus on dict thread safety! It's kind of hard to know that our implementation is actually thread safe without being able to make assertions on where things are being used. And getting a clean run isn't possible without fixing up some of these oddball cases (and I'm only trying to do the bare minimum here, hence why we do things like call back into locking APIs with the lock already held).

I think these asserts do have value - not only are they exposing these subtle external usages they also exposed the issue with dict_traverse being called from get_referrents. They also put a really bright line on the usage of APIs borrowing references, but for testing purposes I just made those lock and be broken (and obviously those are much more discoverable manually).

We don't necessarily need to land asserts but I think it'll eliminate a lot of hard to track down bugs by at least having done a pass with them in (which these 2 PRs + your get_referrants PR basically completes modulo the known borrowing APIs). It'd be nice if we could land them to prevent hard to track down bugs in the future though.

I think we could always make some accommodations for callers which need to call lock free (which might even be locking in a debug build, but that's probably less than ideal) but it'd be nice if the default behavior when you're trying to be smart is that you get a loud failure that shows you thought about it rather than just accidentally have done the wrong thing :)