syllable-kernel — The list is for discussion of Kernel issues by developers

Re: [Syllable-kernel] Arno's kernel patches

[Jake H. <jh...@po...>]

Kristian Van Der Vliet wrote:
> On Friday 28 January 2005 03:26, Jake Hamby wrote:
> 
>>Also, what is the verdict as far as the stability of Arno's patches?
>>Did the Jan. 23 patch removing the cli()/put_cpu_flags() calls make
>>things better or worse?  I'm concerned about Vander's reports of
>>instability during compiles and I'd much rather have a stable kernel
>>that only works on some machines than a kernel that boots on more
>>machines but isn't reliable.
> 
> 
> It fixed booting on SMP (& HT) machines at the expense of stability on SMP and 
> uni machines.  I wouldn't consider it a suitable final patch for inclusion in 
> the next release of Syllable without further work to stabalise it.

Okay, that's what I thought.  I was a little concerned because, if 
anything, we should be _adding_ SMP sychronization mutexes, not removing 
them, unless they are obviously unnecessary and not in the critical 
startup path.  Correctness before optimization and all that.  Syllable 
is already Fast Enough on most machines.

Anyway, after my Windows woes, which thankfully did not involve the 
dreaded registry, I was thinking that the Windows registry is actually a 
fairly useful concept to have available to third parties as an 
abstraction for storing key/value pairs in a simple hierarchy that can 
be browsed and edited by a knowledgeable user.  You may have gripes with 
Microsoft's failings in the implementation, but it is a useful concept 
in these days of plug-and-play devices, bluetooth discovery, etc., not 
to mention tracking shared dll and driver installations and a whole set 
of software configuration options.  It's the over-use of the last one 
(storing third-party application settings that can get messed up) that 
has caused the most grief for users over the years.  Even Microsoft is 
admitting they screwed up and is now offering not one but four different 
APIs for storing application settings in .NET apps: .config files (XML), 
the registry, "special folders" (I assume this is implemented with NTFS 
attributes or some sort of hidden file on FAT), and finally "isolated 
storage" which is like special folders but stored in some special 
location where the program doesn't have to know where it is.  Not much 
of an improvement, really.  :-)

In our case we have AFS attributes, and any app is free to use XML or 
any other format to store settings so, outside of creating an equivalent 
to the hidden "Application Data" and "Local Settings" folders in Windows 
(perhaps ".config" if this hasn't already been decided?) in each user's 
home directory for personal settings, we should be okay on that end. 
But for communications between the kernel and user programs, we need 
something a little different.  In the Linux world this is communicated 
through files in the virtual /proc FS (and the newer /sys FS) and the 
user can get and set flags through sysctl.  For the initial startup 
configuration, simple command-line options, as with Syllable, are 
sufficient.

For the plug-and-play situation and especially for integration between 
the kernel and the GUI desktop, first there was hotplug, now devfs or 
the newer user-mode "udev".  Under at least Gentoo and probably other 
distros, you can choose either devfs or udev.  At the GUI level, the 
FreeDesktop project is working on something called d-bus, which appears 
to be roughly equivalent to our registrar.

Anyway, I will look into the capabilities of the registrar as well as 
read through the d-bus mailing list archives to see how it's being used, 
and see if perhaps we can begin to use the registrar for communication 
of information between user processes and the kernel.  I would very much 
like for Syllable to have an equivalent to the Windows task manager (I 
want to write my own in order to learn the syllable API), and I don't 
want us to continue passing information in fixed length structures, as 
we're currently doing in get_system_info().  If we can require init to 
be running at all times, I don't think it's a big sacrifice to require 
the registrar to be running as well.  Then we can have the equivalent of 
sysctl, /proc, and udev/d-bus, or equivalent to the Windows registry 
only better of course.  :-)

-Jake

Re: [Syllable-kernel] Arno's kernel patches

[Kristian V. D. V. <va...@li...>]

On Friday 28 January 2005 03:26, Jake Hamby wrote:
> Also, what is the verdict as far as the stability of Arno's patches?
> Did the Jan. 23 patch removing the cli()/put_cpu_flags() calls make
> things better or worse?  I'm concerned about Vander's reports of
> instability during compiles and I'd much rather have a stable kernel
> that only works on some machines than a kernel that boots on more
> machines but isn't reliable.

It fixed booting on SMP (& HT) machines at the expense of stability on SMP and 
uni machines.  I wouldn't consider it a suitable final patch for inclusion in 
the next release of Syllable without further work to stabalise it.

-- 
Vanders
http://www.syllable.org
http://www.liqwyd.com

[Syllable-kernel] Arno's kernel patches

[Jake H. <jh...@po...>]

Did Arno Klenke release his kernel patches to anyone in source form?  I 
have his latest kernel.so and the patches from Dec. 30, but nothing 
else.  I sent him a private e-mail so I'm sure I'll hear back from him soon.

Also, what is the verdict as far as the stability of Arno's patches? 
Did the Jan. 23 patch removing the cli()/put_cpu_flags() calls make 
things better or worse?  I'm concerned about Vander's reports of 
instability during compiles and I'd much rather have a stable kernel 
that only works on some machines than a kernel that boots on more 
machines but isn't reliable.

