HN Explorer

Show HN: Dut – a fast Linux disk usage calculator (codeberg.org)

396 points by 201984 ↗ HN
"dut" is a disk usage calculator that I wrote a couple months ago in C. It is multi-threaded, making it one of the fastest such programs. It beats normal "du" in all cases, and beats all other similar programs when Linux's caches are warm (so, not on the first run). I wrote "dut" as a challenge to beat similar programs that I used a lot, namely pdu[1] and dust[2].

"dut" displays a tree of the biggest things under your current directory, and it also shows the size of hard-links under each directory as well. The hard-link tallying was inspired by ncdu[3], but I don't like how unintuitive the readout is. Anyone have ideas for a better format?

There's installation instructions in the README. dut is a single source file, so you only need to download it and copy-paste the compiler command, and then copy somewhere on your path like /usr/local/bin.

I went through a few different approaches writing it, and you can see most of them in the git history. At the core of the program is a datastructure that holds the directories that still need to be traversed, and binary heaps to hold statted files and directories. I had started off using C++ std::queues with mutexes, but the performance was awful, so I took it as a learning opportunity and wrote all the datastructures from scratch. That was the hardest part of the program to get right.

These are the other techniques I used to improve performance:

* Using fstatat(2) with the parent directory's fd instead of lstat(2) with an absolute path. (10-15% performance increase)

* Using statx(2) instead of fstatat. (perf showed fstatat running statx code in the kernel). (10% performance increase)

* Using getdents(2) to get directory contents instead of opendir/readdir/closedir. (also around 10%)

* Limiting inter-thread communication. I originally had fs-traversal results accumulated in a shared binary heap, but giving each thread a binary-heap and then merging them all at the end was faster.

I couldn't find any information online about fstatat and statx being significantly faster than plain old stat, so maybe this info will help someone in the future.

[1]: https://github.com/KSXGitHub/parallel-disk-usage

[2]: https://github.com/bootandy/dust

[3]: https://dev.yorhel.nl/doc/ncdu2, see "Shared Links"

152 comments

[ 4.0 ms ] story [ 216 ms ] thread
kccqzy
I'm away from my Linux machine now but I'm curious whether/how you handle reflinks. On a supported file system such as Btrfs which I use, how does `cp --reflink` gets counted? Similar to hard links? I'm curious because I use this feature extensively.
201984
I've actually never heard of --reflink, so I had to look it up. `cp` from coreutils uses the FICLONE ioctl to clone the file on btrfs instead of a regular syscall.

I don't handle them specifically in dut, so it will total up whatever statx(2) reports for any reflink files.

vlovich123
You’ll probably end up with dupes (and removing these files won’t have the effect you intend) but I don’t know that there’s a good way to handle and report such soft links anyway.
namibj
Btdu will be you friend.
hsbauauvhabzb
This looks handy. Do you have any tips for stuff like queued ‘mv’ or similar? If I’m moving data around on 3-4 drives, it’s common where I’ll stack commands where the 3rd command may free up space for the 4th to run successfully - I use && a to ensure a halt on failure, but I need to mentally calculate the space free when I’m writing the commands as the free space after the third mv will be different to the output of ‘df’ before any of the commands have run.
201984
I haven't run into a situation like that, but if I did, I'd be doing mental math like you. `dut` would only be useful as a (quicker) replacement for `du` for telling you how large the source of a `cp -r` is.
timrichard
Looks nice, although a feature I like in ncdu is the 'd' key to delete the currently highlighted file or directory.
201984
This isn't an interactive program, so ncdu would be better for interactively going around and freeing up space. If you just want an overview, though, then dut runs much quicker than ncdu and will show large files deep down in subdirectories without having to go down manually.
notarealllama
If this accurately shows hidden stuff, such as docker build cache and old kernels, then it will become my go-to!
201984
As long as it has permissions, it totals up everything under the directory you give it including names that start with a '.'. It won't follow symlinks though.
nottorp
Uh, even basic du "shows hidden stuff" accurately doesn't it?

dot files are just a convention on unix.

jepler
did you consider using io_uring? if not, was there a reason other than portability?
201984
io_uring doesn't support the getdents syscall, so there's no way to traverse the filesystem with it. I considered using it for statx(2) to get the disk usage of each file, but decided not to because (a) it would be complicated to mix normal syscalls and io_uring and (b) perf showed the kernel spending most of its time doing actual work and not syscall boilerplate.
jepler
I appreciate the explanation!
nh2
Are you sure the perf may not be misleading?

