sort order is forced reverse alpha

[ChrisCheney]

exfat-fuse exfat-utils 1.2.8-1 (Ubuntu)

I am trying to force sort some exfat directories for use with hardware that doesn't do sorting itself in its user interface. It appears that exfat-fuse sorts files into reverse order regardless of how the files are written into a directory by userland.

If I take a directory and sort it using the following and then use ls -Ul it shows in alphabetical order until I umount and then remount the drive at which point it shows it in reverse order.

Simple test script:

find -type f -print0 | sort -rz | xargs -0 mv --target-directory=temp
cd temp
find -type f -print0 | sort -rz | xargs -0 mv --target-directory=..
cd ..

ls -Ul - shows alphabetical order

umount mount

ls -Ul - now shows reverse alphabetical order

If I then connect the drive to the hardware appliance it shows it is in reverse alpha order as well.

[relan]

fuse-exfat doesn't try to sort entries in any way. When it creates a new entry in a directory it allocates the first suitable slot. But fuse-exfat also maintains a per-directory linked list of entries in memory. New items are added into the beginning of this list instead of the end because other operations over the new item usually follow, so it'll be found faster. When you list a directory, fuse-exfat iterates through the in-memory list, not disk entries (that's much faster).

If you absolutely need an alphabetic order, move files into a new directory in alphabetic order and then unmount and mount again.

[ChrisCheney]

Thats what I have been trying to do as shown above in the test script, it shows it in order with ls -Ul but then when I unmount and remount is done it shows that it hit the disk in reverse order instead.

[ChrisCheney]

Simple reproducer

ccheney@hostname:/media/ccheney/drive$ mkdir test1
cccheney@hostname:/media/ccheney/drive$ cd test1
ccheney@hostname:/media/ccheney/drive/test1$ ls
ccheney@hostname:/media/ccheney/drive/test1$ touch c
ccheney@hostname:/media/ccheney/drive/test1$ touch f
ccheney@hostname:/media/ccheney/drive/test1$ touch a
ccheney@hostname:/media/ccheney/drive/test1$ touch e
ccheney@hostname:/media/ccheney/drive/test1$ touch b
ccheney@hostname:/media/ccheney/drive/test1$ touch g
ccheney@hostname:/media/ccheney/drive/test1$ touch d
ccheney@hostname:/media/ccheney/drive/test1$ ls -Ul
total 0
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 d
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 g
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 b
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 e
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 a
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 f
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 c
ccheney@hostname:/media/ccheney/drive/test1$ cd ..
ccheney@hostname:/media/ccheney/drive$ cd ..
ccheney@hostname:/media/ccheney$ cd drive/test1/
ccheney@hostname:/media/ccheney/drive/test1$ ls -Ul
total 0
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 c
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 f
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 a
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 e
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 b
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 g
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 d
ccheney@hostname:/media/ccheney/drive/test1$ mkdir temp
ccheney@hostname:/media/ccheney/drive/test1$ find -type f -print0 | sort -rz | xargs -0 mv --target-directory=temp
ccheney@hostname:/media/ccheney/drive/test1$ cd temp
ccheney@hostname:/media/ccheney/drive/test1/temp$ ls -Ul
total 0
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 a
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 b
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 c
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 d
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 e
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 f
-rwxrwxrwx 1 ccheney ccheney 0 Feb  9 02:06 g
ccheney@hostname:/media/ccheney/drive/test1/temp$ find -type f -print0 | sort -rz | xargs -0 mv --target-directory=..
ccheney@hostname:/media/ccheney/drive/test1/temp$ cd ..
ccheney@hostname:/media/ccheney/drive/test1$ ls -Ul
total 512
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 a
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 b
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 c
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 d
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 e
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 f
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 g
drwxrwxrwx 1 ccheney ccheney 524288 Feb  9 02:07 temp
ccheney@hostname:/media/ccheney/drive/test1$ cd ../..

-- unmounted/mounted here in gui

ccheney@hostname:/media/ccheney$ cd drive/test1/ 
ccheney@hostname:/media/ccheney/drive/test1$ ls -Ul
total 512
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 g
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 f
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 e
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 d
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 c
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 b
-rwxrwxrwx 1 ccheney ccheney      0 Feb  9 02:06 a
drwxrwxrwx 1 ccheney ccheney 524288 Feb  9 02:07 temp
ccheney@hostname:/media/ccheney/drive/test1$

[ChrisCheney]

So I guess a question to determine the answer to is exfat-fuse actually showing disk directory order when 'ls -Ul' is being used?

       -U     do not sort; list entries in directory order

As ls shows the directory in alphabetical order before unmount and then in reverse alphabetical order after mounting again.

[ChrisCheney]

Tested some more.

It appears the actual bug is the display order after sorting the directory before unmount, which caused me to think I needed 'sort -rz', which puts it in reverse alphabetical order.

If I switch to 'sort -z' instead, which is what it should logically be, 'ls -Ul' shows it in reverse order until I unmount and remount, and then 'ls -Ul' shows it in proper alphabetical order as it apparently hits the disk in order despite showing it backwards before unmount.

[relan]

Exactly.

So, this issue is about making entries order stable across mounts, right? This can be achieved in two ways:

1. Look up a proper place in the list when inserting a new entry (proper = corresponding to the entry offset on the disk). Basically make insertion operations O(n) instead of O(1).
2. Switch from lists to different structures (trees or hashes). This will slow down insertions, but speed up lookups.