Post by @hipsterelectron@circumstances.run

@hipsterelectron@circumstances.run 5 hr. ago

so becausse the 1978 pohlig-hellman paper mentioned that one of knuth's taocp books had the sunzi remainder theorem they used, i finally cracked and opened up the knuth 1998 sorting and searching text

15 Replies

4 Boosts

This comment is unavailable — it may have been deleted or is not visible to you.

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

in fact, it's perfectly coherent to have each recursive supervisor process describe task scheduling mechanics only between its own processes and no one else's. that in fact makes it super easy for the kernel to implement timesharing by allocating time slices to the entire structured subgraph!

think of it like linux namespaces (i.e. containers)--but instead of retroactively figuring out the mapping from each process to its namespace, then calculating some sort of "quota" (while essentially retaining the global round-robin scheduler),

instead we codify being scheduled on the CPU as not only a privileged operation, but indeed a crucial security boundary in which each supervisor process becomes accountable for how much time it allocates across the subprocesses it spawns

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

in the kernel, we could even just do "round robin" again--but iterating over strictly nonoverlapping process groups!

this sounds really basic, but what it means is that we don't experience the awful i/o contention that linux does--because all processes blocking on each other's output can be stopped and started at once!

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

how does "strictly nonoverlapping process groups" work if processes need to share data ex post facto? simple! for two processes A and B, their respective supervisor processes S_A and S_Bmust both request a resource that exposes an interface to write data outside the process-local i/o space. this comes in the form of a capability, and it's the exact definition of our "named i/o sync domains"!

and alternatively but no less appropriately, we will still allow supervisors to request a shared memory buffer capability from the kernel, which it can then expose to multiple processes in its IPC graph. unlike the highly-optimized filesystem abstraction i'm providing (which adds on the concept of "i/o transactions" to negotiate the communication of data across supervisor trees in a structured way), shared memory is going to rely upon the semantics described by the C11 weak memory model for atomic operations for consistency.

the point here is absolutely not to nag applications to do "safe" i/o--all of this is purely motivated by my personal need for speed!!!!

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

in fact, the POSIX approach here is already perfect! https://www.man7.org/linux/man-pages/man3/shm_open.3.html

The operation of shm_open() is analogous to that of open(2). name specifies the shared memory object to be created or opened. For portable use, a shared memory object should be identified by a name of the form /somename; that is, a null-terminated string of up to NAME_MAX (i.e., 255) characters consisting of an initial slash, followed by one or more characters, none of which are slashes.

if the /somename key used by two distinct supervisor trees matches, then they can communicate through a shared memory mapping!

View

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

however, this global namespace is less than ideal. the way we would improve this is as foilows:

any named capability (i/o sync domains, shm mappings) is local to a namespace.
a namespace is itself a capability! but it cannot be requested by name.

instead, a namespace can be created in two ways:

generated freshly by a supervisor process--this corresponds to randomly generating a secure cryptographic keypair (ECC or DH).
subsequent named capabilities can be scoped to this namespace. the supervisor process who generates this can explicitly send this namespace to any process it can communicate with, and it can write the keypair to persistent storage so it can recreate it upon reboot.

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

this next part is a brilliant fucking idea, please get ready (cc @somebody):

if a supervisor process wants to expose a namespace to other processes, it can do it in two ways, by exposing either:
- just the public key, which strictly supports read-only views of resources in that namespace
- the whole keypair (public & private), which allows the recipient to request named resources in that namespace which can mutate data (and therefore can communicate with others who have access to that namespace)

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

@somebody i can't fucking believe how naturally that corresponds to the unambiguous trust relationships of public-key cryptography (or to be precise: it maps specifically to the subgroup of unambiguous trust relationships in PKC--not all PKC is unambiguous lol). cc @ireneista

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

