Re: [PATCH 11/13] hrtimer: turn hrtimers into range timers

[Peter Zijlstra <peterz@infradead.org>]

On Tue, 2008-09-02 at 13:08 +0200, Peter Zijlstra wrote:
> On Tue, 2008-09-02 at 10:22 +0200, Peter Zijlstra wrote:
> > On Mon, 2008-09-01 at 16:08 -0700, Arjan van de Ven wrote:
> > 
> > > @@ -847,7 +847,8 @@ static void enqueue_hrtimer(struct hrtimer *timer,
> > >                  * We dont care about collisions. Nodes with
> > >                  * the same expiry time stay together.
> > >                  */
> > > -               if (timer->expires.tv64 < entry->expires.tv64) {
> > > +               if (hrtimer_get_expires_tv64(timer) <
> > > +                               hrtimer_get_expires_tv64(entry)) {
> > >                         link = &(*link)->rb_left;
> > >                 } else {
> > >                         link = &(*link)->rb_right;
> > 
> > On Mon, 2008-09-01 at 16:13 -0700, Arjan van de Ven wrote:
> > 
> > > +static inline void hrtimer_set_expires_range(struct hrtimer *timer, ktime_t time, ktime_t delta)
> > > +{
> > > +       timer->_softexpires = time;
> > > +       timer->_expires = ktime_add_safe(time, delta);
> > > +}
> > 
> > > @@ -241,10 +259,19 @@ static inline ktime_t hrtimer_get_expires(const struct hrtimer *timer)
> > >  	return timer->_expires;
> > >  }
> > >  
> > > +static inline ktime_t hrtimer_get_softexpires(const struct hrtimer *timer)
> > > +{
> > > +	return timer->_expires;
> > > +}
> > 
> > Somehow the function is called softexpires, but returns the hard expire
> > time...
> > 
> > >  static inline s64 hrtimer_get_expires_tv64(const struct hrtimer *timer)
> > >  {
> > >  	return timer->_expires.tv64;
> > >  }
> > > +static inline s64 hrtimer_get_softexpires_tv64(const struct hrtimer *timer)
> > > +{
> > > +	return timer->_softexpires.tv64;
> > > +}
> > >  
> > >  static inline s64 hrtimer_get_expires_ns(const struct hrtimer *timer)
> > >  {
> > 
> > > @@ -1309,7 +1309,7 @@ void hrtimer_interrupt(struct clock_event_device *dev)
> > >  
> > >  			timer = rb_entry(node, struct hrtimer, node);
> > >  
> > > -			if (basenow.tv64 < hrtimer_get_expires_tv64(timer)) {
> > > +			if (basenow.tv64 < hrtimer_get_softexpires_tv64(timer)) {
> > >  				ktime_t expires;
> > >  
> > >  				expires = ktime_sub(hrtimer_get_expires(timer),
> > 
> > I might be missing something, but this code only looks at the leftmost
> > timer, and we're indexed on the hard expire time, which might be rather
> > far to the right of here.
> > 
> > This means that esp for those timers for which we can save most we're
> > least likely to do so because we'll plain not see them.
> 
> What you need is a data structure that supports stabbing queries on
> overlapping intervals, such like a Priority Search Tree.
> 
> If I'm not mistaken, then the augmented Red-Black tree from the EEVDF
> paper is identical to PST [*].
> 
> This data-structure adds a Heap property to each RB-node, allowing one
> to search the tree on a different property.
> 
> So what you can do in this case, is index the RB-tree on the soft
> expire, and index the heap on the hard expire.
> 
> Then you can find the leftmost hard expire by traversing the tree using
> the heap property - and program the clock-event using that time.

Even better, in the implementations below, the leftmost heap propery can
be read from the root node, so if, as with the clock event, you don't
actually need the entry itself, but just the time, you can find it by
reading the heap propery of the root node.

Which saves a whole log(n) tree traversal ;-)

Same goes for reprogramming the clock event on insert and delete, just
check the root heap property for change.

> And you can search for soft expired entries using the RB-tree like we do
> now.
> 
> 
> [*] Fabio implemented it on top of the linux RB-tree for their wf2q+
> implementation that they used for their BFQ I/O scheduler:
> 
> http://feanor.sssup.it/~fabio/linux/wfq/
> 
> And I borrowed their implementation for my scheduler work:
> 
> http://programming.kicks-ass.net/kernel-patches/sched-eevdf/sched-eedf.patch
> 
> 
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/