Segfault with roaring64_bitmap_flip_inplace

[Ezibenroc]

Segfault with roaring64_bitmap_flip_inplace

[Dr-Emann]

Simplier reproduction:

roaring64_bitmap_t* bm = roaring64_bitmap_from(0);
for (int i = 0; i < 6; ++i) {
    uint64_t val = 1ULL << (i * 8 + 16);
    roaring64_bitmap_add(bm, val);
}
printf("cardinality = %d\n", (int)roaring64_bitmap_get_cardinality(bm));

[lemire]

@SLieve Do you want to have a look?

[Dr-Emann]

A few notes so far:

roaring64_bitmap_internal_validate returns true after every step

Output of running under ASAN

=================================================================
==377453==ERROR: AddressSanitizer: stack-buffer-overflow on address 0xfffffa7f7138 at pc 0xaaaab8ee754c bp 0xfffffa7f6f10 sp 0xfffffa7f6f20
WRITE of size 8 at 0xfffffa7f7138 thread T0
    #0 0xaaaab8ee7548 in art_iterator_down /tmp/tmp.LqZsze1fXs/src/art/art.c:1533
    #1 0xaaaab8ee7ed4 in art_node_init_iterator /tmp/tmp.LqZsze1fXs/src/art/art.c:1588
    #2 0xaaaab8ee8b14 in art_init_iterator /tmp/tmp.LqZsze1fXs/src/art/art.c:1670
    #3 0xaaaab8ea82f0 in roaring64_bitmap_get_cardinality /tmp/tmp.LqZsze1fXs/src/roaring64.c:710
    #4 0xaaaab8e75a9c in test_copy /tmp/tmp.LqZsze1fXs/tests/roaring64_unit.cpp:49
    #5 0xaaaab8fa9028 in cmocka_run_one_test_or_fixture /tmp/tmp.LqZsze1fXs/cmake-build-sanitize-oracle-vm/_deps/cmocka-src/src/cmocka.c:2801
    #6 0xaaaab8fa931c in cmocka_run_one_tests /tmp/tmp.LqZsze1fXs/cmake-build-sanitize-oracle-vm/_deps/cmocka-src/src/cmocka.c:2909
    #7 0xaaaab8fa9844 in _cmocka_run_group_tests /tmp/tmp.LqZsze1fXs/cmake-build-sanitize-oracle-vm/_deps/cmocka-src/src/cmocka.c:3040
    #8 0xaaaab8e81000 in main /tmp/tmp.LqZsze1fXs/tests/roaring64_unit.cpp:1834
    #9 0xffffa73573f8 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #10 0xffffa73574c8 in __libc_start_main_impl ../csu/libc-start.c:392
    #11 0xaaaab8e7542c in _start (/tmp/tmp.LqZsze1fXs/cmake-build-sanitize-oracle-vm/tests/roaring64_unit+0x15542c)

Address 0xfffffa7f7138 is located in stack of thread T0 at offset 152 in frame
    #0 0xaaaab8ee88d0 in art_init_iterator /tmp/tmp.LqZsze1fXs/src/art/art.c:1665

  This frame has 1 object(s):
    [32, 152) 'iterator' (line 1666) <== Memory access at offset 152 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow /tmp/tmp.LqZsze1fXs/src/art/art.c:1533 in art_iterator_down
Shadow bytes around the buggy address:
  0x200fff4fedd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x200fff4fede0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x200fff4fedf0: f1 f1 f1 f1 00 00 f3 f3 00 00 00 00 00 00 00 00
  0x200fff4fee00: 00 00 f1 f1 f1 f1 00 00 f3 f3 00 00 00 00 00 00
  0x200fff4fee10: 00 00 00 00 f1 f1 f1 f1 00 00 00 00 00 00 00 00
=>0x200fff4fee20: 00 00 00 00 00 00 00[f3]f3 f3 f3 f3 00 00 00 00
  0x200fff4fee30: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00 00
  0x200fff4fee40: 00 00 00 00 00 00 00 00 00 00 00 00 00 f3 f3 f3
  0x200fff4fee50: f3 f3 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x200fff4fee60: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x200fff4fee70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==377453==ABORTING

Output of art_printf

Output of art_printf immediately before roaring64_bitmap_get_cardinality (art_printf also does not complain with ASAN)

{
 type: Node4
 prefix_size: 0
 prefix: 
 key: 00 {
  type: Node4
  prefix_size: 0
  prefix: 
  key: 00 {
   type: Node4
   prefix_size: 0
   prefix: 
   key: 00 {
    type: Node4
    prefix_size: 0
    prefix: 
    key: 00 {
     type: Node4
     prefix_size: 0
     prefix: 
     key: 00 {
      type: Node4
      prefix_size: 0
      prefix: 
      key: 00 { type: Leaf, key: 000000000000 }
      key: 01 { type: Leaf, key: 000000000001 }
     }
     key: 18 { type: Leaf, key: 000000001870 }
    }
    key: 41 { type: Leaf, key: 00000041b3e4 }
   }
   key: 40 { type: Leaf, key: 00004079536e }
  }
  key: 80 { type: Leaf, key: 008000000001 }
 }
 key: 01 {
  type: Node4
  prefix_size: 0
  prefix: 
  key: 00 { type: Leaf, key: 010000000001 }
  key: 80 { type: Leaf, key: 018000000001 }
 }
}

And a little more visually:

It appears we're hitting this line:

CRoaring/src/art/art.c

Line 1533 in e1e2359

iterator->frames[iterator->frame].node = indexed_child.child;

with iterator->frame == 6, where iterator->frame is an array of size 6

[SLieve]

Will take a look this weekend.