davix operating system kernel

[thick lagoon]

well

I never claimed to aim for soft-realtime

(although yeah nearly full interruptibility of the kernel would be nice)

but bounded regions with interrupts disabled is enough for me to be happy, really

I should get a new computer keyboard

my current one is really dirty and also quite old

[vital siren]

the flow for like a disk io completion interrupt for me was gonna be something like

1. ISR gets the disk interrupt to shut up and starts next sub-transfer if any. if none, enqueues the DPC
2. DPC dispatches the IO request to the worker thread pool for completion
3. worker thread does IO completion by unwiring page frames, and waking up the requesting thread if synchronous IO. if async, enqueues a kernel APC
4. kernel APC runs in context of the requesting thread and writes out the IO status block to its process's userspace. can't do this from worker thread because the mapped memory could be some crazy file over multiple layers of disk images and/or the network or something and could easily be engineered by a malicious user program to cause extremely lengthy page faults taken in the context of a critical worker thread, which has DOS attack potential. after doing that it signals completion by re-enqueuing itself as a usermode APC
5. usermode APC executes the user-provided callback in userspace in the context of the requesting thread (kind of like a signal)

[round cradle]

these extremely lengthy page faults could cause a stack overflow which you should watch out for

[vital siren]

no they cant

[round cradle]

no?

[vital siren]

nop

[round cradle]

well what if someone mounts a vhd from a vhd from ... from a vhd from a vhd from a vhd from the network

[vital siren]

wouldnt cause stack overflow

[round cradle]

why not

oh right

cause you have your async IO scheme

which pretty much prevents that from happening

[vital siren]

because my driver layering is carefully designed to avoid that exact problem

yeah

[round cradle]

i see

[thick lagoon]

someone pin this message

[round cradle]

i honestly cant wait for the end of my exams in a couple days

then i can finally start working on boron again

[fathom lake]

discord should let thread OPs pin messages tbh

[thick lagoon]

yes

[round cradle]

i agree

[thick lagoon]

but discord...

[vital siren]

also worker thread context is needed for at least part of io completion because the vmm locks are all blocking locks and so just unwiring page frames requires blocking locks to be taken, which requires a thread to take them with

this wasnt true in NT because the relevant vmm locks are spinlocks and so they can do it directly from a DPC. i set myself a goal to use only blocking locks wherever humanly possible and make as much of the kernel preemptible as i could but its up to you whether that makes any sense to you

[fathom lake]

actually, came up witha solution: make a "pin board" message with message links to the pinned stuff, and then link to that message from the original post description which is easily accessed

[thick lagoon]

yeah

but that is annoying to maintain

[fathom lake]

yeah

[thick lagoon]

so I did something where I increased the number of particles in the fireworks test substantially

it stutters a lot when running it on a single vCPU

but with -smp 32 it is very smooth

that means my very primitive form of load balancing (which is only ever done when waking a task) works.

[vital siren]

By how much

[thick lagoon]

uhhhh

I didn't measure :p

but I increased it so each explodeable generates between 500 and 999 points

and between 1 and 5 explodeables are generated with intervals between 2 and 4 seconds long

so probably like 2800 something

which is not very much

but considering this is my sleep:

static void
poor_mans_sleep (nsecs_t ns)
{
    nsecs_t target = ns_since_boot () + ns;
    do {
        schedule ();
    } while (ns_since_boot () < target);
}

[round cradle]

thats like

bad

try implementing a blocking sleep

[thick lagoon]

yeah, I know that :-)

this was a quick-and-dirty way to get your beautiful fireworks test running

[round cradle]

honestly a thing im really proud of in boron (but which isnt really my design per-se) is the timer system

except for the timer queue data structure (i just use an rbtree instead of a calendar queue or whatever)

[thick lagoon]

which, now that I actually also free memory when I'm done using it, it doesn't stop because of OOM now.

[round cradle]

its really versatile, it allows DPCs to be fired when the timer expires, and it gets automatically signaled when the timer expires too

it also integrates with the scheduler's one shot timer system (boron doesnt use periodic ticks but instead reschedules a one shot interrupt for every timer interrupt)

i didnt measure any of this but i think the latency is minimal in my scheme

[thick lagoon]

so in my kernel, I have something which is called the KTimer

now,

the KTimer is per-CPU

but tasks can be woken up on any CPU

this is something I will have to solve with some sort of timer list which is enqueued to only from one CPU, but timers can be removed from by any CPU

[thick lagoon]

yeah your scheme sounds very reasonable

[round cradle]

in my scheme a timer can just be dequeued by any CPU because KiWaitTest can check any CPU thread for wake up

now the only thing preventing latency from being truly minimal here is the big dispatcher lock 😮‍💨

[thick lagoon]

you don't do DPCs per-CPU?

[round cradle]

Yes, I do DPCs per CPU

But you're right, as it stands, you can't specify which CPU the DPC is enqueued on. But that hasn't mattered so far

Wait I just realized

If they're all looking at the same queue

Then their interrupts are mostly in sync

[thick lagoon]

my DPC interface is probably similar to yours

I have a bool DPC::enqueue()

and there's no way to remove a DPC from the queue, other than it being dispatched

and there's no direct way to enqueue a DPC on a remote processor

[thick lagoon]

implementing a timer-based sleep, got general-protection fault

ah yeah, it might be because currently I don't broadcast TLB flushes

so cursed stuff may be happening

[thick lagoon]

at least sched_timeout seems to be working

(will fix TLB flushing then test with --smp 32 before committing)

[thick lagoon]

now I get deadlocks instead... fun.

(with this TLB flushing code)

[thick lagoon]

the best deadlock detection

wait, why the damn are interrupts disabled on CPU0?

alright so CPU0 has an affection for calling smp_call_on_cpu with IRQs disabled

