IRC channel logs

<almuhs>hi. After latest git pull, when i try to compile with -smp 8, i have this compile error https://pastebin.com/HXjb8kgM

<almuhs>i used this flags

<almuhs>../configure --host=i686-gnu CC='gcc -m32' LD='ld -melf_i386' --enable-apic --enable-kdb --enable-ncpus=8--disable-linux-groups

<youpi>now fixed

<almuhs>success now

<almuhs>smp now it's a bit faster, in fact. But doesn't boot yet, like Damien told

<almuhs>do you know where can i find documentation about gnumach's scheduler design? I want to know the algorithm criteria and details

<youpi>that'd be cmu research papers, probably

<almuhs>reading the code, i don't have clear what criteria are using to set priorities, by example

<youpi>again, priorities won't matter for boot speed

<almuhs>but... the gnumach scheduler is literally the same than cmu mach scheduler?

<youpi>I don't know the details

<youpi>but it's probably mostly coming from it

<almuhs>i want to find gaps in the algorithm

<almuhs>usecases that the scheduler don't takes account

<almuhs>or failures

<almuhs>understand scheduler simply reading the code is very hard. I tried many times and i don't understand how it works in detail. By this reason i want to find docs

<youpi>you can probably for a start read scheduling chapters of OS books

<almuhs>i have some knowledge about it from my degree

<almuhs>i have a subject with a long topic about scheduling algorithms and strategies. By this reason, i detected that gnumach's scheduler has multiple queues and priorities

<almuhs>and the queues have some feedback: some process change from a queue to another.

<almuhs>but i don't understand the gnumach's scheduler source code in deep

<almuhs>i don't know if algorithm is round robin with priorities, or a SRT, SJF... or a fully custom

<almuhs>even i don't know if all queues has the same algorithm or each queue has the self. It's very common that in multiqueue scheduling each queue has a different algorithm

<almuhs>but, the most important thing is ... how the scheduler distribute the work between the multiple processors? How the scheduler selects what processor execute each process

<youpi>it has two policies: time sharing and fixed priority; I guess the first is like unix's SCHED_OTHER, and the second is like Unix's SCHED_RR

<youpi>the distribution of work is probably not very advanced

<youpi>that's not really an immediate problem anyway

<almuhs>i found some here https://www.gnu.org/software/hurd/gnumach-doc/Scheduling.html

<youpi>that's just the api

<almuhs>yes, but it explains some data

<almuhs>fixed priorily seems like round robin

<almuhs>"Processor sets may restrict the allowed policies, so this call will fail if the processor set to which thread is currently assigned does not permit policy. "

<almuhs>the criteria in other mode is that "(for timesharing, this means adding an increment derived from cpu usage)."

<almuhs>so, when the process starts, it have the lowest priority

<almuhs>but, this could produce that some new process never get the cpu, because there are many older and long process which are using it all the time

<almuhs>reading from this: https://www.gnu.org/software/hurd/gnumach-doc/Thread-Priority.html#Thread-Priority

<youpi>I don't think process that start have lowest priority

<youpi>usually it's the converse that is done

<almuhs>ok, in the docs adds this info "Newly created threads obtain their priority from their task and their max priority from the thread. "

<almuhs>full paragraph: "Threads have three priorities associated with them by the system, a priority, a maximum priority, and a scheduled priority. The scheduled priority is used to make scheduling decisions about the thread. It is determined from the priority by the policy (for timesharing, this means adding an increment derived from cpu usage). The priority can be set under user control, but may never exceed the maximum priority. Changing t

<almuhs>he maximum priority requires presentation of the control port for the thread's processor set; since the control port for the default processor set is privileged, users cannot raise their maximum priority to unfairly compete with other users on that set. Newly created threads obtain their priority from their task and their max priority from the thread. "

<almuhs>what do it refers with "from their task"?

<youpi>well, the task in which is was created?

<almuhs>parent process?

<youpi>no, the process iteslf

<almuhs>rea, it's thread the unit

<almuhs>*real

<almuhs>the process has many threads

<damo22>i think with MACH_HOST set to 0, there is only one processor set