It would be nice if we had more comments in the code as to the exact 
order in which things are happening in the startup sequence, or why the 
interrupts should or should not be disabled at certain places, as the 
logic can be quite subtle and confusing at this low level.  I'll see 
what I can do to continue Arno and Daniel's cleanups and add some 
appropriate comments as I figure stuff out.  :-)

-Jake

[Syllable-kernel] Kernel warnings

[Daniel G. <da...@fp...>]

Hi, Jake.

During my work on the scheduler, I modified the kernel makefiles to
build on my linux box (although it doesn't link), so that I could catch
stupid compile errors without having to send the patches to my syllable
box.  In addition, I added -Werror to my CFLAGS.  I'm using gcc 3.4.3,
so this caught a bunch of warnings that don't show up on syllable.
Attached are several patches that fix the most obvious of these
warnings.

seqlock_init.patch

This one should definitely be applied. Seqlocks are being
mis-initialized.


syllable-warnings-config-h.patch
syllable-warnings-device-h.patch
syllable-warnings-image-h.patch
syllable-warnings-irq-h.patch
syllable-warnings-socket-h.patch
syllable-warnings-if-h.patch
syllable-warnings-net-h.patch

These all fix "not a prototype" warnings.  This is new to gcc 3.4, where
it now wants a void argument on function prototypes that take no
arguments.


syllable-warnings-spinlock-h.patch

atomic_t now has the volatile in it.


syllable-warnings-sockios-h.patch

No comment around #endif comment


syllable-warnings-strace.patch

This moves two static structures from a header to the single file
they're used in.  They should either be moved, or not marked static (but
rather const), because gcc warns that static structs are not used.  I'd
vote for moving them, hence the patch.

If some or all of these could be applied, that would make my life
somewhat easier.

Thanks,
Daniel

[Syllable-kernel] Scheduler cleanup 2

[Daniel G. <da...@fp...>]

Okay, here's patch 2 is my scheduler cleanup set.  This one has also
been tested, and should be fairly non-contraversial.  It depends on the
previous one.

This is mostly a documentation patch.  I've documented every function in
scheduler.c.  In addition, there are some really basic cleanups (like
not setting the state of a task to wait twice in a row).

The next patch is much more invasive, as it converts wait queues to the
new list primatives.  That one is in testing now.

Daniel

Re: [Syllable-kernel] Scheduler cleanup

[Daniel G. <da...@fp...>]

On Fri, 2005-01-21 at 08:01 +0000, Kristian Van Der Vliet wrote:
> On Thursday 20 January 2005 22:56, Daniel Gryniewicz wrote:
> > Here's the first in a series of cleanup patches for the scheduler.  This
> > is all (hopefully) preperatory to porting Con Kolivas' staircase
> > scheduler from the linux -ck kernel.  This is the scheduler I use on all
> > my linux boxes, and it's absolutely great for desktops.
> 
> This sounds excelent.  I'm happy to see some real interest in the kernel these 
> days.

Yeah, me too. :)  I'm happy to discover I actually have some free time
to work on the kernel.

> > Attached is the patch and the list header, which is assumed to be in
> > inc/list.h
> 
> Could we move it to <atheos/list.h>?  I can think of a few other places in the 
> kernel and the drivers where a generic linked list implementation would be 
> useful.

I have no problem with this.  The choice of basic list primatives
(type-safet NetBSD style, like I have, or
type-unsafe-but-easier-to-use-and-no-heads Linux style) generally causes
a flame war, so I thought I'd start by putting it in the kernel space.
As far as I'm concerned, a set of standard list primatives is a really
good thing, whichever type they be.

> > I've tested this fairly thouroughly, and it works.
> 
> I have a few comments on the patch.  Hope you don't mind!
> 
> 1. In add_thread_to_ready() you have
> 
> 		for ( psTmp = LIST_FIRST( &g_sSysBase.ex_sFirstReady ); NULL != psTmp; psTmp 
> = LIST_NEXT( psTmp, tr_psNext ) )
>  		{
> 		...
> 			if ( LIST_NEXT( psTmp, tr_psNext ) == NULL )
> 				break;
> 		}
> 
>   It looks to me as though you call LIST_NEXT twice within the loop; once
>   within the for() and then again at the bottom of the loop.  Should this not
>   be called once, perhaps at the bottom of the loop E.g.
> 
> 		for ( psTmp = LIST_FIRST( &g_sSysBase.ex_sFirstReady ); NULL != psTmp;  )
>  		{
> 		...
> 			psTmp = LIST_NEXT( psTmp, tr_psNext );
> 			if ( psTmp == NULL )
> 				break;
> 		}

This could easily be done.  I'm starting out with strict cleanup, so I
wanted to change as little as possible, and the for loop was already
open-coded to exit early.  Oh, and your suggestion wouldn't work,
because we need psTmp to point to the last entry, not be NULL, so we can
append to it.  There's a version of the list primatives that allow
appending to the tail of the list, but they're slightly more
inconvenient, and I've so far never needed to append to the end without
walking to it first.  I'll put fixes for this kind of thing into cleanup
patch 4, but the goal is to get there is small steps that people can
easily understand.

> 2. Possibly rename g_SysBase.ex_sFirstReady; to E.g. ex_ReadyListHead or
>     similiar?  Don't worry about this one if it's going to get replaced by the
>     new scheduler changes anyway.

