Out-of-bounds read in integrated mimalloc (fixed upstream)

[fuhsnn]

Bug report

Bug description:

The integrated mimalloc has out-of-bounds bug in the generic implementation of ctz/clz:

cpython/Include/internal/mimalloc/internal.h

Lines 847 to 870 in 6a22963

	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

Linked PRs

• gh-134070: Prevent out-of-bounds read in mi_clz32 and mi_ctz32 #134149
• gh-134070: Fix mi_clz32/mi_ctz32 to prevent out-of-bounds read (GH-134149) #134157

[picnixz]

cc @colesbury