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.

 

[=?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=]

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.

That could be fixed by adding a generation counter to the dictionary,
right? Then an adversary would have to arrange for the generation
counter to roll over for lookdict to not notice that the
dictionary was modified.

Regards,
Martin

 

[=?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=]

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.

That could be fixed by adding a generation counter to the dictionary,
right? Then an adversary would have to arrange for the generation
counter to roll over for lookdict to not notice that the
dictionary was modified.

Regards,
Martin

 

[Duncan Booth]

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.

Nice work.

It would be an interesting exercise to demonstrate this in practice, and I
think it should be possible without resorting to threads (by putting
something to simulate what the other thread would do into the __cmp__
method).

I don't understand your reasoning which says it cannot stay in
ma_smalltable: PyDict_SetItem only calls dictresize when at least 2/3 of
the slots are filled. You can have 5 items in the small (8 slot) table and
the dictionary will resize to 32 slots on adding the 6th,the next resize
comes when you add the 22nd item.

 

[Adam Olsen]

That could be fixed by adding a generation counter to the dictionary,
right? Then an adversary would have to arrange for the generation
counter to roll over for lookdict to not notice that the
dictionary was modified.

Yup. Although it'd still be technically possible to roll over the
counter, it's much easier to say how insanely unlikely it is.
Incidentally, only resizing should increment the counter; it's not
necessary to restart lookups for other accesses (and would harm
performance, as well as producing infinite loops in __cmp__ methods
that read from their containing dict.)

It occurs to me now that getting the original ma_table back could do
worse than just a failed lookup: if the size is smaller than before it
would lead to memory corruption and segfaults. That could be fixed
with with a before/after check of ma_mask.

And if you're *really* feeling paranoid you could add reference
counting to ma_table. I doubt anybody cares quite that much though.

 

[Rhamphoryncus]

Nice work.

It would be an interesting exercise to demonstrate this in practice, and I
think it should be possible without resorting to threads (by putting
something to simulate what the other thread would do into the __cmp__
method).

I had attempted to do so, but I lost interest when I realized I'd have
to manipulate the memory allocator at the same time.

I don't understand your reasoning which says it cannot stay in
ma_smalltable: PyDict_SetItem only calls dictresize when at least 2/3 of
the slots are filled. You can have 5 items in the small (8 slot) table and
the dictionary will resize to 32 slots on adding the 6th,the next resize
comes when you add the 22nd item.

What you're missing is that a slot can be in any of 3 states:
1) Active. A key is here. If the current slot doesn't match
lookdict() will try the next one.
2) Dummy. Used to be a key here, but now it's gone. lookdict() will
try the next one.
3) NULL. Never was a key here. lookdict() will stop.

lookdict() needs the NULL slots to stop searching. As keys are added
and removed from the table it will get filled with dummy slots, so
when the total number of active+dummy slots exceeds 2/3rds it will
trigger a resize (to the same size or even a smaller size!) so as to
clear out all the dummy slots (letting lookups finish sooner).

 

[Raymond Hettinger]

It seems to be a commonly held belief that basic dict operations (get,
set, del) are atomic.

They are atomic so long as the key does not have a custom __hash__,
__eq__, or __cmp__ method which can trigger arbitrary Python code.
With strings, ints, floats, or tuples of those, the get/set/del step
is atomic (i.e. executed in a single Python opcode).

from dis import dis
dis(compile('del d[k]', 'example', 'exec'))

1 0 LOAD_NAME 0 (d)
3 LOAD_NAME 1 (k)
6 DELETE_SUBSCR
7 LOAD_CONST 0 (None)
10 RETURN_VALUE

The DELETE_SUBSCR step completes the whole action in a single opcode
(unless the object has a custom hash or equality test). Of course,
there is a possibility of a thread switch between the LOAD_NAME and
the DELETE_SUBSCR (in which case another thread could have added or
removed that key).


Raymond