[3.4] [3.5] bpo-27945: Fixed various segfaults with dict. (GH-1657) (GH-1678) (#2248)

Based on patches by Duane Griffin and Tim Mitchell.
(cherry picked from commit 753bca3934a7618a4fa96e107ad1c5c18633a683).
(cherry picked from commit 2f7f533cf6fb57fcedcbc7bd454ac59fbaf2c655)

4 files changed, 143 insertions, 30 deletions

diff --git a/Lib/test/test_dict.py b/Lib/test/test_dict.py
index 80feb903a94..75509a7aa4b 100644
--- a/Lib/test/test_dict.py
+++ b/Lib/test/test_dict.py
@@ -952,6 +952,92 @@ class DictTest(unittest.TestCase):
         d = {X(): 0, 1: 1}
         self.assertRaises(RuntimeError, d.update, other)
 
+    def test_equal_operator_modifying_operand(self):
+        # test fix for seg fault reported in issue 27945 part 3.
+        class X():
+            def __del__(self):
+                dict_b.clear()
+
+            def __eq__(self, other):
+                dict_a.clear()
+                return True
+
+            def __hash__(self):
+                return 13
+
+        dict_a = {X(): 0}
+        dict_b = {X(): X()}
+        self.assertTrue(dict_a == dict_b)
+
+    def test_fromkeys_operator_modifying_dict_operand(self):
+        # test fix for seg fault reported in issue 27945 part 4a.
+        class X(int):
+            def __hash__(self):
+                return 13
+
+            def __eq__(self, other):
+                if len(d) > 1:
+                    d.clear()
+                return False
+
+        d = {}  # this is required to exist so that d can be constructed!
+        d = {X(1): 1, X(2): 2}
+        try:
+            dict.fromkeys(d)  # shouldn't crash
+        except RuntimeError:  # implementation defined
+            pass
+
+    def test_fromkeys_operator_modifying_set_operand(self):
+        # test fix for seg fault reported in issue 27945 part 4b.
+        class X(int):
+            def __hash__(self):
+                return 13
+
+            def __eq__(self, other):
+                if len(d) > 1:
+                    d.clear()
+                return False
+
+        d = {}  # this is required to exist so that d can be constructed!
+        d = {X(1), X(2)}
+        try:
+            dict.fromkeys(d)  # shouldn't crash
+        except RuntimeError:  # implementation defined
+            pass
+
+    def test_dictitems_contains_use_after_free(self):
+        class X:
+            def __eq__(self, other):
+                d.clear()
+                return NotImplemented
+
+        d = {0: set()}
+        (0, X()) in d.items()
+
+    def test_init_use_after_free(self):
+        class X:
+            def __hash__(self):
+                pair[:] = []
+                return 13
+
+        pair = [X(), 123]
+        dict([pair])
+
+    def test_oob_indexing_dictiter_iternextitem(self):
+        class X(int):
+            def __del__(self):
+                d.clear()
+
+        d = {i: X(i) for i in range(8)}
+
+        def iter_and_mutate():
+            for result in d.items():
+                if result[0] == 2:
+                    d[2] = None # free d[2] --> X(2).__del__ was called
+
+        self.assertRaises(RuntimeError, iter_and_mutate)
+
+
 from test import mapping_tests
 
 class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
diff --git a/Misc/ACKS b/Misc/ACKS
index 6824554d16e..bc188119b20 100644
--- a/Misc/ACKS
+++ b/Misc/ACKS
@@ -506,6 +506,7 @@ Hans de Graaff
 Tim Graham
 Nathaniel Gray
 Eddy De Greef
+Duane Griffin
 Grant Griffin
 Andrea Griffini
 Duncan Grisby
diff --git a/Misc/NEWS b/Misc/NEWS
index 86985a15879..88d6c70fd4a 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -1,4 +1,4 @@
-+++++++++++
++++++++++++
 Python News
 +++++++++++
 
@@ -10,6 +10,10 @@ Release date: XXXX-XX-XX
 Core and Builtins
 -----------------
 
+- bpo-27945: Fixed various segfaults with dict when input collections are
+  mutated during searching, inserting or comparing.  Based on patches by
+  Duane Griffin and Tim Mitchell.
+
 Documentation
 -------------
 
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 25619c116bf..5fc698c8854 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -805,56 +805,61 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
     PyDictKeyEntry *ep;
     assert(key != dummy);
 
+    Py_INCREF(key);
+    Py_INCREF(value);
     if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
         if (insertion_resize(mp) < 0)
-            return -1;
+            goto Fail;
     }
 
     ep = mp->ma_keys->dk_lookup(mp, key, hash, &value_addr);
-    if (ep == NULL) {
-        return -1;
-    }
+    if (ep == NULL)
+        goto Fail;
+
     assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
