Re: [PATCH v6 08/71] Maple Tree: Add new data structure

[Vasily Gorbik <gor@linux.ibm.com>]

On Sun, Feb 27, 2022 at 02:11:52AM +0100, Vasily Gorbik wrote:
> Hi Liam,
> 
> there is an endianness issue with maple_metadata. This is broken on
> all big endian architectures. Tests are crashing. See potential fixup
> below. Feel free to apply it or fix the issue in your own way. This does
> not resolve all the issues with the patch series though.

Besides this obvious endianness issue there could be synchronization
issue(s) which manifest on s390 with maple tree tests.

I've double checked that:
- userspace-rcu 13.1 I'm using passes unit and regression tests
- maple tree tests are also crashing with asan/ubsan disabled

If I disable check_rcu_simulated() then in most -Og/-O2 asan
enabled/disabled combinations the rest of the tests happen pass for me now.
But otherwise I see "random" crashes not specific to check_rcu_simulated().

I'll try to find time to look into that and isolate issues further.

E.g. with -O2:
==441271==ERROR: AddressSanitizer: heap-use-after-free on address 0x61c00240fd24 at pc 0x000001003c62 bp 0x03ffb58fe8b0 sp 0x03ffb58fe8a8                                                                    [0/9325]
READ of size 4 at 0x61c00240fd24 thread T1
    #0 0x1003c61 in mas_dead_walk ../../../lib/maple_tree.c:5403
    #1 0x101bbcb in mt_free_walk ../../../lib/maple_tree.c:5428
    #2 0x3ffb9c841e5 in call_rcu_thread /userspace-rcu/src/urcu-call-rcu-impl.h:369
    #3 0x3ffb919cf8b in start_thread pthread_create.c:435
    #4 0x3ffb92164fd  (/lib64/libc.so.6+0x1164fd)

0x61c00240fd24 is located 1060 bytes inside of 1536-byte region [0x61c00240f900,0x61c00240ff00)
freed by thread T1 here:
    #0 0x3ffb9db005b in __interceptor_free ../../../../libsanitizer/asan/asan_malloc_linux.cpp:127
    #1 0x10fa17f in kmem_cache_free /devel/src/kernel/tools/testing/radix-tree/linux.c:116

previously allocated by thread T0 here:
    #0 0x3ffb9db0f59 in __interceptor_posix_memalign ../../../../libsanitizer/asan/asan_malloc_linux.cpp:226
    #1 0x10faa21 in kmem_cache_alloc_bulk /devel/src/kernel/tools/testing/radix-tree/linux.c:162
    #2 0x3fffdb7e6af  ([stack]+0xc36af)

Thread T1 created by T0 here:
    #0 0x3ffb9d5a28f in __interceptor_pthread_create ../../../../libsanitizer/asan/asan_interceptors.cpp:216
    #1 0x3ffb9c827d9 in call_rcu_data_init /userspace-rcu/src/urcu-call-rcu-impl.h:434

SUMMARY: AddressSanitizer: heap-use-after-free ../../../lib/maple_tree.c:5403 in mas_dead_walk
Shadow bytes around the buggy address:
  0x100c3800481f50: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x100c3800481f60: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x100c3800481f70: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x100c3800481f80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x100c3800481f90: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
=>0x100c3800481fa0: fd fd fd fd[fd]fd fd fd fd fd fd fd fd fd fd fd
  0x100c3800481fb0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x100c3800481fc0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x100c3800481fd0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x100c3800481fe0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x100c3800481ff0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
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
==441271==ABORTING

Or even stall on rcu_barrier() with default -Og:

Thread 2 (Thread 0x3ffa5bff800 (LWP 439996) "maple"):
#0  futex_wait (private=0, expected=2, futex_word=0x3ffa5bfea40) at ../sysdeps/nptl/futex-internal.h:146
#1  __GI___lll_lock_wait (futex=futex@entry=0x3ffa5bfea40, private=<optimized out>) at lowlevellock.c:50
#2  0x000003ffa94202e8 in lll_mutex_lock_optimized (mutex=0x3ffa5bfea40) at pthread_mutex_lock.c:49
#3  ___pthread_mutex_lock (mutex=0x3ffa5bfea40) at pthread_mutex_lock.c:89
#4  0x000000000102180e in mt_free_walk (head=0x61c00240e908) at ../../../lib/maple_tree.c:5425
#5  0x000003ffa9f041e6 in call_rcu_thread (arg=0x60c000000040) at urcu-call-rcu-impl.h:369
#6  0x000003ffa941cf8c in start_thread (arg=<optimized out>) at pthread_create.c:435
#7  0x000003ffa94964fe in thread_start () at ../sysdeps/unix/sysv/linux/s390/s390-64/clone.S:67
Thread 1 (Thread 0x3ffaaa6f980 (LWP 439995) "maple"):
#0  syscall () at ../sysdeps/unix/sysv/linux/s390/s390-64/syscall.S:37
#1  0x000003ffa9f03c0a in futex (val3=0, uaddr2=0x0, timeout=0x0, val=-1, op=0, uaddr=0x602000000554) at ../include/urcu/futex.h:72
#2  futex_noasync (timeout=0x0, uaddr2=0x0, val3=0, val=-1, op=0, uaddr=0x602000000554) at ../include/urcu/futex.h:81
#3  call_rcu_completion_wait (completion=0x602000000550) at urcu-call-rcu-impl.h:279
#4  urcu_memb_barrier () at urcu-call-rcu-impl.h:895
#5  urcu_memb_barrier () at urcu-call-rcu-impl.h:840
#6  0x00000000010bfc0a in maple_tree_seed () at ../../../lib/test_maple_tree.c:37385
#7  0x00000000010c0280 in maple_tree_tests () at maple.c:47
#8  0x00000000010c02a0 in main () at maple.c:54