Keyronex

[wet apex]

u should copy my xterm customization files, the default white background sucks to look at

good work tho!

[stone orbit]

when are you planning on publishing that branch of keyronex?

[hexed solstice]

cheers, and i just might do that

[hexed solstice]

soon, it's why i've updated mlibc

[stone orbit]

cool, i can't wait to see how streams work :^)

[hexed solstice]

without a doubt one of the coolest additions

https://www.nokia.com/bell-labs/about/dennis-m-ritchie/st.pdf dennis ritchie describes his original design here

[slender flame]

i know it has been said to move the convo but I'll answer here because I don't want to ping you in another channel

This is a choice, glibc can autogenerate sysdeps with a list of syscalls in a very cool way but ironclad syscalls were incompatible with this, so we had to do the 90k files with one function per file

If I wanted to change the ABI to be something glibc finds more pleasant, you could cut down 90% of the patch

[wet apex]

oh thats cool

btw you two should write a blog post about that at some point

[sullen fern]

How big is the patch really?

Is it really 17k loc

[stone orbit]

a bit over 17k

[slender flame]

I will

It makes good blog material

[wet apex]

defo

[hexed solstice]

this is also how solaris does it in FireEngine

it has what are called vertical perimeters

they have a queue and they have a worker thread bound to a single CPU

The thread, entering squeue may either process the packet right away or queue it for later processing by another thread or worker thread. The choice depends on the squeue entry point and on the state of the squeue. The immediate processing is only possible when no other thread has entered the same squeue.

what i have found more problematic is making STREAMS iterative

i can do it well enough for 99% of the cases but certain odd ones are a slight problem

it's only a problem really because of the diversity of things that a stream has to pose as

for instance the line discipline mobule when it gets an ioctl telling it to become canonical, has to tell the stream head to adopt "reads should only return at most one message worth of data", before going on to complete the ioctl

anyway the basic approach to iterativising it, that as far as i can tell is the height of simplicity, is that put procedures are invoked through a dispatching loop, and each put procedure, rather than actually sending the message, returns to the loop a structure saying "here is a message (or chain thereof) and the direction i want you to send it in from here"

[hexed solstice]

my immediate priorities: rewrite futexes, submit a PR to mlibc with updated sysdeps, and make robust and more complete the STREAMS-based socket implementation (particularly the unix domain sockets module, which is a horrible mess on account of rushing the bare minimum semantics to get xorg running)

in general however i think keyronex today now finally exceeds old keyronex in almost every respect

[slow agate]

PR seen, reviewing ...

unrelated to the review, just curiosity: did you run it through clang-format?

bc it sure looks like it, which is very nice

[hexed solstice]

just a healthy dose of autism about making sure it conformed with my C style

i follow the netbsd c style guide near religiously now

[slow agate]

__mlibc_sigentry is an interesting design, I haven't seen something like that before

[slow agate]

close enough

LGTM

[hexed solstice]

the approach is ripped off from somewhere i think, can't remember which OS does it that way

[slow agate]

also nice that the futex stuff has the waker count now, I might tackle the remaining pthread memes tonight then

I'll add a count argument to the futex_wake sysdep for that, hope that's okay with rebasing etc

[hexed solstice]

it's no problem at all, i need to do some housekeeping with the repos anyway to get the new keyronex branch pushable

[sinful jetty]

Can you link it

[hexed solstice]

https://github.com/NetBSD/src/blob/trunk/share/misc/style

freebsd's is another useful reference https://man.freebsd.org/cgi/man.cgi?style(9) and sunos c style is fairly similar https://www.cis.upenn.edu/~lee/06cse480/data/cstyle.ms.pdf

[sinful jetty]

Very detailed

[high solar]

I'm still not convinced that futex wake with anything except for 1 and wake all is useful

[marble crag]

Whats with OpenBSD? Not useful or just very similar?

[hexed solstice]

also quite similar https://man.openbsd.org/style

[sinful jetty]

Now imagine Keyronex with Gnu style

[hexed solstice]

god forbid

i don't know where stallman pulled that out of

[sinful jetty]

Yeah its quite funny

[slow agate]

let me cook

[hexed solstice]

first two: ✅

now futexes are implemented properly

