davix operating system kernel

[fathom lake]

https://0x04.net/doc/elf/tls.pdf

ok i see how to make this thing maybe work in zig tbh. might experiment later idk

[thick lagoon]

ok so I'm going to write two functions read__seg_gs (T *ptr); and write__seg_gs (T *ptr, T value);, and these will be used to access CPU-local variables, with inline asm if sizeof (T) is one of 1, 2, 4, or 8, and by adding the percpu offset to the pointer if it is not

hm... can I do __builtin_constant_p memes to ensure that the value is read as an immediate, i.e. movq %gs:myvar(%rip), %rax, if it is known at compile-time?

actually I can probably do something like this:

template<class T>
static inline T
read__seg_gs (T *ptr)
{
        T value;
        if constexpr (sizeof (T) == 1) {
                asm volatile ("movb %%gs:%1, %0" : "=r" (value) : "m" (*ptr));
        } else if constexpr (sizeof (T) == 2) {
                ...
        } else ...
}

so "dereference" the pointer in the input specification of the asm statement, and then force it to be a memory operand

I probably also need the : "memory" clobber

[worn wolf]

if you're storing the percpu base pointer in gs you can just load that and memcpy at the correct offset

[thick lagoon]

but muh efficiency

[worn wolf]

assuming you pack everything into a .cpulocal section you can take the begin and end pointers and do arithmetic from that

if you reinterpret_cast the bytes to the type you intend to write to you may even get better optimization

and correct behaviour with constructors which i feel might be the more important bit

[thick lagoon]

ok now it's time to see if this works

LGTM

[worn wolf]

i hope thats an automated test you can run easily

[thick lagoon]

Initializing percpu variables... SUCCESS

time to write a printf implementation

I have the old printf, obviously, that I can use as reference

[worn wolf]

steal stb_sprintf tbh

[thick lagoon]

but it is kinda shitty

stb_sprintf is a 1000 lines of code single function monstrosity

[worn wolf]

yeah thats just how printf goes when you support all the specifiers

[thick lagoon]

nahh I'm doing my own thing