Yeah, I'm going to replace the ready list with a priority queue, so that
will get renamed at some point anyway.  Staircase is one of the O(1)
family of schedulers, so it has a fairly complex priority queue.

Second patch is tested now, I'll post it in a different patch.

Daniel

Re: [Syllable-kernel] Scheduler cleanup

[Kristian V. D. V. <va...@li...>]

On Thursday 20 January 2005 22:56, Daniel Gryniewicz wrote:
> Here's the first in a series of cleanup patches for the scheduler.  This
> is all (hopefully) preperatory to porting Con Kolivas' staircase
> scheduler from the linux -ck kernel.  This is the scheduler I use on all
> my linux boxes, and it's absolutely great for desktops.

This sounds excelent.  I'm happy to see some real interest in the kernel these 
days.

> Attached is the patch and the list header, which is assumed to be in
> inc/list.h

Could we move it to <atheos/list.h>?  I can think of a few other places in the 
kernel and the drivers where a generic linked list implementation would be 
useful.

> I've tested this fairly thouroughly, and it works.

I have a few comments on the patch.  Hope you don't mind!

1. In add_thread_to_ready() you have

		for ( psTmp = LIST_FIRST( &g_sSysBase.ex_sFirstReady ); NULL != psTmp; psTmp 
= LIST_NEXT( psTmp, tr_psNext ) )
 		{
		...
			if ( LIST_NEXT( psTmp, tr_psNext ) == NULL )
				break;
		}

  It looks to me as though you call LIST_NEXT twice within the loop; once
  within the for() and then again at the bottom of the loop.  Should this not
  be called once, perhaps at the bottom of the loop E.g.

		for ( psTmp = LIST_FIRST( &g_sSysBase.ex_sFirstReady ); NULL != psTmp;  )
 		{
		...
			psTmp = LIST_NEXT( psTmp, tr_psNext );
			if ( psTmp == NULL )
				break;
		}

2. Possibly rename g_SysBase.ex_sFirstReady; to E.g. ex_ReadyListHead or
    similiar?  Don't worry about this one if it's going to get replaced by the
    new scheduler changes anyway.

> The second patch 
> will follow after I've finished testing it.   After that, my third patch
> makes all WaitQueue_s objects use the list primatives as well.  After
> that, I'll start making actual changes to the scheduler.

Those sound good to me.

-- 
Vanders
http://www.syllable.org
http://www.liqwyd.com

[Syllable-kernel] Scheduler cleanup

[Daniel G. <da...@fp...>]

Hi, all.

Here's the first in a series of cleanup patches for the scheduler.  This
is all (hopefully) preperatory to porting Con Kolivas' staircase
scheduler from the linux -ck kernel.  This is the scheduler I use on all
my linux boxes, and it's absolutely great for desktops.

At anyrate, I went about these first two patches backwards.  The first
patch introduces a new, typesafe list primative, and uses it for the
scheduler's thread queues.  This should give a slight increase in speed,
but it's mostly so I can play around with the queues with a known
correct set of list primatives.  These are the same list primatives I
used in the tmpfs driver.  The second one is documentation and some
cleanup.  I know, they should have been the other way around, but...

Attached is the patch and the list header, which is assumed to be in
inc/list.h

I've tested this fairly thouroughly, and it works.  The second patch
will follow after I've finished testing it.   After that, my third patch
makes all WaitQueue_s objects use the list primatives as well.  After
that, I'll start making actual changes to the scheduler.

Daniel

RE: [Syllable-kernel] Possible scheduler patch

[Daniel G. <da...@fp...>]

On Thu, 2005-01-13 at 09:21 +0000, Kristian Vandervliet wrote:
> Daniel Gryniewicz wrote:
> >
> > (If anyone's interested, I can post my patches...)
> 
> I'd like to take a look at them, just to see if there is anything we
> might be able to tweak.

Okay, attached.  Again, against CVS.

> > On a side note, has anyone gotten sshd working?  It would make
> > development, if not testing, easier.
> 
> I think some people were using it before, but no one has ever used it
> heavily.  I did have telnetd running on a box at one point but I don't
> remember what I did to get it all running.  These sorts of thing really
> need some work so they're easy to install (More important, actually
> work)  A working ftpd would be useful too.
> 

If I get a chance, I'll look into getting sshd working.  Obviously not
until I'm home, tho. :)

Has anyone looked into VNC?  That might be an even better solution...

Daniel

[Syllable-kernel] sshd/telnetd (was Re: Possible scheduler patch)

[Brent P. N. <me...@ot...>]

Quoting Kristian Vandervliet <kri...@xe...>:
> 
> Daniel Gryniewicz wrote:
> > 
> > On a side note, has anyone gotten sshd working?  It would make
> > development, if not testing, easier.
> 
> I think some people were using it before, but no one has ever used it
> heavily.  I did have telnetd running on a box at one point but I don't
> remember what I did to get it all running.

For what it's worth, here's the SUB tutorial on setting up telnetd on Syllable. 
If it's incorrect, please let me know.

    
http://www.other-space.com/sub/?section=Networking&tutorial=Enabling_the_telnet_server

-- 
Brent P. Newhall
http://brent.other-space.com/

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.