now futexing produces a handle to an address, referencing the VM object so as to keep it alive (so if someone unmapped it and it went away, and the address of that vm_object_t were reallocated to another vm object, the futexes won't be confused)

though if someone unmaps what's being waited on with futex_wait anyway that's an odd thing to do, and it's probably harmless to let through a false wakeup to that person

there is a global futex mutex but if it turns out to be a bottleneck it can be hashed out into many mutexes (say to one lock for every PGSIZE / sizeof(int))

[hexed solstice]

something i must've fixed along the way has xclock ticking now

[wet apex]

Xclock not ticking was originally mlibc missing a scanf for floats iirc

[hexed solstice]

maybe the mlibc update did it then, i was using mlibc from over a year ago before

streams-based socket robustifying is proceeding well, all sorts of conditions now mostly handled, things like a socket being closed while mid-connect()

[deft elm]

couldn't resist, made just for this discussion lol

[wet apex]

@hexed solstice completely random question

do u use netbsd

cuz netbsduser

[hexed solstice]

on desktop, but not on my laptop

[wet apex]

oh based

[marble crag]

what do you use on the laptop?
And why NetBSD? I wanna try it time

[stone orbit]

probably linux

[worn elbow]

from between his toes.

[wise orchid]

was reading the readme, found a typo ("Keyronx")

[earnest salmon]

PR the typo fix so that you can be a contributor

[wise orchid]

sure lemme turn on my laptop rq

just made a pr

[hexed solstice]

i've merged it but unfortunately the master branch gets relegated soon and replaced with a new one

[wise orchid]

Augh I didn't realize this is the old one

[hexed solstice]

tempted to do some work on TCP/IP

it would help flesh out STREAMS a bit

the STREAMS flow control mechanism: if a queue has reached its high watermark, then direct processing of messages (except high priority control messages) received is inhibited until that stream reaches its low watermark; queues upstream of that queue find out that this is the case when they want to put messages to the next queue downstream, and are themselves inhibited, and so the backpressure propagates all the way to the stream head and writers are blocked. when the queue that blocked up the rest reaches its low watermark, the next queue upstream has its service-queued-messages entry point invoked, and perhaps that in turn brings it below its low watermark, and so the relief is propagated upstream

this works well going downstream from the head, but for TCP i think it's initially non-ideal for going upstream, because the TCP module sends some data upstream and it has no idea whether it's been read yet or not, it only finds out when the stream head's receive queue is past its high watermark and STREAMS flow control is activated

so what do you advertise for a receive window?

this is one area where i concede a genuine limitation of STREAMS for which i haven't yet thought of a really nice solution

possible solutions i don't entirely like:

• send a control message downstream whenever the stream head satisfies a write, so the tcp module can keep track of how much it's sent v.s. how much has been satisfied: this is probably the most elegant solution, but that's a lot of messages sent downstream! not good for performance
• give queues access to information about the stream head's write queue: efficient but inelegant, breaks the principle of isolation of modules, but on the other hand it's just making read-only, fairly abstract information available, so i don't think it's horrifying

[hexed solstice]

i have heating again

[hexed solstice]

vmm bug of some sort or another

i'm looking for the cause

[hexed solstice]

it was a case where a page for table use was allocated but not zeroed - i thought i was more diligent about that (but then i hadn't touched this branch in over a year before taking up work on it again, so some of the code is like new to me again)

[hexed solstice]

STREAMS flow control is now mostly implemented, and i feel like starting on the TCP/IP stack now that it's there

[deft elm]

0

[hexed solstice]

how i might architect a STREAMS-based networking stack, in rough outline

[obtuse falcon]

did you make this graphic?

[hexed solstice]

yes, with draw.io, it was tortuous

[obtuse falcon]

looks like straight out of a text book

[hexed solstice]

hyena thought similarly #1064583713184292894 message

[obtuse falcon]

lmao

[hexed solstice]

i like draw.io

i've tried to use plantuml and friends (actually the sequence diagram hyena commented on is plantuml) but they really fall apart on this sort of diagram

[obtuse falcon]

i have haunting memories of UML diagrams so i usually avoid them

especially use case diagrams

[hexed solstice]

a lot of them are management bs

[neat steppe]

And this is all to be under one big lock?

[hexed solstice]

no

each TCP/UDP stream has a lock, the IP multiplexor is not locked itself but internally will have various locks (routing table, ARP etc), and each NIC queue has a lock

the name of the game is each stream is encompassed by what solaris calls a "vertical perimeter" that serialises all activity within that stream

the NIC queues are streams in their own right, TCP/UDP streams are of course distinct, i haven't figured out yet whether/how i can adapt the STREAMS multiplexor concept without losing modern scalability - i suspect i can, if i give multiplexors the opportunity to opt out of being a vertical perimeter and instead delegate their synchronisation to themselves to implement - if i can figure it out cleanly then the IP multiplexor will be a multiplexor-stream, if not it'll just be its own thing that intercedes

[neat steppe]

I interpreted you wrongly last time I asked you about your locking plan then

[hexed solstice]

it sounds so, what did you imagine i had in mind?

[neat steppe]

I think I asked if you'd have per module locking and you said something like no it'll be a lock for the whole stream and I interpreted that very broadly

What did we read that advocated putting a bunch of these things into a huge combined module for increased performance at the expense of modularity

Was that Solaris

[hexed solstice]

it could be either solaris or the 'demux architecture' paper

solaris made TCP and IP directly call each other a lot so effectively what was a discrete TCP and IP module become one grand module that stretches out the bottom of each TCP or UDP stream

[neat steppe]

Looking forward to trying to become as knowledgeable as you on this stuff in 54 years when I start my character IO journey

[hexed solstice]

it's all very interesting, i think you'd quite take to it

it's easy for me to like STREAMS though because i'm at liberty to tweak it in ways that solaris for instance never could

if i identify a problem i can tackle it with incompatible solutions

[hexed solstice]

i'm going to try implementing STREAMS multiplexors

what's the worst that can happen

[hexed solstice]

They're simple!

An upper multiplexor is just how you naturally do things if you have a multiple streams terminating into one driver; a lower multiplexor is just like a way to have a "lower stream" get its stream head operations replaced with invocations of the multiplexing driver. I'll diagram it when I'm home

[hexed solstice]

that's an "upper multiplexor"

it doesn't require any support from the STREAMS framework at all, it's entirely natural, you can just decide what you want to do with the messages you get regardless of which stream they arrived on

[hexed solstice]

and that's how a STREAMS lower multiplexor works

so there's really nothing mysterious about it at all, upper multiplexors are just trivially and naturally possible, lower multiplexors are mostly just a mechanism to let a stream head be replaced with termination at the top into another driver

[quick saddle]

if both driver ys are identical are each stream's read and write queues also shared?

[hexed solstice]

they're distinct, it's just that since they both terminate at the top into driver y, driver y can do whatever it wants with the messages

[hexed solstice]

i wrote a large part of TCP logic last year, which has slotted in fine

much work to do to properly integrate and complete it

[steep marlin]

lol do you have a company or smth

or is that just for show

[stone orbit]

nah its just part of the aesthetic

[steep marlin]

has early 2010s vibes

[worn elbow]

Admittedly, I read it as Veta Srale, when first saw it. 😁

Sponsored by astigmatism.

[steep marlin]

well the font doesn't help with that

very thin lines

[hexed solstice]

i'm liable to rename it for that reason

it doesn't look great

i've got a problem with my original plan to do a stream stack like head -> socket module -> tcp -> ip driver

there are two problems really

the first is acceptance; when a listener receives syn, i want to have an embryonic connection set up, ready to be attached to a stream when the program accept()'s. the second is closing, there are several conditions under which you want to keep a vestigial connection around for a while afterwards if you would comply with the RFC. in both cases i need to have a freestanding TCP connection not associated with any stream. but if i have tcp -> ip driver stacking then i'd have to have a real stream for that case. i don't want to do that (tedious to create one, and it would have to be torn apart when accept() happened!) so i'll have tcp and ip live together so they can make direct calls, and i can just have a distinct TCB object that pre-dates (in passive open case) and outlives (in e.g. CLOSE-WAIT case) the stream it's attached to. so the stream stack instead looks like head -> socket module -> tcpip driver

[hexed solstice]

a user program can now connect() and read() until fin; now i need to implement this detachment logic

then close() should work

[hexed solstice]

and then i will probably have to do quite a lot of testing that reassembly, retransmit, etc work!

[hexed solstice]

reassembly appears to work fine in all cases

[hexed solstice]

flow control is in, and the receive window seems to adjust nicely

tcp.c is already large and it doesn't do passive opens yet, nor most of the timers do anything, nor is rfc 5681 congestion control implemented yet, and there's 25 kfatal calls. lots to be done

[stone orbit]

tremendous work

[hexed solstice]

thanks, i mostly followed tcp/ip illustrated vol. 2, which describes BSD's

the distinctive characteristic of which is how output works

a single central function decides what should be sent depending on the current state, and i found that approach really quite elegant and simple

so you need no magic, you write that once, and any output you ever send happens as a result of its decision

i like especially the fact that the th_flags are always derived from the current state (the sole exception is unsetting FIN unless you're sending the last data):

static uint8_t tcp_out_flags[] = {
    [TCPS_CLOSED] = TH_RST | TH_ACK,
    [TCPS_BOUND] = 0,
    [TCPS_LISTEN] = 0,
    [TCPS_SYN_SENT] = TH_SYN,
    [TCPS_SYN_RECEIVED] = TH_SYN | TH_ACK,
    [TCPS_ESTABLISHED] = TH_ACK,
    [TCPS_CLOSE_WAIT] = TH_ACK,
    [TCPS_FIN_WAIT_1] = TH_FIN | TH_ACK,
    [TCPS_CLOSING] = TH_FIN | TH_ACK,
    [TCPS_LAST_ACK] = TH_FIN | TH_ACK,
    [TCPS_FIN_WAIT_2] = TH_ACK,
    [TCPS_TIME_WAIT] = TH_ACK,
};

[earnest salmon]

this is cool

[hexed solstice]

how for instance does retransmission of SYN work v.s. retransmission of data? the exact same way, the output routine just attaches SYN since you are in SYN-SENT or SYN-RECEIVED state

[high solar]

That's more or less what we do in Managarm as well

[hexed solstice]

receive works, send is messed up badly

i'm investigating now

[hexed solstice]

the first problem was that i completely forgot to clear out queued data that's been acknowledged; the second was that i was the active closer and advanced snd_nxt past both the end of all data and FIN, and had some occasion to call the output function again, before the peer acknowledged the FIN, so i remained in a state that produces FIN, and sent another (not as a retransmission) which confused my sequence numbers

[hexed solstice]

retransmit seems operational (unsurprisingly, i did test this quite thoroughly in userland last year)

other than passive open, much cleaning up of the code, and the various niceties (congestion control, persistence, keepalive) i'm reasonably satisfied with the state of the tcp support

[hexed solstice]

i started work on passive open, won't finish tonight, but i expect to serve a webpage from keyronex tomorrow

god willing

as far as i can tell the protocol side of it is done and only plumbing remains

[neat steppe]

inshallah keyronex will serve a webpage tomorrow

[earnest salmon]

lol

[neat steppe]

woah who wheeled the obarrow back in here

the wheel obarrow

the wheelbarrow

get it

[earnest salmon]

yes ahhaha

[neat steppe]

inshallah he will not be wheeled back out soon

[earnest salmon]

inshallah

[wise orchid]

based

[gilded plank]

keyronex prime

[high solar]

very cool

[stone orbit]

god damn that was quick

[steep marlin]

Nice

[hexed solstice]

i wrote most of it in march/april last year so it's largely just been a work of integrating to the kernel & fixing residual bugs

[hexed solstice]

it's time for a break from TCP, now seems a good time to get rid of the hardcoding of interface etc in the kernel and implement an ifconfig tool

[hexed solstice]

one interesting challenge: how on earth do you implement routing sockets on a STREAMS basis? unlike everything else, it makes sense for them to error deep in their own logic

[hexed solstice]

most hardcoding is out, a first pass at routing logic is in, userland interface is via ioctl because i haven't figured out the best way to fit routing sockets into STREAMS yet, but when i do, a routing socket will replace it

the routing table could do with being a radix tree rather than a linked list, which will certainly have to change sooner or later

[hexed solstice]

(i could give AF_ROUTE a special treatment in the already specialised stream head logic for sockets, maybe translate writes into ioctls so acknowledgement can be received)

[neat steppe]

looking forward to the keyronex port to xrstation using monkuous's gcc backend

[hexed solstice]

after aarch64 and riscv it ought to be a breath of fresh air

[hexed solstice]

anyway, let's get interface unplumbing sketched out

[obtuse falcon]

loongarch 💀

[stone orbit]

nah xrarch based

[obtuse falcon]

fpga when

[steep marlin]

I would offer to port xr/station to an FPGA if I actually had the skills...

But last time I tried making a CPU that big the project kinda fell apart

[hexed solstice]

void
str_requnlock(str_head_t *sh, ipl_t ipl)
{
    kassert(splget() == IPL_SCHED);
    kassert(ke_spinlock_held(sh->lockp));

    if (!TAILQ_EMPTY(&sh->req_waiters)) {
        struct req_waiter *waiter;
        waiter = TAILQ_FIRST(&sh->req_waiters);
        TAILQ_REMOVE(&sh->req_waiters, waiter, link);
        if (waiter->synchronous)
            event_set_signalled(&waiter->event, false);
        else
            iop_continue(waiter->iop, IOP_CONTINUE);
    } else {
        sh->req_locked = false;
    }

    ke_spinlock_unlock(sh->lockp, ipl);
}

this function has been aggrieving me for, i think it's been more than an hour

needless to say the event should be signalled true and not false to wake up readers

i thought there was something really awful going on that was corrupting thread's stacks in such a way as ends up with a thread stuck waiting for a req_waiter that's not on the stream head's req_waiters queue

[hexed solstice]

tcp.c down from 25 kfatals to 20, let's go

[twin haven]

mm very nice

[hexed solstice]

now at 8

[earnest salmon]

nice

keyronex is quite a based project icl

[hexed solstice]

cheers, as too is OBOS

i stole a demonstration idea from you

running even a trivial web server and accessing it with a modern browser on the host system is certainly a good stress test for tcp

[zenith karma]

https://github.com/Keyronex/Keyronex/blob/master/kernel/include/kdk/vfs.h#L21 this seems to be wasting 4 bytes for nothing, because there are two uint8_ts right before it and not one

[hexed solstice]

don't worry, it got rewritten

i really need to get the new branch published

[zenith karma]

ahh okay

[hexed solstice]

the locking scheme got dramatically simplified as well, currently a single mutex; that's going to become an rwlock with "busy namecache entries" created across vnode operations so the lock can be relinquished, which is already a fairly scalable solution for not-too-large machines; the next step after that would be RCU-protected lockless happy path lookup

[twin haven]

How do the busy entries work?

Ah - I'm imagining one is created when operating on a vnode, then further operations would see the busy entry and block on it?

[hexed solstice]

yeah, it's a sort of ad-hoc sleeping lock

[twin haven]

I see, interesting.

[hexed solstice]

same pattern as for collided page faults

[twin haven]

That makes sense

[neat steppe]

that was my idea i think

important for me to point out because im a raging narcissist

[twin haven]

Lol, good to know

[hexed solstice]

Its true

My previous namecache sketch just had a mutex per cache entry instead

But that gets tricky around certain operations, if not unsolvably tricky. But the real gain in scalability comes from NOT having to acquire exclusive locks in the happy path; otherwise you will always be contending on the often accessed namecache entries like /, /usr, that sort of thing. So being able to usually proceed under a read-locked rwlock is probably superior to a mutex per cache entry

And this is in spite of the rwlock being global because the write locking is very short in duration and the busy entry trick lets most of the operation happen outwith the rwlock

This approach of having a larger structure which is rwlocked as a whole, and a special waiting mechanism for "busy" entries, turns out to be quite a useful approach in many places, especially if the larger structure is a 🌳

[earnest salmon]

what if the larger structure is a 🌲

(coniferous tree, discord, not evergreen)

[hexed solstice]

then i should write to my father and ask him, since he was a forester

[earnest salmon]

interesting

[hexed solstice]

he will have considerably more knowledge about what to do with trees than i do

[earnest salmon]

you both deal with trees, but different kinds of trees

[hexed solstice]

i'm now implementing this

there is a namecache topology rwlock, a standby positive mutex, and a standby negative mutex. in the case of retaining or releasing a namecache entry, if the refcnt is changing from some positive value to another, then that happens locklessly. else the needful standby mutex is taken, the refcount is revalidated to still be either 0 (retain) or 1 (release); if it is, then the entry is taken off/put on to the needful standby queue, respectively

this is another instance of a common pattern in keyronex, i don't have a name for the pattern yet, i borrowed it from solaris, but the principle is "defer refcount change to (and sometimes also from) 0 until some lock is acquired". one of the other principle uses of this is for vnode release from 1 to 0; that again is deferred, most filesystems with anything like an inode number concept then first lock a "inode number to vnode" map, and check if the refcnt is still 0 (because someone else could've ref'd it via the "inode number to vnode" map)

an eventual goal is to be able to do under RCU a whole lookup without any stores to shared data but for the final refcnt. i expect that would nicely decontend the standby locks

[hexed solstice]

i'm generally rewriting the namecache atm

i feel like the right thing to do in operations like link, rename is to make the needful namecache entries exist, be they negative in the target's case, then lock, verify state hasn't changed, and carry out the vnode ops

[final hatch]

i cant believe i wasnt following this thread

oh right, i was banned

now i am!

[hexed solstice]

9p is so ghastly

The qid represents the server’s unique identification for the file being accessed: two files on the same server hierarchy are the same if and only if their qids are the same. (The client may have multiple fids pointing to a single file on a server and hence having a single qid.) The thirteen-byte qid fields hold a one-byte type, specifying whether the file is a directory, append-only file, etc., and two unsigned integers: first the four-byte qid version, then the eight-byte qid path. The path is an integer unique among all files in the hierarchy. If a file is deleted and recreated with the same name in the same directory, the old and new path components of the qids should be different. The version is a version number for a file; typically, it is incremented every time the file is modified.

bloody stupid way to identify a file

i don't see much of an alternative to sending a 9p open request whenever a vnode is generated for any reason (in order to pin the existence of the file) because otherwise the qid path can and will be reused (it's like an inode number and 9p servers use it as such)

if qids had the version field instead be something like an inode generation counter (st_ctime would be a tolerable choice) then you could actually use that to validate whether you're referring to the same file

otherwise, version changes all the time so you've got no help

[hexed solstice]

https://gist.github.com/netbsduser/208a69288c281279f053b4ebd574b506

am i blind?

configure kernel-headers
install mlibc
build mlibc
configure mlibc
install kernel-headers
build kernel-headers
xbstrap: Package has circular dependencies

i simply don't see where this is coming from at all

correcting the typo on implicit_package fixed it, i have no idea why

[lethal osprey]

that's because xbstrap looks for implict_package with the typo

so with the typo mlibc is an implicit dependency of every package without implict_package: true

including kernel-headers

https://github.com/managarm/xbstrap/blob/676fc7e0b0d742e716df9432bd5a5fc0245f8a15/xbstrap/base.py#L1745-L1747

[high solar]

uh

i didn't know about this typo

[hexed solstice]

one of the troubles with having restarted work on a devleopment branch from over a year ago

in that branch (which was focused originally on vmm rewrite with fine grained locking) i foolishly neglected to include the minor considerations needed for 32-bit compatibility and the approach i take to deal with architectures (i.e. m68k) where page tables aren't page sized

so now i have to refit that to get the m68k port working on it

[hexed solstice]

in general the arch-dependent code for pte cursors could use rationalising and this is providing a good opportunity to identify what ought to be done

[hexed solstice]

as a fun excursion i'm thinking of starting work on the keyronex service manager/init system, now that there is enough of a basis in keyronex to host one

[high solar]

So it won't be initware? 😉

[obtuse falcon]

initware my beloved

[deft elm]

ah yes, the British firmware!

innit ware

[high solar]

fixed by @obtuse falcon on xbstrap master (with the typo still accepted for backwards compat)

[hexed solstice]

I can do quite a lot better if unconstrained by systemd compatibility

[high solar]

that makes sense

[hexed solstice]

Solaris SMF architecture

I'd do quite likewise

[high solar]

Btw a few weeks ago when implementing an ipl / preemption disable on Managarm, i looked at keyronex code and noticed that the cost implied by the fact that keyronex can migrate threads at any point in the kernel is quite high

Because that makes it necessary to disable irqs on every ipl down on all platforms that don't have instructions to load/store from cpu local data

which is basically all risc platforms

[final hatch]

Why don't you put the IPL inside the current thread pointer instead, if accessing the CPU pointer requires irq disabled

[hexed solstice]

Riscv using tp relative, aarch64 using x18 relative loads & stores, using those in new branch keyronex to do ipl changes with no interrupt disabling when moving between software ipls

[steep marlin]

Most RISC platforms have registers to serve as a thread-local data pointer

[final hatch]

There are interrupt disable free ways to get thread local access aren't there?

[steep marlin]

RISC-V has tp

[final hatch]

anyway the idea of storing the IPL in the current thread isn't actually that bad probably. the current thread pointer NEVER changes

and the IPL is transferred between threads on context switch

or the context switch happens at a defined IPL

but anyway yeah tp-relative access should just work

[steep marlin]

But at the same time if you're accessing CPU-local data you probably have interrupts disabled anyway.

[high solar]

Ah, that makes sense

I think i looked at the default branch on gh which may have been outdated at the time

[hexed solstice]

Hyena came up with a nice new algorithm, very efficient, it's in his mintia 2 repo

I need to get new keyronex branch up, I've got most of the prerequisites now up I think, even the mlibc changes

[high solar]

That should also work with the caveat that you need to take some care to ensure that the current thread pointer is updated atomically

otherwise you may run into trouble in nmis

[hexed solstice]

the keyronex service management suite in brief summary: init launches the master restarter; the master restarter launches the configuration daemon; the master restarter starts the configuration tool in a mode that scans for changed service descriptions on disk, so that they can be loaded; the master restarter assembles a graph in-memory with the services and instances thereof in the configuration repository; the master restarter starts the services of in-degree 0 and thence onwards the success or failure of those services to start triggers the starting of dependent services. the master restarter directly supervises services of traditional process type, those of other types it demands a delegated restarter to start

the key element of the architecture is a fairly strict separation of concerns, that gives rise to both flexibility and to robustness: the separation of supervision of entities other than simple process-based services means you win the flexibility to represent all sorts of things in the service graph if you write the appropriate delegated restarter; the siting of service description file parsing into a configuration utility is exactly the sort of thing that the langsec people cry out for

[earnest salmon]

can you make it portable

[hexed solstice]

i plan to do exactly that

the bare requirement will probably be something like a subset of the posix api that includes wait(), fork/exec or posix_spawn(), and unix domain sockets

for those of us which have something like cgroups, process contracts, job objects, i can for them provide the ability to more robustly terminate services and to supervise services that double-fork; similar gains if you have procdescs/pidfds

i will also make a best effort to localise the interactions with posix apis, since in principle at least the logic of the service management suite doesn't depend on them

[final hatch]

its literally just a move to a register in all the architectures i can think of. when is it not

even on x86 the msr update is atomic

[high solar]

Hm?

ah you're assuming that you're pointing the tp/gsbase/etc to the current thread struct

[final hatch]

yeah

[high solar]

if you do it like that, that's true

[final hatch]

how else would you do it?

[high solar]

but that design is not universal, there can be good reasons to do it differently

[final hatch]

the operation (of changing the thread pointer) not being atomic implies it has to change more than one thing

if you had to swap the user thread pointer and kernel thread pointer manually, then yeah, you would have issues when handling nmis

[high solar]

I'm not saying it's difficult but it's something that needs to be taken into account

[final hatch]

it is

[high solar]

(i'm not talking about tp register change but about the way you're tracking the current user thread in general)

[hexed solstice]

nowadays i am having the thread pointer point to the cpu struct instead, since on every arch i support you can do a load (or store, maybe even an exchange) of thread pointer with displacement

[final hatch]

i do this too in my OS

[hexed solstice]

if a target permits an offset in a second register you can even provide this for, for example, dynamically allocated per-cpu data

but riscv doesn't

in practice probably a lot of where you would want the like of that is in places where you don't want the cpu to potentially change anyway

[lethal osprey]

yeah if you make your thread pointer register point to the actual thread structure suddenly cpu local access needs guards, whereas if it points to the cpu structure neither cpu local nor thread local access need guards (since current_cpu->thread stays constant across the lifetime of a thread, even if it gets migrated)

[hexed solstice]

so i think it ends up largely a moot point anyway whether you can have dynamic cpu-local data access in a single instruction. if you want it in code where preemption is disabled, you are unhurt by multi-instruction; in other cases you may really want thread-local data (say you have a worker thread per CPU for some activity or other); in the remainder (performance counters for instance) probably you can tolerate a stale CPU

[hexed solstice]

if it points directly to the thread you may even have need of a self-pointer inside the thread anyway on some targets

[hexed solstice]

i'm going to implement and expose process descriptors for posix immediately

process descriptors as in FDs that represent a process and you can wait on them with the standard APIs for waiting for file readiness

(i'm exposing this at the posix level so early because i cba implementing signals before making my start on the service manager)

[rain flame]

pidfd let's go

[hexed solstice]

i'd like to sketch a job/cgroup/contract model as well

it will come in useful

[earnest salmon]

hm fadanoid u gave me an idea

in my kernel i have process handles which are exactly what they seem like, but they are not waitable or anything

it'd be cool if I added support for that in my poll thing

(nooo but I have to fix my xhci driver bleh)

[hexed solstice]

it's so much cleaner

pids are too racy

[hexed solstice]

i'm being selective with which challenges i take on with the "system service manager" (the fairly uninspired name i gave to it)

for one i see no reason to support supervising services that daemonise, any service that still unavoidably does so (there are very few now because it's not favoured for SMF or systemd, and it's not as far as i know supported at all for launchd) can be patched, and this avoids muddying the service state machine and supervision logic with heuristics to figure out a time to guess the pid from the contents of a cgroup/process contract or try to read it from a potentially stale pid file

on the other hand resilience against out-of-memory conditions on platforms which don't overcommit is a more interesting challenge

[hexed solstice]

a rough diagram of the architecture of the service manager

any class of entity that wants to participate in service management can do so by implementing a delegated restarter that understands how to respond to requests like start/stop from ssmd and in turn publish the state of that entity

so networkd can publish for instance network-link:en0 and ip:en0 and, if you have need of depending on a particular link or ip interface being up, you can do so

[vale pelican]

are these plans for initware or such or a new thing (specific to keyronex?)

[hexed solstice]

for a new thing, designed for keyronex but not tied to it, i'm keeping mostly to posix apis with optional use of os-specific stuff, i do use process descriptors/pidfds but if someone had strong need of not using those and just using traditional pids, i could support that at the cost of the inherent raciness of pids

[vale pelican]

ah

interesting

[hexed solstice]

process descriptors are implemented, now for testing

these APIs are added:

pid_t pdfork(int *pdp, int flags);
int pdkill(int pd, int sig);
pid_t pdwait(int pd, int *status, int options, struct rusage *ru, siginfo_t *si);

thanks to pdfork() you atomically get a procdesc from fork and entirely eliminate any possible race

in any software i write for keyronex i don't think i'll ever again use the traditional posix process management functionality

[final hatch]

pdfork? what for

forking another process you have a descriptor to?

why

[hexed solstice]

to fork yielding a procdesc

[final hatch]

wait nevermind

you fork() and it returns a process fd

instead of a process id

okayyy

i see

whats the point of process IDs anyway and why cant I just return process local handle values as the PIDs

do these processes communicate the PIDs between each other

[lethal osprey]

process ids are system-global

[hexed solstice]

in principle there's no need for them, unix had them historically, it didn't have process descriptors because unix didn't realise at the time that process descriptors are more unixy

[lethal osprey]

well you need them to be able to port most posix software but yeah

[final hatch]

what does "most posix software" mean

[hexed solstice]

the skeleton of the new service manager now runs on keyronex just as well

[lethal osprey]

any posix software that deals with processes uses pids to manage them and assumes that pids are global across the system

[final hatch]

the difference between just returning handle numbers as the pids and returning system globals pids, from an implementation perspective, is that for the latter you have system calls to look up processes by pid

such as waitpid

[vale pelican]

i think it's still nice to have (mostly) global ids for users to look at and pass as command args

[final hatch]

and these system calls work on (almost) any process on the system and not just ones you or related processes created

[quick saddle]

is that a posix standard or just common practice

[lethal osprey]

posix standard

[final hatch]

process descriptors are a good feature

i have them in my kernel too by virtue of everything being managed via handles

[hexed solstice]

i wouldn't go as far yet as to say that PIDs should be abolished, but i do think the thought experiment of a world without PIDs should be considered

[final hatch]

speaking of which i should probably get to work on it again, but exam season is coming up and i'm also burnt out from assignments

i had like 7 or 8 assignments to finish just in the last 2 weeks

[quick saddle]

What would one replace them with?

[final hatch]

I agree, sort of, but there should be a way to look up processes globally on the system

otherwise, some malware may be hard to detect since you have no way of finding its process

and what else would you identify a process with? image name? not nearly unique enough

[hexed solstice]

i wouldn't want to do without them, they eliminate an entire class of race condition i don't want to deal with (pid reuse tocttou)

[final hatch]

randomly generated uuid? sure

[final hatch]

true

[quick saddle]

Or snowflakes

[final hatch]

those two are kinda in the same ballpark as pids

[hexed solstice]

probably something is possible with the chain of supervision from the service manager down and if you add something like job objects/contracts/cgroups to identify groupings of processes

[quick saddle]

You avoid reuse tho

[final hatch]

sure

unfortunately i believe pid_t is 32-bit int no matter what so we can't just use snowflakes for pids 😔

seems like its implementation defined

but idk if any programs allow 64-bit pid_t

[quick saddle]

doubt it's that big of a deal

[lethal osprey]

technically posix doesn't mandate pid_t is 32-bit as long as long is >32 bits, but in reality so much assumes pid_t is 32 bit that doing anything else is infeasible

and while things written in c/c++ might just work regardless of that assumption, the real issue lies in FFI bindings

for example i'm pretty sure when java gets a pid_t from native code it just stores it in an int

[steep marlin]

Not ideal

I use 64-bit PIDs atm 😬

[hexed solstice]

I have a temptation to implement doors 🚪 at some point in the near future

Pthread cancellation is called for as part of this

[final hatch]

what are they ?

[hexed solstice]

"Migrating thread" IPC mechanism

[hexed solstice]

to give a fuller answer now i'm at home

doors is one incarnation of the the general family of IPC mechanisms that was born with LRPC from TAOS (as described by bershad and friends https://people.eecs.berkeley.edu/~prabal/resources/osprelim/BAL+90.pdf)

the principle of which is direct transfer of control between an RPC client and server context

you can think of it as like a generalisation of the system call

a system call lets you call the kernel from the user program context, while doors and similar make it so that you can call one user program (an rpc server) from another user program context

[final hatch]

I see

[hexed solstice]

one thing i am undecided on

is it a true and direct transfer of control within a thread? or is it a fast transfer from one thread to another, with optimisations like the server thread gaining any remaining timeslice of the client?

in the latter case: the server creates threads which immediately call a "door receive" syscall and are then put in a lightweight sleep ready for invocation. in the former case: like the first, but the "door receive" call can actually deallocate most of the thread's kernel-side state, and just save its userland context (we'd do this odd thing, because mlibc has to allocate TLS and other userland thread state)

in either case there are interesting considerations: suppose the client process dies (another thread SEGVs say) while "in" the server? in solaris, since there is a distinct thread in the server running the request, that thread gets a pthread cancellation (if desired, it's optional, otherwise it just runs through and exits and that's the end of the story). this seems a bit harder to manage in the former scheme, because you'd need to take the activation and get it finished up somehow; you can't just make away with it

[high solar]

NOVA (the microkernel other than Managarm's that I'm most familiar) has three types of capabilities related to this: scheduling contexts (SCs), execution contexts (ECs) and portals (= doors)

ECs are thread register images

SCs can be attached to ECs to actually run them

portals have an EC attached that initially has no SC (and hence never runs)

when you do an IPC call through a portal, the kernel takes the current SC and attaches it to the portal's EC

on IPC reply, this is reversed

when the portal's EC is currently busy when an IPC call is done, the kernel does priority inheritance (i.e., it attaches the waiting SC to the EC that it's waiting on)

[hexed solstice]

now that's interesting

priority seemed to me a very salient concern with the "migrating thread" model like this (in the other model you might just have the server threads be higher priority than all clients) and this solves it quite nicely

[sullen fern]

NOVA in general is really interesting

really fast

[earnest salmon]

@hexed solstice what TCP extensions does keyronex support/will support

[quick saddle]

this is post has been sponsored by the bluerock lobby

jk nova is a cool microvisor

[hexed solstice]

at present none, other than what's advised in rfc 9293. i will certainly add window scaling also

[earnest salmon]

I see

will you add selective ACK?

[hexed solstice]

i would like to, it involves a little complication but i think it's not unreasonably diffficult

with doors although i think doing what in Spring is called shuttles - where "threads" as kernel objects are much more limited (more like bags of userland state) and the schedulable entity is the shuttle composed of stacks of these threads - is very cool, i am slightly more inclined to instead do true threads, do a specialised handoff logic when making door calls/returns that donates remaining quantum and lends priority to the target, and thus get most of the same properties. i think the only real loss, if you do this, is that you have to keep the kernel-side thread state allocated throughout. but conceivably at least some of that could still be ditched (kernel stack for instance), because it's not needed till the thread is needed to service a call, or to be gotten rid of

spring doors discussed in https://sites.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/smli_tr-93-14.pdf for the curious

TAOS cited there of course

We have chosen to use an alert mechanism similar to that provided by the Taos system [Birrell et al 1987].
Briefly, associated with each thread is a single bit specifying whether that thread is alerted. Whenever a thread sleeps it can specify that it should be awoken from that sleep with an exception if it is alerted. A thread can also poll its alerted status explicitly and set or clear it as it pleases. Or, by default, a thread may simply decide to ignore alerts all together.
@neat steppe may like it

others might find it reminiscent of pthread cancellation

i have the conjecture that pthread cancellation might have originated as an attempt at nativising these semantics to unix, but i have absolutely no evidence of that

the reason i suspect it is because as far as i know, sun was leading in unix threading and so i'd be very surprised if they didn't shape discussions greatly on pthreads. and pthread cancellation just feels like a rough nativising of TAOS alerts to posix

exactly the sort of thing i would expect when sun adapts doors into solaris, and then submits features of that adaptation to do with thread cancellation to posix committee for consideration

[hexed solstice]

tcp performance at the moment, checked out of interest. there is much to improve on but not an awful start

[wet apex]

very nice

[sinful jetty]

Holy

[marble crag]

My internet would bottleneck first

[hexed solstice]

Download from within a VM from your host

[hexed solstice]

i'm in a solaris mood lately

the service manager is very inspired by SMF, STREAMS are most well known from solaris, i want to implement doors ipc, and i am even getting tempted by the solaris approach to synchronisation

in solaris there's very little use of spinlocks to synchronise, instead almost everything by sleeping locks. even interrupt context is allowed to use sleeping locks

by the expedient of keeping an interrupt thread per interrupt priority level per cpu available. when an interrupt happens, it's done on the stack of the appropriate interrupt thread; if the interrupt tries to block, the dispatcher notices that it's in interrupt context and the interrupt thread is declared asleep

[high solar]

Oh, I didn't know that Solaris has doors

[hexed solstice]

they picked it up from spring at some point

[earnest salmon]

isnt Solaris that one OS I search in config.sub when im tryna add obos to the list

[hexed solstice]

work is underway on getting the repo up. i have a lot of reconciling to do

and i will implement doors ipc

[sinful jetty]

repo of what?

[hexed solstice]

keyronex

in late 2024 i started work on a local branch which included a suite of improved things, i forgot about it for about a year, then rediscovered it not long ago

[sinful jetty]

ohh

[twin haven]

Exciting! I'm keen to give it a read.

[hexed solstice]

i'm preparing to tackle priority inheritance and i wonder again whether solaris making the thread lock a pointer to a lock (either the integral lock of the thread, or the transitional lock, or a runqueue lock, or a sleep queue lock) would turn out to be useful here

i suppose i'll find out in due course

it's almost turnstile time

[prime coyote]

i thought you were doing pushlocks already

[sullen fern]

I still find it interesting that the BSDs cargo culted this

[hexed solstice]

https://docs.freebsd.org/en/books/arch-handbook/smp/ the smpng manifesto for freebsd (based on the smpng manifesto for BSD/OS)

this is what made matt dillon fork

[sullen fern]

why?

[hexed solstice]

dillon was for localising and partitioning state instead and generally taking an approach more like scaling down a distributed operating system to a single machine

[hexed solstice]

sleeping locks in pageable memory is an interesting challenge, i might need to consult the mintia turnstiles

it's challenging in the solaris style turnstiles because the turnstile chain spinlock synchronises elements of the lock word's state

[neat steppe]

i figured out a way to make that not be a problem

[hexed solstice]

the best solution i can immediately generate is to do fault-fallible CAS on the lock word (unwind and indicate failure if there's a page fault) and avoid committing to certain things that solaris does while the turnstile spinlock is held because it knows that it can touch the lock word with the spinlock held

[neat steppe]

thats exactly what i did

[hexed solstice]

solaris is doing a sort of semi-fair direct handoff in some circumstances which is hard to square with this

since there the new owner is decided with the chain lock held, the new lock word is written and then the needful waiter signalled

[outer hill]

I've never planned to support pageable kernel memory, but this is a wee bit more interesting than I'd thought.

Could you tell me if I'm understanding the problem correctly?

In simplified terms, the chain looks like this:
acquire the primitive's interlock (or the turnstile chain lock),
choose the next owner,
write the lock word / hand over ownership (under the same lock?),
wake the chosen waiter.

That seems to work fine if the lock word is guaranteed to be resident. But if the lock word can fault you can't safely touch it while holding a spin lock, because a page fault may block.

[valid sequoia]

@hexed solstice
bit of a random question that i thought thinking of freebsd td_lock being a pointer now

void ki_wake_waiter(kthread_t *thread)
{
    ipl_t ipl = ke_spinlock_acquire(&thread->lock);
    kassert(thread->state == kThreadStateWaiting &&
        thread->wait_status == kInternalWaitStatusSatisfied);
    thread->state = kThreadStateRunnable;
    ki_thread_resume_locked(thread);
    ke_spinlock_release(&thread->lock, ipl);
}
void ki_thread_resume_locked(kthread_t *thread) {
    ...
    ke_spinlock_acquire_nospl(&chosen->sched_lock);
    TAILQ_INSERT_HEAD(&chosen->runqueue, thread, queue_link);
    chosen->reschedule_reason = kRescheduleReasonPreempted;
    ke_spinlock_release_nospl(&chosen->sched_lock);
    ...

who locks kthread_t.state?

void ki_reschedule(void) {
    // old_thread.lock held
    // cpu->sched_lock held
    next->state = kThreadStateRunning;

next->lock isn't held, only old_thread's is?

[hexed solstice]

This is why I'm inclined towards making the thread spinlock be a pointer

As when on a run queue I regard it as locked by that run queues cpu sched lock

[valid sequoia]

in mine i lock next->lock but that's a lock order violation by itself: the only way it could happen though is if two threads mutually try readying eachother.
the state change should make one win the race so the other notices early that the thread is runnable and doesn't proceed in sched_switch locking the other

i could still have a cycle with 3 threads though?

[hexed solstice]

in my case the thread resumption is only callable through a single wakeup path, and that is entered only with exclusive custody of the thread, so no one else could ever try to resume it

(i should'vep repared the new repo by now but i've been sidetracked by a) restoring at least the m68k port to full working order and b) turnstiles, improvements to STREAMS, and other things i want to do)

[valid sequoia]

ownership of the old thread though, not of the new thread though

[hexed solstice]

i've gotten really enamoured with the solaris approach to interrupts

viz. dispatcher priority > most hardware interrupt prioities; most hardware interrupts are arranged to start running on another stack at once (one stack per cpu per IPL < dispatcher level); synchronisation is by sleeping (but adaptively spinning) mutexes; if an interrupt handler does have to sleep awaiting a mutex, then it is 'passivated' into a true thread of very high priority, which is lent to the owner

i don't intend to implement it at present but maybe some day

[hexed solstice]

i've sketched turnstiles and a turnstile based rwlock

i haven't got a great answer to how to make it possible to put them in pageable memory yet (i have an answer but it's not a great one; requires that 2 fallible atomic operations be done with a turnstile lock held in some cases)

anyway i haven't foreclosed on the possibility with my implementation, there is a relatively simple way to do it, so i'm happy with that

[neat steppe]

do you have a special requirement that stops you from copying my way

[hexed solstice]

no, just trying to not be cheeky and reprint the mintia code in c

[neat steppe]

my impl has a limitation currently which is that i dont propagate priority changes to a thread that occur after it already blocked on a lock

like explicit priority changes

done out of band

(as opposed to priority changes caused by propagation of priority from someone who blocks on that thread to release a lock, which are ofc propagated all the way through the waiter chain)

ughhhh i just realized a bug

if you raise a thread's priority explicitly while its blocked on a lock, that isnt propagated

later if someone of lower or same priority tries to propagate inheritance through that thread, it will see the higher priority and wont continue down the chain because of an assumption that any further threads have been boosted appropriately to the same level

stupid of me

i guess ill have to make sure i propagate explicit priority changes

[hexed solstice]

interestingly enough solaris doesn't in this case either

it does adjust the sleep queues but it doesn't try to propagate any further

[lusty gyro]

as far as I remember, they have a fairly simple implementation

[hexed solstice]

it has some interesting livelock avoidance logic

they identified a case called 'dueling losers' where essentially thread 1 and thread 2 are both trying to follow a blocking chain and boost, one chain leads t1 -> t2, the other t2 -> t1

in principle if you just repeatedly trylock then you can end up with a situation where both keep failing to trylock the other

cantrill was a mathematician by training and you can really see the sun engineering ethos in the fact that himself and jeff bonwick identified this possibility (which must be extraordinarily difficult to occur in the first place, and even harder to persist for more than a very transient period) and treated it with the turnstile_loser_lock

[sullen fern]

I am aware of this case and decided to ignore it, because it would require like the two CPUs running in lockstep essentially

[neat steppe]

give me an example for how this can happen if there are no lock hierarchy violations

[hexed solstice]

first bear in mind that the thread locks are pointing at turnstile chain locks

and the turnstile chain i'm on is not given up (netbsd does that) to acquire another

then that's how you can end up with the case of trying to take two in reverse order

[neat steppe]

Right that makes sense then

I think my impl is immune to that one

I don't believe i trylock a chain lock while holding another chain lock

I do that but while holding a thread lock (which is out of order hence the try) which shouldnt cause the same issue

I'm gonna explore two avenues for propagating priority changes which are to either call the chain boost logic directly from the raise priority function, or break the waiting thread out of its wait and let it loop back through the turnstile logic and re-boost the chain itself

Depends on the synchronization issues i run into

[prime coyote]

how would priority inheritance work with pushlocks?

map pushlock to turnstile head by hashing lock address to a bucket and on contented acquire fill a thread local record with lock and waiter pointers

and link that record into the turnstiles waiter struct

or maybe you could host the turnstile node in the pushlock wait blocks

[zenith karma]

i have no idea how pushlocks are implemented exactly

[neat steppe]

thats not really a pushlock anymore

[zenith karma]

but assuming its similar to how my janky ass mutexes work[ed in an older project] (spinlock on the first waiter LSB or something like that to access the first waiter struct, then the waiters form a circular linked list) its pretty straightforward to implement PI by manipulating the waiter list

[neat steppe]

how

[zenith karma]

something kinda like skip list would work i think?

[neat steppe]

issue is that the waiter chain you need to boost is like

cross-lock

[zenith karma]

ah hm

yea but thats just following the pointer chain, no?

hm it might be a bit tricky to implement this without taking some slightly annoying locks

[neat steppe]

if im thread A and i hold lock 1
and then im thread B and i hold lock 2 and block on lock 1
and then im thread C and i hold lock 3 and block on lock 2
and then im thread D and i hold lock 4 and block on lock 3
and then im thread E and im a really high priority thread and i block on lock 4

[zenith karma]

yeye i get the problem

[neat steppe]

then i need to follow a chain of

[zenith karma]

theres like two parts to the problem

[neat steppe]

4 -> D -> 3 -> C -> 2 -> B -> 1 -> A

[zenith karma]

first, figuring out which thread owns a given lock

[neat steppe]

boosting all the threads along the way

[zenith karma]

and second, boosting it by walking the whole dep chain

i.e. you need to be able to go from sync object -> thread and thread -> waited-for sync object

[neat steppe]

ive yet to see an implementation of this that does not somewhere have a lock ordering inversion

dealt with as a trylock and retry on failure

[zenith karma]

oh well its easy to do that

you can take a global lock over all mutex operations except for the lock wait (which you do as a condvar)

and its obviously awful but that proves its possible

[neat steppe]

solaris and mintia both have a trylock/retry idiom somewhere

unknown if autoboost does

@lusty gyro ?

[prime coyote]

what about xnu turnstiles

[neat steppe]

probably

[zenith karma]

if your lock has nontrivial deinit and your threads are RCU'd, then i think you can implement a lock-free "find the thread which is ultimately indirectly responsible for this lock" op

[prime coyote]

https://github.com/xrarch/mintia2/blob/a9e9f076e2cc417cc535553be4dead81967c2d03/OS/Executive/Ke/KeTurnstile.jkl#L242 ?

[neat steppe]

yes

[zenith karma]

but that could have an ABA, i think, not sure

id have to think more about it

i will tho

but im pretty convinced you can do it with no trylocks and without a sucky huge lock over everything

[lusty gyro]

Not really

[neat steppe]

deferring upon failure to get a lock counts as this

does that happen

[lusty gyro]

I know legacy autoboost has a try-convert path but it's not the same problem (they attempt to convert shared to exclusive, if fail update some state and retry)

in autoboost they use deferred propagation heavily so next hop is handled by queueing

[neat steppe]

probably they do that because of lock ordering

[lusty gyro]

they have spin-until-acquired locks (entry byte lock, head spinlock) and thread centric processing in a worker

[lusty gyro]

they don't work synchronously like turnstiles, but postpone heavier operations like processing of self IO boosts or propagation, which makes sense

[neat steppe]

i think that may be for a different reason than you think it is

the overall overhead of that is gonna be larger than doing it on the spot

i think they have a more structural reason for doing that rather than a performance one

its quite rare for a waiter chain to be longer than 1 or 2

like, really rare

so theres no performance reason to add the overhead of deferment to the case of short chains

https://open.spotify.com/track/4LNFBPTsW7t6Z8bi9zasUp?si=e82f6391c9cd4e11

theme song

[lusty gyro]

especially since this is already happening when contended

[neat steppe]

i think the deferment may be to evade lock ordering inversion

https://open.spotify.com/track/1YNcvRZoNJUjR4opG7Qr9o?si=664826d567924167

[lusty gyro]

I'm sure it matters a lot but probably that's not all

deferred processing also occurs at higher IRQL level and is sometimes closely integrated with the scheduler

[prime coyote]

wait is it dpc

cant you defer that processing at passive level

[lusty gyro]

by the way, it's very interesting to look at from the point of view of turnstiles because I haven't seen any implementations of priority inheritance except for autoboost

what is taken for granted in one system is handled differently in another system

and that system is dealing with its own issues

[sullen fern]

It's also a band!

[prime coyote]

whats an example of integration

[neat steppe]

yeah but idc about the band and those are both songs i actually happen to listen to sometimes

[lusty gyro]

they are batched, and their deferred-ready-and-flush-batch mechanism works with batches

[woeful spear]

In case you haven't yet got a reply, no, that doesn't happen

It doesn't trylock and then queue

[neat steppe]

i think the deferment side-steps the lock ordering inversion

[woeful spear]

They always enqueue a worker because this work is always deferred in per-CPU batches

For example, for user mode stuff, they only look at them at context switch moments when needed

Which are reasonable points

[woeful spear]

Yup it's structured differently, they don't have that problem in the end

[neat steppe]

i mean theres a possibility they encountered that problem and their solution was deferment and to make that perform well they added the batching

[woeful spear]

Yeah

But I don't even know what was going on in their first version

I haven't looked at Windows 8 Autoboost

And I don't remember if there is a separate worker for their IO boosting?

[lusty gyro]

this is one of the questions that would be interesting to ask their team

I personally doubt that they started down this path with deferred work, and most likely it was something like that

[prime coyote]

apparently they dont doit exactly that way

https://github.com/apple-oss-distributions/xnu/blob/f6217f891ac0bb64f3d375211650a4c1ff8ca1ea/osfmk/kern/turnstile.c#L3093

its implemented as reserve-wait-recheck rather than trylock-and-retry

[hexed solstice]

one fun challenge for turnstiles: priority inheritance also for userland

[high solar]

I guess the difficulty of that greatly depends on how your userspace mutex interface looks like

[hexed solstice]

illumos seems to go straight to the kernel to do all lock/unlocking of a pi userland mutex, but we know from futex-pi that there's a way to do it without needing the kernel in the uncontended case

[hexed solstice]

at this point i've mostly finished up with the new features i wanted to add, so i expect to speed up the pace of getting everything into the new repo

hopefully there are no snags

i do need to give devfs an improved treatment and i want to implement the new STREAMS scheduler that no longer runs predominantly at dispatch level

the new principle is that there is a STREAMS worker thread per core, every stream has a mutex covering processing in every module within that stream (i don't see a good reason to make that finer-grained), there is a worker thread per core and when a NIC driver receives a packet, for instance, it queues it to a per-stream ingress queue (spin-locked so i can do it from NIC rx dpc context) and wakes the worker thread; while a thread submitting message blocks to a stream can go ahead and do some processing if it wants

there are several things which might be cool to do eventually (making IPL solaris-like with magic interrupt threads; NUMA support) that are simply not going to be done until sometime after i get this tree back to running xorg and such, because otherwise i could find myself, ever lending gratification to the future and never taking any to enjoy in the moment, fain to keep my motivation as bankrupt

[hexed solstice]

almost back up to mounting root on m68k

then the next logical step will be sorting out the vmm, and thence hopefully on to userland execution on m68k again

aside i have no particular desire to write a tutorial but i am tempted to write up a little starter pack resource for those who want to target m68k

a few very broad strokes about the architecture itself, how to use the goldfish pic, rtc, and serial, some brief notes about how they, virtio-mmio, and the architecture connect, a link to https://github.com/DeanoBurrito/lisp, that ought to be enough to get started without having to look at qemu m68k source code or at how keyronex/northport/obos did it

paired with the 68040 manual that's probably enough to port your own kernel

[neat steppe]

can you do recursive paging on 68k

[hexed solstice]

on the 68040 (which implements a subset of the 68030 mmu, which is itself a subset of the discrete MMUs available for earlier 68ks) not trivially at least

the 68040 only allows a 3-table configuration, let's call them PML3, 2, and 1 where PML3 is root and PML1 is leaf and suppose we use 4k pages instead of 8k (the other option.) then PML3 is 128 PDEs, PML2 is 128 PDEs, and PML1 is 64 PTEs, so the bits contributed by each level are 7, 7, and 6 respectively

no, unfortunately i really can't see a way to make it work on the 68040

you'd have to target the 68030

[neat steppe]

the leaf being the smaller one is the problem

if the root table were the small one then it might be more workable in a similar way to how they did recursive page tables on PAE x86

[hexed solstice]

yeah, it makes it quite impossible. i suppose this was what they felt the most popular configuration was. you can do it on the 68030 because you can configure how many bits you want each level to contribute so you can even just do 4k pages with 2 tables contributing each 10 bits there and get the exact same geometry as you are used to

[neat steppe]

ive been considering something

i might remove all of the page table dependencies in mintia2 kernel and abstract it out entirely into something like a pmap module

[sullen fern]

What do you mean by that? Isn't page table code already abstracted?

Or do you do the thing where architectures provide their view of the pte and you edit that directly

[steep marlin]

Certainly sounds like it. This seems to be somewhat common here for the multi arch kernels.

[sullen fern]

Idk I don't do that

I have a pmap-like interface

I can't really have pte views since I have to run on Linux as well

[hexed solstice]

from a pragmatic point of view i think the main reason why mach, sunos vmm had that thoroughgoing abstraction - the diversity of ways in which real MMUs expected to see address spaces described - is no longer the case, now everything is using conventional radix tree type page tables

but there are still some other reasons to go that way

a few of them are: 1) not inherent but it's easy to end up depending on things like "page size = page table size" which is no longer true and in the age of 16 or 64k pages it's turning into madness to require you have a page-sized group of tables at once at each level; 2) also not inherent but if you have a robust pmap abstraction then probably you can more easily deal with doing things like, for instance, a very fast path which avoids contended locks for handling things like software A-bit setting faults; 3) it's aesthetically nicer and generally cooler to have the abstraction

