Re: tickless GSoc queries.

["Mathew, Cherry G.*" <c%bow.st@localhost>]

Hello,

I'm responding to these queries together, as I they are both within the
GSoc context, and I just saw them in the archives now.

I assume you've read through Taylor's post here:
https://wiki.netbsd.org/projects/project/tickless/

Since he's listed as the mentor for this project, I'll leave it to him
to respond if at all, regarding admin and GSoc related issues.

I'll leave some technical comments based on my own investigation of the
technical aspects of this project.

See inline below:

>>>>> "SD" == SD Asif Hossein <s.dah.ingularity47%gmail.com@localhost> writes:


[...]

    SD> General Idea: In this project I am expected to implement the
    SD> Tickless timer (Most probably dynamic tick or completely
    SD> tickless or both) using the High-Resolution timers. 

Can you explain what you mean by "dynamic tick" and how that relates to
"completely tickless" ?

    SD> I have to implement the High-resolution timer support for that,
    SD> as NetBSD's High-Resolution timer is still in development as far
    SD> as I know. 

There is hardware that has "high resolution timer" on several platforms
with support. For eg: even on the humble PC architecture, you can in
theory make the i8254 timer chip interrupt at anything upto the NTSC
resolution (which is slightly above a MHz, iirc). That is less of a
problem in this project - the hardware aspects of this project will
probably be faced when you are ready to integrate the code and get it to
run on the various platforms we support - and there are various port
masters who can assist you with that.

    SD> I also have to implement the architecture independent APIs to
    SD> adopt the configuration, change all the functions that use the
    SD> periodic timer, hardclock to use the tickless timer and make
    SD> them provide service/schedule when needed finally converting all
    SD> the software subsystems to tickless so that they avoid periodic
    SD> work altogether; increasing power consumption of NetBSD.

This is the meat of the project. I'd encourage you to look at
src/sys/kern_clock.c:hardclock() - which is the callback that the
current system calls at frequency hz (which is normally 100Hz).

Have a look at the following manual pages:

hardclock(9)
hz(9)
timecounter(9)
csf(9)
callout(9)

