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
