Thread-safety of dict

[Adam Olsen]

It seems to be a commonly held belief that basic dict operations (get,
set, del) are atomic.  However, since I know searching the hash table
is a multistep process, I thought I'd check it out for sure.

First, my assumption is that one thread is attempting to get a single
key, while other threads are getting, setting, and deleting different
keys.  Obviously you could fail anyway if they were modifying the same
key.

The avenue of attack I'm interested in is when lookdict() calls
PyObject_RichCompareBool().  If this calls out to Python code then the
GIL can/will be released.  Many builtin types won't release the GIL
though, notably str, so you're safe if they're all you use.

Assuming your dict did get modified, lookdict() then has some checks
to protect itself (which it does by restarting the search).  It checks
if mp->ma_table got changed and then it checks if ep->me_key got
changed.  So to attack it we need to: 1) have the same table address
it had before, 2) keep the key it was checking when the change
happened the same, 3) cause your target key to move to an entry it
already searched.

Getting the target key to move entries without deleting it is hard.
The only time that happens is when the dict gets resized.  It's much
easier to strip the dummies from ma_table when copying from another
table, and since it's normally going to a different size it makes sure
it always has a copy.  That means the table address will always change
(violating requirement #1), but there's two catches.

First, ma_smalltable always has the same address.  If we could get it
to resize while staying in ma_smalltable we'd have succeeded.
However, various things come together to make that impossible:
* PyDict_MINSIZE is 8
* dictresize() uses a loop that increases newsize (which defaults to
PyDict_MINSIZE) so long as newsize <= minused
* dictresize() is only called by PyDict_SetItem after a new key is
added, but since our target key must have been there the whole time,
it will be (at least) the 2nd key in the dict
* PyDict_SetItem multiplies the number of keys by 4 before passing it
to dictresize(), meaning our 2 becomes 8.  However, that's big enough
for dictresize()'s loop to go to the next-bigger size (it's just on
the limit), so we won't get ma_smalltable after all.
It's fragile and undocumented, and it's quite possible future versions
will break it, but for now this part is thread-safe.

The second catch is not thread-safe however.  dictresize() always
allocates a new table.  However, if you call dictresize() *twice*, it
could get the original table back again.  This allows us to meet the 3
conditions I outlined, letting the attack succeed.

So there you have it: if you're using a dict with custom classes (or
anything other than str) across multiple threads, and without locking
it, it's possible (though presumably extremely rare) for a lookup to
fail even through the key was there the entire time.

-- 
Adam Olsen, aka Rhamphoryncus