[issue13496] bisect module: Overflow at index computation
Roundup Robot devn...@psf.upfronthosting.co.za added the comment: New changeset 35a3a7e0d66d by Mark Dickinson in branch '3.2': Issue 13496: Fix bisect.bisect overflow bug for large collections. http://hg.python.org/cpython/rev/35a3a7e0d66d New changeset 1a9252280f07 by Mark Dickinson in branch 'default': Issue #13496: Merge from 3.2 http://hg.python.org/cpython/rev/1a9252280f07 New changeset 709af2d0e862 by Mark Dickinson in branch '2.7': Issue 13496: Fix bisect.bisect overflow bug for large collections. http://hg.python.org/cpython/rev/709af2d0e862 -- nosy: +python-dev ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Changes by Mark Dickinson dicki...@gmail.com: -- resolution: - fixed status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Benjamin Peterson benja...@python.org added the comment: LGTM -- nosy: +benjamin.peterson ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Mark Dickinson dicki...@gmail.com added the comment: Updated patch, with comment. -- Added file: http://bugs.python.org/file24774/issue13496_v2.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Raymond Hettinger raymond.hettin...@gmail.com added the comment: Thanks for the updated patch. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Jesús Cea Avión j...@jcea.es added the comment: I think the patch is *NOT* correct. Does it work with http://bugs.python.org/msg148567, in a 32 bits python? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Mark Dickinson dicki...@gmail.com added the comment: I think the patch is *NOT* correct. Can you elaborate? It works fine for that example on a 64-bit build; not sure why 32-bit would be any different. The idea is just that the single cast forces the addition to be done as an addition of integers of type size_t. Since the integers being added are (a) nonnegative and (b) both fit into a Py_ssize_t, the sum fits into a size_t without overflow, and the result of dividing the sum by 2 fits into a size_t. (This is all assuming that 2*Py_SSIZE_T_MAX fits into a size_t, but that's a fairly safe assumption in practice.) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Mark Dickinson dicki...@gmail.com added the comment: Does it work with http://bugs.python.org/msg148567, in a 32 bits python? Yes. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Antoine Pitrou pit...@free.fr added the comment: Perhaps adding a comment before those two lines would make the reason for the cast clearer. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Mark Dickinson dicki...@gmail.com added the comment: Here's a patch. -- keywords: +patch Added file: http://bugs.python.org/file24346/issue13496.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Changes by Mark Dickinson dicki...@gmail.com: -- stage: - patch review ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
akira 4kir4...@gmail.com added the comment: Related bug in Java: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html Do not consider any change as trivial: http://www.solipsys.co.uk/new/BinarySearchReconsidered.html (the author ran binary search coding challenge about 10 years ago http://www.solipsys.co.uk/b_search/ ) -- nosy: +akira ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Changes by Jesús Cea Avión j...@jcea.es: -- nosy: +jcea ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Mark Dickinson dicki...@gmail.com added the comment: Given that we typically need at least 4 bytes just for the PyObject * pointer for each item in a list, I guess real lists are safe. But how about list-like objects, implementing __len__ and __getitem__? The following appears to run forever on my machine: class SquaresList(object): def __init__(self, length): self._length = length def __len__(self): return self._length def __getitem__(self, index): if not 0 = index = self._length: raise IndexError return index**2 import bisect, sys squareslist = SquaresList(sys.maxsize) print bisect.bisect(squareslist, (sys.maxsize - 3)**2) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Antoine Pitrou pit...@free.fr added the comment: Very good point, Mark. -- nosy: +pitrou ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Amaury Forgeot d'Arc amaur...@gmail.com added the comment: [x]range is enough to trigger the bug:: bisect.bisect(range(sys.maxsize), sys.maxsize-3) -- nosy: +amaury.forgeotdarc ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Raymond Hettinger raymond.hettin...@gmail.com added the comment: The fix is trivial. I'll do it soonish. -- priority: low - normal ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
New submission from Daniel Sturm voodoo...@gmail.com: The mid index computation in _bisectmodule.c in both internal_bisect_right and internal_bisect_left is done with: mid = (lo + hi) / 2; // all three variables Py_ssize_t which is susceptible to overflows for large arrays, which would lead to undefined behavior (and in practice almost certainly a crash with a negative index) The fix is trivial - mid = lo + (hi - lo) / 2; - but since I'm just starting to look into the code base I may be missing some undocumented assertions that guarantee this can't happen. -- components: Extension Modules messages: 148517 nosy: Voo priority: normal severity: normal status: open title: bisect module: Overflow at index computation type: behavior versions: Python 3.4 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Changes by Antoine Pitrou pit...@free.fr: -- nosy: +mark.dickinson, rhettinger versions: +Python 2.7, Python 3.2, Python 3.3 -Python 3.4 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Raymond Hettinger raymond.hettin...@gmail.com added the comment: This looks like a reasonable suggestion. -- assignee: - rhettinger priority: normal - low ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Tim Peters tim.pet...@gmail.com added the comment: FWIW, I doubt there's a real issue here. Objects in Python consume a lot more than a byte or two of memory, so the index range of a Python list is generally a lot less than ssize_t allows for. In other words, quantify large in large arrays. How large can a Python list actually be, relative to ssize_t? Similar reasoning accounts for why we never worry about overflow when mucking with refcounts: the size of a refcount member exceeds the maximum number of references that could exist. -- nosy: +tim_one ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue13496] bisect module: Overflow at index computation
Daniel Sturm voodoo...@gmail.com added the comment: TBH I saw this more as an opportunity to get used to the whole system, how to create a patch, etc. :) Should've made it clearer at the start that this is unlikely to ever be a problem, sorry (didn't see a way to set priority to low myself). If my math isn't completely off, the highest possible value here is hi + (hi - 1) so this only occurs if hi (MAX_SSIZE_T + 1) / 2. So this would only work out if we had such an array containing only a handful different objects. And then that's me assuming that a list is actually a thin wrapper around an array of PyObject*. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue13496 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