[high solar]

you can also have both abstractions if you need to

where you implement the pmap for most archs based on a PTE abstraction

[hexed solstice]

this saves what would otherwise be a lot of code which is almost certainly mostly duplicated and the tendency for code like that to subtly diverge, fixes in one copy but not the other, that sort of thing

[hexed solstice]

speaking of pmaps i'm reintegrating the vm with a few hopefully small refactorings

this may be the most painful part or it may just work and on m68k too

[hexed solstice]

unfortunately no such luck

[hexed solstice]

[libc (-2139172916 Entering ld.so)]: Entering ld.so
[libc (-2139172916 ldso: Own base address is: 0x40000000)]: ldso: Own base address is: 0x40000000
[libc (-2139172916 ldso: Own dynamic section is at: 0x4002c1f0)]: ldso: Own dynamic section is at: 0x4002c1f0
[libc (-2139172916 AT_PHNUM: 6)]: AT_PHNUM: 6
[libc (-2139172916 AT_PHENT: 32)]: AT_PHENT: 32
[libc (-2139172916 AT_PHDR: 0x2034)]: AT_PHDR: 0x2034
[libc (-2139172916 AT_ENTRY: 0x21a4)]: AT_ENTRY: 0x21a4
Fatal: ../../../../kernel/common/os/syscall.c:53: Unhandled syscall number 26