<youpi>probably, yes

<damo22>that simplifies the scheduling

<youpi>I don't think mach creates processor sets by itself anyway, it's rather an admin thing

<almuhs>now the question is... how the task get its priority?

<almuhs>is it defined from userspace?

<damo22>i think so for fixed priority threads

<damo22>youpi says the priority is not causing slow boot speed

<almuhs>check if currently are using fixed priority or timeshare as policy

<youpi>admins can set priorities

<youpi>and users can use "nice" to lower priorities

<youpi>almuhs: it's usually timesharing by default

<youpi>since that's what user expect usually

<damo22>almuhs: i have another few patches only in my local, to bind every thread to master cpu

<damo22>it then boots slow

<damo22>which is unexpected

<almuhs>i think that some could be some bad scenarios in which some threads keeps in a low priority and never gets the cpu by this reason

<youpi>almuhs: that's not a problem

<youpi>it's fine for a thread to leave cpu to another thread

<almuhs>could be a problem if this thread is a essential component of the system

<youpi>that'll still be useful for boot to proceed

<youpi>there's nothing "essential" as in that it needs deadlines

<youpi>again, threads don't consume cpus just for fancy

<youpi>so it doesn't really matter which thread runs when

<youpi>it's doing useful stuff anyway

<almuhs>by example, what matters if some ext2fs thread never gets cpu?

<damo22>context switching is set to maximum 33Hz

<youpi>again, that doesn't matter

<youpi>if everything else in the system is waiting for that thread, then that thread *will* get the cpu

<youpi>and again, all of this is the *same* on uni-processor gnumach

<almuhs>the problem is not only slow. is that, once started INIT, this never gets to start the filesystem

<youpi>the only difference on smp is possibly waking the other cpu to run thread sin parallel

<youpi>almuhs: which can very probably be explained by merely something hanging for whatever reason

<damo22>almuhs: the theory of that one is that there are races in userspace servers that lock up the system

<almuhs>but i think that some races could be produced by lacks in scheduler

<damo22>because they are not used to running threads exactly at the same time

<almuhs>i think

<youpi>damn, I have a hard time finishing that python3.11 build on hurd-amd64

<youpi>the kernel keeps crashing

<damo22>oh damn

<damo22>what is the backtrace?

<youpi>almuhs: there *could* be some races in the scheduler that make it miss some threads, yes

<youpi>but by binding everything on cpu0 we should be avoiding that

<youpi>various places

<youpi>most often pmap

<youpi>sometimes ipc

<youpi>which means, well, everything that a microkernel does :)

<almuhs>if all threads goes to the same cpu, the problem can make worse. Because the competition is bigger

<damo22>uhh, no cpu0 can only run one thread at a time

<youpi>AGAIN

<youpi>that does *NOT* matter

<youpi>threads do produce useful stuff during boot

<youpi>whatever their order really *does*. *not*. matter

<damo22>it cant matter, because they cant rely on ordering of operations

<youpi>put another way: competition for *what*?

<damo22>between threads

<youpi>for what?

<youpi>(I was asking almuhs)

<almuhs>i worried about, if the cpu only can execute one thread every time, and there are so so many threads, even many which requires many cpu. If the priority increase with cpu usage, the longer process can keep all cpu for itself

<youpi>so what?

<youpi>if it has stuff to do, then that's good

<youpi>booting will need that done anyway

<youpi>it doesn't matter if it's doing before or after the others

<almuhs>if there are so new process which casually has a low priority, maybe it never gets the cpu, and this task keeps freezed because of that

<youpi>SO WHAT?

<youpi>the "other threads" are not spending cpu time for nothing

<youpi>during boot, *ALL* threads are contributing to booting

<youpi>nothing else

<youpi>damn

<damo22>also on an smp system, every thread has to accept being interrupted at any time to be rescheduled at a later time because there arent enough cpus to run every thread simultanously

<damo22>so maybe this slowness is something to do with IPI/interrupts

<youpi>if there are thousands of IPIs per second, that's a problem for sure

<damo22>i will test

