1

When using du to get the total size of a folder, the command enumerates every file from every (sub)folder and adds it up, in my understanding.

yann@p:~$ du /var/log
4   /var/log/ntpstats
...
148 /var/log/apt
564 /var/log/installer
8   /var/log/cups
91748   /var/log

However, how can the df command return instantly results such as

Filesystem     1K-blocks      Used Available Use% Mounted on
/dev/sda1       35209808  18707476  14694008  57% /

without needing to enumerate all the files on the drive?

If there is a fast way to know the used space on a whole drive, then why is there no fast way to know the size of a folder? Or is there?

Thanks in advance.

3

dfuses the statvfs() system call and asks the filesystem for the current space statistics. This is of course fast as the filesystem always keeps track on the space used on the filesystem while it manages it.

So the reason for df being fast is that is uses precomputed cached values from the filesystem.

Here is the history:

In the 1970s, df has been a suid root program that did access the raw disk device and fetched the filesystem statistics from the super block.

In the mid 1980s, SunOS introduced the syscall statfs() together with the first VFS implementation. This call did not need privilleges anymore. This interface has been given to *BSD during the last SunOS/BSD code exchange in the Tahoe meeting.

In 1989, SVr4/Solaris introduced an enhanced VFS interface that renamed the syscall to statvfs(). This version of the syscall has been added to POSIX from where various OS copied the interface.

Since the df data is indirectly obtained from the super block that only has values for the whole filesystem, there is no quick way to get the numbers for a single directory.

  • IMO this does not answer the question. – ajeh May 24 '18 at 16:25
  • 2
    You are mistaken. – schily May 24 '18 at 16:44
  • The edit you've added kind of answers it, but still not in enough detail. – ajeh May 24 '18 at 17:03
  • Why this does not answer the question? Why df should access all the files to know how much space is used - this is ridiculous!, as it is registered everytime by the filesystem module on the filesystem information? So df just need to read this read-to-go information, i really don't see how this could not be a good explanation - as it is in fact what occurs... – Luciano Andress Martini May 24 '18 at 17:40
  • @ajeh The problem with going into much more detail is that it's both implementation and filesystem specific. statvfs() works differently on BSD from Linux, and differently on (for example) BTRFS from how it does on ext4. – Austin Hemmelgarn May 24 '18 at 19:57
2

The file system probably keeps a count of used and free data blocks as part of normal operation. df uses this information.

Even if the file system doesn't keep a real-time counter, it needs a quick way to find free blocks when writing new data, and that same data can also be used to find the number of free blocks.


In theory, some filesystem could keep such a used space counter on a per-directory basis, too. However, there are a few problems.

If the count was kept for the whole subtree recursively, the filesystem would need to propagate the usage numbers upwards to an arbitrary depth. That might slow down all write operations. If it was only kept for the files immediately within the directory, a recursive walk of the tree would still be required to find the total size of a tree.

On Unix-like filesystems, hard links are an even bigger obstacle. When a file can be linked to from multiple directories (or multiple times from the same directory), it has no unique parent directory. Where would the file's size be counted? Counting it on all directories that link to it would produce an inflated total usage, as the file could be counted multiple times. Counting it on only one directory would also be obviously wrong.

In fact, files (i.e. inodes) on traditional Unix filesystems don't even know the directories they reside in, only the count of links to them (names they have). In most usage, that information is not needed, since files are accessed primarily be name anyway. Storing it would also require an arbitrary amount of data in the inode, duplicating the data in the directories.

  • This does not answer the question as it does not give an explanation on the question why df is so fast. – schily May 24 '18 at 16:47
  • @schily, I read two questions in the Q. One on the title about how df works. I think that's answered in the first two paragraphs (the ones above the line), though I didn't mention df explicitly. The second is at the end of the Q's last paragraph: "why is there no fast way to know the size of a folder? Or is there?". The problems related to that I think I tried to answer in the rest of answer. Did I miss some other question? – ilkkachu May 24 '18 at 16:51
  • 1
    At the time you did write this, you did not give an explanation. You just copied from my answer after you wrote that comment. – schily May 24 '18 at 16:54
  • @schily, like I said, I didn't mention df explicitly. Instead, I told the underlying reason why it's easy to find the used space of the filesystem as a whole. I can remove the references to the system calls. If you're not happy, I suppose you can flag this for moderator attention as a blatant act of plagiarism. – ilkkachu May 24 '18 at 16:59
  • schily if that is true , this should not get good reputation for copying a user answer. right? – Luciano Andress Martini May 24 '18 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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