-    Py_INCREF(value);
     MAINTAIN_TRACKING(mp, key, value);
     old_value = *value_addr;
     if (old_value != NULL) {
         assert(ep->me_key != NULL && ep->me_key != dummy);
         *value_addr = value;
         Py_DECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
+        Py_DECREF(key);
     }
     else {
         if (ep->me_key == NULL) {
-            Py_INCREF(key);
             if (mp->ma_keys->dk_usable <= 0) {
                 /* Need to resize. */
-                if (insertion_resize(mp) < 0) {
-                    Py_DECREF(key);
-                    Py_DECREF(value);
-                    return -1;
-                }
+                if (insertion_resize(mp) < 0)
+                    goto Fail;
                 ep = find_empty_slot(mp, key, hash, &value_addr);
             }
+            mp->ma_used++;
+            *value_addr = value;
             mp->ma_keys->dk_usable--;
             assert(mp->ma_keys->dk_usable >= 0);
             ep->me_key = key;
             ep->me_hash = hash;
+            assert(ep->me_key != NULL && ep->me_key != dummy);
         }
         else {
+            mp->ma_used++;
+            *value_addr = value;
             if (ep->me_key == dummy) {
-                Py_INCREF(key);
                 ep->me_key = key;
                 ep->me_hash = hash;
                 Py_DECREF(dummy);
             } else {
                 assert(_PyDict_HasSplitTable(mp));
+                Py_DECREF(key);
             }
         }
-        mp->ma_used++;
-        *value_addr = value;
-        assert(ep->me_key != NULL && ep->me_key != dummy);
     }
     return 0;
+
+Fail:
+    Py_DECREF(value);
+    Py_DECREF(key);
+    return -1;
 }
 
 /*
@@ -1911,11 +1916,18 @@ PyDict_MergeFromSeq2(PyObject *d, PyObject *seq2, int override)
         /* Update/merge with this (key, value) pair. */
         key = PySequence_Fast_GET_ITEM(fast, 0);
         value = PySequence_Fast_GET_ITEM(fast, 1);
+        Py_INCREF(key);
+        Py_INCREF(value);
         if (override || PyDict_GetItem(d, key) == NULL) {
             int status = PyDict_SetItem(d, key, value);
-            if (status < 0)
+            if (status < 0) {
+                Py_DECREF(key);
+                Py_DECREF(value);
                 goto Fail;
+            }
         }
+        Py_DECREF(key);
+        Py_DECREF(value);
         Py_DECREF(fast);
         Py_DECREF(item);
     }
@@ -2174,14 +2186,15 @@ dict_equal(PyDictObject *a, PyDictObject *b)
                 bval = NULL;
             else
                 bval = *vaddr;
-            Py_DECREF(key);
             if (bval == NULL) {
+                Py_DECREF(key);
                 Py_DECREF(aval);
                 if (PyErr_Occurred())
                     return -1;
                 return 0;
             }
             cmp = PyObject_RichCompareBool(aval, bval, Py_EQ);
+            Py_DECREF(key);
             Py_DECREF(aval);
             if (cmp <= 0)  /* error or not equal */
                 return cmp;
@@ -3046,7 +3059,7 @@ PyTypeObject PyDictIterValue_Type = {
 
 static PyObject *dictiter_iternextitem(dictiterobject *di)
 {
-    PyObject *key, *value, *result = di->di_result;
+    PyObject *key, *value, *result;
     Py_ssize_t i, mask, offset;
     PyDictObject *d = di->di_dict;
     PyObject **value_ptr;
@@ -3082,22 +3095,27 @@ static PyObject *dictiter_iternextitem(dictiterobject *di)
     if (i > mask)
         goto fail;
 
-    if (result->ob_refcnt == 1) {
+    di->len--;
+    key = d->ma_keys->dk_entries[i].me_key;
+    value = *value_ptr;
+    Py_INCREF(key);
+    Py_INCREF(value);
+    result = di->di_result;
+    if (Py_REFCNT(result) == 1) {
+        PyObject *oldkey = PyTuple_GET_ITEM(result, 0);
+        PyObject *oldvalue = PyTuple_GET_ITEM(result, 1);
+        PyTuple_SET_ITEM(result, 0, key);  /* steals reference */
+        PyTuple_SET_ITEM(result, 1, value);  /* steals reference */
         Py_INCREF(result);
-        Py_DECREF(PyTuple_GET_ITEM(result, 0));
-        Py_DECREF(PyTuple_GET_ITEM(result, 1));
+        Py_DECREF(oldkey);
+        Py_DECREF(oldvalue);
     } else {
         result = PyTuple_New(2);
         if (result == NULL)
             return NULL;
+        PyTuple_SET_ITEM(result, 0, key);  /* steals reference */
+        PyTuple_SET_ITEM(result, 1, value);  /* steals reference */
     }
-    di->len--;
-    key = d->ma_keys->dk_entries[i].me_key;
-    value = *value_ptr;
-    Py_INCREF(key);
-    Py_INCREF(value);
-    PyTuple_SET_ITEM(result, 0, key);
-    PyTuple_SET_ITEM(result, 1, value);
     return result;
 
 fail:
@@ -3596,6 +3614,7 @@ dictitems_iter(dictviewobject *dv)
 static int
 dictitems_contains(dictviewobject *dv, PyObject *obj)
 {
+    int result;
     PyObject *key, *value, *found;
     if (dv->dv_dict == NULL)
         return 0;
@@ -3609,7 +3628,10 @@ dictitems_contains(dictviewobject *dv, PyObject *obj)
             return -1;
         return 0;
     }
-    return PyObject_RichCompareBool(value, found, Py_EQ);
+    Py_INCREF(found);
+    result = PyObject_RichCompareBool(value, found, Py_EQ);
+    Py_DECREF(found);
+    return result;
 }
 
 static PySequenceMethods dictitems_as_sequence = {