[Python-Dev] A cute new way to get an infinite loop

[Tim Peters]

[Armin Rigo, on
 >>> x = []
 >>> x.extend(-y for y in x)
 Segmentation fault
]

> The segfault is immediate.  And the example is different, as Ronald pointed
> out: the list 'x' is empty!

Good eye!  I overlooked that too.

> Uh oh.  We have a real bug in listextend(): the list being extended is in a
> semi-invalid state when it's calling tp_iternext() on the 2nd iterable.  This
> might call back Python code, which can inspect the list.  The above example
> does just that.  Crash.
>
> "Semi-invalid" means that all invariants are respected but the final items in
> the list are NULL.  Reading them crashes.  And I'm not even talking about the
> nasty things you can do if you modify the list while it's being extended :-)

Yup.  The code doesn't check for C int overflow of m+n either.

> The safest solution would be to use a regular app1() to add each item as the
> iterable produce them instead of optimizing this case.  I'm not sure we need
> the high-flying optimization of listextend() in this case (this is the case
> where the iterable we extend the list with is neither a list nor a tuple).  I
> believe that the speed of app1() would be acceptable, given the fixed bug and
> the overall decrease of code complexity (though that should be measured).

I think it's easy to fix.  "The usual rule" applies:  you can't assume
anything about a mutable object after potentially calling back into
Python.  So trying to save info in "i", "m", or "n" across loop
iterations can't work, and the list can never be left in an insane
state ("semi" or not) at any time user code may get invoked.  But
since we have both "num allocated" and "num used" members in the list
struct now, it's easy to use those instead of trying to carry info in
locals.

Patch attached.  Anyone object?  Of course in the example at the start
of this msg, it leaves x empty.
-------------- next part --------------
Index: Objects/listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.223
diff -c -u -r2.223 listobject.c
--- Objects/listobject.c	12 Sep 2004 19:53:07 -0000	2.223
+++ Objects/listobject.c	25 Sep 2004 16:14:33 -0000
@@ -769,12 +769,20 @@
 	}
 	m = self->ob_size;
 	mn = m + n;
-	if (list_resize(self, mn) == -1)
-		goto error;
-	memset(&(self->ob_item[m]), 0, sizeof(*self->ob_item) * n);
+	if (mn >= m) {
+		/* Make room. */
+		if (list_resize(self, mn) == -1)
+			goto error;
+		/* Make the list sane again. */
+		self->ob_size = m;
+	}
+	/* Else m + n overflowed; on the chance that n lied, and there really
+	 * is enough room, ignore it.  If n was telling the truth, we'll
+	 * eventually run out of memory during the loop.
+	 */
 
 	/* Run iterator to exhaustion. */
-	for (i = m; ; i++) {
+	for (;;) {
 		PyObject *item = iternext(it);
 		if (item == NULL) {
 			if (PyErr_Occurred()) {
@@ -785,8 +793,11 @@
 			}
 			break;
 		}
-		if (i < mn)
-			PyList_SET_ITEM(self, i, item); /* steals ref */
+		if (self->ob_size < self->allocated) {
+			/* steals ref */
+			PyList_SET_ITEM(self, self->ob_size, item);
+			++self->ob_size;
+		}
 		else {
 			int status = app1(self, item);
 			Py_DECREF(item);  /* append creates a new ref */
@@ -796,10 +807,9 @@
 	}
 
 	/* Cut back result list if initial guess was too large. */
-	if (i < mn && self != NULL) {
-		if (list_ass_slice(self, i, mn, (PyObject *)NULL) != 0)
-			goto error;
-	}
+	if (self->ob_size < self->allocated)
+		list_resize(self, self->ob_size);  /* shrinking can't fail */
+
 	Py_DECREF(it);
 	Py_RETURN_NONE;