Re: Tickless NetBSD with high-resolution timers GSOC project

Ping.
It would be great if I could get some input on this project. Thanks!

Regards,
Dorjoy

On Fri, Mar 14, 2025 at 12:40 AM Dorjoy Chowdhury
<[email protected]> wrote:
>
> 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