<almuhs>yes, but imagine that ext2fs gets priority=10. And, in the same time, other server has priority=100 and increasing because it are are entering one and once time in the cpu. And each time that procfs out of cpu, auth gets the cpu because priority=50 and increasing. ext2fs never gets the cpu

<almuhs>"procfs = other server"

<almuhs>it's a hipotethic

<youpi>SO WHAT

<youpi>so what

<youpi>damsn

<youpi>it's not a problem for other processes to eat cpu

<youpi>they're doing stuff

<youpi>all good

<youpi>ext2fs is behind ? so what

<almuhs>the problem is that ext2fs never gets to make its work

<youpi>if the other processes at some point really want something from ext2fs, they'll block

<youpi>and thus leave the cpu to ext2fs

<youpi>of course it *will*

<youpi>at worse when *EVERYBODY ELSE* has nothing to do

<damo22>i think what youpi means is that the other threads are busy doing things that progress the boot, when they finish their timeslices and block, they will eventually force cpu onto ext2fs

<youpi>and that *DOESN'T* matter for the whole boot time duration

<youpi>the global time spent will be the *SAME*

<youpi>cpu being busy doing stuff from whatever thread all the time

<almuhs>yes, but if every time some thread out of cpu, enter other thread different than ext2fs?

<youpi>so what?

<almuhs>because every thread has high priority than ext2fs?

<youpi>so what?

<youpi>there cannot be an infinite amount of threads that have stuff to do

<almuhs>ext2fs never works

<youpi>at some ponit they'll just all be waiting for ext2fs

<damo22>eventually there will be a time when ext2fs is the only thread that hasnt progressed

<youpi>and *then* ext2fs will obviously get the cpyu

<damo22>in worst case

<almuhs>mutual exclusion

<youpi>that's fine as wlel

<almuhs>ok

<damo22>unless there is a bug and the run queue for NCPUS > 1 is buggy

<almuhs>this is the next step

<youpi>there can be waking mistake yes

<youpi>the scheduler missing that some thread is ready for running

<almuhs>now we have to check that

<youpi>though, again, it's all the same on UP

<youpi>so again, I wouldn't prioritize looking there

<damo22>when i compile for smp and use -smp 1 its still slow

<almuhs>but i think that, once getting INIT, the problem is not only that the boot is slow. Is that some server gets locked

<damo22>almuhs: that problem is solved by binding to cpu0

<youpi>that's a very probable thing yes

<youpi>thus the binding

<almuhs>maybe some server are crashing?

<damo22>they are deadlocked

<damo22>probably on some pthreading issue

<youpi>almuhs: I would doubt about that

<youpi>from their ponit of view, there is no difference betwen UP and SMP

<youpi>(-once bound)

<almuhs>the boot always keeps freeze in the step in which filesystem are starting

<damo22>there could be a pthread race in ext2fs

<damo22>or /sbin/init ?

<almuhs>i remember that, some years ago, youpi and me was searching the cause that ext2fs freeze in booting. We bound it, and this doesn't solve the problem

<almuhs>and we found that there was a ext2fs thread which never was assigned

<damo22>when i bind everything on cpu0 nothing deadlocks its just slow

<almuhs>maybe the scheduler is buggy, as you told before, and it's not assigning the threads

<damo22>i will check how often we get ipi