and so do all other CPUs... (I didn't run with --smp)

you motherf...

reap_task frees the stack, which causes kfree_large, which causes a TLB flush, which calls smp_call_on_cpu in an IRQ-critical section

[thick lagoon]

now I've fixed all issues that I am aware of

• fixed finish_context_switch so it enqueues a DPC for reaping tasks.
• fixed tlb_end_kernel so it actually flushes the TLB on remote processors in SMP.
• implemented sched_timeout, which is now used for delays in the fireworks test.

overall this has been a pretty productive day for Davix, considering that I worked earlier today.

I want locking primitives (mutex and rwmutex), after that I will start working on RCU.

@round cradle https://github.com/dbstream/davix/blob/25f83675b2ce5bd087a1ee7dbc05d71e55367b74/kernel/sched/timeout.cc here is my thread sleep timer code if you want to review it

[thick lagoon]

It's incredibly satisfying to just watch the fireworks test slowly but surely devour the framebuffer.

[torn nova]

thats pretty fast actually i think

[lucid abyss]

you asked what it looked like before, so here it is:

the recording software isn't capturing colours properly

idk why

smoother irl, frame rate gets weird when uploaded to discord

[thick lagoon]

oh, nice.

[thick lagoon]

yeah

the same thing happened to me

[torn nova]

nice

[thick lagoon]

running the fireworks test with wayyy too little memory:

note how many of the explodables spawn way fewer particles than the others. this is because they run OOM.

also note how the kernel doesn't die.

[thick lagoon]

I know already that I will typo a million things because of this

[thick lagoon]

bruh

(that's in the scheduler)

what

lists are broken??

fault address is 0xcafebabe, this means someone is reading the prev field of a ListHead which has been removed

[thick lagoon]

alright I have done some x/<n>g <rsp> in QEMU, and it appears that the call stack looks something a bit like this when the fault occurs:

ktest/mutex.cc            L25    mutex.lock();
kernel/mutex.cc           L93    lock_slowpath(...);
kernel/mutex.cc           L276   sched_timeout_ticket(...);
kernel/sched/timeout.cc   L123   schedule();
kernel/sched/main.cc      L468   pick_next_task(...);
kernel/sched/main.cc      L422   .pop_front();

I'm suspecting there is something wrong with the scheduler and not the mutex.

Something like this might happen if the same task is added to a runqueue twice (BUG!).

oh my god I am a debugging genius

added this code, now I know what is wrong

time to do a manual x/<n>g <rsp> stack trace again (pain)

[round cradle]

consider adding a stack walker and symbol resolver

[thick lagoon]

yeah, later I will do that

[meager sequoia]

why not just use the gdb backtrace command

[thick lagoon]

noreturn/infinite loop optimizes stuff out and kills gdb

[meager sequoia]

huh

weird that it kills gdb like that, it should still be able to backtrace with cfi

[round cradle]

Then don't optimize

[thick lagoon]

yeah, this is not even across an interrupt frame or anything like that

[round cradle]

Use -fno-omit-frame-pointer and stuff

[meager sequoia]

do you by any chance discard eh_frame in your linker script without passing -fno-asynchronous-unwind-tables

passing that flag will put cfi into .debug_frame instead of .eh_frame

[thick lagoon]

eh, I will debug this tomorrow instead

[pastel rivet]

noreturn functions break the top of stack since they don't introduce a new frame (?)

we've also run into this with mlibc since sys_libc_panic is noreturn

i think it's a combination of a tail call into a noreturn function + not establishing a new frame since it'll not return

[thick lagoon]

I think I know what this is actually

so previously, there was a deadlock situation where a task failed to wake up.

this occured when a mutex waiter was woken up, failed to acquire the lock, and went back to sleep.

now, the reason for this is because of sched_ticket_t

pretty much, I forgot to update the sched_ticket_t of the MutexWaiter before going back to sleep

now I suspect that the issue has something to do with updating MutexWaiter::ticket at the wrong time

[thick lagoon]

debugging mastermind

anyway now blocking mutexes work (I even get some nice celebratory fireworks!)

[torn nova]

nice

[thick lagoon]

maybe it's time for RCU now...

[torn nova]

btw what are your allocator zones

[thick lagoon]

ZONE_LOW1M (2) - low 1 megabyte, currently only used to allocate the smpboot trampoline page

ZONE_LOW4G (1) - 32 bits

ZONE_DEFAULT (0) - everything else

[torn nova]

interesting

[thick lagoon]

these are defined in a header file provided by the architecture, in this case arch/x86/include/asm/zone.h.

[torn nova]

i like how u called it asm lol

it was called that in linux because u could include stuff from assembly

i just call it arch/

[thick lagoon]

yeah

[torn nova]

can u include your headers from asm?

[thick lagoon]

also this is mostly not true anymore AFAIK, a lot of the stuff Linux puts under asm/ contains a lot of C

[thick lagoon]

no

well

some of them

[torn nova]

yeah ofc

[thick lagoon]

does anyone know of some stress-test I can run on my RCU implementation to verify its correctness and to measure its performance?

[pastel rivet]

no LOW16M zone for isa dma?

[thick lagoon]

no

ISA does not exist

(at least I pretend it doesn't)

[pastel rivet]

how will you have the floppy disk controller dma to ram then

or the soundblaster 16

[thick lagoon]

floppy? what's a floppy?

my solution to that problem

[torn nova]

most important hw to support in a new os

[pastel rivet]

of course

[torn nova]

i like the under 1M zone idea tbh

[thick lagoon]

it literally has one usecase

[torn nova]

true

[weary prairie]

u still kinda need it

or you can reserve a part of <1M memory before passing it off ot the allocator

and drop the idea of a 1M zone

[torn nova]

i might just reserve some low pages using the boot allocator tbh

[weary prairie]

yeah exactly what i'd do

[thick lagoon]

oh my god RCU is easy

[thick lagoon]

wtf... this is a more-than-a-toy implementation of RCU in like 170 lines of code

[thick lagoon]

however I do need to write a testcase for my RCU implementation in order to make sure that it is correct

[lucid abyss]

I don't understand how rcu works

[torn nova]

https://www.kernel.org/doc/html/next/RCU/whatisRCU.html

read this you will understand literally everything

especially the toy example section

[thick lagoon]

this is the basic idea with generational RCU:

• there is a global "current generation".
• RCU callbacks are enqueued on callback list current_generation + 1 (the next generation).
• every CPU keeps its own "local generation", and whenever the CPU is at a known 'quiet point' (rcu_quiesce is called), it updates its own local generation to the clobal current generation.
• upon doing this, if a CPU sees that all CPUs which are participating in RCU are at the global current generation, it dispatches all RCU callbacks on the callback list for the current generation and then increments the global current generation.

my invention "Segment Tree RCU", which is possibly similar to other generational RCU implementations -- although I do not know that, because I have not looked at the tree RCU patents -- is basically a way to reduce the amount of work that each CPU has to do as part of this last step, to average-case O(1) and worst-case O(log N) rcu_quiesce.

I'm going to try to optimize the invocation of RCU callbacks a tiny bit -- it's probably not a good idea to invoke them right in the middle of the scheduler, where DPCs and IRQs might be disabled.

I will also have to figure something out for the idle task

[thick lagoon]

speaking of which, is monitor/mwait guaranteed on all 64-bit x86 CPUs?

no it is not. 😭

and it is also something which can be disabled by the BIOS. 😭

[worn wolf]

i would assume disabling it in the bios will also clear the cpuid flag bit to detect it

[thick lagoon]

yup

[worn wolf]

on the bright side both instructions are 3 bytes long which is just enough space to squeeze in a short jump so you can patch the kernel at startup to either jump to a normal lock or use the instruction instead

[thick lagoon]

if sti; hlt is executed, can the CPU leave the HLT state because of an interrupt?

[worn wolf]

yes

[thick lagoon]

phew

then it is not so difficult to do what I need to do, actually

[worn wolf]

thats how i pause in my scheduler when theres nothing to do

if you're feeling fancy theres some intel and amd extensions to put the processor into lower sleep states as well

[thick lagoon]

this is what I'll have to do for idle

so basically: rcu_disable can end the current RCU generation, which (if there are any callbacks) adds a DPC into the DPC queue of the current CPU

therefore we need to test has_pending_dpc immediately after disabling RCU

we also explicitly disable raw IRQs, and after doing so, we have to test if there is a lazy deferred IRQ. if there is, we dispatch it.

we can finally perform the sti; hlt (raw_irq_enable_wfi) pair, and afterwards we enable RCU and dispatch whatever it is we got

so the thing that rcu_disable and rcu_enable provide is that we can now step forward generations without idling CPUs needing to call rcu_quiesce

(or CPUs running userspace code, for that matter)

[thick lagoon]

honestly I'm surprised by how easy this was

Well I say that, but I'm surely going to discover a hundred bugs in my implementation whenever I actually begin using RCU for stuff.

Here it is, Segment Tree RCU: https://github.com/dbstream/davix/blob/94d83f6a7679d94f4487ee48eb017073e3027b4a/kernel/rcu.cc

[lucid abyss]

spiders

[digital hawk]

Nice one, I'm keen to have a read of this later.

[thick lagoon]

filesystem gaming:

struct INodeOps {
    int (*i_lookup) (INode *dir, DEntry *entry);
    int (*i_close) (INode *inode);
    int (*i_unlink) (INode *dir, DEntry *entry);
    int (*i_mknod) (INode *dir, DEntry *entry, mode_t mode, dev_t device);
    int (*i_mkdir) (INode *dir, DEntry *entry, mode_t mode);
    int (*i_symlink) (INode *dir, DEntry *entry, mode_t mode, const char *path);
    int (*i_link) (INode *dir, DEntry *entry, INode *inode);
    int (*i_rename) (INode *fromdir, DEntry *from, INode *todir, DEntry *to, unsigned int flags);
    int (*i_chmod) (INode *inode, mode_t mode);
    int (*i_chown) (INode *inode, uid_t uid, gid_t gid);

    /* TODO: i_stat, i_readlink, i_open  */
};

I would include comments explaining what these functions do, and preconditions to them, but discord complains that the message size is too big.

[thick lagoon]

One of the trickiest bits of VFS design is ownership, especially when unmount comes into play.

[thick lagoon]

"singly-linked list" struct SListHead { SListHead *next, **link; }; (edit: I wrote "SList" first but "SListHead" is correct incorrect in the correct way)

was I drunk?

[weary prairie]

yes

you got half of it right though

oh wait.

i mean yeah, i guess you can just remove the link member, change the struct name to SListEntry and you actually did get half of it right :^)

[thick lagoon]

I guess I could've went with it and referred to this as 'slim list', because struct SList { SListHead *first; }; is a single pointer.

but I've renamed it to HList, HListHead, TypedHList (helper type)

[thick lagoon]

struct RefStr {
        refcount_t refcount;
        char string[];
};

This is a handy helper type that I will use when passing null-terminated strings (e.g. filenames) from userspace into the kernel. It will also find use in the VFS←→fs interface for symlinks.

int (*i_readlink)(INode *inode, RefStr **str);

[weary prairie]

why refcount a string

[thick lagoon]

It has some nice properties

namely that now I can store a refcounted string in the symlink inode and now I suddenly don't have to allocate on readlink or on lookup (well... lookup does allocate under some circumstances, but not because of symlinks )

[weary prairie]

you could just do int (*i_readlink)(INode *inode, char *buffer, size_t buf_len);

and read the link into a preallocated buffer

[thick lagoon]

IMO that is a less nice interface. It puts the burden of answering "ok... what type of allocation should I use for this buffer?" on the user of the interface (which is a good thing in some situations, but IMO not in this one.)

and the symlink contents will be cached within a RefStr kept by the filesystem anyways

[thick lagoon]

slowly but surely figuring out VFS objects ownership model...

so here's an overview of what I have in mind for now:

• DEntry, Mount, INode, Filesystem are all reference counted.
• The DEntry holds a reference to the INode and its parent DEntry.
• The INode holds a reference to the Filesystem.
• The Mount holds a reference to its parent Mount, parent DEntry, and inner root DEntry.
• DEntries can exist in a hashtable of (parent DEntry, name) → child DEntry. This hashtable does not hold a reference to the DEntry. Instead, lookup and dget is supported with RCU shenanigans. A DEntry with a reference count of zero is not necessarily immediately removed from the hashtable (instead it is LRU'd).
• INodes also exist in a hashtable of (Filesystem, ino) → INode. This hashtable also does not hold a reference to the INode, again, RCU shenanigans come into play. The reason this hashtable needs to exist has to do with inode lookup on hardlinks.
• Child mounts are kept in a hashtable of (parent Mount, parent DEntry) → Mount. Living in this hashtable does imply an extra reference to the Mount. Eventually, I will have to figure out an approach for handling unmount, particularily the case of recursively unmounting an entire directory tree will be difficult. But umount is unneeded for now anyways.

[thick lagoon]

so I'm actually a bit curious

[thick lagoon]

@high cloak since you have actually gotten around to the implementing part, what are your thoughts on this?

[high cloak]

this sounds very VERY close to how i implemented my stuff (bar the RCU, where i just spin for now)

[thick lagoon]

also going to ping @vital siren because you usually make interesting points on this type of thing

[vital siren]

sounds fine other than the inode shouldnt hold a reference to the filesystem

instead you should purge all the inodes when you unmount the filesystem

also your inode lookup is going to cause you suffering

it turns out this is something that should not be abstracted (imo) because it causes major difficulties across various filesystem types

each fs driver should implement its own inode caching

[thick lagoon]

good point. only problem is that now anyone who holds a reference to an inode also needs to hold a reference to the filesystem.

[vital siren]

with its own locking scheme

and present an interface to the vfs that takes a parent inode and a child name and returns a child inode w/ a biased refcount

vfs doesnt know how it looked it up

[thick lagoon]

yeah this is similar to what I was planning.
int (*i_lookup) (INode *dir, DEntry *entry);

[vital siren]

so that (for example) your ext2 driver can use a hash table keyed by inode number, which is natural, and your FAT driver (where that would be VERY unnatural) can keep a tree of inodes keyed by their names

or whatever else

also itd probably be a good idea to immediately delete an inode when the refcount drops to zero

and hold a reference on it from the dirent cache entry

so that your dirent caching == your inode caching

and you only need to implement the mechanisms for the former

[thick lagoon]

yeah exactly

[vital siren]

the fs is called back to remove it from its structures and stuff

[thick lagoon]

wait did I not write that the dentry holds a reference to the inode?

[vital siren]

u didnt write what your inode caching would be like so i thought id point that out

[vital siren]

also theres a race condition here where another dirent was created for the inode, so the fs driver needs to be able to return from this deletion callback, "hey i took all my locks for my inode lookup stuff and found that it has a refcount > 1, so youre not the only owner anymore. u should abort deleting the inode"

[thick lagoon]

no there's not. the inode can be 'detached' and have nlink=0 but refcount>0 (essentially a still open inode which exists on disk but has no name).

[vital siren]

that doesnt have anything to do with what i just said though

[thick lagoon]

ahhh

I thought you meant for unlink()

[vital siren]

if you delete a dirent cache entry (while trimming the cache) and unreference the inode and the refcount on the inode drops to zero, it could go back up because somebody else looked it up

[thick lagoon]

yeah that makes sense

[pastel rivet]

just merge inodes and dentries and only support fat

easy

[vital siren]

in old mintia i did almost all management of vnodes under the fs-specific locks

and made the fs drivers implement it

because there were lots of races

[thick lagoon]

more RCU shenanigans incoming :^)

[vital siren]

that were difficult to resolve otherwise

especially wrt purging the modified pages in its page cache

but you could probably set it up so whenever # of dirty pages > 0, theres a biased refcount on the inode

so that when the lazy writer gets around to writing them out, itll decrement the refcount (because # of dirty pages is now 0) and at that point its deleted

[thick lagoon]

yeah that's probably what I am going to do

[vital siren]

i think i tried this and for some reasons highly specific to my vmm design it didnt work well

i dont remember what they were though

[thick lagoon]

a biased refcount on the DEntry is how I am planning to implement tmpfs (no i_lookup? no problem. everything is in cache.), but I haven't figured out yet how to deal with unmount.

[thick lagoon]

why is it a problem for the INode to hold a reference to the Filesystem (Linux superblock equiv.)?

[thick lagoon]

New synchronization primitive just dropped.

Used like this:

(whenever someone clears Foo::x, they should invoke condwait_touch(foo);).

(and the load on foo->x in the condition should really be atomic, as should any store to it also be.)

[thick lagoon]

the idea is that something like ensure_dentry_inode can look like this:

int ensure_dentry_inode(DEntry *dentry)
{
retry:
        if (!(atomic_load_acquire(&dentry->flags) & D_UNCACHED)
                return 0;

        d_lock(dentry);
        if (!(dentry->flags & D_UNCACHED)) {
                d_unlock(dentry);
                return 0;
        }

        if (dentry->flags & D_LOOKUP_IN_PROGRESS) {
                d_unlock(dentry);
                int errno = condwait(dentry, dentry,
                        !(atomic_load_acquire(&dentry->flags) & D_UNCACHED)
                );
                if (errno)
                        return errno;
                goto retry;
        }

        INode *dir = d_parent_inode(dentry);

        atomic_set_bits_relaxed(&dentry->flags, D_LOOKUP_IN_PROGRESS);

        d_unlock(dentry);
        i_lock_shared(dir);
        int errno = dir->ops->i_lookup(dir, dentry);
        i_unlock_shared(dir);

        if (errno == ENOENT)
                errno = 0;

        if (!errno)
                atomic_clear_bits_release(&dentry->flags,
                        D_LOOKUP_IN_PROGRESS | D_UNCACHED);
        else
                atomic_clear_bits_release(&dentry->flags, D_LOOKUP_IN_PROGRESS);
        condwait_touch(dentry);

        return errno;
}

[thick lagoon]

Waiter lists are outlined from the objects themselves into a single static array. This means that an object can be made condwaitable at zero cost in object size (and, in fact, any kernel object can be condwaited on.

The only immediately-obvious caveats are:

1. an object must be retained for the duration of the condwait (although this is inherent to waiting on any object).
2. the code that checks the condition must be careful not to take any lock which may be held by someone who is themselves performing a condwait. it may also not block.

number 2 is because the condition is checked under a spinlock, under which it is prohibited to sleep.

I can probably write a toy mutex implementation using this:

struct slim_mutex {
        int lockval = 0;
};

void slim_mutex_lock(slim_mutex *mtx)
{
        for (;;) {
                do {
                        int expected = 0;
                        bool ret = atomic_cmpxchg_weak(&mtx->lockval,
                                &expected, 1, mo_acquire, mo_relaxed);
                        if (ret)
                                return;
                } while(!expected);
                condwait(mtx, mtx, !atomic_load_acquire(&mtx->lockval));
        }
}

void slim_mutex_unlock(slim_mutex *mtx)
{
        atomic_store_release(&mtx->lockval, 0);
        condwait_touch(mtx);
}

blocking mutex in 23 properly-formatted lines of code, counting whitespace.

[thick lagoon]

#define atomic_clr_bits(p, bits, mo) do {                \
        atomic_fetch_and((p), ~(decltype(0+*(p)))(bits), (mo));    \
    } while (0)

The 0+ in the decltype(0+*(p)) is needed to force the inner expression to be of an rvalue type, such that the cast to the decltype is valid.

[thick lagoon]

dput is difficult to get right (atleast without a Big VFS Lock, which I'm not going to accept)

at least I have RCU which gives me one tool to make it a bit easier for myself

D_FREED: set on a dentry when it has been freed. absolutely legendary RCU stuff

[thick lagoon]

Should I be ambitious and implement a percpu LRU of dentries?

For some reason I don't think it will be much harder than a single global LRU would be.

Like the only thing that would require more work is cache trimming would have to dispatch a DPC on the other CPUs.

screw it we ball

I'm doing it, percpu LRU list

[vital siren]

theres an alternate thing you can do

if you have some way to pin a thread to a cpu then you can just pin the cache trimming thread to each cpu in sequence

could be preferable to a DPC if you want/need to take blocking mutexes in order to do the cache trimming

[thick lagoon]

yeah probably

or just migrate the thread that is invoking the cache trimming

there are two cases for dentry cache trimming that I can think of right now:

1. someone wants to allocate a dentry and there are lots of dentries on the LRU. in this case, try to trim a single dentry from the cache.
2. there is memory pressure and lots of dentries are being trimmed.

The problem with LRUing too much is that it might contribute a lot to internal fragmentation.

eh, problem for future me :-)

right now it is not at all a problem since tmpfs dentries will have a flag D_DONT_KEEP set on them that tells the VFS to free them immediately instead of LRUing them

[thick lagoon]

The only sleeping operation I will need to perform when trimming the cache is rcu_synchronize.

[thick lagoon]

nevermind, this will become difficult because it becomes annoying to remove the DEntry from the LRU

The reason a percpu LRU list becomes annoying is because now I would have to keep track of which LRU list the DEntry is on.

[thick lagoon]

200 lines of code dedicated to freeing DEntries (and I haven't even written the cache-trimming part yet!).

discord formatting ruins everything

[thick lagoon]

Work-in-progress DEntry LRU trimming:

[thick lagoon]

VFS work is now in https://github.com/dbstream/davix/tree/vfs.

[thick lagoon]

Also fireworks has been running for like 20min now, it seems to be working.

[thick lagoon]

Initial work on the tmpfs has been done and pushed to the VFS branch in the git.

[thick lagoon]

Spot the mistake.

[thick lagoon]

Alright, so d_free_rcu is supposed to put the DEntry on the RCU callback queue if it has not been put there already, and it should unconditionally unlock the DEntry. If D_FREED is set, indicating that we raced against someone else who has already "freed" the DEntry, the above code doesn't unlock the DEntry, causing two problems:

• If two or more threads race d_free_rcu, one of them will leave the entire dput code with an incremented DPC disable counter which is never restored.
• If three or more threads race d_free_rcu, all but two will spinwait forever.

[thick lagoon]

oh my god this is such a workaround:

So we use a biased refcount on tmpfs DEntries when they are positive (=have an inode) and they are linked into the DEntry tree. But this means that at unlink time, we need to iterate over all DEntries and dput any that still have this biased refcount.

[thick lagoon]

letsgo, I have mounted and unmounted an empty tmpfs!

[high cloak]

nice

[thick lagoon]

Spot the mistake.

Answer: next is never stored to head->next. This causes dropped RCU callbacks and possibly the use of uninitialized memory.

[thick lagoon]

I feel I have made a lot of progress on the virtual filesystem during this weekend. And I have also fixed some bugs elsewhere, and implemented something called KEvents, then rcu_barrier (which differs from Linux rcu_barrier in that mine also implies waiting for a grace period) using KEvents.

(all this work is currently in the vfs branch in the git repository)

The plan for tomorrow: add a pointer to some sort of struct proc_fs_context { refcount_t ref; Path root, cwd; }; to struct Task and install the root of the mounted filesystem into ref, root, and cwd. Then, begin writing implementations of mkdir, mknod etc. and unpack some sort of initrd (not actually writing anything into the files yet). Some work on the page cache must be done before tmpfs will be able to store any file contents, but this'll probably wait until like next weekend or something.

[thick lagoon]

I'm thinking about how to format the initrd.

So the thing with tar is that it is easy to use and so, but it is a really shitty binary file format.

[torn nova]

i mean who cares if its shit, u only write the decoder once

and all the tooling u get for free

[thick lagoon]

True, tooling is the biggest advantage of tar.

[high cloak]

shrug

it's simple enough to the point that it isn't a burden to maintain

if you use another existing archive format you potentially have to decompress

[thick lagoon]

Didn't get much done today, other than pushing code to the repository which mounts root and manages a struct FSContext (the proc_fs_context described above). Tomorrow will hopefully have more results.

[thick lagoon]

rename() is slightly tricky, because if someone does mv /foo/a /foo/b at the same time as someone does mv /foo/a /foo/c, only one of them should succeed.

What might happen if I'm uncareful with my implementation is that both renames lookup /foo/a and they each get the DEntry that is /foo/a, but later the first rename succeeds and that DEntry is now /foo/b all of a sudden, and the second rename takes some locks, checks that the parent directory hasn't changed, etc., and moves from the DEntry that was /foo/a but is now /foo/b into /foo/c.

An implication of this is that I must either cover the path resolution under a global "rename lock", or return both the final component and the parent DEntry in name lookup and then revalidate the DEntry.

Something even trickier is that the first rename might be a RENAME_EXCHANGE operation, which atomically swaps the locations of two DEntries, meaning that the second rename, which fails because the target DEntry was moved, must be retried.

[meager sequoia]

there's also rename("a/b", "a/c/b") gets dentry for b - lookup("a/b/..") gets dentry for b - rename completes - lookup returns c even though the path was a/b/..

[thick lagoon]

yeah...

but that's not going to be an issue for me actually

because I will have a flag LOOKUP_PARENT_DIR which requires the final component to be the child DEntry of a parent directory and causes lookup to additionally return the parent DEntry.

oh wait nvm I misread (I assumed both were renames)

In that case it's actually OK for path resolution to return c.

[meager sequoia]

according to linux docs it isn't

the pathname resolution page specifically mentions the need to protect against it

[thick lagoon]

[thick lagoon]

nice.

[torn nova]

shit like this makes me wanna stay away from vfs stuff for a while

[small zinc]

just have a big vfs lock its that shrimple

no need to worry about it anymore

[thick lagoon]

but muh performance!!!1!1!

[vital siren]

I was just gonna do a big vfs lock which I hold while doing traversals and release across expensive stuff like calling the filesystem

rwlock

[hot rose]

• RCU and i honestly think it's completely reasonable

[vital siren]

I was gonna pull this off by leaving a "transition" dentry which causes anybody who comes across it during a traversal (for any reason) to release the lock, block on the dentry and then retry the entire traversal

Which I set up with the lock held and then release the lock and do whatever under that umbrella

[hot rose]

i think it would scale well enough for most workloads on most computers

[vital siren]

I might need to set up two of them if it's a rename or something

[small zinc]

hi hows keyronex going

[hot rose]

working on it isn't doing it for me at the moment so i've been studying openvme, xerox cedar in the meantime

[small zinc]

ah I see, damn

[thick lagoon]

I just wrote a vfs_rename function. It is 246 LoC and it uses 4 refcounting functions and in total grabs 5 different locks (if you count the rename seqlock and two INode spinlocks, this number becomes 8).

vfs_unlink is also a tiny bit annoying, but not nearly as much.

well both of these functions use a helper function do_get_path(dirfd, filename, lookup_flags) which I am yet to write :^)

do_get_path will be a pain in the bum to write

[torn linden]

isen't rename just link then unlink ?

like ```c
int rename(const char *src,const char *dst){
int ret = link(src,dst);
if(ret < 0) return ret;
return unlink(src);
}

[thick lagoon]

no... rename has some atomicity guarantees that this doesn't provide. this doesn't support renaming directories, either. and then there's RENAME_EXCHANGE.

[torn linden]

you can't link and unlink directoires on most OSes right (on mine you can that why i used this)

[torn linden]

what is RENAME_ECHANGE ?

[torn linden]

also that weird because binutils can provide it's own rename and binutils's rename use link and unlink

[thick lagoon]

yes you can... if the directory is empty.

[thick lagoon]

look at man 2 renameat2 on an up-to-date Linux system

[thick lagoon]

probably as a fallback incase the OS doesn't provide rename

[torn linden]

yes but in this case just manualy copy file content ?

in case the source and dest aren't on the same fs

[torn linden]

i will

[thick lagoon]

yeah you cannot link across devices either

[torn linden]

mein don't care
just unlink a non empty dir and you just leak memory !

[torn linden]

i will thanks (never know that rename was a syscall)

[thick lagoon]

for most Unix filesystems this is really simple...

if (i_nlink == 2) {
        // directory is empty
        return fs_blahblah_do_unlink(bleh);
} else {
        // directory is not empty
        return ENOTEMPTY;
}

[torn linden]

i know i'm just lazy

[torn linden]

also i just realise the link/unlink trick don't work on non unix like fs like Fat32

[pastel rivet]

that doesn't work for files within a directory? a file doesn't have a backlink so nlink is not bumped

[thick lagoon]

bruh

I will have to fix my tmpfs code to deal with this

eh, it's not that big of a deal

just keep track of the number of directory entries somewhere, like i_size

[pastel rivet]

well some stuff (e.g. xbps) does rmdir on all directories going up to the root to clean up empty dirs

e.g. when uninstalling a package

i figured that out when trying xbps-remove on managarm and it nuked /usr because we didn't check for directory not empty on rmdir

[thick lagoon]

yeah, well obviously it is a big deal if you are able to remove non-empty directories

but it's not a very big deal to fix it

[pastel rivet]

ah

[thick lagoon]

filesystem 'security' question: if the mode of a file is -r-xr-xrwx, is the owner and group of the file able to open the file for writing?

(obviously the owner is able to chmod it to whatever it likes, but ignoring that.)

[swift pebble]

the same happened to @rigid idol with ironclad btw lol

[pastel rivet]

lol

[torn linden]

owner and group can't write

which is funny

other is only for neither group or owner so if you fit in owner or group you don't get other perm

[thick lagoon]

I looked at managarm sources a bit, and it seems like there's no chown??

in mlibc it is just a stub

and in posix-subsystem tmp_fs.cc chown is never mentioned

I was hoping to epicly pwn managram by chowning a setuid shell script to uid 0 😭

anyway it is time for pain

I will begin implementing do_get_path now

[thick lagoon]

epic:

[thick lagoon]

I was correct, this is a PITA. I am enjoying this very little.

[thick lagoon]

alright I have written some path lookup code now (untested).

do_get_path is such a mess

[thick lagoon]

FSCK, someone messed up reference counting...

(and that someone is me)

[thick lagoon]

Instead of working on this I have spent time making a new desktop wallpaper

[tough lily]

voronoi noise?

[thick lagoon]

I guess you can call it "fractal" Voronoi noise (not exactly fractal because I don't actually add them together; instead, I interpolate between noise layers with yet another noise function (Perlin-like noise).

[tough lily]

Looks sick

I can imagine it looking even cooler if it were dynamic

[thick lagoon]

Yeah, but then I'd have to make it real-time (most likely by porting it to GPU; this is CPU-drawn)

[thick lagoon]

At like 2560x1440 pixels, it takes probably approximate half a second to render.

(probably like 25000 points generated by poisson disc sampling, stupidly evaluates perlin-like separately for each pixel when gradient evaluation can be done jointly for each 128x128 block of pixels, however it does use KDTrees to find the distance to the nearest neoghbouring point, which is a totally unnecessary optimization since it could've just as well iterated over the neighbouring pixels (a pixel map is used anyway during poisson disc sampling))

[torn nova]

looks like a half-life texture

[thick lagoon]

lol

The idea crossed my mind that this can be used for asset generation for video games.

This can easily (in theory :-)) be made tiling as well.

[thick lagoon]

bruh

(do_get_path dies on rename)

pushed it to github in this broken state (haven't made a commit in three weeks!), will attempt to fix next week. probably a missing path_get or erroneous dput

[thick lagoon]

I have been experimenting a bit with recursive page table mappings for a potential rewrite (), and I must say, that they are actually pretty nice to work with.

e.g. here's how a get_pte_early type of function can be implemented in a really simple way:

Here's a possible virtual address space layout:

Even without any intention to treat PTEs like any other kind of virtual memory (page them to disk, etc.), recursive page tables are actually really nice.

Which is funny to say, because I remember reading about them on the old osdev wiki, thinking "what drunkard came up with this piece of complicated shit when it's so much simpler to traverse the page tables yourself?"

[minor trout]

I like ur maintaining this project 🙂

[thick lagoon]

If I rewrite everything it will be in the form of NT larp

[fathom lake]

yeah theyre nice

[fathom lake]

had the same progression as you there lol, i dont plan to page ptes out or anything but its just nice to access ptes with no extra tables this way

one thing that you can do with them is have a linked list of free PTEs for temporary mappings stored in an array and if that array is page-aligned and a multiple of the page size in byte-length then you can just use that in place

use recursive mappings to access the array/list to get a temporary PTE and its already in a page table so when you set the present bit its immediately usable

[thick lagoon]

why is this illegible...

ah

I don't set the page global enable bit in cr4

nope, apparently that's not it... (??)

actually no it probably has something to do with PGE

on TCG it works

[thick lagoon]

Init IDT... OK!
HalStartKernel: multiboot_info=0x0000000000001000, load_offset=0x200000
CPU model: AMD Ryzen 9 7950X3D 16-Core Processor           (AuthenticAMD)
Memory map:
  [ 0] [0x0 - 0x9ffff] Usable RAM
  [ 1] [0x100000 - 0x7fffff] Usable RAM
  [ 2] [0x800000 - 0x807fff] ACPI NVS Memory
  [ 3] [0x808000 - 0x80afff] Usable RAM
  [ 4] [0x80b000 - 0x80bfff] ACPI NVS Memory
  [ 5] [0x80c000 - 0x810fff] Usable RAM
  [ 6] [0x811000 - 0x8fffff] ACPI NVS Memory
  [ 7] [0x900000 - 0xed3efff] Usable RAM
  [ 8] [0xed3f000 - 0xedfffff] Reserved
  [ 9] [0xee00000 - 0xf8ecfff] Usable RAM
  [10] [0xf8ed000 - 0xf9ecfff] Reserved
  [11] [0xf9ed000 - 0xfaecfff] type 20
  [12] [0xfaed000 - 0xfb6cfff] Reserved
  [13] [0xfb6d000 - 0xfb7efff] ACPI Reclaimable
  [14] [0xfb7f000 - 0xfbfefff] ACPI NVS Memory
  [15] [0xfbff000 - 0xfec1fff] Usable RAM
  [16] [0xfec2000 - 0xfec5fff] Reserved
  [17] [0xfec6000 - 0xfec7fff] ACPI NVS Memory
  [18] [0xfec8000 - 0xfef3fff] Usable RAM
  [19] [0xfef4000 - 0xff77fff] Reserved
  [20] [0xff78000 - 0xfffffff] ACPI NVS Memory
  [21] [0xfeffc000 - 0xfeffffff] Reserved
  [22] [0xfd00000000 - 0xffffffffff] Reserved
Total RAM bytes: 261967872  (249 MiB)
Mapping HHDM range [0xffff880000000000 - 0xffff8800000a0000]
get_pte(0xffff880000000000, 1)
p4e = 0xffffe8743a1d0880
p3e = 0xffffe8743a110000
p2e = 0xffffe87422000000
p1e = 0xffffe84400000000
Reading p4e...
KERNEL PANIC!
What: Page fault on address 0xffffe8743a1d0880! cause: kernelmode data read with reserved bit set in PTE.
  RIP: ffffffff8000f936  RFLAGS: 0000000000210082
  RAX: 0000000000000000  RBX: ffffe8743a110000  RCX: 0000000000000000  RDX: 00000000000000e9
  RDI: ffffffff80003cf8  RSI: ffffffff80003d07  RBP: ffffe87422000000  RSP: ffffffff80003f40
  R8:  00000000000001f0  R9:  0000000000000000  R10: 3030303030303030  R11: 0000000000000000
  R12: 0000000000000001  R13: ffffe84400000000  R14: 0000000000000004  R15: ffffe8743a1d0880
Halting...

Incase you haven't noticed, I added the most important debug print yet.

I could flex and say "first try IDT!!!1!1!"... but really, the entire thing was copied from current Davix

that's __PG_NX | __PG_GLOBAL | __PG_WRITE | __PG_PRESENT set in there

these are the "interesting" registers:

oh, and

EFER = LME | LMA | NXE

CR4 = (lots of shit) | __CR4_PGE

this is really strange why it encounters a reserved bit in a PTE

eh, I will might look at this tomorrow.

[fathom lake]

do you set the global bit

because amd processors reserve the global bit on higher-level PTEs which is all of them when using recursive

[thick lagoon]

wtf actually?

wtf

why

bruh

[fathom lake]

on intel its software use on high level PTEs, on amd its reserved-must-be-zero on high level ptes

had literally this exact issue myself a while back

youd only know this through experimentation or by double checking the AMD manual, but the working on TCG but not otherwise is a telltale sign of it if you know that fact already lol

[thick lagoon]

this basically makes it impossibleish to do recursive PTE in kernel-space without incurring massive overhead for TLB invalidations on kernel page table unmap

pain in the bollocks

[fathom lake]

i just eat the cost tbh, as does NT actually

pain in the bollocks is correct though lol

[thick lagoon]

I guess one (bad) solution is to never unmap kernel page tables

or eat the cost 😁

[fathom lake]

i also dont unmap kernel page tables so doesnt hit me there either

but yeah

NT just eats the cost afaik

though they might have some check to conditionally enable the global bit on intel CPUs idk

i dont have NT source code after all i just saw the recursive stuff in the windows internals book and double checked with kernel debugging

this is my biggest gripe with amd cpus for osdev lol

[thick lagoon]

probably no, because if the global bit is just ignored unless it is a lowest-level PTE or a huge page PTE, it doesn't matter.

[fathom lake]

yeah

the only point it matters is when a high level pte gets treated as lowest level by recursive mappings and you want the ptes themselves global

[thick lagoon]

I guess the one thing that this implies that is annoying is that if you cannot set G bit there, you will increase TLB pressure on kernel page table entries if there are lots of kernel page table modifications going on (because a page table page is duplicated in TLB for each PCID)

[fathom lake]

yep

which is precisely why i wanted G set and then found this issue

[thick lagoon]

unfortunate but probably not a massive performance hit, because seldom is kernel page table modifications a hot path.

[fathom lake]

but im not really doing a lot of kernel page table modifications anyway, idk how much youre doing

yeah

ive got one small block that gets modified for temporary mappings (mmio or uacpi etc) and then when i grow my kernel mode allocator pool thats a bunch but idk what else youd be doing thatd do a ton of kernel page table mods

honestly the biggest annoyance with this thing is just how hard it is to diagnose lmao

if you dont know amd is different here its really hard to figure out

[thick lagoon]

if you expect the global bit to be effective in higher level PTEs but they aren't and you as a result access freed memory because of an unmap-context switch-map sequence that leaves stale TLB entries for PTE space pages in other PCIDs, that'd be debugging hell

[thick lagoon]

Thank you so much for this information; it would've taken a really long time to figure this out myself.

[fathom lake]

glad i could help

[round cradle]

i had to find that out the hard way #1142591991947989093 message

[thick lagoon]

one interesting thing with recursive page tables is how they interact with huge pages

because if you have a level 2 huge page PTE, it will also live as a level 1 PTE with the PAT bit set

which has interesting implications

anyway it doesn't matter, since speculative accesses to the memory type that it becomes are disallowed, and nonspeculative accesses to that memory don't happen

[thick lagoon]

yay!

[thick lagoon]

I am starting to get really annoyed at my syntax highlighting.

no you buffoon that is not an int

[torn nova]

DSL?

[thick lagoon]

datastructure library

or "Davix support library"

[torn nova]

Domain specific language

[thick lagoon]

yeah

the two hardest things in computer programming:

• cache invalidation
• naming things
• off-by-one errors

[torn nova]

True

[thick lagoon]

ugh

I updated the fucking extension and it changed my vscode theme

fuck this

how do I downgrade? I hate this.

[torn nova]

Yes that whole thing expands to an int

[thick lagoon]

the thing is that it works when I compile with g++, but this goddamn idiotic syntax highlighter is absolute ass

I will turn of syntax highlighting

screw this

[meager sequoia]

what extension(s) do you use

[thick lagoon]

I use(d) vscode-ccls (ccls-project.ccls 0.1.29). Upgrading it to 0.1.31 breaks my color scheme which I'm not going to accept (and it also doesn't fix the typedef int ...; problem so it only has disadvantages).

[meager sequoia]

why not just use clangd?

[high cloak]

any reason why

because clangd works almost flawlessly

[thick lagoon]

iirc I initially looked at clangd and saw that it wants a generated compile_commands.json file--that seemed annoying-- so I found ccls which also wants a compile_commands.json, OR a .ccls file which is just a compiler driver and a list of arguments separated by line. that was many years ago.

[thick lagoon]

I should probably look at clangd though, since ccls is shitware (see e.g. this:).

[meager sequoia]

one of the main benefits of using clangd is that it's just clang

so you're not gonna have stuff like that

it's gonna interpret stuff exactly the same as normal clang

[weary prairie]

compile_commands.json is standard, cmake can generate it, meson generates it by default, and you can generate it yourself with Bear

[high cloak]

🤓 actually it's libclang

[round cradle]

i think those are 4 things

[worn wolf]

And scope creep

[thick lagoon]

clangd seems to not shit the bed when confed properly. huh.

[thick lagoon]

A neat hack which Linux does is that SLAB can deal with freeing objects by pointers into the middle of the object, basically letting you do things like

struct foo {
        int x;
        int y;
};

void bar()
{
        struct foo *foo = malloc(sizeof(*foo));
        int *py = &foo->y;
        free(py);
}

(except you call something like kvfree_rcu_cb(py) instead of free(py)).

This is used to implement kfree_rcu so that the object's embedded rcu_head can be at any offset less than PAGE_SIZE within the object.

wtf is this thing called and how do I turn it off?

[pastel rivet]

inlay hints?

[pastel rivet]

does this work on the assumption that each object is sized to be a power of two so you can just mask off the lowest n bits to get the object pointer?

[thick lagoon]

no I don't think so

[pastel rivet]

how else does it figure out that py belongs to foo?

[thick lagoon]

I believe it works by getting an object's index in a slab page, presumably by division

[pastel rivet]

so the same as what i suggested? :^)

[thick lagoon]

object size isn't always a power-of-two

[pastel rivet]

okay fair

although i assumed slab entries are power-of-two-sized?

[thick lagoon]

Linux has e.g. kmalloc-192 and kmalloc-96

[thick lagoon]

no

[thick lagoon]

you can look at /proc/slabinfo to see this.

[pastel rivet]

huh

well then yeah just masking doesn't work

[thick lagoon]

yeah I figured it out already

thanks anyway

[thick lagoon]

with recursively mapped page tables, unmapping a kernel page table practically requires a full TLB flush on all CPUs. this is pain.

(the reason it practically requires a full TLB flush is because paging-structure cache entries are created per-PCID for the kernel page table mappings themselves. and also because it is pain to keep track of the addresses that need flushing.)

[vital siren]

how often are you unmapping a kernel page table

[thick lagoon]

not very often

but it's still annoying

[vital siren]

i allocate all the kernel page tables ahead of time

at boot

i size the dynamic areas of kernel space as some fraction or multiple of phys mem size

[thick lagoon]

yeah... for 64-bit x86 that is not viable

[vital siren]

why not

[thick lagoon]

partially because hugepages

[vital siren]

what does that have to do with it

[thick lagoon]

e.g. you want to use 1 GiB pages to map the PCIe ECAM if possible

so you cannot preallocate PML1 and PML2 for that area

probably the best thing to do is to:

• assume that big (more than a couple of pages) vmap/kmalloc_large/vunmap/kfree_large is very uncommon and accept that they will be a massive performance hit
• optimize small (e.g. four pages, my kernel stack size) kmalloc_large and kfree_large by caching the PML1s (not removing them from the page tables)

[vital siren]

this is only a slight wrinkle to the scheme i suggested though

this is just initializing one thing a bit later

[thick lagoon]

yeah

[vital siren]

if you want to know how to do really robust dynamic kernel space allocation of massive regions theres some descriptions in "what makes it page" of the windows way

i feel like it is way more complicated than any hobby kernel would ever need though

[thick lagoon]

I should buy that book

[thick lagoon]

yeah probably

I guess one scheme which is possible is to have one area for small pages and one area for each huge page size

possibly initializing the area for small pages to be empty

and when you need e.g. more PML1 space, you allocate that from the PML2 space etc.

but that quickly becomes overly complicated

[fathom lake]

I actually sort of do that, albeit I only have a space for small pages

though I can allocate usable memory in large blocks from the buddy alloc

[pastel rivet]

you could do what mammogram does and only map chunks of ecam for one bus at a time on demand :^)

[meager sequoia]

this made me curious on how regular global tlb entries are invalidated, and i can't seem to find any operation that fits the bill

[fathom lake]

mov cr3

[vital siren]

no its toggling the PGE bit in CR4 i believe

is how you flush global tlb entries

mov cr3 specifically doesnt flush those

[fathom lake]

oh right

invlpg also flushes global entries for that page iirc

[vital siren]

yeah

[fathom lake]

what extra sucks is on intel cpus you could actually make the recursive page tables global

but thats a reserved bit page fault on amd

[vital siren]

i imagine that on intel cpus NT actually does make them global

and not on amd cpus

and it may do some like patching of kernel code at boot time

to avoid a branch on cpu type

[fathom lake]

not sure

id assume that theyre loading a initial pte from a variable and overriding the address for that though

so you could do the branch only once

thats how id do it anyway

[vital siren]

yeah

[fathom lake]

and if i had literally any intel hardware i might tbh lol

[meager sequoia]

invlpg: invalidates single-address globals, but only for current pcid
invpcid(0): invalidates single-address, but no globals and only one pcid
invpcid(1): not single-address nor does it do globals, and only one pcid
invpcid(2): invalidates globals on all pcids, but not single-address
invpcid(3): all pcids, but not single-address nor does it do globals
toggle pg: invalidates globals on all pcids, but not single-address
write cr3: not single-address nor does it do globals, and only for new pcid
toggle pge/pcide: invalidates globals on all pcids, but not single-address
toggle pae/smep: invalidates globals, but not single-address and only for current pcid

there is not a single operation that invalidates a single address on all pcids including globals

which means all kernel unmap/reduce-privilege operations need a complete tlb flush

that seems Suboptimal

[vital siren]

thats done extremely rarely

potentially neverish

[fathom lake]

invlpg i think technically is allowed to hit other pcids but no guarantee yeah

[vital siren]

does it not ignore the pcid if the G bit is set

[meager sequoia]

nope

[vital siren]

thats total nonsense

[fathom lake]

invlpg flushes current pcid and globals on that address

[vital siren]

i cant imagine theyd implement it that way

[vital siren]

this makes sense

[meager sequoia]

oh wait i just can't read
invlpg:

It also invalidates any global TLB entries with that page number, regardless of PCID (see Section 5.10.2.4).1

false alarm

[fathom lake]

yep

if its global it hits all PCIDs because it just invalidates the global cache separately

and it "may or may not do so for TLB entries associated with other PCIDs"

if pcide is 0 then it hits the pcid-0 entries

[meager sequoia]

this isnt exclusive to recursively mapped page tables though

with manual walking through hhdm you still have this issue

for the same reason

because the only operations that do any paging-structure cache invalidation either only work on one pcid or are full flushes including tlb

[fathom lake]

yeah the only targeted stuff is single-address

*targeted global/all pcid stuff

[meager sequoia]

well for this you want single-address all-pcids and on x86 that only exists for global tlb entries and not for paging structure cache entries

[fathom lake]

yeah

what i was trying to say but way more competently said lmao

[meager sequoia]

oh i misinterpreted then

[fathom lake]

my brain lumps tlbs and paging structure cache together and then i get or cause confusion by that

maybe when i get around to actually having un/re-mapping that isnt just swapping off of limine ill get around to really internalizing this stuff

but thats neither here nor there

[thick lagoon]

The paging-structure cache invalidation scheme on x86 is IMO horrible.

[thick lagoon]

I am back at work now and so will have less time to do fun stuff like kernel development, also I will probably feel more tired after the work days.

[thick lagoon]

yeah so I have kind of abandoned "current" davix in favour of rewriting it with NT larp

and I just wrote some very scary lines of code

/**
 * KeEnterIRQContextFromUserspace - enter IRQ handler context from user mode.
 *
 * This routine is called by the architecture's low-level interrupt vector entry
 * point(s) before calling KeHandleInterruptVector if the interrupt struck while
 * we were executing in user mode.
 */
void KeEnterIRQContextFromUserspace(void)
{
    KeDisablePreemption();
    KeDisableDPCs();
}

/**
 * KeExitIRQContextToUserspace - leave IRQ handler context to user mode.
 *
 * This routine is called by the architecture's low-level interrupt vector entry
 * point(s) after KeHandleInterruptVector returns if the interrupt struck while
 * we were executing in user mode.
 */
void KeExitIRQContextToUserspace(void)
{
    /*
     * Interrupts need to be enabled when dispatching DPCs or when entering
     * the scheduler.  But we must disable them before leaving kernel-mode.
     */

    if (KiEnableDPCsAndTest()) {
        HalEnableRawIRQs();
        KeDispatchPendingDPCs();
        KeEnablePreemption();
        HalDisableRawIRQs();
    } else if (KiEnablePreemptionAndTest()) {
        HalEnableRawIRQs();
        KeDispatchPendingPreemption();
        HalDisableRawIRQs();
    }
}

^ not very scary

/**
 * KeEnterIRQContextFromKernel - enter IRQ context from kernel mode.
 * @vector: interrupt vector number
 * Returns false if IRQs were lazy-disabled and interrupt handling is deferred.
 *
 * This routine is called by the architecture's low-level interrupt vector entry
 * point(s) before calling KeHandleInterruptVector if the interrupt struck while
 * we were executing in kernel mode.
 */
bool KeEnterIRQContextFromKernel(unsigned int vector)
{
    if (!KeIRQsEnabled()) {
        /*
         * IRQs are lazy disabled; store the pending interrupt and exit
         * with interrupts disabled.
         */
        KeSetPendingIRQ();
        HalWritePerCPU(kiPendingVector, vector);
        return false;
    }

    unsigned int preempt_cnt = HalReadPerCPU(kiProcessorContext.preemption_counter);
    unsigned int dpc_cnt = HalReadPerCPU(kiProcessorContext.dpc_counter);

    KeDisablePreemption();
    KeDisableDPCs();

    unsigned int flags = 0U;
    if (preempt_cnt != 0)
        flags |= 1U;
    if (dpc_cnt != 0)
        flags |= 2U;

    HalWritePerCPU(kiIRQEntryFromKernelFlags, flags);
    return true;
}

/**
 * KeExitIRQContextToKernel - leave IRQ handler context to kernel mode.
 *
 * This routine is called by the architecture's low-level interrupt vector entry
 * point(s) after KeHandleInterruptVector returns if the interrupt struck while
 * we were executing in kernel mode.  If KeEnterIRQContextFromKernel returns
 * false, this function is not called.
 */
void KeExitIRQContextToKernel(void)
{
    /*
     * Interrupts need to be enabled when dispatching DPCs or when entering
     * the scheduler.  But we must disable them before returning from IRQ
     * context.
     *
     * If the preempt counter or the DPC counter were already zero, as
     * indicated by corresponding bits in kiIRQEntryFromKernelFlags, they
     * will be dispatched by the calling code and we should do nothing.
     */

    unsigned int flags = HalReadPerCPU(kiIRQEntryFromKernelFlags);

    if (KiEnableDPCsAndTest() && (flags & 2U)) {
        HalEnableRawIRQs();
        KeDispatchPendingDPCs();
        if (KiEnablePreemptionAndTest() && (flags & 1U))
            KeDispatchPendingPreemption();
        HalDisableRawIRQs();
    } else if (KiEnablePreemptionAndTest() && (flags & 1U)) {
        HalEnableRawIRQs();
        KeDispatchPendingPreemption();
        HalDisableRawIRQs();
    }
}

^ super duper scary

[torn nova]

That's nice

[thick lagoon]

no it's not

rewrites are a disease that plague this server

[torn nova]

Nt kernels are cool though

[thick lagoon]

I mostly just end up copying stuff line by line from the previous iteration and changing very minor things

[vital siren]

Were you inspired by the mintia cruft discussions

[vital siren]

Sometimes they're necessary to make true progress

Or rather they're sometimes the shortest path to making true progress

[round cradle]

can confirm

[thick lagoon]

current status:

• the really bare bones stuff, such as memory allocation for small and large objects, and mapping physical memory ranges into kernel virtual memory, works.
• deferred procedure calls (hopefully) work.
• HPET, TSC, APIC are calibrated
• I am currently getting some sort of "IRQ subsystem" going, will hopefully have a percpu dispatched KTIMER done tomorrow (local APIC oneshot driven).

[thick lagoon]

no, at least I don't think so

"Initial commit" was 11 days ago

[torn nova]

Calibrating hpet is crazy 💀

[round cradle]

boron actually started out in a similar manner as a fun fact

but cool I guess

good luck with the new rewrite

[thick lagoon]

lmao

[worn wolf]

You can never be too sure

[thick lagoon]

after the application of really precise calibration techniques over a time period of 42000 jiffies (patent pending on the super-advanced calibration methodology, so I cannot tell you all the details), I have determined that the HPET main counter runs at one clock cycle per clock cycle.

groundbreaking work

[torn nova]

Buy a separate PCI device that has a timer and calibrate hpet using that instead of reading its frequency

[thick lagoon]

I'm pretty sure Linux does some cursed thing where they calibrate TSC against both the PIT and the HPET, and fail if they are too far off from each other.

[torn nova]

No idea, but they definitely have mechanisms for detecting skews or unreliable time sources

[thick lagoon]

letsgo

ok so I will actually not be doing the one-shot timer stuff right now

instead I will go for periodic, so that I can fall back to something like jiffies for a fast clock when the TSC doesn't exist

I added this very beautiful code so that there is actually time for the timer interrupt to hit us

[torn nova]

i like how u have multiple timestamps next to each other

[thick lagoon]

?? wdym

[torn nova]

look at your memory map

[thick lagoon]

oh lmao

look at the second line of 0xe9 output, I'm sure you'll like it

[torn nova]

lol

[thick lagoon]

I kinda want to do some log ring bullcrap

but first I will get some form of scheduler going, and start up SMP and such

[torn nova]

im gonna do log ring now because i lose my early log messages

[torn nova]

whats the macro to get that compiler info?

[thick lagoon]

not a macro

Makefile stuff

[torn nova]

ah

[thick lagoon]

easy

Ok, I need to make some sort of roadmap for myself, I think.

Roadmap of NT larp rewrite:

• memory allocation etc. (done)
• per-CPU timers (done)
• CPU scheduling (done; TODO: testing and load balancing)
• SMP bringup (done)
• remember to fix the TLB code so that it works in SMP (done)
• locking and synchronization primitives:
  • RCU (my own 'Segment Tree' variant)
  • Mutex based on a turnstile-like thing. At any time the mutex is either NULL (free), points to the owner KTHREAD (busy), or points to some external memory which holds a wait list of some sort.
  • Reader-writer semaphore
• Multiprocessor über-initgraph (Managarm larp)
• PCI (at least conf space, device/bus enumeration, etc. -- really simple stuff and stuff needed for uACPI PCI functions)
• ACPI EC driver,
• IO subsystem (I really want to have some kind of I/O packet stack similar to that of Keyronex, I think that is interesting)
• Filesystem stuff (do it properly now; no two thousand completely untested lines of code in a single file)
• Page cache
• Userspace memory management
• Mount a root filesystem and run /sbin/init
• TODO...

oops

[round cradle]

IRQ subsystem should probably be handled in Ke and not Hal

cause there isn't a different way to connect interrupts depending on the ISA around the x86_64 chip

its just the standard IDT

the HAL can take care of the actual timer interface though

[thick lagoon]

well it's in both

:-)

so the bulk of the IRQ system (vector allocation, threaded interrupt dispatching, etc.) will be in Ke, but it will call into Hal to do things like HalAcknowledgeInterrupt etc.

[thick lagoon]

@stoic violet pin this

[thick lagoon]

thanks

[stoic violet]

np

[thick lagoon]

I am now larping as a powerpoint engineer

(things in upper layers can call into things in lower layers)

the thing is, it is relatively easy to roughly sketch the architecture of a kernel like this in the lower layers, but as you move further upwards the stack, it gets more messy

partially because there are more layers beneath you that you can call into

something like the memory manager, filesystem and IO subsystem

e.g. user wants to read in some bytes of a file.

• performs a syscall,
• the syscall calls into the filesystem driver,
• the filesystem driver page faults,
• the memory manager calls the IO subsystem to satisfy the page fault,
• the IO subsystem wants to allocate some memory but the system is OOM, blocks on the global free list
  it quickly becomes messy and difficult to keep track of everything in your mind

I want to design some kind of robust priority boosting system. But I should really do that at a later time.

[high cloak]

bruh

[thick lagoon]

Some notes for myself:

• DPCs are allowed to call some synchronization primitives (importantly KeSetEvent(KEVENT *) is part of these).
• KEVENT is similar to a Linux completion. There will be a function KeWaitForEvent(KEVENT *) which allows waiting for another thread or DPC context to call KeSetEvent(evt).
• KEVENT should be designed with epoll in mind. Ideally, an epoll instance is just a struct with state information, list linkage, and a KEVENT which you wait on. But this means that a KEVENT can have two kinds of waiters:
  • tasks blocking on KeWaitForEvent
  • epoll instances

I don't intend to have a KeWaitForMultipleEvents-type of function (or maybe I will write one, but then it will most likely be implemented in terms of the epoll infra)

[fathom lake]

ah yes manualresetevent my beloved

or is it auto reset event

both are great

[thick lagoon]

what is that?

[fathom lake]

manualresetevent and autoresetevent are the userspace dotnet versions of KEVENT

which is where i started so thats what my brain calls them instinctively lmao

[thick lagoon]

I'm guessing autoresetevent is similar to a binary semaphore which is reset whenever KeWaitForEvent succeeds. Is this correct?

[fathom lake]

yep

[thick lagoon]

👍

[fathom lake]

on NT theres a flag when you create a KEVENT to pick which mode it uses

[thick lagoon]

well I'm not NT

[fathom lake]

true

either way this sort of KEVENT is so nice to have

[thick lagoon]

the plan is to have a separate KSEMAPHORE or something with actual semaphore semantics (the only user I have in mind for this is the uACPI OSL ) which is similar to an autoresetevent I guess

because of the epoll stuff, my KEVENT is probably going to be a manualresetevent on lots of steroids

[fathom lake]

lol same, the only user of true semaphores for me is the uacpi kernel event functions which isnt confusing at all lmao

[thick lagoon]

yeah tbh uacpi_kernel_wait_for_event and uacpi_kernel_signal_event are poorly named

[fathom lake]

legit the hardest thing getting uacpi going for me was how long it took me to wrap my head around no those arent kevent those are for semaphores yeah

bit late to rename them though

[thick lagoon]

I remember using lai (lightweight AML interpreter, managarm's old thing) which had like a single futex like API and wondering why such an interface would be used

[torn nova]

what should they be named then?

[thick lagoon]

e.g. uacpi_kernel_wait_for_semaphore and uacpi_kernel_signal_semaphore are better names IMO

[fathom lake]

honestly im considering a futex for my kernel just because all the zig std sync primitives can operate on top of just a futex impl tbh

[torn nova]

they're named after the respective aml operator

[fathom lake]

yeah id say just s/event/semaphore on them

[thick lagoon]

ah, makes sense

[torn nova]

It has Event/Signal/Wait

[fathom lake]

that makes sense then yeah

wonder why aml calls it that though

[torn nova]

probably because aml was designed by incompetent people

[thick lagoon]

In this case, I would guess that the API was designed specifically with the Managarm usecase in mind, a microkernel so maybe you are actually implementing it in terms of SYS_futex and it makes a bit more sense

[fathom lake]

fair lmao

[torn nova]

or maybe the idea was u use one single api for both events and mutexes

ah lol

[fathom lake]

wait wrong context

[torn nova]

i didnt look closely

[fathom lake]

theres two convos happening rn and i got mixed up

[fathom lake]

saw this and my brains like but aml has both and then i realised this was probably about the futex thing which idk about

[torn nova]

yeah

i was wondering if lai has both mutex/futex

[fathom lake]

that i cant speak to

[thick lagoon]

I'm pretty sure it only has lai_sync_state or whatever it's called

which is basically just a futex address object because IIRC the APIs deal with lai_sync_state *s

[torn nova]

oh yeah i remember in lai u have to allocate state separately for each eval

its basically a much more low level lib than uacpi

[thick lagoon]

I'm wondering if it is possible to have priority inheritance thru KEVENTs no this is a stupid idea

it is a stupid idea because KEVENTs aren't a lock so they don't have a lock holder, who would you boost?

[torn nova]

they have something like await right

oh wait yeah

well u could have the caller hint the thread it expects to let it make progress or something

[thick lagoon]

yeah but there's also the epoll stuff to consider

anyway it would become a mess

it's better to just... if a thread makes some IO request and blocks on it, copy that thread's priority when that IO request is made and then store it in like the IO packet or something

[torn nova]

ig

[thick lagoon]

I'm wondering if and how to charge threads for the CPU time of other threads inheriting a threads priority through PI

basically, if T1 is really high priority and T2 is really low priority, and T2 lends T1's priority for an extended period of time, is it possible to somehow charge T1 for this CPU time?

I'm leaning towards the answer being 'no, not without excess complexity' and that is not a place where I want to go

[torn nova]

u need hyena advice

[thick lagoon]

this also becomes more complicated taking into account that there are potentially multiple threads that T2 is inheriting its priority from, and those threads can in turn have inherited priority

[thick lagoon]

definitely

but I'm also kind of answering these questions myself, with the answer "this is impossible without a lot of complexity and you don't want that"

I've heard of like the Windows NT Autoboost stuff, but I have no idea what any of the interfaces and data structures for that look like. I am a bit curious about that.

[round cradle]

Internally they're called synchronization [autoreset] and notification [manualreset]

[thick lagoon]

unsurprisingly there is very little information online about what Autoboost actually looks like. It is mentioned here and there, 'Autoboost-tracked locks' etc., but I find nothing which describes how it looks like on the inside

IIRC someone mentioned patent stuff regarding Autoboost. So maybe it is best not to dig too deep.

not really, no

do you study NT or what? You seem to have a lot of insider knowledge about it

I guess the single most important thing is that I am unsure how I will do PI stuff inside the mutex lock and unlock implementations. Like what structures to use, and where to store them, etc.

Like with "normal" non-priority-inheriting Mutexes, it is easy. You have the mutex which is some status bits and a waitlist of tasks, and each task has some struct which is linkage for this list.

[thick lagoon]

A list for each task of what locks it is holding? And what is this used for?

And where does linkage for this list come from?

I imagine one usecase for such a list is to iterate over it and find the priority floor you are boosted to after you have released a lock.

It's probably possible to keep a list per task of only the locks that actually have high-priority waiters and so are relevant for PI.

[hot rose]

i recommend the turnstile

it's a universal mechanism for thread priority inheritance

[torn nova]

is that a spinlock or a mutex?

[hot rose]

this solaris innovation is now used widely (solaris had a huge impact on smp scaling techniques because they published their techniques), xnu, freebsd, and turnstile have all got it

[hot rose]

it's a primitive which you can build a sleeping mutex, rwlock, or other synchronisation objects on top of

[torn nova]

so its not for e.g. irq critical sections?

[thick lagoon]

It's a primitive for things that sleep

hopefully you can disable interrupts without sleeping

:-)

[hot rose]

in solaris the ambition was that almost all interrupt handlers would be threaded, so it could be for those, but not for true interrupt context

[torn nova]

interesting

is there a paper for turnstile

[thick lagoon]

there are some websites or wikis that describe it, I think

[hot rose]

in a usenix submission called "realtime scheduling in sunos 5.0" but i can't find it

https://www.dre.vanderbilt.edu/~schmidt/PDF/beyond_mp.pdf?utm_source=google.com they are touched on in here (good paper in its own right, this is a summary of the entire approach that was taken in solaris to smp)

[torn nova]

thanks

[hot rose]

http://sunsite.uakom.sk/sunworldonline/swol-08-1999/swol-08-insidesolaris.html here is a more detailed description

https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/os/turnstile.c#L28 and the big theory statement on them in illumos

[torn nova]

why doesnt linux use these?

[hot rose]

torvalds is opposed to priority inheritance

there are rt_mutexes in linux added solely because RTLinux definitionally needs them

[torn nova]

ah right

do u know which approach they use?

[hot rose]

they keep a tree of waiters keyed by priority, and the rt mutexes are fat objects

[torn nova]

fat objects?

[hot rose]

one of the distinctive properties of turnstiles is that an rwlock, mutex, etc can be pointer-sized and a pool of turnstiles is used to keep sleep queues, priority inheritance chain, etc

[torn nova]

ah

[hot rose]

by contrast an rt_mutex is large https://github.com/torvalds/linux/blob/8f5ae30d69d7543eee0d70083daf4de8fe15d585/include/linux/rtmutex.h#L23

[torn nova]

yeah

[thick lagoon]

interesting that they take a completely different approach to it. IMO this seems more convoluted than priority inheritance.

I'm seeing a lot of disadvantages to this. Mainly that now you have to traverse the ->blocked_on list in the scheduler every time you encounter a 'donor' task, but also the complications of CPU migration etc.

I'm seeing a nightmare situation where you have a task T1 on CPU1, and then a bunch of tasks try to grab a lock which T1 holds, each of them becoming a 'donor' and migrating to CPU1. This might cause T1 to migrate to CPU2 due to load balancing, but now each of T2, T3 ... blocking on T1 will also migrate to CPU2 etc.

[thick lagoon]

In C++ this means the kiCPU{Present,Online}Bitmap arrays will have 1 as the first array item and the rest are zero filled, does it?

Stuff seems to be working as intended at least, as indicated by a quick little test.

I am very much liking the far right portion of this graph. Hopefully it will all be green onwards. (== I write much code)

[fallen whale]

the problem with autoboost is that this is all the information that is publicly available

each thread stores records, each record stores at least 2 trees

[vital siren]

The first part isn't even true anymore

It now stores a pointer to an array of records

rather than directly storing the records

[fallen whale]

id love to learn more

[fallen whale]

but still in kthread, right?

i wonder what the size limit is

6 was very limiting

it probably worked only when it worked for pushlocks only

[thick lagoon]

Thinking about it a bit more, the Linux proxy execution thing described in the lwn article linked by @ uwop_epilog might actually be better than priority inheritance from this specific perspective. But it is impossible to confidently make such a claim without measuring which I for obvious reasons (not having a kernel competent enough to measure yet) have not done.

Proxy execution can actually be feasible, if you're willing to accept that it requires careful thought about how it impacts CPU load balancing (because SMP proxy execution "virtually migrates" blocking schedulable items across CPUs, which is enough to get things messy).

[thick lagoon]

I guess one idea is to pin a task to the CPU it is running on whenever you block on it. And I think this is needed, because otherwise this is a really big issue.

Short-time roadmap:

• bring up SMP
• write the really core scheduling code
• implement turnstile-or-similar based locking primitives, for now without priority inheritance

[thick lagoon]

the idea is to much later (when I do have a kernel competent enough to measure the impact of this) revisit this thing

[thick lagoon]

hopefully all the items here can be completed in a few weeks

I have to consider that there are lots of IRL things going on too, uni starts in a few weeks and even before that there are lots of things going on.

[fallen whale]

do you mean pinning owner to the cpu where the waiter was?

[thick lagoon]

no

pin the lock owner to whatever runqueue it happens to be on

then "virtually migrate" to it (but migrate back when you unblock)

[thick lagoon]

except this gets very tricky when you consider that the task could in turn be blocking on someone else.

[thick lagoon]

migrating back is actually probably very undesirable unless you were previously pinned to a logical processor. reason: the lock was released on a CPU, let's acquire it on the same CPU where whatever resource it protects is probably in cache.

[fallen whale]

i think cpu affinities in some way can make all that even harder

because you can't proxy to cpu when it's not allowed by the thread's cpu affinity

[thick lagoon]

why not? if T1 pinned to CPU1 "fake migrates" to CPU2 where T2 is running, T1 won't actually ever run on CPU2.

[thick lagoon]

anyway this is also stuff for measurement. you mustn't forget that not migrating back, now all of T1's stuff is no longer hot in cache/TLB/etc.

[fallen whale]

what will happen on lock release ?

[thick lagoon]

idk

[fallen whale]

after you migrated the owner releases the lock

and i believe all that complicated locking in the kernel

this scheme is pretty weird tbh

[thick lagoon]

I guess T2 (lock owner) traverses the list of waiters and says to each of them "you're now blocked on T3 instead"

[thick lagoon]

indeed

[fallen whale]

do you know about size limits?

[thick lagoon]

priority inheritance (which is not intuitive at all unless you have some experience doing low-level concurrent programming) is much more intuitive than proxy execution

[thick lagoon]

Sounds reasonable

[thick lagoon]

Current status: today, I've written some frame code for SMP bringup, which will hopefully work with one or two more hours of work. After that, I will start working on CPU scheduling infrastructure.

[thick lagoon]

And we have our first signs of life!

[thick lagoon]

It was the "last" (I will probably be back some days for some minor details) day of my summer internship today which means that in the upcoming four days, I will have a lot more time to work on this 🥳

In five days, University stuff begins (not 'real' classes yet, but very good activities and some semi-optional introductory lectures to attend)

then I will probably have a bit less free time

[thick lagoon]

on Saturday I will most likely be hanging out with some classmates

so tomorrow, sunday and monday I am free basically the entire day

short time goal: schedule tasks before university stuff begins

[thick lagoon]

I now have an overengineered TSC synchronization routine

discord is drunk again and won't send my message

so I'll paste a screenshot instead

it barely fits on my monitor :-)

[loud canyon]

Ahhhhhh goto statement

[thick lagoon]

It actually makes the code cleaner to use a GOTO.

[loud canyon]

For this it definitely does make it cleaner

[thick lagoon]

And for a lot of other things as well :-)

If the control flow graph of all your GOTOs is acyclic, it is usually fine.

[thick lagoon]

I believe this is similar in a way to the Linux TSC warp check

the basic principle is this: we know that time doesn't go backwards. so let two CPUs repeatedly read the TSC in an ordered manner and check if time went backwards. each CPU spins on an atomic variable set by the other CPU to indicate whose turn it is. when a delta is detected, the "control" CPU doesn't do anything, but the "target" CPU applies this delta to its own TSC readings later when getting the current time.

It's quite fun to do this, because I can actually observe the effects of prescheduling. The only difference between rdtsc() and rdtsc_ordered() is that the latter issues LFENCE as the instruction before reading the TSC. And yet, switching out rdtsc_ordered() for rdtsc() results in a non-zero delta in a system where the TSC is synchronized at boot.

'prescheduling' wtf nooo terminology I learned at work has started slipping into my day-to-day use of the English language

TSC prefetching is what I meant

which I guess to some extent happens because of a kind of instruction prescheduling

[thick lagoon]

Oh, the joys of a non-locked KePrintf!

[thick lagoon]

ugh this is so goddamn ugly

[round cradle]

why? differing naming convention?

[thick lagoon]

no

the code feels super hacky

[round cradle]

https://github.com/iProgramMC/Boron/blob/master/boron/source/ke/amd64/tlbs.c here's mine if it makes you feel any better

[thick lagoon]

ok this is even hackier

so... you acquire a spinlock on CPU1, then you release it on CPU2 in the interrupt handler, then you acquire it on CPU1 again

well if it works, it works

also yours probably scales better than mine, since mine issues an IPI to each processor individually

[round cradle]

it works for me but it's VERY clunky

because there can only be one (1) TLB shootdown request active at once

period

so it's not very scalable at all

[thick lagoon]

I am atleast using cool atomic hacks to enqueue and dequeue the TLB_DATAs

[round cradle]

ah, thats fun

[round cradle]

funnily enough the original version from 2023 was also implemented in the HAL https://github.com/iProgramMC/Boron/commit/be3b79a2bc22347c4e135e2c2700c5149e91d1ee

[lucid abyss]

no intel syntax?

[thick lagoon]

no

why would I use Intel syntax?

it's ugly af

[lucid abyss]

unpopular opinion

[thick lagoon]

[round cradle]

it is ugly af....... to use it when the rest of the generated assembly is in att syntax

but i think att syntax is uglier in general

[thick lagoon]

whatever

[round cradle]

it does have one advantage which is that at a glance you know that movl %a, %b moves from a to b

[thick lagoon]

people are allowed to have their own opinions on subjects like this :-)

[round cradle]

you dont have to think like in C

[lucid abyss]

I prefer the memcpy style

[thick lagoon]

let's... not hijack my project thread to discuss Intel vs. AT&T syntax.

I had an interesting idea a while ago... if I'm disciplined and don't put any structs for mutex waiting etc. on the stack of the calling thread, is it possible to keep all the kernel stacks in the same virtual address range, and do an "atomic" update of cr3 and rsp when context switching?

This is probably the most cursed idea ever

[thick lagoon]

I'm not going to do this

instead I will try to implement 'proper' SMP function call infrastructure and use it instead

[thick lagoon]

actually no I will not do that

'proper' SMP function call infrastructure means blocking on completions etc., which I have not implemented yet

and I really don't want my TLB flushing to depend on that

[thick lagoon]

we have successfully flushed the TLB on each CPU in SMP!

static void flush_tlb_on_all_cpus(TLB_DATA *tlb)
{
    tlb_flush_lock.lock();
    tlb_flush_data = tlb;
    tlb_flush_nrcpus = 0;

    unsigned int nr_ipi = 0;
    unsigned int self = HalCurrentProcessor();
    for (unsigned int cpu = 0; cpu < keProcessorCount; cpu++) {
        if (cpu == self || !KeCPUOnline(cpu))
            continue;
        apic_send_IPI(
            APIC_DM_FIXED | IRQ_VECTOR_TLBFLUSH,
            halCpuToApic[cpu]
        );
        nr_ipi++;
    }
    do_flush_tlb(tlb);
    while (atomic_load_relaxed(&tlb_flush_nrcpus) != nr_ipi)
        barrier();
    tlb_flush_lock.unlock();
}

void HalEndTLB(TLB_DATA *tlb)
{
    if (tlb->num_pages_to_flush == 0 && tlb->page_table_pages.empty())
        return;

    flush_tlb_on_all_cpus(tlb);

    MMPFN *pfn;
    while ((pfn = tlb->page_table_pages.pop_front()))
        MmFreePage(pfn);
}

void HalHandleTLBFlushIPI(void)
{
    do_flush_tlb(tlb_flush_data);
    atomic_inc_fetch(&tlb_flush_nrcpus, _MO_Release);
}

alright, now it is time to write the really core scheduling code

I'm going to use a struct KTHREAD and a struct ETHREAD (which has a KTHREAD as its first member).

struct KTHREAD { /* ... */ };
struct ETHREAD {
        KTHREAD kthread;
};

The plan is that stuff that Ke needs to know goes into KTHREAD, and mostly everything else into ETHREAD.

[worn wolf]

Have a global log queue, try to lock in your print and if you acquire log everything in the queue, otherwise add your message to the queue

It works pretty well

[thick lagoon]

Yeah I'm going to implement some sort of log ringbuffer eventually

[vital siren]

in case youre looking at other ppls ipis https://github.com/xrarch/mintia2/blob/main/OS/Executive/Ke/KeMpInterrupt.jkl

[loud canyon]

This type of code will always be messy unfortunately

[thick lagoon]

Thanks, yeah I was planning on doing something like this where there is a static buffer of SMP call queue entries and you can allocate from there, blocking if none are free. I didn't do this for now because that requires a scheduler, which is something that I don't have (yet).

[loud canyon]

Very nice stuff

[thick lagoon]

not really but it works

@vital siren you couldn't just make a KeDecrementUlong?

[vital siren]

well i just spin if none are free

theres 8 of them and i only support up to 8 processors on my fake computer anyway so it can never actually run out

[thick lagoon]

:-)

[thick lagoon]

this is O(ncpus^2) for ncpus processors if you want to guarantee never running out, isn't it?

[vital siren]

well allocating a slot is O(1) cuz i just use find-first-zero in a bitmap

[thick lagoon]

(ncpus sender table entries, each with ncpus bits)

yeah but O(ncpus^2) static buffer space

[vital siren]

also i dont think you need to guarantee never running out

[thick lagoon]

no, you definitely don't

[vital siren]

you only run out when N processors are simultaneously sending a synchronous IPI

theres also async IPIs where you shoot it off and just continue and then you dont need a sender table entry

for example when you notify a remote processor that its current thread has been preempted

and those are more common usually

[thick lagoon]

yeah

I pretty much made TLB invalidation an "async" IPI that increments a shared integer which the issuer then spins on.

(so not true async)

[vital siren]

also you can do a funny thing where if a core is idle you can do shootdowns as async ipis

you just atomically set a bit telling it to invalidate its tlb next time it becomes non-idle

and carry on

well, to be exact, it performs the shootdown next time it receives an interrupt (in my implementation) because the tlb invalidation could affect a page used by an ISR (like an MDL mapping)

[thick lagoon]

well, if I were to do this, I would consider taking an interrupt as leaving idle context

[thick lagoon]

(this also fits in really well with how I plan on handling RCU for idle cores)

https://github.com/dbstream/davix/blob/94d83f6a7679d94f4487ee48eb017073e3027b4a/kernel/sched/idle.cc this is the pre-NT larp-rewrite idle task.

note the rcu_disable() and rcu_enable() calls -- these could just as well be replaced by more general enter_cpu_idle() and exit_cpu_idle() calls.

[thick lagoon]

lol I accidentally wrote "leaving IRQ context" instead of "leaving idle context"

-_-

[torn nova]

entering GDT context... OK

[thick lagoon]

[thick lagoon]

Here's a neat scheduler trick:

• DPCs and preemption are kept as two separate things (although preemption is set pending in DPC context so masking DPCs also masks preemption).
• Timeslice expiration is handled by a KTIMER. In KTIMER (DPC) context, lock the KSCHEDULER, set KSCHEDULER::next_thread to a runnable thread, unlock the KSCHEDULER, set pending preemption.
• When KeReschedule is called, lock the KSCHEDULER and load next_thread. If next_thread is NULL look at the current task state. If it is KTHREAD_RUNNABLE, return without context switching. Otherwise, select another KTHREAD, using the idle task if needed.
  Since RCU depends on scheduler activity (namely, QS is in KeReschedule), we might want to force a preemption event on a remote processor without necessarily actually rescheduling. This lets us do so in a really simple and efficient way: send a preemption IPI to the target processor without setting KSCHEDULER::next_thread.

[thick lagoon]

did not post yet today (actually yesterday 😆) but the scheduler is slowly but surely taking form. I'm opting for a design where low priorities are scheduled in a way similar to Linux' old CFS scheduler, where each task keeps track of a "virtual runtime", which is the runtime of the task scaled by some factor depending on priority (higher prio == lower scale factor, meaning that higher priority tasks get longer timeslices). The highest priority is reserved for realtime threads, which never preempt eachother. This means that a KSCHEDULER has two containers for runnable threads:

• dsl::TypedList<KTHREAD, &KTHREAD::rq_realtime> realtime_tasks;
• dsl::TypedAVLTree<KTHREAD, &KTHREAD::rq_cfs, VRuntimeComparator> cfs_tasks;

[thick lagoon]

First try!

(Not even joking, this was actually first try -- I didn't expect it to work at all)

There is not yet any load balancing at all, but I do have the beginnings of a relatively competent scheduler.

[thick lagoon]

We do love our mega commits with over 1500 lines added

[torn nova]

how is NT larp working out for you?

[thick lagoon]

stuff is progressing at a calm and controlled pace

[thick lagoon]

I shall update this post

[torn nova]

i forgor if u were doing nt compat or just larp

[thick lagoon]

NT compat is just not something that I believe is realistic to aim for

it's just NT larp

I am going to build some sort of POSIX like interface in userspace, maybe the user<->kernel boundary will look a bit "interesting" (I have not decided yet on how I want to do everything)

[torn nova]

interesting

[thick lagoon]

I read (one of, idk if there are more but it's the one which I saw linked in this discord sometime) @feral snow's paper(s) on Managarm and I kinda want to use some sort of submission/completion ring instead of doing things like epoll (and then implement epoll on top of that)

(oops sorry for ping)

[torn nova]

cool

[thick lagoon]

this is the scheduler's first task switch (see the "Hello from init thread!" message)

it's actually believable that it worked first try

there are like 999 things that could've gone wrong

There's a funny scheduler meme where a thread can wake up itself. In short,

T0
KeSetCurrentState(KTHREAD_INTERRUPTIBLE);
->DPC arrives, signals the thread
  KeWakeThread(T0); // T0 is still running at this point!
KeReschedule();
T1 (or idle thread)
 KiFinalizeContextSwitch(T0)
 sees pending wakeup
 immediately switches back to T0

(relatively) short-term TODO list:

1. (done) write a scheduler 'torture test' - something simple which spawns N (e.g. 100) threads consisting of a loop doing nothing.
   (1.5. (done) fix the bugs that are revealed.)
2. (skipped) **implement some sort of event tracing utility that lets me save the scheduler's decisions for offline analysis.
3. (done) implement task wakeup on remote processors. I have most of the infrastructure for this already; I just need to wire up two IPIs to do this.
   (3.5. (done) fix the bugs that are revealed.)
4. begin working on blocking primitives, such as the Turnstile.

[thick lagoon]

perhaps even shorter-term: shoot down other cores in a panic situation! 🔫

[thick lagoon]

I am imagining a global append-only buffer for tracing, probably with some binary format... I'm probably going to end up writing a DSL (domain-specific language, not datastructure library or Davix support library) that generates "bindings" like void trace_context_switch(KTHREAD *from, KTHREAD *to); that call into some generic routine like __trace_append(uint32_t id, uint32_t num_bytes, const void *bytes); and routines for parsing the binary format that this 'event log' becomes.

[digital hawk]

have a look at boron's fireworks test, it does use the heap a bit too but you can work around (I made the firework-data struct refcounted and the explodable thread sleeps until the refcount is 0, aka all particles are done).

ah I should have read the full message first, you dont have blocking yet

[thick lagoon]

I do know of the fireworks test, in fact I used it before.

very useful