E.g. memory accesses might show up as slower die to CPU caches being flushed when switching between user and kernel space.

I would be extremely interested in a quick (standalone?) benchmark of e.g. 1M stats with vs without uring.

Also https://github.com/tdanecker/iouring-getdents reports big uring speedups for getdents, which makes it surprising to get no speedups for stat.

If uring turns out fast, you might ignore (a), just doing the getdents first and then all stats afterwards. Since getdents is a "batch" syscalls covering many files anyway, but stat isn't.

montroser
Nice work. Some times I wonder if there's any way to trade away accuracy for speed? Like, often I don't care _exactly_ how many bytes is the biggest user of space, but I just want to see some orders of magnitude.

Maybe there could be an iterative breadth-first approach, where first you quickly identify and discard the small unimportant items, passing over anything that can't be counted quickly. Then with what's left you identify the smallest of those and discard, and then with what's left the smallest of those, and repeat and repeat. Each pass through, you get a higher resolution picture of which directories and files are using the most space, and you just wait until you have the level of detail you need, but you get to see the tally as it happens across the board. Does this exist?

201984
Thanks!

What you described is a neat idea, but it's not possible with any degree of accuracy AFAIK. To give you a picture of the problem, calculating the disk usage of a directory requires calling statx(2) on every file in that directory, summing up the reported sizes, and then recursing into every subdirectory and starting over. The problem with doing a partial search is that all the data is at the leaves of the tree, so you'll miss some potentially very large files.

Picture if your program only traversed the first, say, three levels of subdirectories to get a rough estimate. If there was a 1TB file down another level, your program would miss it completely and get a very innaccurate estimate of the disk usage, so it wouldn't be useful at all for finding the biggest culprits. You have the same problem if you decide to stop counting after seeing N files, since file N+1 could be gigantic and you'd never know.

montroser
Yeah, maybe approximation is not really possible. But it still seems like if you could do say, up to 1000 stats per directory per pass, then running totals could be accumulated incrementally and reported along the way.

So after just a second or two, you might be able to know with certainty that a bunch of small directories are small, and then that a handful of others are at least however big has been counted so far. And that could be all you need, or else you could wait longer to see how the bigger directories play out.

geertj
You would still have to getdents() everything but this way you may indeed save on stat() operations, which access information that is stored separately on disk and eliminating these would likely help uncached runs.

You could sample files in a directory or across directories to get an average file size and use the total number of files from getdents to estimate a total size. This does require you to know if a directory entry is a file or directory, which the d_type field gives you depending on the OS, file system and other factors. An average file size could also be obtained from statvfs().

Another trick is based on the fact that the link count of a directory is 2 + the number of subdirectories. Once you have seen the corresponding number of subdirectories, you know that there are no more subdirectories you need to descend into. This could allow you to abort a getdents for a very large directory, using eg the directory size to estimate the total entries.

olddustytrail
> Another trick is based on the fact that the link count of a directory is 2 + the number of subdirectories.

For anyone who doesn't know why this is, it's because when you create a directory it has 2 hard links to it which are

    dirname
    dirname/.
When you add a new subdirectory it adds one more link which is

    dirname/subdir/..
So each subdirectory adds one more to the original 2.
BeeOnRope
This seems difficult since I'm not aware of any way to get approximate file sizes, at least with the usual FS-agnostic system calls: to get any size info you are pretty much calling something in the `stat` family and at that point you have the exact size.
fsckboy
i thought files can be sparse and have holes in the middle where nothing is allocated, so the file size is not what is used to calculate usage, it's the sum of the extents or some such.
BeeOnRope
Yes, files can be sparse but the actual disk usage information is also returned by these stat-family calls, so there is no special cost to handling sparse files.
mos_basik
Something like that exists for btrfs; it's called bdtu. It has the accuracy/time trade-off you're interested in, but the implementation is quite different. It samples random points on the disk and finds out what file path they belong to. The longer it runs the more accurate it gets. The readme is good at explaining why this approach makes sense for btrfs and what its limitations are.

https://github.com/CyberShadow/btdu

