Tickless NetBSD with high-resolution timers GSOC project

[Dorjoy Chowdhury <dorjoychy111%gmail.com@localhost>]

Hi,
Hope everyone is doing well. I am Dorjoy. I am from Bangladesh. I am
interested in the Tickless NetBSD with high-resolution timers[1]
project. I wanted to know if this project is still up for grabs and if
a mentor is available for this project. I would like to start to
discuss this one and see if I can contribute to netbsd.

I have been looking into the related code (kern_timeout.c etc) and the
call wheel based data structure (the paper referenced in
kern_timeout.c as well) for the last few days.

1. The call wheel based data structure works really well because there
is a periodic timer interrupt and the sleep durations are based on
those ticks. Insertion, deletion into the hierarchical call wheel is
basically O(1). When there is a periodic timer interrupt, we basically
move ahead one tick on the wheel and call any callbacks (or move
timers to the next level) which is O(number of callbacks). For high
resolution timer, we won't have any periodic timer at that resolution.
So I believe we will need to just schedule an interrupt at the "next"
event. As we cannot use the call wheel based data structure here
(because we can't move one tick to the next in this case) we will need
to be able to efficiently insert, delete and find the next timer. I
looked at how linux does it a little bit (include/linux/hrtimer.h,
include/linux/hrtimer_types.h, include/linux/hrtimer_defs.h,
include/linux/timerqueue_types.h) and it seems like the ktime_t is a
signed 64 bit value (nanosecond resolution) and red-black tree is
being used as the data structure. I believe we can do the same for
netbsd. Maybe 64 bit unsigned value (I am not sure if signed is
needed) for the resolution at nanosecond (as opposed to the "tick"
used now in kern_timeout.c) and a red-black tree for storing the
timers. That would mean insertion, deletion, finding "next" would be
O(log n). I don't yet have a complete picture of what the code would
look like and how these interrupts are scheduled/work in general but
it makes sense to have the data structure discussion first.

2. I don't know yet what the API should look like but I believe they
should be similar to what we already have now like the functions in
kern_timeout.c. So that we can replace the users of the kern_timeout.c
functions, right?

3 and 4 depend on the above so let's discuss how 1 and 2 should be like first.

Does the above description of 1 and 2 look like a reasonable proposal
for the upcoming GSOC and is there a mentor available for this
project? Please let me know if you have any suggestion on the data
structure / API so that we can discuss and be certain what high
resolution timers should look like in netbsd. Thanks!

Regards,
Dorjoy