RE: [Syllable-kernel] Possible scheduler patch

[Kristian V. <kri...@xe...>]

Daniel Gryniewicz wrote:
> On Wed, 2005-01-12 at 19:26 +0000, Kristian Van Der Vliet wrote:
>> This scheme turned out to be tricky to implement, with no 
>> real benefit over the current scheme.  It suffered from a
>> "ping pong" problem where the dynamic priority would ping-pong
>> between two values as the  algorithm fought over itself.
>
> So, I fared a bit better than you did.  I could log in, and use by box
> normally, as far as I could tell.  However, if I tried to run a sync
> command, the box locked up, with nothing being printed in the kernel
> log.  This was repeatable: sync -> lockup.  Of course, neither the
> original kernel nor your hacked up one caused such a lockup.
> 
> Back to the drawing board, I guess.
> 
> (If anyone's interested, I can post my patches...)

I'd like to take a look at them, just to see if there is anything we
might be able to tweak.

> On a side note, has anyone gotten sshd working?  It would make
> development, if not testing, easier.

I think some people were using it before, but no one has ever used it
heavily.  I did have telnetd running on a box at one point but I don't
remember what I did to get it all running.  These sorts of thing really
need some work so they're easy to install (More important, actually
work)  A working ftpd would be useful too.

-- 
Vanders
http://www.syllable.org
http://www.liqwyd.com
 

_____________________________________________________________________
This message has been checked for all known viruses by Xenicom delivered through the MessageLabs Virus Control Centre. 

Re: [Syllable-kernel] Possible scheduler patch

[Anthony J. <ant...@bt...>]

> As a side note, this is probably a virus or spyware. Download ad-aware, 
> spybot and avg to get rid of it :). Unless you know what the process is, 
> of course.

Cheers, although I am pretty sure the process is our group policies being 
reapplied - the process is services.exe, and checking the system event log 
shows a log entry about a service reapplying the group policies at exactly 
the times it locks up. Prior to our admins fixing a configuration error 
relating to group policies it happened much more frequently, and logged an 
error - at least it believes it succeeds at the moment (I'm sure theres 
probably still something wrong though).

Anthony 

Re: [Syllable-kernel] Possible scheduler patch

[Jarret R <ja...@le...>]

Anthony Jacques wrote:
> Recently at work, under Windows XP I've been suffering from a process 
> that 99.9% of the time is sleeping, but about twice a day it kicks in 
> and uses 100% CPU for about 2 mins, and then goes back to sleep. 
> Unfortunately it starves most of the other processes, making my machine 
> practically unusable while its happening. Note that the process is 
> constantly running - its lifespan is since the last time the machine was 
> rebooted.

As a side note, this is probably a virus or spyware. Download ad-aware, 
spybot and avg to get rid of it :). Unless you know what the process is, 
of course.


Jarret

Re: [Syllable-kernel] Possible scheduler patch

[Daniel G. <da...@fp...>]

On Wed, 2005-01-12 at 19:26 +0000, Kristian Van Der Vliet wrote:
> This scheme turned out to be tricky to implement, with no real benefit over 
> the current scheme.  It suffered from a "ping pong" problem where the dynamic 
> priority would ping-pong between two values as the algorithm fought over 
> itself.  Certain threads were also very suseptable to what appeared to be 
> priority inversion E.g. the desktop thread at login would use a large amount 
> of CPU time, get down to a certain low priority and then hang, likely 
> deadlocked with another thread.  The testcase showed less of an improvement 
> also, so the net benefit was smaller.
> 
> I didn't get more testing done as I really need to rebuild my machine; it has 
> remnants of Glibc 2.3.3 testing on it which are playing havoc.  Once I've got 
> it back to a clean state I'll get back to fiddling with some different ideas.
> 

So, I fared a bit better than you did.  I could log in, and use by box
normally, as far as I could tell.  However, if I tried to run a sync
command, the box locked up, with nothing being printed in the kernel
log.  This was repeatable: sync -> lockup.  Of course, neither the
original kernel nor your hacked up one caused such a lockup.

Back to the drawing board, I guess.

