i feel that the grammar of a programming language is among the least appropriate of all possible facets of its behavior to start off with. why on earth would i care about your preferred tokens to represent concepts which have not yet been defined
Post
Replies:
0
Proof creation has a high cost associated with it.
yeah you keep saying it sucks. aren't you supposed to fix things like that
To give an idea, it has been the author’s experience [93, 94, 96] that, in an interactive theorem prover, verifying the functional correctness of C code can require between one and two orders of magnitude more proof steps than line count,
(a) yeah maybe cause you keep trying to verify functional correctness guarantees about heap allocations in ring 0
(b) "line count" appeals to the VC class. it doesn't work on programmers
literally everyone go read aaron turon's paper on weak atomic memory orderings right now https://plv.mpi-sws.org/gps/paper.pdf yes there's a coq proof but that's not what a paper is for!!!
check out this future work section:
However, the C11 model allows programmers to freely mix memory orderings, and ideally program logics should support such mixed reasoning as well.
literally it's that easy to give a shit about making people safe and providing powerful robust guarantees. this is why rust used to be good
Early investigation suggests that the C11 model has some corner cases when mixing memory orderings that may obstruct compositional reasoning principles.
i get nerd sniped every time i read that line lmao
We believe the extra generality of GPS is important because it enables us to verify a wider class of weak memory programs, including those whose observable behavior is not SC. The circular buffer and Michael-Scott queue are good examples of this (see the appendix [1]). Singh et al. [35] argue that one should not expose the high-level programmer to such non-SC data structures, but GPS shows that in fact it is possible to reason sensibly and modularly about them.
keep in mind seL4 doesn't even represent concurrent behavior at all in their 2009 proof (as far as i can tell), even though concurrency semantics are a feature on any system with a motherboard. and aaron turon shows actually we can make it easier to write complex code with formal verification
honestly i should totally mess around with coq semantics for my ring buffer from hell
oh yeah the other guy was telling me how much it sucks to verify stuff
and in a single person year, we may be limited to verifying no more than something in the order of 1000 lines-of-code (LoC). Little data exists for how proof-based projects scale, but it is unlikely to be linear.
still just ridiculous that this guy is still talking "verification" without doing the work in the c compiler. i know people do that
The economics of verification have two significant consequences.
so bleak to talk about your research focus like this
First, the range of systems we can hope to verify is limited, but is still large enough to be practically interesting.
that's literally not a "consequence" why would you invoke proof jargon incorrectly lmao
Modern microkernels, with implementations around 10,000 LoC are hopefully within the realm of possibility.
you were just a moment ago saying int * p; int * q; was beyond your abilities
Verification of such systems can bring significant improvements to the reliability of the entire software stack, as above the microkernel layer hardware protection domains limit the impact any incorrectly behaving software has on the trusted computing base [83].
- microkernels don't consider it their problem to provide any sort of correctness guarantees except for their own behavior, so this is just a lie.
- the MMU isolation is from the CPU, not the microkernel
i will literally die mad about how casually they mentioned fucking shared memory pages are a replacement for sequenced writes https://trustworthy.systems/publications/nicta_full_text/8988.pdf
In original L4, “long” messages could specify multiple buffers in a single IPC invocation to amortise the hardware mode- and context-switch costs.
a single crumb of structured I/O
While long IPC provides functionality that cannot be emulated
literally the actual criterion for minimality
Shared buffers can avoid any explicit copying be-
tween address spaces
"microkernel layer hardware protection domains" cmon
The result was significant kernel complexity, with many tricky corner cases that risked bugs in the implementation.
i thought that's why we used formal verification? that's why microkernels were worth the cost of proofs?
after reading all this my impression continues to be that microkernels don't do enough isolation at all!!! i even dug up build systems a la carte https://www.microsoft.com/en-us/research/wp-content/uploads/2018/03/build-systems-final.pdf where simon peyton-jones tried to pull this same shit about build systems
i do actually appreciate that seL4 has a lot of use in single-core embedded applications where you're typically not just greedy for i/o like me and the purpose of an OS actually aligns reasonably well with the atomic i/o APIs
For seL4 there are even stronger reasons for staying away from supporting long messages: The formal verification approach explicitly avoided any concurrency in the kernel [Klein et al. 2009], and nested exceptions introduce a degree of concurrency.
i also very specifically want to avoid introducing subtle concurrency bugs but i'm doing that by expanding "isolation" beyond the MMU and expanding named "synchronization contexts" to structure literally all the externally-visible state changes like i/o
i absolutely don't think i could do seL4 better, and i'm not planning to inject tons of confusing and poorly-documented semantics like linux
at first i was thinking "let's literally just add buffers between everything" but then i got hooked on transactions
the one concurrency i will have to figure out is multiple processes writing to the same synchronization domain at once. i think i'm gonna try my damndest to avoid having to use any red-black trees. maybe i'll make it possible to open the same file/shm mapping rw in two+ threads/processes at once but you have to explicitly tell me you actually want me to handle possibly-concurrent write requests to this shared resource
i also got upset about pipes when i learned even though userspace uses them like ring buffers their semantics just encode the whole monolithic memory architecture i h8. they're literally just a fixed-size queue for atomically pushing/pulling some floating pages
i have such a negative ranty post i haven't sent from many hours ago but seL4's autobio paper ending with the very clear remark "we can't figure out how to schedule anything, nothing works" -- i didn't see that as like indicative of moral decline. to me it was clarifying!
i also felt this way learning that linux and openbsd also schedule their processes the exact same way seL4 does (to my mind at least), which is generally round-robin
it's actually kinda absurd thinking about how scheduling based upon something besides fair slicing ends up imposing this huge huge huge change in the way the entire system operates!
not just me being contrarian when i say driving scheduling from the active data dependency graph is really fascinating to consider too because that's also exactly where it would make sense to update the page attribute table
and telling the CPU to schedule my pages while then scheduling the task that's gonna want them sounds so cute
like the only reason i will ever get around to actually doing this is because i want to have extremely deep control over where and how memory flows (including persisted)
and i'm still excited about this bc there's no atomic globally visible changes ever (maybe i/o devices) which is the stuff that makes my brain hurt when linux does it
how simple do my stateful message queues need to get before i can start pretending it's kind of like formal verification
this other citation "why do people still use c for high-reliability environments" https://dl.acm.org/doi/10.1145/1215995.1216004 because nowhere else is willing to maintain a lingua franca out of the goodness of their heart
i was thinking about this too after i learned about the caveats with side effect sequencing. i don't think there's anything terribly special about C other than i know gcc devs are genuinely sweet and thoughtful and passionate
if i wanted to make a language for the macrokernel i would have to decide to understand a lot more than i do now about what the hell a kernel is and especially boot logic. and then i'd have to learn about disk persistence.
i think as an implementation language for managing memory and cpu structures there definitely could be better frontends. and i think once i feel more comfortable about the hardware semantics (particularly x86 cpu + ssd nvme) then i will want to start gernerating structures that translate the macrokernel user API in my head to match the requirements from the hardware
like an interlocking web of formal models dancing together in the memory page prairie is actually what i see in my head when i think of the end goal
look up this paper on "model checking c source code for embedded systems" https://link.springer.com/article/10.1007/s10009-009-0106-5
- buy it for $40! thanks!
two just horrifying suggestions to purchase below that:
- A Model Checker Collection for the Model Checking Contest Using Docker and Machine Learning
- Finding software vulnerabilities in large C projects via bounded model checking
never sure how to take lines like these https://sci-hub.st/10.1007/s10009-009-0106-5
The disadvantage is that all specific knowledge of the C code and the underlying hardware has to be used in the abstraction process as the general purpose model checkers are not aware of these peculiarities.
i assumed everyone doing this sort of thing was the author of the C code they're checking and that everything of course has to be specialized to the particular CPU. i don't know what anyone would expect to get out of model checking otherwise
actually delighted to hear not only that gcc tends to be the de facto here but that CIL is compatible. CIL sounds sick
If the GCC compiler supports the chosen microcontroller, the adjustments are less costly since many of the C code model checkers use the GCC compiler or a compatible framework such as CIL for preprocessing.
yet another seemingly-legit ARPANET paper that seems like it was made to be found discarded in an abandoned laboratory https://people.mpi-sws.org/~gummadi/teaching/sp07/sys_seminar/arpanet.pdf
Attempts at computer networks have been made in the past
"but they weren't evil enough for our purposes".
dude is absolutely crashing out about "load sharing", claiming it will never be worth the cost, and computer programs are incompatible, etc. given that i know that worked for parallel scala compiles, it seemed confusing until the next section
Data Sharing:
The program is sent to a remote computer where a large data bank exists.
This type of operation will be particularly useful where data files are too large to be duplicated economically.
so our boy lawrence g. roberts totally predicted bazel cloud builds and github actions.
Access to this data base will be required simply to make an inquiry or may involve executing a complex program using the data base.
mysterious access control mechanisms? potential surveillance? it gets better:
This type of use is particularly important to the military for command and control, information, retrieval, logistics and war gaming applications.
In these cases, one command would send a program to be executed at another center where the data base existed.
i really never know if they're just saying intentionally ridiculous shit
note how he distinguishes "send a program" -- clearly an RPC call, which were definitely around at the time
fidonet did a ton of load sharing on a per-file basis, including some really interesting locality-based queueing
Program Sharing: Data is sent to a program located at a remote computer and the answer is returned. Software of particular efficiency or capability exists on certain machines.
literally this is all google tech lmao it's like he's salivating over this
The use of specialized programs at remote facilities makes possible large gains in performance.
Perhaps even more important is the potential saving in reprogramming effort.
ridiculous shit
yeah and then he mentions three separate times how scientists can use it to do new science together. it seems important that scientists are on it at all
and i found all that about DARPA salivating over people never writing their own programs again because of:
- the seL4 paper which got best paper https://web.archive.org/web/20110219113850/http://www.ok-labs.com/releases/release/open-kernel-labs-paper-on-formal-verification-wins-top-prize-at-prestigious
still think this paper is terrible. it keeps saying it made compromises for verifiability and wildly overstates the guarantees
turns out that conference SOSP is literally the (ACM) conference whose first year was when a big ARPANET thing was unveiled https://en.wikipedia.org/wiki/Symposium_on_Operating_Systems_Principles
there's these unstructured notes from the fucking pentagon lmao https://web.archive.org/web/20150405055923/https://web.stanford.edu/dept/SUL/library/extra4/sloan/mousesite/EngelbartPapers/B1_F20_CompuMtg.html
and finally this is IETF at its best https://en.wikipedia.org/wiki/Shared_resource choose the most generic possible term that sounds like page cache, but it specifically means network share