this is so fucked up i'm now confident that my parser compiler is literally a dual to a parser compiler for alan turing's double-sided tape dispenser. i don't even know why you'd want to do that!!!!
oh whenever the stack diffs hit certain intermediate points, that corresponds to jumping across the boundary of the start or end of a production case (i.e. starting or ending the expansion of a labelled nonterminal). so parsing an input string in this model (by performing the iterative parse process) assigns each input token back to a corresponding state (a specific literal/nonterminal within a specific production case), and then as transitions are made between consecutive input states, they have stack diffs between them (and a stack diff from start -> input[0] and another from input[-1] -> end)
so you DO have a parse graph which maps the input to a sequence of nonterminal expansions from the nonterminal (production) cases provided by the user. but since it travels through the connecting tissue between input tokens, it supports > 2 independent stacks just as easily as 2 (the stack diffs in the solution will fork to span a region)
i still don't have any practical utility for parsing a turing machine yet, but i can see why you'd want to specify a grammar for it. nonterminal expansions correspond to e.g. function calls, and terminals are basic blocks. and nonterminal cases are used for branching.
well and it's also not "parsing a turing machine". it's parsing a series of instruction pointer locations to recover the call and branch information (???)
i don't think this is decompilation because the instruction pointer grammar is what you might get from the compiler and you need that grammar to make sense of anything
tracing the execution is pretty cool though??? and you consider multiple threads as simply multiple instruction pointer streams
i think the translation of what a turing "tape" value at any given time is the call stack (on one side of the tape head) and branch stack (on the other)????
or maybe just branch list??? and maybe branching and jumping are merged? so it's more like the branch–jump list
yes i think branch–jump list is correct!? and of course each jump is a directed edge. but you don't go backwards. unless you're doing time travel debugging?????
but otherwise i am struck by the forward direction of time imposed by the above described process—which is dual to the forwardness of stack diffs in the parser
well and think: the turing machine starts with no tape, which means no recursive calls yet, and certainly no branch–jump history. and it ends with no tape above, but branch history below.
and that is actually strongly dual to the parsing problem, but the parsing problem iterates over states "from left to right", while at all points the stack diff had to be fully balanced (this was a core assumption of the technique from the start!)
oh come on this is so fucked up. don't tell me at runtime my parser nonsense is individually tracking stack and heap memory????
that would imply the heap is simply never actually free()d from. but no! it's more like moving the sbrk, right?
and of course, that means you can have this fucking two-axis code–data HUD/reticle, right???
well, this means i can implement my "const eval" backend relatively straightforwardly (just emulate the two dynamic data structures)! and then the x86 backend is just using the x86 ISA's emulation of these.....4? ...6 separate data structures???
- instruction pages in (virtual) address space
- stack and heap pages in (virtual) address space
- instruction pointer in virtual mem
- break pointer in virtual mem
- stack pointer in virtual mem
- function call stack and branch–jump history
note that the heap goes one direction during the lifetime of a process, but gets torn down upon process exit (corresponding to levels of the process call graph). meanwhile, the....parallel process branching corresponds to the....perpendicular axis of the process call graph????
and the "process call graph" is only ever a tree of living processes at any one time, but:
- process exit closes a recursive subtree (along with current heap/break) at once (hence why init must always be live)
- the process start and exit marks always have a strictly positive delta of clock cycles????
and the "persistent block layer" (aka "filesystem") can also be mapped into process memory—but because it persists, it exists automatically across all processes, with the kernel/fs acting as the block layer MMU through file descriptors!!!! but filesystem paths and the VFS are not real at all—AND THIS IS WHY PATHS (windows) AND VFS NODE TYPES ARE UNSTABLE ACROSS OPERATING SYSTEMS!!!
oh and multicore is a parallel (fixed-width) execution of <= k monotonic processor clocks at once, and the scheduler is the MMU for task execution (IMPLYING RECURSIVE SCHEDULING IS NOT ONLY PLAUSIBLE BUT OBVIOUS!!!!). so each process is scheduled on <= 1 core at a time, with each such strand organized in strictly monotonic chron order across all cores, constituting a series of "on(core)" (vertex-colored) and "off" regions in the global (unmeasurable) "wall-clock" monotonic chronic arrangement.
in recording this 3-D (2-D in-process, 3rd is core index) discrete plot of the in-process 2-axis states, this time-series instruction-pointer plot can be used to infer ("parse") the runtime function call stack & branch–jump history retroactively for a given process execution.
but what's this about assigning vertex-color-per-core? vertex coloration per core just means only one core can iterate the task's literal core-unaware turing machine at once, and the (totally-ordered and directed) edges connect the contributions from each core. when an edge makes a task cross cores, that requires the CPU to flush per-core caches for any addresses in that process's virtual mem.
......so if there's always an init process, why does the kernel have to get executed first??? ....what exactly is the kernel???
well, the kernel creates a task_struct for init, and schedules it on some core to transition to userspace. i suspect the kernel may be able to initialize and even schedule kernel tasks (task_struct, but without the MMU) before then, if it wants.
there are now two points which are very important for the scheduler: process start (transition from other userspace code) and process exit (from user, to kernel!). (note that in this there is absolutely no distinction between multicore and single-core scheduling!)
the following distinctions arrive twofold:
- the core which
initwas scheduled on vs exited may differ—this is important for e.g. tracinginit's call stack - a task_struct may contain core-specific data (fuck if i know!!), which must be rewritten to form the "core migration" edge
otherwise, everything a kernel should do is in fact not modeled by any unified turing machine model of its own, but rather injects kernel code in response to task-external kernel-specified "fault"s (e.g. page fault) as well as from within the task, upon a syscall. so the total story of a userspace process AFTER initial page mapping is described by the task runtime stack's interaction with the syscall handler–which is possible to record!!!
and so we take no chances—our 2-axis instruction-memory model covers the instruction pointer ranges in kernel code for the duration of the syscall, and the contents of the stack after returning from the syscall are fully contiguous! (this is also true when setting the heap break!)
a fault does not record itself into the userspace process's memory model in this fashion—the effects of the instruction that triggered the fault are reverted.
but that's so fucking crazy though????? this isn't REMOTELY C-specific, or even fucking x86-specific!!!! this describes any system with a contiguous physical address space and an MMU!!!
so FUCK A "TIMING ATTACK"—we can ENCRYPT THE CLOCK CYCLES NOW!!!
or rather, we should say that:
- a "timing attack" is more generally stated as inferring the value of one or more bits from across an MMU boundary
- cache prefetch/writethrough instrs seem relevant
- actually i still don't really believe in these
- but i can see how relative clock cycle tick rate (across separate cores) as well as cache load timings (if running on the same core) are not reflected in this unified abstract model, and i can absolutely see how these could leak info
and the "reason" why that is the case is because my parser compiler analyzes all pairwise state transitions, and when applied to an input (a finite string of tokens), if it matches the whole thing, it ends up synthesizing a turing tape intended for a turing machine using the same set of internal states as the states i synthesized to represent the set of unique atomic input literals (nonterminals)
(also i realized yesterday i made a massive error years ago for compiling contiguous sequences of tokens in the user-provided grammar)