Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork32k
Assignees
Description
Bug report
Bug description:
The integrated mimalloc has out-of-bounds bug in the generic implementation of ctz/clz:
cpython/Include/internal/mimalloc/mimalloc/internal.h
Lines 847 to 870 in6a22963
| staticinlinesize_tmi_ctz32(uint32_t x) { | |
| // de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> | |
| staticconstunsignedchar debruijn[32] = { | |
| 0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8, | |
| 31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9 | |
| }; | |
| if (x==0)return32; | |
| return debruijn[((x & -(int32_t)x) *0x077CB531UL) >>27]; | |
| } | |
| staticinlinesize_tmi_clz32(uint32_t x) { | |
| // de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> | |
| staticconstuint8_t debruijn[32] = { | |
| 31,22,30,21,18,10,29,2,20,17,15,13,9,6,28,1, | |
| 23,19,11,3,16,14,7,24,12,4,8,25,5,26,27,0 | |
| }; | |
| if (x==0)return32; | |
| x |= x >>1; | |
| x |= x >>2; | |
| x |= x >>4; | |
| x |= x >>8; | |
| x |= x >>16; | |
| return debruijn[(uint32_t)(x *0x07C4ACDDUL) >>27]; | |
| } | |
On platforms with 64-bit
UL, the multiplication in index calculation can grow much larger than arraydebruijn[].It has been fixed in this upstream commit:
microsoft/mimalloc@ed31847
CPython versions tested on:
3.14, CPython main branch, 3.13, 3.15
Operating systems tested on:
Linux