Out-of-bounds read in integrated mimalloc (fixed upstream)
Bug report
Bug description:
The integrated mimalloc has out-of-bounds bug in the generic implementation of ctz/clz:
| static inline size_t mi_ctz32(uint32_t x) { | |
| // de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> | |
| static const unsigned char 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) return 32; | |
| return debruijn[((x & -(int32_t)x) * 0x077CB531UL) >> 27]; | |
| } | |
| static inline size_t mi_clz32(uint32_t x) { | |
| // de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> | |
| static const uint8_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) return 32; | |
| 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 array debruijn[].
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