good enough for tonight, i'll wire up the syscalls tomorrow

[obtuse falcon]

what's the big negative number

is that a pointer

[hexed solstice]

should be pid and process name but there isn't yet

so it's just the pointer to the copy of the string (i didn't notice this at first, lmao)

[hexed solstice]

[libc]: Leaving ld.so, jump to 0x21a4
[libc]: Hello from userland!

great, m68k seems to be coming back up nicely

i can only pray fork() also just works on m68k but i won't tempt fate

[obtuse falcon]

neat

[hexed solstice]

current work is the new STREAMS scheduler

[hexed solstice]

the trouble with doing these refactorings is you just end up tracing ground you've already crossed

the result will certainly be worth it but it is a bit boring really

[hexed solstice]

[root@keyronex /]$ help
GNU bash, version 5.2.15(1)-release (m68k-unknown-keyronex)

tomorrow i'll look at forking and such, but in this respect the m68k port is now further than before (now you can type input on it)

[earnest salmon]

I really need to fix my m68k port

but this is really cool nonetheless

[high solar]

very cool

is this now on the default branch or is this yet another "next gen" branch? 😄

[hexed solstice]

this is the branch to end branches

the story of the last one is that in 2024 i did a near-rewrite of parts of the kernel as part of a ploy to make hackernews bait

