commit 90ccc9b0f4c1ab0d69919657d991d6b4fa842730
parent b612a0a8d351cbd4631354ede35479e696a8d266
Author: Jack Mordaunt <jackmordaunt.dev@gmail.com>
Date: Sun, 20 Sep 2026 09:46:13 -0300
walk: read directories with linux syscalls
core:os describes every entry in full: an fd opened and closed around it, a statx
on that fd, and the entry's path read back through /proc/self/fd. Four syscalls
where one statx against the directory answers everything the tree records.
Walking 14,478 entries cost 64,235 calls against du's 21,511, and the procfs
readlink was over half of it. It now costs 18,122, fewer than du. /usr falls from
272 ms to 83 ms at eight workers and 1560 to 480 at one; eight is still the knee.
statx reports allocated blocks as readily as length, so the on-disk figure is
exact rather than the length rounded to a guessed block. A 1 GiB sparse file was
charged 1 GiB and is now charged what it occupies, agreeing with du.
Diffstat:
| D | walk/read.odin | | | 70 | ---------------------------------------------------------------------- |
| A | walk/read_linux.odin | | | 119 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | walk/read_other.odin | | | 71 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
3 files changed, 190 insertions(+), 70 deletions(-)
diff --git a/walk/read.odin b/walk/read.odin
@@ -1,70 +0,0 @@
-package walk
-
-import "core:os"
-import "core:strings"
-
-/*
-Read one directory through core:os.
-
-The portable reader: whatever the platform, core:os describes every entry and this
-records what the tree keeps. It asks for a great deal more than that per entry, which
-is the cost of not knowing which platform it is on.
-*/
-@(private)
-read_dir :: proc(d: Dir, w: ^Worker) -> (nodes, bytes: u64, ok: bool) {
- f, open_err := os.open(d.path)
- if open_err != nil {
- return 0, 0, false
- }
- defer os.close(f)
-
- it := os.read_directory_iterator_create(f)
- defer os.read_directory_iterator_destroy(&it)
-
- for info in os.read_directory_iterator(&it) {
- if _, err := os.read_directory_iterator_error(&it); err != nil {
- continue
- }
- e := Entry {
- name = info.name,
- size = u64(max(info.size, 0)),
- directory = info.type == .Directory,
- symlink = info.type == .Symlink,
- }
- if !e.directory && !e.symlink {
- // core:os reports the logical length and nothing about allocation, so the
- // on-disk figure is the best estimate available here: the size rounded up
- // to a block.
- e.disk = round_up(e.size, BLOCK_ESTIMATE)
- }
- index, descend, recorded := record(w, d.index, e)
- if !recorded {
- return nodes, bytes, false
- }
- if descend {
- path, clone_err := strings.clone(info.fullpath, w.allocator)
- if clone_err != nil {
- w.err = .Out_Of_Memory
- return nodes, bytes, false
- }
- append(&w.found, Dir{index = index, path = path})
- }
- nodes += 1
- bytes += e.disk
- }
- return nodes, bytes, true
-}
-
-// Without filesystem-specific knowledge the allocation unit is a guess, and four
-// kilobytes is the common one. It makes small files cost something rather than
-// nothing, which matters more than being exactly right.
-@(private)
-BLOCK_ESTIMATE :: 4096
-
-@(private)
-round_up :: proc(v, unit: u64) -> u64 {
- if v == 0 {
- return 0
- }
- return (v + unit - 1) / unit * unit
-}
diff --git a/walk/read_linux.odin b/walk/read_linux.odin
@@ -0,0 +1,119 @@
+#+build linux
+package walk
+
+import "core:mem"
+import "core:strings"
+import "core:sys/linux"
+
+/*
+Read one directory with the calls the work actually needs.
+
+core:os describes every entry in full: an fd opened and closed around it, a statx on
+that fd, and the entry's path read back through /proc/self/fd. Four syscalls, where
+one statx against the directory answers everything the tree records. Walking 14,478
+entries cost 64,235 calls that way against du's 21,511 for the same tree, and the
+procfs readlink was over half of it.
+
+getdents also names each entry's type, so most are settled without asking again, and
+statx reports allocated blocks as readily as length. That makes the on-disk figure
+exact here rather than the length rounded up to a guessed block, so a sparse or
+compressed file is charged what it occupies.
+*/
+@(private)
+read_dir :: proc(d: Dir, w: ^Worker) -> (nodes, bytes: u64, ok: bool) {
+ path: Path
+ cpath, path_ok := terminate(d.path, &path)
+ if !path_ok {
+ return 0, 0, false
+ }
+ // Not NOFOLLOW: the queue holds directories, and symlinks only when the caller
+ // asked for those to be followed, so refusing a link here would refuse exactly
+ // the ones it was told to walk. DIRECTORY still rejects a link onto a file.
+ fd, open_errno := linux.open(cpath, {.DIRECTORY, .CLOEXEC})
+ if open_errno != .NONE {
+ return 0, 0, false
+ }
+ defer linux.close(fd)
+
+ // Sized so a directory of any ordinary size comes back in one call. core:os
+ // starts at 512 bytes and grows only when the kernel refuses, which cost it
+ // roughly twice the getdents calls for the same tree.
+ buf: [32 * mem.Kilobyte]u8
+ for {
+ n, errno := linux.getdents(fd, buf[:])
+ if errno != .NONE {
+ return nodes, bytes, false
+ }
+ if n == 0 {
+ return nodes, bytes, true
+ }
+ offset := 0
+ for entry in linux.dirent_iterate_buf(buf[:n], &offset) {
+ name := linux.dirent_name(entry)
+ if name == "." || name == ".." {
+ continue
+ }
+ e := Entry {
+ name = name,
+ directory = entry.type == .DIR,
+ symlink = entry.type == .LNK,
+ }
+ // The name sits in the buffer already terminated, so it addresses the
+ // entry without being copied anywhere first.
+ mask := linux.Statx_Mask{.TYPE, .SIZE, .BLOCKS}
+ st: linux.Statx
+ if linux.statx(fd, cstring(raw_data(name)), {.SYMLINK_NOFOLLOW}, mask, &st) == .NONE {
+ // Some filesystems leave the type out of a directory entry. Those are
+ // the only ones that have to be told apart here.
+ if entry.type == .UNKNOWN {
+ e.directory = linux.S_ISDIR(st.mode)
+ e.symlink = linux.S_ISLNK(st.mode)
+ }
+ e.size = st.size
+ if !e.directory && !e.symlink {
+ // Blocks are counted in 512 byte units whatever the filesystem
+ // builds them from.
+ e.disk = st.blocks * 512
+ }
+ }
+ index, descend, recorded := record(w, d.index, e)
+ if !recorded {
+ return nodes, bytes, false
+ }
+ if descend {
+ child, join_err := join(d.path, name, w.allocator)
+ if join_err != nil {
+ w.err = .Out_Of_Memory
+ return nodes, bytes, false
+ }
+ append(&w.found, Dir{index = index, path = child})
+ }
+ nodes += 1
+ bytes += e.disk
+ }
+ }
+}
+
+// A path as the kernel wants it. Long enough for anything the kernel will accept, so
+// building one costs no allocation.
+@(private)
+Path :: [4096]u8
+
+@(private)
+terminate :: proc(path: string, buf: ^Path) -> (cstring, bool) {
+ if len(path) >= len(buf) {
+ return nil, false
+ }
+ copy(buf[:], path)
+ buf[len(path)] = 0
+ return cstring(&buf[0]), true
+}
+
+// The child's path, which getdents does not hand back and the queue needs.
+@(private)
+join :: proc(dir, name: string, allocator: mem.Allocator) -> (string, mem.Allocator_Error) {
+ if strings.has_suffix(dir, "/") {
+ return strings.concatenate({dir, name}, allocator)
+ }
+ return strings.concatenate({dir, "/", name}, allocator)
+}
diff --git a/walk/read_other.odin b/walk/read_other.odin
@@ -0,0 +1,71 @@
+#+build !linux
+package walk
+
+import "core:os"
+import "core:strings"
+
+/*
+Read one directory through core:os.
+
+The reader that works anywhere. core:os describes every entry in full and this keeps
+the part the tree records, which is most of what it costs: not knowing the platform
+means not knowing which of that description was worth asking for.
+*/
+@(private)
+read_dir :: proc(d: Dir, w: ^Worker) -> (nodes, bytes: u64, ok: bool) {
+ f, open_err := os.open(d.path)
+ if open_err != nil {
+ return 0, 0, false
+ }
+ defer os.close(f)
+
+ it := os.read_directory_iterator_create(f)
+ defer os.read_directory_iterator_destroy(&it)
+
+ for info in os.read_directory_iterator(&it) {
+ if _, err := os.read_directory_iterator_error(&it); err != nil {
+ continue
+ }
+ e := Entry {
+ name = info.name,
+ size = u64(max(info.size, 0)),
+ directory = info.type == .Directory,
+ symlink = info.type == .Symlink,
+ }
+ if !e.directory && !e.symlink {
+ // core:os reports the logical length and nothing about allocation, so the
+ // on-disk figure is the best estimate available here: the size rounded up
+ // to a block.
+ e.disk = round_up(e.size, BLOCK_ESTIMATE)
+ }
+ index, descend, recorded := record(w, d.index, e)
+ if !recorded {
+ return nodes, bytes, false
+ }
+ if descend {
+ path, clone_err := strings.clone(info.fullpath, w.allocator)
+ if clone_err != nil {
+ w.err = .Out_Of_Memory
+ return nodes, bytes, false
+ }
+ append(&w.found, Dir{index = index, path = path})
+ }
+ nodes += 1
+ bytes += e.disk
+ }
+ return nodes, bytes, true
+}
+
+// Without filesystem-specific knowledge the allocation unit is a guess, and four
+// kilobytes is the common one. It makes small files cost something rather than
+// nothing, which matters more than being exactly right.
+@(private)
+BLOCK_ESTIMATE :: 4096
+
+@(private)
+round_up :: proc(v, unit: u64) -> u64 {
+ if v == 0 {
+ return 0
+ }
+ return (v + unit - 1) / unit * unit
+}
