473,372 Members | 1,084 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,372 software developers and data experts.

Thread-safety of dict

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
Jun 1 '07 #1
6 9675
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
Jun 1 '07 #2
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
Jun 1 '07 #3
"Adam Olsen" <rh****@gmail.comwrote:
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.
Jun 1 '07 #4
On 6/1/07, "Martin v. Lwis" <ma****@v.loewis.dewrote:
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.
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.
;)

--
Adam Olsen, aka Rhamphoryncus
Jun 1 '07 #5
On Jun 1, 3:51 am, Duncan Booth <duncan.bo...@invalid.invalidwrote:
"Adam Olsen" <rha...@gmail.comwrote:
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 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).

--
Adam Olsen, aka Rhamphoryncus

Jun 1 '07 #6
On May 31, 9:12 pm, "Adam Olsen" <rha...@gmail.comwrote:
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

Jun 2 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

14
by: adeger | last post by:
Having trouble with my first forays into threads. Basically, the threads don't seem to be working in parallel (or you might say are blocking). I've boiled my problems to the following short code...
4
by: Gilles Leblanc | last post by:
Hi I have started a small project with PyOpenGL. I am wondering what are the options for a GUI. So far I checked PyUI but it has some problems with 3d rendering outside the Windows platform. I...
7
by: Ivan | last post by:
Hi I have following problem: I'm creating two threads who are performing some tasks. When one thread finished I would like to restart her again (e.g. new job). Following example demonstrates...
4
by: Matthew Groch | last post by:
Hi all, I've got a server that handles a relatively high number of concurrent transactions (on the magnitude of 1000's per second). Client applications establish socket connections with the...
5
by: Razzie | last post by:
Hi all, A question from someone on a website got me thinking about this, and I wondered if anyone could explain this. A System.Threading.Timer object is garbage collected if it has no...
16
by: droopytoon | last post by:
Hi, I start a new thread (previous one was "thread timing") because I have isolated my problem. It has nothing to do with calling unmanaged C++ code (I removed it in a test application). I...
9
by: mareal | last post by:
I have noticed how the thread I created just stops running. I have added several exceptions to the thread System.Threading.SynchronizationLockException System.Threading.ThreadAbortException...
13
by: Bob Day | last post by:
Using vs2003, vb.net I start a thread, giving it a name before start. Code snippet: 'give each thread a unique name (for later identification) Trunk_Thread.Name = "Trunk_0_Thread" ' allow...
7
by: Charles Law | last post by:
My first thought was to call WorkerThread.Suspend but the help cautions against this (for good reason) because the caller has no control over where the thread actually stops, and it might have...
3
by: John Nagle | last post by:
There's no way to set thread priorities within Python, is there? We have some threads that go compute-bound, and would like to reduce their priority slightly so the other operations, like...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.