so that was only targeting primary riscv and secondarily amd64 as that made it easier, but i ended up making a lot of improvements

but it wasn't keyronex really

anyway for the last 3 weeks i've started with a blank slate and pulled in the best of both, re-porting to m68k as i go

[hexed solstice]

cool, fork() seemed to work, but i need to do some further vmm adapting to m68k to go further

[hexed solstice]

[root@keyronex /]$ cat /etc/passwd
[libc]: mlibc: fadvise() ignored due to missing sysdep
root:x:0:0:Charlie &:/root:/usr/bin/bash
Fatal: ../../../../kernel/common/posix/syscall.c:94: TODO: not yet implemented

great, forking and execing seem to work fine

one thing of note btw, i wonder if anyone else encountered this oddity when building coreutils for m68k or perhaps for some other platform:

/ws/Projects/Keyronex/build/m68k/system-root/usr/include/unistd.h:278:24: error: conflicting types for 'gl_intptr_t'; have '__mlibc_intptr' {aka 'int'} 278 | typedef __mlibc_intptr intptr_t; | ^~~~~~~~ ./lib/stdint.h:317:18: note: previous declaration of 'gl_intptr_t' with type 'gl_intptr_t' {aka 'long int'} 317 | typedef long int gl_intptr_t; | ^~~~~~~~~~~

