ext4: fix large_dir directory index node split corruption

affected systems

• kernels containing b5776e7 starting Feb 2021
  • 5.12 - 5.13
  • 5.11.3 - ?
  • 5.10.20 - ?
  • 5.4.102 - ?
  • 4.19.178 - ?
  • 4.14.223 - ?
• kernels older than this, have another corruption issue that b5776e7 intended to fix
• only ext4 filesystems with large_dir enabled, to check:

  # sudo tune2fs -l /dev/sdb1 | grep "Filesystem features"
  Filesystem features:      has_journal ext_attr resize_inode dir_index filetype needs_recovery extent
  64bit flex_bg large_dir sparse_super large_file huge_file dir_nlink extra_isize metadata_csum

• only where a directory grows over about 26M files

recommendation

• upgrade to kernel 5.14 or later

security implication

• unprivileged user can corrupt directory index by creating many files

steps to reproduce

1. require a GNU/Linux system with python and 800GB+ free space
2. as root
   1. create ext4 filesystem inside a file tmpfs
   2. enable large_dir
   3. mount it as tmpmnt

   fallocate -l 800G tmpfs
   mkfs -t ext4 tmpfs
   tune2fs -O large_dir tmpfs
   mount tmpfs tmpmnt

3. prepare to write 32 million files by saving the following python script.py

   #!/bin/python
   i = 0
   while i <= 32000000:
       print (i)
       with open('tmpmnt/%d' % i, 'wb') as fout:
           i += 1

4. run python script.py to completion
   1. observe broken behaviour (errno 17 EEXIST or 117 EUCLEAN)

      0
      1
      ...
      26369026
      26369027
      Traceback (most recent call last):
        File "tmpmnt/script.py", line 5, in <module>
          with open('tmpmnt/%d' % i, 'wb') as fout:
      FileExistsError: [Errno 17] File exists: 'tmpmnt/26369027'

   2. expected behaviour

      0
      1
      ...
      31999999
      32000000

5. tidy up

   umount tmpmnt
   rm tmpfs script.py

the bug

• hard to spot
  • large_dir is not enabled by default, and lots of systems on ext2/3
  • directory index htree growth must trigger while under affected kernel
  • large directories grown under unaffected kernel can mask problem under affected kernel
• hard to workaround
  • large_dir once enabled, cannot be disabled
  • e2fsck does not prevent recurrence
• kernel commit b5776e7524afbd4569978ff790864755c438bba7
  • initially flagged as likely possible culprit
    • recent ext4 change regex match "corruption"
    • change to a non-trivial loop full of goto statements
    • comment laments complexity, "the original code doesn't make any sense"
    • complains of inadequate code review, yet no evidence of wide review of itself
  • confirmed by bisection 5.12 - 5.10
  • intended to fix internal Google-Bug-Id: 176345532
  • is a bug fix for the original largedir implementation e08ac99
  • changed the ext4_dx_add_entry function in fs/ext4/namei.c
  • inadvertently removed a critical goto condition
  • specifically, fixes condition restart=0 but breaks restart=1
  • it fixes the rare case (ENOSP) but breaks the more common one
  • incorrectly allows outer scope do_split to be called on pending loop restart
  • leads to Shrödinger split behaviour on future file access
    • subsequent open for read of affected file fails as file does not exist
    • subsequent open for write of affected file fails as file already exists (sic)
• backported to stable kernels as commit 9ce493f642ed2f7280b3d1f4159d98ecc7efb0fa

suggested fix

• a naïve approach would be to reinstate the missing goto, but
  1. such approach is likely to contribute to another mistake in the future
  2. goto considered harmful
• instead refactor the outer scope to handle both restart conditions (goto agnostic):

  diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
  index 9cc9e6c1d582..5052d1a6f6d8 100644
  --- a/fs/ext4/namei.c
  +++ b/fs/ext4/namei.c
  @@ -2428,13 +2428,15 @@ static int ext4_dx_add_entry(handle_t *handle,
  struct ext4_filename *fname,
   			goto journal_error;
   		}
   	}
  -	de = do_split(handle, dir, &bh, frame, &fname->hinfo);
  -	if (IS_ERR(de)) {
  -		err = PTR_ERR(de);
  +	if (!restart) {
  +		de = do_split(handle, dir, &bh, frame, &fname->hinfo);
  +		if (IS_ERR(de)) {
  +			err = PTR_ERR(de);
  +			goto cleanup;
  +		}
  +		err = add_dirent_to_buf(handle, fname, dir, inode, de,
  bh);
   		goto cleanup;
   	}
  -	err = add_dirent_to_buf(handle, fname, dir, inode, de, bh);
  -	goto cleanup;
   
   journal_error:
   	ext4_std_error(dir->i_sb, err); /* this is a no-op if err == 0
  */

• tested in kernel 5.11.20
• sent to ext4-linux
• kernel developers apply naïvefix anyway
• see https://github.com/torvalds/linux/commit/877ba3f729fd3d8ef0e29bc2a55e57cfa54b2e43

funny memes

open questions

• why does the 32M file test require such large space even though only a few % is used
• why is corruption observed with htree 2to3 split but not 1to2 (i.e. large_dir disabled)
• why did ubuntu number their 5.11 kernels incorrectly
• why ubuntu kernel build process requires internet access and downloads zfs debs
• why is getting a modified linux kernel to boot so difficult
• why continue work on this when there is zero incentive to do so