[Python-checkins] bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059) (GH-9199)

[Victor Stinner]

https://github.com/python/cpython/commit/a9274f7b3f69519f0746c50f85a68abd926ebe7b
commit: a9274f7b3f69519f0746c50f85a68abd926ebe7b
branch: 3.6
author: Miss Islington (bot) <31488909+miss-islington at users.noreply.github.com>
committer: Victor Stinner <vstinner at redhat.com>
date: 2018-10-20T00:48:46+02:00
summary:

bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059) (GH-9199)

Address a C undefined behavior signed integer overflow issue in set object table resizing.  Our -fwrapv compiler flag and practical reasons why sets are unlikely to get this large should mean this was never an issue but it was incorrect code that generates code analysis warnings.

(cherry picked from commit 6c7d67ce83a62b5f0fe5c53a6df602827451bf7f)

Co-authored-by: Sergey Fedoseev <fedoseev.sergey at gmail.com>

files:
A Misc/NEWS.d/next/Core and Builtins/2018-09-11-15-19-37.bpo-1621.7o19yG.rst
M Objects/setobject.c

diff --git a/Misc/NEWS.d/next/Core and Builtins/2018-09-11-15-19-37.bpo-1621.7o19yG.rst b/Misc/NEWS.d/next/Core and Builtins/2018-09-11-15-19-37.bpo-1621.7o19yG.rst
new file mode 100644
index 000000000000..4047ff3bfe86
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2018-09-11-15-19-37.bpo-1621.7o19yG.rst	
@@ -0,0 +1,2 @@
+Do not assume signed integer overflow behavior (C undefined behavior) when
+performing set hash table resizing.
diff --git a/Objects/setobject.c b/Objects/setobject.c
index 96485f83ecb6..27836c0fb1ea 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -294,7 +294,6 @@ actually be smaller than the old one.
 static int
 set_table_resize(PySetObject *so, Py_ssize_t minused)
 {
-    Py_ssize_t newsize;
     setentry *oldtable, *newtable, *entry;
     Py_ssize_t oldfill = so->fill;
     Py_ssize_t oldused = so->used;
@@ -307,13 +306,9 @@ set_table_resize(PySetObject *so, Py_ssize_t minused)
 
     /* Find the smallest table size > minused. */
     /* XXX speed-up with intrinsics */
-    for (newsize = PySet_MINSIZE;
-         newsize <= minused && newsize > 0;
-         newsize <<= 1)
-        ;
-    if (newsize <= 0) {
-        PyErr_NoMemory();
-        return -1;
+    size_t newsize = PySet_MINSIZE;
+    while (newsize <= (size_t)minused) {
+        newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
     }
 
     /* Get space for a new table. */