(If anyone's interested, I can post my patches...)

On a side note, has anyone gotten sshd working?  It would make
development, if not testing, easier.

Daniel

Re: [Syllable-kernel] Possible scheduler patch

[Daniel G. <da...@fp...>]

On Wed, 2005-01-12 at 19:26 +0000, Kristian Van Der Vliet wrote:
> On Wednesday 12 January 2005 00:49, Daniel Gryniewicz wrote:
> > On Tue, 2005-01-11 at 21:32 +0000, Kristian Van Der Vliet wrote:
> >> One change I've considered is rather than trying to calculate the CPU
> >> time over the total life of the thread is to keep a count of the number
> >> of times a thread runs to the end of it's quantum.  If the quantum
> >> expires the counter increments by one.  If the thread blocks before the
> >> quantum expires the counter is decremented by one.  The penalty would
> >> then be applied according to the counter value.  Threads with a count of
> >> five would be scaled back by -10, a count of ten by -20, fifteen by -30
> >> etc. (The real numbers would probably require some tuning)  The advantage
> >> here is that the calculation is much easier.  It also solves the problem
> >> where threads which have spent a long time idle suddenly shoot to 100%
> >> CPU usage.  Under the current calculation based on the total life of the
> >> thread the CPU usage would still be calculated as a low percentage and no
> >> penalty imposed.  Under the new scheme a thread at 100% CPU would quickly
> >> acumulate a high count, and be penalized.
> >
> > Yes, that sounds generally better.  Another possibility is a decaying
> > average, which ends up being very similar to what you want to do.
> >
> > In general, the current method you used will help in the normal case of
> > a run-away thread.  It's much more unlikely, in my opinion, for a thread
> > to sleep for a long time and then go berzerk. :)
> >
> > Still, it'll likely be an improvement.  I'll try and get the kernel
> > built on my box here and get some ideas and testing in.
> 
> This scheme turned out to be tricky to implement, with no real benefit over 
> the current scheme.  It suffered from a "ping pong" problem where the dynamic 
> priority would ping-pong between two values as the algorithm fought over 
> itself.  Certain threads were also very suseptable to what appeared to be 
> priority inversion E.g. the desktop thread at login would use a large amount 
> of CPU time, get down to a certain low priority and then hang, likely 
> deadlocked with another thread.  The testcase showed less of an improvement 
> also, so the net benefit was smaller.
> 
> I didn't get more testing done as I really need to rebuild my machine; it has 
> remnants of Glibc 2.3.3 testing on it which are playing havoc.  Once I've got 
> it back to a clean state I'll get back to fiddling with some different ideas.
> 

Okay, I've knocked up an attempt at this too, but not yet tested it. (It
takes a bloody long time to checkout cvs on Syllable...  I guess we need
to do some serious speedups on AFS.)  I'll play around with it a bit
when I get home, and see if I have problems too.

Daniel

Re: [Syllable-kernel] Possible scheduler patch

[Anthony J. <ant...@bt...>]

> One change I've considered is rather than trying to calculate the CPU time
> over the total life of the thread is to keep a count of the number of 
> times a
> thread runs to the end of it's quantum.

(knowing you've now attempted this, and had an issue, so maybe considering 
leaving that sorta idea)...

Recently at work, under Windows XP I've been suffering from a process that 
99.9% of the time is sleeping, but about twice a day it kicks in and uses 
100% CPU for about 2 mins, and then goes back to sleep. Unfortunately it 
starves most of the other processes, making my machine practically unusable 
while its happening. Note that the process is constantly running - its 
lifespan is since the last time the machine was rebooted.

With a prioritisation based off time since the process/thread started a 
process like this would probably tend to starve things 'cos over the whole 
lifespan of the thread it would appear well behaved, even though it 
sometimes isnt. I suspect a strategy similar to the one above, or some 
decaying type algorithm would handle this scenario much better.

Just some food for thought

Anthony 

Re: [Syllable-kernel] Possible scheduler patch

[Kristian V. D. V. <va...@li...>]

On Wednesday 12 January 2005 00:49, Daniel Gryniewicz wrote:
> On Tue, 2005-01-11 at 21:32 +0000, Kristian Van Der Vliet wrote:
>> One change I've considered is rather than trying to calculate the CPU
>> time over the total life of the thread is to keep a count of the number
>> of times a thread runs to the end of it's quantum.  If the quantum
>> expires the counter increments by one.  If the thread blocks before the
>> quantum expires the counter is decremented by one.  The penalty would
>> then be applied according to the counter value.  Threads with a count of
>> five would be scaled back by -10, a count of ten by -20, fifteen by -30
>> etc. (The real numbers would probably require some tuning)  The advantage
>> here is that the calculation is much easier.  It also solves the problem
>> where threads which have spent a long time idle suddenly shoot to 100%
>> CPU usage.  Under the current calculation based on the total life of the
>> thread the CPU usage would still be calculated as a low percentage and no
>> penalty imposed.  Under the new scheme a thread at 100% CPU would quickly
>> acumulate a high count, and be penalized.
>
> Yes, that sounds generally better.  Another possibility is a decaying
> average, which ends up being very similar to what you want to do.
>
> In general, the current method you used will help in the normal case of
> a run-away thread.  It's much more unlikely, in my opinion, for a thread
> to sleep for a long time and then go berzerk. :)
>
> Still, it'll likely be an improvement.  I'll try and get the kernel
> built on my box here and get some ideas and testing in.

This scheme turned out to be tricky to implement, with no real benefit over 
the current scheme.  It suffered from a "ping pong" problem where the dynamic 
priority would ping-pong between two values as the algorithm fought over 
itself.  Certain threads were also very suseptable to what appeared to be 
priority inversion E.g. the desktop thread at login would use a large amount 
of CPU time, get down to a certain low priority and then hang, likely 
deadlocked with another thread.  The testcase showed less of an improvement 
also, so the net benefit was smaller.

I didn't get more testing done as I really need to rebuild my machine; it has 
remnants of Glibc 2.3.3 testing on it which are playing havoc.  Once I've got 
it back to a clean state I'll get back to fiddling with some different ideas.

-- 
Vanders
http://www.syllable.org
http://www.liqwyd.com

Re: [Syllable-kernel] Possible scheduler patch

[Daniel G. <da...@fp...>]

