Ticket #4287 (closed defect: fixed)
Quadratic(?) slowdown on file moves across filesystems
Reported by: | slyfox | Owned by: | andrew_b |
---|---|---|---|
Priority: | major | Milestone: | 4.8.28 |
Component: | mc-core | Version: | master |
Keywords: | Cc: | ||
Blocked By: | Blocking: | ||
Branch state: | merged | Votes for changeset: | committed-master |
Description
Tried to move firefox build tree from one btrfs subvolume to another on NVMe device. It contained ~2M files. Normally it should take under a minute to relink a few gigabytes. But mc did not not succeed in 1 hour.
Looks like there is a quadratic behavior in file moves related to single list traversal.
Here is the reproducer:
- create 1M files in a firectory structure (we will create 1000 dirs 1000 files each)
- put them all in one directory 'd'
- move this 'd' from one tmpfs to another
Expected behavior: operation should take seconds (rougly the same time it takes to create the directory tree).
Actual behaviour: it takes tens of minutes to move the dir.
Script to build a directory:
#!/usr/bin/env bash # fail on first problem set -e echo "prepating two new tmpfs filesystems: /tmp/tmpfs-src and /tmp/tmpfs-dst" mkdir /tmp/tmpfs-src mkdir /tmp/tmpfs-dst sudo mount -t tmpfs tmpfs /tmp/tmpfs-src sudo mount -t tmpfs tmpfs /tmp/tmpfs-dst # allow current user to fiddle with it sudo chown ${USER} /tmp/tmpfs-src /tmp/tmpfs-dst echo "creating 1M files" # create 1 million empty files mkdir /tmp/tmpfs-src/d for d in {1..1000}; do mkdir /tmp/tmpfs-src/d/$d touch /tmp/tmpfs-src/d/$d/{1..1000} done echo "don't forget cleanup: 'sudo umount /tmp/tmpfs-src; sudo umount /tmp/tmpfs-dst'" echo "Now you can run 'mc /tmp/tmpfs-src /tmp/tmpfs-dst' and try to move 'd' directory with F6."
Run as:
- Run '$ prepare_environment.bash'
- Run 'mc /tmp/tmpfs-src /tmp/tmpfs-dst'
- Start moving with 'F6' on 'd' dir.
Attachments
Change History
comment:2 in reply to: ↑ 1 Changed 3 years ago by andrew_b
Replying to slyfox:
96.41% mc libglib-2.0.so.0.6800.3 [.] g_slist_last[...]
#2 0x000000000046d2dd in copy_dir_dir (tctx=0xc27ff0, ctx=0xc27f50, s=0xc24f00 "/tmp/tmpfs-src/d/591", d=<optimized out>, toplevel=<optimized out>, move_over=<optimized out>, do_delete=1, parent_dirs=0xa6c9ab0) at file.c:2989
I can propose to replace g_list_append() with g_list_prepend() if order of erase_list items is no matter or reimplement erase_list using GQueue otherwise.
comment:3 Changed 3 years ago by andrew_b
- Owner set to andrew_b
- Status changed from new to accepted
- Branch state changed from no branch to on review
- Milestone changed from Future Releases to 4.8.28
Branch: 4287_slow_move
changeset:1b39025049322bd311654a4ddaaaeafc1cb39164
comment:4 Changed 3 years ago by slyfox
The patch works for me: 1M files move in ~30 seconds.
Thank you!
comment:5 Changed 3 years ago by andrew_b
- Votes for changeset set to slyfox andrew_b
- Branch state changed from on review to approved
comment:6 Changed 3 years ago by andrew_b
- Status changed from accepted to testing
- Votes for changeset changed from slyfox andrew_b to committed-master
- Resolution set to fixed
- Branch state changed from approved to merged
Merged to master: [130e50ec89be9a2d5fd0025dbab5a5d22e575db0].
comment:8 Changed 3 years ago by Axanar
I believe, that I triggered an issue with the last merged patch as you can see in the attachment.
When moving single files or a list of files, then the move went fine. As soon as you move a directory with no, one or many files then this critical assertion pops up all the time.
May I ask to have a review of the last merged patch ? This issue won't happen with the last official release but happens with mc git.
Changed 3 years ago by Axanar
- Attachment Screenshot_2021-10-02_09-03-53.png added
Picture ilustrating the issue.
'perf record / perf report' renders the following:
GDB's backtrace for possible location:
https://people.gnome.org/~ryanl/glib-docs/glib-Singly-Linked-Lists.html warns about 'g_slist_append':