Crashes on a use-after-free caused by vector iterator invalidation

[nyanpasu64]

When I install the ntfs2btrfs-git AUR package and run, it crashes:

nyanpasu64@ryzen ~> sudo ntfs2btrfs /dev/nvme0n1p6
Using Zstd compression.
Using CRC32C for checksums.
Processing inode 23214 / 23214 (100.0%)
Mapped 13018 inodes directly.
Rewrote 0 inodes.
Inlined 6437 inodes.
Updating directory sizes
Calculating checksums 14862031 / 14862031 (100.0%)
fish: Job 1, 'sudo ntfs2btrfs /dev/nvme0n1p6' terminated by signal SIGSEGV (Address boundary error)

When I rebuild with asan enabled and run again, it prints more information about the crash:

nyanpasu64@ryzen ~/code/ntfs2btrfs/build-GCC_lld_asan-RelWithDebInfo (master)> sudo ./ntfs2btrfs /dev/nvme0n1p6
Using Zstd compression.
Using CRC32C for checksums.
Processing inode 23214 / 23214 (100.0%)
Mapped 13018 inodes directly.
Rewrote 0 inodes.
Inlined 6437 inodes.
Updating directory sizes
Calculating checksums 14862031 / 14862031 (100.0%)
=================================================================
==8895==ERROR: AddressSanitizer: heap-use-after-free on address 0x633000006470 at pc 0x562dbdecd29d bp 0x7ffe88d2a060 sp 0x7ffe88d2a050
READ of size 8 at 0x633000006470 thread T0
    #0 0x562dbdecd29c in std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >::data() const /usr/include/c++/12.1.0/bits/stl_vector.h:1261
    #1 0x562dbdecd29c in root::create_trees(root&, btrfs_csum_type) /home/nyanpasu64/code/ntfs2btrfs/src/ntfs2btrfs.cpp:684
    #2 0x562dbdef752e in convert /home/nyanpasu64/code/ntfs2btrfs/src/ntfs2btrfs.cpp:3595
    #3 0x562dbdf660c9 in main /home/nyanpasu64/code/ntfs2btrfs/src/ntfs2btrfs.cpp:3848
    #4 0x7f7f5003728f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #5 0x7f7f50037349 in __libc_start_main_impl ../csu/libc-start.c:389
    #6 0x562dbde8a5d4 in _start (/home/nyanpasu64/code/ntfs2btrfs/build-GCC_lld_asan-RelWithDebInfo/ntfs2btrfs+0x365d4)

0x633000006470 is located 23664 bytes inside of 98304-byte region [0x633000000800,0x633000018800)
freed by thread T0 here:
    #0 0x7f7f5070378a in operator delete(void*, unsigned long) /usr/src/debug/gcc/libsanitizer/asan/asan_new_delete.cpp:164
    #1 0x562dbdf138a4 in std::__new_allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > >::deallocate(std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >*, unsigned long) /usr/include/c++/12.1.0/bits/new_allocator.h:158
    #2 0x562dbdf138a4 in std::allocator_traits<std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > >::deallocate(std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > >&, std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >*, unsigned long) /usr/include/c++/12.1.0/bits/alloc_traits.h:496
    #3 0x562dbdf138a4 in std::_Vector_base<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >, std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > >::_M_deallocate(std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >*, unsigned long) /usr/include/c++/12.1.0/bits/stl_vector.h:387
    #4 0x562dbdf138a4 in std::_Vector_base<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >, std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > >::_M_deallocate(std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >*, unsigned long) /usr/include/c++/12.1.0/bits/stl_vector.h:383
    #5 0x562dbdf138a4 in void std::vector<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >, std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > >::_M_realloc_insert<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > const&>(__gnu_cxx::__normal_iterator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >*, std::vector<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >, std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > > >, std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > const&) /usr/include/c++/12.1.0/bits/vector.tcc:513

previously allocated by thread T0 here:
    #0 0x7f7f50702672 in operator new(unsigned long) /usr/src/debug/gcc/libsanitizer/asan/asan_new_delete.cpp:95
    #1 0x562dbdf134c5 in std::__new_allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > >::allocate(unsigned long, void const*) /usr/include/c++/12.1.0/bits/new_allocator.h:137
    #2 0x562dbdf134c5 in std::allocator_traits<std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > >::allocate(std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > >&, unsigned long) /usr/include/c++/12.1.0/bits/alloc_traits.h:464
    #3 0x562dbdf134c5 in std::_Vector_base<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >, std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > >::_M_allocate(unsigned long) /usr/include/c++/12.1.0/bits/stl_vector.h:378
    #4 0x562dbdf134c5 in void std::vector<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >, std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > >::_M_realloc_insert<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > const&>(__gnu_cxx::__normal_iterator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >*, std::vector<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >, std::allocator<std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > > > >, std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > > const&) /usr/include/c++/12.1.0/bits/vector.tcc:453

SUMMARY: AddressSanitizer: heap-use-after-free /usr/include/c++/12.1.0/bits/stl_vector.h:1261 in std::vector<unsigned char, default_init_allocator<unsigned char, std::allocator<unsigned char> > >::data() const
Shadow bytes around the buggy address:
  0x0c667fff8c30: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c667fff8c40: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c667fff8c50: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c667fff8c60: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c667fff8c70: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
=>0x0c667fff8c80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd[fd]fd
  0x0c667fff8c90: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c667fff8ca0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c667fff8cb0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c667fff8cc0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x0c667fff8cd0: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
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
==8895==ABORTING

That was a doozy.

The bug is that t is a dangling reference:

for (const auto& t : trees) {
    trees.push_back(buf);
    auto ln = (leaf_node*)((uint8_t*)t.data() + sizeof(tree_header));

You could replace t with a non-owning std::span constructed from trees[i], but it's still wrong to push into trees while iterating over it (the for loop will still error out).

IMO you should replace the foreach loop with a for (size_t i = 0; i < trees.size(); i++), and either replace all uses of t with trees[i] or apply the std::span transformation as I mentioned above. I'd also comment that trees is being pushed onto, so you can't replace the indexed loop with a foreach.

TBH pushing onto a loop while iterating over it is quite tricky to understand. I'm not sure if it's necessary complexity, or if you can refactor to preserve user-facing functionality without pushing onto a loop while iterating over it; I don't actually know how your program works.

Are there any remaining latent or crashing bugs past this? I don't know! I applied the for-loop fix and wrote trees[i] twice, and the resulting ASAN-enabled binary seems to process my partition without crashing...

I think this is the same bug as #47 and possibly #39.

[maharmstone]

Oops! That's a stupid bug, thank you for doing the detective work. I've replaced the std::vector with a std::list instead, which doesn't have a problem with iterator invalidation.