davix operating system kernel

[thick lagoon]

e.g. here you see the fireworks test

[thick lagoon]

oh my god scheduler priorities seem to work

somewhere someone misses to dispatch a DPC

and it is related to printing somehow

no

it is related to KeExitIRQContextToKernel somehow?

actually the most likely culprit is one of KiSetupInitialThreadContext not dispatching pending DPCs correctly, and context_switch restoring them improperly

[broken axle]

How do you implement unit testing in osdev?

[thick lagoon]

I don't

The 'torture test' I have in mind is literally just a bunch of

for (;;)
        ;

threads meant to exercise the scheduler's context switch codepath and others

[broken axle]

Aha is it like userland programs and such that are tests

[thick lagoon]

pretty much (except this is kernel mode)

event tracing for scheduler decisions will allow to trace the runtime of tasks and verify that priorities in CFS works as intended

but now I'm debugging a very annoying bug

[broken axle]

cool

[thick lagoon]

ugh... why is dpc_counter == 0, that should be illegal as a permanent state because if it ever becomes zero it should be dispatched

there is a goddamn race condition somewhere

no it's goddamn related to deferred IRQ handling not dispatching DPCs

yup

found it

🐛 🔫 ggwp, bug

I feel like a debugging mastermind now.

And scheduler priorities work, too!

[thick lagoon]

oh my god this stuff actually works so well

I keep track of a unsigned int taskHeartbeatDistr[10]; and each thread runs the following code:

KeSetBasePriority(prio);

for (;;) {
        for (int i = 0; i < 1000000000; i++)
                asm volatile("" ::: "memory");
        taskHeartbeatDistr[prio++];;
//      KePrintf("%d\n", prio);
}

[thick lagoon]

actually, event tracing is boring. the goal was to prove that thread priorities under CFS somewhat work, and that I have already done

I'll skip that and go directly for SMP stuff instead

[thick lagoon]

Now I have:

• written a 'torture test' (not really since it's only 10 threads, but that's more than I tested it with previously).
• implemented scheduler priorities, (something inspired by CFS for priorities 0...9, and a simple list for realtime threads, which never preempt each other)
• implemented shootdown of remote processors in a panic scenario

[thick lagoon]

I wonder if I should initially do like a really really stupid load balancer that just does round robin between CPUs when waking up threads

it's good because:

1. it's simple
2. it will exercise concurrency sensitive stuff because things will run on different CPUs relatively randomly
3. it is very easy to replace with something better later

[thick lagoon]

literally just

static unsigned int select_cpu_for_wakeup(void)
{
    static unsigned int counter = 0;
    unsigned int cpu = atomic_load_relaxed(&counter);
    for (;;) {
        unsigned int cpu_orig = cpu;
        while (!KeCPUOnline(cpu)) {
            cpu++;
            if (cpu >= keProcessorCount)
                cpu = 0;
        }

        unsigned int next = cpu + 1;
        if (next >= keProcessorCount)
            next = 0;

        bool status = atomic_cmpxchg(
            &counter,
            &cpu_orig,
            next,
            _MO_Relaxed,
            _MO_Relaxed
        );

        if (status)
            return cpu;

        cpu = cpu_orig;
    }
}

something's not working with remote wakeup

This becomes very obvious when looking at the thread "heartbeat" distribution

marked in red: stuff which runs on CPU1. everything else runs on CPU0. CPU1 does the waking up

Oops, wasn't tracking current_thread correctly...

fixed, that's not it

I forgot to acknowledge the scheduler related IPIs

that was the issue

🐛 🔫 ggwp, mr. Bug.

letsgo, load "balancing" works (but currently it is a very stupid variant of load balancing)

It's Turnstile time, I guess.

today has been surprisingly productive

[vital siren]

Ternstyle

[fallen whale]

how it works

or is it described above

[thick lagoon]

described above

[thick lagoon]

this

as for the actual wakeup mechanism, that is a bit more complicated

[fallen whale]

when do you call select_cpu_for_wakeup?

[thick lagoon]

when selecting a CPU to enqueue a task on when waking it up

[fallen whale]

but you don't do periodic balancing right ?

[vital siren]

Idk if that counts as load balancing

[thick lagoon]

these past two days have been very productive

[thick lagoon]

You are correct, arguably it doesn't. But atleast I am enqueueing work on CPUs other than CPU0 :-)

[thick lagoon]

not yet

[vital siren]

Load balancing is when you try to even out the work pending between CPUs

Simplest way is to try to move threads around until they all have the same number of threads on their ready queues

[thick lagoon]

yeah... this doesn't count, in that case

but hey, it's Good Enough For Now :-)