renewiltord
Damn, `ext4` is organized differently entirely. You can't get anything useful from:

    sudo debugfs -R "icheck $RANDOM" /dev/nvme1
    sudo debugfs -R "ncheck $res" /dev/nvme1
and recursing. That's a clever technique given btrfs structs.
oehpr
That is so cool!!! I have always wanted something like this! Arg I wish other filesystems supported a strategy like this!
lenkite
Wish modern filesystems maintained usage per dir as a directory file attribute instead of mandating tools to do this basic job.
hsbauauvhabzb
This is an excellent point and I wholeheartedly agree!
masklinn
Is it? That would require any update to any file to cascade into a bunch of directory updates amplifying the write and for what? Do you “du” in your shell prompt?

Not to mention it would likely be unable to handle the hardlink problem so it would consistently be wrong.

IsTom
> That would require any update to any file to cascade into a bunch of directory updates amplifying the write and for what?

You can be a little lazy about updating parents this and have O(1) update and O(1) amortized read with O(n) worst case (same as now anyway).

aidenn0
This is probably the right solution, but tou need to rebuild on an unclean unmount if you do it lazily.
hsbauauvhabzb
Disks have improved in I/O and write speed metrics substantially to the point where windows will literally index your file system so you can search faster, and antivirus will scan files in the background before you open them. I don’t think maintaining size state on directories would be all that much of a challenge.
Someone
I expect performance would suffer quite a lot. In a system with high I/O, there would be a lot of contention on updating the size of such directories as /home or /tmp, let alone /.

Also, are you going to update a file’s size for every write (could easily be a thousand times if you’re copying over a 10MB file) or are you going to coalesce updates to file sizes? If the latter, how do you recover after a crash?

Virtual directories such as /dev and /proc would require special-casing.

Mounting and unmounting disks probably would require special-casing.

hsbauauvhabzb
Haven’t many similar issues been solved in journaled file systems and/or things like database transaction logs and indexes? Real-time high precision accuracy is not required, knowing how big a directory is, is a frequent use case of directories. Hell, ‘df’ tracks this at the partition level, including edge cases, as does ‘du’
Someone
As far as I am aware, neither of those cascade sizes up.

Also, doing that in databases isn’t a solved problem. count(*) can be slow in databases. See for example

- PostgreSQL: https://dba.stackexchange.com/questions/314371/count-queries..., https://wiki.postgresql.org/wiki/Count_estimate

- Oracle: https://forums.oracle.com/ords/apexds/post/select-count-very...