You can access them by going to https://man.netbsd.org and entering the
keywords in the corresponding text boxes and looking them up (assuming
you don't have a NetBSD system handy).

One of the first things you'll need to do is to define the kernel's
understanding of time. Right now, this is in the form of "tick"s - ie;
the number of ticks that have elapsed, or should elapse after/before an
event of interest. A tick event is assumed to happen once every 1/hz
seconds, and the event corresponds to the function hardclock() being
called.

In order to go tickless, it would be best to change the unit of kernel
timekeeping from ticks, which are very low resolution, to begin with, to
a more absolute and fixed resolution such as bintime(9) - it is defined
in sys/time.h as so:

struct bintime {
        time_t  sec;
        uint64_t frac;
};

As you can see, this is far more accurate than any physical timer device
is capable of (the fraction has a resolution of 1/2 ^ 64 of a second -
which is a *lot*) - so you'll also need to figure out a way to represent
how to approximate the resolution. This approximation is called
"epsilon" in the kernel (read the comments around kern/kern_condvar.c
where bintime(9) is used in cv(9) variants such as cv_timedwaitbt(...)

Not only does epsilon help to bring down our resolution of consideration
to what the hardware is realistically capable of, it also helps us to
understand how to "cluster" together two event requests which are
fractionally closer together. 

The key problem here has to do with callout(9) being our workhorse for
scheduling future callbacks within the kernel.

If we end up scheduling two callout(9) callbacks back-to-back to handle
those events, we'll end up being very busy in the kernel, handling tiny
fractionally separated events. Instead, we can just pretend the events
happened together within a span of "epsilon", and then call the
callback functions, which can decide whether this is a problem for them
or not.

This leads us to Taylor's milestones:

1. "... We need another data structure that provides good performance
for high-resolution sleeps without hurting the performance of the
existing call wheel for existing applications."

The main question here is viewable from the point of view of deciding
when to schedule the next callback. In order to do this, we need to look
up the list of pending scheduled events, make the approximations such as
the above, and then decide what the *nearest* bintime timestamp that
makes sense to be interrupted, so that we can run the next callback
is. All this needs to happen very efficiently, and Taylor's comment is
that the current implementation is efficient for an epsilon of 1/hz, but
not when  your epsilon value goes down to finer resolutions.

This might be a good time to go look at how other projects that have a
tickless kernel manage this problem.

2. "Design a machine-independent high-resolution timer device API ... "

This requires understanding of the timecounter(9) api (see:
kern/kern_tc.c) and how the underlying hardware of the platform you are
developing for works. Once you understand both, it would make sense to
try to come up with an API that is also able to provide callbacks at
arbitrary timestamps. These timers don't have to be complicated - they
should just be able to guarantee that the hardware will interrupt within
an accuracy of "epsilon", at the requested absolute time.

3. "Convert all the functions of the periodic 10 ms timer, hardclock, to
   schedule activity only when needed."

This one is a bit more involved - you'll need to go into each of the
functions called from within hardclock() to understand if they assume
they will be called at frequency hz, and if so, how to make them not
make that assumption. It's a lot of scope to discuss in this email, but
that's the high level gist of it.

4. "Convert the various software subsystems that rely on periodic timer
   interrupts every tick, or every second, via callout(9) ..."

I'm not a 100% sure what the difference here with 3. is, but my take is
that if there are bits of code that don't use callout(9) but directly
hook into the platform timer interrupt, they should be converted to use
callout(9) instead. This might be an integration related task (see my
comments above, re: port masters, etc.).


[...]

    SD> Therefore, I am very interested to contribute to this project. I
    SD> am fairly new to Operating System dev and developed a hobby OS
    SD> for learning purposes. This will be a very interesting and
    SD> challenging journey for me. I hope you will find me capable 😃.

Please note that this is a public mailing list - you seem to be
addressing it as if it is in a private context - I thought I would point
out that it isn't. All the emails here are archived on the public
internet www here:

http://mail-index.netbsd.org/tech-kern/

>>>>> "DC" == Daniel Choo <dchoo%umich.edu@localhost> writes:

    DC> Hello!

Hello Daniel - I hope you read the above comments.

    DC> I'm Daniel, a student at the University of Michigan. I'm
    DC> interested in submitting a proposal for working on NetBSD for
    DC> this year's Google Summer of Code, more specifically the high
    DC> resolution timers project with Taylor Campbell.

Please see my comments above specifically referencing Taylor's
comments. I'll leave it to him to respond (or not).

    DC> I have a basic familiarity with C/C++ and operating systems
    DC> since I'm a TA for our Operating Systems course at my
    DC> school. I've also always wanted to work on open source kernels
    DC> so this sounds really interesting!

Basic familiarity is probably insufficient to take on this project - not
only will you need to understand C itself, but you'll need to have an
understanding of how the compiler translates code to the underlying
hardware (for eg: how volatile variables work and why), how concurrent
state machines interact, and finally how at least one CPU
architecture and corresponding platform works, in detail. This is still
possible to do on the job, but it will require you to be pretty much
full time.

    DC> I was wondering if it'd be possible to start on some easier
    DC> tasks for this and submit a commit or two to see if I'd be a
    DC> good fit/give me a better understanding of this project? If so,
    DC> could someone suggest a few places where I could start looking?

I had posted a patches to start moving hardclock() callees to callout(9)
scheduled callbacks, as a starting point to investigate what would fall
apart.

One really useful thing you could do, would be to try to apply that
patch to a -current source, build a new kernel, boot it up, and try to
stress it out and see what shakes out. At the very least, you will have
gone through a very basic dev/testing cycle that all of us go through
when we develop for the kernel.

http://mail-index.netbsd.org/tech-kern/2024/03/20/msg029505.html

I hope this is useful.

Many Thanks,
-- 
Math/(~cherry)