[thick lagoon]

,

[fallen whale]

do you know if windows has periodic rebalancing ?

[thick lagoon]

it probably does

[fallen whale]

i think it didnt have it originally

but yeah it didnt need it back then

[vital siren]

It has to

Or at least some way to even out the load

[vital siren]

Yeah it didn't because it had a single shared ready queue

[fallen whale]

i think it round robins ideal processor for each thread during creation

[vital siren]

So load was automatically balanced

[fallen whale]

yeah

[fallen whale]

its similar to davix's

[thick lagoon]

yeah but that's not at thread creation (or, I guess you can argue that since thread creation basically always calls KeWakeThread, yes it is called at thread creation)

and there are no further efforts to distribute threads between CPUs

but it is enough for now, because:

1. it is better than nothing.
2. because threads are distributed somewhat "randomly" between cores, important codepaths are likely exercised
3. it can be replaced very easily later

[thick lagoon]

I want to figure out some sort of generic interface for sleep timeouts. Something like the following:

void somefunction(nsec_t ns)
{
        KeSetTimeout(HalReadSchedClock() + ns);
        // ... much later
        KeDisablePreemption();
        KeSetCurrentState(KTHREAD_UNINTERRUPTIBLE | KTHREAD_TIMEOUT);
        KeReschedule();
        KeEnablePreemption();
        KeUnsetTimeout();
}

where basically, any time you block and the KTHREAD_TIMEOUT bit is set in KTHREAD::thread_state, the timeout set by the last call to KeSetTimeout will be used.

This is nice to have because it means I can do things like:

syscall_long_t mysyscall(syscall_long_t timeout_ns, /* ... */)
{
        KeSetTimeout(HalReadSchedClock() + timeout_ns);
        /*
         * ...
         *
         * The above timeout is used throughout the syscall.
         */
        // ...
}

Note: Setting KTHREAD::thread_state != KTHREAD_RUNNING is a promise, i.e. you must block if you ever set another thread_state than KTHREAD_RUNNING. Also it is not allowed to change KTHREAD::thread_state after setting it to something else, because KeWakeThread will cmpxchg it to KTHREAD_WAKING_UP.

[fallen whale]

or maybe they don't do that as i looked through all the ki functions in ntoskrnl.exe and as far as i can tell by names there's nothing like that... ofc that's a really dumb way to check it

but now they have this shared queue per cpu group thing that may not require periodic rebalancing ?

[thick lagoon]

this is the type of thing that info lapic <cpunum> is super helpful with debugging. I see the ISR field nonempty and so I know someone hasn't written EOI before returning from an hardirq handler.

[thick lagoon]

no actually, I think it is very possible to do this in my design. you just have to watch out for some races against KeWakeThread, which is why this is generally not a good idea.

[fallen whale]

are your latest changes published somewhere?

[thick lagoon]

in a private git repository, I can put it in a branch somewhere tomorrow if you want to look at it.

[fathom lake]

I'm also interested in seeing this scheduler stuff

[thick lagoon]