(I'm going to support everything standard except floating point stuff and wide characters)

[worn wolf]

#define STB_SPRINTF_NOFLOAT

[weary prairie]

what the fuck is a movb $0x1,%gs:0x7ffe777b(%rip)

[thick lagoon]

a one-byte store of the integer constant 1 to GSBASE + &pcpu_c

perfectly reasonable stuff

[worn wolf]

at&t syntax makes rip relative stuff look so fucked lol

[thick lagoon]

not really tbh

[weary prairie]

i have never seen rip relative addressing with gs

this seems so cursed

[meager sequoia]

looks perfectly normal to me

[thick lagoon]

(hopefully)

[meager sequoia]

it's a great way to allow cpu local stuff to just be declared as "normal" variables

put them in a special section, and make gsbase point to the offset from that section where the real cpu local stuff can be found

[worn wolf]

i do wish lea worked with gs and fs

[swift pebble]

why should it not be a thing?

you can use any valid addressing mode + a segment override prefix

[fathom lake]

same

[weary prairie]

i know its a thing

i have just never seen it

and it feels cursed lol

[thick lagoon]

Initializing full-day competitive programming session... OK

(I am not going to do any work on davix today)

[thick lagoon]

oh god these problems are difficult

(I cannot post them here because that is against competition rules, so don't ask)

[thick lagoon]

competitive programming be like

[thick lagoon]

Giving up... OK

[torn linden]

what competition ?

[thick lagoon]

a local thing

[torn linden]

okay

[thick lagoon]

well today I will be spending some time prepping my school laptop for an upcoming CTF next weekend :^)

so most likely little or no osdev today :^(

yay, \LaTeX

(taking ages, as per usual)

[thick lagoon]

ok, I have done some work on IRQLs in the rewrite (I will be making sure there is a damn good foundation to build the rest of the kernel upon this time around). here are some of the interesting bits:

static inline irql_t
current_irql (void)
{
    return __read_irql () & __IRQL_LEVEL_MASK;
}

static inline irql_t
__raise_irql (irql_t target, irql_t source)
{
    __add_irql (target - source);
    return source;
}

static inline irql_t
raise_irql (irql_t target)
{
    return __raise_irql (target, current_irql ());
}

static inline void
__lower_irql (irql_t target, irql_t source)
{
    irql_t pending = __xadd_irql (target - source) & __IRQL_PENDING_MASK;
    if (pending > source) [[unlikely]] {
        irql_dispatch_pending (target | pending);
    }
}

static inline void
lower_irql (irql_t target)
{
    irql_t irql = current_irql ();
    if (irql != target)
        __lower_irql (target, irql);
}

wth my discord is having skill issues

(I am trying to paste some more code, but discord isn't letting me.)

rough translation: "your message could not be delivered. this is usually because you do not share a server with the recipient or the recipient only accepts DMs from friends. you can see the full list of reasons here: <link>"

wtf

ok I'm going to binary-search over this message to find the portion that discord doesn't like

/**
 * irql_dispatch_pending - Dispatch pending IRQL events.
 * @current: current raw IRQL flags
 */
void
irql_dispatch_pending (irql_t current)
{
    irql_t tmp, irql = current & __IRQL_LEVEL_MASK;
    if (irql >= IRQL_HIGH)
        return;

    /**
     * If an external interrupt occurs while we are at IRQL_HIGH, it sets
     * __IRQL_IRQ_PENDING and returns with local interrupts disabled.  We
     * must first call the interrupt handler, then reenable interrupts.
     */
    if (current & __IRQL_IRQ_PENDING) {
        /**
         * Handle the case where handle_irq causes another IRQ to become
         * pending, despite interrupts not being enabled - this should
         * never happen.
         */
        current &= ~__IRQL_IRQ_PENDING;
        do {
            __write_irql (current | IRQL_HIGH);
            handle_irq (percpu_ptr (pending_irq_vector).read ());
            tmp = __read_irql ();
        } while (tmp & __IRQL_IRQ_PENDING);
        current |= tmp & __IRQL_PENDING_MASK;
        __write_irql (current);
        raw_irq_enable ();
    }

    if (irql >= IRQL_DISPATCH)
        return;

    if (current & __IRQL_DPC_PENDING) {
        /**
         * Additional DPCs may be enqueued while we are at DISPATCH
         * level.  Therefore we must use xadd to restore the IRQL.
         */
        do {
            tmp = current & __IRQL_LEVEL_MASK;
            __add_irql (IRQL_DISPATCH - tmp - __IRQL_DPC_PENDING);
            dispatch_dpcs ();
            tmp = __xadd_irql (tmp - IRQL_DISPATCH);
        } while (tmp & __IRQL_DPC_PENDING);
        current |= tmp & __IRQL_PENDING_MASK;
    }

    if (irql >= IRQL_APC)
        return;

    if (current & __IRQL_APC_PENDING) {
        /**
         * See comment in __IRQL_DPC_PENDING block above.
         */
        do {
            tmp = current & __IRQL_LEVEL_MASK;
            __add_irql (IRQL_APC - tmp - __IRQL_APC_PENDING);
            dispatch_apcs ();
            tmp = __xadd_irql (tmp - IRQL_APC);
        } while (tmp & __IRQL_APC_PENDING);
    }
}

anyway this is all one big function that handles the case for lower_irql where there are pending events and we need to dispatch them

as is hinted in the __IRQL_IRQ_PENDING block, I am going to do lazy interrupt masking

[thick lagoon]

doing IRQL stuff before I even have basic memory services and interrupt handlers in the rewrite... 🫠

[thick lagoon]

zero progress on the rewrite today... womp womp

[worn wolf]

such is life

[thick lagoon]

indeed.

on one hand, I can't osdev because I am preoccupied with other stuff.

on the other hand, that other stuff is really fun

[broken axle]

What else is there to do david..

[thick lagoon]

definitely not travelling for the finals of a CTF competition that you will also participate in.

[thick lagoon]

ok so I'm at a point where I want to get the basic memory services (struct page, alloc_page, free_page) going in the rewrite, but that requires dealing with the piece of shit that is the multiboot2 (lack of a well-designed) memory map. I'll probably just "steal" the old initmem initmeme, maybe rewrite it to be a bit more idiomatic for the rewrite, and leave it at that. But I won't do it now, because I'm a bit exhausted after a lot of things that have occupied me basically this entire week (mainly competitive programming and finishing writing the discussion part of a really important school thing that needs to be done tomorrow), and I won't do it this weekend, because yeah...

the old kernel was like "setup initmem → start half the kernel subsystems → setup the actual page allocator → start the rest of the kernel subsystems". In the rewrite I will try to do it more like "setup the actual page allocator → start the entire kernel", so hopefully skipping the (painful) initmem

[thick lagoon]

AHHHHH FUUUU....

so... the rewrite... like, I kept it in a separate directory

and I pushed my code

and rmed that directory

except

it didn't push properly

welp.

no rewrite then, I guess

[thick lagoon]

what happened was I did git add . in a subdirectory

[thick lagoon]

I'm going to say some honest words. Osdev is a very interesting topic, and I've become a much better programmer by dabbling in it. However, succeeding at some things in programming requires some level of maturity. And for osdev, I'm just not there yet. For that reason, (and lack of motivation since I just lost like a week worth of work,) you won't be seeing much more of me here for some time.

Initializing S4 sleep... OK

I'll be back.

[torn nova]

Did you git reset hard?

[torn nova]

At least not S5

💀

[thick lagoon]

.

[thick lagoon]

no... 😢

[thick lagoon]

yup. entering osdev hibernation. as I said,

I'll be back.

[torn nova]

That's unfortunate

[weary prairie]

i agree with this so much

i lack the "maturity" as well

and also lack any sort of discipline

so thats why i cant finish anything

[torn nova]

Thats like every hobby os

[digital hawk]

damn - gl with your next project, I'll be keen for davix 2.

[thick lagoon]

@lucid abyss somewhere here I describe how percpu variables can be done using a special section

also I can confirm (if it is not obvious) that I am so back in the game

[lucid abyss]

discord L can't search in a thread only

ah it's not so far up

[thick lagoon]

.

GCC in C++ mode doesn't support __seg_gs, which SUCKS

[thick lagoon]

workaround:

[lucid abyss]

I don't see where you use .percpu section

[thick lagoon]

it's hidden behind a macro

[lucid abyss]

so DEFINE_PERCPU just adds [[section(".percpu")]]

[thick lagoon]

__PERCPU expands to [[gnu::section (".percpu")]] iirc

[peak linden]

https://osdev.wiki/wiki/Section(".percpu")?action=edit&redlink=1

[lucid abyss]

ah

[thick lagoon]

bruh

[lucid abyss]

[[bruh]]

[peak linden]

https://osdev.wiki/wiki/Bruh?action=edit&redlink=1

[thick lagoon]

since I've redone per-CPU variables, because of... this...

but there was also something sketchy that I fixed iirc; this code is probably 90% trustworthy but worth checking a few extra times

[lucid abyss]

what if limine doesn't load the kernel at the address given by linker script?

if it's pie

__KERNEL_START would have the correct value set by the dynamic loader, wouldn't it?

[thick lagoon]

if you use Limine you probably cannot force the .percpu section to be at virtual address zero; Linux does it by basically applying the opposite of any rule for relocations that reference symbols in the .percpu section. I do it by not being (virtually) relocatable.

[thick lagoon]

the ldscript does __KERNEL_START = 0xffffffff80000000;

[lucid abyss]

yes, but aren't all addresses relocated

[thick lagoon]

(assuming you want a virtually relocatable kernel, that is)

[thick lagoon]

I don't relocate

[lucid abyss]

I'm forced to compile my kernel with pic

because of reasons

[thick lagoon]

you can do without forcing the percpu section to virtual zero

[lucid abyss]

I just subtract the load address at runtime?

[thick lagoon]

the reason I even do it is because it is nice to be able to write asm("addq %%gs:0, %0" : "+r" (foo));

[thick lagoon]

idk. If I wanted relocatability, I would place the .percpu section at virtual right next to your kernel (ie. no special handling other than instantiating it on other CPUs), because this makes it easier to reason about

think of it like this: a symbol at X will be accessed as X+load_offset, so the .percpu section at X will be accessed as GSBASE+X+load_offset

thus GSBASE=allocated memory-X-load_offset

[lucid abyss]

yes

[thick lagoon]

in my case, X is always zero and load_offset is always zero, which makes some things easier

[lucid abyss]

I have other things at gsbase

[thick lagoon]

ah.

yeah

well

the same idea applies

[lucid abyss]

well if I have this, I won't need those "other things" (percpu data)

[thick lagoon]

just s/GSBASE/(any other similar mechanism you may have or implement)

[lucid abyss]

what's this for btw

. = __percpu_virt_start + SIZEOF(.percpu);

isn't it at that address anyway?

[thick lagoon]

no, doing .percpu 0 : { /*...*/ } :percpu changes the address to 0

iirc

even if it doesn't, better safe than sorry

[lucid abyss]

ah

[thick lagoon]

and this

[lucid abyss]

lol

[lucid abyss]

I took some inspiration from managarm

it seems to work, but I'm not sure

@thick lagoon

bigplead

[fathom lake]

part of me keeps wanting to figure out doing this in zig at some point

but so far ive been sticking to declaring percpu things in the dedicated percpu struct instead

its a very neat setup

[weary prairie]

should be pretty easy with a fn PerCpu(comptime T: type) type that returns a wrapper that lets you access the variable per-cpu + var x: PerCpu(u32) linksection(".percpu") = undefined; that actually puts it in a dedicated section do you can bootstrap per-cpu data at runtime

[fathom lake]

yeah probs

just a thing id need to get around to trying

[lucid abyss]

well I modified my kernel to use it instead and I think it would break if something didn't work right

[digital hawk]

what you can do (and what I do) is leave the percpu section where the linker wants to put it, and then use gs_base/tp/whatever_arch_reg to store the offset of where the current core's percpu struct is.

also sad this thread wasnt opened for a davix resurrection

[lucid abyss]

that's what I do

[digital hawk]

ah nice

[lucid abyss]

#1326937732122935379 message

[digital hawk]

wow I apparently do not know how to read

[thick lagoon]

yay, HPET and TSC works! (mostly copied from the old kernel)

fixed a few bugs along the way too

[lucid abyss]

how do you handle hpet overflows?

[thick lagoon]

by "faking" a 64-bit counter

[lucid abyss]

especially for the 32 bit timer

[lucid abyss]

hm?

[thick lagoon]

I should make this next repo public

anyway this is the relevant code:

/**
 * Emulate a 64-bit HPET when the underlying hardware is 32-bit.  We do this by
 * tracking the last read "augmented" HPET value.  On a HPET timer read, we take
 * the bitwise union of the real HPET value and the high bits of hpet_last_read.
 * If time "went backwards", we increment hpet_last_read by 2^32.
 */
static uint64_t hpet_last_read;
constexpr uint64_t hpet_32bit_mask = 0xffffffffUL;

static uint64_t
hpet_read_counter (void)
{
        uint64_t value = hpet_read (HPET_MAIN_COUNTER);
        if (!hpet_is_32bit)
                return value;

        uint64_t last_read = atomic_load_relaxed (&hpet_last_read);
        value &= hpet_32bit_mask;
        value |= last_read & ~hpet_32bit_mask;

        if (value < last_read)
                /**
                 * Time went backwards, which means the HPET main counter rolled
                 * over.
                 */
                value += 1UL << 32;

        /**
         * We don't have to update hpet_last_read on _every_ read of the main
         * counter.  Do it when we are half the way to rolling over.
         */
        if (last_read - value > (hpet_32bit_mask >> 1))
                atomic_cmpxchg (&hpet_last_read, &last_read, value,
                                mo_relaxed, mo_relaxed);

        return value;
}

so basically, we keep a variable that stores the last read "augmented" counter value. we expect this to be ever increasing.

when we read from the 32-bit HPET, we take the upper 32 bits of the augmented counter and the lower 32 bits of the "real" (HPET) counter.

[lucid abyss]

do you just call that from a separate thread if hpet isn't being read from anywhere else?

[thick lagoon]

if this is less than the augmented counter, we wrapped around. thus, add 2^32 to it

[thick lagoon]

well in the rewrite, I don't have scheduling yet

but yes, that is basically how you would do it

or not necessarily in a thread

e.g. in the local APIC timer interrupt, it can be done.

[thick lagoon]

Do I just call it davix2 lol?

[meager sequoia]

i just have orphan branches for each rewrite

[lucid abyss]

davixer

[meager sequoia]

main, rewrite, rewrite2

[lucid abyss]

then rename rewrite to main and main to old

[pastel rivet]

then the 3rd rewrite is davixest

[thick lagoon]

yeah, I'm going to do this probably

[meager sequoia]

i (plan to) do that when rewrite is more capable than main

[thick lagoon]

alright so how do I take all the commits from one repository (davix-next) and move them into an orphan branch in another repository (davix)?

[meager sequoia]

idk how to do it while preserving the history from another repo but there's git checkout --orphan

[thick lagoon]

some git remote shenanigans maybe

[meager sequoia]

apparently git push <repo url> refs/heads/<branch name> works? but i haven't tried that

[pastel rivet]

git remote add foo <url> && git push foo master:rewrite?

git push foo master:rewrite means push local branch master to remote foo branch rewrite

[thick lagoon]

yup

[torn nova]

What if you miss two overflows

[thick lagoon]

broken CPU

[thick lagoon]

anyway I have done this now

https://github.com/dbstream/davix.git

davix-old has the old kernel

master has the new kernel

[cerulean swift]

thats kinda a shit way of reading the 64 bit count tbh

ah wait

its a 32 bit hpet

ah yeah okay makes sense

[fathom lake]

reminds me of how the acpi timer has an entire event that you can listen to for when the timer overflows lol

[thick lagoon]

if (!hpet_is_32bit) return value; -_-

[torn nova]

Does hpet generate and irq on overflow?

[thick lagoon]

no

well I guess it is possible to configure one of the comparators to interrupt you the moment before overflow

but it is more trouble than it is worth

with a HPET period of 100000fs (femtoseconds)=0.1ns, you overflow once every approx. 0.5s with a 32-bit HPET

[meager sequoia]

when you put a comparator in 32 bit non-periodic mode, it'll generate an interrupt on overflow

[thick lagoon]

and anything less than that is just unreasonable

because (hopefully) your scheduler is running, the timer should be read more often than this

[worn wolf]

the hpet is basically unused these days anyway lol so who cares

[thick lagoon]

if the timer is HPET, problem solved. if the timer is TSC, there was no problem to start with.

[meager sequoia]

But what if there's only one running task on the core, it's pinned to said core, and it's SCHED_FIFO?

[thick lagoon]

f u and run the timer interrupt anyway

[meager sequoia]

Oh and it just runs an infinite loop

Fair enough

[thick lagoon]

there's not really a better solution than this that I'm aware of.

[meager sequoia]

A better solution imo is just not allowing the hpet to be used as a system timer (aka only use it as a calibration source)

[thick lagoon]

so jiffies if no TSC?

[worn wolf]

linux uses the hpet as the timer of last resort

[meager sequoia]

more like if no tsc fuck you

[worn wolf]

and even then i think it refuses to use it for some stuff

[thick lagoon]

yeah

Linux prefers to calibrate the TSC against PIT

[meager sequoia]

hydrogen inits hpet, kvmclock, tsc in that order and uses the latest one that init'd successfully

[meager sequoia]

why? reading it is much more cumbersome and it only has a 1-microsecond resolution

and the only way to detect it is probing

[thick lagoon]

idk

[thick lagoon]

Linux disagrees

[meager sequoia]

how do they 'detect' it?

[thick lagoon]

well they actually calibrate against both the PIT and the (HPET or PMTIMER) later in boot lmao

[thick lagoon]

iirc it's based on the presence of a legacy PIC, I think.

[meager sequoia]

that's not really detection imo but fair enough

it's theoretically possible to have a pit but no pic, or a pic but no pit

[thick lagoon]

yeah

IMO they overcomplicate it

[worn wolf]

if its good enough for linux its good enough for everyone else (because as long as linux boots on it hardware vendors will sell it)

[thick lagoon]

my TSC calibration code consistently measures my 4.2GHz CPU as 4200.000 +- 0.02 MHz

with a 50ms wait and the HPET as reference timer, that is

[thick lagoon]

and this is a very good measurement

[meager sequoia]

is that in qemu? if so, tcg or kvm?

[thick lagoon]

kvm

[meager sequoia]

hm

[worn wolf]

my timer training is all over the place on tcg lol

+-0.1ghz precision

damn near 0 deviation on kvm though

[thick lagoon]

well tcg is unreliable in that aspect

[meager sequoia]

i consistently get 3792.73 +- 0.02 MHz, but my host kernel thinks it's 3792.874 MHz

on kvm that is

[thick lagoon]

does that change if you reboot?

(your host kernel's measurement)

[meager sequoia]

one second

[worn wolf]

i just round to the nearest number that looks right

1.025ghz is probably a 1ghz cpu

[thick lagoon]

or a 1.025GHz CPU

and now you are banned from any online video games with anticheats for trying to move too fast

[meager sequoia]

not really, it's 3792.873 now but that's expected deviation

[thick lagoon]

yeah

[meager sequoia]

and this is with a 500ms hpet calibration

[thick lagoon]

so Linux does two TSC calibrations: one short, 50ms or so, early in boot, and one "long" (500ms iirc) later. the early one tends to fluctuate more

[meager sequoia]

on bare metal my kernel's measurement is 3792.865 MHz +- 0.001 MHz

[meager sequoia]

yeah I'm looking at the refined one

[thick lagoon]

yeah

[thick lagoon]

over what time period?

[meager sequoia]

500ms

[thick lagoon]

how do you read the TSC and the reference timer when calibrating?

[meager sequoia]

this is the relevant code ```c
#define CALIBRATE_MS 500
#define CALIBRATE_FS (CALIBRATE_MS * 1000000000000)

typedef struct {
uint64_t tsc;
uint64_t apic;
uint64_t hpet;
} timer_data_t;

attribute((noinline)) static void read_timer_data(timer_data_t *out) {
out->tsc = read_time();
out->apic = lapic_timcal_read();
out->hpet = read_hpet();
}

static uint64_t get_elapsed_hpet(timer_data_t *from, timer_data_t *to) {
uint64_t end = to->hpet;
if (end < from->hpet) end += 0x100000000;
return end - from->hpet;
}

static uint64_t get_frequency(uint64_t ticks, uint64_t elapsed) {
__uint128_t temp = (__uint128_t)1000000000000000 * ticks + (elapsed / 2);
div128(&temp, elapsed);
return temp;
}

static void calibrate_tsc(void) {
uint64_t hpet_ticks = (CALIBRATE_FS + (hpet_period_fs / 2)) / hpet_period_fs;

irq_state_t state = save_disable_irq();

timer_data_t start, end;
lapic_timcal_start();
read_timer_data(&start);

do {
    read_timer_data(&end);
} while (get_elapsed_hpet(&start, &end) < hpet_ticks);

restore_irq(state);

uint64_t elapsed = get_elapsed_hpet(&start, &end) * hpet_period_fs;
tsc_freq = get_frequency(end.tsc - start.tsc, elapsed);
lapic_freq = get_frequency(end.apic - start.apic, elapsed);

}```

[thick lagoon]

(see read_tsc_ref in arch/x86/kernel/time.cc for how I do it)

[meager sequoia]

i should probably move that restore_irq down

[thick lagoon]

ahh, you calibrate the local APIC at the same time

[meager sequoia]

i have two things to calibrate, might as well do them at the same time

[thick lagoon]

yeah

well I'm going to calibrate the APIC against ns_since_boot, which is the TSC calibrated against HPET, mostly because it is easy to do it like this

and it also doesn't really matter, as scheduling decisions will not be made based on when the timer interrupt arrives

[meager sequoia]

i'm curious, why not do hpet twice and tsc once? with this you're basically relying on the tsc frequency not being too high, while with hpet twice you can use a constant x microseconds as threshold

[thick lagoon]

(and timer oneshot mode, and TSC deadline)

[thick lagoon]

because HPET is slower to read

[meager sequoia]

i mean yeah but not slow enough that hpet reading latency is indistinguishable from nmi/smi right

[thick lagoon]

idk, I haven't measured

but probably no

[meager sequoia]

but the stable measurement thing is a good idea i think i'll adopt that

[thick lagoon]

come to me and complain when Davix doesn't work on your 100THz CPU then

[meager sequoia]

fair enough

[lucid abyss]

lmao

[thick lagoon]

and also because arch/x86/kernel/time.cc already contains setup code for both the HPET and TSC and I am opposed to further spaghettifying it

[torn nova]

https://elixir.bootlin.com/linux/v6.14.4/source/arch/x86/kernel/i8253.c#L24

basically its assumed to exist if some conditions are met or not met

[meager sequoia]

i dislike that

[torn nova]

who doesnt

[meager sequoia]

but i guess it does work since it's in linux

[torn nova]

i mean It would be possible to enable the clock but the registers are chipset specific and not discoverable. Avoid the whack a mole game.

is fair enough

how else do u handle it

[meager sequoia]

just don't support it in the first place

[torn nova]

apic_needs_pit() will return false for probably all semi modern cpus i think

https://elixir.bootlin.com/linux/v6.14.4/source/arch/x86/kernel/apic/apic.c#L788

kinda interesting

[thick lagoon]

wrong

on my computer, Linux calibrates the TSC against the PIT

[torn nova]

i mean whats your kernel version

[thick lagoon]

(AMD Ryzen 9 7950X3D, B650 chipset)

[thick lagoon]

6.14.something

AKA recent

[torn nova]

really

[meager sequoia]

mine does this too, and i'm on 6.14.4

but i believe the tsc calibration code uses a different check?

[torn nova]

probably not the best idea to run on the bleeding edge kernel

[meager sequoia]

i'm on arch

it's just the regular linux package

and i don't encounter any issues so who cares

[torn nova]

yeah

[thick lagoon]

"don't break userspace" so I don't think it is that dangerous

[torn nova]

arch packages are always bleeding edge

[torn nova]

i meant more like hangs, crashes inthe kernel lol

because you're basically the beta tester

[thick lagoon]

also one of the core kernel maintainers has said that there is very seldom a reason not to upgrade the kernel

[torn nova]

does it report the tsc frequency in cpuid?

[thick lagoon]

no

it's AMD

[torn nova]

maybe thats why

[thick lagoon]

also it seems to lack TSC_DEADLINE

[torn nova]

wait what

[thick lagoon]

yup

[meager sequoia]

yeah amd doesn't have the tsc freq cpuid stuff, and doesn't have tsc deadline

[thick lagoon]

no TSC_DEADLINE on AMD it seems

[meager sequoia]

well i think they might have tsc deadline in some server stuff and maybe one of the 9xxx consumer ones? but it's very recent

[torn nova]

does that mean lapic cannot use tsc?

[meager sequoia]

correct

[torn nova]

will check on my 9950x3d soon

[torn nova]

sad

[thick lagoon]

[torn nova]

well am5 motherboards arent disabling PIT any time soon then

[thick lagoon]

probably not later motherboards either lol

[meager sequoia]

the april 2024 version of the amd manual lists the tsc deadline cpuid bit as reserved

so i don't think anything has it

[torn nova]

mint's motherboard without pit is definitely a newer intel board

and it definitely has a cpuid for tsc freq

[thick lagoon]

but it has HPET?

[torn nova]

of course

and its 64-bit unlike amd

[thick lagoon]

??

[meager sequoia]

yeah amd hpets are 32 bit

[thick lagoon]

wtf

I will look into that on my machine I guess

[torn nova]

just /sys/firmware/acpi/tables/hpet

[meager sequoia]

also fun fact: apparently on intel processors you need to issue mfence; lfence before accessing x2apic or tsc_deadline msrs

[thick lagoon]

luckily 32-bit HPETs aren't a problem for me

[meager sequoia]

i wonder how many kernels here actually do that, proxima certainly doesn't

[thick lagoon]

wtf

where is that documented?

[torn nova]

i meant isnt that expected

because out of order execution and stuff

your tsc read might be way behind

[meager sequoia]

the linux kernel mailing list

[torn nova]

although depends which x2apic msrs u mean

[meager sequoia]

i'm trying to find it in the sdm rn

[torn nova]

but for rdtsc proxima does do lfence right

[meager sequoia]

rdtsc yeah but not x2apic/tsc deadline

[torn nova]

or just mfence

[torn nova]

ah ok

[meager sequoia]

also you need both mfence and lfence, for tsc you just need lfence

actually i don't think old proxima does any fence for tsc

[torn nova]

why is a load barrier enough

your counter can still be behind no?

[meager sequoia]

it's what linux does iirc, i forgot the exact reason

[torn nova]

hm ok

[meager sequoia]

11.12.3 MSR Access in x2APIC Mode

To allow for efficient access to the APIC registers in x2APIC mode, the serializing semantics of WRMSR are relaxed when writing to the APIC registers. Thus, system software should not use “WRMSR to APIC registers in x2APIC mode” as a serializing instruction. Read and write accesses to the APIC registers will occur in program order. A WRMSR to an APIC register may complete before all preceding stores are globally visible; software can prevent this by inserting a serializing instruction or the sequence MFENCE;LFENCE before the WRMSR

can't find it for tsc deadline but intel guy said it on lkml so it's probably correct

[torn nova]

thats interesting

[meager sequoia]

to quote linux:

[...] empirically an RDTSC instruction can be speculatively executed before prior loads. An RDTSC immediately after an appropriate barrier appears to be ordered as a normal load, that is, it provides the same ordering guarantees as reading from a global memory location that some other imaginary CPU is updating continuously with a time stamp.

[meager sequoia]

ah found it, Volume 2 Chapter 6.1 Instructions (W-Z) - WRMSR—Write to Model Specific Register

The WRMSR instruction is a serializing instruction (see “Serializing Instructions” in Chapter 9 of the Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A). Note that WRMSR to the IA32_TSC_DEADLINE MSR (MSR index 6E0H) and the X2APIC MSRs (MSR indices 802H to 83FH) are not serializing.

[torn nova]

ill pretend to understand

[weary prairie]

i run 6.14.x on fedora 42 on my m1 mac too

and i wouldn't say fedora 42 is bleeding edge

mainline would be bleeding edge

[torn nova]

nah i mean its probably fine

but a 5.15 stable 9999999 is probably safer

not that it matters for desktop

[thick lagoon]

I was writing some kernel command-line parsing code so that I can make printk to 0xe9 enablement configurable at boot in order to be able to test on real hardware. Then power went out.

lots of "clearing orphaned inode"

nah we good, I didn't lose anything important

[torn nova]

in(0xE9) == 0xE9 is enough to test

[thick lagoon]

yeah, I will probably make it something like this:

if ("console=0xe9" in cmdline) {
        if (0xe9 == inb (0xe9)) {
                console_register (&debugcon);
        }
}

[torn nova]

Ye

[worn wolf]

man you need to be comitting to git more often lmao

dont let it happen again

[thick lagoon]

well I didn't lose anything

all that ctrl-S spamming

[weary prairie]

i mean, it's not like the page was written to disk immediately after pressing ctrl+s

but i'm sure that helped

[thick lagoon]

• i write code
• i hit C-s
• 1 sec later, power goes out
• the code i wrote is still there

w

[inland cairn]

I honestly can't imagine not having autosave

[thick lagoon]

time to lock in for a 3h competitive programming session

[torn linden]

good luck

[thick lagoon]

we're cooking

[torn linden]

how many participant ?

[thick lagoon]

70 80 something, but probably like half of them have not solved more than like two or three problems

and I'm also not #5 anymore

I am have math skill issue

[thick lagoon]

a problem I failed to solve boils down to the following: You are given a list of N weighted coins, where each coin has a probability P_i \in { 0.01, 0.02, ..., 0.98, 0.99 } (AKA integral percentages distinct from 0% and 100%) of flipping heads. For each k \in { 0 ... N }, output the probability that exactly k coins flip heads.

(N ~ 400000 = pretty big)

[thick lagoon]

ah, and any answer with absolute difference to the judge solution of no more than 10^-6 is accepted

so the idea I have is the following:

• we start by realising that there are only 99 distinct probabilities in play, 1% through 99% (0.01 through 0.99). thus we can store the number of coins with probability x% of flipping heads in an array
• now, swing our dynamic programming wands and construct a table dp[N][100], where dp[i][j] is the probability of flipping at least i heads, considering only the coins with probability less than or equal to j% of flipping heads

[loud canyon]

I have a function that does that kinda

I made a library for probabilistic programming

[thick lagoon]

I doubt that it can deal with 400000 coins

so the intended solution uses the fast fourier transform

[loud canyon]

Yeah definitely not

[loud canyon]

Mine uses recurrence relation of the Poisson binomial distribution

So

Slower

Also

Nice project

Check out #1305395406662012928

:)

[thick lagoon]

another problem was to calculate the total length of a euclidean minimum spanning tree in two dimensions

which

there are relatively fast algorithms for that

[loud canyon]

Isn’t there Delaunay transformation

[thick lagoon]

I should've just C-c C-v:ed something from GitHub but I didn't do that for some reason lol

yup exactly

you do Delaunay triangulation, then MST on that graph

[loud canyon]

Then get can use Krustals to get the MST

Right ?

[thick lagoon]

yup exactly

or Prim's algorithm

idr but I'm p sure one of them had some undesirable time complexity factor

[loud canyon]

What language is this in

I do comp programming in cpp

[loud canyon]

I think with Kruskals is pretty damn slow because it would be O(n^2*a(n)) which is very slow growing

Or

Use Delaunay triangulation, which has only O(n) edges and preserves
EMST, find triangulation in O(n*log n) then Run Kruskal’s on that subset of edges

Wouldn’t that be faster ?

[thick lagoon]

yeah you find the MST of the graph that you get by triangulating the points in O(N log N) time

[loud canyon]

Yeah

I had a problem like this

While ago

Here is the solution I got but it’s in python bc it was Python

Bc this was in high school

import math
from heapq import heappush, heappop

def dist(p1, p2):
    return math.hypot(p1[0] - p2[0], p1[1] - p2[1])

def euclidean_mst(points):
    parent = list(range(len(points)))

    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u

    def union(u, v):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            return True
        return False

    edges = []
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            d = dist(points[i], points[j])
            edges.append((d, i, j))
    
    edges.sort()
    total = 0.0
    for d, u, v in edges:
        if union(u, v):
            total += d
    return total

You could easily make it in Cpp by using CGAL @thick lagoon

You could also brute force it without

[thick lagoon]

ah, nice

but this is O(N²)

[loud canyon]

No, like I said this solution was slow

Hella

Lowkey

Imma make an implementation of that problem

You have

Using cpp

And only standard library

Give me like

20 minutes

[thick lagoon]

Anyway the last problem of the competition was a minimization problem. For a matrix F and A and a vector s and b, minimise x^T F x + s^T x where A x is element-wise larger than b.

[loud canyon]

You’re just giving me brain food

Appreciate it

No comp events around me at the moment

[thick lagoon]

yeah so the intended solution to this linear optimization problem was to ||find the dual problem, then find an analytic solution to that, then do fancy math to bring that back to the original problem, then run a linear solver on that (and that linear solver also has to be fast enough)||

[loud canyon]

Fancy math is real as fuck

[thick lagoon]

mfw I hadn't even heard of what a dual problem is

it's like
first 5 problems: ezpz
problem 6 and 7: medium
problem 8 (the coin flip problem): hard unless you've done convolutions with FFT before
problem 9: hard unless you steal the first best implementation you find on GitHub
problem 10: basically impossible unless you spend all your time only on this problem, and have studied math at a university for the past five years

[thick lagoon]

alright we got ktimers now

and they are actually very decent ktimers, too

previously, I dispatched ktimers directly from within the timer interrupt

but now, the timer interrupt enqueues a DPC which dispatches the ktimers

this means you can actually do fun stuff, like allocating memory, from a ktimer.

also this state is quite fun to manage

because next_expiry is read from within the interrupt handler, any outside code that reads or writes it needs to disable interrupts. this leads to some fun IRQ state juggling in e.g. KTimer::remove():

[worn wolf]

Couldn't you just use atomics and cas rather than toggling interrupts

[thick lagoon]

yes that would work, actually

good idea

[thick lagoon]

although I'm not actually toggling interrupts... disable_irq compiles down to this:

        incb    %gs:13

and enable_irq to this:

        decb    %gs:13
        jz .Lslowpath

[thick lagoon]

what's nice with the current ktimer implementation is that the interrupt handler has a time complexity of O(1). everything with a higher time complexity is kept outside of the interrupt critical section. enqueue and remove have time complexities of O(log N), and dispatch has a time complexity of O(M log N) where N is the number of active KTimers and M is the number of KTimers that are expired.

whoops, I just noticed a mistake:

there's no point in inserting the KTimer in an IRQ-critical section, when a DPC critical section would've done.

so the lines queue->tree.insert (this); and enable_irq (); can be swapped

[thick lagoon]

actually, now that I've fixed this issue, every single IRQ-critical section in the KTimer code is bounded by O(1).

[thick lagoon]

This is a principle I will do my very best to adhere to:

1. Every IRQ-critical section should be wait-free and bounded by O(1).
2. Every interrupt handler should be wait-free and bounded by O(1).
   Rule 2 will not be possible to always follow, because e.g. TLB flushes issue interprocessor interrupts that perform O(N) work (where N=the number of pages to flush).

[weary prairie]

page fault handler won’t be O(1) and might wait :^)

ah you said it already i’m blind

[vital siren]

page fault handler is more usefully thought of as an unplanned syscall than an interrupt

cuz unlike a device interrupt it's doing work on behalf of your thread so it can take mutexes. block. etc

[weary prairie]

you know what, i never thought about it that way

but it makes so much sense

[hot rose]

quite

and it has it in common with all the traps

[weary prairie]

yeah true

man i am really missing a bunch of little things like that

well, not exactly little things, but it's necessary to make a good kernel

i need to study mintia and keyronex vmm implementations, maybe then something will click in my head

every time when i just thought i had the knowledge to write something i discovered another hole in my understanding of whatever i was trying to write

the rabbit hole of implementing a kernel full of fancy things i guess

[hot rose]

sometimes maybe it's harmful to be too self-critical in this way, certainly it's good to be self-critical but there's not many people who did everything right from the getgo, and to try to achieve that is probably quite limiting

there needs to be moments of consolidation and moments of exploration

and that's not myself saying that, that's thomas kuhn

[thick lagoon]

my AVL tree is bugged...

not very many lines above:

[thick lagoon]

(the parameters to m_cmp should be swapped)

[thick lagoon]

as others said, the page fault and other traps, although being dispatched by the same CPU mechanism, aren't really interrupts

[thick lagoon]

alright, I have ported vmatree from the old kernel to the new kernel (and also added some C++ niceties to the implementation). now I also gotta port the test cases...

will do it later

[thick lagoon]

yup, something's borked

[fathom lake]

rip

[thick lagoon]

smh

... and now we page fault instead

yay, we are too big for LTO!

surprisingly, it compiles relatively fast

probably because I added [[gnu::noinline]] to all the tested functions so 20000 lines of function calls aren't each individually assessed for inlining

eh, I'll figure it out tomorrow

[thick lagoon]

this page fault could also be the allocator being relatively untested

will investiage tomorrow

[thick lagoon]

alright it was pretty trivial. I forgot a single goddamn return after having dealt with an easy case of VMATree::remove()

still, find_free_bottomup and find_free_topdown exhibit incorrect behavior

however it is only those functions that fail, so I am relatively confident insert and remove are correct (apart from maybe tracking gaps incorrectly, if that's the root cause of the issue)

tried commenting out these lines in VMATree::find_free_bottomup, still 2048 bad cases of find_free_bottomup and find_free_topdown. phew

(if commenting out those lines fixed anything, it'd be an indicator that biggest_gap tracking was incorrect. and I don't want to deal with that right now)

tfw I just forgot to return when I find a free range lol

still 63 failing testcases, however

this fixes things. FUUUUUUUUUUUUU.....

bruh. so when a node is inserted or removed or otherwise modified, we consider its successor node, whose prev_gap is modified, which means that (if the successor is an ancestor of node), we cannot early exit from fixup, because that might leave biggest_gap in an incorrect state

... and would you look at that

well this is fun

(slab is broken seemingly ok but allocation tracking is broken)

relatively easy fix

[torn nova]

Damn nice

[thick lagoon]

the best configuration system known to man:

# Configuration Makefile.
# Copyright (C) 2025-present  dbstream
#
# This configuration Makefile takes configuration variables from the
# environment, exports them, and adds them to CPPFLAGS.

CONFIG_KTEST ?= n
CONFIG_KTEST_VMATREE ?= n

CPPFLAGS-$(CONFIG_KTEST) += -DCONFIG_KTEST
CPPFLAGS-$(CONFIG_KTEST_VMATREE) += -DCONFIG_KTEST_VMATREE

export CONFIG_KTEST
export CONFIG_KTEST_VMATREE

CPPFLAGS += $(CPPFLAGS-y)

[torn nova]

Totally unique

[thick lagoon]

this is sarcasm btw

also it's literally just

export CONFIG_FOO=y
make -j

, no loading from a .env or anything

.

[worn wolf]

Are you using ubsan and addrsan? It can catch that sort of stuff

[thick lagoon]

no

from what I've heard it should be relatively easy to support, though

[worn wolf]

Yeah it's just a few symbols and all they need to do is assert

[thick lagoon]

except ASAN might be a bit tricky, with tracking what addresses are allocated and which aren't

or whas that MSAN?

not enough sanitizers

[worn wolf]

Alternatively you can build that part of the kernel as a normal library and run it on the build machine rather than in the kernel

[thick lagoon]

yeah

[worn wolf]

Addrsan is a bit tricky

[thick lagoon]

actually VMATree (and the rest of dsl) should be the most portable part of my codebase

it should be trivial to compile those as part of a host application

except integrating it with my build system

[worn wolf]

I found as long as you're not dealing with mmio or context switching most stuff is doable on the build machine

[thick lagoon]

yeah

but IMO it is better to test in kernel-mode, because of subtle differences between running the kernel freestanding and hosted

of course, that comes at the cost of losing some of the great userland debugging tools we normally have

[worn wolf]

just have tests in both then

i test first in userspace then once im happy with that i test in kernelspace

i still dont have a good kunit equivalent but just making one off kernel images is good enough

[thick lagoon]

Here's a neat trick to "automatically" surround kernel virtual memory allocations with guard pages, without having to do any extra work like making every allocation one page larger:

simply search for a hole two pages bigger than what you actually need, and plonk the allocation in the middle

when all allocations do this, this guarantees a one-page guard hole between any two allocations

in other news, we got vmap() now. which means we got >PAGE_SIZE allocations now. which means we can do fun stuff :>)

I was planning on "cheating" and using vmap to identity-map a region outside of the normally vmap-managed memory, namely, the trampoline page. But I realised that this will not work, and the reason being that the trampoline page needs to be mapped with a different set of page flags and page table flags, namely, it cannot have PG_GLOBAL set.

[thick lagoon]

C++ 👌

[thick lagoon]

This is the beginning of the trampoline page of the old kernel, and oh my god... how did this work?

so it starts off by initializing the segment registers to point to the trampoline page itself (e.g. if trampoline page=0x8000, ds=es=fs=gs=ss=0x800)

and then it does some gdt stuff, all good

then we get to movl 0x1000, %esp

which is wrong

it should be movl $0x1000, %esp

but somehow this didn't break

[lucid abyss]

const auto

[thick lagoon]

well the TSC sync mechanism is very cursed and could definitely use some work

I'll do that later

terminology:

• control CPU = the CPU that initiated smpboot
• victim CPU = the CPU that was smpbooted

it seems that TSC values are synchronized at boot on my CPU in QEMU/KVM

though it might be because the host kernel synchronizes them

now, the CPU is a Ryzen 9 7950X3D with 2 CCX'es

for debugging purposes, I print the observed difference between the TSC value measured on the control CPU and that measured on the victim CPU

it always appears to be one of the following values: 84 cycles, 672 cycles, or 714 cycles

this is possibly related to which host CPUs the vCPUs are scheduled on

which is fascinating that we're able to observe this by looking at TSC values

[thick lagoon]

ok there are some other values I observe too, when I run with even more vCPUs

[meager sequoia]

this is done by hardware on most single socket systems

[thick lagoon]

yeah

but we don't trust hardware, do we?

[meager sequoia]

fair enough

[worn wolf]

we could have a world with perfect firmware, all that needs to happen is microsoft pops up a warning dialog at boot if it detects firmware isnt following spec

[thick lagoon]

that would demand the bad firmware detection be perfect. which is a bit too much too ask.

[thick lagoon]

The first Davix test on real hardware went way better than expected.

This General-Protection fault is probably because of some illegal APIC state transition

although I do guard against that

[meager sequoia]

could also be because of an illegal register write

that results in a GP when in x2apic mode

[thick lagoon]

yeah

printf debugging time

[meager sequoia]

you should probably do a regdump on fault-caused panics imo

helps with this kinda thing

[thick lagoon]

yeah

maybe even stack

but that's something I'll do later then

because stack and memory, I want some kind of safe_memcpy that returns some error code on page faults

[torn nova]

u should probably have a safe_write_msr that returns an error in case of a gpf

[thick lagoon]

I'm relatively confident I know what it is

he is the culprit. now how do I check for CPU support

[meager sequoia]

do you need that? it's only useful for lowest priority interrupts and the sdm says this about those

The ability for a processor to send a lowest priority IPI is model specific and should be avoided by BIOS and operating system software

[thick lagoon]

no I just copied it from info lapic in QEMU

lol

[meager sequoia]

then i'd just remove the flag

[thick lagoon]

yeah

but I also want to know why this would be causing a fault

[meager sequoia]

setting a reserved bit is an illegal register write, and an illegal register write causes a fault in x2apic mode

[thick lagoon]

yeah but it's seemingly supported on every x86_64 there is

atleast according to Linux sources, which unconditionally set the bit unless X86_32

need to cross-reference with AMD

AMD mentions nothing about the bit being reserved

[torn nova]

how does linux unconditionally set it then?

[torn nova]

interesting

[thick lagoon]

LETSFUCKINGGOOOOOOOOO

wow osdev is easy

[meager sequoia]

what ended up being the issue?

[thick lagoon]

I removed FCC_DISABLE

[meager sequoia]

ah

still weird that it works on linux then

[thick lagoon]

yes, very.

[torn nova]

its possible that its apic_write does something else

its a dynamic callback

can be x2 or xapic etc

[thick lagoon]

presumably it's just going to be native_apic_msr_write

[torn nova]

any chance your bit is just wrong?

[thick lagoon]

my kernel:

linux:

it's probably some setup that you have to do before setting FOCUS_DISABLED that Linux does somewhere else and that I don't do

I am actually very happy about this

[thick lagoon]

like that was the only thing that I had to fix and now it works on real hardware

[torn nova]

still strange

[thick lagoon]

yeah

but I'll take this as a W

[torn nova]

one thing I see is its reading the previous mask stored there, and u just overwrite it

[thick lagoon]

yeah

true

but according to SDM all the other bits are just reserved MBZ

@torn nova how's your kernel going? you should really get it working on real hardware as soon as possible, it's a massive dopamine boost

[torn nova]

Slowly lol

Yeah I have tons of laptops to test on

[torn nova]

Maybe try that anyway who knows lol

[thick lagoon]

making sure that stuff which depends on the local APIC timer works in SMP.

hmmm that 10 second print seems wrong

no it's just the video being weird

glitched recording software

alright. next on the list is getting interprocessor interrupts up and running so that I can implement some sort of smp_call_on_cpu

[lucid abyss]

kde spectacle?

[thick lagoon]

yup

[lucid abyss]

try gpu screen recorder

[thick lagoon]

dangit this is tricky

so I want to enqueue one of these on any CPU that I am performing smpcalls to

but this is tricky because I'm unsure at what level to acquire the lock

[torn nova]

Why not just atomic?

[thick lagoon]

it should be safe to hold call_on_cpu_control_block::lock in IRQ disabled context

[thick lagoon]

partially because I don't have an atomic linked list helper type

however using a lock might have some advantages, idk.

[torn nova]

Sounds like it would be easy to just make an atomic list thing here but yeah if you don't have that I guess

[thick lagoon]

like this should work

I kind of want to have a spinlock variant that does something like the following:

void lock_irq_smart(void)
{
        irq_disable();
        for (;;) {
                if (raw_trylock()) return;

                do {
                        if (__pending_irq())
                                dispatch_pending_irq();
                        else
                                smp_spinlock_hint();
                } while (atomic_load_relaxed(&value));
        }
}

i.e. disable interrupts and lock, but as an atomic operation

(such that disabling IRQs and acquiring the lock is effectively one operation)

with my lazy IRQ disabling, pending_irq() is easily implementable

this means I could actually do something like this

[fathom lake]

atomic linked list as best I can tell needs 128 bit cmpxchg to do properly also which is technically a downside

(any hardware that supports windows 8 or later will have that though since windows requires that instruction for this exact reason)

[meager sequoia]

this is trivial without lazy irq disabling as well, just use sti; pause; cli instead of just pause as smp_spinlock_hint

[regal grove]

dirty screen.

HP Boot Manager never stops to wonder me... Can you tell me. Did I understand right. So, you have 2 ssd/hdd, and none OS is intalled there. You put the davix loader under the sundisk ssd/hdd \efi\boot\bootx64.efi and just hit <enter> on the 1st menu option and it booted your loader, right?

[thick lagoon]

yeah I should probably clean that screen and the entire device tbh...

anyway so I have a script ./run [--limine] [some other options] which generates a ISO and runs QEMU with it. this is pretty standard stuff, grub-mkrescue for GRUB and xorriso + limine bios-install for limine.

then I just dd if=/tmp/davix.iso of=/dev/sda (the USB stick)

put the USB stick into the device

start it

spam F9

and it Just Works

[thick lagoon]

yeah but let me feel like I am better than everyone else with my fancy lazy IRQ disabling system, thanks

[thick lagoon]

this USB stick is probably like twelve years old or something

[meager sequoia]

lol fair

[regal grove]

Thank you. But that iso written to the stick would have this \efi\boot\bootx64.efi anyway. And HP boot manager does show an option for it. Yet it doesn't for a load option spefically created (on some models at least). Haven't you tried to find the very same stick efi file via the "boot from file" option? I bet it would show up there too.

[thick lagoon]

yeah it does show up there

someone forgot to enable IRQs :p

(there should be a ktimer dispatching every 1 seconds after 10 seconds, but it doesn't work)

hmm, it seems like smp_call_on_cpu sometimes kills ktimers

not very nice

ah, someone is doing one enable_dpc too much

yup, found the culprit

[thick lagoon]

so spinlock_t::lock_irq calls both disable_dpc and disable_irq, and spinlock_t::unlock_irq calls both enable_irq and enable_dpc, but spinlock_t::lock_irq_atomic (this thing) was only calling disable_irq

yes, stuff works now!

I would be very grateful if someone would be willing to test this ISO on their physical hardware that they have available for testing.

(NO WARRANTY, I am not responsible for hardware damage, etc.)

(first run the iso under QEMU to see that it works correctly; iirc discord can be sketchy with file uploads)

[thick lagoon]

it would be nice to know if it works on some device with AMD chipset/CPU

(tbf my main machine that I develop on is AMD but I dare not risk data loss by testing davix on it, at least not right now)

[torn nova]

im curious what data loss you're thinking of it doesnt have any disk drivers

[thick lagoon]

it's just a healthy dose of caution. idk what weird firmware might choke on my still relatively untested kernel; the old school laptop is fine to use, there is nothing I need on it, but my main desktop OTOH...

[torn nova]

if it doesnt have any disk drivers id say the odds are the same as you getting struck by lightning or ran over by a car

[thick lagoon]

no, it's the same as winning the lottery, while getting struck by lightning, while being overran by a car, in a plane which is violently crashing into the ground

[torn nova]

yeah something like that

[thick lagoon]

still, do not want to risk anything on my main desktop

[weary prairie]

then why do you go outside, just to risk being ran over by a car or struck by lightning?

[thick lagoon]

who said I go outside?

I do go outside, the positive effects of going outside on overall wellbeing greatly outweigh any downsides to going outside

[thick lagoon]

tbh I'm probably going to end up testing on it anyway lmao

[thick lagoon]

I thought about this a bit, and actually a slightly limited atomic singly linked list can be implemented using only pointer-sized cmpxchg:

#include <atomic>
using namespace std;
struct NuclearListEntry {
    NuclearListEntry *next;
};
struct NuclearList {
    atomic<NuclearListEntry *> head;
    void push_front(NuclearListEntry *entry)
    {
        NuclearListEntry *next = head.load(memory_order_relaxed);
        do
            entry->next = next;
        while(!head.compare_exchange_weak(next, entry,
                                          memory_order_release,
                                          memory_order_relaxed);
    }
    NuclearListEntry *pop_all()
    {
        return head.exchange(nullptr, memory_order_acquire);
    }
};

the disadvantage of course being that now pop_all gives you the entries in the reversed order in which they were inserted

[lucid abyss]

nuclear list

[thick lagoon]

I thought it was a fun name for an atomic singly linked list

[lucid abyss]

it is

[thick lagoon]

this is the type of code that people would put on a slide at a conference or something

[fathom lake]

there was some aba issue that's why that isn't normally done iirc

where deletion of nodes specifically can result in collateral

https://moodycamel.com/blog/2014/solving-the-aba-problem-for-lock-free-free-lists.htm @thick lagoon have a post going over a bug in that exact impl pattern

i think without being able to pop a single item it might be fine? idk

yeah i think its actually ok as long as you only have push and clear as ops but like how useful is that actually anyway

[fathom lake]

(i have got to stop trying to read code when i just wake up, even if i get pinged about it)

[thick lagoon]

if there is only one consumer, I think it is actually possible to safely pop a single item.

NuclearListentry *pop_one()
{
    NuclearListEntry *item = head.load(memory_order_acquire);
    do {
        if (!item) break;
        NuclearListEntry *next = item->next;
    } while (!head.compare_exchange_weak(item, next,
                                         memory_order_acquire,
                                         memory_order_acquire);
    return item;
}

(memory_order_relaxed is not fine in the cmpxchg, because if it fails, we may have a new item which hasn't been acquired by this thread yet)

if pop_one races against pop_one and reinsert, you get ABA and die, but this never happens so long as there is only a single consumer

[meager sequoia]

iirc that ABA can be solved even for multi consumer as long as your pointers are aligned to a 2 byte boundary: first cmpxchg to set the lowest bit, which will pin the node to the list, then get next and cmpxchg it ```c
struct list_node {
uintptr_t next;
};

struct list_node *list_pop(struct list_node *head) {
uintptr_t address = __atomic_load_n(&head->next, ATOMIC_RELAXED);
struct list_node *node;

do {
    do {
        address &= ~1;
    } while (!__atomic_compare_exchange_n(&head->next, &address, address | 1, true, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED));

    address |= 1;
    node = (struct list_node *)address;
} while (!__atomic_compare_exchange_n(&list->head, &address, node->next & ~1, true, __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE));
return node;

}

[thick lagoon]

but that's basically a lock

[meager sequoia]

so are cmpxchg loops in general

[thick lagoon]

no

idr what it is called but there is a model where, if you pause all but one threads at any moment, that one thread you didn't pause is guaranteed to make progress

"wait-free" maybe

[meager sequoia]

ah yeah this doesn't satisfy that

[thick lagoon]

e.g. if list_pop sets the bit and is then preempted by an interrupt, and that interrupt then does list_pop, you deadlock

(although that wouldn't happen for the original usecase anyways lol)

and my usecase is MPSC

[thick lagoon]

now I have pushed functionality for shooting down remote processors on panic (AKA SMP-safe panic). first, it tries to do it using a regular IPI on a specific vector. if, after 1s, the remote processors haven't announced themselves as offline, the panicking CPU sends an NMI to remaining processors and then waits for them to go offline.

[vital siren]

Very useful

I use that in like 5 diff places in my kernel

[thick lagoon]

I am working on adding exception exiting support to KVM, with the longterm goal of implementing -d int for QEMU/KVM.

over-all plan: step 1, Linux kernel changes:

• patch 1/N: add KVM_CAP_EXCEPTION_EXITING to include/uapi/linux/kvm.h
• patch 2/N: implement KVM_CAP_EXCEPTION_EXITING for SVM
• patch 3/N: implement KVM_CAP_EXCEPTION_EXITING for VMX (this will be more annoying to test than SVM, that's why I'm doing it last)

step 2, QEMU changes:

• if -d int is present on the command line, enable KVM_CAP_EXCEPTION_EXITING and perform a register dump when a KVM_EXIT_EXCEPTION happens

KVM_EXIT_EXCEPTION will probably have to perform the interrupt control transfer "manually" (in userspace)

I want some feedback, does it make sense for the capability to be named KVM_CAP_EXCEPTION_EXITING or should it be named KVM_CAP_X86_EXCEPTION_EXITING?

[fathom lake]

id say the former

also, if that can be made to work under WSL thatd save me so much pain

[thick lagoon]

honestly now that I think about it, I'm leaning towards the latter

except no, KVM_EXIT_EXCEPTION is a generic thing

[inland cairn]

Careful because logging parms are not constant. I don't know too much about kvm, but there's (amost) no functional difference between -d int and using log int in the monitor

And of course the latter can be modified whenever you wish

[thick lagoon]

yeah

there definitely needs to be a bit per-vCPU that determines this behavior

changing -d int at runtime is a QEMU concern, not a KVM one (so long as KVM exports an interface such that changing -d int at runtime can reasonably be implemented)

[inland cairn]

Yeah, i agree, I was warning that your step 2 is insufficient

[thick lagoon]

thanks

the question is, do we need to add a new ioctl, or can we add something to KVM_SET_GUEST_DEBUG (or is that abuse of KVM_CAP_SET_GUEST_DEBUG)?

actually no, KVM_ENABLE_CAP seems to work per vCPU

very nice

hmm, there is no KVM_DISABLE_CAP

struct kvm_enable_cap {
       /* in */
       __u32 cap;

The capability that is supposed to get enabled.

       __u32 flags;

A bitfield indicating future enhancements. Has to be 0 for now.

       __u64 args[4];

Arguments for enabling a feature. If a feature needs initial values to
function properly, this is the place to put them.

       __u8  pad[64];
};

probably one of the args can be used to indicate whether userspace wants this feature to be enabled or not

[fathom lake]

can you not just ignore the info if its been turned off?

[thick lagoon]

yeah userspace can just not print

[fathom lake]

yeah

[thick lagoon]

but kernel maintainers won't like that

[fathom lake]

true

still have a cap is my thought

so if it gets enabled at all you turn it on, and then if its off start ignoring info

[thick lagoon]

one idea is to use one of the bits in kvm_enable_cap.args[0] to indicate whether exceptions should cause vmexits

anyways, I need sleep, should not be designing user API when I'm tired :P

[inland cairn]

Yeah that's a good idea, vmexit on every exception isnt good but if you've already enabled those logs then you're ready to take this perf hit

Better then any hacks/1k loc changes

[thick lagoon]

there is the option of proposing a KVM_CAP_DISABLE_CAP which can be used in the future to disable this capability

although making use of KVM_DISABLE_CAP would require a KVM_CAP_EXCEPTION_EXITING2 lol

damn kernel devs. why do you not have versioned capabilities?

[inland cairn]

Though if I were you I'd worry first how much info you can get from kvm on trap. I suggest implementing the exit => log => enter before playing around with api/details

[thick lagoon]

this is probably the best alternative, because KVM_DISABLE_CAP can be used for other things too

[thick lagoon]

yeah definitely

so my idea for how it would work is something like this:

1. you get KVM_EXIT_EXCEPTION
2. ioctl(KVM_GET_REGS) etc. to read register state
3. exception, error_code, has_error_code in struct kvm_run
4. now it is your responsibility to perform the interrupt control transfer
5. ioctl(KVM_RUN) and we are back

lmaooooo

[thick lagoon]

anyway so it'd be something like this:

int kvm_arch_handle_exit(CPUState *cs, struct kvm_run *run)
{
    // ...
    switch (run->exit_reason) {
    case KVM_EXIT_EXCEPTION:
        DPRINTF("kvm_exit_exception: exception %d exit (error code 0x%x)\n",
                run->ex.exception, run->ex.error_code);
        ret = kvm_handle_exception(cpu, run);
        break;
    // ...
    }

    return ret;
}

// ...

int kvm_handle_exception(CPUState *cs, struct kvm_run *run)
{
    if (!log_int_enabled) {
        fprintf(stderr, "KVM: exception %d exit (error code 0x%x)\n",
            run->ex.exception, run->ex.error_code);
        return -1;
    }

    bql_lock();
    whatever_function_prints_register_state(cs);
    int ret = manually_perform_an_interrupt_control_transfer_lol(cs, run->ex.exception, run->ex.error_code);
    bql_unlock();
    return ret;
}

and that's it for today, I think. Sadly, I am a human being who needs sleep

[torn nova]

wait are u making a hypervisor?

[fathom lake]

#1326937732122935379 message

[torn nova]

damn

[thick lagoon]

question: should KVM_CAP_EXCEPTION_EXITING cause KVM exits for int $n and external IRQs?

I want to say "no", for two reasons:

(1) it makes my job easier

[meager sequoia]

int $n definitely not, that's just a fancy call instruction

[thick lagoon]

(2) it is already possible to intercept external IRQs

[meager sequoia]

and external irqs should probably be separate

[fathom lake]

does it do that on tcg?

cause thats the point of comparison

[thick lagoon]

yeah

[meager sequoia]

tcg doesn't do int $n

and external irqs are separate too in tcg

[thick lagoon]

what about external IRQs?

ahh nice.

[meager sequoia]

they still show up in -d int, but instead of check_exception ... followed by a regdump it's Servicing external ... and nothing else

[thick lagoon]

yeah

[meager sequoia]

at least that's the case for PIC interrupts, i've never bothered to check whether the same is true for APIC

[thick lagoon]

great

[fathom lake]

ive gotten external interrupts showing up with regdump before, or at least what i believe to be that, was hard to debug

[meager sequoia]

oh yeah with apic it does show a regdump

it's still servicing external int=... instead of check_exception ... but there is a regdump

[thick lagoon]

yeah

[thick lagoon]

but I'm going to answer this question with "no" still

because we already have a mechanism for that

[fathom lake]

the question is is it handled by qemu or by a vmexit in tcg when it does servicing external and a regdump

[meager sequoia]

i believe the difference vs pic might be because qemu's userspace ioapic uses MSIs to dispatch IRQs?

[thick lagoon]

the more I look at it, the more difficult this task feels

anyway so here is an excerpt from the AMD64 APM

so we set these bits to intercept exceptions (can we just set them all to 1?)

KVM, being KVM, already touches these in a hundred places

this loop in x86.c is responsible for running the vCPU. AFAICT no fastpath exists for any VMEXIT_EXCP, atleast for SVM

so at some point in between all the clr_exception_intercepts (which, surprisingly, there actually aren't a lot of), I need to set_exception_intercept all the exceptions

I'm deliberately going to avoid looking at nested.c, because that is probably irrelevant and would just be more work

so svm_set_efer can clear the #GP intercept

dangit, there's also some erratum around #GP intercepts

ok so because there is no fastpath for these, all VMEXIT_EXCP[...] will end up calling svm_handle_exit

which ends up calling svm_invoke_exit_handler

which ends up calling svm_handle_invalid_exit for a lot of them

what the damn is this

so ud2; .ascii "kvm" is the newest addition to the x86 instruction set

[meager sequoia]

seems like that's just a kvm instruction prefix

actually no that's just ud2

why does it exist

what's the difference between ud2 and ud2; .ascii "kvm"

 * EMULTYPE_TRAP_UD_FORCED - Set when emulating an intercepted #UD that was
 *                 triggered by KVM's magic "force emulation" prefix,
 *                 which is opt in via module param (off by default).
 *                 Bypasses EmulateOnUD restriction despite emulating
 *                 due to an intercepted #UD (see EMULTYPE_TRAP_UD).
 *                 Used to test the full emulator from userspace.``` right

[thick lagoon]

yeah I'm going to pretend like that's not a thing

yeah #UD is going to be a PITA

because sometimes KVM should legitimately emulate the instruction

yeah #UD makes this a pain

[worn wolf]

libcapstone time

[inland cairn]

Yeah sadly having no logs is better then having incomplete logs.. not sure how you'd test your changes either, simply running linux applications would not be enough imo

[thick lagoon]

I am probably not going to work on this anymore, multiple reasons why:

• just started a job, so I have way less free time now than I have had previously
• there is a low probability to get this merged into mainline
• KVM is weird

anyway here are some potentially useful notes if anyone wants to pick this work up:

• have a KVM_CAP_* and use KVM_ENABLE_CAP to enable it per-vCPU. don't worry about disabling it, for now.
• in SVM (AMD), set_exception_intercept should be used to set the exception bits in the interception bitmap. VMX (Intel) probably has an equivalent.
• SVM exception exits do not go via the fastpath, so execution reaches svm_handle_exit and the logic for making the exception, error code etc. available to user space can be put there.

[lucid abyss]

good job on the job. I hope it's a good job

[thick lagoon]

It's schedulin' time.

I'm currently doing some scheduler design, and I'm taking inspiration from the ULE scheduler but also doing my own thing kinda.

so the gist of it is this:

• every CPU has a runqueue
• every runqueue has N queues (corresponding to N priority levels)
• within each priority level, scheduling is RR with a fixed timeslice. a CPU always picks a task from the highest-priority queue. (yes, this means that starvation is possible.)

I'm also going to have something called the "sched_ticket_t", which is an unblocking ticket which is acquired by sched_get_blocking_ticket, and sched_wake is a no-op unless it is called with the sched_ticket_t most recently returned from sched_get_blocking_ticket. (this is inspired by something I read from avdgrinten)

The sched_ticket_t is very nice because it makes sched_wake much easier. now it can look like this:

bool
sched_wake (Task *task, sched_ticket_t ticket)
{
        disable_dpc();
        if (!CAS(&task->unblock_ticket, &ticket, ticket + 1)) {
                enable_dpc();
                return false;
        }

        /*
         * now we know that we cannot race against another waker.  actually wake
         * up the task now.
         */
        // ...
        return true
}

sched_wake is still a bit tricky

(because of SMP)

consider e.g. the following:

CPU0                  CPU1
T1                    T2
mutex_lock()
->sched_get_blocking_ticket();
  add_mutex_waiter(mutex, self);
  spin_unlock(&mutex->lock);
                      mutex_unlock()
                      ->sched_wake(T1, ticket);
  schedule()

now thread 2 is suddenly waking up thread 1 which hasn't scheduled away yet

the easy way to avoid this is to perform the actual wakeup via IPI. that way, T1 can prevent it from happening by disabling IRQs until after it has called schedule().

the disadvantage to this is of course that, now you need to wake up remote tasks via IPI.

so the solution I am going to use will look something a bit like this:

struct Task {
        // ...
        unsigned int on_cpu;
        unsigned int pending_wakeup;
        // ...
};

void
finish_context_switch (Task *prev)
{
        int state = atomic_load(prev->state);
        if (state == TASK_RUNNABLE)
                return;

        atomic_store_seq_cst(prev->on_cpu, -1U);
        unsigned int expected = 1;
        if (CAS(&prev->pending_wakeup, &expected, 0))
                // wake up the task
}

// (called after we have incremented the unblock ticket)
void
__sched_wake (Task *task)
{
        atomic_store_seq_cst(task->pending_wakeup, 1U);
        if (atomic_load_seq_cst(task->on_cpu) != -1U)
                // the task will be woken up by finish_context_switch
                return;

        unsigned int expected = 1;
        if (CAS(&prev->pending_wakeup, &expected, 0))
                // wake up the task
}

so on_cpu is always a valid CPU number if the task is TASK_RUNNABLE, otherwise it is -1U.

now, seq_cst memory ordering is sufficient

but I'm actually unsure if anything below that would be sufficient

I don't think so, actually...

[thick lagoon]

the reason that this is a problem is because thread 2 might enqueue thread 1 on a different CPU than it is busy scheduling away from

[thick lagoon]

the reason we need seq_cst is this: consider the two lines of __sched_wake

atomic_store(task->pending_wakeup, 1, mo_seq_cst);
if (atomic_load(task->on_cpu, mo_seq_cst) != 1U)
        // the task will be woken up by finish_context_switch
        return;

store-release load-acquire can be reordered into load-acquire store-release, which breaks the expectation that the task will be woken up by finish_context_switch.

similarily in finish_context_switch, consider the two lines

atomic_store(&prev->on_cpu, -1U, mo_seq_cst);
if (atomic_cmpxchg(&prev->pending_wakeup, &expected, 0, mo_seq_cst, mo_relaxed))

without seq_cst ordering, these lines can also be reordered

also breaking the expectation that finish_context_switch will wake up the task if __sched_wake sees on_cpu != -1U after setting pending_wakeup

the CAS in __sched_wake can possibly be relaxed

the reason is that because __sched_wake has already observed on_cpu == -1U with seq_cst memory ordering, and on_cpu is set by finish_context_switch also with seq_cst ordering, enqueueing the task happens-after the task has scheduled away anyways

[thick lagoon]

oh my god it actually works

[lucid abyss]

based

[thick lagoon]

currently trying to get @round cradle's fireworks test running... it is not going very well...

[lucid abyss]

what firework test? I might try it as well

[thick lagoon]

https://github.com/iProgramMC/Boron/blob/master/drivers/test/source/fworktst.c

[round cradle]

Warning - this tests your scheduler and how well you can cope with memory pressure

[thick lagoon]

good.

something seems to go wrong specifically when a task exits.

[lucid abyss]

this is pretty

I don't exit threads though

[thick lagoon]

yeah

I have a suspicion about what might be wrong...

vmap

fking kfree_large page table code might be incorrect and I hate it

[thick lagoon]

ok so there are multiple faults that occur, which is fun...

at least one of them is on this instruction

which is the first thing that touches the stack frame of a newly-switched-to task

[thick lagoon]

This will have to do for now. Will debug and fix this ASAP when I have time but not right now.

[thick lagoon]

famous last words

anyway for now let's look at this beautiful fireworks test and pretend like nothing is wrong.

[lucid abyss]

is that a modified test?

because mine looked different :P

[thick lagoon]

yeah maybe

I kinda just went with the over-all structure of the Boron fireworks test

how does yours look?

[lucid abyss]

screen recorder decided to die

it's a bunch of colourful dots coming up from below and exploding into more dots

[vital siren]

I got a fireworks port from the man himself

[round cradle]

you forgot to scale the speed by a random value and thats why it goes in a circle

[round cradle]

at a cursory glance this looks flawed

https://github.com/dbstream/davix/blob/master/arch/x86/kernel/task.cc#L67 because who's to say the task you're returning here is in the context of the task that was switched from

nvm

i would suggest trying to offload thread reaping to a DPC

that's what i do in boron

[thick lagoon]

yeah

reap_task is right now just a temporary kthread-only thing

later on I plan on having a kthreadd which waits for other kthreads to die

[thick lagoon]

this I will fix tomorrow

[thick lagoon]

oh my god this is so fking stupid

https://github.com/dbstream/davix/blob/6a0eb8d2171b78bf50890b56c033030fdf76e144/arch/x86/kernel/task.cc#L80

so basically, I have a lazy-IRQ scheme

it works like this:

• when someone enters a critical section, they increment a counter.
• when an interrupt happens, if the counter is nonzero, the interrupt stub returns early without issuing EOI or anything, but to a context with raw interrupts disabled
• when that someone leaves their critical section, they decrement their counter and test if there is a pending interrupt. if there is a pending interrupt, handle it and reenable raw interrupts afterwards.

but here's the thing

if a schedule() occurs,

well first off, interrupts are incorrectly enabled in some cases

but secondly, the schedule() lazily disables IRQs. then it calls context_switch, which calls arch_context_switch, which saves raw interrupts, switches stacks, and (when someone returns) restores raw interrupts

but here's the thing

the flag indicating that there is a pending interrupt is 'handed over' to the new task that is switched to

so when asm_switch_to returns to us, that flag says "there is no pending interrupt", but raw_irq_restore does not reenable interrupts

therefore, we get into an incorrect state where interrupts are disabled and they are never reenabled

[round cradle]

yknow i had a suspicion that that could chase issues but i thought that surely youd call arch_context_switch in contexts where it doesnt matter anyway

[thick lagoon]

this is why KTimers die

[round cradle]

i feel like you may want to store this state as part of the current processor struct

[thick lagoon]

yeah

it is percpu, not per task

hence this stuff

(saving/restoring a task's local disable_irq/disable_dpc counts)

[round cradle]

yes but saving and restoring there doesn't work

[thick lagoon]

it does work

[round cradle]

because the values you will be restoring are from all the way back when the thread you just switched to

[thick lagoon]

stupidly saving and restoring raw interrupt enablement state (the interrupts flag in rflags) doesn't work

[round cradle]

which may not match with the actual state

[thick lagoon]

hence the weird stuff around __IRQL_NONE_PENDING

[round cradle]

idk if that solves anything really

tbh why is saving and restoring them even needed

[thick lagoon]

the name "irql" might confuse you

[round cradle]

anything involving interrupts should NOT involve the concept of a current thread

[thick lagoon]

it is because originally I did something where it was like

irql_cookie_t cookie = raise_irql(IRQL_DISPATCH);
// ...
lower_irql(cookie);

[round cradle]

in my OS kernel, interrupts and DPCs can happen in any thread's context

[thick lagoon]

but later I moved to just doing it similarily to preempt_disable and preempt_enable in Linux:

disable_irq();
// ...
enable_irq();

[thick lagoon]

yeah, same here

except interrupts can call scheduler functions like sched_wake

and that might give some annoying edge cases when we are in the middle of a task switch

[round cradle]

if anything DPCs should be the ones doing that

because you'll never execute a DPC during a task switch

[thick lagoon]

yeah... but performance :-)

or something

[round cradle]

at the expense of your kernel struggling to work?

[thick lagoon]

needing to enqueue and dispatch DPCs that otherwise wouldn't be needed

"kernek"

lol

but I'm relatively sure it works now

1sec, going to push these changes to GitHub now

[round cradle]

If you want such luxuries, then you'll need to make your scheduler non-preemptible

[vital siren]

lol his scheduler isnt interruptible this mf got unpredictable interrupt response time 🤭 🤭 🤭

[round cradle]

An interruptible scheduler needs consistent layering

[thick lagoon]

in other news I fixed the fireworks test

[thick lagoon]

it probably is possible to do this while still having an interruptible scheduler

and the reason why is my overengineered __sched_wake function: https://github.com/dbstream/davix/blob/master/kernel/sched/main.cc#L225

[round cradle]

Can be possible if you're willing to fight race conditions between the scheduler and interrupts, which FYI, can interrupt you anywhere when you don't disable interrupts, and so you'd have to disable interrupts every time you make a change to a data structure in the scheduler

Wouldn't you rather not have to do that?

[thick lagoon]

if I am switching away from a task, and I am interrupted by someone who wants to wake that task, I will not enqueue that task. Instead, I set a flag in the task struct indicating that there is a pending wakeup, and once I finish handling the interrupt etc. I return, and finish_context_switch will see that sched_wake left a note saying 'wake me up'

[thick lagoon]

there are really only three things in the scheduler that disable interrupts:

• enqueueing a task to the runqueue
• picking a task to run
• arch_context_switch
  these are all O(1)

well technically pick_next_task is O(number of priority levels), but that is a small constant

and sched_wake also sometimes calls find_least_loaded_cpu, which is O(number of CPUs), but that is also a constant at runtime

[thick lagoon]

so this is incorrect. the scheduler has critical sections that aren't interruptible, but they are bounded. hence, interrupt response times are predictable (given that there isn't another bug somewhere in my kernel)

this is not to say that there aren't other issues with my scheduler as it is right now

[vital siren]

also when are you imagining youd be doing a dpc that you wouldnt otherwise need to, as a result of scheduler functions needing to run at that lower irql

[thick lagoon]

if you cannot sched_wake from an interrupt, and you want to e.g. wake an interrupt thread to go handle that interrupt, you cannot do that without an extra DPC now.

interrupt threads are actually a special-case, because they will have TF_NOMIGRATE which makes __sched_wake and finish_context_switch skip the call to find_least_loaded_cpu and instead always enqueue the task on the CPU it last ran on

[round cradle]

so that either implies that you scan through the entire thread list to see which ones have been woken up (gross) or you have limitations on who __sched_wake can wake up

[thick lagoon]

the runqueue lock is not held while context_switching

https://github.com/dbstream/davix/blob/master/kernel/sched/main.cc#L371

[round cradle]

oh, wait, i misread

you only do this for the task you are actively switching from

[thick lagoon]

yes

[round cradle]

i see

[thick lagoon]

it's quite ingenious. I'm very proud of this design.

(btw this pending_wakeup thing is mainly important for the SMP case)

github does not know what a struct is

[vital siren]

HELLO??????????????????????????????????????!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!?!?!?!??!!?!??!!?!??!

[thick lagoon]

this message was a response to that

[vital siren]

well

its rly not that big of a deal and certainly a very low price to pay for nearly full interruptibility of the kernel

[round cradle]

i agree

[thick lagoon]

yeah