On Tue, 2005-01-11 at 21:32 +0000, Kristian Van Der Vliet wrote:
> 
> One change I've considered is rather than trying to calculate the CPU time 
> over the total life of the thread is to keep a count of the number of times a 
> thread runs to the end of it's quantum.  If the quantum expires the counter 
> increments by one.  If the thread blocks before the quantum expires the 
> counter is decremented by one.  The penalty would then be applied according 
> to the counter value.  Threads with a count of five would be scaled back by 
> -10, a count of ten by -20, fifteen by -30 etc. (The real numbers would 
> probably require some tuning)  The advantage here is that the calculation is 
> much easier.  It also solves the problem where threads which have spent a 
> long time idle suddenly shoot to 100% CPU usage.  Under the current 
> calculation based on the total life of the thread the CPU usage would still 
> be calculated as a low percentage and no penalty imposed.  Under the new 
> scheme a thread at 100% CPU would quickly acumulate a high count, and be 
> penalized.

Yes, that sounds generally better.  Another possibility is a decaying
average, which ends up being very similar to what you want to do.

In general, the current method you used will help in the normal case of
a run-away thread.  It's much more unlikely, in my opinion, for a thread
to sleep for a long time and then go berzerk. :)

Still, it'll likely be an improvement.  I'll try and get the kernel
built on my box here and get some ideas and testing in.

> 
> I'll apply your patches tommorow and I'll try out my counter scheme and let 
> you all know how that works out, too.
> 

Thanks.

Daniel

Re: [Syllable-kernel] Possible scheduler patch

[Kristian V. D. V. <va...@li...>]

On Tuesday 11 January 2005 17:59, Daniel Gryniewicz wrote:
> Overall, this looks quite good.  Nice and simple, and straight forward.
> It's quite likely that the actual dynamic priority calculation and
> quantum sizes could be tweaked for better fairness/whatever, but that's
> easy to do.  Maybe a macro/function to calculate quantum, so it's easy
> to change globally?
>
> One note: in the dynamic priority calculation, you check that the
> reduction won't leave the priority space.  I suspect what you want is
> this:
>
> <snip>
>
> Otherwise, nothing will ever get below 85, and more well-behaved
> processes will get penalized worse than badly behaved processes (they'll
> get to -85, but the bad ones will only get to -50)

Sounds like a good idea to me.

> Attached is my few suggestions for changes.  It's against current CVS,
> so you won't be able to apply it on top of your changes.  Basically, it
> makes the above change, adds a macro for GET_QUANTUM, and adds
> documentation for recalculate_dynamic_priority().

Thanks.

One change I've considered is rather than trying to calculate the CPU time 
over the total life of the thread is to keep a count of the number of times a 
thread runs to the end of it's quantum.  If the quantum expires the counter 
increments by one.  If the thread blocks before the quantum expires the 
counter is decremented by one.  The penalty would then be applied according 
to the counter value.  Threads with a count of five would be scaled back by 
-10, a count of ten by -20, fifteen by -30 etc. (The real numbers would 
probably require some tuning)  The advantage here is that the calculation is 
much easier.  It also solves the problem where threads which have spent a 
long time idle suddenly shoot to 100% CPU usage.  Under the current 
calculation based on the total life of the thread the CPU usage would still 
be calculated as a low percentage and no penalty imposed.  Under the new 
scheme a thread at 100% CPU would quickly acumulate a high count, and be 
penalized.

I'll apply your patches tommorow and I'll try out my counter scheme and let 
you all know how that works out, too.

-- 
Vanders
http://www.syllable.org
http://www.liqwyd.com

Re: [Syllable-kernel] Possible scheduler patch

[Daniel G. <da...@fp...>]

On Tue, 2005-01-11 at 18:55 +0000, Kristian Van Der Vliet wrote:
> On Tuesday 11 January 2005 17:31, Daniel Gryniewicz wrote:
> > On Tue, 2005-01-11 at 16:46 +0000, Kristian Vandervliet wrote:
> > > I've played around with the scheduler today, to see if I could
> > > find a solution to the thread-starvation problem.  I think I may
> > > have a workable solution, which although it is not a complete
> > > rewrite as an O(1) algorithm, it does fix the problem.
> >
> > I'll look at it in more detail a bit later, but in the meantime, could I
> > suggest unified diffs (diff -u)?  They're *much* easier to read as a
> > diff than context diffs are...
> 
> Sorry about that.  The diff was just a quick job to give everyone else 
> something to check over.
> 

That's okay.  I just applied it to my cvs checkout and re-diffed. :)

Daniel

Re: [Syllable-kernel] Possible scheduler patch

[Kristian V. D. V. <va...@li...>]

On Tuesday 11 January 2005 17:31, Daniel Gryniewicz wrote:
> On Tue, 2005-01-11 at 16:46 +0000, Kristian Vandervliet wrote:
> > I've played around with the scheduler today, to see if I could
> > find a solution to the thread-starvation problem.  I think I may
> > have a workable solution, which although it is not a complete
> > rewrite as an O(1) algorithm, it does fix the problem.
>
> I'll look at it in more detail a bit later, but in the meantime, could I
> suggest unified diffs (diff -u)?  They're *much* easier to read as a
> diff than context diffs are...

Sorry about that.  The diff was just a quick job to give everyone else 
something to check over.

-- 
Vanders
http://www.syllable.org
http://www.liqwyd.com

