Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.
$ touch dir/{{1..8},{a..p}}
$ tar cJvf file.tar.xz dir/
dir/
dir/o
dir/k
dir/b
dir/3
dir/1
dir/i
dir/7
dir/4
dir/e
dir/a
dir/g
dir/2
dir/d
dir/5
dir/8
dir/c
dir/n
dir/f
dir/h
dir/6
dir/l
dir/m
dir/j
dir/p

I would have expected it to be alphabetical. But apparently it's not. What's the formula, here?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

As @samiam has stated the list is returned to you in a semi-random order via readdir(). I'll just add the following.

The list returned is what I would call the directory order. On older filesystems, the order is often the creation order that the file entries in the directory's table were added. There is of course a caveat to this, when a directory entry is deleted, this entry is then recycled, so any subsequent files that are stored will replace the previous entry, so the order will no longer by based solely on creation time.

On modern filesystems where directory data structures are based on a search tree or hash table, the order is practically unpredictable.

Examples

Poking at the files created when you run your touch command reveals the following inodes were assigned.

$ touch dir/{{1..8},{a..p}}
$ stat --printf="%n -- %i\n" dir/*
dir/1 -- 10883235
dir/2 -- 10883236
dir/3 -- 10883242
dir/4 -- 10883243
dir/5 -- 10883244
dir/6 -- 10883245
dir/7 -- 10883246
dir/8 -- 10883247
dir/a -- 10883248
dir/b -- 10883249
dir/c -- 10883250
dir/d -- 10883251
dir/e -- 10883252
dir/f -- 10883253
dir/g -- 10883254
dir/h -- 10883255
dir/i -- 10883256
dir/j -- 10883299
dir/k -- 10883302
dir/l -- 10883303
dir/m -- 10883311
dir/n -- 10883424
dir/o -- 10883426
dir/p -- 10883427

So we can see that the brace expansion used by touch creates the filenames in alphabetical order and so they're assigned sequential inode numbers when written to the HDD. (That however does not influence the order in the directory.)

Running your tar command multiple times would seem to indicate that there is an order to the list, since running it multiple times yields the same list each time. Here I've run it 100 times and then compared the runs and they're all identical.

$ for i in {1..100};do tar cJvf file.tar.xz dir/ > run${i};done
$ for i in {1..100};do cmp run1 run${i};done
$ 

If we strategically delete say dir/e and then add a new file dir/ee we can see that this new file has taken the place that dir/e occupied prior in the directories entries table.

$ rm dir/e
$ touch dir/ee

Now let's keep the output from one of the for loop above, just the 1st one.

$ mv run1 r1A

Now if we re-run the for loop that will run the tar command 100 times again, and compare this second run with the previous one:

$ sdiff r1A run1
dir/                                dir/
...
dir/c                               dir/c
dir/f                               dir/f
dir/e                             | dir/ee
dir/o                               dir/o
dir/2                               dir/2
...

We notice that dir/ee has taken dir/e's place in the directories table.

share|improve this answer
    
+1 nicely done sir. –  SparKot ॐ Mar 18 at 5:19
2  
I think it's filesystem dependent. I can imagine a btree-type filesystem sorting them based on order of file hash or some such (I have a sense the old ReiserFS orders them differently, since that filesystem dynamically creates inodes) –  samiam Mar 18 at 7:39
1  
@samiam - right, this answer claims that the 'directory order' is 'the creation order that the file entries in the directory's table were added' and then it itself shows fragments of the tar file contents showing that this is not true. Many filesystems, including current Linux ext* filesystems, use trees and/or hashes in their directory structures, not simple sequential tables like some older filesystems. –  Michał Politowski Mar 18 at 8:44
3  
@John ls -f or ls -U or find -maxdepth 1 –  Wumpus Q. Wumbley Mar 18 at 12:27
1  
@John the -f flag comes from ancient Unix. Its purpose was to be fast. It disabled sorting, the skipping of dotfiles, and a few other things. The -U flag is a GNU innovation which allows you to disable sorting without any other side effects. –  Wumpus Q. Wumbley Mar 18 at 15:57

readdir() bascially. When tar finds out what files are in a directory, it directly asks the kernel for a file listing via opendir() followed by readdir(). readdir() does not return the files in any particular order; the way the files are ordered depends on the file system being used by the Linux kernel.

There, alas, isn't an option for tar to sort files in subdirectories (adding one is left as an exercise for the reader).

share|improve this answer
    
I was wondering if it retrieves them based on their inode's value? –  slm Mar 18 at 4:23
1  
@slm The f_op->iterate call that glibc readdir() eventually filters down to via getdents() is mapped to a filesystem specific implementation. I can't see anything at a higher level that reorders the dirent's the fs implementation returns. –  mtm Mar 18 at 12:56
    
@slm No, I've never heard of a filesystem where the inode value would have an influence on the directory order. –  Gilles Mar 18 at 22:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.