Description

fuhsnn

opened on May 15, 2025

Issue body actions

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 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

Activity

1. fuhsnn

   added

   type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

   on May 15, 2025
2. picnixz

   added

   interpreter-core(Objects, Python, Grammar, and Parser dirs)(Objects, Python, Grammar, and Parser dirs)

   on May 15, 2025
3. picnixz commented on May 15, 2025

   

   picnixz

   on May 15, 2025

   Member

   More actions

   cc @colesbury
4. colesbury

   added

   3.13only security fixesonly security fixes

   3.14bugs and security fixesbugs and security fixes

   3.15bugs and security fixesbugs and security fixes

   on May 16, 2025
5. colesbury

   self-assigned this

   on May 16, 2025
6. vedant713

   added 9 commits that reference this issue on May 17, 2025

   Fix: Prevent out-of-bounds read in mi_clz32 and mi_ctz32 (python#134070)

   6a5b559

   Fix: Prevent out-of-bounds read in mi_clz32 and mi_ctz32 (python#134070)

   e8466b0

   Fix: Prevent out-of-bounds read in mi_ctz_generic32 and mi_clz_generic32

   7ec98ef

   pythongh-134070: Fix mi_clz32/mi_ctz32 to prevent out-of-bounds read (p…

   960e266

   pythongh-134070: Add news entry for mi_clz32/mi_ctz32 out-of-bounds fix

   eb1f908

   pythongh-134070: Add news entry for mimalloc out-of-bounds fix

   64e9718

   pythongh-134070: Add news entry for mimalloc out-of-bounds fix

   c961fa0

   pythongh-134070: Add news entry for mimalloc out-of-bounds fix

   911c128

   pythongh-134070: Add news entry for mimalloc out-of-bounds fix

   bce07b2
7. StanFromIreland commented on Oct 31, 2026

   

   StanFromIreland

   on Oct 31, 2026

   Member

   More actions

   Was this fixed in the mimalloc v2 bump?

   CC @corona10
8. StanFromIreland

   added

   pendingThe issue will be closed if no feedback is providedThe issue will be closed if no feedback is provided

   on Oct 31, 2026
9. corona10

   self-assigned this

   on Oct 31, 2026
10. corona10 commented on Nov 2, 2026

    

    corona10

    on Nov 2, 2026

    Member

    More actions

    cpython/Include/internal/mimalloc/mimalloc/internal.h

    Lines 1042 to 1051 in 313dfd8

    	static inline size_t mi_ctz_generic32(uint32_t x) {
    	// de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf>
    	static const uint8_t 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[(uint32_t)((x & -(int32_t)x) * (uint32_t)(0x077CB531U)) >> 27];
    	}

    Since we've upgraded mimalloc during the core sprint, this issue was also solved :)
    #159111
11. corona10

    closed this as completedon Nov 2, 2026
12. corona10

    added

    topic-free-threading

    and removed

    pendingThe issue will be closed if no feedback is providedThe issue will be closed if no feedback is provided

    on Nov 2, 2026

Issue actions