@SRAZKVT you can use my fractal zip format for this purpose actually (one of the design goals was representing a dataset with changes over time). that's actually a really fascinating corollary of using it to represent atomic transitions between reproducible filesystem states....................i did not realize that VCS is precisely a formulation of atomic filesystem transactions. need to think about this further
Replies:
0
this is all trying to dance around two very subtle points that require a very specialized technical understanding of cryptography to infer:
- the signing keys are secret because downstream distro packagers and/or corporate sysadmins are the malicious actors which module signatures protect against!
- more importantly, cryptographic signatures are just unspoofable checksums!
the fact that they're not "reproducible" is because they use secret data (the private key) to stop "malicious actors" from generating new checksums for "modified loadable modules"!
claiming a cryptographic signature is "nonreproducible" is a non sequiter--they are literally just a list of module checksums. it's the exact same fucking thing, except there is an additional cryptographic proof that modules haven't been modified since they left the custody of the key owner.
lwn, kpcyrd, Thomas Weißschuh, and everyone associated with the module hashing for "reproducibility" is either completely unaware of how cryptography works (and therefore should not be trusted with crypto), or they are lying in order to backdoor linux users (and therefore should not be trusted with crypto)
so here's the answer:
- we build the kernel, then build the modules, then checksum the modules. this gets us checksums for the filesystem tree just before we introduce the secret data.
- we verify the module checksums correspond to the ones produced by kernel maintainers by decrypting the published signatures with their public key. this is a stronger form of build reproducibility!
[in fact, this alone should be sufficient, because the kernel build process should be able to delay module signing until the very end. but for completeness, let's walk through how tree hashing lets us swap out a specific intermediate change and verify the result is correct.]
so our problem now can be decomposed into three stages:
(a) the filesystem state of the kernel build tree right before generating signatures can be checksummed in any way.
(b) adding module signatures is represented as a (normalized) filesystem delta (git can generate this).
(c) the result of the kernel build process continues until completion. generate a normalized delta for the filesystem state change from (b) to (c) with git diff.
the key insight here: unless signatures are copied into more than one place, the delta from (b) to (c) should not depend upon any secret data. so, reproducibility is ensured by:
- matching the checksum of the filesystem state at point (a).
- matching the module checksums against the checksums decrypted against maintainer public keys from the upstream signatures.
- matching the checksum of the filesystem delta from (b) to (c)!
that actually still doesn't require any tree hashing either! but even if we absolutely cannot be assed to split the kernel build process into discrete a/b/c phases, or if the signature data from (b) influences the filesystem delta from (b) to (c) (e.g. if the signatures are copied into a text file), we can still make this shit 100000% reproducible, without any cryptography at all!
how? by simply erasing the signatures! take the upstream kernel build tree filesystem state, then replace any signature data with an equivalent length of zero bits (i.e. zero out the signatures). calculate the resulting checksum from upstream! do the same thing for downstream! YOUR CHECKSUMS WILL MATCH!
of course, this requires identifying the precise regions of data corresponding to signatures. but the kernel already knows this, because it has to read from those exact regions in order to validate module signatures upon load!
i believe the longer-term answer to "reproducible builds" involves OS-level support for filesystem checkpointing, per-process isolation of i/o state, and a deterministic ordering along with transactional semantics for propagating a series of i/o operations as an atomic filesystem delta.
which is to say: reproducible builds require reproducible process executions. and that requires per-process isolation of filesystem state.
@hipsterelectron plan9 has per process filesystems ig
@SRAZKVT keyKOS kinda does
@SRAZKVT omg ugh NOBODY ever tries the literal only thing i want for perf optimization https://doc.cat-v.org/plan_9/4th_edition/papers/fs/
The file system server processes prevent deadlock in the buffers by always locking parent and child directory entries in that order. Since the entire directory structure is a hierarchy, this makes the locking well-ordered, preventing deadlock. The major problem in the locking strategy is that locks are at a block level and there are many directory entries in a single block. There are unnecessary lock conflicts in the directory blocks. When one of these directory blocks is tied up accessing the very slow WORM, then all I/O to dozens of unrelated directories is blocked.
@SRAZKVT literally i'm so upset bc:
- making my writes visible to other processes should absolutely happen in an atomic transaction
- persisting my writes to disk is (1) a completely different fucking thing than IPC (2) should also happen atomically
@SRAZKVT literally nobody has ever asked filesystems to act like a lock-free OS-global hash table. that's a ConcurrentHashMap that's not a "filesystem"
@hipsterelectron well there's a reason why ska, navi, mercurial, git, and i all use it as a hashmap
@SRAZKVT do git/ska/navi/hg/you map pages with DIRECT_IO for that?
@SRAZKVT thanks for identifying this, that's definitely worth supporting (direct block writes) but i feel like that would make more sense to expose as a completely separate resource from the standard filesystem tree.
hmmmmmm actually, i'm not sure about that! if i want transactional semantics across file paths, i also want transactional semantics within a single file path. the pattern of explicit resource request => blocking commit syscall to establish ordered transaction boundaries should be able to apply to changes within a single file too.
and if my goal is to synchronize changes to disk as a transaction (as opposed to just IPC propagation), then i should have to specify that when i request a sync context to expose to a process (e.g. within a subprocess spawn call). cc @miss_rodent
@SRAZKVT @miss_rodent i also think a subprocess spawn should be a two-phase operation. first identify the sync context(s?), the imported paths from each, the executable path among those imports, the command line, the environment, and any initial export paths per sync context, and then the sync domain for each (in-memory, disk-persisted, both, maybe remote mirroring too?).
that initial "spawn" call would return an opaque handle. then you can do some other things in the meantime if you want. then it's another blocking syscall that waits for the task to be assigned a PID (no guarantees about scheduling).
maybe you could actually have a third phase too where you request some amount of cpu time. and then you could have a blocking syscall that waits for the PID to exhaust its assigned cpu time. that would actually be........a much more natural way to schedule than trying to infer cpu scheduling from i/o dependencies??????
@SRAZKVT @miss_rodent obv these sequential phases should be possible to both request and then wait for within a single blocking call. but since the returned "handle" would have a different type for each, i would probably just have four distinct spawn methods. maybe this is a job for mutable out-pointers though
@SRAZKVT @miss_rodent oooooooooo omg so scheduling cpu time slices according to the dependencies inferred from waitpid() calls is sooooooo much easier and simpler. that actually aligns the application task dependency graph directly with a build tool task dependency graph. and spawn()/waitpid() calls are like coroutine yield points, except they don't need to block the current process. so this is actually more powerful than the pants task graph bc it's not limited to python coroutine semantics
@SRAZKVT @miss_rodent requesting a fixed-size CPU time slice wouldn't be the only possibility. "run until complete" sounds reasonable too. and maybe you could have a blocking waitpid() call that works like a compare-and-swap loop, calling a provided process-local function pointer every time the previous slice completes, to either request a new slice or exit with a timeout error. and it returns with either the process exit status or the timeout error from the invoked function pointer. and the function pointer could do arbitrary stuff including blocking on some other call
@somebody [reprimanding my user application processes] blocked blocked blocked blocked blocked. NONE of you are free of sin
omg yet another way simon peyton-jones was wrong. cyclic task dependencies are problematic if you're a build tool and you expect to be able to infer the entire toposorted sequence of task invocations offline before executing them.
but if you are an operating system, there is no concept of global task completion (perhaps when PID 1 exits? do we still need a PID 1?), and you are constantly (in an online manner) selecting which live+active [with a nonzero remaining time slice] tasks to schedule on the available cores.
AND THE TASK SCHEDULER COULD BE A USERSPACE PROCESS TOO???????
i think a task scheduler process/service should be allocated from ring 0 and should have uncontested ownership over a set of hardware cores (i.e. no overlaps with other schedulers). and the scheduler should also have uncontested ownership over a set of live (not necessarily active) application processes.
and maybe application tasks can be explicitly+atomically migrated across schedulers? and maybe cores can be migrated across schedulers too.
and maybe there's an analogous kind of scheduler process for OS tasks (drivers, i/o sync)? so it can migrate cores with application schedulers, but not tasks (bc OS services are expected to have idiosyncratic scheduling requirements).
hmmmmmm......................uncontested ownership of cores sounds silly, because we will generally want to maintain some kind of task-core local affinity (so virtual memory + i/o buffers from those tasks remains warm in per-core L1 cache).
this kind of structured locality is why we invented named i/o sync contexts for i/o state (and the transactional request=>commit model). so two questions arise here:
- should i/o sync contexts be linked to scheduler sync contexts?
- should scheduler processes be linked to cores, or tasks?
@SRAZKVT i was looking at seL4 to steal their kernel bootstrap but then i saw they use google repo to manage their repos and i thought hmmmm no
@SRAZKVT i know QEMU is the standard way to fuck around
@SRAZKVT i was thinking at first that the i/o sync logic (i.e. managing all my little fractal zip journals) would be in ring 0 but the thing about having a contiguous-memory serializable representation of i/o state is that it can be moved across processes and that's obviously the right thing to do
@SRAZKVT literally it's so great to do atomic blocking transactional semantics for i/o propagation bc instead of making my brain hurt thinking about atomics i can just write synchronous logic against the C abstract machine
