Design incremental linking

[davidlattimore]

I'm in the process of writing a design for incremental linking. I'll post a link to it here when done.

[davidlattimore]

Here's the design.. Do let me know if you have any questions for comments. Commenting on this issue is fine or use any other means to contact me.

[Alphare]

I'd like to offer some advice for this bit:

The first stage of diffing will be determining which files have changed. We could hash the entirety of each file, however, with lots of input files, that would be expensive, so instead the plan is to just check to see if the modification timestamp has changed.

This can turn out to be a lot more of a headache than could be expected. I've been recently reminded of this when rewriting parts of Mercurial in Rust to handle faster updates (read: checkout of a revision) and race conditions started to appear because the new code was too fast for the insufficient previous race handling.

For a linker this is fortunately simpler since you're never touching the source files yourself and only the user, but you could still have problems you may not be aware of yet, so I'll list the things I remember in case that saves you time and sanity:

• Some OS/FS pairs only provide second-level mtime granularity or worse for NFS
• Some OS/FS pairs don't provide inodes/inode generations
• OS/FS pairs that provide nanosecond-level mtime granularity (for example BTRFS on Linux) do not provide a guarantee that two changes to the same file will give a different timestamp¹. In fact, it's very easy to reproduce many changes to a file before getting a new timestamp².
• Some implementations return 0 for their nanoseconds, so you can't rely on this particular value for equality
• The easy fix is to remember the start time your linker for this project and re-check all files that have a timestamp that is >= to that of your start time³. This is the filesystem time, not the system clock, since you're trying to detect ambiguity in the filesystem.

I think that's all that's relevant to your use-case, but in case you ever find yourself stuck in this bit, you can send me an email and we can discuss this.

[1] Though there is some movement on this front in Linux: https://lore.kernel.org/all/20241002-mgtime-v10-8-d1c4717f5284@kernel.org [2] See this thread from 2011 by Mercurial's founder Olivia Mackall: https://lore.kernel.org/lkml/93A3B8BD-B4F0-4F07-8E34-7CCA08439AA6@dilger.ca/T/#mf16fb995af336e84223abe7c12f892cd2e685d75 [3] We do that for hg status: https://foss.heptapod.net/mercurial/mercurial-devel/-/blob/65d516db7309848a472bc236409460eae8922cdb/rust/hg-core/src/dirstate/entry.rs#L123

[kabergstrom]

Awesome to see work in this direction. Just wanted to offer an opinion on this:

Besides needing to copy our symbol names, sled does other things that we don’t really need like transactions.

Transactions ensure your on-disk data ends up in a consistent state in case of errors or unexpected events (i.e. power loss). If you persist data to disk in a custom file format, you ought to have a way to identify when your data isn't in a consistent state. Detecting bitrot is also important, and both cases can be solved with a checksum -- or use an embedded database.

On the topic of hash performance for change detection, there are great hash functions that can saturate per-core memory transfer speeds (GxHash, meowhash), meaning you'll mostly be limited by the throughput of the file reads. In the case of incremental linking, I think it's fair to assume all your input files will be resident in OS page cache. If you mmap input files that are in OS page cache, there's no IO or copying performed by the kernel as the pages will be mapped into your address space. The hash input bytes will be read directly from the cached pages and you'll probably hash at memory transfer speeds.

[davidlattimore]

Thanks @Alphare, that's useful info, which I'm sure I'll come back to refer to as I do that bit. My current design relies on me keeping a copy of the old file around, which I'm intending to do via a hard link. I wonder if I can just check to see if the new file and our copy refer to the same file. On Linux, that would presumably be just checking the inode of each. On Windows it looks like it's possible to list the hard links of a file.

[davidlattimore]

Thanks @kabergstrom for the feedback!

Regarding unexpected events like power loss, my plan is to detect that an incomplete link occurred and just start from scratch.

Hashing all the input files, even if they're in cache would be pretty expensive. Just mapping and unmapping files in memory has a cost. For example, when Wild links clang (the C compiler), it takes 38 ms to unmap all the input files. That's more than 10% of the total time (285 ms). For linking clang with debug info, unmapping the input files takes 657 ms. I don't have numbers for how long it takes to page in all the inputs, because the paging in happens lazily as the pages are accessed, but presumably it's similar.