Re: [Syllable-kernel] Possible scheduler patch

[Daniel G. <da...@fp...>]

Overall, this looks quite good.  Nice and simple, and straight forward.
It's quite likely that the actual dynamic priority calculation and
quantum sizes could be tweaked for better fairness/whatever, but that's
easy to do.  Maybe a macro/function to calculate quantum, so it's easy
to change globally?

One note: in the dynamic priority calculation, you check that the
reduction won't leave the priority space.  I suspect what you want is
this:

    if( nRunTotal > 50 && nRunTotal <= 70 )
    {
        psThread->tr_nDynamicPriority -= 15; 
    }
    else if( nRunTotal > 70 && nRunTotal <= 90 )
    {
        psThread->tr_nDynamicPriority -= 35; 
    }
    else if( nRunTotal > 90 )
    {
        psThread->tr_nDynamicPriority -= 50; 
    }

    if (psThread->tr_nDynamicPriority <= -100)
    {   
        psThread->tr_nDynamicPriority = -99;
    }

Otherwise, nothing will ever get below 85, and more well-behaved
processes will get penalized worse than badly behaved processes (they'll
get to -85, but the bad ones will only get to -50)

Attached is my few suggestions for changes.  It's against current CVS,
so you won't be able to apply it on top of your changes.  Basically, it
makes the above change, adds a macro for GET_QUANTUM, and adds
documentation for recalculate_dynamic_priority().

Daniel

