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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1220363227.8609.56.camel@twins>
Date:	Tue, 02 Sep 2008 15:47:07 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Arjan van de Ven <arjan@...radead.org>
Cc:	linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org,
	dwmw2@...radead.org, drepper@...hat.com, mingo@...e.hu,
	tglx@...x.de
Subject: Re: [PATCH 11/13] hrtimer: turn hrtimers into range timers

On Tue, 2008-09-02 at 06:05 -0700, Arjan van de Ven wrote:
> On Tue, 02 Sep 2008 10:22:12 +0200
> Peter Zijlstra <peterz@...radead.org> 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...
> 
> argh that's what you get if you split a patch into a series by hand ;-(
> 
> > > 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.
> 
> you're missing a little detail ;)
> 
> yes we start from left to right, and we stop once we find a timer that
> we can't fire anymore. The thing that you missed is that any timer
> after that (even if we could fire it now) will just be fired when the
> timer we stopped on fires.. so it'll still group them around those
> timers that are otherwise ungroupable.
> (it's not perfect by any means but it works ;-)

Gah, right. How about adding the following:

/*
 * The immediate goal is minimizing wakeups, not running
 * timers at the earliest interrupt after their soft expiration.
 * This allows us to avoid using a Priority Search Tree,
 * which can answer a stabbing querry for overlapping
 * intervals and instead use the simple BST we already have.
 * We don't add extra wakeups by delaying timers that are
 * right-of a not yet expired timer, because that timer will
 * have to trigger a wakeup anyway.
 */



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/