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 <dorjoychy...@gmail.com> 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