On Tue, 2005-01-11 at 16:46 +0000, Kristian Vandervliet wrote:
> I've played around with the scheduler today, to see if I could
> find a solution to the thread-starvation problem.  I think I may
> have a workable solution, which although it is not a complete
> rewrite as an O(1) algorithm, it does fix the problem.
> 
> I've modified the scheduler to use "dyanmic" priorities for each
> thread.  The dynamic priority is calculated for each thread
> every time the thread execution is completed (E.g. the thread is
> pre-empted).  The algorithm simply works out the amount of CPU
> time being used as a percentage, based on the time the thread
> was created (It's total life-time) and the total CPU time it has
> used so far.  If the percentage is deemed to be too high, it's
> dynamic priority is lowered, using a sliding scale.  Well behaved
> threads which use less than 50% CPU time are re-issued with their
> "static" priority, which is the priority given to the thread at
> creation.
> 
> The two scheduler functions which are involved in thread selection,
> add_thread_to_ready() and select_thread(), use the dynamic priority
> instead of the static priority when they are handling threads.
> 
> In this way CPU-bound threads which do not block can not longer
> choke of lower priority threads, which may be bloking often.  The
> dynamic priority is scaled back until the thread releases CPU time
> for other threads, and it slips back in the list of runable threads.
> 
> In addition, the quantum of every thread is calculated, based on
> the threads static priority.  Higher priority threads get a longer
> quantum.  Essentially this allows heavily CPU bound tasks to still
> get more CPU time, but it is no longer at the total expense of the
> other threads.
> 
> An experimental kernel can be downloaded from 
> http://www.liqwyd.com/syllable/kernel.zip  Unzip it and copy it to
> /system/  You might want to back up your original (known good)
> kernel first!
> 
> I have also written a very small test program which demonstrates
> the problem on the old kernel, and the bevahour of the new kernel.
> It is available from http://www.liqwyd.com/syllable/sched_test.zip 
> The source and binary are included.  The binary takes one optional
> argument, "-s"  With no arguments the program creates two threads;
> one to print info and the second which sits in a very tight loop,
> eating your CPU.  The tight-loop thread is created at a priority of
> 150 E.g realtime.  If you pass -s to the test binary, the thread
> will sleep for one second per iteration.
> 
> If you run the test on an existing kernel, your machine will
> essentially become non-responsive.  This is because the CPU bound
> thread gets 100% of the CPU at a higher priority than the appserver.
> If you run the test on the patched kernel, the thread will be
> dynamically scalled back.  It will still claim as much CPU as it
> can, but it can no longer starve other threads.  If you run the test
> on the patched kernel with the -s option, you will see that the
> dynamic priority is never altered as the thread is "well behaved"
> 
> The kernel patch is attached.  I would appreciate feedback and
> especially any improvements.  I do not intend to apply these patches
> to the mainline kernel without plenty of testing, and preferably
> discussion.  Note that the experimental kernel is the stock CVS
> kernel with the scheduler patches, but none of Arno's recent patches.
> No doubt we'll merge our patches soon.
> 
> -- 
> Vanders
> http://www.syllable.org
> http://www.liqwyd.com
> 
> 
> 
> _____________________________________________________________________
> This message has been checked for all known viruses by Xenicom delivered through the MessageLabs Virus Control Centre. 

Re: [Syllable-kernel] Possible scheduler patch

[Daniel G. <da...@fp...>]

On Tue, 2005-01-11 at 16:46 +0000, Kristian Vandervliet wrote:
> I've played around with the scheduler today, to see if I could
> find a solution to the thread-starvation problem.  I think I may
> have a workable solution, which although it is not a complete
> rewrite as an O(1) algorithm, it does fix the problem.

I'll look at it in more detail a bit later, but in the meantime, could I
suggest unified diffs (diff -u)?  They're *much* easier to read as a
diff than context diffs are...

Daniel

[Syllable-kernel] Possible scheduler patch

[Kristian V. <kri...@xe...>]

I've played around with the scheduler today, to see if I could
find a solution to the thread-starvation problem.  I think I may
have a workable solution, which although it is not a complete
rewrite as an O(1) algorithm, it does fix the problem.

I've modified the scheduler to use "dyanmic" priorities for each
thread.  The dynamic priority is calculated for each thread
every time the thread execution is completed (E.g. the thread is
pre-empted).  The algorithm simply works out the amount of CPU
time being used as a percentage, based on the time the thread
was created (It's total life-time) and the total CPU time it has
used so far.  If the percentage is deemed to be too high, it's
dynamic priority is lowered, using a sliding scale.  Well behaved
threads which use less than 50% CPU time are re-issued with their
"static" priority, which is the priority given to the thread at
creation.

The two scheduler functions which are involved in thread selection,
add_thread_to_ready() and select_thread(), use the dynamic priority
instead of the static priority when they are handling threads.

In this way CPU-bound threads which do not block can not longer
choke of lower priority threads, which may be bloking often.  The
dynamic priority is scaled back until the thread releases CPU time
for other threads, and it slips back in the list of runable threads.

In addition, the quantum of every thread is calculated, based on
the threads static priority.  Higher priority threads get a longer
quantum.  Essentially this allows heavily CPU bound tasks to still
get more CPU time, but it is no longer at the total expense of the
other threads.

An experimental kernel can be downloaded from 
http://www.liqwyd.com/syllable/kernel.zip  Unzip it and copy it to
/system/  You might want to back up your original (known good)
kernel first!

I have also written a very small test program which demonstrates
the problem on the old kernel, and the bevahour of the new kernel.
It is available from http://www.liqwyd.com/syllable/sched_test.zip 
The source and binary are included.  The binary takes one optional
argument, "-s"  With no arguments the program creates two threads;
one to print info and the second which sits in a very tight loop,
eating your CPU.  The tight-loop thread is created at a priority of
150 E.g realtime.  If you pass -s to the test binary, the thread
will sleep for one second per iteration.

If you run the test on an existing kernel, your machine will
essentially become non-responsive.  This is because the CPU bound
thread gets 100% of the CPU at a higher priority than the appserver.
If you run the test on the patched kernel, the thread will be
dynamically scalled back.  It will still claim as much CPU as it
can, but it can no longer starve other threads.  If you run the test
on the patched kernel with the -s option, you will see that the
dynamic priority is never altered as the thread is "well behaved"

The kernel patch is attached.  I would appreciate feedback and
especially any improvements.  I do not intend to apply these patches
to the mainline kernel without plenty of testing, and preferably
discussion.  Note that the experimental kernel is the stock CVS
kernel with the scheduler patches, but none of Arno's recent patches.
No doubt we'll merge our patches soon.

-- 
Vanders
http://www.syllable.org
http://www.liqwyd.com



_____________________________________________________________________
This message has been checked for all known viruses by Xenicom delivered through the MessageLabs Virus Control Centre. 

Re: [Syllable-kernel] IO operations

[Kristian V. D. V. <va...@li...>]

On Wednesday 15 December 2004 17:17, Daniel Gryniewicz wrote:
> On Tue, 2004-12-14 at 19:11 -0800, Nathanael Bettridge wrote:
> > IOPL is a chiplevel function. It has no idea what root
> > even is. It sees only the three rings, and in flat
> > paging mode, AFAIK (and definitely in current
> > syllable), only ring 0 (kernel) and 3 (user) are
> > really relevant. In other words, if its allowed in
> > user mode, it can be done, regardless of the user
> > account. It might not be easy to get at via libc or
> > whatever, but it can still be done. To do things
> > properly, we'd have to either shunt hw-accessing code
> > to ring 1 or 2, or have it all done via syscalls.
> >
> > Disclaimer: of course, I could be wrong ;)
>
> No, it's still easy.  IOPL is included in the saved context state when
> transitioning from 3 -> 0 (ie on a syscall or interrupt).  Thus, it's
> restored during the 0 -> 3 transition (ie, on iret).  Since Syllable,
> like all Unix kernels, stores this state on a per-process basis, it's
> easy to enable/disable IOPL on a per-process (or per-user, like most
> Unix does) basis.  Obvsiously, Syllable's not currently doing this, but
> just allowing all processes to have IOPL enabled.  This doesn't mean it
> couldn't be done.
>
> Most likely, we want to enable IOPL on the appserver, and deny it to
> anything else, by default.
>
> Linux does this based on it's fine-grained Capabilities.

Sorry for jumping in late, just got back from holidays.  IOPL should rely on 
the current users ACL capabilities once we have SylSec in place.  That gives 
use full control over who or what gets to mess with IO space; in theory only 
the appserver should ever require that IOPL is enabled, but that's simple to 
deal with once we have ACL's.

At this point there isn't much reason to worry about it, other than doing the 
groundwork to enable or disable IOPL on a process.  If anyone wants to try 
doing IO from user-space on Syllable it'll only mess up there own system, and 
I don't think we need to worry about worms right now!

Any IOPL patches gladly accepted!

-- 
Vanders
http://www.syllable.org
http://www.liqwyd.com