UBSAN: mi_slice_t index out of bounce

[tiran]

CPython's test suite for liblzma is failing under undefined behavior sanitizer mimalloc/segment.c:750:23: runtime error: index 1089 out of bounds for type 'mi_slice_t [1024]'. CPython overrides liblzma's allocator with a custom allocator. In my mimalloc branch the allocator uses mimalloc. The undefined behavior occurs every time when lzma_alloc requests a block of about 67 MB from mimalloc:

Breakpoint 2, lzma_alloc (allocator=0x2117081f990, size=67108872) at common/common.c:48
48                      ptr = allocator->alloc(allocator->opaque, 1, size);
(gdb) s
PyLzma_Malloc (opaque=<optimized out>, items=1, size=67108872) at /home/heimes/dev/python/cpython/Modules/_lzmamodule.c:171
171         if (size != 0 && items > (size_t)PY_SSIZE_T_MAX / size) {
(gdb) n
176         return PyMem_RawMalloc(items * size);
(gdb) s
PyMem_RawMalloc (size=67108872) at ../../Objects/obmalloc.c:717
717         if (size > (size_t)PY_SSIZE_T_MAX)
(gdb) n
719         return _PyMem_Raw.malloc(_PyMem_Raw.ctx, size);
(gdb) s
_PyMimalloc_Malloc (ctx=0x0, size=67108872) at ../../Objects/obmalloc.c:141
141     {
(gdb) n
142         if (size == 0)
(gdb) n
144         void *r = mi_malloc(size);
(gdb) s
_Py_mi_malloc (size=67108872) at ../../Objects/mimalloc/alloc.c:119
119       return mi_heap_malloc(mi_get_default_heap(), size);
...

reproducer

• install clang and CPython build dependencies
• get my mimalloc branch from gh-90815: Add mimalloc memory allocator python/cpython#31164
• configure CPython with CC=clang LD=clang CFLAGS="-fno-sanitize-recover -g -fno-omit-frame-pointer" ./configure -C --with-undefined-behavior-sanitizer
• make
• run test suite with UBSAN_OPTIONS=print_stacktrace=1 ./python -m test test_lzma

full traceback

$ UBSAN_OPTIONS=print_stacktrace=1 ./python -m test test_lzma
0:00:00 load avg: 0.48 Run tests sequentially
0:00:00 load avg: 0.48 [1/1] test_lzma
../../Objects/mimalloc/segment.c:750:23: runtime error: index 1089 out of bounds for type 'mi_slice_t [1024]'
    #0 0x547de7 in mi_segment_span_allocate /home/heimes/dev/python/cpython/builddir/usan/../../Objects/mimalloc/segment.c:750:23
    #1 0x54866e in mi_segment_init /home/heimes/dev/python/cpython/builddir/usan/../../Objects/mimalloc/segment.c:939:18
    #2 0x538fac in mi_segment_alloc /home/heimes/dev/python/cpython/builddir/usan/../../Objects/mimalloc/segment.c:950:10
    #3 0x538fac in mi_segment_huge_page_alloc /home/heimes/dev/python/cpython/builddir/usan/../../Objects/mimalloc/segment.c:1512:27
    #4 0x538fac in _Py__mi_segment_page_alloc /home/heimes/dev/python/cpython/builddir/usan/../../Objects/mimalloc/segment.c:1562:12
    #5 0x548d24 in mi_page_fresh_alloc /home/heimes/dev/python/cpython/builddir/usan/../../Objects/mimalloc/page.c:248:21
    #6 0x548a18 in mi_large_huge_page_alloc /home/heimes/dev/python/cpython/builddir/usan/../../Objects/mimalloc/page.c:785:21
    #7 0x53af95 in _Py__mi_malloc_generic /home/heimes/dev/python/cpython/builddir/usan/../../Objects/mimalloc/page.c:856:21
    #8 0x7f7f53538fd1 in lzma_alloc /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/common/common.c:48:9
    #9 0x7f7f53538fd1 in lz_encoder_init /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/lz/lz_encoder.c:422:13
    #10 0x7f7f53538fd1 in lzma_lz_encoder_init /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/lz/lz_encoder.c:577:6
    #11 0x7f7f5352a9cb in lzma_raw_coder_init /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/common/filter_common.c:286:23
    #12 0x7f7f5352f1de in block_encoder_init /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/common/stream_encoder.c:75:9
    #13 0x7f7f5352f1de in stream_encoder_update /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/common/stream_encoder.c:244:24
    #14 0x7f7f5352ffdd in stream_encoder_init /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/common/stream_encoder.c:323:9
    #15 0x7f7f53530132 in lzma_stream_encoder /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/common/stream_encoder.c:331:2
    #16 0x7f7f5353443a in lzma_easy_encoder /usr/src/debug/xz-5.2.5-7.fc35.x86_64/src/liblzma/common/easy_encoder.c:23:9
    #17 0x7f7f5357d190 in Compressor_init_xz /home/heimes/dev/python/cpython/Modules/_lzmamodule.c:657:17
    #18 0x7f7f5357c072 in Compressor_init /home/heimes/dev/python/cpython/Modules/_lzmamodule.c:820:17
    #19 0x560a8c in type_call /home/heimes/dev/python/cpython/builddir/usan/../../Objects/typeobject.c:1141:19
    #20 0x4b911c in _PyObject_MakeTpCall /home/heimes/dev/python/cpython/builddir/usan/../../Objects/call.c:214:18
    #21 0x61e624 in _PyEval_EvalFrameDefault /home/heimes/dev/python/cpython/builddir/usan/../../Python/ceval.c
    #22 0x613361 in _PyEval_EvalFrame /home/heimes/dev/python/cpython/builddir/usan/../../Include/internal/pycore_ceval.h:53:16
    #23 0x613361 in _PyEval_Vector /home/heimes/dev/python/cpython/builddir/usan/../../Python/ceval.c:6111:24
    #24 0x62348e in do_call_core /home/heimes/dev/python/cpython/builddir/usan/../../Python/ceval.c
...
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../../Objects/mimalloc/segment.c:750:23 in

[tiran]

I can reproduce the problem with just allocator a large chunk, see #544.

[daanx]

Hi @tiran, yikes that is scary .. but I think it is perhaps a "bug" in ubsan? Is the offending line in segment.c:750 of v2.0.3 ?, i.e.

mi_slice_t* last = &segment->slices[slice_index + slice_count - 1];

This is only an address calculation and I don't think any memory is accessed (also due to the if after it). Perhaps if we rewrite it as:

mi_slice_t* last = segment->slices + (slice_index + slice_count - 1);

ubsan will be happy? I will try to repro with ubsan using your commit but if you can try easily let me know.

[tiran]

Yeah, it looks scary to me, too. It looks like an actual bug. If I understand the code correctly then slice_index + slice_count - 1 must be smaller than MI_SLICES_PER_SEGMENT. In the problematic case, slice_count is 1088 and slice_index is 2:

static mi_page_t* mi_segment_span_allocate(mi_segment_t* segment, size_t slice_index, size_t slice_count, mi_segments_tld_t* tld) {
  fprintf(stderr, "%zu %zu %lu\n", slice_index, slice_count, slice_index + slice_count - 1);
  mi_assert_internal((slice_index + slice_count - 1) < MI_SLICES_PER_SEGMENT);

test: malloc-large...  0 2 1
2 1088 1089
mimalloc: assertion failed: at "/home/heimes/dev/misc/mimalloc/src/segment.c":721, mi_segment_span_allocate
  assertion: "(slice_index + slice_count - 1) < MI_SLICES_PER_SEGMENT"
Aborted (core dumped)

[daanx]

I pushed a commit that fixes this as the ubsan check was 'wrong'. Thanks so much.
(I will push a new release of mimalloc soon that will include the fix)

[tiran]

Aah! So the field can be larger than 1024 entries. Got it! Thanks Daan!

[tiran]

Your fix solves the wrong warning for me.

[daanx]

Yes, for "huge" allocations the "span" may be more than the fixed array of slices; the segment_t::segment_slices (in mimalloc-types.h) contains the actual allocated slices for huge allocations. (it is set up this way to share common structures and code and reduce the amount of special cases in the code (and avoid branching etc))

Thanks for the report!