gnulib for coreutils specifically ends up defining its own gl_intptr_t as a long int but on m68k it's an int

[hexed solstice]

  tzh_ttisstdcnt = 117440512, tzh_leapcnt = 0, tzh_timecnt = 4060086272, tzh_typecnt = 117440512,
  tzh_charcnt = 285212672}```
that doesn't look very healthy

ah i see

    tzfile_time.tzh_ttisgmtcnt = mlibc::bit_util<uint32_t>::byteswap(tzfile_time.tzh_ttisgmtcnt);

several more unconditional byteswaps follow

[hexed solstice]

and now another step forward on m68k:

[root@keyronex /]$ ls -al /
total 16
str_ioctl: TIOCGPGRP with no tty_pgrp
drwxr-xr-x 0 root root 4096 Feb 21 17:42 .
drwxr-xr-x 0 root root 4096 Feb 21 17:42 ..
d--------- 0 root root    0 Jan  1  1970 dev
drwxr-xr-x 0 root root 4096 Feb 22 11:57 etc
drwxr-xr-x 0 root root 4096 Feb 21 21:24 usr
[root@keyronex /]$

[hexed solstice]

operating systems once had to grapple with adding 64-bit support but i have the opposite problem

lots of odd things going on with 32-bit

files ending up at absurd offsets

[final hatch]

well, yeah, thats bound to happen when you make assumptions about 64-bit, even unknowingly

one of the big things i had to get past in boron was the use of the HHDM. i still don't think it's entirely gone but for most purposes alternatives exist

(there is still an HHDM that maps the first 256 MB of the physical address space)

i did a lot of things in such a way that i didn't have to modify them for 32-bit, though, such as using uintptr_t/size_t in place of uint64_t, and keeping file offsets and sizes 64-bit

[hexed solstice]

it looks like my first priority will have to be the syscall interface

in particular off_t is 64-bit but i have no provision for 64-bit syscall values on 32-bit platforms, and with other steps along the way, i observe problems that look like the value was zero-extended at some point along the way

[sullen fern]

Is it a good idea to still use 64 bit integers in 32 bit code?

or is it gonna be slower

[hexed solstice]

i need to do freebsd-style syscall generation

[sullen fern]

like im using size_t for most stuff but I have a few uint64_t at some places

and uint128_t even

[final hatch]

You should if you're dealing with time values and file offsets

[sullen fern]

yeah okay

thats what i do

the 128 bit is for timekeeping

[final hatch]

It can be slower, but not by much

[hexed solstice]

freebsd is doing this kind of thing to autogenerate their system call marshalling:

        int sctp_generic_recvmsg(
            int sd,
            _In_reads_(iovlen) _Contains_long_ptr_ struct iovec *iov,
            int iovlen,
            _Out_writes_bytes_(*fromlenaddr) struct sockaddr *from,
            _Out_ __socklen_t *fromlenaddr,
            _In_opt_ struct sctp_sndrcvinfo *sinfo,
            _Out_opt_ int *msg_flags
        );

[hexed solstice]

i feel a bit drawn to the aside of implementing multi-queue NIC support with RSS

i changed how STREAMS works: now there are threads bound to CPUs and a stream has a designated home CPU number, and all processing within that stream is directed to that core. so there is there a foundation for it

[hexed solstice]

i really love STREAMS

by far one of my favourite elements of the kernel

it has everything good: async, message-passing, heritage to dennis ritchie himself

[lusty gyro]

what would you recommend reading about STREAMS?

[hexed solstice]

ritchie introduces it here https://www.nokia.com/bell-labs/about/dennis-m-ritchie/st.pdf and in the books about various unixes of the past there are further details

[hexed solstice]

i've reimplemented pipes (and the foundation for FIFOs) for the new STREMS

now it's time to figure out how unix domain sockets will work

[neat steppe]

@hexed solstice what do you think a good pmap type of abstraction should look like

id like to ask that rather than blindly copying whatever the original mach pmaps would do

[hexed solstice]

the first thing i would say is that mach and family do pmap_enter() for mapping a single virtual to physical address

this stateless interface is not efficient if you are wanting to put in sequential entries

so expose a cursor concept

you will naturally be able to implement that in a way that's efficient for most pmap arch-specific implementations

(for inverted page tables it's another matter but you may never target such an arch)

i also believe there is a case for siting at least part of the page replacement logic in pmap

[neat steppe]

inverted page tables are a big reason im interested in switching to a pmap model at all

a ppc mac port sounds fun

[hexed solstice]

one thing you may want to have a good answer for, for riscs, how do you efficiently do a-bit setting faults? can you avoid taking contended locks?

[hexed solstice]

in that case you can probably live without that feature

freebsd seems to live without it

[high solar]

Managarm uses range based interfaces for everything but faulting

    virtual frg::expected<Error> mapPresentPages(VirtualAddr va, MemoryView *view,
            uintptr_t offset, size_t size, PageFlags flags, CachingMode mode) = 0;

    virtual frg::expected<Error> remapPresentPages(VirtualAddr va, MemoryView *view,
            uintptr_t offset, size_t size, PageFlags flags, CachingMode mode) = 0;

    virtual frg::expected<Error> faultPage(VirtualAddr va, MemoryView *view,
            uintptr_t offset, FetchFlags fetchFlags, PageFlags flags, CachingMode mode) = 0;

    virtual frg::expected<Error> cleanPages(VirtualAddr va, MemoryView *view,
            uintptr_t offset, size_t size) = 0;

    virtual frg::expected<Error> unmapPages(VirtualAddr va, MemoryView *view,
            uintptr_t offset, size_t size) = 0;

• an interface to submit shootdown

MemoryView is the object that resolves mapping offset -> physical address

[flint anvil]

But isn't it only for normal page table arches?

[high solar]

We will probably add a agePages(VirtualAddr va, size_t size) function in the future that flips A bits to zero

[prime coyote]

sorry for off topic, does managarm have priority inversion protection mechanisms ?

what kind is it

[high solar]

Managarm almost never uses locks that put a whole thread to sleep so it doesn't suffer from "classical" priority inversion. However, it doesn't have a protection against running a low priority async task in a high priority thread yet. That's actually something I'd like to have at some point but it requires non trivial research/engineering

This probably only matters for async work that does non-trivial amounts of CPU compute though

Maybe the solution to that is offloading to a thread and then relying on PI as usual

(Just thinking out loud here, not Keyronex related :^)

[sullen fern]

What is a cursor?

[high solar]

More importantly it also does not boost yet in the case where a low priority thread does high priority async work

Say, for example, I have a USB HCD running at low priority but I want to retrieve a webcam frame

then I probably want to boost the HCD for the duration of that operation

[sullen fern]

What kinda locks do you use then?

[high solar]

For cases where other kernels would use sleeping locks, we use async locks that only put a coroutine to sleep

[hexed solstice]

some handle pmap defines to whatever maps a virtual address. the concept really only works for traditional page tables, i think, but i think it could be useful even for that alone

in my case i store the vm_page_t * pointer for each table level and include a pin on the page refcnt so i can cheaply increment/decrement the cursor until a page table boundary is reached, without having to redescend through the tables

[vale pelican]

we do something similar for the actual pt manipulation as well

[sullen fern]

Ah okay yeah that's what I thought, managarm has that

I can't do that tho since I have to handle weird mmus

[hexed solstice]

i like this for being able to do, for instance, clustered pagefaults, but a "map n pages from va a to b, pointing to this array of vm_page_t *" or similar interface works just as fine

[sullen fern]

I think I'll just have a range based thing

That is handled by pmap itself

Instead of a cursor

[sullen fern]

Because of this

[outer hill]

If I understand you right, you mean the system components, but what about third-party user programs? They can create an inversion, and they rely on the kernel to fix it, right?

[hexed solstice]

you can (you can imagine the cursor interface as some object implementing a protocol with methods like "Map a page at current point", "Offset current point by n") just it's grossly mismatched as an interface to, say, an inverted page table

that it pins the vm_page_ts of the page table pages is just an implementation detail

[sullen fern]

I'm running on linux

Where mapping a page is calling mmap on a memfd

It'd be doable but it would be awkward

I suppose I could still do it but I'd have to have an additional layer of abstraction on top

[hexed solstice]

i concede it's actually a lousy abstraction to expose as part of pmap, unless you are only implementing a pmap for radix-tree type page tables, or VAX page tables, but it falls apart completely for others

[sullen fern]

Yeah I think it's better to keep the details of pmap hidden in my case

Though it totally makes sense if you use traditional page tables

[hexed solstice]

since it is sensible to implement also a generic pmap implementation for the common case of radix tree type page tables, i think the abstraction is still worthy for those for internal use by your range-based mechanisms

but as for what i was suggesting earlier i think an interface pmap_enter_range(vaddr_t start, size_t n, vm_page_t *page[n]); is actually the better abstraction to offer as part of the pmap interface

[sullen fern]

yeah that's a good point

[high solar]

which matches exactly what i posted here #1064583713184292894 message

[hexed solstice]

when it comes to any abstraction, you can always count on managarm to have a good story for it

did you refer to mach pmap or did you derive this from first principles?

[sullen fern]

What is a memory view?

[high solar]

For the purposes of this interface, essentially a mapping from offsets to physical addresses (same role as the vm_page_t array in Fadanoid's signature)

[sullen fern]

How do you handle multiple page sizes? Is it in flags?

[high solar]

I looked at the Mach pmap once but not when adding this abstraction. I think this abstraction was added when unifying host pages tables and nested page tables (EPT/NPT)

[high solar]

We don't handle it yet but the plan is to attach a order of two size to each page

i.e. in the mapping provided by the MemoryView

basically let the "what is the page at offset X into this mapping" function return "it's physical address P, part of a contigous, naturally aligned 2MiB region"

[sullen fern]

Ah

I guess you could do it through flags as well

[high solar]

which would allow the pmap to chose between 4k or 2M pages for the affected range (because it can just mask out low bits to find the starting address of the contiguous block)

So this decision would be done by the pmap implementation, not by the caller

[sullen fern]

So memory view also has a size property?

Or does it infer it from the size of the mapping and the alignment

[high solar]

It's more like this: right now, MemoryView is basically a function: offset -> physical address. When we add large pages, it will be a function offset -> (physical address, napot) where napot is the naturally aligned power of two region that the page is part of. So if there is a large page with physical address 0xabcdef200000 at offset zero and you ask it for offset 0x5000, it will answer (0xabcdef205000, 21)

which gives the pmap two options: map 0xabcdef205000 as 4k page, or mask out 21 bits and map 0xabcdef200000 as 2M page (assuming that's within the requested range)

The same mechanism could also neatly support software page sizes

[hexed solstice]

i'm writing the new STREAMS transport provider module for the unix domain

very fun

it's probably masochism but there seems to be something satisfying in handcoding async stuff

[sullen fern]

@hexed solstice what is the current plan for POSIX in keyronex? Will it still be a userspace server?

[hexed solstice]

some of it, but it turns out to be difficult to provide personality-agnostic high-level abstractions, which makes it a challenge

[sullen fern]

Right

And if you end up making your own APIs you kinda have to write your own programs

[hexed solstice]

and you have to reimplement about half of them in the posix personality

so i'm of this opinion now that personality-neutral is only a viable choice for primitives, of the sort that a microkernel exposes

[sullen fern]

I think what is sensible is that internally the kernel is not POSIXy, but it exposes POSIX interfaces

[hexed solstice]

newly rewritten unix domain provider for streams working well enough for xorg

horribly slow though

i really must figure out why

oh i see why

maybe

yes

the new architecture for STREAMS is that your modules create an affine thread per core, and there is a mechanism to queue messages to a stream from dpc context and waking the thread if it's not already running to process the new messages, which i use as the general mechanism for queueing messages to a foreign stream at the moment, but in one place a spinlock was taken without raising IPL (because i only intended the mechanism originally to be for sending messages from interrupt/dpc context) and the worker, which got a priority boost from an IO wait completion, was immediately woken, took over the core, and spun on that spinlock haplessly

[hexed solstice]

this evening's work is implementing stream linking (multiplexors) for the new STREAMS implementation

this is the means by which you can establish edges between a module and several streams below it (say, between IP and some NIC rx/tx streams)

this

[neat steppe]

"Frankly, I think it's a piece of crap," Torvalds writes of Mach, the microkernel on which Apple's new operating system is based, with additional elements from the FreeBSD version of Unix. "It contains all the design mistakes you can make, and manages to even make up a few of its own."

its so funny how he just wasnt that smart at the time and was probably talking out of his ass

part of why he was criticizing mach was because its a microkernel, he apparently didnt know it wasnt really a microkernel as used in OSX

[hexed solstice]

Did he name any concrete complaints?

[hexed solstice]

this evening's work:

• implement persistent stream links (STREAMS multiplexing links that can outlive the particular upper stream that was used to link them under a driver)
• start to sketch out the design of the IP multiplexing driver

the long term goal is to fully exploit multiqueue NICs with RSS

[light cape]

tbf a microkernel is harder to pull off correctly due to the differences in how they are made, and how more critical performance is to a microkernel compared to a traditonal kernel which has most core os services within the same area

but some of this was definitely pulled out of their ass

[neat steppe]

Mach just wasn't a microkernel though is my point

[light cape]

true true

[hexed solstice]

we can all be guilty at that of times, folk "wisdom" propagates and we uncritically parrot it until it's on a subject we care about deeply and the wisdom seems at odds with what we know to be true

[light cape]

i suppose that's true

[hexed solstice]

persistent stream links are in

the big idea for the networking stack:

• TCP/UDP/raw IP endpoints are instances of their respective transport provider
• those transport providers are effectively IP module's upper-multiplexors; they know about IP and register themselves with it out-of-band; the IP module creates connection objects by which to identify them by
• IP demultiplexes packets to the appropriate TCP/... stream
• ifconfig (or some daemon) opens NIC streams, designates which rx/tx queuepair they're to handle and binds accordingly, each stream is persistent-linked under the control ip stream yielding mux edge ids; ifconfig can finally send a message to the control ip stream telling it the intended configuration for that NIC with the mux ids of each queue

IP and higher-level protocol modules remain mostly distinct but the general idea is that IP driver demultiplexes early and the bulk of processing is completed on the CPU to which the higher-level endpoint stream is bound. if there is RSS, then it can not only complete there but also start there from the getgo, and the putting up from IP to the higher-level stream is probably accompanied by an immediate entry to the higher-level stream module to do its processing, since IP is done for now and that stream will be scheduled next

for polling mode: IP can conceivably turn off interrupts on that queue, requeue itself for scheduling, and then fire off a poll for any further packets

[hexed solstice]

this evening's work:

• implement generic library code for exposing a NIC driver to STREAMS
• sketch some initial extensions to DLPI (the STREAMS protocol for communicating with datalink layer) for multiqueue NICs
• virtio-net driver

[high solar]

seems that keyronex is progressing quite well 🙂

[hexed solstice]

cheers, i don't want to jinx it but i feel similarly

STREAMS seems to have become one of its core distinctives

at the cost of making a lot of my conversation here, being about STREAMS, extremely niche and of interest to maybe myself alone

possibly i am the only person in the world with any substantive interest (not just historical) in ritchie's abstraction for character devices and ipc

[sullen fern]

What's nice about STREAMS?

I'm looking into cool stuff I can implement

[hexed solstice]

it's a message-passing based mechanism for implementing layered, asynchronous character-type I/O. it's headed by a stream head which implements the entry points for read, write, ioctl etc by generating messages which can be passed down the stream (also STREAMS-specific entry points for explicitly dealing in the messages)

you start with a stream head and a driver terminating the bottom of the stream, and you can push modules in which interpose and can modify the data

so for instance you might push a line discipline module to add tty line discipline to a simple serial driver

each module has its own message queues available (one for upstream, one for downstream) and can queue data if needed. flow control propagates fullness up/down the stack so higher or lower modules know if things are backed up

[sullen fern]

Is there another use besides TTYs?

[hexed solstice]

modules usually implement at least an rput or wput routine (put a message up to be read or down to be written) and might also implement a server routine for dealing with queued messages (this helps provide the asynchronicity). the principle is that the puts avoid blocking waits and the service routines can respond to various events (TCP timers for instance)

[hexed solstice]

also PTYs (have the terminating driver join two streams as a twisted pair), network interfaces, transport providers (unix domain, tcp, udp, etc), anything that fits it as a data-driven mechanism

[neat steppe]

hey I'm interested I've just been delayed!

[sullen fern]

I'm interested I just have nothing to work on yet

[hexed solstice]

and there isn't just simple head->mod a->mod b->driver arrangements, you can produce wonderful topologies

[sullen fern]

So the advantages are mainly async and modularity/flexibility (elegance)?

[hexed solstice]

the TCP/IP stack of keyronex is to be architected like this: for e.g. TCP sockets, 'stream head->sockets personality module->tcpip driver'; the tcp driver is an upper multiplexor; it terminates into the general IP driver, which has lower multiplexed streams: e.g. NIC queuepair 0 has 'ip driver->nic driver' (there is no stream head because it's been linked under the IP driver; this is how lower multiplexors work, they make the stream terminate at its head into a driver; IP as a STREAMS multiplexor can put data up to tcp/udp endpoints, and down to NIC queuepairs)

[hexed solstice]

yes, i think that's a fair evaluation of it

[hexed solstice]

MINTIA STREAMS is coming

[sullen fern]

Very interesting, I'll certainly be looking into them

You guys have a knack for finding elegant/cool concepts from a bunch of different places and applying them to different use cases from their intended use

[hexed solstice]

https://www.nokia.com/bell-labs/about/dennis-m-ritchie/st.pdf dennis ritchie's original paper

it was reimplemented into UNIX SVRsomething (2? 3?) the main change being that it introduced the multiplexing mechanism ritchie spoke of desiring

and that is, as far as i've been able to find, the sole substantive difference between ritchie streams and sysv STREAMS

oh, one other change, they also split messages into message blocks and data blocks; data blocks are refcounted and message blocks can point at an offset into a data block. so you can receive a message in one module and send half of it's data up to the next module, and keep half of it unsent, without having to allocate a new combined-message-datablock and copy

[sullen fern]

What will your IO system look like? Are you still doing the IOkit thing? How will you mix IOPs with the IOkit hierarchy? (Unrelated)

What I had in mind involved traversing the hierarchy tree (which is functionally equivalent to the NT driver stack) to pass around IOPs but that is essentially recursive

(well, it involves deep call stacks)

[hexed solstice]

i can list maybe two more changes actually: sysv STREAMS exposes the message concept to userland with new syscalls for puting and geting a message (also that's where poll() came from), and it also adds message priority bands. but other than that, that's really all i can list for differences between the two

[hexed solstice]

i do have the tree but the stacks are distinct

otherwise i would end up needing to allocate a lot of space for frames because the device tree can get quite deep, yet in 99% of cases, say i send an IOP to a 9p filesystem on a virtio transport, it travels from 9pfs to virtio-9p-port and there it gets put onto the virtqueue and that's it. it certainly doesn't need to go 9pfs -> virtio-9p-port -> pci device -> pci bridge -> platform root or whatever the tree might look like

there is an argument for dynamic allocation of iop frames because different operations reach different depths

[sullen fern]

So there is a device hierarchy for discovery and drivers etc, and on top of that there are different driver stacks that the IOPs trickle down in?

dunno if that makes sense

[hexed solstice]

exactly that, they are distinct worlds really

[sullen fern]

I suppose those stacks are still built off of IOkit devices though? Like pointers to iokit device objects, just bypassing the hierarchy

[hexed solstice]

of vnodes

[sullen fern]

Do you build the stack dynamically though? How is it done?

I need to look more into actual IO systems before asking questions lol

[lusty gyro]

a small update: it is incorrect that I said it always uses a deferred worker to propagate boosts, however it is staged via lists

but it is correct that it avoids cross-lock ordering by never holding multiple head-entry locks in a chain, it seems to have lock layers: bucket lock which protects the per-bucket RB tree of head entries and head entry lock which protects that lock's owner/waiter sets

[twin haven]

fwiw, I'm also enjoying reading about your adventures with STREAMS.

[hexed solstice]

Im glad to hear

Whether it sets a trend or not we will see

[deft elm]

if it grows will it become RIVERS

nah more seriously i quite like reading this too

[hexed solstice]

i'm glad it's of interest to some

interesting thing, NetLink from linux actually looks easier in principle to implement as a STREAMS transport provider than the BSD routing socket

since as far as i can see netlink doesn't act synchronously in the way the BSD routing socket does. and that synchrony is at odds with the STREAMS model

it could still be done in an API-compatible way because read(), write(), sendmsg(), recvmsg() functions, which already translate socket behaviour to STREAMS, could, if the socket is PF_ROUTE, do something like is already done for ioctl() (where a message is send for the ioctl, and the responding module sends back an acknowledgement with data for write-out and status code)

but that's adding a special case which at first glance netlink doesn't. it's possible netlink has its own necessities, i don't know it particular well at all, maybe it's one of those things that does the Linux thing of consulting the current process state everywhere instead of operating with the credentials that a file was opened with - that's how file descriptors work but linux makes the confusing innovation of often depending on the process an operation is initiated from (pidfd for example does permission checks thus)

but the thrust of what i'm saying anyway is that netlink doesn't seem to leak the synchronous nature of socket operations as the routing socket did, so in that respect it is a better fit to STREAMS

where the principle is that data are encapsulated in messages that are sent down the stream and once they've been sent off, unless you implement an explicit reply mechanism, that's the end of the story

[hexed solstice]

anyway this evenings work

• just a little thinking about and sketching the lower part of the IP stack

[hexed solstice]

i evaluated the bsd routing socket vs linux NetLink

[sinful jetty]

What are your thoughts

[hexed solstice]

i have decided that NetLink® is an improvement on the routing socket. it has its own ugliness but it's extensible, it has superior characteristics in terms of memory use because you can generate, for instance, a series of messages detailing state in response to, for example, a query of somet table that has a lot of entries and these do not have to be a single message, so they can be consumed by the app as they are generated, and fundamentally it is better suited to implementation in a STREAMS based system

[sinful jetty]

Cant wait to get to streams

Do u know which approach Linux uses instead of streams?

[hexed solstice]

essentially similar to the way BSD implemented sockets historically

there are three implementations of STREAMS for linux but none were merged

[sinful jetty]

Some naive/bad way?

[sinful jetty]

Do u know why?

[hexed solstice]

i would not say bad, fairer to say it is an approach that grew out of implementing TCP/IP and it can do a very fine job at that, but it's less flexible/dynamic and requires, for instance, if you want to do async io, to give that an explicit treatment, and this may require you to have each protocol handle it with code of its own. while i get it for free - but only because i have to write async code already as that's how STREAMS works

[hexed solstice]

the first one was LiS which was supposed to be portable to many kernels, does not follow Linux code style, etc, so bringing it in tree was not a reasonable prospect. the second one is OpenSS7's STREAMS module, but that's part of a wider project that implements the SS7 telephony protocols. and the third one is seemingly only used by IBM to support their "Systems Network Architecture" and is clearly developed inhouse at IBM

[sinful jetty]

Interesting stuff

I guess you could say no real effort has been made for that

[hexed solstice]

there was also the big problem in the 90s that STREAMS could refer to three things: an architecture for implementing character devices/network protocols, a particular implementation of that architecture, or (this is the problematic one) an alternative userland API that could be used instead of the userland sockets API. but that alternative API was not especially popular

possibly even more problematically, that alternative userland API was associated with the OSI protocols, which were proposed to replace TCP/IP as the protocols used for the internet. but they never did, and nowadays the only thing anyone remembers about the OSI protocols is the model they created to describe protocol layers

[sinful jetty]

Ah

[hexed solstice]

minimalistic netlink (NETLINK_ROUTE with its commands; i've only done RTM_NEWROUTE yet) turns out to be straightforward enough to implement, it's just the parsing/construction of messages is maximally tedious

[high solar]

I always wondered why they added a socket abstraction to configure routes (which is in principle not unreasonable) but then at the same time decided to configure everything else via ad hoc ioctls and /sys

[neat steppe]

@hexed solstice how are we implementing the parallelizable page table scanning version of working set management without compromising the pmap abstraction

it kind of just doesnt work without multi level page tables

[neat steppe]

ok on the grounds of that alone im deciding not to do pmap and on an architecture like ppc ill just simulate multi-level page tables so that i can keep doing the page table scanning

[neat steppe]

i had a brief episode where i found that to be ugly but i think thats a fairly suitable abstraction actually

just writing all the arch independent code around the existence of multi level page tables and simulating them on architectures that lack them

theyre nearly universal today anyway

if not entirely universal now that the latest POWER chips have it

[final hatch]

I don't blame you for wanting to simulate normal page tables

I still don't understand how PPC's inverted page tables work and I have looked it up several times already

[neat steppe]

its a hash table

"inverted page table" is a really weird name for it

literally its just a hash table (with some swizzling of the hash key per-process so that executables being at the same place in multiple address spaces dont aggressively collide in the hash table and stuff)

[hexed solstice]

I considered this before and concluded that the aging logic had to go into pmap

[neat steppe]

are you open to a counterargument

[final hatch]

hash table that hashes what in its lookup

i guess virtual address and process ID?

[neat steppe]

sort of

its something like that

[final hatch]

i suppose that was the source of part of the confusion 😄

[neat steppe]

i forget the hash function off the top of my head

[hexed solstice]

if you have one i should be eager to hear it

[neat steppe]

basically the aging logic as we've come to understand it is an awfully complicated and specialized piece of logic to relegate to a pmap module and then you need to come up with some alternative for architectures that dont use multi level page tables

you can share it among all the multi level pt pmaps but something about it is still ugly

its also weird that its like

on x86 and aarch64 and riscv and whatever you get this cool parallelized page table scan thing

and then on ppc you get like

a bespoke implementation of an old style working set list?

or what

making both of these things fit into pmap makes the interface to pmap really convoluted too

feels like a mis-abstraction to me at that point

[hexed solstice]

that's what i would've had in mind, or rather a generic version of it. in any case it's the only way i can see to have a true pmap abstraction while having the parallelisable working set scanning technique is that the scanning needs must be in pmap, otherwise you no longer have an abstract pmap

i agree that it is not a very pretty picture you get at the end of it

[neat steppe]

avoiding that is the main reason ive decided not to do pmap after all

[hexed solstice]

my latest test for keyronex: pound it with ping until something goes wrong

on amd64 it worked until pages were exhausted for some reason (i must be forgetting to deallocate something, it's not a big deal)

on m68k IPL is stuck at disp level for whatever reason

it gets stuck there at some point presumably due to some deficiency in how i map keyronex soft IPL to m68k hard IPL or something like that, and seems to happen only under heavy interrupt load

oh, how boring, i think it is just a codepath i forgot to lower IPL on

i'll let it run for a while but it looks like that's the case

now m68k also runs to the point of the memory leak leaking too much, so i think i can conclude i was right

[high solar]

Why is the aging logic that complicated?

[hexed solstice]

if you return to the old technique of aging by iterating over PTEs in page tables, you can parallelise the aging operation

the exact picture of this might be something like linking page tables's page structs to list heads per, say, average age of PTEs in that table

then you can have aging for different average age bands proceed in parallel, and what's more, you have the considerable advantage of doing sequential access to, if you're lucky, 512 PTEs at a time

the cache dynamics then are much better than if you were always jumping around between PTEs located far from each other

[high solar]

if iterating over PTEs is the old technique, what is the new one?

[hexed solstice]

having some data structure which you consult to find PTEs you want to age individually

here it is worth talking a little about how it is that we are interested in aging anyway

VMS had what was called segmented FIFO where the first level of page replacement is FIFO with an array that was treated a bit like a ring buffer

there was no aging at the first level there, just replacement of entries in that ring buffer. if you try to insert a new page and it is full then you simply evict the page at the current insertion index

(as a matter of fact the vax didn't have an accessed bit)

but newer architectures do, and since page faults are relatively expensive, even ones that don't require an IO from disk, it's desirable to make the first level of page replacement more intelligent

but if you keep the data structure from VMS (called a working set list) you have the problems i mentioned above of poor cache dynamics, it's difficult to parallelise the aging even though in principle it should be a very parallelisable operation, and in general maintaining that data structure is a bit annoying, since you need to resize it from time to time

but consider why that data structure was created

you need something like that if you want to do FIFO replacement

but if you want to do something based on looking for aged PTEs instead? then you don't need it, the PTEs themselves are adequate

[high solar]

Ah I see. I guess this make sense from a historical perspective but an actual FIFO seems like a very wasteful data structure to store the age

since you probably need/want way fewer bits to store the age of a PTE than you have virtual address bits

[hexed solstice]

network stack is now almost up to par with before, i haphazardly adapted the old TCP code to new STREAMS. i can wget something without much bother but there is no timers, no support for 'detached from stream' tcp connections (the state a connection yet to be accept()'d, or still there after close() before data is yet unacknowledged, is in), and no passive listeners yet. some adaptation work needed for these all

[neat steppe]

Not sure how clear this was made: the FIFO structure (which was an array called the "working set list") stored a list of all the valid virtual pages within the process and they would iterate over that for aging rather than scan the page tables, for efficiency reasons. This dated back to VMS

It didn't just store the ages

[hexed solstice]

and didn't store the ages at all at one time

when there were no ages and first-level page replacement was really FIFO it was an excellent datastructure for that

[high solar]

yeah i do realize that it worked like this but this means that you essentially double the pt space instead of only storing a few bits for the age

Since the fifo entries need to be word sized

[neat steppe]

It's not as bad as doubling the PT space since you don't always have full PTs but yeah it was less space efficient ultimately

[hexed solstice]

there is another consideration too

sometimes you want to get rid of entries in that working set list given a virtual address

so either you can iterate the whole list which may be 2 million entries long or more, or you need a means by which to speed the lookup

solutions could include an out-of-line hash table (you will want it to be big enough so let's just say the size of the working set list again) or you could do an inline tree

4 billion entries in the working set list extends to 16 tib which should be enough for anyone so you in place of pointers you could use 32-bit indices into the working set list, so this way also doubles the size of the thing

[neat steppe]

An evil idea is to simulate sane people multi level page tables on top of the wacky 68k page tables that have the smaller leaf level

It could up to 2x the space taken by page tables but like

[flint anvil]

just don't use radix trees?

[neat steppe]

I want virtually linear page tables and parallelized PTE aging

[sullen fern]

How do you parallelize it? Do you spawn multiple threads arbitrarily or what

[neat steppe]

Per-node pool of worker threads dedicated to this task

Which select a process and yoink page table pages off a work list and scan the PTEs

They each work on a different page table page in parallel

[sullen fern]

How do you do thread pools in mintia? Do you have a global dynamic worker thread pool that pulls work from a work queue?

[neat steppe]

I have some global ones (well they r really per node) for random tasks but for this they'd probably be dedicated and bespoke

[sullen fern]

ah I see

[hexed solstice]

tcp passive open seems to work with new STREAMS

[steep marlin]

nice

[sinful jetty]

is the code available

[hexed solstice]

keyronex running in VM with Xorg listening on TCP

mate-panel running on linux with DISPLAY=$keyronexip:0

(i thought MATE completely got rid of the unsightly GNOME logo?)

[hexed solstice]

(this is extremely unstable and lasts a few seconds before falling apart; also very slow; i am working on figuring that out)

[woeful spear]

Glad to see progress on keyronex

[hexed solstice]

cheers, so am i

[hexed solstice]

and i think at that i may call it a night

[sinful jetty]

Is it ticking

[hexed solstice]

(why did it not get there before? because xorg sent a lot of data at once and the message block-to-scatter/gather-list function got confused by a message block whose data block spanned two pages)

[hexed solstice]

it's been keeping time since the screenshot was taken

[sinful jetty]

[slim blade]

gnome

[hexed solstice]

this has certainly been a considerable TCP stress test

[hexed solstice]

they dropped X support

[slim blade]

old gnome ig

its gnome 2 i think

[hexed solstice]

i'm not sure if gnome would even work over x11 remote but it's possible

[hexed solstice]

that's mate

[slim blade]

oh

[sullen fern]

mate is a gnome 2 fork

[worn elbow]

Iconic reference

[gilded plank]

is this with mlibc

[stone orbit]

it's xorg running on keyronex and applications connecting to it from the host

you can see the cwd in the terminal is [...]/Projects/Keyronex

[gilded plank]

a

i thought he ported mate

[hexed solstice]

all in good time

[gilded plank]

did you tried to run gtk ?

[hexed solstice]

not yet, i've been working on tcp/ip lately

[wet apex]

Very good work, btw

[hexed solstice]

so X11 remoting was just a (very satisfying) way of testing that