<damo22>- if (myprocessor->state != PROCESSOR_IDLE) {

<damo22>- /*

<damo22>- * Something happened, try again.

<damo22>- */

<damo22>- simple_unlock(&pset->idle_lock);

<damo22>- goto retry;

<damo22>i dont understand this codepath

<almuhs>maybe the scheduler is different when NCPUS > 1, and it has a bug that, even when all is bound to cpu0, it keeps without assign cpu to the threads. Or, exactly, doesn't assign cpu to ext2fs threads

<damo22>why not just dispatch the cpu again

<almuhs>damo22: what are there in retry label?

<youpi>damo22: it just goes back to looking at the value again

<youpi>since it changed between the test without the lock, and the test with the lock

<damo22>why do we care about the test with the lock

<youpi>because otherwise you're not synchronized with whatever processor that changed the state

<youpi>you want atomicity between the state change and the other variables concerning that state

<almuhs>check the codeblocks that are only of NCPUS > 1. Because the scheduler seems work fine in NCPUS = 1

<damo22>so if it stayed true to the state, why do we set it to running instead of dispatching?

<almuhs>so could be a bug that only appears in NCPUS > 1

<damo22>if processor was not dispatched, why not set it to dispatching and goto retry?

<damo22>since we know its idle

<almuhs>sched_prim.c. line 1255. There are a very long code specific to NCPUS > 1

<damo22>what is the point of setting it running and block on idle thread?

<almuhs>line 1269 is related to idle processor

<damo22>I'm referring to this codepath:

<damo22> * Processor was not dispatched (Rare).

<damo22> * Set it running again.

<almuhs>what line is it?

<damo22>it seems to be setting an idle processor to running state when we already have a nice thread to dispatch directly on the idle processor

<almuhs>could be a bug

<almuhs>i have a question about it

<almuhs>/*

<almuhs> * But first check the last processor it ran on.

<almuhs> */

<almuhs> processor = th->last_processor;

<almuhs>what if the thread never ran before?

<damo22>that code path only works on HW_FOOTPRINT = 1

<damo22>we are not using it

<almuhs>real

<almuhs>then we have to check after line 1293

<almuhs>if (pset->idle_count > 0) {

<almuhs>where is this count set?

<almuhs>because the previous HW_FOOTPRINT modify it

<damo22>default_pset.idle_count is the number of idle processors

<damo22>since we use MACH_HOST=0

<almuhs>but, who increase or decrease it?

<damo22>grep for idle_count--

<almuhs>ok, XD

<almuhs>1279: pset->idle_count--;

<almuhs>1293: if (pset->idle_count > 0) {

<almuhs>1295: if (pset->idle_count > 0) {

<almuhs>1299: pset->idle_count--;

<almuhs>1338: pset->idle_count--;

<almuhs>1367: if (default_pset.idle_count > 0) {

<almuhs>1371: default_pset.idle_count--;

<almuhs>1611: pset->idle_count++;

<almuhs>1751: pset->idle_count--;

<almuhs>ok, it's not only in HW_FOOTPRINT

<almuhs>1299 is our usecase

<almuhs>1611 is MACH_FIXPRI

<almuhs>then... idle_count only decrease, never increase

<almuhs>me fail: 1611 is out usecase too

<damo22>no

<almuhs>*our

<almuhs>1751 is our usecase too

<almuhs>then we could discard this as problem, as a first view

<almuhs>this was solved, it's not?

<almuhs>if (processor != current_processor())

<almuhs> cause_ast_check(processor);

<almuhs> return;

<damo22>yeah i added that

<damo22>it causes an IPI so it interrupts machine_idle before the next clock interrupt

<damo22>on processor

<damo22>to wake up the cpu

<almuhs> * Preempt check

<almuhs> */

<almuhs> if (may_preempt &&

<damo22>because machine_idle halts the cpu until next interrupt

<almuhs>i go to check this

<almuhs>1238: boolean_t may_preempt)

<almuhs>1314: if (may_preempt &&

<almuhs>1388: if (may_preempt && (current_thread()->sched_pri > th->sched_pri)) {

<almuhs>is it not set?

<almuhs>i have not find any assignation

<almuhs>if may_preempt is not assigned, it could casually value false by default, and then the processor never preempt

<damo22>its passed in as a param

<almuhs>but not as &

<damo22>?

<almuhs>oh, now undertand

<almuhs>excuse me

<almuhs>then we have to find which calls to this

<almuhs>ok, hardcoded

<almuhs>343: thread_setrun(thread, TRUE);

<almuhs>428: thread_setrun(thread, TRUE);

<almuhs>714: thread_setrun(old_thread, FALSE);

<almuhs>966: thread_setrun(thread, FALSE);

<almuhs>1179: * run_queue_enqueue macro for thread_setrun().

<almuhs>1236:void thread_setrun(

<almuhs>1418: thread_setrun(th, TRUE);

<almuhs>1768: thread_setrun(new_thread, FALSE);

<almuhs>1990: thread_setrun(thread, TRUE);

<almuhs>discard it as problem

<almuhs>then could be a queue bug or a unlock broken

<damo22>with bound threads on cpu0 there are no IPIs being sent

<almuhs>if (pset->idle_count > 0) {

<almuhs> simple_lock(&pset->idle_lock);

<almuhs> if (pset->idle_count > 0) {

<almuhs> processor = (processor_t) queue_first(&pset->idle_queue);

<almuhs> queue_remove(&(pset->idle_queue), processor, processor_t,

<almuhs> processor_queue);

<almuhs> pset->idle_count--;

<almuhs> processor->next_thread = th;

<almuhs> processor->state = PROCESSOR_DISPATCHING;

<almuhs> simple_unlock(&pset->idle_lock);

<almuhs> if (processor != current_processor())

<almuhs> cause_ast_check(processor);

<almuhs> return;

<almuhs> }

<almuhs> simple_unlock(&pset->idle_lock);

<almuhs> }

<almuhs> rq = &(pset->runq);

<almuhs> run_queue_enqueue(rq,th);

<almuhs> /*

<almuhs> * Preempt check

<almuhs> */

<almuhs> if (may_preempt &&

<almuhs>#if MACH_HOST

<almuhs> (pset == current_processor()->processor_set) &&

<almuhs>#endif /* MACH_HOST */

<almuhs> (current_thread()->sched_pri > th->sched_pri)) {

<almuhs> /*

<almuhs> * Turn off first_quantum to allow csw.

<almuhs> */

<almuhs> current_processor()->first_quantum = FALSE;

<almuhs> ast_on(cpu_number(), AST_BLOCK);

<almuhs>ok, then could be a common bug between bound and no-bound

<damo22>please....

<almuhs>sorry

<almuhs>the only common code between bound and no-bound is that

<almuhs>if (th->sched_stamp != sched_tick) {

<almuhs> update_priority(th);

<almuhs> }

<almuhs> assert(th->runq == RUN_QUEUE_NULL);

<almuhs>in this function

<damo22>i guess it makes sense there is nothing to signal when bound on cpu0

<damo22>so no IPIs being sent

<almuhs>and this is the only function, in this file, which has significant differences between NCPUS = 1 and NCPUS > 1

<damo22>but why still slow

<almuhs>the rest differences are simply

<almuhs>#if NCPUS > 1

<almuhs> new_thread->last_processor = current_processor();

<almuhs>#endif /* NCPUS > 1 */

<almuhs>current_processor() works fine/

<almuhs>?

<damo22>sure

<almuhs>then only rest the previous little code

<almuhs>at least in the scheduler

<almuhs>if (th->sched_stamp != sched_tick) {

<almuhs> update_priority(th);

<almuhs> }

<almuhs> assert(th->runq == RUN_QUEUE_NULL);

<almuhs>variables seems correctly assigned, then the rest are update_priority() or the assert(). Probably the assert

<damo22> * Bound, can only run on bound processor. Have to lock

<damo22> * processor here because it may not be the current one.

<damo22>processor_lock(processor) could be expensive

<almuhs>but then, why the slow is in bound and no-bound?

<damo22>its much faster in non-bound

<almuhs>but freeze at the same point

<damo22>freezing is irrelevant

<almuhs>freeze i refers that boot doesn't progress after INIT

<damo22>can we rewrite the dispatch code for bound processors to not lock the processor?

<almuhs>could try

<damo22>what does processor_lock do?

<almuhs>i have to find it

<almuhs>processor.h:225:#define processor_lock(pr) simple_lock(&(pr)->lock)

<damo22>yes but what is its consequence

<almuhs>what makes simple_lock() ?

<damo22>its a spinlock

<almuhs>a while-style llop?

<almuhs>*loop?

<damo22>yes

<almuhs>very expensive, yes

<damo22>only if its been taken before

<almuhs>maybe, instead lock the processor, it could be assigned by a flag that, each time a thread search a processor where execute, discard the processors which have the bound flag

<damo22>it will wait until free

<almuhs>really, the flag is

<damo22>processor is the bound processor in this codepath

<damo22>but it might not be current_processor

<almuhs>yes, i'm searching possible bugs in that

<almuhs>yes, the code check that

<almuhs>if (processor != current_processor())

<almuhs> cause_ast_check(processor);

<almuhs>assume that could be more than one bound processor? because if not, i don't understand how the bound processor could not be the current

<damo22>no

<damo22>bound processor is arbitrary per thread

<almuhs>oh, bound refers that the thread cannot change of cpu?

<damo22>yes

<almuhs>but could be more than a cpu works at same time

<damo22>it can only be bound to a single processor

<damo22>at a time

<almuhs>each thread is assigned to a unique cpu. Each time that thread enter to cpu, always be the same

<almuhs>it's not?

<damo22>no

<damo22>only if bound

<almuhs>yes, i refers to bound

<damo22>if bound_processor == PROCESSOR_NULL, then it is unbound

<damo22>and can run on any

<almuhs>bound doesn't implies no-SMP, only implies that threads cannot change of cpu

<almuhs>yes, i understand this line

<damo22>yea, it basically means it always must be scheduled on the same cpu

<almuhs>yes, i tried to told it before

<almuhs>ok, now understand better

<almuhs>then the if makes sense

<almuhs>but i think than we could force to execute in bound processor only with logic, without locks

<almuhs>without processor_lock i refer

<damo22>i think the lock is needed because the bound processor could be running a different thread currently while this other cpu is choosing to dispatch it

<damo22>but it might not matter if its idle

<almuhs>yes

<almuhs>in no-bound code, there are other simple_lock

<almuhs>if (pset->idle_count > 0) {

<almuhs> simple_lock(&pset->idle_lock);

<damo22>we have that lock as well in bound case

<almuhs>yes, because processor_lock is a simple_lock

<almuhs>by this reason i noticed it

<damo22>i think we dont have to lock processor because thats only to read the processor_set

<almuhs>in no-bound even there are two simple_lock!!

<almuhs>fix: tree

<almuhs>three simple_lock

<almuhs>in no-bound there are 3 simple_lock like this simple_lock(&pset->idle_lock);

<damo22>you cant update the idle_queue of idle processors without that lock

<almuhs>yes

<almuhs>fix: there are a simple_lock and two simple_unlock. It has more sense

<almuhs>i'm a bit tired and i have errors

<almuhs>could be anyway to set this locks with other mechanism than a while loop?

<almuhs>some less expensive

<damo22>its not expensive if the lock is not already taken

<damo22>otherwise it just waits until free

<damo22>its a synchronisation mechanism

<almuhs>real

<almuhs>then we only can remove the locks in the cases than it's not necessary

<almuhs>and continue checking the code to find possible bugs

<damo22>maybe you should sleep

<almuhs>yes

<damo22>cpu_pause()

<almuhs>you can continue checking void thread_setrun()

<almuhs>this is the key of the scheduler

<almuhs>and pay attention to ast calls

<almuhs>i go to sleep, 4:31 AM in Spain

<damo22>night

<ioio>Hello folks, I've been trying my hands around hurd, but I'm having a hard time with the SSH connection.

<ioio>I'm not able to connect despite not having set the password, and I think it has something to do with how the new SSH is configured.

<damo22>man sshd_config

<damo22>i think the scheduler thread itself is consuming much of the cpu time

<youpi>damo22: ? there is no scheduler thread

<youpi>at best only the idle thread that doesn't much beyond calling the scheduler

<damo22>is (hz / 33) : 33 times / second?

<damo22>thats equivalent to ~3 ticks?

<damo22>which is every 30ms

<damo22>yeah thats about right i guess

<damo22>thread_setrun in the bound_processor path gets called heaps

<damo22>like it pages off a few screens before rumpdisk has a chance to print anything

<damo22>can we reduce the frequency of the scheduler

<youpi>you can reduce MIN_QUANTUM, yes

<youpi>I mean, reduce 33, so the MIN_QUANTUM gets bigger

<damo22>yea

<damo22>ill try 10

<damo22>makes no difference to boot speed

IRC channel logs

2023-08-13.log