[Python-Dev] another dict crasher

Tim Peters tim.one@home.com
Fri, 1 Jun 2001 16:36:21 -0400

I suspect there are many ways to get the dict code to blow up, and always
have been.  I picked on dict compare a month or so ago mostly because nobody
cares how fast that runs except in the == and != cases.  Others are a real
bitch; for example, the fundamental lookdict function caches

    dictentry *ep0 = mp->ma_table;

at the start as if it were invariant -- but very unlikely sequences of
collisions with identical hash codes combined with mutating comparisons can
turn that into a bogus pointer.

List objects used to have similar vulnerabilities during sorting (where
comparison is the *norm*, not a one-in-a-billion freak occurrence), and no
amount of slow-the-code paranoia sufficed to plug all conceivable holes.  In
the end we invented an internal "immutable list type", and replace the list
object's type pointer for the duration of the sort (you can still try to
mutate a list during a sort, but all the mutating list methods are
redirected to raise an exception when you do).

The dict code has even more holes and in more places, but they're generally
much harder to provoke, so they've gone unnoticed for 10 years.  All in all,
seemed like a good tradeoff to me <wink>.