(Both databases use MVCC (https://en.wikipedia.org/wiki/Multiversion_concurrency_contr...) to ensure that concurrent queries all see the database in a consistent state. That makes it necessary to visit each row and check their time stamp when counting rows)

aidenn0
I have a "du" command currently running that has been running for ~50 hours. I'd much rather have it update a half-dozen directory entries on each write.
nh2
CephFS does that.

You can use getfattr to ask it for the recursive number of entries or bytes in a given directory.

Querying it is constant time, updates update it with a few seconds delay.

Extremely useful when you have billions of files on spinning disks, where running du/ncdu would take a month just for the stat()s.

[deleted]
(comment deleted)
chomp
GPLv3, you love to see it. Great work.
jeffbee
It's also interesting that the perf report for running dut on my homedir shows that it spends virtually all of the time looking for, not finding, and inserting entries in dentry cache slabs, where the entries are never found again, only inserted :-/ Great cache management by the kernel there.

ETA: Apparently the value in /proc/sys/vm/vfs_cache_pressure makes a huge difference. With the default of 100, my dentry and inode caches never grow large enough to contain the ~15M entries in my homedir. Dentry slabs get reclaimed to stay < 1% of system RAM, while the xfs_inode slab cache grows to the correct size. The threads in dut are pointless in this case because the access to the xfs inodes serializes.

If I set this kernel param to 15, then the caches grow to accommodate the tens of millions of inodes in my homedir. Ultimately the slab caches occupy 20GB of RAM! When the caches are working the threading in dut is moderately effective, job finishes in 5s with 200% CPU time.

201984
Are you referring to the kmem_cache_alloc calls in the profile? If so, that's all in kernel space and there's nothing I can do about it.

https://share.firefox.dev/3XT9L7P

jeffbee
No, see how your profiles have `lookup_fast` at the leaves? Mine has `__lookup_slow` and it is slow indeed.
201984
I just saw your edit. You have WAY more stuff under your home directory than I do. I only have ~2.5M inodes on both my laptop drives combined. The difference in the buff/cache output of `free` before and after running `dut` is only 1 GB for me.

Also, TIL about that kernel parameter, thanks!

jeffbee
Yeah I have a TB of bazel outputs in my cache directory. Unfortunately automatically deleting old bazel outputs is beyond the frontier of computer science and has been pushed out to future releases for 6 years and still going: https://github.com/bazelbuild/bazel/issues/5139
jftuga
You should include the "How to build" instructions near the beginning of the main.c file.
teamspirit
Nice job. I've been using dua[0] and have found it to be quite fast on my MacBook Pro. I'm interested to see how this compares.

[0] https://github.com/Byron/dua-cli

201984
I benchmarked against dua while developing, and the results are in the README. Note that dut uses Linux-specific syscalls, so it won't run on MacOS.

TL;DR: dut is 3x faster with warm caches, slightly faster on SSD, slightly slower on HDD.

IAmLiterallyAB
I'm surprised statx was that much faster than fstatat. fstatat looks like a very thin wrapper around statx, it just calls vfs_statx and copies out the result to user space.
201984
Out of curiosity, I switched it back to fstatat and compared, and found no significant difference. Must've been some other change I made at the time, although I could've sworn this was true. Could be a system update changed something in the three months since I did that. I can't edit my post now though, so that wrong info is stuck there.
[deleted]
(comment deleted)
jmakov
Would be great to have a TUI interface for browsing like ncdu.
jonhohle
Did you consider the fts[0] family of functions for traversal? I use that along with a work queue for filtered entries to get pretty good performance with dedup[1]. For my use case I could avoid any separate stat call altogether, the FTSENT already provided everything I needed.

0 - https://linux.die.net/man/3/fts_read

1 - https://github.com/ttkb-oss/dedup/blob/6a906db5a940df71deb4f...

nh2
fts is just wrapper functions.

You cannot around getdents and stat family syscalls on Linux if you need file sizes.

201984
Those are single threaded, so they would have kneecapped performance pretty badly. 'du' from coreutils uses them, and you can see the drastic speed difference between that and my program in the README.
dima55
Ideas for a better format: do what xdiskusage does.
metadat
What specifically do you feel xdiskusage does well?
dima55
It graphically displays the relative sizes of things, and allows you to interactively zoom into any particular subdirectory to see the relative sizes of the things inside it
shellfishgene
What I need is a du that caches the results somewhere and then does not rescan the 90% of dirs that have not changed when I run it again a month later...
kstrauser
And it would know they did not change without scanning them because how?
svpg
It could hash the contents of a dir. Along the lines of git
Galanwe
Except hashing requires... reading.

There is not much to be done here. Directories entries are just names, no guarantees that the files were not modified or replaced.

The best you could do is something similar to the strategies of rsync, rely on metadata (modified date, etc) and cross fingers nobody did `cp -a`.

shellfishgene
I would be fine with the latter, the program could display a warning like "Results may be inaccurate, full scan required" or something.

I guess I'm just annoyed that for Windows/NTFS really fast programs are available but not for Linux filesystems.

legends2k
And to hash something needs reading all of its data. I think deducing the file size would actually be faster in some file systems and never slower with any.
mort96
Faster in all file systems I'd guess, stat is fast, opening the file and reading its contents and updating a checksum is slow, and gets slower the larger the file is.
[deleted]
(comment deleted)
shellfishgene
Maybe it could run in the background and use inotify to just update the database all the time, or at least keep track of what needs rescanning?
shellfishgene
Thinking about this some more, does this system not already exist for the disk quota calculation in the kernel? How does that work? Would it be possible for a tool to scan the disk once, and then get information about file modifications from the system that's used to update quota info?
anon-3988
I have been using diskonaut, its fast enough given that it also produces a nice visual output.
rafaelgoncalves
neat tool, congrats on the release and thank you for this and the analysis/comparison.
mg
I have this in my bashrc:

    alias duwim='du --apparent-size -c -s -B1048576 * | sort -g'
It produces a similar output, showing a list of directories and their sizes under the current dir.

The name "duwim" stands for "du what I mean". It came naturally after I dabbled for quite a while to figure out how to make du do what I mean.

mixmastamyk
Not as featureful, but what I've been using. If you can't install this tool for some reason, it's still useful. I call it usage:

    #!/bin/bash

    du -hs * .??* 2> /dev/null | sort -h | tail -22
tamimio
Someone, please create a Gdut, a fork that will produce graphs for a quick and easy way to read, it’s almost impossible to read in small vertical screens.
nh2
> I don't know why one ordering is better than the other, but the difference is pretty drastic.

I have the suspicion that some file systems store stat info next to the getdents entries.

Thus cache locality would kick in if you stat a file after receiving it via getdents (and counterintuitively, smaller getdents buffers make it faster then). Also in such cases it would be important to not sort combined getdents outputs before starting (which would destroy the locality again).

I found such a situation with CephFS but don't know what the layout is for common local file systems.

miew
Why C and not Rust or even Zig?
Galanwe
Why Rust or Zig and not C?
nottorp
Better for the author's resume, if they want to make it hype driven.

Also some nebulous "being more secure". Never mind that this tool does not have elevated privileges. You gotta watch out for those remote root exploits even for a local only app, man.

_flux
I mean you could extract an archive you've downloaded to your filesystem and said archive could have funky file names and then you use this tool..

But I suppose it's not a very likely bug to have in this kind of tool.

nottorp
Or “they” could enter your house at 2 am, drug you and hit you with a $5 wrench until they get access to your files :)
gsck
Never understood this line of thought. Not everything needs to be super secure. Not everything is going to be an attack vector. No one is going to deploy this onto a production server where this program specifically is going to be the attack vector.

Memory safety is cool and all, but a program that effectively sums a bunch of numbers together isn't going to cause issues. Worst case the program segfaults

craftoman
Because C is like a cult Toyota Supra with twin turbo and Rust or Zig is like another cool boring Corvette roadster.
201984
Because (a) I felt like it, (b) it would be more difficult to make raw syscalls in Rust, and (c) I use[1] flexible array members to minimize allocations, whereas Rust support for those quite bad[2]. It doesn't even look possible to allocate one with size known at runtime.

[1]: https://codeberg.org/201984/dut/src/branch/master/main.c#L16...

[2]: https://doc.rust-lang.org/nomicon/exotic-sizes.html#dynamica...

estebank
> it would be more difficult to make raw syscalls in Rust

Would you like to expand on this? Is it because of type conversions that you'd have to do?

> I use[1] flexible array members to minimize allocations

I was under the impression that FAM was a non-standard extension, but alas it is part of C99.

From what I'm seeing you have intrusive list where each `entry` points to the previous and next element, where the path itself is a bag of bytes as part of the entry itself. I'm assuming that what you'd want from Rust is something akin to the following when it comes to the path?

    struct Entry<const NAME_LEN: usize> {
        ..
 mode: Mode,
 name: InlineName<NAME_LEN>,
    }

    struct InlineName<const NAME_LEN: usize> {
 value: [u8; NAME_LEN],
    }
201984
For syscalls, I would have needed to either pull in dependencies or write FFI bindings, and neither of those options are appealing when I could simply write the program in Linux's native language.

For the FAM, your example looks like it requires a compile-time constant size. That's the same as hardcoding an array size in the struct, defeating the whole point. Short names will waste space, and long ones will get truncated.

estebank
> For the FAM, your example looks like it requires a compile-time constant size. That's the same as hardcoding an array size in the struct, defeating the whole point. Short names will waste space, and long ones will get truncated.

You made me realize that the const generics stabilization work hasn't advanced enough to do what I was proposing (at least not in as straightforward way): https://play.rust-lang.org/?version=nightly&mode=debug&editi...

Those are const arguments, not const values, which means that you can operate on values as if they didn't have a size, while the compiler does keep track of the size throughout.

I'd have to take a more detailed look to see if this level of dynamism is enough to work with runtime provided strings, which they might not be, unless you started encoding things like "take every CStr, create a StackString<1> for each char, and then add them together".

estebank
This is not an appropriate question to ask, that I see sometimes in these threads. "Because the author wanted" is good enough a reason for them to write a program in C. It being a new project written in C can also be good enough reason for you not to use it: dust already exists and is written in Rust, which you can use instead.
trustno2
Does it depend on linux functionality or can I use it on macos?

Well I can just try :)

Ringz
From the author:

„Note that dut uses Linux-specific syscalls, so it won't run on MacOS.“