[Python-checkins] cpython (2.7): Issues #24099, #24100, and #24101: Fix free-after-use bug in heapq.

Sat May 2 19:27:04 CEST 2015

https://hg.python.org/cpython/rev/d356e68de236
changeset: 95841:d356e68de236
branch: 2.7
parent: 95834:5ce760e2cc59
user: Raymond Hettinger <python at rcn.com>
date: Sat May 02 10:26:57 2015 -0700
summary:
 Issues #24099, #24100, and #24101: Fix free-after-use bug in heapq.
files:
 Misc/NEWS | 3 +
 Modules/_heapqmodule.c | 73 +++++++++--------------------
 2 files changed, 25 insertions(+), 51 deletions(-)

diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -23,6 +23,9 @@
 
 - Issue #23008: Fixed resolving attributes with boolean value is False in pydoc.
 
+- Issues #24099, #24100, and #24101: Fix free-after-use bug in heapq's siftup
+ and siftdown functions.
+
 - Issue #23842: os.major(), os.minor() and os.makedev() now support ints again.
 
 - Issue #23811: Add missing newline to the PyCompileError error message.
diff --git a/Modules/_heapqmodule.c b/Modules/_heapqmodule.c
--- a/Modules/_heapqmodule.c
+++ b/Modules/_heapqmodule.c
@@ -35,10 +35,9 @@
 static int
 _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
 {
- PyObject *newitem, *parent, *olditem;
+ PyObject *newitem, *parent;
+ Py_ssize_t parentpos, size;
 int cmp;
- Py_ssize_t parentpos;
- Py_ssize_t size;
 
 assert(PyList_Check(heap));
 size = PyList_GET_SIZE(heap);
@@ -47,39 +46,28 @@
 return -1;
 }
 
- newitem = PyList_GET_ITEM(heap, pos);
- Py_INCREF(newitem);
 /* Follow the path to the root, moving parents down until finding
 a place newitem fits. */
- while (pos > startpos){
+ newitem = PyList_GET_ITEM(heap, pos);
+ while (pos > startpos) {
 parentpos = (pos - 1) >> 1;
 parent = PyList_GET_ITEM(heap, parentpos);
 cmp = cmp_lt(newitem, parent);
- if (cmp == -1) {
- Py_DECREF(newitem);
+ if (cmp == -1)
 return -1;
- }
 if (size != PyList_GET_SIZE(heap)) {
- Py_DECREF(newitem);
 PyErr_SetString(PyExc_RuntimeError,
 "list changed size during iteration");
 return -1;
 }
 if (cmp == 0)
 break;
- Py_INCREF(parent);
- olditem = PyList_GET_ITEM(heap, pos);
+ parent = PyList_GET_ITEM(heap, parentpos);
+ newitem = PyList_GET_ITEM(heap, pos);
+ PyList_SET_ITEM(heap, parentpos, newitem);
 PyList_SET_ITEM(heap, pos, parent);
- Py_DECREF(olditem);
 pos = parentpos;
- if (size != PyList_GET_SIZE(heap)) {
- PyErr_SetString(PyExc_RuntimeError,
- "list changed size during iteration");
- return -1;
- }
 }
- Py_DECREF(PyList_GET_ITEM(heap, pos));
- PyList_SET_ITEM(heap, pos, newitem);
 return 0;
 }
 
@@ -87,20 +75,16 @@
 _siftup(PyListObject *heap, Py_ssize_t pos)
 {
 Py_ssize_t startpos, endpos, childpos, rightpos, limit;
+ PyObject *tmp1, *tmp2;
 int cmp;
- PyObject *newitem, *tmp, *olditem;
- Py_ssize_t size;
 
 assert(PyList_Check(heap));
- size = PyList_GET_SIZE(heap);
- endpos = size;
+ endpos = PyList_GET_SIZE(heap);
 startpos = pos;
 if (pos >= endpos) {
 PyErr_SetString(PyExc_IndexError, "index out of range");
 return -1;
 }
- newitem = PyList_GET_ITEM(heap, pos);
- Py_INCREF(newitem);
 
 /* Bubble up the smaller child until hitting a leaf. */
 limit = endpos / 2; /* smallest pos that has no child */
@@ -112,37 +96,24 @@
 cmp = cmp_lt(
 PyList_GET_ITEM(heap, childpos),
 PyList_GET_ITEM(heap, rightpos));
- if (cmp == -1) {
- Py_DECREF(newitem);
+ if (cmp == -1)
+ return -1;
+ if (cmp == 0)
+ childpos = rightpos;
+ if (endpos != PyList_GET_SIZE(heap)) {
+ PyErr_SetString(PyExc_RuntimeError,
+ "list changed size during iteration");
 return -1;
 }
- if (cmp == 0)
- childpos = rightpos;
- }
- if (size != PyList_GET_SIZE(heap)) {
- Py_DECREF(newitem);
- PyErr_SetString(PyExc_RuntimeError,
- "list changed size during iteration");
- return -1;
 }
 /* Move the smaller child up. */
- tmp = PyList_GET_ITEM(heap, childpos);
- Py_INCREF(tmp);
- olditem = PyList_GET_ITEM(heap, pos);
- PyList_SET_ITEM(heap, pos, tmp);
- Py_DECREF(olditem);
+ tmp1 = PyList_GET_ITEM(heap, childpos);
+ tmp2 = PyList_GET_ITEM(heap, pos);
+ PyList_SET_ITEM(heap, childpos, tmp2);
+ PyList_SET_ITEM(heap, pos, tmp1);
 pos = childpos;
- if (size != PyList_GET_SIZE(heap)) {
- PyErr_SetString(PyExc_RuntimeError,
- "list changed size during iteration");
- return -1;
- }
 }
-
- /* The leaf at pos is empty now. Put newitem there, and bubble
- it up to its final resting place (by sifting its parents down). */
- Py_DECREF(PyList_GET_ITEM(heap, pos));
- PyList_SET_ITEM(heap, pos, newitem);
+ /* Bubble it up to its final resting place (by sifting its parents down). */
 return _siftdown(heap, startpos, pos);
 }
 
-- 
Repository URL: https://hg.python.org/cpython