finally, how would we use this to support structured communication? well, in order to mimic an FHS system, i would create an i/o sync domain (essentially a chroot) with standard [readonly] executables mapped to /usr/bin/* (i would probably use busybox since coreutils is not a safe dependency anymore sadly).

the first supervisor process is the init system itself! but i'm thinking i would probably try to build that minimal busybox FHS into the initramfs. maybe i wouldn't even share the private key for that with the actual init system, so even an evil PID 1 written by lennart poettering can't modify its contents with evil calls to dlopen()

Filesystem Hierarchy Standard

This standard consists of a set of requirements and guidelines for file and directory placement under UNIX-like operating systems. The guidelines are intended to support interoperability of applications, system administration tools, development tools, and scripts as well as greater uniformity of documentation for these systems.

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

oh and in fact i just changed my mind about several things at once:

all types of shared memory mapping capabilities should require providing the file descriptor to map--this should be mutually exclusive with the standard file i/o interface
any attempts to use write() or read() on the same descriptor after conversion to a shared memory mapping will fail with a specific implementation dependent error code (e.g. EIO or EPERM or whatever)
we don't need a separate feature for anonymous memory mappings if we already have a process-local i/o sync domain by default
- i.e. instead of doing an anonymous mapping, you can just create a new file that you own, and that produces an anonymous mapping since no data is shared outside of the process's **filesystem i/o virtual memory space**

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

this immediately achieves incredible benefits for shell script robustness. instead of e.g. relying upon autoconf's polyfill for mktemp, or having to create a miniature build system to calculate invalidation against file checksums, a shell script can just use the entire filesystem available to it as scratch space, and only produces output artifacts others can see by requesting a communication vector capability!

compare to e.g. m4_maketemp(): https://www.gnu.org/savannah-checkouts/gnu/autoconf/manual/autoconf-2.72/html_node/Redefined-M4-Macros.html#index-m4_005fmaketemp-1

Posix requires maketemp to replace the trailing ‘X’ characters in template with the process id, without regards to the existence of a file by that name, but this a security hole. When this was pointed out to the Posix folks, they agreed to invent a new macro mkstemp that always creates a uniquely named file, but not all versions of GNU M4 support the new macro. In M4sugar, m4_maketemp and m4_mkstemp are synonyms for each other, and both have the secure semantics regardless of which macro the underlying M4 provides.

that last line i bolded was from paul eggert, who fucking rox my sox

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

note that there is no need to request a capability or to allocate anything outside of the standard POSIX interface in order to read from stdin or write to stdout/stderr. that's because POSIX i/o streams are already both anonymous and linearizable: exactly the properties we need!

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

this approach would change some things about shell scripts. for example, under this model, providing a path to another file (e.g. as a command-line argument) would require:

explicitly constructing a new i/o sync domain (i.e. chroot) by cloning another one, then splicing the desired file into the desired path
invoking the subprocess with a modified form of posix_spawn() which accepts a named i/o sync domain to construct the process in

one way to make this more ergonomic is to simply propagate a CoW copy of the i/o sync domain of the parent process into the subprocess by default! this would actually be exactly right!

#!/bin/sh

# This modifies the shell interpreter's local i/o state:
echo 'hey' > wow.txt

# This forks off a CoW i/o sync domain first,
# before spawning a `wc` subprocess that
# automatically sees the file we just created! 
wc -c wow.txt
# => 4

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

finally, this raises the question: when does an i/o sync domain get "named"? because i think we have now just described a system of automatic anonymous i/o sync domains by CoWing from the parent process (this obviously sounds like fork(), but i absolutely do not believe it should be merged with fork() as a syscall)

i mean, i think we solved the "name" problem with asymmetric cryptographic keypairs previously????

as in:

since we no longer have named shm mappings,
and i have just realized that my idea of a "named resource" was incorrectly encoding secret knowledge (the name of the resource to summon)

so, i think we say:

a process can generate new i/o sync domains from scratch at any time
- these are just empty directories--no cryptography
- these can be merged with and mutated and spliced just like the process-global "implicit" i/o sync domain
a process can register an i/o sync domains it has a handle to--and this is where we should generate the cryptographic keypair

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

it is intentional that this cryptographic keypair can be transmitted completely out-of-band. its purpose is to codify a permissions system that can be serialized and transferred across a filesystem or network

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

this means the permissions calculus for my kernel has been narrowed down to exactly three points:

given a public key, validate that the caller indeed possesses it through a cryptographic challenge
- generate a read-only view
given a private key, again validate by challenge
- generate a "standard" (mutable) handle to the shared state of the i/o sync domain
enforcing read-only/immutable status