can someone ping me tomorrow evening if I have not yet made it available and posted something here? (tomorrow is a busy day AFK, so might be tired in the evening and forget/don't have time to do it)

I'm probably going to end up putting this stuff in like a 'rtdavix' branch or something in the "current" repository

I would really like to get some feedback on how understandable the scheduler is so that I can improve the explanatory comments throughout Ke/sched/sched.cc.

but that's blocked on me making this stuff available

[round cradle]

Your repo isn't public

[thick lagoon]

Now it is. https://github.com/dbstream/davix/tree/rtdavix
(cc @fallen whale @fathom lake)

[fallen whale]

thx

[thick lagoon]

Note to self: clamp vruntime between min(vruntime of cfs tasks) - allowed delta and max(vruntime of cfs tasks) + allowed delta when waking up a thread.

[fathom lake]

thanks, I'll read through it later

[thick lagoon]

I implemented this. It seemingly works.

[final galleon]

Somewhat surprisingly, this is a simple and effective solution to the problem, so I copied it to some extent. Regarding balance, one of the nuances I see is a situation where all high-priority threads end up in the same basket. I also sample k (2) candidate queues uniformly at random with affinity-aware filtering and choose the one with the most suitable load parameters for rebalancing (the one with the lower load; ties broken arbitrarily).

[thick lagoon]

I have now written a Turnstile interface inspired by the illumos turnstile implementation.

/**
 * KeTurnstileGet - acquire a turnstile for a synchronization object.
 * @address: pointer to synchronization object
 */
KTURNSTILE *KeTurnstileGet(void *address);

/**
 * KeTurnstilePut - release a turnstile.
 * @tstl: pointer to turnstile
 */
void KeTurnstilePut(KTURNSTILE *tstl);

/** 
 * KeTurnstileBlock - block on a turnstile.
 * @tstl: pointer to turnstile
 * @queue: KTURNSTILE_Q_READER or KTURNSTILE_Q_WRITER
 * Returns true if KeTurnstileWakeOne or KeTurnstileWakeMultiple woke us up.
 */
bool KeTurnstileBlock(KTURNSTILE *tstl, int queue);

/**
 * KeTurnstileWakeOne - wake up one waiter.
 * @tstl: pointer to turnstile
 * @queue: KTURNSTILE_Q_READER or KTURNSTILE_Q_WRITER
 * Returns true if we woke up a waiter.
 */
bool KeTurnstileWakeOne(KTURNSTILE *tstl, int queue);

/**
 * KeTurnstileWakeMultiple - wake up all waiters.
 * @tstl: pointer to turnstile
 * @queue: KTURNSTILE_Q_READER or KTURNSTILE_Q_WRITER
 * Returns the number of waiters we woke up.
 */
unsigned long KeTurnstileWakeMultiple(KTURNSTILE *tstl, int queue);

@vital siren @hot rose you're both familiar with turnstiles. Is there anything which is obviously wrong at first glance about this interface?

[thick lagoon]

(and implemented these functions)

KeTurnstileWakeOne will probably have to be modified to also return whether the queue is empty after the operation completed

[vital siren]

Does illumos allow you to wake only one thread

[thick lagoon]

idk, I didn't study it that in depth

it only has one turnstile_wake interface, I think. IDK if it takes in a number of tasks

[vital siren]

It probably doesn't

It's pretty difficult to support only waking one in practice

[thick lagoon]

why is that the case?

[hot rose]

you can wake as many as you want in solaris turnstiles

[vital siren]

Interactions with the fact you do an atomic CAS on the single pointer sized lock word

And priority inheritance

[vital siren]

I'm pretty sure I checked and both pushlocks and turnstile backed locks in illumos always wake all waiters

[vital siren]

Basically if you release it and wake one and another guy comes in and locks it, all the other waiters don't get a chance to reapply their priority inheritance to the new owner

The easiest solution is to always wake all

[hot rose]

there are specialist uses for turnstiles other than that

but at least for rwlocks it does wake all waiters, i think

[vital siren]

True

I meant specifically for locks

[fallen whale]

btw do you know why pushlock raises irql when waking up push lock? reactos raises to DISPATCH

[vital siren]

Most likely to avoid being preempted a bunch of times by each thread it wakes

[fallen whale]

it does
if (WaitBlock->Previous)
{
/* Raise to Dispatch */
KeRaiseIrql(DISPATCH_LEVEL, &OldIrql);
}

[vital siren]

This would waste tons of cycles

[fallen whale]

ah thats when you wake up multiple threads at a time ?

i see

[vital siren]

ReactOS probably blindly copies it without understanding why it raises to dispatch level there

Judging by the poor quality of the comments in that file

Which I've talked about previously

[final galleon]

When you are waking up more than one thread, you want to avoid rescheduling.

[fallen whale]

i see

and glad to see you back

[vital siren]

hear hear

[fallen whale]

i now find it easier to read the pushlock code in reactos without comments

lol

otherwise i just check the comment against the loc because each comment repeats it

[final galleon]

I feel strongly that its kernel is little more than a rip-off. Even looking at the push lock code raises questions for me.

[torn nova]

Are you an nt engineer?

[final galleon]

Why are you asking?

[hot rose]

        /* Try to find the last block */
        while (TRUE)
        {
            /* Get the last wait block */
            LastWaitBlock = WaitBlock->Last;

            /* Check if we found it */
            if (LastWaitBlock)
            {
                /* Use it */
                WaitBlock = LastWaitBlock;
                break;
            }

            /* Save the previous block */
            PreviousWaitBlock = WaitBlock;

            /* Move to next block */
            WaitBlock = WaitBlock->Next;

            /* Save the previous block */
            WaitBlock->Previous = PreviousWaitBlock;
        }

well this is a bit shite

between the big block comments, the spaces everywhere, and the comments styled after an undergrad's assignment submissions, it's no wonder it's 1200 lines in that file

the comments do hardly at all contribute to my understanding of the logic, they are almost all a masterclass in tautology. compare with https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/os/turnstile.c#L28

[torn nova]

Just curious

[feral snow]

/* Use it */

[fallen whale]

yeah

/* Get, check, use, save, save, move */

[thick lagoon]

Being AFK is kinda nice, actually.