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 -- http://mail.python.org/mailman/listinfo/python-list
