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:

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

@colesbury

cc @colesbury

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

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

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

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

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

Navigation Menu

Repository navigation

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

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	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];
	}

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

Description

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Activity

picnixz commented on May 15, 2025

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions